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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

假設(shè)將物理網(wǎng)絡(luò)G(V,E)劃分為N個(gè)域，其拓?fù)鋱D分別記為 Gi( Vi, Ei)，1≤i≤N，Vi為域i中節(jié)點(diǎn)集合， Vib為域i中邊界節(jié)點(diǎn)集合(將連接2個(gè)不同域的鏈路的兩端稱(chēng)為邊界節(jié)點(diǎn)，連接2個(gè)不同域的鏈路稱(chēng)為邊界鏈路)， Ei為域i中鏈路集合。我們將從分層的角度考慮底層物理網(wǎng)絡(luò)在不同層次的視圖。高層次視圖，也稱(chēng)為路徑矢量網(wǎng)絡(luò)，記為Gl( Vl, El)。路徑矢量網(wǎng)絡(luò)中的鏈路(路徑矢量)對(duì)應(yīng)于底層物理網(wǎng)絡(luò)的路徑或邊界鏈路，例如，圖1中路徑矢量網(wǎng)絡(luò)的鏈路 ( b1, b3)和(b3, b5)分別對(duì)應(yīng)于底層物理網(wǎng)中 b1與 b3間的路徑和邊界鏈路 (b3, b5)。路徑矢量網(wǎng)絡(luò)的節(jié)點(diǎn)集合 Vl由所有域的邊界節(jié)點(diǎn)組成，鏈路集合 El由對(duì)應(yīng)于底層物理網(wǎng)絡(luò)中每個(gè)域邊界節(jié)點(diǎn)之間的路徑或邊界鏈路的路徑矢量組成。低層次視圖，也就是每個(gè)域的物理拓?fù)渥訄D。圖 1給出了一個(gè)物理網(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)模型。對(duì)于一個(gè) LCN構(gòu)建請(qǐng)求可分解為域內(nèi)邏輯鏈路集合和域間邏輯鏈路集合域內(nèi)邏輯鏈路的映射可以采用文獻(xiàn)[9]的方法解決，為此，下面分層線性規(guī)劃模型是針對(duì)域間邏輯鏈路映射的建模。另外，由于的is或it可能不是邊界節(jié)點(diǎn)，此時(shí)，路徑矢量網(wǎng)絡(luò)還要包含該節(jié)點(diǎn)到其域內(nèi)邊界節(jié)點(diǎn)的路徑矢量。

1) 輸入

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

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

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

2) 變量

① 高層次視圖約束條件

② 低層次視圖約束條件

③ 其他約束條件

LCN_HLP模型解釋如下。

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

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

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

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

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

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

約束條件：

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

子問(wèn)題2目標(biāo)是更新變量向量y，表示為

約束條件：

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

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

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

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

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

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

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

圖2 GLCNMA算法流程

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

圖3 LLCNMA算法流程

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

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

約束條件：

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

因?yàn)閦*(y) 表示給定y時(shí)子問(wèn)題 1的最優(yōu)目標(biāo)值，從而可知

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

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

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

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

4 仿真實(shí)驗(yàn)

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

實(shí)驗(yàn)中物理拓?fù)洳捎肂RITE工具[19]隨機(jī)生成，并利用MATLAB工具實(shí)現(xiàn)算法。

4.1 算法的收斂性

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

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

圖4 算法收斂性

4.2 算法的運(yùn)行時(shí)間

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

圖5 算法運(yùn)行時(shí)間

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

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

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

圖6 LCN請(qǐng)求接受率

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

5 結(jié)束語(yǔ)

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

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