Network congestion#Congestive collapse

{{Short description|Reduced quality of service due to high network traffic}}

Network congestion in data networking and queueing theory is the reduced quality of service that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay, packet loss 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.(Al-Bahadili, 2012, p. 282) Al-Bahadili, H. (2012). [https://books.google.com/books?id=uNlplf2C03QC&dq=network+congestion+occurs+when+a+link+or+node+is+carrying+so+much+data+that+its+quality+of+service+deteriorates.&pg=PA282 Simulation in computer network design and modeling: Use and analysis]. Hershey, PA: IGI Global.

Network protocols 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 in protocols such as CSMA/CA in 802.11 and the similar CSMA/CD in the original Ethernet, window reduction in TCP, and fair queueing in devices such as routers and network switches. 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.

Network capacity

Network resources are limited, including router processing time and link throughput. Resource contention may occur on networks in several common circumstances. A wireless LAN is easily filled by a single personal computer.den Hartog, F., Raschella, A., Bouhafs, F., Kempker, P., Boltjes, B., & Seyedebrahimi, M. (2017, November). [http://unsworks.unsw.edu.au/fapi/datastream/unsworks:50254/bin458a10d9-f568-479c-a9b5-5c185ef64e78?view=true A Pathway to solving the Wi-Fi Tragedy of the Commons in apartment blocks]. In 2017 27th International Telecommunication Networks and Applications Conference (ITNAC) (pp. 1-6). IEEE. Even on fast computer networks, the backbone can easily be congested by a few servers and client PCs. Denial-of-service attacks by botnets are capable of filling even the largest Internet backbone network links, generating large-scale network congestion. In telephone networks, a mass call event can overwhelm digital telephone circuits, in what can otherwise be defined as a denial-of-service attack.

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 and a wide area network 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 and loss occur and quality of service is extremely poor.

Congestive collapse was identified as a possible problem by 1984.{{IETF RFC|896}} It was first observed on the early Internet in October 1986,{{cite book |title=TCP/IP Illustrated, Volume 1: The Protocols |author1=Fall, K.R. |author2=Stevens, W.R. |isbn=9780132808187 |url=https://books.google.com/books?id=a23OAn5i8R0C |date=2011 |edition=2 |publisher=Pearson Education |page=739}} when the NSFNET phase-I backbone dropped three orders of magnitude from its capacity of 32 kbit/s to 40 bit/s,{{citation |author1=Van Jacobson |author2=Michael J. Karels |date=November 1988 |title=Congestion Avoidance and Control |url=https://ee.lbl.gov/papers/congavoid.pdf |quote=In October of ’86, the Internet had the first of what became a series of ‘congestion collapses’. During this period, the data throughput from LBL to UC Berkeley (sites separatedby 400 yards and two IMP hops) dropped from 32 Kbps to 40 bps. We were fascinated by this sudden factor-of-thousand drop in bandwidth and embarked on an investigation of why things had gotten so bad. In particular, we wondered if the 4.3BSD (Berkeley UNIX) TCP was mis-behaving or if it could be tuned to work better under abysmal network conditions.The answer to both of these questions was “yes”.}} which continued until end nodes started implementing Van Jacobson and Sally Floyd's congestion control between 1987 and 1988.{{cite news |last1=Hafner |first1=Katie |title=Sally Floyd, Who Helped Things Run Smoothly Online, Dies at 69 |url=https://www.nytimes.com/2019/09/04/science/sally-floyd-dead.html |work=New York Times |date=4 September 2019 |access-date=5 September 2019 |ref=floyd69}} When more packets were sent than could be handled by intermediate routers, the intermediate routers discarded many packets, expecting the endpoints 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.{{Cite journal |last=Nanda |first=Priyadarsi |date=2000-11-01 |title=A Control Theory Approach for Congestion Control in Intranetwork |url=https://www.sciencedirect.com/science/article/pii/S1474667017367356 |journal=IFAC Proceedings Volumes |series=16th IFAC Workshop on Distributed Computer Control Systems (DCCS 2000), Sydney, Australia, 29 November-1 December 2000 |language=en |volume=33 |issue=30 |pages=91–94 |doi=10.1016/S1474-6670(17)36735-6 |issn=1474-6670}} 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, who applied microeconomic theory and convex optimization 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 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_{li}$ 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, 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, $p_l$ . The sum of these multipliers, $y_i=\sum_l p_l r_{li},$ is the price to which the flow responds.

Congestion control then becomes a distributed optimization algorithm. Many current congestion control algorithms can be modeled 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 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

Mitigation

Mechanisms have been invented to prevent network congestion or to deal with a network collapse:

Network scheduler{{snd}} active queue management which reorders or selectively drops network packets in the presence of congestion
Explicit Congestion Notification{{snd}} an extension to IP and TCP communications protocols that adds a flow control mechanism
TCP congestion control{{snd}} 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.{{citation needed|date=February 2019}} Other strategies such as slow start ensure that new connections do not overwhelm the router before congestion detection initiates.

Common router congestion avoidance mechanisms include fair queuing and other scheduling algorithms, and random early detection 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,{{cite journal |author1=Vinton G. Cerf |author2=Robert E. Kahn |title=A Protocol for Packet Network Intercommunication|journal=IEEE Transactions on Communications |volume=22 |issue=5 |date=May 1974 |pages=637–648 |doi=10.1109/tcom.1974.1092259 |archive-url=https://web.archive.org/web/20160304150203/http://ece.ut.ac.ir/Classpages/F84/PrincipleofNetworkDesign/Papers/CK74.pdf |url=http://ece.ut.ac.ir/Classpages/F84/PrincipleofNetworkDesign/Papers/CK74.pdf|archive-date=March 4, 2016}} 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 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 or queuing delay to adjust their transmission rate. Various network congestion avoidance processes support different trade-offs.{{citation |doi=10.1109/LCN.2000.891077 |chapter=TCP Tunnels: Avoiding Congestion Collapse |date=2000|title=Proceedings 25th Annual IEEE Conference on Local Computer Networks. LCN 2000 |pages=408–417 |last1=Lee |first1=B.P. |last2=Balan |first2=R.K. |last3=Jacob |first3=L. |last4=Seah |first4=W.K.G. |last5=Ananda |first5=A.L. |isbn=0-7695-0912-6 |s2cid=34447400 }}

=TCP/IP congestion avoidance=

The TCP congestion avoidance algorithm is the primary basis for congestion control on the Internet.Van Jacobson, Michael J. Karels. [http://citeseer.ist.psu.edu/484335.html Congestion Avoidance and Control] (1988). Proceedings of the Sigcomm '88 Symposium, vol.18(4): pp.314–329. Stanford, CA. August, 1988. This paper originated many of the congestion avoidance algorithms used in TCP/IP.RFC 2001 - TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery AlgorithmsRFC 2581 - TCP Congestion ControlRFC 3390 - TCP Increasing TCP's Initial Window[http://www.eventhelix.com/RealtimeMantra/Networking/TCP_Congestion_Avoidance.pdf TCP Congestion Avoidance Explained via a Sequence Diagram]

Problems occur when concurrent TCP flows experience tail-drops, especially when bufferbloat 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.

=Active queue management=

Active queue management (AQM) is the reordering or dropping of network packets inside a transmit buffer that is associated with a network interface controller (NIC). This task is performed by the network scheduler.

==Random early detection==

One solution is to use random early detection (RED) on the network equipment's egress queue.[http://www.icir.org/floyd/red.html Sally Floyd: RED (Random Early Detection) Queue Management]Sally Floyd, Van Jacobson. [http://citeseer.ist.psu.edu/462978.html Random Early Detection Gateways for Congestion Avoidance] (1993). IEEE/ACM Transactions on Networking, vol.1(4): pp.397–413. Invented Random Early Detection (RED) gateways. On networking hardware ports with more than one egress queue, weighted random early detection (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 linearly or cubically more packets,{{citation |title=An Analytical RED Function Design Guaranteeing Stable System Behavior |citeseerx = 10.1.1.105.5995|quote=...The advantage of this function lies not only in avoiding heavy oscillations but also in avoiding link under-utilization at low loads. The applicability of the derived function is independent of the load range, no parameters are to be adjusted. Compared to the original linear drop function applicability is extended by far...Our example with realistic system parameters gives an approximation function of the cubic of the queue size...}} up to e.g. 100%, as the queue fills further.

==Robust random early detection==

The robust random early detection (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.{{cite journal|first1=Changwang|last1=Zhang|first2=Jianping|last2=Yin|first3=Zhiping|last3=Cai|first4=Weifeng|last4=Chen|title=RRED: Robust RED Algorithm to Counter Low-rate Denial-of-Service Attacks|publisher=IEEE|journal=IEEE Communications Letters|volume=14|issue=5|pages=489–491|date=2010|url=http://sites.google.com/site/cwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow-rateDenial-of-ServiceAttacks.pdf?attredirects=0 |doi=10.1109/LCOMM.2010.05.091407|s2cid=1121461}}

==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.{{cite web |url=https://www.cisco.com/c/en/us/td/docs/ios/qos/configuration/guide/12_2sr/qos_12_2sr_book/congestion_avoidance.html |title=Congestion Avoidance Overview |publisher=Cisco Systems |access-date=2020-08-07}}

==Explicit Congestion Notification==

Another approach is to use Explicit Congestion Notification (ECN).RFC 3168 - The Addition of Explicit Congestion Notification (ECN) to IP 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.[http://citeseer.ist.psu.edu/bagal99comparative.html Comparative study of RED, ECN and TCP Rate Control (1999)]

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.

The L4S protocol is an enhanced version of ECN which allows senders to collaborate with network devices to control congestion.{{Cite web |date=2023-06-14 |title=L4S |url=https://www.bell-labs.com/research-innovation/projects-and-initiatives/l4s/ |access-date=2025-01-31 |website=Nokia Bell Labs |language=en}}

==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.{{citation |url=http://nrlweb.cs.ucla.edu/nrlweb/publication/download/162/2002-ett-0.pdf |title=Generalized Window Advertising for TCP CongestionControl |access-date=2020-11-13}}{{citation |chapter=Advertised Window-Based TCP Flow Control in Routers |doi=10.1007/978-0-387-35522-1_12|title=Telecommunication Network Intelligence|year=2000|last1=Pop|first1=O.|last2=Moldován|first2=I.|last3=Simon|first3=Cs.|last4=Bíró|first4=J.|last5=Koike|first5=A.|last6=Ishii|first6=H.|pages=197–218|isbn=978-1-4757-6693-6|doi-access=free}}

== {{Anchor|BECN}}Backward ECN ==

Backward ECN (BECN) is another proposed congestion notification mechanism. It uses ICMP source quench 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.[http://tools.ietf.org/html/draft-salim-jhsbnns-ecn-00 A proposal for Backward ECN for the Internet Protocol]

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, 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 browsers 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 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 standard for home networking over legacy wiring, Resource Reservation Protocol for IP networks and Stream Reservation Protocol for Ethernet.

References

{{cite book |title=Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice |author1=John Evans |author2=Clarence Filsfils |publisher=Morgan Kaufmann |date=2007 |isbn=978-0-12-370549-5}}
{{cite IETF |RFC=2914 |title=Congestion Control Principles |author=Sally Floyd |date=September 2000}}
{{cite IETF |RFC=896 |title=Congestion Control in IP/TCP |author=John Nagle |date=6 January 1984}}
{{cite web |title=Congestion Avoidance and Control |url=http://ee.lbl.gov/papers/congavoid.pdf |author1=Van Jacobson |author2=Michael J. Karels |date=November 1988}}

External links

Floyd, S. and K. Fall, [http://www.aciri.org/floyd/end2end-paper.html Promoting the Use of End-to-End Congestion Control in the Internet] (IEEE/ACM Transactions on Networking, August 1999)
Sally Floyd, [http://www.ima.umn.edu/talks/workshops/10-22-24.99/floyd/floyd.pdf 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)
[http://www.linktionary.com/q/queuing.html Linktionary term: Queuing] {{Webarchive|url=https://web.archive.org/web/20030308154423/http://www.linktionary.com/q/queuing.html |date=2003-03-08 }}
[https://www.cse.wustl.edu/~jain/papers/mecn_cth.htm Pierre-Francois Quet, Sriram Chellappan, Arjan Durresi, Mukundan Sridharan, Hitay Ozbay, Raj Jain, "Guidelines for optimizing Multi-Level ECN, using fluid flow based TCP model"]
[http://www.cs.washington.edu/homes/ratul/red-pd/ Sally Floyd, Ratul Mahajan, David Wetherall: RED-PD: RED with Preferential Dropping] {{Webarchive|url=https://web.archive.org/web/20030402201326/http://www.cs.washington.edu/homes/ratul/red-pd/ |date=2003-04-02 }}
[http://code.google.com/p/guduz/ A Generic Simple RED Simulator for educational purposes by Mehmet Suzen]
[https://web.archive.org/web/20140221123729/http://utopia.duth.gr/~emamatas/jie2007.pdf Approaches to Congestion Control in Packet Networks]
[https://web.archive.org/web/20100611055219/http://www.ecse.rpi.edu/Homepages/shivkuma/research/cong-papers.html Papers in Congestion Control]
[http://www.icir.org/floyd/red.html Random Early Detection Homepage]
[http://www.icir.org/floyd/ecn.html Explicit Congestion Notification Homepage]
[http://www.icir.org/tfrc/ TFRC Homepage]
[https://web.archive.org/web/20090113204941/http://www.ccs.neu.edu/home/ladrian/abstract/aimdfc.html AIMD-FC Homepage]
[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinlow-ratedosattacks Recent Publications in low-rate denial-of-service (DoS) attacks]