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

In a peer-to-peer (P2P) network, broadcast is a fundamental service for many opera-tions. However, it is not trivial for an activated peer, who has received a broadcast mes-sage, to find a non-activated peer in P2P networks. In past years, it had proposed to ex-plicitly 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 di-rection. 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 envi-ronment, 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 re-quired time to complete a broadcast is significantly reduced in terms of both round num-bers and hop counts. In addition, the load of peers is more balanced