Коррекция размера окна по задержке. Алгоритм Bегас (Vegas)

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

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

Поскольку в i-м цикле регулирования в соединение отправляется блоков данных, то ожидаемая его производительность составляет

.

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

.

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

Ш1. Установить значения «порогов» и {нижняя и верхняя границы числа блоков данных в буферах соединения}

Ш2 Вычислить

Ш3 Вычислить

Ш3. Если То Иначе

Если То Иначе

Ш4. Конец.

Значения порогов и отражают объем буферной памяти соединения. Например, если установить и , то алгоритм Vegas будет поддерживать не менее 2 и не более 4 сегментов в буферах сетевого соединения, что с одной стороны обеспечивает достаточно высокую производительность, а с другой – не допускает возникновения перегрузки. Заметим также, что этот алгоритм при малых значениях порогов стабилизирует задержку передачи, что весьма важно для приложений с изохронным характером трафика. Вместе с тем, вычисление значений и с достаточной точностью требует наличие таймеров с высоким разрешением, что нередко ограничивает возможность применения этого алгоритма.

Заключение

· Адаптационные процедуры уровневых протоколов преобразуют подверженный ошибкам физический дискретный канал связи в надежную систему передачи данных.

· Разбиение информационного потока на блоки данных (циклы, кадры, пакеты и т.п.) является механизмом обеспечения неограниченности объемов информационного обмена и обязательным элементом процедуры обнаружения ошибок в принимаемых данных.

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

· Выявленные ошибки либо исправляются (самокорректирующиеся коды), либо ошибочные блоки данных уничтожаются и, при необходимости, передаются повторно. Последнее - более экономично в вычислительном отношении, но требует наличия обратного канала.

· Механизмы ARQ (автоматической повторной передачи) используют таймеры, нумерацию передаваемых блоков данных и кадры-подтверждения. Алгоритм ARQ с остановками и ожиданием, – простейший из алгоритмов повторной передачи, - может работать на полудуплексном канале связи, требует задания значения предельного времени ожидания подтверждения и удовлетворяется двоичным счетчиком передаваемых и принимаемых кадров. Этот алгоритм эффективен лишь на низкоскоростных линиях, где время полного оборота сравнимо с временем передачи кадра.

· Алгоритм ARQ с возвратом на N обеспечивает более высокую производительность; получатель подтверждает правильно полученные кадры отсылкой кадра «АСК» с указанием номера подтверждаемого кадра; кадр с номером L+W_s не может быть передан, пока не получено подтверждение приема кадра с номером L; в случае если отправитель к моменту истечения тайм-аута не получает подтверждения успешной доставки этого кадра, то он повторно передает все кадры начиная с L; кадры нумеруются по модулю m и размер окна передачи не должен превышать 2^m – 1.

· Алгоритм ARQ с выборочным повторением более эффективен в сравнении с алгоритмом GB_N ARQ; это достигается благодаря тому, что отправитель повторно передает только те кадры, подтверждения правильного приема которых не были получены своевременно; получатель подтверждает правильно полученные кадры отсылкой кадра- квитанции «АСК» с указанием номера подтверждаемого кадра, а кадр, принятый не по порядку, подтверждается квитанцией «NAK» с указанием номера ожидаемого кадра; получатель сохраняет в буферной памяти до W_r принятых кадров и доставляет их приложению только строго упорядочено; нумерация кадров производится по модулю m, но размер окна передачи W_s не должен превышать 2^m-1;

· Эффективность алгоритмов ARQ оценивается величиной, равной той части пропускной способности канала, которая используется для передачи информационного содержания кадров.

· Целью управления потоками является эффективное использование и справедливое распределение ресурсов сети.

· Алгоритм «скользящего окна» является основой процедур управления потоком. Регулирование величины окна передачи осуществляется на основе выполняемых протоколом оценок либо факта возникновения перегрузок (алгоритмы Tachoe, Reno, по факту потери сегментов), либо доступной пропускной способности соединения (алгоритм Vegas, на основе измерения RTT).

· Алгоритм Tachoe содержит фазу медленного старта, начинающуюся со значения W_s=1, и фазу предупреждения перегрузки; он также реализует быструю повторную передачу.

· Алгоритм Reno дополняет алгоритм Tachoe фазой быстрого восстановления величины окна передачи и ликвидирует фазу медленного старта.