Исследование алгоритмов маршрутизации в беспроводных IP-сетях

Вступление

Цели и актуальность

Цель работы – изучить алгоритмы маршрутизации в беспроводных сетях и, на их основе, разработать улучшенный алгоритм. Тема актуальна, благодаря быстрому развитию беспроводных сетей, постепенно вытесняющих проводные. в связи с такой тенденцией, по смежным темам было написано множество магистерских работ и статей как в ДонНТУ, так и в других вузах, в особенности - зарубежных. Часть этих работ представлена в разделе "Библиотека".

Новизна

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

Основное содержание работы

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

В первую очередь, будет промоделирован протокол AODV (Ad-hoc On-Demand Vector Routing[2]), использующий дистанционно-векторный алгоритм. Это реактивный протокол маршрутизации, устанавливающий маршрут до адресата по требованию (посредством отсылки пакетов RREQ). В AODV передача маршрутной информации (кроме сообщений приветствия) не ведётся, пока нет необходимости в установке или восстановлении маршрута.

Перед отправкой данных, узел посылает пакет RREQ (запрос маршрута) соседям через свою зону широковещания. Ближние узлы, в свою очередь, пересылают запрос своим соседям и так далее (см. рис.1), пока пакет с запросом не дойдет до получателя. При пересылке, промежуточные узлы делают отметку о предыдущем узле (таким образом, регистрируя свою часть маршрута), а также о начальном и конечном пунктах маршрута. В случае если промежуточный узел получит несколько одинаковых пакетов(что можно отследить по номеру запроса, выбираемому узлом так, чтобы не пересечься с остальными), то из них будет выбран пакет с наименьшим количеством прыжков(хопов), обеспечивая таким образом выбор наиболее оптимального маршрута.

Если промежуточный узел уже имеет маршрут к узлу назначения и флаг D(доставить до узла назначения) в пакете RREQ неактивен, он отвечает источнику пакетом RREP(или посылает RREQ получателю напрямую), подтверждая установку маршрута (и делая отметку у себя в таблице маршрутизации). Если флаг D активен, возможность использование уже известного маршрута игнорируется (так как топология сети со временем изменяется, этот маршрут мог стать неоптимальным, ненадежным или вовсе исчезнуть).

Для дополнительного подтверждения может использоваться пакет RREP-ACK, посылаемый источником по получении RREP (это может использоваться для проверки маршрута в сетях с ненадежной связью).

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

В протоколе использованы следующие методы борьбы с паразитным трафиком:

• Ограничение времени жизни пакета (TTL) до значения предполагаемого числа промежуточных узлов в сети;
• Ограничение частоты повторения посылки запроса RREQ, в случае разрушения маршрута (или неудачного поиска, к примеру, если на некоторое время маршрут до узла перестал существовать вообще как таковой). В этом случае источник ожидает время вдвое большее, чем было необходимо для установления маршрута.

Протокол обладает следующими преимуществами:

• Простота реализации;
• Отсутствие дополнительного трафика при пересылке данных;
• Низкие требования к ресурсам.

Недостатком протокола является большое время установки маршрута.

Протокол DSR (Dynamic Source Routing[1]), применяющийся в ячеистых(mesh) сетях, схож с AODV в том, что также формирует маршрут по требованию, посредством передачи запроса (реактивный протокол маршрутизации). Основное различие в том, что DSR накапливает информацию о маршруте не в таблицах маршрутизации узлов, а непосредственно в пакете запроса. Основной недостаток – значительное увеличение размера пакета при длинных маршрутах или адресах (в этом случае накопление адресов отключается, и используются непосредственно таблицы маршрутизации).

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

В магистерской работе планируется промоделировать беспроводную сеть, маршрутизируемую по модифицированному протоколу AODV и, возможно, mesh-сети с DSR.

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

Топология беспроводной сети (для i-го момента времени) обычно описывается графом. Поскольку большинство беспроводных сетей при передаче данных использует механизм подтверждений, связь между узлами (вершинами графа) - обычно двунаправленная. Соответственно ребра графа могут быть ненаправленными.

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

• выделенный канал – используется для однонаправленной передачи данных между парой узлов, при этом у других узлов в сети нет доступа к ресурсам канала;
• разделяемый канал – предназначен для всенаправленного обмена данными между несколькими узлами
• канал общего типа – может быть использован и как выделенный, и как разделяемый канал.

Для определения критериев эффективности обмена данными между узлами в сети рассмотрим этот процесс с точки зрения дискретной математики и теории множеств. Пусть некоторый узел i собирается передать своему соседу j некоторое сообщение. В этом случае узел i должен выбрать для передачи данных один из каналов k, удовлетворяющих условию:

где

То есть, подмножество k – это множество каналов связывающих эти два узла. Физически это подмножество может представлять собой набор незанятых другими узлами радиочастот(или полос радиочастот), на которых возможна связь между i и j. После освобождения одного из каналов этого подмножества (из вышеуказанной классификации следует, что канал может быть занят и другими узлами), узел переводит его в состояние «занят» (к примеру, начиная посылку преамбулы и фрейма). При этом данный канал не может быть использован ни одним из узлов кластера, в которые входят i и j (поскольку физически они разделяют один и тот же радиоэфир). Точнее, в кластере i (эфир в который этот узел может вещать по данному каналу) не может быть осуществлена передача, а в кластере j (эфир в котором этот узел может прослушивать данный канал) - прием.

Для многоканальной передачи данных отправка повторяется несколько раз, что, естественно, приводит к увеличению объема трафика, реально обслуженного сетью, в N+1 раз, где N – количество промежуточных узлов ретрансляторов в маршруте передачи сообщения.

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

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

где

Для сети, состоящей из одинаковых устройств, параметр T является постоянным для всех узлов и зависит, в основном, от длины пакета и пропускной способности канала связи.

Параметр ti зависит от интенсивности обслуженного каждого i-го трафика, поэтому для каждого узла имеет смысл вести еще один дополнительный параметр – интенсивность обслуженного трафика для кластера данного узла, или коэффициент использования разделяемого ресурса (ресурсов, в случае, если их несколько).»[3]

Моделирующее программное обеспечение (ПО)

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

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

В GUI запланирована реализация следующей функциональности:

Графический интерфейс моделирующего ПО

В GUI запланирована реализация следующей функциональности:

In GUI implementation of the following functionality is planned:

• Редактор графа (возможно, с импортом данных из XML-файла)
• Графики моделирования (отображают нагрузку на узлы, скорость передачи пакетов и т.д.)
• Возможность управления процессом моделирования(Пауза/Продолжить)
• Возможность изменения параметров и структуры графа во время моделирования (в режиме паузы)
• Возможность конфигурирования устройств (MAС-адрес, IP, и т.д.)
• Возможность выбора протокола маршрутизации
• Вывод формы с кратким описанием ТЗ.

Среда разработки моделирующего ПО

В качестве среды разработки была выбрана Eclipse(Java) так как:

• независима от платформы
• поддерживает ООП
• имеются внешние средства для реализации графов(к примеру - JGraph).

Планируемая структура ядра моделирующего ПО

In modeling software it is planned to implement following classes:

• Node – описывает узел(связанное устройство)
• Device – описывает устройство коммутации(параметры устройства, таблица связей, таблица маршрутизации)
  • WirelessDevice - устройство связи
  • WirelessRouter - маршрутизатор
• Packet – описывает пакет, передаваемый по сети (в частности, его статистические характеристики - количество пройденных хопов, время доставки, размер)
  • RoutingPacket – служебный пакет, предназначенный для установления маршрута
  • Hello – пакет приветствия (отсылается при активации узла, т.е. при добавлении его в сеть)
• Link – описывает связь (ребро) между узлами. Метод getLinkQuality() моделирует случайные изменения в пропускной способности канала
• Net – содержит список узлов сети и некоторые ее характеристики
• Packets – содержит список отслеживаемых пакетов и их общие характеристики.

Результаты

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

• Нагрузка на узлы
• Нагрузка на каналы
• Задержка при передаче пакетов

Заключение

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