Статья опубликована в №49 (сентябрь) 2017
Разделы: Информационные технологии
Размещена 26.09.2017. Последняя правка: 26.09.2017.
Просмотров - 3841

Построение оптимального сетевого графа

Лесных Екатерина Юрьевна

Тольяттинский государственный университет

Студентка кафедры «Прикладная математика и информатика»

Гущина Оксана Михайловна, кандидат педагогических наук, доцент кафедры

УДК 004.65

Введение

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

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

Пользователей интернета с каждым годом становится все больше [13], поэтому ресурсы телекоммуникационных компаний должны увеличиваться непрерывно, чтобы обеспечить связь по всему миру. 

Каждый оператор сети имеет множество разнообразного оборудования, количество которого увеличивается с каждым годом. Для расширения сети ему необходимо запустить новое оборудование в специализированном помещении с достаточным энергопитанием. Все это стоит больших денег: возрастает энергопотребление, появляется необходимость в найме квалифицированного персонала, и в капитальных, операционных затратах. Также аппаратные сетевые устройства имеют свойства устаревать, их функционал становится недостаточным, что приводит к повторению циклов «закупка – проектирование – интеграция – развертывание». Это не увеличивает доходов оператора сети, а скорее приводит к тому, что расходы на построение сети постепенно начинают опережать доходы, так как срок службы оборудования с каждым годом становится меньше [16].

Актуальность работы определяется тем, что описанный путь развития операторских сетей устарел, нужны свежие взгляды на бизнес сервис-провайдеров и операторов сети. Одно из решений данной проблемы – это виртуализация сетевых функций - Network Functions Virtualization (NFV), связанная с концепцией программно-конфигурируемых сетей - Software Defined Network (SDN) [13]. Данная концепция позволит экономить средства на покупке нового оборудования. 

Объект исследования - виртуальные функции программно-определяемой сети SDN.

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

Цель – разработка модели оптимального построения сетевого графа последовательности виртуальных функций для стабильной работы программно-определяемой сети SDN.

Для достижения цели были поставлены следующие задачи:

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

Существующая реализация построения графов сети

Разработкой архитектуры NFV MANO (Network Function Virtualization, далее NFV, Management and Orchestration, далее MANO) занимается специальная группа Европейского Института Телекоммуникационных Стандартов – ETSI NFV Industry Specification Group (ISG). Она устанавливает стандарты управления и оркестрации всех ресурсов NFV в рамках облачных центров обработки данных. Эти ресурсы включают в себя вычислительные, сетевые ресурсы, системы хранения данных, виртуальные машины и др [9].

Цель MANO – создание инфраструктуры для гибкого развертывания и управления сетевыми функциями, а также упорядочение хаоса, который может возникнуть в связи с быстрым темпом появления на рынке новых виртуальных сетевых функций [13].

В NFV свойствах, отношения и другие метаданные подключений указаны в абстракциях виртуальных ссылок. Для моделирования того, как виртуальные каналы подключаются к виртуальным сетевым функциям, NFV использует точки подключения (Connection Point, далее CP), которые представляют виртуальные и / или физические интерфейсы виртуальных сетевых функций (Virtual Network Function, далее VNF) и связанные с ними свойства, а также другие метаданные. Элементы сети расположены в сетевой службе (Network Service, далее NS). NS - это набор сетевых функций, который определяет функции и поведенческую спецификацию. Следовательно, NS можно рассматривать архитектурно, как график пересылки сетевых функций (Network Functions, далее NF), связанных между собой посредством поддержки сетевой инфраструктуры [12].

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

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

Под сетевым графиком (сетевым графом) понимается абстрактный математический объект, представляющий из себя множество вершин графа (VNFs) и набор рёбер, то есть соединений между парами вершин.

В настоящий момент вся настройка взаимодействия сетевых элементов лежит на NS-операторе. Он должен создать VNFs, произвести их настройку, создать необходимые CPs и виртуальные связи (Virtual link, далее VL), которые описывают базовую топологию подключений, а также другие необходимые параметры [11].

Недостатки данного алгоритма:

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

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

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

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

Опишем новый алгоритм деятельности NS-оператора:

• создание виртуальных сетевых функции;
• настройка виртуальных сетевых функции – создание CPs;
• прокладка путей между VNFs, в тех случаях, когда это необходимо. Если же порядок взаимодействия виртуальных сетевых функций не имеет значения, то граф полностью строится автоматически.

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

• трафик не должен проходить через одну вершину более одного раза;
• трафик должен пройти через все вершины.

Рассмотрим основные определения, которые будут использоваться в работе.
Нагруженным неориентированным графом G=(V,E,U) называется тройка множеств:

• V=(v₁,v₂,…,v_n) – множество вершин, числом вершин будем считать |V|=n;
• E⊆V×V – множество ребер графа {v_i , v_j }=e(i,j), будем считать, что |E|=m – количество ребер графа.
• U:E →[0, +∞) - весовая функция на ребрах, весом ребра обозначим u(v_i,v_j ) между вершинами v_i и v_j. Для вершин, не связанных ребром, положим u(v_i,v_j )=∞.

Нагруженный граф будем задавать с помощью матриц длин ребер.
Если {v_i,v_j }∈E, то вершины v_i,v_jназываются смежными.
Ребро e(i,j) инцидентно вершинам v_i и v_j, если v_i,v_j∈V и e(i,j)∈E.
Количество ребер графа, инцидентных v_i называют степенью d(v_i) вершины v_i.
Если справедливо m≪ n², то граф называется разреженным.
Если любая пара вершин соединена одним ребром, то такой граф называют полным.
Путь в графе – чередующаяся последовательность вершин и ребер ∏(_io,jk)= ∏(v(_i0 ),v(_jk ))=v(_i0 ),e(i_0,i1 ),v(_i1 ),…,v(_i(k-1) ),e(_i(k-1),ik ),v(_ik ) , каждое ребро инцидентно двум вершинам – непосредственно предшествующей ему и непосредственно следующей за ним.
Сумма весов входящих в путь ребер – это длина пути.
Кратчайшим путем ∏(v_i,v_j) между вершинами v_i и v_j называют путь, имеющий минимальную длину между вершинами v_i и v_j.
Длину кратчайшего пути между v_i и v_j (m(v_i,v_j )=0,i=1,…,n) называют расстоянием m(v_i,v_j ) между вершинами v_i и v_j.
Если между любыми двумя вершинами графа существует путь, то есть m(v_i,v_j )<∞ для всех i,j, то граф называют связанным.
Графы, не имеющие петель и кратных ребер, называются простыми.
Между начальной и конечной вершинами графа может существовать несколько кратчайших путей равной длины. Это обстоятельство в данной работе не является существенным, поэтому при всех упоминаниях кратчайшего пути будем подразумевать любой кратчайший путь.
Пусть ∏(v_i,v_j) – кратчайший путь в графе G. Тогда любой его подпуть тоже является кратчайшим.
Классическая задача о кратчайшем пути (shortest path problem, SP) [21] в наиболее общем виде формулируется как «найти пути между элементами двух множеств вершин V1 и V2 графа так, чтобы длины найденных путей являлись минимальными в данном графе между соответствующими вершинами».
Задача о кратчайшем пути является одной из важнейших в алгоритмической теории графов.
Различают два варианта задач MDSP (Multiple-destination shortest paths):

• нестационарная задача – вес ребра e(i,j) равен времени перемещения из v_i в v_j , которое задается предопределенной функцией времени, т.е. вес ребра e(i,j) в некотором пути зависит от времени начала обхода пути и от времени, потраченного на обход ребер, предшествующих e(i,j);
• вариант задачи, при котором граф меняется через определенные промежутки времени, являясь статическим между этими промежутками. Второй вариант задачи может иметь две формулировки: частично динамическая задача (можно либо только удалять ребра, либо только добавлять), полностью динамическая задача (разрешены и удаление, и вставка ребер). В обеих формулировках разрешена операция изменения веса ребра setWeight(i, j, w) .

Нестационарная задача DSP с применением техник для задачи SP разрешима за полиномиальное время на графах, обладающих свойством FIFO [2], и NP-трудна на графах этим свойством не обладающих [2]. Задачи DSP с периодическим изменением графа могут быть решены сведением к соответствующим задачам и вычислением кратчайших путей графа «с нуля» при каждой необходимости или с использованием техники реоптимизации кратчайших путей [2].
Решение классической задачи SP на полученном для данного графа G спаннере (spanner) H. Говорят, что граф H=(V,E^s ): E^s⊆E (α,δ) - спаннер графа G=(V,E), если ∀v_i,v_j∈V справедливо m^h (v_i,v_j )≤ α∙m^g (v_i,v_j )+ δ, где m^h (v_i,v_j ),m^g (v_i,v_j ) – кратчайшие расстояния между вершинами v_i,v_jв графах H и G соответственно.
В простейшем случае, когда рассматривается задача SSSP, классическим алгоритмом поиска решения считается поиск в ширину (breadth-first search, BFS) [2]. BFS может решать задачу как на неориентированных, так и на ориентированных графах. Принцип работы алгоритма состоит в обходе вершин графа в порядке обнаружения и выполнение процесса релаксации для дуг между текущей вершиной и каждой новой обнаруженной. Процесс релаксации дуг – уточнение (уменьшение), если это возможно, оценки длины пути от исходной вершины до новой обнаруженной проведением пути через текущую вершину. BFS используется как основа алгоритмов для многих других задач на графах и имеет временную оценку сложности O(m+n), являясь быстрейшим для SSSP на ненагруженных графах.
Существует также ряд важных алгоритмов для неклассических задач о кратчайшем пути. Алгоритм A^* (A star) [6] – информированный поисковый алгоритм, используемый для поиска кратчайших путей из исходной вершины s, если для графа известна дополнительная информация. Обход вершин в алгоритме производится методом BFS, а порядок обхода вершин определяется эвристической функцией f(x)=g(x)+h(x) , где g(x) – известное расстояние от s до x , а h(x) – эвристическая оценка расстояния от s до x, которая должна быть допустимой эвристикой [6].
При решении задачи SPSP, могут применяться двунаправленные версии алгоритмов, используемых для поиска путей (A^*, BFS, Дейкстры). При двунаправленном поиске [7] выполняется одновременный поиск из исходной вершины s и вершины назначения t. Асимптотическая сложность двунаправленного поиска определяется через коэффициент ветвления b [7] как O(b^(d/2) )+O(b^(d/2) ) относительно сложности O(b^d ) однонаправленной версии поиска.
Если граф является ориентированным ациклическим (DAG), решение задачи SSSP на нем может быть получено за время O(m+n) [2]. Сначала вершины графа сортируются в топологическом порядке, после производится ослабление ребер, выходящих из каждой вершины.
Такого рода алгоритмы основываются на понятие об иерархии вершин – кратчайшие пути между сильно удаленными друг от друга вершинами графа чаще проходят через «более важные вершины» (highway nodes), чем через остальные. Соответственно, такие алгоритмы сочетают в себя способ построения иерархии и алгоритм, используемый для поиска путей на получившейся иерархии.
Используя алгоритм поиска в ширину BFS, определим величину длины дуги:
m=min⁡s_i , i ϵ [1;N], (1.1)
где si – величина, вычисляемая по формуле:
si= ∑_(j=1)^(N-1)q_i∙t_i , (1.2)
где q_ij={0,1} – булева функция, значение которой задается в зависимости от наличия отклика вершины v(j+1) на сигнал от vjдля -го графа,
t_ij – время выполнения вершиной v_j тестовой команды.
Определим алгоритм для нахождения оптимального сетевого графа последовательности виртуальных функций:

1. Рекурсивно, начиная с вершины «Primary Inputs» (от входов схемы у выходам), для всех смежных вершин произведем естественное соединение соответствующих отношений и вычислим значение si для конечной вершины.
2. Рекурсивно, начиная с вершины «Primary Outputs» (от выхода схемы к входам), для всех смежных вершин произведем естественное соединение соответствующих отношений, и спроецируем результат на начальную вершину.

Для реализации построения графов рассмотрим 2 способа их представления: с помощью матрицы расстояний и с помощью списка смежности.
Матрица расстояний (таблица 1) является удобным способом представления плотных графов, в которых количество ребер примерно равно количеству вершин в квадрате. В данном представлении заполняется матрица размером M на M, где M – количество вершин, помещая в ячейку A[i][j] значение расстояния между i-ой и j-ой вершинами:
Матрица расстояний

	VNF#1	VNF#2	VNF#3
VNF#1	0	20	37
VNF#2	20	0	13
VNF#3	37	13	0

Матрица расстояний - это способ представления графов, подходящий для ориентированных и неориентированных графов. Неориентированные графы представляются в виде симметричной матрицы A, так как, если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i. Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю [17].
С помощью данного способа представления, можно быстро проверить существует ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u] [17].
Другим способом представления графов являются списки смежности. Этот способ представления больше подходит для разреженных графов, то есть графов, у которых количество ребер гораздо меньше, чем количество вершин в квадрате. В данном представлении используется двумерный массив A содержащий M списков. В каждом списке A[i] содержатся все вершины u, так что между v и u есть ребро. Память, требуемая для представления, равна M + N, где M – количество вершин, а N – количество ребер графа.
Сравнив способы представления графов, делаем вывод, что для описанной предметной области больше подходят списки смежности, так как в графах, которые предстоит строить, количество ребер гораздо меньше, чем количество вершин в квадрате, следовательно, нет необходимости использовать таблицы смежности, которые занимают значительно больше памяти.
Результатом решения задачи, поставленной выше, на графе G является матрица расстояний Mr. Элементы матрицы расстояний M для вершин vi,vj из графа G изменяются по формуле m(vi,vj )= m^r (vi,vj) и производится изменение матрицы последовательностей P по формулам:
p(v_i,v_j )={(p^r (v_i,v_j ),если m(v_i,v_j )>m^r (v_i,v_j ) и p(v_i,p^r (v_i,v_j ))=∞
                p(v_i,p^r (v_i,v_j )),если m(v_i,v_j )>m^r (v_i,v_j ) и p(v_i,p^r (v_i,v_j ))≠∞)(1.6)
где v_i – первая вершина с координатами (X_k,Y_l),k=1…N,l=1…N,
v_j – вторая вершина с координатами (X_q,Y_p),q=1…N,p=1…N,
p^r (vi,v_j ) – элементы матрицы последователей P графа G. Найденные пути между вершинами графа G будут гарантированно кратчайшими.
Значения матриц M и P задаются следующим образом:
m(v_i,v_j )= u(v_i,v_j ) (1.7)
p(v_i,v_j )={(v_i,если u(v_i,v_j )≠∞
               ∅,если u(v_i,v_j )=∞) (1.8)

Заключение

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

• программный модуль должен строить N графов минимальной длины;
• программный модуль должен строить оптимальный сетевой граф;
• программный модуль должен быть оснащен юнит-тестированием.

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

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

1. Божко В. П. Информационные технологии в статистике: учеб.-практ. пособие / В. П. Божко. - Москва : Евразийский открытый институт, 2010. - 167 с.
2. Демидов Д. В. Использование реляционной теории при оптимальном проектировании интегральных схем: науч. работа / Д. В. Демидов – Санкт-Петербург : ИТМО, 2015. – 79 с.
3. Информационные технологии в профессиональной деятельности: учеб. пособие / авт.-сост. А. А. Широких. - Пермь : Пермский гос. гуманит.-пед. ун-т, 2014. - 61 с.
4. Клочко И. А. Информационные технологии в профессиональной деятельности: учеб. пособие / И. А. Клочко. - Саратов : Вузовское образование, 2014. - 236 с.
5. Мишин А. В. Информационные технологии в профессиональной деятельности : учебное пособие / А. В. Мишин, Л. Е. Мистров, Д. В. Картавцев. - Москва : Российская академия правосудия, 2011. - 311 с.
6. Силич В. А. Реинжиниринг бизнес-процессов: учеб. пособие / В. А. Силич, М. П. Силич. - Томск : ТУСУР, 2014. - 199 с.
7. Тимеряев Т. В. Методы и алгоритмы управления маршрутизацией в транспортных сетях на основе оперативной обработки информации в разреженных графах: науч. работа / Т. В. Тимеряев – Уфа : ФГБОУ ВПО, 2015. – 203 с.
8. Юдин К. А. Автоматизация проектирования с применением Autodesk Inventor 2012: учеб. пособие / К. А. Юдин ; Белгородский гос. технол. ун-т им. В. Г. Шухова. - Белгород : БГТУ : ЭБС АСВ, 2013. - 128 с.
9. Dr. Danny Coward Java EE 7. The Big Picture / McGraw-Hill – 2015 – 513 p.
10. Farrell J. Java Programming / Course Technology 2015 – 1026 p.
11. Hof P. van’t, Kamiński M., Paulusma D., Szeider S., Thilikos D.M. On Graph Contractions and Induced Minors // Discrete Applied Mathematics. 2012. Vol. 160. P.
12. Oaks S. Java Performance: The Definitive Guide – O’Reilly, 2014.
13. Pilgrim, P. Digital Java EE 7 Web Application Development / P. Pilgrim — Packt Publishing, 2015. – 486 с.
14. Sam Newman, Building Microservices - O'Reilly Media, 2015. – 280 pages.

Рецензии:

27.09.2017, 7:45 Бондарь Иван Михайлович
Рецензия: В статье Лесных Е.Ю. и Гущиной О.М "Построение оптимального сетевого графа" рассмотрены алгоритмы построения сетевых графов и выбора оптимального пути, описан разработанный алгоритм построения оптимального сетевого графа. Теория графов является достаточно разработанной, но применение этой теории к решению практических задач весьма ограничено. В этом плане, полагаю, рецензируемая статья представляет собой определенный интерес и может быть опубликована. В качестве замечания: считаю, было бы интересно при расчете оптимального пути применить оптимизационные методы линейного программирования с использованием современных информационных технологий, например решение оптимизационных задач с помощью электронных таблиц Exсel. Бондарь И.М.



Комментарии пользователей:

Оставить комментарий