一個基於最佳化分群演算法之高擴充性及高效率群播協定

Abstract

摘要 由於網際網路多媒體應用日漸普及，群播協定成為一個熱門的研究主題。藉由群播可以有效減少網路頻寬消耗，但傳統的群播方法本身使用了IPv4 Class D的特殊保留位址，限制了網際網路上可以同時存在的群播不同群組的數量，而且傳統的群播方式必須要在路由器中保存大量狀態，導致擴充性不佳，無法在網際網路上全面實施。 為了提升擴充性，群播相關的研究接踵而來，最為人所知的就是Explicit Multicast(Xcast) ，由於Xcast將群播的目的地IP位址包在IP封包負載中，因此Xcast不需要在路由器中保存任何狀態，也不需要使用IPv4 Class D的特殊保留位址，如此一來群播的擴充性大增。但個別群組大小仍受到封包最大負載容量的限制。 為了突破Xcast受到封包最大負載容量的限制，Multiple Xcast及Generalized Xcast被提出來，透過將群組拆解成多個子群組，多次傳送Xcast封包來解決封包最大負載容量的限制，但這又衍生了新的問題，該如何將一個群組拆解會得到較好的傳輸效能，如何決定子群組的大小，那些組員該放在那些子群組等。 本篇論文中，我們提出了計算最佳化子群組大小的方式及最佳化分組。最佳化子群組大小是透過子群組大小及產生的資料量的關係式，傳送端可以在實際傳遞Xcast封包前，預先計算得知該將群組分成幾個子群組可以達到最少的資料量。而最佳化分組預先分析網路拓樸，來得到可以產生最短路徑的分組方式。當來源端可以產生最少數量的資料，並且透過最短路徑傳送時，就可以達到最佳的傳送效率。

Abstract Multicast became a popular research topic since more and more multimedia applications are deployed on Internet. Using multicast, we can reduce the consumption of network bandwidth effectively. But traditional multicast uses the reserved IPv4 Class D addresses. It limits the number of different multicast groups on Internet. On the other hand, the traditional multicast must maintain a large number of states in all routers. For this reason, the traditional multicast also experienced the limit of scalability, and not suitable to be used on Internet comprehensively. There are many researches about multicast to resolve the scalability problem, and one of the most famous protocol is “Explicit Multicast (Xcast)”. Xcast puts the addresses of all destinations into the IP packet payload as data, so it doesn’t need to maintain any state in any router, and doesn’t need to use any special reserved IPv4 Class D address. As a result, Xcast increases the scalability greatly, but the size of each group is still limited by the size of maximum transmission unit (MTU). Multiple Xcast and Generalized Xcast were proposed to break the limit of the size of MTU by reconstructing the group into multiple sub groups and transferring multiple Xcast packets. But the new problems came out, like how to reconstruct the group to get better transmission performance, how to decide the size of sub group, and how to put each destination into each sub group. In this thesis, we propose a new scheme which includes the method for calculating the optimal size of each sub group, and the optimal grouping method. The method for calculating the optimal size of each sub group is based on the relationship of the size of sub group and the corresponding amount of generated data. The source of a transmission can calculate the optimal size in advance. On the other hand, the optimal grouping is to get the shortest path of sub groups by analyzing the topology. We can get the best transmission performance when the source generates the least amount of data and the data is transferred by the shortest path.