夏子厚

(信陽職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計算機科學(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ā)機制。與傳統(tǒng)的分布式最短路徑路由相比，軟件定義網(wǎng)絡(luò)對通信采取一個單播路由的集中計算以提供網(wǎng)絡(luò)吞吐量[3]。

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

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

1 問題構(gòu)建

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

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

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

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

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

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

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

輸入：網(wǎng)絡(luò)的實時狀態(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é)點選擇階段*/

If v∈Rvthen

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

else

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

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

結(jié)束

3 性能評估

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

3.1 仿真設(shè)置

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

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

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

3.2 仿真結(jié)果

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