軟件定義網絡中的可靠多播路由研究

夏子厚

(信陽職業技術學院 數學與計算機科學學院，河南 信陽 464000)

軟件定義網絡(SDN)是一個確保網絡資源的靈活管理，以支持大量數據傳輸的新型網絡結構[1]。軟件定義網絡中的OpenFlow[2]有兩個主要元素構成：控制器和轉發機制。與傳統的分布式最短路徑路由相比，軟件定義網絡對通信采取一個單播路由的集中計算以提供網絡吞吐量[3]。

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

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

1 問題構建

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

在故障恢復斯坦納樹中，通過測試不同的r，軟件定義控制技術能夠協調本地存儲的資源消耗和丟包恢復節點的資源消耗w(T)之間的關系。用一個比較大的值r，樹中更多的節點將參與到多播數據傳輸中的丟包恢復短暫存儲中，但是，丟包恢復節點的資源消耗將會顯著減少。同時，軟件定義控制技術能夠根據實時的網絡狀態調整權重α。如果網絡負載過重，設置一個較大的值α，反之亦然。另外，R在有效減少恢復節點的資源消耗上也將起著重要作用，R值和恢復節點的資源消耗成正比例關系。可以看出，故障恢復斯坦納樹問題同時考慮了樹的路由和恢復節點的選擇，可以認為故障恢復斯坦納樹比傳統斯坦納樹更難。

2 算法設計及分析

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

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

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

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

輸入：網絡的實時狀態信息

輸出：最小資源消耗的最優路徑

開始

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

發送傳輸數據流請求給軟件定義網絡控制器;

for i=1 to n

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

/*步驟2: 恢復節點選擇階段*/

If v∈Rvthen

選擇當前節點為故障恢復節點；

else

尋找當前樹的子節點為故障恢復節點；

軟件定義控制器發送配置信號給相應的網絡設備。

結束

3 性能評估

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

3.1 仿真設置

在一個OpenFlow的以太網絡仿真器[6]中，設定有29個節點和33條鏈路的真實軟件定義網絡。然后，通過EstiNet網生成了一個有上千節點和鏈路的集成網絡，并和軟件定義網絡網絡相連接。源節點、目的節點和相關的恢復節點從每個網絡中隨機選擇。

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

圖1樹路由資源消耗圖2節點恢復資源消耗

3.2 仿真結果

通過不同的目的節點個數k對RAEARA算法、SPT算法、ST算法和CPLEX算法進行性能比較，其中恢復節點的個數r選為2，在這些小網絡中，每個節點都是一個候選恢復節點。圖1所示，RAEARA算法生成解的資源消耗非常接近于最優解。SPT算法的資源消耗比其他算法更高。即使ST算法跟SPT算法相比有更小的構建樹資源消耗，但是其目的節點和源節點之間的路徑更長，這是因為為了跟其他路徑相交，目的節點和源節點之間的路徑需要與最短的路徑相隔離。圖2中，如果恢復節點選擇不恰當，ST算法可能產生更高的恢復資源消耗。圖3證明RAEARA算法的重傳資源消耗依然最接近于最優情況。如圖4所示，通過對每個目的節點的觀測，計算每個數據包在網絡中的平均延遲。因為恢復節點更靠近目的節點，樹的深度(比如樹的最長路徑資源消耗)受M限制，因此，RAEARA算法比SPT算法和ST算法提供了更短的傳輸延遲，而且仿真延遲接近于接近于最優解。

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

4 小結

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