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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：43

、訪客IP：18.219.236.62

姓名

陳思源(Szu-Yuan Chen) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

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

相關論文

★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定	★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定	★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談	★ 基於范諾圖之同儕式網路虛擬環境狀態管理
★ 利用多變量分析之多人線上遊戲信任使用者選擇	★ 無位置資訊無線感測網路之覆蓋及連通維持
★ 同儕網路虛擬環境3D串流同儕選擇策略	★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作
★ 同儕式三維資料串流	★ IM Finder: 透過即時通訊網路線上使用者找尋解答
★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法	★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤
★ 頻寬感知同儕式3D串流	★ 無線感測網路旋轉指向天線定位法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本論文提出一個演算法，在軟體定義網路(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.

關鍵字(中)

★ 軟體定義網路
★ 群播樹
★ 延伸 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

論文目次

中文摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 v
表目錄 vi
一、緒論 1
二、背景知識與相關研究 4
2.1 軟體定義網路 4
2.1.1 SDN架構 4
2.1.2 OpenFlow協定 5
2.2 Steiner樹 8
2.2.1 Steiner樹問題 8
2.2.2 SCTF演算法 8
2.3延伸Dijkstra演算法 9
三、場景描述與解法 11
3.1. 場景描述 11
3.2. 解決方法 12
四、實驗模擬與效能評估 14
4.1. 模擬環境 14
4.2. 效能評估 19
五、結論 27
參考文獻 28

參考文獻

[1] Open Networking Foundation, “OpenFlow Switch Specification version 1.5.0,” December 19, 2014.

[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

[5] N. Foster, R. Harrison, M. Freedman, C. Monsanto, J. Rexford, A. Story, and D. Walker, “Frenetic: A Network Programming Language,” in Proc. of the 16th ACM SIGPLAN International Conference on Functional Programming, 2011, pp 279-291.

[6] C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker, “Composing Software-Defined Networks,” in Proc. of NSDI, 2013.

[7] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling Innovation in Campus Networks,” in ACM SIGCOMM Computer Communication, 2008.

[8] E. N. Gilbert and H. O. Pollak, “Steiner minimal trees.” SIAM Journal on Applied Mathematics, 1968.

[9] G. Robins, and A. Zelikovsky “Minimum steiner tree construction,” The Handbook of Algorithms for VLSI Phys. Design Automation, 2009.

[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.)

指導教授

江振瑞(Jehn-Ruey Jiang)

審核日期

2015-8-17

推文