Journal of the ACM Bibliography

Abstract

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

• Friedhelm Meyer auf der Heide and Christian Scheideler. Deterministic routing with bounded buffers: Turning offline into online protocols. In 37th Annual Symposium on Foundations of Computer Science, pages 370-379, Burlington, Vermont, 14-16 October 1996. IEEE.

• Bruce M. Maggs and Eric J. Schwabe. Real-time emulations of bounded-degree networks. Information Processing Letters, 66(5):269-276, 16 June 1998.

Selected references

• M. Ajtai. Recursive construction for 3-regular expanders. In 28th Annual Symposium on Foundations of Computer Science, pages 295-304, Los Angeles, California, 12-14 October 1987. IEEE.

• G. Bilardi and F. P. Preparata. Size-time complexity of Boolean networks for prefix computations. Journal of the ACM, 36(2):362-382, April 1989.

• Ronald I. Greenberg and Charles E. Leiserson. Randomized routing on fat-trees (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 241-249, Portland, Oregon, 21-23 October 1985. IEEE.

• Kieran T. Herley. Efficient simulations of small shared memories on bounded degree networks (preliminary version). In 30th Annual Symposium on Foundations of Computer Science, pages 390-395, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Tom Leighton and Bruce Maggs. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. In 30th Annual Symposium on Foundations of Computer Science, pages 384-389, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Tom Leighton, Bruce Maggs, and Satish Rao. Universal packet routing algorithms (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 256-269, White Plains, New York, 24-26 October 1988. IEEE.

• Nicholas Pippenger. Parallel communication with limited buffers (preliminary version). In 25th Annual Symposium on Foundations of Computer Science, pages 127-136, Singer Island, Florida, 24-26 October 1984. IEEE.

• Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335-348, April 1989.

• Abhiram G. Ranade. How to emulate shared memory (preliminary version). In 28th Annual Symposium on Foundations of Computer Science, pages 185-194, Los Angeles, California, 12-14 October 1987. IEEE.

• Eli Upfal. Efficient schemes for parallel communication. Journal of the ACM, 31(3):507-517, July 1984.

• Eli Upfal. An O(log N) deterministic packet routing scheme (preliminary version). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 241-250, Seattle, Washington, 15-17 May 1989.

• L. G. Valiant and G. J. Brebner. Universal schemes for parallel communication. In Conference Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computation, pages 263-277, Milwaukee, Wisconsin, 11-13 May 1981.

• Abraham Waksman. A permutation network. Journal of the ACM, 15(1):159-163, January 1968.

Shortcuts: