關于跨域虛擬網絡的優化狼群映射研究仿真

王珂琦，張 耀

(河南工業大學漯河工學院，河南 漯河 462000)

1 引言

虛擬網絡的作用是解決物理網絡拓撲的僵化問題[1]，從而使有限的物理資源能夠滿足更多的網絡事務需求。而虛擬網絡映射，就是把物理資源準確有效的配置到相應的虛擬網絡上[2-3]，完成功能擴展。隨著分布式網絡的發展，網絡業務的運營一般不是由單一服務商獨立支撐，而且物理網絡也并非處于同一位置，這就使得虛擬網絡映射需要面對大量具有異構與分布性質的跨域網絡資源，同時對虛擬網絡映射算法提出了更高要求。

文獻[4]分析了網絡節點與鄰近鏈路之間的資源差異，采用k最小路徑方式動態更新節點與鏈路資源，并得到鏈路開銷狀況，該方法獲得較好的映射率，并且能夠在資源缺乏時采取調整動作。文獻[5]針對最優映射采用元胞遺傳算法，定義了元胞自動機，并利用改進遺傳優化元胞近鄰的訓練能力，從而提高算法的收斂速度與局部最優解的搜索性能，但是該方法缺乏對鄰域模型的動態調整能力。文獻[6]針對跨域情況設計了分層分域的資源管理模型，將最低映射開銷作為最優解搜索，并引入蜂群改進尋優性能，取得了較好的網絡請求能力，但是該算法復雜度過高，無法應用在網絡規模較大的場合。文獻[7]也將網絡映射轉換為尋優問題，將單純形算法與遺傳相結合，從而避免遺傳算法早熟。現有的研究算法，都針對虛擬網絡映射的某個方面進行優化，并取得了一定程度的效果，但是缺乏對跨域本質區別的考慮分析，不同域的網絡之間存在信息的未知性，同時，任一網絡域都存在不止一個對外節點，對外節點選取的不同會產生開銷差異，為此，本文提出了關于跨域虛擬網絡的優化狼群映射方法。該方法分別針對域內映射和域間映射進行分析，采用資源開銷作為目標，引入元胞轉換為尋優計算。由于域內映射產生的開銷不大，因此對其進行快速處理，而域間開銷則加入優化狼群，增加元胞尋優的多樣性與全局性，提高域間映射的有效性，降低域間開銷。

2 跨域映射模型

跨域虛擬網絡的映射可以通過圖1來描述。圖中模擬了三個虛擬網絡域，它們分別由三個InPs建立。在任意的網絡域中，都包含N類和B類兩種節點，它們分別代表各域中的內部與邊界節點。所謂的跨域網絡映射，本質就是利用N節點完成虛擬網絡的搭建，并利用B節點實現跨域數據的傳遞。

圖1 跨域映射模型框圖

(1)

(2)

(3)

另外，虛擬網絡中心還需要具有切片功能，因此，在其中一些節點中還應該加以限制

(4)

當滿足上述限制條件時，即認為映射為有效的，虛擬網絡中會出現若干映射情況，而本文針對跨域虛擬網絡映射存在資源分配不合理，開銷過重，以及負載不均衡的問題進行改進優化，為此，這里把跨域虛擬網絡在實現映射過程中所產生的負載情況描述如下

(5)

3 虛擬網絡域內映射

(6)

(7)

網絡底層資源始終處于動態變化，尤其在負載增加的情況下，經常會出現節點非均衡現象，如果要實現最大利益，就應該盡可能縮減網絡底層成本，同時也應該達到節點的均衡性。因此本文將底層資源的配置設定為元胞繁殖動作，將回收設定為元胞死亡動作，于是，更新操作可以進一步描述為

(8)

映射產生的節點成本固定不變，在采用的映射策略改變時，影響的是所需帶寬，于是，設計模型更新過程中的目標函數如下

(9)

(10)

假定虛擬網絡節點u與v依次完成了至底層i與j節點的映射處理，則u與v對應的路徑也會與底層路徑形成對應關系，因此通過上述連接限定，就能夠控制底層節點間的流量。

4 虛擬網絡域間映射

4.1 優化狼群算法

狼群算法在尋求最優解的過程中是利用分工合作機制完成的，其中包含頭狼，探狼，以及猛狼。探狼具有游走行為，根據決策獲取所需信息，同時得到頭狼的位置信息。頭狼具有召喚行為，傳遞猛狼和獵物對應的信息。通過分工合作機制達到信息搜索與傳輸目的，并實現捕獵行為，即最優解搜尋。

(11)

(12)

(13)

其中的D是維度，ω是閾值系數。

4.2 基于狼群優化的虛擬網絡域間映射

對于跨域虛擬網絡，要得到資源的最佳配置，除了分析域內的鏈路與節點消耗外，還需要分析域間的消耗情況。由于狼群算法具有出色的全局尋優性能，因此，引入狼群優化算法，改進映射處理時鏈路與節點資源的全局性。在具有跨域屬性的虛擬網絡中，MANO無法獲知網絡的詳細信息，可以利用競價來估算出各個網絡域的資源配置情況，也就是從域間的鏈路開銷與節點開銷兩方面采取配置分析。其中在鏈路資源方面，采取啟發算法，搜索出滿足時間約束的有效解。在節點資源方面，MANO能夠保存SP所請求的目標節點，同時InPs會把所在域中的可用節點及其對應資源與開銷通知服務中心，服務中心據此來建立競價機制，并由MANO完成節點的合理映射。

將虛擬網絡節點作為元胞，所有節點對應的元胞組成一組向量，向量的大小由節點數量決定，向量中任意分量表示節點標識，不同的映射結果將產生不同的向量。另外，在映射過程中，向量結果也將同步進行更新。更新的判定依據為方向向量，其向量元素包含0和1，分別對應不更新與更新標志。對于每種映射結果，為判定其優劣程度，設計目標函數如下

(14)

這里的LEN(u，v)代表鏈路(u，v)映射時對應的實際跳數，BW(u，v)代表鏈路帶寬。根據該公式，利用域間節點的映射情況計算出鏈路的目標函數，獲取鏈路的適應程度。其處理過程可以描述如下：

1)參數初始化，包括元胞向量，方向向量，狼群數量，以及其它因子參數；

2)隨機選擇頭狼，并搜索出合理的探狼，進行游走，利用方向更新節點元胞位置，得到新的元胞向量；

3)求解映射的最小路徑，利用猛狼感知，當Yi>Wlead時，令Wlead=Yi，并產生召喚信息，當Yi

4)利用目標函數得到適應度，并根據適應度衡量節點元胞向量的優劣性，零局部演化Δfi=0，且kmax=kmax+1，采取獵殺操作，對現有優勢空間進行更新操作。

5)再次更新元胞向量，求解鏈路最小路徑，當成功實現映射，跳回上一步，當未成功完成映射，同時又未達到約束計數上限的，繼續更新元胞向量，直至映射成功或者確定失敗。

5 仿真分析

5.1 仿真與參數設置

仿真采用GT-ITM構建網絡拓撲，其中設定InPs數量為5個，物理節點數量為100，物理鏈路數量為500，且網絡中InPs提供給節點的資源滿足[20,50]與[0,50]均勻分布，設置虛擬節點形成鏈路的概率為0.5。另外初始化參數如表1所示。

表1 初始化參數

5.2 仿真結果分析

為了驗證本文方法在虛擬網絡映射中的實際性能，仿真過程中，采用文獻[5]與文獻[6]中的方法作為對比。首先，通過仿真，得到虛擬網絡映射的開銷與節點數量之間的關系，如圖2所示。根據結果曲線可知，隨著虛擬網絡節點數量的增加，所有方法的映射開銷均呈現增加趨勢，其中兩種文獻方法的增長速度近似線性，當節點數量達到一定值后，很容易導致處理崩潰，而本文方法則近似于對數增長，當節點數量急劇增加時，其映射開銷也不會隨之急劇增加，由于從節點與鏈路兩方面進行資源尋優，同時針對離散情況引入元胞處理，有效提高了離散情況下最優解的尋求性能，能夠有效應對大規模網絡場景。

圖2 映射開銷與節點數量關系曲線

為了驗證本文方法在跨域映射中的具體性能，仿真得出映射開銷與網絡域數量之間的關系，如圖3所示。實驗過程中，令虛擬節點與底層節點數量相同，僅讓底層的網絡域數量發生改變。根據結果數據比較，當網絡域數量發生改變時，文獻方法的映射開銷均有一定程度的增加，而本文方法的映射開銷幾乎保持不變，且始終小于文獻方法的映射開銷。表明網絡域的增加導致文獻方法的額外開銷，本文方法由于針對域間映射做了處理，并引入狼群優化，結合元胞處理，有效應對了跨域映射的尋優性能，合理處理了域內與域間的節點、帶寬資源，實現域間節點的資源均衡。

圖3 映射開銷與網絡域數量關系

圖4所示為三種網絡映射的執行時間結果，可以看出，本文方法的執行速度要稍微領先于文獻方法。這三種方法均為改進方法，在引入算法時帶來了算法與時間復雜度的增加，本文方法由于元胞空間的龐大，導致映射處理的中間變量增加，但是元胞與狼群優化對于尋優和收斂效果的改進，使得本文方法在映射時間上最終還是產生了一定的優勢。

圖4 跨域虛擬網絡映射執行時間

6 結束語

虛擬網絡映射可以把物理資源配置到對應的虛擬節點上，并在其上實現業務處理功能，避免網絡底層資源受成本和性能等因素制約。由于現有虛擬網絡映射算法不能有效滿足跨域分布需求，本文提出了優化狼群映射算法。將跨域映射問題分解為域內和域間兩種情況進行分析。在跨域映射時，主要資源開銷在于域間，因此對域內采取快速處理，僅引入元胞處理進行最優資源開銷搜索。域間處理在元胞基礎上加入了優化狼群，增強全局搜索能力，從而得到合理的節點與鏈路資源分配。通過仿真，驗證了本文方法在跨域情況下，有效降低了網絡映射開銷，且資源開銷受網絡域數量的影響很小，同時也降低了網絡映射的執行時間。