Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 25
Текст из файла (страница 25)
Для обнаружения и устранения этих ошибок вычислительные станции используют дополнительные средства,которые принято назвать протоколами.Основным назначением этих протоколов является передача данных , т. е. получение информации от одной станции и доставка ее по назначению другой станции. Надежная передача данных предполагает повторную передачу тех сообщений, которые были потеряны, избавление от дублирующих сообщений, исправление поврежденных сообщений и устранение фиктивных сообщений. Для этогов протоколе ведется учет состояния информации; в нем отмечается, какие данные уже были отправлены, какие данные были зарегистрированы как полученныеи пр.
В связи с необходимостью использования состояния информации возникаетвопрос об управлении соединением, т. е. инициализации и аннулировании состояния информации. Инициализация называется установлением соединения,а аннулирование — завершением соединения. Трудность управления соединением вызвана тем обстоятельством, что при завершении соединения не исключенавероятность того, что в каналах связи могут еще оставаться сообщения. Приемтаких сообщений может произойти вне всякого соединения связи или в рамкахпоследующих соединений, и получение этих сообщений не должно нарушать правильность проведения очередных соединений.Протоколы, которые будут рассмотрены в этой главе, относятся к разнымуровням иерархии протоколов согласно классификации на основе базовой модели OSI (см. §1.2.2). Эти протоколы включены в книгу по разным причинам;первый из этих протоколов вполне асинхронный, в то время как во втором предусматривается правильное использование таймеров.
Во обоих случаях при верификации этих протоколов внимание будет сосредоточено на проверке свойствабезопасности, которое выражает требование доставки получателю всех правильных данных.Первый протокол, описанный в §3.3.1, предназначен для обмена даннымимежду двумя станциями, которые имеют прямое физическое соединение (напри87мер, по телефонной линии); этот протокол относится к уровню управления передачей данных — второму уровню модели OSI. Второй протокол, описанныйв § 3.3.2, предназначен для организации связи между двумя станциями в том случае, когда эта связь осуществляется через промежуточную сеть, которая включает в себя другие станции и допускает соединение конечных станций по различныммаршрутам; этот протокол относится к транспортному уровню модели OSI.
Эторазличие между протоколами оказывает двоякое влияние на их функциональныевозможности.1. Обрабатываемые ошибки. Для этих двух протоколов будут рассмотрены различные классы ошибок передачи данных. Сообщения не могут обгонятьдруг друга при физическом соединении, и они также не могут дублироваться;поэтому в §3.3.1 рассматриваются только ошибки потери сообщения (об искажении сообщений говорится чуть ниже). В сетях сообщения могут перемещатьсяпо разным маршрутам, и поэтому они могут обгонять друг друга; кроме того,вследствие неисправностей в работе промежуточных станций сообщения могуткак дублироваться, так и утрачиваться. Поэтому в § 3.3.2 будут рассматриватьсяошибки утраты, дублирования и переупорядочения сообщений.2.
Управление соединением. Мы не будем рассматривать управление соединением для первого протокола, этот вопрос существен для второго протокола.Предполагается, что физическое соединение обычно функционирует непрерывнов течение очень долгого времени, а не устанавливается и завершается периодически. Совсем по-другому происходит соединение с удаленными станциями.Потребность в таком соединении возникает на короткий срок для обмена некоторыми данными, но обычно поддерживать неопределенно долгое время соединение с каждой удаленной станцией — это слишком накладно. Поэтому второйпротокол должен обладать способностью устанавливать и завершать соединения.Изучение первого протокола показывает, что добиться требуемых свойствбезопасности протоколов передачи данных можно без привлечения таймеров.В §3.3.1 представлен первый развернутый пример обоснования свойств безопасности, опирающегося на те методы доказательства, которые были описаныв §2.5.2.
Принято считать (см. [199]), что для безопасного управления соединением необходимо использовать таймеры и устанавливать срок пребывания сообщения на этапе пересылки. Поэтому при обосновании свойств безопасностипротоколов управления соединением нужно принимать в расчет ту роль, которую в них играют таймеры. В §3.3.2 мы покажем, как можно ввести таймерыв модель распределенных систем (определение 2.6), и приведем пример одной изтаких расширенных моделей.Искажение сообщений.
Вполне естественно, что во внимание должна бытьпринята вероятность того, что при передаче сообщения подвергаются искажениям. Содержание сообщения, передаваемого по физическому каналу связи, можетбыть повреждено вследствие атмосферных помех, нарушений работы устройствпамяти и т. п. Тем не менее можно предполагать, что процесс-получатель способен обнаруживать искажения сообщений, например, при помощи счетчиков четности или более общих методов обнаружения ошибок (об этом рассказано в ра88Гл.
3. Коммуникационные протоколыботе [182, гл. 3]). В таком случае к получению искаженного сообщения можноотноситься так, как будто никакого сообщения не было получено, и это означает,что искажение сообщения может быть приравнено к потере сообщения. Поэтомумы не уделяем особого внимания искажениям сообщений, но всегда учитываемвероятность того, что сообщение может быть потеряно.3.1.
Симметричный протокол раздвижного окнаВ этом параграфе изучается симметричный протокол, надежный двусторонний обмен информацией. Этот протокол позаимствован из работы [173, гл. 2].Поскольку он служит для обмена информацией между станциями, соединеннымипрямой линией связи, можно предполагать, что в каналах связи поддерживаетсяочередность сообщений. Однако это допущение не будет приниматься в расчетвплоть до §3.1.3, в котором будет показано, что используемая в протоколе нумерация элементов последовательности может быть ограничена. Описание протокола приведено в §3.1.1, а его корректность доказана в §3.1.2.Два взаимодействующих процесса будут обозначаться буквами р и q. Описание протокола, а также все допущения и требования относятся к процессу рв той же мере, в какой они относятся к процессу q.
Входными данными процессар является та информация, которую он должен отправить процессу q, эта информация моделируется бесконечным массивом слов inp. Выходными даннымипроцесса р является та информация, которую он получает от процесса q, и онатакже моделируется бесконечным вектором слов outp. Считается, что р имеетпроизвольный доступ для чтения элементов массива inp и произвольный доступдля записи в массив outp. Первоначально элементы outp[i\ для каждого i имеютнеопределенное значение udef. Вход и выход процесса q соответственно моделируются массивами inq и outq.
Для индексации элементов массивов используютсянатуральные числа, и нумерация элементов начинается с нуля. Как будет показано в §3.1.3, вместо произвольного доступа к массивам можно ограничитьсядоступом к «окну» конечного размера, которое перемещается по массиву. Вотпоэтому этот протокол часто называют «протоколом раздвижного окна».В процессе р имеется переменная sp, служащая для обозначения наименьшего номера того слова, которое процесс р все еще ожидает получить от процесса q.Таким образом, в каждый момент времени участок массива, начинающийся элементом outp[0] и оканчивающийся элементом outp[sp —1], уже заполнен процессом р. Значение переменной sp не убывает. Совершенно аналогичная переменнаяsq имеется в процессе q.
Теперь мы можем сформулировать те требования, которые предъявляются к протоколу. Свойство безопасности предписывает каждомупроцессу формировать на выходе только правильные данные, а свойство живостипредусматривает, что все данные рано или поздно достигнут назначения.1. Безопасная доставка данных. В каждой достижимой конфигурации протокола выполняются соотношенияoutp[0..sp - 1] = inq[0..sp - 1]и outq[0..sq - 1] = inp[0..sq - 1].3.1. Симметричный протокол раздвижного окна892. Неизбежная доставка сообщений. Для каждого целого числа k > Ов ходе выполнения протокола будет достигнута конфигурация, в которой s p > kи Sq ^ k.3.1.1.
Описание протоколаОбычно в протоколах передачи данных значительную роль играют подтверждающие сообщения. Подтверждающее сообщение посылается процессом-получателеичтобы оповестить процесс-отправитель о том, что данные были успешно доставлены по назначению. Если отправитель данных не получает подтверждение, онпередает те же самые данные повторно исходя из предположения о том, что этиданные (или подтверждение об их получении) были потеряны.
Однако в протоколе, который описан в этом параграфе, подтверждающие сообщения в явном видене фигурируют. В рассматриваемом протоколе на обеих станциях есть сообщения, которые они должны отправить друг другу; для каждой станции ее входныеданные используются для подтверждения получения сообщений от другой станции.Сообщения, которыми обмениваются процессы, называются пакетами', пакет представляет собой набор вида (pack, w, i), где w — информационное слово,a i — натуральное число, которое называется порядковым номером пакета.
Этотпакет, будучи отправленным процессом р (по назначению q), не только передаетслово w = inp[i] процессу q, но также, как было отмечено выше, служит подтверждением тому, что ряд пакетов, отправленных процессом q, был успешнополучен. Процесс р может «опережать» процесс q на некоторое заданное числопакетов 1Р, если мы постановим, что отправление пакета (pack, w, i) процессом рподтверждает получение слов с номерами 0, . . .
, i—lp от процесса q. (То же самоезначение придается пакетам, которые отправляются процессом q.) Константы 1Ри lq — это неотрицательные целые числа, известные процессам р и q. Использование пакетов данных в качестве подверждающих сообщений имеет двоякиепоследствия для переходов рассматриваемого протокола.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
