Что такое скользящее окно? Что такое транспортный протокол

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

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

TCP использует технологию скользящего окна для указания числа сегментов, которое может принять приёмник, передающихся с номера подтверждения. В этом разделе рассматривается скользящее окно TCP.

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

На рисунке размер окна равен 3. Отправитель может передать три сегмента на приёмник. С этого момента отправитель ожидает подтверждение от приёмника. Как только приёмник подтверждает получение трёх сегментов данных, отправитель может передать три следующих сегмента. Однако, при уменьшении возможности приёма сегментов, приёмник уменьшит размер окна, так, что бы принимаемые данные не вызвали переполнение буфера и не произошло отбрасывание сегментов.

Каждое подтверждение, переданное приёмником, содержит заявленный размер окна, выражаемый числом байт, которое согласен принять приёмник (иначе — размер окна). Это позволяет окну расширяться или сужаться при необходимости для управления размером буфера и скоростью обработки данных приёмником.

Протокол TCP поддерживает особый параметр — размер окна перегрузки (Congestion Window Size — CWS), который обычно имеет такой же размер, как размер окна приёмника, но CWS уменьшается в 2 раза, когда начинают теряться сегменты. Потеря сегментов воспринимается как перегрузка сети. Протокол TCP активизирует сложный механизм отката и перезапускает алгоритмы, что бы далее не способствовать сетевой перегрузке.

ПРОЦЕСС ПРИМЕНЕНИЯ СКОЛЬЗЯЩЕГО ОКНА.

МАКСИМИЗАЦИЯ ПРОПУСКНОЙ СПОСОБНОСТИ.

Алгоритм обработки окном управляет скоростью передачи данных. Тем самым удается минимизировать отбрасывание данных, поскольку на передачу потерянных данных тратите» дополнительное время, и, следовательно, удаётся увеличить эффективность.

ГЛОБАЛЬНАЯ СИНХРОНИЗАЦИЯ.

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

Данный алгоритм (алгоритм LZ77 4Назван по именам авторов Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Опубликован в 1977 году. ) был одним из первых, использующих словарь . В качестве словаря используются N последних уже закодированных элементов последовательности. В процессе сжатия словарь-подпоследовательность перемещается ("скользит") по входящей последовательности. Цепочка элементов на выходе кодируется следующим образом: положение совпадающей части обрабатываемой цепочки элементов в словаре - смещение (относительно текущей позиции), длина, первый элемент, следующий за совпавшей частью цепочки. Длина цепочки совпадения ограничивается сверху числом n . Соответственно, задача состоит в нахождении наибольшей цепочки из словаря, совпадающей с обрабатываемой последовательностью. Если же совпадений нет, то записывается нулевое смещение, единичная длина и только первый элемент незакодированной последовательности - {0, 1, e} .

Описанная выше схема кодирования приводит к понятию скользящего окна (англ. sliding window), состоящего из двух частей:

1. подпоследовательность уже закодированных элементов длины N - словарь - буфер поиска (англ. search buffer);
2. подпоследовательность длины n из цепочки элементов, для которой будет произведена попытка поиска совпадения - буфер предварительного просмотра (англ. look-ahead buffer).

В терминах скользящего окна алгоритм сжатия описывается так: если e 1 , . . . , e i - уже закодированная подпоследовательность, то e i-N+1 , . . . , e i - суть словарь или буфер поиска, а e i+1 , . . . , e i+n - буфер предварительного просмотра. Аналогично, задача состоит в поиске наибольшей цепочки элементов из буфера предварительного просмотра, начиная с элемента e i+1 , совпадающей с цепочкой из буфера поиска - эта цепочка может начинаться с любого элемента и заканчиваться любым элементом , т.е. выходить за пределы буфера поиска, вторгаясь в буфер предварительного просмотра. Естественно, что выходить за пределы скользящего окна нельзя. Пусть в скользящем окне найдена максимальная по длине совпавшая цепочка элементов e i-p , . . . , e i+q , тогда она будет закодирована следующим образом: {p+1, q+p+1, e i+p+q+2 } - смещение относительно начала буфера предварительного просмотра (e i+1) , длина совпавшей цепочки, элемент, следующий за совпавшей цепочкой из буфера предварительного просмотра. Если в результате поиска найдено два совпадения с одинаковой длиной, то выбирается ближайшее к началу буфера предварительного просмотра. После этого скользящее окно смещается на p + q + 2 элементов вперед, и процедура поиска повторяется.

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

Приведем пример сжатия данным алгоритмом. Сожмем строку "TOBEORNOTTOBE" с параметрами N = 10 и n = 3 :

Если выделить для хранения смещения 4 бита, длины - 2 бита, а элементов - 8 бит, то длина закодированной последовательности (без учета обозначения конца последовательности) составит 4 x 8 + 2 x 8 + 8 x 8 = 112 бит, а исходной - 102 бита. В данном случае мы не сжали последовательность, а, наоборот, увеличили избыточность представления. Это связано с тем, что длина последовательности слишком мала для такого алгоритма. Но, например, рисунок кодового дерева Хаффмена на рис. 13.1 , занимающий 420 килобайт дискового пространства, после сжатия имеет размер около 310 килобайт.

Ниже приведен псевдокод алгоритма сжатия.

// M - фиксированная граница // считываем символы последовательно из входного потока // in - вход - сжатая последовательность // n - максимальная длина цепочки // pos - положение в словаре, len - длина цепочки // nelem - элемент за цепочкой, str - найденная цепочка // in - вход, out - выход // SlideWindow - буфер поиска while(!in.EOF()) //пока есть данные { // ищем максимальное совпадение и его параметры SlideWindow.FindBestMatch(in, n, pos, len, nelem); // пишем выход: смещение, длина, элемент out.Write(pos); out.Write(len); out.Write(nelem); // сдвинем скользящее окно на len + 1 элементов SlideWindow.Move(in, len + 1); } Листинг 13.2. Алгоритм сжатия методом LZ77

Декодирование сжатой последовательности является прямой расшифровкой записанных кодов: каждой записи сопоставляется цепочка из словаря и явно записанного элемента, после чего производится сдвиг словаря. Очевидно, что словарь воссоздается по мере работы алгоритма декодирования.

Видно, что процесс декодирования значительно проще с вычислительной точки зрения.

// n - максимальная длина цепочки // pos - положение в словаре, len - длина цепочки // nelem - элемент за цепочкой, str - найденная цепочка // in - вход, out - выход // Dict - словарь while(!in.EOF()) //пока есть данные { in.Read(pos); in.Read(len); in.Read(nelem); if(pos == 0) { //новый отдельный символ //удаляем из словаря первый (дальний) один элемент Dict.Remove(1); //добавляем в словарь элемент Dict.Add(nelem); out.Write(nelem); } else { //скопируем соответствующую строку из словаря str = Dict.Get(pos, len); //удалим из словаря len + 1 элементов Dict.Remove(len + 1); //Добавляем в словарь цепочку Dict.Add(str + nelem); out.Write(str + nelem); } } Листинг 13.3. Алгоритм

Данный алгоритм является родоначальником целого семейства алгоритмов, и сам по себе в изначальном виде практически не используется. К его достоинствам можно отнести приличную степень сжатия на достаточно больших последовательностях, быструю распаковку, а также отсутствие патента 5документ, обеспечивающий исключительное право эксплуатировать изобретение в течение известного времени (обычно 15-20 лет) на алгоритм. К недостаткам относят медленную скорость сжатия, а также меньшую, чем у альтернативных алгоритмов, степень сжатия (модификации алгоритма борются с этим недостатком). Сочетание алгоритмов Хаффмена (Huffman) ( "Алгоритмы сжатия изображений без потерь") и LZ77 называют методом DEFLATE 6Так называется сжатие, а разжатие называется INFLATE (англ. DEFLATE - сдувать, INFLATE - надувать). . Метод DEFLATE используется в графическом формате PNG, а также в универсальном формате сжатия данных ZIP.

Алгоритм адаптивного тайм-аута KARN

Тайм-ауты

Номера байтов

Дубликаты

Проблемы, решаемые процедурой handshaking

Если станция передает 20 байт, то сервер увеличит ACK на 20 (станет 751 байт) и т.д.

Подтверждения генерируется для всех байт, которые приходят в нужной последовательности. Если будут переданы дубликаты, это не испортит картину. Можно 3 раза подтвердить, что пришло 731 байт (это пример). Все подтверждения кумулятивные. Потерянные подтверждения не создают проблем.

Дубликаты в TCP могут возникать:

1. Из-за потери оригинального сегмента
2. Из-за потери подтверждения
3. Из-за превышения времени повторной передачи
4. Из-за задержки сегмента
5. Из-за перебора всех возможных номеров байтов

Последовательные номера до 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).