Misplaced Pages

#925074

24-453: 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 implemented on BSD-based routers . ALTQ is included in the base distribution of FreeBSD , NetBSD , and DragonFly BSD , and was integrated into the pf packet filter of OpenBSD but later replaced by

48-426: A circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited as a FIFO ( first in, first out ) buffer while a standard, non-circular buffer is well suited as a LIFO ( last in, first out ) buffer. Circular buffering makes

72-485: A good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a linked list approach may be preferred instead. In some situations, overwriting circular buffer can be used, e.g. in multimedia. If

96-430: A maximum in-use size of Length - 1. In this case, the buffer is empty if the start and end indexes are equal and full when the in-use size is Length - 1. Another solution is to have another integer count that is incremented at a write operation and decremented at a read operation. Then checking for emptiness means testing count equals 0 and checking for fullness means testing count equals Length. The following source code

120-576: A new queueing subsystem (it was deprecated with OpenBSD 5.5 release, and completely removed with 5.6 in 2014). With ALTQ, packets can be assigned to queues for the purpose of bandwidth control . The scheduler defines the algorithm used to decide which packets get delayed, dropped or sent out immediately. There are five schedulers currently supported in the FreeBSD implementation of ALTQ: Network scheduler The network scheduler logic decides which network packet to forward next. The network scheduler

144-572: A very specialized circular buffer with exactly two large fixed-length elements. The bip buffer (bipartite buffer) is very similar to a circular buffer, except it always returns contiguous blocks which can be variable length. This offers nearly all the efficiency advantages of a circular buffer while maintaining the ability for the buffer to be used in APIs that only accept contiguous blocks. Fixed-sized compressed circular buffers use an alternative indexing strategy based on elementary number theory to maintain

168-426: 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 . There were early circular buffer implementations in hardware. A circular buffer first starts out empty and has a set length. In the diagram below is a 7-element buffer: Assume that 1 is written in the center of a circular buffer (the exact starting location

192-416: Is a C implementation together with a minimal test. Function put() puts an item in the buffer, function get() gets an item from the buffer. Both functions take care about the capacity of the buffer : A circular-buffer implementation may be optimized by mapping the underlying buffer to two contiguous regions of virtual memory . (Naturally, the underlying buffer‘s length must then equal some multiple of

216-559: 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 , although systemd since its version 217 changes the default queuing discipline to fq_codel . The ifconfig and ip utilities enable system administrators to configure

240-476: 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

264-596: 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 . A network scheduler may have responsibility in implementation of specific network traffic control initiatives. Network traffic control

SECTION 10

#1732855830926

288-443: Is not important in a circular buffer): Then assume that two more elements are added to the circular buffer — 2 & 3 — which get put after 1: If two elements are removed, the two oldest values inside of the circular buffer would be removed. Circular buffers use FIFO ( first in, first out ) logic. In the example, 1 & 2 were the first to enter the circular buffer, they are the first to be removed, leaving 3 inside of

312-520: The latency for certain classes of network packets, and are generally used as part of QoS measures. 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. Examples of algorithms suitable for managing network traffic include: Several of

336-479: The above have been implemented as Linux kernel modules and are freely available . 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 . The Linux kernel packet scheduler

360-463: The buffer is used as the bounded buffer in the producer–consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card ) is unable to momentarily keep up. Also, the LZ77 family of lossless data compression algorithms operates on the assumption that strings seen more recently in a data stream are more likely to occur soon in

384-429: 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 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

408-405: The buffer. If the buffer has 7 elements, then it is completely full: A property of the circular buffer is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In the current example, two more elements — A & B — are added and they overwrite the 3 & 4: Alternatively, the routines that manage the buffer could prevent overwriting

432-507: The classic BPF programmable classifiers to eBPF. These can be compiled using the LLVM eBPF backend and loaded into a running kernel using the tc utility. ALTQ is the implementation of a network scheduler for BSDs . As of OpenBSD version 5.5 ALTQ was replaced by the HFSC scheduler. Ring buffer In computer science , a circular buffer , circular queue , cyclic buffer or ring buffer

456-407: The data and return an error or raise an exception . Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer. Finally, if two elements are now removed then what would be removed is not 3 & 4 (or rather now A & B) but 5 & 6 because 5 & 6 are now the oldest elements, yielding the buffer with: The useful property of

480-403: The end index position and the end index is incremented to the next buffer position. The circular buffer read operation reads an element from the start index position and the start index is incremented to the next buffer position. The start and end indexes alone are not enough to distinguish between buffer full or empty state while also utilizing all buffer slots, but can be if the buffer only has

504-538: The length of the underlying buffer. Perhaps the most common version of the circular buffer uses 8-bit bytes as elements. Some implementations of the circular buffer use fixed-length elements that are bigger than 8-bit bytes—16-bit integers for audio buffers, 53-byte ATM cells for telecom buffers, etc. Each item is contiguous and has the correct data alignment , so software reading and writing these values can be faster than software that handles non-contiguous and non-aligned values. Ping-pong buffering can be considered

SECTION 20

#1732855830926

528-429: The stream. Implementations store the most recent data in a circular buffer. A circular buffer can be implemented using a pointer and three integers: This image shows a partially full buffer with Length = 7: This image shows a full buffer with four elements (numbers 1 through 4) having been overwritten: In the beginning the indexes end and start are set to 0. The circular buffer write operation writes an element to

552-425: The system’s page size .) Reading from and writing to the circular buffer may then be carried out with greater efficiency by means of direct memory access; those accesses which fall beyond the end of the first virtual-memory region will automatically wrap around to the beginning of the underlying buffer. When the read offset is advanced into the second virtual-memory region, both offsets—read and write—are decremented by

576-513: 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 ). 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

#925074