Возвращение на N пакетов назад
В протоколах, использующих метод возвращения на N шагов назад (Go-Back-N, GBN), передающая сторона может посылать последовательности пакетов, не ожидая квитанций, при этом максимальная длина последовательности ограничена некоторым числом N. На рис. 3.18 представлена схема определения диапазона порядковых номеров. Если base — порядковый номер самого «старого» неподтвержденного пакета, a nextseqnum — наименьший из «свободных» порядковых номеров (то есть номер, который будет присвоен следующему посылаемому пакету), то полный диапазон порядковых номеров можно разделить на четыре части. Номера в диапазоне от 0 до base-1 назначены переданным ранее пакетам, для которых уже получены квитанции. Номера от base до nextseqnum-1 также относятся к переданным пакетам, однако для этих пакетов квитанции еще не получены. Номера от nextseqnum до base+N-1 могут быть назначены пакетам, которые необходимо сформировать и отправить сразу при поступлении новых данных от прикладного уровня. Номера, превышающие значение base+N, нельзя использовать до тех пор, пока не будет получена квитанция для текущего пакета, то есть пакета с порядковым номером base.
Как показано на рисунке, диапазон порядковых номеров для пакетов, которые могут быть переданы без ожидания квитанций, можно рассматривать в виде «окна» размером N, лежащего внутри множества порядковых номеров. В процессе выполнения протокола это окно «движется» в сторону увеличения порядковых номеров. Такое представление определило терминологию, в соответствии с которой значение N называют размером окна, а протокол GBN — протоколом скользящего окна. Вероятно, у вас возникает вопрос: для чего нужно ограничивать число пакетов, передаваемых без ожидания подтверждения, размером окна ЛГ? В следующем разделе этой главы мы увидим, что одной из причин является необходимость контролировать передаваемый поток данных. Другая причина будет раскрыта в разделе «Контроль перегрузок в ТСР», где мы займемся изучением механизма контроля перегрузки, реализованного в протоколе TCP.
На практике порядковый номер пакета хранится в одном из полей заголовка, имеющем фиксированную длину. Если k — число битов этого поля, то диапазоном порядковых номеров является [0,2k — 1]. Поскольку множество порядковых номеров конечно, все арифметические операции с ними производятся по модулю 2k (другими словами, множество порядковых номеров можно представить в виде кольца, в котором числом, следующим за 2k — 1, является 0). Возвращаясь к протоколу rdt 3.0, отметим, что разрядность его порядковых номеров равна 1, а диапазон — [0,1]. В конце этой главы перечислены несколько проблем, порождаемых ограниченностью множества порядковых номеров. Как мы увидим позже, в протоколе TCP порядковые номера имеют разрядность 32 и предназначены для подсчета байтов (вместо пакетов) в байтовом потоке.
На рис. 3.19 и 3.20 представлены расширенные модели конечных автоматов, описывающие передающую и принимающую стороны GBN-протокола с механизмом квитирования без использования отрицательных квитанций. Мы назвали эти модели расширенными, поскольку они включают в себя переменные величины base и nextseqnum (напоминающие переменные в языках программирования), а также различные операции и другие действия с участием этих переменных. Более того, спецификация расширенной модели конечных автоматов очень напоминает спецификацию языка программирования.
Передающая сторона GBN-протокола должна реагировать на три вида событий.
□ Вызов протоколом более высокого уровня. Когда «сверху» вызывается функция rdt_send(), передающая сторона сначала производит проверку степени заполнения окна (то есть наличия N посланных сообщений, ожидающих получения квитанций).
Если окно оказывается незаполненным, новый пакет формируется и передается, а значения переменных обновляются. В противном случае передающая сторона возвращает данные верхнему уровню, что является неявным указанием на то, что окно заполнено. Обычно верхний уровень предпринимает повторную попытку передачи данных через некоторое время. На практике передающая сторона чаще всего располагает либо буфером, в котором данные хранятся до появления возможности их пересылки, либо механизмом синхронизации (например, семафором или флагом), позволяющим вызывать функцию rdt_send() только при наличии незаполненного окна.
□ Получение подтверждения. В нашем GBN-протоколе для пакета с порядковым номером п выдается общая квитанция, указывающая на то, что все пакеты с порядковыми номерами, предшествующими п, успешно приняты. Мы вернемся к механизму квитирования при рассмотрении принимающей стороны GBN-протокола.
□ Истечение интервала ожидания. Своим названием GBN-протокол обязан механизму реагирования на потери и задержки данных. Как и в случае протокола с ожиданием подтверждения, для определения фактов потерь и задержек пакетов и квитанций GBN-протокол использует таймер. В случае истечения интервала ожидания передающая сторона осуществляет повторную передачу всех посланных неподтвержденных пакетов. В нашем примере (см. рис. 3.19) передающая сторона использует единственный таймер, который отсчитывает время от момента передачи самого «старого» из пакетов, для которого не получено подтверждение. Если подтверждение получено, но при этом имеются переданные неподтвержденные пакеты, происходит сброс таймера. Отсутствие неподтвержденных пакетов приводит к остановке таймера.
Действия, предпринимаемые принимающей стороной GBN-протокола, также не отличаются сложностью. Если доставка пакета с порядковым номером п произошла корректно и без нарушения очередности (то есть последние данные, переданные верхнему уровню, относятся к пакету с порядковым номером п- 1), то принимающая сторона генерирует подтверждение и передает новые данные верхнему уровню. В противном случае принятый пакет игнорируется, а подтверждение генерируется для последнего корректно обработанного пакета. Поскольку пакеты передаются верхнему уровню по одному, передача пакета k означает, что все пакеты с порядковыми номерами, меньшими k, уже переданы верхнему уровню. Таким образом, применение механизма группового квитирования в GBN-протоколах является весьма естественным.
Наш GBN-протокол игнорирует пакеты, полученные с нарушением порядка следования. Несмотря на то что удаление пакета, не содержащего ошибок (а лишь нарушившего порядок следования данных), кажется нерациональным и неэкономным, существуют причины, обусловливающие это удаление. Мы знаем о том, что приемная сторона должна обеспечивать передачу данных верхнему уровню в правильном порядке. Предположим, что вместо пакета с порядковым номером п приемная сторона получает пакет с номером п + 1. Поскольку мгновенная доставка такого пакета верхнему уровню невозможна, необходимо организовать промежуточное хранение пакета п + 1 до момента, когда будет принят пакет п, а его данные переданы верхнему уровню. В случае потери пакета п в соответствии с GBN-npo-токолом организуется повторная передача как пакета п, так и пакета п + 1.
Таким образом, принимающая сторона может не сохранять пакет п + 1. Кроме того, игнорирование пакетов, полученных с нарушением порядка следования, позволяет упростить буферизацию на принимающей стороне. Из сказанного следует, что передающая сторона оперирует тремя величинами: верхней и нижней границами окна, а также наименьшим свободным порядковым номером. Для принимающей стороны необходим лишь порядковый номер следующего по порядку пакета. Эта величина хранится в переменной expectedseqnum, присутствующей на схеме, показанной на рис. 3.20. Необходимо признать, что механизм удаления успешно принятых пакетов тоже «небезгрешен»: при повторной передаче существует вероятность новой потери пакета, что, в свою очередь, приводит к необходимости дополнительных повторных передач.
На рис. 3.21 показана схема функционирования GBN-протокола, в котором размер окна составляет 4 пакета. Осуществив передачу пакетов с порядковыми номерами от 0 до 3, передающая сторона должна получить подтверждение хотя бы для одного из них. Как только подтверждения будут получены (например, АСКО и АСК1), окно переместится «вперед», и передающая сторона сможет послать 2 новых пакета (pkt4 и pkt5). Когда принимающая сторона обнаруживает потерю пакета 2, пакеты 3, 4 и 5 считаются нарушившими порядок следования данных и игнорируются.
Отметим, что реализация GBN-протоколов в стеке протоколов, как правило, имеет структуру, схожую со структурой конечного автомата, представленного на рис. 3.19. Действия, выполняемые протоколом при наступлении различных событий, оформлены в виде процедур. В подобных событийно-управляемых программах выполнение процедур происходит либо при их вызове другими процедурами стека протоколов, либо при наступлении прерывания. На передающей стороне событиями, управляющими программой, являются вызов функции rdt_send() протоколом верхнего уровня, прерывание от таймера и вызов функции rdt_rcv() протоколом нижнего уровня при получении пакета.
Созданный нами GBN-протокол поддерживает почти все методы, использующиеся в протоколе надежной передачи данных TCP, который будет рассмотрен в следующем разделе. Мы увидим, что и TCP поддерживает порядковые номера, общие квитанции, контрольные суммы, интервалы ожидания и повторную передачу пакетов.