Маршрутизация в ad-hoc сетях

В настоящее время сети передачи данных продолжают активно развиваться, в том числе все большее распространение получает такой их класс, как сети Ad hoc. Это одно- ранговые беспроводные сети передачи данных с переменной топологией и отсутствием четкой инфраструктуры, где каждый узел может выполнять функции маршрутизатора и принимать участие в ретрансляции пакетов данных. Подобные сети могут применяться во время военных действий, в структурах МЧС, в системах транспорта и различных сило- вых структурах. Пример структуры Ad hoc-сети изображен на рис. 1.

 

Рис.2 – Пример структуры Ad hoc-сети

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

 

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

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

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

3. Обеспечивать малое время построения маршрута в условиях постоянно изменяющейся топологии сети.

4. Обладать механизмами оперативного обнаружения разрыва маршрута и его восстановления.

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

6. Рассылать при функционировании как можно меньший объем служебной информации.

7. Обладать высокой масштабируемостью, т.е. обеспечивать высокую производительность сети при различных ее размерах.

8. Поддерживать QoS.

Существующие на данный момент протоколы маршрутизации можно классифицировать следующим образом.

По типу используемых для маршрутизации данных:

1) Топологические. Используют информацию о существующих сетевых соединениях между узлами сети.

 

 

 

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

По принципу работы:

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

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

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

По критерию определения оптимальности маршрута:

1) Протоколы вектора расстояния (англ. distance-vector, hop-count). Всегда считают оптимальным маршрут, содержащий наименьшее число хопов (ретрансляций пакета) между отправителем и адресатом.

2) Протоколы со сложной метрикой маршрутов или протоколы состояния каналов (англ. link-state). Используют комплексную оценку маршрутов по нескольким параметрам, в которые, помимо числа хопов, обычно входят задержка на доставку пакета, пропускная способность канала и др. По числу задействованных в маршрутизации уровней ЭМВОС:

1) Одноуровневые. Работают чисто на сетевом уровне, поэтому обладают универсальностью и сетевой прозрачностью.

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

По наличию поддержки нескольких маршрутов до одного адресата:

1) Однопутевые (англ. single-path). При обработке информации о топологии сети данные протоколы выбирают лишь один, наиболее оптимальный, маршрут до адресата и заносят его в свою таблицу маршрутизации.

2) Многопутевые (англ. multi-path). В отличие от однопутевых, заносят в таблицу маршрутизации два или несколько наиболее оптимальных маршрутов

 

до адресата. В случае обнаружения разрушения основного маршрута данные протоколы просто считывают из таблицы запасной, а не инициализируют процедуру повторного построения маршрута. Также при обнаружении перегрузки сети по основному маршруту многопутевые протоколы могут перераспределять часть нагрузки на резервные. Каждый класс протоколов потенциально имеет свои преимущества и недостатки при использовании в условиях мобильных Ad hoc-сетей. Например, проактивные протоколы обладают явным преимуществом перед реактивными во времени построения маршрута. У проактивных протоколов этот процесс, по сути, происходит заранее, и требуется лишь считать маршрут из таблицы, тогда как реактивным протоколам необходимо разослать широковещательный запрос и дождаться подтверждения от адресата. Однако проактив- ным протоколам необходимо постоянно осуществлять широковещательные рассылки, на что может расходоваться значительная доля пропускной способности сети, особенно в условиях крупных сетей с высокой мобильностью узлов. Однако приведенные выше рассуждения являются сугубо абстрактными и оторванными от конкретных практических реализаций. Адекватное сравнение протоколов с чисто теоретических позиций затруднено тем, что на процесс передачи данных в Ad hoc-сетях оказывает влияние большое число различных факторов, многие из которых носят случайных характер и слабо поддаются строгому математическому анализу. Поэтому основным инструментом сравнительного анализа протоколов маршрутизации при работе в Ad hoc-сетях является имитационное моделирование, которое в целях экономии времени и средств первоначально осуществляется посредством компьютерных программ-симуляторов, без применения реального оборудования. Симуляторы моделируют работу всех уровней ЭМВОС. Для сетей радиосвязи присутствуют модель радиоканала, учитывающая распространение радиоволн используемого частотного диапазона, а также модели, описывающие пространство. Совокупность вышеперечисленных свойств симулятора определяет адекватность проводимых на нем экспериментов и достоверность получаемых при этом результатов. В настоящий момент усилиями исследователей со всего мира были созданы следующие протоколы маршрутизации, наиболее часто используемые в Ad hoc-сетях [5-7]:

1) AODV (Ad hoc On-Demand Distance Vector). Реактивный протокол маршрутизации, разработанный для использования в сетях различного размера. Представляет собой комбинацию двух протоколов: реактивного DSR и проактивного DSDV, от которого он на- следует концепцию hello-сообщений. Это служебные сообщения, рассылаемые на рас- стояние одного хопа, которые служат для поддержания узлом актуального списка своих соседей. Это в итоге позволяет несколько ускорить процесс рассылки запросов на построение маршрута. Протокол описан в документе «IETF Request for Comments 3561» от июля 2003 г. Одна из модификаций протокола, адаптированная для работы с адресами МАС- уровня и метриками маршрутов, под названием HWMP (Hybrid Wireless Mesh Protocol) используется в стандарте IEEE 802.11s.

2) DSR (Dynamic Source Routing). Реактивный протокол, разработанный специально для использования в небольших (диаметром в 5-10 хопов) Ad hoc-сетях с умеренной мо-бильностью узлов. Описан в документе «IETF Request for Comments 4728» от февраля 2007 г.

3) OLSR (Optimized Link-State Routing). Проактивный протокол, который является попыткой адаптации классического LSR (Links State Routing) к использованию в услови- ях беспроводных сетей. Основным нововведением является концепция многоточечных ретрансляторов, которая оптимизирует процесс широковещательной рассылки, значительно сокращая объемы рассылаемой информации. Протокол OLSR описан в документе «IETF Request

 

for Comments 3626» от октября 2003 г. Одна из модификаций протокола под названием RA-OLSR (Radio Aware-OLSR) используется в стандарте IEEE 802.11s.

4) OSPF MANET. Под этим общим названием объединяют несколько протоколов, являющихся попытками адаптации классического проактивного протокола OSPF (Open Shortest Path First) к использованию в условиях беспроводных сетей. Варианты OSPF MANET-MPR и OSPF MANET-OR/SP, подобно OLSR, используют концепцию многоточечных ретрансляторов, а OSPF MANET-MDR придерживается традиционных алгоритмов, заложенных в OSPF. Все протоколы OSPF MANET описаны в рамках соответствующих интернет-драфтов.

5) FSR (Fisheye State Routing). Иерархичный проактивный протокол, целью создания которого была попытка уменьшить объем рассылаемой по сети служебной информации за счет использования концепции «рыбьего глаза», где каждый узел сети осуществляет широковещательные рассылки до узлов с различной частотой: чем дальше находится узел, тем реже ему осуществляется рассылка. Протокол был разработан на базе фирмы Lucent Technologies в 2000 г.

6) LANMAR (Landmark routing protocol). Гибридный протокол, который объединяет узлы в группы по принципу их склонности к совместному передвижению в качестве единой группы. В каждой из групп один узел динамически назначается так называемой реперной точкой, которая служит своеобразным «маяком» при пересылке пакетов между узлами различных групп. Протокол был разработан на базе Калифорнийского универси- тета в сотрудничестве с Rockwell Scientific Company в 2002 г.

7) ZRP (Zone Routing protocol). Протокол, разработанный для использования в круп- ных мобильных Ad hoc-сетях с небольшой плотностью размещения узлов и реализующий классическую концепцию гибридной маршрутизации. Разработан в Корнеллском университете в 2002 г. [4]

ПРАКТИЧЕСКАЯ ЧАСТЬ

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

№ Варианта	Протокол	№ Варианта	Протокол
1.	RIP	15.	IDRP
2.	IGRP	16.	IS-IS level 3
3.	BGR	17.	CIDR
4.	EIGRP	18.	RIPng
5.	AODV	19.	RIP IP
6.	IS-IS	20.	RIP IPX
7.	OSPF	21.	IPX
8.	NLSP	22.	HELLO
9.	HSRP	23.	RIP
10.	CARP	24.	IGRP
11.	OLSR	25.	BGR
12.	TBRPF	26.	EIGRP
13.	EGP	27.	AODV
14.	BGP	28.	IS-IS

 

 

СПИСОК ЛИТЕРАТУРЫ

1. Организация научно-педагогической практики студентов, обучающихся по магистерским программам направления 210700 «Инфокоммуникационные технологии и системы связи» Методические рекомендации / Сост: В.Н. Дмитриев. Астрахань: Изд-во Астрахан. гос. техн. ун-та, 2013. - 42 с.
2. Интернет ресурс Cisco: http://www.cs.vsu.ru/~kas/doc/exe/cisco/CCNA05.pdf

3. Гольдштейн Б. С. Сигнализация в сетях связи. — М.: Радио и связь, 1997. —

4. Статья. В.М. Винокуров, А.В. Пуговкин, А.А. Пшенников, Д.Н. Ушарова, А.С. Филатов Маршрутизация в беспроводных мобильных Ad hoc-сетях. https://journal.tusur.ru/ru/arhiv/2-1-2010/marshrutizatsiya-v-besprovodnyh-mobilnyh-ad-hoc-setyah