Distributed end‐host multicast algorithms for the Knowledge Grid
Wanqing Tu, Jogesh K. Muppala, Hai Zhuge · Concurrency and Computation Practice and Experience · 2006
Abstract The Knowledge Grid built on top of the peer‐to‐peer (P2P) network has been studied to implement scalable, available and sematic‐based querying. In order to improve the efficiency and scalability of querying, this paper studies the problem of multicasting queries in the Knowledge Grid. An m‐dimensional irregular mesh is a popular overlay topology of P2P networks. We present a set of novel distributed algorithms on top of an m‐dimensional irregular mesh overlay for the short delay and low network resource consumption end‐host multicast services. Our end‐host multicast fully utilizes the advantages of an m‐dimensional mesh to construct a two‐layer architecture. Compared to previous approaches, the novelty and contribution here are: (1) cluster formation that partitions the group members into clusters in the lower layer where cluster consists of a small number of members; (2) cluster core selection that searches a core with the minimum sum of overlay hops to all other cluster members for each cluster; (3) weighted shortest path tree construction that guarantees the minimum number of shortest paths to be occupied by the multicast traffic; (4) distributed multicast routing that directs the multicast messages to be efficiently distributed along the two‐layer multicast architecture in parallel, without a global control; the routing scheme enables the packets to be transmitted to the remote end hosts within short delays through some common shortest paths; and (5) multicast path maintenance that restores the normal communication once the membership alteration appears. Simulation results show that our end‐host multicast can distributively achieve a shorter delay and lower network resource consumption multicast services as compared with some well‐known end‐host multicast systems. Copyright © 2006 John Wiley & Sons, Ltd.