پایداری شبکه های FIFO تحت مدل های مخالف: حالت هنر

Network stability is an important issue that has attracted the attention of many researchers in recent years. Such interest comes from the need to ensure that, as the system runs for an arbitrarily length of time, no server will suffer an unbounded queue buildup. Over the last few years, much research has been carried out to gain an understanding of the factors that affect the stability of packet-switched networks. In this paper, we attempt to review the most noteworthy results in this area. We will focus on networks where the scheduling policy is of the FIFO type, which is, by far, the most widely adopted policy. We gather these results and present them in an organized manner. Furthermore, we also identify some directions open to future research.

A growing number of networking applications today have constraints in terms of their maximum allowable end-to-end delay, packet loss rate, bandwidth, availability, and so forth. Therefore, it is becoming increasingly important to find out the conditions under which a given communication network guarantees performance bounds when dealing with emerging real-time-oriented networking scenarios. In spite of the significant advances in the complexity of communication networks, much work still needs to be done in that direction. In order to characterize the performance of a network, one crucial issue is that of stability, which has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. The importance of such an issue is obvious, since if one cannot guarantee stability, then one cannot hope to be able to ensure deterministic guarantees for most of the network performance metrics. In a paper dating back to 1975 [1], Kelly proved that in stochastic networks where packet sizes and packet inter-arrival times are exponentially distributed, if the service time at servers follows the same distribution then the well-known scheduling policy FIFO (which is by far the most widely adopted policy) is stable. After that and for many years, the common belief was that only overloaded queues1 could generate instability, while underloaded ones could only induce delays that are longer than desired, but always remain stable. This general wisdom goes back to the models of packet-switching networks originally developed by Kleinrock [2], and based on Jackson queuing networks [3]. Stability results for more general classes of queueing networks [4] and [5] also confirmed that only overload generates instability. This belief was shown to be wrong when it was observed that, in some networks, the backlogs in specific queues could grow indefinitely even when such queues were not overloaded [6] and [7]. It was later observed that instability could also occur, even when the ratio between arrival rate and service rate is arbitrarily small, under the FIFO scheduling policy, both by using probabilistic assumptions [8] and [9] and by considering deterministic ones [10]. However, the above mentioned counterexamples required that the time needed to process a packet be different from one to another. Clearly, this is not, in general, a valid assumption in packet-switched networks, where servers generally have the same service rates for all packets (such networks are usually said to be of the Kelly type[5]). Nevertheless, shortly afterwards it was shown that instability could also arise in some types of Kelly networks, including networks using the FIFO scheduling policy [11] and [12]. These later results aroused an interest in understanding the stability properties of packet-switched networks. This paper provides a review and synthesis of the most important results concerning stability of networks using the FIFO scheduling policy, which have usually appeared in a continuous but dispersed form. Here, we bring these results together and present them in an organized manner. Furthermore, throughout this survey we also identify a number of directions open to future research. The paper has two clearly differentiated parts. In the first, which comprises Sections 2, 3 and 4, we talk about network stability and discuss the different dimensions from which stability can be investigated. We also characterize the model of input traffic we will use and formally define what we mean by stability in that model. In the second part, which comprises Sections 5, 6 and 7, we review the state of the art concerning stability in networks with a FIFO scheduling policy, and present the results obtained when considering several different points of view; whereas in Section 5 we present some instability results, in Section 6 we present the most relevant directions used to approach stability and in Section 7 we tackle the problem of deciding which networks are stable. We finish with some concluding remarks in Section 8. In order to keep a historical perspective of the results, in each reference we include the first version of the paper (mostly conference versions) as well as the final one (mostly journal papers).

Undoubtedly, network stability is an important issue that, in recent years, has attracted the attention of many researchers. Such interest comes from the need to ensure that, as the system runs for an arbitrary length of time, no server will suffer an unbounded queue buildup. In this survey, we have presented, in a structured manner, the recent advances concerning the stability of FIFO in packet-switched networks. Furthermore, we have also identified some directions open to future research. Although the results obtained are mainly theoretical, they have contributed to form a core of fundamental results, and it is a matter of time before such results will be taken into account for more practical issues, such as the design of network protocols, the analysis of multiprocessor systems, and so forth. The current state of the art regarding the stability of FIFO constitutes a first step toward the development of a more mature theory of stability. We think that in the next few years many more new results will appear, especially in the form of identifying situations where FIFO is stable (e.g., new forms of injection rates, networks structures, etc.), together with work carried out on devising techniques for guaranteeing stability.