Simple algorithms for routing on butterfly networks with bounded queues

ABSTRACT

This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any pure queuing protocol, a routing problem in which each of the N inputs sends a packet to a randomly chosen output requires O(log N) steps, with high probability, provided that the queue size is a sufficiently large, but fixed, constant. We also show that for any deterministic non-predictive queuing protocol, there exists a permutation that requires &OHgr;(N/q log N) time to route, where q is the maximum queue size. We present a new algorithm for routing a random problem on a fully-loaded butterfly with bounded-size queues in O(log N) steps, with high probability. The algorithm is simpler than the previous algorithms of Ranade and Pippenger because it does not use ghost messages, it does not compare the ranks or destinations of packets as they pass through a switch, and it cannot deadlock. Finally, using Valiant's idea of random intermediate destinations, we generalize a result of Koch's by showing that, if each wire can support q messages, then for any permutation, the expected number of messages that succeed in locking down paths from their origins to their destinations in back-to-back butterflies is &OHgr;(N(log N1/q). The analysis also applies to store-and-forward algorithms that drop packets if they attempt to enter full queues.

REFERENCES

• 1: W. A. Aiello, F. T. Leighton, B. M. Maggs, and M. Newman. Fast algorithms for bit-serial routing on a hypercube. Mathematical Systema Theory, 24:253-271, 1991.
• 2: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• 3: D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18(2):155-193, April 1979.
• 4: K. Butcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring joint Competing Conference, volume 32, pages 307-314, 1968.
• 5: ButterflyTM Parallel Processor Overview. BBN Report No. 6148, Version 1, Cambridge, MA, March 1986.
• 6: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• 7: A. Gottlieb. An overview of the NYU Ultracomputer Project. in J. J. Dongarra, editor, Experimental Parallel Computing Architectures, pages 25-95. Elsevier Science Publishers, B. V., Amsterdam, The Netherlands, 1987.
• 8: W. Hoeffding. On the distribution of the number of successes in independent trials. Annals of Math. ~ matical Statiatica, 27:713-721, 1956.
• 9: R. R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Proceedings of the #gth Annual Symposium on Foundations of Computer Science, pages 221-230. IEEE, October 1988.
• 10: D. Krizane. Oblivious routing with limited buffer capacity. Technical Report TR-14-87, Center for Research in Computing Technology, Harvard University, Cambridge, MA, 1987.
• 11: C. P. Kruskal and M. Snir. The performance of multistage interconnection networks for multiproeessors. IEEE Transactions on Computers, C- 32(12):1091-1098, December 1983.
• 12: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 13: F. T. Leighton, B. M. Maggs, A. G. Ranade, and S. B. Rao. Randomized routing and sorting on fixed-connection networks. Unpublished manuscript.
• 14: T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proceedings of the #gth Annual Symposium on Foundations of Computer Science, pages 256-271. IEEE, October 1988.
• 15: T. Nskata, S. Matsushita, N. Tanabe, N. Kajihara, H. Onozuka, Y. Asano, and N. Koike. Parallel programming on Cenju: A multiprocessor system for modular circuit simulation. NEC Research g_4 De. velopment, 32(3):421-429, July 1991.
• 16: G. F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey, W. J. Kleinfelder, K. P. McAuliffe, E. A. Melton, V. A. Norton, and J. Weiss. An introduction to the IBM Research Parallel Processor Prototype (RP3). in J. J. Dongarra, editor, Experimental Parallel Computing Architectures, pages 123- 140. Elsevier Science Publishers, B. V., Amsterdam, The Netherlands, 1987.
• 17: N. Pippenger. Parallel communication with limited buffers. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pages 127-136. IEEE, October 1984.
• 18: P. Raghavan. Lecture notes on randomized algorithms. Research Report RC 15340 (#68237), IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY, January 1990.
• 19: A. G. Ranade. Constrained randomization for parallel communication. Technical Report YALEU/DCS/TR-511, Department of Computer Science, Yale University, New Haven, CT, 1987.
• 20: A. G. Ranade. Equivalence of message scheduling algorithms for parallel communication. Technical Report YALE/DCS/TR-512, Department of Computer Science, Yale University, New Haven, CT, 1987.
• 21: A. G. Ranade. How to emulate shared memory. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 185-194. IEEE, October 1987.
• 22: George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
• 23: H. Suzuki, H. Nagano, T. Suzuki, T. Takeuichi, and S. Iwasaki. Output-buffer switch architecture for asynchronous transfer mode. In Proceedings of the 1989 IEEE International Conference on Communications, pages 99-103, June 1989.
• 24: T. Szymemski and S. Shaikh. Markov chain analysis of packet-switched banyans with arbitrary switch sizes, queue sizes, link multiplicities and speedups. In Proceedings of the IEEE INFOCOM '89, pages 960-971, April 1989.
• 25: Athanasios M. Tsantilas , L. G. Valiant, Communication issues in parallel computation, 1990
• 26: Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
• 27: L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Competing, 11(2):350- 361, May 1982.
• 28: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 29: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Performance, Theory