بی ثباتی FIFO در شبکه های جلسه گرا

We show that the First-In-First-Out (FIFO) scheduling discipline can be unstable in the (σ,ρ)-regulated session model for packet-switched networks. In this model packets are injected into the network in fixed sessions. The total size of the session-i packets injected during the time interval [x,y) is at most σi+ρi(y−x) for some burst parameter σi and rate ρi. The sum of the rates of sessions passing through a server is at most the server speed. Previous work on FIFO stability either allowed for dynamically changing session paths or else assumed that session-i packets are injected at a constant rate. Our result shows that FIFO can be unstable for static paths as long as the injections into a session can be temporarily suspended.

First-In-First-Out (FIFO) is the simplest of all queueing disciplines. Indeed, its simplicity means that it is widely used to provide best-effort service in packet-switched networks. Hence, in order to characterize the performance of many networks it is important to understand the performance of FIFO. One crucial issue is that of stability. Under what conditions is there a bound on the total size of packets in the network? Equivalently, under what conditions can we provide a bound on the delay suffered by packets in the network? In this paper we show that FIFO can be unstable in the (σ, ρ)-regulated session model. This model was proposed by Cruz [8,9] and is one of the most commonly studied models in the networking literature (e.g., [2,7–9,12,15,16,19,21,22,25,27,28]). We now describe the model and contrast it with other network models that have been defined. In particular, we show how it differs from the adversarial queueing model [3] for which FIFO stability was analyzed in [1].

We have shown that FIFO can be unstable in the (σ, ρ)-regulated session model.A number of open problems remain. Since 1 − 3 × 10−9 is so close to 1, it would be interesting to find an example of FIFO instability with a smaller network load. Indeed, it is known that for non-Kelly networks, FIFO can be unstable for arbitrarily small network loads. Is the same true for Kelly networks or is there some r > 0 such that for ρG
r, FIFO is stable? More generally, given a network and a set of sessions, is there a succinct set of conditions that determine whether or not FIFO is stable?