Revision #1 Authors: Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

Accepted on: 8th April 2003 00:00

Downloads: 1461

Keywords:

We prove that

the {\sf FIFO} ({\it First-In-First-Out}) protocol

is {\em unstable}

in the standard model

of {\em Adversarial Queueing Theory}~\cite{BKRSW01}

for arbitrarily low rates of packet injection.

In order to prove this,

we

proceed as follows:

\begin{enumerate}

\item[{\it (1)}]

We first consider the extension of the standard model to networks

with {\em dynamic capacities,} which was introduced

in~\cite{BOR01}. We assume that each network link may arbitrarily

take on a value in the two-valued integer set $\{1,C\}$ where

$C>4$ is an integer parameter (the {\em high} capacity). Here, for

any $r>0$, we construct a {\sf FIFO} network (whose size is a

small polynomial in $\frac{1}{r}$) which is unstable at any rate

at least $r$ in this setting.

\item[{\it (2)}]

Then, we show how to {\em simulate} the construction in {\it (1)}

in order to produce a {\sf FIFO} network with all link capacities

being now equal to $C$, which is also unstable at any rate at

least $r$ in this setting.

\item[{\it (3)}]

Finally, we provide a simple simulation of the construction in

{\it (2)} in order to produce a {\sf FIFO} network (whose size is

still a small polynomial in $\frac{1}{r}$) with all capacities

being now equal to $1$, which is similarly unstable. Since all

capacities are equal to $1$ in the standard model of Adversarial

Queueing Theory~\cite{BKRSW01}, this implies our main result: {\sf

FIFO} is unstable in the standard model of Adversarial Queueing

Theory model for arbitrarily low rates of packet injection.

\end{enumerate}

We emphasize

that all of our networks

are {\em planar};

we allow though

the paths of packets

to

have cycles of edges

that can be

repeated a {\em bounded}

number of times.

Our result closes a major open problem, that of {\sf FIFO}

(in)stability, in the standard model of Adversarial Queueing

Theory, which was already posed in the original pioneering work of

Borodin {\em et al.}~\cite{BKRSW01}.

TR03-016 Authors: Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

Publication: 24th March 2003 17:26

Downloads: 1217

Keywords:

In this work, we study the stability of the {\sf FIFO} ({\sf

First-In-First-Out}) protocol in the context of Adversarial

Queueing Theory. As an important intermediate step, we consider

{\em dynamic capacities}, where each network link capacity may

arbitrarily take on values in the two-valued set of integers

$\{1,C\}$ for $C>1$ being the {\em high capacity} (a parameter).

In this context:

\begin{itemize}

\item[(1)] We construct a {\sf FIFO} network

of only eight nodes which is already unstable at rate $r=0.41$.

This is the current record for instability of {\sf FIFO} over

networks of fixed-size (independent of $r$).

\item[(2)] For every $r>0$ we then

construct a {\sf FIFO} network

(whose size increases with $\frac{1}{r}$)

which is unstable at

rate $r$.

\end{itemize}

Subsequently, we show how to simulate the particular {\sf FIFO}

network in (2) above with dynamic capacities $1$, $C$, in order to

produce a {\sf FIFO} network with all link capacities being equal,

while preserving instability thresholds. Hence, we eventually show

our main result: {\sf FIFO} can become unstable in the usual model

of {\em unit capacities} links, for arbitrarily low packet

injection rates. This closes a major open problem (the question of

{\sf FIFO} stability) in the field of Adversarial Queueing Theory

posed in the pioneering work of Borodin {\em et al.}~\cite{BKRSW01}.