Nagle's algorithm

From Wikipedia, the free encyclopedia - View original article

 
Jump to: navigation, search

Nagle's algorithm, named after John Nagle, 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.

Nagle's document, Congestion Control in IP/TCP Internetworks (RFC 896) 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 often occurs in Telnet sessions, where most keypresses generate a single byte of data that is transmitted immediately. Worse, over slow links, many such packets can be in transit at the same time, potentially leading to congestion collapse.

Nagle's algorithm works by combining 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 acknowledgment, 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.

Algorithm[edit]

 if there is new data to send   if the window size >= MSS and available data is >= MSS     send complete MSS 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     end if   end if end if 

where MSS = maximum segment size.

This algorithm interacts badly with TCP delayed acknowledgments, a feature introduced into TCP at roughly the same time in the early 1980s, but by a different group. With both algorithms enabled, applications that do two successive writes to a TCP connection, followed by a read that will not be fulfilled until after the data from the second write has reached the destination, 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 user-level solution is to avoid write-write-read sequences on sockets. write-read-write-read is fine. write-write-write is fine. But write-write-read is a killer. So, if you can, buffer up your little writes to TCP and send them all at once. Using the standard UNIX I/O package and flushing write before each read usually works."[1]

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.

Negative effect on non-small writes[edit]

The algorithm applies to data of any size. If the data in a single write spans 2n packets, the last packet will be withheld, waiting for the ACK for the previous packet.[2] In any request-response application protocols where request data can be larger than a packet, this can artificially impose a few hundred milliseconds latency between the requester and the responder, even if the requester has properly buffered the request data. Nagle's algorithm must be disabled by the requester in this case. If the response data can be larger than a packet, the responder must also disable Nagle's algorithm so the requester can promptly receive the whole response.

In general, since Nagle's algorithm is only a defense against careless applications, it will not benefit a carefully written application that takes proper care of buffering; the algorithm has either no effect, or negative effect on the application.

Interactions with real-time systems[edit]

Applications that expect real time responses can react poorly with Nagle's algorithm. Applications such as networked multiplayer video games expect that actions in the game are sent immediately, while the algorithm purposefully delays transmission, increasing bandwidth efficiency at the expense of latency. For this reason applications with low-bandwidth time-sensitive transmissions typically use TCP_NODELAY to bypass the Nagle delay.[3]

Another option is to use UDP instead.

References[edit]

  1. ^ Boosting Socket Performance on Linux - Slashdot
  2. ^ "TCP Performance problems caused by interaction between Nagle's Algorithm and Delayed ACK". Stuartcheshire.org. Retrieved November 14, 2012. 
  3. ^ Bug 17868 – Some Java applications are slow on remote X connections

External links[edit]