Network scheduler

For the scheduling of processes, see process scheduler.
Packets queuing in a FIFO (first in, first out) data structure.

A network scheduler, also called packet scheduler, is an arbiter program 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, 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 may be divided into different queues, with each of them holding the packets of one flow according to configured packet classification rules; for example, packets can be divided into flows by their 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

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.[1][2] 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.[3][4][5]

Examples of algorithms suitable for managing network traffic include:

Several of the above have been implemented as Linux kernel modules[17] and are freely available.

Bufferbloat

Main article: Bufferbloat

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.

Terminology

Implementations

Linux kernel

The Linux kernel packet scheduler is somewhere in the network stack together with netfilter, nftables and the Berkeley Packet Filter.

The Linux kernel packet scheduler is configured with the user-space CLI utility program tc (traffic control). As the default queuing discipline, it uses a FIFO implementation called pfifo_fast,[18] although systemd since its version 217 changes the default queuing discipline to fq_codel.[19] The Linux kernel packet scheduler is an integral part of the Linux kernel network stack and manages the ring buffers of all NICs, by working on the layer 2 of the OSI model and handling e.g. Ethernet frames. It manages the transmit and receive buffers of all NICs installed in a computer.

The user space programs ifconfig and ip enable system administrators to configure the buffer sizes txqueuelen and 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.

Another network scheduler is being developed as part of Netfilter and nftables.

eBPF was mainlined into Linux kernel 3.18 and since Linux kernel version 4.1, eBPF filters can be attached to the Linux kernel packet scheduler's classifiers.[20] To be more precise, the patches to the eBPF mainlined into for 4.1 extend the "classic" BPF programmable tc classifier by extending its scope also to native eBPF code, thus allowing userspace to implement own custom, 'safe' C like classifiers that can then be compiled with the LLVM eBPF back-end to an eBPF elf file and loaded into the kernel via iproute2's tc, and be JITed in the kernel.[21]

BSD

ALTQ is the implementation of a network scheduler for BSDs. It is not to be confused with the Berkeley Packet Filter.

See also

References

  1. "Traffic Control HOWTO: Classless Queuing Disciplines (qdiscs)". tldp.org. Retrieved November 24, 2013.
  2. Saravanan Radhakrishnan (September 30, 1999). "QoS Support in Linux: Queuing Disciplines". qos.ittc.ku.edu. Retrieved March 18, 2014.
  3. "Traffic Control HOWTO: Components of Linux Traffic Control". tldp.org. Retrieved November 24, 2013.
  4. "Traffic Control HOWTO: Traditional Elements of Traffic Control". tldp.org. Retrieved November 24, 2013.
  5. "Queuing Disciplines: Order of Packet Transmission and Dropping" (PDF). tau.ac.il. October 25, 2006. Retrieved March 18, 2014.
  6. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.4477&rep=rep1&type=pdf
  7. "DRR Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
  8. "FavorQueue: a Parameterless Active Queue Management to Improve TCP Traffic Performance" (PDF).
  9. "Heavy-Hitter Filter qdisc". kernel.org.
  10. "HTB Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
  11. "QFQ Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
  12. "Fair Queue packet scheduler committed to Linux kernel 3.12".
  13. "Network emulator Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
  14. "Proportional Integral controller Enhanced (PIE)". kernel.org.
  15. "SFQ Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
  16. "TBF Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
  17. "The Linux kernel network scheduler". kernel.org. 2012-12-26. Retrieved 2013-09-07.
  18. "Linux Advanced Routing and Traffic Control HOWTO, Section 9.2.1. pfifo_fast". lartc.org. 2012-05-19. Retrieved 2014-09-19.
  19. "systemd System and Service Manager: NEWS file". freedesktop.org. 2015-05-22. Retrieved 2015-06-09.
  20. "Linux kernel 4.1, Section 11. Networking". kernelnewbies.org. 2015-06-21.
  21. "Linux kernel packet scheduler#classifiers". wiki.OpenWrt.org.
This article is issued from Wikipedia - version of the Tuesday, April 19, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.