Содержание к диссертации
Введение
1. Адаптивное распределение информационных потоков в корпоративных вычислительных сетях 10
1.1. Управление структурой сети 10
1.2. Управление одиночной маршрутизацией 17
1.3. Управление объемом информационных потоков 27
Выводы по первой главе 31
2. Методика комплексной оценки эффективности функционирования корпоративных сетей 32
2.1. Постановка задачи 32
2.2. Определение средних продолжительностей стационарных и переходных состояний в процессе работы корпоративной сети 34
2.3. Определение значения комплексной оценки эффективности работы корпоративной вычислительной сети 36
2.4. Основные этапы методики 38
Выводы по второй главе 41
3. Имитационная модель иерархической распределенной адаптивной маршрутизации в корпоративных вычислительных сетях 42
3.1. Основные параметры модели 42
3.2. Структура и поведение модели 45
Выводы по третьей главе 50
4. Программная реализация модели иерархической распределенной адаптивной маршрутизации 51
4.1. Укрупненная структура программы 51
4.2. Реализация алгоритмов моделирования 52
Выводы по четвертой главе
5. Анализ эффективности функционирования фрагментов корпоративных сетей 70
5.1. Моделирование стационарного состояния 70
5.2. Моделирование переходного состояния 81
5.3 Анализ вычислительных сетей различной структуры 87
Выводы по пятой главе 89
Заключение 91
Литература
- Управление одиночной маршрутизацией
- Определение средних продолжительностей стационарных и переходных состояний в процессе работы корпоративной сети
- Структура и поведение модели
- Реализация алгоритмов моделирования
Управление одиночной маршрутизацией
Для маршрутизации одиночных сообщений между постоянными абонентами корпоративных вычислительных сетей в настоящее время наибольшее распространение получил метод двухуровневой иерархической распределенной групповой маршрутизации. Перед описанием данного алгоритма рассмотрим классификацию одноуровневых методов.
Одноуровневые методы распределенной групповой маршрутизации разделяются на два подкласса по используемому принципу построения матрицы потокораспределения. К первому классу относятся методы дистанционно-векторной маршрутизации (ДВМ), ко второму - методы состояния связей.
Алгоритмы дистанционно-векторной маршрутизации позволяют использовать любые аддитивные метрики пути передачи сообщений. Матрица потокораспределения представляет собой вектор подсетей, в каждый элемент которого записываются метрика маршрута, минимальная по всем направлениям передачи сообщений, и номер данного направления. Поддерживается наличие нескольких маршрутов с различными метриками.
Модификация маршрутной информации осуществляется путем обмена сообщениями между соседними узлами сети. Периодичность данного процесса может быть задана как синхронно через некоторые интервалы времени, так и асинхронно при изменении состояния соседнего узла. Коррекция элементов матрицы потокораспределения осуществляется в следующих случаях: в результате обмена маршрутной информацией с узлом другого направления уменьшается метрика маршрута к данной подсети; в результате обмена маршрутной информацией с узлом текущего хранимого направления метрика маршрута к данной подсети увеличивается; узел по текущему хранимому направлению стал недоступным в течение определенного промежутка времени.
Дальнейшее развитие алгоритм дистанционно-векторной маршрутизации получил в так называемом методе рельефов. Основным отличием данного метода от алгоритма ДВМ является существование отдельных векторов расстояний до узлов-получателей для каждого направления маршрутизации. Метод рельефов включает в себя две процедуры. 1. Формирование рельефа при начальном запуске и расширении сети. 2. Периодическая коррекция рельефа в процессе функционирования сети. Под рельефом некоторого узла сети понимается совокупность расстояний до него от других узлов сети по всем возможным направлениям связи.
Рассмотрим процесс формирования рельефа на сети из N узлов. 1. Во всех узлах сети i=l ..N создается матрица R1 размера N х М;, где М; -число исходящих направлений узла с номером і. 2. Для каждого узла сети і заполняются элементы матриц R-m, где j=l..N, m=l..Mj по следующим правилам: формирование рельефа для узла і начинается с записи метрики в элемен ты R-m (1-ый рельеф) для всех узлов], непосредственно соединенных с исходным узлом і (rrij - номер связи узла], соединяющей его с узлом і); после формирования k-го рельефа узла і на узле j происходит формирование к+1-го рельефа на всех узлах, соединенных с j за исключением направления, с которого был получен k-ый рельеф; формирование к+1-го рельефа узла і не выполняется в случае, если один из элементов вектора R- содержит метрику, меньшую чем текущая записываемая метрика k-го рельефа. Выполнение коррекции маршрутной матрицы осуществляется по методу ДВМ. Информацией, передаваемой между соседними узлами сети, являются текущие столбцы минимальных метрик для каждого узла і: Rj =minR 1 .і, 1,J ,где: j, =l..Mi,j2 =l..Mi,...jN=l..Mi. R N = min R j JN Поиск оптимального пути между двумя узлами і, и і2 состоит в попытке установления соединения по таким направлениям в і, и всех промежуточных узлах, которым в строках № і2 матриц соответствуют минимальные метрики.
Дистанционно-векторные алгоритмы имеют два основных недостатка: низкая скорость адаптации к изменениям состояния сети; возможность зацикливания маршрутов. Преимуществом данного класса методов является возможность охвата крупной сети, количество узлов и маршрутных метрик в которой превышает способности маршрутизаторов хранить полную информацию о ее состоянии. Метод состояния связей (распределенный матричный метод) [7] [8] принадлежит к асинхронным методам маршрутизации и базируется на алгоритме кратчайшего пути Дейкстры [9].
При использовании метода состояния связей вся сеть подразделяется на отдельные, возможно пересекающиеся, области. Граничные маршрутизаторы областей также образуют так называемую центральную область. Принцип работы метода основан на поддержании единого графа состояния сети области на всех устройствах маршрутизации, принадлежащих ей. Метод включает в себя три процедуры. 1. Получение маршрутизатором информации о своих соседях в области. 2. Периодический обмен информацией о графе состояний. 3. Построение дерева кратчайших расстояний. Первый обмен информацией о соседях происходит при подключении устройства маршрутизации к сети. Для подтверждения работоспособности соседей процесс обмена повторяется через определенные промежутки времени.
Обмен информацией о графе состояний сети между соседними узлами происходит следующим образом. Каждое устройство маршрутизации поддерживает две матрицы смежности. Постоянная матрица смежности предназначена для хранения запланированной структуры сети области и корректируется только при изменении данного плана.
Определение средних продолжительностей стационарных и переходных состояний в процессе работы корпоративной сети
Во второй главе диссертации разработана методика комплексной оценки эффективности функционирования корпоративных вычислительных сетей. Для получения статистик времен передачи отдельных сообщений и количеств содержащейся в них информации необходимо построить имитационную модель функционирования корпоративной сети.
В данной главе будет создана имитационная модель функционирования методов иерархической распределенной адаптивной групповой маршрутизации одиночных сообщений в одном состоянии КВСе.
В качестве конечного уровня детализации модели выбрана глобальная часть центральной сети корпорации. При этом модель является открытой, т.е. получаемые значения Del. . . могут быть использованы вместе .ЧИ J2 h) ki,s(ji ,J2 ,h) со значениями данной характеристики на остальных участках пути абонент-абонент для получения интегральных значений. В случае если путь от абонента до глобальной части ЦСК единственен (т.е. маршрутизация фактически отсутствует), то для нахождения недостающих времен передачи могут быть использованы математические модели канальных протоколов [20-23].
Определим основные параметры модели (см. раздел 2.4, пп. 1 и 2 алгоритма нахождения значения комплексной оценки эффективности функционирования корпоративной вычислительной сети). 1. Типы информационных потоков подразделяются на два класса: потоки информации на сегментах сети; потоки служебной информации протоколов маршрутизации. Базовыми параметрами потоков каждого типа являются: размер одной информационной единицы; значение приоритета сообщений. 2. Структура корпоративной сети представляет собой связный мульти граф, вершинами которого являются устройства маршрутизации, а ребра ми - глобальные каналы связи. Каждый канал связи имеет следующие основные параметры [6]: тип канала (симплексный, полудуплексный, дуплексный); скорость передачи информации; задержка передачи информации; вероятность сбоя при передаче на единицу длины сообщения. 3. Протоколы передачи данных добавляют дополнительный параметр для типов информационных потоков: максимальное время жизни для сообщений данного типа. Также дополнительными параметрами для каналов связи являются: длина контрольной суммы; общая длина служебной части сообщения. 4. Отдельный сетевой сегмент образуется парой абонентов, каждый из ко торых подключен к одной из локальных сетей, типом потока сообщений и направлением передачи. Параметры сегментов сети: распределение времени генерации сообщений; распределение количества информационных единиц в одном сообщении. Наиболее распространенными распределениями времени между последовательным появлением двух соседних сообщений у абонента вычислительной сети являются [11][24]: потоки Пуассона; потоки Эрланга; потоки Бернулли; регулярные потоки (обычно при передаче служебной информации). К основным распределениям длины сообщений относятся: равномерное распределение; распределение Пуассона; биномиальное распределение. 5. Используемые методы АРИП.
Т.к. модель определяет работу корпоративной сети в единичном состоянии, то методы управления структурой сети в ней не реализованы. Методы управления объемом информационных потоков: в качестве методов управления объемом поступающих потоков в модели использовано константное ограничение длин входных и выходных очередей устройств маршрутизации; реализацией методов управления объемом транзитных потоков [14] является обслуживание поступающих сообщений по дисциплине с относительным приоритетом (по значению соответствующего параметра для информационных потоков различного типа); методы управления началом сеанса связи не реализованы; методы управления объемом потоков на линиях связи не реализованы. На параметрах методов управления маршрутизацией остановимся более подробно. Модель включает в себя реализацию методов иерархической распределенной адаптивной маршрутизации (см. раздел 1.2): на верхнем уровне все узлы сети по использованию алгоритма внешней маршрутизации разделяются на множество непересекающихся округов; по использованию алгоритма внутренней маршрутизации узлы также разделяются на множество непересекающихся зон; в случае использования в некоторой зоне алгоритмов маршрутизации по состоянию связей она также может быть разделена на отдельные частично пересекающиеся регионы.
Таким образом, каждый узел сети характеризуется: параметрами округа (внешней маршрутизации); параметрами зоны (внутренней маршрутизации); параметрами всех регионов , к которым принадлежит данная вершина. - параметр может отсутствовать. Округ, зона или регион имеют следующие параметры: метод маршрутизации (синхронный или асинхронный метод ДВМ, синхронный или асинхронный метод рельефов, метод состояния связей); метрические параметры метода; интервал времени действия маршрутов; интервал времени проверки маршрутизатором своих соседей; интервал времени между двумя синхронизациями маршрутных матриц (для синхронных методов); распределения скорости маршрутизации различных типов информации; распределения задержки маршрутизации различных типов информации; распределение скорости обработки служебной информации; распределение задержки обработки служебной информации.
Структурная схема соединения элементов ВСе Архитектура имитационных моделей может быть разложена на две отдельные составляющие: структурную и поведенческую [25]. Рассмотрим формальную структурную схему соединения устройств маршрутизации и каналов связи в вычислительных сетях (см. рис. 3.1), где: RP - порт маршрутизатора; RU - функциональный блок маршрутизатора; AS - абонентские станции.
Порты маршрутизаторов RP представляют собой структуру из двух очередей для входящих и выходящих сообщений подключенного канала связи. Совокупность очередей входящих сообщений всех портов одного устройства составляет входную очередь к соответствующему блоку RU, аналогично очереди выходящих сообщений каждого порта RP подключены к его выходу.
Блок RU объединяет в себе внешний источник потока служебных сообщений и непосредственно структурный элемент маршрутизации, выполняющий обработку всех входящих сообщений по некоторому заданному закону распределения времени (см. раздел 3.1, параметры округов, зон и регионов). Таким образом, структура разрабатываемой модели представляет собой открытую сеть массового обслуживания (СеМО) [14][26]. Построим фрагменты СеМО, соответствующие каналам связи и устройствам маршрутизации (см. рис. 3.2-3.5).
Структура и поведение модели
В каждом случае было проведено 7 экспериментов, равномерно распределенных на отрезке значений интенсивности [0; 0,09].
Оценим с уровнем а= 0,95 доверительные интервалы [31] для полученных зависимостей. Минимальное количество сгенерированных абонентских сообщений для используемого распределения (экспоненциальный поток) составляет ninf «At - 1,96л/At, где А -суммарная по всем сегментам интенсивность сообщений (А = Хк ), a t = 200 с (при условии At 9). Таким образом, для суммарной интенсивности абонентского сегмента при X 10 ninf 6,7 10 X. Доверительный интервал для вероятности потери сообщения р, может быть вычислен по формуле 1,96 II р исходя из свойств биномиального распределения, т.к. при X 10 n-nfp(l - р) 25 . Итоговое значение составляет не более 1,5 10-2 (при X = 0,05 оно « 0,01). Для оценки доверительных интервалов коэффициентов загрузки элементов сети также можно применить биномиальную схему. В качестве элементарных событий выберем состояние обслуживающего прибора через равные промежутки времени. При этом длина интервала в общем случае должна превосходить максимальное с заданным уровнем доверия время обслуживания сообщения (для рассматриваемого примера время обслуживания задано регулярным распределением, однако в программе моделирования предусмотрено задание других типов непрерывных распределений, см. гл. 4).
Для устройств маршрутизации минимальная длина интервала составляет 2050 байт/10 байт/с = 0,2 с. Для линий связи ее значение составляет 2050 байт/(1,25 10 байт/с) = 0,2 с. Таким образом, количество испытаний в схеме Бернулли можно взять равным 200 с/0,2 с =1000. Для уровня доверия а = 0,95 и коэффициента загрузки р = 0,05 доверительный интервал «0,01; для р = 0,5 он приближенно составляет 0,03.
Полученные результаты показывают, что при заданных параметрах моделирования наиболее эффективным по количеству успешно переданных сообщений является метод ДВМ, причем его синхронная модификация обеспечивает более низкую загрузку устройств маршрутизации и линий связи. В целом, синхронные методы являются более эффективными как по критерию потерь, так и по критерию загрузки элементов сети.
Исходя из количества потерь при средних коэффициентах загрузки наиболее используемых элементов сети можно сделать вывод о недостаточности значения лимита времени для пребывания в сети сообщений с низкими значениями приоритета.
Для каждого из трех типов потоков были построены зависимости значений функций IEf (h) от интенсивности X (см. рис. 5.12-5.15), сравнительный анализ которых также подтверждает сделанные выводы. Асинхронный ДВМ
Сеть регулярной топологии типа "эллипсоид1 Моделирование переходного состояния работы КВСе проиллюстрируем на примере сети регулярной топологии типа "эллипсоид" (см. рис. 5.17). Более жирными на рисунке выделены линии внутризоновой связи (т. о. сеть разделена на 6 зон). Значения параметров моделирования: модель сетевого фрагмента состоит из 18 узлов и 36 линий связи; линии связи представляют полудуплексные каналы; размер служебной части сообщений - 50 байт; скорость передачи информации в сети - 0,8 Мбит/с, задержка - 10" с; помехи на линиях связи отсутствуют; максимальное время нахождения сообщений в сети - 5 с; моделируется однонаправленная приоритетная передача 3 потоков абонентских сообщений с одинаковыми параметрами от одной "концевой" вершины ("полюса") сети к другой; размер информационной части сообщения имеет дискретное равномерное распределение от 1000 до 2000 байт; время генерации абонентских сообщений для каждого потока имеет экспоненциальное распределение с интенсивностью 20 сообщений/с; максимальный размер входной и выходной очередей устройств маршрутизации и входной очереди в локальной сети равен 100 сообщениям; скорости маршрутизации составляют 0,8 Мбит/с, задержки - 10" с; время действия маршрутов изменяется в процессе моделирования; интервал опроса соседей (в асинхронных методах) и интервал синхронизации (в синхронных методах) - равен 1/5 времени действия маршрутов; моделируется отказ устройства маршрутизации №6 (нумерация ведется по направлению от "полюса"-источника к "полюсу"-приемнику); для внутризоновой маршрутизации используются методы ДВМ, для межзоновой - методы рельефов.
Введем обозначение для используемых комбинаций межзонового и внутризонового методов маршрутизации: хРуД, где х и у принимают значения А и С, соответствующие их асинхронной и синхронной реализациям. Таким образом, моделируется следующие методы: АР АД, АРСД, СРАД, СРСД. Время моделирования = 50 с
Для заданных выше параметров функционирования сети максимальная нагрузка в стационарном состоянии без потерь сообщений достигается при времени действия маршрутов «5с (метод СРСД). На рис. 5.18-5.20 приведены зависимости отношения IEPisCJ -h щ при Kj = 0,К2 = 1 к общему количеству сообщений, переданных по сегменту (физический смысл - среднее время доставки одного байта) для четырех методов маршрутизации.
На рис. 5.21 приведены зависимости составляющей потерянных сообщений IEP;s(j , J в переходном состоянии (К, = 1,К2 = 0), т.е. количества потерянных байт информации для различных методов маршрутизации. Из полученного графика по критерию знаков с уровнем доверия а = 0,99 по 11 испытаниям нельзя отвергнуть гипотезы о том, что метод СРАД является более лучшим, чем каждый из остальных методов.
На рис. 5.22 для данного метода маршрутизации построены зависимости долей теряемой информации каждого приоритета. Из гистограммы можно сделать заключение о равномерном характере потерь.
Реализация алгоритмов моделирования
Метод запуска процесса моделирования производит первичную генерацию событий xTRANSFERMATRIX для всех уровней иерархии маршрутизации, реализованных на текущем устройстве. Для каждого из асинхронных методов также производится генерация событий xHELLO.
Метод обработки одиночного события, как и в классе CReliability, осуществляет передачу событий конкретным функциям обработки.
Опишем реализацию собственных функций класса.
Функция генерации сообщений ICxCHANGED реализует заключительные части рассмотренных выше синхронных и асинхронных алгоритмов маршрутизации (начиная со сброса признака изменения маршрутных матриц).
Функция генерации рассылок сообщений по текущему обрабатываемому служебному сообщению (ICxHELLO, ICxCHANGED и ICxGETMATRIX), сгенерированному на данном устройстве маршрутизации, производит добавление его копий (по одной на каждый используемый на данном уровне иерархии маршрутизации порт) в очередь выходящих сообщений.
Функция обработки сообщений реализует следующий алгоритм. 1. Определяется номер входного порта устройства. 2. По номеру порта находится уровень иерархии, на котором осуществляется маршрутизация сообщения. 3. Определяется тип сообщения. 4. По уровню иерархии и типу сообщения находятся временные параметры его обработки (в соответствующем объекте класса CZone). 5. По найденному закону распределения времени (маршрутизации абонентского сообщения или обработки служебного) генерируется событие FREE. Функции передачи сообщений в линию связи осуществляют передачу служебных сообщений и маршрутизацию абонентских другим устройствам сети. Основная функция осуществляет последовательную попытку передачи всех сообщений из выходной очереди в порядке их приоритета. Непосредственно попытка передачи реализована второй функцией.
1. Осуществляется проверка времени нахождения сообщения в сети. В случае превышения лимита вызывается функция окончания маршрутизации класса CMessage с соответствующим параметром.
2. В случае, если сообщение является служебным, вызывается третья функция непосредственной передачи сообщения в заданный порт. Возвращаемое ей значение передается основной функции.
3. Если сообщение является пользовательским, то создается список доступных направлений по всем уровням иерархии маршрутизации. Список упорядочивается по величине метрики. Далее осуществляется последовательный перебор направлений с передачей каждого в третью функцию. Перебор осуществляется до первой успешной попытки передачи. Третья функция осуществляет следующие действия. 1. В случае занятости порта (см. соответствующее данное) возвращается ответ о невозможности пересылки. 2. Признак занятости порта устанавливается в истинное значение. 3. В сообщении устанавливаются номера исходного (текущее) и результирующего устройств маршрутизации. 4. Генерируется событие NEWMESSAGE для соответствующей линии связи. 5. Функция возвращает ответ об успешной передаче сообщения в порт. Рассмотрим обработчики событий класса CRouter. Класс обрабатывает все типы событий программы, исключая событие USERMESSAGE. Обработчик события FAILURE выполняет следующие действия: 1. Вызов соответствующей функции базового класса. 2. Удаление из очереди события FREE для текущего устройства. 3. Вызов методов сброса сообщений для входной и выходной очередей. 4. Вызов функции окончания маршрутизации текущего обрабатываемого сообщения (с параметром отказа устройства).
Обработчик события RECOVERY осуществляет прямой вызов аналогичной функции базового класса.
Обработчики событий xHELLO выполняют асинхронную часть алгоритмов маршрутизации (см. выше описание синхронных и асинхронных алгоритмов). Обработчики событий xTRANSFERMATRIX выполняют синхронную часть алгоритмов маршрутизации. Для генерации сообщений 1Сх-CHANGED используется вызов соответствующей функции класса.
Обработчик события ENGAGEPORTS устанавливает признак занятости порта по номеру линии связи. Обработчик события FREEPORTS выполняет обратную операцию и для данного порта устанавливает признаки состояния на каждом уровне иерархии (см. данные класса CZone) в значение исправен. В случае, если устройство маршрутизации находится в рабочем состоянии (см. данные класса CReliability), вызывается основная функция передачи сообщений из выходной очереди в линию связи.
Обработчик события NEWMESSAGE осуществляет следующие действия: 1. В случае нахождения маршрутизатора в нерабочем состоянии для поступающего сообщения вызывается функция окончания маршрутизации и алгоритм завершает работу. 2. В сообщении устанавливается номер входного порта. 3. Сообщение вносится в очередь входящих сообщений. 4. Вызывается функция обработки сообщений. Обработчик события BACKMESSAGE выполняет п. 1 предыдущего алгоритма, вносит сообщение в очередь выходящих сообщений и вызывает основную функцию передачи сообщений в линию связи. Одной из главных функций класса CRouter является метод обработки события FREE. Рассмотрим его реализацию. 1. В случае, если для обрабатываемого сообщения не определен номер порта (сообщение сгенерировано на текущем устройстве, кроме сообщений ICxTMATRIX), вызывается функция генерации рассылок служебных сообщений. В противном случае определяется класс сообщения. 2. Для сообщений ICUSERMESSAGE, направляемых в присоединенные к устройству линии связи, устанавливается соответствующий порт. Далее все сообщения данного типа добавляются в выходную очередь. 3. Обработка сообщений ICxHELLO заключается в вызове на соответствующем уровне иерархии маршрутизации функции обновления времени записей в маршрутной матрице (см. методы класса CZone). 4. Сообщения ICxTMATRIX обрабатываются путем вызова функции обновления маршрутной матрицы соответствующего уровня. Если возвращаемое ей значение является истинным, то устанавливается признак изменения маршрутных матриц (данное класса CRouter). 5. По сообщению ICxCHANGED генерируется ответное (не широковещательное) сообщение ICxGETMATRIX. 6. При поступлении сообщения ICxGETMATRIX создается объединенная по всем уровням иерархии маршрутная матрица. В случае использования на х-уровне методов простой ДВМ (не метода рельефов) из матрицы удаляются лишние записи по принципу наименьшей метрики. Далее полученная матрица пересылается в ответном сообщении ICxTMATRIX. 7. Во втором этапе алгоритма, после выполнения одного из пунктов 1-6, выполняется очистка текущего сообщения и последовательный вызов функций обработки сообщений и передачи сообщений в линию связи.
