Routing schemes for multiple random broadcasts in arbitrary network topologies

Varvarigos, EA

doi:10.1109/71.532119

Routing schemes for multiple random broadcasts in arbitrary network topologies

1996-01-01

7

PRE

AI

DOI：10.1109/71.532119

Original

Original request for help

Save

Abstract

En 中文

We consider the problem where packets are generated at each node of a network according to a Poisson process with rate lambda, and each of them has to be broadcast to all the other nodes. The network topology is assumed to be an arbitrary bidirectional graph. We derive upper bounds on the maximum achievable broadcast throughput, and lower bounds on the average time required to complete a broadcast. These bounds apply to any network topology, independently of the scheme used to perform the broadcasts. We also propose two dynamic broadcasting schemes, called the indirect and the direct broadcasting scheme, that can be used in a general topology, and we evaluate analytically their throughout and average delay. The throughput achieved by the proposed schemes is equal to the maximum possible, if a half-duplex link model is assumed, and is at least equal to one half of the maximum possible, if a full-duplex model is assumed. The average delay of both schemes is on the order of the diameter of the trees used to perform the broadcasts. The analytical results obtained do not use any approximating assumptions.

Keywords:

general graphs

edge-disjoint trees

dynamic broadcasting

queuing systems

Routing schemes for multiple random broadcasts in arbitrary network topologies

Abstract

AI Summary

Journal

Organization