Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

DEVELOPING METHODS AND ALGORITHMS ROUTING DYNAMIC DATA FLOW OF APPLICATIONS AND SERVICES IN THE HETEROGENEOUS CLOUD PLATFORM

Bolodurina I.P. 1 Parfenov D.I. 1
1 Orenburg State University
The paper is devoted to the research of algorithms for dynamic routing of data flows in networks of data center used to operate heterogeneous cloud platforms. In the research the model is designed to describe the service level agreement in order to ensure the quality of service in data centers. A graph model of the physical support network is introduced which can be deployed over software-defined network. The problem of optimization of channel capacity management for the selected class of applications and services in a heterogeneous software-defined cloud platform in data center is solved. On the basis of the constructed models the algorithm balancing flows is designed to optimize adaptive routing and to reduce the response time of cloud applications and services, and as a consequence improve the user requests processing and reduce the number of failures.
heterogeneous cloud platform
data flows
applications
services
software-defined network
routing
1. Bolodurina I.P., Parfjonov D.I. Algoritmy kompleksnoj optimizacii potreblenija vychislitelnyh resursov v oblachnoj sisteme distancionnogo obuchenija [Tekst] / I.P. Bolodurina, D.I. Parfjonov // Vestnik Orenburgskogo gosudarstvennogo universiteta. 2013. no. 9. рр. 177–184.
2. Bolodurina I.P., Parfjonov D.I. Upravlenie potokami dannyh v vysokonagruzhennyh informacionnyh sistemah, postroennyh na baze oblachnyh vychislenij [Tekst] / I.P. Bolodurina, D.I. Parfjonov // Sistemy upravlenija i informacionnye tehnologii. 2015. no. 1.1. рр. 111–118.
3. Tarasov V.N. Izmerenie proizvoditelnosti programmno-konfiguriruemyh setej v centrah obrabotki dannyh [Tekst] / V.N. Tarasov, M.V. Ushakova, Ju.A. Ushakov // Intellekt. Innovacii. Investicii. 2013. no. 2. рр. 86–89.
4. Bolodurina I., Parfenov D., Shukhman A. Approach to the effective controlling cloud computing resources in data centers for providing multimedia services // Control and Communications (SIBCON), 2015 International Siberian Conference on. IEEE, 2015. рр. 1–6.
5. Charuenporn P., Intakosum S. Qos-Security Metrics Based on ITIL and COBIT Standard for Measurement Web Services // J. UCS. 2012. Vol. 18. no. 6. рр. 775–797, available at: www. http://jucs.org/jucs_18_6/
6. DAndria F. et al. Cloud4soa: multi-cloud application management across PaaS offerings // Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2012 14th International Symposium on. IEEE, 2012. рр. 407–414.
7. Zhu J., Zheng Z., Lyu M.R. DR2: Dynamic Request Routing for Tolerating Latency Variability in Online Cloud Applications // IEEE CLOUD. 2013. рр. 589–596.

В настоящее время доля использования технологии облачных вычислений для размещения приложений и сервисов в центрах обработки данных постоянно растет. Это обусловлено экономической эффективностью эксплуатации ИТ-инфраструктуры. Однако лавинный рост использования облачных приложений и сервисов приводит к появлению ряда проблем в существующей традиционной архитектуре центров обработки данных (ЦОД). Одной из таких проблем является проблема эффективной маршрутизации каналов связи как внутри самого ЦОД, так и за его пределами [3]. В существующих сетях передачи данных, как правило, используется ряд традиционных узкоспециализированных алгоритмов маршрутизации. Основной особенностью работы данных алгоритмов является оценка стоимости маршрута на основе набора метрик. Как правило, управление сетью осуществляется с двух сторон. С одной стороны, администраторы ЦОД задают правила, ограничивают и регулируют потоки передаваемых данных в определенных направлениях, с другой стороны, сами алгоритмы маршрутизации пытаются провести оптимизацию с точки зрения стоимости, рассчитанной на основе базовых метрик, используемых в протоколе [1–2]. Современные сетевые приложения, размещаемые в гетерогенной облачной платформе и генерирующие основной трафик в ЦОД, никак не учитываются в существующих протоколах, что оказывает существенное влияние на обеспечение качества обслуживания в сети (QoS) [4]. Задача обеспечения требуемого качества обслуживания в сетях передачи данных, задействованных в работе ЦОД, решается путем введения правил обработки потоков передаваемой информации в соответствии с определенным типом трафика. Характеристики качества обслуживания при предоставлении услуг облачными провайдерами формулируются в виде соглашений об уровне сервиса (Service Level Agreement, SLA), формируемых на базе стандартов ITIL и COBIT [5]. Однако задание статических правил для определенных потоков данных в современных конвергентных сетях недостаточно эффективно.

Для решения данной проблемы исследователями Стэнфордского университета разработана концепция программно-конфигурируемых сетей (ПКС). Она основывается на использовании технологии OpenFlow, которая позволяет осуществлять более гибкое управление сетью за счет анализа потоков данных, проходящих через коммутаторы. На специализированных контроллерах OpenFlow задаются динамические правила, осуществляющие перераспределение потоков данных на менее загруженные маршруты согласно заданным условиям. Данная архитектура также позволяет собирать информацию о состоянии сети в критически важных узлах. Существенным преимуществом технологии ПКС является легкость настройки и развертывания конфигурации на множество устройств внутри ЦОД [6]. Принципы, на которых основана данная технология организации сети, позволяют легко масштабировать предлагаемое решение. Технология программно-конфигурируемых сетей на текущий момент находится на пути становления, поэтому также не лишена недостатков [7]. Существующие сетевые операционные системы, используемые в контроллерах ПКС, пока не обладают должной гибкостью в плане маршрутизации и балансировки потоков данных. Предлагаемые разработчиками OpenFlow решения используют подходы, заложенные в традиционные протоколы маршрутизации, адаптируя и динамически изменяя таблицы правил для составления новых маршрутов. Такой подход учитывает конвергентность сети ЦОД, но по-прежнему не позволяет классифицировать потоки передаваемых данных в соответствии с заданными критериями (тип приложения или сервиса, объем передаваемых данных, пропускная способность канала, требуемая полоса пропускания, задержки, джиттер и т.д.), а также не дает возможность осуществлять балансировку нагрузки в каналах связи и между сетевыми устройствами. В связи с этим большое значение приобретают вопросы разработки эффективных адаптивных алгоритмов динамической маршрутизации потоков данных в сетях ЦОД, используемых для работы гетерогенных облачных платформ. Кроме перечисленных проблем современные алгоритмы маршрутизации должны решать задачи повышения надежности и производительности критически важных сегментов сети при передаче информации реального времени, например потоки данных видео или VOIP-сервисов и другие.

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

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

Формализованное описание модели SLA может быть представлено в виде следующего набора характеристик:

bol01.wmf (1)

где InfA – описание приложений и сервисов, а также перечисление объектов инфраструктуры ЦОД, задействованных для обеспечения их работы;

DateTime – сроки действия соглашения, а также дни и часы, когда будет действовать соглашение об уровне сервиса;

CntObj – количество объектов (пользователей и/или оборудования), входящих в соглашение об уровне сервиса;

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

Qupd – описание процедуры запросов на изменение, с указанием времени выполнения;

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

Cost – финансовое описание услуг, связанных соглашением об уровне сервиса;

Resp – разграничение зон ответственности, включая демаркацию границ, в пределах которых гарантируется соблюдение соглашения об уровне сервиса;

RPM – процедура разрешения рассогласований, связанных с соглашением об уровне сервиса.

Improve – процесс улучшения SLA.

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

bol02.wmf, (2)

где AvgAvl – средняя доступность, выраженная как среднее число сбоев на период предоставления сервиса;

MinUAvl – минимальная доступность для каждого пользователя;

AvgRespT – среднее время отклика сервиса;

MaxURespT – максимальное время отклика для каждого пользователя;

AvgBandwidth – средняя пропускная способность;

InfoReport – методика расчета метрик и частоты сбора отчётов.

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

bol03.wmf, (3)

где VON – множество вершин, представляющих собой сетевые объекты (коммутаторы и контроллеры); |VON| = N, EON – множество ребер графа, представляющих собой существующие физические соединения между сетевыми объектами; |EON| = M, WON – множество весов ребер, характеризующих параметры физического канала между сетевыми объектами.

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

bol04.wmf (4)

bol05.wmf – множество сетевых устройств (узлов / серверов / и т.д.);

bol06.wmf – множество дуг, представляющих собой активные сетевые соединения.

Кроме того, программно-конфигурируемая сеть (SDN) является подмножеством каналов связи физической опорной сети ЦОД. В каждый момент времени исходное множество сегментов SG, входящих в физическую опорную сеть центра обработки данных ON, можно разделить на два непересекающихся подмножества ST∪SR = SG. В первое множество (ST) входят сегменты сети, содержащие активные сетевые объекты, используемые ПКС для передачи потоков данных приложений и сервисов гетерогенной облачной платформы. Ко второму множеству (SR) будем относить сегменты опорной физической сети ЦОД, не задействованные в текущий момент времени для обеспечения работоспособности гетерогенной облачной платформы. При этом сегменты опорной физической сети множества SR так же могут содержать активные сетевые объекты, используемые для развертывания программно-конфигурируемой сети ЦОД. Множество SR сегментов опорной физической сети, как правило, используется для организации альтернативных каналов между узлами ЦОД, применяемых для балансировки и распределения нагрузки между сетевыми устройствами.

Для построения структурной схемы каналов опорной физической сети ЦОД можно построить дерево, отражающее существующие связи между сетевыми устройствами. Каждый канал между парой сетевых объектов промаркируем относительно двух свойств, характеризующих их расположение по отношению к гетерогенной облачной платформе: принадлежность одному из множеств SR или ST, а также стоимость передачи данных по данному каналу. При этом стоимость передачи данных по каналу является динамической величиной и зависит от множества факторов. Каждому каналу из множества сегментов ST поставим в соответствие канал или маршрут из множества SR, проходящий через несколько сетевых устройств, если прямой связи между сетевыми объектами не существует. Таким образом, получим три набора маршрутов, описывающих структуру связей в опорной физической сети ЦОД. К первому набору (А1) будем относить маршруты между парой сетевых устройств с одинаковой стоимостью. Ко второму набору (А2) будем относить маршруты с разной стоимостью. К третьему набору (А3) отнесем безальтернативные маршруты (маршруты, не имеющие аналогов в сегменте SR). Такие маршруты, и входящие в них каналы, являются узким местом опорной физической и программно-конфигурируемой сети ЦОД. При поиске оптимальных решений для построения пар альтернативных маршрутов для определенного потока данных следует избегать использования безальтернативных маршрутов, для этого им присваивается максимальный вес.

Для уточнения разработанной модели и приближения ее к реальной сети введем ряд ограничений. Предположим, что в экспериментальной программно-конфигурируемой сети ЦОД присутствует как минимум три класса приложений, таких как веб-приложения; case-приложения (прикладное ПО, доступное по DaaS или SaaS модели); видеосервисы. Каждый класс приложений генерирует в ПКС уникальный поток данных. Под потоком данных будем понимать запросы пользователей к каждому классу приложений. Каждому потоку данных в рамках трех классов приложений присвоим весовые коэффициенты k1, k2, k3. Каждый из перечисленных коэффициентов позволяет разделить заявки на классы и оказывает влияние на следующий набор параметров: время выполнения, маршрут, приоритет в очереди на обработку, интенсивность поступления, а также закон распределения, согласно которому осуществляется генерация потока данных.

Для решения задачи по оптимизации адаптивной маршрутизации и балансировки потоков данных в программно-конфигурируемой сети ЦОД необходимо опередить законы распределения трафика для каждого класса приложений, что позволит динамически распределять потоки данных по каналам, связывающим объекты доступа (виртуальные сервера, контейнеры и системам хранения) в гетерогенной облачной платформе. Для этого необходимо установить определенный маршрут и построить для него закон управления на временном интервале T = [t1, t2].

Динамический поток данных облачных приложений и сервисов гетерогенной облачной платформы в программно-конфигурируемой сети ЦОД можно описать следующей дискретной системой:

bol07a.wmf

bol07b.wmf, (5)

где bol08.wmf – доля пропускной способности канала между i-м и j-м сетевым узлом в момент времени t; N – количество виртуальных узлов в сети; K – количество классов приложений и сервисов в сети; bol09.wmf – пропускная способность каналов между i-м и j-м сетевым узлом (i ≠ j); bol10.wmf – объем потока данных (количество запросов пользователей), проходящий через сетевой узел i в момент времени t и предназначенной для передачи в направлении узла j; bol11.wmf – интенсивность поступающей нагрузки, которая определяется как суммарная интенсивность потока запросов пользователей, подключаемых к сетевому узлу i и ведущих обмен с j-м узлом; bol12.wmf – доля пропускной способности канала выделенного в сегменте программно-конфигурируемой сети (i, l), в момент времени t потоку запросов пользователей к приложению k-го класса, осуществляющего работу с данными в узле j.

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

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

bol13.wmf, (6)

где bol14.wmf – максимальный предел выделяемой доли пропускной способности, доступный сетевому объекту i в сегменте ПКС l для передачи потока данных в направлении объекта j; bol15.wmf – доля пропускной способности канала для сетевого объекта i в сегменте ПКС l, выделенная для передачи пакетов запросов пользователей к приложению k-го класса для реализации динамической стратегии управления виртуальными ресурсами при доступе к сетевому объекту j.

В качестве критерия оптимальности рассмотрим максимизацию производительности системы, достигаемой за фиксированный период T = [t1, t2], которая в рамках модели формализуется в виде целевой функции вида

bol16.wmf. (7)

Для решения задачи оптимизации применим итерационный метод, который позволяет исследовать динамику работы системы на интервале T = [t1, t2] и осуществлять управление пропускной способностью канала для выделенного класса приложений и сервисов гетерогенной облачной платформы в программно-конфигурируемой сети ЦОД.

Алгоритм оптимизации адаптивной маршрутизации и балансировки потоков данных приложений и сервисов в гетерогенной облачной платформе

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

Укрупненно алгоритм имеет следующий вид.

Шаг 1. Разбить множество каналов ПКС на подмножество каналов, которые входят в дерево маршрутов, проходящих через сегменты множества ST, подмножество альтернативных каналов, проходящих через сегменты множества SR.

Шаг 2. Сформировать оптимальные маршруты в ПКС для потока данных определенного класса приложения гибридной облачной платформы, на базе весов каналов связи для каждого из подмножеств.

Шаг 3. Для каждого канала ПКС определить точки вхождения в дерево оптимальных маршрутов и во множество альтернативных каналов.

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

Шаг 5. Если сетевой объект не является листом дерева, то вычислить альтернативные маршруты в ПКС для этого объекта, с учетом веса канала в ранее построенном дереве оптимальных маршрутов, и выбрать лучшее значения альтернативного маршрута. Процедура выполняется для формирования списка альтернативных маршрутов в случае динамического изменения нагрузки канала связи.

Шаг 6. Для каждого узла связи сформировать полный список альтернативных маршрутов в ПКС ЦОД.

Шаг 7. Анализируя полученную используемым протоколом маршрутизации информацию, определить, произошло ли изменение нагрузки какого-либо канала связи. Если да, то перейти к шагу 8, иначе – к шагу 7.

Шаг 8. Используя список альтернативных маршрутов, определить, требуется ли сменить текущий маршрут для текущего потока данных: если да, то перейти к шагу 9, если нет – к шагу 13.

Шаг 9. Для сетевого объекта, у которого потенциал уменьшился и у которого в список альтернативных маршрутов входит канал связи с изменившейся метрикой, определить путь минимальной длины и поместить канал, который привел к уменьшению потенциала сетевого объекта в дерево оптимальных маршрутов, а сменившийся канал из дерева оптимальных маршрутов – в множество альтернативных каналов ПКС, при необходимости произвести перерасчет весовой функции канала.

Шаг 10. Определить, уменьшился ли потенциал других сетевых объектов ЦОД, расположенных выше по иерархии, после выполнения перехода на альтернативный маршрут ПКС. Если да, то перейти к шагу 11, иначе – к шагу 12.

Шаг 11. Для каждого сетевого объекта ЦОД, у которого потенциал уменьшился, определить маршрут минимальной длины. Если новый минимальный маршрут для каждого объекта сети содержит канал из списка альтернативных маршрутов, то поместить данный канал в дерево оптимальных маршрутов ПКС, а канал из дерева оптимальных маршрутов – в множество альтернативных маршрутов.

Шаг 12. Построить новое дерево оптимальных маршрутов ПКС ЦОД.

Шаг 13. Передать текущие потоки данных приложений и сервисов по доступным маршрутам ПКС, пересчитать точки вхождения в дерево и во множество альтернативных маршрутов, переформировать список альтернативных маршрутов для каждого изменившегося сетевого объекта. Перейти к шагу 7.

Применение предложенного алгоритма оптимизации адаптивной маршрутизации балансировки потоков данных позволило снизить трудоемкость расчета оптимальной маршрутизации до значения O(kN), где k – число выполненных переходов к альтернативным маршрутам, N – число объектов в ПКС ЦОД. Таким образом, разработанный алгоритм позволяет ускорить поиск и выбор оптимальных маршрутов для потоков данных приложений и сервисов, расположенных в гетерогенной облачной платформе, в условиях динамических изменений нагрузки на каналах связи.

Для оценки эффективности разработанного алгоритма оптимизации адаптивной маршрутизации балансировки потоков данных приложений и сервисов в гетерогенной облачной платформе центра обработки данных, нами проведено экспериментальное исследование. В качестве базовой платформы выбрана облачная система Openstack. Для сравнения в эксперименте использовались алгоритмы, применяемые в OpenFlow версии 1.4, для управления маршрутами в ПКС сети. Для экспериментального исследования создан прототип среды ЦОД, включающий в себя основные узлы, а также программные модули для разработанных алгоритмов, выполняющие перераспределение потоков данных и приложений.

Для верификации разработанного алгоритма оптимальной маршрутизации и балансировки трафика в условиях динамических изменений параметров каналов в ПКС ЦОД были развернуты ряд экспериментальных сетей, состоящих из 25, 50, 100, 200, 300 и 400 объектов. Все сформированные запросы воспроизводились последовательно на двух экспериментальных площадках: с традиционной технологией маршрутизации (площадка 1, NW) и с применением технологии программно-конфигурируемых сетей (площадка 2, SDN). Данное ограничение введено в связи с необходимостью сопоставления результатов с традиционной инфраструктурой сети, не способной к динамической реконфигурации. При этом на площадке 2 проводились два испытания. В первом случае использовались типовые алгоритмы маршрутизации, применяемые в OpenFlow версии 1.4, во втором случае (NEW SDN) использовался разработанный алгоритм оптимизации маршрутизации. Время эксперимента составило один час, что соответствует наиболее длительному периоду времени пиковой нагрузки, зафиксированному в реальном трафике сети гетерогенной облачной платформы. В качестве базовой метрики оценки эффективности предлагаемого решения выбрано время отклика приложений и сервисов запущенных в гетерогенной облачной платформе. Результаты эксперимента представлены на рисунке.

Из анализа полученных результатов следует: применение алгоритма оптимизации адаптивной маршрутизации балансировки потоков данных на основе собранной информации об альтернативных маршрутах позволило снизить время отклика приложений и сервисов гетерогенной облачной платформы при динамическом изменении нагрузки на каналах по сравнению с традиционным сетями на 40 % и по сравнению с типовыми алгоритмами протокола OpenFlow версии 1.4 на 25 %. Таким образом, разработанный алгоритм является эффективным при построении оптимальных маршрутов и решении задачи балансировки трафика в ПКС ЦОД в условиях динамических изменений нагрузки на каналах связи.

bolod1.wmf

График зависимости времени отклика приложений и сервисов в гетерогенной облачной платформе от количества сетевых объектов в ЦОД

Выводы

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

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

Работа выполнена при поддержке РФФИ (научные проекты 16-37-60086 мол_а_дк и 16-07-01004).