HOME

TheInfoList



OR:

Network congestion in
data networking A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...
and
queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
is the reduced
quality of service Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay,
packet loss Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is either caused by errors in data transmission, typically across wireless networks, or network congestion.Kur ...
or the blocking of new connections. A consequence of congestion is that an incremental increase in offered load leads either only to a small increase or even a decrease in network
throughput Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ove ...
.
Network protocol A communication protocol is a system of rules that allows two or more entities of a communications system to transmit information via any kind of variation of a physical quantity. The protocol defines the rules, syntax, semantics and synchroniza ...
s that use aggressive retransmissions to compensate for packet loss due to congestion can increase congestion, even after the initial load has been reduced to a level that would not normally have induced network congestion. Such networks exhibit two stable states under the same level of load. The stable state with low throughput is known as congestive collapse. Networks use congestion control and congestion avoidance techniques to try to avoid collapse. These include:
exponential backoff Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. These algorithms find usage in a wide range of systems and processes, with radio network ...
in protocols such as
CSMA/CA Carrier-sense multiple access with collision avoidance (CSMA/CA) in computer networking, is a network multiple access method in which carrier sensing is used, but nodes attempt to avoid collisions by beginning transmission only after the channel ...
in
802.11 IEEE 802.11 is part of the IEEE 802 set of local area network (LAN) technical standards, and specifies the set of media access control (MAC) and physical layer (PHY) protocols for implementing wireless local area network (WLAN) computer com ...
and the similar
CSMA/CD Carrier-sense multiple access with collision detection (CSMA/CD) is a medium access control (MAC) method used most notably in early Ethernet technology for local area networking. It uses carrier-sensing to defer transmissions until no other statio ...
in the original
Ethernet Ethernet () is a family of wired computer networking technologies commonly used in local area networks (LAN), metropolitan area networks (MAN) and wide area networks (WAN). It was commercially introduced in 1980 and first standardized in 1 ...
,
window A window is an opening in a wall, door, roof, or vehicle that allows the exchange of light and may also allow the passage of sound and sometimes air. Modern windows are usually glazed or covered in some other transparent or translucent mat ...
reduction in TCP, and fair queueing in devices such as routers and
network switch A network switch (also called switching hub, bridging hub, and, by the IEEE, MAC bridge) is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destination device. A netw ...
es. Other techniques that address congestion include priority schemes which transmit some packets with higher priority ahead of others and the explicit allocation of network resources to specific flows through the use of
admission control Admission control is a validation process in communication systems where a check is performed before a connection is established to see if current resources are sufficient for the proposed connection. Applications For some applications, dedicated ...
.


Network capacity

Network resources are limited, including router processing time and link
throughput Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ove ...
.
Resource contention In computer science, resource contention is a conflict over access to a shared resource such as random access memory, disk storage, cache memory, internal buses or external network devices. A resource experiencing ongoing contention can be des ...
may occur on networks in several common circumstances. A
wireless LAN A wireless LAN (WLAN) is a wireless computer network that links two or more devices using wireless communication to form a local area network (LAN) within a limited area such as a home, school, computer laboratory, campus, or office buildi ...
is easily filled by a single personal computer. Even on fast computer networks, the
backbone The backbone is the vertebral column of a vertebrate. Arts, entertainment, and media Film * ''Backbone'' (1923 film), a 1923 lost silent film starring Alfred Lunt * ''Backbone'' (1975 film), a 1975 Yugoslavian drama directed by Vlatko Gilić ...
can easily be congested by a few servers and client PCs.
Denial-of-service attack In computing, a denial-of-service attack (DoS attack) is a cyber-attack in which the perpetrator seeks to make a machine or network resource unavailable to its intended users by temporarily or indefinitely disrupting services of a host conn ...
s by
botnet A botnet is a group of Internet-connected devices, each of which runs one or more bots. Botnets can be used to perform Distributed Denial-of-Service (DDoS) attacks, steal data, send spam, and allow the attacker to access the device and its conn ...
s are capable of filling even the largest
Internet backbone The Internet backbone may be defined by the principal data routes between large, strategically interconnected computer networks and core routers of the Internet. These data routes are hosted by commercial, government, academic and other high-ca ...
network links, generating large-scale network congestion. In telephone networks, a
mass call event A mass call event or mass calling event (also MCE in telephony usage) is a situation in which an extraordinarily high number of telephone calls are attempted into or out of an area, causing tremendous network congestion, and therefore service which ...
can overwhelm digital telephone circuits.


Congestive collapse

Congestive collapse (or congestion collapse) is the condition in which congestion prevents or limits useful communication. Congestion collapse generally occurs at choke points in the network, where incoming traffic exceeds outgoing bandwidth. Connection points between a
local area network A local area network (LAN) is a computer network that interconnects computers within a limited area such as a residence, school, laboratory, university campus or office building. By contrast, a wide area network (WAN) not only covers a larger ...
and a
wide area network A wide area network (WAN) is a telecommunications network that extends over a large geographic area. Wide area networks are often established with leased telecommunication circuits. Businesses, as well as schools and government entities, u ...
are common choke points. When a network is in this condition, it settles into a stable state where traffic demand is high but little useful throughput is available, during which
packet delay End-to-end delay or one-way delay (OWD) refers to the time taken for a packet to be transmitted across a network from source to destination. It is a common term in IP network monitoring, and differs from round-trip time (RTT) in that only path in t ...
and loss occur and
quality of service Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
is extremely poor. Congestive collapse was identified as a possible problem by 1984. It was first observed on the early Internet in October 1986, when the
NSFNET The National Science Foundation Network (NSFNET) was a program of coordinated, evolving projects sponsored by the National Science Foundation (NSF) from 1985 to 1995 to promote advanced research and education networking in the United States. The p ...
phase-I backbone dropped three orders of magnitude from its capacity of 32 kbit/s to 40 bit/s, which continued until end nodes started implementing
Van Jacobson Van Jacobson (born 1950) is an American computer scientist, renowned for his work on TCP/IP network performance and scaling.
and
Sally Floyd Sally Jean Floyd (May 20, 1950 – August 25, 2019) was an American computer scientist known for her work on computer networking. Formerly associated with the International Computer Science Institute in Berkeley, California, she retired in 2009 a ...
's congestion control between 1987 and 1988. When more packets were sent than could be handled by intermediate routers, the intermediate routers discarded many packets, expecting the end points of the network to retransmit the information. However, early TCP implementations had poor retransmission behavior. When this packet loss occurred, the endpoints sent extra packets that repeated the information lost, doubling the incoming rate.


Congestion control

Congestion control modulates traffic entry into a telecommunications network in order to avoid congestive collapse resulting from oversubscription. This is typically accomplished by reducing the rate of packets. Whereas congestion control prevents senders from overwhelming the ''network'', flow control prevents the sender from overwhelming the ''receiver''.


Theory of congestion control

The theory of congestion control was pioneered by
Frank Kelly Francis Kelly (28 December 1938 – 28 February 2016) was an Irish actor, singer and writer, whose career covered television, radio, theatre, music, screenwriting and film. He is best remembered for playing Father Jack Hackett in the Channel 4 ...
, who applied
microeconomic theory Microeconomics is a branch of mainstream economics that studies the behavior of individuals and firms in making decisions regarding the allocation of scarce resources and the interactions among these individuals and firms. Microeconomics foc ...
and
convex optimization Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization pr ...
theory to describe how individuals controlling their own rates can interact to achieve an ''optimal'' network-wide rate allocation. Examples of ''optimal'' rate allocation are max-min fair allocation and Kelly's suggestion of
proportionally fair Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize total throughput of the network (wired or not) while at the same time allowing all ...
allocation, although many others are possible. Let x_i be the rate of flow i, c_l be the capacity of link l, and r_ be 1 if flow i uses link l and 0 otherwise. Let x, c and R be the corresponding vectors and matrix. Let U(x) be an increasing, strictly concave function, called the
utility As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosoph ...
, which measures how much benefit a user obtains by transmitting at rate x. The optimal rate allocation then satisfies : \max\limits_x \sum_i U(x_i) : such that Rx \le c The Lagrange dual of this problem decouples so that each flow sets its own rate, based only on a ''price'' signaled by the network. Each link capacity imposes a constraint, which gives rise to a
Lagrange multiplier In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied e ...
, p_l. The sum of these multipliers, y_i=\sum_l p_l r_, is the price to which the flow responds. Congestion control then becomes a distributed optimization algorithm. Many current congestion control algorithms can be modelled in this framework, with p_l being either the loss probability or the queueing delay at link l. A major weakness is that it assigns the same price to all flows, while sliding window flow control causes
burstiness In statistics, burstiness is the intermittent increases and decreases in activity or frequency of an event.Lambiotte, R. (2013.) "Burstiness and Spreading on Temporal Networks", University of Namur. One of measures of burstiness is the Fano factorâ ...
that causes different flows to observe different loss or delay at a given link.


Classification of congestion control algorithms

Among the ways to classify congestion control algorithms are: *By type and amount of feedback received from the network: Loss; delay; single-bit or multi-bit explicit signals *By incremental deployability: Only sender needs modification; sender and receiver need modification; only router needs modification; sender, receiver and routers need modification. *By performance aspect: high bandwidth-delay product networks; lossy links; fairness; advantage to short flows; variable-rate links *By fairness criterion: Max-min fairness; proportionally fair;
controlled delay Control may refer to: Basic meanings Economics and business * Control (management), an element of management * Control, an element of management accounting * Comptroller (or controller), a senior financial officer in an organization * Controllin ...


Mitigation

Mechanisms have been invented to prevent network congestion or to deal with a network collapse: *
Network scheduler A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
active queue management In Router (computing), routers and network switch, switches, active queue management (AQM) is the policy of dropping packets inside a buffer associated with a network interface controller (NIC) before that buffer becomes full, often with the goal ...
which reorders or selectively drops network packets in the presence of congestion *
Explicit Congestion Notification Explicit Congestion Notification (ECN) is an extension to the Internet Protocol and to the Transmission Control Protocol and is defined in RFC 3168 (2001). ECN allows end-to-end notification of network congestion without dropping packets. ECN is ...
an extension to IP and TCP communications protocols that adds a flow control mechanism *
TCP congestion control Transmission Control Protocol (TCP) uses a network congestion-avoidance algorithm that includes various aspects of an additive increase/multiplicative decrease (AIMD) scheme, along with other schemes including slow start and congestion windo ...
various implementations of efforts to deal with network congestion The correct endpoint behavior is usually to repeat dropped information, but progressively slow the repetition rate. Provided all endpoints do this, the congestion lifts and the network resumes normal behavior. Other strategies such as slow start ensure that new connections don't overwhelm the router before congestion detection initiates. Common router congestion avoidance mechanisms include fair queuing and other
scheduling algorithms In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows. The scheduling activity is ca ...
, and
random early detection Random early detection (RED), also known as random early discard or random early drop is a queuing discipline for a network scheduler suited for congestion avoidance. In the conventional tail drop algorithm, a router or other network component ...
(RED) where packets are randomly dropped as congestion is detected. This proactively triggers the endpoints to slow transmission before congestion collapse occurs. Some end-to-end protocols are designed to behave well under congested conditions; TCP is a well known example. The first TCP implementations to handle congestion were described in 1984, but Van Jacobson's inclusion of an open source solution in the Berkeley Standard Distribution UNIX (" BSD") in 1988 first provided good behavior. UDP does not control congestion. Protocols built atop UDP must handle congestion independently. Protocols that transmit at a fixed rate, independent of congestion, can be problematic. Real-time streaming protocols, including many
Voice over IP Voice over Internet Protocol (VoIP), also called IP telephony, is a method and group of technologies for the delivery of voice communications and multimedia sessions over Internet Protocol (IP) networks, such as the Internet. The terms Internet t ...
protocols, have this property. Thus, special measures, such as quality of service, must be taken to keep packets from being dropped in the presence of congestion.


Practical network congestion avoidance

Connection-oriented protocols, such as the widely used TCP protocol watch for
packet loss Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is either caused by errors in data transmission, typically across wireless networks, or network congestion.Kur ...
, or
queuing delay In telecommunication and computer engineering, the queuing delay or queueing delay is the time a job waits in a queue until it can be executed. It is a key component of network delay. In a switched network, queuing delay is the time between the c ...
to adjust their transmission rate. Various network congestion avoidance processes support different trade-offs.


TCP/IP congestion avoidance

The
TCP congestion avoidance algorithm Transmission Control Protocol (TCP) uses a network congestion-avoidance algorithm that includes various aspects of an additive increase/multiplicative decrease (AIMD) scheme, along with other schemes including #Slow start, slow start and #Conge ...
is the primary basis for congestion control on the Internet. Problems occur when concurrent TCP flows experience tail-drops, especially when
bufferbloat Bufferbloat is a cause of high latency and jitter in packet-switched networks caused by excess buffering of packets. Bufferbloat can also cause packet delay variation (also known as jitter), as well as reduce the overall network throughput. ...
is present. This delayed packet loss interferes with TCP's automatic congestion avoidance. All flows that experience this packet loss begin a TCP retrain at the same moment – this is called
TCP global synchronization TCP global synchronization in computer networks can happen to TCP/ IP flows during periods of congestion because each sender will reduce their transmission rate at the same time when packet loss occurs. Routers on the Internet normally have packe ...
.


Active queue management

Active queue management In Router (computing), routers and network switch, switches, active queue management (AQM) is the policy of dropping packets inside a buffer associated with a network interface controller (NIC) before that buffer becomes full, often with the goal ...
(AQM) is the reordering or dropping of network packets inside a transmit buffer that is associated with a
network interface controller A network interface controller (NIC, also known as a network interface card, network adapter, LAN adapter or physical network interface, and by similar terms) is a computer hardware component that connects a computer to a computer network. Ear ...
(NIC). This task is performed by the
network scheduler A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
.


Random early detection

One solution is to use
random early detection Random early detection (RED), also known as random early discard or random early drop is a queuing discipline for a network scheduler suited for congestion avoidance. In the conventional tail drop algorithm, a router or other network component ...
(RED) on the network equipment's egress queue.Sally Floyd: RED (Random Early Detection) Queue Management
/ref> On
networking hardware Networking hardware, also known as network equipment or computer networking devices, are electronic devices which are required for communication and interaction between devices on a computer network. Specifically, they mediate data transmission in ...
ports with more than one egress queue,
weighted random early detection Weighted random early detection (WRED) is a queueing discipline for a network scheduler suited for congestion avoidance. It is an extension to random early detection (RED) where a single queue may have several different sets of queue thresholds. E ...
(WRED) can be used. RED indirectly signals TCP sender and receiver by dropping some packets, e.g. when the average queue length is more than a threshold (e.g. 50%) and deletes
linear Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...
ly or cubically more packets, up to e.g. 100%, as the queue fills further.


Robust random early detection

The
robust random early detection Robust random early detection (RRED) is a queueing disclipine for a network scheduler. The existing random early detection (RED) algorithm and its variants are found vulnerable to emerging attacks, especially the Low-rate Denial-of-Service attacks ...
(RRED) algorithm was proposed to improve the TCP throughput against denial-of-service (DoS) attacks, particularly low-rate denial-of-service (LDoS) attacks. Experiments confirmed that RED-like algorithms were vulnerable under LDoS attacks due to the oscillating TCP queue size caused by the attacks.


Flow-based WRED

Some network equipment is equipped with ports that can follow and measure each flow and are thereby able to signal a too big bandwidth flow according to some quality of service policy. A policy could then divide the bandwidth among all flows by some criteria.


Explicit Congestion Notification

Another approach is to use
Explicit Congestion Notification Explicit Congestion Notification (ECN) is an extension to the Internet Protocol and to the Transmission Control Protocol and is defined in RFC 3168 (2001). ECN allows end-to-end notification of network congestion without dropping packets. ECN is ...
(ECN). ECN is used only when two hosts signal that they want to use it. With this method, a protocol bit is used to signal explicit congestion. This is better than the indirect congestion notification signaled by packet loss by the RED/WRED algorithms, but it requires support by both hosts. When a router receives a packet marked as ECN-capable and the router anticipates congestion, it sets the ECN flag, notifying the sender of congestion. The sender should respond by decreasing its transmission bandwidth, e.g., by decreasing its sending rate by reducing the TCP window size or by other means.


TCP window shaping

Congestion avoidance can be achieved efficiently by reducing traffic. When an application requests a large file, graphic or web page, it usually advertises a ''window'' of between 32K and 64K. This results in the server sending a full window of data (assuming the file is larger than the window). When many applications simultaneously request downloads, this data can create a congestion point at an upstream provider. By reducing the window advertisement, the remote servers send less data, thus reducing the congestion.


Backward ECN

Backward ECN (BECN) is another proposed congestion notification mechanism. It uses
ICMP source quench The Internet Control Message Protocol (ICMP) is a supporting protocol in the Internet protocol suite. It is used by network devices, including routers, to send error messages and operational information indicating success or failure when commun ...
messages as an IP signaling mechanism to implement a basic ECN mechanism for IP networks, keeping congestion notifications at the IP level and requiring no negotiation between network endpoints. Effective congestion notifications can be propagated to transport layer protocols, such as TCP and UDP, for the appropriate adjustments.A proposal for Backward ECN for the Internet Protocol
/ref>


Side effects of congestive collapse avoidance


Radio links

The protocols that avoid congestive collapse generally assume that data loss is caused by congestion. On wired networks, errors during transmission are rare.
WiFi Wi-Fi () is a family of wireless network protocols, based on the IEEE 802.11 family of standards, which are commonly used for local area networking of devices and Internet access, allowing nearby digital devices to exchange data by radio wa ...
, 3G and other networks with a radio layer are susceptible to data loss due to interference and may experience poor throughput in some cases. The TCP connections running over a radio-based physical layer see the data loss and tend to erroneously believe that congestion is occurring.


Short-lived connections

The slow-start protocol performs badly for short connections. Older
web browser A web browser is application software for accessing websites. When a user requests a web page from a particular website, the browser retrieves its files from a web server and then displays the page on the user's screen. Browsers are used o ...
s created many short-lived connections and opened and closed the connection for each file. This kept most connections in the slow start mode. Initial performance can be poor, and many connections never get out of the slow-start regime, significantly increasing latency. To avoid this problem, modern browsers either open multiple connections simultaneously or reuse one connection for all files requested from a particular server.


Admission control

Admission control Admission control is a validation process in communication systems where a check is performed before a connection is established to see if current resources are sufficient for the proposed connection. Applications For some applications, dedicated ...
is any system that requires devices to receive permission before establishing new network connections. If the new connection risks creating congestion, permission can be denied. Examples include Contention-Free Transmission Opportunities (CFTXOPs) in the ITU-T
G.hn G.hn is a specification for home networking with data rates up to 2 Gbit/s and operation over four types of legacy wires: telephone wiring, coaxial cables, power lines and plastic optical fiber. A single G.hn semiconductor device is able to n ...
standard for home networking over legacy wiring, Resource Reservation Protocol for IP networks and Stream Reservation Protocol for
Ethernet Ethernet () is a family of wired computer networking technologies commonly used in local area networks (LAN), metropolitan area networks (MAN) and wide area networks (WAN). It was commercially introduced in 1980 and first standardized in 1 ...
.


See also

* * * * * * * * *


References

* * * *


External links

* Floyd, S. and K. Fall,
Promoting the Use of End-to-End Congestion Control in the Internet
' (IEEE/ACM Transactions on Networking, August 1999) * Sally Floyd,
On the Evolution of End-to-end Congestion Control in the Internet: An Idiosyncratic View
' (IMA Workshop on Scaling Phenomena in Communication Networks, October 1999) ('' pdf format'')
Linktionary term: Queuing


* ttp://www.cs.washington.edu/homes/ratul/red-pd/ Sally Floyd, Ratul Mahajan, David Wetherall: RED-PD: RED with Preferential Dropping
A Generic Simple RED Simulator for educational purposes by Mehmet Suzen

Approaches to Congestion Control in Packet Networks







TFRC Homepage



Recent Publications in low-rate denial-of-service (DoS) attacks
{{DEFAULTSORT:Network Congestion Network performance Teletraffic Transport layer protocols Technological failures Packets (information technology) de:Ãœberlastkontrolle