Статья опубликована в рамках: XXXVI Международной научно-практической конференции «Технические науки - от теории к практике» (Россия, г. Новосибирск, 23 июля 2014 г.)
Наука: Технические науки
Секция: Информатика, вычислительная техника и управление
Скачать книгу(-и): Сборник статей конференции
- Условия публикаций
- Все статьи конференции
дипломов
Статья опубликована в рамках:
Выходные данные сборника:
ОБ УПРАВЛЕНИИ ЗАГРУЗКОЙ ИСХОДЯЩИХ КАНАЛОВ СЕТИ RTMCDN ВО ВРЕМЯ ПЕРЕГРУЗОК
Манакова Ирина Павловна
аспирант Уральского Федерального Университета, РФ, г. Екатеринбург
Email:
ABOUT OUTBOUND CHANNELS LOAD BALANCING FOR RTMCDN DURING OVERLOAD
Irina Manakova
postgraduate student Ural Federal University, Russia, Ekaterinburg
Автор благодарит руководителя работы д.ф.-м.н. В.В. Прохорова за ценные замечания и оказанную помощь.
АННОТАЦИЯ
В работе рассматриваются задачи управления загрузкой исходящих каналов сети раздачи мультимедийных потоков реального времени (Real-Time Multimedia Content Delivery Network, RTMCDN) при возможных перегрузках на участках сети. В качестве решения задач предлагается использовать схему подключения приёмных устройств (плееров) зрителей. Приведённый в работе способ управления загрузкой заключается в переподключении плееров на менее загруженные узлы.
ABSTRACT
In this article we describe the problems of outbound channels load balancing of Real-Time Multimedia Content Delivery Network (RTMCDN) during overload. Circuit of connection media players and network nodes is used to address the problem. Method as mentioned in the article is that the media players switches to the less loaded nodes.
Ключевые слова: CDN; RTMCDN; потоковое мультимедиа; управление загрузкой каналов сети.
Keywords: CDN; RTMCDN; streaming media; outbound channels load balancing.
1. Перегрузка сети RTMCDN
Сети раздачи мультимедийного контента реального времени (Real-Time Multimedia Content Delivery Network, RTMCDN) используются для предоставления услуг онлайн-TV, конференцсвязи, телеприсутствия и др. Они строятся на базе глобальных IP-сетей. Пример организации раздачи контента сетью RTMCDN представлен на рис. 1:
Рисунок 1. Пример раздачи мультимедийного контента сетью RTMCDN
Из-за повышения спроса на мультимедийные услуги, которое наблюдается сегодня, а также из-за нестабильностей IP-сетей, RTMCDN испытывают большие нагрузки, часто находятся в состоянии перегрузки. Появляются задержки и прерывания, происходят отключения зрителей, оказывается невозможным подключить новых клиентов. Пребывание сети RTMCDN в состоянии перегрузки на протяжении длительного времени может вызвать прекращение доставки мультимедийного контента кому-то из зрителей.
Указанные выше ситуации вызывают ухудшение качества обслуживания клиентов, что снижает популярность конкретной RTMCDN, её преимущества по сравнению с конкурирующими сетями. В связи с этим, актуальным и целесообразным представляется решение задачи вывода сети RTMCDN из состояния перегрузки для сохранения высокого качества обслуживания клиентов.
Существующие алгоритмы (например, указанные в [5]) во многом не подходят для управления нагрузкой сети RTMCDN во время перегрузок. В [1—4] автором были определены особенности RTMCDN, которые можно использовать для управления сетью в случае перегрузки.
Сеть RTMCDN может оказаться в состоянии перегрузки в двух случаях. Во-первых, когда во время раздачи мультимедиа в IP-сети повышается нагрузка и появляются узлы, сигнализирующие о том, что они перешли в состояние перегрузки. Это может быть вызвано внешними обстоятельствами, например, DDOS-атакой или возникновением неисправностей на узле (узлах). Во-вторых, когда происходит подключение к сети нового клиента, но ни один из узлов не может его обслужить, так как подключение вызвало бы перегрузку узла.
В первом случае известно, насколько загрузка исходящего канала узла сети RTMCDN превышает отведённую норму. Во втором случае известно, какой поток запрашивает клиент (его качество, скорость передачи, разрешение видео и др.).
Указанные выше случаи порождают два типа задач по оптимизации нагрузки. Первый тип — «распределение загрузки каналов сети RTMCDN для оптимизации раздачи контента», второй тип — «перераспределение загрузки каналов сети RTMCDN для подключения нового клиента».
Задача второго типа сводится к N задачам первого типа, где N — количество узлов, к которым может быть подключен клиент. Из множества решений требуется выбрать оптимальное. Вследствие этого далее будем рассматривать задачу «распределение загрузки каналов сети RTMCDN для оптимизации раздачи контента».
Для решения задачи по распределению нагрузки будем использовать схему подключения плееров зрителей к узлам сети. В данном случае распределение нагрузки на сеть основывается на распределении загрузки исходящих каналов узлов.
Схема подключения плееров к узлам сети — это совокупность связей типа «узел-поток-плеер», которая характеризует загрузку исходящих каналов сети. Каждый клиент, подключаясь к сети с использованием мультимедийного плеера, запрашивает определенный поток. Некоторые узлы сети RTMCDN передают копии этого потока. Из общего количества узлов, передающих такой поток, выбирается наиболее подходящий, и плеер клиента подключается к нему, занимая некоторую часть пропускной способности исходящего канала узла. Набор таких связей образует схему подключения плееров. Клиент с подключённым к сети плеером становится зрителем.
Поскольку генераторами однотипных потоков являются в одно и то же время некоторые совокупности узлов сети, наименее нагруженные из них можно использовать для перераспределения нагрузки. В данном случае можно использовать способ переподключениия плееров.
«Переподключение плееров» — это процесс программного отключения плеера от того потока, который он получает в данный момент, и подключение к другому. Под «отключением» понимается не столько операция физического отключения от узла и подключение к новому, сколько запуск механизма перехода с одного потока на другой. В данной работе конкретные механизмы «отключения» и «подключения» не рассматриваются. Допускается, что переподключение всегда занимает одинаковое время.
«Переподключение плееров» направлено на освобождение требуемого объёма пропускной способности исходящего канала некоторого узла сети RTMCDN, чтобы обеспечить выход этого узла из состояния перегрузки и/или обеспечить подключение нового клиента. При изменении узла зрители должны получать тот же самый поток и того же качества, что и до момента отключения. Этим гарантируется сохранение качества обслуживания.
3. Переподключение плееров
Рассмотрим общую постановку задачи о переподключении плееров для распределения загрузки исходящих каналов сети RTMCDN. Предположим, что для переподключения отобрано множество узлов и множество клиентов, тогда постановку задачи можно сформулировать следующим образом:
Имеется некоторая сеть RTMCDN, состоящая из N узлов, передающих мультимедийные потоки. К узлам подключены приёмные устройства зрителей (плееры), которые получают некоторые потоки от сети.
О каждом узле Ri () известен набор параметров {ri, max, ri, RN,св, Ui, max, Ui, UN,св, Si}, где: ri, max — максимально доступная пропускная способность канала i-го узла; ri — занятая пропускная способность на i-м узле; RN,св определяет количество остаточной пропускной способности узла N и выражается, как rN,max – rN,; Ui, max — максимальное количество пользователей, которое можно подключить к i-му узлу; Ui — количество пользователей, подключенных к i-му узлу; UN,св определяет количество плееров, которые могут быть подключены к узлу N и выражается, как UN,max – UN.; Si — массив потоков, которые генерирует i-й узел; для каждого потока известна скорость передачи мультимедиа.
Каждое приёмное устройство зрителя (плеер) U j может быть подключено только к одному узлу. О нем известен набор параметров {bi,j, Bi,j, Yi,j, Ki,j}, где: bi,j — поток, который получает j-й клиент на i-м узле; поток выражается через скорость передачи мультимедиа; Bi,j — поток j-го пользователя «изменится»/«не изменится», если пользователя подключить к i-му узлу (); Yi,j — j-й пользователь «подключен»/»не подключен» к i-му узлу; (); Ki,j — j-й пользователь «может быть подключен»/«не может быть подключен» к i-тому узлу ().
Известно, что один из узлов находится в состоянии перегрузки. Необходимо оптимизировать схему подключения зрителей так, чтобы качество получаемых зрителями потоков не изменилось, а количество переподключений было минимальным.
Задача может быть описана в терминах линейного программирования. Для составления целевой функции и системы уравнений, представим условие задачи в виде схемы (таблица 1):
Таблица 1.
Схема подключения плееров зрителей
|
N1 |
N... |
NN |
||||
U1 |
Y1,1 |
b1,1 |
Y...,1 |
b...,1 |
YN,1 |
bN,1 |
|
B1,1 |
K1,1 |
B...,1 |
K...,1 |
BN,1 |
KN,1 |
||
U... |
Y1,... |
b1,... |
Y...,... |
b...,... |
YN,... |
bN,... |
|
B1,... |
K1,... |
B...,... |
K...,... |
BN,... |
KN,... |
||
UU |
Y1,U |
b1,U |
Y...,U |
b...,U |
YN,U |
bN,U |
|
B1,U |
K1,U |
B...,U |
K...,U |
BN,U |
KN,U |
||
|
U1, max |
R1, св |
U..., max |
R..., св |
UN, max |
RN, св |
|
В таблице 1 множество узлов представлено, как {N1, N2, ..., NN}, где N — количество узлов. Множество плееров представлено, как {U1, U2, ..., UU}, где U — количество плееров.
Параметр UN,max определяет максимальное количество плееров, которое можно подключить к узлу N. Параметр RN,св определяет количество остаточной пропускной способности узла N и определяется, как RN,св = rN,max – rN. Таким образом, для каждого узла задана нагрузка по зрителям и по объему пропускной способности канала.
Схема подключения плееров до момента анализа сети на предмет переподключения представляет собой набор значений Y = {Yi,j | , }, каждое из которых либо равно 0, либо равно 1. Параметры b, B, K накладывают дополнительные ограничения на схему подключения плеров.
Для поиска решения по оптимизации, необходимо составить новую схему подключения плееров X = {Xi,j | , } так, чтобы у каждого из узлов остаточная пропускная способность стала больше 0, при этом таблица X должна минимально (в равномерной метрике) отличаться от таблицы Y.
Математическую постановку задачи можно представить в виде системы:
(1)
Решая систему (1), мы получаем комбинаторную задачу с ограничениями, которую можно реализовать в виде программного кода на ЭВМ. Максимальное количество произведённых действий по перемещению будет равно NU и равно полному перебору всех возможных вариантов на матрице (табл. 1). Уменьшения количества итеративных шагов можно добиться за счет оптимизации выбора узлов и плееров или за счет оптимизации алгоритма перестановок.
4. Переподключение плееров в случае существования потоков меньшего качества
Мультимедийные узлы могут генерировать несколько исходящих потоков из одного входящего, осуществляя репликацию мультимедиа потока. Используя разные способы кодирования и декодирования, а также разные подходы к отправке мультимедиа, можно создавать несколько потоков разного качества (с разной скоростью передачи, размером кадра, количеством помех в кадрах и др.) для одного источника мультимедийных данных. Каждый такой поток при передаче от узла к узлу (от узла к плееру) занимает определённую часть пропускной способности канала.
Создаваемые системой потоки (как исходящие, так и входящие) можно представить в виде иерархии от потока с наилучшим качеством до потока с наихудшим. Если сеть RTMCDN или некоторые её узлы находятся в состоянии перегрузки, можно осуществить перераспределение нагрузки, используя эту иерархию. В данном случае методика управления загрузкой исходящих каналов сети заключается в переподключении плееров на потоки меньшего качества.
Учитывая новые условия, сформулируем задачу о переподключении плееров для распределения загрузки исходящих каналов сети RTMCDN.
Имеется некоторая сеть RTMCDN, состоящая из N узлов, передающих мультимедийные потоки. К узлам подключены зрители, которые получают некоторые потоки от сети. О каждом узле Ri известен набор параметров {ri, max, ri, RN,св, Ui, max, Ui, UN,св, Si}. О каждом плеере зрителя известен набор параметров {bi,j, Yi,j, Ki,j}. Один из узлов находится в состоянии перегрузки. Необходимо оптимизировать схему подключения зрителей так, чтобы количество переподключений и понижений качества мультимеедиа у зрителей были минимальны.
Схема подключения зрителей до момента анализа сети на предмет переподключения зрителей представляет собой набор значений Y = {Yi,j | , }, каждое из которых либо равно 0, либо равно 1. Для поиска решения по оптимизации, необходимо составить новую схему подключения зрителей X = {Xi,j | , } так, чтобы у каждого из узлов остаточная пропускная способность стала больше 0, при этом таблица X должна минимально (в равномерной метрике) отличаться от таблицы Y.
Обозначим q качество получаемого зрителем потока. Обозначим значение качества обслуживания j-го зрителя на момент появления сигнала о том, что некоторый узел перегружен. Обозначим значение качества обслуживания j-го зрителя после переподключения. Тогда должно выполняться условие .
Обозначим QY суммарное качество обслуживания сети на момент сигнала о том, что некоторый узел перегружен: . Обозначим QX суммарное значение качества обслуживания сети после переподключения зрителей: . Тогда должно выполняться условие .
Постановку задачи можно представить в виде системы:
(2)
Решая систему (2), мы получаем комбинаторную задачу с ограничениями, которую можно реализовать в виде программного кода на ЭВМ.
5. Переподключение плееров в случае ненадёжной сети
Описанные ранее содержательные постановки задач, а также их формализация, относятся к случаям, когда для сетей RTMCDN гарантируется стабильная работа на протяжении всего периода раздачи мультимедийных потоков реального времени. Такие ситуации встречаются в случае сетей с зарезервированными каналами, т. е. когда RTMCDN изолирована от других сетей. Как правило, такая сеть гарантирует постоянную работу за счёт того, что в ней передаются только мультимедийные потоки, раздаваемые самой RTMCDN, а внешний трафик мал и не влияет на передачу потоков реального времени. В этом случае сеть может гарантировать передачу потоков с практически постоянной фиксированной скоростью. В подобной сети увеличение нагрузки на каналы происходит в основном из-за подключения новых клиентов, а в редких случаях — из-за технических неполадок. Сеть RTMCDN, которая может гарантировать постоянную фиксированную скорость передачи потоков, будем называть надёжной.
Создание изолированной сети RTMCDN требует дополнительных затрат на резервирование каналов с гарантированной пропускной способностью в рамках существующих сетей или на создание выделенных каналов. Чаще используются публичные сети с разделяемыми ресурсами с негарантированной скоростью. Такие сети не могут гарантировать стабильность работы. Нестабильность вызывается внешним трафиком от других сетей или неполадками на промежуточных узлах IP-сети, которыми сложно (как правило невозможно) управлять в рамках RTMCDN. В этом случае нельзя считать, что скорость передачи мультимедийных потоков будет постоянной. Сеть RTMCDN, которая не может гарантировать фиксированную скорость передачи потоков, будем называть ненадёжной.
Введём коэффициент надёжности раздачи мультимедийных потоков — RD (Reliability of Distribution). Коэффициент надёжности будет определять то, насколько скорость передачи мультимедийного потока для конкретного плеера будет отличаться от фиксированной скорости, заданной для этого потока. Для любого исходящего потока каждого узла сети RTMCDN можно определить коэффициент надёжности.
Скорость передачи потоков и, как следствие, качество конечного мультимедиа определяются некоторым законом распределения. Введём характеристику «коэффициент надёжности» RD как функцию, описывающую зависимость скорости передачи потоков от времени и загрузки каналов сети. С уменьшением скорости передачи потоков (относительно той, что зафиксирована для данного потока) ухудшается качество конечного мультимедиа.
Вместо фиксированного значения bi,j (скорость потока, который получает j-й зритель на i-том узле), которое было определено в п. 2 и 3, реальная скорость передачи потоков будет равна . Таким образом, получаем задачу, в которой качество мультимедиа определяется законом распределения скорости передачи потоков.
Приведённые ранее задачи (п. 2, 3) модифицируем вводом коэффициента надёжности. При этом в целом постановка задач останется прежней.
В случае задачи, описанной в п. 2 (где понижение качества конечного мультимедиа не разрешено), система уравнений примет вид:
(3)
В случае задачи, описанной в п. 3 (где понижение качества конечного мультимедиа разрешено), система уравнений примет вид:
(4)
Значение коэффициента RD равное 0 на всём временном интервале означает, что клиент/зритель не может получать данный поток от узла. Значение коэффициента RD равное 1 на всём временном интервале означает, что клиент/зритель может получать от узла поток с фиксированной скоростью, которая равна допустимому максимуму. Значение коэффициента RD, равное некоторому постоянному числу на всём временном интервале означает, что клиент/зритель может получать от узла поток с фиксированной скоростью.
6. Общая постановка задач с учётом критерия оптимальности
В п. 2—4 были сформулированы постановки задач управления загрузкой исходящих каналов сети RTMCDN с использованием схемы подключения плееров к узлам сети и метода переподключения плееров.
Приведённые примеры касались случаев, когда перегруженным по загрузке исходящего канала становится один из узлов сети. Однако в практике нередки случаи, когда за сравнительно короткие промежутки времени перегруженными становится несколько узлов. Образуется очередь узлов, нуждающихся в разгрузке. Тогда задачу о «распределении загрузки исходящих каналов сети RTMCDN для оптимизации раздачи контента» с использованием метода переподключения для оптимизации схемы подключения плееров можно сформировать следующим образом:
Пусть имеется некоторая сеть RTMCDN, состоящая из N узлов, передающих мультимедийные потоки. К узлам подключены зрители, которые получают из сети определённые потоки. Каждый узел можно характеризовать некоторым ограниченным набором параметров R{a1, a2, …, ax}, где x — количество параметров. Мультимедийное устройство (плеер), при помощи которого зритель получает поток(и) от сети, также можно характеризовать некоторым ограниченным набором параметров U{b1, b2, …, by}, где y — количество параметров. Известно, что в сети RTMCDN существуют узлы, которые находятся в состоянии перегрузки по загрузке исходящего канала и образуют очередь. Необходимо оптимизировать схему подключения плееров зрителей таким образом, чтобы как можно большее количество узлов из очереди вышло из состояния перегрузки.
В данном случае целевая функция одна — максимальное количество узлов, выведенных из состояния перегрузки. Набор параметров, характеризующих узлы и плееры, как и уравнения, описывающие ограничения в задаче, аналогичны тем, что приведены в п. 2—4.
В общем случае можно сформулировать следующую постановку задачи о «распределении загрузки исходящих каналов сети RTMCDN для оптимизации раздачи контента»:
Пусть имеется некоторая сеть RTMCDN, состоящая из N узлов, передающих мультимедийные потоки. К узлам подключены зрители, которые получают определённые потоки от сети. Каждый узел можно характеризовать некоторым ограниченным набором параметров R{a1, a2, …, ax}, где x — количество параметров. Мультимедийное устройство (плеер), при помощи которого зритель получает поток(и) от сети, также можно характеризовать некоторым ограниченным набором параметров U{b1, b2, …, by}, где y — количество параметров. Известно, что схема подключения плееров не оптимальна по некоторому критерию. Необходимо распределить нагрузку между узлами сети так, чтобы оптимизировать схему подключения плееров.
Под критерием оптимальности можно понимать как существование перегруженных узлов, так и низкое качество конечного мультимедиа у зрителя (зрителей). Решением задач при этом может стать как поиск решения, минимизирующего нагрузку на узлах, так и поиск решения, максимизирующего качество конечного мультимедиа.
Список литературы:
1.Манакова И.П., Петров К.Б. К вопросу о подключении пользователей к мультимедиа-сети. «Инновации науке» // Материалы XVI международной заочной научно-практической конференции, 28 января 2013 г. Новосибирск: Изд. «СибАК», — 2013. — Ч. I. — С. 94—108.
2.Манакова И.П. Менеджер управления мультимедиа-сетью. «СПИСОК-2013» // Материалы всероссийской научной конференции по проблемам информатики, 23—26 апреля 2013 г., Санкт-Петербург. – СПб.: Издательство ВВМ, 2013. — С. 441—447.
3.Петров К.Б., Манакова И.П. Распределение пользователей по видеосерверам онлайн трансляции с условием минимального перемещения зрителей. Технические науки — от теории к практике // Материалы X международной заочной научно-практической конференции, 28 мая 2012 г. / [под ред. Я.А. Полонского]. Новосибирск: Изд. «Сибирская ассоциация консультантов», 2012. — С. 27—35.
4.Прохоров В.В., Манакова И.П. К вопросу об оптимизации построения мультимедиа-сетей. III Информационная школа молодого учёного: сб. научных трудов / ЦНБ УрО РАН; отв. ред. П.П. Трескова; сост. О.А. Оганова. Екатеринбург: ООО «УИПЦ», 2013. — С. 306—315.
5.Cisco Services Modules. Understanding CSM Load Balancing Algorithms [Электронный ресурс]. — Режим доступа. — URL: http://www.cisco.com/en/us/ products/hw/modules/ps2706/products_tech_note09186a00801adbde.shtml, свободный.
дипломов
Оставить комментарий