Software & Systems

Графовые модели маршрутизации [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 op­timal 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 prime­rakh i zadachakh [Optimization methods on examples and tasks]. Moscow, Vysshaya shkola Publ., 2005, 544 p.