Назад в библиотеку

Классификация методов многопутевой маршрутизации

Авторы: В.П. Шувалов, И.Ю. Вараксина
Источник: Шувалов В. П., Вараксина И. Ю. Классификация методов многопутевой маршрутизации // T-Comm. № 1. 2014. С. 29–32.

Аннотация

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


Разработке методов и протоколов маршрутизации посвящено множество научных работ. Немалый интерес также вызывает и классификация этих методов. Классификация многопутевой маршрутизации в беспроводных ad-hoc сетях достаточно полно представлена в работе [18]. Анализ математических моделей для решения задач многопутевой маршрутизации рассмотрен такими авторами, как Поповский В.В., Лемешко А.В. и др. в статье [16]. Общая классификация методов маршрутизации без разделения по количеству путей представлена Новиковым С.Н. в работе [17].

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

Как в однопутевой маршрутизации, так и в многопутевой выделяют два класса алгоритмов поиска путей: статические [2], [6] и динамические (адаптивные) [1], [3], [4], [5] алгоритмы. Принципиальная разница между ними — в степени учета изменения топологии и нагрузки сети при решении задачи выбора маршрута.

Для получения представления о проработанности предметной области выполним статистическое исследование количества статей по критерию «балансировка нагрузки в сети SDN» в поисковойсистеме Google Scholar. Полученная закономерность распределения публикаций по годам представлена на рисунке 1.

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

Динамические протоколы основаны на лавинных алгоритмах маршрутизации и алгоритмах маршрутизации от источника и способны динамически реагировать на изменения топологии сети. Одним из таких протоколов является Ad hoc On Demand Distance Vector (AODV) [10].

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

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

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

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

Гибридные протоколы работают по принципам дистанционно-векторных протоколов, но строят таблицы маршрутизации, как протоколы состояния линии. Метрики, используемые протоколами маршрутизации:

Немаловажным фактором при выборе метода маршрутизации является логическая топология сети. При таком подходе удачным решением являются графовые модели и использование соответствующих алгоритмов поиска кратчайших путей. Они являются статическими и обеспечивают предварительное резервирование каналов. В основу графовых (графо-комбинаторных) алгоритмов положено математическое описание телекоммуникационных сетей в виде ориентированного или неориентированного графа с последующим использованием комбинаторных алгоритмов поиска множества кратчайших путей между заданными парами узлов (вершин) сети. К таким методам можно отнести алгоритмы, описанные в работах [1], [2], [3], [4], [5]. В указанных работах обычно используются классические алгоритмы Дейкстры, Беллмана-Форда, Шуурбалле и других для поиска кратчайших маршрутов.

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

Ко второй группе можно отнести, так называемые, потоковые методы [10], [11], [12]. Потоковые модели, в свою очередь, одновременно с расчетом множества искомых путей формализуют решение задачи распределения трафика пользователей по этим путям.

Для решения задач многопутевой маршрутизации средствами потоковых моделей можно выделить [16]:

С точки зрения резервирования существуют алгоритмы, в которых выделяется дополнительный резервный канал. При этом этот канал может быть совместно используемым с другой группой путей (shared-link), либо же относиться только к одной группе. Данное условие позволяет управлять коэффициентом готовности пути для обеспечения требуемых гарантий качества обслуживания. В частности, реализация идеи выделения отдельного резервного канала предложена в работах [1], [5]. Однако, основным преимуществом многопутевой маршрутизации является отсутствие холодного резерва и использование всех путей с оптимальным распределением нагрузки по ним. Поэтому наибольшее распространение все же имеют методы без резервирования. В таких алгоритмах выбранные пути обеспечивают саморезервирование и не требуют выделения дополнительных ресурсов. Анализ трех описанных подходов (без резервирования, назначенное (холодное)резервирование и совместно используемые резервные каналы) приведен в [9].

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

Взвешенная балансировка нагрузки предполагает расчет некоторых метрик, на основании которых найденным путям присваиваются коэффициенты распределения трафика. И в случае отказа одного или нескольких путей данные метрики учитываются при перераспределении трафика с отказавшего пути [15]. Как правило, в таких алгоритмах используется одна метрика, т.е. один критерий, которому должны удовлетворять найденные пути. Например, полоса пропускания, или значение задержки. Многокритериальные подходы, учитывающие сразу несколько параметров при распределении нагрузки и поиске оптимальных маршрутов, предложены в [19], [20]. При этом обеспечивается большая гибкость с точки зрения удовлетворения требованиям QoS, но значительно возрастает сложность алгоритма и время расчета маршрута. Поэтому многокритериальная маршрутизация используется обычно в алгоритмах статической маршрутизации. Другим протоколом, использующим сразу несколько метрик для поиска маршрутов и балансировки трафика, является EIGRP, разработанный компанией Cisco [22].

Рис. 1. — Обобщенная классификация методов многопутевой маршрутизации

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

В таком случае промежуточным узлам остается лишь осуществлять пересылку пакета без дополнительной обработки и построения своей таблицы маршрутизации. Недостатком данной технологии является плохая масштабируемость. Так как с увеличением количества узлов в сети, также увеличивается размер заголовка пакета. При использовании пошаговой маршрутизации источник передает па кет на промежуточный узел, а не строит сразу весь путь до получателя. В свою очередь, промежуточный узел уже направляет пакет к получателю. Это, так называемая, двухфазная маршрутизация, используемая в основе методик, изложенных в работах [13], [14]. В основе указанных алгоритмов лежит балансировка нагрузки по Валианту (Valiant Load Balancing) [21]. Пошаговая маршрутизация применяется в больших масштабируемых сетях.

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

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

Заключение

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

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

Список использованной литературы

1. Sheng Huang, Biswanath Murkherejee. Adaptive Reliable Multi-Path Provisioning in WDM Networks. / in Proc. of IEEE ICC — Beijing, China, 2008. Pр. 5300-5304.
2. Smita Rai, Omkar Deshpande, Canhui (Sam) Ou, Charles U. Martel, and Biswanath Mukherjee.Reliable Multi-Path Provisioning for HighCapacity Backbone Mesh Network// IEEE/ACM Transactions on Networking, 2007. — Vol 15, No4. Pр. 803-812.
3. Ananya Das, Charles Martel, Biswanath Mukherjee, and Smita Rai. New Approach to Reliable Multipath Provisioning / Optical Communication Networks, 2011. — Vol. 3, No.1. Pр. 95-103.
4. Ananya Das, Charles Martel, Biswanath Mukherjee. Partial-Protection Approach Using Multipath Provisioning / In Proc. of the 2009 IEEE international conference on Communications. — IEEE Press Piscataway, NJ, USA, 2009. Pр. 1256-1260.
5. Lei Song, Biswanath Mukherjee. On the Study of Multiple Backups and Primary-Backup Link Sharing for Dynamic Service Provisioning in Survivable WDM Mesh Networks / IEEE Journal on selected areas in Telecommunication, 2008. Vol. 26, No6. Pр. 84-91.
6. Lena Wosinska. Connection Availability in WDM Mesh Networks with Multiple Failures / ICTON, 8th International Conference on Transparent Optical Networks. — Nottingham, United Kingdom, 2006. Pр. 126-129.
7. Matin Bagherpour, Oivind Kure. A Mixed Integer Programming Model for Multicast Routing with Multipath Delay Jitter Reduction / ICUMT, International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT'10). — Moscow, Russia, 2010. Pр. 504-510.
8.Yang Junlong, Yu Hewei. Optimizing Multi-Path Routing by Avoiding Key Nodes / In Proc. of IC-BNMT, 2009. Pр.48-51. 9. Jing Zhang, Keyao Zhu, Hui Zang, Norman S. Matloff, Biswanath Mukherjee. Availability-Aware Provisioning Strategies for Differentiated Protection Services in Wavelength-Convertible WDM Mesh Networks / IEEE/ACM TRANSACTIONS ON NET-WORKING, 2007. — Vol.15, No. 5. Pр.1177-1190.
10. Canfeng Chen Weiling Wu Zheng Li. Multipath Routing Modeling in Ad Hoc Networks / In Proc. of IEEE Globecom. — St. Louis, Missouri, USA, 2005. Pр. 2594-2598.
11. Cai Ling, Jinkuan Wang, Cuirong Wang, Xu Peng. Load Balancing Algorithm Based on Time Series Prediction of Packet Loss / 4th IEEE Conference on Industrial Electronics and Applications (ICIEA) — Xian, China, 2009. Pр.145-149.
12. Shaohua Liu, Xu Zhang, Junsheng Yu, Yinghui Liu, Xiaodong Chen. A Dynamic Traffic Distribution Strategy for Multipath Routing / In Proc.of the 7th international conference on Information, communications and signal processing ICICS'09. — NJ, USA. — IEEE Press Piscataway, 2009. Pр.1256-1260.
13. Rui Zhang-Shen, Nick McKeown. Designing a predictable Internet Backbone Network with Valiant Load-Balancing / In Proc. of 13th IEEE International Workshop on Quality of Service (IWQoS). — Passau, Germany, 2005. Pр. 178-192.
14. Rui Zhang-Shen, Nick McKeown. Designing a Fault-Tolerant Network Using Valiant Load-Balancing / 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies. — Phoenix, AZ, USA: IEEE INFOCOM, 2008. Pр. 2360-2368.
15. Шувалов В.П., Селянина И.Ю. Методика обеспечения отказоустойчивости в мультисервисных сетях связи // Проблемы информатики. №2(14),2012. — C. 55-62.
16. Поповский ВВ., Лемешко А.В., Мельникова Л.И.,Андрушко Д.В. Обзор и сравнительный анализ основных моделей и алгоитмов многопутевой маршрутизации в мультисервисных телекоммуникационных сетях // Прикладная радиоэлектроника, 2005. — Том.4. — Вып. No 4. — С. 372-382.
17. Новиков С.Н. Классификация методов маршрутизации в мультисервисных сетях связи //Вестник СибГУТИ. №1, 2013. — C. 57-67.
18. Гоголева М.А. Классификация и анализ методов маршрутизации в MESH-Сетях // Радиотехника. Вып.155б, 2008. — C. 173-185.
19. Афанасьев А.Л., Гармонов А.В.Многокритериальная многопутевая маршрутизация в mesh-сетях // Связь и телекоммуникации — инновационное развитие регионов: науч.-техн. конф.. — Воронеж, 2011. — [Электронный ресурс]. Систем. требования: MS Office Word. — URL: http://www.govvrn.ru/wps/ wcm/connect/voronezh/avo/main/authorities/other +executive+power/machinery+of+administration5/stat 290320111454 (дата обращения: 02.11.2013).
20.Кутафин А., Некрылов Д. Анализ перспектив применения математического аппарата многокритериального анализа к задаче автоматической маршрутизации в телекоммуникационных сетях // Энциклопедия знаний Pandia.ru — [Электронный ресурс]. — URL: http://www.pandia.ru/text/77/132/330.php (дата обращения 02.11.2013).
21. Valiant L.G., Brebner G.J. Universal schemes for parallel communication // STOC'81: Proc. Of 13th annual ACM symp. on theory of computing. — Milwaukee, USA. — N.Y.:ACM Press, 1981. Pр. 263-277.
22. Протокол EIGRP (усовершенствованный внутренний протокол маршрутизации шлюзов) //Официальная документация Cisco. — [Электронный ресурс]. Дата обновления: 3.04.2008 — Перевод, вы полненный профессиональным переводчиком. — URL: http://www.cisco.com/cisco/web/support/RU/9/92/92088_eigrp-toc.html (дата обращения 02.11.2013).