РАСПРЕДЕЛЕНИЕ ПОЛЬЗОВАТЕЛЕЙ ПО ВИДЕОСЕРВЕРАМ ОНЛАЙН ТРАНСЛЯЦИИ С УСЛОВИЕМ МИНИМАЛЬНОГО ПЕРЕМЕЩЕНИЯ ЗРИТЕЛЕЙ

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

преподаватель (стажёр), НТИ (ф) УрФУ, г. Нижний Тагил

E-mail:

Петров Кирилл Борисович

студент, НТИ (ф) УрФУ, г. Нижний Тагил

E-mail:

THE DISTRIBUTION OF USERS ON VIDEO SERVERS OF ONLINE TRANSLATION WITH THE MINIMUM DISPLACEMENT VIEWERS

Irina Manakova

lecturer (probationer), NTI (b) UFU, Nizhny Tagil

Kirill Petrov

student, NTI (b) UFU, Nizhny Tagil

АННОТАЦИЯ

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

ABSTRACT

Conducting Internet broadcasts in real-time video requires the organization of the system of video points which are connected to each other. It is necessary to organize the best connection to the points for users. The paper presents a mathematical formulation of the problem of distribution of users at a high load on the broadcasting system and its solution. Objective function is defined. System of equations is obtained as a result. Its solution can be implemented in software. Software on the distribution of users during the broadcast can be developed.

Ключевые слова: транспортная задача; линейное программирование; онлайн видео технологии; распределение пользователей; целевая функция; видео реального времени

Keywords: transportation problem; linear programming; online video technology; the distribution of users; the objective function; real-time video

Использование сети Интернет для проведения онлайн-семинаров, конференций, а также для показа событий различного рода в реальном времени, на сегодняшний день очень актуально. Чаще всего для этого используют некоторую систему связанных видеосерверов [4] для предоставления качественных услуг большому количеству пользователей, чтобы снизить нагрузку на одну конкретную машину. В данном случае под видеосерверами понимаются: во-первых, сервер-инициатор трансляции (главный сервер); во-вторых сервера-ретрансляторы, которые выполняют роль промежуточного звена между главным сервером и клиентами-зрителями, получая от предыдущего сервера n установленных видеопотоков и передавая их далее. Один ретранслятор может быть связан с другим и так далее, всё больше увеличивая количество зрителей (рис. 1):

Рис. 1. Пример организации онлайн видео трансляции

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

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

Система может сама регулировать распределение M_max пользователей по видеоточкам, отвечая за оптимальность выбранной схемы подключения, т. е. за число M_max и нагрузку на канал конкретной точки. Однако, возникает ситуация, когда к системе хочет подключиться M_max+1 пользователь, однако та минимальная нагрузка (m_min), которую он просит, не может быть прибавлена к нагрузке конкретной видеоточки из-за нехватки ресурсов.

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

Однако этот вариант нельзя назвать оптимальным при условии, если система имеет незанятую пропускную способность отличную от нуля, т. е. R_св>0, где R_св — общая незанятая пропускная способность.

При условии, если  можно попробовать перераспределить M пользователей по N видео-серверам, где M — число отобранных пользователей для перемещения, включающее M_max+1 пользователя, а N — число отобранных видеосерверов, которые должны принимать участие в перераспределении.

В данном случае речь идёт именно о выборке, а не обо всех видеосерверах и всех подключённых к системе пользователях, поскольку существуют единицы, которые необходимо исключить. Например, видеосервера у которых R=0, где R — пропускная способность конкретного видеосервера. Также необходимо исключить пользователей, занимаемых пропускную способность большую, чем R_св.

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

Формулировка задачи может быть представлена следующим образом: есть система из N={n₁, n₂, n₃,..., n_N} видеосерверов, у которых сосредоточены запасы одного и того же видеопотока. О каждом видеосервере известна следующая информация:

R_i — пропускная способность i-го ретранслятора,

R_{i ms} — занятая пропускная способность на i-м ретрансляторе,

M_i — количество пользователей, подключённых к i-му ретранслятору где ,

m_j — пропускная способность, необходимая для обслуживания j-го пользователя при подключении к системе видеоточек, где , M — общее количество пользователей, m_j, — одинаково при подключении к любому из серверов, , где R_св — общая незанятая пропускная способность системы.

К системе хочет подключиться один пользователь, просящий m_j+1 пропускной способности при условии, что m_j+1 есть минимально запрашиваемое число, причём  и  (т. е. больше самого большого ресурса, занимаемого одним из пользователей). Как распределить пользователей по видеосерверам с учётом подключения нового пользователя, чтобы число перемещений было минимальным, а само перераспределение оптимальным при условии, что каждый конкретный пользователь может быть подключён только к одному видеосерверу?

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

Количество m_j,i было выбрано как постоянное в связи с тем, что не должно происходить ухудшение или улучшение качества конечного видеоизображения, что происходит при понижении или повышении размера необходимой пропускной способности. Т. е. если пользователь был подключён к видеоточке № 1 и занял пропускную способность в 2 Мб, вторая точка может принять его ровно с такой же пропускной способностью. Если же это условие не может быть удовлетворено, такого пользователя необходимо оставить на прежней видеоточке и не учитывать его при переподключении.

Сформулированная выше задача частично напоминает транспортную [3], однако имеет ряд отличий:

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

2.  В транспортной задаче изначально не составлен опорный план. В случае данной задачи существует опорный план подключения пользователей к видеоточкам без учёта вновь подключаемого пользователя с m_j+1 запрашиваемой пропускной способностью.

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

Несмотря на указанные отличия, данную задачу можно отнести к классу задач линейного программирования [2]. Это в свою очередь говорит о том, что её можно перенести на программный код и реализовать как некоторое программное обеспечение по оптимальному подключению пользователей.

Поскольку существует некоторый опорный план подключения, воспользуемся им: составим систему уравнений и целевую функцию для решения задачи [1].

Схематически задачу распределения можно представить в виде матрицы, содержащей нули (пользователь не подключён к данной видеоточке) и единицы (пользователь подключён к данной видеоточке). Строки матрицы — M пользователей. Столбцы — N видео-точек. Пересечение x_i,j означает принадлежность пользователя к видеоточке (1 - «истина/принадлежит», 0 - «ложь/не принадлежит»).

Саму задачу можно записать в виде таблицы (табл. 1). Необходимо вписать в каждую ячейку таблицы 0 либо 1, так чтобы занять необходимое общее количество ресурсов. Т. е. необходимо найти все x_i,j=1 при этом, удовлетворяя условию, что количество перераспределений (т. е. перемещений с первоначального видеоузла на другой) должно быть минимальным. Поскольку при перемещении с одного сервера на другой число занимаемых ресурсов остаётся прежним, нахождение минимума перестановок и будет целевой функцией.

Таблица 1.

Матрица подключений

В общем случае все найденные x_i,j должны удовлетворять условию (формула 1):

Также известна матрица существующих значений на момент начала выполнения алгоритма подключений. Её вид и размер соответствуют искомой матрице, то есть она состоит из 0 и 1, во всех строках (кроме последней) один элемент равен 1, все остальные — 0. Последняя строка заполнена нулями. Количество перенесённых пользователей будет тем меньше, чем меньше различий между заданной и искомой матрицами. Обозначим элементы заданной матрицы y_i,j. Необходимо найти (формула 2):

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

Если рассматривать табл. 1, как сочетание строк или сочетание столбцов, тогда появляется ещё несколько ограничений. Одно из них — по строкам (формула 3). Другое — по столбцам (формула 4).

В формуле 3 сложение происходит по строкам. Т. е. Будет M+1 уравнений, в каждом из которых существует лишь одно x_i,j=1.

В формуле 4 сложение происходит по столбцам. Т. е. будет N уравнений, в каждом из которых могут встречаться как значения x_i,j=1, так и x_i,j=0. Однако, вписанная суммарная пропускная способность не должна превышать возможной пропускной способности на выбранной видео-точке.

Тогда система уравнений примет следующий вид (формула 5):

Следовало бы потребовать, чтобы все x_i,j могли принимать только 2 значения: 0 и 1. Однако это условие оказывается излишним.

Рассмотрим пример решения задачи о распределении пользователей по видеоточкам. Пусть при проведении онлайн-вещания футбольного матча задействовано 2 сервера. Об эфире известна следующая информация, необходимая для подключения нового пользователя (табл. 2):

Таблица 2.

Пример матрицы подключений

Изначально матрица равна матрице существующих подключений.

Проверим, достаточно ли ресурсов для подключения пользователя u₅: пользователь запрашивает 4 единицы, 4 единицы доступно с учётом того, что пользователи u_1-4 занимали пропускную способность 2, 2, 1, 1 соответственно (10-6=4). Значит, пользователя можно попробовать подключить к системе.

Составим систему уравнений (формула 6):

Предположим, что нового пользователя необходимо подключить к точке n_1. Тогда нарушается неравенство (формула 7):

Чтобы уравновесить это выражение необходимо переместить 2 единицы на точку n₂. Перенесём пользователя u₁ и проверим уравнения (формула 8):

Все равенства выполняются. Новая таблица подключений (табл. 3):

Таблица 3

Матрица подключений с учётом запроса нового пользователя

Проверим целевую функцию (формула 9):

Количество перемещений минимально. Согласно табл. 3 вся доступная пропускная способность будет занята. Переместить необходимо u₁ и подключить u₅ к n₁.

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

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

2.  После этапа тестирования необходимо внести изменения в решении задачи, если это необходимо.

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

Решение этих вопросов станет предметом наших дальнейших исследований.

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

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

1.Альсова О.К., Казанская О.В., Юн С.Г.. Методы оптимизации и теория принятия решения: учебн. пособие [электронный ресурс] — Режим доступа. - URL: http://edu.nstu.ru/courses/mo_tpr/files/0.html (дата последнего обращения: 19.05.2012)

2.Банди Б. Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. – 176 с.: ил.

3.Самаров К.Л. Транспортная задача: учебн. пособие. [электронный ресурс] — Режим доступа. - URL: http://www.resolventa.ru/metod/student/transproblem.htm (дата последнего обращения: 19.05.2012)

4.Vidicor Video System. [электронный ресурс] — Режим доступа. - URL: http://vidicor.ru/ (дата последнего обращения: 19.05.2012)