diploma.tex

% Титульный лист (отдельно)
% Лист задания (отдельно)
% Аннотация (отдельно)

\nocite{*}
% Оглавление
\tableofcontents

\section*{Введение}
\addcontentsline{toc}{section}{Введение}
	Актуальность темы. Уже сейчас только объём видео-контента высокого качества (в 4K разрешении) достигает
	колоссальных размеров, а его передача большой аудитории зрителей в режиме реального времени требует поддержания
	масштабной инфраструктуры, затраты на которую будут только рости с повышением качества контента и увеличением числа
	пользователей. Если не начать решать задачу оптимизации систем для вещания видео-трансляций сейчас, то в
	скором будущем такие системы не смогут одновременно обеспечивать качественный сервис для своих зрителей и в тоже
	время оставаться рентабельными. Для решения поставленной задачи можно использовать несколько подходов. Одним из них
	является переход от традиционной клиент-серверной модели к модели одноранговых сетей. Именно этот подход лежит в
	основе системы, описываемой в работе.

	Цель работы заключается в разработке P2P-системы для организации вещания видео-трансляций в режиме
	реального времени с использованием мобильного приложения. В данной работе демонстрируется один из вариантов
	построения системы на базе одноранговых сетей для передачи потокового контента между пользователями, которая
	позволит большому числу участников вести  видео-трансляции в режиме реального времени, а основными узлами
	инфраструктуры системы выступают сами устройства зрителей. Главные особенности такого подхода заключаются в:
	\begin{itemize}
		\item значительном снижаении числа централизованных узлов, что непосредственно влияет на отказоустойивость
		системы в целом, а так же на стоимость поддержки системы;
		\item организации системы, управление которой принадлежит самим пользователям, а не ограниченному кругу лиц.
	\end{itemize}

	Объектом исследования являются P2P-системы для организации обмена видеоконтентом между узлами в режиме
	реального времени.

	Предметом исследования являются методы организации передачи видеоконтента в режиме реального времени в
	P2P-системах.

	Научная новизна. На момент разработки системы существует ряд исследований по данному направлению, но
	большинство из них носит академический характер в виде исследовательских работ и не были апробированы в реальных
	условиях, а только были реализованы прототипы для проведения тестирования (GridMedia \cite{4013958}, Overcast
	\cite{1251243}, NICE \cite{633045}, ZIGZAG \cite{2314951}, Chainsaw \cite{2138975}, CoolStreaming \cite{878473483},
	LayerP2P \cite{5208239}). Лишь небольшое число систем, описанных в исследовательских работах, было воплощено в
	готовые продукты для конечных пользователй, но и они не пока не стали широко распространены (PPLive \cite{1403001},
	PPStream \cite{4685232}, SOPCast \cite{4346415}). По этому, учитывая сложившуюся ситуацию, я
	считаю, что разработка системы, которая носит практическую ценность, а не только исследовательскую, является важным
	шагом на пути распространения систем такого типа, так как по настоящему корректность описанных моделей можно лишь
	проверить на практике, и есть вероятность, что часть моделей может оказаться непригодной к реальным условиям.

% Основная часть
\section{Анализ предметной области}

	В последнее время стремительно растёт популярность приложений, в которых используется потоковое видео-вещание.
	В качестве примеров можно привести сервисы YouTube и Netflix. Только у Netflix насчитывается более 100 миллионов
	пользователей, которые просматривают более 125 миллионов часов фильмов и сериалов каждый день. Но так стремительно
	растёт не только пользовательская база \cite{4454567}. Трафик, генерируемый просмотром потокового видео-контрента высокого
	разрешения, достигает до 50\% всего трафика на территории Соединённых Штатов Америки, из которых 20\% принадлежат
	трафику Netflix. Для предоставления сервиса потокового вещания в таких масштабах Netflix использует ресурсы
	сторонних CDN, а с 2011 года разворачивает свою выделенную инфраструктуру CDN в рамках проекта Open Connect для
	снижения эксплуатационных расходов.

	Помимо CDN существует и другой способ доставки контента до пользователей: одноранговые (пиринговые) сети.
	Главная особенность таких сетей заключается в том, что участник сети одновременно является и получателем контента,
	и сам принимает участие в передаче контента другим заинтересованным участникам. Таким образом, ресурсы каждого из
	участника становятся частью общедоступных ресурсов всего сервиса. Это позволяет быстро и дёшево масштабировать
	сервис в зависимости от числа пользователей, что является важным показателем для сервисов потокового видео-вещания.
	Резкое изменение числа пользователей сервиса обуславливается привычками пользователей. Например, в вечерние часы
	число пользователей резко возрастает. Так же резкий рост нагрузки на систему может возникать в ходе проведения
	различных мероприятий (спортивные игры, концерты, празники).

	На протяжении последних лет в научном сообществе было предложено множество различных схем организации пиринговых
	сервисов обмена видео-контентом по запросу, так и в режиме реального времени. Но до сих пор остаётся открытым вопрос
	об архитектуре, которая наилучшим образом подойдёт для решения большинства задач. Некоторые авторы утверждают, что
	mesh-архитектура обладают наилучшей производительностью, тогда как tree-архитектура лучше подходит для организации
	вещания в режиме реального времени. Главный вопрос заключается в выборе архитектуры, в системе на базе которой будут
	наименьшие издержки на накладные расходы, наименьшее время на задержку перед вещанием и наименьшее число прерываний
	во время вещания. Некоторые авторы предлагают гибридные системы разных видов, когда в системе или берутся лучшие
	идеи из разных архитектур и совмещаются вместе (что повышает сложность таких систем и издержки на накладные расходы),
	или в зависимости от текущих условий работы система выбирает наиболее подходящую архитектуру организации системы.
	На рисунке \ref{img:p2p-mechanisms} представленно отображение проблемы, когда каждый из типов архитектур лучше
	подходит под те или иные условия и нет единого универсального решения.

	\begin{figure}[h]
		\center{\includegraphics[width=0.8\linewidth]{p2p-mechanisms.png}}
		\caption{Механизмы организации системы в зависимости от условий}
		\label{img:p2p-mechanisms}
	\end{figure}

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

	Для достижения поставленной цели были рассмотренны следующие задачи:
	\begin{itemize}
		\item анализ литературы в области существующих решений P2P-систем для ведения трансляций (такой анализ позволил
		определить ключевые аспекты архитектуры рассматриваемых систем и определить потенциальные возможности и
		недостатки этих систем);
		\item проектирование системы в целом и архитектруы мобильного приложения в частности (при решении этой задачи
		было получено описание всех необходимых модулей системы, схема их взаимодействия, а так же модель для данных,
		которые используются при передаче информации от одного модуля к другому);
		\item разработка модуля системы, отвечающего за формирование и поддержание связей между участниками и передачу
		данных между ними;
		\item разработка мобильного приложения для пользователей, с помощью которого они могут вести свои
		видео-трансляции или могут быть зрителями других трансляций;
		\item тестирование разработанного ПО для получения данных об эффективности применяемых подходов в его создании.
	\end{itemize}

	\subsection{Традиционные способы организации видео-трансляций}
	Первым, что приходит на ум при упоминании традиционных систем передачи контента с большой аудиторией - это
	телевизионное вещание. В его основе лежит простая идея - транслировать контент всем, кто находится в пределах
	досягаемости (broadcast). Но такой подход не применим для передачи контента через Интернет, так как лишь
	заинтересованные лица должны получать контент (multicast). При таком подходе система может быть
	организована с использованием паттерна издатель/подписчик, когда заинтересованные участники объеденяются в группы и
	получают новый контент предназначенный конкретной группе. В контексте систем видео-трансляций в режиме реального
	времени этот подход является ключевым и может быть реализован на различных уровнях сетевой модели OSI.

	Существует два подхода к организации multicast в рамках стека TCP/IP: Internet Protocol Multicast \cite{rfc791} и Application
	Level Multicast (ALM). На рисунке \ref{img:ip-multicast-vs-application-multicast} представленно схематическое
	изображение каждого из подходов, а далее по тексту приведенно более подробное описание каждого подхода.

	\begin{figure}[h]
		\center{\includegraphics[width=0.7\linewidth]{ip-multicast-vs-application-multicast.png}}
		\caption{Схема взаимодействия узлов при работе через IP Multicast и ALM}
		\label{img:ip-multicast-vs-application-multicast}
	\end{figure}

		\subsubsection{Internet Protocol Multicast}
		Протокол сетевого уровня модели OSI IP уже включает в себя поддержку многоадрессного вещания
		(multicast). Но несмотря на высокую производительность этой технологии по сравнению с другими, она не
		стала массово распространенной из-за дополнительных требований к роутерам в сети Интернет и ограниченности
		доступных адресов для организации групп пользователей. В рамках одной автономной системы эта технологий может
		использоваться для организации IP-телевидения (IPTV), но не в рамках глобального Интернета для организации
		видео-трансляций.

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

		\subsubsection{Application Level Multicast}
		Для преодоления проблем развёртывания систем с использованием IP multicast, в настоящее время multicast
		реализуют на уровне приложения (Application Level Multicast). В приложении описывается протокол, с
		использованием которого организуется передача данных. Тогда как в IP multicast пересылкой и дублированием
		пакетов занимаются роутеры, в ALM этим занимаются конечные устройства пользователей. Коммуницирование между
		конечными устройствами происходит с использованием только IP unicasts, в связи с чем на промежуточные устройства,
		такие как роутеры, не накладываются дополнительные ограничения. Но если сравнивать использование IP unicasts с
		IP multicast, то в ALM появляется дополнительный накладной трафик, так как пакеты с одним контентом могут
		пересылаться по одним и тем же направлениям несколько раз.

		С точки зрения P2P-систем, ALM подходит под это определение, так как узлы предоставляют ресурсы, такие как
		пропускная способность и вычислительная мощность, друг другу. Архитектура multicast-системы может быть
		централизованной или полностью распределённой, в зависимости от сценария использования приложения. Одним из
		примеров систем общего назначения ALM, построенным на основе Distributed Hash Table (DHT) \cite{6763343}, является Scribe, в
		которой отсутствуют централизованные элементы.

		Также нужно отметить разницу между используемыми топологиями в IP multicast и ALM. IP multicast всегда
		использует spanning tree для организации вещания несколькими участниками в рамках одной группы, а в ALM
		может использоваться любая сетевая топология. Так, для предотвращения дублирования и избежания не нужных
		пересылок, большинство систем поддерживают список в виде дерева для распространения пакетов данных. Для ведения
		трансляций в режиме реального времени требуется высокая пропускная способность и низкие задержки при передачи
		данных от источника к участникам, что влияет на выбор подходящей топологии при построении системы.

	\subsection{Пиринговое вещание}
	P2P-системы для видео-трансляций в режиме реального времени являются подмножеством ALM-систем, в которых
	распространение контента от источника реализовано на уровне приложения. Но в отличии от стандартных ALM-систем,
	P2P-системы включают конечных пользователей в общую схему доставки контента. Таким образом, каждый пользователь
	вносит вклад в распространение контента, который он получает от других пользователей, предоставляя свои ресурсы.
	Это требует координации между пользователями, что бы быть увереным, что каждый из участников получит пакеты данных,
	требуемые для декодирования видео-потока. Существующие P2P-системы можно разделить на tree-based,
	mesh-based или hybrid, в зависимости от их топологии сети.

		\subsubsection{Tree-based topologies}
		Tree-based системы по строению схожи с дизайном IP multicast систем, в которых узлы образуют дерево, исходящее
		от источника. Такое строение обеспечивает низкие задержки и корректный порядок пакетов при передачи данных.
		Новые пользователи, при подключении, занимают своё место в дереве в соответствии с протоколом построения
		оверлейной сети. Источник посылает пакеты своим дочерним узлам, тем в свою очередь пересылают своим дочерним
		узлам и так далее. Так как данные пересылаются от источника к листьям по дереву в порядке их отправления, то не
		требуется механизм планирования доставки пакетов. Вместо этого какждый узел просто пересылает все полученные
		пакеты своим дочерним узлам. Такой подход к организации передачи данных называют push-based. Так как
		узлы в системе расположены в виде дерева, то возникает вопрос в выборе оптимального соотношения между шириной и
		высотой дерева. Чем дерево шире, тем меньше его высота, и данные быстрее доходят до листьев дерева. Но в то же
		время это повышает ветвление в промежуточных узлах, что означает увеличение нагрузки в этих узлах.

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

		Для повышения надёжности системы во время активного изменения дерева узлов, а некоторых системах используется
		несколько деревьев. Разница между системами с одним деревом и несколькими показана на рисунке
		\ref{img:tree-based-system}. Обе оверлейные сети состоят из источника (S) и пятерых зрителей (A-E). В системе с
		одним деревом используются ресурсы только узлов A и B. В системе с несколькими деревьями поток данных от
		источника разделён на два, и для каждого из них используется своё дерево. Каждый из узлов включён в каждое из
		деревьев только один раз, что позволяет каждому из пользователей предоставлять свои ресурсы системе. Совместо с
		применением MDC для декодирования видео становится возможным передача независимых частей трансляции по каждому
		из дереьев, которые могут быть декодированы независимо друг от друга. Таким образом решения на базе нескольких
		деревьев эффективнее используют ресурсы узлов и имеют повышенную стабильность в сравнении с системами с одним
		деревом.

		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{tree-based-system.png}}
			\caption{Организация оверлейной сети в tree-based системах}
			\label{img:tree-based-system}
		\end{figure}

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

		\subsubsection{Mesh-based topologies}
		В mesh-based системах участники соединены между собой краткосрочными соединениями. Они обмениваются друг с
		другом информациий о доступном контенте на каждом из узлов и запрашивают друг у друга недостающие части на
		основе этих данных. Механизм, когда сам получатель запрашивает недостающие части, называется pull-based.
		Для получения сведений о новых узлах в системе, участники регулярно обмениваются информацией о их текущих
		соседних узлах. В случае, когда узел узнаёт о новых участника в системе, он может инициировать новое соединение.
		На рисунке \ref{img:mesh-based-system} показана оверлейная топология mesh-based систем в два разных момента
		времени.

		\begin{figure}[h]
			\center{\includegraphics[width=0.7\linewidth]{mesh-based-system.png}}
			\caption{Организация оверлейной сети в mesh-based системах}
			\label{img:mesh-based-system}
		\end{figure}

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

		Узлы в mesh-сетях как правило поддерживают соединение до тех пор, пока оно используется для передачи данных
		трансляции. Если отправитель не содержит боьше нужных получателю пакетов данных, то соединение может быть
		закрыто и установлено новое с другим узлом. Время существования соединения не влияет на схему планирования
		передачи данных в pull-based системах, так как регулярно каждый узел сообщает сведения о доступных у него
		пакетах данных соседним участникам. И в случае, если не удалось загрузить данные с одного узла, то они
		будут запрошены с другого узла, который ранее сообщих о их доступности. Из-за такого поведения mesh-based
		системы более устойчивы к регулярной смене узлов в оверлейной сети, но в то же время появляются дополнительные
		накладные расходы и увеличиваются задержки на передачу данных.

		Обе схемы планирования распространения контента показаны на рисунке \ref{img:scheduling-scheme}. Так, в
		push-based системах получатель отправляет запрос источнику на установку соедиения, и после получения
		подтверждения, он будет получать новые пакеты данных от источника, как только они станут доступны отправителю.
		Когда получатель решит, что он больше не хочет получать данные от источника, то он просто закроет соединение.
		В pull-based системах в место установления соединения источник отправляет информацию о доступных пакетах данных
		(buffermap) получателю, а тот на основе полученной информации запрашивает необходимые ему пакеты данных. Для
		каждого пакета данных получатель отправляет отдельный запрос. По прошествию небольшого отрезка времени,
		источник отправляет обновлённую информацию о доступных пакетах, которые он получил за время после отправки
		предыдущей информации.

		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{scheduling-scheme.png}}
			\caption{Схемы планирования распространения контента в push-based системах (слева) и в pull-based системах
					(справа)}
			\label{img:scheduling-scheme}
		\end{figure}

	\subsection{Обзор аналогов}
		\subsubsection{P2P tree-based system}

		Overcast. Одним из примеров систем с единым деревом в основе оверлейной сети является Overcast. В этой системе
		создаётся и поддерживается единое дерево, которое имеет высокую пропускную способность для передачи контента от
		источника до получателей. Алгоритм, отвечающий за построение дерева, выбирает такое строение, при котором будет
		максимальной пропускная способность от источника до каждого листа. Это достигается путём поддержания небольшого
		числа соединений на промежуточных узлах, что отрицательно влияет на задержки в узлах-листах. Overcast не был
		спроектирован для видео-трансляций в режиме реального времени, а его задачей является передача контента большим
		группам пользователей, где допустимы задержки до 15 секунд. Основной целью является доставка контента не на
		прямую конечным пользователям (участникам оверлейной сети), а вместо этого конечные пользователи получают
		контент с узлов сети Overcast используя протокол Hypertext Transfer Protocol (HTTP) \cite{2345234}. Таким
		образом эту систему можно сравнить с CDN.

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

		CoopNet. Система CoopNet является одной из первых, в которой P2P-подход не полностью заменяет централизованный подход
		для решения задач видео-трансляций, а совмещает в себе принципы из двух подходов. Авторы предположили, что
		узлы в системе могут часто как присоединяться, так и отключаться от оверлейной сети, что делает её непостоянной.
		Одиним из решений проблемы устойчивости к потере пакетов было использование видео-кодека MDC и рассылка
		независимых пакетов данных по разным деревьям в сети для возможности независимого декодирования потока на
		узле зрителя. Для поддержания консистентного состояния дерева используется централизованный узел в виде
		источника, который выполняет всю необходимую работу поддержания топологии. Централизованный подход к построению
		оверлейной сети позволяет CoopNet оптимизировать дерево узлов в соответствии с текущими условиями.
		В представленном отчёте о работе системы видно, что применение системы позволило значительно снизить нагрузку
		на центральный сервер при массовом прибытии новых пользователей.

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

		SplitStream. Система SplitStream \cite{945474} отличается от других решений тем, что не строит свою оверлейную сеть, а вместо
		этого использует DHT и системы группового общения, построенные поверх DHT. Авторы используют в своей работе SCRIBE \cite{1038579} и
		PASTRY \cite{Rowstron2001}, но так же могут быть использованы и другие системы. Изначально система SCRIBE не проектировалась для
		передачи больших объёмов данных, но использование нескольких деревьев для передачи пакетов данных решает данную
		проблему.

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

		Stanford Peer-to-Peer Multicast. Протокол Stanford Peer-to-Peer Multicast (SPPM) \cite{5167392} использует ключевые идеи двух уже рассмотренных выше систем:
		CoopNet и SplitStream. В нём также поддерживаются несколько деревьев, но не используется MDC кодирование.
		Вместо этого, если при первоначальной передаче от источника к получателю пакет не был доставлен, то получатель
		запрашивает недостающий пакет сам у родительского узла. Если родительский узел в течении определённого времени
		не переслал нужный пакет, то требуемый пакет запрашивается у других узлов. SPPM оптимизирован для передачи
		видео в формате H.264/AVC, выставляя более высокий приоритет некоторым пакетам (ключевые кадры видео) в
		зависимости от их содержимого.

		\subsubsection{P2P mesh-based system}

		CoolStreaming/DONet. DONet относится к классу систем, в которых узлы обмениваются информацией о доступном контенте и уже на её основе
		происходит построение связей между узлами. Во время трансляции видео-поток делится на пакеты, и узлы сообщают
		соседним узлам о доступных у них пакетах с помощью buffer maps. Для воспроизведения видео-потока в
		режиме реального времени необходимы только пакеты для текущего воспроизведения, поэтому в buffer maps передаётся
		информация только о тех пакетах, в которых есть данные для текущего момента воспроизведения, или более новые,
		для последующего воспроизведения. Размер буфера напрямую влияет на задержку воспроизведения контента на узле по
		сравнению с источником. В DONet допускаются задержки до одной минуты, что означает большой размер буфера.
		Buffer maps представляет битовый список, где каждый бит означает наличие того или иного пакета, и идентификатор
		первого пакета, предназначенного для синхронизации с другими узлами. Обмен пакетами и buffer maps может
		происходить в обе стороны, поэтому в такой оверлейной сети нету родительских отношений, в все узлы являются
		соседями друг друга.

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

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

		Prime. В системе Prime \cite{4803721} узлы устанавливают соединения между собой случайным образом, образуя mesh-сеть. Отношение
		входящих и исходящих соединений на каждом из узлов определяется динамически, в зависимости от пропускной
		способности каждого узла. Вся передача данных в системе разделена на два этапа: diffusion и
		swarming.

		Общую схему оверлейной сети в системе Prime можно увидеть на рисунке \ref{img:prime-overlay}.

		\begin{figure}[H]
			\center{\includegraphics[width=0.8\linewidth]{prime-overlay.png}}
			\caption{Схема оверлейной сети в системе Prime}
			\label{img:prime-overlay}
		\end{figure}

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

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

		\subsubsection{Hybrid system}

		mTreebone. В системе mTreebone \cite{4268203} в построении дерева принимают участие только стабильные узлы, которые уже присутствуют в
		сети определённое время, а все новые узлы считаются нестабильными и могут быть только листьями дерева. Для
		повышения эффективности передачи данных в системе по сравнению с системами с одним деревом, в дополнении к
		основному дереву в mTreebone строится оверлейная mesh-сеть между узлами, которая помагает в построении дерева и
		его восстановлении и в передаче пакетов данных. Так как при построении дерева учитываются только стабильные узлы,
		то накладные расходы на поддержание сбалансированного дерева находятся в допустимых границах.

		На рисунке \ref{img:mtreebone-overlay} показан пример построения оверлейной сети в mTreebone.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{mtreebone-overlay.png}}
			\caption{Схема оверлейной сети в системе mTreebone. (a) Оверленая сеть, (b) Перестроение сети после
			выхода из неё узлов}
			\label{img:mtreebone-overlay}
		\end{figure}

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

		Для снижения задержек при передачи данных между узлами необходимо поддерживать дерево в сбалансированном виде и
		как можно короче. Для этого в mTreebone используется два алгоритма:
		\begin{itemize}
			\item если у узла больше потомков, чем у его родительского узла, то этот узел передвигается выше по дереву и
			его родительский узел становится его потомком;
			\item узел будет всегда стараться минимизировать расстояние между ним и источником, если позволяет
			пропускная способность родительского узла.
		\end{itemize}

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

		BitTorrent Live. BitTorrent Live \cite{6934295} является одной из немногих систем, реализации которых в виде конечных продуктов доступны
		пользователям. Первая реализация системы была представленна в 2013 году. В основе системы лежит несколько разных
		механизмов, которые используются одновременно. На рисунке \ref{img:btlive-overlay} показан пример оверлейной
		сети. Весь процесс передачи данных трансляции можно разделить на три этапа: передача частей видео-потока от
		источника до клубов (clubs), передача данных между участниками клуба и обмен данными с участниками
		других клубов.

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

		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{btlive-overlay.png}}
			\caption{Схема оверлейной сети в системе BitTorrent Live}
			\label{img:btlive-overlay}
		\end{figure}

		\newpage
		\subsubsection{Результаты сравнения}
		После изучения вышеперечисленных систем была составлена итоговая таблица \ref{tbl:comparison-p2p-model} с
		оценкой каждой системы по четырём ключевым характеристикам.

		\input{table/comparison-p2p-system.tex}

	\subsection{Определение требований}
	Требования к P2P-системам для организации видео-трансляций в режиме реального времени можно разделить на две
	категории. Пользовательские требования - это те требования, которые относятся к конкретному виду приложения.
	Системные требования являются более обобщёнными и могут применяться к более широкому кругу систем.

	К пользовательским требованиям можно отнести следующие пункты:
	\begin{itemize}
		\item низкая задержка при старте --- пользователь желает начать просмотр как можно быстрее и в случае
		длительной задержки может выйти из системы;
		\item непрерывное воспроизведение трансляции --- если трансляция уже началась, то частые прерывания могут
		спровоцировать закончить просмотр;
		\item наилучшее качество трансляции --- пользователь хочет смотреть трансляцию наилучшего качества, которое
		только доступно;
		\item умеренное потребление ресурсов --- приложение должно потреблять только необходимое колическтво
		ресурсов (процессорное время, пропускная способность канала, заряд аккумулятора).
	\end{itemize}

	К системным требованиям относятся следующие пункты:
	\begin{itemize}
		\item анализ передаваемых данных --- протокол должен понимать формат передаваемых им данных для возможности
		применения необходимых эвристик;
		\item низкие накладные расходы --- небольшой объём вспомогательных данных по отношению к трафику
		видео-трансляции;
		\item высокая пропускная способность системы;
		\item низкая задержка при передаче данных от источника до пользователей;
		\item надёжная доставка данных между узлами;
		\item устойчивость к частым подключениям и отключениям узлов в сети;
		\item масштабируемость.
	\end{itemize}

	\subsection{Выводы по главе}

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

	Одной из самых известных P2P-технологий кооперативного обмена данными через Интернет является протокол
	BitTorrent. Уже на протяжении 16 лет пользователи активно используют системы на базе этого протокола для
	передачи данных между собой, исключая из цепочки передачи централизованные узлы. По данным на начало 2013 года,
	трафик для передачи данных с использованием протокола BitTorrent составляет 3,35\% от общего мирового трафика
	Интренета. BitTorrent хорошо справляется с задачей обмена файлами, но для эффективной передачи данных
	видео-трансляции в режиме реального времени в том виде, в котором его используют, он не подходит. Поэтому в 2011
	году был представленн стандарт RFC 7574 Peer-to-Peer Streaming Peer Protocol (PPSPP) \cite{rfc7574} , в котором описывается
	протокол передачи данных, в основе которого лежат идеи из BitTorrent, но доработанный с учётом специфики передачи
	видео-контента. Именно этот стандарт и был взят за основу разработанной системы.

\section{Проектирование P2P-системы для организации видеотрансляций}
	Если проанализировать современные системы, то можно увидеть, что для достижения высоких показателей
	производительности и масштабируемости инженеры разрабатывают сложные инфраструктуры, состоящие из множества
	узлов разных типов. Одни узлы предназначены для поддержания работы кластеров СУБД, обеспечивающих хранение данных,
	вторые - для кеширования данных, третьи - для балансировки запросов от пользователей и так далее. В результате
	поддержка современных клиент-серверные систем требует много ресурсов, и это стало целой областью задач.

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

	Сам тип P2P-систем уже несёт в себе информацию о том, что роли у узлов одинаковы и между всеми узлами может
	устанавливаться соединение и происходить обмен данными. Основными положениями в описании той или иной P2P-системы
	являются:
	\begin{itemize}
		\item используемая модель для построения оверлейной сети;
		\item виды используемых сообщений для обмена данными;
		\item алгоритм для планирования последовательности пересылки данных;
		\item модель обмена данными между узлами.
	\end{itemize}

	\subsection{P2P-протокол для передачи потокового контента}
	Протокол Peer-to-Peer Streaming Peer Protocol (PPSPP) предназначен для потокового распространения контента среди
	заинтересованных лиц. PPSPP поддерживает потоковую передачу как записанного контента, так и трансляций в режиме
	реального времени. Протокол базируется на идеи пиринговой сети, когда узлы при получении контента сами становятся
	источником контента для других узлов, таким образом предоставляя свои ресурсы в распоряжение других участников. Он
	был спроектирован с учётом поддержки различных механизмов для оптимизации передачи данных между узлами, а так же
	имеет возможность работы с двумя различными схемами обнаружения узлов в сети (централизованный трекер и
	распределённые хеш-таблицы). Все способы оптимизаций, применяемые в протоколе, направлены на снижение задержки перед
	началом просмотра трансляции, а также на достижение непрерывного воспроизведения.

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

		\subsubsection{Каналы}
		В протоколе PPSPP используется понятие каналов для возможности узлу одновременно участвовать в нескольких
		трансляциях, но в тоже время использовать один адрес на транспортном уровне. На рис. \ref{img:ppspp-chanels}
		показан пример использования каналов, когда узел имеет лишь один транспортный адрес, а с помощью каналов
		происходит мультиплексинг входящих сообщений. При установке соединения узел A генерирует свой идентификатор
		канала (channel id), который будет в дальнейшем использоваться во время пересылки последующих сообщений. В ответ
		на запрос узла A узел B генерирует свой идентификатор канала, и эта пара идентификаторов в дальнейшем и будет
		обозначать канал между ними.

		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-chanels.png}}
			\caption{Пример использования каналов}
			\label{img:ppspp-chanels}
		\end{figure}

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

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

		HANDSHAKE. Для установки соединения новым узлом A с узлом B, который уже принимает участие в обмене,
		первым посылается сообщение типа HANDSHAKE. Предполагается, что узел A уже получил необходимую метаинформацию о
		трансляции, которая включает:
		\begin{itemize}
			\item идентификатор трансляции;
			\item размер сегмента данных;
			\item метод адресации сегментов;
			\item метод проверки целостности контента.
		\end{itemize}

		Формат сообщения представлен на рис. \ref{img:ppspp-message-handshake}.

		\begin{figure}[H]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-handshake.png}}
			\caption{Формат сообщения HANDSHAKE}
			\label{img:ppspp-message-handshake}
		\end{figure}

		Destination Channel ID - это channel id узла, с которым устанавливается соединение.
			В случае, если это сообщение является инициирующим, то значение равно 0. Если сообщение
			отправляется в ответ на запрос, то поле заполняется идентификатором, которвый пришёл в запросе.

		Source Channel ID - локальный channel id, сгенерированный самим узлом.

		Protocol Options - список настроек протокола.

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

		Формат сообщения представлен на рис. \ref{img:ppspp-message-have}.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-have.png}}
			\caption{Формат сообщения HAVE}
			\label{img:ppspp-message-have}
		\end{figure}

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

		Формат сообщения представлен на рис. \ref{img:ppspp-message-data}.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-data.png}}
			\caption{Формат сообщения DATA}
			\label{img:ppspp-message-data}
		\end{figure}


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

		Формат сообщения представлен на рис. \ref{img:ppspp-message-ask}.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-ask.png}}
			\caption{Формат сообщения ASK}
			\label{img:ppspp-message-ask}
		\end{figure}


		SIGNED\_INTEGRITY. Сообщения этого типа используются для верификации получаемых сегментов трансляции.

		Формат сообщения представлен на рис. \ref{img:ppspp-message-signed-integrity}.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-signed-integrity.png}}
			\caption{Формат сообщения SIGNED\_INTEGRITY}
			\label{img:ppspp-message-signed-integrity}
		\end{figure}

   		REQUEST. Сообщения этого типа используются для запроса у других узлов конкретных сегментов трансляции.
   		Это требуется при pull-based подходе, когда узлы отправляют сегменты только после запроса, но так же и при
   		push-based подходе, когда по разным причинам до узла не дошёл нужный ему сегмент.

   		Формат сообщения представлен на рис. \ref{img:ppspp-message-request}.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-request.png}}
			\caption{Формат сообщения REQUEST}
			\label{img:ppspp-message-request}
		\end{figure}

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

   		Формат сообщения представлен на рис. \ref{img:ppspp-message-cancel}.
		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-message-cancel.png}}
			\caption{Формат сообщения CANCEL}
			\label{img:ppspp-message-cancel}
		\end{figure}


   		CHOKE и UNCHOKE. В случае, если узел A больше не желает обрабатывать запросы от узла B, то он
   		посылает сообщение CHOKE, тем самым сообщая узлу B, что тот не должен посылать запросы узлу A. Если узел A готов
   		снова обрабатывать запросы от узла B, то он посылает сообщение UNCHOKE, и после этого узел B может вновь
   		отправлять запросы узлу A.

		% 4. Chunk Addressing Schemes (p.21)
		\subsubsection{Метод адресации сегментов}
		При передаче контента трансляции от источника к другим участникам поток данных делиться на сегменты, которые
		являются неделимой единицей информации при передаче между узлами. Для возможности идентифицировать разные
		сегменты при указании диапазона необходимо определённое соглашение об адресации, которого будут придерживаться
		все узлы, принимающие участие в одной трансляции. В спецификации описанно два способа идентификации сегментов.

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

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

		% 5. Content Integrity Protection (p.24) & 6. Live Streaming (p.32)
		\subsubsection{Метод проверки целостности контента}
		Для проверки целостности сегментов на стороне получателя для трансляций в режиме реального времени используется
		схожий метод, что и в случае с распространением записанного контента, но с учётом особенностей контента. Для
		статического контента используется древовидное хеширование (Merkle tree), когда есть корневой хеш, и на его
		основе рекурсивно расчитывается хеш для всех сегментов контента. В случае с динамически-генерируемым контентом
		такой метод не подходит, так как невозможно расчитать постоянный корневой хеш контента. В качестве решения
		используется подписание источником новых сегментов своим приватным ключом, а получатель верифицирует полученные
		сегменты с помощью публичного ключа, которым является идентификатор трансляции.

		% 7. Protocol Options
		\subsubsection{Конфигурация протокола}
		При установки соединения между узлами в первом сообщении типа HANDSHAKE передаются настройки протокола, в
		соответствии с которыми в дальнейшем узлы будут взаимодействовать. Каждая настройка кодируется с помощью пары
		8-ми битных чисел, первое из которых означает код настройки, а второе - значение. В конце последовательности
		обязательно указывается код завершения списка настроек, формат которого указан на рис.
		\ref{img:ppspp-end-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.3\linewidth]{ppspp-end-option.png}}
			\caption{Формат завершающей последовательности списка настроек}
			\label{img:ppspp-end-option}
		\end{figure}

		Версия. Последняя версия протокола, которую поддерживает узел. Всегда указывается первой в списке
		настроек. Формат кодирования представлен на рис. \ref{img:ppspp-version-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.5\linewidth]{ppspp-version-option.png}}
			\caption{Формат кодирования версии протокола}
			\label{img:ppspp-version-option}
		\end{figure}

		\newpage
		Минимальная версия. Минимальная поддерживаемая версия протокола. Формат кодирования представлен на рис.
		 \ref{img:ppspp-min-version-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.5\linewidth]{ppspp-min-version-option.png}}
			\caption{Формат кодирования минимальной версии протокола}
			\label{img:ppspp-min-version-option}
		\end{figure}

		Идентификатор трансляции. При установке соединения со стороны инициирующего обязательно указывается
		идентификатор транслсяции. В обратном случае идентификатор может быть указан для проверки на другой стороне
		соединения. Формат кодирования представлен на рис. \ref{img:ppspp-swarm-id-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-swarm-id-option.png}}
			\caption{Формат кодирования идентификатора трансляции}
			\label{img:ppspp-swarm-id-option}
		\end{figure}

		Метод проверки целостности. Указания метода проверки целостности контента, который использую узлы при
		получении сегментов трансляции. Для трансляций в режиме реального времени используется метод
		"Unified Merkle Tree". Формат кодирования представлен на рис. \ref{img:ppspp-cimp-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.5\linewidth]{ppspp-cimp-option.png}}
			\caption{Формат кодирования метода проверки целстности}
			\label{img:ppspp-cimp-option}
		\end{figure}

		Алгоритм генерации ключей. Алгоритм для генерации ключей, используемых для проверки целостности
		контента при трансляции в режиме реального времени. Список доступных алгоритмов описан в
		"Domain Name System Security (DNSSEC) Algorithm Numbers": RSASHA1, RSASHA256, ECDSAP256SHA256 и
		ECDSAP384SHA384. Формат кодирования представлен на рис. \ref{img:ppspp-lsa-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.5\linewidth]{ppspp-lsa-option.png}}
			\caption{Формат кодирования алгоритма для генерации ключей}
			\label{img:ppspp-lsa-option}
		\end{figure}

		Метод адресации сегментов. В качестве методов адресации могут выступать следующие значения:
		\begin{itemize}
			\item 64-bit byte ranges;
			\item 32-bit chunk ranges;
			\item 64-bit chunk ranges.
		\end{itemize}
		Формат кодирования представлен на рис. \ref{img:ppspp-cam-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.5\linewidth]{ppspp-cam-option.png}}
			\caption{Формат кодирования метода адресации сегмента}
			\label{img:ppspp-cam-option}
		\end{figure}

		Размер сегмента. При инициализации соединения участники должны обязательно согласовать размер сегментов,
		на которые делится текущая трансляция. Формат кодирования представлен на рис. \ref{img:ppspp-chunk-size-option}.

		\begin{figure}[h]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-chunk-size-option.png}}
			\caption{Формат кодирования размера сегмента}
			\label{img:ppspp-chunk-size-option}
		\end{figure}

	\subsection{Структура системы}
		\subsubsection{Архитектура системы}
			Архитектура большинства P2P-систем имеет схожее строение, которая заключается в множестве равноправных между
			собой узлов, взаимодействующих друг с другом. В современных P2P-системах, как правило, имеется центральные
			узлы, которые позволяют новым участникам находить уже существующие узлы в сети. В дополнению к
			централизованному способу обнаружения действующих участников также может использловаться DHT и протокол PEX.

			Основные виды узлов в разрабатываемой системе представленны на рис. \ref{img:system-architecture}.

			\begin{figure}[h]
				\center{\includegraphics[width=0.8\linewidth]{system-architecture.png}}
				\caption{Архитектура системы}
				\label{img:system-architecture}
			\end{figure}

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

			В качестве протокола общения между трекером и узлами в сети был разработан стандарт Peer-to-Peer Streaming
			Tracker Protocol (PPSTP), в котором указано, что взаимодействие с трекером происходит с использованием
			протокола HTTP, а так же описан формат данных, с использованием которого происходит обмен данными.

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

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

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

		\subsubsection{Архитектура мобильного приложения}
			В качестве программного обеспечения, предоставляющего возможность как ведения трансляции, так и их просмотр,
			выступает мобильное приложение для платформы iOS. Всё приложение можно разделить на подмодули, каждый из
			которых выполняет отведённые ему задачи.

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

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

			Модуль PPSPP. Данный модуль отвечает за реализацию протокола Peer-to-Peer Streaming Peer Protocol.
			В его задачи входит передача получаемых сегментов трансляции от модуля захвата изображения заинтересованным
			узлам в сети, получение необходимых сегментов для воспроизведения трансляции и передача их модулю
			воспроизведения, а так же построение оверлейной сети вокруг узла.

			Сетевой модуль. Задачей этого модуля является предоставление абстаркции над стеком TCP/IP модулю
			PPSPP. В его задачи входит передача датаграмма по протоколу UDP и установка связи между узлами, которые
			находятся за NAT.

	\subsection{Алгоритм работы системы}
		Любая сложная система характеризуется как статическими параметрами, так и процессами, протекающими в системе.
		В системах, предназначенных для решения схожих задач, обычно можно выделить ряд общих процессов, которые
		протекают во всех системах этого тип. Так, в P2P-системах можно выделить следующие процессы.

		\subsubsection{Алгоритм обмена данными}
		В разработанной системе в качестве механизма для распространения сегментов трансляции используется pull-подход,
		алгоритм работы которого изображён на рис. \ref{img:pull-based-data-flow}.

		\begin{figure}[H]
			\center{\includegraphics[width=0.7\linewidth]{pull-based-data-flow.png}}
			\caption{Алгоритм передачи данных в pull-based P2P-системах}
			\label{img:pull-based-data-flow}
		\end{figure}

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

		На рисунке \ref{img:message-flow} представленна диаграмма обмена сообщениями между узлами в сети в
		соответствии со спецификацией протокола PPSPP.

		\begin{figure}[H]
			\center{\includegraphics[width=0.85\linewidth]{message-flow.png}}
			\caption{Диаграмма обмена сообщениями в соответствии с протоколом PPSPP}
			\label{img:message-flow}
		\end{figure}

		Представим, что участник Peer A хочет начать трансляцию, которую смогут смотреть другие участники.
		Для этого он должен отправить сообщение CONNECT трекеру для регистрации своей трансляции.

		После получения корректного сообщения на регистрацию, трекер отвечает участнику Peer A сообщением OK.

		Всё то время, пока Peer A ведёт трансляцию, он должен регулярно отправлять сообщения
		STAT\_REPORT трекеру. Рекомендуемый интервал времени составляет 3 минут и задаётся параметром
		Track\_timeout. В случае успешного приёма сообщения, трекер должен ответить сообщением OK.

		Предположим, что участник Peer B хочет присоеденится к просмотру трансляции, организованной участником
		Peer A. Для этого ему необходимо запросить у трекера список доступных трансляций и на основе
		полученного списка запросить необходимые сведения о выбранной трансляции - идентификатор трансляции
		(swarm\_id).

		Затем участник Peer B посылает трекеру сообщение CONNECT для попытки присоединения к выбранной
		трансляции. В ответ трекер посылает участнику Peer B сообщение OK со списком IP-адресов
		участников, которые уже участвуют в трансляции (на данный момент это только участник Peer A).

		Участник Peer B понимает, что в трансляции уже участвует Peer A, и посылает ему сообщение
		HANDSHAKE. В теле сообщения указываются channel ID и список параметров протокола.

		Участник Peer A определяет, может ли он начать коммуницировать с Peer B на основе текущих
		показателей сетевого соединения. В случае, если Peer A может начать взаимодействовать с Peer B,
		он посылает в ответ датаграмму с сообщениями HANDSHAKE и HAVE.

		После получения подтверждения от Peer A, участник Peer B может обновить список участников,
		участвующих в трансляции, отправив сообщение PEX\_REQ для обнаружения других участников, информацию о
		которых он не получил от трекера.

		Участник Peer A в ответ на запрос отвечает сообщением PEX\_RES, в котором указаны адреса
		участников Peer C и Peer D.

		Если Peer B потребуется взаимодействие с одним из этих участников, то первым сообщением должно быть
		HANDSHAKE.

		Как и в случае с Peer A, участники Peer C и Peer D должны решить, могут ли они
		взаимодействовать с Peer A. Предположим, что Peer C может общаться с Peer B, а
		Peer D - нет. В таком случае, Peer C посылает в ответ на запрос сообщения HANDSHAKE и
		HAVE, а Peer D - HANDSHAKE, HAVE и CHOKE.

		После получения ответов на запросы, Peer B определяет, какие участники доступны для взаимодействия.
		На основе этой информации он рассылает сообщения REQUEST участникам Peer A и Peer C
		для получения недостающих частей данных трансляции (chanks).

		После получения запроса от Peer B, Peer A и Peer C должны ответить сообщениями
		SIGNED\_INTEGRITY и DATA, в которых содержится запрашиваемые части трансляции и метаинформация
		для проверки корректности этих частей.

		В ответ на полученные сообщения, Peer B должен подтвердить получения данных с помощью сообщения
		ACK. Так же ему необходимо разослать сообщения HAVE всем другим известным ему участникам
		трансляции с целью оповещения о наличии у него новых частей контента.

		Участник Peer B получает от Peer D сообщение UNCHOKE, которое означает, что
		Peer D готов взаимодействовать с Peer B.

		Затем Peer B посылает сообщение REQUEST Peer D c целью получить недостающие части
		трансляции. В ответ Peer D присылает запрашиваемые части. После проверки целостности полученных данных,
		Peer B может разослать сообщения HAVE с целью оповещения о наличии у него новых частей
		контента.

		Peer C и Peer D могут также запрашивать части контента у Peer B с помощью сообщений
		REQUEST.

		В случае, если Peer B хочет покинуть трансляцию, то он может закрыть все текущие соединения с помощью
		отправки сообщения HANDSHAKE каждому из них, в котором в качестве значения chanel id будут
		указаны 0. Так же ему следует отправить сообщение трекеру, сигнализирующее о выходе из списка участников
		трансляции.

		\subsubsection{Алгоритм построения оверлейной сети}
		Одной из главных задач, решаемых в рамках P2P-сетей, является задача организации взаимодействия между узлами.
		При установлении связей между узлами формируется топология сети, которая во многом влияет на скорость и задержки
		передачи данных по сети.

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

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

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

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

		Tracker. Tracker является единственным централизованным узлом в системе, к которому обращаются новые
		узлы, которые хотя присоединиться к трансляции. Его основная задача заключается в предоставлении актуального
		списка текущих участников для каждой из трансляций. При старте трансляции в качестве единственного узла
		выступает сам ведущий трансляции. В качестве протокола взаимодействия с трекером используется стандарт
		Peer-to-Peer Streaming Tracker Protocol (PPSTP). Главное преимущество использование трекера --- быстрое
		получения списка участников трансляции, что позволит зрителю быстрее начать просмотр.

		DHT. Распределённая хеш-таблица представляет децентрализованную распределённую систему для объединения
		большого количества постоянно исчезающих и появляющихся узлов и эффективной передачи сообщений между ними.
		Данный вид систем используется в P2P-системах для обнаружения новых узлов, участвующих в передаче данных, в сети.
		Использование такой системы позволит помочь зрителям быстрее найти друг друга, снизить нагрузку на трекер и
		поддержать трансляции в периоды недоступности трекера.

		PEX. Peer exchange представляет из себя gossip-протокол, в котором уже соединённые пиры просто
		обмениваются адресами тех, к кому они уже присоединены. Является эффективным средством для поддержания списков
		участников в сети в узлах в актуальном состоянии.

		\subsubsection{Управление нагрузкой в сети}
		В соответствии со спецификацией протокола PPSPP в нём в качестве транспортного протокола используется UDP.
		В отличии от TCP, в данном протоколе отстутствует ряд гарантий, одной из которых является контроль за
		перегрузкой в сети. По этому в ряде случаев при использовании только UDP могут возникнуть ситуации, когда
		отправитель шлёт больше данных, чем получатель может обработать. Для избежания таких ситуаций
		необходимо иметь возможность контролировать загруженность в сети и динамически подстраиваться под текущие
		условия.

		В качестве такого алгоритма управления нагрузкой в сети в PPSPP предложенно использовать LEDBAT \cite{rfc6817}. Этот алгоритм
		использует время прохождения пакетов от источника до получателя в качестве метрики для определения загруженности
		канала между узлами, что позволяет на раннем этапе предсказать задержки при получении данных со стороны
		получателя для того, что бы он смог успеть запросить сегменты трансляции у других узлов в сети.

\section{Реализация P2P-системы для организации видеотрансляций}
	В разрабатываемой P2P-системе существует два основных типа узлов: трекер и мобильное приложение для пользователей.
	Соответственно для каждого из типов необходимо разработать своё программное обеспечение.

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

		\subsection{Модуль захвата изображения и воспроизведения}

			\subsubsection{Фреймворк Video Toolbox}
			По умолчанию, в SDK для платформы Apple iOS уже существует реализация плеера для воспроизведения популярных
			форматов видео. Так же SDK имеет ряд инструментов для работы с протоколом HTTP Live Streaming (HLS) \cite{8945984}, который
			позволяет передавать небольшие сегменты H.264/AAC видео, упакованые в контейнер формата MPEG-TS, и плейлист,
			что позволяет клиентским приложениям динамически переключаться между разными версиями контента в зависимости
			от доступных ресурсов.

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

			В случаях, когда же необходима поддержка видео-контейнеров других форматов, например MKV, или поддержка
			адаптивных протоколов передачи данных, таких как DASH or Smooth Streaming, то необходимо использовать
			фреймворк более низкого уровня VideoToolbox. Он принимает несжатый видеопоток на входе и позволяет
			перекодировать его в несжатый видеопоток другого формата или закодировать с использованием указанного кодека.

			Video Toolbox представляет API, базируюшийся на трёх фреймворках CoreMedia, CoreVideo, и CoreFoundation,
			ключевым элементом которого является сессия, которая одновременно может отвечать только или за кодирование,
			или за декодирование. Для управления фреймами и временем воспроизведения используются объекты из фреймворков
			CoreMedia и CoreVideo, такие как CMTime или CVPixelBuffer.

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

			Процесс воспроизведения видео в приложении зрителя выглядит следующим образом (рис.
			\ref{img:play-video-frames}). Фреймворк AVFoundation предоставляет объект
			AVSampleBufferDisplayLayer, на вход которому подаются видео-фреймы в формате H.264
			(CMSampleBuffer), полученные по сети. Для декодирования видео необходимо указать параметры
			входящего потока, которые регулярно передаются источником контента. После декодирования данные видеопотока
			хранятся в объектах CMPixelBuffer в несжатом виде, готовом к воспроизведению.

			\begin{figure}[h]
				\center{\includegraphics[width=0.8\linewidth]{play-video-frames.png}}
				\caption{Схема воспроизведения видеопотока}
				\label{img:play-video-frames}
			\end{figure}

			\subsubsection{Потоки в формате H.264}
			Для передачи данных, сжатых с помощью кодека H.264, был разработан специальный стандарт. В нём определяется
			такой тип данных, как NALU (Network Abstraction Layer Unit), из объектов которых состоит закодированный
			видеопоток. Существует два типа NALU: VCL и non-VCL. NALU типа VCL содержат в себе непосредственно данные
			видеопотока, а non-VCL --- метаинформацию о потоке. Последовательность NALU образует H.264-поток
			(рис. \ref{img:h264-stream}), который может быть двух разных форматов: AVCC (MPEG-4) и Annex B (Elementary
			Stream).

			\begin{figure}[H]
				\center{\includegraphics[width=0.8\linewidth]{h264-stream.png}}
				\caption{Пример H.264-потока}
				\label{img:h264-stream}
			\end{figure}

			Главное различие между форматами заключается в том, каким образом NALU в потоке разделяются между
			собой: в потоке формата AVCC в начале каждого NALU указана 4-х байтный заголовок с размером элемента, тогда
			как в NALU формата Annex B в заголовке указывается стартовый код 0x000001 или 0X0000001.

			\subsubsection{Конвертация между форматами H.264-потока}
			Так как фреймворк Apple работает с H.264-потоком в формате AVCC (MPEG-4), а передача данных по сети
			происходит в формате Annex B (Elementary Stream), то встаёт задача по преобразованию данных между этими
			форматами на стороне ведущего трансляции и на стороне зрителя.

			MPEG-4 $\rightarrow$ Elementary Stream. После получении данных потока с камеры устройства и их сжатия
			видео-фреймы храняться в объектах
			%\texttt{CMSampleBuffer}
			, который содержит текущее время (CMTime),
			описание формата закодированного видео (CMVideoFormatDescription) и сами данные потока
			%(\texttt{CMBlockBuffer})
			. Фреймы потока могут быть представленны тремя разными видами: I-, B-, или P-фреймы.
			Для передачи параметров формата данных используются NALU двух типов: PPS (Picture Parameter Set) и SPS
			(Sequence Parameter Set).

			Elementary Stream $\rightarrow$ MPEG-4. При получении данных трансляции на стороне зрителя для их отображения
			необходимо преобразовать полученные NALU из формата Elementary Stream в MPEG-4 для их дальнейшего
			воспроизведения. На рис. \ref{img:annex-b-to-avcc-stream} показан процесс этого преобразования.

			\begin{figure}[h]
				\center{\includegraphics[width=0.6\linewidth]{annex-b-to-avcc-stream.png}}
				\caption{Преобразование потока Elementary Stream в MPEG-4}
				\label{img:annex-b-to-avcc-stream}
			\end{figure}

			\subsubsection{Пользовательский интерфейс приложения}
			На данный момент в системе реализована возможность ведения только одной трансляции одновременно. Основной
			интерфейс мобильного приложения для ведущего и зрителя показан на рис. \ref{img:interface}. На нём
			представлен интерфейс для двух состояний: трансляция запущена (первое изображение) и трансляция
			приостановлена (второе изображение). Для зрителя интерфейс представлен на третем изображении.

			\begin{figure}[h]
				\center{\includegraphics[width=0.8\linewidth]{interface.png}}
				\caption{Интерфейс приложения}
				\label{img:interface}
			\end{figure}

		\subsection{Модуль PPSPP}
		После того, как сегменты трансляции были закодированы на устройстве ведущего, их необходимо дальше
		распространять по сети. Аналогичная задача стоит и перед зрителями: одновременно с просмотром трансляции
		передавать сегменты другим узлам. Описанные выше задачи решаются в модуле PPSPP, схема которго изображена на
		рис. \ref{img:ppspp-architecture}.

		\begin{figure}[H]
			\center{\includegraphics[width=0.8\linewidth]{ppspp-architecture.png}}
			\caption{Устройство модуля PPSPP}
			\label{img:ppspp-architecture}
		\end{figure}

		Для реализации данного модуля был выбран язык C с целью переиспользования
		разработанного модуля в приложениях на других платформах. На устройстве каждого из пользователей в системе
		существует буфер с сегментами (Data Buffer), необходимы для их передачи другим узлам в сети. Главное
		отличие между зрителем и ведущим заключается в том, что у зрителя данный буфер наполняется данными из сети,
		тогда как у ведущего - данными с камеры. При сохранении в буфере нового сегмента на устройстве зрителя
		выполняется две задачи: воспроизведение сегмента на устройстве и рассылка уведомлений соседним узлам о новом
		сегменте. Подсистема Scheduling отвечает за определение порядка запросов новых сегментов у других узлов
		для поддержания непрерывной трансляции.

		\subsection{Сетевой модуль}
		Главной задачей сетевого модуля в приложении является сокрытие деталей передачи данных между пользователями для
		модуля PPSPP. Одна из главных проблем, с которой сталкиваются при разработке приложений с использованием
		пиринговых сетей, это установка соединения между пользователями, которые находятся за NAT. Существует несколько
		способов решения данной проблемы, которые в совокупности решают данную проблему для большинства пользователей.

		Протокол Interactive Connectivity Establishment (ICE) позволяет двум участникам, находящимся за NAT, установить
		соединение между собой. В его работе используются такие механизмы, как STUN (Simple Traversal of UDP
		through NATs) и TURN (Traversal Using Relay NAT).

		STUN предлагает пользователю определить параметры своего соединения (IP-адрес, порт, тип NAT), используя которые
		другой пользователь сможет установить соединение с этим узлом.

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

\section*{Заключение}
\addcontentsline{toc}{section}{Заключение}
	В настоящее время применение P2P-подхода к решению задач обмена видеоконтентом в режиме реального времени ещё не
	получило широкого применения, но решение этой задачи с помощью этого подхода позволит в будущем получать
	пользователям более высокий уровень качества оказываемых им услуг, а компаниям снизить количество используемых
	ресурсов на поддержание инфраструктуры.

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

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

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

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

	Исходный код приложения: https://github.com/pshishkanov/watch-stream-app.

% Список литературы
\bibliographystyle{bibliography/utf8gost705u}
\bibliography{bibliography/biblio}