ALCOMFT-TR-02-100

Dimitrios Koukopoulos, Sotiris Nikoletseas and Paul Spirakis
Stability Issues in Heterogeneous and FIFO Networks under the Adversarial Queueing Model
Patras. Work package 2. May 2002.

Abstract: In this paper, we investigate and analyze the stability properties of heterogeneous networks, which use a combination of different universally stable queueing policies for packet routing, in the Adversarial Queueing model. We interestingly prove that the combination of SIS and LIS policies, LIS and NTS policies, and LIS and FTG policies leads to instability for specific networks and injection rates that are presented. It is also proved that the combination of SIS and FTG policies, SIS and NTS policies, and FTG and NTS policies is universally stable. Furthermore, we prove that FIFO is non-stable for any r >= 0.749, improving significantly the previous best known bounds of [2,10], by using new techniques for adversary construction and tight analysis of the packet flow time evolution. We also show a graph for which FIFO is stable for any adversary with injection rate r <= 0.1428, and, by generalizing, we present upper bounds for stability of any network under the FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. The work presented here combines new and recent results of the authors.

Postscript file: ALCOMFT-TR-02-100.ps.gz (109 kb).