Bounds on the greedy routing algorithm for array networks

ABSTRACT

We extend previous work on greedy routing for array networks by providing bounds on the average delay and the average number of packets in the system. We analyze the dynamic routing problem, where packets are generated at each node according to a Poisson process. Each packet is sent to a destination chosen uniformly at random. Packets are routed greedily, first moving to the correct column and then to the correct row. Packets require unit time to travel across a directed edge between nodes; only a single packet can cross an edge at any given time, and packets waiting for an edge are buffered. Our bounds are based on comparisons with computationally more simple queueing networks, and the methods used are generally applicable to other network systems. A primary contribution of the paper is a new lower bound technique that also improves on the previous lower bounds by Stamoulis and Tsitsiklis for heavily loaded hypercube networks. [11] On heavily loaded array networks, our lower and upper bounds differ by only a small constant factor. We further examine extensions of the problem where our methods prove useful. For example, we consider variations where edges can have different transmission rates or the destination distribution is non-uniform. In particular, we study to what extent optimally configured array networks outperform the standard array network.

REFERENCES

• 1: Mor Harchol-Balter , Paul E. Black, Queueing analysis of oblivious packet-routing networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.583-592, January 23-25, 1994, Arlington, Virginia, United States
• 2: J. Jackson, "Jobshop-Like Queueing Systems," Management Science, vol. 10, 1963, 131-142.
• 3: N. Kahale and T. Leighton, private communication.
• 4: F.P. Kelly, Reversibility and Stochastic Networks, John Wiley & Sons, 1979.
• 5: Leonard Kleinrock, Communication nets; stochastic message flow and delay, Dover Publications, Incorporated, 1972
• 6: L. Kleinrock, Queuein9 Systems. Volume II:, John Wiley, 1975.
• 7: F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
• 8: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 9: J.D.C. Little, "A proof of the queueing formula L = )#W," Operations Research, volume 9, 383-387.
• 10: S.Ross, Introduction to Probability Models, Academic Press, Inc., 1989.
• 11: G.D. Stamoulis and J.N. Tsitsiklis, "The Efficiency of Greedy Routing in Hypercubes and Butterflies," Journal of the ACM, 199t.
• 12: D. Stoyan, Comparison Methods for Queues and Other Stochastic Models, John Wiley & Sons, 1983.
• 13: J. Walrand, An Introduction to Queueing Networks, Prentice-Hall, 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

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

General Terms:
Algorithms, Theory, Verification