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}.

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}.