We start by presenting some basic concepts to facilitate the understanding of the numerous policing techniques that are presented afterwards.
Packets
A data sender usually splits data to be sent into small units known as packets. Each packet consists of a header and a payload carrying the data to be delivered. The header contains fields defined by the relevant communication protocol. The great majority of packets carried by commercial networks nowadays are so-called IP packets. IP is the Internet Protocol. This ensures that a network of routers can forward any packet from the source to its destination. IP is a connectionless protocol—that means that the header information in each data packet is sufficiently self-contained for routers to deliver it independently of other packets; each packet could even take a different route to reach the destination.
Distributed Bandwidth Sharing and Congestion
Data traversing the Internet follows a path between a series of routers, controlled by various routing protocols. Each router seeks to move the packet closer to its final destination. If too much traffic traverses the same router in the network, the router can become congested and packets start to experience excessive delays whilst using that network path. If sources persist in sending traffic through that router it could become seriously overloaded (congested) and even drop traffic (when its buffers overflow). If sources still persist in sending traffic through this bottleneck it could force more routers to become congested, and if the phenomenon keeps spreading, that can lead to a congestion collapse for the whole Internet—which occurred regularly in the mid-1980s.
The solution to that problem has been to ensure that sources take responsibility for the rate at which they send data over the Internet by implementing congestion control mechanisms. Sources monitor feedback from the receiver of the metric that characterises path congestion in order to detect when the path their data is following is getting congested, in which case they react by reducing their throughput—while they may slowly increase their rate when there is no sign of the path becoming congested.
Typical path characterisation metrics that sources monitor are average roundtrip time (RTT) for the data path, variance of the roundtrip time (jitter) and level of congestion on the path.
The congestion level can be signalled either implicitly (through congested routers dropping packets when their buffers overflow or to protect themselves) or explicitly (through mechanisms such as explicit congestion notification—see next subsection). Currently the most common option is implicit signalling.
Sources using TCP are able to detect losses, because a packet loss causes a gap in the sequence; whenever a TCP source detects a loss, it is meant to halve its data transmission rate, but no more than once per round trip time, which alleviates the congestion on the router at the bottleneck.
DEC-Bit Scheme
The DEC-bit scheme was the ancestor of modern mechanisms to convey congestion notification in packet networks by providing explicit congestion notification to the sources. This is discussed in a paper entitled “A Binary Feedback Scheme for Congestion Avoidance in Computer Networks” by Ramakrishnan and Jain, which will be referred to for convenience as [RAN90a]. Bibliographic details of this and other prior art documents are provided in the “References” section below. With this scheme when a router detects congestion it sets a bit (CI) in each packet, the receiver then relays this information back to the sender in its acknowledgments, and the sender in turn adjusts its transmission rate. In the router the congestion detection algorithm is based on average queue length. The source reaction to DEC-bit in acknowledgments is an Additive Increase Multiplicative Decrease (AIMD) response which means that congestion window grows at linear rate in the absence of congestion feedback and it declines multiplicatively (i.e. exponentially) for every congestion feedback event.
Explicit Congestion Notification
Explicit Congestion Notification (ECN) [RFC3168] conveys congestion in TCP/IP networks by means of two-bit ECN field in the IP header, whether in IPv4 (see FIG. 1) and IPv6 (see FIG. 2). Prior to the introduction of ECN, these two bits were present in both types of IP header, but always set to zero. Therefore, if these bits are both zero, a queue management process assumes that the packet comes from a transport protocol on the end-systems that will not understand the ECN protocol so it only uses drop, not ECN, to signal congestion.
The meaning of all four combinations of the two ECN bits is shown in FIG. 3. If either bit is one, it tells a queue management process that the packet has come from an ECN-capable transport (ECT) that will understand ECN marking, as well as drop, as a signal of congestion. When a queue management process detects congestion, for packets with a non-zero ECN field, it sets the ECN field to the Congestion Experienced (CE) codepoint. On receipt of such a marked packet, a TCP receiver sets the Echo Congestion Experienced (ECE) flag in the TCP header, which the TCP source interprets as if the packet has been dropped for the purpose of its rate control.
Drop and congestion signals are not mutually exclusive signals, and flows that enable ECN have the potential to detect and respond to both signals.
As well as the idea of ECN being adopted in IP, it was previously adopted in Frame Relay and ATM, but in these latter two protocols the network arranges feedback of the congestion signals internally, and the network enforces traffic limits to prevent congestion build-up [ITU-T Rec.I.371]. When a cell arriving at a switch causes a congestion threshold to be exceeded, then its EFCI bit is set.
The IEEE has standardised an explicit congestion approach where Ethernet switches not the end systems arrange to feedback the congestion signals, although the Ethernet device on the sending system is expected to co-operate by reducing its rate in response to the signals. The approach is tailored exclusively for homogeneous data centre environments.
In previous approaches, each frame (or packet) carried just a binary flag and the strength of the congestion signal depended on the proportion of marked frames—effectively a unary encoding of the congestion signal in a stream of zeroes and ones. However, the IEEE scheme signals a multi-bit level of congestion in each feedback frame, hence its name: Quantised Congestion Notification or QCN [IEEE802.1Qau].
Random Early Detection (RED)
Historically, routers would drop packets when they got completely saturated (i.e. when a traffic burst cannot be accommodated in the buffer of the router)—this policy is called drop-tail. Random early detection (RED) [RED] is an improvement intended to desynchronise TCP flows (synchronisation occurs when multiple TCP flows increase and decrease their transmission window at the same time). RED is an active queue management (AQM) process that monitors the average queue length in a buffer and when this is higher than a given threshold, the router starts to drop/mark packets with a probability which increases with the excess length of the averaged queue over the threshold. RED is widely used in today's Internet because it allows sources to react more promptly to incipient congestion and it keeps queues from growing unnecessarily long. Equipment vendors have implemented variants of RED, e.g. Cisco' proprietary implementation is Weighted Random Early Detection (WRED). However, it is well known that RED is very sensitive to parameter setting.
In the course of experimental work to investigate the sensitivity of RED to its parameter settings, the timescale over which RED averaged the queue was investigated, and in one case at least averaging was turned off completely, instead using the instantaneous queue [RED-params].
The use of an Active Queue Management (AQM) technique using Random Early Detection (RED) will be described with reference to FIG. 4.
RED randomly drops/marks packets with a probability p that depends upon the smoothed queue qave. In a RED-based AQM, a smoothed queue qave is continuously estimated by means of an exponential weighted moving average (EWMA) of the real queue q:qave←(1−wq)qave+wqq where wq is the weight given to the real queue's length; see FIG. 4a) for an example of real queue versus smoothed queue evolution over time.
When the smoothed queue size qave is below a minimum threshold q0 then no packets are dropped/marked. When qave is between q0 and q1 then packets are discarded with a probability p, between 0 and p1, that is linearly proportional to qave. When qave is greater than threshold q1 then probabilistic drop/mark continues with an increased probability ranging between p1 and pmax, which still depends linearly on qave. This is also known as the Gentle variant of RED algorithm [GRED] (see FIG. 4b)). Its behaviour differs from the original RED between q1 and qmax: while GRED drops/marks packets with a probability which depends linearly upon smoothed queue length with a maximum probability pmax, in such interval RED marks with a maximum probability pmax. See FIG. 4c) for an example of time evolution of packet drop/mark probability. Assuming the Sources of packet load are responsive to congestion, it can be seen that a period of drops/marks p>0 results in senders slowing down, which results in reduced queue length and hence no drop/mark p=0; subsequently senders increase their transmission rate which results in an increased queue length, note that it takes some time before p>0 again because of the queue length smoothing.
Fairness Improvement for RED (FI-RED)
A paper entitled “FI-RED: AQM Mechanism for Improving Fairness among TCP Connections in Tandem Networks” by H. Ohsaki et al [FI-RED] discusses an active queue management mechanism for improving fairness among heterogeneous TCP connections. In FI-RED, an ECN-based technique is used for differentiating the packet marking probability of RED in dependence on whether the CE (Congestion Experienced) bit is set in arriving packets. With FI-RED, congestion indications to TCP connections with a large number of hops (i.e. those connections with a high probability that the CE bit is set) are suppressed. By virtue of such a modification to RED, a TCP connection with a large number of hops will suffer almost the same packet marking probability as one with a small number of hops. This is intended to improve fairness among TCP connections with different numbers of hops. It will be noted that with FI-RED, ECN marks are assigned to packets with a marking probability based on pre-existing congestion markings on the arriving packets (not the ECN-capability itself), which is then compared with the marking probability determined from the local queue length by the traditional RED algorithm.
Random Exponential Marking (REM) [REM]
Whereas with RED, congestion notification depends upon the average queue length, with the REM AQM, congestion signals depend on rate deviation (i.e. queue growth over a period) and queue deviation (i.e. difference between queue length and a target queue length). The queue is sampled periodically. Between samples, the congestion signal thus depends on a delayed rather than an instantaneous measure of the queue. The probability of marking or dropping in the REM AQM is characterised by an exponential as opposed to a piece-wise linear function used by RED, and similarly to RED congestion feedback can be by dropping or by ECN marking. The exponential function in REM ensures that signals accumulated along a path are precisely summed to signal end-to-end congestion to the source.
BLUE
BLUE [BLUE] is an AQM designed to overcome the inefficiencies that arise in the presence of bursty traffic and AQMs based on a smoothed queue such as RED. With bursty traffic, queue length often oscillates wildly and RED-like AQMs that drop based on smoothed queue length are unable to react sufficiently quickly. BLUE maintains a probability of packet marking or dropping which is based on actual queue occupancy hence, congestion notification (drop or ECN-mark) depends upon actual queue length and not smoothed queue length. This marking probability is increased when packets are being dropped and is decreased when there is less congestion.
Proportional-Integral (PI)
Proportional-integral [PI] controllers are controllers based on feedback control theory which perform AQM functions. Like BLUE, a key feature of the PI controller is to use the instantaneous queue size not an averaged queue length to determine marking and/or loss probability, in order to minimise delay of the feedback signal.
RED in a Different Light (nRED)
nRED is a self-configuring variant of RED which is available online [nRED] but has not been published in peer reviewed journals or conferences. This AQM estimates the persistent queue, which differs from the smoothed-RED queue as it only seeks to track persistent buffer occupancy that has not cleared within a given time interval. This is achieved by means of a filtered function of the instantaneous queue length. It compares the instantaneous queue to the filtered value and, if it is greater, the filtered function rises using the same exponentially weighted moving average as RED, but if it is less, the filtered value tracks the instantaneous queue downwards.
Controlled Delay (CoDel)
CoDel [CoDel] superseded nRED. It uses the service time (or sojourn time) that a packet spends in a queue as the characterisation of queue length and produces a smoothed value of recent sojourn times by taking the minimum sojourn time seen over a recent time interval.
Sample Path Shadow Pricing (SPSP)
Sample Path Shadow Pricing (SPSP) [GI99] is a scheme which prescribes to mark packets that cause the unsmoothed queue to exceed a threshold and then lead to buffer overflow. This is unattainable in practice, as a packet may have left the queue by the time a decision is made that it should have been marked. However, it is used as a theoretical ideal e.g. to define the SPSP marking fairness principle, that is, a marking algorithm satisfies SPSP fairness if it marks the same number of packets that SPSP would have marked. SPSP purely concerns ECN marking and does not consider loss.
Pre-Congestion Notification (PCN)
The IETF pre-congestion notification (PCN) architecture is a framework that supports Quality of Service (QoS) of inelastic traffic within a DiffServ domain. Admission control (or flow termination) of inelastic traffic in a PCN-domain depends upon the marked PCN-traffic observed within the priority class reserved for PCN-traffic. PCN traffic can coexist with other traffic and receive different treatment within the queue. Two PCN marking algorithms have been standardised[PCN] based on the idea of virtual queue [GI99] which is a fictitious queue that emulates the behaviour of a real queue if it were draining at a slower rate that the actual link capacity.
The standardised PCN marking algorithms both use the instantaneous length of the virtual queue, not a smoothed queue length as with DEC-bit or RED. PCN uses the Not-ECT codepoint in the ECN field (FIG. 3) in a similar way to ECN, in order to support a mixture of traffic sharing the same queue, some of which is capable of being PCN-marked and some hot. Non-PCN traffic sharing a priority queue would be dropped rather than marked if it exceeded the policed rate of the priority queue.
Congestion Control for High Bandwidth-Delay-Product (BDP) Networks
Traditional TCP/IP congestion control and recovery mechanics can be detrimental to the performance of delay sensitive applications. This is particularly problematic for high Bandwidth-Delay-Product (BDP) networks (also known as Long Fat Networks (LFN)). The literature on congestion control improvements for LFN is vast. It will not be covered further here, given the focus on AQM mechanisms in queues rather than congestion control algorithms in end-systems.
Reach Overload, Send ECN (ROSE)
The ROSE algorithm [WI99] is a queue marking variant of RED [RED] designed to improve its fairness while scaling to large networks. This is achieved by marking all packets whenever the queue size exceeds a threshold b and dynamically adapting b as follows:                if a packet would have been marked by SPSP, then decrease b, i.e. such that b←b−κε;        when a packet is marked then increase b, i.e. such that b←b+ε;where κ is a variable indicating how many marks are equivalent to a drop (1 or more) and ε is an infinitesimally small variable. This algorithm, which is based on actual queue length, can be shown to be fair to flows as it marks packets proportionally to the congestion they cause.        
ROSE is particularly relevant because it starts from the premise that an ECN mark need not be equivalent to a drop, instead the two being linearly related through the parameter κ. However, ROSE is a theoretical demonstration of a point, rather than a concrete algorithm proposal, so it does not actually specify the algorithm that should be used to drop packets rather than mark them, although perhaps it is implied that ROSE would be used with κ=1.
Mark and Drop Signals
As discussed in [open-ECN], the ECN specification for TCP/IP [RFC3168] stipulates that a packet should only be congestion marked if it would have been dropped, were it unmarkable. It is even stipulated that this assumption should be embedded in implementations, by stating that the ECT flag should only be checked after the decision has been made to drop a packet. Exactly mimicking drop behaviour is motivated by the need to provide incentives for hosts to switch to ECN capability when competing with unmarkable flows.
The [open-ECN] report was an openly published review of the ECN specification during its progress along the IETF's standards track. It agrees with the ECN specification that one ECN mark needs to be equivalent to one drop, but only within the best efforts service, for incremental deployment reasons. For other service disciplines than best efforts, it takes the position of Wischik [WI99] that one ECN mark need not be equivalent to one drop.
Data Centre TCP
Data-centre TCP (DCTCP), proposed by Alizadeh Attar et al. [ALI10] and also discussed in US patent application US2011/0211449 (Attar et al) has shown the considerable benefit of signalling congestion based on the instantaneous length of the queue rather than signalling congestion dependent on a moving average of the queue length. As a result, DCTCP keeps buffers nearly empty nearly all the time, resulting in very low and very predictable delay and extremely low loss-rates, both of which lead to significantly superior performance.
DCTCP is an enhancement of TCP aimed at meeting the requirements of the applications running in data centres, so as to simultaneously achieve high throughput and burst tolerance as well as low latency. It relies on the usage of Explicit Congestion Notification [RFC3168]. The analysis of traffic patterns within Microsoft data centres have shown that even in the absence of the smoothing effects arising from multiplexing, DCTCP can achieve low queuing delay with low variance. DCTCP departs from earlier proposals by prescribing changes both at the senders and within network switches, which can be arranged to be deployed within a data centre where a single entity administers both:                Switch-side: the AQM in switches signals congestion by ECN marking packets based on instantaneous buffer length (i.e. no queue smoothing is carried out in switches as for example in RED). If the queue is greater than a threshold then it marks packets, otherwise it doesn't mark. This can be implemented with a RED AQM in commodity switches with a suitable choice of threshold parameters and the queue averaging parameter set to 1, which effectively turns off averaging.        Sender-side: it reacts to every congestion indication in proportion to congestion levels, i.e. the greater the number of ECN marks observed the greater the reduction in congestion window, Cwnd. The algorithm maintains average α of fraction F of packets marked in each RTT as follows:F=(Number of marked ACKs)/(Total ACKs)α←(1−g)α+g F (where 0<g<1 weight given to new samples)Cwnd←(1−α/2)Cwnd         
DCTCP does not specify what the AQM should do for packets that do not support ECN, because ECN support is enabled by construction of the scheme throughout the data centre.
Phantom Queue
The phantom queue [PR11] is aimed at achieving ultra-low latency solutions, particularly in data centres. The aim is to remove buffering delay from the data centre forwarding fabric by using a virtual queue on the switch (similar to PCN [PCN]) in combination with DCTCP [ALI10] on the end-systems.
Other Techniques
US patent application US2003/0088690 (Zuckerman et al) relates to an AQM process which splits ECN and non-ECN packets into separate queues, then treats them differently. When congestion rises, the rate of ECN-marking on ECN-capable packets is increased. For non-ECN-capable packets, delay is introduced as an alternative to increasing loss.
A paper entitled “A fair AQM scheme for aggregated ECN and non-ECN traffic” by Chong at al [ARQUA] describes a technique called ARQUA-DAB, which applies separate AQM algorithms to ECN and non-ECN traffic. ARQUA-DAB divides the capacity of the real link over two virtual buffers, each with service rates proportional to the number of ECN and non-ECN flows. It runs a substantially similar AQM algorithm in each virtual buffer, the only difference being the rates at which it drains the buffers.
U.S. Pat. No. 7,139,281 relates to a method of active queue management for handling prioritised traffic in a packet transmission system.
US2011292801 relates to a proposed modification to the ECN protocol to allow a receiver terminal to exhibit some control of bandwidth share relative to other receiver terminals.
US2003112814 relates to a system and method for traffic management and regulation in a packet-based communication network which aims to facilitate proactive, discriminating congestion control on a per flow basis of packets traversing the Internet via use of a WRED algorithm that monitors the incoming packet queue and optimises enqueuing or discard of incoming packets to stabilise queue length and promote efficient packet processing.
US2004179479 relates to methods for alleviating traffic congestion by selectively discarding packets in a switch or router. In particular, it is directed to the problem of calculating average queue depth for RED in a manner that responds to rapid increases and decreases in the instantaneous queue depth.