Hierarchical Message Dissemination In Very Large Wans

Message dissemination or broadcasting is the process whereby a message, originated by one source node, is transmitted to all the nodes of the network. Unfortunately, the current IP and emerging OSI Internet algorithms for broadcasting does not scale well with the tremendous growth of network size. Moreover, optimizing broadcast time and the cost of routing is difficult as they are conflicting performance measures. We propose a hierarchical broadcasting technique in very large arbitrary networks which achieves near optimal cost and time measures. The network is partitioned into hierarchical clusters which are interconnected with each other through gate nodes. Our approach is based on using a fully distributed minimum spanning tree algorithm within the gate-node network while achieving time optimal broadcasting within the local clusters by formulating the problem as finding maximum matching in constrained bipartite graphs. Extensive simulation results are presented which show the tradeoff between the two conflicting performance criteria