Journal of the ACM Bibliography

Paul Bay and Gianfranco Bilardi. Deterministic on-line routing on area-universal networks. Journal of the ACM, 42(3):614-640, May 1995. [BibTeX entry]

Two deterministic routing networks are presented: the pruned butterfly and the sorting fat-tree. Both networks are area-universal, i e., they can simulate any other routing network fitting in similar area with polylogarithmic slowdown. Previous area-universal networks were either for the off-line problem, where the message set to be routed is known in advance and substantial precomputation is permitted, or involved randomization, yielding results that hold only with high probability. The two networks introduced here are the first that are simultaneously deterministic and on-line, and they use two substantially different routing techniques. The performance of their routing algorithms depends on the difficulty of the problem instance, which is measured by a quantity lambda known as the load factor. The pruned butterfly algorithm runs in time O(lambda log^2 N), where N is the number of possible sources and destinations for messages and lambda is assumed to be polynomial in N. The sorting fat-tree algorithm runs in O(lambda log N + log^2 N) time for a restricted class of message sets including partial permutations. Other results of this work include a ``flexible'' sorting circuit that is area-time optimal across a range of different input sizes and an area-time lower bound for routers based on wire-length arguments. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in: Paul Bay and Gianfranco Bilardi. Deterministic on-line routing on area-universal networks (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 297-306, St. Louis, Missouri, 22-24 October 1990. IEEE.

Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors) -- interconnection architectures; C.2.1 [Computer-Communication Networks]: Network Architecture and Design; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computation on discrete structures; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Area-universal, fat-tree, general purpose

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database