A network scheduler, also called packet scheduler, queueing discipline, qdisc or queueing algorithm, is an arbiter on a node in packet switching communication network. It manages the sequence of network packets in the transmit and receive queues of the network interface controller. There are several network schedulers available for the different operating systems, that implement many of the existing network scheduling algorithms.
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, classification, 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.
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 quality of service (QoS) measures.
Examples of algorithms suitable for managing network traffic include:
- AVQ (adaptive virtual queue)
- CBQ (class-based queueing) discipline
- CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for unresponsive flows) is a variant of RED
- CoDel (controlled delay) and fair/flow queue CoDel
- Credit-based fair queuing
- DRR (deficit round robin) and DWRR, implementation e.g. written by Patrick McHardy for the Linux kernel and published under the GNU General Public License.
- FaQ (FavourQueue)
- GCRA (generic cell rate algorithm)
- 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)
- FIFO (first in, first out)
- pkt_sched: fq: fair queue packet scheduler 
- NETEM network emulator
- PIE (proportional integral controller enhanced)
- RED (random early detection)
- RR (round-robin) and WRR (weighted round robin)
- SFB (stochastic fair blue) as well as RSFB (resilient SFB)
- SFQ (stochastic fairness queuing)
- TBF (token bucket filter)
- TEQL (trivial link equalizer)
Bufferbloat is a phenomenon in packet-switched networks generally, in which excess buffering of packets causes high latency and packet delay variation (also known as jitter), as well as reducing the overall network throughput. When a router device is configured to use excessively large buffers, even very high-speed networks can become practically unusable for many interactive applications like voice calls, chat, and even web surfing.
The CoDel algorithm attempts to reduce this problem by improving upon the RED algorithm. CoDel is less prone to the effects of bufferbloat than the common tail drop disciplines.
||This section is in a list format that may be better presented using prose. (September 2014)|
- Active queue management (AQM) – the employment of an arbiter program
- Network traffic control – an umbrella term for all measures aimed at the control of traffic
- Traffic shaping – a form of AQM, where the available bandwidth is being limited to match certain use cases
- Link sharing – this term is used when more individuals or customers share the same Internet connection
- Traffic prioritizing – a form of AQM, that selectively prioritizes certain network packets (e.g. VoIP-packets)
- TCP Turbo – by prioritizing ACK-packets on the upload, a slow-down of the download rate of a TCP connection is prevented
- Bandwidth management – the management of the available bandwidth
The Linux kernel packet scheduler is configured using the userspace CLI utility called
tc (short for "traffic control"). As the default queuing discipline, the packet scheduler uses a FIFO implementation called pfifo_fast, although systemd since its version 217 changes the default queuing discipline to fq_codel. The packet scheduler is an integral part of the Linux kernel's network stack and manages the ring buffers of all NICs, by working on the layer 2 of the OSI model and handling Ethernet frames, for example. It manages the transmit and receive buffers of all NICs installed in a computer.
The user space programs
ip enable system administrators to configure the buffer sizes
rxqueuelen for each device separately, with their units being 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. The overall size of all buffers has been the point of critique by the Bufferbloat project, which provided a partial solution with CoDel that has been primarily tested in OpenWrt.
eBPF was merged into the Linux kernel mainline in kernel version 3.18, and eBPF filters can also be attached to the packet scheduler's classifiers since the kernel version 4.1. The eBPF functionality brought by version 4.1 of the Linux kernel extends the "classic" BPF programmable classifier by extending its scope to native eBPF code, allowing userspace to implement its own custom, safe, C-like classifiers that can be compiled using the LLVM eBPF backend and loaded into a running kernel using the
tc utility.[better source needed]
Since OpenBSD version 5.5 ALTQ was totally replaced by HFSC scheduler.
- Network congestion
- Quality of service
- Queue (abstract data type)
- Queueing theory
- Statistical time division multiplexing
- Traffic shaping
- Traffic classification
- Type of service
- "Traffic Control HOWTO: Classless Queuing Disciplines (qdiscs)". tldp.org. Retrieved November 24, 2013.
- Saravanan Radhakrishnan (September 30, 1999). "QoS Support in Linux: Queuing Disciplines". qos.ittc.ku.edu. Retrieved March 18, 2014.
- "Traffic Control HOWTO: Components of Linux Traffic Control". tldp.org. Retrieved November 24, 2013.
- "Traffic Control HOWTO: Traditional Elements of Traffic Control". tldp.org. Retrieved November 24, 2013.
- "Queuing Disciplines: Order of Packet Transmission and Dropping" (PDF). tau.ac.il. October 25, 2006. Retrieved March 18, 2014.
- "DRR Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
- "FavorQueue: a Parameterless Active Queue Management to Improve TCP Traffic Performance" (PDF).
- "Heavy-Hitter Filter qdisc". kernel.org.
- "HTB Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
- "QFQ Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
- "Fair Queue packet scheduler committed to Linux kernel 3.12".
- "Network emulator Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
- "Proportional Integral controller Enhanced (PIE)". kernel.org.
- "SFQ Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
- "TBF Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
- "The Linux kernel network scheduler". kernel.org. 2012-12-26. Retrieved 2013-09-07.
- "Linux Advanced Routing and Traffic Control HOWTO, Section 9.2.1. pfifo_fast". lartc.org. 2012-05-19. Retrieved 2014-09-19.
- "systemd System and Service Manager: NEWS file". freedesktop.org. 2015-05-22. Retrieved 2015-06-09.
- "Linux kernel 4.1, Section 11. Networking". kernelnewbies.org. 2015-06-21.
- "Linux kernel packet scheduler#classifiers". wiki.OpenWrt.org.