Analysis of the increase and decrease algorithms for congestion avoidance in computer networks

Published on Jun 10, 1989in Computer Networks and Isdn Systems
· DOI :10.1016/0169-7552(89)90019-6
Dah Ming Chiu37
Estimated H-index: 37
Raj Jain65
Estimated H-index: 65
Congestion avoidance mechanisms allow a network to operate in the optimal region of low delay and high throughput, thereby, preventing the network from becoming congested. This is different from the traditional congestion control mechanisms that allow the network to recover from the congested state of high delay and low throughput. Both con- gestion avoidance and congestion control mechanisms are basi- cally resource management problems. They can be formulated as system control problems in which the system senses its state and feeds this back to its users who adjust their controls. The key component of any congestion avoidance scheme is the algorithm (or control function) used by the users to in- crease or decrease their load (window or rate). We abstractly characterize a wide class of such increase/decreas e algorithms and compare them using several different performance metrics. They key metrics are efficiency, fairness, convergence time, and size of oscillations. It is shown that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for con- vergence to an efficient and fair state regardless of the starting state of the network. This is the algorithm finally chosen for implementation in the congestion avoidance scheme recom- mended for Digital Networking Architecture and OSI Trans- port Class 4 Networks.
📖 Papers frequently viewed together
3 Authors (Mark Allman, ..., W. Stevens)
1,934 Citations
4 Authors (Matt Mathis, ..., A. Romanow)
1,505 Citations
1997SIGCOMM: ACM Special Interest Group on Data Communication
4 Authors (Matt Mathis, ..., Teunis Ott)
1,371 Citations
#1Raj JainH-Index: 65
Last. Dah Ming ChiuH-Index: 37
view all 3 authors...
Widespread use of computer networks and the use of varied technology for the interconnection of computers has made congestion a signi cant problem. In this report, we summarize our research on congestion avoidance. We compare the concept of congestion avoidance with that of congestion control. Brie y, congestion control is a recovery mechanism, while congestion avoidance is a prevention mechanism. A congestion control scheme helps the network to recover from the congestion state while a congesti...
157 Citations
Aug 1, 1988 in SIGCOMM (ACM Special Interest Group on Data Communication)
#2Raj JainH-Index: 65
We propose a scheme for congestion avoidance in networks using a connectionless protocol at the network layer. The scheme uses feedback from the network to the users of the network. The interesting challenge for the scheme is to use a minimal amount of feedback (one bit in each packet) from the network to adjust the amount of traffic allowed into the network. The servers in the network detect congestion and set a congestion indication bit on packets flowing in the forward direction. The congesti...
265 CitationsSource
#1Raj JainH-Index: 65
The authors compare the concept of congestion with that of flow control and congestion control. A number of possible alternatives for congestion avoidance are identified. From these a few are selected for study. The criteria for selection and goals for these schemes are described. In particular, the authors wanted the scheme to be globally efficient, fair, dynamic, convergent, robust, distributed, configuration-independent, etc. They model the network and the user policies for congestion avoidan...
151 CitationsSource
Jan 1, 1986 in ICDCS (International Conference on Distributed Computing Systems)
#1Beverly A. SandersH-Index: 1
7 Citations
#1Eli Gafni (UCLA: University of California, Los Angeles)H-Index: 37
We consider a distributed iterative algorithm for dynamically adjusting the input rate of each session of a voice or data network using virtual circuits so as to exercise flow control. Each session origin periodically receives information regarding the level of congestion along the session path and iteratively corrects its input rate. In this paper we place emphasis on voice networks, but the ideas involved are also relevant for dynamic flow control in data networks. The algorithm provides for t...
74 CitationsSource
#1Jeannine MoselyH-Index: 1
Abstract : This document considers algorithms for flow control in computer networks with fixed routing. The goal is to establish input rates, for each source-destination pair, that satisfy a particular fairness criterion. Described are several algorithms in which the input rates are calculated based on controls established by the links of the network. These controls are updated iteratively, using feedback information from the network. It is shown that the rates thus calculated converge to the de...
35 Citations
#1Dimitri P. Bertsekas (MIT: Massachusetts Institute of Technology)H-Index: 97
We present an algorithmic model for distributed computation of fixed points whereby several processors participate simultaneously in the calculations while exchanging information via communication links. We place essentially no assumptions on the ordering of computation and communication between processors thereby allowing for completely uncoordinated execution. We provide a general convergence theorem for algorithms of this type, and demonstrate its applicability to several classes of problems ...
179 CitationsSource
Thesis (Elec.E.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1981.
43 Citations
The problem of optimally choosing message rates for users of a store-and-forward network is analyzed. Multiple users sharing the links of the network each attempt to adjust their message rates to achieve an ideal network operating point or an "ideal tradeoff point between high throughput and low delay." Each user has a fixed path or virtual circuit. In this environment, a basic definition of "ideal delay-throughput tradeoff" is given and motivated. This definition concentrates on a fair allocati...
425 CitationsSource
Cited By1722
Last. Rijwan KhanH-Index: 4
view all 3 authors...
#1Martin J. Tunnicliffe (KUL: Kingston University)H-Index: 6
#2Gordon Hunter (KUL: Kingston University)H-Index: 9
Abstract We investigate the predictive capability of mathematical models of the type-token relationship applied to the vocabulary growth profiles of selected of English language documents. We compare the existing Good-Toulmin and Heaps formulae with an alternative approach based on Bernoulli trial word selection from a fixed finite vocabulary using the Zipf and Zipf-Mandelbrot probability distributions. We make two major observations: firstly, while the Zipf-Mandelbrot model makes better predict...
#1Giannis Fikioris (Cornell University)
#2Rachit Agarwal (Cornell University)H-Index: 17
Last. Éva Tardos (Cornell University)H-Index: 75
view all 3 authors...
Every computer system -- from schedulers in public clouds (Amazon, Google, etc.) to computer networks to hypervisors to operating systems -- performs resource allocation across system users. The defacto allocation policy used in most of these systems, max-min fairness, guarantees desirable properties like incentive compatibility and Pareto efficiency, assuming user demands are time-independent. However, in modern real-world production systems, user demands are dynamic, i.e., vary over time. As a...
Last. Seán McLoone ('QUB': Queen's University Belfast)H-Index: 27
view all 3 authors...
We consider the problem of simultaneous scheduling and resource allocation of an incoming flow of requests to a set of computing units. By representing each computing unit as a node, we model the overall system as a multi-queue scheme. Inspired by congestion control approaches in communication networks, we propose an AIMD-like (additive increase multiplicative decrease) admission control policy that is stable irrespective of the total number of nodes and AIMD parameters. The admission policy all...
#1Yukimasa Nagai (Mitsubishi Electric)H-Index: 5
#2Jianlin Guo (Mitsubishi Electric Research Laboratories)H-Index: 6
Last. Hiroshi Mineno (Shizuoka University)H-Index: 11
view all 6 authors...
Motivated by the explosion of the Internet of Things (IoT), we examined Sub-1 GHz (frequencies below 1 GHz) band wireless technologies that are essential to enable various IoT applications. IEEE 802.15.4g and IEEE 802.11ah are two wireless technologies developed for outdoor IoT applications such as smart utility, smart city and infrastructure monitoring for which both technologies operate in Sub-1 GHz Bands. Our coexistence simulation of IEEE 802.15.4g and IEEE 802.11ah using standard defined co...
#1Konstantinos Tsiknas (DUTH: Democritus University of Thrace)H-Index: 3
#2Paraskevas I. Aidinidis (DUTH: Democritus University of Thrace)
Last. Kyriakos E. Zoiros (DUTH: Democritus University of Thrace)H-Index: 24
view all 3 authors...
In recent years, cloud data centers have received increased attention by the research community, due to their key function of hosting a big number of cloud applications and services. At the same time, however, various and conflicting requirements have emerged, such as a mixture of different type of flows in shallow buffer switches, which are interconnected via fiber optics in many-to-one network topology. In this environment, the conventional transmission control protocol (TCP) exhibits severe p...
#2Behrouz Zadmehr (AUT: Amirkabir University of Technology)
Last. Mohammad Shokouhifar (Shahid Beheshti University)H-Index: 11
view all 5 authors...
Aug 9, 2021 in SIGCOMM (ACM Special Interest Group on Data Communication)
#1Venkat Arun (MIT: Massachusetts Institute of Technology)H-Index: 5
#2Mina Tahmasbi Arashloo (Cornell University)H-Index: 4
Last. Hari Balakrishnan (MIT: Massachusetts Institute of Technology)H-Index: 120
view all 5 authors...
The diversity of paths on the Internet makes it difficult for designers and operators to confidently deploy new congestion control algorithms (CCAs) without extensive real-world experiments, but such capabilities are not available to most of the networking community. And even when they are available, understanding why a CCA underperforms by trawling through massive amounts of statistical data from network connections is challenging. The history of congestion control is replete with many examples...
#1Konstantinos Tsiknas (DUTH: Democritus University of Thrace)H-Index: 3
#2Paraskevas I. Aidinidis (DUTH: Democritus University of Thrace)
Last. Kyriakos E. Zoiros (DUTH: Democritus University of Thrace)H-Index: 24
view all 3 authors...
Data center networks (DCNs) hold a key role in information industry as the infrastructure for hosting cloud data services and related applications. The increasing number of customers using cloud services sets, however, new challenges for the efficient management of the DCN traffic handled by the transport protocols. TCP is adapted as the main transport control protocol in DCNs, but the standard congestion control algorithm it employs has been found to be very inefficient in providing a fair shar...
#1Michal Barcis (AAU: Alpen-Adria-Universität Klagenfurt)H-Index: 2
#2Hermann Hellwagner (AAU: Alpen-Adria-Universität Klagenfurt)H-Index: 33