Title

Scalable and efficient broadcasting algorithms for very large internetworks

Keywords

Bipartite graphs; Broadcasting; Distributed algorithms; Hierarchical networks; Maximum matching; Minimum spanning tree; Routing

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. © 1998 Elsevier Science B.V.

Publication Date

7-15-1998

Publication Title

Computer Communications

Volume

21

Issue

10

Number of Pages

912-923

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/s0140-3664(98)00140-6

Socpus ID

0032124267 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0032124267

This document is currently not available here.

Share

COinS