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

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

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

Квитанции служат для того, чтобы принимающая сторона могла уведомлять передающую сторону о том, содержатся ли искажения в каждом из принятых предложений. В сфере компьютерных сетей протоколы надежной передачи данных, обладающие подобным механизмом многократного повторения передачи, называются протоколами с автоматическим запросом повторной передачи (Automatic Repeat reQuest, ARQ).

Для разрешения проблем искажения битов в ARQ-протоколах используются три дополнительных механизма.

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

□ Обратная связь с передающей стороной. Поскольку приемная и передающая стороны находятся на разных оконечных системах, возможно, разделенных тысячами километров, единственный способ уведомить передающую сторону о результате передачи пакетов заключается в организации обратной связи, исходящей от принимающей стороны. Обратная связь, как и в примере с телефонным сообщением, заключается в посылке положительных (АСК) или отрицательных (NAK) квитанций. Минимальная длина квитанции составляет 1 бит, поскольку двух различных значений (0 и 1) достаточно, чтобы указать исход передачи.

□ Повторная передача. Пакет, при передаче которого были зафиксированы ошибки, подлежит повторной передаче передающей стороной.

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

Автомат передающей стороны имеет два состояния. Состояние а соответствует ожиданию передачи данных от верхнего уровня. При наступлении события rdt_send(data) передающая сторона создает пакет sndpkt, включающий данные и поле контрольной суммы (например, вычисляемой по аналогии с протоколом UDP, как описано в предыдущем разделе), и отсылает его приемной стороне методом udt_send(sndpkt). Состояние б соответствует ожиданию квитанции от приемной стороны. В случае получения квитанции АСК, то есть наступления события rdt_rcv(rcvpkt) && isACK (rcvpkt), передающая сторона переходит в состояние ожидания данных от верхнего уровня. Если квитанция оказывается отрицательной (NAK), происходит повторная передача пакета и ожидание ее результата (квитанции). Важной особенностью передающей стороны является то, что, находясь в состоянии ожидания квитанции, она не может принимать данные от верхнего уровня; прием новой порции данных возможен только после получения положительной квитанции для текущего пакета. Таким образом, безошибочная передача предыдущего пакета является необходимым условием для начала передачи следующего пакета. Протоколы, функционирующие подобным образом, называют протоколами с ожиданием подтверждений.

39.png

Принимающая сторона rdt 2.0 по-прежнему описывается единственным состоянием. При получении пакета генерируется квитанция АСК или NAK в зависимости от того, содержит принятый пакет ошибки или нет. Приему пакета, содержащего ошибки, соответствует событие rdt_rcv(rcvpkt) && corrupt(rcvpkt).

Со стороны протокол rdt 2.0 может выглядеть работоспособным, однако ему присущ «врожденный» порок, заключающийся в незащищенности квитанций от возможных искажений (перед тем как двигаться дальше, обдумайте возможные пути решения этой проблемы). Этот порок, к сожалению, гораздо серьезней, чем кажется на первый взгляд. Для его устранения нам необходимо, как минимум, включить в квитанцию поле контрольной суммы. Нетривиальным также является решение вопроса о том, каким образом протокол должен действовать при наличии ошибок в квитанциях, поскольку принимающая сторона в этом случае не получает никакой информации о результатах передачи последнего пакета.

Ниже приведены три возможных варианта организации работы протокола с квитанциями, содержащими ошибки.

□ Вернемся к примеру с телефонным сообщением и представим себе, как два человека могут решить подобную проблему. Если передающий абонент не расслышал фразу «Да!» или «Повтори это еще раз!», он может обратиться к принимающему абоненту с фразой «Что ты сказал?», являющейся новым типом пакета в протоколе. С другой стороны, как поступить, если и она не будет расслышана? Не понимая, является ли эта фраза новым предложением, принимающий, вероятно, ответит фразой «Что ты сказал?»; в свою очередь, она также может быть не расслышана. Очевидно, что описанный способ решения проблемы является весьма громоздким и ненадежным.

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

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

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

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

310.png

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

311.png

Погода в Виннице

Данная статья "Надежная передача данных по каналу, допускающему искажение битов" размещена на сайте Компьютерные сети и многоуровневая архитектура интернета (conlex.kz) в ознакомительных целях.

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

Ответственность, за все изменения, внесённые в систему по советам данной статьи, Вы берёте на себя.

Копирование статьи "Надежная передача данных по каналу, допускающему искажение битов", без указания ссылки на сайт первоисточника Компьютерные сети и многоуровневая архитектура интернета (conlex.kz), строго запрещено.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *