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

Математическая теория телетрафика и сети телекоммуникаций

УДК 519.21;51-76

DOI: 10.22363/2312-9735-2017-25-2-123-132

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

видеопотока Ю. В. Гайдамака*, Е. Г. Медведева*, С. И. Салпагаров^, Е. В. Бобрикова* * Кафедра прикладной информатики и теории вероятностей ^ Кафедра информационных технологий Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Последние годы концепция одноранговых Р2Р-сетей успешно используется в системах телевещания P2PTV, которые предоставляют пользователям возможность смотреть телевизионные каналы по сетям Р2Р. Для повышения качества предоставления услуги Р2Р-телевидения используются различные схемы организации структуры наложенной сети. В работе исследована так называемая «модель VUD» (View-Upload Decoupling), основанная на разделении (Decoupling) загружаемых пользователем потоков данных на два типа: поток для собственного просмотра, соответствующий телевизионному каналу, зрителем которого он является (View), и поток (один или несколько) другого телевизионного канала, исключительно для раздачи другим пользователям (Upload). Как правило, последние

— это потоки телевизионных каналов с низкой популярностью, принудительное распространение которых обеспечивает стабильность многоканальной системы. Для модели VUD построена вероятностная модель обмена данными между пользователями в однородной и неоднородной с точки зрения скоростей раздачи пользователей Р2Р-сети, позволяющая проводить анализ основного показателя качества обслуживания в потоковых сетях — вероятности состояния всеобщей передачи, как для отдельного телевизионного канала, так и для системы в целом. На основе построенной модели предложен метод расчёта этих характеристик, приведён пример сравнения двух схем организации структуры наложенной сети - традиционной модели ISO (Isolated Channel) и модели VUD.

Ключевые слова: peer-to-peer, одноранговая сеть, потоковые данные, вероятность всеобщей передачи, View-Upload Decoupling, P2PTV, замкнутые сети массового обслуживания

1. Введение

В настоящее время телекоммуникационные сети все чаще используют технологию P2P (peer-to-peer) [1,2] при обмене файлами, для организации распределённых

— облачных и туманных — вычислений, а также при передаче потокового видео. Известен целый список успешных коммерческих проектов по созданию систем телевещания P2PTV, включая PPLive [3], Tribler [4], PPS.tv [5], которые предоставляют десяткам тысяч пользователей несколько сотен телевизионных каналов для просмотра в режиме реального времени. При организации телевещания по технологии P2P к известным преимуществам одноранговой сети, таким как устойчивость, масштабируемость, добавляется невысокая стоимость функционирования, поскольку сеть P2PTV является наложенной, и дополнительное оборудование для получения услуги телевещания пользователю сети Интернет не требуется.

Статья поступила в редакцию 1 декабря 2016 г.

Исследование выполнено при финансовой поддержке РФФИ в рамках научных проектов №14-0700090, № 17-07-00845.

Для повышения качества предоставления услуги телевещания используются различные схемы организации структуры наложенной 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 будем проводить в тех же обозначениях.

Пусть М — множество пользователей сети, = N, J = {1, 2,... J} — множество каналов, заданных своим порядковым номером в системе вещания, упорядоченное по убыванию популярности канала, = J. Для каждого канала заданы его скорость воспроизведения rj, j G J, также заданы скорости раздачи данных ип для каждого n-пользователя, п G N.

В модели VUD каждый пользователь загружает несколько потоков данных: один из них соответствует выбранному для просмотра телевизионному каналу, остальные загружаются исключительно для раздачи другим пользователям и соответствуют каналам, зрителем которого пользователь не является. Модель строим в предположении о том, что каждый пользователь системы, являющийся зрителем канала j, назначается для раздачи одного потока канала к, где к = j, k,j G J. Таким образом, для каждого канала можно определить множество Mj пользователей-зрителей j-канала и множество Lj пользователей, раздающих j-канал, Mj С N, Lj С N, j G J.

Рассматриваем неоднородный случай, считая, что известны скорости раздачи каналов rj и в сети имеется два типа пользователей: пользователи с низкой скоростью раздачи и1 < rj, образующие множество М1, \Nl\ = N1, и пользователи с высокой скоростью раздачи uh > rj, образующие множество Мh, \Мh\ = Nh. Заметим, что N1 ПNh = 0, Nl UNh = N, N1 + Nh = N. Для схемы ISO Lj = Mj, при этом 0 < ICjI = IMjI ^ N, а для сети с двумя типами пользователей 0 ^ Llj ^ N1, 0 < Lh < Nh. Здесь Llj = Nl П Lj, Lh = Mh П Lj, а Llj = \ Llj \ и Lh = \ Lh \ — количество пользователей, соответственно, с низкой и с высокой скоростями раздачи в группе раздачи j-канала, j G J.

По построению, для схемы VUD выполнено соотношение Mj Л Ld = 0, j G J. Следовательно, должно выполняться условие

Lj CM\Mj, j Gj

а для сети с двумя типами пользователей — условия

С\ С Ml\Mj, j Gj; С1] С Nh\Mj, j G J.

Схема УиБ предполагает разделение потока канала на несколько подпотоков

J

(substream). Пусть Sj - число подпотоков 3-канала, з £ J, и обозначим I = ^ Sj.

3 = 1

Для каждого 8-подпотока з-канала назначается так называемая группа раздачи под-потока - множество пользователей не являющихся зрителями этого канала,

но отвечающих за раздачу данных назначенного им з-подпотока со скоростью г^,8),

С Lj, Lj = У £(»), 3 = 1,... ^, в = 1,... ,Sj. Разделение на подпотоки про-

3=1

изводится для того, чтобы пользователь с низкой скоростью раздачи и1 мог внести вклад в суммарный поток для раздачи ^-канала, поэтому

г(о,з) 8 = 1,...,Sj , ги,3) = Гз , з .

з=1

Обозначим С^ = М1 П L(j,s), Lh^s) = L(j,s). Заметим, что L1^^ =

С

И,*)

Lh

h

L

— количество пользователей, соответственно, с низкой и с высокой

скоростями раздачи в группе з-подпотока ^-канала, и Lj = \, з £ ^. Обозначим Mj = \Му \ — количество зрителей ^-канала, з £ ^. Для заданного Mj с учётом (1) и (2) имеем:

0 < Lj < N1

0 < Ь18) < N1 - М), 0 < Ь< Nн - М* з = 1,...,Sj, з £ ^,

LlU,s) U С%,8)= 0, s = 1,...,S3, j GJ.

Задача формирования групп пользователей для раздачи потоков каналов представляет собой комбинаторную задачу разложения шаров по корзинам, где шар соответствует пользователю, а корзина - группе раздачи подпотока. Распределить N1 + Nн пользователей по I подпотокам можно С^-^ 1_1  С^-^Н-1 способами. Ограничения (3)-(5) снижают размерность задачи: в случае ^-канала с Mj зрителями и

87 подпотоками необходимо распределить N1 + Nн — М^ пользователей, которые не являются зрителями ]-канала, по I — Sj подпотокам.

Каждый вариант распределения пользователей по группам раздачи подпотоков может быть описан с помощью вектора Ь = (Ь 1, Ь^) = ^1^1,..., —^, —I,..., —}

где Ц

(7, 1),..., -"и^)) , Ь 7 = \Щ, Г)^.^ ЬЬ,в3),

Ь1^ а) матрицы Ц соответствует числу пользователей с низкой скоростью в группе раздачи з-подпотока ^-канала, 8 = 1,..., Sj, ] £ J.

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

Р множество всех векторов Ь, для которых выполняются условия (4)—(5). Вероятность события

^ , ] £ J. Например, элемент

. в - £ Р : £

3=1

Е

> г 7 М7

3 £ 3,

является вероятностью Р1]7 всеобщей передачи ^-канала: Р1]7 = Р {А/}, ] £ 3. Заметим, что вероятность всеобщей передачи всей системы определяется как Ри =

ез А'}.Для сети с двумя типами пользователей Ф°рмула (6) принимает вид

в,

Ь £ V

Е [('•'

Л— ч 7,3)) ьЬ.з) + — >'<,,.)) ¿к.)

3=1

> Г 7 М7

3 £ 3.

Обозначим "Л7 множество всех векторов Ь £ Т>, для которых выполняется условие (7). Тогда с учётом введённых обозначений вероятность всеобщей передачи ^-канала определяется формулой

ртт. =

а вероятность Ри всеобщей передачи всей системы — формулой

ри =

п ^

/

Таким образом, группы раздачи каналов следует формировать в соответствии с вектором Ь = (Ь 1, Ь^) £ Т>, являющимся решением оптимизационной задачи, в которой множество определено формулой (7):

ри

V)

^ тах ^ е П

Для неоднородной сети с двумя типами пользователей при и1 < г7 из (7) имеем очевидное ограничение на число 87 подпотоков: 1 <87 < Г7/и1. Число 87 подпотоков для ^-канала может быть найдено как решение оптимизационной задачи

ри,

К^- <Гз/и1

где в качестве целевой функции выбрана вероятность всеобщей передачи ^-канала

ри, = ри, (в,).

Заметим, что в [1] рекомендуется выбирать значение скорости 8-подпотока канала по формуле Г(у^) = г^/Sj, в = 1,... ,Sj, ] £ J. Рекомендации по формированию групп раздачи каналов, числа подпотоков и их скоростей для потока каждого канала вытекают из решения оптимизационных задач (10) и (11).

Алгоритм 1 расчёта вероятности всеобщей передачи по формулам (8)-(9) изложен для сети с двумя типами пользователей, в которой нет деления потоков на подпотоки, то есть = 1 ] £ J.

Алгоритм 1. Расчёт вероятностно-временных характеристик

input N, J, Nl, ul,uh, Mj Vj = 1,J

output PUj, PU Vj = 1,J

for all j low peer d.g.

if N1 <= N - Mj then Plj e [N -else Plj e {Nl, N1 - 1,..., 1, 0} -Mj,N -Mj - 1,.. ., 1, 0}

for all j high peer d.g.

if Nh <= N - Mj then P1} e [N else Ph e {Nl,Nl - 1,...,1, 0} - Mj, N -Mj - 1,. .., 1, 0}

find all P= (P[,Pl2,...,Plj,Ph,Ph,-- ., Pj) such that

Pl, + Ph = 0 and ' Pij + p} <= N - Mj and sum,(Pj) = Nl and sum (p)) = Nh

T=count

PU, = 0

for all P

3 = 1

t = 0

do while j <= J

if Plj(ul - r) + Ph(uh - r) >= Mjr then

PUj = PUj + 1

t = t+1

end if

3=3 + 1

if t = J

PU = PU + 1

end if

end for

for all j channel find probability

PUi = PU, /T

end for

PU = PU/T

В этом случае вектор Ь = (Г/, , характеризующий численность групп раздачи, принимает вид (р1^ 1), . . . , Р1^ 1),Р>(1 1), . . . , 1)1 (в Алгоритме 1 ё^. от англ.

Distribution Group). Исходными данными являются общее число пользователей сети N, число пользователей с низкой и с высокой скоростями раздачи N1, Nh = N — N1 соответственно, число зрителей каждого канала Mj, j £ J, скорости раздачи и1 и uh.

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

3. Пример расчёта вероятности всеобщей передачи

Для иллюстрации работы метода выбрана сеть небольшой размерности, в которой сервер транслирует три телевизионных канала для 400 пользователей (табл. 1). Характеристики видеопередачи усреднены и соответствуют данным, актуальным в настоящее время для ряда торрент-клиентов и пользователей, где скорость потоковой передачи видеоданных г^ = г = 5 Мбит/с, что позволяет просматривать видео с разрешением до 1920 х 1080 пикселей.

Таблица 1

Исходные данные

Характеристика сети Значение

Число пользователей N = 400

Множество каналов J = {1, 2, 3}

Доля пользователей о низкой скоростью раздачи 0,1 < f < 0,9 c шагом 0,1

Потоковая скорость каналов rj = г = 5Мбит/с

Низкая скорость раздачи и1 = 0.2г = 1Мбит/с

Высокая скорость раздачи uh = зг = 15Мбит/с

На рис. 1 и 2 приведены графики вероятности всеобщей передачи для каждого канала при обеих схемах организации структуры наложенной сети — VUD и ISO — в зависимости от доли f пользователей c низкой скоростью раздачи.

г

5:е

Цвд

SPL2

В Ш

\

V 1 \

W

ч i \

- \

<4 ч. \

V чч

N..

J

---VUDPU1

-----YUDPU2

.........VUD PU3

-ISOPU1

---ISOPU2

--ISO РШ

3,2 -3,3 Ц4 Q5 0.6 Q7 3,S Q9

Доля пользователей с низкой скоростью раздачи

Рис. 1. Вероятность всеобщей передачи, z = 0, 5

Рис. 2. Вероятность всеобщей передачи, z = 1, 5

Число пользователей с низкой и с высокой скоростями раздачи определяется формулами N1 = \Nf], Nh = N — N1. Для схемы VUD расчёты выполнены по методу, предложенному в предыдущем разделе, для схемы ISO - по методу [6]. Как и в [1,2,6], предполагаем, что популярность канала имеет распределение Ципфа с параметром z:

Pj = —3 = !,...,J.

j X]

i=i

В этом случае при N ^ < число Mj зрителей j-канала имеет вид Mj =

lim N pj [8], а для конечной сети может быть определено по формуле Mj = \Npj ].

N ^-rx

Графики на рис. 1 и рис. 2 построены для двух значений параметра Ципфа: z = 0, 5 и z = 1, 5. Меньшее значение параметра определяет более равномерное распределение числа зрителей по каналам, то есть более плавное падение популярности каналов, чем для z =1, 5.

Для традиционной схемы ISO при обоих значениях параметра Ципфа с уменьшением популярности канала вероятность всеобщей передачи падает. Значение этой характеристики зависит от доли пользователей с низкой скоростью раздачи, и если более половины пользователей сети имеют высокую скорость раздачи (/ < 0, 5), то вероятность всеобщей передачи равна единице для всех каналов. В противном случае популярные каналы имеют более высокую вероятность всеобщей передачи при большем значении параметра z, поскольку при больших значениях параметра z популярные канал имеют больше (а непопулярные - меньше) зрителей, чем те же каналы при меньших значениях z. Например, для сети с 30 % пользователей с высокой скоростью раздачи (f = 0, 7) при z = 0, 5 вероятность всеобщей передачи наиболее популярного канала №1 PU1 = 0, 72, а при z = 1, 5 вероятность всеобщей передачи PUi = 0,8. В то же время для наименее популярного канала №3 PUs = 0, 63 при z = 0, 5 и PUs = 0,59 при z = 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. Заключение

На основе предложенного в статье метода расчёта вероятностных характеристик модели сети Р2РТУ при схеме УИБ разделения данных на поток для просмотра и поток для раздачи было разработано программное средство, которое формирует все возможные варианты разложения пользователей по группам раздачи каналов. Для рассмотренного примера сети Р2РТУ небольшой размерности число таких вариантов имеет порядок 108 (при г = 0, 5, / = 0, 5). Поэтому в дальнейшем планируется разработать метод, позволяющий решать задачи большой размерности, в том числе, предполагающие разбиение потоков телевизионных каналов на подпотоки. Также будет сформулирована оптимизационная задача распределения пользователей по группам раздачи с точки зрения максимизации характеристики всеобщей передачи (10) для системы Р2РТУ. При этом группы раздачи каналов формируются согласно вектору-решению задачи оптимизации, компоненты которого соответствуют числу пользователей с низкой и с высокой скоростями раздачи в группах раздачи подпотоков каналов.

Литература

1. Wu D., Liu Y., Ross K. Queuing Network Models for Multi-Channel P2P Live Streaming Systems // IEEE INFOCOM. — 2009. — Pp. 73-81.

2. Медведева Е. Г., Гайдамака Ю. В. К анализу параметров качества передачи мультиканального потокового трафика в одноранговой сети // Современные информационные технологии и ИТ-образование. — 2015. — Т. 2, № 11. — С. 192-198.

3. Сайт системы P2PTV PPLive [Электронный ресурс]. — http://www.pptv.com/.

4. Сайт системы P2PTV Tribler [Электронный ресурс]. — https://www.tribler. org/.

5. Сайт системы P2PTV PPS.tv [Электронный ресурс]. — https://www.pps.tv/.

6. Гайдамака Ю. В., Самуйлов А. К. Анализ стратегий заполнения буфера оборудования пользователя при предоставлении услуги потокового видео в одноранговой сети // T-Comm — Телекоммуникации и Транспорт. — 2013. — № 11. — С. 77-81.

7. Самуйлов А. К., Бобрикова Е. В. Простейшая жидкостная модель файлообмен-ной P2P-сети // T-Comm — Телекоммуникации и Транспорт. — 2012. — № 7. — С. 180-184.

8. Адаму А., Гайдамака Ю. В. Аппроксимация нормальным законом вероятностных характеристик модели сети P2P TV // Вестник РУДН. Серия: Математика. Информатика. Физика. — 2011. — № 3. — С. 63-68.

9. Liang C., Liu Y. Vivud: Virtual Server Cluster Based View-Upload Decoupling for Multi-Channel P2P Video Streaming Systems // Global Telecommunications Conference (GLOBECOM 2010) 2010 IEEE. — 2010. — Pp. 1-5.

UDC 519.21;51-76

DOI: 10.22363/2312-9735-2017-25-2-123-132

Analysis of Model for Multichannel Peer-to-Peer TV Network with View-Upload Decoupling Scheme

Yu. V. Gaidamaka*, E. G. Medvedeva*, S. I. Salpagarov", E. V. Bobrikova*

* Department of Applied Probability and Informatics ^ Department of Information Technologies Peoples' Friendship University of Russia (RUDN University) 6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

In recent years, video streaming systems such as P2PTV successfully use P2P-based networks to allow users watching numerous streaming TV channels. Various designs of an overlaid network were proposed to improve the quality of services of P2PTV. In this paper, we explore View-Upload Decoupling-scheme (VUD), which strictly decouples data to what peer uploads and what it personally views. It's based on the split of downloaded user data streams into two types: the stream of the chosen TV channel, and the stream (one or more) of the other TV channel, exclusively to deliver it to other users. Such peers form the distribution swarm which is assigned the streams of the channels with low popularity, so that would guarantee the stability of multichannel systems. The mathematical model of VUD scheme is proposed, which considers two classes of users - homogeneous type (all users have the same upload rate) and heterogeneous systems (there are two types of users — with low and high upload rate). We develop the method for calculation the probability of universal streaming - one of the key performance indicators in streaming TV - when all users receive the requested video data with guaranteed quality, defined in the service level agreement (SLA). We propose a method for calculating the probability of universal streaming for a single channel. Statistically significant results for a small network in comparison to VUD and ISO schemes are presented.

Key words and phrases: peer-to-peer, P2PTV, multichannel streaming, probability of universal streaming, distribution group, substream, view-upload decoupling, closed queuing network model

References

1. D. Wu, Y. Liu, K. Ross, Queuing Network Models for Multi-Channel P2P Live Streaming Systems, IEEE INFOCOM (2009) 73-81.

2. E. Medvedeva, Yu. Gaidamaka, On Analysis of Performance Characteristics of P2P Video Streaming Network, Modern Information Technology and IT-Education 2 (11) (2015) 192-198.

3. PPLive.

URL http://www.pptv.com/

4. Tribler.

URL https://www.tribler.org/

5. PPS.tv.

URL https://www.pps.tv/

6. Yu. Gaidamaka, A. Samuylov, Analysis of Playback Continuity for Video Streaming in Peer-to-Peer Networks with Data Transfer Delays, T-Comm (11) (2013) 77-81, in Russian.

7. K. Samuylov, E. Bobrikova, A Simple Fluid Model of P2P File Sharing Network, T-Comm (7) (2012) 180-184, in Russian.

8. A. Adamu, Yu. Gaidamaka, Approximation of a Universal Streaming Probability with the Normal Distribution, Bulletin of Peoples' Friendship University of Russia. Series: Mathematics. Information Sciences. Physics (3) (2011) 63-68, in Russian.

9. C. Liang, Y. Liu, Vivud: Virtual Server Cluster Based View-Upload Decoupling for Multi-Channel P2P Video Streaming Systems, Global Telecommunications Conference (GLOBECOM 2010) 2010 IEEE (2010) 1-5.

© Гайдамака Ю.В., Медведева Е. Г., Салпагаров С. И., Бобрикова Е.В., 2017