Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31093
An Adversarial Construction of Instability Bounds in LIS Networks

Authors: Dimitrios Koukopoulos


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.

Keywords: quality of service, network stability, greedy scheduling protocols, adversarial queueing theory

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 965


[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.