Open Science Research Excellence

Open Science Index

Commenced in January 2007 Frequency: Monthly Edition: International Publications Count: 29527


Select areas to restrict search in scientific publication database:
9398
An Adversarial 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, ¤ü)-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.
Digital Object Identifier (DOI):

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.
Vol:13 No:04 2019Vol:13 No:03 2019Vol:13 No:02 2019Vol:13 No:01 2019
Vol:12 No:12 2018Vol:12 No:11 2018Vol:12 No:10 2018Vol:12 No:09 2018Vol:12 No:08 2018Vol:12 No:07 2018Vol:12 No:06 2018Vol:12 No:05 2018Vol:12 No:04 2018Vol:12 No:03 2018Vol:12 No:02 2018Vol:12 No:01 2018
Vol:11 No:12 2017Vol:11 No:11 2017Vol:11 No:10 2017Vol:11 No:09 2017Vol:11 No:08 2017Vol:11 No:07 2017Vol:11 No:06 2017Vol:11 No:05 2017Vol:11 No:04 2017Vol:11 No:03 2017Vol:11 No:02 2017Vol:11 No:01 2017
Vol:10 No:12 2016Vol:10 No:11 2016Vol:10 No:10 2016Vol:10 No:09 2016Vol:10 No:08 2016Vol:10 No:07 2016Vol:10 No:06 2016Vol:10 No:05 2016Vol:10 No:04 2016Vol:10 No:03 2016Vol:10 No:02 2016Vol:10 No:01 2016
Vol:9 No:12 2015Vol:9 No:11 2015Vol:9 No:10 2015Vol:9 No:09 2015Vol:9 No:08 2015Vol:9 No:07 2015Vol:9 No:06 2015Vol:9 No:05 2015Vol:9 No:04 2015Vol:9 No:03 2015Vol:9 No:02 2015Vol:9 No:01 2015
Vol:8 No:12 2014Vol:8 No:11 2014Vol:8 No:10 2014Vol:8 No:09 2014Vol:8 No:08 2014Vol:8 No:07 2014Vol:8 No:06 2014Vol:8 No:05 2014Vol:8 No:04 2014Vol:8 No:03 2014Vol:8 No:02 2014Vol:8 No:01 2014
Vol:7 No:12 2013Vol:7 No:11 2013Vol:7 No:10 2013Vol:7 No:09 2013Vol:7 No:08 2013Vol:7 No:07 2013Vol:7 No:06 2013Vol:7 No:05 2013Vol:7 No:04 2013Vol:7 No:03 2013Vol:7 No:02 2013Vol:7 No:01 2013
Vol:6 No:12 2012Vol:6 No:11 2012Vol:6 No:10 2012Vol:6 No:09 2012Vol:6 No:08 2012Vol:6 No:07 2012Vol:6 No:06 2012Vol:6 No:05 2012Vol:6 No:04 2012Vol:6 No:03 2012Vol:6 No:02 2012Vol:6 No:01 2012
Vol:5 No:12 2011Vol:5 No:11 2011Vol:5 No:10 2011Vol:5 No:09 2011Vol:5 No:08 2011Vol:5 No:07 2011Vol:5 No:06 2011Vol:5 No:05 2011Vol:5 No:04 2011Vol:5 No:03 2011Vol:5 No:02 2011Vol:5 No:01 2011
Vol:4 No:12 2010Vol:4 No:11 2010Vol:4 No:10 2010Vol:4 No:09 2010Vol:4 No:08 2010Vol:4 No:07 2010Vol:4 No:06 2010Vol:4 No:05 2010Vol:4 No:04 2010Vol:4 No:03 2010Vol:4 No:02 2010Vol:4 No:01 2010
Vol:3 No:12 2009Vol:3 No:11 2009Vol:3 No:10 2009Vol:3 No:09 2009Vol:3 No:08 2009Vol:3 No:07 2009Vol:3 No:06 2009Vol:3 No:05 2009Vol:3 No:04 2009Vol:3 No:03 2009Vol:3 No:02 2009Vol:3 No:01 2009
Vol:2 No:12 2008Vol:2 No:11 2008Vol:2 No:10 2008Vol:2 No:09 2008Vol:2 No:08 2008Vol:2 No:07 2008Vol:2 No:06 2008Vol:2 No:05 2008Vol:2 No:04 2008Vol:2 No:03 2008Vol:2 No:02 2008Vol:2 No:01 2008
Vol:1 No:12 2007Vol:1 No:11 2007Vol:1 No:10 2007Vol:1 No:09 2007Vol:1 No:08 2007Vol:1 No:07 2007Vol:1 No:06 2007Vol:1 No:05 2007Vol:1 No:04 2007Vol:1 No:03 2007Vol:1 No:02 2007Vol:1 No:01 2007