Анализ динамики и использования ресурсов для обмена файлами в P2P-сетях по пространственно-временной модели

Анализ динамики и использования ресурсов для обмена файлами в P2P-сетях по пространственно-временной модели

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

Введение

Приложения peer-to-peer (P2P), такие как обмен файлами, в последнее время стали занимать значимое место в области интернет-коммуникаций. Более поздние версии таких приложений это: Gnutella, Napster и Kazaa, в то время как BitTorrent в настоящее время самые популярные системы. Системы P2P используют большую часть трафика в Интернете. С точки зрения оператора важно, чтобы транспортная нагрузка производства P2P-приложений сильно не нагружала сеть. Эффективное использование ресурсов сети, также улучшит обслуживание отдельных пиров за счет сокращения среднего времени ожидания.

Мы делаем акцент на подобном BitTorrent протоколе P2P из-за его популярности, но результаты применимы и к другим протоколам. Идея протокола BitTorrent заключается в том, чтобы разбить файл на блоки так, чтобы разные части можно было скачать с нескольких пиров одновременно. Размер блока, как правило, составляет 256 Кб. Вы можете увидеть технические параметры BitTorrent в статье. Проведенные исследования в статьях [2], [3], [4], показали, что развитие одного файла в системе можно разделить на три этапа. На первом этапе увеличивается спрос на недавно появившийся файл. Далее следует устойчивое состояние и, наконец, гибель файла.

Было проанализировано несколько статей о P2P системах обмена файлами по стохастическим моделям. В работе [5], анализ BitTorrent представлен наподобие переходного и установившегося государственного режима. Мощность переходного режима изучается по ветвящимся процессам, а устойчивое состояние с помощью модели Маркова. В работе исследуется производительность системы детерминированной жидкостной модели, в то время как в статье задержки сетевого уровня смоделированы задержкой одного открытого класса сетей массового обслуживания и задержки равноправного уровня задержками M/G/1/K процессора обмена очередей. Однако эти модели не учитывают всех вышеупомянутых фаз из процесса обмена, а именно вспышка толпы, устойчивое состояние, и особенно конец фазы.

В этой работе мы изучаем динамику обмена блоками, то есть одной части из файла, в системе P2P. Сперва мы смоделируем детерминированную жидкостную модель и исследуем динамику среднего числа пользователей (downloader) и источников (seeds) в течение долгого времени. Детерминированные жидкостные модели, однако, неспособны охватить все детали процесса обмена блоками, такие как возможная неустойчивость и исчезновение из системы. По этой причине мы построим полную модель Цепи Маркова для получения большей информации о жизненном цикле процесса обмена блоками.

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

Статья организована следующим образом: В разделе 2 жидкостной моделью была изучена система демографической динамики. Затем в разделе 3 была построена модель Цепи Маркова для того, чтобы вычислить время к исчезновению. В разделе 4 вводится геометрический подход к моделированию обмена блоками и сравнивается различный выбор стратегии пиров. Наконец, в разделе 5 подведены итоги статьи.

Детерминированные жидкостные модели для обмена блоками В этом и следующих разделах мы проанализируем демографическую динамику обмена блоками одного файла. Мы исследуем, как изменяется количество пользователей и источников с момента появления блока до его исчезновения. При исчезновении одного блока прекращается доступ ко всему файлу, так как становится неполным. Работа мотивируется моделью из статьи [6], но имеет некоторые отличия. В работе проблема совместного использования нескольких блоков одновременно решены, предполагая, что пиры могут пересылать блоки с постоянной скоростью. Тем не менее, мы находим данное предположение нереалистичным и модель, вероятно, скрывает некоторые детали демографической динамики. По этой причине мы рассматриваем передачу по одному блоку. Кроме того, среди прочих, работы и полагают, что по крайней мере один источник оставляет блоки в системе. Однако исследования показывают, что в BitTorrent процесс обмена файлов умрет рано или поздно. Поэтому время жизни процесса также изучено.

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

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

(1)

где и. Пусть и — возможные равновесные значения и. Если, стационарное решение и. С учетом ограничения, получаем условие равновесия:. Если, то решением уравнений (1) является у = 0 и х > ?.

Рис. 1. Число загрузчиков на левой пользователей и количество источников на правой стороне, как функции времени (в единицах 1/мd). Сплошные линии: жидкостная модель (1), серые линии: моделирование., , .

Эволюция числа пользователей и источников изображена на рисунке.

1.Мы уменьшили значения и, чтобы лучше продемонстрировать динамику системы. Сплошная линия соответствует жидкостной модели (1) и серые линии соответствуют до 10 различным моделям. Мы видим, что в начале потенциал системы не достаточен для того, чтобы поступали запросы на блок. Это рассматривается как резкое увеличение числа пользователей. Однако, после этого некоторые пользователи изменили свой статус на источники и система стабилизировалась. В конце времени (t = 20) 4 моделируемых процесса из 10 умирает и количество скачивающих в этих процессах увеличивается без каких-либо ограничений.

Цепь Маркова, модель обмена блоками Детерминированная жидкостная модель, из предыдущего пункта, описывает поведение системы при обмене блоками. Тем не менее, из результатов моделирования, мы наблюдаем два результата в динамике популяций, которые не были захвачены жидкостной моделью. Во-первых, когда блоки стали доступны, не все источники могли служить загрузчиками, а во-вторых, если первоначальные источники покидают систему, кусок погибает, и весь процесс обмена файлами является безрезультатным, даже если. Ограниченное время жизни процесса совместного использования файлов влияет на производительность системы и должны быть проанализированы некоторые другие модели. Именно поэтому в этом пункте мы изучим эволюцию процесса более подробно на примере Цепи Маркова — модель с поглощением. Построим цепь Маркова с непрерывным временем, где состояние пары и матрица скорости перехода Q с элементами:

если (2)

Состояния, при у = 0 в цепи Маркова являются поглощающими. С тех пор мы не интересуемся процессом после ввода одного из поглощающих состояний, мы объединяем их в одно состояние: 0. Среднее время ожидания до поглощения может определяться следующим образом: пусть — среднее время до поглощения, когда система находится в состоянии i. Учитывая матрицу переходов Q, среднее время до поглощения определяется известной марковской рекурсией:

(3)

где и. Поглощение времени, начиная с начального состояния (0,1), т. е. время жизни системы, в зависимости от, показано в левой часть рисунка 2. Сплошная линия рассчитывается путем численного решения системы линейных уравнений (3) в усеченном пространстве 35 Ч 35 состояний. Точки получены путем моделирования соответствующей бесконечной системы, анализирующей результаты. На рисунке показано, что системное время жизни увеличивается по экспоненте, как функция ожидаемого количества источников в системе.

В одном случае предельное время поглощения может быть приближенным. Когда среднее время жизни и очень маленькое, система может быть представлена как модель M / M /? с частотой поступления л и скоростью г, с которой источник покидает систему. Среднее время поглощения равно средней продолжительности периода занятости в очереди М / M / ?:

(4)

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

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

Модель одновременного использования блока, основанная на его местоположении Наша следующая цель состоит в изучении возможного сокращения использования ресурсов сети на основе определения местоположения пира, а не случайный выбор источника. Мы анализируем местоположения одновременно используемого блока в упрощенной настройке, где в основной топологии сети отменены и заменены простые геометрические структуры. При таком подходе мы аналитически можем оценить емкость использования. Как и прежде, новые заявки на блок прибывают в систему со скоростью л, по пуассоновскому закону. Каждый новый запрос связан с пиром i, местоположение которого случайно выбрано на поверхности сферы, по равномерному распределению. Мы выбрали сферическую геометрию прежде всего потому, что она симметрична и не имеет никаких искусственных границ. Также это естественный выбор, если рассматривать глобальную сеть. Пусть R-радиус сферы и пусть расположение пиров i описано цилиндрическими координатами и. Легко проверить, что если и, где u и u' взяты из равномерного распределения U (0, 1), пиры равномерно расположены на сфере.

Пусть D (t) множество пользователей и S (t) — множество источников в момент времени t. Пусть параметр — это j-ый источник, выбранный i-ым пользователем. Для измерения расстояния между двумя пирами i и j мы используем кратчайший путь между пирами на поверхности сферы и обозначаем .

Количество потребляемых ресурсов основной сети, при загрузки блока, пропорционально расстоянию между пирами. Если пиры расположены далеко друг от друга, то при передаче блока обычно требуется больше ссылок, чем в случае двух соседних пиров. Пусть с (t) — общая мощность, необходимая для обмена блоками в момент времени t,, т. е. с (t) описывается суммой расстояний между пирами обмена блоками. Однако, когда мы рассматриваем оптимальное использования ресурсов, более интересной величиной является средняя мощность C загрузки блока за период времени, определяется она как, где n — количество блоков, переданных в течение этого периода.

Рассмотрим две различные категории пиров: случайный выбор пиров (RPS), где источник для загрузки выбирается случайным образом среди всех доступных и выбор ближайших пиров (NPS), где выбирается ближайший возможный пир.

Анализ использования мощности В RPS, каждый пользователь выбирает случайный источник. Расстояние до случайного источника не зависит от их количества. Если предположить, что среднее время загрузки одного блока, то ожидаемое потребление ресурсов сети за скачанный блок равно среднему расстоянию между двумя точками на сфере (предполагается единичная площадь):. В NPS, для загрузки выбран ближайший пир среди источников. Если на сфере с единичной площадью случайным образом выбрано N точек, расстояние до ближайшего соседа может быть легко определено по формуле:

(5)

которое очень точно приближенно к, с максимальной ошибкой 0,16% при n = 4. В момент времени t, N включает источников и самого пользователя. Следовательно,. Количество потребляемых ресурсов для NDP:

(6)

В общем, распределение стационарного состояния, , может быть рассчитано по модели Маркова, описанной в раздела 3. Из-за сложности модели, решение не может быть выражено в закрытой форме. Однако, в случае, когда скорость загрузки на сервере ограничена и в системе остается, по крайней мере, один пир, систему пользователей и источников можно рассмотреть как две последовательных очереди М/М/ ?, где частота поступления в первую и вторую очередь — л, скорость обслуживания — и соответственно. Известно, что при данных предположениях, стационарное распределение пользователей и источников следует из распределения Пуассона. Ожидаемое потребление ресурсов сети составляет:

(7)

Отметьте, что это аналитическое значение для использования мощности предполагает, что каждый раз, когда статус источника меняется, пользователи должны обновить свои пиры, и затем опять найти ближайший. Это, однако, не очень реалистично. По этой причине (7) может быть рассмотрено, как нижняя граница использования ресурсов. Наше моделирование, предполагает, что эта оценка недалека от более реалистичной схемы выбора пира.

Рис. 3. Среднее использование мощности представлено в виде функции от,. Серые треугольники: модель с RPS, черных треугольников: модель с NPS. Пунктирная линия: ожидаемое использование ресурсов для RPS и сплошные линии: ожидаемое использование ресурсов для NPS. Левый рисунок: система с ограниченной загрузкой. Правый рисунок: мощность сервиса, ограниченная и загрузкой и скоростью загрузки.

Результаты моделирования Далее, на численных примерами мы изучим, как выбранная модель влияет на использование мощности. Во-первых, на левой стороне рисунка 3 мы изучаем сценарий, объясненный в предыдущем подразделе, где на сервисе всегда ограничена скорость загрузки и, по крайней мере, один пир остается в системе. Использование мощности C показано в виде функции, с ожидаемым числом источников (моделирование запускается во время 0, и). Серые треугольники соответствуют модели с RPS, черные треугольники с NPS. Когда принимает маленькие значения, источники покидают систему вскоре после загрузки и пиры, которые хотят загрузить блок, должны запросить его из исходного источника. Расстояния от загрузчика до исходного источника, используя две различные модели, остаются прежними. При увеличении, также увеличивается число источников, и выбранная модель оказывает влияние на использование ресурсов. Мы можем видеть, что, например, для использование мощности для модели с NPS составляет только 23% использования мощности для модели с RPS. Результаты моделирования очень близки к аналитическим границам, особенно при .

Затем мы рассматриваем систему, в которой емкость сервиса ограничена и загрузкой и скоростью загрузки, и система умирает, если все источники покинули систему (модель представлена в Разделе 2). Когда новый пользователь прибывает, он ищет или случайный доступный (RPS) или ближайший доступный (NPS) источник для загрузки.

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

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

Заключение

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

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

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

1. B. Cohen, Incentives Build Robustness in BitTorrent, 2003,

2. http://www.bittorrent.com/bittorrentecon.pdf.

3. M. Izal, G. Uvroy-Keller, E.W. Biersack, P.A. Felber, A. Al Hamra, and L. Garces-Erice, Dissecting BitTorrent: Five Months in a Torrent’s Lifetime, PAM, 2004.

4. J.A. Pouwelse, P. Garbacki, D.H.J. Epema, H.J. Sips, The BitTorrent P2P File-sharing system: Measurements and analysis, IPTPS, 2005.

5. L. Massouli¶e and M. Vojnovi¶c, Coupon replication Systems, SIGMETRICS, 2005.

6. X. Yang, G. de Veciana, Service Capacity of Peer to Peer Networks, INFOCOM 2004.

7. D. Qiu, R. Srikant, Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks, SIGCOMM 2004.

8. K.K. Ramachandran, B. Sikdar, An Analytic Framework for Modeling Peer to Peer Networks, INFOCOM 2005.