Nagle’s algorithm

How Nagle’s algorithm is making TCP/IP better and when is ok to use it. Truth be told, Nagle should be avoided in today’s high-speed networks.

This article it’s not about mathematics, don’t be afraid. I’m running a networking blog and it’s not my intention to speak or write about anything related to mathematics. Biggest math problem that I’ve done in last few years is some simple subneting, EIGRP metric calculation and that is where I stopped with math for now.

On the other hand, I love the theory behind algorithms, specially if the algorithm is used in networking and if it is so simple and powerful as Nagle’s algorithm.

You can guess, John Nagle is the name of the fellow who created the algorithm. He found a solution for TCP/IP efficiency issue also known as “small packet problem”.

Here’s what happens:

If you decide to send, let’s say, one single letter across the network to some destination, your machine will probably take that one letter and send it immediately across the network, right?

Ok, a bit of math now. One letter or some other single character, when converted to binary, will take on byte of data. Here’s an example with few letters from ASCII code table. Red are the binary for first few letters:

DEC OCT HEX BIN Symbol HTML
Description
63 77 3F 111111 ? ? Question mark
64 100 40 1000000 @ @ At symbol
65 101 41 1000001 A A Uppercase A
66 102 42 1000010 B B Uppercase B
67 103 43 1000011 C C Uppercase C
68 104 44 1000100 D D Uppercase D
69 105 45 1000101 E E Uppercase E
70 106 46 1000110 F F Uppercase F
71 107 47 1000111 G G Uppercase G

Ok, so If you decide to send one single letter across the network your PC will take that one byte of data and encapsulate is with 40 bytes of header.

40 bytes of header is a normal size of the header, 20 bytes for TCP and 20 bytes for IPv4.

You see here that we will basically have 4000% header overhead giving that payload could be up to 1500 bytes and we have only one byte. Either way the header stays the same size. 40 bytes header for 1500 bytes payload is not a big overhead, but 40 bytes header for 1 byte of payload is pretty bad.

One of the examples that sends one by one character across the network is Telnet sessions. Telnet will send the characters as you type. Over slow links, many telnet packets will be in transit at the same time, making the link congested.

Nagle came up with an great idea. Small outgoing data pieces will be buffered, combined together and sent out all at once in one single packet. In details, as long as client is waiting the acknowledgement for previously sent packet it will not send another one until the buffered bytes of data are not enough to fill up the packet (up to maximum payload size).

Algorithm

if there is new data to send
  if the window size >= MAXPAYLOAD and available data is >= MAXPAYLOAD
    send complete MAXPAYLOAD 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 MAXPAYLOAD = maximum segment size.

 

ISSUES

Nagle’s algorithm works basically by intentionally delaying packets. By doing this it increases bandwidth efficiency and makes latency worse by increasing it too.

Time sensitive applications that need real-time interaction with destination can use TCP_NODELAY to bypass the Nagle delay, or simply use UDP.

Today’s networks with huge throughput are not the place where you should use Nagles’s algorithm. Most of the applications today are real-time apps that communicate with server all the time with response to user expected instantly. Having non-blocking network devices and 10G network speeds is making any kind of intentional delay unwelcome.

 

Leave a Reply