Blue is a

scheduling discipline In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows. The scheduling activity is c ...

for the

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 q ...

developed by graduate student Wu-chang Feng for Professor Kang G. Shin at the

University of Michigan , mottoeng = "Arts, Knowledge, Truth" , former_names = Catholepistemiad, or University of Michigania (1817–1821) , budget = $10.3 billion (2021) , endowment = $17 billion (2021)As o ...

and others at the

Thomas J. Watson Research Center The Thomas J. Watson Research Center is the headquarters for IBM Research. The center comprises three sites, with its main laboratory in Yorktown Heights, New York, U.S., 38 miles (61 km) north of New York City, Albany, New York and wit ...

of IBM in 1999.

Functioning

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 the conventional tail drop algorithm, a router or other network component ...

(RED), Blue operates by randomly dropping or marking packet with

explicit congestion notification 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 ...

mark before the transmit buffer of the

network interface controller A network interface controller (NIC, also known as a network interface card, network adapter, LAN adapter or physical network interface, and by similar terms) is a computer hardware component that connects a computer to a computer network. Ear ...

overflows. Unlike RED, however, it requires little or no tuning to be performed by the network administrator. A Blue queue maintains a drop/mark probability ''p'', and drops/marks packets with probability ''p'' as they enter the queue. Whenever the queue overflows, ''p'' is increased by a small constant ''p_i'', and whenever the queue is empty, ''p'' is decreased by a constant ''p_d < p_i''. If the mix of traffic on the interface does not change, ''p'' will slowly converge to a value that keeps the queue within its bounds with full link utilization.

Stochastic fair Blue

The main flaw of Blue, which it shares with most single-queue

queuing discipline 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 q ...

s, is that it does not distinguish between

traffic flows In mathematics and transportation engineering, traffic flow is the study of interactions between travellers (including pedestrians, cyclists, drivers, and their vehicles) and infrastructure (including highways, signage, and traffic control devi ...

, but treats all flows as a single aggregate. Therefore, a single aggressive flow can push packets out of the queue belonging to other, better behaved, flows. Stochastic fair Blue (SFB) is a stochastically fair variant of Blue which hashes flows and maintains a different mark/drop probability for each hash value. Assuming no hash collisions, SFB is able to provide a fair share of buffer space for every flow. In the presence of hash collisions, SFB is only stochastically fair. Unlike other stochastically fair queuing disciplines, such as SFQ (

Stochastic Fairness Queuing 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 q ...

), SFB can be implemented using a

bloom filter A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in ...

rather than a

hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...

, which dramatically reduces its storage requirements when the number of flows is large. When a flow's drop/mark probability reaches 1, the flow has been shown to not react to congestion indications from the network. Such an inelastic flow is put in a "

penalty box The penalty box or sin bin (sometimes called the bad box, or simply bin or box) is the area in ice hockey, rugby union, rugby league, roller derby and some other sports where a player sits to serve the time of a given penalty, for an offence not ...

", and rate-limited.

Resilient stochastic fair Blue

Many scheduling algorithms, including the fairness-aimed ones, are notably vulnerable to spoofing

distributed denial-of-service In computing, a denial-of-service attack (DoS attack) is a cyber-attack in which the perpetrator seeks to make a machine or network resource unavailable to its intended users by temporarily or indefinitely disrupting services of a host connect ...

(DDoS) attacks. A resilient stochastic fair Blue (RSFB) algorithm was proposed in 2009 against spoofing DDoS attacks. The basic idea behind RSFB is to record the responsive normal TCP flows and rescue their dropped packets. RSFB algorithm is effective in preserving the TCP throughput in the presence of spoofing DDoS attacks.Abstract
/ref>

Implementations

An implementation of Blue is part of

ALTQ ALTQ (ALTernate Queueing) is the network scheduler for Berkeley Software Distribution. ALTQ provides queueing disciplines, and other components related to quality of service (QoS), required to realize resource sharing. It is most commonly impleme ...

, the

for BSD Unix. An implementation of SFB for

Linux Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...

was included in the

Linux kernel The Linux kernel is a free and open-source, monolithic, modular, multitasking, Unix-like operating system kernel. It was originally authored in 1991 by Linus Torvalds for his i386-based PC, and it was soon adopted as the kernel for the GNU ope ...

in version 2.6.39.

References

{{Reflist Packets (information technology) Network performance