Network scheduler#BSD
{{Short description|Arbiter on a node in packet switching communication network}}
{{About|scheduling in networking|scheduling in computing generally|Scheduling (computing)}}
File:Data Queue.svg (first in, first out) data structure.]]
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.
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.
Terminology and responsibilities
A network scheduler may have responsibility in implementation of specific network traffic control initiatives. Network traffic control is an umbrella term for all measures aimed at reducing network congestion, latency and packet loss. Specifically, active queue management (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 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 (QoS) is the prioritization of traffic based on service class (Differentiated services) or reserved connection (Integrated services).
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.{{cite web
| url = http://www.tldp.org/HOWTO/Traffic-Control-HOWTO/classless-qdiscs.html
| title = Traffic Control HOWTO: Classless Queuing Disciplines (qdiscs)
| access-date = November 24, 2013
| website = tldp.org
}}
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.{{cite web
| url = http://www.tldp.org/HOWTO/Traffic-Control-HOWTO/components.html
| title = Traffic Control HOWTO: Components of Linux Traffic Control
| access-date = November 24, 2013
| website = tldp.org
| url = http://www.tldp.org/HOWTO/Traffic-Control-HOWTO/elements.html
| title = Traffic Control HOWTO: Traditional Elements of Traffic Control
| access-date = November 24, 2013
| website = tldp.org
| url = http://www.eng.tau.ac.il/~netlab/resources/booklet/lab9.pdf
| title = Queuing Disciplines: Order of Packet Transmission and Dropping
| date = October 25, 2006 | access-date = March 18, 2014
| website = tau.ac.il }}
Classful queueing disciplines allow the creation of classes, which work like branches on a tree. Rules can then be set to filter packets into each class. Each class can itself have assigned other classful or classless queueing discipline. Classless queueing disciplines do not allow adding more queueing disciplines to it.{{Cite web |title=Advanced traffic control - ArchWiki |url=https://wiki.archlinux.org/title/advanced_traffic_control |access-date=2023-09-11 |website=wiki.archlinux.org}}
Examples of algorithms suitable for managing network traffic include:
Several of the above have been implemented as Linux kernel modules{{cite web|url=https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/net/sched|title=The Linux kernel network scheduler|publisher=kernel.org|date=2012-12-26|access-date=2013-09-07}}{{Cite web |title=tc(8) - Linux manual page |url=https://man7.org/linux/man-pages/man8/tc.8.html |access-date=2023-09-11 |website=man7.org}} and are freely available.
Bufferbloat
Bufferbloat is a phenomenon in packet-switched networks in which excess buffering of packets causes high latency and packet delay variation. Bufferbloat can be addressed by a network scheduler that strategically discards packets to avoid an unnecessarily high buffering backlog. Examples include CoDel, FQ-CoDel and random early detection.
Implementations
{{expand section|reason=What about network equipment, non-Unix-like OSs?|date=October 2018}}
= Linux kernel =
File:Simplified Structure of the Linux Kernel.svg, nftables, and Berkeley Packet Filter.]]
The Linux kernel packet scheduler is an integral part of the Linux kernel's network stack and manages the transmit and receive ring buffers of all NICs.
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,{{cite web
| url = http://www.lartc.org/howto/lartc.qdisc.classless.html
| title = Linux Advanced Routing and Traffic Control HOWTO, Section 9.2.1. pfifo_fast
| date = 2012-05-19 | access-date = 2014-09-19
| website = lartc.org
}} although systemd since its version 217 changes the default queuing discipline to fq_codel.{{cite web
| url = http://cgit.freedesktop.org/systemd/systemd/tree/NEWS
| title = systemd System and Service Manager: NEWS file
| date = 2015-05-22 | access-date = 2015-06-09
| website = freedesktop.org
}}
The ifconfig 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.{{efn|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.}}
Berkeley Packet Filter filters can be attached to the packet scheduler's classifiers. The eBPF functionality brought by version 4.1 of the Linux kernel in 2015 extends the classic BPF programmable classifiers to eBPF.{{cite web |url=http://kernelnewbies.org/Linux_4.1#head-c64a7aa1ccb73618b4a7b5f3bef64ff435738098 |title=Linux kernel 4.1, Section 11. Networking |date=2015-06-21 |website = kernelnewbies.org}} These can be compiled using the LLVM eBPF backend and loaded into a running kernel using the tc utility.{{cite web |url=https://cilium.readthedocs.io/en/latest/bpf/ |title=BPF and XDP Reference Guide |website=Cilium documentation web site}}
= BSD and OpenBSD =
= Cell-Free Network Scheduling =
Schedulers in communication networks manage resource allocation, including packet prioritization, timing, and resource distribution. Advanced implementations increasingly leverage artificial intelligence to address the complexities of modern network configurations. For instance, a supervised neural network (NN)-based scheduler has been introduced in cell-free networks to efficiently handle interactions between multiple radio units (RUs) and user equipment (UEs). This approach reduces computational complexity while optimizing latency, throughput, and resource allocation, making it a promising solution for beyond-5G networks. {{cite journal
| last1 = Huleihel
| first1 = Yara
| last2 = Maman
| first2 = Gil
| last3 = Hadad
| first3 = Zion
| last4 = Shasha
| first4 = Eli
| last5 = Permuter
| first5 = Haim H.
| title = Data-driven cell-free scheduler
| journal = Ad Hoc Networks
| volume = 169
| pages = 103738
| year = 2025
| publisher = Elsevier
| doi = 10.1016/j.adhoc.2025.103738
}}
See also
Notes
{{Notelist}}
References
{{Reflist}}
{{Computer science}}
Category:Linux kernel features