ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Optimal routing using the network congestion criterion

The article was published in issue no. № 4, 2013 [ pp. 173-176 ]
Abstract:The article considers the network information flow model with reroute messages for any number of switching nodes and links. There are criteria for optimizing with time-delay messages and the maximum network congestion, restrictions for the capacity of the channels and the conservation of flows in the network. An example of a network consisting of five nodes and seven channels of communication is described. It is shown that the problem of optimal routing refers to non-linear optimization of several variables function with inequality constraints and equations. Inequality constraints are formulated for channel capacity and the type of equations for the conservation of flows in the network nodes according to their division into input node, output node and intermediate nodes. Based on the standard fmincon function, a program as developed in MatLab. It allows finding the optimal distribution of flows in the network consisting of an arbitrary number of nodes and links according the topological structure of the network, the input flow and capacity of channels. The article shows the results of the optimum flow separation calculation using criteria of congestion and delays for the considered example. The analysis of changes in the criteria of maximum load at different intensities of the input stream is made. It is shown that the determination of the optimum distribution of channels load while separating each channel to any number of lines can be done using analytical optimization techniques. There are results of the calculation of the optimum flow separation on two links by load for the considered example.
Аннотация:Рассмотрена потоковая модель информационной сети с альтернативной маршрутизацией сообщений для произвольного количества коммутационных узлов и каналов связи. Сформулированы критерии оптимизации по времени задержки сообщений и максимальной загруженности сети, ограничения на пропускные способности каналов и условия сохранения потоков в сети. Рассмотрен пример сети, состоящей из пяти узлов и семи каналов связи. Показано, что задача оптимальной маршрутизации относится к классу задач нелинейной оптимизации функции нескольких переменных с ограничениями типа неравенств и равенств. Сформулированы ограничения типа неравенств для пропускных способностей каналов и типа равенств для условия сохранения потоков в узлах сети с учетом их разбиения на узел-вход, узел-выход и промежуточные узлы. На основе стандартной функции fmincon в среде MatLab разработана программа, позволяющая по топологической структуре сети, входному потоку и пропускным способностям каналов найти оптимальное распределение потоков в сети, состоящей из произвольного количества узлов и каналов связи. Приведены результаты расчета оптимального разделения потоков по критериям загруженности и задержки для рассмотренного примера. Проведен анализ изменения критерия максимальной загруженности при различных интенсивностях входного потока. Показано, что определение оптимального распределения нагрузки каналов при разделении каждого канала на произвольное количество линий связи может быть выполнено с помощью аналитических оптимизационных методов. Приведены результаты расчета оптимального разделения потоков на две линии связи по критерию загруженности для рассмотренного примера.
Authors: Dmitriev G.A. (kirsanich@mail.ru) - Tver State Technical University, Tver, Russia, Ph.D, Margolis B.I. (borismargolis@yandex.ru) - Tver State Technical University, Tver, Russia, Ph.D, Muzanna M.M. (mohamed1984a@yahoo.com) - Tver State Technical University, Tver, Russia
Keywords: optimal routing, switching node, communication channel, the average message delay, maximum load carrying capacity, capacity, nonlinear optimization, inequality constraints and equations, input stream, topology, information network
Page views: 11628
Print version
Full issue in PDF (7.95Mb)
Download the cover in PDF (1.45Мб)

Font size:       Font:

Графовые модели маршрутизации [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, то есть больше, чем в первом случае.

Подпись:  

Рис. 5. График зависимости критерия загруженности от входного трафика
С помощью разработанной программы можно проанализировать зависимость загруженности информационной сети от интенсивности входного потока g. На рисунке 5 показаны результаты расчета изменения критерия максимальной загруженности T1 при различных интенсивностях входного потока.

Оптимальное распределение нагрузки каналов можно произвести и для произвольного количества m линий связи. В этом случае удобно использовать соотношения аналитической оптимизационной модели, предложенной в работе [3]. Результаты расчета оптимальных потоков по критерию загруженности при разделении на два канала для топологии сети, приведенной на рисунке 1, при входном потоке g=40 показаны на рисунке 6.

Подпись:   

Рис. 7. Результаты расчета оптимального 
разделения потоков на два канала
Внешний вид экрана при оптимизации по критерию загруженности с разделением потоков на два канала с помощью программы 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.


Permanent link:
http://swsys.ru/index.php?page=article&id=3680&lang=en
Print version
Full issue in PDF (7.95Mb)
Download the cover in PDF (1.45Мб)
The article was published in issue no. № 4, 2013 [ pp. 173-176 ]

Perhaps, you might be interested in the following articles of similar topics: