New Heuristic for Message Broadcasting in Networks

In this paper, we present a new heuristic that generates broadcast schemes in arbitrary networks. The heuristic gives optimal broadcast time for HyperCube, and best results for Cube-Connected Cycles and large Shuffle-Exchange graphs. Extensive simulations show that our new heuristic outperforms the best known broadcast algorithms for two different network models representing Internet generated using BRITE (Boston university Representative Internet Topology gEnerator). It also has a low time complexity, O(ElogV), which is lower compared to the complexities of most of the other good algorithms. The last advantage of the heuristic is that approximately one half of the nodes are informed via a shortest path from the originator, while the rest of the vertices receive the message via a path at most three hops longer.