JISE


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


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


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


JENG-WEI LIN1, TUN WEI WANG2 AND RAY-I CHANG2
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

  Retrieve PDF document (JISE_201301_11.pdf)