Композиционные методы разработки протоколов на основе сетей Петри

• Автор: Анисимов, Николай Александрович
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 1994
• Место защиты: Владивосток
• Количество страниц: 337 с. : ил.

Содержание
ВВЕДЕНИЕ

1 ЛОГИЧЕСКАЯ СТРУКТУРА СЕТЕЙ ЭВМ

1.1 Понятие логической структуры сетей ЭВМ

1.2 Эталонная модель В ОС

1.3 Протоколы и сервис.

1.3.1 Понятие протокола

1.3.2 Архитектурные модели протокола

1.3.3 Понятие сервиса

1.3.4 Структура протокола.

1.3.5 Примеры простейших протоколов и сервисов

1.3.6 Свойства протоколов.
1.4 Принципы разработки логической структуры ИВС.
1.4.1 Общие принципы разработки
1.4.2 Принцип неделимости логической структуры
1.4.3 Принцип композициональности проектирования
1.4.4 Принцип единой формальной основы
1.5 Состояние теории протоколов
1.5.1 Конечные автоматы и протоколы.
1.5.2 Средства формального описания и .
1.5.3 Сети Петри и протоколы
1.6 Выводы по главе
2 СЕТИ ПЕТРИ
2.1 Сети Петри.
2.1.1 Сети.
2.1.2 Маркировка сетей. Правила функционирования
2.1.3 Пометка. Бисимуляционная эквивалентность .
2.2 Предикатные сети.
2.2.1 Формальное определение Предикатных сетей .
2.2.2 Графическая форма Предикатныхсетей
2.2.3 Правила функционирования Предикатныхсетей.
2.2.4 Пометка Предикатныхсетей
2.2.5 Трансформация Предикатныхсетей в сети Петри.
2.3 Протоколы и сети Петри.
2.4 Библиографические замечания
3 ТОЧКИ ДОСТУПА. БАЗОВОЕ ИСЧИСЛЕНИЕ СЕТЕЙ
3.1 Точки доступа к сети Петри.
3.2 Вспомогательные операции над сетями
3.2.1 Операция слияния переходов.
3.2.2 Операция слияния мест
3.2.3 Трансформации точек доступа
3.2.4 Свойства операции эслияния сетей
3.3 Исчисление ТДсетей
3.3.1 Понятие ТДсети
3.3.2 Определение операций над ТДсегями
3.3.3 Иптуитивный смысл операций над объектами
3.4 О полноте исчисления ТДсетей.
3.5 Выводы по Главе
4 УРОВЕНЬ СИСТЕМЫ ИСЧИСЛЕНИЕ ПРОТОКОЛЬНЫХ ОБЪЕКТОВ
4.1 Определение объекта
4.2 Нормальные формы объекта
4.3 Операции над объектами
4.4 Эквивалентность объектов
4.5 Интерпретация объектов
4.5.1 Спецификация сервиса. Среда передачи
4.5.2 Объект таймера
4.5.3 Протокольный объект.
4.5.4 Спецификация протоколов и уровней логической структуры
4.5.5 Анализ и верификация протоколов
4.5.6 Иерархическая композиция протоколов.
4.6 Выводы по Главе
5 УРОВЕНЬ ОБЪЕКТОВ. ИСЧИСЛЕНИЕ ПРОТОКОЛЬНЫХ ПРОЦЕДУР
5.1 Понятие протокольной процедуры
5.2 Правила композиции протокольных процедур
5.3 Корректность правил композиции.
5.4 Выводы по Главе .
6 УРОВЕНЬ ПРОЦЕДУР
6.1 Спецификация протокольных процедур.
6.2 Верификация протокольных процедур
6.2.1 Проверка помеченных сетей Петри на бисимуляционную эквивалентность.
6.2.2 Построение сокращенного графа достижимости
6.2.3 Распределенная бисимуляционпая эквивалентность
6.3 Использование протокольных процедур, выраженных в других
формализмах
6.4 Выводы по главе
7 АВТОМАТИЗИРОВАННАЯ СИСТЕМА РАЗРАБОТКИ ПРОТОКОЛОВ
7.1 Назначение и область применения АСРП.
7.2 Архитектура АСРП.
7.3 Подсистема базового редактора
7.3.1 Термины графичссого интерфейса с пользователем.
7.3.2 Инструментальная Панель Базового редактора.
7.3.3 Меню Базового редактора
7.4 Подсистема алгебраического режима редактирования АСРП. . . .
7.5 Подсистема архитектурного редак тора.
7.5.1 Инструментальная Панель Архитектурного редактора . . .
7.6 Подсистема анализа свойств сети
7.6.1 Реализация алгоритма построения дерева достижимости. .
7.6.2 Реализация алгоритма проверки на биссимуляционную эквивалентность.
7.7 Подсистема визуализации функционирования сети
7.8 Пример спецификация протокола.
8 РАЗРАБОТКА ЛОГИЧЕСКОЙ СТРУКТУРЫ КОММУНИКАЦИОННЫХ СИСТЕМ
8.1 Разработка логической структуры процессора передачи данных .
8.1.1 Архитектура АСПД
8.1.2 Структура ЦКС. Подсистема передачи данных
8.1.3 Логическая структура ППД
8.1.4 Сервис передачи сообщений
8.1.5 Объектмаршрутизатор
8.1.6 Объект протокола ВМО.
8.1.7 Объект протокола
8.1.8 Спецификация ПИЛ с использованием АСРП
8.2 Разработка транспортного уровня ИВ С
8.2.1 Структура транспортного уровня.
8.2.2 Транспортный сервис
8.2.3 Локальный сетевой сервис.
8.2.4 Транспортный объект
8.3 Выводы по главе.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Так, например, транспортный протокол И СО [8] описывается как множество протокольных процедур, которые в различном составе объединяются в пять версий (классов) протокола. В этом разделе приводятся описания нескольких простейших протоколов, которые в дальнейшем будут использоваться на протяжении всей работы для иллюстративных целей. Эти примеры, с одной стороны, достаточно просты для понимания, а, с другой стороны, все еще достаточно информативны для демонстрации вводимых методов. При описании протоколов будет использоваться потация сетей Петри. Простейший протокол передачи (Тоу-протокол). На рис. Петри, описывающая модель простейшего протокола передачи данных через надежную среду передачи данных. Этот протокол, использующийся в иллюстративных целях в ранних работах, посвященных описанию и анализу протоколов [7], является более чем тривиальным, но служит основой для описания более сложных протоколов. Тоу-протокол описан в рамках двухуровневой архитектурной модели. Он состоит из объекта-передатчика (места - St s2, $з> переходы - tlf t2, *з)> объекта-приемника (s4, s5, , <4, ^5, <6) и среды передачи данных (, s8). Срабатыванию перехода t передатчика соответствует получение сервисного блока данных DatReq от пользователя, предназначенного для удаленного пользователя. После этого передатчик передает протокольный блок -DT в среду передачи (срабатывает переход t2), а сам переходит в состояние ожидания подтверждения (метка помещается в место $2). После этого приемник может принять этот блок данных +DT (срабатывает переход <4), после чего он передает подтверждение об успешном приеме (переход <5). Далее приемник передает полученный блок пользователю, используя примитив Datlnd (переход t6) и переходит в исходное состояние (метка в месте S5). После этого передатчик получает подтверждение +АК (переход ^з) и также возвращается в начальное состояние (метка в месте ). После этого д протокол может продолжить свое функционирование сначала. Тоу-протокол с повторной передачей (Тоуй-протокол). Рис. Для коррекции обнаружения и коррекции таких ошибок в протоколы вводятся дополнительные механизмы. На рис. Здесь дополнительные переходы /7 и tg моделируют потерю средой блоков данных и подтверждений, соответственно. Дополнительный переход ? Предполагается, что механизм повторной передачи включается в случае, когда передатчик решил, что данные не дошли до приемника. Обычно для принятия такого решения используется механизм таймаутов, который, однако, в данном описании явно не специфицирован. Протокол альтернативного бита (АВ-протокол). I см. АВ-протокол не является практически используемым. Одпако он является прототипом многих реальных протоколов, например, протокола передачи со скользящим окном. Рис. На рис. Петри, описывающая АВ-иротокол. Как и в предыдущем протоколах АВ-протокол имеет объекты передачи и передатчика. К каждому блоку данных и подтверждения приписывается дополнительная инфор-I мация, размером в один бит, который может принимать два значения “0” и “1”. Передатчик, посылая блоки данных попеременно чередует значение этого бита нулем и единицей, таким образом идентифицируя данные. Послав данные, передатчик ожидает подтверждение на него с тем же значением бита. Приемник также чередует значение бита ожидаемого блока данных. Получив же данные с ожидаемым битом, он возвращает подтверждение с тем же зпачепием бита. Если же приемнику поступает блок данных со значением бита, отличным от ожидаемого, то этот блок считается ошибочным и игнорируется без изменения состояния. С другой стороны, если объект-передатчик получает подтверждение не с тем значением бита, то оно также считается ошибочным и игнорируется. Среда передачи, как и предыдущем протоколе, может терять сообщения, для чего также вводится механизм повторной передачи. Простейший сервис передачи данных. Все три предыдущие протокола, несмотря на свои различия, имеют целью обеспечить передачу блоков данных от одного пользователя к другому. Иными словами эти три протокола обеспечивают (или по крайней мере должны обеспечивать) один и тот же сервис передачи * данных. На рис. Петри, описывающая этот сервис.