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

На правах рукописи

АДАМУ Амину

ПОСТРОЕНИЕ ВЕРОЯТНОСТНЫХ МОДЕЛЕЙ И АНАЛИЗ ПОКАЗАТЕЛЕЙ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ПОТОКОВЫХ ОДНОРАНГОВЫХ СЕТЕЙ

05.13.17 - «Теоретические основы информатики»

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

2 ОЕЗ Ш

005008963

Москва-2012

005008963

Работа выполнена на кафедре систем телекоммуникаций Российского университета дружбы народов.

Научный руководитель:

кандидат физико-математических наук, доцент

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

Официальные оппоненты:

доктор технических наук, профессор

Степанов Сергей Николаевич

кандидат физико-математических наук .Дедовских Татьяна Владимировна

Ведущая организация:

Институт проблем информатики Российской академии наук (ИПИ РАН)

Защита диссертации состоится « 24 » февраля 2012 г. в 16 час. 30 мин. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе, д. 3, ауд. 110.

С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов по адресу: 117198, г.Москва, ул. Миклухо-Маклая, д. 6. (Отзывы на автореферат просьба направлять по указанному адресу.)

Автореферат разослан « 23 » января 2012 г.

Ученый секретарь диссертационного совета

М.Б. Фомин

Общая характеристика работы

Актуальность проблемы. Современная одноранговая сеть (от англ. Peer-to-Peer, P2P - «равный к равному») объединяет пользователей, которые без централизованного управления делают свои ресурсы (вычислительная мощность, объем памяти и др.) доступными друг другу, и не только загружают, но и раздают загруженные данные другим пользователям, что снижает нагрузку на серверы-источники информации. Различают файлообменные и потоковые одноранговые сети. Первоначально одноранговые сети использовались для обмена файлами, такими как видеоролики, фильмы, электронные книги и др. Такие сети называют файлообменными Р2Р-сетями. Только недавно технология P2P начала использоваться для передачи потокового трафика, например, при предоставлении услуги цифрового вещательного телевидения. Несколько потоковых Р2Р-систем были успешно созданы для предоставления услуги потокового видео по требованию и услуги видео в режиме реального времени через Интернет и сейчас обслуживают одновременно сотни тысяч пользователей, просматривающих телевизионные каналы со скоростью от 300 кбит/с до 1 Мбит/с. Примерами таких систем являются PPLive, PPStream, UUSee, SopCast, CoolStreaming, TVants и многие другие. В ближайшие годы эти системы будут использоваться при трансляции большого числа телевизионных каналов со всего мира для огромного количества пользователей и могут составить серьезную конкуренцию известным подходам к предоставлению услуг IPTV, таким как традиционное IP-мультивещание. Дальнейший рост объемов трафика потокового вещания через Интернет с использованием Р2Р архитектуры ожидается также за счет видео, произведенного самими пользователями и транслируемого с их веб-камер и беспроводных устройств. Привлекательность технологии Р2Р обусловлена в том числе низкой стоимостью развертывания Р2Р-сети, поскольку сеть является наложенной и для ее организации не требуется дополнительного сетевого оборудования.

Для анализа показателей эффективности функционирования файлообменных сетей применяются так называемые жидкостные модели, а для анализа показателей эффективности потоковых сетей - дискретные модели. Существенный вклад в развитие данной области внесли в основном зарубежные ученые: L. Heinrock, K.W. Ross, Е. Setton, В. Girod, В. Hajek, R. Srikant, D. Qiu, F. Clévenot, Ph. Nain, J. Virtamo и др. При анализе моделей Р2Р-сетей используют методы исследований, разработанные известными

российскими учеными: Г. П. Башариным, В. М. Вишневским, Б. С. Гольдштейном, А. Е. Кучерявым, А. В. Печинкиным, А. П. Пшеничниковым, К. Е. Самуйловым, С. Н. Степановым, А. Д. Харкевичем, И. И. Цитовичем, М. А. Шнепс-Шнеппе, С. Я. Шоргиным и др.

Для каждого пользователя сети максимально возможные скорости входящего трафика (так называемая скорость загрузки) и исходящего трафика (так называемая скорость раздачи) обусловлены особенностями технологии подключения к сети Интернет, причем часто скорость загрузки значительно превышает скорость раздачи, например, при подключении через АОБЬ-модем. Как правило, скорости воспроизведения телеканалов, транслирующихся в потоковых одноранговых сетях вещательного телевидения (Р2РТУ-сетях), ниже скоростей загрузки пользователей, поэтому проблемы с качеством предоставления услуги телевещания в Р2РТУ-сети возникают в ситуации, когда скорости раздачи видеопотока телеканала сервером и пользователями -соседями по Р2РТУ-сети ниже скорости воспроизведения канала. Данная диссертационная работа посвящена анализу качества предоставления услуг именно потоковых одноранговых сетей. Кроме того, исследованию моделей файлообменных одноранговых сетей посвящено значительное количество публикаций, а модели потоковых одноранговых сетей являются менее исследованными.

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

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

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

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

Научная новизна диссертации состоит в следующем.

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

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

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

2. В разработке модели воспроизведения видеопотока в Р2Р-сети, отличия которой от известных моделей состоят в следующем.

— Модель с учетом вероятностей появления пользователя в Р2Р-сети и его ухода из сети ранее не исследовалась.

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

Практическая ценность. Модели, методы и алгоритмы, разработанные в диссертационной работе, предназначены для расчета показателей эффективности потоковых одноранговых сетей - вероятности состояния всеобщей передачи транслируемых в сети каналов, вероятности просмотра видео без перерывов воспроизведения и задержки начала воспроизведения видеопотока. Эти показатели могут быть применены проектными организациями и операторами сетей при планировании сетевых ресурсов, требуемых для обеспечения надлежащего уровня качества обслуживания пользователей. Результаты диссертации использованы в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов, обучающихся по направлению «Прикладная математика и информатика», при подготовке магистерских диссертаций, а также в рамках исследований по фанту РФФИ

№10-07-00487-а «Задача управления доступом в широкополосной сети и анализ марковской модели с мультипликативным распределением вероятностей состояний» и НИР 020612-1-173 «Разработка математических моделей и методов анализа информационно-телекоммуникационных сетей».

Апробация работы. Результаты, полученные в ходе выполнения работы, были представлены на IV отраслевой научной конференции-форуме «Технологии информационного общества» 5-7 апреля 2010 г. (Москва, МТУСИ); XLVI Всероссийской научной конференции факультета физико-математических наук РУДН, 19-23 апреля 2010 г. (Москва, РУДН); 2nd International Congress on Ultra Modem Telecommunications and Control Systems (IEEE ICUMT 2010), Oct. 18-20, 2010 (Moscow, Russia); V отраслевой научной конференции-форуме «Технологии информационного общества», 9-10 февраля 2011 г. (Москва, МТУСИ); XLVII Всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем», 18-22 апреля 2011 г. (Москва., РУДН)*, 11th International Conference on Next Generation Wired/Wireless Networking, NEW2AN, Aug. 23-25, 2011 (St. Petersburg, Russia).

Публикации. По теме диссертации опубликовано 6 работ, из которых [1-4] -в ведущих рецензируемых научных журналах и содержат выносимые на защиту результаты, а [5,6] - в рецензируемых трудах международных конференций.

В работах, выполненных в соавторстве, соискателю принадлежит: в [1] -метод анализа модели воспроизведения каналов телевидения; в [2] - метод анализа состояния буфера; в [3] - утверждения об аппроксимации нормальным законом вероятности состояния всеобщей передачи; в [4] - метод анализа и расчета вероятности просмотра видео без перерывов воспроизведения. Все результаты, выносимые на защиту, получены автором лично.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии из 107 наименований. Диссертация изложена на 114 страницах текста, содержит 35 рисунков, 5 таблиц.

Содержание работы

Во введении обоснована актуальность темы диссертации, сформулированы цели и задачи исследований, представлено содержание основных результатов

диссертации, дана характеристика результатов по главам, изложена их научная новизна и практическая ценность.

Глава 1 посвящена особенностями построения моделей одноранговых сетей.

В разделе 1.1 исследованы принципы построения и классификации одноранговых сетей. Для каждого класса Р2Р-сети кратко описан процесс его функционирования, кроме того, четко определены показатели эффективности для каждого класса. Основным показателем эффективности функционирования файлообменных сетей является время загрузки файла (англ. Latency), а в потоковых сетях основными показателями эффективности функционирования являются задержка начала воспроизведения (англ. Startup Delay), вероятность просмотра видео без перерывов воспроизведения (англ. Playback Continuity) и вероятность состояния всеобщей передачи (англ. Universal Streaming).

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

В разделе 1.3 также исследованы модели для анализа файлообменной Р2Р-сети. В отличие от модели раздела 1.2 при построении моделей раздела 1.3 учитывается расстояние между пользователями: предполагается, что пользователи в сети загружают требуемые данные от соседних пользователей со скоростью, которая уменьшается с увеличением расстояния. Исследованы три режима функционирования файлообменной Р2Р-сети, а именно, жидкостной, жесткий и стационарный режимы.

Глава 2 посвящена построению и анализу модели одноранговой сети вещательного телевидения, далее - Р2РТУ-сети.

В разделе 2.1 исследованы принципы функционирования одноранговой сети вещательного телевидения.

В разделе 2.2 исследован метод построения одноранговой сети с потоковым трафиком в виде экспоненциальной однородной сети массового обслуживания и построены модели Р2РТУ-сети с конечным и бесконечным числом пользователей, основанные на модели поведения пользователя. Предполагается, что в рассматриваемой сети транслируется \.1(\ = М

ТВ-каналов, и в сети находятся = # пользователей, каждый из которых просматривает один из каналов сети. Для каждого канала определена рт -

м -1 популярность т-канала, £р,„=1, а также - среднее время просмотра

т=1

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

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

В разделе 2.3 рассмотрены частные случаи исследованных в разделе 2.2 моделей для анализа сети с двумя классами пользователей - пользователи с высокой скоростью раздачи и пользователи с низкой скоростью раздачи данных. Предполагается, что часть пользователей в сети имеет одинаковую высокую скорость раздачи, равную ик, а другая часть имеет одинаковую низкую скорость раздачи, равную и', т.е. и' <ик. Соответствующие

подмножества пользователей обозначены ЛИ и Л1 =|^'А|> Л7' =|- >

Л' = тогда и„ е {мЛ,м'|, пе .А .

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

= {(4Л) :0 < 4, < ,0 < х'т < М1,*т + хУ + х'У > хтЯт), т е Л ,

где х^ и х'т - число пользователей с высокой и с низкой скоростью раздачи на т-канале, а хт = х^ + х!т - общее число пользователей на т-канале.

Вероятность пт = Р(■-/„,) события •-/„, представляет собой вероятность состояния всеобщей передачи для т-канала. Справедливы следующие утверждения.

Утверждение 1. Вероятность всеобщей передачи »¡-канала Р2РТУ-сети с конечным числом пользователей с высокой и с низкой скоростью имеет вид

ы'

Ът=РУт)= Е Z 1{.'/„)рт(£)рт(4,}.'ПеЛ, (1)

4=о4,=о \ I \ I

где маргинальные распределения рт(xsmj числа пользователей класса se{h,l]

на m-канале имеют вид

\Хт)

I(-'/m) - функция-индикатор.

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

Кт = РШ= I I IШРтШРтШ^еЛ, (2)

4=0^=0

где маргинальные распределения рт (xsm j числа пользователей класса se {/г,/} на /и-канале имеют вид

, (у,;)4

Pm(4l) = e^'m meJ{' se{h,l},

хт.

где = lim Nspm(Ns), meJ{,se{h,l}.

При численном анализе вероятности состояния всеобщей передачи телевизионных каналов с различными популярностями рассмотрен фрагмент Р2РТУ-сети, в которой транслируются М =100 телевизионных каналов. В сети присутствуют // = 2000 пользователей, каждый из которых просматривает один из каналов. Предполагается, что популярность каналов распределена по

( " 1 т'

закону Ципфа с параметром z=l, т.е. pm = m:Y— , те Л, таким образом,

V tlm-J

каналы упорядочены в порядке убывания популярности. Все каналы в сети имеют одинаковые требования к скорости передачи данных, т.е.

/?,„ = /{ = 500кбит/с, те Л . Предположим, что Ы' = 0,5Ы пользователей в сети имеют низкую скорость раздачи, а остальные - высокую скорость раздачи. Пользователи с высокой скоростью раздают видеопоток со скоростью иь = 1500кбит/с, пользователи с низкой скоростью - с скоростью и1 = 100 кбит/с.

Исследована зависимость вероятности состояния всеобщей передачи для каналов с различной популярностью от числа пользователей с низкой и с высокой скоростями раздачи. На рисунках 1 и 2 изображены графики зависимости веротности пт от числа пользователей Ы1' и Ы1 для 1-го и 100-го канала соответственно, т.е. для канала с самой высокой популярностью и канала с самой низкой популярностью.

Рис.1. Вероятность состояния всеобщей передачи для 1-го канала

Рис.2. Вероятность состояния всеобщей передачи для 100-го канала

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

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

В разделе 2.4 получена аппроксимация для упрощения расчета вероятности состояния всеобщей передачи канала Р2РТУ-сети для случая сети с бесконечным числом пользователей, сформулированная ниже.

Утверждение 3. Вероятность %т всеобщей передачи т-канала в Р2РТУ-сети с бесконечным числом пользователей с высокой и с низкой скоростями раздачи

аппроксимируется нормальным законом А1! 0,~+еЦ: | т.е. лт =Ф

V

К + г

т 7

где Ф

•Лл {К-гт)у'т +8

8т = — Т„, и

стандартное нормальное распределение и

в. Я., -и'

и - К

(3)

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

»

° ^

V &

о

СО X

•я £

(- Д 0.91

о ^

о У

X &

Н и 0.

К С

0.85-

«С

1 12 23 34 45 56 67 78 89 100

Номер канала, да

Рис. 3. Вероятность состояния всеобщей передачи для каналов Р2РТУ-сети

На рисунке 3 каналы пронумерованы в порядке убывания популярности, т.е. 1-й канал является наиболее популярным, а 100-й канал имеет самую низкую популярность. Можно заметить, что вероятность пт состояния всеобщей передачи падает с уменьшением популярности канала. Сравнение значений показывает, что относительная погрешность приближения (3) для каналов с большой популярностью (каналы 1-7) равна нулю. Самая большая относительная погрешность приближения наблюдается для наименее

_9

популярного канала (канал 100), она составляет порядка 10 . Следовательно, аппроксимацию (3) можно использовать для оценки значения вероятности %т

состояния всеобщей передачи Р2РТУ-сети, причем с ростом популярности канала точность оценки повышается.

Глава 3 посвящена разработке модели для анализа вероятности просмотра видео без перерывов воспроизведения в Р2РТУ-сети.

В разделе 3.1 детально исследован процесс обмена данными между пользователями Р2РТУ-сети на основе механизма буферизации, который применяется для обеспечения непрерывного воспроизведения потокового видео. Видеопоток разбивается на порции данных, например, длиной около одной секунды, а в оконечном оборудовании пользователя предусмотрен буфер для хранения М порций видеоданных. Процесс воспроизведения видеопотока разбит на такты, длина каждого такта соответствует времени воспроизведения одной порции данных. При подключении нового пользователя к видеопотоку сначала заполняется буфер в оборудовании этого пользователя в соответствии с применяемой в сети стратегией выбора места буфера для загрузки (далее -стратегией загрузки), а затем порции видеоданных из буфера начинают поступать в видеоплеер. Наиболее распространенными стратегиями загрузки являются стратегия Rarest First (RF), при которой пользователь на каждом такте пытается загрузить наиболее «свежую», реже всего встречающуюся в сети порцию данных, и стратегия Greedy (Gr), при которой выбирается самая «старая», т.е. наиболее близкая к воспроизведению порция данных.

В разделе 3.2 построена модель процесса заполнения буфера оборудования пользователя в виде цепи Маркова (ЦМ). Предполагается, что в сети с одним сервером (источник видеопотока) присутствуют N пользователей, просматривающих один и тот же видеопоток. Состояние каждого пользователя (и-пользователя) представлено парой z(n) = (а(л),х(я)), где а(п) - индикатор присутствия пользователя в сети, т.е. a(ri) = 1, если пользователь находится в сети, и а(п) = 0 в противном случае, и х(л)= (х0(п),х,(п),-■-,хм(п)) - состояние буфера ^-пользователя (рисунок 4).

«-пользователь

Скачивание видео

хМ

Хм(п)

Направление видео

порции от сервера воспроизведения

Рис. 4. Состояние буфера «-пользователя

При этом хт(п) - состояние т-места буфера и-пользователя, т.е. хт(и) = 1,

если т-место буфера занято порцией данных, и хт(п) = 0 в противном случае,

т = 0,М. Места с первого (т=1) до последнего (т=М) предназначены для загрузки порций данных от других пользователей, а 0-место (т=0) - для загрузки порций данных от сервера. Таким образом, наиболее «старая» порция данных, которая будет отправлена на воспроизведение на ближайшем такте, находится на М-месте, а порция данных, находящаяся на ш-месте, отправится на воспроизведение через М — т тактов. Если на каждом такте М-место буфера п-пользователя, присутствующего в сети, заполнено, то «-пользователь будет просматривать видео без пауз в воспроизведении.

Матрица Х = (х(л))п_— описывает состояние буферов всех пользователей, и вектор-индикатор а = (а(и))л_— определяет состояние всех пользователей в

сети, следовательно, состояние модели можно представить в виде пары Ъ = (г(п)) = (а,Х) = (а(п),х(п))л_—, причем п-я строка матрицы X соответствует

состоянию буфера присутствующего в сети и-пользователя и сНтХ = Г\[(М +1). Таким образом, пространство состояний модели определяется формулой Х={0,1}мх{0,1}*'м+,) и |зг| = 2м<м+2'.

Обозначим М°(х(п)) и А/'(х(и)) множества номеров пустых и заполненных данными мест в буфере «-пользователя, т.е. М° (х(л)) = {т: хт (п) = 0, т = 1,м|,

М'(х(п)) = {т: хт(п) = 1, т = Ш}, причем М°(х(и))им1(х(и))={1,2,...,М}.

В момент ¿,+0 начала такта/, 1>0, сервер равновероятно выбирает любого из присутствующих (а1 (п) = 1) в сети пользователей и начинает загружать ему порцию данных на 0-место его буфера. Если выбран (-пользователь, то л:0(г)=1 в момент ?/+1 -0. Каждый из присутствующих

(а'(и) = 1, в сети пользователей, который не выбран сервером для

загрузки, выполняет следующие действия. Если в буфере есть пустые места, т.е. М°(х(и)) Ф 0, то л-пользователь выбирает случайным образом из

присутствующих в сети пользователей /г-пользователя, /г^п, а!(к) = 1, и пытается загрузить от него одну из недостающих порций данных. Пусть М'(х(/г)) - множество заполненных данными мест в буфере Л-пользователя.

Тогда л/°(х(л))ГШ'(х(й)) - множество номеров мест в буфере «-пользователя, на которые возможна загрузка порций данных от h-пользователя, n^h. Если Ma(x(n))[\Ml{x{h))*Z>, то «-пользователь выбирает в соответствии со стратегией загрузки 5 е {RF,Gr} место «г5 (х(«),х(/г)) в своем буфере, на которое он будет загружать порцию данных от h -пользователя, следующим образом:

Iminjm: me Л/°(х(/г))Г)Л/1(х(Л))}, при стратегииRF,

тах[т: те М°(х(«))ПЛ/'(х(/г))}, при стратегии Gr.

Загрузки для «-пользователя не будет на рассматриваемом такте, если Af°(x(n))(W(x(A)) = 0, или в буфере «-пользователя нет пустых мест

(Л/°(х(«)) = 0). В конце такта / в момент f;+1 для всех пользователей

происходит сдвиг буфера: порция данных, находившаяся в буфере пользователя на М-месте, отправляется на воспроизведение; все остальные порции данных в буфере сдвигаются на одну позицию вправо к концу буфера; 0-место в буфере пользователя освобождается для принятия порции данных от сервера на следующем такте.

Обозначим а (л) вероятность появления «-пользователя в сети и р(п) вероятность ухода «-пользователя из сети. Для простоты предположим, что для всех пользователей вероятности появления в сети одинаковы и вероятности ухода из сети одинаковы, т.е. а(п) = а, Р («) = Р, n = l,N.

Обозначим 1} = (а',Х') состояние сети в момент tl - 0. Нетрудно убедиться, что последовательность |z'J=|z', />о| образует цепь Маркова над пространством состояний % = {0,l}Nx{0,l}N(M+1), разложимую, с одним классом X существенных состояний, У. С. У. . Введем обозначения: 7г' (Z) - абсолютная вероятность ЦМ {z'}/>q на шаге /, т.е. %'(z) = p{z' =z} и n/,/+1(Z,Y) -

переходная вероятность ЦМ на шаге I. Заметим, что переходные вероятности n""(z,y) зависят от номера места в буфере т5 (х(п),х(й)) и от вероятностей а

появления и (5 ухода пользователя из сети. Таким образом, переходные вероятности зависят от стратегии загрузки 5 , а абсолютные вероятности к' (Z) удовлетворяют системе уравнений 7t'+1(Y) = ^K'(Z)n''+l (Z,Y), Ye X,/>0.

Основной характеристикой рассматриваемой модели является вероятность V(n)

того, что п-пользователь в конце такта на М-месте буфера имеет порцию данных для воспроизведения видеопотока. Для нахождения этой вероятности введена функция /г™(Z), соответствующая числу пользователей, у которых на ш-месте есть порция данных для загрузки «-пользователю согласно стратегии загрузки 5 , когда сеть находится в состоянии Z:

К(Z) = __ X 5m5(x(„),x(M),m - Ze ЗГ, где , = h=\,N:h#n,a'(h)=\

Определена вероятность <2,' (/и) того, что на такте I у одного или нескольких находящихся в сети пользователей имеется порция данных для загрузки «-пользователю на m-место в его буфере в соответствии со стратегией загрузки. Обозначим N(a')= ^a'(j) число присутствующих в сети пользователей, когда

;=1.N

сеть находится в состоянии Z'=(а',Х'). Если число пользователей N(a')>2, тогда

Й(»)=-1«,(2)--^-.в;(0) = 0,т = Ш. (4)

ж N(a )-1

Обозначим р'0(п,т) и р\{п,т) вероятность того, что на такте/ т-место буфера «-пользователя пусто и заполнено соответственно.

Предположим, что существует финальное распределение ЦМ {z'}. Обозначим pl(n,m) = limp¡(n,/n) и ра(п,т) = \\т р'0{п,т). Тогда вероятность занятости т-места буфера «-пользователя p¡ (п,т) определяется по следующему рекуррентному соотношению. Утверждение 4.

PiM) = p р,{п,т + \) = p1(n,m)-(l-P) + p0{n,m)-(l-V)-Q„(m) + a-Q„(m),

т = О.М-1. (6)

Заметим, что рекуррентное соотношение (6) дает метод для расчета вероятности p¡(n, М) того, что М-место буфера «-пользователя заполнено. Отсюда вероятность V(n) просмотра «-пользователем видео без перерывов воспроизведения имеет вид

У{и) = д(п,М). (7)

В разделе 3.3 проведен анализ нескольких стратегий загрузки и их сравнение с точки зрения двух показателей эффективности функционирования

1, j=i, О, j * i.

потоковых сетей - вероятности V просмотра видео без перерывов воспроизведения и задержки % начала воспроизведения. В построенной модели задержка начала воспроизведения представляет собой интервал времени с момента появления пользователя в сети, через который на М-месте буфера пользователя появится порция видеоданных, т.е. число тактов, через которые пользователь начнет просматривать видеопоток. Анализ стратегий выполнен с помощью разработанной имитационной модели для следующих исходных данных, близких к реальным: в сети находятся N=1000 пользователей, каждый из которых имеет буфер с М=40 местами для хранения порций данных. На первом этапе анализ проведен для случая, когда все пользователи постоянно находятся в сети и не покидают ее (а = 0 и Р = 0). Результаты анализа показали, что при использовании стратегии ЯР вероятность просмотра видео без перерывов воспроизведения выше, чем при использовании стратегии вг, т.е. УСг, что показано на графиках рисунка 5 в точке от=39.

Рис. 5. Вероятность р, (п,т) наличия данных на т-месте в буфере (а =0 и (5 =0)

На втором этапе анализ проведен для случая, когда пользователи могут появляться в сети с вероятностью а > 0 и покидать ее с вероятностью р > 0. Результаты анализа показали, что с точки зрения просмотра видео без перерывов воспроизведения не всегда стратегия ИР работает лучше стратегии вг. При больших значениях вероятности ¡3 ухода пользователей из сети, т.е. когда пользователи в большом количестве покидают сеть или переключаются на другой телеканал, например, во время рекламы, вероятность просмотра видео без перерывов воспроизведения выше при использовании стратегии вг, чем при использовании стратегии ИР, т.е. У°Г>УКР, а при небольших значениях вероятности р ухода пользователей из сети вероятность просмотра

видео без перерывов воспроизведения выше при использовании стратегии ЯР, чем при использовании стратегии О г, т.е. > УСг.

Кроме того, результаты второго этапа анализа показали, что х1^ >ТСг при любых значениях аир, т.е. задержка начала воспроизведения при использовании стратегии Сг меньше, чем при использовании стратегии Ш3, например, при а =0,5 и Р=0,1 имеем 1^-21 тактов и ТСг = 2 такта. Это объясняется тем, что при стратегии вг приоритет при загрузке отдается последним местам буфера, а при стратегии ИР - первым местам буфера.

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

В заключении сформулированы основные результаты, полученные в диссертации.

Основные результаты и выводы

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

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

3. В виде цепи Маркова разработана модель процесса заполнения буфера оборудования пользователя при воспроизведении видеопотока в одноранговой сети с учетом вероятностей появления пользователя в сети и его ухода из сети. В модели номер места в буфере для загрузки порции данных определяется в соответствии с заданной стратегией загрузки.

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

Основные результаты диссертации отражены в следующих опубликованных работах:

1. Адаму А., Гайдамака Ю.В., Самуйлов А.К. Построение и анализ модели воспроизведения каналов вещательного телевидения в P2P сети // «Вестник РУДН. Серия «Математика. Информатика. Физика». - 2010. -№3(1).-С. 47-53.

2. Адаму А., Гайдамака Ю.В., Самуйлов А.К. К анализу состояния буфера пользователя одноранговой сети с потоковым трафиком // Т-Сошш -Телекоммуникации и Транспорт. - 2011. - №7. - С. 8-12.

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

4. Адаму А., Гайдамака Ю.В. Анализ вероятности непрерывного воспроизведения видеопотока в Р2Р-сети // «Вестник РУДН. Серия «Математика. Физика». - 2011. - №4. - С. 38-46.

5. Adamu A., Gaidamaka Yu., Samuylov A. Analytical Modeling of P2PTV Network // Proc. of the 2nd International Congress on Ultra Modern Telecommunications and Control Systems (IEEE ICUMT 2010), Oct. 18-20, 2010. - Moscow,Russia.-P. 1115-1120.

6. Adamu A., Gaidamaka Yu., Samuylov A. Discreet Markov Chain Model for the Analysis of P2P Streaming Network Probability Measures // Proc. of the IEEE 11th International Conference on Next Generation Wired/Wireless Networking (IEEE NEW2AN 2011), Aug. 23-25, 2011. - St. Petersburg, Russia. -P. 428-439.

Адаму Амину (Нигерия)

Построение вероятностных моделей и анализ показателей эффективности функционирования потоковых одноранговых сетей

В виде замкнутой однородной сети массового обслуживания (СеМО) с одной заявкой построена модель поведения пользователя услуги цифрового вещательного телевидения, на основе которой разработана общая модель потоковой одноранговой сети с несколькими пользователями.

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

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

Adamu Aminu (Nigeria)

Probabilistic models construction and analysis of performance efficiency

measures OFP2P streaming networks

In the form of homogeneous closed queuing network with one call (request), a model of user behavior for a broadcast digital television service was developed, based on which a general model of P2P streaming network with finite number of users was developed.

For the network model with high and low uploading users, an analytical formula for the probability of universal streaming was obtained, and an approximation formula for the probability of universal streaming for the case of network with infinite users was obtained using the normal law.

A Markov chain model of buffer filling process by a user while playing a video stream in P2P network was developed, taking into account the probability of user appearance into the network and the probability of his departure out of the network. In the model, a user downloads a video chunk in accordance with the chunk selection strategy. The formula for the probability of playback continuity was obtained.

Подписано в печать 20.01.2012г.

Заказ № 07557 Тираж: ЮОэкз. Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

61 12-1/449

РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

На правах рукописи

Адаму Амину

ПОСТРОЕНИЕ ВЕРОЯТНОСТНЫХ МОДЕЛЕЙ И АНАЛИЗ ПОКАЗАТЕЛЕЙ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ПОТОКОВЫХ ОДНОРАНГОВЫХ СЕТЕЙ

Специальность 05.13.17 - теоретические основы информатики

Диссертация

на соискание ученой степени кандидата физико-математических наук

Научный руководитель кандидат физико-математических наук, доцент Гайдамака Юлия Васильевна

Москва-2012

ОГЛАВЛЕНИЕ

1.2.

1.3.

1.4.

Глава 2.

список основных обозначений

Введение

глава 1. Особенности построения моделей одноранговых сетей

1.1. Принципы построения файлообменных и потоковых сетей

Жидкостная модель файлообменной сети Модели файлообменной сети с учетом расстояния взаимодействия пользователей Постановка задачи исследований Аналитическая модель одноранговой сети вещательного телевидения

2.1. Принципы вещательного телевидения в одноранговой сети

2.2. Модель потоковой сети в виде однородной сети массового обслуживания

2.3. Анализ модели сети с двумя типами пользователей с высокой и с низкой скоростью раздачи видеопотока

2.4. Аппроксимация нормальным законом вероятности всеобщей передачи

Глава 3. Модель для анализа вероятности просмотра видео без перерывов воспроизведения в одноранговой сети

3.1. Анализ процесса обмена данными между пользователями в потоковых сетях

3.2. Модель процесса заполнения буфера оборудования пользователя в виде цепи Маркова

3.3. Анализ стратегий заполнения буфера Заключение

Библиография

3 6

13

13

16 28

42 45

45

48

59

65

70

70 77

84

104

105

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ

Глава 1

- число личеров в сети в момент времени t > О

y(t) — число сидов в сети в момент времени t> О

Я - интенсивность поступления личеров в сеть

М — скорость раздачи пользователя

С - скорость загрузки пользователя

в - интенсивность отмены процесса загрузки личерами

7 - интенсивность ухода сидов из сети

Л - доля личеров, участвующих в процессе раздачи

данных

F - размер загружаемого файла

Т - время загрузки файла,

англ. Latency

R - ограниченное расстояние для установления

соединения

Глава 2

М - число ТВ каналов Р2РТУ-сети

N - число пользователей Р2РТУ-сети

© - маршрутная матрица

вш - вероятность переключения с ¿-канала на т-канал

Хт - число пользователей на ш-канале

X(i) - процесс, описывающий функционирование сети

рт - популярность т-канала

^fl - среднее время просмотра т-канала «-пользователем

х - состояние «-пользователя на т-канале

пт

X - матрица, описывающая состояние сети

Ж - пространство состояний сети

ут - среднее число пользователей на ш-канале при N по

Rm - скорость воспроизведения т-канала

Wnm (Х) - видеопоток, доступный «-пользователю, просматривающему т-канал

К (Х) и„

Nh N'

rh

' т

г1

/ т

К

Глава 3

N

М

а(п)

*« W

х(«)

Х = (хМЦ

Z = (X,a)

рх{п,т)

pQ(n,m) «

суммарный видеопоток, доступный всем пользователям, просматривающим те-канал

вероятность состояния всеобщей передачи т-канала, англ. Universal Streaming

скорость раздачи видеопотока «-пользователем

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

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

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

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

отношение числа пользователей с высокой скоростью раздачи к числу пользователей с низкой скоростью раздачи

- число пользователей

- число мест в буфере

- индикатор присутствия «-пользователя в сети

- состояние т-места буфера «-пользователя

- вектор, описывающий состояние буфера п-пользователя

- матрица, описывающая состояние буферов всех пользователей

- вектор, определяющий состояния всех пользователей сети

- состояние сети

- пространство состояний сети

- вероятность выбора и успешной загрузки порции видеоданных для т-места буфера «-пользователя

- вероятность того, что т-место буфера «-пользователя заполнено данными

- вероятность того, что т-место буфера «-пользователя пусто

- вероятность появления пользователя в сети

Р - вероятность ухода пользователя из сети

V - вероятность просмотра видео без перерывов

воспроизведения (вероятность непрерывного воспроизведения видеопотока), англ. Playback Continuity

т - задержка начала воспроизведения,

англ. Startup Delay

S - стратегия выбора места буфера для загрузки порции

данных (стратегия загрузки)

ВВЕДЕНИЕ

Современная одноранговая сеть (от англ. peer-to-peer, Р2Р - «равный к равному») объединяет пользователей, которые без централизованного управления делают свои ресурсы (вычислительная мощность, объем памяти и др.) доступными друг другу, и не только загружают, но и раздают загруженные данные другим пользователям, что снижает нагрузку на серверы-источники информации. Различают файлообменные и потоковые одноранговые сети. Первоначально одноранговые сети использовались для обмена файлами, такими как видеоролики, фильмы, электронные книги и др. Такие сети называют файлообменными Р2Р-сетями. Только недавно технология Р2Р начала использоваться для передачи потокового трафика, например, при предоставлении услуги цифрового вещательного телевидения. Несколько потоковых Р2Р-систем были успешно созданы для предоставления услуги потокового видео по требованию и услуги видео в режиме реального времени через Интернет и сейчас обслуживают одновременно сотни тысяч пользователей, просматривающих телевизионные каналы со скоростью от 300 кбит/с до 1 Мбит/с. Примерами таких систем являются PPLive, PPStream, UUSee , SopCast, CoolStreaming, TVants и многие другие. В ближайшие годы эти системы будут использоваться при трансляции большого числа телевизионных каналов со всего мира для огромного количества пользователей и могут составить серьезную конкуренцию известным подходам к предоставлению услуг IPTV, таким как традиционное IP-мультивещание. Дальнейший рост объемов трафика потокового вещания через Интернет с использованием Р2Р архитектуры ожидается также за счет видео, произведенного самими пользователями и транслируемого с их веб-камер и беспроводных устройств. Привлекательность технологии Р2Р обусловлена в том числе низкой стоимостью развертывания Р2Р-сети, поскольку она является наложенной и для ее организации не требуется дополнительного сетевого оборудования.

Для анализа показателей эффективности функционирования файлообменных сетей применяются так называемые жидкостные модели, а для анализа показателей эффективности потоковых сетей - дискретные модели. Существенный вклад в развитие данной области внесли в основном зарубежные ученые: L. Kleinrock, K.W. Ross, Е. Setton, В. Girod, В. Hajek, R. Srikant, D. Qiu, F. Clévenot, Ph. Nain, J. Virtamo и др. [48, 58, 80, 83, 84, 85, 88]. При анализе моделей Р2Р-сетей используют методы исследований, разработанные известными российскими учеными: Г. П. Башариным, В. М. Вишневским, Б. С. Гольдштейном,

А. Е. Кучерявым, А. В. Печинкиным, А. П. Пшеничниковым,

К. Е. Самуйловым, С. Н. Степановым, А. Д. Харкевичем,

И. И. Цитовичем, М. А. Шнепс-Шнеппе, С. Я. Шоргиным и др. [7, 10, 18, 23, 26].

Отметим, что наиболее исследованными являются модели файлообменных одноранговых сетей [37, 44, 48, 62, 85, 88], а публикаций, посвященных потоковым одноранговым сетям [42, 58, 79, 84], насчитывается значительно меньше. Ввиду изложенного, с учетом известных на момент написания диссертационной работы результатов, актуальной является задача разработки дискретных математических моделей, предназначенных для анализа потоковых одноранговых сетей.

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

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

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

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

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

2. В разработке модели воспроизведения видеопотока в Р2Р-сети, отличия которой от известных моделей состоят в следующем.

- Модель с учетом вероятностей появления пользователя в сети и его ухода из Р2Р-сети ранее не исследовалась.

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

Модели, методы и алгоритмы, разработанные в диссертационной работе, предназначены для расчета показателей эффективности потоковых одноранговых сетей - вероятности состояния всеобщей

передачи транслируемых в сети каналов, вероятности просмотра видео без перерывов воспроизведения видеопотока и задержки начала воспроизведения видеопотока. Эти показатели могут быть применены проектными организациями и операторами сетей при планировании сетевых ресурсов, требуемых для обеспечения надлежащего уровня качества обслуживания пользователей. Результаты диссертации использованы в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов, обучающихся по направлению «Прикладная математика и информатика», при подготовке магистерских диссертаций, а также в рамках исследований по гранту РФФИ №10-07-00487-а «Задача управления доступом в широкополосной сети и анализ марковской модели с мультипликативным распределением вероятностей состояний» и НИР 020612-1-173 «Разработка математических моделей и методов анализа информационно-телекоммуникационных сетей».

Результаты, полученные в ходе выполнения работы, были представлены на IV отраслевой научной конференции-форуме «Технологии информационного общества» 5-7 апреля 2010 г. (Москва, МТУСИ); XL VI Всероссийской научной конференции факультета физико-математических наук РУДН, 19-23 апреля 2010 г. (Москва, РУДН); 2-d International Congress on Ultra Modern Telecommunications and Control Systems (IEEE ICUMT 2010), Oct. 18-20, 2010 (Moscow, Russia); V отраслевой научной конференции-форуме «Технологии

информационного общества», 9-10 февраля 2011 г. (Москва, МТУСИ); XL VII Всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем», 18-22 апреля 2011 г. (Москва, РУДН); 11th International Conference on Next Generation Wired/Wireless Networking, NEW2AN, Aug 23-25, 2011 (St. Petersburg, Russia).

Диссертация состоит из введения, трех глав, заключения и библиографии из 107 наименований. Глава 1 посвящена особенностями построения моделей одноранговых сетей. В разделе 1.1 описываются принципы построения и классификации одноранговых сетей, для каждого класса Р2Р-сети коротко описан процесс его функционирования и определены его показатели эффективности: для файлообменных сетей -время загрузки файла (англ. Latency), для потоковых сетей - задержка начала воспроизведения (англ. Startup Delay), вероятность просмотра видео без перерывов воспроизведения (англ. Playback Continuity) и вероятность состояния всеобщей передачи или для краткости вероятность всеобщей передачи (англ. Universal Streaming). Далее на основе аналитического обзора источников, указанных в библиографии, в разделах 1.2 и 1.3 исследованы жидкостные модели, предназначенные для анализа времени загрузки файла, причем отличие моделей раздела 1.3 состоит в учете расстояния между пользователями. Исследованы три режима функционирования сети: жидкостной, жесткий и стационарный. При написании главы 1 были использованы источники [7,8,11,35,37,38,39,44,45,49,51,52,60,62,67,70,75,76,77,81,85,89].

Глава 2 посвящена построению и анализу модели одноранговой сети вещательного телевидения, далее - Р2РТУ-сети. В разделе 2.1 детально исследованы принципы функционирования одноранговой сети вещательного телевидения. В разделе 2.2 исследован метод построения одноранговой сети с потоковым трафиком в виде экспоненциальной однородной сети массового обслуживания и построены модели P2PTV-сети с конечным и бесконечным числом пользователей, основанные на модели поведения пользователя. Получена формула для расчета вероятности жт состояния всеобщей передачи ш-канала Р2РТУ-сети в зависимости от популярности канала. В разделе 2.3 рассмотрены частные случае исследованных в разделе 2.2 моделей для анализа сети с двумя классами пользователей - пользователи с высокой скоростью отдачи данных и пользователи с низкой скоростью отдачи. Проведен численный

анализ вероятности всеобщей передачи телевизионных каналов с различными популярностями в зависимости от числа пользователей с низкой и с высокой скоростью отдачи. В разделе 2.4 получена аппроксимация для упрощения расчета вероятности всеобщей передачи канала Р2РТУ-сети для случая сети с бесконечным числом пользователей. При написании главы 2 были использованы источники [8,9,10,11,12,14,16,36,37,40,50,55,56,58,59,61,63,64,65,66,69,73,74,78,83,86, 87,90,91,92,94,96,99,101,102,103,104,105,106].

Глава 3 посвящена разработке модели анализа вероятности просмотра видео без перерывов воспроизведения в Р2РТУ-сети. В разделе 3.1 детально исследован процесс обмена данными между пользователями потоковой Р2РТУ-сети на основе механизма буферизации. В разделе 3.2 в виде цепи Маркова (ЦМ) построена модель процесса заполнения буфера оборудования пользователя, учитывающая стратегию заполнения буфера, а также возможность появления пользователя в сети и его ухода из сети. Определена вероятность того, что в начале такта у одного или нескольких находящихся в сети пользователей имеется порция данных для загрузки «-пользователю на m-место в его буфере в соответствии со стратегией выбора. Получен метод расчета вероятности просмотра видео без перерывов воспроизведения. В разделе 3.3 проведен анализ нескольких стратегий заполнения буфера пользователя для проверки их эффективности с точки зрения показателей эффективности функционирования потоковых Р2Р-сетей - вероятности просмотра видео без перерывов воспроизведения и времени ожидания начала просмотра. Для этого введено формальное описание двух наиболее часто используемых стратегий загрузки - Rarest First и Greedy. Проведен численный анализ Р2Р-сети с постоянно находящимися в сети пользователями, а также Р2Р-сети, в которой пользователи могут подключаться к сети и уходить из нее. Для максимизации вероятности просмотра видео без перерывов воспроизведения и минимизации времени ожидания начала просмотра в

разделе 3.3 работы предложены и исследованы смешанные стратегии, которые показали более высокую эффективность. При написании главы 3 были использованы источники [8,11,15,28,41,43,58,66,78,80,83,94,104].

В заключении сформулированы основные результаты, полученные в диссертации.

ГЛАВА 1

ОСОБЕННОСТИ ПОСТРОЕНИЯ МОДЕЛЕЙ ОДНОРАНГОВЫХ

СЕТЕЙ

1.1. Принципы построения файлообменных и потоковых сетей

Peer-to-Peer (Р2Р) (от англ. peer-to-peer, Р2Р - «равный к равному») технологии в последнее время стали перспективным подходом к построению распределенных и масштабируемых сетевых приложений. Основная идея дизайна Р2Р заключается в мотивировании пользователей выступать в роли клиента и сервера одновременно, и в этом случае пользователей называют пирами (англ. peer - равный). Здесь и в дальнейшем ввиду отсутствия русскоязычных терминов мы будем использовать обозначения, полученные транслитерацией на русский язык англоязычных терминов. В Р2Р-сетях пользователи не только загружают данные от других пользователей, но и раздают загруженные данные другим пользователям, требующим эти данные. Таким образом, пропускная способность конечных пользователей эффективно используется для того, чтобы уменьшить нагрузку на серверы.

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