集中與分布：協(xié)同虛擬網(wǎng)絡(luò)映射

豐旻　廖建新　王敬宇

摘要：結(jié)合傳統(tǒng)集中式和分布式兩類算法各自的特性，提出了協(xié)同虛擬網(wǎng)絡(luò)映射算法。該算法保留了集中式算法中擁有全局視野的中心控制實(shí)體，負(fù)責(zé)總體控制和關(guān)鍵決策，同時(shí)將具體映射方案的計(jì)算過程交給有限的底層網(wǎng)絡(luò)子集實(shí)現(xiàn)；唯一的中心控制實(shí)體與多個(gè)底層節(jié)點(diǎn)相互配合協(xié)作，共同完成虛擬網(wǎng)絡(luò)映射的整個(gè)過程。該算法繼承了集中式和分布式算法各自的優(yōu)勢(shì)，有效彌補(bǔ)了二者的缺陷，初步的仿真試驗(yàn)也證明了其可行性和有效性。

關(guān)鍵詞： 網(wǎng)絡(luò)虛擬化；虛擬網(wǎng)絡(luò)映射；集中；分布；協(xié)同虛擬網(wǎng)絡(luò)映射

1 網(wǎng)絡(luò)虛擬化

作為消除互聯(lián)網(wǎng)僵化頑疾的強(qiáng)大工具，網(wǎng)絡(luò)虛擬化被視為下一代網(wǎng)絡(luò)架構(gòu)的關(guān)鍵技術(shù)，獲得了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注[1-5]。網(wǎng)絡(luò)虛擬化通過虛擬化技術(shù)將作為基礎(chǔ)設(shè)施的底層網(wǎng)絡(luò)抽象為相應(yīng)的虛擬底層，通過虛擬資源切片的方式，將多個(gè)彼此隔離且異構(gòu)的虛擬網(wǎng)絡(luò)同時(shí)映射到其上。許多新的計(jì)算和網(wǎng)絡(luò)技術(shù)都受益于網(wǎng)絡(luò)虛擬化，如軟件定義網(wǎng)絡(luò)、云計(jì)算和數(shù)據(jù)中心網(wǎng)絡(luò)。在網(wǎng)絡(luò)虛擬化環(huán)境中，傳統(tǒng)的網(wǎng)絡(luò)服務(wù)提供商自然分化為負(fù)責(zé)部署、管理和維護(hù)底層網(wǎng)絡(luò)資源的基礎(chǔ)設(shè)施提供商和租用網(wǎng)絡(luò)資源構(gòu)建虛擬網(wǎng)絡(luò)以向終端用戶提供多樣化服務(wù)的服務(wù)提供商。

2 集中式和分布式的虛擬

網(wǎng)絡(luò)映射

基礎(chǔ)設(shè)施提供商需要采用有效的算法來(lái)將虛擬網(wǎng)絡(luò)請(qǐng)求映射到底層網(wǎng)絡(luò)的特定節(jié)點(diǎn)和鏈路上，以更加有效且高效地使用底層網(wǎng)絡(luò)資源。這就是虛擬網(wǎng)絡(luò)映射問題。然而由于存在多維的資源限制和多個(gè)目標(biāo)，使得無(wú)論問題空間是否受限，虛擬網(wǎng)絡(luò)映射問題都是NP難的[6]。隨著網(wǎng)絡(luò)虛擬化技術(shù)的快速發(fā)展和應(yīng)用，虛擬網(wǎng)絡(luò)映射便成了其中亟待解決的核心問題之一。

難以駕馭的計(jì)算復(fù)雜性促使研究者們專注于設(shè)計(jì)各種啟發(fā)式算法來(lái)尋找接近最優(yōu)解的切實(shí)可行的映射解決方案[7-14]?，F(xiàn)有虛擬網(wǎng)絡(luò)映射算法可以按照不同的標(biāo)準(zhǔn)進(jìn)行多種分類，如按照節(jié)點(diǎn)映射與鏈路映射是同時(shí)進(jìn)行還是先后進(jìn)行，分為一階段算法和兩階段算法（如文獻(xiàn)[8]、文獻(xiàn)[9]、文獻(xiàn)[11]）；按照涉及單個(gè)還是多個(gè)基礎(chǔ)設(shè)施提供商，分為單域算法（如文獻(xiàn)[9]、文獻(xiàn)[10]、文獻(xiàn)[11]）和多域算法（如文獻(xiàn)[14]）；按照考慮可生存性分配備用冗余資源（如文獻(xiàn)[7]、文獻(xiàn)[8]）與否等標(biāo)準(zhǔn)進(jìn)行分類。本文中我們考慮虛擬網(wǎng)絡(luò)映射實(shí)現(xiàn)的控制方式，將現(xiàn)有虛擬網(wǎng)絡(luò)映射算法分為集中式的虛擬網(wǎng)絡(luò)映射算法和分布式的虛擬網(wǎng)絡(luò)映射算法兩大類。

2.1 集中式虛擬網(wǎng)絡(luò)映射算法

在集中式算法中，只有一個(gè)唯一的中心控制實(shí)體負(fù)責(zé)映射的全部決策。集中式算法的優(yōu)勢(shì)在于這個(gè)唯一的中心控制實(shí)體通過收集、評(píng)估和管理底層網(wǎng)絡(luò)中的所有資源信息而具有全局視野，清楚的了解整個(gè)網(wǎng)絡(luò)的各種信息，因此更可能找出全局最優(yōu)或者至少接近全局最優(yōu)的映射方案，資源分配的過程中也不會(huì)發(fā)生沖突等情況。邏輯上集中的控制也使得根據(jù)具體業(yè)務(wù)需求進(jìn)行的全局資源調(diào)配和優(yōu)化成為可能，并使得整個(gè)虛擬網(wǎng)絡(luò)的映射運(yùn)營(yíng)過程便于維護(hù)調(diào)整，提升了網(wǎng)絡(luò)控制的便捷性。但是另一方面，這個(gè)唯一的控制實(shí)體也就成為了整個(gè)網(wǎng)絡(luò)的“瓶頸”。隨著底層網(wǎng)絡(luò)的不斷擴(kuò)容，中心控制實(shí)體與眾多節(jié)點(diǎn)間的通信數(shù)量將呈指數(shù)增長(zhǎng)，及時(shí)獲取底層資源的實(shí)時(shí)信息將越來(lái)越難以完成，因此對(duì)于網(wǎng)絡(luò)拓?fù)洳粩嘧兓膭?dòng)態(tài)網(wǎng)絡(luò)來(lái)說延遲較高。其面對(duì)大尺度網(wǎng)絡(luò)則很容易出現(xiàn)擴(kuò)展性問題和產(chǎn)生系統(tǒng)單點(diǎn)故障，而一旦中心控制實(shí)體出現(xiàn)問題，整個(gè)網(wǎng)絡(luò)的映射、運(yùn)行、管理和維護(hù)就會(huì)難以為繼。

俞敏嵐等[9]將虛擬網(wǎng)絡(luò)映射分為節(jié)點(diǎn)映射和鏈路映射兩個(gè)階段，并假定底層物理網(wǎng)絡(luò)支持靈活的路徑分割和周期性的路徑遷移。算法采用了貪婪的節(jié)點(diǎn)映射，鏈路映射階段則使用多商品流算法或K最短路徑算法求解。

Chowdhury等[10]通過在節(jié)點(diǎn)映射階段考慮鏈路的帶寬限制，來(lái)協(xié)調(diào)節(jié)點(diǎn)映射和鏈路映射。算法結(jié)合地理位置約束條件，由底層網(wǎng)絡(luò)加上元節(jié)點(diǎn)和元鏈路構(gòu)成增廣的拓?fù)鋱D，進(jìn)而將虛擬網(wǎng)絡(luò)映射問題建模成混合整數(shù)規(guī)劃，并利用確定或隨機(jī)取整求解可行的節(jié)點(diǎn)映射方案。其鏈路映射算法與文獻(xiàn)[9]相同。

廖建新等[11]提出將多個(gè)拓?fù)涮卣髦导蓱?yīng)用于設(shè)計(jì)拓?fù)涓兄挠成渌惴?。文中提出?個(gè)反映不同網(wǎng)絡(luò)拓?fù)鋵傩缘耐負(fù)涮卣髦担M(jìn)而利用其各自特點(diǎn)和優(yōu)勢(shì)設(shè)計(jì)了基于多拓?fù)涮卣髦档耐負(fù)涓兄惴?。算法核心的?jié)點(diǎn)排序策略也可用于改進(jìn)其他映射算法。拓?fù)涮卣髦颠€被用于拓?fù)浞纸?，以解開大尺寸虛擬網(wǎng)絡(luò)的層次結(jié)構(gòu)，優(yōu)化映射過程。

2.2 分布式虛擬網(wǎng)絡(luò)映射算法

相比于依賴單一中心控制實(shí)體的集中式算法，分布式算法則依靠分布廣泛且數(shù)量眾多的底層節(jié)點(diǎn)。虛擬網(wǎng)絡(luò)映射的整個(gè)決策由各底層節(jié)點(diǎn)共同實(shí)現(xiàn)完成，于是負(fù)載得以分散，可擴(kuò)展性得以增強(qiáng)，整個(gè)映射過程和網(wǎng)絡(luò)運(yùn)行不會(huì)因?yàn)閱吸c(diǎn)故障而完全失效。然而，分布式的設(shè)計(jì)思路也一把雙刃劍，與更好可擴(kuò)展性、魯棒性相伴的是節(jié)點(diǎn)間更大的同步開銷。底層網(wǎng)絡(luò)的全局信息，如各個(gè)節(jié)點(diǎn)和鏈路的狀態(tài)，實(shí)時(shí)資源占用情況等等，都需要有完善的消息傳遞機(jī)制在所有底層節(jié)點(diǎn)間隨時(shí)進(jìn)行更新和同步，以在各底層節(jié)點(diǎn)維護(hù)最新的統(tǒng)一的全局信息。因?yàn)橹挥忻總€(gè)底層節(jié)點(diǎn)對(duì)全局信息了解得越清楚越及時(shí)，才越可能做出當(dāng)前真實(shí)網(wǎng)絡(luò)條件下的最佳映射決策，并且避免可能出現(xiàn)的沖突和不一致。

Houidi等[12]提出使用多代理系統(tǒng)設(shè)計(jì)分布式算法。實(shí)現(xiàn)節(jié)點(diǎn)間協(xié)商與同步的消息傳遞采用了洪泛機(jī)制，即每個(gè)底層節(jié)點(diǎn)映射虛擬節(jié)點(diǎn)和鏈路后，都向所有其他節(jié)點(diǎn)發(fā)送消息，告知映射結(jié)果。因此消息的數(shù)量相對(duì)底層網(wǎng)絡(luò)的尺寸成指數(shù)增長(zhǎng)，算法受到過多同步消息和較大映射開銷的困擾，在擴(kuò)展性和映射性能方面還無(wú)法與集中式算法相比。

卿蘇德等[13]提出了基于布隆過濾器的分布式映射算法。算法利用機(jī)器學(xué)習(xí)和推理技術(shù)，通過積累的歷史信息在沒有或缺乏底層網(wǎng)絡(luò)信息的情況下對(duì)節(jié)點(diǎn)的能力進(jìn)行評(píng)估，并依賴底層節(jié)點(diǎn)的自主映射完成整個(gè)虛擬網(wǎng)絡(luò)映射。同步消息中捎帶的布隆過濾器實(shí)現(xiàn)了有限范圍的信息同步，既有效避免了映射沖突，又規(guī)避了傳統(tǒng)洪泛算法的巨大通信開銷。

Chowdhury等[14-15]針對(duì)多個(gè)基礎(chǔ)設(shè)施提供商，提出了根據(jù)地域切分和映射的PolyViNE架構(gòu)，以協(xié)調(diào)解決基礎(chǔ)設(shè)施提供商與服務(wù)提供商間的利益沖突。服務(wù)提供商將虛擬網(wǎng)絡(luò)請(qǐng)求發(fā)給多個(gè)基礎(chǔ)設(shè)施提供商，由其各自提出涉及自己和其他基礎(chǔ)設(shè)施提供商網(wǎng)絡(luò)的跨域映射方案和報(bào)價(jià)，最終由服務(wù)提供商擇優(yōu)確定映射方案。另外基礎(chǔ)設(shè)施提供商之間也存在競(jìng)爭(zhēng)，爭(zhēng)奪高利潤(rùn)的映射任務(wù)并盡力將難以牟利的部分留給其他基礎(chǔ)設(shè)施提供商。

3 協(xié)同虛擬網(wǎng)絡(luò)映射算法

集中式算法和分布式算法各自的優(yōu)劣勢(shì)啟發(fā)我們?cè)诒疚闹袊L試充分結(jié)合利用兩者的特點(diǎn)與優(yōu)勢(shì)，設(shè)計(jì)一個(gè)介于集中與分布控制之間的虛擬網(wǎng)絡(luò)映射算法，我們稱之為協(xié)同虛擬網(wǎng)絡(luò)映射（CVNE）。

集中式算法的優(yōu)勢(shì)源于中心控制實(shí)體擁有全局視野，因此我們保留全局唯一的中心控制實(shí)體，依然負(fù)責(zé)收集、評(píng)估和管理底層網(wǎng)絡(luò)中的所有資源信息，并具有全局視野和關(guān)鍵決策的控制權(quán)。分布式算法的優(yōu)勢(shì)在于映射的整個(gè)決策由眾多底層節(jié)點(diǎn)實(shí)現(xiàn)完成，分散負(fù)載，于是我們將具體細(xì)節(jié)的映射方案計(jì)算過程交給底層節(jié)點(diǎn)實(shí)現(xiàn)。中心控制實(shí)體與底層節(jié)點(diǎn)相互配合協(xié)作，共同完成虛擬網(wǎng)絡(luò)映射。

3.1 協(xié)同算法總體流程

當(dāng)一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求達(dá)到后，首先進(jìn)入中心控制實(shí)體維護(hù)的虛擬網(wǎng)絡(luò)請(qǐng)求隊(duì)列。中心控制實(shí)體采取自定義的排隊(duì)機(jī)制依次進(jìn)行虛擬網(wǎng)絡(luò)映射。

對(duì)于當(dāng)前進(jìn)行映射的虛擬網(wǎng)絡(luò)請(qǐng)求，如果其虛擬節(jié)點(diǎn)數(shù)量較少、拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單且無(wú)需分區(qū)域映射，則中心控制實(shí)體首先采取特定算法選取一個(gè)或多個(gè)底層節(jié)點(diǎn)作為“中心節(jié)點(diǎn)”。選取中心節(jié)點(diǎn)的具體數(shù)量由整個(gè)系統(tǒng)（包括底層網(wǎng)絡(luò)和中心控制實(shí)體）的負(fù)載情況決定：系統(tǒng)負(fù)載較輕時(shí)可以選擇合理數(shù)量的多個(gè)中心節(jié)點(diǎn)，而負(fù)載較重時(shí)則將只選取唯一的中心節(jié)點(diǎn)。中心節(jié)點(diǎn)的選擇算法可借鑒文獻(xiàn)[11]中的拓?fù)涓兄墓?jié)點(diǎn)排序算法，即利用基于多拓?fù)涮卣髦档墓?jié)點(diǎn)排序策略對(duì)底層節(jié)點(diǎn)排序，然后選取初步滿足映射要求的候選底層節(jié)點(diǎn)中排名較高且自身資源占用率較低的作為中心節(jié)點(diǎn)。中心控制實(shí)體將當(dāng)前虛擬網(wǎng)絡(luò)請(qǐng)求和全局網(wǎng)絡(luò)信息一同發(fā)給各中心節(jié)點(diǎn)，由其為該虛擬網(wǎng)絡(luò)計(jì)算映射方案。中心節(jié)點(diǎn)獲得全局網(wǎng)絡(luò)信息后，進(jìn)一步從與相鄰節(jié)點(diǎn)（一定跳數(shù)范圍內(nèi)）的通信中獲取自己所處局部網(wǎng)絡(luò)的實(shí)時(shí)信息，更新全局網(wǎng)絡(luò)信息，以解決中心控制實(shí)體獲取底層網(wǎng)絡(luò)信息的延遲問題。節(jié)點(diǎn)和鏈路映射算法可根據(jù)中心節(jié)點(diǎn)所屬網(wǎng)絡(luò)的具體設(shè)置，靈活選用定制的算法。每個(gè)中心節(jié)點(diǎn)計(jì)算出映射方案后發(fā)回給中心控制實(shí)體，由中心控制實(shí)體比較選定最優(yōu)方案（默認(rèn)總開銷最少為最優(yōu)）進(jìn)行資源分配，完成映射。如果中心節(jié)點(diǎn)計(jì)算映射方案失敗，則將失敗情況告知中心控制實(shí)體，由中心控制實(shí)體進(jìn)行相應(yīng)調(diào)整：重新選擇其他中心節(jié)點(diǎn)計(jì)算映射方案，或在多次映射失敗后推遲或放棄該虛擬網(wǎng)絡(luò)請(qǐng)求。我們將上述過程稱為“簡(jiǎn)單網(wǎng)絡(luò)映射”。

如果當(dāng)前虛擬網(wǎng)絡(luò)請(qǐng)求的虛擬節(jié)點(diǎn)數(shù)量較多、拓?fù)浣Y(jié)構(gòu)復(fù)雜或者有地域限制需要分區(qū)域映射，則中心控制實(shí)體需要在中心節(jié)點(diǎn)選擇之前首先對(duì)虛擬網(wǎng)絡(luò)拓?fù)溥M(jìn)行預(yù)處理：對(duì)于有地域限制或者跨多個(gè)運(yùn)營(yíng)商等情況的虛擬網(wǎng)絡(luò)請(qǐng)求，優(yōu)先根據(jù)具體限制情況將其自然分解為多個(gè)虛擬子網(wǎng)；對(duì)于虛擬節(jié)點(diǎn)數(shù)量較多或拓?fù)浣Y(jié)構(gòu)復(fù)雜的虛擬網(wǎng)絡(luò)我們采用KS核分解算法[11]將其分解為一個(gè)核心網(wǎng)絡(luò)和多個(gè)邊緣網(wǎng)絡(luò)。自然分解的多個(gè)虛擬子網(wǎng)將被相應(yīng)分配給各底層網(wǎng)絡(luò)自治域中處于相鄰邊界的一個(gè)或多個(gè)中心節(jié)點(diǎn)，分別進(jìn)行多個(gè)簡(jiǎn)單網(wǎng)絡(luò)映射，然后各中心節(jié)點(diǎn)將各自的虛擬子網(wǎng)映射方案發(fā)回給中心控制實(shí)體，由其選擇其中的全局最優(yōu)（默認(rèn)總開銷最少為最優(yōu)）的方案組合進(jìn)行映射，或進(jìn)行相應(yīng)調(diào)整。拓?fù)浞纸夂蟮暮诵木W(wǎng)絡(luò)則首先進(jìn)行簡(jiǎn)單網(wǎng)絡(luò)映射。由于每個(gè)邊緣網(wǎng)絡(luò)通過KS核分解算法生成，核心網(wǎng)絡(luò)中與之相連的銜接節(jié)點(diǎn)已確定映射方案，因此我們?cè)谶吘壘W(wǎng)絡(luò)映射中將已映射的銜接節(jié)點(diǎn)作為下階段的中心節(jié)點(diǎn)，其從上階段核心網(wǎng)絡(luò)映射的中心節(jié)點(diǎn)處得到全局網(wǎng)絡(luò)信息和邊緣網(wǎng)絡(luò)信息后進(jìn)行簡(jiǎn)單網(wǎng)絡(luò)映射。如果邊緣網(wǎng)絡(luò)映射的中心節(jié)點(diǎn)計(jì)算映射方案失敗，則將失敗原因告知核心網(wǎng)絡(luò)的中心節(jié)點(diǎn)，由其進(jìn)行相應(yīng)調(diào)整，重新映射對(duì)應(yīng)的銜接節(jié)點(diǎn)，或在多次映射失敗后推遲或放棄該虛擬網(wǎng)絡(luò)請(qǐng)求。

協(xié)同虛擬網(wǎng)絡(luò)映射算法相比傳統(tǒng)集中式算法，由于將大量具體的映射任務(wù)交由底層中心節(jié)點(diǎn)完成，中心控制實(shí)體在映射中只負(fù)責(zé)虛擬網(wǎng)絡(luò)請(qǐng)求的預(yù)處理、分配、重分配、方案確定和資源分配等，因此負(fù)載明顯減輕。由中心控制實(shí)體在頭尾階段進(jìn)行全局最優(yōu)的決策，由分布的中心節(jié)點(diǎn)進(jìn)行局部最優(yōu)的方案計(jì)算，保證了最終的映射方案是接近最優(yōu)解的，也不會(huì)出現(xiàn)映射沖突等情況。動(dòng)態(tài)網(wǎng)絡(luò)的延遲問題由于中心節(jié)點(diǎn)從中心控制實(shí)體處獲取的全局網(wǎng)絡(luò)信息與在所處局部網(wǎng)絡(luò)中的實(shí)時(shí)信息更新相結(jié)合而得以有效解決；面對(duì)大尺度網(wǎng)絡(luò)的擴(kuò)展性問題和系統(tǒng)單點(diǎn)故障問題也將得到極大緩解。

相比傳統(tǒng)分布式算法，協(xié)同虛擬網(wǎng)絡(luò)映射算法中雖然每個(gè)底層節(jié)點(diǎn)都具備成為中心節(jié)點(diǎn)的能力，但是每一次映射只有少數(shù)更有能力的優(yōu)質(zhì)節(jié)點(diǎn)被選中，映射任務(wù)限定在有限的底層網(wǎng)絡(luò)子集中。映射沖突由于中心控制實(shí)體的存在得以有效避免。這些都使得節(jié)點(diǎn)間的同步開銷大大降低，無(wú)需采取洪泛等產(chǎn)生大量同步消息的消息傳遞機(jī)制。多個(gè)中心節(jié)點(diǎn)同時(shí)計(jì)算部分或整體映射方案也實(shí)現(xiàn)了虛擬網(wǎng)絡(luò)映射的并行計(jì)算，可以明顯降低映射耗時(shí)。

3.2 協(xié)同算法映射實(shí)例

圖1顯示了服務(wù)提供商的兩個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求通過協(xié)同算法映射到基礎(chǔ)設(shè)施提供商的底層網(wǎng)絡(luò)的實(shí)例。圖中實(shí)線代表鏈路連接，其粗細(xì)反映帶寬大??；虛線代表映射成功的虛擬鏈路；底層網(wǎng)絡(luò)節(jié)點(diǎn)用大寫字母表示，虛擬網(wǎng)絡(luò)節(jié)點(diǎn)用小寫字母表示，在映射中被指定為中心節(jié)點(diǎn)的底層網(wǎng)絡(luò)節(jié)點(diǎn)用綠色標(biāo)明。虛擬網(wǎng)絡(luò)請(qǐng)求1和2先后到達(dá)，進(jìn)入虛擬網(wǎng)絡(luò)請(qǐng)求隊(duì)列中，但由于虛擬網(wǎng)絡(luò)請(qǐng)求2預(yù)期收益較高，因此將優(yōu)先映射。虛擬網(wǎng)絡(luò)請(qǐng)求2節(jié)點(diǎn)較多，于是通過KS核分解算法被分解為紅色的1個(gè)核心網(wǎng)絡(luò)和藍(lán)色的3個(gè)邊緣網(wǎng)絡(luò)。其核心網(wǎng)絡(luò)被中心控制實(shí)體分配給底層網(wǎng)絡(luò)的中心節(jié)點(diǎn)A計(jì)算映射方案。3個(gè)邊緣網(wǎng)絡(luò)在核心網(wǎng)絡(luò)映射方案確定后被分別交給下階段的中心節(jié)點(diǎn)B、C、F，同時(shí)計(jì)算各自邊緣網(wǎng)絡(luò)的映射方案。最后的總體映射方案由中心控制實(shí)體確定，并進(jìn)行資源分配以完成映射。虛擬網(wǎng)絡(luò)請(qǐng)求1由于節(jié)點(diǎn)數(shù)量少，拓?fù)浜?jiǎn)單，也沒有地域限制，因此無(wú)需分解。其被中心控制實(shí)體交給底層節(jié)點(diǎn)I計(jì)算映射方案，最后得以映射。

4 仿真結(jié)果

初步的仿真實(shí)驗(yàn)參照文獻(xiàn)[9]、文獻(xiàn)[11]和文獻(xiàn)[13]的網(wǎng)絡(luò)環(huán)境和參數(shù)設(shè)置進(jìn)行，將集中式算法的代表——文獻(xiàn)[9]的算法（以BL表示），以及分布式算法的代表——文獻(xiàn)[13]的基于布隆過濾器的分布式算法（以P2PVNE表示）作為對(duì)比算法，定量測(cè)試我們的協(xié)同虛擬網(wǎng)絡(luò)算法（以CVNE表示）在長(zhǎng)期平均收益、接受率和收益開銷比3項(xiàng)性能指標(biāo)上的表現(xiàn)。協(xié)同算法中虛擬網(wǎng)絡(luò)請(qǐng)求隊(duì)列采用了傳統(tǒng)收益優(yōu)先的排隊(duì)機(jī)制，即按照預(yù)期收益由多到少的順序先后進(jìn)行映射；各中心節(jié)點(diǎn)處的映射算法采用了文獻(xiàn)[11]中的NDC算法。

協(xié)同算法與集中式、分布式代表算法的長(zhǎng)期平均收益比較如圖2所示。協(xié)同算法與集中式、分布式代表算法的長(zhǎng)期接受率比較如圖3所示。協(xié)同算法與集中式、分布式代表算法的長(zhǎng)期收益開銷比比較如圖4所示。從圖2、圖3和圖4中我們可以看到，文獻(xiàn)[13]中的分布式算法在長(zhǎng)期平均收益、接受率和收益開銷比3項(xiàng)性能指標(biāo)上相比文獻(xiàn)[9]中的集中式算法都有了明顯提升，而我們的協(xié)同算法在長(zhǎng)期接受率和收益開銷比兩項(xiàng)性能指標(biāo)相比前兩者又有了更大的提升，在長(zhǎng)期平均收益上相比分布式算法也有一定的提升?？偟膩?lái)看，協(xié)同虛擬網(wǎng)絡(luò)映射算法由于將集中式算法和分布式算法的相對(duì)優(yōu)勢(shì)充分結(jié)合，有效彌補(bǔ)了二者的缺陷，從而達(dá)到了更好的映射性能。

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

虛擬網(wǎng)絡(luò)映射問題是網(wǎng)絡(luò)虛擬化中的關(guān)鍵挑戰(zhàn)，傳統(tǒng)集中式和分布式的映射算法各有利弊。我們?cè)诒疚闹谐浞纸Y(jié)合利用兩大類算法的相對(duì)優(yōu)勢(shì)，設(shè)計(jì)了兼具集中與分布特點(diǎn)的協(xié)同虛擬網(wǎng)絡(luò)映射算法。算法相比傳統(tǒng)的集中式和分布式算法的綜合優(yōu)勢(shì)明顯，初步的仿真試驗(yàn)結(jié)果也證明了算法的可行性和有效性。

參考文獻(xiàn)

[1] CHOWDHURY N， BOUTABA R. A survey of network virtualization [J]. Computer Networks， 2010，54（5）： 862-876.

[2] 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.

[3] BAVIER A， FEAMSTER N， HUANG M， et al. In VINI veritas： Realistic and controlled network experimentation [J]. ACM SIGCOMM Computer Communication Review， 2006，36（4）： 3-14.

[4] ANDERSON T， PETERSON L， SHENKER S， et al. Overcoming the Internet impasse through virtualization [J]. IEEE Computer Magazine， 2005，38（4）： 34-41.

[5] TURNER J， TAYLOR D. Diversifying the Internet [C]//Proceedings of the Global Telecommunications Conference， 2005. St. Louis， MO， 2005，2： 755-760. doi：10.1109/GLOCOM.2005.1577741.

[6] ANDERSEN D G. Theoretical approaches to node assignment [R]. Unpublished Manuscript， 2002.

[7] YU H， QIAO C， ANAND V， et al. Survivable Virtual Infrastructure Mapping in a Federated Computing and Networking System under Single Regional failures [C]//Proceedings of the IEEE GLOBECOM， 2010：1-6.

[8] YU H， ANAND V， QIAO C， et al. Cost Efficient Design of Survivable Virtual Infrastructure to Recover from Facility Node Failures [C]//Proceedings of the IEEE ICC， 2011：1-6.

[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] CHOWDHURY N， RAHMAN M， BOUTABA R. Virtual network embedding with coordinated node and link mapping [C]//Proceedings of the IEEE INFOCOM， 2009： 783-791.

[11] LIAO J， FENG M， LI T， et al. Topology-aware Virtual Network Embedding Using Multiple Characteristics [J]. KSII Transactions on Internet and Information Systems， 2014，8（1）： 145-164.

[12] HOUIDI I， LOUATI W， ZEGHLACHE D. A distributed virtual network mapping algorithm [C]//Proceedings of the IEEE ICC， 2008：5634-5640.

[13] 卿蘇德. 網(wǎng)絡(luò)虛擬化映射算法研究 [R]. 北京郵電大學(xué)博士學(xué)位論文. 2013.

[14] CHOWDHURY M， SAMUEL F， BOUTABA R. Polyvine： policy-based virtual network embedding across multiple domains [C]//Proceedings of the 2nd ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures， New York， USA， 2010：49-56.

[15] FENG M， ZHANG L， ZHU X， et al. Topology-aware virtual network embedding through the degree [C]//Proceedings of the IET National Doctoral Academic Forum on Information and Communications Technology， 2013：1-6.