Биография Библиотека Список ссылок Отчет о поиске Задание ДонНТУ
Солдатова Виктория Александровна
Специальность:	"Программное обеcпечение автоматизированных систем"
Тема магистерской работы:	"Исследование адаптивных алгоритмов маршрутизации в компьютерных сетях"
Научный руководитель:	доц., канд. техн. наук Ладыженский Юрий Валентинович
E-mail:	_sunshine@mail.ru

Автореферат выпускной магистерской работы

СОДЕРЖАНИЕ

1. Актуальность темы
2. Обзор имеющихся исследований и разработок
3. Определение и характеристики маршрутизации
3.1 Общая постановка задачи маршрутизации
3.2 Классификация алгоритмов маршрутизации
3.3 Основные характеристики задачи маршрутизации
4. Алгоритмы маршрутизации
4.1 Алгоритмы проверки состояния линии связи
4.2 Дистанционно-векторные алгоритмы
4.3 Адаптивный, оптимальный алгоритм маршрутизации Daemon
5. AntNet – адаптивный, базирующийся на агентах алгоритм маршрутизации
5.1 Принципы поведения муравьев
5.2 Применение роевого интеллекта к задаче маршрутизации
5.3 Описание алгоритма AntNet и его характеристик
5.4 Расчет укрепляющего коэффициента
6. Результаты исследования поведения алгоритмов маршрутизации
Заключение
Литература

1. Актуальность темы

С каждым годом количество пользователей компьютерных сетей растет. Это, в свою очередь, обуславливает рост сложности структур сетей и взаимодействия между ними. Соответственно усложняется и поиск оптимальных путей в сети для быстрой доставки запросов пользователей сети, т.е. усложняется задача маршрутизации.

Маршрутизация пакетов в сети занимает одно из важных мест в управлении сетью. Под маршрутизацией обычно понимают доставку пакетов из одного узла сети в другой, максимизируя при этом производительность сети. Задачу маршрутизации в сети решают специальные устройства - маршрутизаторы. Алгоритм маршрутизации - это часть программного обеспечения маршрутизатора, отвечающая за выбор выходной линии, на которую поступивший пакет должен быть передан. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети, длин очередей в узлах коммутации и т.п.

В виду сложности структур современных компьютерных сетей, задача маршрутизации не решается в полной мере. В большинстве случаев это связано с маршрутизаторами [1], не справляющимися с поддержанием таблиц маршрутизации и выбором оптимальных маршрутов для данного класса трафика. Поэтому возникает задача исследования существующих алгоритмов маршрутизации с целью улучшения их характеристик, или создания новых алгоритмов маршрутизации.

В данной работе описаны различные виды алгоритмов маршрутизации. Большинство алгоритмов уже используются для решения задачи маршрутизации в сетях. Однако эти алгоритмы не всегда соответствуют выдвигающимся к ним требованиям. Поэтому в работе [2] был предложен новый подход к задаче маршрутизации - алгоритм AntNet. Это адаптивный, базирующийся на агентах алгоритм маршрутизации, который демонстрирует лучшие результаты производительности, среди всех рассмотренных алгоритмов [2]. Алгоритм AntNet использует для маршрутизации данных по сети роевых интеллект. Такой интеллект присущ некоторым видам социальных насекомых (муравьи, осы, пчелы, термиты).

Целью магистерской работы является реализация алгоритма Antnet и сравнение его с другими алгоритмами маршрутизации.

2. Обзор имеющихся исследований и разработок

Впервые алгоритм AntNet был описан Джанни Ди Каро (Gianni Di Caro) и Марко Дориго (Marco Dorigo) в 1998 году в работе [2]. Дориго и Ди Каро протестировали этот алгоритм, используя, построенную ими, дискретно-событийную модель.

Шондерверд (Schoonderwoerd) и другие в 1996-1997 гг. [3,4] рассмотрели маршрутизацию как возможную область применения роевого интеллекта. Их подход к управлению сетью с помощью муравьев (ABC - ant-based control) используется при маршрутизации данных в телефонных сетях и во многом отличается от алгоритма AntNet. Кроме того, в 1997 году Субраманиан (Subramanian), Друшель (Druschel) и Чен (Chen) предложили свой алгоритм [5], базирующий на поведении колонии муравьев в природе. Данный алгоритм был применен к сетям с коммутацией пакетов и являлся расширением ABC-алгоритма, предложенного Шондервердом.

3. Определение и характеристики маршрутизации

3.1 Общая постановка задачи маршрутизации

Маршрутизация может быть представлена в следующем виде. Пусть дан направленный взвешенный граф G=(V,E), в котором каждый узел из множества V представляет собой устройство, обрабатывающее и передающее данные, а каждое ребро из множества E является линией связи. Основной задачей алгоритмов маршрутизации является передача данных из узла источника в узел приемник, максимизируя при этом производительность сети. При моделировании алгоритмов маршрутизации возникают две проблемы, затрудняющие процесс создания системы. Во-первых, поток данных не является статическим, во-вторых, он имеет стохастический характер.

Алгоритмы маршрутизации должны выполнять следующие функции:
1. сбор, организация и распределение информации о созданном пользователем трафике и состояниях сети;
2. использование собранной информации для создания подходящих маршрутов, максимизирующих производительность объектов;
3. направление трафика пользователя по выбранному маршруту.

Способ реализации описанных трех функции сильно зависит от технологии передачи и коммутации пакетов, положенной в основу сети, и от особенностей других взаимодействующих уровней приложений. Отправка трафика пользователя может происходить с использованием двух базовых операций сети: коммутация каналов и коммутация пакетов (которые также связанные с понятиями ориентированный и неориентированный на соединение.) При коммутации каналов на стадии установки соединения ищутся и резервируются ресурсы сети, которые впоследствии будут предоставлены каждой новой сессии. В этом случае все пакеты данных, принадлежащие одной и той же сессии, будут направлены по одному и тому же пути. От маршрутизаторов требуется хранение информации об активной сессии. При коммутации пакетов нет стадии резервирования, информация о состоянии не хранится на маршрутизаторах, и пакеты данных могут отправляться по разным путям. В каждом промежуточном узле принимается самостоятельное решение о выборе выходной линии, по которой будет отправлен пакет данных в узел приемник.

В данной работе используются сети с коммутацией пакетов.

Общим параметром для всех видов алгоритмов маршрутизации является таблица маршрутизации. Таблица маршрутизации располагается в каждом узле сети, и содержит всю информацию о ней. Эта информация, в свою очередь используется маршрутизаторами для создания маршрутов отправки пакетов данных. Тип информации, содержащейся в маршрутных таблицах, зависит исключительно от алгоритма маршрутизации.

3.2 Классификация алгоритмов маршрутизации

Алгоритмы маршрутизации можно классифицировать следующим образом [2]:
• Централизованные и распределенные;
• Статические и адаптивные.

В централизованных алгоритмах главное управляющее устройство отвечает за обновление таблиц маршрутизации всех узлов и/или принимает каждое решение о маршрутизации. Централизованные алгоритмы могут быть использованы только в частных случая и для малых сетей. В общем, задержки необходимые для сбора информации о состоянии сети и для трансляции запроса на обновление данных делает такие алгоритмы неприменимыми на практике. Более того, централизованные системы не являются отказоустойчивыми. В данной работе рассматривается только распределенная маршрутизация, разделяющая вычисление маршрутов между узлами сети, которые обмениваются необходимой информацией.

В статических системах маршрутизации путь, который проходит пакет, определяется только на основе его источника и приемника, без рассмотрения текущего состояния сети. Этот путь обычно выбирается как кратчайший относительно выбранного стоимостного критерия, и может быть изменен только за счет поврежденных линий связи или узлов.

Адаптивные маршруты, в принципе, более привлекательны, так как они могут адаптировать способ маршрутизации к временным и к пространственным изменениям трафика. Как недостаток такого подхода выделяют то, что слишком частые изменения в сети могут стать причиной колебаний в выбранных путях. Это обстоятельство, в свою очередь, может привести к созданию циклических путей, а также к большим отклонениям в выполнении алгоритма. К тому же адаптивная маршрутизация может привести к противоречивым ситуациям, которые могут возникнуть при выходе из строя узлов, линий связи или при изменении локальной топологии. Однако, все эти проблемы устойчивости более характерны для сетей неориентированных на соединение.

Другой способ классификации алгоритмов маршрутизации имеет вид [2]:
• Минимальная маршрутизация и неминимальная маршрутизация;
• Оптимальная маршрутизация и маршрутизация, определяющая кратчайший путь.

Минимальные маршруты позволяют пакетам выбирать только пути с минимальной стоимостью, в то время как неминимальные алгоритмы позволяют делать выбор между всеми доступными путями, используя при этом некоторые эвристические стратегии.

Оптимальная маршрутизация имеет доступ ко всей сети и ко всем ее объектам для оптимизации функции всех отдельных потоков линий связи (обычно эта функция является суммой стоимостей путей назначенных в соответствии со средними задержками пакетов) [6].

Маршрутизация, определяющая кратчайшие пути, объективно определяет кратчайший путь (минимальную стоимость) между двумя узлами. Учитывая содержание в таблицах маршрутизации различной информации, алгоритмы нахождения кратчайших путей могут быть поделены на два класса: дистанционно-векторные и алгоритмы состояния связи.

Оптимальная маршрутизация является статической и требует знания всех характеристик трафика. Алгоритмы нахождения кратчайших путей более гибкие, они не требуют априорных знаний о моделях трафика, и, на данный момент, наиболее распространены среди алгоритмов маршрутизации.

3.3 Основные характеристики задачи маршрутизации

Существуют две основные характеристики, на которые существенное влияние оказывает алгоритм маршрутизации - пропускная способность (количество обслуживания) и средняя задержка пакета (качество обслуживания) [6]. Маршрутизация считается хорошей, если ей удается увеличить пропускную способность и уменьшить среднюю задержку пакета.

Маршрутизация взаимодействует с управлением потоками в определении характеристик посредством механизма обратной связи, представленном на рисунке 3.1.

Рисунок 3.1 - Взаимодействие между маршрутизацией и управлением потока с помощью механизма обратной связи

Величины задержки пакетов и пропускной способности зависят от решений, принятых алгоритмом маршрутизации. Однако на пропускную способность в большей степени влияет алгоритм управления потоками. Такие алгоритмы обычно действуют на основе поддержания баланса между пропускной способностью и средней задержкой [6]. Поэтому если алгоритму маршрутизации удается более успешно поддерживать малую задержку, то алгоритм управления потоками разрешает принимать сеть больше трафика. Хотя точный баланс между задержкой и пропускной способностью устанавливается алгоритмом управления потоками, хорошая маршрутизация в условиях большого предлагаемого трафика дает предпочтительную кривую задержка - пропускная способность, по которой действует алгоритм управления потоками (см. рис. 3.2).

Рисунок 3.2 - Кривые зависимости задержки от пропускной способности для хорошей и плохой маршрутизации

4. Алгоритмы маршрутизации

4.1 Алгоритмы проверки состояния линии связи

Маршрутизация с проверкой состояния линий связи, в общем, имеет следующий вид.

Во время инициализации маршрутизатор определяет стоимость линии для каждого из своих сетевых интерфейсов. Затем маршрутизатор передает эту информацию всем остальным маршрутизаторам в сети, а не только соседним. Далее маршрутизатор следит за состоянием своих линий связи. При значительном изменении (радикально меняется стоимость линии, создается новая линия, становится недоступной существующая линия), маршрутизатор снова объявляет о стоимости своих линий всем маршрутизаторам конфигурации.

Поскольку каждый маршрутизатор получает информацию о стоимости линий от всех маршрутизаторов, каждый маршрутизатор должен рассчитать топологию всей конфигурации, а затем вычислить кратчайший путь к каждой сети. Выполнив расчет, маршрутизатор может сформировать маршрутную таблицу с данными о первом ретрансляционном участке в направлении каждого потенциального получателя. Поскольку при таком подходе к маршрутизации, маршрутизатор имеет данные обо всей сети, то нет необходимости использовать распределенную версию алгоритма маршрутизации, применяемой, например, в дистанционно-векторных алгоритмах. Вместо этого маршрутизатор может воспользоваться любым алгоритмом определения кратчайшего пути. На практике используют алгоритм Дейкстры [1].

В программе ROUTING_SIMULATOR планируется реализовать такие алгоритмы маршрутизации как OSPF [1,2,7] и SPF [2].

4.2 Дистанционно-векторные алгоритмы

Для дистанционно-векторной маршрутизации требуется, чтобы каждый узел (маршрутизатор или хост, на котором реализован протокол RIP [8] (Routing Information Protocol - протокол маршрутной информации)) обменивался информацией с соседними узлами. Для работы алгоритма каждый узел хранит три вектора [1]:

-Wx = [ w(x,1), . . . , w(x,M) ]	- вектор стоимости линий, где
M – количество сетей, с которыми напрямую соединен узел x; w(x,i) - стоимость линии, которая ассоциируется с выходом каждого узла для каждой присоединенной сети i.
- Lx = [ L(x,1), . . . , L(x,N) ]	- вектор расстояния для узла x, где
L(x,j) - текущая оценка минимальной задержки от узла x до сети j; N - количество сетей в конфигурации.
- Rx = [ R(x,1), . . . , R(x,N) ]	- вектор следующего ретрансляционного участка узла x, где
R(x,j) - следующий маршрутизатор на текущем маршруте от узла x до сети j.

Периодически (каждые 30 секунд) каждый узел обменивается своим вектором расстояний с соседями. На основе всех входящих векторов расстояний узел x обновляет оба своих вектора следующим образом:

, где

• y=R(x,j) - значение, минимизирующее предыдущее выражение;
• Neighbours - множество узлов, соседних с x;
• N_xy - сеть, соединяющая узел x с узлом y.

В программе ROUTING_SIMULATOR планируется реализовать дистанционно-векторный алгоритм маршрутизации BF (Bellman-Ford - распределенный алгоритм Беллмана-Форда) [1,2]. Также к классу дистанционно-векторынх алгоритмов относят алгоритмы Q-R (Q-Routing) [2,9] и PQ-R (Predictive Q-Routing) [2]. Оба эти алгоритма основываются на известном направлении Reinforcement Learning [9] (обучение подкреплением).

4.3 Адаптивный, оптимальный алгоритм маршрутизации Daemon

Целью оптимальной маршрутизации является оптимизация (минимизация) функции всех потоков линии связи [2]. Оптимальные модели маршрутизации также называют потоковыми моделями, потому что они пытаются оптимизировать весь средний поток, присутствующий в сети.

Алгоритм Daemon является приближением к идеальному алгоритму маршрутизации. Использование Daemon при исследовании поведения различных алгоритмов маршрутизации позволяет определить эмпирическую границу производительности, которая вообще может быть достигнута. С помощью этой эмпирической границы возможно получение некоторой информации, о том, какие еще улучшения могут быть сделаны. При отсутствии каких-либо априорных предположений о статистике трафика, эмпирическая граница может быть определена алгоритмом "демоном", способным к чтению любого состояния очередей и любого элемента сети, и способного рассчитывать мгновенные "реальные" стоимости для всех линий связи и путей назначения на основании пересчета кратчайших путей для каждого хопа пакета во всей сети. Очевидно, что реализация такого "идеального" алгоритма в реальных сетях невозможна.

В работе [2] стоимости линий связи, используемые для расчета кратчайших путей, определяются следующей формулой:

, где

• d_l - задержка передачи для линии связи l;
• b_l - пропускная способность
• S_p - размер (в битах) пакета данных, совершающего хоп;
• S_Q(l) - размер (в битах) очереди линии связи l;
• - это экспоненциальное среднее размеров очередей линий связи и коррекций их действительного размера, исходя из того, что исследуется на данный момент.

Коррекция определяется весовым коэффициентом равным 0.4 [2]. Следует отметить, что способ вычисления C_l может быть произвольным.

5. ANTNET – адаптивный, базирующийся на агентах алгоритм маршрутизации

В последние два десятилетия при оптимизации сложных систем исследователи все чаще применяю природные механизмы поиска наилучших решений. В частности для решения оптимизационных задач используют так называемый роевый интеллект (Swarm Intelligence), основанный на поведение социальных насекомых. На Земле около двух процентов насекомых являются социальными, половину из них составляют муравьи, поэтому наибольшее распространение получили алгоритмы, использующие поведение муравьев в природе. Также к социальным насекомым относят термитов, некоторый вид пчел и ос.

5.1 Принципы поведения муравьев

Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива - колонии. Поведение муравьев при транспортировании пищи, преодолении препятствий, строительстве муравейника и других действиях зачастую приближается к теоретически оптимальному.

Основу социального поведения "муравьев" составляет самоорганизация. Под самоорганизацией понимают множество динамических механизмов, обеспечивающих достижение системой глобальной цели в результате низкоуровневого взаимодействия ее элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. При этом исключается любое централизованное управление и обращение к глобальному образу, представляющему систему во внешнем мире. Самоорганизация является результатом взаимодействия следующих четырех компонентов [10]:

• случайность;
• многократность;
• положительная обратная связь;
• отрицательная обратная связь.

Муравьи используют два способа передачи информации: прямой (например, обмен пищей) и непрямой - стигмержи (stigmergy) [2]. Стигмержи - это распределенный во времени тип взаимодействия, когда один субъект взаимодействия изменяет некоторую часть окружающей среды, а остальные используют информацию об ее состоянии позже, когда находятся в ее окрестности. В природе стигмержи осуществляется через феромон (pheromone) - специальный секрет, оставляемый как след при перемещении муравья. Чем больше концентрация феромона на пути, тем больше муравьев будет по нему двигаться. Со временем феромон испаряется, что позволяет муравьям адаптировать свое поведение под изменения внешней среды. Распределение феромона по пространству передвижения муравьев является своего рода динамически изменяемой глобальной памятью муравейника. Любой муравей в фиксированный момент времени может воспринимать и изменять лишь одну локальную ячейку этой памяти [10].

5.2 Применение роевого интеллекта к задаче маршрутизации

Поведение муравьев в природе можно использовать для решения задачи маршрутизации.

Представим компьютерную сеть как окрестность, в которой взаимодействуют муравьи, при этом узлы этой сети будут являться источниками пищи для муравьев. Узлы соединены линиями связи, на которых муравьи могут отставлять след феромона. Каждый узел в сети характеризуется двумя структурами данных: локальной моделью трафика и вероятностной таблицей маршрутизации. Муравьев в такой сети будем называть мобильными агентами. Каждый мобильный агент движется от одного узла сети к другому (от муравейника к источнику пищи), при этом собирая информацию о линиях связи, соединяющих эти узлы. Чтобы распространить собранную информацию по сети, агент должен вернуться в узел, отправивший его. Для этого у каждого агента существует память, организованная в виде стека, в которую записан весь маршрут движения агента от узла-источника в узел-приемник. При выборе пути движения от узла-источника в узел-приемник через промежуточные узлы агенты используют вероятностное правило выбора пути. Вероятность выбора пути прямо пропорциональна количеству феромонов на этом пути. То есть, линии связи, содержащие большее количество феромонов, являются наиболее удобными маршрутами для пересылки пакетов в сети. В результате своего движения агенты должны собрать информацию о состоянии трафика и обновить главные структуры данных узла.

Проиллюстрировать такой подход можно рисунком 5.1.

Рисунок 5.1 - Применение поведения муравьев к задаче маршрутизации

Аналогию с колонией муравьев в [2] использовали М. Дориго (Marco Dorigo) и Д. Ди Каро (Gianni Di Caro) для создания распределенного, адаптивного алгоритма маршрутизации AntNet.

В этом алгоритме моделирование искусственной колонии муравьев протекает в итерационном процессе. Здесь каждый муравей строит решение, используя два типа локально достижимой информации: информация специфичная для задачи (например, время достижения узла сети), и информация, добавленная муравьем во время предыдущей итерации алгоритма. Фактически, во время построения решения, каждый муравей собирает информацию, содержащую характеристики задачи и собственную производительность, и, далее, использует эту информацию для модификации представления задачи, с локальной точки зрения других муравьев. Представление о задачи модифицируется таким образом, что информация, содержащейся в предыдущем хорошем решении может быть использована для построения новых лучших решений.

5.3 Описание алгоритма AntNet и его характеристик

Перед тем, как описать основные шаги алгоритма, следует определить структуры данных и характеристики, с которыми будет оперировать алгоритм.

AntNet легко описывается в терминах двух множеств однородных мобильных агентов, называемых соответственно вперед идущие (Forward ants, В-муравьи) и назад идущие муравьи (Backward ants, Н-муравьи). Агенты каждого множества имеют одинаковую структуру, но по-разному ведут себя в окружающей среде; то есть, у них могут быть разные входы и разные, независимые выходы. Агенты общаются косвенным путем, обмениваясь информацией, которую они совместно читают или записывают в две структуры данных, хранящихся в узле сети k (см. рис 5.2) [2].

Рисунок 5.2 - Структура узла сети, использующей алгоритм маршрутизации AntNet

Из рисунка 5.2 видно, что узел сети содержит две структуры данных:

1. Таблица маршрутизации T_k организована также как и в дистанционно-векторных алгоритмах, но содержит вероятностные значения. Для каждого возможного узла d и для каждого соседнего узла n, маршрутная таблица T_k узла k хранит вероятностное значение P_nd, определяющее вероятность выбора узла n, при условии, что d узел-приемник:
   
2. Массив - это структура данных, определяющая простую параметрическую статистическую модель для распределения трафика в сети с точки зрения локального узла k. Модель является адаптивной и описывается выборочным средним и дисперсией, рассчитанными с помощью полученных при различных опытах времен обхода мобильными агентами сети, и движущимся окном наблюдений Wd, которое используется для хранения лучшего значения времени W_bestd обхода агентами сети.

Для каждого узла-приемника d в сети, вычисленные значения математического ожидания и дисперсии, и , представляют собой ожидаемое значение времени достижения этого узла и, соответственно, стабильность этого ожидаемого времени. Опыты показали [2], что для расчета статистики лучше использовать экспоненциальную модель:

где o_k->d - новое исследуемое время движения агента из узла k в узел d.

Движущееся окно наблюдений W_d используется для расчета значения W_bestd лучшего времени движения агентов по направлению к узлу d, наблюдаемого в последних w опытах. После каждого нового опыта значение w увеличивается на модуль |W|_max, где |W|_max - максимально допустимый размер окна наблюдений. Значение W_bestd представляет собой краткосрочную память, выражающую движущуюся эмпирическую нижнюю границу оценки времени достижения узла d из текущего узла.

T и M могут рассматриваться как локальная память узлов, которая содержит различные аспекты сетевой динамики сети. Модель M содержит абсолютные оценки расстояния/времени ко всем узлам, в то время как таблица маршрутизации содержит относительные вероятностные измерения полезности для каждой пары линия связи - узел-приемник при использовании такого метода маршрутизации на всей сети.

Таким образом, после определения основных структур данных алгоритма его можно описать в следующем виде:

1. Через регулярные интервалы времени dt из каждого узла сети s запускается мобильный агент (В-муравей) F_s->d, направленный к узлу назначения d. Целью В-муравья является исследование состояний загрузки сети и определение наиболее подходящего дешевого пути к узлу d. В-муравьи перемещаются по тем же очередям, что и пакеты данных. Это сделано для того, чтобы агент "испытал на себе" те же самые загрузки трафика, что и пакет с данными.
   Узлы-приемники выбираются локально в зависимости от сгенерированных локальной рабочей нагрузкой моделей данных трафика: если принять f_sd за величину потока передачи данных (в битах или количество пакетов) от узла s к узлу d, то вероятность создания в узле s В-муравья с узлом-приемником d будет вычисляться по формуле [2]:

   

2. Во время движения к узлу-приемнику, агенты хранят память о пройденных путях и об обнаруженных состояниях трафика. Идентификатор каждого пройденного узла k и время, прошедшее с момента запуска муравья до момента достижения им k-го узла, заталкиваются в память муравья, имеющего структуру стека S_s->d(k).
3. Из каждого узла k каждый двигающийся агент для того, чтобы достичь узел d выбирает узел n. Этот узел может быть выбран среди множества соседних узлов, которые еще не были рассмотрены или, если же все узлы уже были пройдены, то выбор происходит по всем соседним узлам. Соседний узел n выбирается с вероятностью (полезностью) P'_nd, которая рассчитывается как нормализованная сумма вероятностного элемента P_nd таблицы маршрутизации и эвристического поправочного коэффициента l_n, учитывающего состояние (длину) n-ой очереди связи текущего узла k [2]:

   

   где l_n - эвристический поправочный коэффициент, определяется как нормализованное значение пропорциональное длине очереди линии связи q_n (измеряется в битах ожидающих отправки), соединяющей узел k с его соседними узлами n [2]:

   

   Коэффициент l_n отражает мгновенное состояние очередей узла и предполагает, что процесс извлечения из очереди почти постоянен или медленно изменяется. l_n определяет количественную меру, связанную со временем ожидания в очереди. Значения в таблице маршрутизации, с другой стороны, являются результатом непрерывного процесса обучения и фиксируют как текущее состояние всей сети, так и прошлое ее состояние относительно локального узла. Коррекция этих значений с помощью коэффициента l позволяет системе быть более "чувствительной", но в то же время избегать присущие каждой сети колебания. Принятие решений агентом происходит на основе комбинации долгосрочного процесса обучения и мгновенного эвристического прогнозирования.
4. Если обнаружен цикл, т.е. муравей вынужден вернуться к уже пройденному им узлу, узлы цикла выталкиваются из стека муравья и вся память о них уничтожается.
5. Когда узел назначения d достигнут, агент F_s->d генерирует другого агента (Н-муравья) B_d->s, передавая ему при этом всю собранную информацию, и умирает (уничтожается).
6. Н-муравей двигается по тому же пути что и В-муравей, но в противоположном направлении. Во время прохождения пути в каждом узле k происходит выталкивание данных из стека S_s->d(k), таким образом, Н-муравей узнает следующий узел для перемещения. В отличие от В-муравьев Н-муравьи не расположены в тех же очередях что и пакеты данных. Так как перед Н-муравьями стоит задача как можно быстрее распространить между узлами информацию, собранную В-муравьями, то муравьи, идущие назад используют более приоритетные очереди.
7. Достигнув узел k, из соседнего узла f, Н-муравей обновляет две главные структуры данных узла, локальную модель трафика M_k и все элементы таблицы маршрутизации T_k для узла-приемника d.
   Опишем способ обновления M и T относительно общего узда d' S_k->d.
   • M_k модифицируется с помощью значений, хранящихся в стеке S_s->d(k). Время достижения (для В-муравья) узла назначения d' из текущего узла используется для обновления средних и дисперсионных оценок и , и для определения лучшего значения, передаваемого в окно наблюдения W_d'. В этом случае используется параметрическая модель времени движения муравья к узлу назначения d'. Среднее значение времени движения муравья к узлу назначения d' и его дисперсия могут сильно варьироваться, в зависимости от состояний трафика: "плохое" время (путь) при низкой загрузке трафика может быть "хорошим" при сильной загрузке трафика. Статистическая модель должна уметь выявлять эти изменения и исследовать помехоустойчивость системы при колебаниях трафика.
   • Таблица маршрутизации T_k изменяется путем увеличения вероятности P_fd' (т.е. вероятности выбора соседнего узла f когда узел назначения d') и уменьшения, нормализацией, других вероятностей P_nd'. Количество изменений в вероятностях зависит от величины полезности, которую мы ассоциируем со временем движения В-муравья T_k->d'. Это время представляет собой единственный, доступный явный сигнал обратной связи для оценки путей. Что дает четкое представление о полезности r следующего маршрута, т.к. она пропорциональна его длине от физической точки (кол-во хопов, емкость передач данных, используемая линиями связи, быстродействие в перекрестных узлах) и от точки перегрузки трафика (В-муравей находится в той же очереди что и пакеты данных).

В алгоритме AntNet для, того чтобы искусственные муравьи могли определить является ли этот путь хорошим, то есть как часто другие муравьи используют его, вводится специальный укрепляющий коэффициент, аналог феромонов.

Авторы алгоритма определяют укрепляющий коэффициент r=r(T,Mk) [2], как функцию от времени движения муравья, которое рассчитано относительно локальной модели трафика. Коэффициент r это безразмерная величина, r (0,1], используемая текущим узлом k как положительный укрепляющий коэффициент для узла f, из которого пришел Н-муравей B_d->s. Коэффициент r учитывает некоторое среднее число наблюдаемых величин и их дисперсии для расчета полезности времени движения T, такого что, чем меньше T, тем выше r. Вероятность P_fd' увеличивается за счет укрепляющего коэффициента следующим образом [2]:

Вероятности P_nd' для узла назначения d' других соседних узлов n получают неявно отрицательные укрепляющие коэффициенты с использованием нормализации. Т.е. их значения уменьшаются, так что сумма вероятностей остается равной 1 [2]:

5.4 Расчет укрепляющего коэффициента

Укрепляющий коэффициент является критической величиной, которая может быть определена с точки зрения трех аспектов:

1. пути должны получить увеличение вероятности их выбора пропорционально их полезности;
2. полезность это относительная мера, зависящая от условий трафика, которые могут быть вычислены с помощью значений модели M;
3. важно не отслеживать все осцилляции трафика.

В [2] предлагается два способа вычисления укрепляющего коэффициента r:

1. Самый простой способ это установить r=constant, Независимо от результатов, полученных муравьями, исследуемые пути будут вознаграждены одинаково. Очевидная проблема этого приближения является то, что хотя прибытие муравьев, следовавших по более длинным путям, происходит с задержкой, они в любом случае получат такой же эффект в маршрутных таблицах, что и муравьи, прошедшие более короткий путь. В экспериментах, проведенных авторами алгоритма, при использовании такого способа задания укрепляющего коэффициента, алгоритм продемонстрировали умеренно хорошую производительность.
2. Для получения лучших результатов коэффициент r можно определить как функцию от времени движения муравьев, и от параметров локальной модели трафика. Для вычисления укрепляющего коэффициента в [2] предлагается следующая формула:

   

W_best это лучшее время, полученное муравьем при движении по направлению к узлу d, в окне наблюдений W. Максимальный размер окна (максимально кол-во рассмотренных опытов до изменения значения W_best) устанавливается на основе коэффициента , который предсталяет собой весовой коэффициент, определяющий количество эффективных опытов, которые действительно влияют на оценку значения математического ожидания.

I_sup и I_inf это оценки границ доверительных интервалов математического ожидания (соответственно нижняя и верхня граница). I_inf устанавливается равным W_best, а , где , а коэффициент уровень уверенности [2].

Первое слагаемое в формуле для расчета укрепляющего коэффициента показывает отношение между текущим и лучшим временем движения агента. Это слагаемое корректируется вторым слагаемым, которое показывает, как сильно значение T отклоняется от I_inf относительно расширения доверительного интервала, т.е., учитывает постоянство в последних временах обхода. Коэффициенты с1 и с2 это весовые коэффициенты, определяющие важность каждого слагаемого. Первое слагаемое наиболее важно, в то время как второе - играет роль корректора. В работе [2] установлено, что поведение алгоритма довольно стабильно для значений с2 в пределах от 0.15 до 0.35. Весовые коэффициенты с1 и с2 в [2] соответственно установлены с1=0.7 и с2=0.3.

Алгоритм устойчив к изменениям значения , которое определяет уровень уверенности: изменяя уровень уверенности в пределах от 75% до 95%, производительность почти не меняется. Лучшие результаты были получены при значениях в пределах 75%-80% [2].

Окончательно, значение r преобразуется с использованием сжимающей функции s(x) [2]:

Сжатие значений r позволяет системе быть более чувствительной к определению наилучших (высоких) значение r, при этом иметь тенденцию к насыщению плохих (близких к 0) значение r: сжимается нижняя часть значений и расширяется их верхняя часть. Таким образом, выделяются хорошие результаты, а роль низких значений укрепляющего коэффициента понижается.

Коэффициент a/N_k в формуле для сжимающей функции определяет параметрическую зависимость сжатого значений укрепляющего коэффициента от количества |N|_k соседей укрепляемого узла k: чем больше количество соседей, тем больше укрепляющий коэффициент (см. рис. 5.3).

Рисунок 5.3 - Пример использования сжимающей функции для переменного количества соседних узлов

6. Результаты исследования поведения алгоритмов маршрутизации

На данный момент система ROUTING_SIMULATOR позволяет промоделировать два алгоритма маршрутизации: AntNet и OSPF. Целью сравнения двух алгоритмов было получение двух характеристик: пропускной способности (байт/сек) и потери пакетов (пакетов/сек).

Эксперименты проводились на сети с 8-ю узлами (см. рис. 6.1), пропускная способность линий связи которой равна 1 МБит/с. Для создания рабочей нагрузки, между всеми парами узлов сети открываются сессии передачи пакетов данных. Каждая сессия имеет скорость передачи (bit rate) 10⁵ байт/сек. Длина пакетов данных , которыми обмениваются узлы, составляет 512 байт.

Рисунок 6.1 - Простая компьютерная сеть

Моделирование поведения алгоритмов длилось 300 виртуальных секунд. На 100-й секунде моделирования происходит резкое изменение скорости передачи данных в сессии между 1-м и 6-м узлами с 10⁵ байт/сек на 1.4*10⁶ байт/сек, т.е. 1-й узел выступает в роли хот-спота [2]. Выключение хот-спота происходит на 200-ой секунде.

Для алгоритмов AntNet и OSPF получены графики для пропускной способности сети между 1-м и 6-м узлами и общей потери пакетов в сети.

Рисунок 6.2 - Графики пропускной способности (байт/сек) для алгоритмов AntNet и OSPF

Рисунок 6.3 - Потеря пакетов для алгоритмов AntNet и OSPF

Из рисунков 6.2 и 6.3 видно, что до включения хот-спота в узле №1 пропускная способность между 1-м и 6-м узлами для обоих алгоритмов одинакова и составляет 100000 байт/сек. При включении хот-спота пропускная способность и уровень потери пакетов резко возрастают. Для алгоритма OSPF эти характеристики со временем стабилизируются (перестают изменяться), вплоть до момента выключения хот-спота. Алгоритм AntNet, напротив, все время пытается изменить маршрутные таблицы для оптимизации работы сети. Вследствие этого пропускная способность для AntNet постоянно растет, а уровень потери пакетов - снижается.

Заключение

Маршрутизация играет важную роль в обслуживании коммуникационных сетей. При правильно организованной маршрутизации возможно оптимизировать такие важные показатели производительности сети как пропускная способность и задержка пакетов.

В результате проведенной работы реализовано два алгоритма маршрутизации - AntNet и OSPF. При исследовании поведения алгоритмов в одинаковых экспериментальных условиях было получено, что производительность алгоритма AntNet лучше, чем у OSPF. Для объективной оценки производительности AntNet необходимо сравнить его еще с некоторыми адаптивными алгоритмами маршрутизации, такими как BF, Q-R, PQ-R и SPF. Реализация этих алгоритмов планируется в дальнейших исследованиях.

Литература

1. Столлингс В. Современные компьютерные сети. 2-е изд. - СПб: Питер, 2003. - 783с.
2. Di Caro G., Dorigo M. AntNet: Distributed Stigmergetic Control for Communications Networks: Journal of Artificial Intelligence Research. - 1998. - №9 - pp. 317-365
3. Бертсекас Д., Галлагер Р., Сети передачи данных: Пер.с англ. - М.:Мир 1989. - 544с.
4. Schoonderwoerd R., Holland O., Bruten J., & Rothkrantz, L. Ant-based load balancing in telecommunications networks: Adaptive Behavior. - 1996. - №5(2), pp. 169-207.
5. Schoonderwoerd R., Holland O., & Bruten J. Ant-like agents for load balancing in telecommunications networks. In Proceedings of the First International Conference on Autonomous Agents: ACM Press. - 1997. - pp. 209-216.
6. Subramanian, D., Druschel, P., & Chen, J. Ants and reinforcement learning: A case study in routing in dynamic networks. In Proceedings of IJCAI-97, International Joint Conference on Artificial Intelligence: Morgan Kaufmann. - 1997. - pp. 832-838.
7. RFC 2328 (rfc2328) - OSPF Version 2 - http://www.faqs.org/rfcs/rfc2328.html
8. RFC 2453 (rfc2453) - RIP Version 2 - http://www.faqs.org/rfcs/rfc2453.html
9. Kaelbling, L. P., Littman, M. L., & Moore, A. W. Reinforcement learning: A survey: Journal of Artificial Intelligence Research. - 1996. - №4 - pp. 237-285.
10. Штовба С. Д. Муравьиные алгоритмы: Мастерская решений: Exponenta Pro. - 2003. -№4(4) - сс. 70-75.