ИСПОЛЬЗОВАНИЕ ЖИДКОСТНОЙ МОДЕЛИ ПРИ АНАЛИЗЕ ВРЕМЕНИ РАСПРОСТРАНЕНИЯ ФАЙЛА МЕЖДУ ПОЛЬЗОВАТЕЛЯМИ В ОДНОРАНГОВОЙ СЕТИ*

-

THE APPLICATION OF A FLUID-BASED MODEL FOR THE ANALYSIS OF THE

DISTRIBUTION TIME OF A FILE AMONG USERS IN PEER-TO-PEER NETWORK

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

Обмен файлами по принцPи2пPуявляется альтернативой классическому прпиунциклиент/сервер и позволяет усилить мощность раздачи принимающих узлов с целью улучшения качества про распространения файла [ 1 ].P2PВ-сети, как только пользователь получил порцию файла, он мож передать копию этой порции любому другому пол ь,зозвааитнелтеюресованному в передаваемом файле. Можно привести множество примеров сетей, работающих по Pп2рPи:нNцaиpпsуter [ 2 ], Gnutella [ 3 ], Freenet [ 4 ], Vuse [ 5 ] и т. д. МPн2оPги-сеети используют протокBолitTorrent [ 6 ]. Масштабируемость, присущая P2P-сети, позволяет распространять файлы большого размера нескольким тысячам пользователей. В такой сети не требуется высокая пропускная способность для раздающих се Пользователь с обычным компьютером и соединением может таким образом распространять ф большого размера другим пользователям, количество которых значительно больше, чем это может при классическом подходе клиент/сервер.

На сегодняшний день обмен файламP2иP шпиороко используется в сети Интернет. Имеется ряд вопросов, которые требуют тоат:венеобходимо количественно оценить качество обмена фаPй2лPа;ми по действительно ли подхоPд2P существенно превосходит подход клиент/сервер; насколько хорошо масштабируется P2P-сеть, когда число принимающих узлов резко возрастает и становитсяак огромным; влияет на общее время распространения файла взаимодействие пропускной способности разд серверов и пропускной способности раздачи и загрузки остальных пользователей. Вопро математического моделирования, измерения, имитационного моделированиPя2P-дселтяей посвящено большое количество работ, среди -1н2и]х и[7 другие.

В данной работе рассматриваются фундаментальные вPо2пPр-оссеыти, лежащие в основе механизма P2P-обмена. Представлено выражение для минимального времени необходимого для загрузки це копии файла всем пользователям, заинтересованном в этом файле. В выражении использу жидкостные переменные, т.к. для описPа2нPи-ясети используется жидкостная модель. При этом минимальное время выражается через основные парPам2Pет-среыти: размер фай,лачисло серверов, число принимающих узлов, пропускную способность загрузки и раздачи всех узлов, участвую файлообмене. Выражение для минимального времени применимо при произвольных пропускн способностях загрузки и раздачи. Для жидкостной м-осдеетлии фPо2рPмула для минимального времени имеет явный вид и может быть выписана в простой компактной форме. Постановка задачи п [ 13 ]. Полученный результат для минимального времени позволяет ответить на многие фундаментал вопросы, касающиесPя2P-сети.

Статья построена следующим образом. В разделе «Постановка задачи» дается описание за приводится основной результат работы и обсуждается вопрос применимости полученного результат разделе «Минимальное время распространения файла» предстчаивсллеенныные результаты в случае, когда узлы, заинтересованные в файле, имеют разную пропускную способность раздачи. В закл приведены основные выводы. Постановка задачи

Основной задачей обмена файлами поP2Pсяетвиляется задача определения оптималоьносгпособа распространения файла пользователям или пирамpe(eаrн)глв. этой сети. Согласно прPи2нPцфипайул по сети распространяется частями или порциями. Все пиры делятся sнeаed)сидиов ли(чаенрглов. (англ. leecher). Каждый личер заинтересован ввансикиачиопределенного файла. Каждый сид обладает копией этого файла и присутствует в сети для того, чтобы другие пиры могли скачивать у него п Сначала у личеров нет ни одной порции файла, и им приходится скачивать порции у сидов. какой-то из личеров получает порцию, он начинает передавать эту порцию другим личерам. образом, личеры загружают порции файла от сидов и от других личеров, которые имеют пор может выйти из сети после того, как он получит файл цзеалкилкюочма.етсЗяадавча минимизации времени распространения файла, т. е. времени необходимого для того, чтобы все л заинтересованные в файле, получили этот файл.

Рассмотрим следующие параметры. – множество пиров P2вP-сети; = | | – число пиров; – множество сидо в; = | | – число сидов; ℒ – множество личеровL;=| ℒ| – число личеров. Таким образо м, = ∪ ℒ и = + . , ( ), ( )}. Теорема личер не может получать файл со скоростью бы с(т р)е.е -Втчреемтьих,

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

. В-овторых, ≤ min{ ( ), ( )} и ≤ min{ ( ), ( )} и ( )

≤ min{ ( )≤ min{ ≤ (ℒ)/( − 1); ≥ (ℒ)/( − 1); , ( )}; , ( )}.

Рисунок 2. ( ), Рисунок 1. Схема распространения файла по P2P-сети Рассмотрим три численных примера, раскрывающих значение представленной теоремы. В каждо

Пропускная

значение миньинмоагло

времени при трёх различных личера есть= 200КБит/с. С ростом распространен и я фиксированных возрастает. значениях числа На

обычных личеортов 1 рисунке 2

представлено пропускной способности раздачи сидов: = 1000КБит/с, = 1500 КБит/с, = 2000КБит/с. меньше чем выше вечлиина = 200 КБит/с, = 600 КБит/с, примере пропускная способность загрузки личера

с но=ва200р0аКвнБаит/с. раздачи сида теперь постоянна и = 1р5ав0н0аКБит/с.

На рисунке 3 та же функция, но теперь меняется пропускная способность раздачи личера, а = 1000 КБит/с. следует, также

( )и быть применены описанные рассуждения. получена бесконечную для

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

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

Как и ожидалось, с ростом ч ислоабычных личеров суммарная скорость доступная в сети для раздачи снижается, что приводит к росту з на ч.енКиаяк видно из графика на рисунке 2 это вр зависит от пропускной способности р аз диачилдя суперличеров с= 2 МБит/с минимальное время распространения принимает наименьшее значение. На графике рисунка 3 в иднтоа,кжчето зависит от пропускной способности разд ачии для обычных личер о в с= 1 МБит/с минимально. Наконец, на Рисунке 4 видно, зачвтиосит от пропускной способности загруизкидля личеров с = 2,6 Мбит/с минимально. Заметим, что, начиная со зн а чен=ия5 , значения функции совпадают для пропускных способностей за гру=зк1и,6 МБит/с и = 2,6 МБит/с.

Для однородной системы полученное выражени е дблляизко к выражению для в случае chunk-based-модели. Представленная погрешность демонстрирует фаэктто.т Исследование показывает, что обсуждаемая жидкостная модель является хорошим приближением Pк2Pрсеатлиь.ноРйезультаты, полученные в работе, могут быть развиты в различных направлениях. Можно сравнить миним время распространения для жидкойстнмоодели с минимальным временем распространеcнhиuяnk-для based-модели для неоднородной системы. Другим направлением исследования является определен минимального времени распространения для сетей, в которых число одновременных соединений м пирами, уачствующими в процессе файлообмена, ограничено. Благодарности

Авторы выражают благодарность зав. кафедрой прикладной информатики и теории вероятнос РУДН проф. К.Е.Самуйлову за полезные советы при подготовке работы.

Публикация подготовлена при поддер«жПкреограммы РУДН -1050» и при финансовой поддержке РФФИ в рамках научных проекто-в07-№0360185, № -0177-00845.

Литература

References Об авторах: Бобрикова Екатерина Васильевна, кандидат физ и-мкаотематических наук, старший преподаватель кафедры прикладной информатики и теории вероятностей факульте-тмаатефмиазтиикчоеских и естественных наРуокс,сийский университет дружбы нар,оbдoоbв[e-mail] Гайдамака Юлия Васильевна, кандидат физи-мкаотематических наук, доцент, доцент прикладной информатики и теории вероятностей факультета -мафтиемзиактоических естественных наукР,оссийский университет дружбы нар,оgдaоyв[e-mail] Ромашкова Оксана Николаевна, доктор технических наук, профессор, зав. кафедрой информатики института математики, информатики и естественных наук, городской педагогчиеский университетR,[e-mail] кафедры и прикладной Московский

References

1. Гайдамака Ю.В. , Самуйлов А .К. Анализ стратегий заполнения буфера оборудования пользователя при предоставле услуги потокового видвео одноранговой сетиT-C/o/mm - Телекоммуникации и Транспо-рт2 . 013 . - № 11 . - C. 77 - 81

2. Napster company info [электронный ресурс] U/R/L: http://us.napster.com/availability/ ( дата обращения 15.06 . 2017 ).

3. The Gnutella Protocol Specification v0.4 [электронныйресурс] //URL: https://gnunet.org/node/147/ (дата обращения 15.06. 2017 ).

4. What is Freenet? Freenet company info [электронный ресурс] // URL: https://freenetproject.org/ ( дата обращения 15.06 . 2017 ).

5. The BitTorrent Protocol Specification [электронный ресурс] // URL: http://www.bittorrent.org/beps/bep\_ 0003 , (дата обращения 15.06 . 2017 ).

6. Vuse BitTorrent Client [электронный ресурс] //URL: http://www.vuze.com, free (дата обращения 15.06 . 2017 ).

7. X. Yang , G. de Veciana. Service Capacity of Peer-to-Peer Networks // In Proceedings of IEEE INFOCOM. - 2004 . - Vol. 04 . - P. 2242 - 2252 .

8. D. Qiu , R. Srikant Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks / / In Proceedings of ACM SIGCOMM, Portland, OR. - August 2004 . - Vol. 34 , № - 4P .. 367 - 378 .

9. Z. Mordji , M. Amad , D. Aissani A Derived Queueing Network Model for Structured P2P Architectures // VECoS 2014 (Bejaia , Algeria). - 2014 . - P. 76 - 84 .

10. Ferragut , F. Paganini Fluid models of population and download progress in P2P networks // IEEE Trans. on Control of Network Systems . - May 2016 . - Vol. 3 ( 1 ). - P. 34 - 45 .

11. Васильев И. , Гайдамака Ю .В., Самуйлов А .К. Анализ вероятности непрерывного воспроизведения потPо2кPо-вого видео в сети с помощью имитационного моделирования // Современные информационные техно-олборгиазиованиие.ИТ Сборник избранных трудIоXвМеждународной научн-опрактической конференции: учеб-мноетодическое пособие . Под ред.проф. В.А . Сухомлина- . М.: ИНТУИТ .РУ-. 2014 . - С . 36 - 7375 .

13. R. Kumar , K.W. Ross Optimal Peer-Assisted File Distribution: Single and Multi-Class Problems // In Proceedings of IEEE Workshop on Hot Topics in Web Systems and Technologies (HOTWEB) . - Boston. - 2006.

14. Самуйлов К.Е. , Бобрикова Е .В. Простейшая жидкостная модель файлPо2оPб-мсентниой/T/-Comm: Телекоммуникации и транспорт . - 2012 . - № 7. - С . 18 - 0184 .

1. Gaidamaka Yu .V., Samuilov A.K. Analysis of playback continuity for video streaming in Peer-to-Peer networks with data transfer delays // T-Comm - Telecommunications and Transport . - 2013, - № 11. - . P. 77 - 81 .

2. Napster company info [electronic resource] // URL: http://us.napster.com/availability/ ( date of access 15.06 . 2017 ).

3. The Gnutella Protocol Specification v0.4 [ electronic resource] // URL: https://gnunet.org/node/147 (date of access 15.06 . 2017 ).

4. What is Freenet? Freenet company info [electronic resource] // URL: https://freenetproject.org / (date of access 15.06 . 2017 ).

5. The BitTorrent Protocol Specification [electronic resource] // URL: http://www.bittorrent.org/beps/bep\_0003/ (date of access 15.06. 2017 ).

6. Vuse BitTorrent Client [electronic resource] // URL: http://http://www.vuze. com/ (date of access 15.06 . 2017 ).

7. X. Yang , G. de Veciana. Service Capacity of Peer-to-Peer Networks // In Proceedings of IEEE INFOCOM. - 2004 . - Vol. 04 . - P. 2242 - 2252 .

8. D. Qiu , R. Srikant Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks / / In Proceedings of ACM SIGCOMM, Portland, OR. - August 2004 . - Vol. 34 , № - 4P .. 367 - 378 .

9. Z. Mordji , M. Amad , D. Aissani A Derived Queueing Network Model for Structured P2P Architectures // VECoS 2014 (Bejaia , Algeria). - 2014 . - P. 76 - 84 .

10. Ferragut , F. Paganini Fluid models of population and download progress in P2P networks // IEEE Trans. on Control of Network Systems . - May 2016 . - Vol. 3 ( 1 ). - P. 34 - 45 .

11. Vasilyev I. , Gaidamaka Yu .V., Samuilov A.K. Анализ of the probability of continuous playback of video streaming in P2P networks using simulation // Sovremennye informatsionnye tekhnologii i IT-obrazovanie . Selected proceedings of the IX International Scientific-Practical Conference. Under the editorship of Prof . Sukhomlin V. A. - M.: INTUIT.RU . - 2014 . - С . 367 - 375 .

12. Medvedeva E.G. , Gaidamaka Yu .V. On Analysis of Performance Characteristics of P2P Video Streaming Network // Sovremennye informatsionnye tekhnologii i IT-obrazovanie . - 2015 . - Т . 2, № - P1 . 11 . 92 - 198 .

13. R. Kumar , K.W. Ross Optimal Peer-Assisted File Distribution: Single and Multi-Class Problems // In Proceedings of IEEE Workshop on Hot Topics in Web Systems and Technologies (HOTWEB) . - Boston. - 2006.

14. Samouylov K. E. , Bobrikova E. V. A simple fluid model of P2P file sharing network // T-Comm: Telecommunications and Transport. - 2012 . - № 7. - P. 180 - 184 .