TCP не посылает один пакет, ожидая прихода подтверждения, чтобы послать следующий. Вместо этого он использует принцип «скользящего окна». Этот принцип позволяет послать несколько сообщений и только потом ожидать подтверждения.
Скользящее окно TCP
Выражаясь образно, TCP как бы накладывает окно на поток данных, ожидающих передачи, и передает все данные, попавшие в окно. Приняв подтверждение о доставке всех данных, TCP перемещает окно дальше по потоку и передает следующие попавшие в него сообщения. Работая сразу с несколькими сообщениями, TCP может одновременно «выставить» их на сетевой канал и только потом ожидать прихода подтверждения. Метод скользящего окна значительно увеличивает производительность соединения, а также эффективность циклов обмена сообщениями и подтверждениями об их доставке.
Передача сообщений и подтверждений о доставке по схеме скользящего окна.
Передатчик и приемник используют скользящее окно шириной в три пакета. То есть передатчик сначала высылает три пакета и только после ждет прихода подтверждения. Приняв подтверждение о доставке третьего последнего пакета, передатчик может посылать следующие три.
TCP регулирует полосу пропускания сети, договариваясь с другой стороной о некоторых параметрах потока данных. Причем процесс регулировки происходит на протяжении всего соединения TCP. В частности, регулировка заключается в изменении размеров скользящего окна. Если сеть загружена не сильно и вероятность столкновения данных минимальна, TCP может увеличить размер скользящего окна. При этом скорость выдачи данных на канал увеличивается и соединение становится более эффективным, поскольку через сеть проходит больше данных за одно и то же время.
Если, наоборот, вероятность столкновения данных велика, TCP уменьшает размер скользящего окна. Если размер скользящего окна принять равным восьми пакетам при обычном сетевом трафике, то в худших условиях, когда Интернет сильно загружен, его размер может уменьшиться до пяти. Наоборот, когда данных в сети немного, размер окна может увеличиться, например, до 10-20 пакетов.
Имейте в виду, что описанная в предыдущих абзацах схема несколько упрощена. На самом деле TCP задает размер окна в байтах. То есть размер окна по умолчанию может равняться нескольким тысячам байтов, а не восьми, десяти и двенадцати байтам, как в предыдущем примере. Как правило, модуль TCP передает несколько сегментов, прежде чем скользящее окно заполнится целиком. Большинство систем в Интернет устанавливают окно равным по умолчанию 4096 байтам. Иногда размер окна равен 8192 или 16384 байтам.
В тех случаях, когда другие методы обеспечения надежности не срабатывают и пакеты теряются, применяют методы повторной передачи пакетов. Эти методы требуют использования протоколов, ориентированных на соединение.
Чтобы убедиться в необходимости повторной передачи данных, отправитель нумерует отправляемые кадры и для каждого кадра ожидает от приемника так называемой положительной квитанции (Positive Acknowledgment, АСК) - служебного кадра, извещающего о том, что исходный кадр получен и данные в нем корректны. Для того чтобы организовать такую нумерацию, и нужна процедура логического соединения - она дает точку отсчета, с которой начинается нумерация. Время ожидания квитанции ограничено - при отправке каждого кадра передатчик запускает таймер, и, если по истечении заданного времени положительная квитанция на получена, кадр считается утерянным. Приемник в случае получения кадра с искаженными данными может отправить отрицательную квитанцию (Negative Acknowledgment, NACK) - явное указание на то, что данный кадр нужно передать повторно.
Существует два метода организации процесса обмена квитанциями: метод простоя источника и метод скользящего окна.
Метод простоя источника требует, чтобы источник, пославший кадр, ожидал получения квитанции (положительной или отрицательной) от приемника и только после этого посылал следующий кадр (или повторял искаженный). Если же квитанция не приходит в течение тайм-аута, то кадр (или квитанция) считается утерянным и его передача повторяется. На рис. 6.6, а видно, что в этом случае производительность обмена данными ниже потенциально возможной, - хотя передатчик и мог бы послать следующий кадр сразу же после отправки предыду-
щего, он обязан ждать прихода положительной квитанции. (Далее, где это не искажает существо рассматриваемого вопроса, положительные квитанции для краткости будут называться просто «квитанциями».)
Недостатки этого метода коррекции особенно заметны на низкоскоростных каналах связи, то есть в территориальных сетях.
Второй метод называется методом скользящего окна (sliding window). В этом методе для повышения скорости передачи данных источнику разрешается передать некоторое количество кадров в непрерывном режиме, то есть в максимально возможном для источника темпе без получения на эти пакеты квитанций. Количество пакетов, которые разрешается передавать таким образом, называется размером окна. Рисунок 6.6, б иллюстрирует применение данного метода для окна размером W пакетов.
В начальный момент, когда еще не послано ни одного пакета, окно определяет диапазон пакетов с номерами от 1 до W включительно. Источник начинает передавать пакеты и получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности, что и пакеты, которым они
соответствуют. В момент t t при получении первой квитанции Kj окно сдвигается на одну позицию, определяя новый диапазон от 2 до (W + 1).
Процессы отправки пакетов и получения квитанций идут достаточно независимо друг от друга. Рассмотрим произвольный момент времени t n , когда источник получает квитанцию на пакет с номером п. Окно сдвигается вправо и определяет диапазон разрешенных к передаче пакетов от (n + 1) до (W + п). Все множество пакетов, выходящих из источника, можно разделить на перечисленные ниже группы (см. рис. 6.6, б).
Пакеты с номерами от 1 до η уже были отправлены и квитанции на них получены, то есть они находятся за пределами окна слева.
Пакеты, начиная с номера (η + 1) и заканчивая номером (W + п), находятся в пределах окна и потому могут быть отправлены, не дожидаясь прихода какой-либо квитанции. Этот диапазон может быть разделен еще на два поддиапазона:
О пакеты с номерами от (η + 1) до m уже отправлены, но квитанции на них еще не получены;
О пакеты с номерами от m до (W + п) пока не отправлены, хотя запрета на это нет.
Все пакеты с номерами, большими или равными (W + η + 1), находятся за пределами окна справа и поэтому пока не могут быть отправлены.
Перемещение окна вдоль последовательности номеров пакетов иллюстрирует рис. 6.6, в. Здесь t〇 - исходный момент, tļ и t n - моменты прихода квитанций на первый и η-й пакет соответственно. Каждый раз, когда приходит квитанция, окно сдвигается влево, но его размер при этом не меняется и остается равным W.
При отправке пакета в источнике устанавливается тайм-аут. Если за это время квитанция на отправленный пакет не придет, пакет (или квитанция на него) считается утерянным, и пакет передается снова.
Если же поток квитанций поступает регулярно в пределах допуска в W пакетов, то скорость обмена достигает максимально возможной величины для данного канала и принятого протокола.
В некоторых реализациях скользящего окна от приемника не требуется посылать квитанции на каждый принятый корректный пакет. Если среди пришедших пакетов нет «прогалин», то приемнику достаточно послать квитанцию только на последний принятый пакет, и эта квитанция будет свидетельствовать отправителю о том, что все предыдущие пакеты также дошли благополучно.
В других методах используются отрицательные квитанции. Отрицательные квитанции бывают двух типов - групповые и избирательные. Групповая квитанция содержит номер пакета, начиная с которого нужно повторить передачу всех пакетов, отправленных передатчиком в сеть. Избирательная отрицательная квитанция требует повторной передачи только одного пакета.
Метод скользящего окна имеет два параметра, которые могут существенно влиять на эффективность передачи данных между передатчиком и приемником, - это размер окна и величина тайм-аута ожидания квитанции. Выбор тайм-аута зависит не от надежности сети, а от задержек передачи пакетов сетью.
В надежных сетях, в которых пакеты искажаются и теряются редко, для повышения скорости обмена данными размер окна нужно увеличивать, так как при этом передатчик будет посылать пакеты с меньшими паузами. В ненадежных сетях размер окна следует уменьшать, так как при частых потерях и искажениях пакег тов резко возрастает объем вторично передаваемых через сеть пакетов, а значит, пропускная способность сети во многом расходуется вхолостую, и полезная пропускная способность сети падает.
Размер окна может быть постоянным параметром алгоритма скользящего окна. В этом случае он выбирается при установлении соединения и не меняется в течение сеанса. Существуют также адаптивные версии алгоритма, когда размер окна меняется в течение сеанса в соответствии с текущим состоянием сети и узла назначения.
Надежность сети в подобных алгоритмах определяется по таким признакам потерь пакетов, как истечение тайм-аута для положительной квитанции или приходе дубликата квитанции на определенный пакет. Дубликат говорит о том, что в узле назначения истек тайм-аут ожидания очередного пакета, и узел запрашивает отправку этого пакета вторично. При наступлении таких событий узел отправитель уменьшает размер окна, стараясь найти оптимальный режим передачи данных.
Размер окна может быть также изменен узлом назначения. Причиной уменьшения размера окна является перегрузка узла назначения, который не успевает обработать поступающие пакеты. Мы вернемся к этой проблеме позже, в разделе «Обратная связь» главы 7, когда будем изучать методы борьбы с перегрузками.
Существуют также реализации метода скользящего окна, в которых в качестве размера окна используется не количество пакетов, а количество байтов. Наиболее известным примером такого подхода является протокол TCP.
В общем случае метод скользящего окна более сложен в реализации, чем метод простоя источника, так как передатчик должен хранить в буфере все пакеты, на которые пока не получены положительные квитанции. Кроме того, при использовании данного метода требуется отслеживать несколько параметров алгоритма: размер окна W, номер пакета, на который получена квитанция, номер пакета, который еще можно передать до получения новой квитанции.
Алгоритм адаптивного тайм-аута KARN
Тайм-ауты
Номера байтов
Дубликаты
Проблемы, решаемые процедурой handshaking
Если станция передает 20 байт, то сервер увеличит ACK на 20 (станет 751 байт) и т.д.
Подтверждения генерируется для всех байт, которые приходят в нужной последовательности. Если будут переданы дубликаты, это не испортит картину. Можно 3 раза подтвердить, что пришло 731 байт (это пример). Все подтверждения кумулятивные. Потерянные подтверждения не создают проблем.
Дубликаты в TCP могут возникать:
Последовательные номера до 2 32 . При скорости 2 Мбит/сек на перебор всех значений уйдет 9 часов. Из-за дублирования последовательного номера может получиться дубликат. С повышением скорости вероятность этого увеличивается.
Борются невероятным количеством средств.
Задают тайм-ауты. Значение тайм-аута влияет на производительность. Тайм-аут связан с временем двойного пробега (RTT). Большой тайм-аут – большое ожидание при ошибке. Маленький тайм-аут – ненужная повторная передача.
Существуют различные алгоритмы адаптивного тайм-аута (задача ОС). CISCO использует алгоритм KARN.
Суть алгоритма. Вычисляется среднее время RTT, умножается на определенный коэффициент (в KARN коэффициент равен 2). Необходимо изменять не только среднее время тайм-аута, но изменять размер окна. В KARN окно меняется до тех пор, пока свободным не станет от 20% до 40% от окна.
Протокол TCP предполагает динамическое окно. Получатель сообщает то число байт, которое он может принять (от 0 до 65535). Начальный номер окна всегда устанавливается на стадии установления соединения. Приемник определяет, какое окно должно быть, согласно минимальным возможностям. Прикладной процесс получателя, который использует буферы, достаточно сильно влияет на производительность TCP. Правильный подбор размера окна оптимизирует TCP. Открывается окно, когда принимающий процесс на другой стороне читает подтверждение и освобождает буфер TCP. Если левая граница совпала с правой границей, отправитель должен прекратить передачу (нулевое окно). Окно закрывается, когда происходит передача и подтверждение данных (левая граница двигается вправо).
Завершается соединение, когда станция шлет серверу флаг FIN. Сервер отсылает ACK и FIN. Далее сервер шлет еще раз FIN, а станция ACK и FIN.
Защита от перегрузок – медленный старт – не сразу и быстро отправлять пакеты в сеть.
Существует также механизм быстрой повторной передачи (не нужен медленный старт) и
механизм задержанного подтверждения (в Windows).
Для увеличения коэффициента полезной загрузки канала используется механизм «скользящего окна». Предварительно отметим, что если рассмотренные выше механизмы квитирования и тайм-аута предполагали наличие между взаимодействующими узлами полудуплексного канала, то механизм скользящего окна может быть реализован только при наличии дуплексного канала. При этом, кадры данных и квитанции могут передаваться одновременно по разным каналам (рис. 1.48).
Суть механизма «скользящего окна» заключается в следующем. Узел-отправитель может послать подряд несколько кадров данных без получения на эти кадры квитанций. При этом кадры циклически нумеруются от 1 до W, где W - размер (ширина) окна - максимальное количество кадров, которые могут быть переданы без подтверждения. Номер кадра указывается в заголовке. Ширина окна может быть выбрана из условия максимальной загрузки прямого канала связи от узла-отправителя к узлу-получателю, которая может быть достигнута за счёт передачи ещё нескольких кадров за время ожидания квитанции на первый кадр:
где - минимальное время ожидания квитанции; -
время передачи кадра, - время распространения сигнала по каналу
связи, - время, затрачиваемое в узле-получателе на обработку кадра и
формирование квитанции.
Как следует из представленного выражения, если пренебречь временем распространения сигнала по каналу связи и временем обработки кадра в узле-получателе У 2 , то минимальная ширина окна должна быть не менее 2.
Положим, что в начальный момент времени окно узла-отправителя У1 выглядит так, как это показано на рис.1.49,а), что означает возможность передачи W кадров без подтверждения. Для того чтобы простой канала связи свести к минимуму, квитанция в узле-получателе может быть сформирована раньше, чем закончится передача всех W кадров, то есть узел-получатель может отправить квитанцию узлу-отправителю в любой удобный для него момент времени. Такой момент обычно связан с формированием кадра данных, посылаемого по обратному каналу от узла У2 к узлу У1. При этом в заголовок этого кадра вставляется квитанция, указывающая номер последнего кадра, который был принят без ошибок (положительная квитанция) или с ошибкой (отрицательная квитанция). Если квитанция на кадр с номером к (1 < к < W) - положительная, то окно в узле У1 сдвигается так, как это показано на рис. 1.49,6), что означает возможность передачи ещё W кадров с номерами без квитанции. Если квитанция на кадр с номером - отрицательная, то это означает, что кадры с номерами до (k-1) приняты правильно, а кадры, начиная с номера к, должны быть переданы повторно. При этом окно в узле У1 сдвигается так, как это показано на рис.1.49,в) что означает возможность передачи ещё W кадров с номерами без квитанции. Таким образом, квитанция может формироваться не на все передаваемые кадры, а только на некоторые из них, причём, если положительная квитанция пришла на кадр с номером к, то считается, что этот кадр и все предыдущие кадры с номерами от 1 до (к -1) приняты без ошибок. Аналогично, отрицательная квитанция на кадр с номером к означает, что все предыдущие кадры приняты без ошибок, и повторной передаче подлежат все ранее переданные кадры, начиная с номера к.
Один из наиболее естественных приемов, используемых для организации надежной передачи - это квитирование . Отправитель отсылает данные и ждет, пока к нему не придет квитанция, подтверждающая, что его данные благополучно дошли до адресата. В протоколе TCP используется частный случай квитирования - алгоритм скользящего окна. Прежде чем перейти к подробному рассмотрению особенностей реализации этого алгоритма в протоколе TCP, очень полезно обсудить его с общих позиций.
Итак, существует два метода организации процесса обмена квитанциями: метод простоя источника и метод скользящего окна.
Метод простоя источника требует, чтобы источник, пославший кадр (в данном случае не имеет значения, какое название используется для единицы передаваемых данных), дожидался от приемника квитанции, извещающей о том, что исходный кадр получен и данные в нем корректны, и только после этого посылал следующий кадр (или повторял искаженный). Если же квитанция в течение тайм-аута не пришла, то кадр (или квитанция) считается утерянным и его передача повторяется. На рис. 17.10 показано, что второй кадр отсылается только после того, как пришла квитанция, подтверждающая доставку первого кадра.
Рис. 17.10. Метод простоя источника
Однако затем произошла длительная пауза в отправке следующего третьего кадра. В течение этой паузы источник был вынужден повторить передачу кадра 2, так как квитанция на первую его копию была потеряна. Понятно, что при таком алгоритме работы источника принимающая сторона должна уметь распознавать дублирующиеся кадры и избавляться от них.
Достаточно очевидно, что при использовании данного метода производительность обмена данными ниже потенциально возможной - передатчик мог бы посылать следующий кадр сразу же после отправки предыдущего, но он обязан ждать прихода квитанции.
Второй метод называется методом скользящего окна (sliding window). В этом методе для повышения скорости передачи данных источнику разрешается передать некоторое количество кадров в непрерывном режиме, то есть в максимально возможном для источника темпе еще до получения на эти кадры квитанций . Количество кадров, которые разрешается передавать таким образом, называется размером окна.
Рисунок 17.11 иллюстрирует применение данного метода для окна размером 5 кадров.
Рис. 17.11. Метод скользящего окна
В начальный момент, когда еще не послано ни одного кадра, окно определяет диапазон номеров кадров от 1 до 5 включительно. Источник начинает передавать кадры и через какое-то время получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности (но не обязательно в том же темпе), что и кадры, которым они соответствуют. В момент получения отправителем квитанции 1 окно сдвигается на одну позицию вверх, определяя новый диапазон разрешенных к отправке кадров (от 2 до 6).
Процессы отправки пакетов и получения квитанций идут достаточно независимо друг от друга. В нашем примере отправитель продолжает передавать кадры, но некоторое время не получает на них квитанции. После передачи кадра 6 окно исчерпывается, и источник приостанавливает передачу.
После получения квитанции 2 (на кадр 2) окно сдвигается вверх на единицу, определяя диапазон разрешенных к передаче кадров от 3 до 7. Аналогичное «скольжение» окна вверх происходит после получения каждой квитанции : окно сдвигается вверх на 1, но его размер при этом не меняется и остается равным 5. После прихода квитанции 8 окно оказывается в диапазоне от 9 до 13 и остается таковым достаточно долго, так как по каким-то причинам источник перестает получать подтверждения о доставке кадров. Отправив последний разрешенный кадр 13, передатчик снова прекращает передачу с тем, чтобы возобновить ее после прихода квитанции 9.
При отправке кадра в источнике устанавливается тайм-аут. Если за установленное время квитанция на отправленный кадр не придет, то кадр (или квитанция на него) считается утерянным, и кадр передается снова. Если же поток квитанций поступает регулярно в пределах допуска в 5 кадров, то скорость обмена достигает максимально возможной величины для данного канала и принятого протокола.
В общем случае метод скользящего окна более сложен в реализации, чем метод простоя источника, так как передатчик должен хранить в буфере копии всех кадров, на которые пока не получены квитанции. Кроме того, при использовании данного метода требуется отслеживать несколько параметров алгоритма, таких как размер окна, номер кадра, на который получена квитанция, номер кадра, который еще можно передать до получения новой квитанции.
