Steiner Tree for Fast Data Distribution
Hongbing Fan, Yue-Ang Chen, Ilias Kotsireas, Roderick Melnik, Brian West · AIP conference proceedings · 2011
This paper studies the multicast problem of distributing data from a source node to a group of destination nodes along a peer‐to‐peer (P2P) overlay network of tree topology. A star‐based data distribution protocol is used, which allows a node to send data packet to all its children one after another. After all its children receive the data, the node signals them to send the data to their children. The data distribution time of this protocol is defined to be the time span starting from data dispatching at the source node and ending at data received on all destination nodes. The problem is to find a Steiner tree connecting the source node and destination nodes that minimizes data distribution time. A formulation of data distribution time is given and used as an objective function in finding a Steiner tree. The corresponding optimization problem is NP‐hard. A heuristic algorithm is presented, which derives an optimal solution when data transfer delays between all pairs of nodes are the same.