應用層群播路由協定之設計與效能分析

Design and Analysis of Application Layer Multicast Routing Protocols

黃家煇(Chia-Hui Huang)

指導教授 ： 柯開維

國立臺北科技大學/電資學院/資訊工程系研究所/博士(2013年)

https://doi.org/10.6841/NTUT.2013.00505

摘要

群播 (multicast) 對於許多需要一對多及多對多之資料傳送服務的網路應用如即時影音及檔案分享而言是一項重要的技術。網際網路群播 (IP multicast) 協定為實作於網路層且具有最佳效能的群播機制，但因為管理及安全等因素之限制，使得網際網路群播之全面建置也相對的困難，因此，應用層群播 (Application Layer Multicast, ALM) 應運而生。應用層群播之概念在於使應用層上之主機 (end system) 能夠取代網路路由器而具有執行群播路由協定之能力進而達成群播之效果。根據來源端個數之不同，應用層群播路由協定可分為單源 (single-source) 及多源 (multisource) 群播協定。

本論文旨在提出一個具有快速路徑回復 (fast route recovery) 及低成本之應用層群播路由機制。本論文首先提出一具有快速路徑回復特性之應用層群播路由協定 (Distributed Multisource Forwarding Trees, DMFTs)。接著，本論文證明多源和單源應用層群播的最佳成本 (minimum cost) 之間具有一倍數關係，意即多源應用層群播之最佳成本可以用單源群播之最佳成本乘以來源個數即可得到。基於對單源及多源應用層群播最佳成本之分析及推導，本論文再進一步探討網路規模 (network size) 及群播群組大小 (multicast group size) 對於群播最佳成本之影響，並發現應用層群播與網際網路群播之效能差距 (performance penalty) 會隨著群組大小之持續增大而呈現先上升再下降之趨勢。經由理論之探討及歸納，本論文提出了應用層群播路由機制之設計方針 (design principle)，其目標在於藉由降低群播樹之成本，使得群播之資料傳送在延遲 (delay)、延遲變異量 (jitter) 等影響即時應用之服務品質的效能指標能夠有效的改善。

本論文將所提出之設計方針應用於DMFTs路由機制並修改部份DMFTs架構而得到一新的群播架構 (Cluster-based Distributed Forwarding Trees, CDMFTs) ，經由電腦模擬之效能驗證，相對於DMFTs，CDMFTs在訊息控制量 (control overhead) 、延遲 (delay) 、延遲變異量 (jitter) 、連結壓力 (link stress) 以及傳送樹長度 (tree length) 等各種效能指標能達到2%至80%不等的改善，並且能夠維持快速路徑回復之特性。因此，本論文所得之研究成果對應用層群播之相關研究與應用設計人員將具有實用參考之價值。

關鍵字

應用層群播 ； 網際網路群播協定 ； 單源群播 ； 多源群播 ； 路徑回復機制 ； 最佳群播成本 ； 成本倍數關係

並列摘要

Application Layer Multicast (ALM) routing is an indispensable mechanism for efficient distribution of data from a source or many sources to many receivers. With the growing of Internet real-time and file sharing applications that demand large network resources and call for multicasting mechanism, the necessity of analyzing and deriving the minimum cost of ALM routing protocols and developing an efficient ALM routing protocol is explicit.

According to the number of sources, ALM routing protocols can be categorized into single-source and multisource. The main goal of this research is to design a multisource ALM routing protocol with fast route recovery and low cost. With the goal, a multisource ALM routing with fast route recovery mechanism, distributed data forwarding trees (DMFTs), was firstly developed, and the theoretical minimum cost of multisource ALM routing protocols was found by deriving and proving a multiplicative property on the costs of multisource ALM routings relative to single-source ones. With the multiplicative property, the minimum cost of multisource ALM routings can be simply obtained by multiplying the minimum cost of single-source ALM routings by the number of sources. By analyzing the minimum costs of single-source and multisource ALM routings, the research discovered and proved the cost impact that the performance penalty of ALM continuously increases with multicast group size until a certain group size is reached. That is, as the multicast group size is over the certain value, the performance penalty starts to decrease. From theoretical analyses, the research proposed principles to design an ALM routing protocol. The objective of the principles is to reduce the delay and jitter of ALM routing by reducing the total cost of ALM routing tree.

Applying the design principles on DMFTs, the research proposed a new multisource ALM routing protocol, cluster based distributed forwarding trees (CDMFTs). Through intensive computer simulations, it can be shown that the control overhead, dealy, jitter, link stress, and total tree length of CDMFTs were reduced by 2% to 80%, comparing to that of DMFTs. The results demonstrated the efficiency of CDMFTs as well as the effectiveness of the proposed design principles. The analytical analysis and design work provided useful insights for the researchers and developers of ALM routing protocols.

並列關鍵字

Application Layer Multicast (ALM) ； Internet Protocol (IP) Multicast ； Route Recovery ； Single-source ； Multisource ； Minimum Multicast Cost ； Multiplicative Property

參考文獻

[1] C. Telecom. [Online]. Available: http://mod.cht.com.tw/

[4] X. Hei, Y. Liu, and K. W. Ross, “Iptv over p2p streaming networks: the meshpull approach,” IEEE Communications Magazine, vol. 46, no. 2, pp. 86–92, 2008.

[5] BBC. [Online]. Available: http://www.bbc.co.uk/

[7] N. P. Radio. [Online]. Available: http://www.npr.org/

[8] J. L. Martins and S. Duarte, “Routing algorithms for content-based publish/ subscribe systems,” IEEE Communications Surveys & Tutorials, vol. 12, no. 1, pp. 39–58, 2010.