Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,118

АЛГОРИТМ УПРАВЛЕНИЯ РЕСУРСАМИ СЕТЕЙ RTMCDN

Манакова И.П. 1
1 ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»
Для управления ресурсами сетей раздачи мультимедийного контента реального времени (Real-Time Multimedia Content Distribution Network, RTMCDN) во время полной или частичной перегрузки возможен способ «Переподключение плееров зрителей», основывающийся на балансировке загрузки исходящих каналов сетей. В работе описываются алгоритм переподключения плееров, программное решение для задач переподключения и результаты численного эксперимента. В ходе проведённых экспериментов были установлены зависимости времени поиска решения от количества мультимедийных узлов, от мощности вычислительной машины, от количества мультимедийных потоков, от методики поиска решения, от сложности задачи поиска и объема свободных ресурсов на узлах. Эксперименты показали, что реализованный алгоритм переподключения может использоваться для реальных сетей RTMCDN. Полученные результаты используются в разработанном комплексе по исследованию и управлению системами раздачи мультимедийного контента реального времени.
RTMCDN
CDN
сеть раздачи мультимедиа
система раздачи мультимедиа
1. Манакова И.П. Графическая среда построения мультимедийных CDN // Материалы международной науч.-практ. конф. «Молодёжь и наука» (23 мая 2014 г., г. Нижний Тагил) в 2 т. Т. 1 – Нижний Тагил: НТИ (ф) УрФУ, 2014. –
Т. 1. – С. 107–110. 197 с.
2. Манакова И. П. Об управлении загрузкой исходящих каналов сети RTMCDN во время перегрузок // Технические науки – от теории к практике: сб. ст. по материалам XXXVI междунар. научн.-практ. конф. – Новосибирск: Изд. «СибАК», 2014. – № 7 (32). – С. 30–42.
3. Манакова И.П. Менеджер управления мультимедиа-сетью. СПИСОК–2013 // СПИСОК-2013: Материалы всероссийской научной конференции по проблемам информатики, 23–26 апреля 2013 г., Санкт-Петербург. – СПб.: Изд-во ВВМ, 2013. – С. 441–447.
4. Петров К.Б., Манакова И.П. К вопросу о подключении пользователей к мультимедиа-сети. «Инновации науке» / И.П. Манакова, К.Б. Петров // Материалы XVI международной заочной научно-практической конференции, 28 января 2013 г. – Новосибирск: Изд. «СибАК», 2013. –
Ч. I. – С. 94–108.
5. Прохоров В.В., Манакова И.П. Модель системы раздачи мультимедийных потоков // Фундаментальные исследования. – 2014. – № 8 (часть 2). – С. 311–316.

Способ управления ресурсами сетей RTMCDN «Переподключение плееров»

Проблема управления нагрузкой сетей раздачи мультимедийного контента реального времени (Real-Time Multimedia Content Distribution Network, RTMCDN) [5] описана в [4], а также более подробно в [2], где приводится постановка задач управления нагрузкой сетей RTMCDN во время полной или частичной перегрузки. Предлагаемые там решения основываются на балансировке загрузки исходящих каналов мультимедийных узлов с использованием схемы подключения плееров зрителей (связи типа «узел – поток – плеер»). Способ управления нагрузкой назван «Переподключение плееров».

«Переподключение плееров» [2, с. 32] – это процесс программного отключения плеера от того потока, который он получает в данный момент, и подключения к другому потоку. Под «отключением» понимается не столько операция физического отключения от узла и подключения к новому, сколько запуск механизма перехода с одного потока на другой. В данной работе конкретные механизмы «отключения» и «подключения» не рассматриваются; предполагается, что переподключение всегда занимает одинаковое время.

«Переподключение плееров» направлено на освобождение части пропускной способности исходящего канала некоторого узла сети RTMCDN, чтобы обеспечить выход этого узла из состояния перегрузки и/или обеспечить подключение нового клиента [2, с. 33].

В [2] были приведены постановки некоторых типов задач переподключения плееров. Рассмотрим два из них.

Первый тип – «Классическое переподключение плееров». В данном случае одним из критериев поиска оптимального решения является условие, что при изменении узла зрители должны получать тот же самый поток и того же качества, что и до момента отключения. Этим гарантируется сохранение качества обслуживания. 

Второй тип – «Классическое переподключение плееров в случае ненадёжной сети». В данном случае учитывается тот факт, что сеть не может гарантировать стабильность работы. Нестабильность может быть вызвана внешним трафиком от других сетей или неполадками на промежуточных узлах IP-сети, которыми сложно (как правило, невозможно) управлять в рамках RTMCDN. В этом случае нельзя считать, что скорость передачи мультимедийных потоков постоянна.

Математическую постановку задач можно представить в виде системы усло-
вий [2, с. 39]:

766206.jpg (*)

Здесь N – количество узлов; U – количество плееров; Yi,j – схема подключения плееров до момента анализа сети на предмет переподключения; Xi,j – новая схема подключения плееров; Ui, max – максимальное количество пользователей, которое можно подключить к узлу i; Ri,св определяет объём остаточной пропускной способности узла i; bi,j – поток, который получает клиент j на узле i (выражается через скорость передачи мультимедиа); Bi,j – поток пользователя j «изменится»/«не изменится», если пользователя подключить к узлу i; Ki,j – пользователь j «может быть подключен»/«не может быть подключен» к узлу i; RD – коэффициент надёжности раздачи мультимедийных потоков, который представляет собой функцию, описывающую зависимость скорости передачи потоков от времени и загрузки каналов сети.

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

Алгоритм «Переподключение плееров»

Предлагаемый подход реализации алгоритма «Переподключение плееров» основывается на следующих шагах:

1. Выбор узла для осуществления операции переподключения: из очереди узлов, сигнализирующих о перегруженности, выбирается первый согласно принципу «первым пришёл, первым обслужен».

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

3. Проверка существования ресурсов для переподключения, уточнение схемы подключения зрителей:

3.1. Определение количества разнородных потоков, а также их связей. Исключение тех узлов, потоки которых нельзя использовать для переподключения. Если количество потоков на всех узлах равно 1, то переподключение невозможно.

3.2. Определение запасов пропускной способности сети. В зависимости от объёма запасов можно установить параметры переподключения: нужно ли распределить ресурсы так, чтобы на загруженном узле перегрузка стала равна 0, или же нужно рассмотреть варианты, когда на узле появятся дополнительные ресурсы, или же ресурсов недостаточно и нужно разгрузить узел, насколько возможно.

3.3. Определение загруженности сети по количеству зрителей. Формирование ответа на вопрос: можно ли задействовать зрителей для переподключения и каких из них.

3.4. Формирование схемы подключения зрителей с уточнением узлов, потоков и зрителей согласно пунктам 2.1–2.3 или же формирование ответа «переподключение невозможно» (пункт 4).

4. Поиск решения по переподключению.

4.1. Фиксирование того, насколько узел перегружен.

4.2. Фиксирование потоков, генерируемых на узле, от большего к меньшему.

4.3. Формирование вариантов освобождения ресурсов из суммы потоков, которые генерирует узел. Например, установлено, что узел перегружен на 5 Мбит/с. Узел передаёт потоки 1 Мбит/с, 2 Мбит/с, 3 Мбит/с. Варианты решения 5 = 3 + 2, 5 = 3 + 1 + 1, 5 = 2 + 1 + 1 + 1.

4.4. Проверка осуществления операции переподключения для решения, где участвует меньше всего зрителей. Для ситуации, приведённой в п. 4.3, сначала проверка варианта 5 = 3 + 2 (2 зрителя), затем 5 = 3 + 1 + 1 (3 зрителя), потом 5 = 2 + 1 + 1 + 1 (4 зрителя). Если на первом шаге появляются новые перегруженные узлы, то алгоритм срабатывает для них (второй шаг) и так далее. При этом происходит проверка с соседним по количеству зрителей вариантом.

4.5. Формирование результата по переподключению.

5. Формирование ответа о новой схеме подключения зрителей или же генерация сообщения «переподключение невозможно».

6. Проведение переподключения, если было установлено, что оно возможно.

7. Проверка существования очереди перегруженных узлов: если очередь не пуста, то возврат к пункту 1, если нет – то конец работы.

Согласно сформированным шагам разработано программное решение, которое реализует алгоритм «Переподключение плееров».

Программная реализация алгоритма «Переподключение плееров»

Используя технологию объектно-ориентированного программирования, были реализованы на языке Python программный класс Reconnection Algorithms и менеджер формирования задач. Язык программирования выбирался с точки зрения последующей интеграции решения в разрабатываемую среду [3] для анализа моделей систем раздачи мультимедийного контента реального времени [5].

Программная реализация алгоритма «Переподключение плееров» включает в себя несколько функций анализа:

1. Поиск решения по условию «разгрузить узел на Х, используя операции переподключения». Объём ресурсов, подлежащих понижению, задаётся некоторым значением Х. Например, понизить нагрузку на 15,4 Мбит/с или на 25,0 Мбит/с.

2. Поиск решения по условию «разгрузить узел на Х или максимум до Y, используя операции переподключения». Объём ресурсов, подлежащих перераспределению, задаётся в виде интервала [Х; Y], где Х – ресурсы, подлежащие понижению, Y – объём свободных ресурсов у системы. Если не удаётся найти решение при Х, осуществляется поиск при Х + ΔХ, затем при Х + 2∙ΔХ и так далее до Y.

3. Поиск решения по условию «разгрузить узел на Х или минимум до 0, используя операции переподключения». Объём ресурсов, подлежащих перераспределению, задаётся в виде интервала [0; Х], где Х – ресурсы, подлежащие понижению. Если не удаётся найти решение при Х, осуществляется поиск при Х – ΔХ, затем при Х –2∙ΔХ и так далее до 0.

4. Поиск решения по условию «снизить нагрузку узла насколько возможно, используя операции переподключения». Поиск решения начинается от некоторого Х (ресурсы, подлежащие перераспределению). Если решение при данном условии не будет найдено, осуществляется поиск по интервалу
[Х; Y] аналогично пункту 2. Если решение при данном условии не будет найдено, осуществляется поиск по интервалу [0; Х] аналогично пункту 3.

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

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

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

Апробация предлагаемых решений

После реализации алгоритма переподключения плееров зрителей в виде компьютерной программы были проведены тесты для сбора статистической информации о работоспособности предлагаемого решения.

Цель экспериментов – определение времени быстродействия программы и определение правильности решения.

Было проведено 2450 экспериментов с разными вариациями настроек, с разным объёмом ресурсов, подлежащих перераспределению, а также с разным объёмом свободных ресурсов на узлах, которые можно использовать. В ходе экспериментов были определены зависимости времени поиска решения от разных характеристик.

Зависимость времени вычислений от количества потоков, генерируемых мультимедийными узлами. Были организованы эксперименты с установками: 100 узлов, на каждом узле от 2 до 4 потоков размером от 1 до 5 Мбит/с, объём свободных ресурсов на узлах от 2 до 12 Мбит/с. Один из графиков зависимости представлен на рисунке, а.

Зависимость времени вычислений от объёма свободных ресурсов на мультимедийных узлах. Были организованы эксперименты с установками: 50 узлов, на каждом узле от 2 до 4 потоков размером 1, 2, 3, 5 Мбит/с, объём свободных ресурсов на узлах от 2 до 10 Мбит/с (затем увеличено в 2 и 3 раза). Один из графиков зависимости представлен на рисунке, б.

pic_12.tif 

а

pic_13.tif 

б

pic_14.tif 

в

pic_15.tif 

г

pic_16.tif 

д

pic_17.tif 

е

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

Зависимость времени вычислений от количества мультимедийных узлов. Были организованы эксперименты с установками: количество узлов от 25 до 100, на каждом узле от 2 до 4 потоков размером 1, 2, 3, 5 Мбит/с, объём свободных ресурсов на каждом узле равен 20 Мбит/с. Один из графиков зависимости представлен на рисунке, в.

Зависимость времени вычислений от сложности (глубины) задачи поиска. Под глубиной поиска решения подразумевается количество перегруженных узлов на каждом шаге выполнения алгоритма. На первом шаге существует только один перегруженный узел – тот, который нуждается в распределении нагрузки. При поиске решения может получиться так, что этот узел разгрузится, но другие узлы станут перегружены. Тогда нужно произвести поиск решения для новых перегруженных узлов – это второй шаг, и т.д. Один из графиков зависимости представлен на рисунке, г.

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

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

В ходе проведённых экспериментов было установлено:

1. Во всех проведённых экспериментах алгоритм выдавал правильный ответ.

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

3. На время проведения эксперимента влияют объём потоков, глубина поиска решения, мощность компьютера.

4. Алгоритм поиска решения по условию «разгрузить узел на Х, используя операции переподключения» работает быстрее, чем остальные. Алгоритм поиска решения по условию «разгрузить узел на Х или максимум до Y, используя операции переподключения» при одних и тех же условиях выдавал положительный ответ чаще, т.к. варианты с распределением большего объема ресурсов также могли быть правильными.

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

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

Проведённые эксперименты показали, что предлагаемые алгоритмы переподключения работоспособны и могут использоваться для реальных сетей RTMCDN. Полученные результаты будут использованы в разрабатываемом комплексе по исследованию и управлению системами раздачи мультимедийного контента реального времени [1].

Автор благодарит научного руководителя В.В. Прохорова за ценные замечания и оказанную помощь.

Рецензенты:

Воротников В.И., д.ф.-м.н., профессор, ФГАОУ ВПО «Нижнетагильский технологический институт (филиал) УрФУ», г. Нижний Тагил;

Прохоров В.В., д.ф.-м.н., профессор, ООО «Научно-производственный центр «Видикор», г. Екатеринбург.

Работа поступила в редакцию 02.12.2014.


Библиографическая ссылка

Манакова И.П. АЛГОРИТМ УПРАВЛЕНИЯ РЕСУРСАМИ СЕТЕЙ RTMCDN // Фундаментальные исследования. – 2014. – № 11-12. – С. 2593-2598;
URL: http://fundamental-research.ru/ru/article/view?id=36028 (дата обращения: 16.12.2018).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252