Графовые модели маршрутизации [1, 2], положенные в основу большинства существующих маршрутизирующих протоколов (RIP, IGRP, EIGRP, IS-IS, OSPF, PNNI), получили широкое распространение, однако на практике все более востребованы именно потоковые модели маршрутизации, которые, с одной стороны, учитывают потоковый характер современного, преимущественно мультимедийного трафика (видео, речь и др.), а с другой – более адаптированы под решение задачи балансировки нагрузки и обеспечение качества обслуживания в мультисервисных телекоммуникационных сетях (ТКС).
Модель оптимального распределения потоков в телемедицинских сетях, предложенную в [3], можно использовать для произвольного числа линий связи и узлов. Однако при наличии в топологии моделируемой сети промежуточных узлов необходимо также учитывать условия сохранения потоков для них. В этом случае для решения задачи понадобится использование численных оптимизационных методов. В то же время распределение полученных оптимальных потоков по нескольким линиям связи может быть произведено по аналитической оптимизационной модели.
Рассмотрим следующую модель информационной сети (ИС) с альтернативной маршрутизацией сообщений. ИС состоит из n узлов коммутации и M каналов. Обозначим через jik, информационные потоки по каналам с учетом того, что каждый канал может быть разделен на m линий связи. Основными характеристиками качества функционирования сети являются средняя задержка сообщения T и максимальная загруженность T1 сети.
Тогда задачу оптимальной маршрутизации можно сформулировать следующим образом. По заданной топологической структуре ИС, значению входного потока g и матрице пропускных способностей С1ik, необходимо найти оптимальные значения потоков ||jik||. Минимизацию можно производить по двум указанным критериям T и T1:
(1)
(2)
при выполнении следующих ограничений:
. (3)
Для каждого из узлов коммутации должно выполняться условие сохранения потоков:
(4)
где E – множество каналов связи; i – узел-источник; j – узел-адресат; l=i и l=j характеризуют соответственно узел-вход и узел-выход.
Рассмотрим пример сети [4], состоящей из n=5 узлов и M=7 каналов связи (рис. 1), в которой поступающая нагрузка формируется в виде бесприоритетного трафика. Входной поток должен быть передан из узла 1 в узел 5. В данном примере разделение по линиям связи не производится, то есть m=1, и рассмотренные матрицы потоков и пропускных способностей являются одномерными массивами. Номера каналов указаны на рисунке в круглых скобках.
Задача оптимизации критериев (1) и (2) относится к классу задач нелинейной оптимизации функции нескольких переменных с ограничениями типа неравенств (3) и равенств (4) [5]. Решение таких задач может быть эффективно осуществлено в среде MatLab с помощью функции fmincon. Cтандартное обращение с полным списком выходных параметров, возвращаемых функцией, выглядит следующим образом:
A=[ ]; b=[ ]; nonlcon=[ ];
options=optimset('Display', 'iter', 'MaxFunEvals', 1000, 'TolX', TolX, 'GradObj', grad_par, 'Hessian', 'off');
[fmin, Tval, exitflag, output, lambda, grad, hessian]=fmincon(@Tkrit1, f0, A, b, Aeq, beq, lb, ub, nonlcon, options, Ysum, C1, nsig, TolX, nkrit).
Ограничения типа неравенств могут быть заданы в виде матриц A; b или нижней и верхней границ lb, ub. В данном случае предпочтительнее задать (3) с помощью границ. Ограничения типа равенств (4) задаются в виде матриц Aeq, beq. Нелинейные ограничения nonlcon отсутствуют. Расчет критериев (1) или (2) Tval производится функцией Tkrit1, а выбор критерия осуществляется по значению nkrit. Начальное приближение разделения потоков f0 может быть определено с помощью функции linprog с учетом тех же граничных условий.
Ограничения типа равенств (4) являются условиями сохранения потоков для узлов коммутации и для приведенной на рисунке 1 сети будут выглядеть следующим образом:
j1+ j2=g; (5)
–j1+ j3+j4+j5=0; (6)
–j2–j3+j6=0; (7)
–j4–j6+j7=0; (8)
–j5–j7= –g. (9)
Здесь равенства (5) и (9) описывают условия сохранения потоков соответственно для узла-входа и узла-выхода, а (6)–(8) – для промежуточных узлов.
Пропускные способности линий связи первоначально удобно задать в виде двухмерного массива ||Cij||, а уже затем перейти к одномерному массиву пропускных способностей ||C1i||, чтобы рассчитать оптимизируемые потоки ||ji||. Для рассмотренного примера указанные массивы выглядят следующим образом:
, (10)
||C1i|| = |40 20 45 35 10 50 40|. (11)
Для решения задачи оптимальной маршрутизации в среде MatLab разработана программа chisl.m, позволяющая найти оптимальные информационные потоки по каналам как по критериям средней задержки сообщения T и максимальной загруженности сети T1. Для информационной сети, изображенной на рисунке 1, входного потока g=40 и пропускных способностей ||C1i|| (11) результаты расчета оптимального распределения потоков по критериям T и T1 представлены на рисунках 2 и 3.
Внешний вид экрана при оптимизации по критерию задержки с помощью программы chisl.m показан на рисунке 4. Оптимальное значение критерия T=0,2029, но в этом случае критерий загруженности сети T1=1 (полностью загружен канал 5). При оптимизации по критерию загруженности T1=0,8113, но T=0,3295, то есть больше, чем в первом случае.
С помощью разработанной программы можно проанализировать зависимость загруженности информационной сети от интенсивности входного потока g. На рисунке 5 показаны результаты расчета изменения критерия максимальной загруженности T1 при различных интенсивностях входного потока.
Оптимальное распределение нагрузки каналов можно произвести и для произвольного количества m линий связи. В этом случае удобно использовать соотношения аналитической оптимизационной модели, предложенной в работе [3]. Результаты расчета оптимальных потоков по критерию загруженности при разделении на два канала для топологии сети, приведенной на рисунке 1, при входном потоке g=40 показаны на рисунке 6.
Внешний вид экрана при оптимизации по критерию загруженности с разделением потоков на два канала с помощью программы chisl.m показан на рисунке 7. Оптимальные значения критериев: T1=0,8005, T=0,6692.
Таким образом, предложенная модель оптимального распределения потоков в информационной сети позволяет на основе численных и аналитических оптимизационных методов для произвольных топологии сети и количества каналов связи произвести оптимизацию по критериям средней задержки и максимальной загруженности сети. Она учитывает условия сохранения потоков для промежуточных узлов сети. Оптимизация по критерию максимальной загруженности позволяет обеспечить наиболее сбалансированную загруженность каналов ТКС и повысить качество обслуживания.
Литература
1. Остерлох Х. Маршрутизация в IP-сетях. Принципы, протоколы, настройка. СПб: БХВ, 2002. 512 c.
2. Вегенша Ш. Качество обслуживания в сетях IP; [пер. с англ.]. М.: Вильямс, 2003. 386 с.
3. Марголис Б.И., Музанна М.М. Решение задачи оптимальной маршрутизации по критерию средней задержки // Программные продукты и системы. 2013. № 3. С. 202–205.
4. Лемешко А.В., Вавенко Т.В. Усовершенствование потоковой модели многопутевой маршрутизации на основе балансировки нагрузки // Проблемы телекоммуникаций. 2012. № 1 (6). С. 12–29.
5. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. М.: Высш. школа, 2005, 544 с.
References
1. Osterlokh Kh. Marshrutizatsiya v IP-setyakh. Printsipy, protokoly, nastroyka [Routing in IP nets. Principles, protocols, customizing]. St. Petersburg, BHV Publ., 2002, 512 p.
2. Vegensha Sh. Kachestvo obsluzhivaniya v setyakh IP [Quality of service in IP Networks]. (Russ. ed.) Moscow, Vilyams Publ., 2003, 386 p.
3. Margolis B.I., Muzanna M.M. Solving the problem of optimal routing using average delay criteria. Programmnye produkty i sistemy [Software & Systems]. 2013, no. 3, pp. 17–19.
4. Lemeshko A.V., Vavenko T.V. Upgrading flow-oriented model of multipath routing based on load balancing. Problemy telekommunikatsiy [Telecommunication problems]. 2012, no. 1 (6), pp. 12–29 (in Russ.).
5. Panteleev A.V., Letova T.A. Metody optimizatsii v primerakh i zadachakh [Optimization methods on examples and tasks]. Moscow, Vysshaya shkola Publ., 2005, 544 p.