Алгоритм Нейгла

Алгоритм Нейгла — назван в честь Джона Нейгла, является средством повышения эффективности работы сетей TCP/IP, позволяющим уменьшить количество пакетов, которые должны быть отправлены по сети.

Документ Нейгла, Управление Перегрузкой IP/TCP Сетей ([tools.ietf.org/html/rfc896 RFC 896]) описывает то, что он назвал «проблемой небольших пакетов», которая заключается в том, что приложение неоднократно посылает данные небольшими порциями, часто размером в 1 байт. Так как TCP пакеты имеют 40 байт заголовка (20 байт TCP, 20 байт IPv4), это приводит к тому, что передается пакет размером 41 байт, несущий в себе 1 байт полезной информации, то есть к огромным накладным расходам. Эта ситуация часто встречается в сессии Telnet, где большинство нажатий клавиш генерируют один байт данных, который немедленно передается. Кроме того, по медленным каналам связи многие такие пакеты могут находиться в пути в одно и то же время, что может привести к перегруженности сети.

Алгоритм Нейгла работает путём объединения нескольких небольших исходящих сообщений, а затем отправки их всех сразу. В частности, пока существует отправленный пакет, для которого отправитель еще не получил никакого подтверждения о доставке, отправитель должен держать в буфере следующие данные для отправки, до тех пор, пока не наберется достаточно данных на полный пакет, который можно отправить единожды.

Алгоритм

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

где MSS — максимальный размер блока данных для TCP-пакета. MSS зависит от MTU.

Этот алгоритм плохо взаимодействует с технологией TCP с отложенным подтверждением, которая была представлена в TCP примерно в то же время, в начале 1980-х. Если приложение, использующее оба алгоритма, устанавливает два последовательных write — соединения TCP, а затем read, то последнее не будет выполнено, пока данные из второго write не достигнут места назначения. В результате получается постоянная задержка до 500 мс, «задержка ACK». По этой причине TCP реализация обычно предоставляет приложениям интерфейс для отключения алгоритма Нейгла (опция TCP_NODELAY).

«На уровне пользователя нужно избегать последовательности „запись-запись-чтение“ на сокетах. „Запись-чтение-запись-чтение“ будет работать хорошо. „Запись-запись-запись“ тоже. Но „запись-запись-чтение“ все ухудшит. Так что, если вы можете, то сохраняйте в буфер ваши небольшие пакеты TCP с данными для записи, а затем отправляйте их все сразу. Если вы используете стандартный пакет UNIX ввода-вывода и „вымывание из буфера“ данных для записи перед каждым чтением, чтение обычно работает нормально.»

Проблему передачи небольших данных (tinygram problem) и «синдром узкого потока» ([en.wikipedia.org/wiki/Silly_window_syndrome Silly window syndrome]) часто путают. Проблема передачи небольших данных проявляется, когда окно почти пусто. Синдром узкого потока проявляется, когда оно почти заполнено.

Негативное влияние на передачу больших данных для записи

Алгоритм применим для данных любого размера. Если данные для записи охватывают 2n пакетов, то последний пакет будет удержан в ожидании ACK предыдущего пакета. В любом протоколе приложений типа запрос-ответ, где данные запроса могут быть больше, чем пакет, это может искусственно наложить несколько сотен миллисекунд задержки между запросом и ответом, даже если запрашивающий будет сохранять в буфер данные запроса перед отправкой. В этом случае запрашивающий должен отключить алгоритм Нейгла. Если данные ответа могут быть больше, чем пакет, ответчику также необходимо отключить алгоритм Нейгла, чтобы запрашивающий оперативно получал весь ответ.

Таким образом, алгоритм Нейгла позволяет защититься от небрежно написанного приложения, но он не пойдет на пользу тщательно написанному, которое уделяет надлежащее внимание буферизации; для такого приложения алгоритм либо не будет давать никакого эффекта, либо будет давать отрицательный эффект от применения.

Взаимодействие с системами реального времени

Приложения, для которых важно актуальное время ответа, могут плохо работать с алгоритмом Нейгла. Такие приложения, как сетевые многопользовательские игры, предполагают, что какие-либо действия в игре отправляется сразу, тогда как алгоритм целенаправленно задерживает передачу, увеличивая эффективность использования полосы пропускания сети за счет задержки. По этой причине приложения с низкой пропускной способностью срочных передач обычно используют TCP_NODELAY, чтобы обойти задержки алгоритма Нейгла.

Другим вариантом в данном случае является использование UDP.

Литература

• Peterson, L.L. and Davie, B.S. Computer Networks: A Systems Approach. — Morgan Kaufmann, 2007. — P. 402—403. — ISBN 9780123705488.

Ссылки

• [developers.slashdot.org/comments.pl?sid=174457&threshold=1&commentsort=0&mode=thread&cid=14515105 Boosting Socket Performance on Linux]
• [www.stuartcheshire.org/papers/NagleDelayedAck/ TCP Performance problems caused by interaction between Nagle’s Algorithm and Delayed ACK]
• [bugs.freedesktop.org/show_bug.cgi?id=17868 Bug 17868 — Some Java applications are slow on remote X connections ]

Отрывок, характеризующий Алгоритм Нейгла

Вернувшись в полк и передав командиру, в каком положении находилось дело Денисова, Ростов с письмом к государю поехал в Тильзит.
13 го июня, французский и русский императоры съехались в Тильзите. Борис Друбецкой просил важное лицо, при котором он состоял, о том, чтобы быть причислену к свите, назначенной состоять в Тильзите.
– Je voudrais voir le grand homme, [Я желал бы видеть великого человека,] – сказал он, говоря про Наполеона, которого он до сих пор всегда, как и все, называл Буонапарте.
– Vous parlez de Buonaparte? [Вы говорите про Буонапарта?] – сказал ему улыбаясь генерал.
Борис вопросительно посмотрел на своего генерала и тотчас же понял, что это было шуточное испытание.
– Mon prince, je parle de l'empereur Napoleon, [Князь, я говорю об императоре Наполеоне,] – отвечал он. Генерал с улыбкой потрепал его по плечу.
– Ты далеко пойдешь, – сказал он ему и взял с собою.
Борис в числе немногих был на Немане в день свидания императоров; он видел плоты с вензелями, проезд Наполеона по тому берегу мимо французской гвардии, видел задумчивое лицо императора Александра, в то время как он молча сидел в корчме на берегу Немана, ожидая прибытия Наполеона; видел, как оба императора сели в лодки и как Наполеон, приставши прежде к плоту, быстрыми шагами пошел вперед и, встречая Александра, подал ему руку, и как оба скрылись в павильоне. Со времени своего вступления в высшие миры, Борис сделал себе привычку внимательно наблюдать то, что происходило вокруг него и записывать. Во время свидания в Тильзите он расспрашивал об именах тех лиц, которые приехали с Наполеоном, о мундирах, которые были на них надеты, и внимательно прислушивался к словам, которые были сказаны важными лицами. В то самое время, как императоры вошли в павильон, он посмотрел на часы и не забыл посмотреть опять в то время, когда Александр вышел из павильона. Свидание продолжалось час и пятьдесят три минуты: он так и записал это в тот вечер в числе других фактов, которые, он полагал, имели историческое значение. Так как свита императора была очень небольшая, то для человека, дорожащего успехом по службе, находиться в Тильзите во время свидания императоров было делом очень важным, и Борис, попав в Тильзит, чувствовал, что с этого времени положение его совершенно утвердилось. Его не только знали, но к нему пригляделись и привыкли. Два раза он исполнял поручения к самому государю, так что государь знал его в лицо, и все приближенные не только не дичились его, как прежде, считая за новое лицо, но удивились бы, ежели бы его не было.
Борис жил с другим адъютантом, польским графом Жилинским. Жилинский, воспитанный в Париже поляк, был богат, страстно любил французов, и почти каждый день во время пребывания в Тильзите, к Жилинскому и Борису собирались на обеды и завтраки французские офицеры из гвардии и главного французского штаба.
24 го июня вечером, граф Жилинский, сожитель Бориса, устроил для своих знакомых французов ужин. На ужине этом был почетный гость, один адъютант Наполеона, несколько офицеров французской гвардии и молодой мальчик старой аристократической французской фамилии, паж Наполеона. В этот самый день Ростов, пользуясь темнотой, чтобы не быть узнанным, в статском платье, приехал в Тильзит и вошел в квартиру Жилинского и Бориса.
В Ростове, также как и во всей армии, из которой он приехал, еще далеко не совершился в отношении Наполеона и французов, из врагов сделавшихся друзьями, тот переворот, который произошел в главной квартире и в Борисе. Все еще продолжали в армии испытывать прежнее смешанное чувство злобы, презрения и страха к Бонапарте и французам. Еще недавно Ростов, разговаривая с Платовским казачьим офицером, спорил о том, что ежели бы Наполеон был взят в плен, с ним обратились бы не как с государем, а как с преступником. Еще недавно на дороге, встретившись с французским раненым полковником, Ростов разгорячился, доказывая ему, что не может быть мира между законным государем и преступником Бонапарте. Поэтому Ростова странно поразил в квартире Бориса вид французских офицеров в тех самых мундирах, на которые он привык совсем иначе смотреть из фланкерской цепи. Как только он увидал высунувшегося из двери французского офицера, это чувство войны, враждебности, которое он всегда испытывал при виде неприятеля, вдруг обхватило его. Он остановился на пороге и по русски спросил, тут ли живет Друбецкой. Борис, заслышав чужой голос в передней, вышел к нему навстречу. Лицо его в первую минуту, когда он узнал Ростова, выразило досаду.
– Ах это ты, очень рад, очень рад тебя видеть, – сказал он однако, улыбаясь и подвигаясь к нему. Но Ростов заметил первое его движение.
– Я не во время кажется, – сказал он, – я бы не приехал, но мне дело есть, – сказал он холодно…