使用延伸Dijkstra演算法建立Steiner樹用於軟體定義網路群播

本論文提出一個演算法，在軟體定義網路(Software-Defined Networking, SDN)架構中，利用延伸Dijkstra最短路徑(Extended Dijkstra’s Shortest Path)演算法與修改的(Modified)SCTF(Selective Closest Terminal First) Steiner樹演算法建立群播樹(multicast tree)以實作群播(multicast)傳輸方式，可以使用在如線上直播影片串流(live video streaming)傳輸上，降低延遲時間(delay)、降低封包傳輸量及減少網路使用頻寬(bandwidth)，更有效率地分配網路資源，以減輕尖峰時段經常會出現的嚴重壅塞現象。延伸Dijkstra最短路徑演算法，不僅考慮邊的權重(延遲)，連節點的權重也一併考慮，使得交換器處理封包的時間也能考量進實驗模擬中，因此可以建立具有真正最短延遲的封包傳輸路徑。另一方面，在改良的SCTF(Selective Closest Terminal First)Steiner樹演算法中，我們將離群播來源(source)較近的節點優先加入優先佇列(priority queue)中，可以有效地減少Steiner樹內部節點( internal node)的數目，因而大量減少頻寬的使用。我們使用EstiNet網路模擬器針對不同的網路拓樸(topology)、不同數目的群播來源伺服器(server)、不同數目的群播群組(group)與不同數目的群播資料訂閱者(subscriber)，採用固定位元速率( constant bit rate)與現實SDN交換器的參數進行模擬實驗。我們修改Ryu控制器實作群播傳輸和相關演算法，以比較所提演算法與其他6種相關的演算法在平均端到端延遲(average end-to-end delay)和總頻寬消耗(total bandwidth consumption)方面的效能。我們發現所提演算法具有最佳綜合效能，因為其在總頻寬消耗方面僅次於窮舉的最佳Steiner樹演算法，而在端到端延遲方面僅次於不考慮頻寬消耗的延伸Dijkstra最短路徑演算法。

關鍵字

軟體定義網路；群播樹；延伸 Dijkstra演算法； Steiner樹； SCTF演算法；端到端延遲；總頻寬消耗

並列摘要

We propose a method to build multicast tree for live video streaming with Extended Dijkstra’s Shortest Path algorithm and Modified Selective Closest Terminal First Steiner Tree algorithm. It can decrease the delay time, the volume of package transmission, and the usage of Internet bandwidth. We can allocate network resources more efficiently to reduce the heavy congestion in the rush hour. Extended Dijkstra’s Shortest Path algorithm considers not only the edge weights but also the node weights for building package transmission path with the shortest delay. In Modified SCTF Steiner Tree algorithm, we let the node near to source have higher priority to add in priority queue. In this way, we can decrease the number of internal node in Steiner tree for using less bandwidth. We take our experiment in EstiNet simulator with different network topology, different number of servers, different number of multicasting groups, and different number of multicasting subscribers. We simulate our method with constant bit rate and modified Ryu controller. We compare the average end-to-end delay and total bandwidth consumption between our algorithm and other six kinds of related algorithms. The results show that the proposed algorithm seconds only to the exhaustive optimal Steiner tree algorithm in total bandwidth consumption, and has the least average end-to-end delay after Extended Dijkstra’s Shortest Path algorithm.

並列關鍵字

Software-Defined Networking ； multicast tree ； Extended Dijkstra’s algorithm ； Steiner tree ； Selective Closest Terminal First algorithm ； average end-to-end delay ； total bandwidth consumption

參考文獻

[2] B. Nunes, M. Mendonça, X. Nguyen, K. Obraczk, and T. Turletti, “A survey of software-defined networking: Past, present, and future of programmable networks,” to appear in IEEE Communications Surveys & Tutorials, 2014.

[3] S. Jain, et. al., “B4, Experience with a Globally-Deployed Software Defined WAN,” ACM SIGCOMM conference, 2013.

[4] J. Jiang, H. Huang, J. Liao, and S. Chen, “Extending Dijkstra’s Shortest Path Algorithm for Software Defined Networking,” in APNOMS, Asia-Pacific. IEEE, 2014

[10] S. RAMANATHAN,” Multicast tree generation in networks with asymmetric links,” in IEEE/ACM Transactions on Networking (TON), 1996

[11] S. Wang, C. Chou, and C. Yang,”EstiNet openflow network simulator and emulator,” Communications Magazine, IEEE, 2013.)

國際替代計量

使用延伸Dijkstra演算法建立Steiner樹用於軟體定義網路群播

未授權

主題瀏覽