![Data Queue](https://upload.wikimedia.org/wikipedia/commons/5/52/Data_Queue.svg)
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an
arbiter on a
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines, ...
in a
packet switching
In telecommunications, packet switching is a method of grouping Data (computing), data into ''network packet, packets'' that are transmitted over a digital Telecommunications network, network. Packets are made of a header (computing), header and ...
communication network. It manages the sequence of
network packet
In telecommunications and computer networking, a network packet is a formatted unit of data carried by a packet-switched network. A packet consists of control information and user data; the latter is also known as the ''payload''. Control informa ...
s in the transmit and receive
queues of the
protocol stack
The protocol stack or network stack is an implementation of a computer networking protocol suite or protocol family. Some of these terms are used interchangeably but strictly speaking, the ''suite'' is the definition of the communication protoco ...
and
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 ...
. There are several network schedulers available for the different
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
s, that implement many of the existing network
scheduling algorithm
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 ...
s.
The network scheduler logic decides which network packet to forward next. The network scheduler is associated with a queuing system, storing the network packets temporarily until they are transmitted. Systems may have a single or multiple queues in which case each may hold the packets of one
flow
Flow may refer to:
Science and technology
* Fluid flow, the motion of a gas or liquid
* Flow (geomorphology), a type of mass wasting or slope movement in geomorphology
* Flow (mathematics), a group action of the real numbers on a set
* Flow (psych ...
,
classification Classification is a process related to categorization, the process in which ideas and objects are recognized, differentiated and understood.
Classification is the grouping of related facts into classes.
It may also refer to:
Business, organizat ...
, or priority.
In some cases it may not be possible to schedule all transmissions within the constraints of the system. In these cases the network scheduler is responsible for deciding which traffic to forward and what gets
dropped.
Terminology and responsibilities
A network scheduler may have responsibility in implementation of specific
network traffic control
In computer networking, network traffic control is the process of managing, controlling or reducing the network traffic, particularly Internet bandwidth, e.g. by the network scheduler.M. Noormohammadpour, C. S. Raghavendra"Datacenter Traffic Con ...
initiatives. Network traffic control is an umbrella term for all measures aimed at reducing
network congestion
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 ...
, latency and packet loss. Specifically,
active queue management
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 i ...
(AQM) is the selective dropping of queued network packets to achieve the larger goal of preventing excessive network congestion. The scheduler must choose which packets to drop.
Traffic shaping
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, improv ...
smooths the bandwidth requirements of traffic flows by delaying transmission packets when they are queued in bursts. The scheduler decides the timing for the transmitted packets.
quality of service
Quality of service (QoS) is the description or measurement of the overall performance of a service, such as a telephony or computer network, or a cloud computing service, particularly the performance seen by the users of the network. To quantitat ...
(QoS) is the prioritization of traffic based on service class (
Differentiated services
Differentiated services or DiffServ is a computer networking architecture that specifies a mechanism for classifying and managing network traffic and providing quality of service (QoS) on modern IP networks. DiffServ can, for example, be used t ...
) or reserved connection (
Integrated services In computer networking, integrated services or IntServ is an architecture that specifies the elements to guarantee quality of service (QoS) on networks. IntServ can for example be used to allow video and sound to reach the receiver without interrup ...
).
Algorithms
In the course of time many network queueing disciplines have been developed. Each of these provides specific reordering or dropping of network packets inside various transmit or receive
buffers.
Queuing disciplines are commonly used as attempts to compensate for various networking conditions, like reducing the
latency for certain classes of network packets, and are generally used as part of QoS measures.
Examples of algorithms suitable for managing network traffic include:
* AVQ (
adaptive virtual queue
Adaptation, in biology, is the process or trait by which organisms or population better match their environment
Adaptation may also refer to:
Arts
* Adaptation (arts), a transfer of a work of art from one medium to another
** Film adaptation, a ...
)
* CBQ (
class-based queueing Class-based queuing (CBQ) is a queuing discipline for the network scheduler that allows traffic to share bandwidth equally, after being grouped by classes. The classes can be based upon a variety of parameters, such as priority, interface, or origin ...
) discipline
* CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for unresponsive flows) is a variant of RED
*
CoDel
CoDel (''Controlled Delay''; pronounced "coddle") 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 har ...
(controlled delay) and
FQ-CoDel (flow queue CoDel)
*
CAKE
Cake is a flour confection made from flour, sugar, and other ingredients, and is usually baked. In their oldest forms, cakes were modifications of bread, but cakes now cover a wide range of preparations that can be simple or elaborate, ...
(Common Applications Kept Enhanced), implemented in linux kernel
*
Credit-based fair queuing
Credit-based fair queuing is a computationally efficient alternative to fair queueing. Credit is accumulated to queues as they wait for service. Credit is spent by queues while they are being serviced. Queues with positive credit are eligible fo ...
* DRR (
deficit round robin
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) poli ...
) and DWRR, implementation e.g. written by Patrick McHardy for 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 ...
and published under the
GNU General Public License
The GNU General Public License (GNU GPL or simply GPL) is a series of widely used free software licenses that guarantee end users the Four Freedoms (Free software), four freedoms to run, study, share, and modify the software. The license was th ...
.
* FaQ (FavourQueue)
* FQ-PIE (Flow Queue Proportional Integral controller Enhanced)
* GCRA (
generic cell rate algorithm The generic cell rate algorithm (GCRA) is a leaky bucket-type scheduling algorithm for the network scheduler that is used in Asynchronous Transfer Mode (ATM) networks. It is used to measure the timing of cells on virtual channels (VCs) and or Virt ...
)
* HFF (
heavy-hitter filter)
* HFSC (
hierarchical fair-service curve)
* HTB (
hierarchical token bucket)
* QFQ (
quick fair queueing)
* FQ (
fair queuing) and WFQ (
weighted fair queuing
Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in ...
)
* FIFO (
first in, first out)
* pkt_sched: fq: fair queue packet scheduler
* NETEM network emulator
* PIE (
proportional integral controller enhanced)
* RED (
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 b ...
)
** ARED (
advanced random early detection)
** GRED (
generalized random early detection)
** RRED (
robust random early detection 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 ...
)
** WRED (
weighted random early detection
Weighted random early detection (WRED) is a queueing discipline for a network scheduler suited for congestion avoidance. It is an extension to random early detection (RED) where a single queue may have several different sets of queue thresholds. Ea ...
)
* RR (
round-robin) and WRR (
weighted round robin
Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes.
Weighted round robin is a generalisation of round-robin scheduling. It serves a set of queues or tasks. Whereas round-robin cycles over the q ...
)
* SFB (
stochastic fair blue) as well as RSFB (resilient SFB)
* (stochastic fairness queuing)
* TBF (
token bucket filter)
* TEQL (
trivial link equalizer)
Several of the above have been implemented as
Linux kernel module
In computing, a loadable kernel module (LKM) is an object file that contains code to extend the running kernel, or so-called ''base kernel'', of an operating system. LKMs are typically used to add support for new hardware (as device drivers) and/o ...
s and are
freely available.
Bufferbloat
Bufferbloat
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 (also known as jitter), as well as reduce the overall network throughput. ...
is a phenomenon in packet-switched networks in which excess
buffer
Buffer may refer to:
Science
* Buffer gas, an inert or nonflammable gas
* Buffer solution, a solution used to prevent changes in pH
* Buffering agent, the weak acid or base in a buffer solution
* Lysis buffer, in cell biology
* Metal ion buffer
* ...
ing of packets causes high
latency and
packet delay variation
In computer networking, packet delay variation (PDV) is the difference in end-to-end one-way delay between selected packets in a flow with any lost packets being ignored.RFC 3393 The effect is sometimes referred to as packet jitter, although t ...
. Bufferbloat can be addressed by a network scheduler that strategically discards packets to avoid an unnecessarily high buffering backlog. Examples include
CoDel
CoDel (''Controlled Delay''; pronounced "coddle") 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 har ...
,
FQ-CoDel and
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 b ...
.
Implementations
Linux kernel
![Simplified Structure of the Linux Kernel](https://upload.wikimedia.org/wikipedia/commons/6/65/Simplified_Structure_of_the_Linux_Kernel.svg)
The Linux kernel packet scheduler is an integral part of the Linux kernel's network stack and manages the transmit and receive
ring buffer
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. Ther ...
s of all NICs, by working on the
layer 2
The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking. This layer is the protocol layer that transfers data between nodes on a network segment across the physical layer. The data link layer pr ...
of the
OSI model
The Open Systems Interconnection model (OSI model) is a conceptual model that 'provides a common basis for the coordination of SOstandards development for the purpose of systems interconnection'. In the OSI reference model, the communications ...
and handling
Ethernet frame
In computer networking, an Ethernet frame is a data link layer protocol data unit and uses the underlying Ethernet physical layer transport mechanisms. In other words, a data unit on an Ethernet link transports an Ethernet frame as its payload.
...
s, for example.
The packet scheduler is configured using the utility called
tc
(short for "traffic control"). As the default queuing discipline, the packet scheduler uses a FIFO implementation called ''pfifo_fast'', although
systemd
systemd is a software suite that provides an array of system components for Linux operating systems. Its main aim is to unify service configuration and behavior across Linux distributions; Its primary component is a "system and service manager ...
since its version 217 changes the default queuing discipline to
fq_codel
.
The
ifconfig
ifconfig (short for ''interface config'') is a system administration utility in Unix-like operating systems for network interface configuration.
The utility is a command-line interface tool and is also used in the system startup scripts of man ...
and
ip
utilities enable system administrators to configure the buffer sizes
txqueuelen
and
rxqueuelen
for each device separately in terms of number of Ethernet frames regardless of their size. The Linux kernel's network stack contains several other buffers, which are not managed by the network scheduler.
Berkeley Packet Filter
The Berkeley Packet Filter (BPF) is a technology used in certain computer operating systems for programs that need to, among other things, analyze network traffic. It provides a raw interface to data link layers, permitting raw link-layer packets ...
filters can be attached to the packet scheduler's classifiers. The
eBPF
eBPF (often aliased BPF) is a technology that can run sandboxed programs in a privileged context such as the operating system kernel. It is used to safely and efficiently extend the capabilities of the kernel at runtime without requiring to chan ...
functionality brought by version 4.1 of the Linux kernel in 2015 extends the classic BPF programmable classifiers to eBPF. These can be compiled using the
LLVM
LLVM is a set of compiler and toolchain technologies that can be used to develop a front end for any programming language and a back end for any instruction set architecture. LLVM is designed around a language-independent intermediate represen ...
eBPF backend and loaded into a running kernel using the
tc
utility.
BSD and OpenBSD
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 implemen ...
is the implementation of a network scheduler for
BSDs
There are a number of Unix-like operating systems under active development, descended from the Berkeley Software Distribution (BSD) series of UNIX variants developed (originally by Bill Joy) at the University of California, Berkeley Electrical Eng ...
. As of OpenBSD version 5.5 ALTQ was replaced by the HFSC scheduler.
See also
*
Queueing theory
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
*
Statistical time division multiplexing
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation (DBA). In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bitrate digital channels or ...
*
Type of service
Notes
References
{{Computer science
Linux kernel features
Network performance
Network scheduling algorithms
Network theory