Topology Optimization for Heterogeneous DHT-Based Multicast

Topology Optimization for Heterogeneous DHT-Based Multicast

Hoai Son Nguyen (VNU University of Engineering and Technology, Vietnam)
DOI: 10.4018/978-1-5225-8295-3.ch006


Since the deployment of IP multicast remains restricted due to many practical and political issues, researchers have shifted focus to exploiting application-layer multicast for multicast data delivery. Recently there has been considerable interest in applying DHT routing algorithms to application-level multicast. However, early DHT-based multicast protocols are insufficient in addressing a number of technical issues such as heterogeneous capacity of nodes or node churn. In this chapter, the author describes a solution called BAM-Chord (i.e., Bandwidth Adaptive Multicast over Chord) that optimizes the topology of a multicast tree based on node bandwidth. In the proposed solution, node position (i.e., node identifier) on a BAM-Chord ring will be decided based on node bandwidth capacity such that it can build a wide and balanced multicast tree rooted at the source node. As a result, BAM-Chord protocol can utilize network resources of every node to reduce the depth of the multicast tree and take advantages of DHTs in maintaining the multicast tree.
Chapter Preview


The disadvantages of implementing multicast at the IP level (Deering, & Cheriton,1990) have led to the emergence of interesting application-level multicast approach (Banerjee, Bhattacharjee, &Kommareddy, 2002; Tran, Hua, & Do, 2004; Magharei, & Rejaie, 2010; Tsuneizumi, Aikebaier, Ikeda, Enokido, & Takizawa, 2011). Application-level multicast utilizes network capacity of end nodes that act not only as receivers but also as senders. Each end node can forward its received data to other end nodes, and therefore reduce the load at streaming servers. Since network capacities are heterogeneous between nodes and nodes can join/leave a network in anytime, a big challenge of application-level multicast protocols is how to build and maintain a multicast tree which can efficiently utilize network resources of end nodes while still guaranteeing the availability of data delivery.

In recent years, Distributed Hash Table (DHT) (Ratnasamy, Francis, Handley, & Karp, 2001; Stoica, Morris, Karger, Kaashoek, & Balakrisnan, 2001; Rowstron, & Druschel, 2001) becomes an active and ongoing area of research. Originally, DHTs were developed with applications like peer-to-peer file sharing. Recently, there has been considerable interest in applying DHTs to application-level multicast (Ratnasamy, Handley, Karp, & Shenker, 2001; Castro, Druschel, Kermarrec, & Rowstron, 2002; El-Ansary, Alima, Brand, & Haridi, 2003; Li, Sollins, & Lim, 2005; Huanga & Zhang, 2010) since DHTs have many advantages that are good for multicast applications: decentralization, scalability, fault tolerance, load balancing, and good routing performances. Generally, DHT-based application-layer multicast protocols utilize the structure of DHT-based overlay networks to send multicast messages. Thus, nodes in these systems do not need to maintain extra links to other nodes in the overlay network, except the links to neighbor nodes defined by a DHT algorithm. DHT-based multicast also gets benefits from failure recovery algorithms, which are implemented in most of DHT networks. Therefore, DHT-based application-layer multicast schemes can scale to multicast groups of thousands of nodes.

However, early DHT-based multicast designs are insufficient in addressing all of following issues:

  • Heterogeneous Bandwidths Between Nodes: Since the number of child nodes of a node in a multicast tree is decided based on the links to neighbor nodes without consideration of node’s bandwidth capacity, a node with low bandwidth may become a bottleneck if it is an internal node of a multicast tree and has a lot of child nodes;

  • Effective Bandwidth Utilization: If a node with high bandwidth is a leaf node, the system cannot utilize the bandwidth capacity of the node to deliver multicast messages;

  • Dynamic Membership: The optimization of multicast trees must be achieved even when member nodes join or leave at any time.

To utilize bandwidth of nodes effectively, Castro, Druschel, Kermarrec, Nandi, Rowstron, and Singh (2003) propose SplitStream, a multiple-tree solution constructing multiple multicast trees such that a node, which is an interior node of one tree will be a leaf node of all other trees. However, SplitStream require nodes to have equal out-bandwidth. In CAM-Chord design proposed by Zhang, Chen, Ling and Chow (2005), heterogeneity is tackled by allowing each node to decide its out-degree according to its out-bandwidth. However, their work did not consider the bandwidth capacity of nodes when building a multicast tree. Thus, effective bandwidth utilization issue still remains open. Huanga and Zhang (2010) tried to build a balanced tree on a Chord ring but the path length from source node to leaf nodes of the multicast tree is still long.

Key Terms in this Chapter

Chord Protocol: A typical DHT- based P2P network protocol proposed by Stoica et al. in the year 2001. In Chord, nodes and keys are assigned an m-bit identifier using from a one-dimensional circular key space and a finger table is built at each node for key-based lookup.

Finger Table: A table contains a set of links between a node to its successor node and a number of neighbor nodes. A node uses its finger table to determine the next hop during key location.

Application-Layer Multicast: Sending multicast data at the application layer in which multicast routing is implemented at peers instead of routers.

DHT-Based Message Routing: Route a message with a destination key to a node which is responsible for the destination key by the use of a DHT routing algorithm.

Distributed Hash Table: A class of decentralized distributed systems which support a hash table interface for storing and retrieving (key, value) pairs on P2P networks where a key is used to determine the node responsible for storing a value associated with the key.

Multicast-Tree: A tree rooted at the source node, which gives the paths of sending multicast data from the source node to other nodes of the tree.

Peer-to-Peer Networks: A network of computers, each of which acts as a node sharing computing resources such as file storage or network bandwidth within the network.

End Node: A user computer or a server which joins a P2P network. End nodes may join/leave the network freely with or without notification.

Complete Chapter List

Search this Book: