基于遺傳算法和虛擬化技術的網絡配置方法*

孫美衛

(泉州經貿職業技術學院信息技術系，福建 泉州 362000)

引言

近幾年，除了網絡數據激增之外，以大數據為基礎的數據分析也顯著增加.大數據處理有著極大的容量要求，這為通信開銷帶來了很大負擔，因為在利用遠程計算機資源時需要進行數據遷移[1].此外，頻繁的數據遷移也會產生安全問題.在分析和處理大數據時，經常遇到這樣的問題，即：大規模計算機被集中在某個特定的位置(如數據中心)，而數據附近的計算機資源可能不足以分析大容量數據.

光虛擬網絡[2]是解決上述問題的重要手段，目前已有一些光虛擬網絡構建方法.如利用波分復用(Wavelength Division Multiplexing, WDM)[3,4]技術滿足速率和容量需求的光網絡構建方法.然而，總體來看，雖然網絡鏈路上實施了高速WDM，但電信號和光信號的轉換，以及節點上的跨層處理是數據傳輸的瓶頸.為了解決此問題，諸多學者提出了相應的措施，如羅廣俊等[5]人提出采用光交叉連接(Optical cross connect, OXC)技術，通過數據包傳輸的光切換來解決[5]，也就是任何節點間數據發送和數據接收的傳輸路徑均使用的光波長進行標記.

Halabi 等人[6]應用IP和光信號特性進行網絡虛擬化.由于光信號的不同波長不會對彼此產生干擾.因此，對于不同網絡使用不同波長，進行各自波長的操作，可使得在相同的物理鏈路上可創建多個不同的虛擬鏈路.其優點是能夠通過光切換技術，降低路徑中數據包傳輸時的IP處理數量.

Tode等[7]提出了“阿米巴網絡架構”，該架構使用光波長路徑將分散于不同地理位置的節點組合在一起，并向該節點集合賦予路由器功能.通過OXC實現光傳輸層中的高速交換處理，以實現節點集合的互連.其優點是降低IP處理數量，通過在IP層的網絡規模簡并降低路由處理的復雜性.另一方面，僅通過識別阿米巴節點就可對拓撲的處理能力進行自由調整，不需要對物理設施進行加強.

以往的大數據分析方法圍繞著幾個龐大的數據中心進行集中式計算.本文提出了基于細粒度的云計算，在分布式并行計算環境中進行大數據分析.假設分布式計算資源，建立一個低延遲的計算環境，其中計算機資源位于用戶附近.該方法通過降低延遲拉近計算機資源與大數據的距離，來實現對所分配的計算機資源在距離方面的公平性.最后，測試所提算法的用戶和供應商的公平性指數，以及光波長路徑總數的變化情況.

1 光虛擬網絡配置方法

基于計算機資源以細粒度[8]分布，提出建立一個低延遲的邊緣計算環境，其中計算機資源被放置于用戶附近.從網絡基礎設施的角度，旨在提升計算機資源之間的鄰近度.在大數據方面，通過引入一個光虛擬網絡，降低用戶將數據傳輸到計算機資源的延遲，該虛擬網絡應用了光波長路徑技術，以實現IP級網絡拓撲的自由更改[9].本文計算環境結構如圖1所示,計算機資源的所有者為小規模供應方：各個企業和個人被放置于一個公用通信運營商所提供的網絡基礎設施上.

圖1 提出的計算環境的結構

1.1 網絡模型和控制流程

研究的網絡模型使用兩種類型的終端主機，分別稱為“用戶”和“供應商”，連接到物理光網絡的每個節點.用戶請求大數據分析計算機資源,供應商向用戶提供計算機資源.此外，計算機資源表明計算機的總體計算力，并概括出CPU和內存容量等性能參數.

控制器和所有用戶、供應商相互連接，隨時收集來自網絡中每個節點的流量信息，并接收用戶的計算機資源請求和供應商的計算機資源供給.控制器通過使用一個遺傳算法[10](Genetic Algorithm, GA)，確定任意兩個節點之間光波長路徑的最優配置，以及能夠滿足每個用戶需求的計算機資源分配，并將信息傳輸到網絡所有節點和用戶.其中，信息節點通過設定與相應節點間的光波長路徑，構建出一個光虛擬網絡.其后，供應商的計算機資源被分配給用戶，以供其對大數據的分析和處理.

在真實的操作環境中，控制器接收到請求計算機資源的用戶組，并為其執行該GA算法.此時，除了正在使用的計算機資源之外，其余可用計算機資源，被視為供應商的可分配資源容量的初始數值.出于效率考慮，本文對該問題應用了GA算法.這主要是因為大數據分析要求快速響應，而GA算法能夠通過在范圍寬廣的求解區域進行多點搜索，推導出網絡配置的最優解.

1.2 利用遺傳算法推導出最優解

通過遺傳算法推導光波長路徑的最佳配置，以及分配給每個用戶的計算機資源量.

1)染色體表達：即一個染色體與兩條信息相關聯.第1條信息是任意兩個節點間的光波長路徑的配置信息，其被直接表示為一個染色體表征；第2條信息是用戶與供應商間資源分配的復合信息.基于這兩條信息，確定每個染色體的相對優點.

算法的染色體表征代表從任意兩個節點之間通過K-最短路徑算法推導出K個路徑，沿此路線設置任意兩個節點間的光波長路徑.每個基因被表示為整數[-K，K].即配置阿米巴節點的內部鏈路，而負整數則代表將節點連接在一起的外部鏈路，基因的絕對值對應于路由ID.當該數值為零時，表示不存在連接兩個節點的光波長路徑.

網絡拓撲示例如圖2所示，其網絡拓撲中染色體表征的樣例如圖3所示.圖3的染色體中最左邊的數值指的是節點I和節點II間的路徑，數值為-2.這說明節點I和節點II之間的外部鏈路(IP級邏輯鏈路)，沿著圖2中三個不同路由間的NO.2路徑所設定的光波長路徑而實現.

圖2 網絡拓撲的示例

圖3 染色體表征的示例

2)變異：在提出的算法中，染色體中任何一個基因(隨機選擇)均會變異為其他數值.此處，如果完全隨機地將變異后的數值確定在[-K，K]中，則收斂效率會變得較差，因為在染色體中需要出現許多個“0”數值，以應對在染色體表征中需要展示真實解情況.但是，如果按上文所述方法確定變異后的數值，則會生成許多個包含極少“0”的染色體.由此，會形成很多使用過度的光波長資源的染色體，這樣會造成無用解空間的搜索.

為避免這一問題，本文通過以下方法設定了變異算法.首先，以二分之一的相同概率，選擇“0(無光波長路徑)”或“一個非零數值(存在光波長路徑)”.如果選擇的是后者，則以相同的概率從[-K，1]或[1，K]中選擇，并變異為該數值.由此，可以通過對算法進行調整使得“0”經常出現在染色體中，以搜索有效的解空間.

3)適應度：本文使用一個適應性度量，通過采用以下的目標函數F，確定基因的相對優點，當解的質量較高時，F的數值較小：

(1)

式中，User和Supplier分別表示用戶和供應商的集合.此外，Demu(s)表示分配給用戶u的供應商s的計算機資源，Hopu(s)表示從用戶u至供應商s的IP跳數.由于所使用的計算機資源量的增加，會造成通信量的增加，因此有必要最大限度減少Demu(s)和Hopu(s)的乘積和.

4)操作程序：下文將展示基于前文的設置環境，基因算法的特定操作程序.

a)染色體組的初始化

使用隨機數，建立起Nc個數量的染色體.

b)交叉

從染色體組中隨機選擇兩個染色體，并通過這些染色體的均勻交叉，生成兩個子染色體.重復這一操作，直到建立起Nc個數量的子染色體.

c)變異

通過1.2節的2)中介紹的變異方法，取一定概率Pm應用到兩個染色體上，這兩個染色體包括一個父染色體和一個子染色體.

d)選擇

通過1.2節的3)中介紹的適應度方法，計算所有染色體的適應度，并執行Nc次的競賽選擇，以使得競賽的規模為Nt.由此，確定具有子染色體的染色體的數量Nc.

e)重復從b)至d)的操作，重復次數為Ng代.

1.3 向每個用戶分配的資源

最基本的資源分配方案包括“集體分配方案”，即貪婪算法.首先，該方案逐個選擇用戶，并識別出從該用戶處通過最少IP跳數可以達到的供應商，并將這些供應商的全部空閑計算機資源分配給該用戶.一旦該用戶的資源請求得到了滿足，則為下一個用戶進行計算機資源分配.這一方案使得接收到首次資源分配的用戶，可以使用鄰近度最高的供應商所提供的計算機資源.然而，對后續用戶所分配的計算機資源量中，將不包括已經被分配給其他用戶的計算機資源.因此，在一個用戶發起資源請求，而網絡中可用的計算機資源量并不充足的情況下，該方案中網絡用戶與供應商的距離可能存在不公平現象.此外，該方案還可能使得過量的負載被集中在特定的供應商.

為解決這一問題，提出了一個“分割分配方案”，以確保用戶和供應商之間在網絡距離方面的公平性，并確保每個供應商的負載均衡.提出的方案確保了計算機資源的所有需求不會一次性分配給單個用戶；而是通過將總資源請求量除以復數的輪，得到資源分配的單位量.

按照資源請求的接受順序，為網絡中每個用戶分配一個ID.計算機資源的分配過程由“輪”組成(本文定義輪的數量為Ns).該程序在每輪過程中，逐個選擇所有用戶，并對供應商所支持的計算機資源量X(請求計算機資源量的1/Ns)進行分配.同時，該程序按照用戶ID的升序和降序，在每輪交替切換用戶的選擇順序，由此，本文通過更改用戶選擇的次序，解決上述的不公平性問題.

計算機資源的分配以“分配候選供應商列表”為基礎，編制該列表的目的是根據特定用戶對最高優先級的供應商進行調整，如圖4所示.控制器為每個用戶生成列表，并在每輪過程對該表進行更新.首先，在主要組中，按照總資源量內已經被分配給用戶的計算機資源量的比例(定義為“資源利用率”)進行排序.若資源利用率相同，則按照與供應商距離最近的用戶的數量進行排序(定義為“競爭力”).此外，若競爭力也相同，則按照與用戶建立連接所需的IP跳數來進行排序.另一方面，在次要組中，將連接到用戶所需的IP跳數作為首要排序指標，而資源利用率則作為次級排序指標，競爭力被用作最后排序指標.需要指出的是，在這兩個組中，對所有排序指標中排名均相同的供應商進行隨機選擇.主要組中的成員與用戶的鄰近度均在可接受范圍內，因此，該程序將供應商之間的負載均衡作為首要考慮目標.另一方面，次要組中的成員在與用戶的距離方面處于可接受范圍之外，因此，該程序將鄰近度作為首要考慮目標，并在可能的情況下將負載均衡納入考慮.

圖4 分配候選供應商列表的示例

提出的方法不但考慮到鄰近度，還考慮到了資源利用率和競爭力，可以避免將負載集中到某個特定的供應商.如果可接受鄰近跳數被指定為一個較大的數值，則負載均衡的優先度最高；如果可接受鄰近跳數被指定為一個較小的數值時，鄰近度則成為優先考慮的指標.因此，可以通過配置來調整負載平衡和鄰近度的具體比重.在對計算機資源進行分配時，提出的方案選擇分配候選供應商列表中排名最前的供應商，并向用戶分配特定的計算機資源量X.在對可用的計算機資源量進行分配后，提出的方法按照供應商列表中成員排序，依次進行資源分配.當對所有用戶執行上述程序后，即完成一輪的處理.一輪處理的工作流程如圖5所示.將該輪重復Ns次，直到所有用戶請求均得到滿足.

圖5 每輪中每個用戶的資源分配程序

2 仿真與評價

2.1 仿真環境

本文在連接到光網絡的每個轄區中依次放置節點，總共包括48個節點和82條鏈路，通過計算機資源量設定每對節點之間的傳輸流量.隨著用戶所使用的供應商計算機資源的增大，流量也會增加.使用公式(2)計算用戶i(位于節點i中的用戶)與供應商j(位于節點j中的供應商)之間的流量traij如下：

traijfficij=A×Demij

(2)

其中，用戶i所使用的供應商的資源量為Demij，A為比例常數.設置A為1，將單個鏈路中傳輸的流量上界和單個波長中的下界分別限制在5 000和100.

從48個節點中隨機選出8個節點并逐個與用戶連接，然后從剩余的40個節點中隨機選出15個節點并逐個與供應商相連接.每個用戶請求的計算機資源量為40，每個供應商提供的計算機資源量為30.K為兩個節點之間導出的路由候選數量，Ns為提出的分割分配方案中的輪數，α為可接受的鄰近跳數，分別設K=8，Ns=10，α=1,還為網絡虛擬化設置了四個限制：

1)光波長路徑的數量的上限，可在一個鏈路上進行多路復用，該上限被設為50；

2)通過光波長路徑可以直接連接的物理跳數的上限，該上限被設為6；

3)組成一個阿米巴節點的節點數量上限，該上限設為7；

4)阿米巴節點內僅執行波長轉換處理而不進行IP處理的連續跳數上限，設為2.最后，遺傳算法相關的參數的數值設定如表1所示.

表1 遺傳算法相關的參數

2.2 評價指標

將HU-S定義為鄰近度的評價指標(如圖7所示)，表示在資源分配關系中從用戶至供應商的IP跳數.此外，假定對供應商之間的相互通信采用并行分析處理，定義HS-S表示向同一個用戶提供計算機資源的供應商間的IP跳數.

通過度量每個用戶的平均HU-S和平均HS-S，并推導出其Jain公平性指數[11，12].若該指數接近1，則意味著用戶間的差異較小，公平性較高.此外，還度量了每個供應商的資源利用情況，并推導出其公平性指數，以進行負載均衡的評價.

2.3 評價分析

實驗中，整個網絡的光波長路徑設為100個，每個用戶的HU-S和HS-S的均值和公平性指數，以及每個供應商之間資源利用率的公平性指數如表2所示.本文對比了四種不同仿真案例：

1)“普通方法”，該案例將集體分配方案應用到一個不帶虛擬化的普通IP網絡；

2)“阿米巴網絡[7]”，該案例用光波長路徑將分散于不同地理位置的節點組合在一起，并向該節點集合賦予路由器功能；

3)“虛擬IP+光信號特性[6]”，該案例將一個虛擬IP網絡，通過引入光波長路徑對網絡進行配置；

4)將分割分配方案應用到一個虛擬的IP網絡，通過引入捷徑路徑和阿米巴節點對該網絡進行配置.

表2中給出了在整個網絡的光波長路徑設為100個情況下，每個用戶的HU-S和HS-S的均值和公平性指數，以及每個供應商之間資源利用率的公平性指數.由表2可知，在普通方法和阿米巴網絡[7]的比較中，即使沒有使用虛擬化技術，在采用了提出的分割分配方法后，HU-S和HS-S的平均IP跳數略有增加，但其公平性指數得到了改善，在每個用戶之間實現了鄰近度上的公平性.而集體分配方案由于后續的用戶僅有非常少的供應商可供選擇，因此各用戶之間的公平性會變得很低.此外，集體分配方案因為資源請求集中在用戶附近的供應商，所以會產生負載偏差.

表2 仿真結果均值

目標函數F(公式(1))隨網絡中光波長路徑總數的變化情況如圖6所示，HU-S隨網絡中光波長路徑總數的變化情況如圖7所示，HS-S隨網絡中光波長路徑總數的變化情況如圖8所示，從三項指標的示意圖，可以看出，普通方案由于不帶虛擬化的IP網絡，其目標函數F值更大，HU-S和HS-S的平均跳數也更高.在阿米巴網絡[7]和本文方法中，每項指標均降低(即性能提高)，這主要因為光波長所確定的路徑總數增加了.文獻[6]僅通過節點間的外部鏈路來改善網絡距離，所提方法較優，主要是因為其使用光波長實現了更靈活的網絡配置，能夠更自由地對節點配置內的IP拓撲進行簡并.

在本文提出的分割分配方案中，雖然負載均衡和公平性相關問題得到了解決，但為了維持公平性，并非一定要為每個用戶分配距離最近的供應商，因此造成平均跳數的增加.為解決這一問題，本文通過光波長路徑引入了網絡虛擬化，如圖7和圖8，其平均跳數得到了較大改善.

圖6 目標函數F隨網絡中光波長路徑總數的變化情況

圖7 HU-S隨網絡中光波長路徑總數的變化情況

圖8 HS-S隨網絡中光波長路徑總數的變化情況

3 結論與展望

本文研究了基于細粒度云計算進行大數據分析的分布式并行計算環境，由此提出了一個虛擬光網絡配置方法，提升了計算機資源與大數據之間的鄰近度.還提出了一種資源分配方法，以在大數據和計算機資源之間實現網絡距離上的公平性，以及計算機資源間的有效負載均衡.所提方法的有效性在性能評價中得到驗證.

未來將研究光網絡環境中，新增大數據和資源供應商的動態控制應用，以及數據分析完成后的計算機資源釋放問題.