An Adversarial Construction of Instability Bounds in LIS Networks

In this work, we study the impact of dynamically changing link slowdowns on the stability properties of packetswitched networks under the Adversarial Queueing Theory framework. Especially, we consider the Adversarial, Quasi-Static Slowdown Queueing Theory model, where each link slowdown may take on values in the two-valued set of integers {1, D} with D > 1 which remain fixed for a long time, under a (w, ¤ü)-adversary. In this framework, we present an innovative systematic construction for the estimation of adversarial injection rate lower bounds, which, if exceeded, cause instability in networks that use the LIS (Longest-in- System) protocol for contention-resolution. In addition, we show that a network that uses the LIS protocol for contention-resolution may result in dropping its instability bound at injection rates ¤ü > 0 when the network size and the high slowdown D take large values. This is the best ever known instability lower bound for LIS networks.

Authors:

• Dimitrios Koukopoulos

Keywords:

• Network stability
• quality of service
• adversarial queueing theory
• greedy scheduling protocols.

References:

[1] C. Alvarez, M. Blesa, J. Diaz, M. Serna and A. Fernandez, "Adversarial
Models for Priority-Based Networks," Networks, Vol. 45, No. 1, pp. 23-
35, January 2005.
[2] C. Alvarez, M. Blesa and M. Serna, "A Characterization of Universal
Stability in the Adversarial Queuing model," SIAM Journal on
Computing, Vol. 34, No. 1, pp. 41-66, 2004.
[3] C. Alvarez, M. Blesa and M. Serna, "The Impact of Failure Management
on the Stability of Communication Networks," in Proceedings of the
10th International Conference on Parallel and Distributed Systems, pp.
153-160, July 2004.
[4] M. Andrews, B. Awerbuch, A. Fernandez, J. Kleinberg, T. Leighton and
Z. Liu, "Universal Stability Results for Greedy Contention-Resolution
Protocols," Journal of the ACM, Vol. 48, No. 1, pp. 39-69, January
2001.
[5] E. Anshelevich, D. Kempe and J. Kleinberg, "Stability of Load
Balancing Algorithms in Dynamic Adversarial Systems," in Proceedings
of the 34th Annual ACM Symposium on Theory of Computing, pp. 399-
406, May 2002.
[6] B. Awerbuch, P. Berenbrink, A. Brinkmann and C. Scheideler, "Simple
Routing Strategies for Adversarial Systems," in Proceedings of the 42nd
IEEE Symposium on Foundations of Computer Science, pp. 158-167,
October 2001.
[7] A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan and D. Williamson,
"Adversarial Queueing Theory," Journal of the ACM, Vol. 48, No. 1, pp.
13-38, January 2001.
[8] A. Borodin, R. Ostrovsky and Y. Rabani, "Stability Preserving
Transformations: Packet Routing Networks with Edge Capacities and
Speeds," in Proceedings of the 12th Annual ACM-SIAM Symposium on
Discrete Algorithms, pp. 601-610, January 2001.
[9] H. Chen and D. D. Yao, Fundamentals of Queueing Networks. Springer-
Verlag, 2000.
[10] J. Diaz, D. Koukopoulos, S. Nikoletseas, M. Serna, P. Spirakis and D.
Thilikos, "Stability and Non-Stability of the FIFO Protocol," in
Proceedings of the 13th Annual ACM Symposium on Parallel
Algorithms and Architectures, pp. 48-52, July 2001.
[11] D. Koukopoulos, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "On
the Stability of Compositions of Universally Stable, Greedy, Contention-
Resolution Protocols," in Proceedings of the 16th International
Symposium on DIStributed Computing, LNCS 2508, pp. 88-102,
October 2002.
[12] D. Koukopoulos, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "The
Impact of Network Structure on the Stability of Greedy Protocols," in
Proceedings of the 5th Italian Conference on Algorithms and
Complexity, LNCS 2653, pp. 251-263, May 2003. Also, accepted in the
Journal Theory of Computing Systems.
[13] D. Koukopoulos, S. Nikoletseas and P. Spirakis, "Stability Issues in
Heterogeneous and FIFO Networks under the Adversarial Queueing
Model," in Proceedings of the 8th International Conference on High
Performance Computing, LNCS 2228, pp. 3-14, Dec. 2001. Invited
Keynote Address.
[14] D. Koukopoulos, M. Mavronicolas and P. Spirakis, "Instability of
Networks with Quasi-Static Link Capacities," in Proceedings of the 10th
International Colloquium on Structural Information and
Communication Complexity, pp. 179-194, June 2003.
[15] P. Tsaparas, "Stability in Adversarial Queueing Theory," M.Sc.Thesis,
Computer Science Department, University of Toronto, 1997.