Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 73
Текст из файла (страница 73)
3.14, б. Прибытие кадра с неверной контрольной суммой не показано, так как оно не изменяет состояния в протоколе 3. При нормальной Работе протокола переходы 1, 2 3 и д „ „, другом снова и снова. На каждом цикле доставляются два пакета, возвращая отправителя в исходное состояние, в котором он пытается переслать новый кадр с последовательным номером О, Если канал теряет кадр О, происходит переход из состояния (000) в состояние (00 — ). Наконец у отправителя срабатывает таймер (переход 7), и система возвращается в состояние (000). Потеря подтверждения является более сложной ситуацией, так как требует для восстановления два перехода — 7 и 5 (или 8 и 6 в симметричной ситуации). Одно из свойств, которыми должен обладать протокол с 1-битовым порядковым номером, заключается в том, что ни при каких обстоятельствах получатель не должен передавать своему сетевому уровню два нечетных пакета подряд, не передав между ними четного пакета, и наоборот.
Для изображенного на рис. 3.14 графа это требование может быть перефразировано более формально так: «не должно быть пути, начинающегося в исходном состоянии, при котором переход 1 осуществляется два раза подряд без перехода 3 между ними, и наоборот». Из рисунка видно, что данное требование удовлетворяется. Другим сходным требованием является отсутствие пути, при котором отправитель изменяет свое состояние дважды (например, с 0 на 1 и обратно на О) при неизменном состоянии получателя.
Существование такого пути означало бы, что два кадра подряд были безвозвратно потеряны, причем так, что получатель этого не заметил. При этом в последовательности доставляемых сетевому уровню пакетов образовалась бы незаиеченная брешь в два пакета. Еще одним важным свойством протоколов является отсутствие тупиков. Тупиком называется ситуация, в которой протокол не может продвинуться дальше (то есть доставлять пакеты сетевому уровню) ни при каких обстоятельствах. В'терминах графической модели наличие тупика характеризуется существованием подмножества состояний, достижимого из исходного состояния и обладающего двумя следующими свойствами: 1. Из этого подмножества состояний нет перехода. 2. В подмножестве нет переходов, обеспечивающих дальнейшую работу протокола.
Попав в тупиковую ситуацию, протокол остается в ней навсегда. По графу видно, что в протоколе 3 нет тупиков. Сети Петри Конечный автомат является не единственным методом формального описания протокола. В данном разделе будет описана другая методика — сеть Петри (ПавгЬ1пе, 1980). Сетевая модель Петри состоит из четырех основных элементов: позиций, переходов, дуг и маркеров (или фишек). Позицией называется состояние, в котором может находиться система или ее часть. На рис.
3.15 показана сеть 274 Глава Э. Уровень передачи данных Петри, состоящая из двух позиций, А и В, изображенных в виде кружков. В данный момент система находится в состоянии А, отмеченном маркером (жирной точкой) в позиции А. Переход обозначается вертикальной или горизонтальной чертой. У каждого перехода может быть ноль или несколько входящих дуг, идущих от своих исходных позиций, а также ноль или несколько исходящих дуг, направляющихся к выходным позициям, Рио. 3.16.
Сеть Петри из двух позиций и двух переходов Переход называется разрешенным, если имеется хотя бы один маркер на его входных позициях. Любой разрешенный ттереход может возбужлатьгл по желанию, удаляя маркер со всех исходных позиций и размещая их на всех выходных позициях. Количество маркеров на исходных и выходных позициях не обязано совпадать. Если разрешены два илн более переходов, произойти может любой из них. Благодаря недетермпнированности выбора перехода, который произойдет, сети Петри могут использоваться для моделирования протоколов.
Сеть Петри, изображенная на рис. 3.15, детерминирована и может применяться для моделирования любого двухфазного процесса (например, поведения ребенка; поел, поспал, опять поел, опять поспал, и т. д.), Как и при любом моделировании, лишние детали игнорируются. На рис. 3.16 показана сетевая модель Петри, соответствующая графу, описанному в листинге ЗА.
В отличие от конечного автомата, здесь нет составных состояний. Состояния отправителя, получателя и канала изображаются отдельно. Переходы 1 и 2 соответствуют обычной и повторной (но тайм-ауту) передаче кадра О. Переходы 3 и 4 означают то же самое, но для кадра 1. Переходы 5, 6 и 7 соответствуют потере кадра О, подтверждения и кадра 1. Переходы 8 и 9 означают приход к получателю кадра с неверным номером.
Переходы 10 и 11 обозначают получение принимающей машиной следующего кадра и передачу его сетевому уровню. Сети Петри, так же как и конечные автоматы, могут применяться для обнаружения ошибок в протоколах. Например, если какая-нибудь последовательность переходов будет вклточать переход 10 дважды без перехода 11 между ними, зто будет означать, что протокол неверен, Концепция тупиков в сети Петри также мало отличается от своего аналога в модели машины конечных состояний. Сети Петри могут представляться в виде набора алгебраических формул, напоминающих грамматические правила. Каждому переходу соответствует одно правило грамматики. Каждое такое правило описывает входные и выходные позиции перехода.
Поскольку на рис. 3.16 изображено 11 переходов, то и грамматика илтеет 11 правил. Пронумеруем правила таким образом, чтобы каждое из них соответствовало переходу с тем же номером. Грамматика сети Петри, изображенной на рис. 3.16, представлена ниже: Верификация протоколов 275 С. Кедр О на линии О: Подтверждение на пинии Е: Кедр 1 нв линии Обработка кадра О Передача кадра О Ожидание кедра 1 Свкидания подтверждения О Передача кадра 1 Обработка кадра 1 Ожидания подтверждения 1 Ожидание кадра Π— Потеря Состояния отправителя Состояние канала Состояние получателя Интересно, что нам удалось компактно описать довольно сложный протокол набором из 11 элементарных правил грамматики, легко реализуемых компьютерной программой.
Текущее состояние сети Петри представляется неупорядоченным набором позиций, каждая из которых появляется в наборе столько раз, сколько фишек в ней имеется. Любое правило из грамматики, имеющее левую часть, может активироваться, удаляя свои левые позиции из текущего состояния сети и добавляя свои правые (выходные) позиции к текущему состоянию. Текущее состояние (маркировка) сети, изображенной на рис. 3.16, — АСС, поэтому, например, правило 10 1 ВО -+ АС 2: А -+ А З АО -+ ВЕ 4: В -+ В 5: С -> б: 0 -л 7: Е -ч В; СГ -+ ОГ 9 Е6 -+ 06 10: С6 -+ ОГ 11: ЕГ -ч 06 Рис. 3.13. Сетевая модель Петри для протокола 3 276 Глава 3. Уровень передачи данных (СС -+ 1Щ может быть применено, а правило 3 (А1з -+ ВЕ) — нет, потому что 1) не имеет маркера.
Примеры протоколов передачи данных В следующих разделах мы рассмотрим нскоторыс широко используемые протоколы передачи данных. Первый из них, классический бит-ориептированный протокол Н1)).С, часто употреблялся во многих сетях. Второй, РРР, — это протокол уровня передачи данных, используемый при подключении к Интернету домашних компьютеров. НО~С вЂ” высокоуровневый протокол управления каналом В данном разделе мы рассмотрим группу тесно связанных друг с другом протоколов, немного устаревших, но все еще широко применяемых в сетях. Все они произошли от одного протокола передачи данных, применявшегося в разработанных компанией 1ВМ мейнфреймах, — этот протокол называется $1)1.С (Зупс!1гопопз Паса 1(п1с Сопгго1 — синхронное управление каналом).
После разработки протокола 51)(.С корпорация 1ВМ представила его на рассмотрение институтов А)х131 и 150 для утверждения в качестве стандарта США и международного стандарта соответственно. АХ51 модифицировал протокол в А1)ССР (Абчапсеб РаСа Сощшпп1сат(оп Сопгго1 Ргоссбцге — усовершенствованная процедура управления информационным обменом), а 150 переделала его в НОЕС (Н1ф-1ече1 Эа1а 1.1п(с Со|пго1 — высокоуровневый протокол управления каналом), После этого протокол был принят комитетом СС1 гт, который адаптировал Н1)1 С для своего протокола доступа к каналу 1.АР (1.1пк Ассезз Ргосес)цге — процедура доступа к каналу), являющегося частью стандарта сетевого интерфейса Х.25, однако затем снова изменил его иа МАРВ, повысив его совместимость с более поздней версией НР1.С. Что хорошо в стандартах, так это то, что у вас всегда есть из чего выбрать.
Если же вас не устраивает ни один из имеющихся стандартов, вы можете просто подождать появления новой модели в новом году. В основе всех этих протоколов лежат одни и те же принципы. Все они являются бит-ориентированными, и во всех применяется битовое заполнение, обеспечивающее прозрачность данных. Они различаются только в незначительных, ио, тем не менее, вызывающих раздражение деталях, Последующее обсуждение бит-ориентированных протоколов нужно рассматривать как общее введение. Специфические детали протоколов приводятся в соответствующих официальных описаниях.
Во всех бит-ориентированных протоколах используется формат кадра, показанный на рис, 3.17. Поле Ай(гезз (адрес) чрезвычайно важно для линий с несколькими терминалами, где оно используется для идентификации одного из терминалов, В двухточечных сетях это поле иногда используется, чтобы отличать команды от ответов. Примеры протоколов передачи данных 277 Поле Сон(го! (управляющей информации) используется для хранения порядковых номеров, подтверждений и других служебных данных, как будет показано далее.
8 8 8 О 16 8 Биты Рис. 3.17. Формат кадра бит-ориентированных протоколов Поле !хата (данныс) может содержать произвольную информацию. Оно может быть любой длины, хотя эффективность контрольной суммы снижается с увеличением длины кадра пз-за увеличения вероятности многочисленных пакетов ошибок. Поле С)гесЬигл (контрольная сумма) является разновидностью циклического избыточного кода, который мы рассматривали в разделе еКоды с обнаружением ошибок».
В качестве заголовка и концевика кадра используется флаговый байт (01111110). В линиях «точка — точка», которые в текущий момент времени простаивают, флаговые последовательности передаются постоянно. Кадр хшнимального размера состоит из трех полей, занимающих в обшей сложности 32 бита, не считая флаги в начале и в конце.
Все кадры можно разделить на три категории: информационные, супервизорные и ненумерованные. Содержимое поля Сон(го! для этих трех типов кадров показано на рис. 3.18. Протокол использует скользящее окно с 3-битовым порядковым номером. В каждый момент времени в сети может находиться не более семи неподтвержденных кадров. Поле 5е() на рис. 3.18, а содержит порядковый номер кадра. Поле №хг является пересылаемым вместе с кадром подтверждением. Однако все протоколы придерживаются соглашения о том, что вместо т(омера последнего правильно принятого кадра в поле №хт пересылается номер первого не принятого кадра (то есть следующего ожидаемого кадра). Впрочем, номер кадра, используемого для подтверждения, не принципиален.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
