Title

Scalable and efficient broadcasting algorithms for very large internetworks

Authors

Authors

S. Chatterjee;M. A. Bassiouni

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Comput. Commun.

Keywords

broadcasting; routing; minimum spanning tree; bipartite graphs; maximum; matching; hierarchical networks; distributed algorithms; NETWORKS; TREES; Computer Science, Information Systems; Engineering, Electrical &; Electronic; Telecommunications

Abstract

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's 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.

Journal Title

Computer Communications

Volume

21

Issue/Number

10

Publication Date

1-1-1998

Document Type

Article

Language

English

First Page

912

Last Page

923

WOS Identifier

WOS:000074719300005

ISSN

0140-3664

Share

COinS