А В Воробьев - Исследование эффективности метода локальных динамических моделей - страница 1

Страницы:
1  2 

Комп 'ютерні системи та інформаційні технології

УДК 519.6: 629.7.036.3 А.В. ВОРОБЬЕВ

Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ», Украина

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДА ЛОКАЛЬНЫХ ДИНАМИЧЕСКИХ МОДЕЛЕЙ

Проанализирована задача балансировки нагрузки. Показана необходимость перехода от статических методов балансировки нагрузки к динамическим, позволяющим повысить эффективность функциони­рования телекоммуникационной сети. Рассмотрен метод локальных динамических моделей для реше­ния задач балансировки нагрузки. Проведено исследование эффективности рассмотренного метода на однопродуктовой сети. Предложены рекомендации по выбору режимов работы метода. Предложены рекомендации по особенностям применения метода локальных динамических моделей в случаях не стационарности интенсивности поступающей нагрузки в сеть.

Ключевые слова: маршрутизация, оптимизация, динамическое управление, балансировка нагрузки, распределение ресурсов, моделирование.

Введение

Решение задач маршрутизации занимает важ­ное место в функционировании телекоммуникаци­онных систем (ТКС) и напрямую влияет на эффек­тивность их работы [1, 2].

В ТКС для решения задач маршрутизации ис­пользуются распределенные подходы управления, которые обладают высокой сходимостью, но при этом приводят к неравномерной загрузке сети. Пер­спективным направлением развития является опти­мальная маршрутизация, использование которой на практике предполагает реализацию централизован­ного подхода к управлению сетью. Такое управле­ние, хотя теоретически дает лучшие результаты, на практике связано с рядом трудностей. Основными недостатками являются большая размерность моде­ли ТКС и медленная сходимость, поскольку управ­ление зависит от глобальных параметров, которые трудно знать априорно. При имеющихся недостат­ках полностью децентрализованного и централизо­ванного управления, возникает потребность в объе­динении их положительных особенностей [3].

В такой ситуации возникает необходимость в новых методах, которые позволят обеспечить эф­фективность распределения нагрузки, а также будут совместимыми с существующими распределенными методами маршрутизации. Одним из возможных вариантов решения такой задачи может быть введе­ние дополнений к существующим методам маршру­тизации, которые будут выполнять более сбаланси­рованное распределение нагрузки на локальных участках сети. Некоторые попытки реализовать дан­ный подход привели к созданию методов баланси­ровки нагрузки [4].

Анализ методов балансировки нагрузки

В большинстве современных маршрутных про­токолов возможные пути следования сетевого тра­фика определяются значением наименьшей суммар­ной стоимости (метрики) на основе алгоритмов по­иска «кратчайшего» пути. При наличии в сети не­скольких равноценных альтернативных маршрутов осуществляется балансировка (равномерное распре­деление) нагрузки (БН).

Балансировка нагрузки (load balancing) - спо­собность маршрутизатора распределять трафик по всем сетевым портам, которые находятся на одина­ковом расстоянии от получателя. В алгоритмах распределения нагрузки используется информация о пропускной способности и надежности каналов. Распределение нагрузки повышает интенсивность использования сетевых сегментов, а значит, и эф­фективную пропускную способность сети в целом [4].

Ранее в работе [5], было проведено краткое сравнение методов балансировки нагрузки исполь­зуемых в протоколах OSPF, RIP, EIGRP, более рас­ширенное и дополненное сравнение показано в табл. 1. Несмотря на то, что в последнее время по­является ряд работ посвященных решению задач БН предлагаемые решения пока не нашли широкого внедрения в практику управления IP-сетями уровня MAN и WAN, а потому вопрос остается открытым. Приведенные недостатки указывают на то, что ре­шение задачи балансировки нагрузки еще далеко от своего завершения и требует дальнейших исследо­ваний.

При разработке новых методов БН необходимо учитывать:

© А.В. Воробьев

Таблица 1

Сравнение протоколов OSPF, EIGRP и RIP по реализации балансировки нагрузки

Сравниваемый параметр

Метод БН в составе протокола маршрутизации

 

OSPF

EIGRP

RIP

БН между маршрутами с одинаковой метрикой

+

+

+

БН между маршрутами с разной метрикой

-

+

-

По-пакетно (per-packet)

+

+

+

По-получателю (per-destination)

+

+

+

Учет состояния загруженности каналов связи выходящих из маршрутизатора

-

-

-

Динамический перерасчет управляющих пере­менных

-

-

-

Автоматический выбор режимов работы метода БН при изменяющихся условиях

-

-

-

Согласованность работы метода БН с методами обработки очередей

-

-

-

- динамику при перерасчете управляющих пе­ременных;

- возможность реализации автоматической ра­боты по выбору режимов работы метода;

- согласованность с методами обработки очере­дей;

- состояния загруженности каналов связи вы­ходящих из маршрутизатора;

- возможность реализации БН по маршрутам с разной стоимостью.

В работе [5] был предложен метод локальных динамических моделей (ЛДМ), позволяющий устра­нить ряд недостатков существующих методов рас­смотренных в таблице. Однако существует слож­ность в реализации этого метода, заключающаяся в необходимости подобрать такие значения элементов матрицы определяющей важность каналов связи выходящих из маршрутизатора, которые бы обеспе­чили максимальную эффективность работы на ло­кальном участке и сети в целом.

Постановка задачи исследования

В статье исследуется эффективность метода ЛДМ при различных значениях элементов матрицы определяющей важность каналов связи выходящих из маршрутизатора в условиях изменения интенсив­ности входной нагрузки с целью достижения мак­симальной производительности работы сети.

Метод локальных динамических моделей

Метод ЛДМ, позволил устранить недостатки существующих методов БН. В его основу положена динамическая модель маршрутизатора состоящая из функциональной и структурной моделей представ­ленных в пространстве состояний.

Для описания структуры сети применяется ориентированный взвешенный граф, вершины кото­рого Vi, i = 1, N, моделируют узлы (которыми, как правило, выступают маршрутизаторы) ТКМ, а дуги Ei j, i, j = 1, N, i Ф j, - каналы связи, где N - коли­чество узлов сети. Так, основной характеристикой узлов является объем их буферной памяти xmax, а каналов связи - их пропускные способности Ci j.

Динамическая функциональная модель мар­шрутизатора может быть представлена системой дифференциально-разностных уравнений в дис­кретные моменты времени tk, k = 0,1, ... , с ин­тервалом дискретизации At = tk+1 tk. В качестве

переменных состояний выберем величины загрузки буфера на маршрутизаторе тем трафиком, для дос­тижения которого имеется несколько маршрутов. В качестве управляющих выберем балансировочные переменные, которые соответствуют частям пропу­скной способности тех интерфейсов маршрутизато­ра, между которыми осуществляется БН.

Количество уравнений для описания работы маршрутизатора в общем случае равно N — 1, а в частном случае с целью решения распределения нагрузки его можно определить через количество получателей, для достижения которых имеется не­сколько маршрутов с разной стоимостью. Таким образом, динамическую модель маршрутизатора можно представить в следующем виде:

N

xi,j (k +1) = xi,j (k) x bi,i (k)ui,! (k) + l=1

N

+ x bm,i(k)um,i(k)+yi,j(k), (1)

m=1 m*i,j

Комп'ютерні системи та інформаційні технології

где xi j (k) - объем данных, находящихся в момент

времени tk на текущем маршрутизаторе V и пред­назначенных для маршрутизатора Vj, достижение

которого возможно по нескольким маршрутам с разной метрикой;

bii (k) = (k)At, Cii (k) - пропускная способ­ность канала связи (интерфейса маршрутизатора) Ei i, через который выполняется распределение на­грузки за вычетом пропускной способности, уже отведенной под другие задачи;

uji(k) - доля пропускной способности канала Ei i, выделенная в момент времени tk для передачи трафика, предназначенного маршрутизатору Vj;

bm i (k) = cm i (k)At, cm i (k) - пропускная спо­собность канала связи (интерфейса маршрутизатора) Em i, через который данные поступают от соседних маршрутизаторов;

Urn i (k) - доля пропускной способности канала Em i, выделенная в момент времени tk для переда­чи транзитного трафика, проходящего через теку­щий маршрутизатор V и предназначенного мар­шрутизатору Vj ;

yi j (k) = (k)At, (k) - интенсивность по­ступления нагрузки в момент времени tk от або­нентов сети на узел V, предназначенной для мар­шрутизатора Vj; At - период перерасчета управ­ляющих переменных.

На введенные переменные состояния и управ­ления с целью исключения возможности перегрузки маршрутизатора, что связано с ограниченностью буферной очереди на маршрутизаторе и пропускных способностей каналов связи (интерфейсов маршру­тизатора), наложены ограничения

. N

0 < ui,i(k) < 1, x u^(k) < 1, i=1

N

0 < xi,j(k) < xmax, xxi,j(k) < xmax, (2)

j=1

где xmax - объем буфера на маршрутизаторе.

Систему уравнений (1) в векторно-матричном виде можно представить следующим образом:

x (k +1) = A(k)x (k) + B(k)u (k) + y (k), (3) где x(k) - вектор переменных состояния (объемы буферов маршрутизатора);

u(k) - вектор переменных входа (балансировки нагрузки);

y(k) - вектор управляемых возмущений (внеш­ней нагрузки);

B(k) - матрица, элементами которой в соответ­ствии   с   выражением   (1)   являются величины

±bi,j(k);

A(k) - единичная матрица.

Задача распределения нагрузки в рамках при­веденной модели может быть рассмотрена как зада­ча по минимизации некоторого целевого функцио­нала при наличии ограничений.

Для решения подобного рода задач на сего­дняшний день существует достаточно большой вы­бор методов [6, 7].

Так, в качестве критерия оптимизации выбира­ем минимум квадратичного функционала:

J =x xT(k)Qx(k) + uT(k)Ru(k) -> min, (4)

k=0

где Q, R - диагональные, положительно опреде­ленные весовые матрицы, определяемые приоритет­ностью очереди на маршрутизаторе и важностью каналов связи, выходящих из этого маршрутизатора; K - количество интервалов At. На рис. 1 представлена структурная схема ра­боты метода ЛДМ.

Исследование эффективности метода локальных динамических моделей

Исследование эффективности метода ЛДМ проводилось при помощи моделирования на основе однопродуктовой сети топология, которой показана на рис. 2.

Сеть состоит из передающего А (формирует поступающую нагрузку на сеть) и принимающего В абонентов, 6 маршрутизаторов и 10 каналов связи с соответствующими величинами их пропускных спо­собностей (Мб/с). При этом функции маршрутиза­ции в основном возлагались на маршрутизатор 1 (выделен рамкой на рисунке), который описывался предложенной математической моделью (3) с уче­том ограничений (2) и выполняли балансировку на­грузки согласно (4). Время моделирования Тм = 100 с с шагом At = 1с.

Входная нагрузка

Процесс балансировки нагрузки

МАРШРУТИЗАТОР

Входной

Таблицы маршрутизации и топо-

Выходной

буфер

логии. Сведенья SNMP

буфер

Выходная нагрузка

Блок подготовки вводных данных и

выбор режима БН

xi,j(k)

 

yi,j(k)

A,B

bm,i(k)um,i(k) N

f

Nj

xbi,i(k)uij,i(k)

i=1

Математическая модель маршрутизатора для решения задачи

 

 

балансировки нагрузки

 

 

x(k + 1)

= A(k)x(k) + B(k)u(k)-

+ y(k)

\

x(k)

 

 

 

u(k)

n

f

 

 

Схема балансировки нагрузки в соответствии с критерием

 

K—1

 

 

 

 

J =x

- T x

(k)Qx(k) + uT(k)Ru(k)

min

 

k=0

 

 

 

 

uj,i(k)

Рис. 1. Структурная схема работы метода ЛДМ

Предполагали, что весь поступающий трафик направлен от маршрутизатора 1 к маршрутизатору 6. Для удобства проведения исследования процесс поступления нагрузки в сеть был детерминиро­ванным и задавался интенсивностью поступления трафика со значениями y(k) равными 70, 170, 270, 370, 470 и 500 Мб/с. При каждом из таких значений входной интенсивности, подбирались такие элементы матрицы R, при которых дости­гались равные значения элементов вектора u(k) , что позволяло достичь максимального равномер­ного   использование  пропускных способностей

выходных каналов связи B(k)u(k) и соответствен­но максимального значения нормированного по­казателя производительности сети за все время моделирования Pkn.

Математическая модель маршрутизатора 1. Из маршрутизатора 1 к маршрутизатору 6 ведут че­тыре непересекающихся маршрута, а именно 1,2,6; 1,3,6; 1,4,6; 1,5,6. Матрицы B, A, Q для маршру­тизатора №1 обозначим как B1, A1, Q1, они имеют следующий вид:

B1 = [50  100  150  200], A1 = [1], Q1 = [1], yu(k) = y(k).

Матрицу R для первого маршрутизатора обо­значим R1, и значения ее элементов подберем та­ким образом, чтобы добиться максимальной произ­водительности сети.

В итоге модель можно записать так: xu(k +1) = [1]- xu(k)

ui7,2(k) u7,3(k) u7,4(k) _uu(k)_

Начальные условия являются нулевыми для векторов x(k), u(k) в момент времени t0.

Определение показателей производительности ТКС. Эффективность функционирования сети за время моделирования Тм , которое содержит K временных интервалов ( Тм = KAt) оценивалась по показателям, рассмотренным в [5].

— [100 60]-

+ y1,7(k).

Рис. 2. Топология сети

Результаты моделирования

В рамках приведенной модели при заданных начальных условиях были получены результаты моделирования, приведенные в табл. 2.

Из полученных результатов видно, что макси­мальная производительность сети при разных вели­чинах входной интенсивности поступающей нагруз­ки достигалась при разных значениях диагональных элементов матрицы R , однако прослеживается яв­ная пропорциональная зависимость с незначитель­ными отклонениями. Обобщая полученные резуль­таты можно сделать вывод по рекомендациям в вы­боре величин значений диагональных элементов матрицы R , а именно каналу связи с максимальной пропускной способностью присваивать значение 1, а остальным пропорционально отношению их пропу­скной способности к пропускной способностью ка­нала со значением 1.

Также из полученных результатов видно, что при низкой загруженности локального участка ис­пользование методов БН не дает выигрыша по сравнению с маршрутизаций по кратчайшему пути.

Страницы:
1  2 


Похожие статьи

А В Воробьев - Исследование эффективности метода локальных динамических моделей