БОРЬБА  С  ПЕРЕГРУЗКАМИ  В  СИСТЕМАХ  ОНЛАЙН-ВЕЩАНИЯ

Манакова  Ирина  Павловна

аспирант  Уральского  Федерального  Университета,  РФ,  г.  Екатеринбург

E -mail:  iman@vidicor.ru

FIGHTING  WITH  THE  OVERLOAD  IN  THE  INTERTEN  VIDEO  SYSTEMS

Irina  Manakova

postgraduate  student  Ural  Federal  University,  Russia,  Ekaterinburg

АННОТАЦИЯ

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

ABSTRACT

When  implementing  the  Internet  video  systems,  one  may  face  the  real-life  problem  of  the  limited  bandwidth  of  Internet  network  segments,  when  they  may  become  overloaded  which  results  in  crash  of  quality  video  communication.  The  scientific  paper  is  dedicated  to  the  research  of  the  methods  of  coping  with  overloads.  Also  the  scientific  paper  is  dedicated  to  the  algorithm  of  coping  with  overloads  and  its  implementation.The  conducted  research  has  demonstrated  that  the  proposed  solutions  may  be  used  in  real  Internet  video  systems  that  they  actually  allow  to  cope  with  overloads,  and  also  allow  to  increase  the  number  of  clients  linked  to  the  network.

Ключевые  слова:   мультимедийный  трафик;  видеосистема;  система  онлайн-вещания;  CDN;  RTMCDN.

Keywords:   multimedia  content;  video  system;  online  broadcast;  CDN;  RTMCDN.

1.  Проблемы  внедрения  систем  онлайн-вещания

При  внедрении  систем  онлайн-вещания  можно  столкнуться  с  возникающей  в  реальных  условиях  проблемой  ограниченности  пропускной  способности  звеньев  интернет-сети,  когда  могут  появляться  перегрузки  сети,  ведущие  к  краху  качественной  видеосвязи.  Проблема  ограниченности  пропускной  способности  каналов  связи  связана  с  их  ненадежностью  и  неоднородностью,  а  также  с  низкой  пропускной  способностью  звеньев  сети  [3].  Проблема  может  решаться  созданием  инфраструктуры,  включающей  узлы  репликации  (размножения)  мультимедийных  потоков  на  базе  Интернет  сети.  Для  этого  требуется  решение  определенных  проблем.  Из-за  использования  публичных  каналов  связи  сети  разных  провайдеров  накладываются  друг  на  друга,  при  этом  появляется  разнородный  трафик.  Из-за  этого,  а  также  из-за  повышения  спроса  на  мультимедийные  услуги,  узлы  систем  онлайн-вещания  могут  оказываться  перегруженными,  что  влияет  на  качество  предоставляемых  услуг  [3].

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

2.  Модель  системы  онлайн-вещания

Рассмотрим  предлагаемую  структурную  модель  системы  онлайн-вещания  (рис.  1).  Её  элементы  частично  описаны  в  [6].

Рисунок  2.  Модель  структуры  системы  онлайн-вещания

На  основании  полученной  структурной  модели,  предлагается  математическая  модель  описания  нагрузки  на  систему  в  конкретный  момент  времени.  Это  набор  параметров  ,  где  N  (node)  —  множество  мультимедийных  узлов,  U  (user)  —  множество  подключенных  к  системе  плееров  зрителей,  S  (stream)  —  множество  мультимедийных  потоков,  L  (load  status)  —  статус  (модель)  нагрузки  системы,  W  (waiting)  —  очередь  плееров  ожидающих  подключения.

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

Здесь  статическими  параметрами  являются:  (объем  ресурсов  процессора),  (объем  ресурсов  оперативной  памяти),    (допустимое  количество  подключенных  плееров),    (объем  пропускной  способности  исходящего  канала),    (объем  пропускной  способности  входящего  канала),  S  (множество  потоков,  которые  передает  узел),  BL  (граница  перехода  из  состояния  «нагружен»  в  состояние  «перегружен»). 

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

Нагрузка  на  узел  описывается  как  сумма  функций  его  внешней  (f_ex)  и  внутренней  нагрузки  (f_inc):

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

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

Каждый  плеер  зрителя  u  характеризуется  набором  параметров:  ,  где  b  —  мультимедийный  поток,  Y  —  узел,  к  которому  подключен  плеер,  B  —  качество  потока,  K  —  множество  возможных  подключений,  которое  характеризует  то,  к  каким  узлам  может  быть  подключен  плеер.

Каждый  поток  s  характеризуется  набором  параметров  ,  где  n_parent  —  родительский  узел,  который  является  началом  передачи  потока,  n_stream  —  множество  узлов  репликации  потока,  q  —  качество  потока,  b_s  —  величина  потока  (битрейт).

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

Используем  разработанную  модель  для  постановки  и  решения  задачи  о  перераспределении  нагрузки  системы  онлайн-вещания  между  ее  узлами.  Задача  более  подробно  приведена  в  [4].

3.                     Постановка  задачи  о  перераспределении  нагрузки  системы  онлайн-вещания  между  ее  узлами

Имеется  некоторая  мультимедийная  сеть,  состоящая  из  N  узлов.  Вместе  узлы  генерируют  S  разнородных  мультимедийных  потоков.  К  системе  подключены  U  плееров  зрителей,  которые  получают  некоторые  потоки  от  сети.  Причем  каждый  плеер  может  быть  подключен  только  к  одному  узлу.  О  каждом  узле  (n_i)  известна  модель  текущей  нагрузки:  ,  где    и  —  параметры  исходящего  канала.  О  каждом  плеере  (u_j)  известна  модель  текущего  подключения:.  Известно,  что  некоторый  узел  n_o  перегружен  по  загрузке  исходящего  канала.  Также  известна  величина  перегрузки.  Необходимо  проверить  существует  ли  решение  задачи  освобождения  на  узле  n_o  нужного  объема  ресурсов  для  вывода  узла  из  состояния  перегрузки.  При  этом  остальные  узлы  системы  не  должны  быть  перегружены.  Если  такое  решение  существует,  принять  его  к  исполнению. 

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

4.  Предлагаемые  методики  решения  задачи 

Рассмотрим  две  методики  решения  задачи  о  перераспределении  нагрузки  системы  онлайн-вещания  между  ее  узлами.  Эти  методики  были  предложены  автором  ранее  в  [1;  4].

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

Представим  текущую  схему  подключения  клиентов  в  виде  бинарной  матрицы  Y  =  {Y_i,j|  ,  },  размерность  матрицы  —  N  x  U.  Тогда,  для  того,  чтобы  схема  подключения  была  оптимальной,  должны  выполняться  следующие  условия:

В  поставленной  задаче  известно,  что  текущая  схема  подключения  плееров  Y  не  оптимальна  по  первому  условию  системы  (2)  для  узла  n_o.  Следовательно,  система  онлайн-вещания  не  обеспечивает  максимальное  качество  обслуживания  всех  клиентов.  Поэтому  необходимо  найти  новую  схему  подключения  Y¢,  которая  удовлетворяла  бы  всем  условиям.

Обозначим  бинарную  матрицу  возможных  подключений  как  KB.  Каждый  элемент  KB_i,j  матрицы  KB  представим  как:  .  Матрица  KB  определяет  множество  вариантов  подключения. 

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

Здесь  целевая  функция  —  минимум  изменений  в  матрице  подключений.

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

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

Здесь  целевая  функция  —  минимум  изменений  в  матрице  качества  для  каждого  плеера  зрителя  ().

Предложенные  методики  легли  в  основу  реализованных  алгоритмов  “Source  Change”  (смена  источника)  и  “Quality  Change”  (смена  качества  потока).

5.  Общий  алгоритм  решения  задачи

Решая  задачу  об  уменьшении  нагрузки,  обратимся  к  начальным  условиям.  Поскольку  известен  перегруженный  узел  n_o  поиск  решения  Y¢  осуществляется  исходя  из  модели  текущей  нагрузки  данного  узла. 

Величина  перегрузки  ov  узла  n_o  определяется  как:

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

Утверждение  1.   Вычислительная  сложность  первого  этапа  алгоритма  не  превышает  O(N).

Доказательство .  Из  условия  задачи  известно,  что  существует  массив  узлов  длины  N.  Для  проверки  условий,  сформированных  на  первом  этапе,  необходимо  получить  данные  о  каждом  узле.  Раз  количество  узлов  равно  N,  то  в  худшем  случае  необходимо  осуществить  N  шагов  цикла.  Следовательно,  вычислительная  сложность  первого  этапа  алгоритма  не  превышает  O(N).  Утверждение  доказано.

Второй  этап   предлагаемого  алгоритма  заключается  в  формировании  упорядоченного  набора  {y₁,  y₂,  …,  y_i}  возможных  вариантов  освобождения  на  узле  n₀  нужного  объема  пропускной  способности  канала.  Здесь  i  –  количество  вариантов.  Варианты  упорядочиваются  согласно  количеству  плееров,  участвующих  в  распределении  ресурсов.

Каждый  вариант  y_a  определяется  на  основании  набора  s^H  =  {s₁,  s₂,  …,  s_H}  разнородных  потоков,  передаваемых  узлом  n₀.  Каждый  вариант  должен  подчиняться  условиям:

где:    —  количество  плееров  для  потока  s_H,  необходимое  для  формирования  варианта  y_a,

—  величина  потока  s_H,

—  количество  плееров,  подключенных  к  потоку  s_H,

  —  общее  количество  плееров,  подключенных  к  системе.

Если  y^a  окажется  пустым,  то  перераспределение  нагрузки  по  данному  алгоритму  невозможно. 

Утверждение  2.   Вычислительная  сложность  второго  этапа  алгоритма  не  превышает  O().

Доказательство .  По  условию  задачи  известно,  что  каждый  вариант  y_a  освобождения  на  узле  n₀  нужной  величины  пропускной  способности  канала  определяется  как    .  Следовательно,  .  Предположим,  что  множество  вариантов  освобождения  на  узле  n₀  нужной  величины  пропускной  способности  канала  формируется  исходя  из  количества  плееров,  подключенных  к  потоку  s₁.  Тогда

,

,

,

…,

.

Следовательно,  необходимо  осуществить    шагов  цикла.  На  каждом  таком  шаге  необходимо  рекурсивно  разложить  элементы  ,  аналогично  способу,  приведенному  для  потока  s₁.  Следовательно,  количество  циклических  шагов  равно  и  равно  .  Следовательно,  вычислительная  сложность  второго  этапа  алгоритма  не  превышает  O().  Утверждение  доказано.

Третий  этап  работы  алгоритма  заключается  в  поиске  вариантов  перемещения  нагрузки  с  узла  n₀  на  узлы  из  массива  n_l.  Варианты  из  множества  y^a  проверяются  в  порядке  убывания  количества  перемещаемых  плееров.  Таким  образом,  соблюдается  условие  минимума  перемещений.

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

Утверждение  3.   Вычислительная  сложность  третьего  этапа  алгоритма  не  превышает  O().

Доказательство .  Известно,  что  на  втором  этапе  алгоритма  формируется  множество  вариантов  освобождения  на  узле  n₀  требуемой  величины  пропускной  способности  канала.  Количество  элементов  данного  множества  равно  .  Следовательно,  чтобы  последовательно  проверить  все  варианты,  необходимо  выполнить    шагов  цикла.  Предположим,  что  проверяется  вариант  .  По  условию  задачи  его  можно  разбить  на  составные  части  ,  где  H  –  количество  потоков,  используемых  для  формирования  данного  варианта.  Таким  образом,  чтобы  последовательно  проверить  все  составные  части,  необходимо  осуществить  H  шагов  цикла.  На  каждом  таком  шаге  необходимо  найти  узлы,  которые  можно  использовать  для  перенесения  ресурсов.  Для  этого  необходимо  получить  данные  о  каждом  узле.  Количество  узлов  равно  N,  так  что  в  худшем  случае  необходимо  осуществить  N  шагов  вложенного  цикла.  В  худшем  случае  необходимо  осуществить    шагов.  Таким  образом,  вычислительная  сложность  третьего  этапа  алгоритма  не  превышает  O().  Утверждение  доказано.

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

При  проверке  вариантов  с  перегрузкой  узел  n₀  исключается  из  множества  анализируемых  узлов.  Новый  перегруженный  узел  становится  узлом  n₀.  Шаги  1—4  повторяются  для  этого  узла.

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

Если  при  завершении  работы  алгоритма  множество  возможных  решений  окажется  пустым,  это  означает,  что  гипотеза  о  том,  что  существует  хотя  бы  одно  решение  Y¢  более  удачное,  чем  Y,  неверна.

Утверждение  4.   Вычислительная  сложность  четвертого  этапа  алгоритма  не  превышает  O()).

Доказательство .  На  третьем  этапе  алгоритма  формируется  множество  вариантов  переключения  с  перегрузкой.  Количество  элементов  данного  множества  равно  .  Следовательно,  для  проверки  всех  вариантов  полным  перебором  необходимо  осуществить    шагов  цикла.  На  каждом  таком  шаге  последовательно  выполняются  шаги  1—3.  Следовательно,  необходимо  осуществить    шагов.  Циклы  —  вложенные,  так  что  необходимо  осуществить  )  шагов.  Таким  образом,  вычислительная  сложность  четвертого  этапа  алгоритма  не  превышает  O()).  Утверждение  доказано.

Предложенные  описания  легли  в  основу  реализованных  программных  алгоритмов  “Source  Change”  и  “Quality  Change”. 

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

В  качестве  апробации  реализованных  алгоритмов  “Source  Change”  и  “Quality  Change”  был  проведен  их  сравнительный  анализ  с  алгоритмом  «Least  Connection»  (наименьшее  количество  подключений),  который  часто  используется  в  традиционной  практике  для  распределения  заявок  клиентов  по  узлам  сети.  Результаты  сравнения  приведены  в  табл.  1.  Сравнение  производилось  по  количеству  одновременно  подключенных  плееров  зрителей.

Таблица  1. 

Сравнение  алгоритмов  “Source  Change”,  “Quality  Change”,  “Least  Connection”

В  среднем  алгоритм  “Source  Change”  позволяет  увеличить  количество  подключенных  клиентов  на  2  %,  алгоритм  “Quality  Change”  на  17  %  по  сравнению  с  традиционным  “Least  Connection”  при  условии,  что  система  вещает  хотя  бы  из  двух  точек  и  количество  потоков  разного  качества  для  каждой  такой  точки  больше  одного.  Таким  образом,  предлагаемые  методики  и  алгоритмы  могут  использоваться  для  реальных  систем  онлайн-вещания  как  для  повышения  их  эффективности,  так  и  для  увеличения  количества  одновременно  подключенных  плееров  зрителей. 

Список  литературы:

1.Манакова  И.П.  Алгоритм  управления  ресурсами  сетей  RTMCDN  //  Фундаментальные  исследования.  —  2014.  —  №  11  (часть  12).  —  С.  2593—2598. 

2.Манакова  И.П.  Анализ  видео-трафика  систем  раздачи  мультимедийного  контента  реального  времени  //  Апробация,  —  №  10(25),  —  2014  г.  —  С.  18—24.

3.Манакова  И.П.,  Прохоров  В.В.  Построение  Интернет-видеосистем  в  условиях  существенно  ограниченной  пропускной  способности  каналов  связи  //  Аграрный  вестник  Урала  —  №  3(133),  —  2015.  —  С.  34—38.

4.Манакова  И.П.  Об  управлении  загрузкой  исходящих  каналов  сети  RTMCDN  во  время  перегрузок.  Технические  науки  —  от  теории  к  практике:  сб.  ст.  по  материалам  XXXVI  междунар.  научн.-практ.  конф.  №  7  (32)  //  Новосибирск:  Изд.  «СибАК»,  2014.  —  С.  30—42.

5.Поршнев  С.В.,  Овечкина  Е.В.,  Каплан  В.Е.  Теория  и  алгоритмы  аппроксимации  эмпирических  зависимостей  и  распределений.  Екатеринбург:  УрО  РАН,  2006.  —  166  с.

6.Прохоров  В.В.,  Манакова  И.П.  Модель  системы  раздачи  мультимедийных  потоков  //  Фундаментальные  исследования.  —  2014.  —  №  8  (часть  2).  —  С.  311—316.