Многопутевая маршрутизация

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

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

Мобильные сети

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

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

Истинный КМР

Более мощная форма CMR (истинный CMR) выходит за рамки простого представления путей приложениям, к которым они могут привязываться. Истинный CMR объединяет все доступные пути в один виртуальный путь.

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

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

Капиллярная трассировка

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

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

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

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

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

Смотрите также

• Многопутевая маршрутизация с равной стоимостью
• IEEE 802.1aq
• Многопутевой TCP
• TRILL (Прозрачное взаимодействие множества ссылок)

Ссылки

• С.-Дж. Ли и М. Герла, «Разделенная многопутевая маршрутизация с максимально непересекающимися путями в сетях Ad Hoc», Труды ICC 2001, т. 10, стр. 3201–3205, июнь 2001 г.
• А. Насипури, Р. Кастанеда и С. Р. Дас, «Производительность многопутевой маршрутизации для протоколов по требованию в мобильных сетях Ad Hoc», Мобильные сети и приложения, т. 6, № 4, стр. 339–349, август 2001 г.
• MK Marina и SR Das «Многопутевая маршрутизация по требованию с использованием векторов расстояний в сетях Ad Hoc», Труды ICNP 2001, стр. 14–23, ноябрь 2001 г.
• А. Циригос и З. Дж. Хаас, «Многопутевая маршрутизация при частых топологических изменениях», журнал IEEE Communications, т. 39, № 11, стр. 132–138, ноябрь 2001 г.
• Х. Лим, К. Сюй и М. Герла, «Производительность TCP при многопутевой маршрутизации в мобильных сетях Ad Hoc», Труды ICC 2003, т. 2, стр. 1064–1068, май 2003 г.
• А. Циригос и З. Дж. Хаас, «Анализ многопутевой маршрутизации — часть I: влияние на коэффициент доставки пакетов», IEEE Trans. Wireless Communications, т. 3, № 1, стр. 138–146, январь 2004 г.
• С. Кард, Ф. Тимс, «Параллельная многопутевая маршрутизация и транспорт в мобильном беспроводном шлюзе», несекретный доклад, представленный на секретной сессии MILCOM 2004, доступен по запросу в службу поддержки на сайте www.critical.com.
• Н. Камменхубер, «Маршрутизация с адаптацией к трафику», Глава 6.2 «Связанные работы», http://mediatum.ub.tum.de/doc/635601/635601.pdf

Для повышения безопасности сети :

• W. Lou и Y. Fang, «Метод многопутевой маршрутизации для безопасной доставки данных», Proc. MILCOM 2001, т. 2, стр. 1467–1473, октябрь 2001 г.
• CK-L. Lee, X.-H. Lin и Y.-K. Kwok, «Метод многопутевой специальной маршрутизации для борьбы с ненадежностью беспроводных соединений», Proc. ICC 2003, т. 1, стр. 448–452, май 2003 г.
• С. Буам и Дж. Бен-Отман, «Безопасность данных в сетях Ad Hoc с использованием многопутевой маршрутизации», Труды PIMRC 2003, т. 2, стр. 1331–1335, сентябрь 2003 г.
• П. Пападимитратос и З. Дж. Хаас, «Безопасная передача данных в мобильных сетях Ad Hoc», Труды ACM WiSe 2003, стр. 41–50, сентябрь 2003 г.
• Чжи Ли и Ю-Квонг Квок, «Новый подход к многопутевой маршрутизации для повышения безопасности TCP в беспроводных сетях Ad Hoc», Труды семинаров ICPP, стр. 372–379, июнь 2005 г.

Внешние ссылки

• Dijiang Huang. "Библиография многопутевой маршрутизации". Архивировано из оригинала 2008-10-13.