research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleInstability of Networks with Quasi-Static Link Capacities
Bibtex cite IDRACTI-RU1-2003-15
Booktitle Colloquium on Structural Information and Communication Complexity
Year published 2003
Month August
Volume 381
Number 1-3
Pages 44-56
Publisher Elsevier
DOI 10.1016/j.tcs.2007.04.008
Keywords Adversarial Queuing Theory; Adversarial Quasi-Static Queuing Theory; Network stability; Greedy protocols
In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, where each link capacity may take on only two possible (integer) values, namely 1 and C>1 under a (w,ñ)-adversary. We obtain the following results: • Allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the LIS (Longest-in-System) protocol for contention–resolution results in instability at rates View the MathML source and for large enough values of C. • The combination of dynamically changing link capacities with compositions of contention–resolution protocols on network queues suffices for similar instability bounds: The composition of LIS with any of SIS (Shortest-in-System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) protocols is unstable at rates View the MathML source for large enough values of C. • The instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instability bounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol.
Koukopoulos, Dimitrios
Mavronicolas, Marios
Spirakis, Paul
getPDF.pdf (main file)
Publication ID279