Stability preserving transformations: packet routing networks with edge capacities and speeds

ABSTRACT

In the context of an adversarial input model, we consider the effect on stability results when edges in packet routing networks can have capacities and speeds/slowdowns. In traditional packet routing networks, every edge is considered to have the same unit capacity and unit speed. We consider both static modifications (i.e. where the capacity or speed of an edge is fixed) and dynamic modifications where either the capacity or the speed of an edge can be dynamically changing over time. Amongst our results, we show that the universal stability of LIS is not preserved when either the capacity or the speed is changing dynamically whereas many other common scheduling protocols do maintain their universal stability. In terms of universal stability of networks, stability is preserved for dynamically changing capacities and speeds. The situation for static modifications, is not as clear but we are able to show that (in contrast to the dynamic case) that any “well defined” universally stable scheduling rule maintains its universality under static capacities, and common scheduling rules also maintain their universal stability under static speeds.

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 , 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, 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
• 5: 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
• 6: 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]
• 7: 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]
• 8: 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
• 9: 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]
• 10: Ashish Goel, Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing, Stanford University, Stanford, CA, 1997
• 11: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 12: P. TSAPARAS. Stability in Adversarial Queueing Theory M.Sc Thesis, Department of Computer Science, University of Toronto, 1997.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Routing and layout

General Terms:
Algorithms, Performance, Reliability, Standardization, Theory, Verification