Topology Optimization For DHT - based Application Layer Multicast Nguyen Ngoc Anh Faculty of Information Technology Hanoi University of Engineering and Technology Vietnam National University, Hanoi Supervised by Doctor Nguyen Hoai Son A thesis submitted in fulfillment of the requirements for the degree of Master of Information Technology June, 2012 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ORIGINALITY STATEMENT ’I hereby declare that this submission is my own work and to the best of my knowledge it contains no materials previously published or written by another person, or substantial proportions of material which have been accepted for the award of any other degree or diploma at Coltech or any other educational insti- tution, except where due acknowledgment is made in the thesis. I also declare that the intellectual content of this thesis is the product of my own work. i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract In recent years, Distributed Hash Table (DHT) becomes active and ongoing area of research at a lot of universities and labs. DHT has many advantages: Decentraliza- tion, scalability, fault tolerance, load balancing, data integrity, and performance,.
Those properties make DHTs are very suitable for deploying multicast services at application layer and in fact, DHT-based network such as CAN, Chord, Pastry, Tapestry, etc can be used to implement Internet-scale application layer multicast. However, early DHT-based multicast systems are insufficient in addressing all of these issues: Heterogeneous node capacity, large- scale multicast and dynamic membership. Moreover, in those system, when one node joins into system through an arbitrary way, some factors are not considered: nodes bandwidth, nodes positon on DHT network (i.e node identifiers), thus, the multicast tree can be built inefficiently and not balance in structure. The solution for assigning an appropriate number of child nodes to each node is far from optimal in term of bandwidth: If the number of child nodes is too high, low capacity node will be overloaded, therefore slows the entire session multicast down.
If the number of child nodes is too low, high capacity nodes will be used inefficiently. In this thesis, we study the method to optimize topology for DHT-based multi- cast. We propose a DHT- based bandwidth adaptive multicast system that forcus on host heterogeneity, scalibility, fault tolerate. In our system, nodes bandwidth is firstly considered, result of this process is the basis for determining the level of the node and correlatively caculating nodes identify.
Level of a node is used to define maximum number of its child nodes. As a result, in our model, each node is assigned an optimal numbers of child nodes to forward multicast data. Thus, our method can make tradeoff between depth of the multicast tree and bandwidth of every node and take advandtages of DHTs in maintaining multicast tree in churn overlay. System chosen for implementation and avaluation is Chord.
This model is called Bandwidth Adaptive Multicast over Chord: BAM-Chord. ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail. I would like to express my great gratitude to my supervisor, Dr. Nguyen Hoai Son, in the Department of Communication and Networking at Hanoi University of Engineering and Technology of Vietnam National University, for his encouragement, support, patience, guidance and advice.
Without his constant invaluable direction and tolerance, I could not have become a better researcher. My thanks also go to Dr. Le Anh Cuong, Dr. Pham Bao Son, Dr.
Nguyen Ha Nam, who provided valuable guidance to my ideas in the writing of the thesis. I would also like to respect to my lecturers who has taught me educational subjects at Hanoi University of Engineering and Technology of Vietnam National University I owe all friends and colleagues a huge thank for their encouragement and friend- ship. They have provided great mental support to me when I got stressful at times. Last but not least, thank to my wife Nguyen Bao Tram for her sympathy and love during the past years.
I heartily thank my parents, parents-in-law and my sisters for their encouragement and the many years of support during my studies. Again, I owe my success in life as I am today to my parent’ unconditional love, hard work, and sacrifices To all, I thank you. iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table of Contents Abstract 1 Acknowledgements iii Abstract 1 1 Introduction 2 1.2 Application Layer Multicast .2 Application layer multicast protocols .2 DHT-based multicast .1 Introduction of P2P Networks .1 Unstructured P2P Network model .2 Hybrid P2P Network model .3 Structured P2P Network model .2 DHT-based structure P2P networks. 16 iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com TABLE OF CONTENTS v 2.2 Content Adressable Network .3 DHT-based multicast .1 CAN-based multicast .2 Chord-based multicast .4 Topology optimization issues for DHT-based multicast .3 Related works on topology optimization for DHT-based multicast .2 Capacity Aware Multicast based on Overlay Network - CAM- Chord .3 DHT-based lightweight broadcast algorithms in large-scale com- puting infrastructures.
28 3 Bandwidth Adaptive Multicast over Chord : BAM Chord 31 3. 36 4 Simulations and Evaluations 38 4.1 The depth of multicast tree. 40 5 Conclusions 42 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Figures 2.1 Type of transmissions .3 A Comparison between IP multicast and application-layer multicast .5 A unstructured P2P Network with a server .7 An example of Hybrid P2P Model .8 Scheme of a classic Hash Table .9 Scheme of a Distributed Hash Table (DHT) .10 A Chord ring with 6 bit identifier. Notice how the finger table is organized and how K54 is looked up following Chord’s algorithm .11 Example of Chord Finger table .12 Example of Content Addressable Network .13 Smart multicast in CAN.
The dot represents the starting node .14 An example of Chord-based multicast method. In this example, Node 1 sends messages to all nodes in the Chord ring.15 A simple example illustrating the basic approach of SplitStream. Original content is split into two stripes and correlatively, an inde- pendent multicast tree is built for each stripes. A node is a leaf in one tree and a interior in the other .16 An example of CAM- Chord, neighbors of x.17 Balanced Distributed broadcast tree construction using token in 16- node Chord .18 Balanced Distributed broadcast tree construction using partition in an 11-node Chord .1 An example of CAM- Chord, neighbors of x.
33 vi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LIST OF FIGURES vii 3.2 An example of CAM- Chord, neighbors of x.3 An example of CAM- Chord, neighbors of x.1 Average path length .2 Maximum path length .3 Average path length in Chord, CAM-Chord and BAM-Chord after 32 time steps .4 Average link number per node in Chord .5 Average link in Chord, CAM-Chord and BAM-Chord after 32 time steps. 41 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Tables 2.1 Definition of variables for node n, using m-bit identifiers. 19 viii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract In recent years, Distributed Hash Table (DHT) becomes active and ongoing area of research at a lot of universities and labs. DHT has many advantages: Decentraliza- tion, scalability, fault tolerance, load balancing, data integrity, and performance,.
Those properties make DHTs are very suitable for deploying multicast services at application layer and in fact, DHT-based network such as CAN, Chord, Pastry, Tapestry, etc can be used to implement Internet-scale application layer multicast. However, early DHT-based multicast systems are insufficient in addressing all of these issues: Heterogeneous node capacity, large- scale multicast and dynamic membership. Moreover, in those system, when one node joins into system through an arbitrary way, some factors are not considered: nodes bandwidth, nodes positon on DHT network (i.e node identifiers), thus, the multicast tree can be built inefficiently and not balance in structure. The solution for assigning an appropriate number of child nodes to each node is far from optimal in term of bandwidth: If the number of child nodes is too high, low capacity node will be overloaded, therefore slows the entire session multicast down.
If the number of child nodes is too low, high capacity nodes will be used inefficiently. In this thesis, we study the method to optimize topology for DHT-based multi- cast. We propose a DHT- based bandwidth adaptive multicast system that forcus on host heterogeneity, scalibility, fault tolerate. In our system, nodes bandwidth is firstly considered, result of this process is the basis for determining the level of the node and correlatively caculating nodes identify.
Level of a node is used to define maximum number of its child nodes. As a result, in our model, each node is assigned an optimal numbers of child nodes to forward multicast data. Thus, our method can make tradeoff between depth of the multicast tree and bandwidth of every node and take advandtages of DHTs in maintaining multicast tree in churn overlay. System chosen for implementation and avaluation is Chord.
This model is called Bandwidth Adaptive Multicast over Chord: BAM-Chord. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 1 Introduction 1.1 Motivation Today, Internet continues to grow rapidly, many communication requirements that we must deal with. Cause of the explosion in data communications, demand on transferring large volumes of data to many destination quickly increases. To solve bandwidth problems, multicast is a effective solution.
As the most cost-effective way of delivering the same data to a multiple receivers at the same time, multicast is suited to a large number of applications as mobile Internet, e-commerce, content rich applications, and multi-media services: television broadcast, video conferencing. The word ”multicast” is typically used to refer to network layer multicast - IP multicast and was proposed about some decades ago. However, IP multicast still has not been widely deployed because of various technical and administrational reasons. The disadvantages of implementing multicast at the IP level has led to an interesting application-level multicast.
Application layer multicast refers to the implementation of multicast capability at the application layer instead of network layer. A number of application-level multicast systems have been proposed that are built using structured peer-to-peer (p2p) overlays. Originally, distribute hash table (DHTs) were developed with applications like peer-to-peer file sharing. Recent years, there has been considerable interest in ap- plying DHTs to overlay multicast applications since it has many advantages: Decen- tralization, Scalability, Fault tolerance, Load balancing, and performance,.Those properties make DHTs are very suitable for deploying multicast services at applica- tion layer and in fact, DHT-based network such as CAN, Chord, Pastry, Tapestry, 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Motivation 3 etc has been already used to implement Internet -scale applicastion layer muticast. However, early DHT-based multicast systems are insufficient in addressing a number of technical issues: • Heterogeneous output bandwidth of Node: Since the number of child nodes of a node in a multicast tree is decided based on the DHT algorithm without consideration of nodes bandwidth capacity, a node with low bandwidth may become a bottleneck if it is an internal node of a multicast tree • Effective bandwidth utilization: If a node with high bandwidth is a leaf node, the system can not utilize the bandwidth capacity of the node to deliver mul- ticast messages. • Dynamic membership: The optimization of multicast trees must be achieved even when member nodes join or leave at anytime. To limit the multicasting load on a node, M.
Castro, el al. propose a solution in SplitStream (M.Castro, ), where one node informs its out-degree. When it re- ceives a futher join requests, it pushdown this request to its children. Nevertheless, Bharambe, et al.
explored and found heterogeneity issue is not address with Split- Stream (Feb, February 24 25 2005). With CAM CAM-Chord and CAM-Koorde designs in (6-1, 6 10 June 2005), heterogeneity is tackled by allowing node to al- ter out-degree according to its capacity. However, they did not describe how to maintain topology when the out-degree limits.