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