The miniworkshop on "Internet congestion control" will be devoted to congestion control in large-scale networks and the nature of Internet congestion. Explicit Congestion Notification, becoming available in the Internet, has provided a substantial impetus to work on congestion control, and exciting progress has been made recently towards a theoretical understanding of TCP, both of its equilibrium, using optimization theory, and its dynamics, using control theory. In parallel there has been important progress on mathematical models that address the statistical relationship between traffic, capacity, routing and realized performance.
The mechanisms for regulating traffic on the internet constitute one of the largest automatic control systems yet developed. Key features of this control problem are its necessarily decentralized nature and the fact that feedback from the network about congestion is subject to appreciable delay (both due to the finite speed of light). This talk will present techniques for analysing the stability of this and similar systems, and also modifications of the usual algorithms which can guarantee the robust stability of a network with arbitrary topology and heterogenous round trip times.
References:
G. Vinnicombe
On the Stability of End-to-End Congestion Control for the Internet.
Recent advances in the modeling of network congestion control systems have highlighted the importance of dynamic effects. In particular, many empirically observed oscillations can be traced to instability, and appear even at the level of averaged flow quantities. Designing a stable alternative is non-trivial due to the decentralized nature of the information, and the dependence on unknown network parameters.
In this talk we describe a congestion control system which is arbitrarily scalable, in the sense that its stability is maintained for arbitrary network topologies and arbitrary amounts of delay. Such a system can be implemented in a decentralized way with information currently available in networks plus a small amount of additional signaling.
References:
F. Paganini, J. Doyle, S. Low
Scalable Laws for Stable Network Congestion Control.
In TCP, packet loss is used by the source of a TCP flow to gauge congestion and to adapt the congestion window to the level of congestion in the network. In RED, this mechanism is used by routers to signal, by preemptively dropping packets, congestion to the sources.
ECN (Explicit Congestion Notification, see RFC 3168, Floyd and Ramakrishnan, Sept 2001) replaces ``dropping'' with ``marking'' as the signalling mechanism. The most obvious advantage is that marked packets do not need to be re-transmitted. Derived advantages are that the marking rate can be arbitralily large, and thus that the amount of information ``signalled'' can be much greater.
This allows for jointly designing new router- and source behaviors.
The most likely payoff of such a joint design is to make it possible for `best effort' type traffic to efficiently utilize the bandwidth left unused by higher priority (say VoIP, Video) traffic, even if the bandwidth available to the best effort traffic varies considerably. (Either because the higher priority traffic varies, or because the total bandwidth varies, e.g. as in a fading microwave channel.)
A mathematical model that illustrates the kind of investigation required will be presented, and simulation results will be presented that show that even with a fairly naive approach it is possible to improve QoS to low priority traffic, without doing damage to higher priority traffic.
References:
T.J Ott, J.H.B. Kemperman and M. Mathis
The stationary behaviour of ideal TCP congestion avoidance
T.J. Ott ECN
protocols and the TCP paradigm
A. Misra and T.J. Ott
Jointly coordinating ECN and TCP for rapid adaptation to varying bandwidth
The aim of this talk is to analyze the performance of a large number of long lived TCP controlled flows sharing many routers, from the knowledge of the network parameters (capacity, buffer size, topology) and of the characteristics of each TCP flow (RTT, route etc.). This work is based on the AIMD model which describes the joint evolution of the window sizes of all flows in the congestion avoidance phase over a single bottleneck router, in function of the synchronization rate. It is shown that the generalization of this dynamics to a network composed of several routers can be described geometrically as a billiards in the Euclidean space with as many dimensions as the number of flow classes and as many reflection facets as there are routers. This can first be used as a simulation tool allowing us to emulate the interaction of millions of flows on tens of thousands of routers. This representation also leads to several results of mathematical nature, including a general periodicity theorem for the asymptotic behavior of the interacting flows and a new way of assessing TCP's fairness, which is exemplified on a few typical cases of small dimension. Finally, we also show that aggregated traffic generated by this billiards representation exhibits the same short time scale statistical properties as those observed on real traces.
References:
Francois Baccelli & Dohy Hong
We interpret TCP/AQM as carrying out a distributed primal-dual algorithm over the Internet to maximize aggregate source utility. Different protocols correspond to different optimization algorithms to solve the same prototype problem with different utility functions, and we derive these utility functions explicitly. It illustrates why the current protocol fills, rather than empties the queues, subjecting mice to unnecessary loss and delay. We describe a linear model to study the dynamics of TCP/RED around the equilibrium. It suggests that the TCP/RED will become unstable as delay increases, or more strikingly, as network capacity increases.
References:
S. Low
A Duality Model of TCP and Queue Management Algorithms
S. Low, F. Paganini, J. Wang, S. Adlakha and J. Doyle
Dynamics of TCP/RED and a Scalable Control
A first-order discrete-time dynamic model for a simplified TCP network with RED control is introduced and its nonlinear dynamical behavior is analyzed. The results are used to consider automatic parameter tuning to improve dynamical behavior during congestion. It is argued that for this discrete time normalized feedback system, two controller parameters as opposed to three are enough to completely classify the dynamical behavior of the system. This system is used to analyze the operating point of TCP-RED and its stability with respect to various controller and system parameters. The existence of both typical (period doubling) and atypical (border collision) bifurcations with respect to certain parameters is demonstrated. An explicit stability condition in terms of system parameters is given and its implication for the dynamics of a network is discussed. Finally, a simple real time control algorithm is proposed for delaying the instability in the system and rendering the system stable. With the help of bifurcation diagrams it is demonstrated that the interaction between a RED gateway and TCP Reno connections can lead to chaotic behavior if the parameters are improperly selected. The analysis is validated through simulation.
References:
Priya Ranjan and Eyad H. Abed
Nonlinear Instabilities in TCP-RED
Congestion controllers for the Internet can be viewed as algorithms to solve a problem of resource allocation among competing users. The resource allocation problem is a convex program, which we solve using an exact penalty function approach. In an exact penalty function approach, the system solves a constrained optimization problem using penalty functions; however, by appropriate choice of penalty functions, the solution to the penalty formulation coincides exactly with the solution to the original convex program even when the penalty is not infinite. This is achieved by tuning the parameters of the penalty functions so that they converge to the Lagrange multipliers associated with the constraints in the convex program. We will show that such an approach naturally suggests a robust active queue management scheme at the routers which we call the Adaptive Virtual Queue (AVQ). Under the AVQ scheme, each router maintains a virtual queue whose capacity is adapted to reach a desired utilization.
References:
S. Kunniyur and R. Srikant.
A time-scale
decomposition approach to adaptive ECN marking.
S. Kunniyur and R. Srikant.
Analysis and Design of an Adaptive Virtual Queue Algorithm for Active Queue Management
Congestion control algorithms are difficult to analyze or simulate on a large scale, i.e., when there are large numbers of nodes, links and sources in a network. The reasons for this include the complexity of the actual implementation of the algorithm and the randomness introduced in the packet arrival and service processes due to many factors such as arrivals and departures of sources and uncontrollable short flows in the network. To make the analysis or simulation tractable, often deterministic fluid approximations of these algorithms are used. These approximations are in the form of either deterministic delay differential equations, or more generally, deterministic functional differential equations (FDEs). In this talk, we will justify the use of deterministic models for proportionally-fair congestion controllers under a limiting regime where the number of flows in a network is large. We will also present some examples of design rules that can be obtained from such models.
References:
S. Shakkottai and R. Srikant.
Mean FDE models of Internet Congestion Control.
I'll describe the design of OverQoS and the algorithms it employs. OverQoS provides a range of end-to-end QoS guarantees without requiring QoS mechanisms in all IP routers on network paths, unlike all other QoS proposals. It is therefore incrementally deployable and empowers both ISPs and third-party providers to deploy and experiment with innovative QoS models in the Internet. The key idea that enables this is a "controlled loss virtual link" (CLVL) abstraction provided to the overlay traffic on the network path connecting two OverQoS routers. The CLVL abstraction guarantees that the loss rate for the overlay traffic on the corresponding network path will almost never exceed a pre-specified target loss rate, regardless of the nature of other traffic sharing portions of this path. I'll describe an algorithm to implement CLVL using forward error correction, and show some results that indicate that OverQoS might be a useful architecture for the future.
Joint work with I. Stoica and L. Subramanian
In this talk we describe a number of issues related with implementing congestion control schemes. First we describe the theoretical tradeoffs between a rate based and a buffer based scheme. We show that network parameters have diametrically opposite effects on the performance of the mechanisms in the two cases. Next, we describe ongoing efforts in implementing a buffer based congestion control scheme, the PI controller, in real systems. The controller is being implemented by two major router vendors, and we discuss the design limitations we face with hardware implementations. We also describe the implementation and experimentation of the controller on a software router/testbed.
We consider unicast equation based rate control defined as follows. A source adjusts its rate primarily at loss events to f(p) where p is an estimator of loss event ratio. Function f is typically the loss-throughput formula of a TCP source. In absence of loss events, the send rate can be also increased by an additional mechanism. We suppose the estimator is unbiased estimator of the loss event interval (amount of data sent between two consecutive loss events). Indeed, for the loss event intervals fixed to some value, the throughput x satisfies x=f(p). However, if loss process is random, it is not clear how the throughput would relate to f(p). If x<=f(p), we say the control is conservative. We derive a representation of the throughput, and obtain that conservativeness is primarily due to various convexity properties of function f, and variability and correlation structure of the loss process. In many cases, these factors drive the control to be conservative, but we also show some reasonable cases of non-conservative control. However, having observed that our source should experience larger long-run loss event ratio than TCP would, non TCP-friendliness becomes less likely. In our study we do not consider the effects involved due to randomness of the round-trip time.
References:
M. Vojnovic and J.-Y. Le Boudec On
the Long-Run Behavior of Equation-Based Rate Control
M. Vojnovic and J.-Y. Le Boudec Some
Observations on Equation-Based Rate Control
Much current research into Internet congestion control has focussed on so-called elastic traffic, which can adapt its sending rate arbitrarily, and which is also insensitive to latency. For many applications, one or both of these assumptions may be violated. For example, streaming media requires a minimum rate (goodput) to give an acceptable user experience, while real-time interactive applications are sensitive to delay. An interesting question is to what extent service differentiation is possible without partitioning the network in a hard or soft manner. Stimulated by talk of web mice and elephants, we consider how to share bandwidth between transient flows, and long-lived or persistent flows. Informally, transient flows are those which have a fixed volume of data to transfer, while persistent or long-lived flows either persist or last for a fixed-time independent of their sending rate. By considering an associated optimisation problem, we show that for this scenario it is possible to find a decentralised solution, which requires minimal network support. In effect, this implements a form of weighted processor sharing, and that can approximate the shortest-remaining processing time discipline. We then look more closely at certain specific types of long-lived flows, and consider applications which can only switch between a fixed number of sending-rates, and must send above some minimum rate. They adapt their rate by occasionally measuring or probing the network. For these applications, by appealing to limiting functional central limit results, we show that for moderately sized networks minimal probing is needed and hence minimal change of rate by the application. Questions of fairness with elastic traffic are handled by adaptation and by the application occasionally not entering the network, rather than by mimicking the behaviour of elastic traffic.
References:
S. Deb, A. J. Ganesh and P. B. Key Resource
Allocation with Persistent and Transient Flows
MSR Technical Report, MSR-TR-2001-114.
Revised version to appear in Networking 2002.
Alan Bain and P. B. Key
Modelling the Performance of Distributed Admission Control for Adaptive Applications
MAMA Workshop, June 2001, Performance Evaluation Review.
Peter Key and Laurent Massoulié
User policies in a network implementing congestion pricing
Workshop on Internet Service Quality Economics (ISQE), December 1999.
Understanding the three-way statistical relationship between traffic, capacity and realized performance is vital not only for adequately provisioning IP network resources to satisfy anticipated demand but also for defining the service model and congestion control mechanisms that determine how those resources are shared. In expressing demand it is particularly important to know what set of traffic characteristics has a significant impact on performance and needs therefore to be monitored and controlled. This set clearly depends on the adopted network architecture: defined service classes, scheduling mechanisms, admission controls, traffic routing algorithms,... We argue that an essential criterion in designing the network architecture is that the resulting traffic-capacity-performance relationship be as simple as possible. In other words, resource sharing schemes should be such that performance is largely insensitive to detailed traffic characteristics. This in not true, for example, of schemes relying on significant buffering in the network to smooth out momentary rate overloads since delays can vary widely depending on the correlation structure of the packet arrival process (particularly when the latter is long range dependent). Two resource sharing schemes which do meet the insensitivity criterion are so-called bufferless multiplexing for open-loop controlled streaming traffic and fair bandwidth sharing for closed-loop controlled elastic traffic. We review the powerful insensitivity results available for these multiplexing schemes and suggest that they indeed constitute the preferred basis for a network architecture offering guaranteed quality of service. Necessary congestion control mechanisms are described and their implementation is discussed.
QoS and Traffic Engineering (TE) are central issues in the evolution of the Internet technology, and in its ability to be the convergence technology. To succeed in this challenge, IP will have to support legacy services such as Frame Relay, Voice, and VPN together with classic Internet applications such as email, web, and media streaming. In this presentation, we take the perspective and the experience gained in a tier 1 IP backbone to explain why over-provisioning is the only approach to provide quality of service in the Internet. Alternatives to overprovisioning are discussed. In particular, we explain why MPLS is not needed in a well designed IP network. We show that Classes of Service can be provided in the Internet with simple TE practices and with overprovisioning. Various aspects of a large backbone engineering and operations are taken into consideration to justify our position, in particular resistance to failure, simplicity of management, and costs.
Static optimization models of optimal routing have traditionally focused on a single network manager aiming to minimize total network cost (expressed in terms of delay, loss, or some other congestion measure). Such a framework matched the early stages of the Internet, where growth and management of the network were under the central control of government agencies (albeit in agreements with private network providers).
Today, however, the situation is quite different: the modern Internet is a collection of networks run by competing providers, and connected through contractual arrangements between these providers. As a result, past models of the routing problem are no longer adequate. A framework for today's Internet must consider the conflicting interests of the individual network providers in determining the routing of traffic, as well as the placement of peering points between networks.
In this talk, we will present several simple models to explore the routing and peering problem from the point of view of individual networks, considering in particular the optimal placement of peering points for both sender and receiver.