基于軟件定義網(wǎng)絡(luò)的可靠性虛擬網(wǎng)絡(luò)映射保障機(jī)制

趙季紅，吳豆豆，曲 樺，殷振宇

（1. 西安郵電大學(xué)通信與信息工程學(xué)院，西安710121； 2. 西安交通大學(xué)電子與信息工程學(xué)院，西安710049）

（*通信作者電子郵箱:630611797@qq.com）

0 引言

軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）［1］具有控制和轉(zhuǎn)發(fā)分離、網(wǎng)絡(luò)集中管控、直接可編程和靈活配置等特性，實(shí)現(xiàn)了網(wǎng)絡(luò)控制平面與轉(zhuǎn)發(fā)平面的分離。根據(jù)其天然優(yōu)勢(shì)為網(wǎng)絡(luò)虛擬化技術(shù)［2］提供了新的架構(gòu)方案。兩者的結(jié)合，可以更方便地為網(wǎng)絡(luò)租戶提供定制化和私有化的網(wǎng)絡(luò)服務(wù)，通過虛擬網(wǎng)絡(luò)映射（Virtual Network Embedding，VNE)［3］方法，可以完成從用戶需求到底層資源切片的映射。高效、可靠的虛擬網(wǎng)絡(luò)映射算法，可以減少租戶和基礎(chǔ)設(shè)施提供商（Infrastructure Provider，InP）的故障損失。當(dāng)?shù)讓泳W(wǎng)絡(luò)元素失效時(shí)，保證網(wǎng)絡(luò)切片上運(yùn)行業(yè)務(wù)的可靠性也是非常有必要的。

可靠性虛擬網(wǎng)絡(luò)映射，也稱生存性虛擬網(wǎng)絡(luò)映射（Survivable Virtual Network Embedding，SVNE）算法［4］，主要研究物理網(wǎng)絡(luò)元素失效時(shí)，盡可能保障虛擬網(wǎng)絡(luò)的業(yè)務(wù)不受影響，屬于NP-hard問題［5］。

對(duì)于SVNE 問題的解決方案，主要可以分為先驗(yàn)式保護(hù)和后驗(yàn)式恢復(fù)兩種。文獻(xiàn)［6］通過合理映射其他虛擬鏈路，降低節(jié)點(diǎn)故障的影響，提出了一種基于網(wǎng)絡(luò)子圖的SVNE 算法。屬于后驗(yàn)式恢復(fù)方式，對(duì)于資源需求很大的虛擬網(wǎng)絡(luò)（Virtual Network，VN）節(jié)點(diǎn)或者物理網(wǎng)絡(luò)（Substrate Network，SN）負(fù)載較大的情況，故障恢復(fù)率較低。文獻(xiàn)［7］提出了一種基于位置約束的節(jié)點(diǎn)備份SVNE 算法，為每個(gè)虛擬節(jié)點(diǎn)預(yù)留地理位置接近的備份節(jié)點(diǎn)，該算法可以保證很高的節(jié)點(diǎn)故障恢復(fù)率，但是對(duì)于資源消耗較大，冗余過多。文獻(xiàn)［8］通過對(duì)虛擬鏈路實(shí)現(xiàn)虛擬網(wǎng)絡(luò)級(jí)別的備份，提出了一種聯(lián)合備用資源分配和映射的算法。該算法實(shí)現(xiàn)閑置資源的最大化利用，提高了鏈路的可靠性，但在虛擬請(qǐng)求數(shù)量巨大情況下，公共備份路徑的可靠性是更需要考慮的問題。另外該算法沒有考慮節(jié)點(diǎn)的故障問題，鏈路選擇算法時(shí)間復(fù)雜度過高，不適用于大規(guī)模底層網(wǎng)絡(luò)的情況。文獻(xiàn)［9］提出了一種基于資源衡量的SVNE 算法，通過聯(lián)合先驗(yàn)式和后驗(yàn)式的方式，盡可能地為虛擬網(wǎng)絡(luò)提供備份資源，在物理網(wǎng)絡(luò)不滿足資源需求時(shí)，利用后驗(yàn)式恢復(fù)保障可靠性，該算法對(duì)資源需求較小虛擬節(jié)點(diǎn)和鏈路預(yù)留了備份資源，而實(shí)際中，這些資源需求較少的網(wǎng)絡(luò)元素發(fā)生故障時(shí)，通過后驗(yàn)式進(jìn)行故障恢復(fù)是很容易的，因此這種備份方式會(huì)預(yù)留很多無效冗余。

本文提出了基于SDN 的可靠性虛擬網(wǎng)絡(luò)映射（Deterministic Survivable Virtual Network Embedding，D-SViNE）保障機(jī)制，采用聯(lián)合先驗(yàn)式保護(hù)和后驗(yàn)式恢復(fù)的方式。在先驗(yàn)式保護(hù)階段，對(duì)虛擬節(jié)點(diǎn)考慮可行域內(nèi)節(jié)點(diǎn)資源感知和預(yù)測(cè)，對(duì)域內(nèi)相對(duì)剩余資源減少的虛擬節(jié)點(diǎn)預(yù)留備份虛擬節(jié)點(diǎn)和相關(guān)虛擬鏈路，將擴(kuò)展VN 通過可靠性虛擬網(wǎng)絡(luò)映射（Deterministic Virtual Network Embedding，D-ViNE）算法［10］進(jìn)行映射。對(duì)已經(jīng)進(jìn)行先驗(yàn)保護(hù)的虛擬節(jié)點(diǎn)和相關(guān)鏈路，在發(fā)生故障時(shí)，采用遷移工作節(jié)點(diǎn)和相關(guān)鏈路的方式完成故障恢復(fù)；對(duì)于沒有預(yù)留備份資源的網(wǎng)絡(luò)元素發(fā)生故障，采用后驗(yàn)式故障恢復(fù)算法，當(dāng)節(jié)點(diǎn)故障時(shí)，采用貪婪算法重映射故障節(jié)點(diǎn)；當(dāng)鏈路故障時(shí)，利用最短路徑算法重路由以迅速找到可恢復(fù)路徑。實(shí)驗(yàn)表明，該保護(hù)機(jī)制提高了節(jié)點(diǎn)故障恢復(fù)率以及虛擬請(qǐng)求接受率。

1 問題描述和定義

為保證虛擬網(wǎng)絡(luò)映射（VNE）的可靠性，采用聯(lián)合先驗(yàn)式保護(hù)和后驗(yàn)式恢復(fù)的方式。其中，先驗(yàn)式保護(hù)機(jī)制部署在虛擬請(qǐng)求接受之前，屬于虛擬網(wǎng)絡(luò)級(jí)別的保護(hù)，即根據(jù)物理節(jié)點(diǎn)和鏈路的剩余資源變化趨勢(shì)，設(shè)定是否預(yù)留備份。后驗(yàn)式故障恢復(fù)機(jī)制是部署在虛擬請(qǐng)求映射成功之后，當(dāng)發(fā)生故障時(shí)根據(jù)剩余資源進(jìn)行故障的恢復(fù)，對(duì)節(jié)點(diǎn)和鏈路故障分別采用節(jié)點(diǎn)遷移和鏈路重路由的方式。

1.1 先驗(yàn)式保護(hù)

在SDN 網(wǎng)絡(luò)環(huán)境中，對(duì)于任意虛擬網(wǎng)絡(luò)GV=(NV，LV，)和物理網(wǎng)絡(luò)GS=(NS，LS，)，在VNE 時(shí)需要構(gòu)建工作拓?fù)浜蛡浞萃負(fù)?。其中工作拓?fù)浒üぷ鞴?jié)點(diǎn)M()∈NS和工作路徑Ω()∈PS；備份拓?fù)浒▊浞莨?jié)點(diǎn)bp()∈NS和備份路徑bp()∈PS。對(duì)任意虛擬節(jié)點(diǎn)∈NV，設(shè)置備份標(biāo)記BF()定義如下:

其中:PS表示物理節(jié)點(diǎn)之間的物理路徑。同樣地，對(duì)于虛擬鏈路∈LV，設(shè)置備份標(biāo)記BF（）為:

虛擬鏈路到物理路徑的映射關(guān)系表示為:

其中:M表示VNE 的鏈路映射，lv（ni，nj）表示節(jié)點(diǎn)ni和nj之間的虛擬鏈路，VN 節(jié)點(diǎn)ni和nj分別映射到SN 節(jié)點(diǎn)ns和nt，Ps（ns，nt）表示SN 節(jié)點(diǎn)之間的物理路徑；BP表示備份鏈路的映射，bps（ns，nt）表示ns和nt之間的備份路徑。

1.2 后驗(yàn)式故障恢復(fù)

后驗(yàn)式故障恢復(fù)是在故障發(fā)生時(shí)，分離受故障影響的虛擬網(wǎng)絡(luò)元素，然后對(duì)每個(gè)網(wǎng)絡(luò)元素逐個(gè)進(jìn)行虛擬級(jí)別的故障恢復(fù)。對(duì)于單物理節(jié)點(diǎn)故障情況，對(duì)同一個(gè)虛擬請(qǐng)求，單個(gè)物理節(jié)點(diǎn)故障最多會(huì)導(dǎo)致單個(gè)虛擬節(jié)點(diǎn)失效，但是，可能同時(shí)會(huì)導(dǎo)致多條虛擬鏈路的失效，因此要分別考慮受影響虛擬網(wǎng)絡(luò)的多個(gè)網(wǎng)絡(luò)元素。

對(duì)于單個(gè)鏈路發(fā)生故障，該物理鏈路上可能承載多個(gè)虛擬網(wǎng)絡(luò)的多條虛擬鏈路，也可能承載同一虛擬網(wǎng)絡(luò)的多條虛擬鏈路，因此需要分離該物理鏈路上承載的每條虛擬鏈路。故障分離如圖1所示。

圖1 故障分離示意圖Fig. 1 Schematic diagram of fault separation

4 仿真與分析

本文中由GT-ITM［12］生成設(shè)定的網(wǎng)絡(luò)拓?fù)?，通過NS2［13］中的Tk 工具生成可視化的網(wǎng)絡(luò)拓?fù)鋱D，結(jié)合Java 作為仿真工具，對(duì)該保障機(jī)制以及幾種可靠性保證方法進(jìn)行仿真，通過虛擬請(qǐng)求接受率、算法時(shí)間、虛擬節(jié)點(diǎn)級(jí)別的故障恢復(fù)率以及物理級(jí)別節(jié)點(diǎn)故障恢復(fù)率驗(yàn)證該算法的性能。

4.1 仿真環(huán)境與參數(shù)設(shè)計(jì)

本次實(shí)驗(yàn)通過GT-ITM 模擬物理節(jié)點(diǎn)故障發(fā)生的情形，并生成了1 000個(gè)虛擬網(wǎng)絡(luò)和1個(gè)物理網(wǎng)絡(luò)。實(shí)驗(yàn)參數(shù)［14-17］如表1 所示（U 表示均勻分布；P 表示泊松分布；E 表示指數(shù)分布）。其中，故障的發(fā)生服從泊松分布，平均每次記錄時(shí)間單元內(nèi)發(fā)生4 次物理節(jié)點(diǎn)的故障，實(shí)驗(yàn)總時(shí)間為20 000 個(gè)時(shí)間單元，每1 000 個(gè)時(shí)間單元記錄一次節(jié)點(diǎn)的故障恢復(fù)情況和虛擬網(wǎng)絡(luò)接受情況，實(shí)驗(yàn)共隨機(jī)生成80個(gè)物理節(jié)點(diǎn)故障。

表1 實(shí)驗(yàn)參數(shù)Tab. 1 Test parameters

4.2 對(duì)比方案

在可靠性保障階段，采用的對(duì)比方案是兩種關(guān)SDN 可靠性映射保障的方法:一種方法為基于位置受限的生存性虛擬網(wǎng)絡(luò)映射（Location Constrained Survivable Virtual Network Embedding，LC-SVNE）算法［7］，其屬于全備份可靠性保障；另一種方法為基于SDN 的生存性虛擬網(wǎng)絡(luò)映射（SDNSurvivable Virtual Network Embedding，SDN-SVNE）算法［9］，其屬于盡可能的備份方式。三種算法的對(duì)比如表2所示。

表2 SVNE對(duì)比算法Tab. 2 SVNE contrast algorithms

4.3 性能分析

1）虛擬請(qǐng)求接受率。

圖3 表示不同算法的虛擬請(qǐng)求接受率。從圖中可以得出，三種算法初始階段接受率都很高，隨著虛擬網(wǎng)絡(luò)的到達(dá)和離開接受率會(huì)趨于穩(wěn)定。D-SViNE 算法相比較高的原因在于該算法屬于部分備份方式，并且盡可能地降低了備份資源的消耗，因此在后期仍有著較高的虛擬網(wǎng)絡(luò)請(qǐng)求接受率。而LC-SVNE 算法是對(duì)所有的虛擬節(jié)點(diǎn)都進(jìn)行備份，備份節(jié)點(diǎn)會(huì)占用很多底層資源，導(dǎo)致虛擬網(wǎng)絡(luò)接受率最低。SDN-SVNE算法初始接近全備份的方式，會(huì)使得映射備份消耗資源過多，底層網(wǎng)絡(luò)資源很快會(huì)耗盡，后期無法對(duì)資源消耗較大的元素進(jìn)行映射，導(dǎo)致虛擬請(qǐng)求的拒絕，所以該算法虛擬請(qǐng)求接受率會(huì)很快降低。

圖3 虛擬請(qǐng)求接受率Fig. 3 Virtual request acceptance rate

2）算法時(shí)間性能。

圖4 表示不同算法的實(shí)驗(yàn)時(shí)間。其中，實(shí)驗(yàn)一對(duì)前500個(gè)虛擬網(wǎng)絡(luò)進(jìn)行先驗(yàn)保護(hù)；實(shí)驗(yàn)二為映射1 000個(gè)擴(kuò)展虛擬網(wǎng)絡(luò)。從圖中可以得出，在虛擬網(wǎng)絡(luò)較少時(shí)，算法的映射時(shí)間很接近。隨著物理網(wǎng)絡(luò)負(fù)載的增大，D-SViNE 算法運(yùn)行時(shí)間增長(zhǎng)幅度介于SDN-SVNE 和LC-SVNE 算法之間。其中，相比于LC-SVNE 算法，SDN-SVNE 算法的運(yùn)行時(shí)間減少了20%。其原因在于LC-SVNE 算法基于鏈路的可分裂方式，增加了鏈路映射的運(yùn)行時(shí)間。在實(shí)驗(yàn)一中，D-SViNE 算法在時(shí)間效率上優(yōu)于SDN-SVNE 算法，因?yàn)镈-SViNE 算法在映射時(shí)，計(jì)算節(jié)點(diǎn)SPR 值排序結(jié)果，相比于SDN-SVNE 的節(jié)點(diǎn)隨機(jī)映射會(huì)花費(fèi)更少的時(shí)間，此外，由于初始時(shí)底層網(wǎng)絡(luò)剩余資源充足，SDNSVNE設(shè)置的備份資源更多，備份映射會(huì)消耗更多的時(shí)間。而實(shí)驗(yàn)二中，兩者時(shí)間消耗接近，因?yàn)镾DN-SVNE 底層負(fù)載較大時(shí)，會(huì)選擇部分備份或不備份的方式，因此算法運(yùn)行時(shí)間相對(duì)D-SViNE較小。

圖4 不同算法運(yùn)行時(shí)間對(duì)比Fig. 4 Running time of different algorithms

3）虛擬節(jié)點(diǎn)級(jí)別的故障恢復(fù)率。

圖5 表示虛擬級(jí)別故障恢復(fù)率，當(dāng)故障到來時(shí)先進(jìn)行故障的恢復(fù)。從圖中可以看出，初始階段虛擬級(jí)別故障恢復(fù)率都為1，主要因?yàn)榇藭r(shí)隨機(jī)節(jié)點(diǎn)故障可能沒有影響虛擬網(wǎng)絡(luò)，而且當(dāng)?shù)讓淤Y源充足，三種算法初始都有節(jié)點(diǎn)的主動(dòng)備份，因此可以基本全部恢復(fù)。隨著時(shí)間推移，隨機(jī)節(jié)點(diǎn)故障越來越多，虛擬節(jié)點(diǎn)的故障恢復(fù)率趨于穩(wěn)定的值。

LC-SVNE 算法節(jié)點(diǎn)的故障恢復(fù)率最高，穩(wěn)定狀態(tài)下可以達(dá)到80%。因?yàn)長(zhǎng)C-SVNE 采用全備份的方式，節(jié)點(diǎn)的故障只能通過預(yù)留的備份節(jié)點(diǎn)資源完成故障的恢復(fù)。鏈路采用可分裂的路徑映射方式，一旦備份路路徑的鏈路點(diǎn)發(fā)生故障，則可能同時(shí)影響工作路徑和備份路徑導(dǎo)致故障的恢復(fù)失敗。

D-SViNE 算法屬于感知型備份方式，對(duì)資源需求較小的虛擬網(wǎng)絡(luò)元素進(jìn)行了冗余備份，而實(shí)際中這部分網(wǎng)絡(luò)元素即使發(fā)生故障也很容易故障恢復(fù)，因此該算法無效備份較多，其故障恢復(fù)成功率在穩(wěn)定狀態(tài)下約為68.7%。

SDN-SVNE 算法的故障恢復(fù)率最低，主要因?yàn)樵撍惴奚锢碣Y源，以提高虛擬請(qǐng)求接受率。后期故障發(fā)生時(shí)，采用隨機(jī)映射方式，重映射故障虛擬節(jié)點(diǎn)；相關(guān)故障鏈路的重映射，采用最短路徑的方式，這種方式對(duì)資源需求較少的故障節(jié)點(diǎn)和鏈路效果較好，但對(duì)資源需求較大的情況，故障恢復(fù)率較低。

圖5 虛擬級(jí)別故障恢復(fù)率Fig. 5 Virtual level failure recovery rate

4）物理級(jí)別節(jié)點(diǎn)故障恢復(fù)率。

圖6表示物理級(jí)別節(jié)點(diǎn)故障恢復(fù)率。從圖中可以看出DSViNE 算法和SDN-SVNE 算法在物理級(jí)別節(jié)點(diǎn)故障恢復(fù)率方面明顯優(yōu)于LC-SVNE 算法，因?yàn)長(zhǎng)C-SVNE 沒有設(shè)置節(jié)點(diǎn)故障的后驗(yàn)故障恢復(fù)機(jī)制，同一個(gè)物理節(jié)點(diǎn)可以在不同的虛擬請(qǐng)求中，承載不同的虛擬網(wǎng)絡(luò)元素，發(fā)生故障時(shí)，僅靠預(yù)留的備份節(jié)點(diǎn)和相關(guān)鏈路，不足以恢復(fù)故障節(jié)點(diǎn)承載的所有虛擬網(wǎng)絡(luò)。相比于SDN-SVNE 算法，D-SViNE 算法的物理級(jí)別恢復(fù)率相較于SDN-SVNE 提高約10 個(gè)百分點(diǎn)，這是因?yàn)镾DNSVNE只對(duì)資源需求較少的虛擬網(wǎng)絡(luò)元素進(jìn)行先驗(yàn)保護(hù)，對(duì)資源需求較大的網(wǎng)絡(luò)元素只進(jìn)行故障后驗(yàn)恢復(fù)，而資源需求較大的網(wǎng)絡(luò)元素，在網(wǎng)絡(luò)負(fù)載很大時(shí)，很難恢復(fù)成功，因此SDNSVNE 的無效備份資源較多，物理級(jí)別故障恢復(fù)率較低。而D-SViNE 算法可以更好地感知底層網(wǎng)絡(luò)剩余資源的變化，針對(duì)部分關(guān)鍵節(jié)點(diǎn)預(yù)留備份資源，可以降低冗余并且減少無效的備份。

圖6 物理級(jí)別故障恢復(fù)率Fig. 6 Physical level failure recovery rate

5 結(jié)語(yǔ)

本文針對(duì)SDN 網(wǎng)絡(luò)底層資源發(fā)生故障的問題，提出了一種基于SDN 的可靠性VNE 保障機(jī)制。首先對(duì)虛擬網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)映射域內(nèi)剩余資源進(jìn)行感知，提出了先驗(yàn)式保護(hù)算法；然后通過D-ViNE算法完成對(duì)虛擬擴(kuò)展網(wǎng)絡(luò)的映射，并設(shè)計(jì)后驗(yàn)式恢復(fù)機(jī)制。故障恢復(fù)時(shí)，采用聯(lián)合先驗(yàn)式保護(hù)和后驗(yàn)式恢復(fù)的方式。仿真結(jié)果表明，該可靠性保障機(jī)制，在虛擬請(qǐng)求接受率、虛擬級(jí)別以及物理級(jí)別節(jié)點(diǎn)故障恢復(fù)率方面都優(yōu)于現(xiàn)有算法。此外，在隨機(jī)故障模型和區(qū)域性故障模型中，先驗(yàn)式備份的作用很小，所以設(shè)計(jì)更加合理的可靠性保障機(jī)制可作為后續(xù)的研究方向。