使用延伸Dijkstra演算法建立Steiner樹用於軟體定義網路群播;Building Steiner Tree with Extended Dijkstra′s Algorithm for Software-Defined Networking Multicast

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/68932

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/68932

Title:	使用延伸Dijkstra演算法建立Steiner樹用於軟體定義網路群播;Building Steiner Tree with Extended Dijkstra′s Algorithm for Software-Defined Networking Multicast
Authors:	陳思源;Chen,Szu-Yuan
Contributors:	資訊工程學系
Keywords:	軟體定義網路;群播樹;延伸 Dijkstra演算法;Steiner樹;SCTF演算法;端到端延遲;總頻寬消耗;Software-Defined Networking;multicast tree;Extended Dijkstra’s algorithm;Steiner tree;Selective Closest Terminal First algorithm;average end-to-end delay;total bandwidth consumption
Date:	2015-08-17
Issue Date:	2015-09-23 14:46:53 (UTC+8)
Publisher:	國立中央大學
Abstract:	本論文提出一個演算法，在軟體定義網路(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最短路徑演算法。 ;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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	411	View/Open

社群 sharing

Loading...