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 "universal" stability results when edges in packet routing networks can have capacities and speeds/slowdowns. A packet routing scheduling rule is universally stable if it is stable for any network and a network is universally stable if every "greedy" scheduling rule is stable on this network. 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 (i.e. Longest in System packet gets highest priority) is not preserved when either the capacity or the speed is changing dynamically whereas many other common scheduling protocols do maintain their universal stability. 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. In terms of universal stability of networks, stability is preserved for dynamically changing capacities and speeds.
References
W. Aiello , Adaptive Packet Routing for Bursty Adversarial Traffic, Proc. of the 30th Ann. ACM Symposium on the Theory of Computing (STOC) (1998) pp. 359–368. Google Scholar- C. Àlvarez, M. Blesa, and M. Serna. A Characterization of Universal Stability for Directed Graphs in the Adversarial Queueing Model. Technical Report LSI-02-4-R, Departament de Llenguatges i Sistemes, Universitat Politècnica Catalunya, January 2002 . Google Scholar
M. Andrews , Universal Stability Results for Greedy Contention-Resolution Protocols, Proceedings of the Thirty-Seventh Annual IEEE Symposium on Foundations of Computer Science (1996) pp. 380–389. Google Scholar- M. Andrews, B. Awerbuch, A. Fernández, J. Kleinderg, F. T. Leighton, Z. Liu. Universal Stability Results and Performance Bounds for Greedy Contention-Resolution Protocols. Journal version of [3]; to appear in JACM . Google Scholar
-
M. Andrews , Instability of FIFO in Session Oriented Networks , Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms ( 2000 ) . Google Scholar -
M. Andrews and L. Zhang , The Effects of Temporary Sessions on Network Performance , Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms ( 2000 ) . Google Scholar - R. Bhattacharjee and A. Goel. Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. Unpublished manuscript, 2002 . Google Scholar
A. Borodin , Adversarial Queueing Theory, Proceedings of the Twenty–Eighth Annual ACM Symposium on Theory of Computing (1996) pp. 376–385. Google Scholar- A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. Williamson. Adversarial Queueing Theory. Journal version of [8]; to appear in JACM . Google Scholar
D. Gamarnik , Stability of Adversarial Queues via Fluid Models, Proceedings of the 39th Symposium on the Foundations of Computer Science (1998) pp. 60–70. Google ScholarD. Gamarnik , Stability of Adaptive and Non-Adaptive packet Rounting Policies in Adversarial Queuing Networks, Proceedings of the Thirty–First Annual ACM Symposium on Theory of Computing (1999) pp. 206–214. Google Scholar- A. Goel. Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing. Stanford University Technical Note STAN-CS-TN-97-59, June 1997 . Google Scholar
-
R. Motwani and P. Raghavan , Randomized Algorithms ( Cambridge University Press , 1995 ) . Crossref, Google Scholar - P. Tsaparas. Stability in Adversarial Queueing Theory M.Sc Thesis, Department of Computer Science, University of Toronto, 1997 . Google Scholar
