Active queue management

Last updated

In routers and 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 of reducing network congestion or improving end-to-end latency. This task is performed by the network scheduler, which for this purpose uses various algorithms such as random early detection (RED), Explicit Congestion Notification (ECN), or controlled delay (CoDel). RFC 7567 recommends active queue management as a best practice.

Contents

Overview

An Internet router typically maintains a set of queues, one or more per interface, that hold packets scheduled to go out on that interface. Historically, such queues use a drop-tail discipline: a packet is put onto the queue if the queue is shorter than its maximum size (measured in packets or in bytes), and dropped otherwise.

Active queue disciplines drop or mark packets before the queue is full. Typically, they operate by maintaining one or more drop/mark probabilities, and occasionally dropping or marking packets according to the probabilities before the queue is full.

Benefits

Drop-tail queues have a tendency to penalise bursty flows, and to cause global synchronisation between flows. By dropping packets probabilistically, AQM disciplines typically avoid both of these issues. [1]

By providing endpoints with congestion indication before the queue is full, AQM disciplines are able to maintain a shorter queue length than drop-tail queues, which combats bufferbloat and reduces network latency.

Drawbacks

Early AQM disciplines (notably RED and SRED) require careful tuning of their parameters in order to provide good performance. These systems are not optimally behaved from a control theory perspective. [2] Modern AQM disciplines (ARED, Blue, PI, CoDel, CAKE) are self-tuning, and can be run with their default parameters in most circumstances.

Network engineers have historically been trained to avoid packet loss, and have therefore sometimes been critical of AQM systems that drop packets: "Why should I drop perfectly good packets when I still have free buffer space?" [3]

Simulation

An active queue management and denial-of-Service (AQM&DoS) simulation platform is established based on the NS-2 simulation code of the RRED algorithm. The AQM&DoS simulation platform can simulate a variety of DoS attacks (Distributed DoS, Spoofing DoS, Low-rate DoS, etc.) and AQM algorithms (RED, RRED, SFB, etc.). It automatically calculates and records the average throughput of normal TCP flows before and after DoS attacks to facilitate the analysis of the impact of DoS attacks on normal TCP flows and AQM algorithms. [4]

Active queue management algorithms

Related Research Articles

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly referred to as TCP/IP. TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network. Major internet applications such as the World Wide Web, email, remote administration, and file transfer rely on TCP, which is part of the Transport Layer of the TCP/IP suite. SSL/TLS often runs on top of TCP.

Traffic shaping is a bandwidth management technique used on computer networks which delays some or all datagrams to bring them into compliance with a desired traffic profile. Traffic shaping is used to optimize or guarantee performance, improve latency, or increase usable bandwidth for some kinds of packets by delaying other kinds. It is often confused with traffic policing, the distinct but related practice of packet dropping and packet marking.

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 optional feature that may be used between two ECN-enabled endpoints when the underlying network infrastructure also supports it.

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.

FAST TCP is a TCP congestion avoidance algorithm especially targeted at long-distance, high latency links, developed at the Netlab, California Institute of Technology and now being commercialized by FastSoft. FastSoft was acquired by Akamai Technologies in 2012.

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 communications, traffic policing is the process of monitoring network traffic for compliance with a traffic contract and taking steps to enforce that contract. Traffic sources which are aware of a traffic contract may apply traffic shaping to ensure their output stays within the contract and is thus not discarded. Traffic exceeding a traffic contract may be discarded immediately, marked as non-compliant, or left as-is, depending on administrative policy and the characteristics of the excess traffic.

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 window (CWND), to achieve congestion avoidance. The TCP congestion-avoidance algorithm is the primary basis for congestion control in the Internet. Per the end-to-end principle, congestion control is largely a function of internet hosts, not the network itself. There are several variations and versions of the algorithm implemented in protocol stacks of operating systems of computers that connect to the Internet.

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.

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. Packet loss is measured as a percentage of packets lost with respect to packets sent.

Bandwidth management is the process of measuring and controlling the communications on a network link, to avoid filling the link to capacity or overfilling the link, which would result in network congestion and poor performance of the network. Bandwidth is described by bit rate and measured in units of bits per second (bit/s) or bytes per second (B/s).

Tail drop is a simple queue management algorithm used by network schedulers in network equipment to decide when to drop packets. With tail drop, when the queue is filled to its maximum capacity, the newly arriving packets are dropped until the queue has enough room to accept incoming traffic.

Blue is a scheduling discipline for the network scheduler developed by graduate student Wu-chang Feng for Professor Kang G. Shin at the University of Michigan and others at the Thomas J. Watson Research Center of IBM in 1999.

Sally Jean Floyd 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 and died in August 2019. She is best known for her work on Internet congestion control, and was in 2007 one of the top-ten most cited researchers in computer science.

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, as well as reduce the overall network throughput. When a router or switch is configured to use excessively large buffers, even very high-speed networks can become practically unusable for many interactive applications like voice over IP (VoIP), audio streaming, online gaming, and even ordinary web browsing.

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 (LDoS). Experiments have confirmed that the existing RED-like algorithms are notably vulnerable under LDoS attacks due to the oscillating TCP queue size caused by the attacks.

CoDel is an active queue management (AQM) algorithm in network routing, developed by Van Jacobson and Kathleen Nichols and published as RFC8289. It is designed to overcome bufferbloat in networking hardware, such as routers, by setting limits on the delay network packets experience as they pass through buffers in this equipment. CoDel aims to improve on the overall performance of the random early detection (RED) algorithm by addressing some of its fundamental misconceptions, as perceived by Jacobson, and by being easier to manage.

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 queues of the protocol stack and network interface controller. There are several network schedulers available for the different operating systems, that implement many of the existing network scheduling algorithms.

Kathleen Nichols is an American computer scientist and computer networking expert. Nichols is the founder and CEO of Pollere, Inc, a network architecture and performance company based in California, US. Before founding Pollere, Nichols was VP of Network Science at Packet Design, where she was part of the founding team. Prior to Packet Design she was director of advanced Internet architectures in the Office of CTO at Cisco Systems.

Dave Taht Made the internet better for 10s of millions thus far

Dave Täht is an American computer scientist, musician, lecturer, asteroid exploration advocate, and Internet activist. He is the CEO of TekLibre, LLC.

References

  1. ↑ Floyd, Sally; Jacobson, Van (August 1993). "Random Early Detection (RED) gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking. 1 (4): 397–413. CiteSeerX   10.1.1.147.3833 . doi:10.1109/90.251892. S2CID   221977646 . Retrieved 2008-03-16.
  2. ↑ C.V. Hollot, Vishal Misra, Don Towsley and Wei-Bo Gong, Analysis and Design of Controllers for AQM Routers Supporting TCP Flows
  3. ↑ "The criminal mastermind: bufferbloat!". jg's Ramblings. Gettys.wordpress.com. 2010-12-03. Retrieved 2014-01-23.
  4. ↑ "AQM&DoS Simulation Platform - Changwang Zhang".
  5. ↑ Imer, Orhan; Basar, Tamer (December 2005). "A Global Stability Result in Utility-Based Congestion Control" (PDF). Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference 2005: 6740–6743.
  6. ↑ Athuraliya, S. (June 2001). "REM: Active Queue Management". IEEE Transactions on Networking. 15 (3): 48–53.
  7. ↑ Ratul Mahajan, Sally Floyd, and David Wetherall, Controlling high-bandwidth flows at the congested router, ICNP 2001
  8. ↑ Changwang Zhang, Jianping Yin, Zhiping Cai, and Weifeng Chen, RRED: Robust RED Algorithm to Counter Low-rate Denial-of-Service Attacks, IEEE Communications Letters, vol. 14, pp. 489-491, 2010. Ref
  9. ↑ Changwang Zhang, Jianping Yin, and Zhiping Cai, RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks, in International Symposium on Communication and Information Technology (ISCIT), 2009. Ref
  10. ↑ "Smart Queue Management". bufferbloat.net. Retrieved 3 October 2020.
  11. ↑ "OpenWrt·Traffic Shaping·SQM". OpenWrt.org. OpenWrt Project. 2 January 2017. Retrieved 3 October 2020.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.