Алгоритм адаптивного тайм-аута 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).

Что такое скользящее окно?

TCP не посылает один пакет, ожидая прихода подтверждения, чтобы послать следующий. Вместо этого он использует принцип «скользящего окна». Этот принцип позволяет послать несколько сообщений и только потом ожидать подтверждения.

Скользящее окно TCP

Что такое транспортный протокол?

Выражаясь образно, TCP как бы накладывает окно на поток данных, ожидающих передачи, и передает все данные, попавшие в окно. Приняв подтверждение о доставке всех данных, TCP перемещает окно дальше по потоку и передает следующие попавшие в него сообщения. Работая сразу с несколькими сообщениями, TCP может одновременно «выставить» их на сетевой канал и только потом ожидать прихода подтверждения. Метод скользящего окна значительно увеличивает производительность соединения, а также эффективность циклов обмена сообщениями и подтверждениями об их доставке.

Передача сообщений и подтверждений о доставке по схеме скользящего окна.

Передатчик и приемник используют скользящее окно шириной в три пакета. То есть передатчик сначала высылает три пакета и только после ждет прихода подтверждения. Приняв подтверждение о доставке третьего последнего пакета, передатчик может посылать следующие три.

TCP регулирует полосу пропускания сети, договариваясь с другой стороной о некоторых параметрах потока данных. Причем процесс регулировки происходит на протяжении всего соединения TCP. В частности, регулировка заключается в изменении размеров скользящего окна. Если сеть загружена не сильно и вероятность столкновения данных минимальна, TCP может увеличить размер скользящего окна. При этом скорость выдачи данных на канал увеличивается и соединение становится более эффективным, поскольку через сеть проходит больше данных за одно и то же время.

Если, наоборот, вероятность столкновения данных велика, TCP уменьшает размер скользящего окна. Если размер скользящего окна принять равным восьми пакетам при обычном сетевом трафике, то в худших условиях, когда Интернет сильно загружен, его размер может уменьшиться до пяти. Наоборот, когда данных в сети немного, размер окна может увеличиться, например, до 10-20 пакетов.

Имейте в виду, что описанная в предыдущих абзацах схема несколько упрощена. На самом деле TCP задает размер окна в байтах. То есть размер окна по умолчанию может равняться нескольким тысячам байтов, а не восьми, десяти и двенадцати байтам, как в предыдущем примере. Как правило, модуль TCP передает несколько сегментов, прежде чем скользящее окно заполнится целиком. Большинство систем в Интернет устанавливают окно равным по умолчанию 4096 байтам. Иногда размер окна равен 8192 или 16384 байтам.

Один из наиболее естественных приемов, используемых для организации надежной передачи - это квитирование . Отправитель отсылает данные и ждет, пока к нему не придет квитанция, подтверждающая, что его данные благополучно дошли до адресата. В протоколе 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 кадров, то скорость обмена достигает максимально возможной величины для данного канала и принятого протокола.

В общем случае метод скользящего окна более сложен в реализации, чем метод простоя источника, так как передатчик должен хранить в буфере копии всех кадров, на которые пока не получены квитанции. Кроме того, при использовании данного метода требуется отслеживать несколько параметров алгоритма, таких как размер окна, номер кадра, на который получена квитанция, номер кадра, который еще можно передать до получения новой квитанции.

Один из наиболее естественных приемов, используемых для организации надёжной передачи - это квитирование. Отправитель отсылает данные и ждет, пока к нему не придет квитанция, подтверждающая, что его данные благополучно дошли до адресата. В протоколе TCP используется частный случай квитирования - алгоритм скользящего окна. Прежде чем перейти к подробному рассмотрению особенностей реализации этого алгоритма в протоколе TCP, очень полезно обсудить его с общих позиций.

Метод простоя источника требует, чтобы источник, пославший кадр (в данном случае не имеет значения, какое название используется для единицы передаваемых данных), дожидался от приемника квитанции, извещающей о том, что исходный кадр получен и данные в нем корректны, и только после этого посылал следующий кадр (или повторял искаженный). Если же квитанция в течение тайм-аута не пришла, то кадр (или квитанция) считается утерянным и его передача повторяется. На рис. 1 показано, что второй кадр отсылается только после того, как пришла квитанция, подтверждающая доставку первого кадра. Однако затем произошла длительная пауза в отправке следующего третьего кадра.

В течение этой паузы источник был вынужден повторить передачу кадра 2, так как квитанция на первую его копию была потеряна. Понятно, что при таком алгоритме работы источника принимающая сторона должна уметь распознавать дублирующиеся кадры и избавляться от них.

Рис. 1. Метод простоя источника

Второй метод называется методом скользящего окна (sliding window). В этом методе для повышения скорости передачи данных источнику разрешается передать некоторое количество кадров в непрерывном режиме, то есть в максимально возможном для источника темпе еще до получения на эти кадры квитанций. Количество кадров, которые разрешается передавать таким образом, называется размером окна.

Рисунок 2 иллюстрирует применение данного метода для окна размером 5 кадров. В начальный момент, когда еще не послано ни одного кадра, окно определяет диапазон номеров кадров от 1 до 5 включительно. Источник начинает передавать кадры и через какое-то время получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности (но не обязательно в том же темпе), что и кадры, которым они соответствуют. В момент получения отправителем квитанции 1 окно сдвигается на одну позицию вверх, определяя новый диапазон разрешенных к отправке кадров (от 2 до 6).

Рис. 2. Метод скользящего окна

После получения квитанции 2 (на кадр 2) окно сдвигается вверх на единицу, определяя диапазон разрешенных к передаче кадров от 3 до 7. Аналогичное «скольжение» окна вверх происходит после получения каждой квитанции: окно сдвигается вверх на 1, но его размер при этом не меняется и остается равным 5. После прихода квитанции 8 окно оказывается в диапазоне от 9 до 13 и остается таковым достаточно долго, так как по каким-то причинам источник перестает получать подтверждения о доставке кадров. Отправив последний разрешенный кадр 13, передатчик снова прекращает передачу с тем, чтобы возобновить ее после прихода квитанции 9.

Основная идея этого метода (его еще часто называют методом LZ1, см. ) состоит в использовании ранее прочитанной части входного файла в качестве словаря. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Таким образом, метод основан на скользящем окне. Окно разбивается на две части. Часть слева называется буфером поиска. Она будет служить текущим словарем, и в ней всегда содержатся символы, которые недавно поступили и были закодированы. Правая часть окна называется упреждающим буфером, содержащим текст, который будет сейчас закодирован. На практике буфер поиска состоит из нескольких тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Вертикальная черта | между символами t и е означает текущее разделение между двумя буферами. Итак, предположим, что текст «sir_sid_eastman_easily_t» уже сжат, а текст «eases_sea_sick_seals» нуждается в сжатии.

sir_sid_eastman_easily_t

eases_sea_sick_seals

Кодер просматривает буфер поиска в обратном порядке (справа налево) и ищет в нем первое появление символа е из упреждающего буфера. Он обнаруживает такой символ в начале слова easily. Значит, е находится (по смещению) на расстоянии 8 от конца буфера поиска. Далее кодер определяет, сколько совпадающих символов следует за этими двумя символами е. В данном случае совпадение по символам eas имеет длину 3. Кодер продолжает поиск, пытаясь найти более длинные совпадающие последовательности. В нашем (лучае имеется еще одна совпадающая последовательность той же длины 3 в слове eastman со смещением 16. Декодер выбирает самую длинную из них, а при совпадении длин - самую удаленную, и готовит метку (16, 3, «е»).

Выбор более удаленной ссылки упрощает кодер. Интересно отметить, что выбор ближайшего совпадения, несмотря на некоторое усложнение программы, также имеет определенные преимущества. При этом выбирается наименьшее смещение. Может показаться, что в этом нет преимущества, поскольку в метке будет предусмотрено достаточно разрядов для хранения самого большого смещения. Однако, можно следовать LZ77 с кодированием Хаффмана или другого статистического кодирования меток, при котором более коротким смещениям присваиваются более короткие коды. Этот метод, предложенный Бернардом Хердом (Bernard Herd), называется LZH. Если получается много коротких смещений, то при LZH достигается большее сжатие.

Следующую идею очень легко усвоить. Декодер не знает, какое именно совпадение выбрал кодер, ближайшее или самое дальнее, но ему это и не надо знать! Декодер просто читает метки и использует смещение для нахождения текстовой строки в буфере поиска. Для него не важно, первое это совпадение или последнее.

В общем случае, метка из LZ77 имеет три поля: смещение, длина и следующий символ в упреждающем буфере (в нашем случае, это будет второе е в слове teases. Эта метка записывается в выходной файл, а окно сдвигается вправо (или входной файл сдвигается влево) на четыре позиции: три позиции для совпадающей последовательности и одна позиция для следующего символа.

Sid_eastman_easily_tease

s_sea_sick_seals …

Если обратный поиск не обнаружил совпадение символов, то записывается метка со смещением 0 и длиной 0. По этой же причине метка будет иметь третью компоненту. Метки с нулевыми смещением и длиной всегда стоят в начале работы, когда буфер поиска пуст или почти пуст. Первые семь шагов кодирования нашего примера приведены ниже.

	sir_sid_eastman_r
	ir_sid_eastman_e
	r_sid_eastman_ea
	Sid_eastman_eas
	sid_eastman_easi

	astman_easily_te

Ясно, что метки вида (0,0,...), которые кодируют единичные символы, не обеспечивают хорошее сжатие. Легко оценить их длину. Размер смещения равен , где - длина буфера поиска. На практике этот буфер имеет длину в несколько сотен байт, поэтому смещение имеет длину 10 - 12 бит. Поле «длина» имеет размер равный , где - длина упреждающего буфера (в следующем абзаце будет объяснено почему надо вычитать 1). Обычно упреждающий буфер имеет длину нескольких десятков байтов. Поэтому длина этого поля равна нескольким битам. Размер поля «символ», обычно, равен 8 бит, но в общем случае - , где - размер алфавита. Полный размер метки (0,0,...) одиночного символа равен бит, что много больше длины 8 «сырого» символа без нулевых элементов кода.

Следующий пример показывает, почему поле «длина» может быть длиннее размера упреждающего буфера:

alf_eastman_easily_grows_alf

Первый символ а в упреждающем буфере совпадает с 5-ым а буфера поиска. Может показаться, что оба крайних а подходят с длиной совпадения 3, поэтому кодер выберет самый левый символ и создаст метку (28,3,«а»). На самом деле кодер образует метку (3,4,«_»). Строка из четырех символов «alfa» из упреждающего буфера совпадает с тремя символами «alf» буфера поиска и первым символом «а» упреждающего буфера. Причина этого заключается в том, что декодер может обращаться с такой меткой очень естественно безо всяких модификаций. Он начинает с позиции 3 буфера поиска и копирует следующие 4 символа, один за другим, расширяя буфер вправо. Первые 3 символа копируются из старого содержимого буфера, а четвертый является копией первого из этих новых трех. Следующий пример еще более убедителен (хотя он немного надуман):

alf_eastman_easily_yells_A

Кодер создает метку (1,9,«А») для совпадения первых девяти копий символа «А» в упреждающем буфере, включая десятый символ А. Вот почему длина совпадения, в принципе, может быть равна размеру упреждающего буфера минус 1.

Декодер метода LZ77 гораздо проще кодера (то есть, метод LZ77 является асимметричным методом сжатия). Он должен соорудить такой же буфер поиска, как и кодер. Декодер вводит метку, находит совпадение в своем буфере, записывает совпадающие символы и символ из третьего поля в буфер. Этот метод или его модификация хорошо работает, если файл сжимается один раз (или несколько раз), но часто разжимается. Часто используемый архив старых сжатых файлов может служить хорошим примером использования этого алгоритма.

На первый взгляд в описанном методе сжатия не делается никаких предположений относительно входных данных. В частности, не обращается внимание на частоты появления отдельных символов. Однако, немного подумав, видно, что из-за природы скользящего окна метод LZ77 всегда сравнивает упреждающий буфер с недавним содержимым буфера поиска, но не с данными, поступившими очень давно (и которые уже покинули буфер поиска). Следовательно, неявно предполагается, что похожие участки входного файла повторяются близко друг от друга. Данные, удовлетворяющие этому свойству будут хорошо сжиматься.

Базисный метод LZ77 улучшался исследователями и программистами многими способами в течение 80-х и 90-х годов прошлого века. Один возможный путь это использование кодов переменной длины при кодировании полей смещения и длины в метке. Другой путь - увеличение размеров обоих буферов. Увеличение буфера поиска дает возможность искать больше совпадений, но ценой будет служить увеличение времени поиска. Очевидно, большой буфер поиска потребует более изощренной структуры данных для ускорения поиска (см. § 2.4.2). Третье улучшение относится к скользящему окну. Простейший подход заключается в перемещении всего текста влево после каждого совпадения. Более быстрый прием заключается в замене линейного окна на циклическую очередь, в которой скольжение окна делается переустановкой двух указателей (см. § 2.1.1). Еще одно улучшение состоит в добавлении одного бита (флага) в каждую метку, что исключает третье поле (см. § 2.2).