First Input First Output

Description

First Input First Output (FIFO) is a classic queuing algorithm employed within various protocol layers of the 3GPP radio access and core network stack. It operates on a simple principle: entities (like data packets or protocol data units) are stored in a buffer, and the entity that has been waiting the longest (the first one in) is the next to be processed or transmitted (the first one out). This creates a strict temporal ordering. In 3GPP specifications, FIFO behavior is often the default or a mandated mode for certain channels and bearers, particularly for acknowledging mode (AM) in the Radio Link Control (RLC) layer.

At the RLC layer, for an AM data bearer, the transmitter maintains a transmission buffer. PDCP PDUs are delivered to RLC and segmented into RLC SDUs if necessary. These are stored and transmitted in FIFO order. The receiver side also uses FIFO principles in its reassembly buffer to reorder received RLC PDUs before delivering them in sequence to the upper PDCP layer. This guarantees in-sequence delivery to the higher layers, which is a fundamental requirement for many TCP-based applications. The specifications (e.g., TS 36.323, TS 38.323) detail procedures like window-based flow control and ARQ retransmissions that work in conjunction with this FIFO buffering.

Beyond RLC, FIFO concepts apply to scheduling queues in the MAC layer, buffering in user plane gateways, and traffic management functions. While advanced schedulers use complex algorithms for QoS prioritization, FIFO remains a critical component for flows designated as non-GBR (Guaranteed Bit Rate) or default bearers, where simple fairness is acceptable. Its implementation is computationally lightweight, requiring minimal state management compared to priority queues. However, its simplicity is also a limitation, as it does not prioritize delay-sensitive traffic, making it unsuitable for real-time services without additional QoS mechanisms at a higher layer.

Purpose & Motivation

FIFO exists as a foundational, reliable method for managing data queues in telecommunications systems. Its primary purpose is to ensure predictable, in-order delivery of data units, which is a basic requirement for error-free communication. Before the adoption of sophisticated QoS-aware schedulers, FIFO was the de facto method for handling all traffic, providing a simple form of fairness where all data flows get served in turn based on arrival time.

In 3GPP systems, it was standardized to provide a clear, interoperable baseline behavior for protocol entities like the RLC layer. This solves the problem of how to reliably reconstruct a data stream from potentially out-of-order or retransmitted packets over an unreliable radio link. The FIFO discipline at the receiver, combined with sequence numbers, allows the RLC layer to deliver a perfect, sequential stream to the PDCP layer, hiding the complexities of the radio interface from upper-layer protocols.

Its continued specification addresses the need for a low-complexity, robust fallback mechanism. For certain types of background or best-effort traffic, the overhead of complex priority queuing is unnecessary. FIFO provides a guaranteed behavior that is easy to implement, test, and debug. It serves as the reference model against which more advanced scheduling algorithms (like Proportional Fair, QoS-based) are compared and optimized, ensuring that even the most basic implementation maintains network stability and data integrity.