ARQ на n шагов назад (Go Back N)

Широко используемый алгоритм. Используется в стандартных протоколах УЛПД - HDLC, SDLC, ADCCP, LAPB.

Пакеты нумеруются и посылаются из А в В без ожидания запроса НЗ, тем самым подтверждаются все пакеты до НЗ.

n - число шагов назад, означает, что узлу А не разрешается посылать пакет i+n, пока пакет i не получит подтверждение (т.е. НЗ = i+1).

Иначе этот протокол называют протоколом со скользящим окном.

Пусть - последний НЗ, принятый в т.А. Тогда из т.А могут посылаться пакеты с номерами в "окне" от до + n - 1.

Затем при получении нового НЗ возрастает и окно скользит вверх.

Если в т.В принят пакет с ошибкой, то пакеты с большими номерами не принимаются, пока А не повторит передачу этого пакета.

Пример: Протокол на 4 шага назад

 

 

1. из-за этой ошибки пакеты после четвертого повторяются начиная с 1-го

2. эта ошибка не вызвала сложностей, подтверждение пришло до того, как пришлось бы идти назад.

3. когда пакет 5 передается повторно приходит НЗ=7. Возможно разумно сразу за 5-м передавать 7-й, а не 6-й

При выборе n большим можно исключить некоторые повторные передачи.

Алгоритм остается корректным, если порядковый номер ПН и НЗ номер запроса передаются по модулю m (m>n), поскольку величина |Z- Y_пр| самое большее равна n.

(Z - номер пакета, помещаемого в кадр;
Y_пр- номер ожидаемого пакета)

Повторные передачи в этом методе появляются по следующим причинам:

1. ошибки при передаче в прямом направлении;

2. ошибки при передаче в направлении обратной связи;

3. длина кадров в направлении обратной связи больше, чем в прямом направлении. Выход - увеличение n.

(в стандартных протоколах используется m=8, m=128)

Пример: ARQ на 7 шагов назад.

Но если увеличить n, то эффективность возрастает по причинам 2 и 3, но падает по причине 1. Если приемный модуль будет посылать короткие управляющие кадры при приеме кадра с ошибкой, то возврат будет произведен быстрее (или можно рассчитать, в каком кадре должно быть подтверждение) Разновидности: ARQ с возвращением и "заиканием" на последнем сообщении.

ARQ с выборочным повтором (с адресным переспросом)

Для т.В считаются принятыми пакеты, идущие в произвольном порядке. Повторная передача запрашивается из А только для тех пакетов, которые принимаются неправильно.

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