Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11]


Journal of Information Science and Engineering, Vol. 29 No. 1, pp. 149-163 (January 2013)

Optimal Schedule on Message Broadcast Tree in Structured Peer-to-Peer Networks*

1Department of Information Management
Tunghai University
Taichung, 407 Taiwan
2Department of Engineering Science and Ocean Engineering
National Taiwan University
Taipei, 106 Taiwan

In a peer-to-peer (P2P) network, broadcast is a fundamental service for many operations. However, it is not trivial for an activated peer, who has received a broadcast message, to find a non-activated peer in P2P networks. In past years, it had proposed to explicitly build a spanning tree so that each peer can forward the broadcast message to its children along the edges on the tree, and aggregate useful information in the reverse direction. In this paper, we further schedule the message forwardings in the tree so that the total time to complete the broadcast is reduced. We assume that, in a cooperative environment, an activated peer can send a broadcast message to a non-activated descendent peer in one round. We present an optimal algorithm and its two simplified variants to compute a minimum round schedule on the tree. Simulation results show that the required time to complete a broadcast is significantly reduced in terms of both round numbers and hop counts. In addition, the load of peers is more balanced.

Keywords: structured P2P, DHT, message broadcast tree, scheduling

Full Text () Retrieve PDF document (201301_11.pdf)

Received August 20, 2011; revised December 4, 2011 & January 19, 2012; accepted February 18, 2012.
Communicated by Ren-Hung Hwang.
* This work was supported in part by the National Science Council, Taiwan, under Grants No. NSC 95-2221-E- 029-018- and 100-2218-E-002-007-.