A New Heuristic Algorithm for Minimum Delay Application Layer Multicast Trees

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

林宗銘(Tsung-Ming Lin)

指導教授 ： 林華君

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

摘要

本篇論文主要研究方向在於設計一個應用層之上的啟發式群播樹演算法。主要會與過去他人所提出的啟發式演算法做比較。我們以數個參數變化作各種環境的模擬，模擬結果顯示我們所提出的演算法效能，一般而言，在大部分的狀況之下都能夠比過去的方法改善超過10%，最好的狀況則可達到50%的改善幅度。

關鍵字

應用層 ； 群播樹 ； 啟發式 ； 演算法

並列摘要

HASH(0x1d1b46e0)

並列關鍵字

application layer ； multicast tree ； heuristic algorithm ； HASH(0x1d1b45a0)

參考文獻

[9] M. Garey and D. Johnson, Computers and Intractability. San Francisco: Freeman, 1979.

[1] 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.

[2] A. Bar-Noy, S. Guha, J. S. Naor, and B. Schieber, “Message multicasting in heterogeneous networks,” SIAM Journal on Computing, vol. 30, no. 2, pp. 347-358, 2001.

[3] E. Brosh, “Approximation and heuristic algorithms for minimum delay application-layer multicast trees,” Master’s thesis, Departement of EE Systems, Tel-Aviv University, Ramat-Aviv, Israel, 2003.

[6] 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.