Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-099 | 1st October 2001 00:00

The Range of Stability for Heterogeneous and FIFO Queueing Networks


Authors: Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis
Publication: 13th December 2001 17:02
Downloads: 2780


In this paper, we investigate and analyze for the first time 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 \geq
0.749$, improving significantly the previous best known bounds of
\cite{2,10}, by using new techniques for adversary construction
and tight analysis of the packet flow time evolution.

ISSN 1433-8092 | Imprint