|
глава 21 тайм-ауты и повторные передачи tcp tcp - это надежный транспортный уровень. один из способов обеспечения надежности заключается в том, что удаленный участник обмена подтверждает полученные данные. однако, сегменты данных, которые должны быть подтверждены, могут быть потеряны. tcp отрабатывает подобные ситуации установкой тайм-аута, при отправке данных; если данные не были подтверждены до момента истечения тайм-аута, tcp передает их повторно. основными составляющими частями подобной технологии являются тайм-ауты и повторные передачи. как определяются величины тайм-аутов, и как часто осуществляются повторные передачи? мы уже видели два примера тайм-аута и повторной передачи: (1) в примере, посвященном недоступности порта icmp в разделе "icmp ошибка недоступности порта" главы 6, мы видели, что tftp клиент, использующий udp, применяет простую стратегию тайм-аута и повторной передачи: он устанавливает период тайм-аута в 5 секунд и осуществляет повторную передачу каждые 5 секунд. (2) в примере arp для несуществующего хоста (глава 4, раздел "примеры arp") мы видели, что когда tcp старается установить соединение, он повторно передает свои syn, используя увеличенные задержки между каждой повторной передачей. tcp управляет четырьмя таймерами для каждого соединения.
в этой главе мы начнем с простых примеров того, как tcp использует тайм-ауты и повторные передачи, а затем рассмотрим более подробные примеры, которые позволят понять, как tcp осуществляет управление таймерами. мы увидим то, как стандартные реализации рассчитывают время возврата сегментов tcp, и как tcp использует эти расчеты, для того чтобы вычислить тайм-аут для повторной передачи следующего сегмента, который он собирается отправить. затем мы рассмотрим, как tcp избегает переполнения - что tcp делает, когда пакеты теряются - и в завершение, рассмотрим реальные примеры того, каким образом теряются пакеты. также мы рассмотрим новый алгоритм быстрой передачи и алгоритм быстрого восстановления, а затем посмотрим, что позволяет tcp быстрее определять факт потери пакетов, нежели просто ожидание того, когда истечет таймер. простой пример использования тайм-аутов и повторных передач во-первых, давайте рассмотрим стратегию повторных передач, которая используется tcp. мы установим соединение, отправим какие-нибудь данные, чтобы убедиться в том, что соединение функционирует, отсоединим кабель, отправим еще данные и посмотрим, как поступит tcp:
на рисунке 21.1 показан вывод команды tcpdump. (мы удалили всю информацию, связанную с типом сервиса, которую устанавливает bsdi.)
рисунок 21.1 простой пример тайм-аута и повторной передачи tcp.
строки 1, 2 и 3 соответствуют обычному установлению tcp соединения. строка 4 это передача "hello, world" (12 символов плюс символ возврата каретки и пропуска строки), а в строке 5 - подтверждение. затем мы отсоединяем ethernet кабель от svr4. в строке 6 показано, как передается "and hi". строки 7-18 это 12 повторных передач сегмента, а в строке 19 tcp прекращает попытки передачи и посылает сброс. обратите внимание на временные промежутки между последовательными повторными передачами: они происходили в моменты времени 1, 3, 6, 12, 24, 48 и 64 секунды. дальше в этой главе мы увидим, что первый тайм-аут устанавливается в 1,5 секунды после первой передачи. (причина, по которой он возник через 1,0136 секунды после первой передачи, а не точно через 1,5 секунды, была объяснена на рисунке 18.7.) после этого величина тайм-аута удваивается для каждой передачи, причем верхний предел составляет 64 секунды. подобное увеличение называется экспотенциальным наращиванием (exponential backoff). сравните это с примером tftp, который приведен в разделе "icmp ошибка недоступности порта" главы 6, где каждая повторная передача осуществляется через 5 секунд после предыдущей. разница во времени между первой передачей пакета (строка 6, момент времени 24,480) и сбросом (строка 19, момент времени 566,488) составляет примерно 9 минут. современные tcp реализации довольно настойчивы в попытках отправить данные! в большинстве реализаций полная величина тайм-аута ненастраиваемая. solaris 2.2 позволяет администратору изменить эту величину (переменная tcp_ip_abort_interval в разделе "solaris 2.2" приложения e), а по умолчанию она составляет только 2 минуты, а не 9 минут, как это принято в большинстве реализаций. определение времени возврата основой тайм-аутов и повторных передач tcp является расчет времени возврата (rtt - round-trip time), соответствующего данному соединению. мы ожидаем, что оно может изменяться со временем, так как может измениться маршрут, или загрузка сети. tcp должен отследить эти изменения и соответственно модифицировать тайм-ауты. во-первых, tcp должен рассчитать rtt между отправкой байта с конкретным номером последовательности и получением подтверждения на этот номер последовательности. из предыдущей главы мы знаем, что обычно не существует полного соответствия между сегментами данных и подтверждениями (ack). на рисунке 20.1 это означало, что один rtt, который может быть вычислен отправителем, является временем между передачей сегмента 4 (байты данных 1-1024) и получением сегмента 7 (ack байт 1-2048), даже если этот ack подтверждает дополнительно 1024 байта. мы используем величину m, чтобы обозначить рассчитанный rtt. для определения rtt существует расширение к исходной спецификации tcp, которое называется хэшированная оценочная функция rtt (обозначается r)
r ¬ a r + (1 - a )m
где a это коэффициент хэширования с рекомендуемым значением 0,9. хэширование - способ организации структур данных (хэш таблиц), обеспечивающий эффективный поиск и пополнение; положение элемента данных в хэш таблице определяется значением функции расстановки, отображающей множество возможных ключей элементов данных и множество индексов таблицы и обеспечивающей равномерное заполнение. хэшированный rtt обновлялся каждый раз, когда осуществлялось новое вычисление. девяносто процентов данных для каждого нового расчета берется из предыдущего расчета, а десять из нового.для подобной хэшированной оценочной функции, которая изменяется с изменением rtt, rfc 793 рекомендует, чтобы тайм-аут повторной передачи (rto) устанавливался следующим образом
rto = r b
где b это коэффициент изменения задержки с рекомендуемым значением равным 2.[jacobson 1988] подробно обсуждает проблемы, связанные с подобным подходом, в основном заключающиеся в том, что он не может применяться при широком диапазоне изменения rtt, и является причиной нежелательных повторных передач. как замечает jacobson, нежелательные повторные передачи увеличивают загрузку сети. в этом случае необходимо добавить возможность отслеживать расхождения в расчетах rtt в дополнение к хэшированной функции оценки rtt. расчет rto основанный на среднем и расхождении дает значительно лучшие результаты при широком диапазоне изменений времен возврата, чем просто расчет rto как постоянного кратного среднего значения. рисунки 5 и 6 в [jacobson 1988] показывают сравнение значений rto в соответствии с rfc 793 для некоторых реальных времен возврата, с расчетами rto, которые мы показали ранее, которые принимают во внимание изменение времен возврата. как описано у jacobson, среднее отклонение является хорошим приближением к стандартному отклонению, однако рассчитывается значительно легче. (расчет стандартного отклонения требует вычисления квадратного корня.) таким образом, следующие уравнения могут быть применены к каждому расчету rtt m.
err = m - a a ¬ a + gerrd ¬ d + h(| err | - d)rto = a + 4d
где a это хэшированный rtt (оценочная функция среднего), а d это хэшированное среднее отклонение. err это разница между только что рассчитанным значением и текущим значением оценочной функции rtt. оба a и d используются для расчета следующего тайм-аута повторной передачи (rto). увеличение среднего (g) установлено в значение 1/8 (0,125). увеличение отклонения (h) установлено в 0,25. максимальное увеличение отклонения делает рост rto быстрее при изменении rtt. [jacobson 1988] устанавливает 2d при расчете rto, однако для следующих исследований [jacobson 1990c] изменяет это значение на 4d, что соответствует реализации bsd net/1.
jacobson показывает способ осуществить эти вычисления с использованием целочисленной арифметики, именно так это обычно делается в стандартных реализациях. (одна из причин заключается в том, что g, h и множитель 4 - это степени двух, поэтому все операции могут быть осуществлены с помощью сдвига, без умножений и делений.) сравнение исходного метода с методом jacobsonа показывает, что расчеты хэшированного среднего одинаковы ( a равно единица минус увеличение (g)), однако используются различные увеличения. также, расчет rto по jacobsonу зависит от обоих значений - хэшированного rtt и хэшированного среднего отклонения, тогда как оригинальный метод использует умножение хэшированных rtt.в следующем разделе мы увидим, как устанавливаются эти оценочные функции, когда будем рассматривать примеры. в процессе повторной передачи пакета могут возникнуть проблемы. скажем, пакет передан, тайм-аут отработан, rto экспотенциально увеличен, как показано в разделе "простой пример использования тайм-аутов и повторных передач" этой главы, пакет передан повторно с большим rto и получено подтверждение. соответствует ли это подтверждение первой передаче или второй? это называется проблемой двусмысленности повторной передачи (retransmission ambiguity problem) . [karn and partridge 1987] указывает, что когда применяется тайм-аут и повторная передача, мы не можем обновить оценочные функции rtt, когда, в конце концов, прибывает подтверждение на повторно переданные данные. это потому, что мы не знаем, которой передаче соответствует подтверждение (ack). (возможно, первая передача была задержана, но не была отброшена, или был задержан ack на первую передачу.) так как данные были повторно переданы и к rto было применено экспотенциальное наращивание, мы повторно используем экспотенциально увеличенный rto для следующей передачи. новый rto не рассчитывается до тех пор, пока не будет получено подтверждение на сегмент, который не отправлялся повторно. в этой главе мы рассмотрим примеры, которые проиллюстрируют детали разных реализаций tcp тайм-аутов и повторных передач, медленный старт и предотвращение переполнения. с помощью программы sock отправлено 32768 байт данных с хоста slip на discard сервис хоста vangogh.cs.berkeley.edu: slip % sock -d -i -n32 vangogh.cs.berkeley.edu discard
обратимся к рисунку, находящемуся на внутренней стороне обложки. из рисунка видно, что slip подсоединен к ethernet 140.252.1 двумя slip каналами, а затем через internet к пункту назначения. так как используется два slip канала (со скоростью 9600 бит в секунду), мы ожидаем появления определенных задержек. команда, приведенная выше, осуществит 32 записи по 1024 байта. так как mtu между slip и bsdi составляет 296, то будет сгенерировано 128 сегментов, каждый из которых будет содержать 256 байт пользовательских данных. полное время передачи займет примерно 45 секунд, и мы увидим один тайм-аут и три повторные передачи. пока осуществляется эта передача, мы запустим tcpdump на хосте slip, чтобы увидеть все сегменты, которые были переданы и приняты. в дополнение мы указали опцию -d, чтобы включить отладку сокетов (см. приложение a, раздел "опция отладки сокета"). кроме того, у нас была возможность запустить модифицированную версию программы trpt(8), которая позволяет напечатать некоторые переменные в блоке управления соединением, имеющие отношение к временам задержки, медленному старту и предотвращению переполнения. из-за того, что вывод достаточно большой, мы не можем показать его целиком, однако рассмотрим его по частям, в процессе изучения главы. на рисунке 21.2 показана передача данных и подтверждений в течение первых 5 секунд. мы немного модифицировали этот вывод от предыдущего вывода команды tcpdump. мы только оценили моменты времени, когда пакет отправлялся или принимался хостом, на котором запущена программа tcpdump, на этом рисунке мы хотели показать, что пакет двигается по сети (так как это соединение в локальной сети не похоже на распределенный ethernet), и показать, когда принимающий хост, возможно, генерирует подтверждения. (мы удалили все объявления окна. slip всегда объявляет окно размером 4096, а vangogh всегда объявляет окно 8192.)
рисунок 21.2 обмен пакетами и расчет rtt.
также обратите внимание на то, что на этом рисунке мы пронумеровали сегменты 1-13 и 15 в том порядке, в котором они были отправлены или приняты хостом slip. это соответствует выводу tcpdump, который был получен для этого хоста. определение времени возврата три большие фигурные скобки, находящиеся с левой стороны временной диаграммы, указывают на то, какие сегменты были использованы при расчете rtt. не для всех сегментов время было засечено. большинство реализаций tcp, происходящих от berkeley, рассчитывают только одно значение rtt для соединения за один раз. если в тот момент, когда отправляется сегмент данных, таймер для данного соединения уже используется, время для этого сегмента не засекается. установка времени осуществляется путем увеличения счетчика каждый раз, когда запускается 500-миллисекундный таймер tcp. это означает, что для сегмента, подтверждение на который прибывают через 550 миллисекунд после того, как сегмент был отправлен, может быть принято rtt как равное одному тику (500 миллисекунд), так и rtt равное двум тикам (1000 миллисекунд). в дополнение к этому счетчику тиков для каждого соединения, запоминается начальный номер последовательности данных в сегменте. когда принимается подтверждение, содержащее этот номер последовательности, таймер выключается. если данные не были повторно переданы, когда прибыл ack, хэшированное rtt и хэшированное среднее отклонение обновляется на основе новых значений. таймер для соединения, показанного на рисунке 21.2, стартует, когда передается сегмент 1, и выключается, когда прибывает подтверждение на него (сегмент 2). несмотря на то, что его rtt равен 1,061 секунды (из вывода команды tcpdump), исследование отладочной информации сокета показывает, что за этот период произошло 3 тика часов tcp, а это обозначает, что rtt равен 1500 миллисекунд. следующий сегмент, для которого засекли время, сегмент номер 3. когда, через 2,4 миллисекунды, передается сегмент номер 4, он не может быть отслежен по времени, так как таймер для этого соединения уже используется. когда прибывает сегмент 5, подтверждая данные, на которые было засечено время, его rtt рассчитывается равным 1 тику (500 миллисекунд), даже несмотря на то, что, как мы видели из вывода команды tcpdump, его rtt равен 0,808 секунды. таймер стартует снова, когда передается сегмент 6, и выключается, когда прибывает подтверждение на него, через 1,015 секунды (сегмент 10). полученный rtt равен 2 тикам часов. сегменты 7 и 9 не могут быть оценены по времени, так как таймер занят. также, когда принимается сегмент 9 (ack 769), ничего не обновляется, так как подтверждение не подтверждает байты, на которые засекли время. на рисунке 21.3 показана взаимосвязь между реальными rtt, которые мы можем определить из вывода команды tcpdump, и счетчиком тиков часов.
рисунок 21.3 расчет rtt и тики часов.
вверху мы показали тики часов, каждые 500 миллисекунд. внизу - моменты времени, полученные из вывода команды tcpdump, и то, когда таймер соединения включался и выключался. мы знаем, что между отправкой сегмента 1 и получением сегмента 2 прошло 3 тика, что заняло 1,061 секунды, таким образом, мы предполагаем, что первый тик возник в момент времени 0,03. (первый тик должен произойти между 0,00 и 0,061.) на рисунке показано, что второй rtt был оценен равным 1 тику, а третий - 2 тикам. в этом примере было передано 128 сегментов и получено 18 значений rtt. на рисунке 21.4 показаны измеренные rtt (взятые из вывода tcpdump) вместе с rto, используемого в tcp для установки тайм-аутов (взято из отладочной информации сокета). момент времени 0 (на рисунке 21.2) по оси ox соответствует отправке первого сегмента данных, а не отправке первого syn.
рисунок 21.4 рассчитанные rtt и rto tcp для этого примера.
первые три точки, которые соответствующие измеренным rtt, соответствуют трем rtt, которые мы показали на рисунке 21.2. пропуски в значениях rtt около моментов времени 10, 14 и 21 вызваны повторными передачами, которые здесь имели место (что будет показано позже в этой главе). алгоритм карна не позволяет обновить наши оценки до тех пор, пока еще один сегмент не будет передан и подтвержден. также обратите внимание на то, что для этой реализации рассчитанные rto tcp всегда кратны 500 миллисекундам. расчет оценочных функций rtt давайте посмотрим, как устанавливаются и обновляются оценочные функции rtt (хэшированный rtt и хэшированное среднее отклонение), и как рассчитывается тайм-аут для каждой передачи. переменные a и d устанавливаются в 0 и 3 секунды соответственно. исходный тайм-аут для передачи рассчитывается с использованием формулы
rto = a + 2d = 0 + 2 x 3 = 6 секунд
(коэффициент 2d используется только для этого первоначального расчета. затем при расчете rto к a прибавляется 4d, как было показано ранее.) это rto для передачи первоначального syn. в случае если исходный syn потерян, осуществляется тайм-аут и повторная передача. на рисунке 21.5 показаны первые четыре строки вывода команды tcpdump.
рисунок 21.5 тайм-аут и повторная передача исходного syn.
когда тайм-аут возникает позже, через 5,802 секунды, текущий rto рассчитывается следующим образом
rto = a + 4d = 0 + 4 x 3 = 12 секунд
затем к rto равному 12 применяется экспотенциальное наращивание. так как это первый тайм-аут, используется множитель 2, при этом значение следующего тайм-аута будет равно 24 секундам. следующий тайм-аут рассчитывается с использованием множителя 4, значения тайм-аута становится 48 секунд: 12 x 4. (эти исходные rto для первого syn, 6 секунд и затем 24 секунды, как раз то, что мы видели на рисунке 4.5.) ack прибывает через 467 миллисекунд после повторной передачи. значения a и d не обновляются, потому что алгоритм карна определяет двусмысленность передачи. следующий отправляемый сегмент - это ack в строке 4, однако время для него не засекается, так как это всего лишь подтверждение. (время устанавливается только для сегментов, содержащих данные.) когда отправляется первый сегмент данных (сегмент 1 на рисунке 21.2), rto не меняется, опять же в соответствии с алгоритмом карна. текущее значение, равное 24 секундам, повторно используется до тех пор, пока не будет осуществлено измерение rtt. это означает, что rto для момента времени равного 0 на рисунке 21.4 равно в действительности 24, однако мы не берем во внимание эту точку. когда прибывает подтверждение на этот первый сегмент данных (сегмент 2 на рисунке 21.2), получено 3 тика часов, и наши показатели устанавливаются следующим образом
a = m + 0,5 = 1,5 + 0,5 = 2 d = a/2 = 1
(значение m равное 1,5 соответствует 3-м тикам часов.) предыдущие установки a и d в 0 и 3 были сделаны для расчета первоначального rto. эти установки предназначены для первого расчета оценочных функций, с использованием первого измерения rtt m. rto рассчитывается следующим образом
rto = a + 4d = 2 + 4 x 1 = 6 секунд
когда прибывает ack на второй сегмент данных (сегмент 5 на рисунке 21.2), отсчитан 1 тик часов (0,5 секунды), и наши показатели обновляются следующим образом
err = m - a = 0,5 - 2 = -1,5 a = a + gerr = 2 - 0,125 x 1,5 = 1,8125 d = d + h(|err| - d) = 1 + 0,25 x (1,5 - 1) = 1,125 rto = a + 4d = 1,8125 + 4 x 1,125 = 6,3125
существует несколько тонкостей в представлении err, a и d, при расчетах с фиксированной точкой, которая и используется в действительности (однако мы показали для простоты с плавающей точкой). эта разница дает rto равное 6 секундам (а не 6,3125), как раз столько, сколько было показано на рисунке 21.4 для момента времени 1,871. мы описали алгоритм медленного старта в разделе "медленный старт" главы 20, а также видели его в действии на рисунке 21.2. первоначально по соединению отправляется только один сегмент, и подтверждение на него должно быть получено перед тем, как будет отправлен другой сегмент. когда сегмент 2 принят, отправляются два следующих сегмента. давайте теперь рассмотрим передачу сегментов данных. на рисунке 21.6 показана зависимость стартового номера последовательности сегмента от времени, когда сегмент был отправлен. это позволит нам более наглядно представить процесс передачи данных. обычно точки, соответствующие данным, должны двигаться вверх вправо, при этом наклон соответствует скорости передачи. повторные передачи показаны отклонением графика вниз вправо. в начале раздела "пример rtt" этой главы мы сказали, что полное время передачи составляло примерно 45 секунд, однако на этом рисунке мы показали только 35 секунд. (потому что, именно 35 секунд потребовалось для передачи только сегментов данных.) первый сегмент данных не передавался в течении 6,3 секунды после отправки первого syn, потому что первый syn был потерян при передаче и передан повторно (рисунок 21.5). после того как последний сегмент данных и fin были отправлены (момент времени 34,1 на рисунке 21.6), потребовалось еще примерно 4,0 секунды на то, чтобы принять последние 14 ack от получателя перед тем, как от получателя был получен fin.
рисунок 21.6 отправка 32768 байт данных от slip на vangogh.
на рисунке 21.6 мы сразу видим три повторные передачи в моменты времени 10, 14 и 21. во всех трех случаях только один сегмент передается повторно, потому что только одна точка оказалась ниже предыдущих. давайте рассмотрим первый из этих "скачков вниз" (в момент времени 10). вывод команды tcpdump мы рассмотрим вместе с рисунком 21.7.
рисунок 21.7 обмен пакетами в процессе повторной передачи в районе 10-секундной метки.
мы удалили все объявления окна, за исключением сегмента 72, который мы обсудим ниже. slip всегда объявляет окно равное 4096, а vangogh объявляет окно равное 8192. сегменты на этом рисунке пронумерованы как продолжение рисунка 21.2, где первый сегмент данных по соединению был с номером 1. как и на рисунке 21.2, сегменты пронумерованы в соответствии с тем, как они отправлялись или принимались на хосте slip, где была запущена программа tcpdump. мы также удалили несколько сегментов, которые не имели отношения к нашему обсуждению (44, 47 и 49, а также все ack от vangogh). случилось так, что сегмент 45 либо потерялся, либо пришел поврежденным - мы не можем сказать этого определенно, основываясь на выводе команды. все что мы можем увидеть на хосте slip это то, что было подтверждено все, за исключением байта 6657 (сегмент 58), за которым следовали следующие восемь ack с тем же самым номером последовательности. прием сегмента 62, третьего из дублированных ack, вызвал повторную передачу данных, начиная с номера последовательности 6657 (сегмент 63). в действительности, реализации, происходящие от berkeley, подсчитывают количество принятых дублированных ack, и когда принимается третий, они подразумевают, что сегмент потерян, и повторно передают только один сегмент, начиная с этого номера последовательности. подобное поведение является частью алгоритма быстрой повторной передачи (fast retransmit), который следует за алгоритмом быстрого восстановления данных (fast recovery algorithm), которые мы обсудим в разделе "быстрая повторная передача и алгоритм быстрого восстановления" этой главы. обратите внимание на то, что после повторной передачи (сегмент 63) отправитель продолжает обычную передачу данных (сегменты 67, 69 и 71). tcp не ожидает того, что удаленный конец подтвердит повторную передачу. давайте посмотрим, что происходит на принимающем конце. когда обычные данные приходят последовательно (сегмент 43), принимающий tcp передает 256 байт данных пользовательскому процессу. однако следующий принятый сегмент (сегмент 46) не в порядке; стартовый номер последовательности данных (6913) не является следующим ожидаемым номером последовательности (6657). tcp сохраняет 256 байт данных и отвечает посредством ack с самый большим номером последовательности, который был принят успешно, плюс один (6657). следующие семь сегментов, принятых vangogh (48, 50, 52, 54, 55, 57 и 59), также не в порядке. данные сохраняются принимающим tcp, и генерируются дублированные ack. таким образом, для tcp не существует способа сообщить удаленному концу, что сегмент отсутствует. помимо этого tcp не может подтвердить поврежденные данные. все что может сделать vangogh в подобном случае - это продолжать посылать ack с номером 6657. когда прибывают отсутствующие данные (сегмент 63), принимающий tcp имеет в своем буфере байты данных 6657-8960. он передает эти 2304 байта пользовательскому процессу. все 2304 байта подтверждены в сегменте 72. также обратите внимание на то, что этот ack объявляет окно равное 5888 (8192 - 2304), так как пользовательский процесс не имеет возможности прочитать 2304 байта, которые уже готовы для него. если мы рассмотрим более подробно вывод команды tcpdump для моментов времени 14 и 21 на рисунке 21.6, то увидим, что они были вызваны получением трех дублированных ack, а это указывает на то, что пакет был потерян. во всех этих случаях только один пакет был передан повторно. мы продолжим рассмотрение этого примера в разделе "пример переполнения (продолжение)" этой главы, после того как рассмотрим более подробно алгоритм предотвращения переполнения. алгоритм предотвращения переполнения медленный старт, который мы описали в разделе "медленный старт" главы 20, это способ первоначально установить поток данных по соединению. однако, в это же самое время мы достигнем предела у промежуточного маршрутизатора, при котором пакеты будут отбрасываться. предотвращение переполнения это способ, позволяющий предотвратить потерю пакетов. подробности можно найти в [jacobson 1988]. предположение, на котором строится этот алгоритм, заключается в том, что из-за различных повреждений теряется очень малое число пакетов (значительно меньше чем 1%), поэтому потеря пакетов сигнализирует о том, что в каком-либо месте сети между источником и назначением появилось переполнение. существуют два признака, по которым можно определить, что пакеты теряются: появление тайм-аутов и получение дублированных ack. (мы видели последнее в разделе "пример переполнения" этой главы. если же использовать тайм-аут как показатель возникновения переполнения, то нам потребуется хороший алгоритм расчета rtt, примерно такой, как описан в разделе "определение времени возврата".) предотвращение переполнения и медленный старт это независимые друг от друга алгоритмы, более того, работающие с различными объектами. однако, когда возникает переполнение, мы хотим замедлить скорость передачи пакетов по сети, а затем использовать медленный старт, чтобы начать все с начала. на практике эти алгоритмы используются вместе. предотвращение переполнения и медленный старт требуют, чтобы для каждого соединения были определены две переменные: окно переполнения, cwnd, и размер порога медленного старта, ssthresh. вместе алгоритмы работают следующим образом: инициализация заданного соединения устанавливает cwnd в один сегмент, а ssthresh в 65535 байт. подпрограмма вывода tcp определит, какое из значений меньше: cwnd или окно, объявленное получателем и никогда не пошлет больше минимального значения. предотвращение переполнения это способ контролировать поток данных, со стороны отправителя, тогда как объявление окна это способ контролировать поток данных, со стороны получателя. первый основан на оценке отправителем того, насколько переполнена сеть, тогда как последний связан с величиной доступного буферного пространства у получателя для данного соединения. когда возникает переполнение (на что указывает тайм-аут или получение дублированных ack), одна половина текущего размера окна (меньшее значение из величин cwnd и размера окна, объявленного получателем, но по меньшей мере два сегмента) сохраняется в ssthresh. более того, если мы узнали о переполнении с помощью тайм-аута, cwnd устанавливается в один сегмент (то есть осуществляется медленный старт). когда новые данные подтверждены удаленным концом, cwnd увеличивается, однако способ этого увеличения зависит от того, работает ли алгоритм медленного старта или предотвращения переполнения. если cwnd меньше или равно ssthresh, используется медленный старт; иначе используется предотвращение переполнения. медленный старт продолжается до тех пор, пока мы не достигнем половины пути до того момента где были, когда возникло переполнение (то есть, до того момента пока мы не запишем половину размера окна, которое доставило нам проблемы в шаге 2), после чего используется алгоритм предотвращения переполнения. медленный старт требует, чтобы cwnd начиналась с одного сегмента и увеличивалась на один сегмент каждый раз при приеме ack. как указано в разделе "медленный старт" главы 20, это открывает окно экспотенциально: посылается один сегмент, затем два, затем четыре и так далее. предотвращение переполнения требует, чтобы cwnd увеличивалась на 1/cwnd плюс меньшая дробная часть размера сегмента (размер сегмента, поделенный на 8) каждый раз, когда прибывает ack. (это ошибка реализации, которая присутствовала во всех релизах 4.3bsd и даже в 4.4bsd. но этой ошибки нет в будущих реализациях [floyd 1994]. обратите внимание на то, что в примерах ниже в главе используется этот термин, потому что примеры исполнялись на реализации с ошибкой [см. рисунок 21.9 и рисунок 21.11]). это увеличение посредством сложения, по сравнению с экспотенциальным увеличением при медленном старте. мы хотим увеличивать cwnd по крайней мере на один сегмент за каждый промежуток времени равный времени возврата (вне зависимости от того, сколько ack было принято за этот rtt), тогда как медленный старт увеличивает cwnd на количество ack принятых за время возврата. прибавление меньшей дробной части размера сегмента позволяет быстрее открывать большие окна. релиз 4.3bsd tahoe, описанный в [leffler et al. 1989], осуществляет медленный старт, только если удаленный конец находится в другой сети. это было изменено в релизе 4.3bsd reno таким образом, что медленный старт осуществляется всегда.
на рисунке 21.8 приведено описание медленного старта и предотвращения переполнения. мы показали размер cwnd и ssthresh в блоках сегментов, тогда как в действительности их размер измеряется в байтах.
рисунок 21.8 медленный старт и предотвращение переполнения.
на этом рисунке мы предположили, что переполнение возникает, когда cwnd имеет значение равное 32 сегментам. ssthresh устанавливается в 16 сегментов, а cwnd устанавливается в 1 сегмент. один сегмент посылается в момент времени 0 и предполагается, что ack на него возвращается в момент времени 1, cwnd увеличивается до 2 сегментов. затем отправляется два сегмента и предполагается, что их ack прибывают в момент времени 2, cwnd увеличивается до 4 сегментов (по одному разу на каждый ack). этот экспотенциальный рост продолжается до тех пор, пока cwnd не будет равно ssthresh, а именно после того как 8 ack были приняты между моментами времени 3 и 4. с этой точки увеличение cwnd линейное, причем максимальный увеличение - это увеличение на один сегмент за период равный времени возврата. как видно из этого рисунка, термин "медленный старт" не вполне корректен. это, скорее, замедление передачи пакетов, которое вызвано переполнением, однако скорость увеличения количества пакетов, отправленных в сеть, увеличивается в течение медленного старта. скорость увеличения не уменьшается до тех пор, пока не будет достигнуто значение ssthresh, когда начинает действовать предотвращение переполнения. быстрая повторная передача и алгоритм быстрого восстановления в тексте не приводится достаточно жесткого разграничения между алгоритмом быстрой повторной передачи и быстрого восстановления. это два абсолютно независимых алгоритма. алгоритм быстрой повторной передачи вступает в действие, когда tcp определяет потерю сегмента и номер потерянного сегмента по наличию небольшого количества последователььных дублированных подтверждений (ack). потерянный сегмент передается повторно. алгоритм быстрого востановления говорит, что после быстрой повторной передачи необходимо осуществить предотвращение переполнения, а не медленный старт. алгоритм быстрой повторной передачи впервые появился в 4.3bsd tahoe, однако за ним неправильно следовал медленный старт. алгоритм быстрого восстановления впервые был применен в 4.3bsd reno. в 1990 году [jacobson 1990b] алгоритм предотвращения переполнения был модифицирован. мы уже видели эти модификации в действии в примере переполнения (раздел "пример переполнения" этой главы). перед тем как познакомиться с этими изменениями представьте, что tcp требует сгенерировать немедленное подтверждение (дублированный ack), когда принят поврежденный сегмент. этот дублированный ack не должен быть задержан. цель дублированного ack заключается в том, чтобы сообщить удаленному концу о том, что сегмент был получен поврежденным, и сообщить, какой ожидается номер последовательности. так как мы не знаем, было ли дублирование ack вызвано потерей сегмента или просто тем, что изменился порядок следования сегментов, мы ожидаем прихода небольшого количества дублированных ack. это означает, что если сегменты просто пришли в другом порядке, будет получено только один или два дублированных ack перед тем, как перемешанные сегменты будут обработаны, после чего будет сгенерирован новый ack. если же последовательно пришло три или более дублированных ack, это уже является признаком того, что сегмент был потерян (раздел "пример переполнения"). мы осуществляем повторную передачу отсутствующего сегмента, не ожидая истечения таймера повторной передачи. также мы осуществляем предотвращение переполнения, но не медленный старт. на рисунке 21.7 мы видели, что медленный старт не осуществлялся после того, как было принято три дублированных ack. вместо этого отправитель осуществил повторную передачу, за которой следует три сегмента новых данных (сегменты 67, 69 и 71), перед тем как были получены подтверждения на повторную передачу (сегмент 72). причина того, что в этом случае не был применен медленный старт, заключается в том, что получение дублированных ack сообщило нечто большее, нежели просто о потере одного пакета. так как получатель может только генерировать дублированные ack, когда прибывает еще один сегмент, можно сказать, что этот сегмент вышел из сети и находится в буфере получателя. таким образом, данные все еще двигаются между двумя концами, и мы не хотим внезапно уменьшить поток, воспользовавшись медленным cтартом. алгоритм функционирует следующим образом.
мы увидим, что произойдет с переменными cwnd и ssthresh, в следующем разделе. пример переполнения (продолжение) просматривая соединение с использованием tcpdump и отладочной опции сокетов (которую мы описали в разделе "пример rtt"), мы можем увидеть значения cwnd и ssthresh при передаче каждого сегмента. если максимальный размер сегмента (mss) равен 256 байт, исходные значения cwnd и ssthresh будут равны 256 и 65535 соответственно. каждый раз, когда принимается ack, cwnd увеличивается на значение mss и принимает значения 512, 768, 1024, 1280 и так далее. предположим, что переполнения не происходит, поэтому окно переполнения достигнет значения окна, объявленного получателем, а это, в свою очередь, будет означать, что объявленное окно ограничивает поток данных. однако нам интересно посмотреть, что произойдет в случае возникновения переполнения. рассмотрим тот же пример из раздела "пример rtt". в этом примере переполнение появлялось четыре раза. был тайм-аут при передаче исходного syn, который предназначался для установления соединения (рисунок 21.5), после чего, в процессе передачи данных, было потеряно три пакета (рисунок 21.6). на рисунке 21.9 показаны значения двух переменных cwnd и ssthresh, когда осуществлялась повторная передача исходного syn, за которым следовало семь первых сегментов данных. (мы показали обмен исходными сегментами данных и их ack на рисунке 21.2.) переданные байты данных показаны в формате вывода команды tcpdump: 1:257(256), что означает байты с 1 по 256. когда возникает тайм-аут при передаче syn, ssthresh устанавливается в свое минимальное значение (512 байт, что равно, в этом примере, двум сегментам). cwnd устанавливается в один сегмент (256 байт), чтобы войти в фазу медленного старта. когда получены syn и ack, с этими переменными ничего не происходит, так как новые данные не были подтверждены. когда прибывает ack 257, мы все еще находимся в режиме медленного старта, так как cwnd меньше либо равно ssthresh, поэтому cwnd увеличивается на 256. то же самое происходит, когда прибывает ack 513. когда прибывает ack 769, мы больше не находимся в режиме медленного старта, однако переходим в режим предотвращения переполнения. новое значение cwnd рассчитывается следующим образом
cwnd ¬ cwnd + (разм.сегмента x разм.сегмента)/cwnd + разм.сегмента/8
это больше на 1/cwnd, чем то, что мы показали ранее, принимая во внимание то, что cwnd рассчитывается в действительности в байтах, а не в сегментах. для этого примера мы рассчитаем
cwnd ¬ 768 + (256 x 256)/768 + 256/8
рисунок 21.9 пример предотвращения переполнения.
что равно 885 (с использованием целочисленной арифметики). когда прибывает следующий ack 1025, мы рассчитаем
cwnd ¬ 885 + (256 x 256)/885 + 256/8
что равно 991. это суммарное увеличение cwnd продолжается до появления первой повторной передачи, которая происходит в районе 10-секундной метки на рисунке 21.6. рисунок 21.10 это график для тех же самых данных, которые приведены на рисунке 21.6, но сюда добавлены значения cwnd. первые шесть значений cwnd на этом рисунке - это значения, которые мы рассчитали для рисунка 21.9. на этом рисунке невозможно указать разницу между экспотенциальным увеличением в течение медленного старта и суммарным увеличением в течение предотвращения переполнения, потому что фаза медленного старта проходит очень быстро. нам необходимо объяснить, что происходит в трех точках, когда возникает повторная передача. вспомним, что каждая повторная передача возникает из-за того, что были приняты три дублированных ack (это указывает на то, что пакет был потерян). здесь вступает в действие алгоритм быстрой повторной передачи, описанный в разделе "быстрая повторная передача и алгоритм быстрого восстановления". ssthresh сразу же устанавливается в половину размера окна, который соответствовал тому моменту, когда была осуществлена повторная передача, однако cwnd позволяет продолжать увеличение до тех пор, пока принимаются дублированные ack, так как каждый дублированный ack означает, что сегмент все еще находится в сети (принимающий tcp буферизировал его, ожидая прибытия отсутствующих данных). рисунок 21.10 аналогичен рисунку 21.9 и показывает значения cwnd и ssthresh. номера сегментов в первой колонке соответствуют рисунку 21.7.
рисунок 21.10 значения cwnd и номера отправляемых последовательностей, при передаче данных.
рисунок 21.11 пример предотвращения переполнения (продолжение).
значения cwnd увеличиваются постоянно, от последнего значения на рисунке 21.9 для сегмента 12 (1089), до первого значения на рисунке 21.11 для сегмента 58 (2426). значение ssthresh осталось тем же самым (512), так как за этот период не было осуществлено повторных передач. когда прибыли первые два дублированные ack (сегменты 60 и 61), они просто подсчитываются (третий дублированный ack не прибыл), а cwnd остается неизменным. (эта неизменяющаяся часть рисунка 21.10, предваряет первую повторную передачу.) однако когда прибывает третий ack, ssthresh устанавливается в значение равное половине cwnd. cwnd устанавливается в значение ssthresh плюс размер сегмента, умноженный на количество дублированных ack (1024 + 3 x 256). затем осуществляется повторная передача. прибывает еще пять дублированных ack (сегменты 64-66, 68 и 70), при этом cwnd каждый раз увеличивается на размер сегмента. наконец, прибывает новый ack (сегмент 72), и cwnd устанавливается в значение ssthresh (1024), при этом стартует стандартный алгоритм предотвращения переполнения. так как cwnd меньше или равно ssthresh (они равны), к cwnd добавляется размер сегмента, при этом получается значение 1280. когда прибывает следующий ack (который не показан на рисунке 21.11), cwnd больше чем ssthresh, поэтому cwnd устанавливается в значение 1363. в течение фазы быстрой повторной передачи и быстрого восстановления мы передаем новые данные после получения дублированных ack в сегментах 66, 68 и 70, однако не после получения дублированных ack в сегментах 64 и 65. причина этого заключается в значении cwnd по сравнению с количеством неподтвержденных байтов данных. когда прибывает сегмент 64, cwnd становится равным 2048, однако мы имеем 2304 неподтвержденных байта (девять сегментов: 46, 48, 50, 52, 54, 55, 57, 59 и 63). мы ничего не можем послать. когда прибывает сегмент 65, cwnd становится равным 2304, поэтому мы все еще ничего не можем отправить. однако, когда прибывает сегмент 66, cwnd становится равным 2560, теперь мы можем послать новый сегмент данных. точно так же, когда прибывает сегмент 68, cwnd становится равным 2816, что больше чем 2560 байт неподтвержденных данных, таким образом, мы можем послать еще один новый сегмент данных. то же самое происходит, когда прибывает сегмент 70. когда в момент времени 14,3 происходит следующая повторная передача (см. рисунок 21.10), которая также вызвана приемом трех дублированных ack, мы видим такое же увеличение cwnd как если бы прибыл еще один дублированный ack, после чего происходит уменьшение до 1024. повторная передача в момент времени 21,1 на рисунке 21.10 также происходит при приходе дублированных ack. мы получили еще три дублированных ack после повторной передачи, поэтому мы видим три дополнительных увеличения cwnd, после чего следует уменьшение до 1280. для остальной передачи cwnd увеличивается линейно с окончательным значением 3615. более новые реализации tcp хранят большинство из показателей, которые мы описали в этой главе в записях таблицы маршрутизации. предположим, что tcp соединение закрыто, при этом по соединению было отправлено достаточное количество данных, чтобы получить статистику, и запись в таблице маршрутизации для определенного пункта назначения не является маршрутом по умолчанию. при выполнении этих условий в записи таблицы маршрутизации сохраняется следующая информация (эта информация будет использована при следующих обращениях к этой записи): хэшированный rtt, хэшированное среднее отклонение и порог медленного старта. понятие "достаточное количество данных" - означает 16 окон данных. при этом можно получить 16 примеров rtt, что позволяют фильтру хэшированного rtt получить значение с отклонением в пределах 5% от реального. помимо этого, администратор может воспользоваться командой route(8) , чтобы установить показатели для заданного маршрута: три показателя, упомянутых в предыдущем параграфе, а также mtu, емкость исходящего канала в зависимости от полосы пропускания (раздел "пропускная способность для неинтерактивных данных" главы 20) и емкость входящего канала в зависимости от полосы пропускания. когда устанавливается новое tcp соединение, либо активное, либо пассивное, и пункт таблицы маршрутизации, который используется для этого соединения, имеет значения для этих показателей, соответствующие переменные инициализируются значениями показателей. давайте посмотрим, как tcp обрабатывает icmp ошибки, которые возвращаются по соединению. в основном tcp обрабатывает следующие icmp ошибки: подавление источника, хост недоступен и сеть недоступна. текущие реализации (производные от berkeley) обрабатывают эти icmp ошибки следующим образом:
более ранние реализации bsd некорректно разрывали соединение, когда приходила icmp ошибка о недоступности хоста или недоступности сети.
пример мы можем посмотреть, как icmp ошибка о недоступности хоста обрабатывается на нашем slip канале, когда он погашен в середине соединения. мы установили соединение с хоста slip на хост aix. (на рисунке, находящемся на внутренней стороне обложки, мы видим, что это соединение проходит через slip канал.) после установления соединения и передачи какого-то количества данных, slip канал между маршрутизаторами sun и netb погашен. при этом запись, соответствующая маршруту по умолчанию в sun (которую мы показывали на рисунке 9.2), будет удалена. ожидается, что sun затем будет отвечать на ip датаграммы, направляемые в ethernet сеть 140.252.1, ошибкой icmp о недоступности хоста. мы хотим посмотреть, как tcp обрабатывает эти icmp ошибки. здесь приведена интерактивная сессия на хосте slip:
на рисунке 21.12 показан соответствующий вывод команды tcpdump, полученный на маршрутизаторе bsdi. (установление соединения и все объявления окна удалены.) мы подсоединились к эхо серверу на хосте aix и напечатали "test line" (строка 1). она отразилась эхом (строка 2), и эхо было подтверждено (строка 3). затем мы погасили slip канал. затем ввели "another line" (строка 3) и ожидаем, что tcp отработает тайм-аут и повторно передаст сообщение. и действительно, эта строка отправляется шесть раз перед тем, как будет получен отклик. строки 4-13 показывают первую передачу и следующие четыре повторные передачи, каждая из которых генерирует icmp ошибку о недоступности хоста с маршрутизатора sun. это как раз то, что мы ожидали: ip датаграммы, двигаются от slip к маршрутизатору bsdi (который имеет маршрут по умолчанию, указывающий на sun) и затем на sun, где и находится поврежденный канал. пока происходят эти повторные передачи, slip канал восстанавливается, и повторная передача в строке 14 достигают пункта назначения. строка 15 это эхо от aix, а строка 16 - подтверждение на эхо. можно сделать вывод, что tcp игнорирует icmp ошибку о недоступностии хоста и продолжает осуществлять повторные передачи. мы также видим ожидаемое экспотенциальное наращивание времени в каждом тайм-ауте при повторной передаче: первый возникает через 2,5 секунды, затем умножается на 2 (при этом длительность тайм-аута составляет 5 секунд), затем на 4 (10 секунд), затем на 8 (20 секунд) и затем на 16 (40 секунд). после чего мы напечатали третью строку ввода ("line number 3") и увидели, что она отправлена в строке 17, отражена эхом в строке 18, и эхо подтверждено в строке 19. сейчас мы хотим посмотреть, что произойдет, когда tcp осуществляет повторную передачу, а затем прекращает попытки после получения icmp ошибки о недоступности хоста. для этого мы снова выключаем slip канал. после того как канал выключен, мы печатаем "the last line" и видим, что она передается 13 раз перед тем, как tcp прекращает попытки. (строки 30-43 удалены из вывода. в них показаны дополнительные повторные передачи.) необходимо обратить внимание на одну деталь которая, заключается в том, что сообщение об ошибке печатается нашей программой sock, когда она в конце концов прекращает работу: "no route to host". (нет маршрута к хосту.) это соответствует ошибке операцинной системы unix, которая, в свою очередь соответствует icmp ошибке о недоступности хоста (рисунок 6.12). значит, tcp сохраняет icmp ошибку, которую он получил по соединению, и когда он в конце концов прекращает свою работу, то печатает эту ошибку вместо "connection timed out" (соединение закрыто по тайм-ауту). и в заключение, обратите внимание на то, что временные промежутки между повторными передачами в строках 22-46 сравнимы с промежутками в строках 6-14. это происходит из-за того, что tcp обновил свои оценочные функции, когда третья строка, которую мы напечатали, была отправлена и подтверждена без повторных передач в строках 17-19. исходный тайм-аут повторной передачи в настоящее время равен 3 секундам, при этом последующие значения будут равны 6, 12, 24, 48 и затем верхний предел 64.
рисунок 21.12 обработка tcp полученной icmp ошибки о недоступности хоста. когда tcp отрабатывает тайм-ауты и осуществляет повторные передачи, он не должен повторно передавать идентичные сегменты (если исходно было 10 пакетов по одному байту, то при повторной передаче можно передать 1 пакет размером десять байт). вместо этого, tcp разрешено осуществлять пересборку пакетов (repacketization), отправляя сегменты большего размера, что может увеличить производительность. (в действительности, сегменты большего размера не могут превосходить по размеру mss, объявленный удаленным получателем.) протокол tcp может себе это позволить, потому что он идентифицирует данные, которые были отправлены и подтверждены, по номерам байтов, а не по номерам сегментов. мы можем легко посмотреть, как это происходит. воспользуемся программой sock, чтобы подсоединиться к discard серверу, и напечатаем одну строку. затем мы отсоединяем ethernet кабель и вводим вторую строку. пока эта вторая строка будет повторно передаваться, мы вводим третью строку. при этом ожидается, что следующая повторная передача будет содержать обе и вторую, и третью строки.
на рисунке 21.13 показан вывод команды tcpdump. (мы удалили установление соединения, прерывание соединения и все объявления окна.)
рисунок 21.13 пересборка пакетов tcp.
в строках 1 и 2 показана первая строка ("hello there"), которая отправлена и подтверждена. затем мы отсоединяем ethernet кабель и печатаем "line number 2" (14 байт, включая символ новой строки). эти байты передаются в строке 3, а затем повторно передаются в строках 4 и 5. перед тем как осуществляется повторная передача в строке 6, мы печатаем "and 3" (6 байт, включая символ новой строки) и видим, что повторная передача на этот раз содержит 20 байт: обе строки, которые мы напечатали. подтверждение, которое прибывает в строке 9, подтверждает все 20 байт. в этой главе детально рассматривается стратегия tcp тайм-аутов и повторных передач. наш первый пример был посвящен потерянному syn, с помощью которого устанавливаются соединения, и мы видели, как применяется экспотенциальное наращивание значений последовательных тайм-аутов при повторной передаче. tcp рассчитывает время возврата и затем использует полученные значения, чтобы поддерживать и обновлять значение хэшированной оценочной функции rtt и хэшированной оценочной функции среднего отклонения. эти два показателя затем используются при расчете следующего значения тайм-аута для повторной передачи. большинство реализаций рассчитывают только один rtt на окно. алгоритм карна снимает проблему двусмысленной повторной передачи, поэтому не приходится рассчитывать rtt в случае потери пакета. наш подробный пример, в котором было потеряно три пакета, позволил нам рассмотреть большинство алгоритмов tcp в действии: медленный старт, предотвращение переполнения, быструю повторную передачу и быстрое восстановление. мы также имели возможность рассчитать оценочные функции rtt tcp вместе с окном переполнения и порогом медленного старта, а также сравнить эти значения с реальными значениями, полученными из вывода отладочных программ. мы закончили рассмотрением влияния различных icmp ошибок на tcp соединение, и как tcp позволено перестраивать порядок движения данных. мы видели, что "мягкие" icmp ошибки не приводят к разрыву соединения, однако запоминаются таким образом, что когда соединение разрывается по каким-либо причинам, ошибка может быть выведена в виде сообщения. упражнения
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
