Авторы: Rakesh Kumar, Mahesh Kumar
Автор перевода: Чабанный А.А.
Источник: Global Journal of Computer Science and Technology / Vol. 10 Issue 11 (Ver. 1.0) October 2010. - pp. 8 - 12
Аннотация
Rakesh Kumar, Mahesh Kumar. Исследование применения генетических алгоритмов для оптимизации кратчайшего пути в сетях передачи данных. Интернет сервис провайдеры (Internet Service providers, ISPs) являются строительными блоками для Интернета. В связи с огромным спросом на Интернет различных бизнес сообществ и отдельных лиц, ISPs пытаются удовлетворить растущий спрос на передачу трафика улучшая использования имеющихся ресурсов и применением новых технологий. Маршрутизация пакетов может повлиять на использование сетевых ресурсов. Пакет отправляется от источника к получателю вдоль пути. Внутридоменный протокол маршрутизации Open Shortest Path First (OSPF) является наиболее часто используемым протоколом. Был реализован генетический алгоритм для нахождения множества оптимальных маршрутов, по которым передается трафик от источника к получателю.
Ключевые слова – Генетический алгоритм, Хромосома, Кроссинговер, Мутация, Маршрутизация.
I. ВВЕДЕНИЕ
Маршрутизация в сетях передачи данных это процесс, который обеспечивает передачу пакетов от источника к получателю с учетом минимальной стоимости (задержка на передачу, обработка и задержка в очереди, пропускная способность, нагрузка, джиттер, надежность и т.д.). Маршрутизация в больших сетях является сложной, поскольку пакет проходит много потенциальных промежуточных узлов пока он достигнет узла назначения. Таким образом алгоритм маршрутизации должен получать и распространять информацию о состоянии сети. Он должен генерировать возможные маршруты между узлами и передавать трафик по выбранному пути и также давать высокую производительность. Маршрутизация в сочетании с контролем перегрузки и контролем доступа определяют производительность сети. Веса связей в сети назначаются операторами сети. Чем меньше вес, тем больше вероятность, что трафик будет направляться по этому каналу [BLU00]. Когда происходит передача или прием данных через Интернет информация делится на маленькие кусочки называемые пакетами или дейтаграммами. Заголовок содержит необходимую информацию для передачи, такую как IP адрес источника и получателя и т.д. Данные передаются по линиям связи между маршрутизаторами в Интернет. Когда пакет приходит на маршрутизатор, входящий пакет помещается в очередь в ожидании обработки. Маршрутизатор читает заголовок пакета, извлекая IP адрес узла назначения, и определяет лучший путь для передачи пакета. Алгоритм маршрутизации должен иметь общие цели и стратегии маршрутизации, динамически переконфигурировать маршруты, а также опираться на имеющуюся информацию. Он также должен удовлетворять требованиям качества обслуживания. Для достижения этих требований предлагались следующие методы: эволюционные алгоритмы, алгоритмы поведения насекомых и когнитивные пакетные сети. Алгоритмы поведения насекомых и когнитивные пакетные сети используют вероятностную таблицу маршрутизации и позволяют пакетам самостоятельно исследовать сеть, сообщая о топологии сети и производительности. В генетических алгоритмах популяция ассоциируется с каждым узлом для решения проблемы.
II. Маршрутизация в сети
Маршрутизация это процесс построения маршрутов между узлами в сети. Существует два типа маршрутизации – статическая и динамическая. При статической маршрутизации происходит предварительное построение маршрутов на основе определенных факторов, и записываются в таблицу маршрутизации. Все пакеты между двумя любыми узлами передаются по одному и тому же пути. Когда топология сети изменяется, то путь между двумя узлами также изменяется, и статические маршруты становятся непригодными. При динамической маршрутизации маршруты не хранятся, но строятся когда это необходимо. Новые маршруты строятся, основываясь на таких факторах, как трафик, коэффициент использования линии, пропускная способность, джиттер, задержка и т.д., которые позволяют получить максимальную эффективность. Маршрутизация может быть централизованной или распределенной. В случае централизованной маршрутизации, только центральный узел строит маршруты между любыми двумя парами узлов сети. Централизованная маршрутизация не является адекватной для IP сетей так как для этого необходимо собрать информацию о всей сети перед вычислением маршрутов, что является очень сложной задачей. При распределенной маршрутизации, каждый узел строит маршруты независимо. Также маршрутизация классифицируется по типу найденного пути – оптимальный путь (глобальная маршрутизация) и кратчайший путь (локальная маршрутизация) [CAUOO]. Также протоколы маршрутизации делятся на алгоритмы вектора расстояния и алгоритмы состояния канала. Топология сети может изменяться с ростом числа узлов в сети или отказом узлов. Это изменение топологии должно быть отражено в таблице маршрутизации, которая, в свою очередь, помогает протоколам маршрутизации строить оптимальные маршруты с учетом текущего состояния сети. К протоколам маршрутизации в проводных сетях относят – Routing Information Protocol (RIP), Interior gateway routing protocol (IGRP), Open source shortest path first (OSPF) и Border gateway protocol (BGP). Протокол OSPF является протоколом состояния каналов, который использует алгоритм кратчайшего пути для построения маршрутов. Он используется в IP сетях. Enhanced Interior Gateway Routing Protocol (EIGRP) представляет собой расширенную версию протокола вектора расстояния, который минимизирует влияния изменения топологии и эффективным использованием пропускной способности, а также вычислительной мощности маршрутизатора. EIGRP использует неравную балансировку. Маршрутизатор хранит таблицу маршрутизации на каждом, которая содержит всех соседей данного узла [CAUOO]. Он также хранит маршрут к другим узлам, а также число переходов для достижения этих узлов. Маршрутизатор решает, какого соседа использовать для передачи конкретного узла назначения.
III. Проблема кратчайшего пути
Проблема кратчайшего пути заключается в нахождении минимальной длины (стоимости) пути между любой парой узлов. Алгоритм Дейкстры рассматривается как наиболее эффективный метод для вычисления кратчайшего пути в IP сетях. Но когда сеть очень большая, то он становится неэффективным, так как необходимо повторять многие расчеты [BIL08]. Также он не может быть решен за разрешенное время [YIN06].
IV. Генетический алгоритм
Генетический алгоритм (ГА) представляет собой особый вид стохастического алгоритма поиска, который использует биологическую эволюцию для решения проблемы. ГА работает в пространстве поиска называемом популяцией [GOL89]. Каждый элемент в популяции называется хромосомой. ГА начинается случайным выбором множества допустимых решений из популяции. Каждая хромосома представляет собой решение. Для каждой хромосомы оценивается ее фитнесс функция, и эта функция представляет качество решения. ГА использует адаптивный эвристический метод поиска, который находит набор лучших решений в данной популяции. Новые потомки генерируются/эволюционируют при помощи операций селекции, кроссинговера и мутации над хромосомами. Наиболее подходящие хромосомы перемещаются в следующее поколение. У слабых кандидатов меньше шансов попасть в новое поколение. Это потому, что ГА базируется на принципах теории эволюции Дарвина, которая утверждает, что «выживают лучшие». Этот процесс повторяется, пока хромосом имеет лучшее значение для данной проблемы [LAU91]. Подытоживая можно написать, что средняя приспособленность популяции увеличивается на каждой итерации, так что, повторяя этот процесс итерационно, можно найти лучшее решение. ГА был широко изучен во многих областях техники. ГА предоставляет альтернативные методы решения задач, которые трудно решить с помощью традиционных методов. ГА можно применять для нелинейного программирования, таких задача как задача коммивояжера, минимального остового дерева, задачи календарного планирования и многое другое.
1) Особенности генетического алгоритма
- Наиболее важная особенность ГА является то, что они параллельны по природе. Они исследуют пространство решений в нескольких направлениях одновременно. ГА очень хороши для решения задач в которых пространство решений огромно и время поиска решения очень велико.
- ГА хорошо справляются со сложными задачами. Если функция не является непрерывной, зашумленной, со временем изменяется или имеет много локальных оптимумов, то ГА дает лучший результат [VIJ08].
- ГА обладает способностью решать задачи не имея о них информации (вслепую). Производительность ГА зависит от способа представления, оценки фитнесс функции и других параметров, таких как размер популяции, вероятность кроссинговера и мутации, а также отбора.
2) Постановка проблемы
Рассматриваемая сеть представляется в виде связанного графа G=(V,E) с N узлами. Оптимизируется метрика стоимости пути. Общая стоимость представляет собой сумму стоимостей всех хопов маршрута. Цель найти путь с наименьшей суммарной стоимостью между источником Vsrc и получателем Vdest, где Vsrc и Vdest принадлежат V. В данной работе представлен эффективный алгоритм маршрутизации использующий ГА.
А. Инициализация таблицы маршрутизации
Модуль, используемый для создания всех возможных путей от данного узла ко всем остальным узлам в сети. Создается n
случайных путей (хромосом). Эти n
путей определяют размер популяции. Эти хромосомы формируют первое поколение.
В. Поиск оптимального пути
В этом модуле осуществляется поиск оптимального пути с помощью генетического алгоритма. На вход этого модуля подается множество сгенерированных путей. Каждый путь называется хромосомой. Размер популяции равен m
:
(а) Вычисляется фитнесс функция каждой хромосомы. Фитнесс функция хромосомы вычисляется следующим образом: Fitness = no of hops in path * 10 – total cost of path. Количество хопов показывает число промежуточных узлов в маршруте, а общая стоимость представляет собой сумму стоимостей всех хопов маршрута.
(b) Выбор двух лучших хромосом родителями (используется рулеточный отбор)
(c) Выполнить кроссинговер с вероятностью 0,7
(d) Выполнить мутацию с вероятностью 0,01
(e) Поместить детей в популяцию и заменить худшие хромосомы с наихудшей фитнесс функцией.
(f) Если маршрут не найден повторить шаги i – vi.
Если (критерий прекращения поиска достигнут) { Хранить найденные пути в течении времени t; передать данные получателю через выбранный путь}.
(g) Обновить маршруты через время t, чтобы обновить текущее состояние сети.
С. Отбор
Это особенность ГА – отбор родителей в следующее поколение. В данной работе используется рулеточная селекция. В этом методе особи выбираются пропорционально значению приспособленности. Также есть другие методы турнирная селекция, селекция на основе элитаризма и т.д.
D. Кроссинговер
Оператор кроссинговера объединяет под части двух родительских хромосом и производит потомство, которое содержит генетический материал со стороны обоих родителей. Наиболее часто используется два вида кроссинговера, а именно одноточечный и многоточечный. При одноточечном кроссинговере выбирается одна точка обмена, а при многоточечном кроссинговере больше чем одна точка. Одноместный метод кроссинговера прост; он имеет некоторые проблемы, такие как формирование циклов, когда используется для поиска маршрутов. Следовательно, необходимо использовать некоторые расширенные методы многоточечного кроссинговера для устранения циклов. Одни из продвинутых методов многоточечного кроссинговера Partially Mapped Crossover (PMX), Cycle crossover (CX) and Order crossover (OX) [GOL98, SIV08]. В статье рассматриваются кроссинговер PMX. В Partially Matched Crossover [SIV08], две строки равны, а две точки кроссинговера выбираются случайно.
Рассмотри две строки:
Parent A 4 8 7 | 3 6 5 | 1 10 9 2
Parent B 3 1 4 | 2 7 9 | 10 8 6 5
После случайного выбора двух точек кроссинговера включается механизм PMX и происходит обмен частями хромосом между двумя родителями в результате чего получается два новых потомка.
Child A 4 8 6 | 2 7 9 | 1 10 5 3
Child B 2 1 4 | 3 6 5 | 10 8 7 9
Каждый потомок содержит частичную информацию о родителях. Полученных потомков необходимо проверить на правильность маршрута. Если маршруты действительны, то вычисляется их фитнесс функция. Если же маршруты недействительны то они отбрасываются.
Е. Мутация
Оператор кроссинговера может привести к вырождению популяции. Для избегания вырождения популяции используется оператор мутации. Мутация может быть побитовая перестановка, инверсия, вставка, взаимный обмен и т.д. [AUL06]. В работе используется метод вставки. В случае использования мутации узел вставляется в случайное место в строке. Это связано с тем, что в результате кроссинговера в оптимальном маршруте может быть удален узел. Используя вставку, узел может быть возвращен. После операции мутации потомки полученные в результате мутации должны быть проверены таким же образом, как и при кроссинговере.
F. Критерий прекращения поиска
Критерий прекращения поиска определяет, когда необходимо остановить поиск. Максимальное число поколений, никаких изменений в фитнесс функции считается как критерий прекращения поиска. В качестве критерия было выбрано максимальное количество итераций (скажем 1000). Второй критерий остановки это определенный уровень фитнесс функции.
Рисунок 1 – Пример топологии сети
В таблице 1 стоимость 999 показывает, что между узлами нет прямой связи. В ходе выполнения алгоритма только линии с малыми значениями используются для построения маршрута.
Таблица 1 – Стоимость линии связи
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 999 | 5 | 3 | 7 | 999 | 999 |
| 2 | 5 | 999 | 999 | 3 | 5 | 999 |
| 3 | 3 | 999 | 999 | 3 | 999 | 999 |
| 4 | 7 | 3 | 3 | 999 | 999 | 999 |
| 5 | 999 | 5 | 999 | 999 | 999 | 3 |
| 6 | 999 | 999 | 999 | 2 | 3 | 999 |
V. Результаты
В данной работе используется сеть с 6 узлами. Создается 15 случайных хромосом, из которых только 10 лучших образуют первое поколение. На каждой итерации хромосомы проверяются, и наилучшая хромосома переходит в новое поколение. На каждой итерации значение фитнес функции для хромосом улучшается. Сгенерировано 15 случайных хромосом
| Chromosome | Delay | Fitness |
| 1 4 2 5 6 3 | 18 | 32 |
| 1 2 5 6 4 3 | 18 | 32 |
| 1 4 6 5 3 2 | 12 | 18 |
| 1 2 4 3 5 6 | 11 | 19 |
| 1 2 4 3 6 5 | 11 | 19 |
| 1 2 5 4 3 6 | 10 | 10 |
| 1 4 2 3 5 6 | 10 | 10 |
| 1 4 6 3 5 2 | 9 | 11 |
| 1 2 4 5 3 6 | 8 | 12 |
| 1 2 3 4 5 6 | 5 | 5 |
| 1 2 3 6 4 5 | 5 | 5 |
| 1 2 6 4 5 3 | 5 | 5 |
| 1 2 6 4 3 5 | 5 | 5 |
| 1 3 5 6 4 2 | 3 | 7 |
| 1 6 3 4 5 2 | 0 | 0 |
Поколение 1
| Chromosome | Delay | Fitness | Nodes visited |
| 1 4 2 5 6 3 | 18 | 32 | 5 |
| 1 2 5 6 4 3 | 18 | 32 | 5 |
| 1 4 6 5 3 2 | 12 | 18 | 4 |
| 1 2 4 3 5 6 | 11 | 19 | 4 |
| 1 2 4 3 6 5 | 11 | 19 | 4 |
| 1 2 5 4 3 6 | 10 | 10 | 3 |
| 1 4 2 3 5 6 | 10 | 10 | 3 |
| 1 4 6 3 5 2 | 9 | 11 | 3 |
| 1 2 4 5 3 6 | 8 | 12 | 3 |
| 1 2 3 4 5 6 | 5 | 5 | 2 |
Поколение 2
| Chromosome | Delay | Fitness | Nodes visited |
| 1 3 4 2 5 6 | 17 | 33 | 5 |
| 1 3 4 6 5 2 | 16 | 34 | 5 |
| 1 4 6 5 3 2 | 12 | 18 | 4 |
| 1 2 4 3 5 6 | 11 | 19 | 4 |
| 1 2 4 3 6 5 | 11 | 19 | 4 |
| 1 2 5 4 3 6 | 10 | 10 | 3 |
| 1 4 2 3 5 6 | 10 | 10 | 3 |
| 1 4 6 3 5 2 | 9 | 11 | 3 |
| 1 2 4 5 3 6 | 8 | 12 | 3 |
| 1 2 3 4 5 6 | 5 | 5 | 2 |
Мы взяли размер популяции 10 для первого поколения. Отобрав хромосомы на основе рулеточной селекции и применили к ним ГА операторы. После того как все маршруты от источника 1 ко всем остальным узлам построены они отображаются. Пусть узлом назначения будет узел 6. Ниже приведено множество путей от узла 1 к узлу 6. Оптимальный маршрут проходит через узлы 1, 3. 4 и 6 с задержкой равной 8.
Таблица 2 – Маршруты к узлу получателю 6
| Source | Destination | Delay | Route |
| 1 | 6 | 13 | 1 2 5 6 |
| 1 | 6 | 10 | 1 2 4 6 |
| 1 | 6 | 9 | 1 4 6 |
| 1 | 6 | 18 | 1 4 2 5 6 |
| 1 | 6 | 8 | 1 3 4 6 |
VI. ЗАКЛЮЧЕНИЕ
В данной работе использовался ГА для маршрутизации пакетов в сетях с коммутацией пакетов. Они исследуют пространство решений одновременно в нескольких направлениях. ГА очень хорошо подходит для решения задач, в которых пространство решений огромно, а также время необходимое для нахождения решения велико. Поскольку размер сети может увеличится то возможные решения для передачи данных между двумя узлами также может увеличиться. Добавление нескольких новых узлов в сеть увеличивает пространство поиска экспоненциально. Таким образом, ГА хорошо подходит для решения задачи маршрутизации, так как он исследует пространство решений одновременно в нескольких направлениях, что позволяет с меньшей вероятностью попасть в локальный оптимум. ГА позволяет решить проблему не имея предварительных знаний о ней. ГА Эффективность ГА зависит от способа формирования хромосом, вычислении фитнес функции, размера популяции, частоте кроссинговера, вероятности мутации и метода отбора. Предложенный алгоритм вначале создает первоначальную популяцию, вычисляет фитнес функцию, создает новую популяцию, используя генетические операторы, и прекращает поиск по достижению критерия останова. Текущая работа может быть улучшена с помощью более интеллектуального заполнения таблицы маршрутизации и использования лучших операторов кроссинговера, мутации и поддержки балансировки нагрузки.