Содержание к диссертации
Введение
Глава 1 - Анализ существующих протоколов маршрутизации и алгоритмов управления трафиком в IP - сетях 11
1.1. Маршрутизация и ее место в семиуровневой модели OSI 12
1.2. Маршрутизация в стеке протоколов TCP/IP 17
1.3. Протоколы и алгоритмы маршрутизации 19
1.4. Таблица маршрутизации. Метрика 26
1.5. Маршрутизация как процесс управления 32
Выводы 35
Глава 2, Алгоритмы многофакторного управления с нечеткими множествами 37
2.1. Теории нечетких множеств, Операции над нечеткими множествами 39
2.2. Лингвистические переменные и логический вывод с нечеткими множествами 48
2.3. Особенности моделирования телекоммуникационных систем с помощью нечеткой логики 55
Выводы 59
Глава 3. Модели систем управления маршрутизацией с использованием нечетких множеств в компьютерных сетях 60
3.1. Используемая модель маршрутизатора 61
3.2. Моделирование маршрутизации в рамках протокола ШР 64
3.3- Моделирование маршрутизатора в рамках протокола IGRP 74
3.3.1. Аппроксимация метрики протокола TGRP нечеткими множествами 75
3.3.2. Управление трафиком на основе загруженности буфера в рамках протокола IGRP 81
3.4. Оценка эффективности метода маршрутизации с нечеткими множествами 86
3.5. Анализ эффективности алгоритма маршрутизации с помощью имитационного моделирования 90
3.6. Реализация системы управления с нечеткими множествами на базе протокола SNMP 97
Выводы 103
Заключение 104
Список используемой литературы 105
- Протоколы и алгоритмы маршрутизации
- Лингвистические переменные и логический вывод с нечеткими множествами
- Моделирование маршрутизации в рамках протокола ШР
- Анализ эффективности алгоритма маршрутизации с помощью имитационного моделирования
Введение к работе
На сегодняшний день большинство компьютеров объединены в различные информационно-вычислительные сети от малых локальных в офисах до глобальных типа Internet. Всемирная тенденция к объединению компьютеров в сети обусловлена рядом важных причин, таких как ускорение передачи информационных сообщений, возможность быстрого обмена информацией между пользователями, получение и передача сообщений не отходя от рабочего места, возможность мгновенного получения любой информации из любой точки земного шара, а так же обмен информацией между компьютерами разных фирм, работающих под разным программным обеспечением [29].
Большинство компьютерных сетей являются составными. Составными сетями называются сети, которые могут быть представлены в виде нескольких локальных сетей, объединенных между собой с помощью коммуникационного оборудования. В компьютерных сетях несколько локальных сетей (ЛВС) объединяются между собой с помощью маршрутизаторов.
Современные компьютерные сети строятся с использованием пакетной технологии передачи информации с дальнейшей маршрутизацией пакетов между ЛВС [48]. Так как маршрутизация каждого пакета происходит независимо, решение задач маршрутизации приобретает первостепенную важность. Таким образом, маршрутизация пакетов является краеугольной задачей всей технологии IP.
Актуальность темы
Развитие компьютерных сетей выявляет тенденцию усложнения их топологии. Эта тенденция ведет ко все возрастающей значимости задачи маршрутизации, так как качество решения этой задачи напрямую влияет на производительность и эффективность использования сети в целом.
Маршрутизацией называется выбор наиболее рационального пути передачи информации, а её решение является одной из главных задач
сетевого уровня. Эта проблема осложняется тем, что самый короткий путь не всегда самый лучший [33], Часто критерием при выборе маршрута является время передачи данных, которое зависит от многих факторов, например, пропускной способности каналов и интенсивности трафика, которая в свою очередь может изменяться с течением времени. Выбор маршрута может осуществляться и по другим критериям (надёжности передачи, ширина полосы пропускания канала, загрузка интерфейсного буфера и т.п.)*
Таким образом, сложность проблемы маршрутизации заключается в ее многофакторности [27]. Каким образом привести в единство и соответствие критерии учета факторов для того, чтобы объективно выбрать лучший маршрут? Учет множества факторов сводит задачу маршрутизации к задаче оптимального распределения ресурсов сети. Проблема оптимального распределения ресурсов - вечная проблема, данный класс задач характеризуется не одним, а целым множеством решений, отсюда -неоднозначность решения задачи оптимального распределения ресурсов.
По словам Хизер Остерлох (Heather Osterloh), «...без маршрутизации и протоколов маршрутизации всемирный обмен информацией был бы невозможен» [36]. Усложнение компьютерных сетей ведет к усложнению используемых протоколов маршрутизации. Это в свою очередь ведет к появлению все новых и новых программных реализаций протоколов маршрутизации? которые осуществляют управление трафиком в компьютерных сетях.
Значительный вклад в изучение компьютерных сетей и проблемы маршрутизации внесли:
Postal, J. ("Internet Protocol" RFC 791,1981 [70]);
Mills, D.L. (RPC-891,1983 [67]; RFC-940,1985 [66]);
Hedrick, С ("Routing Information Protocol" RFC-1058,1988 [62]);
Waitzman, D., Partridge, C, Deering, S. (RFC-1075,1988 [79]);
Moy, J. ("The OSPF Specification" RFC-1131, 1989 [68]);
Callon, R. ("Use of OSIIS-IS for routing in TCP/IP and dual environments" RFC-1195,1990 [59]);
Rekhter, Y., Li, T. ("A Border Gateway Protocol 4 (BGP-4)" RFC-1771, 1995 [73]);
J, Parker, Ed. ("Recommendations for Interoperable IP Networks using Intermediate System to Intermediate System (IS-IS)" RFC-3787, 2004 [64]);
и многие другие. Наряду с зарубежными исследователями, теоретическую базу компьютерных сетей развивали и такие отечественные авторы как: Вишневский В- М [6], Олифер В. Г., Олифер Н. А. [34], Лагутин В. С. [25].
Как уже отмечалось выше, решение задачи маршрутизации связано с многофакторностью вопроса, что определяет сложность решения поставленной задачи: чем большее количество параметров учитывается, тем более громоздким становится алгоритм маршрутизации. Как преодолеть данное противоречие?
Перспективным является использование для решения задачи маршрутизации аппарата нечеткой логики (Fuzzy Logic). Данная технология позволяет с легкостью и простотой арифметики решать сложные задачи управления, которые характеризуются многофакторностью, нелинейностью и неоднозначностью связи параметров. Более детально технология Fuzzy Logic будет рассмотрена во второй главе диссертации. Неоценимый вклад в развитие данной области знаний внесли: Лотфи Заде (L. Zadeh [65]), Барт Коско (В, Kosco [57]), М. Сугено (М. Sugeno [44]) и другие.
Применение нечеткой логики к задачам телекоммуникаций описывается в статьях [80, 72, 71, 75] авторами: Y. Phillis, R. Zhang, С. Chang, S. Ghosh и др. А применению нечеткой логики к задачам маршрутизации посвящена работа [55] авторов: Runton Zhang и Keeping Long.
Цель работы: конструирование и исследование алгоритмов маршрутизации в IP-сетях с использованием технологии Fuzzy Logic.
8 Основные задачи исследования
анализ существующих алгоритмов управления трафиком в IP-сетях для определения критериев эффективности маршрутизации;
разработка модели функционирования маршрутизатора;
исследование возможности применения аппарата нечеткой логики для разработки алгоритма маршрутизации;
разработка алгоритма маршрутизации с элементами нечеткой логики;
оценка эффективности функционирования алгоритма маршрутизации с элементами нечеткой логики.
Объектом исследования служат протоколы маршрутизации, функционирующие в глобальные компьютерных сетях с маршрутизацией ІР-пакетов,
Предметом исследования является механизм управления трафиком в IP - сети через маршрутизацию пакетов,
Методы исследования
При выполнении данной работы использовались элементы теории нечетких множеств, теория управления, теория массового обслуживания, методы имитационного моделирования и теории вероятностей.
Научная новизна заключается в:
разработке модели маршрутизации, позволившей применить аппарат нечеткой логики к решению задачи определения метрики маршрутизации;
разработке методики построения метрики маршрутизации с использованием нечетких множеств;
разработке алгоритма маршрутизации с использованием нечетких множеств на основе предложенной методики;
разработке имитационной модели процесса маршрутизации, позволившей оценить эффективность работы предложенного алгоритма.
Достоверность результатов работы обеспечивается адекватностью использованных методов теории нечетких множеств, теории автоматического управления, имитационного моделирования и теории вероятностей. Достоверность положений и выводов работы подтверждается результатами имитационного моделирования.
Личный вклад: теоретические и практические исследования, проведенное имитационное моделирование на ЭВМ, а также выводы и рекомендации получены автором лично.
Практическая ценность работы:
разработанная методика построения метрики маршрутизации позволяет увеличить число учитываемых параметров;
разработанная методика конструирования метрики расширяет класс задач, решаемых средствами теории нечетких множеств;
разработанная в диссертации методика синтеза метрики маршрутизации обеспечивает создание алгоритмов маршрутизации с улучшенными характеристиками.
Реализация результатов работы.
Научные и практические результаты работы применяются в ООО НПЦ «Интернет ТВ», а также учтены при проектировании нового программного обеспечения компанией D-Link. Алгоритмические и программные средства, разработанные в рамках диссертации, используются в учебном процессе Поволжской Государственной Академии телекоммуникаций и информатики. Результаты диссертационной работы использованы в учебном процессе кафедры информационных систем и технологий Самарского государственного аэрокосмического университета имени академика СП. Королева,
Практическое использование результатов работы подтверждено соответствующими актами, приведенными в приложении к диссертационной работе.
10 Апробация работы.
Основные положения работы докладывались и обсуждались на V Международной научно-технической конференции "Проблемы техники и технологии телекоммуникаций", ПГАТИ (Самара, 2004); XII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, ПГАТИ, (Самара, 2005); XIII Юбилейной российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, ПГАТИ , (Самара, 2006); VII Международной научно-технической конференции "Проблемы техники и технологии телекоммуникаций1', ПГАТИ (Самара, 2006); V Международной научно-технической конференции "Информационно-вычислительные технологии и их приложения", РИО ПГСХА (Пенза, 2006).
Публикации.
По теме диссертации опубликовано 9 работ, в том числе две статьи в журналах из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных работ, 1 статья в сборнике международной научно-технической конференции и 6 тезисов докладов в материалах международных и всероссийских конференций.
Структура и объем работы.
Диссертационная работа состоит из введения, трех глав, заключения, списка источников и приложений. Основная часть работы содержит ПО страниц текста с 58 иллюстрациями и 11 таблиц. Список источников насчитывает 80 наименований. Общий объем работы с приложениями составляет 121 страниц.
Положения, выносимые на защиту;
модель маршрутизации, допускающая применение алгоритмов с нечеткими множествами для вычисления метрики;
методика построения метрики маршрутизации с использованием нечетких множеств;
алгоритм маршрутизации с использованием нечеткой логики;
имитационная модель процесса маршрутизации.
її Глава 1. Анализ существующих протоколов маршрутизации и алгоритмов управления трафиком в IP»сетах
Передача информации оо сети оеуодестшяетея с помощью пакетов. Пакет - базовая единица данных в компьютерной сеш [23]. Сообщение, пересылаемое uq сети, разбивается на пакеты, каждый їв которых снабжается адресом и другий сопутствующей информацией (і частности, годами проверки на наличие ошибок).
Самым популярным на сегодняшний деаь является стек протоколов TCP/IP [34].
TCP/IP IPX
NetBEUI
-Другие
Рис, 1,1, Доїш протоколов в общемировой инсталляционной сетевой
До 1996 года бесспорным лидером был стек IPX/SPX компании Novell» но даем картина резко изменилась - exes TCP/IP но темпам роста числа установок намного стал опережать другие стеки» ас 1998 года дошел в лидеры в абсолютном выражении [34].
1.1. Маршрутизация и ее место в семиуровневой модели OSI
Семейство протоколов TCP/IP работает на любых моделях компьютеров, произведенных различными производителями компьютерной техники и работающих под управлением различных операционных систем. С помощью протоколов TCP/IP можно объединить практически любые компьютеры, и что самое удивительное, сегодняшние реализации протокола TCP/IP очень далеки от того, как он задумывался исходно. В конце 60-х годов начался исследовательский проект, финансируемый правительством США, по разработке сети пакетной коммутации, а в 90-х годах результаты этих исследований превратились в наиболее широко используемую форму сетевого взаимодействия между компьютерами. В настоящее время это действительно открытая система, а именно, семейство протоколов и большое количество бесплатных реализаций (либо достаточно дешевых). Они в совокупности составляют основу того, что в настоящее время ассоциируется с общепринятым термином Internet [78].
Архитектура протоколов TCP/IP предназначена для объединенной сети, состоящей из соединенных друг с другом маршрутизаторами отдельных разнородных пакетных подсетей, к которым подключаются разнородные машины [49]. Каждая из подсетей работает в соответствии со своими специфическими требованиями и имеет свою природу средств связи. Однако предполагается, что каждая подсеть может принять пакет информации (данные с соответствующим сетевым заголовком) и доставить его по указанному адресу в этой конкретной подсети. Не требуется, чтобы подсеть гарантировала обязательную доставку пакетов и имела надежный сквозной протокол,
IP представляет собой технологию маршрутизации пакетов. Каждый пакет включает в себя управляющую информацию, идентифицирующую станцию назначения (компьютер, терминал, хост). Это означает, что каждый
13 пакет одного информационного потока обрабатывается (маршрутизируется) независимо от остальных [48]- Таким образом, маршрутизация в технологии IP становится основным фактором, влияющим на производительность и эффективность сети в целом.
Когда необходимо передать пакет между машинами, подключенными к разным подсетям, машина-отправитель посылает пакет соответствующему маршрутизатору (маршрутизатор подключен к подсети так же, как обычный узел). Оттуда пакет направляется по определенному маршруту через систему маршрутизаторов и подсетей, пока не достигнет маршрутизатора, подключенного к той же подсети, что и машина-получатель; там пакет направляется к получателю. Поскольку на процесс выбора дальнейшего маршрута влияет каждый маршрутизатор на пути следования пакета, связь между маршрутизацией и качеством работы всей сети в целом приобретает свойство многофакторности, сложности и нелинейности. Все это говорит о сложности решения поставленной задачи.
Хотя стек протоколов ТСРЯР изначально не был ориентирован на работу в среде взаимодействия открытых систем (ВОС), на сегодняшний день задача приспособления данного протокола для работы в среде ВОС практически решена. Таким образом, стек протоколов ТСРЯР представляет собой весьма гибкое, доступное и продуктивное средство объединения локальных подсетей в объединенную сеть, отвечающую современным нормам и требованиям построения открытых систем.
Проблема доставки пакетов в такой системе решается путем реализации во всех узлах и шлюзах межсетевого протокола IP- Межсетевой уровень является по существу базовым элементом во всей архитектуре протоколов, обеспечивая возможность стандартизации протоколов верхних уровней [24].
Сетевой уровень (Network Layer) служит для образования единой транспортной системы, объединяющей несколько сетей, причём эти сети могут использовать различные принципы передачи между конечными
14 узлами и обладать произвольной структурой связей. Функции сетевого уровня достаточно разнообразны.
Поскольку технологии, по которым построены объединяемые подсети, в общем случае весьма разнородны, задачи сетевого уровня распадаются на ряд подзадач :
функции ретрансляции и маршрутизации;
функции независимого от подсети совмещения (функции НПС);
функции зависимого от подсети совмещения (функции ЗПС);
функции доступа к подсети (функции ДП);
функции, выполняемые подсетями («услуги подсетей»)[52].
Следует особо подчеркнуть принадлежность функции маршрутизации
сетевому уровню модели OSI (модели ВОС). В большинстве других уровней
модели ВОС компоненты уровней содержатся только в оконечных системах
и взаимодействуют между собой строго попарно- Но сетевой уровень (СУ)
гораздо сложнее других уровней, поскольку содержит дополнительные
функциональные компоненты (каждая из которых поддерживается
компонентами канального и физического уровней), размещенные вне
оконечных систем (компьютеров, терминалов, хостов). К ним относятся
«ретрансляционные компоненты» промежуточных систем -(маршрутизаторов), а также функции, выполняемые в подсетях. Эти компоненты представлены на рис. 1.2, который изображает взаимосвязь систем ВОС через подсети [52],
На сетевом уровне сам термин сеть наделяют специфическим значением. В данном случае под сетью понимается совокупность компьютеров, соединенных между собой в соответствии с одной из стандартных топологий и использующих для передачи данных один из протоколов канального уровня, определённый для данной топологии.
Функции НПС
Функции НПС
Функции верхних уровней
Функции маршрутизации
Функции нездвисимого от подсети совмещения
Функции верхних уровней
Функции маршрутизации
Функции независимого от подсети совмещения
Функцій зависимого от подсети совмещения
Функции ЗПС
Функции ЗПС
Функции зависимого от подсети совмещения
Функции доступа к подсети
функции канального уровня
функция физического уровня
Оконечная система ВОС
Функции доступа к подсети
Функции канального уровня
Функции физического уровня
Функции доступа к подсети
Функции канального уровня
Функции физического уровня
Функции доступа к подсети
Функции капельного уровня
Функции (риэичвекого уровня
Оконечная система ВОС
Рис. 1.2, Взаимосвязь через подсети систем ВОС
Внутри подсети доставка данных обеспечивается соответствующим канальным уровнем, а доставкой данных между подсетями занимается сетевой уровень, который и поддерживает возможность правильного выбора маршрута передачи сообщения даже в том случае, когда структура связи между составляющими сетями имеет характер, отличный от принятого в протоколах канального уровня.
Маршрутизацией называется выбор наиболее рационального пути передачи информации, решение проблемы маршрутизации является одной из основных задач сетевого уровня [53]. Следует также отметить, что для технологии IP проблема выбора наилучшего пути (проблема маршрутизации) становится главенствующей. От того, как будут выбраны маршруты во многом будет зависеть производительность IP - сети.
Решение этой проблемы осложняется тем, что самый короткий путь не всегда самый лучший. Часто критерием при выборе маршрута является время передачи данных по этому маршруту, оно зависит от пропускной способности каналов связи и интенсивности трафика, которая может изменяться с течением времени. Некоторые алгоритмы маршрутизации пытаются приспособиться к изменению нагрузки, в то время как другие принимают решения на основе средних показателей за длительное время.
Выбор маршрута может осуществляться и по другим критериям, например надёжности передачи.
Классификацию конкретных функций по указанным группам не следует считать твердо установленной, поскольку она может зависеть от типа используемых подсетей. Например, в одном случае некоторая функция может привлекаться как часть услуг подсети, в другом же она может выполняться как функция НПС,
На рис. 1.3 представлена внутренняя архитектура сетевого уровня.
Компоненты верхних уровней
Компоненты верхних уровней
Компонента
транспортного
уровня оконечной
системы
Компонента сотового уровня
Ретрансляционная компонента сетевого уровня
Компонента
транспортного
уровня оконечной
системы
Компонента сетевого уровня
Компоненте канального уровня
| подсеть |
Компонента анального уровня
Компонента канального уровни
I подсеть J
Компонента канального уровни
Компонента физического уровня
Компонента физического уровня
Компонента физического уровня
Компонента физического уровня
Оконечная системе ВОС
Промежуточная система ВОС
Оконечная система ВОС
Рис. 1.3. Внутренняя архитектура сетевого уровня
В общем случае функции сетевого уровня шире, чем функции передачи сообщений по связям с нестандартной структурой. Сетевой уровень решает также задачи согласования разных технологий, упрощения адресации в крупных сетях и т. п. [34].
Сообщения сетевого уровня принято называть пакетами (packet, datagramm). При организации доставки пакетов на сетевом уровне используется понятие "номер сети". В этом случае адрес получателя состоит из старшей части - номера сети и младшей - номера узла в этой сети. Все узлы одной сети должны иметь одну и ту же старшую часть адреса, поэтому термину "сеть" на сетевом уровне можно дать и другое, более формальное определение; сеть - это совокупность узлов, сетевой адрес которых содержит один и тот же номер сети [35].
17 1.2. Маршрутизация в стеке протоколов TCP/IP
Так как стек TCP/IP был разработан до появления модели взаимодействия открытых систем ISO/OSI, то, хотя он также имеет многоуровневую структуру, соответствие уровней стека TCP/IP уровням модели OSI достаточно условно [34], С другой стороны разработчики модели OSI учли весь накопленный к тому времени опыт в построении сетей следовательно, модель OSI унаследовала часть полезных свойств и от модели протоколов TCP/IP, За годы совместного существования обе модели сблизились друг с другом настолько, что к настоящему времени стали практически полностью совместимы.
Таким образом, имеет смысл отметить тот ряд свойств, который присущ обеим моделям- Соответствие уровней модели OSI уровням модели TCP/IP представлено на рис. 1 А
Как видно из рисунка, сетевой уровень (уровень маршрутизации) модели OSI совпадает с соответствующим уровнем модели TCP/IP (уровень межсетевого взаимодействия). Функции данного уровня подробно рассмотрены в предыдущем разделе. Здесь следует остановиться лишь на том, что данное соответствие уровней лишний раз подчеркивает важность маршрутизации в технологии IP.
Прикладной уровень стека протоколов TCP/IP соответствует прикладному и представительному уровням модели ВОС. Прикладной уровень реализуется программными системами, построенными в архитектуре клиент-сервер, базирующимися на протоколах нижних уровней [34].
Транспортный уровень стека протоколов TCP/IP (также называемый основным уровнем) соответствует сеансовому и транспортному уровням модели ВОС. Он решает задачу обеспечения надежной информационной связи между двумя конечными узлами. На этом уровне функционируют два протокола TCP и UDP.
Уровни
модели
Уровни
стека
TCP/IP
Рис. 1А Соответствие уровней стека TCP/IP семиуровневой модели
Уровень сетевых интерфейсов стека протоколов TCP/IP соответствует канальному и физическому уровням модели ВОС, Уровень сетевых интерфейсов - сетезависимый уровень. Протоколы этого уровня должны обеспечить интеграцию объединяемых локальных сетей в составную сеть. Таким образом, для каждой технологии локальной сети, включаемой в составную сеть, разрабатываются собственные средства инкапсуляции IP-пакетов уровня межсетевого взаимодействия в кадры локальных технологий. Уровень сетевых интерфейсов в протоколах TCP/IP не регламентируется, но он поддерживает все популярные стандарты физического и канального уровней-
1.3. Протоколы и алгоритмы маршрутизации
Маршрутизация включает в себя два основных компонента: определение оптимальных трактов маршрутизации (маршрутов) и транспортировка информационных групп (пакетов) через объединенную сеть [15].
Пакет - это порция передаваемой информации, снабженная блоком служебной информации. Состав IP - пакета регламентируется документом RFC-791 [70]. Заголовок IP - пакета, являющийся блоком служебной информации, в своем составе имеет поле, которое содержит адрес получателя. Эта информация используется маршрутизаторами для продвижения пакета по сети. Строго говоря, маршрутизатор не обрабатывает весь пакет, а работает только с его заголовком.
Как отмечалось выше, IP относится к протоколам негарантированной доставки. Перед данным протоколом не ставится задача надежной доставки пакета от отправителя к получателю. Протокол IP обрабатывает каждый пакет как независимую единицу, не имеющую связи ни с какими другими ІР-пакетами [34].
Маршрутизация обеспечивает доставку пакетов между конечными системами (узлами), расположенными в различных сетях. Без маршрутизаторов и маршрутизируемых протоколов связь между конечными узлами ограничивалась бы обменом данными только между системами в одной и той же подсети [36].
На сегодняшний день известно большое число протоколов маршрутизации [36]- Спецификация, описывающая тот или иной протокол маршрутизации, состоит из двух разделов: один описывает алгоритм маршрутизации, а второй - формат данных, которыми обмениваются маршрутизаторы (рис, 1,5)-
Алгоритм маршрутизации структура табшщы шршрутшедш
* ирдаиза шшт-румрбтшш мегршш
* алгоритм шчйслсїшя мщщуугш
Формат данных
^npiiipvTHOH мнформаїсин пр&вшіа пршма/иередачи
ШІрШрУїИОЙ ВДіфорМШІШ
Рис. 1,5- Структура протоколе маршрутизацш
Проблема выбора шршругав в сета одновременна шішетш дробленой качества работы тати в целом*
Определение маршрута может базироваться на отдельных показателях (критерияк) эффективности маршрут или комбинациях гжих показателей,. Программное реализации алгоритмов маріпрутаищии вычисляют показатели маршрутов да определения наиболее оптимальных из внх<
Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритму могут Быть:
* Статическими или динамическими;
# Одномаршрутшми или мвогожршрушште;
Одноуровневыми шш иерархическими;
С интеллектом в глшійой вычислительной машине млн в маршрутизаторе;
# Вйутрндоменцыми и неждомиоаши^
Алгоритмами состояния канала или лектора расстояний.
Статические тм динамические алгоритмы
Распределение статических таблиц маршругщвдии устанавливается администратором сети до тачала маріпрутизации* Оно m меняется сел яг
21 только администратор сети не изменит его. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в сетях, где трафик сети относительно предсказуем, а схема сети относительно проста [37].
Так как статические системы маршрутизации не могут реагировать на изменения в сети, они, как правило, считаются непригодными для современных крупных, постоянно изменяющихся сетей. Большинство доминирующих на сегодняшний день алгоритмов маршрутизации -динамические.
Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в режиме реального времени- Они выполняют это путем анализа поступающих сообщений об обновлении параметров маршрутизации. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации. Такие сообщения пронизывают сеть, стимулируя маршрутизаторы заново прогонять свои алгоритмы и соответствующим образом изменять таблицы маршрутизации, Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это уместно. Например, можно разработать "маршрутизатор последнего обращения" (т.е. маршрутизатор, в который отсылаются все неотправленные по определенному маршруту пакеты). Такой маршрутизатор выполняет роль хранилища неотправленных пакетов, гарантируя, что все сообщения будут, по крайней мере, обработаны определенным образом. Одномаршрутные или многомаршрутные алгоритмы
Некоторые протоколы маршрутизации обеспечивают
множественность маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям; одномаршрутные алгоритмы не могут делать этого [46]. Преимущества многомаршрутных алгоритмов очевидны -
22 они могут обеспечить значительно большую пропускную способность и надежность. Одноуровневые или иерархические алгоритмы
Некоторые алгоритмы маршрутизации оперируют в «плоском пространстве», в то время как другие используют иерархии маршрутизации. В одноуровневой системе маршрутизации все маршрутизаторы равны по отношению друг к другу. В иерархической системе маршрутизации некоторые маршрутизаторы формируют то, что составляет основу {backbone- базу) маршрутизации [73]. Пакеты из небазовых маршрутизаторов перемещаются к базовым маршрутизаторам и пропускаются через них до тех пор, пока не достигнут общей области пункта назначения. Начиная с этого момента, они перемещаются от последнего базового маршрутизатора через один или несколько небазовых маршрутизаторов до конечного пункта назначения.
Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами, или автономными системами (AS), или областями. В иерархических системах одни маршрутизаторы какого-либо домена могут сообщаться с маршрутизаторами других доменов, в то время как другие маршрутизаторы этого домена могут поддерживать связь с маршрутизаторами только в пределах своего домена, В очень крупных сетях могут существовать дополнительные иерархические уровни. Маршрутизаторы наивысшего иерархического уровня образуют базу маршрутизации [73].
Основным преимуществом иерархической маршрутизации является то, что она имитирует организацию большинства компаний и следовательно, хорошо поддерживает их схемы трафика. Большая часть сетевой связи имеет место в пределах групп небольших компаний (доменов), Внутридоменным маршрутизаторам необходимо знать только о других маршрутизаторах в пределах своего домена, поэтому их алгоритмы маршрутизации могут быть упрощенными. Соответственно может быть
23 уменьшен и трафик обновления маршрутизации, зависящий от используемого алгоритма маршрутизации.
Алгоритмы с интеллектом в главной вычислительной машине или в маршрутизаторе
Некоторые алгоритмы маршрутизации предполагают, что конечный узел источника определяет весь маршрут. Обычно это называют маршрутизацией от источника. В системах маршрутизации от источника маршрутизаторы действуют просто как устройства хранения и пересылки пакета, без всякий раздумий отсылая его к следующему устройству.
Другие алгоритмы предполагают, что главные вычислительные машины ничего не знают о маршрутах. При использовании этих алгоритмов маршрутизаторы определяют маршрут через объединенную сеть, базируясь на своих собственных расчетах. В первой системе, рассмотренной выше, интеллект маршрутизации находится в главной вычислительной машине. В системе, рассмотренной во втором случае, интеллектом маршрутизации наделены маршрутизаторы.
Компромисс между маршрутизацией с интеллектом в главной вычислительной машине и маршрутизацией с интеллектом в маршрутизаторе достигается путем сопоставления оптимальности маршрута с непроизводительными затратами трафика [46], Системы с интеллектом в главной вычислительной машине чаще выбирают наилучшие маршруты, так как они, как правило, находят все возможные маршруты к пункту назначения, прежде чем пакет будет действительно отослан. Затем они выбирают наилучший маршрут, основываясь на определении оптимальности данной конкретной системы. Однако акт определения всех маршрутов часто требует значительного трафика поиска и большого объема времени. Внутридоменные или междоменные алгоритмы
Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие - как в пределах доменов, так и между ними. Природа этих
24 двух типов алгоритмов различная [68]. Поэтому понятно, что оптимальный алгоритм внутридоменной маршрутизации не обязательно будет оптимальным алгоритмом междоменной маршрутизации. Алгоритмы состояния канала или вектора расстояния
Алгоритмы состояния канала (известные также как алгоритмы "первоочередности наикратчайшего маршрута") направляют потоки маршрутной информации во все узлы объединенной сети [4]. Однако каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния требуют от каждого маршрутизатора посылки всей или части своей маршрутной таблицы, но только своим непосредственным соседям. Алгоритмы состояния каналов фактически направляют небольшие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние маршрутизаторы [79],
Отличаясь более быстрой сходимостью, алгоритмы состояния каналов несколько меньше склонны к образованию петель маршрутизации» чем алгоритмы вектора расстояния. С другой стороны, алгоритмы состояния канала характеризуются более сложными расчетами в сравнении с алгоритмами вектора расстояний, требуя большей процессорной мощности и памяти, чем алгоритмы вектора расстояний. Вследствие этого, реализация и поддержка алгоритмов состояния канала может быть более дорогостоящей. Несмотря на их различия, оба типа алгоритмов хорошо функционируют при самых различных обстоятельствах.
На основе имеющихся данных бал произведен сравнительный анализ наиболее популярных протоколов маршрутизации [38]. Результат данного анализа приведен в таблице 1.1.
25 Таблица 1.1. Популярные протоколы маршрутизации
1,4. Таблица маршрутизации. Метрика
Дет обжгчшш процесса определения маршруту алгоритмы морифутизации инициализируют и поддерживают телицы ыюртарупвдцин,
в которых содержится маршрутная информация [5]* Маршрутная информация изменяется в зависимости от используемого алгоритма
маршрутизации*
Для выполнении своой основной функции —- переключения трафика — каждгоі маршрутизатор исполюует таблицу маршрутдаации, в которой отражена тт&могт сети їш дашшй момент времени, Тшзты образом, таблица шршрутизации mm яетоя і іеотьш ji емой частью ал піритна маршрутизации, Пример таблицы маршрутизации представлен на рис. h6 [56], В самом общем случае таблица маршрутизации содержит адрес гати назначеная (Network), адрес следующей) узла ма пути к этой сети (Next Gateway) и метрику (стоимость) пути (Metric), Создание и последующее обновление таблицы маршрутизации яри изменении топоиогаи сети осуществляется с помощью щтотжем (ш сошвегетвуюших им ттртж&ш) маршрутизации- Наибольшей популярностью тятуюгея алгоритмы динамической маршрутизации.
HgrntEtig Table Іжшзрк:
Рис. 1,6. Пример таблицы маршрутазацин
Использование динамической маршрутизации связано с управлением таблицей маршрутизации соответствующим протоколом маршрутизации. Алгоритмы маршрутизации заполняют маршрутные таблицы информацией, отражающей топологию сети (в рамках используемого протокола маршрутизации). Ассоциации "Пункт назначения/следующая пересылка'* сообщают маршрутизатору, что определенный пункт назначения может быть оптимально достигнут путем отправки пакета в определенный маршрутизатор, представляющий "следующую пересылку" на пути к конечному пункту назначения. При приеме поступающего пакета маршрутизатор проверяет адрес пункта назначения и пытается ассоциировать этот адрес со следующей пересылкой,
В маршрутных таблицах может содержаться также и другая информация. "Показатели" обеспечивают информацию о желательности какого-либо канала или тракта [3 7], Маршрутизаторы сравнивают показатели, чтобы определить оптимальные маршруты. Показатели отличаются друг от друга в зависимости от использованной схемы алгоритма маршрутизации.
Маршрутизаторы сообщаются друг с другом (и поддерживают свои маршрутные таблицы) путем передачи различных служебных сообщений. Одним из видов таких сообщений является сообщение об "обновлении маршрутизации"- Обновления маршрутизации обычно включают всю маршрутную таблицу или ее часть. Анализируя информацию об обновлении маршрутизации, поступающую от всех маршрутизаторов, любой из них может построить детальную картину топологии сети. Другим примером сообщений, которыми обмениваются маршрутизаторы, является "объявление о состоянии канала". Объявление о состоянии канала информирует другие маршрутизаторы о состоянии каналов отправителя. Канальная информация также может быть использована для построения полной картины топологии сети. После того, как топология сети становится
28 понятной, маршрутизаторы могут определить оптимальные маршруты к пунктам назначения.
Маршрутные таблицы содержат информацию, которую используют программы маршрутизации для выбора наилучшего маршрута. Чем характеризуется построение маршрутных таблиц? Какова особенность природы информации, которую они содержат?
В алгоритмах маршрутизации используется много различных показателей. Сложные алгоритмы маршрутизации при выборе маршрута могут базироваться на множестве показателей, комбинируя их таким образом, что в результате получается один отдельный (интегральный) показатель - метрика. Метрика - специфическая структура данных, содержащая в себе в виде компонент показатели качества канала.
Поскольку компоненты метрики (показатели) весьма разнородны как по диапазонам своих значений, так и по размерности (смысловое значение), метрика как правило является величиной безразмерной. Необходимая компенсация размерностей производится за счет способа определения метрики.
Проведенный анализ протоколов маршрутизации (см. таблица 1.1) выявил следующие тенденции формирования метрики на основе своих компонент:
веса компонентов (каждый компонент вносит свой вклад в формирование метрики, в соответствии с весовым коэффициентом);
эмпирическая формула (конструируется формула, в которую тем или иным образом входит каждый компонент метрики);
алгоритм (вычисление метрики происходит алгоритмически, соответствующий алгоритм приводится в спецификации на протокол маршрутизации).
Ниже перечислены показатели, которые используются в алгоритмах маршрутизации;
длина маршрута;
надежность;
задержка;
ширина полосы пропускания;
стоимость связи [37]. Длина маршрута
Длина маршрута является наиболее общим показателем маршрутизации. Некоторые протоколы маршрутизации позволяют администраторам сети назначать произвольные цены на каждый канал сети, В этом случае длиной тракта является сумма расходов, связанных с каждым каналом, который был траверсирован. Другие протоколы маршрутизации определяют "количество пересылок", то есть показатель, характеризующий число проходов, которые пакет должен совершить на пути от источника до пункта назначения через устройства маршрутизации [62]. Надежность
Надежность, в контексте алгоритмов маршрутизации, относится к надежности каждого канала сети (обычно описываемой в терминах соотношения бит/ошибка). Некоторые каналы сети могут отказывать чаще, чем другие. Отказы одних каналов сети могут быть устранены легче или быстрее, чем отказы других каналов. При назначении оценок надежности могут быть приняты в расчет любые факторы надежности. Оценки надежности обычно назначаются каналам сети администраторами сети. Как правило, это цифровые величины [56]. Задержка
Под задержкой маршрутизации обычно понимают отрезок времени, необходимый для передвижения пакета от источника до пункта назначения через объединенную сеть. Задержка зависит от многих факторов, включая полосу пропускания промежуточных каналов сети, очереди в порт каждого маршрутизатора на пути передвижения пакета, перегруженность сети на всех промежуточных каналах сети и физическое расстояние, на которое
необходимо переместить пакет. Так как здесь имеет место конгломерация нескольких важных переменных, задержка является наиболее общим и полезным показателем [68], Ширина полосы пропускания
Полоса пропускания отражает максимальное количество информации способное пройти по какому-либо каналу в единицу времени. При прочих равных показателях, канал Ethernet 10 Мбит/с предпочтителен любой арендованной линии с полосой пропускания 64 Кбит/с, Хотя полоса пропускания является оценкой максимально достижимой пропускной способности канала, маршруты, проходящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие каналы [59]. Стоимость связи
Величина, отражающая финансовую стоимость использования данного направления. Задается в каких-либо условных единицах. Как правило, присутствует в алгоритмах маршрутизации опционально, устанавливается администратором сети вручную, по умолчанию не учитывается [73].
Проведенный анализ протоколов маршрутизации, результатом которого явилась таблица 1.1, выявил полную бессистемность, царящую в построении протоколов маршрутизации. Для дальнейшего развития протоколов маршрутизации требуется некая концепция, определяющая дальнейшую стратегию данного направления. Такой «системообразующей» концепцией может послужить нечеткая логика, применение которой при конструировании алгоритмов маршрутизации, само по себе уже будет определять структуру создаваемого алгоритма.
Метрика - специфическая структура данных, компоненты которой могут быть ранжированы или иметь зависимость в виде графа.
На рис. 1.7 представлен когнитивный граф [31], отражающий качественное влияние параметров метрики на ее величину.
- отказы по передаче
Рис. 1.7. Когнитивный граф метрики
На рис. 1.7 приняты следующие условные обозначения :
М - метрика;
Р1 - Интенсивность потока;
Р2 - Объем буфера;
РЗ - Заполненный объем буфера;
Р4 - Длина маршрута;
Р5 - Надежность канала;
Р6 - Задержка;
Р7 - Ширина полосы пропускания канала;
Р8 - Стоимость связи.
В таблице 1.2 представлен состав метрик наиболее популярных протоколов маршрутизации [38].
32 Таблица 1-2. Компоненты метрики протоколов маршрутизации
* - учитывается по умолчанию х - может быть учтена
1.5. Маршрутизация как процесс управления
Процесс маршрутизации пакета связан с управлением устройством, осуществляющим выбор выходного интерфейса маршрутизатора (переключение трафика)- Управляющее воздействие на маршрутизирующее устройство подается в виде метрики (М). Метрика, в свою очередь зависит от параметров маршрутизируемого пакета- Налицо система управления с обратной связью, схема которой представлена на рис, 1.8 .
Пакет.
Пакет
IP - адрес
Таблица маршрутизации
Вычисление метрики
Параметры маршрута
Рис. 1.8. Схема управления трафиком при маршрутизации пакета
Нарис. 1-8 приняты следующие условные обозначения:
SW - маршрутизирующее устройство;
М — метрика.
По IP-адресу в поступившем пакете находится соответствующая запись в таблице маршрутизации, которая содержит параметры маршрута, применительно к конкретному выходному интерфейсу. Параметры маршрута зависят от используемого протокола маршрутизации, в качестве таких параметров могут выступать число промежуточных узлов до сети назначения; время, которое требуется для передачи пакета по маршруту; пропускная способность канала и другие величины. Затем по выдаваемым параметрам вычисляется метрика, которая и определяет интерфейс маршрутизатора, используемый в качестве выходного.
Постановка задачи управления связана с понятиями объекта управления и управляющим воздействием. Как видно из рис. 1.8, объектом управления в контексте решаемой задачи является маршрутизирующее устройство, а в роли управляющего воздействия выступает метрика.
Следует найти такое воздействующее управление, при котором метрика была бы минимальной. Управляющее воздействие направлено на маршрутизирующее устройство, которое осуществляет выбор дальнейшего маршрута следования пакета- Таким образом, управляемым фактором является маршрут следования пакета.
Решая основную задачу управления, не следует забывать и о критериях эффективности самого управления. Такими критериями могут быть:
время ожидания пакета в очереди;
количество потерянных (не обслуженных) пакетов;
различные производные величины от перечисленных выше. Проведенный анализ существующих протоколов маршрутизации
показал, что такой параметр как объем маршрутизируемого пакета, а
34 следовательно и заполненность буферной памяти интерфейса, обычно не учитывается при вычислении метрики.
Схема управления трафиком на основе заполненности буфера представлена на рис. 1.9 .
Рис. 1.9. Схема управления трафиком на основе заполненности буфера
На рис. 1.9 через Kmem обозначен коэффициент заполненности буферной памяти интерфейса.
Однако, маршрутизация пакета, исходя только из одной заполненности буфера, не представляется целесообразной. Необходимо кроме коэффициента заполненности использовать и те параметры, которые изначально учитываются в определенном протоколе маршрутизации.
Обобщенная схема управления трафиком представлена на рис. 1.10. Здесь комбинированная метрика вычисляется как с учетом величины загруженности буфера, так и с учетом параметров маршрута. Такая схема позволяет проводить более гибкое управление трафиком, что в конечном итоге должно повысить эффективность функционирования сети в целом.
Рис. 1.10. Обобщенная схема управления трафиком
Управление трафиком на основе маршрутизации следует рассматривать как взаимодействие двух процессов: процесса передачи информации и процесса выбора маршрута, обеспечивающего процесс передачи. Эти процессы используют общие сетевые ресурсы и в первую очередь полосу пропускания каналов.
Выводы
Общая тенденция развития протоколов маршрутизации свидетельствует об усложнении соответствующих алгоритмов выбора маршрутов. При этом центральной проблемой становится конструирование метрики, адекватно отображающей процессы маршрутизации с учетом текущего сетевого трафика.
Проведенная работа по систематизации и анализу протоколов маршрутизации выявила, что на текущий момент системный подход к формированию метрики как основного критерия маршрутизации практически не используется. Использование разного рода эвристических формул для определения метрик в различных протоколах маршрутизации лишено универсальности и эволюционного развития, адекватного высоким темпам развития компьютерных сетей.
Проведенный анализ способов конструирования метрики в различных протоколах маршрутизации выявил тот факт что, несмотря на усложнение алгоритмов маршрутизации и рост учитываемых в метрике факторов, количество учитываемых факторов остается небольшим (1-4 фактора). Это свидетельствует о недостаточно глубоком отражении в метрике всех аспектов функционирования сети. Для повышения адекватности алгоритма маршрутизации, его метрика должна учитывать большее количество факторов.
Проблема конструирования метрики должна решаться на новой основе эволюционной (адаптивной) маршрутизации с использованием алгоритмов, основанных на нечетких множествах.
Протоколы и алгоритмы маршрутизации
Проблема выбора шршругав в сета одновременна шішетш дробленой качества работы тати в целом Определение маршрута может базироваться на отдельных показателях (критерияк) эффективности маршрут или комбинациях гжих показателей,. Программное реализации алгоритмов маріпрутаищии вычисляют показатели маршрутов да определения наиболее оптимальных из внх
Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритму могут Быть:
Статические тм динамические алгоритмы
Распределение статических таблиц маршругщвдии устанавливается администратором сети до тачала маріпрутизации Оно m меняется сел яг только администратор сети не изменит его. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в сетях, где трафик сети относительно предсказуем, а схема сети относительно проста [37].
Так как статические системы маршрутизации не могут реагировать на изменения в сети, они, как правило, считаются непригодными для современных крупных, постоянно изменяющихся сетей. Большинство доминирующих на сегодняшний день алгоритмов маршрутизации -динамические.
Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в режиме реального времени- Они выполняют это путем анализа поступающих сообщений об обновлении параметров маршрутизации. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации. Такие сообщения пронизывают сеть, стимулируя маршрутизаторы заново прогонять свои алгоритмы и соответствующим образом изменять таблицы маршрутизации, Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это уместно. Например, можно разработать "маршрутизатор последнего обращения" (т.е. маршрутизатор, в который отсылаются все неотправленные по определенному маршруту пакеты). Такой маршрутизатор выполняет роль хранилища неотправленных пакетов, гарантируя, что все сообщения будут, по крайней мере, обработаны определенным образом. Одномаршрутные или многомаршрутные алгоритмы
Некоторые протоколы маршрутизации обеспечивают множественность маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям; одномаршрутные алгоритмы не могут делать этого [46]. Преимущества многомаршрутных алгоритмов очевидны 22 они могут обеспечить значительно большую пропускную способность и надежность. Одноуровневые или иерархические алгоритмы
Некоторые алгоритмы маршрутизации оперируют в «плоском пространстве», в то время как другие используют иерархии маршрутизации. В одноуровневой системе маршрутизации все маршрутизаторы равны по отношению друг к другу. В иерархической системе маршрутизации некоторые маршрутизаторы формируют то, что составляет основу {backbone- базу) маршрутизации [73]. Пакеты из небазовых маршрутизаторов перемещаются к базовым маршрутизаторам и пропускаются через них до тех пор, пока не достигнут общей области пункта назначения. Начиная с этого момента, они перемещаются от последнего базового маршрутизатора через один или несколько небазовых маршрутизаторов до конечного пункта назначения.
Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами, или автономными системами (AS), или областями. В иерархических системах одни маршрутизаторы какого-либо домена могут сообщаться с маршрутизаторами других доменов, в то время как другие маршрутизаторы этого домена могут поддерживать связь с маршрутизаторами только в пределах своего домена, В очень крупных сетях могут существовать дополнительные иерархические уровни. Маршрутизаторы наивысшего иерархического уровня образуют базу маршрутизации [73].
Основным преимуществом иерархической маршрутизации является то, что она имитирует организацию большинства компаний и следовательно, хорошо поддерживает их схемы трафика. Большая часть сетевой связи имеет место в пределах групп небольших компаний (доменов), Внутридоменным маршрутизаторам необходимо знать только о других маршрутизаторах в пределах своего домена, поэтому их алгоритмы маршрутизации могут быть упрощенными. Соответственно может быть уменьшен и трафик обновления маршрутизации, зависящий от используемого алгоритма маршрутизации.
Алгоритмы с интеллектом в главной вычислительной машине или в маршрутизаторе
Некоторые алгоритмы маршрутизации предполагают, что конечный узел источника определяет весь маршрут. Обычно это называют маршрутизацией от источника. В системах маршрутизации от источника маршрутизаторы действуют просто как устройства хранения и пересылки пакета, без всякий раздумий отсылая его к следующему устройству.
Другие алгоритмы предполагают, что главные вычислительные машины ничего не знают о маршрутах. При использовании этих алгоритмов маршрутизаторы определяют маршрут через объединенную сеть, базируясь на своих собственных расчетах. В первой системе, рассмотренной выше, интеллект маршрутизации находится в главной вычислительной машине. В системе, рассмотренной во втором случае, интеллектом маршрутизации наделены маршрутизаторы.
Компромисс между маршрутизацией с интеллектом в главной вычислительной машине и маршрутизацией с интеллектом в маршрутизаторе достигается путем сопоставления оптимальности маршрута с непроизводительными затратами трафика [46], Системы с интеллектом в главной вычислительной машине чаще выбирают наилучшие маршруты, так как они, как правило, находят все возможные маршруты к пункту назначения, прежде чем пакет будет действительно отослан. Затем они выбирают наилучший маршрут, основываясь на определении оптимальности данной конкретной системы. Однако акт определения всех маршрутов часто требует значительного трафика поиска и большого объема времени. Внутридоменные или междоменные алгоритмы
Лингвистические переменные и логический вывод с нечеткими множествами
Прежде чем приступить к описанию понятия «лингвистическая переменная», следует ввести такое понятие, как лингвистический терм (linguistic term). Каждый лингвистический терм характеризуется своим лингвистическим значением, например: «высокий», «средний», «низкий». Лингвистическому значению ставится в соответствие функция принадлежности, определенная на универсуме X. Очевидным является тот факт, что на одном и том же универсуме можно определить несколько (в общем случае бесконечное количество) лингвистических термов, высокий
Пример определения лингвистических термов Лингвистическая переменная это переменная, область значений которой состоит из набора лингвистических термов. Например, переменная Kmem (коэффициент заполненности буфера интерфейса) может содержать три определенных выше терма:
Управление с нечеткими множествами тесно связано с таким понятием, как система нечеткого вывода. Нечеткие выводы - это наиболее важный метод в нечеткой логике. Выводы в «четком» искусственном интеллекте являются частным случаем нечетких выводов [44].
Построение системы нечеткого вывода состоит из следующих этапов:
фаззификация входных переменных;
формирование базы нечетких правил;
агрегирование подусловий;
активация подзаключений;
аккумуляция заключений;
дефаззификация выходных переменных. Рассмотрим более подробно каждый из этапов.
Фаззификация входных переменных. На этапе фаззификации для каждой лингвистической переменной определяется множество соответствующих ей лингвистических термов, А для каждого определенного лингвистического терма определяется соответствующая функция принадлежности (см, рис. 2.6).
Также в зависимости от используемого алгоритма нечеткого вывода, набор лингвистических термов может задаваться и для выходной переменной (рис. 2,7),
Целью этапа фаззификации является установление соответствия между конкретным (четким, crisp) значением отдельной входной переменной и значением функции принадлежности соответствующего ей терма входной лингвистической переменной. После завершения этого этапа для всех входных переменных должны быть определены конкретные значения функций принадлежности по каждому из лингвистических термов[26].
Формирование базы нечетких правил. База нечетких правил состоит из записей вида: ПРАВИЛО_Х: ЕСЛИ "Условие Х" ТО "Заключение_Х" (Fx) , где Fx - весовой коэффициент соответствующего правила. Здесь выражение, стоящее после ЕСЛИ, называют антцедентом, предпосылкой, условием. А выражение, стоящее после ТО - консеквентом, заключением, операцией.
Моделирование маршрутизации в рамках протокола ШР
Наиболее распространенным и простым протоколом, основанным на дистанционно-векторном алгоритме (DVA), является протокол RIP (Routing Information Protocol), выбранный в данной работе для иллюстрации методов управления трафиком сети, основанных на нечетких множествах.
Спецификация протокола RIP определяет диапазон значений метрики от 0 до 16 [61]. Если значение метрики равно 0, то сеть назначения непосредственно подключена к данному интерфейсу. Значение метрики равное 16 в протоколе RIP соответствует недосягаемости сети назначения.
При моделировании маршрутизатора в рамках протокола RIP была принята следующая логическая структура котроллера интерфейса (рис. 3.2). Контроллер интерфейса состоит из двух модулей: определения параметров и вычисления метрики [18].
Модуль определения параметров на основе адреса сети назначения маршрутизируемого пакета опрашивает таблицу маршрутизации и вычисляет значения параметров, необходимых для вычисления метрики для данного выходного интерфейса. На основании этих параметров модуль вычисления метрики определяет значение метрики, исходя из заложенного алгоритма. В данном случае такой параметр один - дистанция.
Алгоритм работы модуля вычисления метрики тривиален: метрика численно равна значению дистанции, что проиллюстрировано на рис. 3.3.
Вторым фактором, оказывающим большое влияние на выбор маршрута, может служить степень загруженности буферной памяти выходного интерфейса. Этот фактор определяет целесообразность отбрасывания пакета. В некоторых случаях целесообразнее направить пакет по более длинному маршруту, на котором буферы соответствующих интерфейсов менее загружены. Таким образом, при маршрутизации было бы разумным рассматривать два входных параметра: дистанцию и загруженность буферной памяти соответствующего интерфейса.
Какому фактору отдать предпочтение, дистанции или загруженности буфера, и в какой степени? Ответы на эти и подобные вопросы в значительной степени субъективны, поэтому алгоритм выбора решения целесообразно формировать на основе нечеткой логики [32], которая позволяет учитывать влияние многих факторов, связанных с проблемой маршрутизации. При этом структура контроллера выходного интерфейса будет иметь вид, представленный на рис. 3.4.
Модуль вычисления метрики приобретает характер нечеткой системы, а сам процесс определения метрики состоит из основных этапов формирования нечеткого отклика: фаззификация, композиция и дефаззификация [9].
Фаззификация связана с определением нечетких множеств, характеризующих входные переменные - дистанцию и коэффициент использования буферной памяти Kmem. Такие множества описываются характеристическими функциями, принимающими значения в интервале от нуля до единицы, определяющими степень предпочтения соответствующего фактора. В некоторых случаях такие функции можно определить объективно, исходя из условий задачи, в других (что встречается чаще всего) субъективно, на основе здравого смысла. В рассматриваемой проблеме маршрутизации мы имеем примеры и того и другого подхода. Первый этап фаззификации состоит из определения входных и выходных переменных, а также соответствующих им нечетких лингвистических переменных. Соответствие "четких" входных и выходных переменных системы лингвистическим переменным приведено в таблице 3.1.
Анализ эффективности алгоритма маршрутизации с помощью имитационного моделирования
Для количественной оценки эффективности марщрутнзацкя, основанной на алгоритме с нечеткими множествами, была построена имитационная модель, изображенная на рис. 3.23 [39]. Моделирование является ОДНИМ из распространенных способов научения различных процессов н явлений и широко используется в научных исследованиях [50].
Исследование данной модели связано с определением входного воздействия и анализом разпичных нок&загелей [20,21] (доля потерянных, пакетов, время задержки в очереди, длина очереди и т.п.). Выходная яоспваовагашйкаъ В данной модели пакеты, поступающие на один из интерфейсов, имитируются входной шсдедоштельноетью заявок (тегов). Заявка, ноступивїяая на вход, направляется на маршрутизирующее устройство (SW), котреє определяет, в какую из очередей {Q1 или Q2) направить данную заявку»
QI и Q2 представляют собой конечные очереди, организованные но принципу FIFO. Они имитируют буферную намять выходных интерфейсов маршрутизатора Вели очередь, в которую направляется заявка, заполнена, то данная заявка не обслуживается, что имитирует потерю пакета в маршрутизаторе (счетчик не обслуженных заявок при этом увеличивается на единицу). В1 и В2 представляют собой обслуживающие устройства [12], которые имитируют работу выходных линий маршрутизатора.
Для проведения имитационного моделирования был использован программный продукт Micro Saint [16]. Блок-схема модели, построенной в программе Micro Saint с целью моделирования процесса маршрутизации представлена на рис. 3,24.
Здесь блок «begin» служит для генерации тегов, имитирующих пакеты. Блок «SWITCH» имитирует работу маршрутизирующего устройства, блоки «Q1» и «Q2» имитируют конечные очереди, блоки «intl» и «int2» имитируют работу выходных линий. Блоки «trash 1» и «trash2» служат для подсчета потерянных пакетов.
Для проведения всестороннего анализа модели необходимо на ее вход подать различные последовательности данных. Данные могут наилучшим образом подходить для конкретной модели, могут быть организованы наихудшим образом. Наихудший вариант представляет собой странную конструкцию, никогда не встречающуюся на практике, но такой вид анализа предоставляет полезную информацию о производительности [45].
Первый эксперимент связан с подачей на вход модели детерминированной последовательности (рис. 3.25). Это делается с целью еернфшшдш яостроашшй модели- В данном туч.ж наша модель представляет собой систему массового обслуживания B/D/2 [ 12].
Здесь X - шітенсшшость входного потока, t - время.
Сяедукшрй эксперимент связан є шд&чей на код модшш Еіуассонавского потока (рис. 326)- Пуассоновский ноток характеризуется экспоненциальным характером распределения внтбрвадй& времени штщ заявками (пакетамв) 130]. В данном случае модель представляет собой систему массового обслуживания М/Ш2.
Похожие диссертации на Методы IP-маршрутизации на основе алгоритмов с использованием нечетких множеств
