ALCOMFT-TR-03-135

Dimitrios Koukopoulos, Marios Mavronicolas and Paul Spirakis
Instability of Networks with Quasi-Static Link Capacities
Patras and Cyprus. Work packages 2 and 4. December 2003.

Abstract: A packet-switched network is stable if the number of

packets in the network remains

bounded at all times. A very

natural question that arises in the context of stability

properties of such networks is how the dynamical change of network

link capacities precisely affects these properties.

In this work, we embark on a systematic study of this question

adopting the Adversarial Queueing Theory framework, where an

adversary controls rates of packet injections and determines

packet paths. In addition, the power of the adversary is enhanced

to include manipulation of link capacities. However, in

doing so, the adversary may use only two possible (integer)

values, namely 1 and C>1; moreover, the capacity changes are not

abrupt: once a link capacity is set to a value, it maintains this

value for a period of time proportional to the number of packets

in the system at the time of setting the link capacity to the

value. We call this the Adversarial, Quasi-Static Queueing

Theory model.

Within this model, we obtain a comprehensive collection of

results in the form of instability bounds on injection rate of the

adversary for various greedy protocols:

• Allowing the dynamical changing of link capacities of a network

  that uses LIS ( Longest-in-System) protocol for

  contention-resolution may result in dropping its instability

  bound. This is shown through a construction of an LIS

  network of just ten nodes which becomes unstable at rates \rho > \sqrt{2}-1 for large enough values of C. This represents the

  current record for the instability bound on the injection rate of

  the adversary for LIS over models of Adversarial Queueing

  Theory with dynamic capacities.

• The combination of dynamically changing link capacities

  with the use of compositions of protocols for

  contention-resolution on network queues suffices to drop the

  instability bound of a network to a substantially low value. This

  is shown through novel, yet simple and natural, combinatorial

  constructions of networks on which a composition of greedy

  protocols are running. In particular, we show that 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 \rho > \sqrt{2}-1 for large enough values of C. These represent the

  first results of instability bounds on injection rate for

  compositions of greedy protocols over models of Adversarial

  Queueing Theory with dynamic capacities.

• How much can the instability bound of

  network subgraphs that are forbidden for stability be affected by

  the dynamical changing of link capacities? Through improved

  combinatorial constructions of networks and executions, we present

  instability bounds for all directed subgraphs that are known

  to be forbidden for stability on networks running a certain

  greedy protocol. These bounds are lower than their counterparts

  for the classical Adversarial Queueing Theory model.

Postscript file: ALCOMFT-TR-03-135.ps.gz (290 kb).