Scalable and efficient broadcasting algorithms for very large internetworks

Broadcast is a special case of routing in which a packet is to be delivered to a set that includes all the network nodes. While dynamic and distributed broadcast techniques have been proposed and used in the Internet, unfortunately they suffer from scalability problems, i.e. they are not efficient with respect to the tremendous size of today\u27s networks. Moreover, it has been observed that the cost of routing and the broadcast time are two conflicting performance measures as far as optimization is concerned, especially in large networks. Also, many of the current techniques are not robust enough and, give low performance under events of link failure. First, we show that in order to achieve universal reachability, internets have naturally acquired a multi-level hierarchical structure. Second, utilizing this existing hierarchy, we propose scalable broadcasting protocols which achieve near-optimal cost and time measures. Because of the hierarchy, our proposed algorithm only maintains information of links connected to direct neighbors, thereby making it scalable to future growth in size of the network. We show that time-optimal broadcast in point-to-point networks can be achieved by formulating the problem as finding maximum marching in bipartite graphs. Several heuristics based on matchings are presented. Performance bounds are derived along with numerical and simulation results obtained that prove the validity and feasibility of the scheme. (C) 1998 Elsevier Science B.V