最小延遲之應用層群播樹的啟發式演算法

A Heuristic Algorithm for Minimal Delay Application Layer Multicast Trees

蔡易陵(Yi-Lin Tsai)

指導教授 ： 林華君

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

摘要

群播(multicast)對於很多網路應用都是非常重要的核心，例如網路電台、多人會議、VOIP等等。但 IP Multicast 因為其先天的各種限制，如可擴充性、網路管理、硬體部署等問題，至今仍無法普及在網際網路普及。為了解決這個問題，許多近期的研究都著重於應用層的群播，將群播的功能轉移到應用層，底層延用傳統的單點廣播(unicast)網路，形成一個邏輯上的網路，即所謂的疊代網路(overlay network)，在疊代網路上做群播稱之為應用層群播(application layer multicast, ALM)。針對群播效率的相關研究主要著重於如何由疊代網路來產生群播用拓樸的演算法。按照應用上各種不同的需求，在設計上對於目標效率的定義也會有所不同，例如降低新舊節點的加入/離去等動作成本、提高整體架構上的容錯能力、最佳化平衡負載、最小化訊息傳送的延遲等等。因此針對不同的應用，應該要按其所需要的目標，設計出對其目標最有效率的演算法。
本篇論文以最小化應用層群播的延遲為目標，我們提出一個heuristic，其嘗試找出一個有著最小延遲的群播樹。相對於之前的方法定義疊代網路為一個無向的完全圖，我們的方法定義疊代網路為一個有向的非完全圖，其可以適用於更多種不同的網路架構。在效率方面，比起先前的一個類似方法 ，我們的方法與該方法時間複雜度一樣，但比起該方法，我們的方法所產生的群播樹的延遲可減少達28%，在效果上有著明顯的改進。

關鍵字

群播 ； 應用層群播 ； 最小化延遲

並列摘要

無資料

並列關鍵字

multicast ； application layer multicast ； minimum delay

參考文獻

[2] C. K. Yeo, B. S. Lee and M. H. Er, "A survey of application level multicast techniques," Comput. Commun., vol. 27, pp. 1547-1568, 2004.

[3] S. Banerjee, B. Bhattacharjee and C. Kommareddy, “Scalable Application Layer Multicast,” ACM Press New York, NY, USA, 2002,

[4] E. Brosh, A. Levin and Y. Shavitt, "Approximation and Heuristic Algorithms for Minimum-Delay Application-Layer Multicast Trees," IEEE/ACM Transactions on Networking, vol. 15, pp. 473-484, 2007.

[7] S. Banerjee, C. Kommareddy, K. Kar, B. Bhattacharjee and S. Khuller, "Construction of an efficient overlay multicast infrastructure for real-time applications," in IEEE INFOCOM, 2003, pp. 1521-1531.

[8] I. Cidon, I. Gopal and S. Kutten, "New models and algorithms for future networks," IEEE Trans. Inf. Theory, vol. 41, pp. 769-780, 1995.