Построение и анализ модели воспроизведения каналов вещательного телевидения в р2р сети

УДК 621.39

Построение и анализ модели воспроизведения каналов вещательного телевидения в Р2Р сети

Амину Адаму, Ю. В. Гайдамака, А. К. Самуйлов

Кафедра систем телекоммуникаций Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

В статье построена вероятностная модель просмотра каналов вещательного телевидения пользователями одноранговой сети (от англ. peer-to-peer, P2P — равный к равному). Поведение отдельного пользователя представлено в терминах замкнутой экспоненциальной сети массового обслуживания. Стационарное распределение вероятностей состояний модели функционирования P2PTV-сети представлено в мультипликативном виде по числу телеканалов и числу пользователей системы. С учётом популярности телеканалов получены формулы для анализа основного показателя качества функционирования P2PTV-сети на уровне пользователя (QoE, Quality of Experience) — вероятности всеобщей передачи (от англ. universal streaming), т.е. качественного приёма видеопотока всеми пользователями.

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

1. Введение

Пиринговая, или одноранговая сеть, — это любая распределённая архитектура сети, участники которой делают часть своих ресурсов (таких как вычислительный ресурс, объем памяти, пропускная способность и пр.) доступными другим пользователям этой сети без необходимости централизованной координации. Каждый пользователь такой сети, называемый «пиром» (от англ. peer — равный), выступает в роли как клиента, так и сервера, т.е. по мере потребления ресурсов сети пользователь способен сам предоставлять новые ресурсы, например, отдавать другим пользователям видеопоток одного из телеканалов. В этом заключается преимущество перед традиционной клиент-серверной моделью, где источником ресурсов является только сервер. Это позволяет Р2Р-сети сохранять работоспособность практически при любом количестве и любом сочетании доступных узлов. Р2Р-сети обычно организуют динамическую наложенную сеть прикладного уровня поверх имеющейся топологии базовой сети. Эти наложенные сети используются для индексирования и поиска пиров, в то время как данные передаются по базовой сети.

Р2Р-сети нашли применение, например, при распределённых вычислениях, но особенно широко они стали использоваться для обмена данными. По разным подсчётам общий трафик, генерируемый Р2Р-сетями, составляет до 60% всего трафика Интернет. Кроме того, в последние годы был внедрён ряд крупномасштабных Р2Р-сетей, предназначенных для передачи потокового видео — CoolStreaming, PPLive, PPStream, UUSee, Sopcast и другие [1-4]. В этих сетях сотни тысяч пользователей имеет возможность одновременно просматривать множество телеканалов. Известен ряд исследований, посвящённых анализу показателей качества функционирования одноранговых сетей, предназначенных для передачи потокового видео, в том числе вещательного телевидения (далее P2PTV-сеть). В этих исследованиях используются различные методы — измерения, имитационное и аналитическое моделирование. Обратим внимание на работу К. Росса [5], где построена аналитическая модель P2PTV^ra с применением аппарата экспоненциальных сетей массового обслуживания (СеМО) и введено понятие вероятности всеобщей передачи как вероятности качественного воспроизведения телеканала оборудованием пользователя.

Статья поступила в редакцию 30 июня 2010 г.

В большинстве функционирующих в настоящее время крупномасштабных динамических Р2РТУ-сетей применяется единый принцип распространения информации: пользователи, просматривающие один и тот же телеканал, объединяются в одну группу, а внутри этой группы пользователи обмениваются друг с другом пакетами видео данных, соответствующих содержанию телеканала. Авторы [5] называют такой механизм обмена данными системой изолированных телеканалов (isolated channel) или сокращённо — системой ISO Р2Р. Отметим, что использование этой системы может приводить к нестабильности просмотра телеканалов пользователями. Недавние исследования показали, что ISO-подобная система PPLive имеет несколько фундаментальных проблем производительности, таких как большие задержки при переключении телеканалов, прерывание воспроизведения, а также низкое качество воспроизведения малопопулярных телеканалов.

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

Видеосервер

Рис. 1. Пример переключения телеканала пользователем P2PTV-coth

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

На сегодняшний день в международных стандартах не нормированы требования к качеству предоставления услуги вещательного телевидения в Р2РТУ-сетях. Традиционно показателем качества обслуживания в мультисервисных сетях является, например, вероятность блокировки запроса пользователя на предоставление услуги [6-8]. Для Р2РТУ-сетей интересно рассмотреть такой показатель качества обслуживания, как вероятность того, что все пользователи, запросившие услугу, получают её с гарантированным качеством, определённым в соглашении об уровне качества предоставления услуги (англ. SLA — Service Level Agreement). В [5] эта вероятность качественного приёма видеопотока всеми пользователями принята за основной показатель качества трансляции видеоканала в Р2РТУ-сети и называется вероятностью всеобщей передачи. В данной статье по сравнению с [5] предложен новый подход к построению модели функционирования Р2РТУ-сети, основанный на представлении процесса просмотра телеканалов отдельным пользователем в виде процесса блуждания заявки по замкнутой экспоненциальной СеМО. Этот подход позволяет исследовать модель с конечным числом пользователей и затем получить искомый результат для переменного числа пользователей предельным переходом, устремляя число пользователей к бесконечности.

2. Модель поведения пользователей P2PTV-сети

Будем считать, что телеканал удовлетворяет требованиям соглашения об уровне качества предоставления услуги, если все без исключения пользователи, просматривающие этот телеканал, получают услугу с гарантированным качеством. Задача состоит в анализе показателей качества обслуживания пользователей в Р2РТУ-сети.

Построим модель поведения отдельного пользователя Р2РТУ-сети в виде однородной замкнутой экспоненциальной СеМО, в которой множество M (М =

|) узлов соответствует множеству телеканалов, а единственная заявка, блуждающая по узлам сети, описывает процесс переключения телеканалов пользователем. Пусть 0 = (в^— стохастическая матрица переходных вероятностей рассматриваемой СеМО и вектор-строка р = (рт)тем является решением система

мы уравнений р = р0. Предположив ^ рт = 1, можно считать, что в^ соответ-

ш= 1

ствует вероятности переключения пользователя с г-канала на j-канал, а величина Рт — популярности m-канала, i,j,m G M. Пусть все узлы СеМО представляют собой системы массового обслуживания типа IS (Infinite Server), причём среднее время обслуживания р,^1 в m-узле соответствует среднему времени просмотра m-канала пользователем, т G M.

Обозначим ут G {0,1} состояние пользователя, просматривающего т-канал, и У =(У m)mgM вектор состояния системы. Из теоремы Гордона Ньюэлла [8] для случая N =1 (один пользователь в системе) вытекает следующее утверждение.

Утверждение 1. Для модели СеМО, описывающей поведение отдельного пользователя Р2РТУ-сети, стационарное распределение вероятностей состояний имеет вид:

р

тбМ тбМ

Далее аналитическая модель строится в предположении, что N>0 (М = |) пользователей Р2РТУ-сети функционируют независимо друг от друга в соответствии с моделью поведения, определённой в утверждении 1. Обозначим хпт £ {0,1} состояние п-пользователя на т-канале, т.е. хпт = 1, если пользователь смотрит т-канал, и хпт = 0 в противном случае. Тогда состояние сети описывается матрицей

Х = , (2) а пространство состояний модели имеет вид

X = <! X : хпт G {0,1}, V хпт = 1, п G N }.

mG

Утверждение 2. Вероятность состояния X модели Р2РТУ-сети с N < то пользователями определяется формулой

Р

Формула (4) очевидным образом вытекает из предположения о независимости пользователей и утверждения 1.

Заметим, что в матрице X сумма хт = ^

^иш по ^^ столбцу соответствует

пе^

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

Множество состояний сети, когда т-канал просматривают ровно к пользователей, имеет вид

Хт

Тогда маргинальное распределение Рт(к) числа пользователей, просматривающих т-канал, определяется формулой

Рт

хехт

Утверждение 3. В случае N < то маргинальное распределение числа пользователей Р2РТУ-сети, просматривающих т-канал, имеет вид

Рт

В [5] случай модели с бесконечным числом пользователей представлен открытой экспоненциальной СеМО. Мы предлагаем исследовать этот случай путём предельного перехода от модели с конечным числом к модели с бесконечным числом пользователей. Положим рт(М) — популярность т-канала, когда в сети присутствуют N пользователей.

Утверждение 4. В случае N = то маргинальное распределение числа пользователей Р2РТУ-сети, просматривающих m-канал, имеет вид

Рт

гъ!

где 7ТО = lim Npm(N). N—>оо

Доказательство утверждения 4 следует из известного предельного перехода от биномиального распределения к распределению Пуассона.

Можно показать, что величина 7т соответствует среднему числу пользователей, просматривающих т-канал, а представив эту величину в виде 7т = \т/рт, можно считать, что интенсивность потока запросов пользователей на просмотр т-канала равна \т. Пронормировав величины 7т так, что рт = , мож-

гем

но считать, что величина рт, как и ранее, соответствует популярности т-канала пользователями, т е М.

3. Анализ вероятности качественного приёма

телеканала

Предположим, что в сети имеется видеосервер, для которого определена скорость отдачи видеопотока т-канала ьт [бит/с], а оборудование п-пользователя характеризуется скоростью отдачи видеопотока ип [бит/с]. Таким образом, видеопоток, доступный пользователям, просматривающим т-канал, формируется из потока, отдаваемого видеосервером, и потоков, отдаваемых всеми пользователями т-канала. Следовательно, когда система находится в состоянии X, величина ют(Х) видеопотока, доступного пользователям т-канала, определяется по формуле

^т

пе^

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

Если выполнено неравенство

ют

пел

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

{Х £ Х : + ^ ^ ^пш^п ^ %пт}

пел пел

и есть искомый показатель качества — вероятность качественного приёма т-канала пользователями:

Рит = Р

хех

Г 1, если ,Ат истинно где I(Ат) = < „ — функция индикатор.

0, в противоположном случае

Заметим, что в [5] показатель (12) называется вероятностью всеобщей передачи телеканала.

Для определённости предположим, что в сети имеется всего два типа пользователей: с высокой скоростью отдачи и с низкой скоростью и1 отдачи видеопотока. Обозначим соответствующие подмножества пользователей Nн и N1 (Лн = |Nн\, N1 = |N 1\). Тогда скорость отдачи видеопотока п-пользователем определяется формулой

ин, п £ Nн

(ин [и1,

и1, п £ N1

где Nн и N1 удовлетворяют соотношениям N = Nн и N1, Nн П N1 = 0.

Введём обозначения аналогично тому, как это было сделано выше: в каждом состоянии сети X величина х^ = ^ хпт обозначает число пользователей т-

пел н

канала с высокой скоростью отдачи и х1т =5^ хпт — число пользователей с

пел1

низкой скоростью отдачи, при этом верно равенство хт = х^ + х1т, т £ Ж. С учётом введённых обозначений событие Ат определяется формулой

Ат = {X £ X : ьт + инх^ + и1х1т > хтгт, х1^ > 0, х1т > 0},

причём справедливо следующее утверждение.

Утверждение 5. Вероятность качественного приёма т-канала пользователями в Р2РТУ-сети определяется формулой

лн л1

Рит = Р

где маргинальные распределения Рт(х^) и Рт(х1т) определены утверждением 4.

Рассмотрим теперь пример расчёта вероятности качественного приёма телеканалов пользователями Р2РТУ-сети для исходных данных из [5]. Пусть М = 20

— число телеканалов, транслируемых видеосервером, все телеканалы имеют одинаковые требования к ширине полосы пропускания, которые совпадают со скоростью отдачи видеопотока сервером, т.е. гт = ут = г, т £ М. Предполагается, что 50% пользователей имеют низкую скорость отдачи и1 =0, 2г и 50% пользователей — высокую скорость отдачи иъ' = 3г. Величины популярности телеканалов распределены по закону Ципфа:

1

Рт —

М

т £ М,

г=1

где ^ — параметр распределения. Это означает, что телеканалы перенумерованы по убыванию популярности. В примере рассмотрен случай г = 1.

На рис. 2 показаны графики вероятности качественного приёма для моделей со средним числом пользователей 7 = 1800 и 7 = 200, при этом среднее число пользователей, просматривающих т-канал, определяется по формуле 7Ш = 7рт, т £ М. Сравнение графиков подтверждает очевидный качественный вывод: во-первых, чем больше в P2PTV-сети пользователей, тем выше вероятность качественного приёма телеканалов; во-вторых, с уменьшением популярности телеканала эта вероятность снижается.

Рис. 2. Зависимость вероятности качественного приёма от популярности телеканала

4. Заключение

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

В дальнейшем предполагается исследовать, как такие характеристики телеканала, как скорость отдачи соответствующего видеопотока видеосервером, индивидуальные скорости пользователей, просматривающих телеканал, число пользователей, просматривающих телеканал, доля пользователей с высокой скоростью отдачи видеопотока и т.п., влияют на качество приёма видеопотока пользователями. Целью исследования является выявление характеристик Р2РТУ-сети, которые оказывают существенное влияние на функционирование сети.

Кроме того, интересно построить модель Р2РТУ-сети, в которой предусмотрена задержка воспроизведения телеканала оборудованием пользователя, и исследовать зависимость качества приёма видеопотока пользователями от значения этой задержки.

Поскольку отличительной чертой сетей следующего поколения является предоставление услуг с различными уровнями качества, ещё одной задачей дальнейших исследований может служить построение модели Р2РТУ-сети, каждый пользователь которой может выбрать уровень качества приёма видеопотока из нескольких уровней, предоставляемых сетью.

Литература

1. Сайт системы CoolStreaming Р2РТУ. — http://www.coolstreaming.us.

2. Сайт системы РРЪгге Р2РТУ. — http://www.pplive.com.

3. Сайт системы PPStream Р2РТУ. — http://www.pps.tv.

4. Cohen B. ^e Bi^on-ent Protocol Specification, vers. 11031. — Feb. 2008. — http: //bittorrent.org/beps/bep_0003.html.

5. Wu D., Liu Y, Ross K. W. Modeling and Analysis of MultiChannel Р2Р Live Video Systems // IEEE/ACM ^a^actions on Networking. — 2010.

6. Башарин Г. П. Лекции по математической теории телетрафика: Учеб. Пособие. — 3-е, испр. и доп. издание. — М.: РУДН, 2009. — 342 с.

7. Наумов В. А., Самуйлов К. Е., Яркина Н. В. Теория телетрафика мультисер-висных сетей. — М.: РУДН, 2007. — 191 с.

8. Плаксина О. Н. О двух системах массового обслуживания с «прозрачными» заявками и их применении к анализу услуг мультивещания. — 2010. — № 2, вып. 1. — С. 37-41.

UDC 621.39

Playback Model for Broadcast Television Channels in P2P

Networks

Aminu Adamu, Y. V. Gaidamaka, A. K. Samouilov

Telecommunication Systems Department Peoples' Friendship University of Russia 6, Miklukho-Maklaya str., Moscow, 117198, Russia

In this paper, we introduce a closed queueing network model with a single customer to analyze the behavior of a peer in P2P streaming systems. Then we use the passage to the limit when the number of peers approaches infinity in a closed queueing network model with limited population to analytically study the performance of multi-channel P2P streaming systems with the isolated channel (ISO) streaming design. The product-form solution for steady state probabilities and the expressions for the probability of universal streaming for a channel were derived. Some calculations for both models (when the number of peers is limited and when the number of peers approaches infinity) were conducted.

Key words and phrases: P2P network, broadcast television, queuing network, single user behavior model, popularity of TV-channel, probability of high quality video reception.