Edge congestion of shortest path systems for all-to-all communication

Author

Fiduccia, Charles M. ; Hedrick, Paul J.

Author_Institution

Center for Comput. Sci., Bowie, MD, USA

Volume

8

Issue

10

fYear

1997

fDate

10/1/1997 12:00:00 AM

Firstpage

1043

Lastpage

1054

Abstract

The problem of choosing a static shortest-path system that minimizes maximum edge congestion in a network is studied. Bounds based on parameters, such as diameter, bisection width, and average distance, are derived and conditions for producing uniform congestion on all edges are explored. Trees are shown to have maximum congestion on edges that are incident to a centroid node. Cartesian product graphs, which generalize multidimensional meshes, are shown to satisfy several closure properties and a generic factor-routing scheme is defined and shown to be optimal in many cases

Keywords

computational geometry; hypercube networks; telecommunication congestion control; trees (mathematics); Cartesian product graphs; all-to-all communication; average distance; bisection width; centroid node; diameter; edge congestion; generic factor-routing scheme; multidimensional meshes; shortest path systems; Concrete; Concurrent computing; Hypercubes; Multidimensional systems; Multiprocessor interconnection networks; Routing; Telecommunication traffic; Traffic control; Tree graphs; Upper bound;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.629487

Filename

629487