Topology Optimization for Heterogeneous DHT-Based Multicast

Introduction

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.