跨域邏輯承載網(wǎng)映射方法研究

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

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

1 引言

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

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

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

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

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

2 邏輯承載網(wǎng)映射問題描述

LCN構(gòu)建是根據(jù)用戶業(yè)務(wù)的需求及物理網(wǎng)絡(luò)當前的資源狀況，通過映射算法在構(gòu)建需求與網(wǎng)絡(luò)資源之間進行匹配，以獲得最優(yōu)的網(wǎng)絡(luò)資源分配方案。下面對LCN映射問題進行數(shù)學(xué)描述。

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

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

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

3 跨域邏輯承載網(wǎng)映射算法

3.1 跨域映射分層優(yōu)化模型

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

圖1 物理網(wǎng)絡(luò)的2層視圖

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

1) 輸入

跨域LCN構(gòu)建請求：

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

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

2) 變量

① 高層次視圖約束條件

② 低層次視圖約束條件

③ 其他約束條件

LCN_HLP模型解釋如下。

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

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

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

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

3.2 模型求解及映射算法設(shè)計

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

約束條件：

子問題1可以看作是LCN構(gòu)建請求在路徑矢量網(wǎng)絡(luò)中的映射問題，該模型是一個線性規(guī)劃問題，可以通過單純形方法或內(nèi)點法進行求解。

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

約束條件：

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

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

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

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

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

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

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

圖2 GLCNMA算法流程

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

圖3 LLCNMA算法流程

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

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

約束條件：

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

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

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

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

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

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

4 仿真實驗

本節(jié)仿真實驗的目的包括2個方面：一是驗證本文提出的跨域映射算法的收斂性以及在大規(guī)模網(wǎng)絡(luò)環(huán)境下算法的運行速度；二是在動態(tài)網(wǎng)絡(luò)環(huán)境下，即LCN構(gòu)建請求隨機到達及LCN隨機拆除情況下，驗證算法性能，包括LCN請求接受率和LCN構(gòu)建平均收益。

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

4.1 算法的收斂性

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

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

圖4 算法收斂性

4.2 算法的運行時間

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

圖5 算法運行時間

4.3 算法的動態(tài)性能

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

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

圖6 LCN請求接受率

圖7 LCN構(gòu)建平均收益

5 結(jié)束語

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

[1] 汪斌強, 鄔江興. 下一代互聯(lián)網(wǎng)的發(fā)展趨勢及相應(yīng)對策分析[J]. 信息工程大學(xué)學(xué)報, 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] 王浩學(xué), 汪斌強, 于婧等. 一體化承載網(wǎng)絡(luò)體系架構(gòu)研究[J]. 計算機學(xué)報, 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] 齊寧, 汪斌強, 郭佳. 邏輯承載網(wǎng)構(gòu)建方法的研究[J]. 計算機學(xué)報,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] 李文, 吳春明, 陳健等. 物理節(jié)點可重復(fù)映射的虛擬網(wǎng)映射算法[J].電子與信息學(xué)報,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.