分布式環(huán)境中基于協(xié)商的虛擬網(wǎng)映射算法

江逸茗，蘭巨龍，程?hào)|年，吳方明

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2.2 映射目標(biāo)

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

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

2.3 映射環(huán)境

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

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

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

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

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

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

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

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

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

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

3 分布式映射算法

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法流程

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

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

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

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

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

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

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

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

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

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

4) 對(duì)每個(gè)ns∈C計(jì)算χ(ns,nv)值，并按照該值對(duì)C中的節(jié)點(diǎn)排序；

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

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

3.2.2 主流程控制算法

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

算法2主流程控制算法

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

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

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

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

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

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

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

輸出：ASK消息或Failure消息

3.2.4 路徑搜索算法

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

3.3 沖突避免機(jī)制

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

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

4 仿真結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

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

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

4.2 參數(shù)影響

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

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

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

4.3 通信開銷

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

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

圖4 通信開銷

4.4 負(fù)載均衡

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

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

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

4.5 虛擬鏈路的路徑長(zhǎng)度

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

圖6 虛擬鏈路的平均路徑長(zhǎng)度

4.6 接收率

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

圖7 接收率

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

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

通過(guò)路徑分裂技術(shù)能夠提高虛擬鏈路的映射成功率，但也為虛擬網(wǎng)的控制和管理增加了一定的難度，因此在分布式虛擬網(wǎng)映射算法中如何引入路徑分裂機(jī)制有待進(jìn)一步研究。此外，本文算法只討論了單個(gè)域內(nèi)的映射問(wèn)題，而在涉及多個(gè)域的虛擬網(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ò)映射問(wèn)題研究綜述[J].通信學(xué)報(bào),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.