Nagle's algorithm

From Wikipedia, the free encyclopedia

Nagle's algorithm is a means of improving the efficiency of TCP/IP networks by reducing the number of packets that need to be sent over the network. It is named after John Nagle, then at Ford Aerospace and lately at Animats.

Nagle's document, Congestion Control in IP/TCP Internetworks (RFC896) describes what he called the 'small packet problem', where an application repeatedly emits data in small chunks, frequently only 1 byte in size. Since TCP packets have a 40 byte header (20 bytes for TCP, 20 bytes for IPv4), this results in a 41 byte packet for 1 byte of useful information, a huge overhead. This situation occurs in Telnet sessions, where keypresses generate a single byte of data which is transmitted immediately. Worse, over slow links, many such packets can be in transit at the same time, potentially leading to congestion collapse.

The Nagle algorithm works by coalescing a number of small outgoing messages, and sending them all at once. Specifically, as long as there is a sent packet for which the sender has received no acknowledgement, the sender should keep buffering its output until it has a full packet's worth of output, so that output can be sent all at once.

[edit] Algorithm

if there is new data to send
 if the window size and available data is >= MSS
  send complete MSS size segment now
 else
  if there is unconfirmed data still in the pipe
   enqueue data in the buffer until an acknowledge is received
  else
   send data immediately

with MSS = maximum segment size

This algorithm interacts badly with TCP delayed acknowledgements, a feature introduced into TCP at roughly the same time in the early 1980s, but by a different group. With both algorithms enabled, applications which do two successive writes to a TCP connection, followed by a read, experience a constant delay of up to 500 milliseconds, the "ACK delay". For this reason, TCP implementations usually provide applications with an interface to disable the Nagle algorithm. This is typically called the TCP_NODELAY option. The first major application to run into this problem was the X Window System.

The tinygram problem and silly window syndrome are sometimes confused. The tinygram problem occurs when the window is almost empty. Silly window syndrome occurs when the window is almost full.