Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/38

Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях

Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути (RCSP) в графе G = (V,E). Задача RCSP является расширением известной задачи о кратчайшем пути в ориентированном графе, когда каждой дуге e £ E кроме основного веса w(e) дополнительно задаются несколько весовых функций wr (e), отражающих потребности в ресурсах, которые необходимы для передвижения по этой дуге. Задача RCSP позволяет моделировать мультисер-висные телекоммуникационные сети и определять в них оптимальный маршрут передачи данных между двумя заданными узлами сети. Предлагаются два алгоритма для приближённого решения задач RCSP на сетях большой размерности. Первый алгоритм является расширением известного алгоритма Дейкстры, который присваивает дополнительные метки каждой вершине. Эти метки позволяют алгоритму Дейкстры находить ресурсоограниченный путь в графе. В отличие от известных модификаций, такая модификация не требует дополнительных знаний о графе. Второй алгоритм, помимо дополнительных меток, добавляет к алгоритму Дейкстры потенциальные функции и ориентиры. Потенциальные функции, вычисленные на основе ориентиров, дают значительное ускорение на графах большой размерности. Предлагаемые алгоритмы не превосходят по вычислительной сложности алгоритм Дейкстры. Приводятся результаты вычислительных экспериментов, подтверждающие эффективность предложенных алгоритмов.

Algorithm for optimal routing in multiservice networks.pdf Большинство современных телекоммуникационных сетей являются мультисервис-ными, поскольку предоставляют пользователям множество разнообразных услуг, касающихся проводной телефонии, сотовой связи, кабельного телевидения и передачи данных. Качество обслуживания (Quality of Service, QoS) в мультисервисных сетях определяется такими параметрами, как полоса пропускания, задержка, вариация задержки, стоимость и надёжность передачи данных [1]. Всякий запрос пользователя на оказание услуги предполагает определение некоторого (желательно, оптимального по затратам, например, по времени или стоимости) маршрута между двумя узлами с учётом ресурсных возможностей этой сети. Таким образом, задача оптимального обслуживания пользователя в мультисервисной сети может быть математически сформулирована как задача поиска ресурсоограниченного кратчайшего пути в графе. Данная задача известна в литературе под названием Resource Constrained Shortest Path (RCSP) [2, 3]. На практике задача RCSP возникает как при проектировании, так и при эксплуатации мультисервисных сетей. На этапе проектирования с помощью многократного решения задачи RCSP возможна оценка качества услуг, которую проектируемая сеть способна предоставить потенциальным пользователям. При эксплуатации сети RCSP решается в реальном масштабе времени для каждого отдельного запроса пользователя на какую-либо услугу. В настоящее время мультисервисные сети активно расширяются путем увеличения числа предоставляемых услуг и входящих в них узлов. Количество узлов в сети может достигать нескольких сотен тысяч. Именно для таких больших сетей, чаще всего, требуется находить решение задачи RCSP в реальных условиях. Известны две формулировки задачи RCSP: в терминах теории графов и целочисленного линейного программирования. В теоретико-графовой формулировке мульти-сервисная сеть представляется ориентированным графом, вершины которого соответствуют узлам сети, а дуги - каналам связи. Предполагается, что всякая дуга обладает основным весом (это может быть стоимость или время прохождения по дуге), а также некоторыми дополнительными весами, отражающими потребности в ресурсах, которые нужны для передвижения по этой дуге. Требуется найти кратчайший путь между двумя заданными узлами сети, отвечающий заданным ограничениям на итоговые ресурсные затраты, необходимые для прохождения этого пути. Показано, что даже при ограничении на один ресурс задача RCSP является NP-трудной [4]. В настоящее время выделяют три класса методов и алгоритмов, способных находить точное или приближенное решение задачи RCSP: методы ранжирования путей [4], методы маркировки вершин [1, 2, 5], методы лагранжевой релаксации [6-8]. Первые два класса методов основаны на теоретико-графовой постановке задачи, методы третьего класса исходят из постановки задачи RCSP на языке целочисленного линейного программирования. Большинство существующих алгоритмов не приспособлены к сетям большой размерности и, как следствие, не отвечают реальному масштабу времени, необходимому для обработки запросов при эксплуатации мультисервисных сетей. Поэтому актуальны различные приёмы и методы ускорения существующих алгоритмов, а также разработка новых подходов к решению задачи RCSP [1, 8]. Рассмотрим задачу RCSP в теоретико-графовой постановке, используя общепринятые в теории графов терминологию и обозначения [9]. Пусть мультисервисная сеть описана взвешенным ориентированным графом (далее просто графом) G = (V, E) без кратных дуг и петель, в котором каждая вершина v Е V представляет узел сети, каждая дуга e Е E - канал связи между соответствующими узлами сети. Считаем, что на множестве дуг графа G задана функция w(e): E ^ R+, ставящая в соответствие каждой дуге e Е E её вес w(e) ^ 0. Пусть для вершин s,d Е V в графе G существует путь P, идущий от вершины s к вершине d. Полагаем, что вес этого (з^)-пути P вычисляется как сумма весов всех входящих в него дуг: w(P) = Е w(e), (1) т. е. функция w(P) является аддитивной. Если w(e) -стоимость передвижения по дуге e, то w(P) -стоимость прохождения (s, d)-пути P в графе G. Пусть для каждой дуги графа G = (V, E), кроме w(e), заданы весовые функции wr(e): E ^ R+, r = 1,... , k, отражающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Предполагается, что все эти функции аддитивные, т. е. для любого (s, d)-пути P верны равенства wr (P) = Е wr (e), r = 1,..., k. Считаем, что заданы также величины Wr Е R+, r = 1,..., k, определяющие ресурсные ограничения мультисервисной сети. Всякий (s, d)-путь P называется допустимым, если он удовлетворяет ресурсным ограничениям Е Wr (e) ^ Wr, r = 1,..., k. (2) Очевидно, что кратчайший ^^)-путь в графе G не обязательно допустимый. Задачу RCSP можно сформулировать следующим образом. Заданы граф G = = (V, E), на дугах которого определены неотрицательные вещественнозначные функции w(e) и wr(e); величины Wr, r = 1,... , k; (s, d)-запрос. Требуется найти в G ресур-соограниченный кратчайший (s^-путь, т.е. такой ^^)-путь P, который минимизирует w(P) в (1) и удовлетворяет ограничениям (2). Задача RCSP не имеет решения, если множество допустимых (s^-путей пустое. Для решения задачи RCSP предлагается эвристический алгоритм Ai, являющийся модификацией алгоритма Дейкстры. Как известно, алгоритм Дейкстры - маркировочная процедура, осуществляющая поиск кратчайшего пути в графе на основе меток вершин за полиномиальное время [5]. В алгоритме A1 к меткам алгоритма Дейкстры добавлены ещё две метки: величина затраченных ресурсов при прохождении пути от стартовой вершины s до текущей вершины v и допустимость (да/нет) использования вершины v для дальнейшего построения искомого пути. Применение этих меток позволяет, прежде всего, находить допустимые пути и далее среди них кратчайший путь, не увеличивая существенно время поиска. В остальном алгоритм A1 полностью соответствует классическому алгоритму Дейкстры. Если множество допустимых решений задачи RCSP непустое, то решение, найденное алгоритмом A1, всегда допустимое, но не обязательно оптимальное. С целью применения алгоритма Дейкстры к графам большой размерности в настоящее время разрабатываются всевозможные приёмы ускорения [10, 11]. Одним из таких приёмов является применение потенциальных функций, которые могут определяться различными способами, в частности с помощью ориентиров. Предлагаемый двухфазный алгоритм A2 предназначен для ускорения алгоритма A1. На первой фазе алгоритм A2 производит расстановку ориентиров в вершинах графа и вычисляет потенциальные функции, на второй фазе - осуществляет с помощью алгоритма A1 и вычисленных потенциальных функций поиск ресурсоограниченного оптимального маршрута в графе. Алгоритм A2 имеет следующие параметры: число ориентиров и стратегия их расстановки (случайным образом в вершинах графа, случайным образом в вершинах, образующих оболочку графа, и др.). Для вычисления потенциальных функций алгоритм A2 использует евклидову метрику. Для оценки эффективности предложенных алгоритмов проведены серии вычислительных экспериментов. В табл. 1 представлены параметры графов, на которых проводились эксперименты. Первая серия экспериментов состояла в сравнении алгоритма A1 и пакета IBM ILOG CPLEX [12]. Эксперименты проводились на случайно сгенерированных графах с различным числом вершин и рёбер для последовательности а, состоящей из 1000 случайно сгенерированных (s, d)-запросов. Сравнение осуществлялось по числу выполненных запросов, точности найденного решения и времени работы алгоритмов. Запрос считался выполненным, если для него получено точное или приближенное решение задачи RCSP. Точность приближённого решения, найденного алгоритмом A1 , оценивалась относительно результата, вычисленного с помощью CPLEX. В качестве результата пакет программ CPLEX всегда выдаёт оптимальное решение задачи RCSP, если множество допустимых решений не пусто. Таблица 1 Параметры графов Название графа Число вершин Число дуг Gi 100 720 G2 625 4800 G3 2500 19600 AK 69082 157662 CT 153011 375310 MA 308401 771362 Результаты первой серии экспериментов представлены в табл. 2, где qerr обозначает количество запросов, для которых найдено приближённое решение; err - максимальная относительная погрешность в процентах. По этим результатам можно сделать следующие выводы. Пакет CPLEX для рассматриваемых графов с заданными ресурсными ограничениями выполняет примерно половину запросов последовательности а. Время нахождения точного решения существенно зависит от размеров графа и числа рассматриваемых ресурсов. Например, для исходного графа с числом вершин 2500, числом рёбер 19600 и количеством ресурсов 10 с помощью пакета CPLEX не удалось получить решение за 1000 с. Алгоритм A1 выполняет примерно такую же долю запросов, что пакет CPLEX, затрачивая на это на два порядка меньше времени. Эвристический характер алгоритма не исключает ситуации, когда построенное решение не является точным. Однако, как показывают эксперименты, это происходит сравнительно редко и с малой относительной погрешностью. Таким образом, алгоритм A1 можно применять к реальным мультисервисным сетям с числом узлов, не превосходящим 10 000, для которых приемлема небольшая потеря точности в решении. Таблица 2 Результаты сравнения алгоритма Ai с пакетом CPLEX Название графа Количество ресурсов CPLEX Ai Время обработки а, с Число выполненных запросов Время обработки а, с Число выполненных запросов err всего qerr О! 1 39,8 945 0,050 937 1 2 G2 1 79,1 855 0,339 829 1 0,4 Оз 1 267,2 959 5,919 944 3 3 О! 2 39,6 961 0,048 872 4 7 G2 2 79,6 807 0,294 757 3 4 Оз 2 284,1 799 3,541 783 6 0,7 О! 5 40,0 756 0,029 727 3 11 О2 5 89,0 703 0,264 701 2 1 Оз 5 362,6 666 2,337 647 4 0,2 О! 10 43,6 828 0,038 807 0 0 О2 10 111,9 712 0,245 713 7 1 Оз 10 - - 2,836 694 - - Цель второй серии экспериментов - сравнение алгоритмов A1 и A2 на графах большой размерности. Для алгоритма A2 выбраны следующие параметры: число ориентиров- 12, стратегия их расстановки - случайное размещение в вершинах графа. Сравнение производилось по времени работы и доле выполненных запросов. Результаты представлены в табл. 3. Видно, что время работы алгоритма A2 меньше времени работы алгоритма Ai в несколько раз, при этом число выполненных запросов совпадает. Это позволяет сделать следующий вывод: алгоритм A2 можно применять к реальным мультисервисным сетям с числом узлов в несколько сотен тысяч, для которых приемлема небольшая потеря точности в решении. Во время экспериментов полагалось, что все поступающие запросы однородны и не конкурируют между собой. В реальных сетях возможны ситуации, когда несколько запросов конкурируют за ресурсы или имеют разный характер, например различные требования к ресурсам. Таким образом, требуется дальнейшее развитие алгоритмов для эффективной маршрутизации в подобных сетях. Таблица 3 Название Количество A A графа ресурсов Число выпол Время обра Число выпол Время обраненных запроботки а, с ненных запроботки а, с сов сов AK 1 531 511,171 531 434,538 CT 1 821 1100,88 821 117,283 MA 1 738 687,516 738 103,052 AK 2 587 548,222 587 397,847 CT 2 667 735,669 667 73,765 MA 2 802 776,492 802 158,573 AK 5 523 473,254 523 368,664 CT 5 813 1152,33 813 123,665 MA 5 806 756,533 806 137,998 AK 10 541 410,33 541 329,267 CT 10 679 688,384 679 74,905 MA 10 557

Ключевые слова

big graph, resource constrained shortest path, графы большой размерности, ресурсоограниченный кратчайший путь

Авторы

ФИООрганизацияДополнительноE-mail
Солдатенко Александр АлександровичСибирский федеральный университетаспирант Института математики и фундаментальной информатикиglinckon@gmail.com
Всего: 1

Ссылки

IBM ILOG CPLEX Optimizer Studio. CPLEX User's Manual. Version 12 Release 6, 2015.
Быкова В. В., Солдатенко А. А. Адаптивное размещение ориентиров в задаче о кратчайшем пути для графов большой размерности // Программные продукты и системы. 2016. №1. С. 60-67.
Mehlhorn K. and Ziegelmann M. Resource constrained shortest paths // LNCS. 2000. V. 1879. P. 326-337.
Jepsen M., Petersen B., Spoorendonk S., and Pisinger D. A branch-and-cut algorithm for the capacitated profitable tour problem // J. Discr. Optimization. 2014. V. 14. P. 78-96.
Horvath M. and Kis T. Solving resource constrained shortest path problems with LP-based methods // J. Computers & Operat. Res. 2016. V. 73. P. 150-164.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Книжный дом «Либроком», 2012. 390с.
Быкова В. В., Солдатенко А. А. Оптимальная маршрутизация по ориентирам в нестационарных сетях // Прикладная дискретная математика. 2017. №37. С. 114-123.
Dumitrescu I. and Boland N. Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem // J. Networks. 2003. V.42. P. 135-153.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416с.
Van Mieghem P., Kuipers F. A, Korkmaz T., et al. Quality of service routing // LNCS. 2003. V. 2856. P. 80-117.
Joksch H. C. The shortest route problem with constraints // J. Math. Analysis Appl. 1966. V.14. P. 191-197.
Dror M. Note on the complexity of the shortest path models for column generation in VRPTW // J. Operat. Res. 1994. V.42. P. 977-978.
 Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/38

Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/38