Применение ортогональной модели телекоммуникационной сети для решения задачи оптимального распределения трафика

1. Введение

Решение задачи управления трафиком является одной из ключевых задач телекоммуникационной индустрии, классификация таких задач приведена в ^[1,2]. По умолчанию такую задачу решают протоколы динамической маршрутизации внутреннего и внешнего шлюза, которые обеспечивают, как правило, поиск маршрута с минимальной стоимостью. Для одновременной передачи пакетов по маршрутам с неравной стоимостью необходимо вносить корректировки в стандартные конфигурационные параметры маршрутизаторов задавая коэффициенты балансировки для каждого маршрута, таким образом, задача автоматического управления трафиком в телекоммуникационных сетях на данный момент не решена в полном объеме, что делает ее актуальной, очевидно, что основной проблемой является сложность решаемой задачи, так как необходимо решать задачи линейного и нелинейного программирования в реальном масштабе времени для больших систем, как телекоммуникационные сети (ТКС). Перспективным направлением для применения задач подобного типа является концепция, заложенная в технологию программно-конфигурируемых сетей (SDN – software-defined networking) ^[3,4], согласно которой для управления сетью будет создан прикладной интерфейс, не зависящий от производителя. В связи, с чем в данной статье предлагается алгоритм, позволяющий решить задачу управления трафиком, с целью повысить эффективность работы ТКС. Согласно приведенным критериям классификации в ^{[1, 2]}, данную задачу по типу математического подхода можно отнести к потоко-ориентированной на основе тензорной модели. В ^[2] сделан вывод, что используя тензорные модели описания телекоммуникационных сетей совместно с централизованным управлением, позволит более эффективно использовать ресурсы сети. В настоящее время ведутся активные исследования по применению тензорного анализа сложных систем для решения телекоммуникационных задач основы, которых заложены в работах ^[5,6] для получения математических моделей ТКС. Анализ статей по данной тематике показал, что существует несколько школ в России и Украине. В России можно отметить работы Петрова М.Н. и его учеников ^[7-10], работы Пасечникова И.И. ^[11-13], Золотарёва С. В. ^[14-16], в Украине можно выделить работы Лемешко А.В. ^[17-22]. Анализ проведенных работ показывает, что авторы шли своим путем развивая применение тензорного анализа для описания ТКС, каждый из авторов использует свое инвариантное уравнение и набор геометрических объектов, которыми описывается ТКС. В данной статье также применяется свое инвариантное уравнение и набор геометрических объектов.

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

Особенность тензорного подхода к описанию ТКС является минимально необходимое число независимых переменных, которыми описывается ТКС, в отличии от задач ^[23-25], где в основу положены алгоритмы поиска всех беспетельных маршрутов между каждой парой источник приемник, на основании чего составляется целевая функция с числом переменных равным числу найденных маршрутов. В данной статье, используя тензорный аппарат анализа сложных систем, целевая функция будет иметь меньшее число переменных, что снижает вычислительную сложность данной задачи.

2. Постановка задачи

Исходными данными для решения задачи оптимизации трафика сети служит топология сети провайдера, матрица запросов между отдельными сетями, потоки между сетями, как правило, задаются в виде матрица запросов, представляющую собой, матрицу размерности DxD, где элемент dij – показывает интенсивность потока от i-й сети до j-й сети Анализируемыми характеристиками являются потоки трафика и загрузка каналов связи при ограничениях на параметры качества обслуживания. В результате оптимизации будут предложены маршруты прохождения трафика между каждой парой сетей. Пусть топология сети провайдера представлена в виде ориентированного графа G(N,A), где каждое ребро графа определяет однонаправленный канал связи. Как известно из теории массового обслуживания в качестве математической модели однонаправленного двухточечного каналы связи может выступать одноканальная система массового обслуживания, так как алгоритм обслуживания пакетов в интерфейсе маршрутизатора/коммутатора соответствует модели обслуживания одноканальной СМО. Таким образом, в качестве модели всей сети выступает сеть массового обслуживания. Граф сети массового обслуживания может быть описан матрицей инцидентности I, каждый элемент которой равен -1 или 1 и показывает: входит или выходит ветвь i из узла j.

3. Общий подход к решению задачи тензорным методом

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

Поскольку все сети с топологией, состоящей из одинакового числа ветвей связаны между собой тензором преобразования, то среди множества проекций можно выделить так называемую примитивную сеть ^{[5, 6]}, примитивная сеть состоит из такого же количества ветвей, как и исследуемая сеть, но количество несвязанных компонент в ней также равно числу ветвей, в связи с чем, потоки в каждой ветви примитивной сети оказываются независимыми. Топология примитивной контурной сети показана на рисунке 1. Как видно в примитивной контурной сети каждой контурной интенсивности соответствует интенсивность в соответствующей ветви.

Рисунок 1 – Примитивная контурная сеть

Топология примитивной узловой сети показана на рисунке 2. Как видно в примитивной узловой сети каждой узловой интенсивности соответствует интенсивность в соответствующей ветви. Под узловой интенсивностью можно понимать сумму потоков втекающих или вытекающих из узлов

Рисунок 2 – Примитивная узловая сеть

Если определить математическую модель простейшего элемента сети, которым является одноканальная СМО, как или ^[26], то согласно постулату обобщения Крона если известна математическая модель, описывающая поведение простейшего элемента, то и система, состоящая из совокупности простейших элементов, будет описана такой же математической моделью только в матричном виде. Следовательно, математическая модель примитивной сети имеет тривиальный вид, и для примитивной контурной сети показывает связь контурных интенсивностей с контурными временами обслуживания и контурными загрузками.

(1)

где

λi (i=1…n) – интенсивность поступления, поступающая на вход, элемента сети;

ti (i=1…n) – среднее время обслуживания;

ρi (i=1…n) – загрузка i-го элемента.

Или в тензорном виде:

(2)

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

(3)

где

λi (i=1…n) – интенсивность поступления, поступающая на вход, элемента сети;

µi (i=1…n) – интенсивность обслуживания;

ρi (i=1…n) – загрузка i-го элемента.

Или в тензорном виде:

(4)

В данной статье рассматривается так называемый ортогональные сети, то есть сети, которые содержат, как замкнутые пути, так и разомкнутые, такие сети можно анализировать, приводя их к одному из двух типов сетей, либо к контурной, либо к узловой ^[27,28]. При анализе таких сетей в начале необходимо было определить тензор преобразования от примитивной сети к анализируемой, и после ряда преобразований получалась финальная система линейных уравнений.

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

Таким образом, в ортогональной сети базисными элементами будет совокупность линейно-независимых контуров и линейно-независимых разрезов. Следовательно, необходимо установить следующее преобразование.

, (5)

где - вектор, содержащий как узловые, так и контурные интенсивности в исследуемой сети;

- вектор примитивных элементов, содержащий как контурные, так и узловые примитивные элементы;

Х – тензор преобразования.

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

Определим структуру тензора преобразования X.

Выражения (5) можно записать развернутом виде:

(6)

Как видно из (6) тензор преобразования X состоит из двух составляющих, тензора А, который связывает узловые интенсивности примитивной сети с узловыми интенсивностями исследуемой сети, и тензора преобразования , который связывает контурные интенсивности примитивной сети с контурными интенсивностями исследуемой. Правило получение тензора А аналогично, тому как это было в ^[6], когда правило получения матрицы , заключается в том что необходимо однозначно сопоставить одной контурной интенсивности примитивной сети только одну контурную интенсивность исследуемой сети. Как известно из теории графов, совокупность всех ребер графа делиться на ветви и хорды, то есть контурная интенсивность в исследуемой сети соответствует интенсивности в той ветви примитивной сети, которая после преобразования в исследуемую сеть стала хордовым ребром.

Для получения тензора преобразования между примитивной и анализируемой сети можно воспользоваться математическим аппаратом теории графов, согласно которому переход между узловыми интенсивностями примитивной к узловым интенсивностям анализируемой сети обеспечивается с помощью матрицы инцидентности без одной строки, а связь между контурными интенсивностями обеспечивается с помощью матрицы хорд. Соответственно если придерживаться обозначений теории графов, то систему уравнений (6) можно записать в виде:

, (7)

где I’ – матрица инцидентности без линейно-независимой строки;

Н – матрица хорд графа.

Алгоритмы получения этих матриц известны, и сложность этих алгоритмов растет линейно с ростом числа ветвей в сети. Обозначим тензор преобразования за X, тогда уравнение (7) можно привести к следующему виду:

Соответственно проводя анализ по Крону ^[6] с учетом теории двойственных сетей ^{[5, 29]} можно убедиться в справедливости следующих соотношений :

(8)

где– фазовые загрузки примитивной сети;

– значение фазовых загрузок исследуемой сети.

(9)

– матрица фазовых интенсивностей обслуживания исследуемой сети

– матрица фазовых интенсивностей обслуживания примитивной сети.

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

(10)

А значение загрузок и интенсивностей поступления в каждой ветви можно определить следующим образом:

(11)

(12)

Системы уравнений (11) и (12) уже являются математическими моделями, описывающими распределения трафика в телекоммуникационной сети. Поскольку данные системы уравнений имеют бесконечное число решений, то для выбора оптимального решения зададимся следующей целевой функцией, учитывая, что интерфейсам маршрутизатора/коммутатора соответствует модели обслуживания одноканальной СМО, например М/М/1, то в качестве целевой функции можно предложить суммарное число пакетов находящихся на обслуживании во всех СМО.

, (13)

где - интенсивность обслуживания j-го интерфейса.

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

Полученный результат, однако, еще не говорит о том каким маршрутом пойдет трафик от источника до каждого из приемников, по этому следующим этапом необходимо рассчитать получившиеся маршруты, и интенсивность трафика по каждому из маршрутов. Для решения предположим, что через каждую ветвь данной сети проходит поток для каждого приемника, обозначим такой поток как , где n – число ветвей графа, i – число приемников. Таким образом, суммарный поток в ветви есть сумма потоков в этой ветви для каждого источника, значение же суммарной интенсивности в каждой ветви было получено в ходе оптимизации в векторе . Пусть потоки для каждого приемника в каждой ветви будут заданы в виде векторов столбцов , элементы которого будут выражены через контурные интенсивности. Отсюда следует вывод, что для данного случая число контурных интенсивностей необходимых для оптимального решения должно быть три, когда необходимое число контурных интенсивностей для нахождения маршрутов должно быть девять, то есть число приемников умноженное на число контурных интенсивностей. Тогда для определения маршрутов между каждой парой источник-приемник можно определить, решив следующую систему линейных неравенств:

, (14)

где N – число приемников;

n – номер ветви.

Система уравнений (14) имеет бесконечное число решений, так как число уравнений будет меньше числа неизвестных, но любое решение даст уже не просто распределение по ветвям, а позволит определить маршруты прохождения от источника к каждому приемнику. При этом необходимо стремиться к тому, чтобы число маршрутов между каждой парой источник-приемник было как можно меньше, то есть лучшим решение будет, то которое содержит больше всего нулей. Такое решение обеспечивается, если применить линейные методы решения системы неравенств с нулевыми начальными условиями.

4. Численный пример.

В качестве примера рассмотрим сеть массового обслуживания рисунок 3, которая моделирует гипотетическую телекоммуникационную сеть.

Рисунок 3 – Анализируемая СеМО

Для СеМО рисунок 3 введены линейно-независимые контурные интенсивности λα, λβ, λγ, и линейно-независимые узловые интенсивности λi i (1..9). Система уравнений (6) для СеМО будет выглядеть следующим образом:

В матричном виде, эта система уравнений будет выглядеть следующим образом:

Полученная система уравнений соответствует формуле (7), откуда получаем фазовые интенсивности исходной сети:

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

Очевидно следующее, все элементы матрицы равны нулю, так как каждый элемент является суммой потоков в одном из узлов. Элементы матрицы как правило, являются известными значениями при анализе и указаны в матрице запросов D.

Поскольку в данном случае рассматривается сеть с одним источником и тремя получателями, то матрица запросов будет представлять собой вектор размером 1х4, для численного примера предположим, что .

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

На основании формулы (9) получим фазовые интенсивности обслуживания исследуемой сети.

В качестве примера предположим, что матрица обслуживания примитивной сети будет задана в следующем виде:

Затем по формуле (10) получим значения фазовых загрузок исследуемой сети, подставляя их в выражение (12) получаем систему уравнений, показывающую однозначную связь между потоками в ветвях и потоками в контурах (хордах) анализируемой сети.

(15)

Используя вектор интенсивностей поступления (15) и значение интенсивностей обслуживания, и подставляя их в целевую функцию, находим ее минимум с учетом следующих ограничений:

Для решения оптимизационной задачи использовался метод сопряженного градиента в среде MathCAD.

Значение целевой функции в данной точке равно

Значение первых частных производных равны:

Малые значения производной указывают, что в найденной точке минимума значение целевой функции будет близко к минимальному.

Само же экстремальное значение функции определяется координатами:

Как видно одно из значений меньше нуля, следовательно, экстремальное значение находится за пределами области ограничений.

Значение целевой функции в точке экстремума равно

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

Подставляя минимальные полученные значения в (15), получаем распределение трафика по ветвям сети.

.

Для сети, изображенной на рисунке 3 система уравнений (14) будет записана в виде:

Используя встроенный алгоритм решения системы линейных неравенств в среде MathCAD получаем значения контурных интенсивностей для отдельно взятого получателя.

Имея непосредственную связь между контурными интенсивностями и интенсивностями в ветвях сети, находим потоки в каждой ветви для каждого приемника, тем самым определяя маршруты прохождения трафика.

Распределения трафика по сети от источника 1 к приемнику 8.

Рисунок 4 – Маршруты следования трафика от источника 1 к приемнику 8

Распределения трафика по сети от источника 1 к приемнику 10.

Рисунок 5 – Маршруты следования трафика от источника 1 к приемнику 10

Распределения трафика по сети от источника 1 к приемнику 11.

Рисунок 5 – Маршрут следования трафика от источника 1 к приемнику 11

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

Заключение

В данной статье приведен алгоритм получение метаматематической модели ТКС, позволяющий найти оптимальное распределение потоков информации по каналам связи в случае одного источника информации по критерию минимума пакетов находящихся на обслуживании. Перед анализом ТКС необходимо преобразовать к эквивалентной сети массового обслуживания, для чего каждый канал связи должен быть представлен своей СМО, симплексные каналы представляются одной СМО, дуплексные ­– двумя параллельно соединенными СМО направленные встречно друг к другу. Особенностью данного метода является то, что вместо независимых переменных в целевой функции выступают не всевозможные маршруты прохождения трафика между каждой парой источник-приемник, а фазовые переменные – контурные интенсивности, которых в общем случае будет меньше чем маршрутов. Тем самым снижается размерность целевой функции, а, следовательно, и ускоряется поиск оптимального решения. В свою очередь, с практической точки зрения, необходимо знать именно по каким маршрутам будет проходить трафик, так как эта информация необходима для управления маршрутизаторами или коммутаторами, поэтому после оптимального распределения трафика решается система линейных неравенств (14) также относительно фазовых переменных, количество которых больше числа фазовых переменных в целевой функции в N раз, где N число приемников. Следует отметить, что в данном случае решалась не самая общая задача, так как в общем случае число источников больше одного. В таком случае число фазовых переменных в целевой функции возрастет M раз, где М число источников.

Полученная модель позволит также оценить такие вероятностно-временные характеристики (ВВХ), как сквозная задержка и ее дисперсию, вероятность потерь пакетов при использовании в качестве модели канала связи СМО с ограниченной очередью. Поскольку ВВХ являются функциями от интенсивности поступления, интенсивности обслуживания и размеров буферной памяти обслуживающего интерфейса, то данные функциональные зависимости можно использовать в качестве ограничений при решении систем уравнений (11) или (12), или же в (14).

Дальнейшая перспектива исследования о применении тензорного анализа в ТКС лежит в получении математических моделей с учетом классификации трафика по классам и различных дисциплин обслуживания на интерфейсах коммутационных устройств, учета интенсивности потерь пакетов при их обслуживании и восстановлении потерянных данных источником. Необходимо также разработать методику получения коэффициентов взаимного влияния в метрическом тензоре, что позволит исследовать более широкий класс инфокоммуникационных систем.

Еще одним аспектом решения задачи оптимального распределения трафика требующего улучшения, являются момент не связанный с тензорным анализом. Как было показано, прежде чем перейти к нахождению непосредственно оптимального решения необходимо найти произвольное решение удовлетворяющее системе ограничений, данное решение будет начальной точкой, с которой начнется поиск оптимального решения, это связано с тем, что целевая функция имеет большое число точек разрыва второго рода. Это связано с тем, что каждое слагаемое целевой функции представляет собой среднее число пакетов находящихся в очереди, и при достижении загрузки равной единицы, значение средней очереди становится бесконечным. Такой же разрыв наблюдается у всех ВВХ, описывающих СМО. Из сказанного следует, что начальная точка должна лежать не только на монотонном участке с минимумом целевой функции, но и слева от точек разрыва. В связи, с чем необходимо разработать апроксимационные модели ВВХ для различных систем массового обслуживания, в которых устранена точка разрыва второго рода, тем самым при использовании такой аппроксимации отпадет проблема нахождения начальной точки, и в качестве нее можно будет использовать точку с произвольными значениями.