Nagle's algorithm

Nagle's algorithm. It is a TCP congestion control method created by John Nagle while working at Ford Aerospace. The algorithm was designed to reduce the number of small, inefficient packets, known as packets, on a network by coalescing small amounts of data. It combats a problem termed Silly window syndrome, which can degrade network performance by allowing the transmission of packets carrying very little application data relative to their header overhead. The algorithm's deployment became widespread, notably within the BSD TCP/IP stack, influencing many modern operating systems.

Overview

The algorithm was formulated in response to inefficiencies observed in early ARPANET applications, such as Telnet, which often sent single keystrokes as individual packets. This behavior, exacerbated by certain remote procedure call implementations, could lead to network congestion. The core principle involves buffering small outgoing segments if there is already an unacknowledged packet in flight. This simple rule prevents a sender from flooding the network with tiny datagrams, thereby improving the ratio of payload to TCP and IP header data. Its development was contemporaneous with other key IETF standards and congestion control mechanisms like Van Jacobson's work.

Operation

The algorithm's logic is governed by a straightforward conditional check within the TCP/IP stack of the sending host. When an application performs a write operation, the resulting data is not immediately transmitted if any previously sent data remains unacknowledged by the receiver. Instead, the new data is buffered locally. Transmission occurs only when an ACK is received for the outstanding data, or when the buffered data accumulates to form a full-sized maximum segment size packet. This mechanism interacts directly with the socket-level option TCP_NODELAY, which allows applications like the X Window System or real-time games to disable the algorithm for low-latency needs.

Interaction with the TCP delayed acknowledgment

A significant interaction occurs with another common optimization, the TCP delayed acknowledgment algorithm, standardized in RFC 1122. This algorithm, employed by the receiving host, intentionally delays sending ACK packets for a brief period, often 200 milliseconds, hoping to combine the ACK with an outgoing data segment or to acknowledge multiple incoming segments at once. When both algorithms are enabled, they can create a detrimental feedback loop: the sender waits for an ACK before releasing more data, while the receiver waits for more data before sending an ACK. This scenario, sometimes called a form of deadlock, can introduce noticeable latency, particularly in client-server applications such as HTTP.

Effects on performance

In bulk data transfer scenarios, such as FTP sessions or large HTTP downloads, Nagle's algorithm is generally beneficial by ensuring larger, more efficient packets are sent. However, for interactive applications requiring real-time feedback, like SSH keystrokes or online gaming via protocols such as Quake, the buffering delay can harm user experience. The performance impact is highly dependent on network round-trip time and application behavior. Studies and experiences from companies like Microsoft and Google have documented these trade-offs, leading to recommendations in various RFC documents for application developers to carefully consider their use of the TCP_NODELAY option.

Alternatives and modifications

Several alternatives and modifications have been proposed to mitigate the algorithm's drawbacks. One common approach is for applications to use the TCP_NODELAY socket option to disable it entirely, a practice employed by the Linux kernel for certain sockets and by many video game engines. Another strategy is to use buffer-writing techniques, such as corking, which allows an application to explicitly decide when to flush data. The Linux kernel also implements a hybrid approach sometimes called `TCP_CORK`. Furthermore, modern protocols like QUIC, developed by Google, avoid this issue entirely by operating over UDP and implementing their own congestion control without head-of-line blocking. Research continues within the IETF and groups like the IRTF to refine transport layer mechanisms.

Category:Network protocols Category:Internet architecture Category:Algorithms