江逸茗，蘭巨龍，程東年，吳方明

(1. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002；2. 吉林大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130022 )

1 引言

隨著規(guī)模的不斷擴(kuò)大，現(xiàn)有互聯(lián)網(wǎng)結(jié)構(gòu)僵化、可擴(kuò)展性差的缺點日益突出，為不同網(wǎng)絡(luò)體系之間的融合以及網(wǎng)絡(luò)的更新?lián)Q代增加了一定困難。網(wǎng)絡(luò)虛擬化技術(shù)[1,2]成為了解決上述問題的重要技術(shù)手段。通過網(wǎng)絡(luò)虛擬化技術(shù)，服務(wù)提供商可以在共享的底層物理網(wǎng)絡(luò)上創(chuàng)建多個相互隔離的虛擬網(wǎng)(VN,virtual network)，從而為用戶提供多樣化的可定制端到端服務(wù)[3]，例如為網(wǎng)絡(luò)視頻會議或IPTV[4]等服務(wù)建立專門的虛擬網(wǎng)，以實現(xiàn)具有特定傳輸需求的高質(zhì)量服務(wù)。在虛擬網(wǎng)的運行環(huán)境中，基礎(chǔ)設(shè)施提供商(InP, infrastructure provider)負(fù)責(zé)管理和運營底層網(wǎng)絡(luò)，服務(wù)提供商(SP, service provider)以虛擬網(wǎng)請求的方式向InP申請網(wǎng)絡(luò)資源并建立服務(wù)。虛擬網(wǎng)的實現(xiàn)基礎(chǔ)是解決虛擬網(wǎng)請求的映射問題，也就是通過為虛擬網(wǎng)請求分配相應(yīng)的底層網(wǎng)絡(luò)資源，來實現(xiàn)虛擬網(wǎng)到底層網(wǎng)絡(luò)的映射。

目前，針對虛擬網(wǎng)映射問題的研究大部分采用了集中式的映射方法[5～12]，即由一個管理節(jié)點完成網(wǎng)絡(luò)狀態(tài)的收集維護(hù)和映射方案的決策。如果該管理節(jié)點出現(xiàn)故障，則整個網(wǎng)絡(luò)將面臨癱瘓的風(fēng)險，這種單點失效(single point of failure)現(xiàn)象將會給虛擬網(wǎng)的可靠性和穩(wěn)定性帶來較大的負(fù)面影響。

分布式的映射方法由于不依賴這種集中式的管理節(jié)點，使其在管理節(jié)點出現(xiàn)故障時仍然能夠正常的進(jìn)行虛擬網(wǎng)的映射和維護(hù)，從而有效地避免了單點失效現(xiàn)象，但現(xiàn)有的分布式算法[13]仍然存在3點不足：1) 算法要求網(wǎng)絡(luò)的全部節(jié)點周期性地相互交換資源狀態(tài)信息，這會帶來大量的通信開銷；2)在映射各個星形子拓?fù)鋾r僅考慮了節(jié)點的負(fù)載壓力，導(dǎo)致邏輯上相鄰的星形子拓?fù)淇赡芊謩e被映射到相距較遠(yuǎn)的底層節(jié)點上，使部分虛擬鏈路占用了過多的底層鏈路資源；3) 該算法未考慮底層節(jié)點和鏈路的最大資源能力限制，也未考慮并行映射時的資源沖突問題。

針對現(xiàn)有的分布式算法存在的問題，本文設(shè)計了一種基于節(jié)點協(xié)商的分布式虛擬網(wǎng)映射算法，該算法不依賴集中式的管理節(jié)點，不在全網(wǎng)范圍內(nèi)進(jìn)行大規(guī)模的狀態(tài)信息交換，僅通過節(jié)點之間的協(xié)商和狀態(tài)查詢來實現(xiàn)虛擬網(wǎng)的映射，從而降低了映射過程中產(chǎn)生的通信開銷。同時為了提升映射請求的響應(yīng)速度，部分子算法可在多個節(jié)點上并行執(zhí)行，并設(shè)計了相應(yīng)的機(jī)制來避免并行執(zhí)行過程中產(chǎn)生沖突。

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

2.1 網(wǎng)絡(luò)映射模型

虛擬網(wǎng)映射問題的模型描述如下。

底層網(wǎng)絡(luò)。底層網(wǎng)絡(luò)的拓?fù)淇梢杂脦?quán)無向圖Gs=(N s,Ls,CsN,CsL)表示，其中，N s和Ls是底層網(wǎng)絡(luò)的節(jié)點集合和鏈路集合，CsN和CsL分別為底層網(wǎng)絡(luò)的節(jié)點和鏈路所能提供的最大 CPU處理能力和最大帶寬。

虛擬網(wǎng)請求。一個虛擬網(wǎng)請求包括虛擬網(wǎng)拓?fù)銰v、映射請求到達(dá)時間ta和請求持續(xù)時間td。虛擬網(wǎng)拓?fù)淇梢杂脦?quán)無向圖Gv=(Nv,Lv,RvN,RvL)表示，其中，Nv為虛擬節(jié)點的集合，Lv為虛擬鏈路的集合，RvN和RvL分別表示虛擬節(jié)點和虛擬鏈路的資源需求約束。虛擬網(wǎng)請求在ta時刻到達(dá)后，底層網(wǎng)絡(luò)為其分配滿足RvN和RvL約束的網(wǎng)絡(luò)資源。虛擬網(wǎng)在運行td時刻后，其所占用的資源將被底層網(wǎng)絡(luò)回收。

虛擬網(wǎng)映射問題。虛擬網(wǎng)映射問題可以描述為將虛擬網(wǎng)請求的拓?fù)銰v映射到底層網(wǎng)絡(luò)拓?fù)銰s上，并且該映射要滿足RvN和RvL的約束

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

2.2 映射目標(biāo)

虛擬網(wǎng)的映射目標(biāo)主要是增加的InP的收益，同時降低其映射的開銷。InP的收益是由請求接收率(AR, acceptance ratio)來決定的，其定義為

其中，RS是成功映射的虛擬網(wǎng)數(shù)量，RT是虛擬網(wǎng)請求總數(shù)量。要想提高請求接收率就需要對資源進(jìn)行合理分配，資源的合理利用性體現(xiàn)在2方面：1) 負(fù)載均衡，也就是避免出現(xiàn)底層網(wǎng)絡(luò)的部分節(jié)點或鏈路負(fù)載過高而其他節(jié)點或鏈路卻利用率較低的現(xiàn)象；2）最短路徑優(yōu)先，一條虛擬鏈路的路徑可能由多條底層鏈路組成，若路徑的長度越長則意味著虛擬鏈路占用的帶寬資源也越多。因此，采用最短路徑優(yōu)先原則一方面能夠節(jié)約帶寬資源，提高請求接收率，另一方面能夠降低InP的映射開銷。

2.3 映射環(huán)境

虛擬網(wǎng)的映射環(huán)境可以分為集中式映射環(huán)境和分布式映射環(huán)境。

集中式映射環(huán)境指的是在底層網(wǎng)絡(luò)中存在至少一個中心管理節(jié)點，該節(jié)點負(fù)責(zé)收集和維護(hù)整個底層網(wǎng)絡(luò)的狀態(tài)信息，同時還負(fù)責(zé)虛擬網(wǎng)的映射、撤銷和正常運行維護(hù)。由于中心管理節(jié)點掌握了網(wǎng)絡(luò)的全局信息，因此可以根據(jù)底層網(wǎng)絡(luò)的資源利用狀態(tài)來制定虛擬網(wǎng)的映射策略，從而更加合理地分配底層網(wǎng)絡(luò)資源。但集中式映射環(huán)境也存在一些局限性，具體如下。

1) 若中心管理節(jié)點出現(xiàn)故障，將使底層網(wǎng)絡(luò)在故障期間無法處理虛擬網(wǎng)請求，并且對正在運行的虛擬網(wǎng)也將產(chǎn)生較大的負(fù)面影響，降低了整個網(wǎng)絡(luò)的可靠性和穩(wěn)定性。

2) 虛擬網(wǎng)有可能被映射在多個底層網(wǎng)絡(luò)域上。如果各個底層網(wǎng)絡(luò)域是由不同InP負(fù)責(zé)運營，則出于利益因素的考慮，各個網(wǎng)絡(luò)域可能不對外公布自身的拓?fù)錉顟B(tài)信息，導(dǎo)致無法在多個域之間建立一個中心管理節(jié)點。這就限制了集中式映射方法的應(yīng)用范圍。

3) 如果單個底層網(wǎng)絡(luò)域的規(guī)模較大，則維護(hù)網(wǎng)絡(luò)的狀態(tài)信息將需要大量的通信開銷，并加重中心管理節(jié)點的信息處理壓力。

由于分布式映射算法不需要底層網(wǎng)絡(luò)的全局狀態(tài)信息，因此在分布式映射環(huán)境中可以不用設(shè)置中心管理節(jié)點，也就避免了集中式管理帶來的問題。相對于集中式環(huán)境來說，分布式映射環(huán)境存在以下不同。

1) 集中式環(huán)境中，只有中心管理節(jié)點能夠接收和處理虛擬網(wǎng)請求。而在分布式環(huán)境中，底層網(wǎng)絡(luò)的任意一個節(jié)點都可以接收并處理虛擬網(wǎng)請求。

2) 集中式環(huán)境中，中心管理節(jié)點掌握了網(wǎng)絡(luò)域內(nèi)所有節(jié)點和鏈路的資源狀態(tài)信息。在分布式環(huán)境中，每個節(jié)點只掌握本節(jié)點以及連接在本節(jié)點上所有鏈路的資源狀態(tài)信息。若某個節(jié)點要想知道其他節(jié)點或鏈路的狀態(tài)信息，需要通過發(fā)送狀態(tài)查詢消息來實現(xiàn)。

3) 集中式環(huán)境中，虛擬網(wǎng)的映射策略是中心管理節(jié)點根據(jù)其維護(hù)的全網(wǎng)資源狀態(tài)信息來制定的。而分布式環(huán)境中，虛擬網(wǎng)的映射策略是通過各個節(jié)點之間的相互協(xié)商來制定的。

4) 集中式環(huán)境中，虛擬網(wǎng)請求是依次被處理的。但在分布式環(huán)境中，可能有多個虛擬網(wǎng)請求同時被映射，在各個并行的映射進(jìn)程之間可能會產(chǎn)生沖突。

3 分布式映射算法

在虛擬網(wǎng)的分布式映射環(huán)境中，由于沒有節(jié)點來維護(hù)底層網(wǎng)絡(luò)的全局信息，因此虛擬網(wǎng)的分布式映射需要通過底層節(jié)點之間的協(xié)商和信息交換來完成。但是節(jié)點之間過多的通信不但會加重網(wǎng)絡(luò)的負(fù)擔(dān)，還會影響映射請求的響應(yīng)速度。因此，對于分布式映射算法來說，不但要實現(xiàn)底層資源的合理利用，還要盡量降低映射時的通信開銷。

針對單個域內(nèi)的分布式映射問題，本文提出一種基于協(xié)商的分布式虛擬網(wǎng)映射算法(N-DVE, distributed VN embedding algorithm based on negotiation)，該算法考慮了底層節(jié)點和鏈路的最大能力限制，并盡量減少了分布式映射時狀態(tài)信息的交換次數(shù)。映射時的狀態(tài)信息獲取和控制命令下發(fā)等操作都是通過分布式映射協(xié)議實現(xiàn)的。

3.1 分布式映射協(xié)議

分布式映射協(xié)議主要用于節(jié)點間的協(xié)商，該協(xié)議由資源狀態(tài)查詢和控制命令這2大類消息組成。資源狀態(tài)查詢消息是用于底層節(jié)點之間的資源狀態(tài)信息交換，具體包括以下幾方面。

1) Query(ns)：向一個底層節(jié)點ns查詢其資源狀態(tài)，包括ns的可用CPU資源、連接在ns上的所有底層鏈路的可用帶寬資源。

2) PathQuery(p)：該消息可用來查詢某個底層路徑p的最小可用帶寬。

控制命令類消息主要用于在虛擬網(wǎng)映射過程中向節(jié)點下發(fā)各種控制命令，以實現(xiàn)各個節(jié)點之間的協(xié)同映射。

3) Authorize(ns,nv,Gv)：將虛擬節(jié)點nv的映射決策權(quán)授予底層節(jié)點ns。此外，該消息還將為映射決策提供必要的狀態(tài)信息，如映射請求的拓?fù)銰v、已映射的節(jié)點和鏈路信息等。

4) Failure(ns,nv)：當(dāng)?shù)讓庸?jié)點ns向另一個底層節(jié)點n'授權(quán)進(jìn)行虛擬節(jié)點nv的映射決策后，若n'無法為nv確定一個滿足約束條件的映射目標(biāo)時，則n'要向ns發(fā)送一個映射失敗的反饋消息。

5) Embed(ns,nv,lv,p,backup)：用于下發(fā)映射執(zhí)行命令，也就是將虛擬節(jié)點nv映射到底層節(jié)點ns上，或?qū)⑻摂M鏈路lv映射到底層路徑p上，backup是沖突避免機(jī)制的備選映射方案。

6) ASK (ns,nv)：當(dāng)被授權(quán)的底層節(jié)點ns成功映射虛擬節(jié)點nv后，返回一個確認(rèn)消息。

7) Start(Req,N')：當(dāng)映射請求Req的所有虛擬節(jié)點和鏈路都已經(jīng)被映射后，由某個特定節(jié)點向被Req映射的底層節(jié)點集合N'下達(dá)虛擬網(wǎng)開始運行的命令。

8) Stop(Req,N')：在映射請求Req的映射過程中，如果無法為某個虛擬節(jié)點或鏈路找到合適的映射目標(biāo)，則向已被Req映射的底層節(jié)點集合N'下達(dá)撤銷映射的命令，該虛擬網(wǎng)請求將被拒絕。

3.2 算法流程

為了降低通信開銷，本算法將不會在全網(wǎng)范圍內(nèi)進(jìn)行周期性的狀態(tài)信息交換，在虛擬網(wǎng)映射的過程中僅根據(jù)需要來對部分節(jié)點進(jìn)行狀態(tài)信息的查詢，從而最大程度地減少無用的狀態(tài)信息傳遞。此外，由于算法在計算多條路徑時需要全網(wǎng)拓?fù)?，因此，要求底層網(wǎng)絡(luò)使用的路由協(xié)議能夠支持每個節(jié)點都維護(hù)一個全網(wǎng)拓?fù)浣Y(jié)構(gòu)圖，如OSPF協(xié)議。

在映射時將被映射的第一個底層節(jié)點設(shè)為虛擬網(wǎng)的中心節(jié)點，該節(jié)點將與其他節(jié)點協(xié)同完成后續(xù)的映射操作，在映射完成后由中心節(jié)點下達(dá)虛擬網(wǎng)的Start和Stop命令。在映射時，N-DVE算法按照與中心節(jié)點的距離將虛擬節(jié)點分為多個層次，同一層次中的虛擬節(jié)點將會由多個底層節(jié)點并行的進(jìn)行映射。

N-DVE算法由4個子算法組成，分別是：中心節(jié)點選擇算法、主流程控制算法、映射目標(biāo)搜索算法和路徑搜索算法。中心節(jié)點選擇算法是由接收虛擬網(wǎng)請求的節(jié)點來執(zhí)行，主流程控制算法是由中心節(jié)點來執(zhí)行，而映射目標(biāo)搜索算法和路徑搜索算法則是并行地運行在多個被授權(quán)的底層節(jié)點上。

3.2.1 中心節(jié)點選擇算法

在分布式映射環(huán)境中，接收虛擬網(wǎng)請求的可能是某一特定節(jié)點，也可能是底層網(wǎng)絡(luò)中的任意一個節(jié)點。當(dāng)某節(jié)點接收到虛擬網(wǎng)請求后，將調(diào)用中心節(jié)點選擇算法來從底層網(wǎng)絡(luò)中選取一個可用資源較多的底層節(jié)點作為中心節(jié)點。底層節(jié)點的可用資源既包括其自身的可用 CPU資源，也包括與其相連的底層鏈路的可用帶寬，底層節(jié)點的可用資源狀態(tài)的定義為

其中，CR表示底層節(jié)點ns或底層鏈路ls的剩余可用資源，NL表示連接在某個底層節(jié)點上的底層鏈路集合，β為權(quán)重因子，d(nv)表示虛擬節(jié)點nv的度數(shù)。算法流程如算法1所示。

算法1中心節(jié)點選擇算法

1) 接收虛擬網(wǎng)請求，選擇度數(shù)最大的虛擬節(jié)點nv作為初始映射節(jié)點；

2) 向所有底層節(jié)點發(fā)送Query消息；

3) 將按時反饋狀態(tài)信息并有足夠資源承載nv的底層節(jié)點加入候選集C；

4) 對每個ns∈C計算χ(ns,nv)值，并按照該值對C中的節(jié)點排序；

5) 選擇χ值最高的底層節(jié)點nmin作為中心節(jié)點；

6) 發(fā)送Authorize消息將虛擬網(wǎng)的映射控制權(quán)交給nmin。

3.2.2 主流程控制算法

當(dāng)中心節(jié)點選擇算法運行完以后，虛擬網(wǎng)的映射控制權(quán)就移交給運行在中心節(jié)點上的主流程控制算法。該算法主要負(fù)責(zé)分發(fā)虛擬節(jié)點的映射授權(quán)。首先，將Gv中度數(shù)最大的虛擬節(jié)點nv映射到中心節(jié)點上，并按照與nv的最短路徑長度將剩余的虛擬節(jié)點劃分為多個層次（如與nv距離為i跳的虛擬節(jié)點設(shè)為第i層，nv設(shè)為第0層），然后，將按照層次由低到高的次序依次對虛擬節(jié)點的映射控制權(quán)進(jìn)行分發(fā)。當(dāng)?shù)趇層的虛擬節(jié)點全部映射完畢后，中心節(jié)點將會把第i+1層的虛擬節(jié)點nv的控制權(quán)交給與其相連的第i層虛擬節(jié)點，如果nv與多個第i層節(jié)點相連，則依次檢查這些節(jié)點對之間的虛擬鏈路，并將控制權(quán)交給帶寬需求最大的虛擬鏈路的端節(jié)點，這樣就能使占用帶寬較多的虛擬鏈路更有可能被映射到較短的底層路徑上，從而減少虛擬鏈路占用的帶寬資源。算法流程如算法2所示。

算法2主流程控制算法

輸入：映射請求的拓?fù)銰v；

3.2.3 映射目標(biāo)搜索算法

收到中心節(jié)點映射授權(quán)的底層節(jié)點稱為執(zhí)行節(jié)點，執(zhí)行節(jié)點將會運行映射目標(biāo)搜索算法。該算法從授權(quán)消息中獲取待映射的虛擬節(jié)點，并為這些虛擬節(jié)點搜索合適的映射目標(biāo)，同時還要完成部分虛擬鏈路的映射。

算法首先要為待映射的虛擬節(jié)點搜索符合資源約束的映射目標(biāo)，為了縮短虛擬鏈路的路徑長度，并減少信息收集的時間消耗，可以將搜索的范圍限定在執(zhí)行節(jié)點周圍h跳以內(nèi)。如果底層網(wǎng)絡(luò)采用的路由協(xié)議支持區(qū)域劃分（如 OSPF協(xié)議中的Area機(jī)制），還可以把映射目標(biāo)的搜索范圍限定在執(zhí)行節(jié)點所在的區(qū)域或是其鄰接區(qū)域內(nèi)，從而進(jìn)一步降低搜索的時間和虛擬鏈路的路徑長度。在搜索到多個可用映射目標(biāo)以后，需要對每個映射目標(biāo)進(jìn)行評價并選出最優(yōu)目標(biāo)。本文用映射評價系數(shù)μ來對映射目標(biāo)進(jìn)行評價，其定義為

其中，nv是待映射的虛擬節(jié)點，ns是nv的可用映射目標(biāo)，lv是連結(jié)nv與執(zhí)行節(jié)點的虛擬鏈路，R(lv)是lv的帶寬需求約束，Lp是lv的底層路徑長度。在對各個可用映射目標(biāo)按μ值進(jìn)行排序后，就可以選出最優(yōu)的映射目標(biāo)，并將待映射虛擬節(jié)點映射到該目標(biāo)上。算法流程如算法3所示。

算法3映射目標(biāo)搜索算法

輸入：映射請求的拓?fù)銰v，待映射的虛擬節(jié)點集合Nv，最大跳數(shù)h；

輸出：ASK消息或Failure消息

3.2.4 路徑搜索算法

路徑搜索算法用于在2個底層節(jié)點之間尋找一條滿足帶寬約束的路徑。其流程是先調(diào)用K短路徑算法[14]計算出多條路徑，然后通過發(fā)送 PathQuery消息來檢查每一條路徑的最小可用帶寬，最后挑選長度最短的可用路徑作為算法的輸出結(jié)果。

3.3 沖突避免機(jī)制

在分布式的虛擬網(wǎng)映射環(huán)境中，有可能在同一時刻存在多個正在被處理的映射請求，且每個映射請求是由不同的中心節(jié)點進(jìn)行處理。而 N-DVE算法是通過查詢響應(yīng)機(jī)制來獲取網(wǎng)絡(luò)的資源狀態(tài)，從查詢到映射命令下達(dá)之間會存在一定的時間差，這就使多個虛擬網(wǎng)在并行映射時，可能由于彼此之間缺乏協(xié)商而引發(fā)沖突。這種沖突會導(dǎo)致部分虛擬網(wǎng)的映射流程出現(xiàn)錯誤，比如若某個虛擬網(wǎng)通過向一個底層節(jié)點ns發(fā)送Query消息獲知ns能夠滿足自身的映射要求，但在ns收到其發(fā)出的Embed命令之前，另一個虛擬網(wǎng)通過發(fā)送Embed命令將自己的虛擬節(jié)點映射在ns上，這就可能導(dǎo)致ns在收到前一個虛擬網(wǎng)的Embed命令時已經(jīng)沒有足夠的資源滿足該虛擬網(wǎng)的映射要求，從而使映射流程出現(xiàn)錯誤。

針對該問題，N-DVE設(shè)計了一種沖突避免機(jī)制。在執(zhí)行節(jié)點向虛擬節(jié)點nv的映射目標(biāo)發(fā)送Embed命令時(映射目標(biāo)搜索算法的步驟16))，會選擇一個次優(yōu)的映射目標(biāo)作為nv的備選映射方案加入到 Embed命令里。在映射目標(biāo)節(jié)點收到 Embed命令后，首先，檢查自身的資源狀態(tài)是否依然能夠滿足nv的映射要求，若不能滿足則表明可能出現(xiàn)了映射沖突現(xiàn)象，這時該節(jié)點將會直接把Embed命令轉(zhuǎn)發(fā)給備選映射方案所指定的映射目標(biāo)，由備選底層節(jié)點完成nv的映射。這樣就可以使2個映射進(jìn)程在某個底層節(jié)點上發(fā)生沖突時，其中一個進(jìn)程將可以通過執(zhí)行備選映射方案來回避在該節(jié)點上的映射沖突，從而避免由此帶來的死鎖或映射失敗等問題。

4 仿真結(jié)果分析

4.1 實驗環(huán)境

本實驗在Pentium 4 CPU 3.2 GHz、1 GB內(nèi)存的PC機(jī)上運行。底層網(wǎng)絡(luò)拓?fù)浜吞摂M網(wǎng)請求的拓?fù)溆?GT-ITM[15]工具生成，底層網(wǎng)絡(luò)共包括共包含100個節(jié)點和570條鏈路，底層節(jié)點的計算資源和底層鏈路的帶寬資源取值在[50,100]內(nèi)均勻分布。虛擬網(wǎng)請求共計 2 000個，每個請求的節(jié)點個數(shù)在[2,10]內(nèi)均勻分布，節(jié)點連接概率為0.25，虛擬節(jié)點的資源取值在[0,20]，虛擬鏈路的帶寬取值在[0,35]之間均勻分布，請求的到達(dá)時間服從平均100個單位時間到達(dá)5個請求的泊松過程，持續(xù)時間服從參數(shù)為1 000的指數(shù)分布。

實驗將選取一種分布式算法 DVNMA[13]作為N-DVE算法的比較對象，DVNMA的狀態(tài)通告周期為5個時間單位。DVNMA與N-DVE都屬于基于貪婪思想的映射算法，因此為了在虛擬鏈路的路徑長度和接收率等方面進(jìn)行進(jìn)一步比較，實驗還選取了一種基于貪婪思想的集中式算法 G-SP[5]作為N-DVE算法的比較對象。G-SP在集中式環(huán)境下運行，不啟用路徑分裂和重映射機(jī)制。N-DVE算法的參數(shù)設(shè)置為k=3，β=0.1。每處理100個虛擬網(wǎng)請求記錄一次實驗數(shù)據(jù)。

4.2 參數(shù)影響

在映射目標(biāo)搜索算法中，執(zhí)行節(jié)點在為待映射的節(jié)點搜索映射目標(biāo)時，為了減少通信開銷和響應(yīng)時間，可以通過設(shè)置參數(shù)h來限制映射目標(biāo)與執(zhí)行節(jié)點之間的距離。h值越小則意味著映射目標(biāo)搜索的范圍越小，節(jié)點映射失敗的概率會相應(yīng)的增加，但由于降低了虛擬鏈路的帶寬資源占用，所以降低了鏈路映射失敗的概率。因此可以根據(jù)節(jié)點和鏈路的資源狀態(tài)來對參數(shù)h進(jìn)行設(shè)置，節(jié)點資源緊張時h可以設(shè)置得較大，鏈路資源緊張時可以將h設(shè)置得較小。

如圖2所示，隨著h值的增加，N-DVE搜索映射目標(biāo)的范圍也越大，所以映射一個虛擬網(wǎng)所需的平均資源查詢消息數(shù)量也就越多。同時，搜索范圍的增大會導(dǎo)致路徑搜索算法的調(diào)用次數(shù)增加，因此若h值增大，則算法的響應(yīng)時間也會增長（如圖2所示）。在后續(xù)實驗中，h的值設(shè)為3。

圖2 N-DVE映射虛擬網(wǎng)時所需的平均消息數(shù)

4.3 通信開銷

N-DVE是通過小范圍內(nèi)的查詢響應(yīng)機(jī)制來獲取網(wǎng)絡(luò)的狀態(tài)信息，而DVNMA則是通過在全網(wǎng)范圍內(nèi)進(jìn)行周期性的信息交換來獲取網(wǎng)絡(luò)的狀態(tài)信息。因此，與DVNMA相比，N-DVE映射時所花費的通信開銷更少。實驗統(tǒng)計了 N-DVE算法和DVNMA算法映射一個虛擬網(wǎng)所需的平均消息數(shù)量，由圖 4可知，N-DVE算法的通信開銷僅為DVNMA算法的20%左右。

圖3 N-DVE算法的平均響應(yīng)時間

圖4 通信開銷

4.4 負(fù)載均衡

為了合理利用底層網(wǎng)絡(luò)的資源，應(yīng)將負(fù)載均衡情況作為虛擬網(wǎng)映射算法的評價標(biāo)準(zhǔn)之一。本實驗用平均負(fù)載方差來衡量算法的負(fù)載均勻程度，定義為

其中，N s、Ls分別是底層節(jié)點和鏈路的集合，S表示某個底層節(jié)點或鏈路的負(fù)載壓力，也就是已分配資源在該節(jié)點或鏈路的資源總量中占有的比例，Sarg表示底層網(wǎng)絡(luò)中全部節(jié)點或鏈路的平均負(fù)載壓力。由式(5)可知，平均負(fù)載方差同時評價了底層網(wǎng)絡(luò)中的節(jié)點和鏈路的負(fù)載均衡情況，該值越小表示評價越好。如圖 5所示，N-DVE的平均負(fù)載方差優(yōu)于DVNMA，與G-SP處于同一水平。

圖5 平均負(fù)載方差

4.5 虛擬鏈路的路徑長度

虛擬鏈路的路徑長度主要是用來衡量底層鏈路帶寬資源的利用效率，較短的虛擬鏈路路徑長度意味著虛擬網(wǎng)占用的底層鏈路帶寬資源較少，從而使底層網(wǎng)絡(luò)能承載更多的虛擬網(wǎng)。在 N-DVE算法中，當(dāng)執(zhí)行節(jié)點為每個待映射節(jié)點選擇映射目標(biāo)時，都會考慮該目標(biāo)與執(zhí)行節(jié)點的距離，使其在負(fù)載均衡的前提下盡量縮短虛擬鏈路的路徑長度。而DVNMA算法在映射時將虛擬網(wǎng)拓?fù)洳鸱譃槎鄠€星形子拓?fù)?，但在映射這些星形子拓?fù)鋾r只考慮了子拓?fù)鋬?nèi)部節(jié)點之間的距離，而沒有考慮各個子拓?fù)渲g的距離，使其虛擬鏈路的平均路徑長度要高于N-DVE（如圖6所示）。G-SP算法由于是一種兩階段映射算法，節(jié)點映射和鏈路映射是分開進(jìn)行的，因此算法在映射虛擬節(jié)點時沒有考慮縮短虛擬鏈路的長度，導(dǎo)致其虛擬鏈路的平均路徑長度最長。

圖6 虛擬鏈路的平均路徑長度

4.6 接收率

接收率決定了InP的收益，接收率的高低與負(fù)載均衡程度和虛擬鏈路長度有很大的關(guān)系。由于N-DVE算法在上述 2個評價標(biāo)準(zhǔn)中都有較好的表現(xiàn)，因此其接收率要高于DVNMA算法和G-SP算法如圖7所示。

圖7 接收率

5 結(jié)束語

本文研究了分布式環(huán)境下的虛擬網(wǎng)映射算法。首先，分析了集中式映射與分布式映射之間的差別，闡述了分布式映射的特點和應(yīng)用場景。針對已有的分布式算法通信開銷大、虛擬鏈路占用資源過多的缺點，設(shè)計了一種基于協(xié)商的分布式虛擬網(wǎng)映射算法，該算法僅在小范圍內(nèi)進(jìn)行狀態(tài)信息的交換，并且在降低映射代價方面進(jìn)行了優(yōu)化設(shè)計。此外，為了支持并行處理能力，算法還加入了沖突避免機(jī)制。實驗證明，本算法只需要以較小的通信代價就能在各項指標(biāo)上獲得較好的評價。

通過路徑分裂技術(shù)能夠提高虛擬鏈路的映射成功率，但也為虛擬網(wǎng)的控制和管理增加了一定的難度，因此在分布式虛擬網(wǎng)映射算法中如何引入路徑分裂機(jī)制有待進(jìn)一步研究。此外，本文算法只討論了單個域內(nèi)的映射問題，而在涉及多個域的虛擬網(wǎng)映射中，如何協(xié)同利用分布式與集中式的映射算法也是有待探索的工作。

[1] CHOWDHURY M, BOUTABA R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5): 862-876.

[2] JORGE C, JAVIER J. Network virtualization-a view from the bottom[A]. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures[C]. Barcelona, Spain, 2009.73-80.

[3] 程祥, 張忠寶, 蘇森等. 虛擬網(wǎng)絡(luò)映射問題研究綜述[J].通信學(xué)報,2011,32(10):143-151.CHENG X, ZHANG Z, SU S,et al. Survey of virtual network embedding problem[J]. Journal on Communications, 2011, 32(10): 143-151.

[4] BIAO S, MOHAMMAD H, EUI-NAM H. Delivering IPTV service over a virtual network: a study on virtual network topology[J]. Journal of Communications and Networks, 2012,14(3):319-335.

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

[6] CHOWDHURY M, RAHMAN MR, BOUTABA R. ViNEyard: virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE Transactions on Networking, 2012, 20(1): 206-219.

[7] ZHANG M, YANG Q, WU C,et al. Hierarchical virtual network mapping algorithm for large-scale network virtualisation[J]. IET communications, 2012, 6 (13): 1969-1978.

[8] FAJJARI I, AITSAADI N, PUJOLLE G,et al. VNE-AC: Virtual network embedding algorithm based on ant colony metaheuristic[A]. Proc IEEE ICC 2011[C]. Kyoto, Japan, 2011.1-6.

[9] ZHANG Z, CHENG X, SU S,et al. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J].International Journal of Communication Systems, 2012, doi:10.1002/dac.1399.

[10] YU H F, QIAO C M, ANAND V,et al. Survivable virtual infrastructure mapping in a federated computing and networking system under single regional failures[A]. Proc IEEE GLOBECOM 2010[C]. Miami,USA, 2010.1-6.

[11] CAI Z, LIU F, XIAO N,et al. Virtual network embedding for evolving networks[A]. Proc IEEE GLOBECOM 2010[C]. Miami, USA, 2010.1-5.

[12] FAJJARI I, AITSAADI N, PUJOLLE G,et al. VNR algorithm: a greedy approach for virtual networks reconfigurations[A]. Proc IEEE GLOBECOM 2011[C]. Houston, USA, 2011.1-5.

[13] HOUIDI I, LOUATI W, ZEGHLACHE D. A distributed virtual network mapping algorithm[A]. Proc IEEE ICC[C]. Beijing, China,2008.5634-5640.

[14] EPPATEIN D. Finding thekshortest paths[A]. IEEE Symposium on Foundations of Computer Science[C]. SantaFe, NM, 1994. 154-165.

[15] ZEGURA E, CALVERT K, BHATTACHARJEE S. How to model an internetwork[A]. Proc IEEE INFOCOM[C]. San Francisco, USA,1996.594-602.