The increase of the instability of networks due to Quasi-Static link capacities
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 (omega,rho)-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 rho > root 2 - 1 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-toSource), and FTG (Furthest-to-Go) protocols is unstable at rates p > root 2 - 1 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. (c) 2007 Elsevier B.V. All rights reserved.
greedy protocols adversarial queuing theory adversarial quasi-static queuing theory network stability