Network congestion
Network congestion in
Networks use congestion control and congestion avoidance techniques to try to avoid collapse. These include:
Network capacity
Network resources are limited, including
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
Congestive collapse was identified as a possible problem by 1984.
Congestion control
Congestion control modulates traffic entry into a telecommunications network in order to avoid congestive collapse resulting from oversubscription.[7] 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
Let be the rate of flow , be the capacity of link , and be 1 if flow uses link and 0 otherwise. Let , and be the corresponding vectors and matrix. Let be an increasing, strictly concave function, called the utility, which measures how much benefit a user obtains by transmitting at rate . The optimal rate allocation then satisfies
- such that
The
Congestion control then becomes a distributed optimization algorithm. Many current congestion control algorithms can be modelled in this framework, with being either the loss probability or the queueing delay at link . 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 – active queue management which reorders or selectively drops network packets in the presence of congestion
- Explicit Congestion Notification – an extension to IP and TCP communications protocols that adds a flow control mechanism
- TCP congestion control – 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] 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
Some end-to-end protocols are designed to behave well under congested conditions;
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
TCP/IP congestion avoidance
The
Problems occur when concurrent TCP flows experience
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.[15][16] 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
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.[18]
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.[19]
Explicit Congestion Notification
Another approach is to use Explicit Congestion Notification (ECN).[20] 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.[21][15]
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.[22][23]
Backward ECN
Backward ECN (BECN) is another proposed congestion notification mechanism. It uses
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.
Short-lived connections
The slow-start protocol performs badly for short connections. Older
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.
See also
- Bandwidth management – Capacity control on a communications network
- Cascading failure – Systemic risk of failure
- Choke exchange – Telephone exchange designed to handle many simultaneous call attempts
- Erlang (unit) – Load measure in telecommunications
- Sorcerer's Apprentice syndrome – Network protocol flaw in the original versions of TFTP
- Teletraffic engineering – Application of traffic engineering theory to telecommunications
- Thrashing – Constant exchange between memory and storage
- Traffic shaping – Communication bandwidth management technique
- Reliability (computer networking) – Protocol acknowledgement capability
References
- ^ (Al-Bahadili, 2012, p. 282) Al-Bahadili, H. (2012). Simulation in computer network design and modeling: Use and analysis. Hershey, PA: IGI Global.
- ^ den Hartog, F., Raschella, A., Bouhafs, F., Kempker, P., Boltjes, B., & Seyedebrahimi, M. (2017, November). 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.
- RFC 896
- ISBN 9780132808187.
- ^ Van Jacobson; Michael J. Karels (November 1988), Congestion Avoidance and Control (PDF),
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 bythis 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)TCPwas mis-behaving or if it could be tuned to work better under abysmal network conditions.The answer to both of these questions was "yes".
- ^ Hafner, Katie (4 September 2019). "Sally Floyd, Who Helped Things Run Smoothly Online, Dies at 69". New York Times. Retrieved 5 September 2019.
- ISSN 1474-6670.
- doi:10.1109/tcom.1974.1092259. Archived from the original(PDF) on March 4, 2016.
- S2CID 34447400
- ^ Van Jacobson, Michael J. Karels. 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 Algorithms
- ^ RFC 2581 - TCP Congestion Control
- ^ RFC 3390 - TCP Increasing TCP's Initial Window
- ^ TCP Congestion Avoidance Explained via a Sequence Diagram
- ^ a b Sally Floyd: RED (Random Early Detection) Queue Management
- ^ Sally Floyd, Van Jacobson. 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.
- CiteSeerX 10.1.1.105.5995,
...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...
- S2CID 1121461.
- Cisco Systems. Retrieved 2020-08-07.
- ^ RFC 3168 - The Addition of Explicit Congestion Notification (ECN) to IP
- ^ Comparative study of RED, ECN and TCP Rate Control (1999)
- ^ Generalized Window Advertising for TCP CongestionControl (PDF), retrieved 2020-11-13
- ISBN 978-1-4757-6693-6
- ^ A proposal for Backward ECN for the Internet Protocol
- John Evans; Clarence Filsfils (2007). Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice. Morgan Kaufmann. ISBN 978-0-12-370549-5.
- Sally Floyd (September 2000). Congestion Control Principles. RFC 2914.
- John Nagle (6 January 1984). Congestion Control in IP/TCP. RFC 896.
- Van Jacobson; Michael J. Karels (November 1988). "Congestion Avoidance and Control" (PDF).
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) (pdfformat)
- Linktionary term: Queuing Archived 2003-03-08 at the Wayback Machine
- 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"
- Sally Floyd, Ratul Mahajan, David Wetherall: RED-PD: RED with Preferential Dropping Archived 2003-04-02 at the Wayback Machine
- A Generic Simple RED Simulator for educational purposes by Mehmet Suzen
- Approaches to Congestion Control in Packet Networks
- Papers in Congestion Control
- Random Early Detection Homepage
- Explicit Congestion Notification Homepage
- TFRC Homepage
- AIMD-FC Homepage
- Recent Publications in low-rate denial-of-service (DoS) attacks