Randomized routing and sorting on fixed-connection networks


Journal Article

This paper presents a general paradigm for the design of packet routing algorithms for fixed-connection networks. Its basis is a randomized on-line algorithm for scheduling any set of N packets whose paths have congestion c on any bounded-degree leveled network with depth L in O(c + L + log N) steps, using constant-size queues. In this paradigm, the design of a routing algorithm is broken into three parts: (1) showing that the underlying network can emulate a leveled network, (2) designing a path selection strategy for the leveled network, and (3) applying the scheduling algorithm. This strategy yields randomized algorithms for routing and sorting in time proportional to the diameter for meshes, butterflies, shuffle-exchange graphs, multidimensional arrays, and hypercubes. It also leads to the construction of an area-universal network: an N-node network with area Θ(N) that can simulate any other network of area O(N) with slowdown O(log N). © 1994 Academic Press, Inc.

Full Text

Duke Authors

Cited Authors

  • Lejghton, FT; Maggs, BM; Ranade, AG; Rao, SB

Published Date

  • January 1, 1994

Published In

Volume / Issue

  • 17 / 1

Start / End Page

  • 157 - 205

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1006/jagm.1994.1030

Citation Source

  • Scopus