*112227*

Телекоммуникационные системы и сети

Демишева Екатерина Дмитриевна

ГВУЗ «Национальный горный университет», Украина

Муравьиный алгоритм, его реализация, применение в сетях с пакетной передачей

Введение:

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

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

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

Муравьиный алгоритм:

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

Представьте себе фрагмент сети, изображенный на рис. 1. Буквами обозначены маршрутизаторы, а рядом с каждой линией связи указана ее метрика. Конкретные значения не балуют разнообразием, но они выбраны одинаковыми для того, чтобы проблему было проще понять. Очевидно, что, формируя маршрут от A к E, и RIP, и OSPF выберут путь AFGE. Маршрут через узлы B, C и D будет отвергнут, как более длинный. Теперь представим себе, что с узла H на узел I пересылаются большие объемы данных. Это приведет к тому, что пакет, переданный с A и адресованный E, будет поставлен в хвост длинной очереди на передачу сначала на узле F, а потом и на G. В сложившейся ситуации маршрут ABCDE оказался более предпочтительным, но используемые в настоящее время протоколы не позволяют обнаружить этот факт.

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

Рис 1.1

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

Рис 1.2

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

Муравьиные алгоритмы для сетей с пакетной передачей данных.

Алгоритм можно описать в следующем виде:

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

(1.1)

2. Во время движения к узлу-приемнику, агенты хранят память о пройденных путях и об обнаруженных состояниях трафика. Идентификатор каждого пройденного узла k и время, прошедшее с момента запуска муравья до момента достижения им k-го узла, заталкиваются в память муравья, имеющего структуру стека S_s->d(k).

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

(1.2)

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

(1.3)

Коэффициент 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. 
Результаты исследования поведения алгоритмов маршрутизации:

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

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

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

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

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

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

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

Вывод:

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

Литература

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. Schoonderwoerd R., Holland O., Bruten J., & Rothkrantz, L. Ant-based load balancing in telecommunications networks: Adaptive Behavior. - 1996. - №5(2), pp. 169-207.

4. 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.

5. 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.

6. Kaelbling, L. P., Littman, M. L., & Moore, A. W. Reinforcement learning: A survey: Journal of Artificial Intelligence Research. - 1996. - №4 - pp. 237-285.