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

□ Можно добавить в квитанции некоторое количество контрольных битов, достаточное не только для обнаружения, но и для исправления ошибок. Этот способ решает поставленную проблему в случае, если канал только искажает данные, но не теряет их.

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

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

На рис. 7.4 и 7.5 приведены схемы конечных автоматов для протокола rdt 2.1, являющегося исправленной версией rdt 2.0. Оба автомата теперь имеют вдвое больше состояний по сравнению с протоколом rdt 2.0. Это объясняется тем, что необходимо различать состояния протокола, соответствующие двум возможным порядковым номерам (0 и 1) принимаемого/передаваемого пакета. Обратите внимание на то, что действия при приеме/передаче пакета с порядковым номером 0 являются зеркальным отображением действий при приеме/передаче пакета с порядковым номером 1; единственное различие заключается в обработке порядкового номера.

В протоколе rdt 2.1 используются оба вида квитанций (положительные и отрицательные). В случае, когда порядковый номер принятого пакета отличается от ожидаемого, генерируется АСК; если пакет содержит искаженные данные, то генерируется NAK. Мы можем добиться эффекта NAK, если перешлем АСК для последнего принятого пакета. Если передающая сторона получит две положительные квитанции для одного и того же пакета (то есть произойдет удвоение положительных квитанций), то это будет указывать на наличие ошибок в пакете, следующем за тем, для которого были получены сдвоенные квитанции. Модель протокола rdt 2.2, осуществляющего надежную передачу по каналу, допускающему искажения битов без отрицательного квитирования, приведена на рис. 7.6 и 7.7. Единственное различие между протоколами rdt 2.1 и rdt 2.2 заключается в том, что в rdt 2.2 принимающая сторона должна включать в АСК порядковый номер пакета (это достигается путем передачи аргументов АСК,0 и АСКД процедуре make_pkt(); см. схему автомата принимающей стороны), а передающей стороне, в свою очередь, необходимо анализировать порядковый номер пакета, включенный в АСК (путем включения дополнительного аргумента 0 или 1 в процедуру isACK(); см. схему автомата передающей стороны).

Надежная передача данных по каналу, допускающему искажение битов и потерю пакетов

Теперь предположим, что нам необходимо обеспечить передачу данных по каналу, в котором возможны не только искажения, но и потери пакетов (такая ситуация вполне типична для современных компьютерных сетей, включая Интернет). При разработке протокола нам придется решить две дополнительные задачи: найти способ определения факта потери пакета и указать действия, предпринимаемые в этом случае. Последняя задача решается с помощью контрольных сумм, порядковых номеров, квитанций и повторных посылок — механизмов, реализованных ранее в протоколе rdt 2.2. Для решения первой задачи нам потребуется применение новых механизмов.

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

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

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

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

На рис. 7.8 приведена схема конечных автоматов протокола rdt 3.0, осуществляющего надежную передачу данных по каналу, допускающему искажение и потерю пакетов, а на рис. 7.9 — схема функционирования протокола для четырех возможных случаев: передача происходит без потерь и задержек; происходит потеря пакета; происходит потеря квитанции для пакета; истекает интервал ожидания квитанции. Для каждого случая время показано пунктирной стрелкой, направленной сверху вниз. Обратите внимание на то, что момент получения пакета принимающей стороной наступает позже момента передачи пакета передающей стороной из-за задержек в распространении сигнала в сети. На рис. 7.9, б, в и г квадратные скобки обозначают моменты запуска и переполнения таймера. Поскольку порядковые номера пакетов представляют собой меняющиеся значения 0 и 1, протокол rdt 3.0 называется протоколом с чередованием битов.

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

Протоколы надежной передачи данных с конвейеризацией

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

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

Время оборота между хостами при условии, что распространение сигнала происходит со скоростью света, составляет приблизительно 30 мс. Предположим, что хосты соединены между собой каналом связи со скоростью передачи R = 1 Гбит/с = = 109 бит/с. Если размер пакета, включая заголовок и данные, L = 1000 байт = = 8000 бит, то время фактической передачи пакета по каналу:

t(пер) = L/R = (8000 бит/пакет) / (10^9 бит/с) = 8 мкс.

Рис. 7.9 Схема работы протокола rdt 3.0: a - потери пакетов отсутствуют; б-потеря пакета; в-потеря подтверждения; г - истек интервал ожидания

Обратимся к рис. 7.11, а. Если с помощью нашего протокола передающая сторона начнет передачу пакетов в момент времени t = 0, то при t = L/R = 8 мкс последний бит окажется в канале. Распространение пакета в канале займет 15 мс; таким образом, последний бит пакета достигнет принимающей стороны в момент времени t = = RTT/2 + L/R = 15,008 мс. Считая размеры квитанций достаточно малыми для того, чтобы временем их передачи можно было пренебречь, и предполагая, что начало отправки квитанции совпадает с окончанием приема пакета, получаем, что квитанция достигает передающей стороны в момент времени t = RTT + L/R = = 30,008 мс. С этого момента передающая сторона может начинать передачу следующего пакета.