A Systematic 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, 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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:52650", author = "Dimitrios Koukopoulos", title = "A Systematic Construction of Instability Bounds in LIS Networks", 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.", volume = "1", number = "7", pages = "1952-6", }
