Adversarial queuing theory

ABSTRACT

We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.

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: Matthew Andrews, Instability of FIFO in session-oriented networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.440-447, January 09-11, 2000, San Francisco, California, United States
• 3: Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001 [doi>10.1145/363647.363677]
• 4: 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
• 5: 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]
• 6: BERTSIMAS, D., GAMARNIK, D., AND TSITSIKLIS, J. N. 1996. Stability conditions for multiclass fluid queuing networks. IEEE Trans. Automat. Cont. 41 (Nov.), 1618-1631.
• 7: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
• 8: BORODIN, A., OSTROVSKY, R., AND RABANI, Y. 2001. Routing networks with speeds and capacities. In Proceedings of the 12th Annual ACM-SIAM Symposium on Theory of Computing. ACM, New York.
• 9: BRAMSON, M. 1994a. Instability of FIFO queuing networks. Ann. Appl. Prob. 4, 414-431.
• 10: BRAMSON, M. 1994b. Instability of FIFO queuing networks with quick service times. Ann. Appl. Prob. 4, 693-718.
• 11: BRAMSON, M. 1996. Convergence to equilibria for fluid models of FIFO queuing networks. Que. Syst. 22, 5-45.
• 12: 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
• 13: CRUZ, R. L. 1991a. A calculus for network delay, Part I. IEEE Trans. Inf. Theory 37 (Jan.), 114-131.
• 14: CRUZ, R. L. 1991b. A calculus for network delay, Part II. IEEE Trans. Inf. Theory 37 (Jan.), 132-141.
• 15: DAI, J. G. 1995. On positive Harris recurrence of multiclass queuing networks: A unified approach via fluid limit models. Ann. Appl. Prob. 5, 49-77.
• 16: DAI, J. G., AND MEYN, S. P. 1995. Stability and convergence of moments for multiclass queuing networks via fluid limit models. IEEE Trans. Automat. Cont. 40 (Nov.), 1889-1904.
• 17: J. G. Dai , G. Weiss, Stability and instability of fluid models for reentrant lines, Mathematics of Operations Research, v.21 n.1, p.115-134, Feb. 1996 [doi>10.1287/moor.21.1.115]
• 18: DOWN, D. D., AND MEYN, S. P. 1995. Stability of acyclic multiclass queuing networks. IEEE Trans. Automat. Cont. 40, 5, 916-920.
• 19: DURRETT, R. 1995. Probability: Theory and Examples, 2nd ed. Duxbury Press, Belmont, Calif.
• 20: 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
• 21: 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]
• 22: Ashish Goel, Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing, Stanford University, Stanford, CA, 1997
• 23: HAJEK, B. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob. 14, 502-525.
• 24: 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
• 25: 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]
• 26: JACKSON, J. R. 1963. Jobshop-like queuing systems. Manage. Sci. 10, 131-142.
• 27: 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
• 28: KELLY, F. P. 1979. Reversibility and stochastic networks. Wiley, New York.
• 29: KLEINROCK, L. 1975. Queuing Systems. Wiley, New York.
• 30: 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]
• 31: LEIGHTON, F. T., MAGGS, B. M., AND RAO, S. B. 1994. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica 14, 167-180.
• 32: LEIGHTON, F. T., MAGGS, B. M., AND RICHA, A. W. 1999. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 3, 375-401.
• 33: LOEVE, M. 1978. Probability Theory, vol. 2. Springer-Verlag, New York.
• 34: LU, S. H., AND KUMAR, P. R. 1991. Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automat. Cont. 36, 12, 1406-1416.
• 35: K. Mani Chandy , John H. Howard, Jr. , Donald F. Towsley, Product Form and Local Balance in Queueing Networks, Journal of the ACM (JACM), v.24 n.2, p.250-263, April 1977 [doi>10.1145/322003.322009]
• 36: Yishay Mansour , Boaz Patt-Shamir, Greedy packet scheduling on shortest paths (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.165-175, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112615]
• 37: MEYN, S. P., AND DOWN, D. 1994. Stability of generalized Jackson networks. Ann. Appl. Prob. 4, 124-148.
• 38: D. Mitra , R. A. Cieslak, Randomized parallel communications on an extension of the omega network, Journal of the ACM (JACM), v.34 n.4, p.802-824, Oct. 1987 [doi>10.1145/31846.42226]
• 39: 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]
• 40: 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]
• 41: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 42: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 43: PEMANTLE, R., AND ROSENTHAL, J. S. 1998. Moment conditions for a sequence with negative drift to be uniformly bounded in L. Tech. Rep. 9814. Dept. Statistics, Univ. Toronto, Toronto, Ont., Canada.
• 44: PEMANTLE, R., AND ROSENTHAL, J. S. 1999. Moment conditions for a sequence with negative drift to be uniformly bounded in L. Stoch. Proc. Their Appl. 82, 143-155.
• 45: PERKINS, J. R., AND KUMAR, P. R. 1989. Stable distributed real-time scheduling of flexible manufacturing/assembly/disassembly systems. IEEE Trans. Automat. Cont. 34, 139-148.
• 46: 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]
• 47: RYBKO, A. N., AND STOLYAR, A. L. 1992. Ergodicity of stochastic processes describing the operation of open queuing networks. Prob. Inf. Trans. 28, 199-220.
• 48: SEIDMAN, T. I. 1994. 'First come, first serve' can be unstable. IEEE Trans. Automat. Cont. 39, 2166-2171.
• 49: 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]
• 50: 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]
• 51: TSAPARAS, P. 1997. Stability in adversarial queuing theory. M.Sc dissertation. Dept. of Computer Science, Univ. of Toronto, Toronto, Ont. Canada.
• 52: WALRAND, J. 1988. An Introduction to Queuing Networks. Prentice-Hall, Englewood Cliffs, N.J.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

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

General Terms:
Theory

Keywords:
packet routing, scheduling protocols, stability