鄭永偉，艾中良

(華北計算技術(shù)研究所總體部，北京 100083)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，網(wǎng)絡協(xié)議和服務不斷豐富，傳統(tǒng)的互聯(lián)網(wǎng)架構(gòu)已經(jīng)不能滿足當前的需要，而重新規(guī)劃網(wǎng)絡架構(gòu)困難重重，網(wǎng)絡虛擬化作為構(gòu)建新一代互聯(lián)網(wǎng)架構(gòu)的重要技術(shù)被提出［1］。利用網(wǎng)絡虛擬化技術(shù)，多個異構(gòu)的網(wǎng)絡架構(gòu)能夠同時存在于同一個共享的底層基礎網(wǎng)絡環(huán)境之上。在網(wǎng)絡虛擬化環(huán)境中，多個服務提供商SP無需自己投資搭建物理基礎設施，只需要從一個或多個基礎設施提供商ISP租賃共享的資源，并在其基礎上構(gòu)建異構(gòu)虛擬網(wǎng)絡，為端用戶提供定制的端到端服務［2-4］。網(wǎng)絡虛擬化也是網(wǎng)絡測試試驗床(GENI，Emulab，DETER等)的重要組成［5-7］，基于虛擬化，每個項目組根據(jù)試驗需求構(gòu)建滿足要求的虛擬網(wǎng)絡拓撲，之后在共享的試驗床上部署試驗環(huán)境并測試，而不用擔心與其他項目組的試驗沖突。

虛擬網(wǎng)絡由虛擬節(jié)點和連接虛擬節(jié)點的虛擬鏈路組成，節(jié)點有計算能力和位置等要求，鏈路有帶寬等要求，其中虛擬節(jié)點部署在底層網(wǎng)絡的一個物理節(jié)點上，虛擬鏈路對應到底層網(wǎng)絡上通常是源節(jié)點到目的節(jié)點的一條路徑。網(wǎng)絡虛擬化首要解決的是虛擬網(wǎng)映射問題，即如何把帶有虛擬節(jié)點和虛擬鏈路約束的虛擬網(wǎng)絡請求，映射到具有有限計算能力的物理節(jié)點和有限帶寬資源的物理路徑的底層網(wǎng)絡上。虛擬網(wǎng)絡映射問題已經(jīng)成為了研究熱點，它本身是NP難［8］，并且高效的映射算法能提高底層環(huán)境接收虛擬網(wǎng)絡的數(shù)量和底層環(huán)境的利用率。從根本講，虛擬網(wǎng)映射問題也屬于資源分配問題，隨著時間的增長，底層網(wǎng)絡資源將產(chǎn)生不能使用的資源碎片，即空閑的資源被分割成許多小片，這些資源不能分配給新的請求。

虛擬網(wǎng)的映射由節(jié)點映射和鏈路映射兩部分組成，一個設計合理的映射算法需要具備映射成功率高以及映射完成后底層環(huán)境能夠接受更多的映射請求的能力，底層資源利用率高。虛擬網(wǎng)絡映射如圖1所示。

本文采用中心資源分配方式設計節(jié)點和鏈路協(xié)同映射的算法，該算法結(jié)合鏈路分割和鏈路遷移技術(shù)來提高資源映射的成功率和收益比，并采取鄰近節(jié)點鄰近映射來降低映射花費。

圖1 虛擬網(wǎng)絡映射

1 相關(guān)工作

虛擬網(wǎng)絡映射問題與虛擬私有網(wǎng)VPN［9］嵌套以及網(wǎng)絡測試床映射問題類似，然而經(jīng)典的VPN請求僅包含帶寬需求，不含節(jié)點約束;Emulab測試床使用Assign算法［10］，考慮帶寬約束以及節(jié)點的獨占使用，也就是說不同的虛擬網(wǎng)絡不能共享底層物理節(jié)點。但是網(wǎng)絡虛擬化具有虛擬節(jié)點和虛擬鏈路的容量要求，并且底層節(jié)點和鏈路可以被不同的虛擬網(wǎng)絡共享，但同一個虛擬網(wǎng)絡內(nèi)的不同虛擬節(jié)點不能映射到同一個物理節(jié)點上。

為了減少虛擬網(wǎng)絡映射的難度，當前的研究從不同的角度來限制問題空間，包括:(1)設定所有請求的到達時間是靜態(tài)的、可知的，并且占用物理網(wǎng)絡的時間也是可知的［11-12］;(2)忽略請求的資源約束［13］;(3)設定物理網(wǎng)絡資源理想化，即資源是無限的［12-13］;(4)忽略請求拓撲的多樣性［11］。文獻［14］提到的分布式算法在沒有中央控制器的情況下，同時映射虛擬節(jié)點和虛擬鏈路，但是算法的規(guī)模和性能與中心控制算法相比相差許多。文獻［15］提出一種基于窗口的算法，根據(jù)收益大小來選擇虛擬網(wǎng)絡，此算法簡化了問題，類似線下解決方案;為了能夠接收更多的虛擬網(wǎng)絡請求，文獻［16］周期性地對底層物理環(huán)境中映射的虛擬鏈路進行重新映射來減少底層環(huán)境資源的碎片。

本文研究的問題是在線網(wǎng)絡映射也稱作動態(tài)網(wǎng)絡映射，并且充分考慮請求的資源約束。

2 虛擬網(wǎng)映射模型

虛擬網(wǎng)絡映射由3部分組成:虛擬網(wǎng)絡、底層物理網(wǎng)絡、虛擬網(wǎng)絡和底層物理網(wǎng)絡的映射約束。

2.1 底層網(wǎng)絡模型

底層網(wǎng)絡模型用加權(quán)無向圖表示為GS=(NS，LS)，其中NS是底層節(jié)點的集合，LS是節(jié)點集合中節(jié)點之間的底層鏈路集合。與屬于NS的底層節(jié)點ns相關(guān)的加權(quán)能力值分別為:C(ns)表示節(jié)點ns的CPU計算能力，Loc(ns)表示節(jié)點ns的地址位置，B(ns)表示與節(jié)點ns相連鏈路的帶寬資源，以及Deg(ns)表示與節(jié)點ns連接的鏈路個數(shù)，其值越大表示節(jié)點ns資源越稀缺。與屬于集合LS的節(jié)點i和j之間的鏈路ls(i，j)相關(guān)聯(lián)的兩個非負數(shù)為:(1)W(ls(i，j))表示鏈路的花費和延遲等一系列參數(shù)的集合;(2)C(ls(i，j))表示鏈路全部帶寬。

設φ為底層網(wǎng)絡GS中的底層路徑的集合，兩個底層節(jié)點間的底層路徑P∈φ的最大帶寬定義為底層路徑中的最小帶寬，即C(P)=C(ls(i，j));底層路徑的權(quán)重(花費、延遲、抖動等)W(P)定義為路徑P中的所有鏈路權(quán)重的和:W(P)=W(ls(i，j))。

2個物理節(jié)點的距離定義為底層網(wǎng)絡中2個節(jié)點的最小跳數(shù)。

2.2 虛擬網(wǎng)絡請求模型

用戶提交的對共享底層網(wǎng)絡的請求可以用加權(quán)無向圖表示為GV(NV，LV)，其中NV是虛擬節(jié)點的集合，LV是NV集合中節(jié)點之間的虛擬鏈路集合。每個屬于NV的虛擬節(jié)點nv與物理節(jié)點類似，具有相關(guān)加權(quán)能力值:C(nv)表示節(jié)點nv的CPU計算需求，Loc(nv)表示節(jié)點nv的地址位置需求，B(nv)表示與節(jié)點nv相連鏈路的帶寬資源需求，以及非負最大距離D(nv)表示從虛擬節(jié)點nv到映射節(jié)點ns的往返時延RTT 約束，即 dis(Loc(nv)，Loc(ns))≤D(nv)。兩個相連節(jié)點之間的虛擬鏈路lv∈LV的最低帶寬需求用能力加權(quán)值C(lv)表示，鏈路的花費和延遲用W(lv)表示。

虛擬網(wǎng)絡請求可以用四維的公式Req=(Reqid，GV，VV，MV)表示，其中 Reqid為請求的唯一標識。=(，)，其中和表示請求中的虛擬節(jié)點和虛擬鏈路。VV和MV分別表示圖GV中節(jié)點和鏈路的需求矩陣:是虛擬節(jié)點的需求向量，其中1 ≤i≤||。

M=[(C(l(i，j))，W(l(i，j)))]表示節(jié)點Vvv和之間的虛擬鏈路lv∈的需求矩陣。

2.3 底層網(wǎng)絡的資源負載

底層網(wǎng)絡的資源使用情況采用S標識，其中底層節(jié)點負載SN(ns)表示為:分配在該底層節(jié)上所有虛擬節(jié)點的CPU需求總和，即SN(ns)，其中ns∈NS，x→y表示虛擬節(jié)點x映射在底層物理節(jié)點y上;同樣地，底層鏈路負載SL(ls)表示為:所有分配的底層物理路徑經(jīng)過此鏈路的虛擬鏈路的帶寬總和，即SL(ls)，其中 ls∈LS，x→y 表示虛擬鏈路x映射到的底層路徑經(jīng)過底層鏈路y。

底層節(jié)點的剩余可用計算資源RN(ns)表示為底層節(jié)點ns∈NS的可用CPU資源，即RN(ns)=C(ns)-SN(ns)。同樣，底層鏈路的剩余可用帶寬資源RL(ls)表示為底層鏈路ls∈LS的所有可用帶寬的總量，即RL(ls)=C(ls)-SL(ls)。底層節(jié)點的剩余可用帶寬資源RL(ns)表示為所有與底層節(jié)點ns∈NS相連的鏈路的可用帶寬資源之和，即RL(ns)=(ls)，其中，ns≠nj。底層節(jié)點的所有資源RAN(ns)表示為:節(jié)點的CPU資源、節(jié)點的剩余可用帶寬資源以及與節(jié)點相連鏈路個數(shù)的乘積，即RAN(ns)=RN(ns)*RL(ns)*Deg(ns)。底層路徑P∈φ的可用帶寬能力表示為該路徑上所有底層鏈路的最小帶寬資源，即RL(P)=

2.4 虛擬網(wǎng)絡映射問題

基于底層和虛擬網(wǎng)絡模型，查找虛擬網(wǎng)絡GV到底層網(wǎng)絡GS的最佳映射方案是一個NP難問題。映射MAP需要底層網(wǎng)絡資源達到最好的負載均衡，并且在滿足能力約束情況的同時，減少花費。虛擬網(wǎng)絡映射可以分解為兩個組成部分。

(1)節(jié)點映射。設MAPN:→表示虛擬節(jié)點到底層節(jié)點的映射函數(shù)，其中表示至少能夠滿足請求中一個虛擬節(jié)點的底層節(jié)點的集合，即:

(2)鏈路映射。設MAPL→?∈φ表示虛擬鏈路和底層路徑之間的映射函數(shù)，其中?={P∈φ|RL(P)≥C(lv)，?lv∈}。

2.5 映射目標

虛擬網(wǎng)絡映射算法的目標為:虛擬網(wǎng)絡請求映射的成功率最大、產(chǎn)生的收益最大、消耗的資源最少。虛擬網(wǎng)絡請求映射的成功率定義為:θ=m/n，其中m為n個虛擬網(wǎng)絡請求映射成功的個數(shù);映射成功的收益定義為:

其中α表示鏈路帶寬資源和節(jié)點計算資源的相對權(quán)重;定義虛擬請求消耗的底層資源的總和為:

其中nv→ns和表示底層鏈路ls分配給虛擬鏈路lv的帶寬總和，αls與βns表示底層資源消耗的參數(shù)。由上可知，單位時間內(nèi)收益的提高可通過提高映射的成功率和首先映射收益較大的請求，由于要解決的屬于線上問題，請求不可預知，因此只能通過提高映射成功率來提高收益;映射資源的消耗可通過降低映射過程中鏈路映射到路徑的長度來解決。

3 優(yōu)化的兩階段協(xié)同映射算法

對映射目標分析可知，消耗資源的降低主要通過降低虛擬鏈路映射到物理路徑上的距離(距離指跳數(shù))，跳數(shù)越低則消耗的鏈路帶寬資源越少，因此提出一種綜合考慮節(jié)點映射和鏈路映射的兩階段協(xié)同映射算法。算法在節(jié)點映射階段采用貪婪算法來盡可能映射虛擬網(wǎng)絡上相鄰節(jié)點到底層網(wǎng)絡上的鄰近節(jié)點上，結(jié)合路徑遷移來解決瓶頸鏈路。算法在鏈路映射階段采用鏈路分流來解決瓶頸映射帶寬。其中路徑遷移和鏈路分流結(jié)束能夠使用底層物理網(wǎng)絡的鏈路碎片，從而提高映射的成功率;貪婪算法是為了解決在節(jié)點映射階段選取節(jié)點時，如何降低資源消耗的問題。本文采用的貪婪算法是集中映射的貪婪算法，即所有的虛擬節(jié)點盡可能映射到較小的底層物理網(wǎng)絡區(qū)域范圍，由此降低鏈路帶寬消耗。

3.1 節(jié)點映射

令F表示本次請求已經(jīng)完成映射的虛擬節(jié)點，S表示本次請求未映射到的物理節(jié)點。初始化時，F(xiàn)=Φ，S=Ns。

(1)統(tǒng)計每個虛擬節(jié)點nv的滿足其距離約束的物理節(jié)點集合，記作θ(nv)。按照nv計算需求從θ(nv)排除掉節(jié)點計算能力不夠的節(jié)點得δ(nv)={ns|RN(ns)≥C(nv)，ns∈NS}∩θ(nv)。若 δ(nv)= Φ，映射失敗，終止算法;統(tǒng)計S中每個節(jié)點的計算能力與相連鏈路帶寬和乘積，記作q(ns)。

(2)分別對底層節(jié)點的剩余可用帶寬資源RL(ns)和虛擬節(jié)點的帶寬需求B(nv)按照從大到小進行排序，排序的結(jié)果分別記作SSubBand和SReqBand。

(3)從SReqBand中選取尚未分配的第一個節(jié)點記作nv，并從SSubBand中查找大于B(nv)的物理節(jié)點，并與δ(nv)相交取得交集?(nv)。

(4)?(nv)={ns|B(nv)≤RL(ns)，ns∈S}∩δ(nv)。若?(nv)為空，進行第(4)步;否則進行第(5)步。

(5)從δ(nv)中查找本次請求中尚未分配的物理節(jié)點δ(nv)∩S，并且與該節(jié)點相連的鏈路在現(xiàn)已完成的映射中已被分配，統(tǒng)計與該節(jié)點相連的鏈路在現(xiàn)已完成映射的鏈路映射階段的帶寬消耗和(注:只統(tǒng)計節(jié)點既不作為路徑的源節(jié)點，也不作為路徑的目的節(jié)點的帶寬消耗)，將得到的帶寬和與該節(jié)點相連鏈路剩余帶寬和加起來，從結(jié)果集中查找大于帶寬請求的節(jié)點子集，繼續(xù)從中篩選出路徑遷移代價較小的(遷移鏈路個數(shù)最小)的幾個節(jié)點按照代價從小到大進行路徑遷移，并且要求后面的遷移不能影響前面節(jié)點的路徑遷移，如果全部遷移失敗，則映射失敗，終止算法;否則路徑遷移成功的節(jié)點記作集合?(nv)，更新帶寬資源和q(ns)，并繼續(xù)進行下一步。

(6)從F中查詢所有與節(jié)點nv相連的節(jié)點集合，記作 τ(nv)={nvi|l(nv，nvi)∈LV，nvi∈F}，若 τ(nv)≠Φ，分別統(tǒng)計?(nv)中每個節(jié)點與τ(nv)集合中所有節(jié)點映射到的物理節(jié)點ns的最短距離與對應虛擬鏈路帶寬的乘積和，并除以q(ns)，選擇結(jié)果最小的即為nv映射到的物理節(jié)點。若τ(nv)=Φ，則選擇?(nv)中節(jié)點的q(ns)最大的節(jié)點，作為nv映射到的物理節(jié)點。

(7)更新GN節(jié)點和帶寬的剩余資源，重新排序，并把nv添加到F中，映射到的物理節(jié)點從S中刪除，重復步驟(3)。

算法分析:該節(jié)點映射算法，結(jié)合了距離約束和節(jié)點相連的鏈路約束，減少了映射解的空間;算法采用路徑遷移來解決由于與節(jié)點相連的鏈路資源不足問題;算法第(6)步采用到已完成映射節(jié)點對應物理節(jié)點鏈路帶寬消耗最小和節(jié)點資源最大作為貪婪準則的貪婪算法來選取映射節(jié)點，能有效降低映射資源消耗中的帶寬消耗;如果有大量以往或未來虛擬網(wǎng)絡請求數(shù)據(jù)，可以統(tǒng)計所有虛擬節(jié)點的計算能力，形成概率分布，查找物理節(jié)點分配成功后剩余計算能力的對應概率，該概率表示將來能夠映射的可能性，概率越大映射的可能性越大，該概率加一并除以到已完成映射節(jié)點對應物理節(jié)點鏈路帶寬消耗的結(jié)果可以作為貪婪準則。

3.2 鏈路映射

該階段主要采用多商品流算法，算法默認采用了鏈路分割技術(shù)來解決節(jié)點鏈路資源能滿足需求，但單獨的鏈路不滿足映射的問題，如果不存在可行解，則拒絕本次映射請求，算法終止;否則，接受該請求，并更新節(jié)點和鏈路資源。

4 仿真實驗結(jié)果及分析

本文的仿真實驗環(huán)境采用GT-ITM工具生成網(wǎng)絡拓撲結(jié)構(gòu)，執(zhí)行時間為40000個時間單元，并參考文獻［15，17］分別設計生成底層網(wǎng)絡拓撲和虛擬網(wǎng)絡拓撲請求。其中底層網(wǎng)絡拓撲是模擬具有100個節(jié)點的中等規(guī)模的ISP，每對底層節(jié)點有0.5的概率隨機相連，底層節(jié)點CPU和底層鏈路帶寬資源都是服務參數(shù)為50和100的均勻分布。虛擬網(wǎng)絡的請求，以每100時間單元6虛擬網(wǎng)絡請求的速率泊松到達。每個虛擬網(wǎng)絡請求的生命周期服從均值為1000時間單元的指數(shù)分布，虛擬節(jié)點的個數(shù)服從參數(shù)為2和10的均勻分布，虛擬網(wǎng)絡節(jié)點對的連接率固定在0.5，虛擬節(jié)點的CPU需求服從參數(shù)為0和20的均勻分布，虛擬鏈路的帶寬需求服從參數(shù)為0和0的均勻分布，并且虛擬節(jié)點的位置隨機選取一個物理節(jié)點作為中心，滿足距離約束的節(jié)點是到中心節(jié)點的跳數(shù)為1或2的節(jié)點。

仿真實驗結(jié)果見圖2、圖3，并與文獻［17］中提到的兩階段映射算法D-ViNE進行對比，其中兩種算法依賴的軟硬件環(huán)境和算法的輸入是一致的，結(jié)果表明本文的算法在映射成功率、資源收益消耗比方面有一定程度的提高。

圖2 映射成功率對比圖

圖3 算法收益花費比對比圖

5 結(jié)束語

本文主要研究了網(wǎng)絡虛擬化中的關(guān)鍵問題——虛擬網(wǎng)絡映射問題，針對該問題進行了討論和分析，并基于現(xiàn)有的兩階段映射算法，加以優(yōu)化。該算法與現(xiàn)有算法相比，主要改進如下:(1)在節(jié)點映射的鏈路帶寬資源不能滿足需求的情況下，采用路徑遷移，提高了映射的成功率;(2)算法充分考慮了節(jié)點的位置、計算、帶寬等需求，使得映射更加符合真實情況;(3)節(jié)點映射階段綜合考慮了物理節(jié)點的資源和鏈路映射的帶寬消耗，并有效地把兩個階段協(xié)同起來，降低映射的資源消耗;(4)算法著重降低鏈路映射資源消耗;(5)本文分析了采用貪婪算法的原因以及貪婪準則。

［1］Thomas Anderson，Larry Peterson，Scott Shenker，et a1.Overcoming the Internet impasse through virtualization［J］.Computer，2005，38(4):34-41.

［2］Turner J，Taylor D.Diversifying the Internet［C］//Proceedings of the 2005 IEEE GLOBECOM.2005，2:755-760.

［3］Bavier A，F(xiàn)eamster N，Huang M，et al.In VINI veritas:Realistic and controlled network experimentation［C］//Proceedings of the 2006 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.2006:3-14.

［4］Feamster N，Gao L，Rexford J.How to lease the Internet in your spare time［J］.ACM SIGCOMM Computer Communication Review，2007，37(1):61-64.

［5］GENI.net.Global Environment for Network Innovations［EB/OL］.http://www.geni.net，2010-12-22.

［6］Jay Lepreau.Emulab:Network Emulation Testbed［EB/OL］.http://www.emulab.net，2006-12-22.

［7］The DETER Project.The DETER Testbed:Overview［DB/OL］.http://www.isi.edu/deter/docs/testbed.overview.pdf，2004-08-25.

［8］Andersen D G.Theoretical Approaches to Node Assignment［DB/OL］.http://www.cs.cmu.edu/～ dga/papers/andersen-assign-abstract.html，2002-12-01.

［9］Duffield N G，Goyal P，Greenberg A，et al.Resource management with hoses:Point-to-cloud services for virtual private networks［J］.IEEE/ACM Transactions on Networking，2002，10(5):679-692.

［10］Ricci R，Alfeld C，Lepreau J.A solver for the network testbed mapping problem［J］.ACM SIGCOMM Computer Communication Review，2003，33(2):65-81.

［11］Lu J，Turner J.Efficient Mapping of Virtual Networks onto a Shared Substrate［R］.Washington University，2006.

［12］Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components［C］//Proceedings of the 25th IEEE International Conference on Computer Communications.2006，6:2812-2823.

［13］Fan J，Ammar M.Dynamic topology configuration in service overlay networks:A study of reconfiguration policies［C］//Proceedings of the 25th IEEE International Conference on Computer Communications.2006，2:641-652.

［14］Chowdhury M，Samuel F，Boutaba R.PolyViNe:Policybased virtual network embedding across multiple domains［C］//Proceedings of the 2nd ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures.2010:49-56.

［15］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.

［16］Butt N F，Chowdhury M，Boutaba R.Topology-awareness and reoptimization mechanism for virtual network embedding［C］//Proceedings of the 9th IFIP TC 6 International Conference on Networking.2010:27-39.

［17］Chowdhury M，Rahman M R，Boutaba R.Virtual network embedding with coordinated node and link mapping［C］//Proceedings of the 28th IEEE International Conference on Computer Communications.2009:783-791.