Asynchronous distributed rate control algorithms for best-effort sessions in integrated services networks with minimum rate guarantees

Abstract

Packet switching networks provide a best-effort transport service that is typically used by store-and-forward applications, such as email, file transfer, and web browsing. In an Integrated Services Packet Network, the best-effort sessions share the bandwidth that is left over after serving the guaranteed service traffic. Further, this residual bandwidth needs to be shared fairly among the existing best-effort sessions. Since such sessions are controllable, a feedback control is used to modulate the emission of packets from the best-effort sources. In this thesis, we are concerned with the problem of distributed rate control of best-effort sessions. Our motivation comes from the definition of the Available Bit Rate (ABR) service in Asynchronous Transfer Mode (ATM) networks. The problem we deal with has the following features:

An arbitrary network topology with a fixed configuration of best-effort sessions. The sources transmit at a rate governed by explicit rate feedback from the network. The link capacities (or bandwidths) available to the best-effort sessions are stochastically varying. There are rapid small variations and infrequent large variations in the link bandwidth-the former caused by rate variations in guaranteed Variable Bit Rate (VBR) sessions, and the latter by the arrival or departure of large guaranteed service sessions. A form of max-min fairness is enforced between the sessions. Sessions can request a minimum rate (Minimum Cell Rate (MCR) in ABR terminology). The sources intersperse their data cells (packets) with Resource Management (RM) cells, which carry control information between the network and the sources.

We begin by developing a notion of max-min fairness with minimum rate guarantees. This is a natural generalization of the corresponding notion without such rate guarantees. The basic theory for the original concept of max-min fairness is extended, and a centralized algorithm for obtaining max-min fair rates with minimum rate guarantees is developed and proved. Another outcome of this development is a property of the max-min fair allocation that is useful for the development of distributed control algorithms. We show that the max-min fair allocation problem can be formulated as the solution of a certain non-linear vector equation; the equation depends on the network topology, session configuration, and link capacities. In our development of distributed algorithms, we begin by considering a generic synchronous distributed algorithm for the case where the capacity available on the links is fixed. This generic algorithm incorporates autonomous updates at the links, with no explicit communication between the computing nodes. We analytically prove that the rate allocations for the sources computed by this generic algorithm converge to the max-min fair allocation. We also show how two existing algorithms, generalized to incorporate MCRs, are special cases of this generic framework. We then propose two extensions of one of these special cases to operate in an asynchronous environment with feedback delays. We then consider the case of stochastic available link capacities with rapid variations. The “solution-of-equations” perspective enables us to formulate the distributed control problem as the solution of a vector equation given noisy observations. We propose a distributed stochastic approximation algorithm for solving this problem. The algorithm retains the desired structure of autonomous updates without explicit communication between computing nodes. The convergence of session rates to their max-min fair rates is analytically proved using the Ordinary Differential Equation (ODE) method. Until this point in our work, the available link capacity is viewed as a given quantity (in the stochastic case, the capacity is viewed as this given quantity plus noise). Thus, the algorithms are purely rate control algorithms, with no attention paid to buffer occupancies at links or probabilities of buffer overflow. We incorporate this aspect by appropriately defining the available capacity of a link so that if the sources adapt to this rate, the buffer overflow probability remains small. Clearly, the mean of the stochastic link capacity would not suffice, since adapting the total flow of best-effort traffic to the mean available capacity would cause large queue buildups at network nodes. We consider the problem of computing the constant input rate into a queue with a stochastic service rate that ensures a constrained queue buildup. The formulation we use is the dual of the equivalent bandwidth formulation for sources with stochastic sending rates. We propose two online estimation algorithms that estimate this input rate, which we call the equivalent service capacity of the link. Finally, the distributed stochastic algorithm developed is combined with the available capacity estimation technique, and simulations are run to study the overall approach. At this point, some heuristics are developed for adapting to large changes in link capacities (such as those caused by arrivals or departures of guaranteed service sessions). We find that the algorithm tracks the theoretically calculated max-min fair rates. Further, the equivalent service capacity approach succeeds in limiting cell losses while avoiding the arbitrariness of simply using the mean link capacity times a factor such as 0.95.