Учебно-методическии комплекс дисциплины «Компьютерные сети» для специальности 6М011100 — «Информатика» (стр. 31 )

Таким образом, принимающая сторона может не сохранять пакет п + 1. Кроме того, игнорирование пакетов, полученных с нарушением порядка следования, позволяет упростить буферизацию на принимающей стороне. Из сказанного следует, что передающая сторона оперирует тремя величинами: верхней и нижней границами окна, а также наименьшим свободным порядковым номером. Для принимающей стороны необходим лишь порядковый номер следующего по порядку пакета. Эта величина хранится в переменной expectedseqnum, присутствующей на схеме, показанной на рис. 3.20. Необходимо признать, что механизм удаления успешно принятых пакетов тоже «небезгрешен»: при повторной передаче существует вероятность новой потери пакета, что, в свою очередь, приводит к необходимости дополнительных повторных передач.

На рис. 7.15 показана схема функционирования GBN-протокола, в котором размер окна составляет 4 пакета. Осуществив передачу пакетов с порядковыми номерами от 0 до 3, передающая сторона должна получить подтверждение хотя бы для одного из них. Как только подтверждения будут получены (например, АСКО и АСК1), окно переместится «вперед», и передающая сторона сможет послать 2 новых пакета (pkt4 и pkt5). Когда принимающая сторона обнаруживает потерю пакета 2, пакеты 3, 4 и 5 считаются нарушившими порядок следования данных и игнорируются.

Рис. 7.15 Функционирование GBN-протокола

Отметим, что реализация GBN-протоколов в стеке протоколов, как правило, имеет структуру, схожую со структурой конечного автомата, представленного на рис. 7.13. Действия, выполняемые протоколом при наступлении различных событий, оформлены в виде процедур. В подобных событийно-управляемых программах выполнение процедур происходит либо при их вызове другими процедурами стека протоколов, либо при наступлении прерывания. На передающей стороне событиями, управляющими программой, являются вызов функции rdt_send() протоколом верхнего уровня, прерывание от таймера и вызов функции rdt_rcv() протоколом нижнего уровня при получении пакета.

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

4. Выборочное повторение

Как показано на рис. 7.10, GBN-протокол, в отличие от протоколов с ожиданием подтверждения, позволяет передающей стороне «заполнять конвейер» пакетами, повышая чрезвычайно низкую загрузку линии связи. Тем не менее возможны ситуации, в которых эффективность GBN-протокола также оказывается весьма невысокой. Например, если размер окна и произведение пропускной способности на задержку распространения велики, конвейер может содержать слишком много пакетов. Наличие искажения хотя бы в одном из пакетов приводит к необходимости повторной передачи значительных объемов уже однажды переданных (причем без ошибок) данных. Чем выше вероятность искажений при передаче, тем большая часть издержек на передачу данных оказывается бесполезной. Возвращаясь к примеру с диктовкой сообщений, можно представить рассматриваемую ситуацию следующим образом: если «размер окна» составляет 1000 слов, то любое искаженное слово приводит к необходимости повторения всех 1000 слов «окна». Понятно, что такое «общение» отнимет у собеседников слишком много времени.

Как ясно из названия, метод выборочного повторения (Selective Repeat, SR) направлен на снижение количества повторных передач путем отправки только тех пакетов, которые были зафиксированы принимающей стороной как потерянные или искаженные. Это требует введения отдельных квитанций для каждого успешно принятого пакета. Как и в GBN-протоколе, число пакетов, находящихся в конвейере, ограничивается размером окна N, однако передающая сторона может получать квитанции для некоторых пакетов окна. На рис. 7.16 представлена схема определения диапазона порядковых номеров, а представленная ниже последовательность действий иллюстрирует работу передающей стороны SR-протокола.

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

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

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

Рис. 7.16 Диапазон порядковых номеров с точки зрения передающей и принимающей сторон SR-протокола

Принимающая сторона выдает квитанцию каждому принятому правильному (не содержащему ошибок) пакету, независимо от того, нарушает он порядок следования или нет. Пакеты, нарушающие порядок следования, хранятся в буфере до тех пор, пока не будут получены предшествующие пакеты; после этого данные всех принятых пакетов доставляются верхнему уровню. Ниже перечислены действия, выполняемые принимающей стороной SR-протокола, а рис. 7.17 иллюстрирует реакцию принимающей стороны на ситуацию, когда при передаче происходит потеря пакета. Обратите внимание на то, что принимающая сторона помещает пакеты 3, 4 и 5 в буфер, где они хранятся до тех пор, пока не будет получен пакет 2; после этого содержимое пакетов 2, 3, 4 и 5 доставляется верхнему уровню.

Рис. 7.17 Функционирование SR-протокола

1. Успешно принят пакет с номером, лежащим в диапазоне [rcv_base, rcv_base + N - 1]. В этом случае принятый пакет принадлежит окну, и принимающая сторона генерирует подтверждение для этого пакета. Если прием пакета осуществляется впервые, он заносится в буфер. В случае совпадения порядкового номера пакета с базой окна (rcv_base на рис. 7.16) этот пакет вместе со всеми пакетами, хранящимися в буфере, образует последовательность с наименьшим номером rcv_base. Данные, извлеченные из последовательности, передаются верхнему уровню; затем происходит сдвиг окна передающей стороны на длину последовательности. Подобная ситуация изображена на рис. 7.17: при получении пакета 2 верхнему уровню передаются данные пакетов 2, 3, 4 и 5.

2. Принят пакет с номером, лежащим в диапазоне [rev_base - N, rcv_base - 1]. Несмотря на то что квитанция для этого пакета уже была послана передающей стороне ранее, в этом случае предусматривается повторное квитирование пакета.

3. Иначе пакет игнорируется.

Действие 2 представленной процедуры демонстрирует важную особенность SR-протокола: принимающая сторона повторно квитирует пакеты с порядковыми номерами, лежащими ниже текущего базового номера окна. Для чего нужно повторное квитирование? Обратимся к рис. 7.16. При указанных множествах порядковых номеров принимающей и передающей сторон отсутствие подтверждения для пакета send_base приведет к его повторной передаче, несмотря на его успешный прием (очевидный для нас, но не для передающей стороны). Если подтверждение не будет сгенерировано, окно передающей стороны не сможет переместиться вперед! Эта ситуация указывает на важное свойство SR-протоколов (и не только): принимающая и передающая стороны не всегда имеют одинаковое представление о том, какие данные переданы корректно, а какие — нет. В случае SR-протоколов различие состоит в несовпадении окон обменивающихся сторон.

Отсутствие синхронизации между окнами передающей и принимающей сторон имеет важные последствия, когда мы сталкиваемся с ограниченностью диапазона порядковых номеров. Представим себе, что у нас имеется 4 порядковых номера (0, 1, 2 и 3), при этом размер окна равен 3. Пусть пакеты с порядковыми номерами 0, 1 и 2 были успешно получены и квитированы принимающей стороной. В этом случае окно принимающей стороны должно переместиться на 3 пакета вперед, то есть охватить пакеты с номерами 3, 0 и 1. Далее рассмотрим две ситуации. Первая ситуация, представленная на рис. 7.18, а, заключается в потере квитанции для переданных пакетов, что приводит к необходимости их повторной передачи. Таким образом, следующий пакет, получаемый принимающей стороной, будет иметь порядковый номер 0 и являться копией пакета, переданного ранее.

Во второй ситуации, представленной на рис. 7.18, б, квитанция для трех переданных пакетов успешно доставляется передающей стороне. Передающая сторона сдвигает свое окно на 3 позиции и осуществляет передачу пакетов с порядковыми номерами 3, 0 и 1; при этом пакет с номером 3 теряется, а пакет 0 доставляется на принимающую сторону. Заметим, что в пакете с номером 0 содержатся новые, не переданные ранее данные.

Теперь рассмотрим ту же ситуацию с точки зрения принимающей стороны. Действия, выполняемые передающей стороной, скрыты от нее; принимающая сторона способна лишь следить за последовательностями получаемых пакетов и генерируемых квитанций. Подобная ограниченность приводит к тому, что обе описанные выше ситуации воспринимаются принимающей стороной как одинаковые. Принимающая сторона не может отличить исходную передачу первого пакета от его повторной передачи. Очевидно, что протокол, размер окна которого на единицу меньше диапазона порядковых номеров, не является работоспособным. Однако насколько малым должен быть размер окна? В одном из упражнений, приведенных в конце этой главы, вам предлагается самостоятельно доказать, что размер окна SR-протокола не должен превосходить половины диапазона порядковых номеров.