軟件定義網(wǎng)絡(luò)中的可靠多播路由研究

夏子厚

(信陽職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，河南 信陽 464000)

軟件定義網(wǎng)絡(luò)(SDN)是一個確保網(wǎng)絡(luò)資源的靈活管理，以支持大量數(shù)據(jù)傳輸?shù)男滦途W(wǎng)絡(luò)結(jié)構(gòu)[1]。軟件定義網(wǎng)絡(luò)中的OpenFlow[2]有兩個主要元素構(gòu)成：控制器和轉(zhuǎn)發(fā)機(jī)制。與傳統(tǒng)的分布式最短路徑路由相比，軟件定義網(wǎng)絡(luò)對通信采取一個單播路由的集中計(jì)算以提供網(wǎng)絡(luò)吞吐量[3]。

多播通信能夠?qū)崿F(xiàn)多目的節(jié)點(diǎn)的數(shù)據(jù)傳輸，但是，多播傳輸在最小網(wǎng)絡(luò)資源消耗方面，如果沒有可靠傳輸，網(wǎng)絡(luò)的傳輸效率將會受到很大的影響。為了支持多播中的可靠傳輸，基于源的可靠多播傳輸[4]首先被提出，以直接從源恢復(fù)丟失的包，但是它也面臨擴(kuò)展性問題，因?yàn)樵垂?jié)點(diǎn)需要向大量的目的節(jié)點(diǎn)提供丟失數(shù)據(jù)，這就使得源數(shù)據(jù)可能被淹沒[5]。因此，需要設(shè)計(jì)一個新的算法來同時實(shí)現(xiàn)一個多播樹的高效路由和多播傳輸恢復(fù)節(jié)點(diǎn)的選擇。

本文將基于軟件定義控制技術(shù)提出了一個新的可靠多播樹，叫做故障恢復(fù)斯坦納樹(RST)。在一組多播中給定源節(jié)點(diǎn)和目的節(jié)點(diǎn)和網(wǎng)絡(luò)中相應(yīng)的恢復(fù)節(jié)點(diǎn)以及一個非負(fù)整數(shù)r，故障恢復(fù)斯坦納樹旨在找到一個實(shí)現(xiàn)以下功能的樹：(1)連接源節(jié)點(diǎn)和目的節(jié)點(diǎn)；(2)至多跨越樹中r個作為本地丟包恢復(fù)的恢復(fù)節(jié)點(diǎn)。我們的目標(biāo)是將樹的資源消耗和總恢復(fù)資源消耗最小化，樹的資源消耗是樹中所有支撐數(shù)據(jù)傳輸?shù)馁Y源消耗總和[8]。

1 問題構(gòu)建

為了找到跨越源節(jié)點(diǎn)s和目的節(jié)點(diǎn)集合D的邊界集合，定義在故障恢復(fù)斯坦納樹(RST)中至多有r個恢復(fù)節(jié)點(diǎn)的集合為R?？紤]一個直接圖G(V,E),其中V和E分別表示節(jié)點(diǎn)和邊的集合。每條在集合E中的邊e(e∈E)被分配給一個資源消耗值c(e):E→R+，其中R+代表正實(shí)數(shù)的集合。

在故障恢復(fù)斯坦納樹中，通過測試不同的r，軟件定義控制技術(shù)能夠協(xié)調(diào)本地存儲的資源消耗和丟包恢復(fù)節(jié)點(diǎn)的資源消耗w(T)之間的關(guān)系。用一個比較大的值r，樹中更多的節(jié)點(diǎn)將參與到多播數(shù)據(jù)傳輸中的丟包恢復(fù)短暫存儲中，但是，丟包恢復(fù)節(jié)點(diǎn)的資源消耗將會顯著減少。同時，軟件定義控制技術(shù)能夠根據(jù)實(shí)時的網(wǎng)絡(luò)狀態(tài)調(diào)整權(quán)重α。如果網(wǎng)絡(luò)負(fù)載過重，設(shè)置一個較大的值α，反之亦然。另外，R在有效減少恢復(fù)節(jié)點(diǎn)的資源消耗上也將起著重要作用，R值和恢復(fù)節(jié)點(diǎn)的資源消耗成正比例關(guān)系?？梢钥闯觯收匣謴?fù)斯坦納樹問題同時考慮了樹的路由和恢復(fù)節(jié)點(diǎn)的選擇，可以認(rèn)為故障恢復(fù)斯坦納樹比傳統(tǒng)斯坦納樹更難。

2 算法設(shè)計(jì)及分析

本節(jié)中，我們將提出一個新的的k階近似算法，稱為故障恢復(fù)邊界減少(RAEARA)算法，RAEARA算法能夠找到多播樹的路由路徑并選擇合適的恢復(fù)節(jié)點(diǎn)，從而達(dá)到故障恢復(fù)斯坦納樹的資源消耗和恢復(fù)節(jié)點(diǎn)的資源消耗總和最小化。

RAEARA算法包含兩個階段：(1)故障恢復(fù)斯坦納樹路由階段，(2)恢復(fù)節(jié)點(diǎn)選擇階段。第一階段從根節(jié)點(diǎn)s的最短路徑樹開始，通過迭代生成最短路徑樹以減少樹的資源消耗。更具體一點(diǎn)，M表示從根節(jié)點(diǎn)s到樹中目的節(jié)點(diǎn)集合D中所有節(jié)點(diǎn)最短路徑的資源消耗。計(jì)算故障恢復(fù)斯坦納樹中所有節(jié)點(diǎn)到一個目的節(jié)點(diǎn)d的最短路徑，然后，選擇一個最大的重復(fù)路由路徑來減少構(gòu)建樹的資源消耗。另外，重復(fù)路由路徑能夠確保從根節(jié)點(diǎn)s到另一個目的節(jié)點(diǎn)的端對端鏈接。重復(fù)路由路徑需要包含至少一個相關(guān)的故障恢復(fù)節(jié)點(diǎn)，以實(shí)現(xiàn)本地丟包恢復(fù)。同時，為了避免生成一條路徑比原有的最短路徑樹深度更深，在一個新樹中，從根節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的端對端路徑資源消耗不能超過M。重復(fù)上述路由過程到樹的資源消耗不能被進(jìn)一步地減少。

恢復(fù)選擇階段是在故障恢復(fù)斯坦納樹中選擇恢復(fù)節(jié)點(diǎn)，從而達(dá)到恢復(fù)資源消耗的最小化。對于任何一個節(jié)點(diǎn)v∈VT，VT表示根在v的T的子樹。Rv為在Tv上的恢復(fù)子集，Tv關(guān)于Rv的恢復(fù)資源消耗表示為w(Tv,Rv)。RAEARA算法為兩種情況選擇最優(yōu)恢復(fù)節(jié)點(diǎn)集合：v在Rv中被選中。如果v沒有在Rv中被選中，RAEARA算法將隨后分配一些在T中的先輩節(jié)點(diǎn)作為恢復(fù)父節(jié)點(diǎn)。如果在Tv中的恢復(fù)節(jié)點(diǎn)滿足v?R，我們稱為情況Ⅰ，反之，如果v∈R，我們稱為情況Ⅱ。對于給定的Rv，如果Rv中沒有其它的恢復(fù)節(jié)點(diǎn)在Tv的v到u路徑上，則在集合DYRv中的節(jié)點(diǎn)u(u≠v)能夠被任意節(jié)點(diǎn)v控制。對于一個滿足x≤r的非負(fù)整數(shù)和一個滿足k≤|D|的正整數(shù)，σxmk(Tv)表示在情況I下所有在Tv上滿足|Rv|≤x的Rv(v不在Rv上)。因此，v完全的控制樹T上在集合D∪Rv中的節(jié)點(diǎn)k。相應(yīng)地，τx(Tv)表示所有情況Ⅱ下滿足|Rv|≤x的恢復(fù)集合Rv在樹Tv上的最小恢復(fù)資源消耗。

算法：故障恢復(fù)邊界減少算法(RAEARA)

輸入：網(wǎng)絡(luò)的實(shí)時狀態(tài)信息

輸出：最小資源消耗的最優(yōu)路徑

開始

/*步驟1：故障恢復(fù)斯坦納樹路由階段*/

發(fā)送傳輸數(shù)據(jù)流請求給軟件定義網(wǎng)絡(luò)控制器;

for i=1 to n

找到min w(T)并把具有min w(T)的鏈路作為最優(yōu)路徑；

/*步驟2: 恢復(fù)節(jié)點(diǎn)選擇階段*/

If v∈Rvthen

選擇當(dāng)前節(jié)點(diǎn)為故障恢復(fù)節(jié)點(diǎn)；

else

尋找當(dāng)前樹的子節(jié)點(diǎn)為故障恢復(fù)節(jié)點(diǎn)；

軟件定義控制器發(fā)送配置信號給相應(yīng)的網(wǎng)絡(luò)設(shè)備。

結(jié)束

3 性能評估

我們將在本節(jié)中對RAEARA算法進(jìn)行仿真分析，通過和其它路由策略進(jìn)行比較，證明RAEARA路由算法的效率。

3.1 仿真設(shè)置

在一個OpenFlow的以太網(wǎng)絡(luò)仿真器[6]中，設(shè)定有29個節(jié)點(diǎn)和33條鏈路的真實(shí)軟件定義網(wǎng)絡(luò)。然后，通過EstiNet網(wǎng)生成了一個有上千節(jié)點(diǎn)和鏈路的集成網(wǎng)絡(luò)，并和軟件定義網(wǎng)絡(luò)網(wǎng)絡(luò)相連接。源節(jié)點(diǎn)、目的節(jié)點(diǎn)和相關(guān)的恢復(fù)節(jié)點(diǎn)從每個網(wǎng)絡(luò)中隨機(jī)選擇。

把RAEARA算法與以下三個算法進(jìn)行比較：(1)最短路徑樹算法(SPT)(2)斯坦納樹算法(ST)[7](3)CPLEX[8]。在SPT算法和ST算法中，恢復(fù)節(jié)點(diǎn)的選擇是隨機(jī)的。并改變網(wǎng)絡(luò)規(guī)模|V|、目的節(jié)點(diǎn)數(shù)量k、和恢復(fù)節(jié)點(diǎn)個數(shù)r。

圖1樹路由資源消耗圖2節(jié)點(diǎn)恢復(fù)資源消耗

3.2 仿真結(jié)果

通過不同的目的節(jié)點(diǎn)個數(shù)k對RAEARA算法、SPT算法、ST算法和CPLEX算法進(jìn)行性能比較，其中恢復(fù)節(jié)點(diǎn)的個數(shù)r選為2，在這些小網(wǎng)絡(luò)中，每個節(jié)點(diǎn)都是一個候選恢復(fù)節(jié)點(diǎn)。圖1所示，RAEARA算法生成解的資源消耗非常接近于最優(yōu)解。SPT算法的資源消耗比其他算法更高。即使ST算法跟SPT算法相比有更小的構(gòu)建樹資源消耗，但是其目的節(jié)點(diǎn)和源節(jié)點(diǎn)之間的路徑更長，這是因?yàn)闉榱烁渌窂较嘟?，目的?jié)點(diǎn)和源節(jié)點(diǎn)之間的路徑需要與最短的路徑相隔離。圖2中，如果恢復(fù)節(jié)點(diǎn)選擇不恰當(dāng)，ST算法可能產(chǎn)生更高的恢復(fù)資源消耗。圖3證明RAEARA算法的重傳資源消耗依然最接近于最優(yōu)情況。如圖4所示，通過對每個目的節(jié)點(diǎn)的觀測，計(jì)算每個數(shù)據(jù)包在網(wǎng)絡(luò)中的平均延遲。因?yàn)榛謴?fù)節(jié)點(diǎn)更靠近目的節(jié)點(diǎn)，樹的深度(比如樹的最長路徑資源消耗)受M限制，因此，RAEARA算法比SPT算法和ST算法提供了更短的傳輸延遲，而且仿真延遲接近于接近于最優(yōu)解。

圖3平均重傳數(shù)據(jù)包(Mbps)圖4平均延遲

4 小結(jié)

單播數(shù)據(jù)傳輸是軟件定義網(wǎng)絡(luò)主要的通信方式。但是，多播數(shù)據(jù)傳輸可以顯著地減少網(wǎng)絡(luò)資源的消耗。由于許多應(yīng)用程序(例如YouTube)需要可靠的數(shù)據(jù)傳輸，因此，在軟件定義網(wǎng)絡(luò)中的可靠多播服務(wù)顯得尤為重要。本文中，我們首先提出了軟件定義網(wǎng)絡(luò)中的故障恢復(fù)斯坦納樹(RST)，它將構(gòu)建樹和數(shù)據(jù)恢復(fù)的資源消耗擬合最小化。另外，我們也提出了故障恢復(fù)邊界減少算法(RAEARA)。仿真結(jié)果證明，RAEARA算法能夠提供更低的的總資源消耗，并減少數(shù)據(jù)包的重傳概率，并有效降低數(shù)據(jù)傳輸延遲。