МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МАРШРУТИЗАЦИИ
ПАКЕТОВ В ГЛОБАЛЬНОЙ ИНФОРМАЦИОННОЙ СЕТИ
Денисов Е.А.
(г. Москва,
МГТУ «Станкин», Россия)
Анализ эффективности функционирования глобальной вычислительной сети невозможен без сравнительной оценки применяемых методов маршрутизации. В качестве конечного уровня детализации модели маршрутизации логично рассматривать устройства маршрутизации и соединяющие их каналы передачи информации.
Основные параметры модели маршрутизации.
1. Типы информационных потоков (пользовательский или служебный, значение приоритета передачи, размер одной единицы информации, максимальное время жизни пакета).
2. Параметры каналов связи (тип канала, скорость и задержка передачи пакетов, вероятность сбоя при передаче пакета на единичной длины, размер служебной части пакета).
3. Параметры сегментов сети (распределения времени генерации пакетов и количества информационных единиц в одном пакете).
4. Используемые методы управления объемом информационных потоков (управление объемом поступающих и транзитных потоков, управление началом сеанса связи, управление объемом потоков на линиях связи).
5. Используемый метод маршрутизации (тип метода, метрические параметры, интервалы времени: действия маршрутов, проверки маршрутизатором своих соседей, синхронизации маршрутных матриц, распределения скорости и задержки обработки информации различных типов).
Архитектура любой имитационной модели может быть разложена на две отдельные составляющие: структурную и поведенческую.
В качестве структурного компонента построенной модели была выбрана открытая сеть массового обслуживания (СеМО, см рис. 1-4).
Рис. 1. Фрагмент СеМО, соответствующий симплексному каналу связи
Рис. 2. Фрагмент СеМО, соответствующий полудуплексному каналу связи
Рис. 3. Фрагмент СеМО,
соответствующий дуплексному каналу связи
Рис. 4. Фрагмент СеМО, соответствующий устройству маршрутизации
· ОП, ОП1, ОП2 – обслуживающие приборы;
· R1, R2 – устройства маршрутизации;
· B и B* – успешное и неуспешное окончание передачи пакета;
· RU и RPi – функциональный блок и порты устройства маршрутизации.
Основными поведенческими подпроцессами в работе сети являются передача пакетов и изменение маршрутных матриц.
В соответствии с распределениями времен генерации и длины абонентские пакеты каждого типа информационных потоков добавляются во входную очередь начального устройства маршрутизации. Маршрутизация пакетов происходит в порядке их приоритета по заданному закону распределения времени и состоит в задании пакету приоритетного списка направлений передачи. Далее пакет попадает в выходную очередь маршрутизатора и производится попытка приоритетной передачи в каналы связи всех находящихся в ней пакетов. Предварительно для каждого из них производится проверка истечения лимита времени нахождения в сети. Низкоприоритетные пакеты теряются при переполнении очередей.
При передаче пакета по каналу связи производится проверка на отсутствие ошибок. В случае возникновения искажений пакет передается обратно в выходную очередь маршрутизатора-отправителя. Если пакет передан нормально, то он попадает во входную очередь следующего маршрутизатора. Далее процесс повторяется до обработки пакета маршрутизатором, находящимся в одной локальной сети с абонентом-получателем.
Модель поддерживает три способа изменения матриц маршрутизации.
1. Служебные пакеты с подтверждением действия маршрутов (во всех маршрутных записях, полученных от данного маршрутизатора корректируется время генерации пакета).
2. Синхронная передача служебных пакетов с копиями текущих матриц маршрутизации (по схеме запрос-ответ).
3. Асинхронная передача служебных пакетов с копиями матриц маршрутизации в случае их изменения (по схеме уведомление-запрос-ответ).
Процесс передачи первого пакета начинается со входной очереди маршрутизатора-источника и заканчивается его обработкой на приемной стороне. Для способов 2 и 3 обработка служебных пакетов в маршрутизаторе-приемнике порождает генерацию и помещение в выходную очередь следующего пакета в цепочке.
Каждая запись маршрутной матрицы имеет следующие поля:
· номер адресуемой локальной сети;
· номер маршрутизатора-источника;
· номер порта-источника;
· время возникновения записи;
· значение метрики расстояния.
Построенная модель реализована в виде инструментального программного средства имитационного моделирования на основе метода статистических испытаний, объектно-ориентированной архитектуры и событийного принципа моделирования. В настоящее время в программе реализован метод двухуровневой иерархической маршрутизации одиночных пакетов с независимым применением синхронной и асинхронной модификаций методов простой дистанционно-векторной маршрутизации и рельефов.
Для данных методов маршрутизации модель позволяет получить за приемлемое время адекватные значения вероятностно-временных характеристик сетей с размерностью более 100 узлов. При увеличении количества узлов сети время моделирования имеет линейную зависимость от среднего количества устройств маршрутизации, проходимых одним пакетом.
Модель предоставляет возможность проводить анализ как стационарных, так и переходных состояний в процессе работы глобальной сети.
ЛИТЕРАТУРА
1. Олифер В.Г. Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб.: «Питер», 1999.
2. Обельченко С.Е. Разработка специальных систем связи. М.: ИПК РРиС, 1998.
3.
Климов Г.П.
Стохастические системы обслуживания. – М.: Наука, 1966.