Universal-stability results and performance bounds for greedy contention-resolution protocols

ABSTRACT

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability—will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

REFERENCES

• 1: William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276788]
• 2: A. Fernandez, Universal stability results for greedy contention-resolution protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.380, October 14-16, 1996
• 3: Matthew Andrews , Lisa Zhang, The effects of temporary sessions on network performance, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 09-11, 2000, San Francisco, California, United States
• 4: Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
• 5: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001 [doi>10.1145/363647.363659]
• 6: Andrei Broder , Eli Upfal, Dynamic deflection routing on arrays (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.348-355, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237981]
• 7: A. Z. Broder , A. M. Frieze, A general approach to dynamic packet routing with bounded buffers, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.390, October 14-16, 1996
• 8: CRUZ, R. L. 1991a. A calculus for network delay. Part I: Network elements in isolation. IEEE Trans. Inf. Theory 37, 1 (Jan.) 114-131.
• 9: CRUZ, R. L. 1991b. A calculus for network delay. Part II: Network analysis. IEEE Trans. Inf. Theory 37, 1 (Jan.) 132-141.
• 10: David Gamarnik, Stability of Adversarial Queues via Fluid Models, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.60, November 08-11, 1998
• 11: David Gamarnik, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.206-214, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301306]
• 12: Ashish Goel, Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing, Stanford University, Stanford, CA, 1997
• 13: HAJEK, B. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob. 14, 502-525.
• 14: 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
• 15: Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225133]
• 16: Nabil Kahale , Tom Leighton, Greedy dynamic routing on arrays, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.558-566, January 22-24, 1995, San Francisco, California, United States
• 17: KELLY, F. P. 1979. Reversibility and Stochastic Networks. Wiley, New York.
• 18: KLEINROCK, L. 1975. Queueing Systems. Wiley, New York.
• 19: 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]
• 20: LEIGHTON, F. T., MAGGS, B. M., AND RAO, S. B. 1994. Packet routing and job-shop scheduling in O(congestion 1 dilation) steps. Combinatorica 14, 2, 167-186.
• 21: Michael Mitzenmacher, Bounds on the greedy routing algorithm for array networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.346-353, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181446]
• 22: Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258659]
• 23: Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
• 24: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• 25: N. Robertson , P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory Series B, v.48 n.2, p.227-254, Apr. 1990 [doi>10.1016/0095-8956(90)90120-O]
• 26: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 27: Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237519]
• 28: STAMOULIS, G. D., AND TSITSIKLIS, J. N. 1994. The efficiency of greedy routing in hypercubes and butterflies. IEEE Trans. Commun. 42, 11 (Nov.), 3051-3061.
• 29: Leandros Tassiulas , Leonidas Georgiadis, Any work-conserving policy stabilizes the ring with spatial re-use, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.205-208, April 1996 [doi>10.1109/90.490748]

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory

Keywords:
adversarial queuing theory, end-to-end delay, network stability, packet scheduling