Выборочное повторение
Как показано на рис. 3.16, GBN-протокол, в отличие от протоколов с ожиданием подтверждения, позволяет передающей стороне «заполнять конвейер» пакетами, повышая чрезвычайно низкую загрузку линии связи. Тем не менее возможны ситуации, в которых эффективность GBN-протокола также оказывается весьма невысокой. Например, если размер окна и произведение пропускной способности на задержку распространения велики, конвейер может содержать слишком много пакетов. Наличие искажения хотя бы в одном из пакетов приводит к необходимости повторной передачи значительных объемов уже однажды переданных (причем без ошибок) данных. Чем выше вероятность искажений при передаче, тем большая часть издержек на передачу данных оказывается бесполезной. Возвращаясь к примеру с диктовкой сообщений, можно представить рассматриваемую ситуацию следующим образом: если «размер окна» составляет 1000 слов, то любое искаженное слово приводит к необходимости повторения всех 1000 слов «окна». Понятно, что такое «общение» отнимет у собеседников слишком много времени.
Как ясно из названия, метод выборочного повторения (Selective Repeat, SR) направлен на снижение количества повторных передач путем отправки только тех пакетов, которые были зафиксированы принимающей стороной как потерянные или искаженные. Это требует введения отдельных квитанций для каждого успешно принятого пакета. Как и в GBN-протоколе, число пакетов, находящихся в конвейере, ограничивается размером окна N, однако передающая сторона может получать квитанции для некоторых пакетов окна. На рис. 3.22 представлена схема определения диапазона порядковых номеров, а представленная ниже последовательность действий иллюстрирует работу передающей стороны SR-протокола.
1. Получены данные от верхнего уровня. Передающая сторона анализирует значение первого свободного порядкового номера. Если он принадлежит окну, то формируется пакет, содержащий переданные данные, и отсылается принимающей стороне. В противном случае передача данных откладывается, при этом данные либо помещаются в буфер, либо возвращаются верхнему уровню, как и в GBN-протоколах.
2. Истек интервал ожидания. Для обнаружения потерь пакетов снова приходится прибегать к использованию таймера. Каждый пакет должен быть снабжен собственным логическим таймером, поскольку необходимо, чтобы в интервале ожидания передавался только один пакет. Для организации множества логических таймеров достаточно иметь единственный аппаратный таймер.
3. Получено подтверждение. Передающая сторона помечает соответствующий пакет как принятый (при условии, что он принадлежит окну). Если оказывается, что порядковый номер пакета совпадает со значением send_base, база окна сдвигается вперед к неподтвержденному пакету с наименьшим порядковым номером. Если после сдвига окна обнаруживаются пакеты, попавшие внутрь окна и еще не переданные, осуществляется их передача.
Принимающая сторона выдает квитанцию каждому принятому правильному (не содержащему ошибок) пакету, независимо от того, нарушает он порядок следования или нет. Пакеты, нарушающие порядок следования, хранятся в буфере до тех пор, пока не будут получены предшествующие пакеты; после этого данные всех принятых пакетов доставляются верхнему уровню. Ниже перечислены действия, выполняемые принимающей стороной SR-протокола, а рис. 3.23 иллюстрирует реакцию принимающей стороны на ситуацию, когда при передаче происходит потеря пакета. Обратите внимание на то, что принимающая сторона помещает пакеты 3, 4 и 5 в буфер, где они хранятся до тех пор, пока не будет получен пакет 2; после этого содержимое пакетов 2, 3, 4 и 5 доставляется верхнему уровню.
1. Успешно принят пакет с номером, лежащим в диапазоне [rcv_base,rcv_base + N — 1]. В этом случае принятый пакет принадлежит окну, и принимающая сторона генерирует подтверждение для этого пакета. Если прием пакета осуществляется впервые, он заносится в буфер. В случае совпадения порядкового номера пакета с базой окна (rcv_base на рис. 3.22) этот пакет вместе со всеми пакетами, хранящимися в буфере, образует последовательность с наименьшим номером rcv_base. Данные, извлеченные из последовательности, передаются верхнему уровню; затем происходит сдвиг окна передающей стороны на длину последовательности. Подобная ситуация изображена на рис. 3.23: при получении пакета 2 верхнему уровню передаются данные пакетов 2, 3, 4 и 5.
2. Принят пакет с номером, лежащим в диапазоне [rev_base — N,rcv_base — 1]. Несмотря на то что квитанция для этого пакета уже была послана передающей стороне ранее, в этом случае предусматривается повторное квитирование пакета.
3. Иначе пакет игнорируется.
Действие 2 представленной процедуры демонстрирует важную особенность SR-протокола: принимающая сторона повторно квитирует пакеты с порядковыми номерами, лежащими ниже текущего базового номера окна. Для чего нужно повторное квитирование? Обратимся к рис. 3.22. При указанных множествах порядковых номеров принимающей и передающей сторон отсутствие подтверждения для пакета send_base приведет к его повторной передаче, несмотря на его успешный прием (очевидный для нас, но не для передающей стороны). Если подтверждение не будет сгенерировано, окно передающей стороны не сможет переместиться вперед! Эта ситуация указывает на важное свойство SR-протоколов (и не только): принимающая и передающая стороны не всегда имеют одинаковое представление о том, какие данные переданы корректно, а какие — нет. В случае SR-протоколов различие состоит в несовпадении окон обменивающихся сторон.
Отсутствие синхронизации между окнами передающей и принимающей сторон имеет важные последствия, когда мы сталкиваемся с ограниченностью диапазона порядковых номеров. Представим себе, что у нас имеется 4 порядковых номера (0, 1, 2 и 3), при этом размер окна равен 3. Пусть пакеты с порядковыми номерами 0, 1 и 2 были успешно получены и квитированы принимающей стороной. В этом случае окно принимающей стороны должно переместиться на 3 пакета вперед, то есть охватить пакеты с номерами 3, 0 и 1. Далее рассмотрим две ситуации. Первая ситуация, представленная на рис. 3.24, а, заключается в потере квитанции для переданных пакетов, что приводит к необходимости их повторной передачи. Таким образом, следующий пакет, получаемый принимающей стороной, будет иметь порядковый номер 0 и являться копией пакета, переданного ранее.
Во второй ситуации, представленной на рис. 3.24, б, квитанция для трех переданных пакетов успешно доставляется передающей стороне. Передающая сторона сдвигает свое окно на 3 позиции и осуществляет передачу пакетов с порядковыми номерами 3, 0 и 1; при этом пакет с номером 3 теряется, а пакет 0 доставляется на принимающую сторону. Заметим, что в пакете с номером 0 содержатся новые, не переданные ранее данные.
Теперь рассмотрим ту же ситуацию с точки зрения принимающей стороны. Действия, выполняемые передающей стороной, скрыты от нее; принимающая сторона способна лишь следить за последовательностями получаемых пакетов и генерируемых квитанций. Подобная ограниченность приводит к тому, что обе описанные выше ситуации воспринимаются принимающей стороной как одинаковые. Принимающая сторона не может отличить исходную передачу первого пакета от его повторной передачи. Очевидно, что протокол, размер окна которого на единицу меньше диапазона порядковых номеров, не является работоспособным. Однако насколько малым должен быть размер окна? В одном из упражнений, приведенных в конце этой главы, вам предлагается самостоятельно доказать, что размер окна SR-протокола не должен превосходить половины диапазона порядковых номеров.
Итак, мы завершаем разговор о протоколах надежной передачи данных. Мы рассмотрели значительный объем материала и ознакомились с множеством механизмов, используемых в этих протоколах, — итог накопленным знаниям подводит табл. 3.2. Просмотрев этот раздел сначала, вы сможете увидеть, как различные механизмы постепенно включались в создаваемый протокол передачи данных, делая его все более и более реалистичным и улучшая качество его функционирования.
Напоследок особо отметим еще одно допущение, лежащее в основе рассмотренной модели канала передачи данных. Оно состоит в том, что во время передачи пакетов не может произойти нарушение порядка их следования. В случае, если канал представляет собой физическую линию связи, подобное допущение выглядит естественным, однако при передаче по разветвленной компьютерной сети изменение порядка следования пакетов вполне возможно. Одно из проявлений такого изменения заключается в том, что пакеты и квитанции с порядковым номером х могут появиться на принимающей и передающей сторонах в те моменты времени, когда номер х уже не принадлежит текущему окну. Фактически процесс передачи по каналу в этом случае можно представить как буферизацию пакетов и отбрасывание их из буфера в случайные моменты времени. Поскольку одни и те же порядковые номера могут неоднократно использоваться при передаче, необходимо следить за возможным дублированием пакетов. Механизмы слежения обеспечивают уверенность передающей стороны в том, что при использовании любого из порядковых номеров в сети не будет ни одного пакета с таким же порядковым номером. Обычно такая уверенность достигается путем введения понятия максимального времени жизни пакета. Например, согласно документу RFC 1323, в протоколе TCP максимальное время жизни пакета для высокоскоростных сетей приблизительно равно 3 мин.
