In packet switching communication networks, a network scheduler, also called packet scheduler, is an arbiter program that manages the sequence of network packets in the transmit and receive queues of the network interface controller, which is a circular data buffer. There are several network schedulers available for the different operating system kernels, that implement many of the existing network scheduling algorithms.
The network scheduler logic decides, in a way similar to statistical multiplexers, which network packet to forward next from the buffer. The buffer works as a queuing system, storing the network packets temporarily until they are transmitted. The buffer space is divided into different queues, using each of them to hold the packets of one flow as classified, for example, by the source and destination IP addresses. Network scheduling algorithms and their associated settings determine how the network scheduler manages the buffer.
Also, network schedulers are enabling accomplishment of the active queue management and traffic shaping.
Network scheduling algorithms
||It has been suggested that Queuing discipline be merged into this section. (Discuss) Proposed since September 2014.|
In the course of time several network scheduling algorithms (also called queueing discipline, qdisc or queueing algorithm) have been developed. Each of the scheduling algorithms used internally for these queuing disciplines 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 the quality of service (QoS) measures.
There is a rough distinction between leaky bucket and token bucket types of algorithms,[dubious ] and between class-based and classless schemes. The head drop discipline CoDel is less prone to the effects of bufferbloat than the common tail drop disciplines.
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 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.
- HFF (Heavy-hitter filter)
- HFSC (Hierarchical Fair Service Curve)
- HTB (Hierarchy Token Bucket)
- QFQ (Quick Fair Queueing)
- FQ (Fair queuing) and WFQ (Weighted fair queuing)
- First In, First Out (FIFO)
- pkt_sched: fq: Fair Queue packet scheduler 
- NETEM Network emulator
- PIE (Proportional integral controller enhanced)
- RED (Random early detection) as well as ARED, GRED, RRED (Robust random early detection) und WRED (Weighted random early detection)
- RR (Round-robin) and WRR (Weighted round robin)
- SFB (Stochastic Fair Blue) as well as 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.
||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 currently available network scheduler for the Linux kernel is an integral part of the Linux network stack; it arbiters the ring buffers of all NICs, hence it works on layer 2 of the OSI model and handles Ethernet frames. It manages the transmit and receive buffers of all present NICs.
The user space programs
ip enable the system administrator to regulate the buffer sizes:
rxqueuelen; the unit being number of Ethernet frames (regardless of their size) for each device separately. The Linux 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. The project provided a partial solution with CoDel, which was primarily tested in OpenWrt.
- Network congestion
- Quality of service
- Queue (abstract data type)
- Queueing theory
- Statistical time division multiplexing
- Traffic shaping
- Traffic classification
- Type of service
- Classless Queuing Disciplines (qdiscs). "Traffic Control HOWTO". tldp.org. Retrieved November 24, 2013.
- Saravanan Radhakrishnan (September 30, 1999). Queuing Disciplines. "QoS Support in Linux". qos.ittc.ku.edu. Retrieved March 18, 2014.
- Components of Linux Traffic Control. "Traffic Control HOWTO". tldp.org. Retrieved November 24, 2013.
- Traditional Elements of Traffic Control. "Traffic Control HOWTO". 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.
- "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.
- 9.2.1. pfifo_fast. "Linux Advanced Routing and Traffic Control HOWTO". lartc.org. 2012-05-19. Retrieved 2014-09-19.