Метод скользящего окна применяется для. Повторная передача и скользящее окно. Что такое скользящее окно

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

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

Еще по теме Повторная передача и скользящее окно:

1. § 29 Передача и переход прав по обязательствам. – Римская конструкция права передачи. – Облегчение передачи новейшим законодательством. – Передаточная надпись. – Ограничения передачи. – Действие передачи. – Ответственность передатчика и права приобретателя. – Вступление в право кредитора или суброгация. – Русский закон передачи. – Передача заемных писем. – Переход требований к кредиторам.

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

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

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

Основная идея этого метода (его еще часто называют методом LZ1, см. ) состоит в использовании ранее прочитанной части входного файла в качестве словаря. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Таким образом, метод основан на скользящем окне. Окно разбивается на две части. Часть слева называется буфером поиска. Она будет служить текущим словарем, и в ней всегда содержатся символы, которые недавно поступили и были закодированы. Правая часть окна называется упреждающим буфером, содержащим текст, который будет сейчас закодирован. На практике буфер поиска состоит из нескольких тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Вертикальная черта | между символами t и е означает текущее разделение между двумя буферами. Итак, предположим, что текст «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. Эта метка записывается в выходной файл, а окно сдвигается вправо (или входной файл сдвигается влево) на четыре позиции: три позиции для совпадающей последовательности и одна позиция для следующего символа.

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

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

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

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

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

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

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

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