Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

Исследование алгоритмов маршрутизации с гарантированным качеством услуг Грозовская Е.Л., к.т. н Егунов М.М (научный руководитель) СибГУТИ, Новосибирск Современные требования доставки информации выдвигают на первый план QoS маршрутизацию. QoS-маршрутизация классифицируется по двум категориям: зависящая от состояния и зависящая от времени - в соответствии с осведомленностью о будущих требованиях к трафику в сети. Актуальной задачей является обеспечение качества услуг (QoS) маршрутизации для высокоскоростных сетей или IP-сетей следующего поколения, чтобы обеспечить разные услуги с обязательными требованиями такие, как видео, аудио, интерактивные мультимедиа, телеконференции. Алгоритм маршрутизации (QoS) должен быть очень быстрым, чтобы соответствующий протокол маршрутизации мог установить путь за незначительное время и обеспечить высокое качество для наилучшей работы ресурсов сети. Проблемы маршрутизации процесса QoS делятся на несколько категорий. Среди проблем процесса маршрутизации, выделяют проблему пути ограниченной оптимизации PCPO (path-constrained path-optimization problem)1 и проблему универсального пути ограничений MCP (multi-path constrained)2 которые являются NP полными. Проблема PCPO заключается в поиске пути с минимальной стоимостью, который зависит от одного или более ограничений. Таким образом, в проблеме РСРО поиск походящего пути является фундаментальным шагом, который нужно выполнить много раз. В то время как в MCP нужно найти путь, зависимый от двух и более ограничений без необходимости нахождения “ оптимального” решения. Кроме РСРО проблемы существует много других QoS индивидуальных или множественных проблем маршрутизации сообщений. Для этих проблем эффективность основного шага имеет значительное влияние на алгоритмы более высокого уровня. В настоящее время разработано большое количество эвристических алгоритмов. Особый интерес представляют эвристики, предложенные в работах T. Korkmaz[3] и Gang Fend [1]. Для решения проблемы РСРО с многочисленными ограничениями, основанными на нелинейном ослаблении Лагранжа (NLR), T. Korkmaz предложил эвристический алгоритм H_MCOP. В поиске оптимального пути алгоритм H_MCOP проходит дважды алгоритм Дэйкстра [4] (с небольшими изменениями). Таким образом, H_MCOP обеспечивает компромисс между временной сложностью и качеством решения. Хотя H_MCOP показывает превосходную способность находить приемлемые решения проблем многолинейных ограничений (MCP), он не использует полностью возможности, которые представляет NLR техника .[5] Gang Fend предложил новый эвристический MCP, названный NLR_MCP. Изучив выполнение алгоритма NLR_MCP , когда он будет использоваться как основной шаг для решения проблемы ограниченности задержки наименьшей стоимости. DCLC (delay-constrained least cons)3. Опыты показали, что с NLR_MCP мы можем достигнуть высокой производительности с виртуально идентичной временной сложностью в сравнении с тем случаем, когда используется H_MCOP. Не исследованным является вопрос сравнительного анализа алгоритмов на различных структурах сетей. Данная работа посвящена исследованию алгоритмов NLR_MCP и H_MCP. На языке программирования Delphi разработано программное средство для проведения сравнительного анализа алгоритмов. Для сравнения работы алгоритмов NLR_MCP и H_MCP строились сети следующих структур: сети в виде кольца, решетки и полносвязного графа. Рассматривались графы различных размеров, в качестве числа вершин брались значения 50, 100, 150, 200. Значение весов ребер брались как псевдослучайные числа из интервала [0,100]. На каждом наборе входных данных осуществлялась серия запусков алгоритмов (по 10 раз). Результаты показывают, что с NLR_MCP мы достигаем вычисления оптимального пути за меньшее время работы (12 %) в сравнении с тем случаем, когда используется H_MCP. Это показывает, что основанная на NLR эвристика, в сравнении с H_MCOP, может обеспечить существенные улучшения, если она используется как основной шаг для решения более сложных проблем QoS маршрутизации. Общий вывод по всем структурам: 1)Из графиков 1,2,3 можно сделать следующие выводы, что время работы алгоритмов существенно зависит и от количества ребер в графе. 2) Время работы алгоритма NLR_MCP меньше по сравнению со временем работы алгоритма H_MCP. Из результатов экспертного анализа видно, что метод неопределенных множителей Лагранжа эффективно используется при решении задач QoS маршрутизации. Исследование алгоритмов маршрутизации с гарантированным качеством услуг применимых в высокоскоростных сетях и IP-сетях следующего поколения, является актуальной задачей, требующей в дальнейшем более глубокого изучения. Библиография 1 G. Feng, C. Doulgeris, K. Makki, and N. Pissinou, “Linear and nonlinear Lagrange relaxation algorithms for delay-constrained least-cost QoS routhing,” IEICE Trans. Communications, Vol.E85-B No.11, pp. 2437-2446, Nov.2002 2 G. Feng, K.Makki, N.Pissinou, “Efficient implementations of a delay-constrained least-cost multicast algorithm,” Journal of Communications and Networks, Vol.4, No. 3, pp. 246-255, Sep.2002 3 T. Korkmaz and M. Krunz, “Multi-constrained optimal path selection,” INFOCM’2001, Alaska, 2001 4 E/ Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol.1, pp. 269-271, 1959. 5 Gang Feng. Nonlinear Lagrange Relaxation Based QoS Routing Revisited. (WI 53818)2005.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2007, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2007, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:51)