An O(logN) deterministic packet routing scheme

ABSTRACT

We present a deterministic &Ogr;(log N) time algorithm for the problem of routing an arbitrary permutation on an N-processor bounded-degree network with bounded buffers. Unlike all previous deterministic solutions to this problem, our routing scheme does not reduce the routing problem to sorting and does not use the Ajtai, Komlos and Szemeredi sorting network [AKS]. Consequently, the constant in the run time of our routing scheme is substantially smaller, and the network topology is significantly simpler.

REFERENCES

• Al1: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• Al2: N Alon, Expanders, sorting in rounds and superconcentrators of limited depth, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.98-102, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22156]
• AKS: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• Ba: K. Batcher, Sorting Networks and their Applications, Proc. AFiPS Spring Joint Conference, Vol. 32, 1988, pp. 307-314.
• BH: 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]
• CD: R. Cole and C.O. Dunlaing, Note on the AKS Sorting Network, U1- tracomputer Note ~109, Computer Science Department Technical Report ~243, New York University, 1988.
• Le: Tom Leighton, Tight bounds on the complexity of parallel sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.71-80, December 1984 [doi>10.1145/800057.808667]
• LPS: A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
• Pa: M. S. Paterson, Improved Sorting Networks with O(log n) Depth, University of Warwick, Coventry, UK, 1987
• Ta: R.M. Tanner, Explicit Concentrators from Generalized N-gons, SIAM J. on Algebraic & Discrete Methods 5, (1984), pp. 287-293.

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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

General Terms:
Algorithms, Theory