Компьютерные сети. 6-е изд.

3.3. Элементарные протоколы передачи данных на канальном уровне

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

3.3.1. Исходные упрощающие допущения

Независимые процессы. Для начала предположим, что физический, канальный и сетевой уровни являются независимыми процессами, которые взаимодействуют между собой путем передачи сообщений. Типичная реализация показана на илл. 3.10. Процесс физического уровня и часть процесса канального уровня выполняются на специальном оборудовании: сетевой интерфейсной карте (Network Interface Card, NIC). Остальная часть процесса канального уровня и процесс сетевого уровня осуществляются на центральном процессоре (ЦП), являясь частью операционной системы. При этом программное обеспечение процесса канального уровня зачастую принимает вид драйвера устройства. Также возможны другие варианты реализации, например, три процесса, выполняющиеся на сетевом ускорителе или на ЦП с программно определяемой частотой. На самом деле оптимальная реализация меняется с течением времени

Илл. 3.10. Реализация физического, канального и сетевого уровней

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

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

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

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

3.3.2. Базовая схема передачи и приема данных

Получив пакет от сетевого уровня отправителя, канальный уровень формирует из него фрейм, добавляя заголовок и трейлер (см. илл. 3.1). Таким образом, фрейм состоит из встроенного пакета, некоторой служебной информации (в заголовке) и контрольной суммы (в трейлере). Затем фрейм передается канальному уровню целевого устройства. Мы будем исходить из наличия подходящих библиотечных процедур, например to_physical_layer для отправки фрейма и from_physical_layer для его получения. Они вычисляют и добавляют или проверяют контрольную сумму (обычно это делается аппаратно), так что при разработке протоколов, представленных в этом разделе, можно об этом не беспокоиться. К примеру, они могут использовать рассмотренный ранее алгоритм CRC (циклический избыточный код).

Изначально получатель ничего не должен делать, он просто ожидает. В протоколах, рассматриваемых в этой главе, ожидание событий канальным уровнем происходит путем вызова процедуры wait_for_event(&event). Эта процедура возвращает управление, только когда что-то происходит (например, получение фрейма). При этом переменная event сообщает, что именно случилось. Наборы возможных событий отличаются в разных протоколах, поэтому будут описываться для каждого протокола отдельно. Следует отметить, что на практике канальный уровень не находится в холостом цикле ожидания событий (согласно нашему допущению), а получает прерывание, когда это событие происходит. При этом он приостанавливает текущие процессы и обрабатывает полученный фрейм. Но для простоты мы проигнорируем эти детали и будем исходить из того, что канальный уровень все свое время посвящает работе с одним каналом.

Когда принимающая сторона получает фрейм, контрольная сумма вычисляется заново. Если она неверна (то есть при передаче возникли ошибки), канальный уровень получает соответствующую информацию (event=cksum_err). Если фрейм приходит без ошибок, канальному уровню об этом также сообщается (event=frame_arrival), после чего он может получить этот фрейм у физического уровня с помощью процедуры from_physical_layer. Получив неповрежденный фрейм, канальный уровень проверяет управляющую информацию, находящуюся в заголовке, и если все в порядке, часть фрейма передается сетевому уровню; заголовок фрейма не передается ни при каких обстоятельствах.

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

На илл. 3.11 показаны некоторые объявления (на языке C), общие для многих протоколов, обсуждаемых ниже. Выделяются пять типов данных: boolean, seq_nr, packet, frame_kind и frame. Тип boolean представляет собой перечисляемый тип, переменные которого могут принимать значение true или false. Тип seq_nr является целым без знака, используемым для нумерации фреймов, благодаря которой их можно различать. Нумерация идет от 0 до числа MAX_SEQ включительно, определяемого для конкретного протокола. Тип packet — это единица информации, используемая при обмене данными между сетевым и канальным уровнями одного компьютера или двумя сетевыми уровнями. В нашей модели пакет всегда состоит из MAX_PKT байт, хотя на практике он обычно имеет переменную длину.

Тип frame содержит четыре поля: kind, seq, ack и info; первые три содержат управляющую информацию, а последнее может включать данные, которые необходимо передать. Три управляющих поля вместе называются заголовком фрейма (frame header).

Поле kind сообщает о наличии данных внутри фрейма, так как некоторые протоколы отличают фреймы, содержащие только управляющую информацию, от фреймов, в которых также есть данные. Поле seq используется для хранения последовательного номера фрейма, ack — для подтверждения. Подробнее их применение будет описано ниже.

Поле данных фрейма info содержит один пакет. В управляющем фрейме это поле не задействуется. На практике используется поле info переменной длины, в управляющих фреймах оно полностью отсутствует.

Важно понимать взаимоотношения между пакетом и фреймом (см. илл. 3.1). Сетевой уровень создает пакет, принимая сообщение от транспортного уровня и добавляя к нему свой заголовок. Пакет передается канальному уровню, который включает его в поле info исходящего фрейма. Когда целевое устройство получает фрейм, канальный уровень извлекает пакет из фрейма и передает его сетевому. Таким образом, сетевой уровень может действовать так, будто устройства обмениваются пакетами напрямую.

#define MAX_PKT 1024 /* определяет размер пакета в байтах

typedef enum {false, true} boolean; /* тип boolean */

typedef unsigned int seq_nr; /* порядковые номера фреймов или подтверждений */

typedef struct {unsigned char data[MAX_PKT];} packet; /* определение пакета */

typedef enum {data, ack, nak} frame_kind; /* определение типа фрейма */

typedef struct { /* фреймы, транспортируемые на данном уровне */

frame_kind kind; /* тип фрейма */

seq_nr seq; /* порядковый номер */

seq_nr ack; /* номер подтверждения */

packet info; /* пакет сетевого уровня */

} frame;

/* Ожидать события и вернуть тип события в переменной event. */

void wait_for_event(event_type *event);

/* Получить пакет у сетевого уровня для передачи по каналу. */

void from_network_layer(packet *p);

/* Передать информацию из полученного пакета сетевому уровню. */

void to_network_layer(packet *p);

/* Получить пришедший пакет у физического уровня и скопировать его в r. */

void from_physical_layer(frame *r);

/* Передать фрейм физическому уровню для отправки. */

void to_physical_layer(frame *s);

/* Запустить таймер и разрешить событие timeout. */

void start_timer(seq_nr k);

/* Остановить таймер и запретить событие timeout. */

void stop_timer(seq_nr k);

/* Запустить вспомогательный таймер и разрешить событие ack_timeout. */

void start_ack_timer(void);

/* Остановить вспомогательный таймер и запретить событие ack_timeout. */

void stop_ack_timer(void);

/* Разрешить сетевому уровню инициировать событие network_layer_ready. */

void enable_network_layer(void);

/* Запретить сетевому уровню инициировать событие network_layer_ready. */

void disable_network_layer(void);

/* Макрос inc развертывается прямо в строке: циклически увеличить переменную k. */

#define inc(k) if (k < MAX_SEQ) k = k + 1; else k = 0

Илл. 3.11. Общие определения для последующих протоколов. Определения располагаются в файле protocol.h

На илл. 3.11 также перечислен ряд процедур. Это библиотечные процедуры, детали которых зависят от конкретной реализации; их внутреннее устройство мы рассматривать не будем. Как уже упоминалось ранее, процедура wait_for_event представляет собой холостой цикл ожидания какого-либо события. Процедура to_network_layer используется канальным уровнем для отправки пакетов сетевому, from_network_layer — для получения пакетов от него. Обратите внимание: процедуры from_physical_layer и to_physical_layer служат для обмена фреймами между канальным и физическим уровнями, тогда как процедуры to_network_layer и from_network_layer применяются для передачи пакетов между канальным и сетевым уровнями. Другими словами, процедуры to_network_layer и from_network_layer относятся к интерфейсу между уровнями 2 и 3, а процедуры from_physical_layer и to_physical_layer — к интерфейсу между уровнями 1 и 2.

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

В приведенных здесь протоколах этот сигнал реализован в виде значения event=timeout, возвращаемого процедурой wait_for_event. Для запуска и остановки таймера используются процедуры start_timer и stop_timer соответственно. Событие timeout может произойти, только если был запущен таймер, но еще не была вызвана процедура stop_timer. Процедуру start_timer разрешается запускать во время работающего таймера. Такой вызов просто перезапускает таймер, и отсчет начинается заново (до нового перезапуска или выключения).

Процедуры start_ack_timer и stop_ack_timer запускают и останавливают вспомогательные таймеры, используемые для создания подтверждений в некоторых ситуациях.

Процедуры enable_network_layer и disable_network_layer применяются в более сложных протоколах, где уже не предполагается, что у сетевого уровня всегда есть пакеты для отправки. Когда канальный уровень разрешает работу сетевого, последний может посылать сигнал прерывания, когда ему нужно передать пакет. Такое событие обозначается как event = network_layer_ready. Когда сетевой уровень отключен, он не может инициировать такие события. Канальный уровень тщательно следит за включением и выключением сетевого и не допускает ситуации, когда тот заваливает его пакетами, для которых нет места в буфере.

Последовательные номера фреймов всегда находятся в пределах от 0 до MAX_SEQ включительно. Число MAX_SEQ отличается в разных протоколах. Для увеличения последовательного номера фреймов на 1 циклически (то есть с обнулением при достижении числа MAX_SEQ) используется макрос inc. Он определен в виде макроса, поскольку используется прямо в строке в тех местах программы, где быстродействие является критичным. Как мы увидим далее, производительность сети часто ограничена скоростью выполнения протоколов. Определение простых операций в виде макросов (а не процедур) не снижает удобочитаемости программы, увеличивая при этом ее быстродействие.

Объявления на илл. 3.11 входят во все последующие протоколы. В целях экономии места и для наглядности они были извлечены и собраны вместе, но, по сути, они должны быть объединены с протоколами. В языке C такое объединение производится путем размещения определений в специальном файле заголовка (в данном случае protocol.h) и включения их в файлы протокола с помощью #include — директивы препроцессора C.

3.3.3. Симплексные протоколы канального уровня

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

Протокол «Утопия»: без управления потоком и без исправления ошибок

В качестве первого примера мы рассмотрим самый простой протокол. Данные передаются только в одном направлении, а опасений, что где-то может произойти ошибка, даже не возникает. Сетевые уровни передающего и целевого устройств находятся в состоянии постоянной готовности. Время обработки минимально, размер буфера неограничен. А главное, линия связи между канальными уровнями никогда не теряет и не искажает фреймы. Этот совершенно нереальный протокол под названием «Утопия» показан на илл. 3.12. Он всего лишь демонстрирует базовую структуру, необходимую для построения настоящего протокола.

Протокол состоит из двух процедур, sender1 (отправитель) и receiver1 (получатель). Процедура sender1 работает на канальном уровне отправляющего устройства, а процедура receiver1 — на канальном уровне целевого. Ни последовательные номера, ни подтверждения не используются, поэтому MAX_SEQ не требуется. Единственным возможным событием является frame_arrival (то есть получение неповрежденного фрейма).

Процедура sender1 представляет собой бесконечный цикл while, отправляющий данные на линию с максимально возможной скоростью. Тело цикла состоит из трех действий: получение пакета от сетевого уровня (всегда исправно работающего), формирование исходящего пакета с помощью переменной s и передача пакета адресату. «Утопия» использует только поле info, поскольку другие поля фрейма относятся к обработке ошибок и управлению потоком, а они в данном протоколе не применяются.

Процедура receiver1 так же проста. Вначале она ожидает, пока что-нибудь произойдет (как уже упоминалось, единственным событием в данном протоколе может быть получение неповрежденного фрейма). Когда фрейм приходит, процедура wait_for_event возвращает управление, при этом переменной event присваивается значение frame_arrival (которое все равно игнорируется). Вызов процедуры from_physical_layer удаляет вновь прибывший фрейм из аппаратного буфера и помещает его в переменную r. Наконец, порция данных передается сетевому уровню, а канальный уровень переходит в режим ожидания следующего фрейма.

/* Протокол 1 («Утопия») обеспечивает только одностороннюю передачу данных — от отправителя к получателю. Предполагается, что в канале связи нет ошибок и получатель способен мгновенно обрабатывать входящие данные. Соответственно, отправитель в цикле передает данные на линию с максимально доступной для него скоростью.

typedef enum {frame_arrival} event_type;

#include “protocol.h”

void sender1(void)

{

frame s; /* буфер для исходящего фрейма */

packet buffer; /* буфер для исходящего пакета */

while (true) {

from_network_layer(&buffer); /* получить у сетевого уровня пакет для передачи */

s.info = buffer; /* скопировать его во фрейм s для передачи */

to_physical_layer(&s); /* послать фрейм по каналу */

} /* Мы дни за днями шепчем: «Завтра, завтра». Так тихими шагами жизнь ползет К последней недописанной странице.

— Макбет, V, v */

}

void receiver1(void)

{

frame r;

event_type event; /* заполняется процедурой ожидания событий, но не используется здесь */

while (true) {

wait_for_event(&event); /* единственная возможность — доставка фрейма (событие frame_arrival) */

from_physical_layer(&r); /* получить прибывший фрейм */

to_network_layer(&r.info); /* передать данные сетевому уровню */

}

}

Илл. 3.12. Неограниченный симплексный протокол «Утопия»

Протокол «Утопия» абсолютно нереалистичен, так как он не способен ни управлять потоком данных, ни исправлять ошибки. Он напоминает службу без подтверждения и без установки соединения, которая надеется, что все эти проблемы решаются на более высоких уровнях. Однако даже такая служба обладает некоторыми способностями распознавать ошибки.

Добавляем управление потоком: протокол с остановкой и ожиданием

Усложним задачу: предположим, отправитель посылает данные слишком быстро и получатель не успевает их обработать. В реальности такая ситуация может возникнуть в любой момент, поэтому крайне важно научиться ее предотвращать. Допущение об отсутствии ошибок в канале связи сохраняется. Линия остается симплексной.

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

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

Протоколы, в которых отправитель посылает один фрейм, после чего ожидает подтверждения, называются протоколами с остановкой и ожиданием (stop-and-wait). На илл. 3.13 приведен пример такого симплексного протокола.

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

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

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

Добавляем исправление ошибок: порядковые номера и протокол ARQ

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

/* Протокол 2 (с ожиданием) также обеспечивает только одностороннюю передачу данных, от отправителя к получателю. Снова предполагается, что в канале связи нет ошибок. Однако на этот раз емкость буфера получателя ограниченна и, кроме того, ограниченна скорость обработки данных получателем. Поэтому протокол должен не допускать отправления данных быстрее, чем получатель способен их обработать. */

typedef enum {frame_arrival} event_type;

#include “protocol.h”

void sender2(void)

{

frame s; /* буфер для исходящего фрейма */

packet buffer; /* буфер для исходящего пакета */

event_type event; /* frame_arrival является единственным возможным событием */

while (true) {

from_network_layer(&buffer); /* получить у сетевого уровня пакет для передачи */

s.info = buffer; /* скопировать его во фрейм s для передачи */

to_physical_layer(&s); /* отправка фрейма */

wait_for_event(&event); /* не продолжать, пока на это не будет получено разрешения */

}

}

void receiver2(void)

{

frame r, s; /* буферы для фреймов */

event_type event; /* frame_arrival является единственным возможным событием */

while (true) {

wait_for_event(&event); /* единственная возможность — прибытие фрейма (событие frame_arrival) */

from_physical_layer(&r); /* получить входящий фрейм */

to_network_layer(&r.info); /* передать данные сетевому уровню */

to_physical_layer(&s); /* передать пустой фрейм, чтобы «разбудить» отправителя */

}

}

Илл. 3.13. Симплексный протокол с ожиданием и остановкой

На первый взгляд может показаться, что можно улучшить протокол 2, добавив таймер. Получатель будет возвращать подтверждение только в случае получения правильных данных. Неверные пакеты будут просто игнорироваться. Через некоторое время у отправителя истечет интервал времени и он отправит фрейм еще раз. Этот процесс будет повторяться до тех пор, пока фрейм наконец не прибудет в целости.

В приведенной выше схеме имеется один критический недостаток. Прежде чем читать дальше, попытайтесь понять, что же неверно в данном варианте протокола.

Чтобы разобраться, что может пойти не так, вспомните, что цель канального уровня заключается в предоставлении безошибочной прозрачной связи между двумя процессами сетевого уровня. Сетевой уровень устройства A передает серию пакетов своему канальному уровню, который должен обеспечить доставку идентичной серии пакетов сетевому уровню устройства B его канальным уровнем. В частности, сетевой уровень B не может распознать потерю или дублирование пакета, поэтому канальный уровень должен гарантировать, что повтора не произойдет ни при каких обстоятельствах.

Рассмотрим следующий сценарий.

1. Сетевой уровень устройства A передает пакет 1 своему канальному уровню. Пакет доставляется в целости на устройство B и передается его сетевому уровню. B посылает фрейм подтверждения обратно на A.

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

3. У канального уровня устройства A внезапно истекает отведенный интервал времени. Не получив подтверждения, оно предполагает, что отправленный им фрейм с данными был поврежден или потерян, и посылает его еще раз.

4. Дубликат фрейма в целости прибывает на канальный уровень B и передается на сетевой уровень. В итоге часть файла, переданного с A на B, дублируется. Копия файла на устройстве B будет неверной, и ошибка не будет обнаружена, другими словами, протокол даст сбой.

Разумеется, необходим некий механизм, с помощью которого получатель смог бы различать новые фреймы и переданные повторно. Наиболее очевидное решение — нумерация фреймов. Отправитель указывает порядковый номер фрейма в его заголовке. Благодаря этому принимающее устройство отличает новый фрейм от дубликата, который необходимо проигнорировать.

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

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

На стороне отправителя событием, запускающим передачу фрейма m + 1, является получение подтверждения доставки фрейма m. Но это означает, что фрейм m – 1 уже передан и подтверждение его доставки отправлено и получено. В противном случае протокол не стал бы посылать новый фрейм. Следовательно, неопределенность может возникнуть только между двумя соседними фреймами.

Таким образом, для нумерации фрейма достаточно всего одного бита информации (со значением 0 или 1). В каждый момент времени получатель ожидает прибытия фрейма с определенным порядковым номером. Фрейм с верным номером принимается, передается сетевому уровню, затем отправляется подтверждение его получения. Номер следующего ожидаемого фрейма увеличивается по модулю 2 (то есть 0 становится 1, а 1 — 0). Фрейм с неверным номером отбрасывается как дубликат. Однако последнее подтверждение повторяется, чтобы сообщить отправителю, что фрейм получен полностью.

Пример такого протокола представлен на илл. 3.14. Протокол, в котором отправитель ожидает положительного подтверждения, прежде чем перейти к пере-

/* Протокол 3 (PAR) обеспечивает симплексную передачу данных по ненадежному каналу.

#define MAX_SEQ 1 /* в протоколе 3 должно быть равно 1 */

typedef enum {frame_arrival, cksum_err, timeout} event_type;

#include "protocol.h"

void sender3(void)

{

seq_nr next_frame_to_send; /* порядковый номер следующего исходящего фрейма */

frame s; /* временная переменная */

packet buffer; /* буфер для исходящего пакета */

event_type event;

next_frame_to_send = 0; /* инициализация исходящих последовательных номеров */

from_network_layer(&buffer); /* получить первый пакет у сетевого уровня */

while (true) {

s.info = buffer; /* сформировать фрейм для передачи */

s.seq = next_frame_to_send; /* вставить порядковый номер во фрейм */

to_physical_layer(&s); /* послать фрейм по каналу */

start_timer(s.seq); /* запустить таймер ожидания подтверждения */

wait_for_event(&event); /* ждать событие frame_arrival, cksum_err или timeout */

if (event == frame_arrival) {

from_physical_layer(&s); /* получить подтверждение */

if (s.ack == next_frame_to_send) {

stop_timer(s.ack); /* остановить таймер

from_network_layer(&buffer); /* получить следующий исходящий пакет */

inc(next_frame_to_send); /* инвертировать значение переменной next_frame_to_send */

}

}

}

}

void receiver3(void)

{

seq_nr frame_expected;

frame r, s;

event_type event;

frame_expected = 0;

while (true) {

wait_for_event(&event); /* ожидание возможных событий: frame_arrival, cksum_err */

if (event == frame_arrival) { /* пришел неповрежденный фрейм */

from_physical_layer(&r); /* получить пришедший фрейм */

if (r.seq == frame_expected) { /* именно этот фрейм и ожидался */

to_network_layer(&r.info); /* передать данные сетевому уровню */

inc(frame_expected); /* в следующий раз ожидать фрейм с другим порядковым номером */

}

s.ack = 1 – frame_expected; /* номер фрейма, для которого посылается подтверждение */

to_physical_layer(&s); /* отправить подтверждение */

}

}

}

Илл. 3.14. Протокол с положительным подтверждением и повторной передачей

сылке следующего фрейма, часто называется PAR (Positive Acknowledgement with Retransmission — положительное подтверждение с повторной передачей) или ARQ (Automatic Repeat reQuest — автоматический запрос повторной передачи). Подобно протоколу 2, он передает данные только в одном направлении.

Протокол 3 отличается от своих предшественников тем, что и отправитель, и получатель содержат переменную, значение которой хранится, пока канальный уровень находится в режиме ожидания. Отправитель запоминает номер следующего фрейма в переменной next_frame_to_send, а получатель записывает номер следующего ожидаемого фрейма в переменной frame_expected. Каждый протокол имеет короткую фазу инициализации перед началом бесконечного цикла.

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

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

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