Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 69
Текст из файла (страница 69)
Все остальные состояния могут рассматриваться как временные,промежуточные между этими двумя. Обычно выбираются состояния, соответствующие ожидаемым событиям (это соответствует вызову процедуры wait (event)в наших примерах протоколов). Состояние протокольной машины полностью определяется состоянием ее переменных. Количество состояний равно 2", где п —количество битов, необходимых для описания всех переменных, вместе взятых.Состояние всей системы представляет собой комбинацию всех состояний двухпротокольных машин и состояний канала. Состояние канала определяется егосодержимым. При использовании протокола 3 у канала может быть четыре возможных состояния: кадр 0 или кадр 1, перемещающийся от отправителя к получателю, кадр подтверждения, двигающийся в противоположном направлении, илиВерификация протоколов271пустой канал.
Если отправитель и получатель могут находиться в двух различных состояниях, то вся система будет иметь 16 различных состояний.Следует сказать несколько слов о состоянии канала. Концепция кадра, находящегося в канале, конечно, является абстракцией. Имеется в виду, что кадр частично передан, частично принят, но еще не обработан получателем. Кадр остается «в канале» до тех пор, пока протокольная машина не выполнит процедуруfrom_physical_layer и не обработает его.Каждое состояние может быть соединено с другими состояниями несколькими(0 или больше) переходами.
Переходы всегда соответствуют каким-либо событиям. Для протокольной машины переход происходит, когда прибывает новыйкадр, истекает время ожидания какого-либо таймера, происходит прерывание и т. д.Для канала обычными событиями являются следующие: помещение протокольной машиной в канал нового кадра, доставка кадра протокольной машине илипотеря кадра вследствие всплеска шума. Имея полное описание протокольноймашины и характеристик канала, можно нарисовать направленный граф, изображающий все состояния в виде узлов, а переходы — в виде направленных дуг.Одно особое состояние обозначается как начальное. Оно соответствует состоянию системы в момент ее запуска или состоянию, близкому к нему.
Из начального состояния можно попасть во многие (вероятно, даже во все) другие состояния с помощью серии переходов. Применяя хорошо известные методы теорииграфов (например, вычисляя транзитивное замыкание графа), можно определить, какие из состояний достижимы, а какие нет. Такой метод называется анализом достижимости (Lin и др., 1987). Данный анализ может быть полезен дляопределения правильности протокола.Формально модель протокола машины конечных состояний можно рассматривать как набор их четырех множеств (5, М, /, Т), где S — множество состояний,в которых могут находиться процессы и канал; М — множество кадров, передающихся по каналу; / — множество начальных состояний процессов; Т — множе* ство переходов между состояниями.В начальный момент времени все процессы находятся в исходном состоянии.Затем начинают происходить события — например, появляются кадры, которыенужно передать по каналу, или срабатывает таймер.
Каждое событие может переключить один из процессов или канал в новое состояние. Тщательно нумеруявсе возможные предшественники каждого состояния, можно построить дереводостижимости и проанализировать протокол.Анализ достижимости может применяться для обнаружения разнообразныхошибок спецификации протокола. Например, если какой-либо кадр может оказаться в таком состоянии, в котором конечный автомат не сможет определить,какое действие следует предпринять, это означает, что спецификация ошибочна(неполнота протокола). Если имеется ряд состояний, из которых нет выхода (тоесть никакие кадры больше не смогут передаваться), это также означает ошибкуспецификации (тупик).
Менее серьезной ошибкой спецификации протокола является описание обработки события в состоянии, в котором это событие не может произойти (лишний переход). Могут быть обнаружены и другие ошибки.272Глава 3. Уровень передачи данныхВерификация протоколовВ качестве примера конечного автомата рассмотрим рис. 3.14, а.
Этот графсоответствует протоколу 3, описанному ранее, — у каждой протокольной машины может быть два состояния, а у канала — четыре состояния. Итого возможны16 состояний, некоторые из которых недоступны из начального состояния. Недостижимые состояния не показаны на рисунке. Для упрощения также опущеныситуации с ошибками контрольных сумм.Каждое состояние помечено тремя символами: SRC, где S является 0 или 1и соответствует номеру кадра, который пытается послать отправитель; R такжеможет быть равно 0 или 1 и означает номер кадра, ожидаемого получателем, а Сможет принимать значения 0, 1, Л или пусто (-), в соответствии с состоянием канала.
В данном примере было выбрано исходное состояние (000). То есть отправитель только что послал кадр 0, получатель ожидает кадра 0, и кадр 0 находитсяв канале.ПереходКтоуправляет?Кадрпринят012345678ПолучательОтправительПолучательОтправительПолучательПолучательОтправительОтправитель0Подтверждение1Подтверждение01(тайм-аут)(тайм-аут)КадрпереданСетевомууровню(кадр потерян)Подтверждение1Подтверждение0ПодтверждениеПодтверждение01Да_ДаНетНет-273тевому уровню, изменяет свое состояние на ожидание кадра 1 и пересылаетподтверждение. Остальные переходы приведены на рис. 3.14, б.
Прибытие кадрас неверной контрольной суммой не показано, так как оно не изменяет состояния в протоколе 3.При нормальной работе протокола переходы 1, 2, 3 и 4 повторяются друг задругом снова и снова. На каждом цикле доставляются два пакета, возвращая отправителя в исходное состояние, в котором он пытается переслать новый кадр споследовательным номером 0. Если канал теряет кадр 0, происходит переход изсостояния (000) в состояние (00-).
Наконец у отправителя срабатывает таймер(переход 7), и система возвращается в состояние (000). Потеря подтвержденияявляется более сложной ситуацией, так как требует для восстановления два перехода — 7 и 5 (или 8 и 6 в симметричной ситуации).Одно из свойств, которыми должен обладать протокол с 1-битовым порядковым номером, заключается в том, что ни при каких обстоятельствах получательне должен передавать своему сетевому уровню два нечетных пакета подряд, непередав между ними четного пакета, и наоборот. Для изображенного на рис. 3.14графа это требование может быть перефразировано более формально так: «не должно быть пути, начинающегося в исходном состоянии, при котором переход 1 осуществляется два раза подряд без перехода 3 между ними, и наоборот».
Из рисунка видно, что данное требование удовлетворяется.Другим сходным требованием является отсутствие пути, при котором отправитель изменяет свое состояние дважды (например, с 0 на 1 и обратно на 0) принеизменном состоянии получателя. Существование такого пути означало бы, чтодва кадра подряд были безвозвратно потеряны, причем так, что получатель этогоне заметил. При этом в последовательности доставляемых сетевому уровню пакетов образовалась бы незамеченная брешь в два пакета.Еще одним важным свойством протоколов является отсутствие тупиков. Тупиком называется ситуация, в которой протокол не может продвинуться дальше(то есть доставлять пакеты сетевому уровню) ни при каких обстоятельствах._ Втерминах графической модели наличие тупика характеризуется существованием подмножества состояний, достижимого из исходного состояния и обладающего двумя следующими свойствами:1.
Из этого подмножества состояний нет перехода.2. В подмножестве нет переходов, обеспечивающих дальнейшую работу протокола.Попав в тупиковую ситуацию, протокол остается в ней навсегда. По графувидно, что в протоколе 3 нет тупиков.Сети ПетриРис. 3.14. Диаграмма состояний для протокола 3 (а); переходы (б)На рис. 3.14 показаны девять типов переходов. Переход 0 заключается в потере каналом содержимого. Переход 1 состоит в том, что канал успешно доставляет пакет 0 получателю, при этом получатель передает пакет 0 своему се-Конечный автомат является не единственным методом формального описанияпротокола.
В данном разделе будет описана другая методика — сеть Петри(Danthine, 1980). Сетевая модель Петри состоит из четырех основных элементов:позиций, переходов, дуг и маркеров (или фишек). Позицией называется состояние, в котором может находиться система или ее часть. На рис. 3.15 показана сеть274Глава 3. Уровень передачи данныхПетри, состоящая из двух позиций, Аи В, изображенных в виде кружков. В данный момент система находится в состоянии А, отмеченном маркером (жирнойточкой) в позиции А. Переход обозначается вертикальной или горизонтальнойчертой.
У каждого перехода может быть ноль или несколько входящих дуг, идущих от своих исходных позиций, а также ноль или несколько исходящих дуг, направляющихся к выходным позициям.Верификация протоколовАС1 : BD2: A BE3 : AD4: В -> В5: С - >6 : D -*7: Е ->8 : CF -» DF9 : EG - > DG10: CG - > DF1 1 : EF - > DGС: Кадр 0 на линииD: Подтверждение на линииЕ: Кадр 1 на линииРис. 3.15. Сеть Петри из двух позиций и двух переходовПереход называется разрешенным, если имеется хотя бы один маркер на еговходных позициях. Любой разрешенный переход может возбуждаться по желанию, удаляя маркер со всех исходных позиций и размещая их на всех выходныхпозициях. Количество маркеров на исходных и выходных позициях не обязаносовпадать.
Если разрешены два или более переходов, произойти может любой изних. Благодаря недетерминированности выбора перехода, который произойдет,сети Петри могут использоваться для моделирования протоколов. Сеть Петри,изображенная на рис. 3.15, детерминирована и может применяться для моделирования любого двухфазного процесса (например, поведения ребенка: поел, поспал, опять поел, опять поспал, и т. д.). Как и при любом моделировании, лишние детали игнорируются.На рис. 3.16 показана сетевая модель Петри, соответствующая графу, описанному в листинге 3.4. В отличие от конечного автомата, здесь нет составных состояний. Состояния отправителя, получателя и канала изображаются отдельно.Переходы 1 и 2 соответствуют обычной и повторной (по тайм-ауту) передачекадра 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
