Editing Network congestion (section)

==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 [[TCP congestion control#Slow start|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,<ref>{{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}}</ref> but Van Jacobson's inclusion of an open source solution in the Berkeley Standard Distribution UNIX ("[[BSD]]") in 1988 first provided good behavior.

[[User Datagram Protocol|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 communication|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.<ref>{{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 }}</ref>

===TCP/IP congestion avoidance===
The [[TCP congestion avoidance algorithm]] is the primary basis for congestion control on the Internet.<ref>[[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&ndash;329. Stanford, CA. August, 1988. This paper originated many of the congestion avoidance algorithms used in TCP/IP.</ref><ref>RFC 2001 - TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms</ref><ref>RFC 2581 - TCP Congestion Control</ref><ref>RFC 3390 - TCP Increasing TCP's Initial Window</ref><ref>[http://www.eventhelix.com/RealtimeMantra/Networking/TCP_Congestion_Avoidance.pdf TCP Congestion Avoidance Explained via a Sequence Diagram]</ref>

Problems occur when concurrent TCP flows experience [[tail-drop]]s, 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.<ref name="FloydRED">[http://www.icir.org/floyd/red.html Sally Floyd: RED (Random Early Detection) Queue Management]</ref><ref>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&ndash;413. Invented Random Early Detection (RED) gateways.</ref> 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 [[linear]]ly or [[Cubic function|cubically]] more packets,<ref>{{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...}}</ref> 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.<ref name=RRED>{{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 <!-- original URL http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5456075 -->|doi=10.1109/LCOMM.2010.05.091407|s2cid=1121461}}</ref>

====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.<ref>{{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}}</ref>

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

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.<ref>{{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}}</ref>

====TCP window shaping====
{{See also|TCP window scale option}}

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.<ref>{{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}}</ref><ref>{{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}}</ref>

==== {{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.<ref>[http://tools.ietf.org/html/draft-salim-jhsbnns-ecn-00 A proposal for Backward ECN for the Internet Protocol]</ref>