Анализ модели многоканальной одноранговой сети вещательного телевидения для схемы с разделением видеопотока

Полный текст

1. Введение В настоящее время телекоммуникационные сети все чаще используют технологию P2P (peer-to-peer) [1, 2] при обмене файлами, для организации распределённых облачных и туманных - вычислений, а также при передаче потокового видео. Известен целый список успешных коммерческих проектов по созданию систем телевещания P2PTV, включая PPLive [3], Tribler [4], PPS.tv [5], которые предоставляют десяткам тысяч пользователей несколько сотен телевизионных каналов для просмотра в режиме реального времени. При организации телевещания по технологии P2P к известным преимуществам одноранговой сети, таким как устойчивость, масштабируемость, добавляется невысокая стоимость функционирования, поскольку сеть P2PTV является наложенной, и дополнительное оборудование для получения услуги телевещания пользователю сети Интернет не требуется. Для повышения качества предоставления услуги телевещания используются различные схемы организации структуры наложенной P2P-сети. При традиционной схеме Isolated-Channel (ISO) зрители одного и того же телевизионного канала обмениваются фрагментами просматриваемого видео друг с другом [6]. Для каналов с большим числом зрителей эта схема обеспечивает высокое качество предоставления услуги телевещания, однако, в случае передачи потоков непопулярных каналов с небольшой аудиторией, а также для систем с возможностью воспроизведения видеопотока канала на различных потоковых скоростях, схема ISO (Isolated Channel) не обеспечивает устойчивое предоставление услуги. Одной из альтернатив является схема View-Upload Decoupling (VUD), основанная на разделении (Decoupling) загружаемых пользователем потоков данных на два типа: поток для собственного просмотра, соответствующий выбранному телевизионному каналу (View), и поток (один или несколько) исключительно для раздачи другим пользователям (Upload). Использование схемы VUD в сетях большой размерности позволяет улучшить характеристики вещания для каналов с небольшой аудиторией [1], в частности, повысить один из основных показателей качества обслуживания - вероятность всеобщей передачи (Universal Streaming), то есть вероятность того, что все пользователи, запросившие услугу, получают её с гарантированным качеством, определённым в соглашении об уровне качества предоставления услуги (SLA, Service Level Agreement). В работе для схемы VUD [6, 7] формализована вероятностная модель обмена данными между пользователями в однородной (скорости раздачи видеоданных всех пользователей одинаковы) и неоднородной (скорости раздачи видеоданных пользователей различаются) P2P-сети и предложен метод расчёта вероятности всеобщей передачи как для отдельного канала, так и для системы в целом. Для иллюстрации приведён пример расчёта этой характеристики для сети небольшой размерности, проведено её сравнение с вероятностью всеобщей передачи в сети с традиционной схемой ISO. Для схемы VUD даны рекомендации по формированию групп раздачи каналов, сформулированы задачи дальнейших исследований по поиску аппроксимации показателей качества вещания при схеме VUD для систем P2PTV большой размерности. 2. Математическая модель схемы VUD Рассмотрим систему P2PTV, в которой пользователи получают видеопотоки телевизионных каналов от одного сервера-источника. В [4] для схемы ISO построена математическая модель процесса функционирования системы P2PTV в виде открытой экспоненциальной сети массового обслуживания, получено совместное распределение числа пользователей на каналах системы и предложен метод оценки вероятности всеобщей передачи. Построение модели для схемы VUD будем проводить в тех же обозначениях. Пусть - множество пользователей сети, = , = 1, 2, . . . - множество каналов, заданных своим порядковым номером в системе вещания, упорядоченное по убыванию популярности канала, = . Для каждого канала заданы его скорость воспроизведения , , также заданы скорости раздачи данных для каждого -пользователя, . В модели VUD каждый пользователь загружает несколько потоков данных: один из них соответствует выбранному для просмотра телевизионному каналу, остальные загружаются исключительно для раздачи другим пользователям и соответствуют каналам, зрителем которого пользователь не является. Модель строим в предположении о том, что каждый пользователь системы, являющийся зрителем канала , назначается для раздачи одного потока канала , где ̸= , , ∈ . Таким образом, для каждого канала можно определить множество пользователей-зрителей -канала и множество пользователей, раздающих -канал, ⊆ , ⊆ , ∈ . Рассматриваем неоднородный случай, считая, что известны скорости раздачи каналов и в сети имеется два типа пользователей: пользователи с низкой скоростью раздачи < , образующие множество , = , и пользователи с высокой скоростью раздачи > , образующие множество , = . Заметим, что - количество пользователей, соответственно, с низкой и с высокой скоростями раздачи в группе раздачи ��-канала, ∈ . По построению, для схемы VUD выполнено соотношение = ∅, . Следовательно, должно выполняться условие ⊆ ∖ , ∈ (1) а для сети с двумя типами пользователей - условия (2) Схема VUD предполагает разделение потока канала на несколько подпотоков (substream). Пусть - число подпотоков ��-канала, ∈ , и обозначим Для каждого ��-подпотока -канала назначается так называемая группа раздачи подпотока - множество пользователей (,), не являющихся зрителями этого канала, но отвечающих за раздачу данных назначенного им -подпотока со скоростью (,), Разделение на подпотоки производится для того, чтобы пользователь с низкой скоростью раздачи мог внести вклад в суммарный поток для раздачи ��-канала, поэтому Обозначим Заметим, что - количество пользователей, соответственно, с низкой и с высокой скоростями раздачи в группе ��-подпотока -канала, и = , . Обозначим = - количество зрителей -канала, . Для заданного с учётом (1) и (2) имеем: (3) (4) (5) Задача формирования групп пользователей для раздачи потоков каналов представляет собой комбинаторную задачу разложения шаров по корзинам, где шар соответствует пользователю, а корзина - группе раздачи подпотока. Распределить + пользователей по подпотокам можно -1 способами. Ограничения (3)-(5) снижают размерность задачи: в случае ��-канала с зрителями и подпотоками необходимо распределить + - пользователей, которые не являются зрителями -канала, по - подпотокам. Каждый вариант распределения пользователей по группам раздачи подпотоков может быть описан с помощью вектора где . Например, элемент матрицы L соответствует числу пользователей с низкой скоростью в группе раздачи ��-подпотока -канала, = 1, . . . , , ∈ . Согласно [1] канал находится в состоянии всеобщей передачи, если все зрители канала получают данные со скоростью не ниже его потоковой скорости. Обозначим множество всех векторов →-L , для которых выполняются условия (4)-(5). Вероятность события является вероятностью всеобщей передачи ��-канала: = , . Заметим, что вероятность всеобщей передачи всей системы определяется как = ⋂︀∈ . Для сети с двумя типами пользователей формула (6) принимает вид (7) Обозначим множество всех векторов →-L , для которых выполняется условие (7). Тогда с учётом введённых обозначений вероятность всеобщей передачи ��-канала определяется формулой (8) а вероятность всеобщей передачи всей системы - формулой (9) Таким образом, группы раздачи каналов следует формировать в соответствии с вектором →-L = L, L ∈ , являющимся решением оптимизационной задачи, в которой множество определено формулой (7): (10) Для неоднородной сети с двумя типами пользователей при < из (7) имеем очевидное ограничение на число подпотоков: 1 < < . Число подпотоков для ��-канала может быть найдено как решение оптимизационной задачи (11) где в качестве целевой функции выбрана вероятность всеобщей передачи ��-канала = ( ). Заметим, что в [1] рекомендуется выбирать значение скорости ��-подпотока -канала по формуле (,) = / , = 1, . . . , , . Рекомендации по формированию групп раздачи каналов, числа подпотоков и их скоростей для потока каждого канала вытекают из решения оптимизационных задач (10) и (11). Алгоритм 1 расчёта вероятности всеобщей передачи по формулам (8)-(9) изложен для сети с двумя типами пользователей, в которой нет деления потоков на подпотоки, то есть = 1 ∈ . В этом случае вектор →-L = (︀L, L)︀, характеризующий численность групп раздачи, принимает вид (︁)︁ (в Алгоритме 1 d.g. от англ. Distribution Group). Исходными данными являются общее число пользователей сети , число пользователей с низкой и с высокой скоростями раздачи , = соответственно, число зрителей каждого канала , , скорости раздачи и . В следующем разделе приведён пример расчёта вероятности всеобщей передачи канала и системы в целом с использованием Алгоритма 1. 3. Пример расчёта вероятности всеобщей передачи Для иллюстрации работы метода выбрана сеть небольшой размерности, в которой сервер транслирует три телевизионных канала для 400 пользователей (табл. 1). Характеристики видеопередачи усреднены и соответствуют данным, актуальным в настоящее время для ряда торрент-клиентов и пользователей, где скорость потоковой передачи видеоданных = = 5 Мбит/с, что позволяет просматривать видео с разрешением до 1920 × 1080 пикселей. Исходные данные Таблица 1 Характеристика сети Значение Число пользователей = 400 Множество каналов = {1, 2, 3} Доля пользователей c низкой скоростью раздачи 0, 1 < < 0, 9 c шагом 0,1 Потоковая скорость каналов = = 5Мбит/с Низкая скорость раздачи = 0.2 = 1Мбит/с Высокая скорость раздачи = 3 = 15Мбит/с На рис. 1 и 2 приведены графики вероятности всеобщей передачи для каждого канала при обеих схемах организации структуры наложенной сети - VUD и ISO - в зависимости от доли пользователей c низкой скоростью раздачи. Рис. 1. Вероятность всеобщей передачи, = 0, 5 Рис. 2. Вероятность всеобщей передачи, = 1, 5 Число пользователей с низкой и с высокой скоростями раздачи определяется формулами = , = . Для схемы VUD расчёты выполнены по методу, предложенному в предыдущем разделе, для схемы ISO - по методу [6]. Как и в [1, 2, 6], предполагаем, что популярность канала имеет распределение Ципфа с параметром : (12) В этом случае при → ∞ число зрителей ��-канала имеет вид = lim [8], а для конечной сети может быть определено по формуле = ⌈ ⌉. Графики на рис. 1 и рис. 2 построены для двух значений параметра Ципфа: = 0, 5 и = 1, 5. Меньшее значение параметра определяет более равномерное распределение числа зрителей по каналам, то есть более плавное падение популярности каналов, чем для = 1, 5. Для традиционной схемы ISO при обоих значениях параметра Ципфа с уменьшением популярности канала вероятность всеобщей передачи падает. Значение этой характеристики зависит от доли пользователей с низкой скоростью раздачи, и если более половины пользователей сети имеют высокую скорость раздачи ( < 0, 5), то вероятность всеобщей передачи равна единице для всех каналов. В противном случае популярные каналы имеют более высокую вероятность всеобщей передачи при большем значении параметра , поскольку при больших значениях параметра популярные канал имеют больше (а непопулярные - меньше) зрителей, чем те же каналы при меньших значениях . Например, для сети с 30 % пользователей с высокой скоростью раздачи ( = 0, 7) при = 0, 5 вероятность всеобщей передачи наиболее популярного канала №1 1 = 0, 72, а при = 1, 5 вероятность всеобщей передачи 1 = 0, 8. В то же время для наименее популярного канала №3 3 = 0, 63 при = 0, 5 и 3 = 0, 59 при = 1, 5. Заметим, что детально зависимость вероятности всеобщей передачи от доли пользователей с низкой скоростью раздачи была исследована в [8]. Для схемы VUD, которая была предложена с целью улучшить показатели качества непопулярных каналов, с уменьшением популярности канала вероятность всеобщей передачи растёт. На рис. 1 и 2 для обоих значений параметра Ципфа кривые этой характеристики для непопулярных каналов лежат выше, чем для популярных каналов. При этом для сети, в которой доля пользователей с высокой скоростью раздачи не превышает 20 %, схема VUD для наименее популярного канала № 3 даёт более высокую вероятность всеобщей передачи, чем схема ISO. Значение вероятности всеобщей передачи канала № 3 всегда выше, чем для каналов № 1 и № 2, поскольку численность группы раздачи этого канала выше, чем у каждого из остальных каналов. Заметим, что значения вероятности всеобщей передачи при заданных исходных параметрах сети показывают низкое качество предоставления услуги телевещания даже для канала № 3. Это объясняется невысокой размерностью сети, выбранной для иллюстрации работы метода. Для сетей с числом пользователей порядка 2000 вероятность всеобщей передачи самого непопулярного канала может достигать значения 0, 8 [1, 9]. Развитием идеи разделения загружаемых пользователем данных на поток для собственного просмотра и поток для раздачи другим пользователям стала предложенная в [9] модификация схемы VUD, так называемая схема ViVUD (Virtual Server Cluster VUD), при которой в раздаче потока непопулярных каналов используются дополнительные серверы-источники данных, что позволяет осуществлять телевещание в соответствии с соглашениями SLA об уровне качества предоставления услуги. 4. Заключение На основе предложенного в статье метода расчёта вероятностных характеристик модели сети P2PTV при схеме VUD разделения данных на поток для просмотра и поток для раздачи было разработано программное средство, которое формирует все возможные варианты разложения пользователей по группам раздачи каналов. Для рассмотренного примера сети P2PTV небольшой размерности число таких вариантов имеет порядок 108 (при = 0, 5, = 0, 5). Поэтому в дальнейшем планируется разработать метод, позволяющий решать задачи большой размерности, в том числе, предполагающие разбиение потоков телевизионных каналов на подпотоки. Также будет сформулирована оптимизационная задача распределения пользователей по группам раздачи с точки зрения максимизации характеристики всеобщей передачи (10) для системы P2PTV. При этом группы раздачи каналов формируются согласно вектору-решению задачи оптимизации, компоненты которого соответствуют числу пользователей с низкой и с высокой скоростями раздачи в группах раздачи подпотоков каналов.

Об авторах

Юлия Васильевна Гайдамака

Российский университет дружбы народов

Email: ygaidamaka@sci.pfu.edu.ru
Кафедра прикладной информатики и теории вероятностей ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Екатерина Георгиевна Медведева

Российский университет дружбы народов

Email: egmedvedeva@gmail.com
Кафедра прикладной информатики и теории вероятностей ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Солтан Исмаилович Салпагаров

Российский университет дружбы народов

Email: sismalg@gmail.com
Кафедра информационных технологий ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Екатерина Васильевна Бобрикова

Российский университет дружбы народов

Email: ebobrikova@gmail.com
Кафедра прикладной информатики и теории вероятностей ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

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