跨域邏輯承載網映射方法研究

張旻，吳春明，王濱，姜明

（1. 杭州電子科技大學 計算機學院，浙江 杭州 310018；2. 浙江大學 計算機科學與技術學院，浙江 杭州 310027）

1 引言

隨著互聯網業務類型的不斷豐富，網絡規模的不斷擴大，促使網絡技術需要不斷地進行革新，以適應用戶業務和網絡規?？焖侔l展的需求。然而，僅僅依靠拓展鏈路傳輸帶寬，提高節點處理速度等方法，不僅難以滿足特性差異日益擴大的用戶業務承載需求，而且面對大量差異化用戶業務的規?；瘧茫W絡無法適應的問題日趨凸現。針對上述問題，文獻[1,2]以用戶業務需求為驅動，提出了面向服務提供的可重構柔性承載網絡(UCN, universal carrying network)技術體系，基于可重構路由交換平臺，通過構建可重構邏輯承載網(LCN, logical carrying network)的形式，快速、靈活和高效地為用戶業務提供多樣化的網絡服務。

LCN映射是構建可重構邏輯承載網的核心過程，也就是根據用戶業務承載需求(如LCN的拓撲、帶寬等)，為每條邏輯鏈路選擇適當的物理網絡路徑，并為其分配資源。LCN映射問題從理論和應用上來說都是一個非常具有挑戰性的問題,主要原因在于：一方面，LCN構建需求的多樣性、物理網絡資源的有限性、LCN構建請求是動態到達且不可預知的；另一方面，LCN映射既要滿足用戶業務需求，也要高效地利用物理網絡資源，以期在資源有限的物理網絡上能夠構建盡可能多的邏輯承載網，實現物理網絡提供商利益的最大化。

目前，國內外研究人員對LCN映射或虛擬網[3,4]映射問題做了諸多有益的探索，取得了一定的成果。王浩學等[2]設計了一種基于資源均衡的LCN映射算法，比較了分別采用基于負載均衡的映射算法和不支持負載均衡的映射算法時 LCN構建成功的概率。齊寧等[5]討論了映射策略的若干重要原則，并在此基礎上提出了帶遷移同時考慮網絡均衡的映射方法。李文等[6]結合K短路徑的思想，尋找滿足邏輯鏈路帶寬需求的物理路徑。Cheng Xiang等[7]運用馬爾科夫隨機漫步模型把網絡資源與網絡拓撲相結合對網絡節點排序，基于節點排序結果進行虛擬網映射，該方法突破了傳統映射過程只考慮網絡資源的思想，提高了映射效率。W. Szeto[8]基于多商品流問題中的最大并行流問題（maximum-concurrent flow problem）在物理網絡中每個邊緣節點對之間進行資源的預分配，采用線性規劃的方法來進行求解。當一個新的虛擬網構建需求到達后，在預分配資源中對虛擬網所需資源進行實際分配。Minlan Yu等[9]提出了多徑映射的思想，通過將虛擬鏈路映射到多條物理路徑上，以提高物理網絡的負載均衡和資源可利用率，并基于多商品流問題來進行建模求解。Jens Lischka等[10]提出通過子圖同構檢測和回溯的方法來將虛節點和虛鏈路同步映射到物理網絡中，以提高虛擬網構建成功的概率。針對虛節點映射的位置要求，N. M. Mosharaf等[11]提出通過在底層物理網絡上設立虛擬的元節點和元邊來擴展物理網絡，從而將一個虛節點映射位置不確定問題轉化為確定性問題，再通過混合整數規劃的方法來進行建模求解。

上述提出的一些映射算法都屬于集中式的解決方案，即需要獲取整個物理網絡的拓撲、帶寬資源等信息。然而，在實際中，物理網絡分成了多個自治域，由不同的基礎設施提供商(InP, infrastructure provider)管理，而每個InP往往不愿提供其物理網絡拓撲、資源等相關信息。因此，目前的這些映射算法無法對跨域的LCN進行映射。盡管文獻[12]和文獻[13]分別提出了一種分布式和跨域映射方案，但文獻[12]中的分布式算法還是要求網絡中的每個結點通過通信協議獲取整個網絡拓撲等信息，而文獻[13]提出的是一種啟發式跨域映射方案，沒有從數學模型上考慮網絡資源優化和映射代價?；谏鲜鲈?，如何有效地對跨域 LCN進行映射仍是具有重要研究意義和挑戰的工作。

針對跨域LCN映射問題，本文將物理網絡分為2層視圖，低層視圖即各個域的物理網絡拓撲，而高層視圖是由路徑矢量構成的網絡拓撲。在此基礎上，本文以最小映射代價為目標，提出了一個新穎的分層優化模型，并運用最優化理論中的原始分解方法，將該模型分解為2個子問題，其中一個子問題涉及各個域的物理網絡信息，從而可以由各個域獨立求解，而另一問題與路徑矢量網絡有關，可在路徑矢量網絡上作優化。最終，基于跨域LCN映射分層模型的分解，本文提出了一個跨域LCN映射算法，實驗表明該算法可以快速收斂，并與其他跨域映射方案相比，具有更好的性能。

2 邏輯承載網映射問題描述

LCN構建是根據用戶業務的需求及物理網絡當前的資源狀況，通過映射算法在構建需求與網絡資源之間進行匹配，以獲得最優的網絡資源分配方案。下面對LCN映射問題進行數學描述。

物理網絡可以抽象表示為G(V,E)，其中，V表示物理節點的集合，E表示物理鏈路的集合。本文將考慮LCN的拓撲和邏輯鏈路帶寬需求，LCN構建需求表示為｛Gv( Vv, Ev),D｝ ，其中，Gv( Vv, Ev)表示LCN的拓撲， Vv和 Ev分別表示LCN節點和邏輯鏈路的集合，為邏輯鏈路帶寬需求的集合。進一步可以用一個三元組(s,t,d)表示承載網邏輯鏈路的帶寬需求，其中，s和t表示承載網邏輯鏈路的2個端點，LCN構建需求也可表達為三元組的集合，即{(si, ti, di)|1 ≤ i≤m}，m為待構建的承載網中邏輯鏈路的個數。

對于LCN映射問題，可描述為將邏輯鏈路映射到某條物理路徑，記作path(s,t)= Mlink(e)，其中，path(s, t)表示s至t所經過的物理鏈路，Mlink(·)表示邏輯鏈路到物理路徑的映射關系。這時，LCN映射可以看作是在 G(V, E)中構建一個子圖G′( V′, E ′)，這個子圖應當滿足承載網構建需求，而構建子圖 G ′( V′, E ′)的目標是使構建費用最小化，即：

其中，w表示鏈路e單位帶寬的代價，x(e)表示在鏈路e上所需的帶寬。

3 跨域邏輯承載網映射算法

3.1 跨域映射分層優化模型

假設將物理網絡G(V,E)劃分為N個域，其拓撲圖分別記為 Gi( Vi, Ei)，1≤i≤N，Vi為域i中節點集合， Vib為域i中邊界節點集合(將連接2個不同域的鏈路的兩端稱為邊界節點，連接2個不同域的鏈路稱為邊界鏈路)， Ei為域i中鏈路集合。我們將從分層的角度考慮底層物理網絡在不同層次的視圖。高層次視圖，也稱為路徑矢量網絡，記為Gl( Vl, El)。路徑矢量網絡中的鏈路(路徑矢量)對應于底層物理網絡的路徑或邊界鏈路，例如，圖1中路徑矢量網絡的鏈路 ( b1, b3)和(b3, b5)分別對應于底層物理網中 b1與 b3間的路徑和邊界鏈路 (b3, b5)。路徑矢量網絡的節點集合 Vl由所有域的邊界節點組成，鏈路集合 El由對應于底層物理網絡中每個域邊界節點之間的路徑或邊界鏈路的路徑矢量組成。低層次視圖，也就是每個域的物理拓撲子圖。圖 1給出了一個物理網絡的2層視圖，其中，圖1(b)和圖 1(c)分別是物理網絡(圖 1(a))的高層次視圖和低層次視圖。

圖1 物理網絡的2層視圖

基于物理網絡分層結構，采用多商品流數學模型，本文可以建立以下跨域 LCN映射的分層線性規劃(LCN_HLP, logical carrying network hierarchical linear program)模型。對于一個 LCN構建請求可分解為域內邏輯鏈路集合和域間邏輯鏈路集合域內邏輯鏈路的映射可以采用文獻[9]的方法解決，為此，下面分層線性規劃模型是針對域間邏輯鏈路映射的建模。另外，由于的is或it可能不是邊界節點，此時，路徑矢量網絡還要包含該節點到其域內邊界節點的路徑矢量。

1) 輸入

跨域LCN構建請求：

邊界鏈路集合：bE表示所有邊界鏈路。

物理鏈路剩余帶寬：uvr表示物理鏈路的剩余帶寬。

2) 變量

① 高層次視圖約束條件

② 低層次視圖約束條件

③ 其他約束條件

LCN_HLP模型解釋如下。

1) 式(2)為數學規劃的目標函數，目標是使構建的邏輯承載網的代價最小化。式中由各域預先計算得到，本文采用的計算方法是：先通過網絡最大流計算出節點u和v之間的最大流，并計算得到最大流的代價，從而可以計算出u和v間的平均代價。設uvλ和分別表示由最大流算法計算得到的節點u和v之間的最大流及經過物理鏈路的流量，則

2) 式(3)、式(4)是高層次視圖中多商品流模型的約束條件，其中構建帶寬需求 di作為多商品流模型中的商品需求， yuv作為容量限制。式(5)、式(6)是低層次視圖中多商品流模型的約束條件，其中yuv作為商品需求，物理鏈路剩余帶寬 ruv作為容量限制。

3) 為了后面描述方便，本文采用粗體字和大寫字母表示向量和矩陣，式(3)、式(4)可以用矩陣表示為Bf≤y,Afi=di,1≤i≤m，其中，fi表示變量所構成的向量，di表示LCN需求向量，y表示變量yuv所構成的向量同樣地，式(5)、式(6)可以用表示為及

圖4(a)和圖4(b)分別逆變器橋臂上的主開關器件S1和S2進行狀態切換過程中承受的電壓uS1和uS2及所流經的電流iS1和iS2的實驗波形，能看出S1和S2在開通過程中完成了零電壓軟開通動作，在關斷過程中完成了零電壓軟關斷動作.圖4(c)和圖4(d)分別為逆變器輔助開關Sa1和Sa4切換時端電壓uSa1和uSa4及所流經的電流iSa1和iSa4的實驗波形，可看出Sa1和Sa4在開通過程中分別完成了零電壓軟開通動作和零電流軟開通動作，在關斷過程中分別完成了零電壓軟關斷動作和零電流軟關斷動作.

3.2 模型求解及映射算法設計

基于原始分解方法[14]，LCN_HLP問題可以分解為2個最優子問題。當y固定時，子問題1可以表示為

約束條件：

子問題1可以看作是LCN構建請求在路徑矢量網絡中的映射問題，該模型是一個線性規劃問題，可以通過單純形方法或內點法進行求解。

子問題2目標是更新變量向量y，表示為

約束條件：

其中， z*(y)是給定y時，子問題1的最優目標值。定理1 設Θ表示可使線性規劃式(10)～式(13)

具有可行解的y的集合。對于y∈Θ，z*(y)是凸函數。證明 根據凸函數的定義，要證明 z*(y)是凸的，只需驗證：對給定的若，則

因為式(11)～式(13)及式(10)都是線性的，很容易直接驗證z*(y) 是凸函數。

盡管函數z*(y)是凸的，但是不可微的。次梯度方法是求解子問題 2的一個簡便方法。設向量為子問題1中式(11)對應的對偶變量，其可作為z*(y)的次梯度，并由對偶理論可知由此，可以采用公式nθ←-yyq更新向量y，其中，nθ是第n步的步大小，其可以通過下式計算[15]：

如果更新后的y不滿足式(15)～式(17)，需要修正y以保證滿足物理網絡鏈路的剩余帶寬限制。顯然，修正y可以分解到各個域完成，即第i域修正

通過上述分析，可以設計算法對LCN_HLP模型進行求解，該算法包括2部分：全局邏輯承載網映射算法(GLCNMA, global logical carry network mapping algorithm)和局部邏輯承載網映射算法(LLCNMA, local logical carry network mapping algorithm)。GLCNMA其主要過程是求解子問題1和更新變量uvy。LLCNMA將在各域中運行，其將修正uvy，以保證滿足物理網絡鏈路約束條件。值得一提的是，由于GLCNMA僅需要路徑矢量網絡的拓撲信息，LLCNMA在各域中運行，只需各域的網絡拓撲信息，因此，本文提出的跨域 LCN映射算法可以在無法獲得底層物理網絡全局拓撲的情況下，通過GLCNMA和LLCNMA的相互協作共同完成跨域映射。

圖2具體描述了GLCNMA的基本過程。Step1)給出算法的初始值，Step3)中采用次梯度方法更新變量uvy，其中，是子問題 1中式(11)對應的對偶變量，若那么設由于uvt可能不滿足物理網絡鏈路的剩余帶寬約束條件，Step4)～Step5)把uvt發送給各域的LLCNMA，通過LLCNMA修正后返回得到滿足物理網絡鏈路的剩余帶寬約束條件的uvy值。Step6)針對更新后的uvy 求解子問題 1。Step3)～Step6)經過K次迭代得到LCN在路徑矢量網絡中的最優映射結果，該結果通過Step8)發送給各域，由各域的LLCNMA計算出LCN在物理網絡上的最終映射結果。

圖2 GLCNMA算法流程

圖3描述了在第i域中運行的LLCNMA算法。LLCNMA包括3部分：1)初始化，uvy看作是路徑矢量網絡中節點u與v間分配的帶寬容量，本文采用文獻[16]的最大最小公平多商品流算法為所有公平分配帶寬；2)修正以滿足物理網絡鏈路的剩余帶寬約束條件[17]；3)路徑映射。采用最小代價多商品流模型將路徑矢量網絡的鏈路映射到物理網絡上。

圖3 LLCNMA算法流程

定理 2 如果次梯度更新步長足夠小，則本文提出的跨域 LCN映射算法可以收斂到最優解附近一個很小的區域內。

證明 由線性規劃對偶理論可得子問題1的對偶問題，其表達式為

約束條件：

其中，向量 ,q p分別為子問題 1中式(11)和式(12)對應的對偶變量。

因為z*(y) 表示給定y時子問題 1的最優目標值，從而可知

并且由于z*(y) 是最優值，因此

進一步由式(19)和式(20)可得：

由次梯度定義[18]， q*是 y = y*時 z*(y)的次梯度，也就是向量q作為子問題 1中式(11)對應的對偶變量，其值可作為 z*(y)的次梯度。

因為跨域 LCN映射算法采用次梯度方法[18]更新向量y，而文獻[18]已證明了當次梯度更新步長足夠小時，次梯度算法可以收斂到最優值。因此，跨域 LCN映射算法可以收斂到最優解附近一個很小的區域內。

4 仿真實驗

本節仿真實驗的目的包括2個方面：一是驗證本文提出的跨域映射算法的收斂性以及在大規模網絡環境下算法的運行速度；二是在動態網絡環境下，即LCN構建請求隨機到達及LCN隨機拆除情況下，驗證算法性能，包括LCN請求接受率和LCN構建平均收益。

實驗中物理拓撲采用BRITE工具[19]隨機生成，并利用MATLAB工具實現算法。

4.1 算法的收斂性

隨機生成分為10個域的物理網絡，其中每個域包括50個節點，物理網絡的鏈路帶寬容量服從100～120間的均勻分布。隨機生成跨域LCN構建請求，LCN的拓撲包含 30條邏輯鏈路，邏輯節點隨機分布在各域，帶寬需求為90。通過圖4可以看到算法在40次迭代后便可收斂于LCN_HLP模型的最優值；盡管 LCN_HLP模型的最優解與全局集中式映射算法最優值[9]之間存在偏差，但小于3%。

顯然，映射算法的運行速度與迭代次數有關，迭代次數越多，運行時間越長。算法需要在最優性和運行時間(即迭代次數)之間平衡，從圖 4中可以看出，迭代 15次時，算法得到的解與最優值間的偏差小于 4%，因此，在后面動態環境下實驗中，將算法的迭代次數設為15。

圖4 算法收斂性

4.2 算法的運行時間

圖5給出了不同物理網絡大小下的算法運行時間。在實驗中，隨機產生 6個物理網絡，每個物理網絡都分為10個域，而每個物理網絡域的節點數從50～100間增加。物理網絡的鏈路帶寬容量服從100～120間的均勻分布。隨機生成跨域LCN構建請求，LCN的拓撲包含30條邏輯鏈路，邏輯節點隨機分布在各域，帶寬需求為90。實驗測試了迭代次數分別為0,5,10,15時算法的運行時間，并與全局集中式映射算法[9]進行了比較。從圖5中可知，全局集中式映射算法隨著物理網絡規模的增大，其運行時間也迅速增加，而本文跨域映射算法的運行時間緩慢增加。其主要原因是：①LLCNMA在各域中并行運行；②GLCNMA算法的運行時間主要在求解子問題1，而子問題1的復雜度與路徑矢量網絡大小有關，但路徑矢量網絡與物理網絡相比，規模更小。

圖5 算法運行時間

4.3 算法的動態性能

在這個實驗中，本文評估在動態環境下算法的LCN請求接受率和LCN構建平均收益，并與文獻[13]中的PolyViNE算法進行比較。實驗中的所有仿真都執行3 000個時間單位，以獲得穩定的性能測試結果。性能測試指標定義如下：

仿真實驗所采用的網絡隨機生成分為10個域的物理網絡，其中每個域包括50個節點，物理鏈路的帶寬服從100～120間的均勻分布。隨機生成LCN構建請求，LCN的邏輯鏈路帶寬服從20～30間的均勻分布，LCN請求到達間隔時間和LCN生命周期均服從Poisson分布。通過圖6和圖7可以看到，本文的算法在接受率和平均收益上明顯優于基于單徑啟發式搜索的PolyViNE算法，授受率提高了近10%，平均收益提高了大約20%。其原因在于：PolyViNE算法將LCN的每條邏輯鏈路映射到物理網絡的單個路徑上，而物理網絡隨著構建的LCN的增多，有些關鍵鏈路上的資源不足，導致在單個路徑上無法完成邏輯鏈路映射。本文算法允許邏輯鏈路映射到物理網絡的多條路徑上，在資源不足時，會將LCN鏈路帶寬需求分割到多條路徑，從而提高了接受率和平均收益。

圖6 LCN請求接受率

圖7 LCN構建平均收益

5 結束語

LCN映射算法是實現可重構邏輯承載網的關鍵技術，而目前提出資源優化映射算法在無法獲取整個物理網絡拓撲信息的情況下，難以對跨域的LCN進行映射。為了解決大規模網絡環境中跨域LCN的映射問題，本文以最小映射代價為目標，提出了一個分層線性規劃模型，并基于模型的原始分解，設計了一個跨域LCN映射算法?；贛ATLAB的仿真實驗分析本文跨域映射算法的性能，實驗表明該算法可以快速收斂到最優值，當迭代次數選擇15時，可以較好地達到最優性與運行時間的折中;與現有的跨域映射方案相比，本文算法的構建請求接受率和平均收益分別提高了近10%和20%，具有更好的性能。

[1] 汪斌強, 鄔江興. 下一代互聯網的發展趨勢及相應對策分析[J]. 信息工程大學學報, 2009, 10(1):1-10.WANG B Q, WU J X. Development trends and associated countermeasures analysis for NGN[J]. Journal of Information Engineering University , 2009, 10(1):1-10.

[2] 王浩學, 汪斌強, 于婧等. 一體化承載網絡體系架構研究[J]. 計算機學報, 2009,32(3): 371-376.WANG H X, WANG B Q, YU J, et al. Research on architecture of universal carrying network[J]. Chinese Journal of Computers, 2009,32(3): 371-376.

[3] ANDERSON T, PETERSON L, SHENKER S. Overcoming the internet impasse through virtualization[J]. Journal Computer, 2005, 38(4):34-41.

[4] FEAMSTER L, GAO L, REXFORD J. How to lease the internet inyour spare time[J]. ACM SIGCOMM Computer Communications Review, 2007, 37(1): 61-64.

[5] 齊寧, 汪斌強, 郭佳. 邏輯承載網構建方法的研究[J]. 計算機學報,2010,33(9): 1533-1540.QI N, WANG B Q, GUO J. Research on construction methods of logical carrying network[J]. Chinese Journal of Computers，2010,33(9):1533-1540.

[6] 李文, 吳春明, 陳健等. 物理節點可重復映射的虛擬網映射算法[J].電子與信息學報,2011,33(4):908-914.LI W, WU C M, CHEN J, et al. Virtual network mapping algorithm with repeatable mapping over substrate nodes[J]. Journal of Electronics ＆ Information Technology, 2011,33(4):908-914.

[7] CHENG X, SU S, ZHANG Z, et al. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2):39-47.

[8] SZETO W, IRAPI Y, BOUTABA R. A multi-commodity flow based approach to virtual network resource allocation[A]. Proc of the IEEE GLOBECOM[C]. San Francisco, USA, 2003.3004-3008.

[9] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[10] LISCHKA J, KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[A]. Proc of the ACM SIGCOMM[C].Barcelona ,Spain, 2009.81-88.

[11] MOSHARAF N M, CHOWDHURY K. Virtual network embedding with coordinated node and link mapping[A]. Proc of the IEEE INFOCOM[C]. Rio de Janeiro, Brazil, 2009. 783-791.

[12] HOUIDI I, LOUATI W. A distributed virtual network mapping algorithm[A]. Proc of the IEEE ICC[C]. Beijing, China, 2008. 5634-5640.

[13] CHOWDHURY M, SAMUEL F, BOUTABA R. PolyViNE: policy-based virtual network embedding across multiple domains[A].Proc of the Second ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures[C]. New Delhi, India,2010. 49-56.

[14] CHIANG M, LOW S, CALDERBANK A. Layering as optimization decomposition: a mathematical theory of network architectures[J].Proceedings of the IEEE, 2007, 95(1): 255-312.

[15] BARAHONA F, ANBIL R. The volume algorithm: producing primal solutions with a subgradient method[J]. Math Program, 2000,87:385-399.

[16] ALLALOUF M, SHAVITT Y. Centralized and distributed algorithms for routing and weighted max-min fair bandwidth allocation[J]. Networking, IEEE/ACM Transactions on, 2008, 16(5): 1015-1024.

[17] HE J, SHEN R, LI Y, et al. DaVinci: dynamically adaptive virtual networks for a customized internet[A]. Proc of the 2008 ACM CoNEXT Conference[C]. Madrid, Spain, 2008.1-12.

[18] FREUND R. Subgradient Optimization, Generalized, Programming,and Nonconvex Duality[R]. MIT, 2004.

[19] MEDINA A, LAKHINA A, MATTA I. BRITE: an approach to universal topology generation[A]. Proc of Ninth International Symposium on Modeling, Analysis and Simulaion of Computer and Telecommunication Systems[C]. Ohio, USA, 2001.346-353.