A Systematic Construction of Instability Bounds in LIS Networks

Authors: Dimitrios Koukopoulos

Abstract:

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, p)-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 p > 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: Parallel computing, network stability, adversarial queuing theory, greedy scheduling protocols.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330505

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, Jan. 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 Proc. 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, Jan. 2001.
[5] E. Anshelevich, D. Kempe and J. Kleinberg, "Stability of Load Balancing Algorithms in Dynamic Adversarial Systems," in Proc. 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 Proc. of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 158-167, Oct. 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, Jan. 2001.
[8] A. Borodin, R. Ostrovsky and Y. Rabani, "Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds," in Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 601-610, Jan. 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 Proc. 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 Proc. of the 16th Int. Symposium on DIStributed Computing, LNCS 2508, pp. 88-102, Oct. 2002.
[12] D. Koukopoulos, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "The Impact of Network Structure on the Stability of Greedy Protocols," in Proc. 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 Proc. of the 8th Int. 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 Proc. 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.