Предисловие

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

Задача

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

Первичный анализ

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

Во-вторых, выделю общие черты для любых реализаций:

• Разбиение всех данных клиента на блоки по тому или иному признаку (файлы, блоки фиксированного размера и т.д.)
• Наличие “файла” с хэшем данных для каждого блока

Рассмотрим “файл”: для уменьшения избыточности передаваемых данных при обновлении/восстановлении клиента, размер блока должен быть не очень большим, и, как следствие, их кол-во будет значительным. Из этого следует немалый размер “файла” (например torrent-файл, содержащий данных на 2^16 блоков, будет весить около 1.25МБ). Ещё было бы крайне удобным, включить в этот “файл” информацию о версии (номер версии, название, changelog и т.д.). Загружать такой “файл” при каждом запуске клиента – неэффективно, т.к. в большинстве случаев он не изменился с последней загрузки. Поэтому будет разумно хранить этот “файл” локально и при запуске приложения проверять, не изменился ли он на сервере, и только если изменился – качать. При загрузке этого “файла” нельзя упускать из вида то, что обязательным условием реализации загрузки является гарантия достоверности этого “файла”, т.к. он обеспечивает не только актуальность, но и целостность клиента (это не защита от модификации клиента самими пользователями, это защита от внешних атак на компьютеры пользователей).

Структура клиента

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

1. Запускающее приложение – обычное оконное приложение, запускается первым и служит для решения следующих задач:
   • Проверка системных требований (поддержка необходимых наборов команд процессора, версии DirectX, кол-во ОЗУ и т.д.)
   • Проверка/загрузка обновлений ПО клиента
   • Проверка/восстановление целостности ПО клиента
   • Настройки некоторых параметров клиента (например выбора монитора, его разрешения, настроек графики и т.д.)
   • В МО/ММО можно использовать для логина игрока и операций с его аккаунтом (смена пароля, привязка в IP, оплата, обращение в техподдержку и т.д.)
2. Основное приложение – собственно игра
3. Маленькие файлы ресурсов (при изменении их обычно приходится полностью перекачивать)
4. Большие файлы ресурсов (большие паки, обновление которых происходит изменением блоков данных, без изменения положения остальных блоков, что позволяет обновлять их фрагментами)

* именно на 4ю группу приходится более 99% данных клиента

Анализ потенциальных трудностей

Основной сложностью данной задачи является периодическая потребность в передаче огромнейшего кол-ва данных. В качестве примера приведу последнее обновление AION размером 3.3Гб. Для передачи его 50`000 пользователей (что для онлайн игр совсем не много) потребовалось бы передать ~161ТБ информации, и это, не считая накладных расходов. Чтобы выполнить такую задачу за сутки сервера обновления должны обладать суммарным каналом в 20Гб/с (и это при том, что я взял небольшое кол-во пользователей). Но такая нагрузка будет существовать всего раз в несколько месяцев, а всё остальное время канал и оборудование будут использоваться лишь на 1-2%, а то и меньше.

Использование технологий наподобие мегатекстуры может увеличить размеры клиентов и обновлений до нескольких десятков раз. И если, с точки зрения клиента, скачать обновление размером 100-200Гб за сутки – это не проблема (ориентируюсь на скорость интернета более 10Мб/с как массовую), то содержание серверов, способных отдавать данные со скоростью 1Тб/с и выше, будет чрезвычайно затратным.

Кроме того, даже при установке таких серверов проблема доставки контента пользователям не будет решена в полной мере. Хотя пользовательские каналы и широки, но при подъёме вверх по сетевой иерархии они не обеспечены на 100% соотв. магистралями, и в момент, когда начнётся массовая загрузка такого объёма данных, скорость скачивания с серверов обновления станет ограничена промежуточными звеньями (см. рис. 1).

Например, в момент выхода обновления AION 3.0 пользователи русских серверов наблюдали очень грустную картину с загрузкой обновления на скорости 150 – 200КБ/с.

Поиск путей решения

Проблема доставки большого кол-ва одинаковой информации многим клиентам не нова, с такой же проблемой сталкиваются и IP-телевидение, и файлообмен.

После ознакомления с различными решениями в данной области пришлось сразу отбросить всё, что связанно с мультикастингом, т.к. он работает только в рамках одного сегмента сети и требует наличие “ретрансляторов”, в том числе в сетях ISP.

CDN

Одним из возможных решений проблемы загрузки промежуточных каналов могло бы стать использование целой сети датацентров для зеркалирования данных и загрузки данных потребителем с ближайшего сервера (CDN – Content Delivery Network).

Существует несколько коммерческих сетей CDN, размещающих материалы в своей сети на платной основе. Плата обычно взимается за кол-во трафика и колеблется от 7.5$ до 100$ за ТБ в зависимости от планируемого кол-ва трафика, провайдера CDN и региона (данные за 4й квартал 2011 года). Учитывая, что в большой онлайн игре может быть многим более чем миллион пользователей, то при выходе обновления размером 10ГБ речь будет идти уже о трафике в 10ПБ или порядка 100`000-200`000$. Что существенно дешевле поддержания своей сети серверов (особенно учитывая характер нагрузки – резкий пик в момент выхода больших обновлений и очень незначительные нагрузки в остальное время). Однако в последнее время наметилась тенденция с переходом соотв. компаний на модель оплаты за канал, а не за трафик, что делает их использование заметно менее выгодным – канал, необходимый для доставки 10Пб конечным пользователям за сутки, будет стоить порядка 2`500`000$ в месяц.

Кроме того, у данного решения есть один минус – оно не может полностью избавить нас от проблем каналов “последней мили”, т.к. сервера CDN в любом случае находятся в датацентрах.

P2P-сети

Еще одним решением может стать использование p2p сети для доставки контента. P2P-сети используются не только для доставки данных конечному пользователю. Например в Twitter используется система Murder (основанная на протоколе BitTorrent) для развёртывания ПО на более чем тысяче серверов за 30-60 секунд. Это становится возможным, т.к. в таких сетях все клиенты выступают одновременно и серверами.

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

Первая из них – это возможность обслуживания сети практически любого размера лишь несколькими выделенными серверами обновлений из-за того, что с ростом числа клиентов растёт и поддержка серверов с их стороны. И хотя с этим не всё так безоблачно из-за ассиметричных каналов пользователей и закрытых у многих портов, но для поддержания работоспособности сети достаточно около 10-15% узлов с открытыми портами (зачастую пользователь может легко добиться открытого порта на своей машине, однако его следует мотивировать к таким действиям – об этом далее). Кроме того, хотя часто ISP и предоставляют доступ в интернет с ассиметричной скоростью доступа, скорость обмена между клиентами провайдера обычно не регламентируется и ограничивается только техническими средствами.

Вторая особенность – это расположение “серверов” в таких сетях. Т.к. “сервера” расположены у конечных пользователей, то возникает возможность качать непосредственно из своего сегмента сети (ну или более близкого сегмента). Однако эффективное использование этого преимущества требует поддержки соотв. алгоритмов поиска “ближайших” пиров на уровне протокола и ПО.

Таким образом использование р2р-сетей для реализации системы обновления клиентов МО/ММО игр может оказаться крайне удачным решением:

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

Возможное решение: BitTorrent protocol

При беглом взгляде на проблему, хорошим решением показалось использование протокола BitTorrent. Этот открытый протокол чрезвычайно распространён в интернете (по данным некоторых исследований на него приходится до 30% мирового интернет трафика). Из-за этого для него существует множество клиентов, библиотек и т.д., что существенно облегчает разработку необходимого нам ПО (по сути нам достаточно лишь включить его поддержку в запускающее приложение, т.к. для серверов обновлений и генерации torrent-файлов можно использовать существующие решения). Обновление по данному протоколу уже используется некоторыми играми.

Из личного опыта скажу, что помимо перечисленных выше достоинств у p2p-протоколов есть еще одно – хорошая скорость скачивания даже вечером (в часы пик). Обычно в это время скорость передачи данных в один поток сильно снижается, но из-за того, что в p2p-протоколах скачивание ведётся по множеству соединений, общая скорость остаётся приемлемой.

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

Во-первых, это представление нескольких файлов единым байтовым потоком и использование неполной части только в конце всего потока, а не в конце каждого файла. Такая организация хэшей требует выполнения полного рехеша клиента при каждом обновлении (в то время как при принадлежности части только одному файлу, можно просто сверять хэши в старой и новой версии “информации о клиенте” и избегать рехеша основной массы частей). При большом размере клиента это крайне неудобно. И если на клиентах размером ~20ГБ такая операция может занимать до 2-3 минут, то на больших клиентах до часа и более. И пользователя будет раздражать часовое ожидание при обновлении в пару сотен мегабайт. Конечно можно пойти на хитрость и разместить описание больших файлов в начале torrent-файла. А кроме того принудительно устанавливать их размер кратным размеру части в torrent-файле, но это уже полумеры.

Вторым крупным минусом BitTorrent протокола является механизм построения сети пиров. Обычно трекер отдаёт пиру список из случайно выбранных пиров, кроме него самого (в некоторых реализациях используется дополнительная оптимизация для непередачи сидам других сидов). Такой способ построения сети пиров не очень удобен для решения нашей задачи, т.к. не способствует локализации обмена (хотя замечу, что работы в сторону локализации обмена ведутся и в протоколе Bittorrent).

Третьим минусом можно назвать равноправность участников обмена. С целью оптимизации процесса распространения данных серверам обновления хотелось бы в первую очередь отсылать данные пирам, способным их распространить максимальному кол-ву других пиров (т.е. пиров с открытыми портами). Введение такого принципа обслуживания также будет способствовать тому, что пользователи будут стремиться иметь открытый порт, а это в свою очередь позитивно скажется на работоспособности сети. Конечно можно использовать алгоритм “superseed” на серверах, но он не отвечает в полной мере нашим требованиям, а кроме того, будет создавать много проблем в “не пиковое” время.

Есть еще несколько минусов, вроде избыточности HTTP-tracker протокола и т.д. Но это мелкие и незначительные факторы, которые не могут серьезно повлиять на выбор протокола.

Предлагаемое решение: SkyUpdate protocol

SkyUD protocol является полностью открытым протоколом, с полным описанием которого можно ознакомиться тут.

В свете вышеперечисленных недостатков torrent-протокола, на его базе мною был разработан SkyUpdate-протокол, со следующими основными отличиями:

• Изменения метафайла:
  • Т.к. формат bencode отнюдь не лучший формат сериализации, то вместо него был использован формат CatStructureStorageFormat (открытый формат собственной разработки для сериализации произвольных структур данных)
  • Т.к. использование какого-либо алфавита, кроме английского в именах файлов игры не является целесообразным, то такая возможность была исключена вместе с соотв. полем
  • С целью избавить клиентов от необходимости лишних обращений к DNS, список серверов (они пришли на смену трекерам) хранится в виде IP-адресов в IPv6-формате
  • Т.к. метафайлов, хранящих информацию только об одном файле, не предвидится (исходя из описанной выше структуры клиента), то секция с описанием файлов была упрощена и теперь всегда является массивом
  • Каждая часть теперь может принадлежать только одному файлу (упрощение логики клиента)
  • Размер части строго 8МБ и не может быть изменён (убрано соотв. поле) (по сети части передаются блоками по 32КБ, в конце части может быть блок меньшего размера)
• Изменения сетевого протокола:
  • Изначальная ориентированность на IPv6 (поддержка IPv4 сохранена)
  • Отсутствие расширений протокола (некоторые расширения torrent-протокола вроде команд CanFaster или запроса дополнительных адресов пиров у подключённых пиров)
  • Отсутствие шифрования протокола (признано нецелесообразным, хотя может быть легко добавлено впоследствии)
  • 96-ти байтное рукопожатие (сервера в ответе вместо своего ID указывают IP-адрес, под которым они видят клиента, в IPv6-формате. Это требуется для того, чтобы клиент всегда знал свой реальный IP-адрес и мог корректно выбирать пиров для подключения)
  • Наличие флага состояния в рукопожатии, с помощью которого реализуется ряд функций: проверка доступности порта, уведомление о перезагрузке или отсутствии требуемого образа (также наличие этого флага позволило отказаться от команды bitfield)
  • Команда постоянной длины в 4 байта (у torrent-протокола длина команды от 1го до 13-ти байт), за которой могут следовать до 32КБ данных (в зависимости от команды)
  • 4-х байтные команды располагаются в порядке little-endian (а не big-endian как у torrent), что крайне удобно для платформы x86_64 (являющейся сейчас основной)
• Изменения структуры сети:
  • Вместо равноправных пиров (которые могут быть как личерами, так и сидерами) и трекера (единой точки обмена информацией об участниках файлообмена) были введены клиенты и серверы. Клиенты – это пиры, которые всегда являются личерами (ведь, как только загрузка обновления закончена, происходит запуск игры; т.е. это компьютеры пользователей), а серверы – это постоянно действующие сидеры, являющиеся, кроме того, еще и заменой трекерам

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

• Не более 256-ти файлов в образе
• Не более 2^20 частей (т.е. максимальный размер образа может составлять 8ТБ)

Анализ эффективности предлагаемого решения

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

Симулятор

Симулятор имеет следующие характеристики:

• Сеть пиров представляла из себя иерархическое дерево на основании 32 портовых коммутаторов с дополнительным uplink-портом для связи с вышестоящим коммутатором.
• Сеть между коммутаторами имеет неограниченную скорость
• Сеть между пирами и ближайшими коммутаторами имеет ограниченную скорость передачи и неограниченную скорость приёма
• Считается, что сервер соединён с каждым пиром отдельной сетью, скорость которой ограничена скоростью, с которой сервер может отдавать данные (данное допущение разумно, пока каждый клиент получает с сервера лишь небольшой % от общего объёма данных)

Для дальнейшего анализа симулятор собирает следующую статистику:

• Кол-во итераций, потребовавшихся, чтобы все клиенты скачали образ
• Кол-во раз, которое сервер выгрузил полный образ
• Для каждой итерации средняя нагрузка на порты коммутаторов (независимые значения для каждого уровня сетевой иерархии)
• Среднее кол-во переданных данных для портов каждого уровня сетевой иерархии

Симуляция осуществляется по-тиково. Тиком считается отрезок времени, за который клиент способен отдать 1 блок образа – 32 КБ (для клиентсого порта в 1Мб/с продолжительность тика составляет ~284мс).

Первичный анализ

Теперь предстояло решить как именно проводить анализ. После некоторых изысканий объектами для исследования были выбраны следующие параметры:

• Метод построения сети пиров (случайный против кольца)
• Дросселирование пиров (а также проверка тех предположений, на основании которых строились рекомендации по настройке сервера)
• Оптимизация отправки Have-сообщений (сообщение Have для части посылается только тем клиентам, у которых, по нашим данным, еще нет данной части)
• Размер образа
• Кол-во пиров

Т.к. расчёт результатов (особенно для случаев с большим кол-вом пиров/размером образа) занимает значительное время, то было принято решение провести первичный анализ для уменьшения необходимого кол-ва симуляций. Все симуляции первичного анализа проводились исходя из того, что порт сервера был в 10 раз быстрее порта клиента (при таких настройках вклад сервера не превышал 1.5% от размера образа).

Во время проведения первичных симуляций было установленно, что  алгоритм “Оптимизация отправки Have-сообщений” не влияет ни на какие параметры, кроме кол-ва служебной информации (служебный трафик снижается на 3-3.5%).

Подтверждение необходимости дросселирования пиров

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

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

Такое поведение вполне предсказуемо, т.к. клиенты могут обмениваться лишь блоками частей, которые они полностью скачали. При одновременном обслуживании всех клиентов скорость скачивания каждым из них очень низка, а для начала работы p2p-сети необходимо, чтобы у клиентов появились целые части. Это же объясняет наличие резкого пика p2p-активности в точке появления у клиентов первых частей. Т.к. все клиенты качали случайные части, то в этот момент практически все заинтересованы в скачивании у всех. Время появления пика также совпадает с аналитически предсказанным. Для сети в 1024 клиента обмен начинается на 26113-й итерации, а уже на 26256-й итерации пик для образа в 1ГБ полностью заканчивается (для образа 8ГБ он заканчивается чуть позднее – 26264-я итерация). Учитывая, что за одну итерацию сервер распространяет 320КБ данных, получается, что до начала обмена сервер успевает раздать 7,969ГБ данных, т.е. почти по 8МБ на клиента, или одну часть. Для сети в 2048 клиентов ситуация полностью аналогична: начало обмена на 52225-й итерации и 15,937ГБ розданных сервером данных.

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

Отлично видно что с увеличением кол-ва блоков, отдаваемых одному клиенту, исчезает пик в начале работы p2p-сети, начало становится более гладким и уменьшается мёртвая зона в начале скачивания. Когда кол-во отдаваемых одному клиенту блоков достигает 256-ти (одной части), то мёртвая зона пропадает вовсе (что приводит к сокращению времени скачивания с 68369 итераций до 53162). Дальнейший рост кол-ва отдаваемых блоков до смены пира хоть и приводит к некоторому сокращению времени скачивания, но он уже не так важен.

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

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

Графики показывают, что и на клиенте дросселирование пиров даёт положительные результаты, хотя и менее заметные, чем на сервере (вполне логично, т.к. у клиентов соединений от 32-х до 64-х).

В итоге после применения дросселирования и на сервере, и на клиенте, время скачивания образа 1ГБ в сети из 1024 клиентов со случайной топологией  сократилось с 68369 до 49034 итераций, т.е. на 28.3%.

Влияние размеров образа на получаемый результат

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

1024 клиента, сеть со случайной топологией

Размер (ГБ)	Время (в тиках)	Среднее кол-во служебных данных на порт первого уровня (КБ)	Среднее кол-во служебных данных на порт второго уровня (КБ)	Среднее кол-во полезных данных на порт первого уровня (МБ)	Среднее кол-во полезных данных на порт второго уровня (МБ)
1	49034	262,61	8117,77	1009,3	31189,4
2	91871	525,5	16247,1	2019,96	62446,73
4	179683	1051,19	32506,33	4041,16	124958,5
8	352104	2102,83	65038,81	8084,54	250033,18
16	784120	4199,4	129913,11	16144,7	499429,4
32	1540003	8400,91	259881,2	32298,2	999081,51
64	2851142	16819,34	520063,42	64665,9	1999376,23

1024 клиента, сеть с кольцевой топологией

Размер (ГБ)	Время (в тиках)	Среднее кол-во служебных данных на порт первого уровня (КБ)	Среднее кол-во служебных данных на порт второго уровня (КБ)	Среднее кол-во полезных данных на порт первого уровня (МБ)	Среднее кол-во полезных данных на порт второго уровня (МБ)
1	48859	260,32	2218,8	1009,8	8595,77
2	93629	520,89	4439,67	2019,42	17211,24
4	170148	1043,5	8873,17	4044,7	34401,28
8	330657	2086,88	17814,35	8091,9	69072,77
16	735119	4168,4	35890,54	16159,65	139173,16
32	1416522	8341,5	72469,95	32335,71	281085,16
64	2841039	16681,46	145065,53	64668,98	562649,3

Как мы видим, при обеих топологиях сети наблюдается линейная (у времени распространения данных – близкая к линейной) зависимость всех параметров от размера образа.

Итоги

Итогами первичного анализа стали следующие решения:

• Все тесты будут проводиться с включённым алгоритмом “Оптимизация отправки Have-сообщений”
• Все тесты будут проводиться с дросселированием пиров, настроенным на отдачу 256-ти частей за одну сессию (как на сервере, так и на клиенте)
• Все тесты будут проводиться для образов размером 1ГБ

Основной анализ

Даже несмотря на то, что после первичного анализа кол-во необходимых тестов удалось сократить до 110 (все тесты проводились для образа размером 1ГБ, с включённым дросселированием пиров у сервера и клиентов), реально было проведено только 104 из них, т.к. последние 6 имели непозволительно большое время рассчёта. Выполнение тестов заняло 1200 часов. А учитывая, что многие тесты приходилось выполнять более одного раза, время выполнения симуляции перевалило за 2000 часов (все тесты выполнялись на выделенном сервере с 4-х ядерным процессором).

При анализе данных для различных соотношений скоростей портов клиента и сервера, было выявлено, что результаты получаются примерно одинаковыми (за исключением случаев, когда вклад сервера превышал 10%. Однако их вообще бесполезно рассматривать, т.к. допущения, принятые при написании симулятора, делают полученные в таких условиях данные недостоверными). Т.к. использовать соотношение скоростей 1:10 не представлялось возможным (тесты для более чем 256к клиентов не проводились по причине, описанной выше), то было принято решение анализировать тесты для соотношения скоростей 1:100 (тем более, что такое отношение выглядит очень правдоподобным: клиенты 10-100Мб/с, сервер 1-10Гб/с). Таким образом кол-во анализируемых тестов сократилось до 22-х.

Служебные данные

В техническом описании протокола сказано, что теоритически накладные расходы протокола – от 0,024% до 0,81%.

Топология	Минимальное значение	Среднее зрачение	Максимальное значение
Случайная	0,0254%	0,0257%	0,0350%
Кольцевая	0,0248%	0,0254%	0,0328%

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

Влияние кол-ва пиров на получаемый результат

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

• Peers – кол-во пиров
• Ticks – время скачивания (в тиках)
• Сontr. – вклад сервера в распространение данных (при 100% какая-либо активность p2p-обмена отсутсвтует, и все данные скачиваются с сервера)
• T1, T2, T3, T4 – среднее кол-во данных, переданных через порт соотв. уровня за весь период симуляции (в МБ)
• A1, A2, A3, A4 – средняя нагрузка на порты сетевой инфраструктуры соотв. уровня (относительно скорости клиентского порта)
• P1, P2, P3, P4 – пиковая нагрузка на порты сетевой инфраструктуры соотв. уровня (относительно скорости клиентского порта)

Зависимость нагрузки на сеть от кол-ва клиентов (кольцевая/случайная топология)

Peers	Ticks	Contr.	T1	T2	T3	T4
1024	34023 / 37163	10,14% / 11,07%	920,17 / 910,59	7776,22 / 28166,7	–	–
2048	37898 / 40970	5,65% / 6,11%	966,17 / 961,48	8174,9 / 30244,2	8084,32 / 462602,96	–
4096	42775 / 44582	3,19% / 3,33%	991,36 / 989,98	8410,54 / 31408,8	8474,57 / 738495,48	–
8192	49815 / 47515	1,86% / 1,77%	1004,99 / 1005,83	8548,56 / 32046,6	8590,89 / 889040,25	–
16384	59616 / 50172	1,11% / 0,93%	1012,62 / 1014,43	8686,43 / 32388,4	8792,7 / 966460,4	–
32768	77909 / 52293	0,73% / 0,49%	1016,57 / 1019,1	9149,13 / 32573,5	10334,52 / 1007297,16	–
65536	105431 / 52533	0,49% / 0,24%	1018,97 / 1021,49	9448,28 / 32671,55	10707,47 / 1029093,18	9848,1 / 15585657,1
131072	155263 / 52134	0,36% / 0,12%	1020,29 / 1022,75	9486,8 / 32719,61	9947,8 / 1038278,99	9204,28 / 24332965,32
262144	272170 / 51612	0,32% / 0,06%	1020,75 / 1023,38	9516,41 / 32744,1	9905,29 / 1043468,51	11821,58 / 28916798,33
524288	540387 / 51445	0,31% / 0,03%	1020,77 / 1023,69	9528,97 / 32755,97	9826,52 / 1046019,66	10206,7 / 31224806,84
1048576	1079896 / 51353	0,31% / 0,0149%	1020,78 / 1023,84	9511,3 / 32761,97	9812,12 / 1047294,1	10149,81 / 32391343,81

Нагрузка на сетевую инфраструктуру (кольцевая/случайная топология) 

Peers	A1	A2	A3	A4	P1	P2	P3	P4
1024	0,87 / 0,78	7,31 / 24,25	–	–	1 / 1	10,34 / 31,53	–	–
2048	0,82 / 0,75	6,89 / 23,61	6,83 / 361,41	–	1 / 1	9,47 / 31,75	14,0 / 570,15	–
4096	0,74 / 0,71	6,28 / 22,54	6,34 / 530,21	–	1 / 1	9,09 / 31,88	11,50 / 808,96	–
8192	0,65 / 0,68	5,48 / 21,53	5,52 / 597,63	–	1 / 1	8,97 / 31,94	10,63 / 917,49	–
16384	0,54 / 0,65	4,65 / 20,65	4,72 / 616,57	–	1 / 1	8,84 / 31,97	10,50 / 969,88	–
32768	0,42 / 0,62	3,74 / 19,92	4,25 / 616,56	–	0,96 / 1	8,44 / 31,97	10,38 / 996,98	–
65536	0,31 / 0,62	2,85 / 19,89	3,25 / 626,41	2,99 / 9496,28	0,76 / 1	7,06 / 32	8,33 / 1010,54	16,0 / 17354,51
131072	0,21 / 0,63	1,94 / 20,07	2,05 / 637,46	1,90 / 14939,44	0,58 / 1	5,43 / 32	6,29 / 1017,71	14,25 / 25308,32
262144	0,12 / 0,63	1,10 / 20,29	1,16 / 647,13	1,39 / 17933,29	0,37 / 1	3,41 / 32	3,84 / 1021,06	10,75 / 29144,17
524288	0,06 / 0,64	0,55 / 20,37	0,58 / 650,81	0,60 / 19427,50	0,25 / 1	2,31 / 32	2,81 / 1022,58	7,50 / 30958,51
1048576	0,03 / 0,64	0,27 / 20,41	0,29 / 652,77	0,30 / 20189,40	0,15 / 1	1,41 / 32	1,65 / 1023,46	5,88 / 31867,31

Анализ этих данных позволяет нам сделать следующие выводы:

• Время скачивания у сети с кольцевой топологией демонстрирует стабильный рост вместе с ростом числа клиентов, в то время как у сети со случайной топологией его практически не наблюдается.
• Назгрузка на сетевую инфраструктуру у сети со случайной топологией увеличивается линейно, в то время как сеть с кольцевой топологией практически не демонстрирует роста нагрузки.
• Начиная с 32К пользователей, сеть с кольцевой топологией перестаёт использовать возможности конечного канала клиентов на 100%, даже при пиковой нагрузке на p2p сеть.
• Хотя случайная топология и даёт выигрыш во времени скачивания, но для его получения требуется сетевая инфраструктура, обеспечивающая линейный рост пропускной способности каналов вместе с ростом кол-ва пользователей (чего нет в реальности, см. “Анализ потенциальных трудностей”).

Теперь попробуем оценить время скачивания не только в бесконечнобыстрой сетевой среде, но и в среде с ограниченной скоростью работы как каналов клиентов и сервера, так и всей сетевой инфраструктуры. Ниже преведённая таблица предполагает следующую сетевую инфраструктуру: L1 (и порты клиентов) – 10Мб/с, L2 – 100Мб/с, L3 – 1000Мб/с и L4 – 10000Мб/с. Если для сети с неограниченной пропускной способностью рассчёт времени скачивания очень прост – время тика составляет ~28,4мс, то вот для сети с ограниченной пропускной способностью рассчёт был более сложным.

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

Время скачивания (кольцевая/случайная топология) 

Peers	Время скачивания в сети с неограниченной пропускной способностью	Время скачивания в сети с ограниченной пропускной способностью
1024	16,1 мин / 17,6 мин	16,1 мин / 43,8 мин
2048	17,9 мин / 19,4 мин	17,9 мин / 73,3 мин
4096	20,2 мин / 21,1 мин	20,2 мин / 114,0 мин
8192	23,6 мин / 22,5 мин	23,6 мин / 137,1 мин
16384	28,2 мин / 23,7 мин	28,2 мин / 149,5 мин
32768	36,9 мин / 24,8 мин	36,9 мин / 156,3 мин
65536	49,9 мин / 24,9 мин	49,9 мин / 246,3 мин
131072	73,5 мин / 24,7 мин	73,5 мин / 371,8 мин
262144	128,8 мин / 24,4 мин	128,8 мин / 441,0 мин
524288	255,8 мин / 24,4 мин	255,8 мин / 475,9 мин
1048576	511,15 мин / 24,3 мин	511,15 мин / 493,7 мин

Для справки: минимальное время, необходимое для скачивания 1ГБ информации через канал 10Мб/с – 15,5 минут.

Как мы видим, с введением ограничения на пропускную способность сетевой инфраструктуры ситуация резко меняется, и кольцевая топология начинает выигрывать у случайной. Причём выигрыш во времени скачивания достигает 5-ти раз. И это при значительно более низкой нагрузке на сетевую инфраструктуру во время скачивания.

Несколько слов о сетевой топологии

Наверное многие читатели уже задавали себе вопрос: почему для определения сетевого расстояния между пирами используется разность их IP-адресов? Ведь в реальности сеть имеет куда более сложную топологию, чем у симулятора, описанного в данной статье.

Во-первых, SkyUD Protocol разрабатывался в первую очередь для сетей IPv6 и уже потом для IPv4. В сетях IPv6 адреса распределяются как раз по территориальному и маршрутизационному признакам: континент, страна, регион, провайдер и т.д.. Нечто подобное наблюдается и в IPv4 сетях, хотя в куда менее структурированной форме.

Во-вторых, пусть это и не самый точный, зато очень быстрый и простой способ.

Вместо послесловия

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

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

Найденное же решение оказалось поразительно простым: помимо 32-64 соединений с кольцом необходимо устанавливать всего одно соединение со случайным пиром в рое. При этом не требуется вносить никаких изменений в логику скачивания. Даже такое простое решение дало поразительные результаты. Ниже приводятся 3 таблицы из раздела “Влияние кол-ва пиров на получаемый результат”, только вместо данных случайной топологии сети в них данные от кольцевой топологии с одним случайным соединением:

Зависимость нагрузки на сеть от кол-ва клиентов (кольцевая/кольцевая со случайным соединением)

Peers	Ticks	Contr.	T1	T2	T3	T4
1024	34023 / 33931	10,14% / 10,11%	920,17 / 920,45	7776,22 / 8857,91	–	–
2048	37898 / 37586	5,65% / 5,6%	966,17 / 966,65	8174,9 / 9321,82	8084,32 / 38546,23	–
4096	42775 / 41762	3,19% / 3,11%	991,36 / 992,14	8410,54 / 9646,55	8474,57 / 54972,22	–
8192	49815 / 46897	1,86% / 1,75%	1004,99 / 1006,11	8548,56 / 9743,42	8590,89 / 64214,15	–
16384	59616 / 51979	1,11% / 0,97%	1012,62 / 1014,09	8686,43 / 9895,0	8792,7 / 69330,33	–
32768	77909 / 56772	0,73% / 0,53%	1016,57 / 1018,59	9149,13 / 9958,48	10334,52 / 72383,16	–
65536	105431 / 54643	0,49% / 0,25%	1018,97 / 1021,39	9448,28 / 9949,15	10707,47 / 71951,91	9848,1 / 1039872,03
131072	155263 / 53542	0,36% / 0,12%	1020,29 / 1022,72	9486,8 / 9943,03	9947,8 / 71746,69	9204,28 / 1540040,51
262144	272170 / 50968	0,32% / 0,06%	1020,75 / 1023,39	9516,41 / 9898,61	9905,29 / 71224,08	11821,58 / 1781417,55
524288	540387 / 49089	0,31% / 0,03%	1020,77 / 1023,71	9528,97 / 9884,91	9826,52 / 71090,59	10206,7 / 1903464,2
1048576	1079896 / 47567	0,31% / 0,0138%	1020,78 / 1023,86	9511,3 / 9872,42	9812,12 / 71183,22	10149,81 / 1968932,64

Нагрузка на сетевую инфраструктуру (кольцевая/кольцевая со случайным соединением) 

Peers	A1	A2	A3	A4	P1	P2	P3	P4
1024	0,87 / 0,87	7,31 / 8,35	–	–	1 / 1	10,34 / 11,22	–	–
2048	0,82 / 0,82	6,89 / 7,93	6,83 / 32,83	–	1 / 1	9,47 / 10,63	14,0 / 55,01	–
4096	0,74 / 0,76	6,28 / 7,38	6,34 / 42,13	–	1 / 1	9,09 / 10,5	11,50 / 64,77	–
8192	0,65 / 0,69	5,48 / 6,63	5,52 / 43,83	–	1 / 1	8,97 / 9,91	10,63 / 70,52	–
16384	0,54 / 0,62	4,65 / 6,08	4,72 / 42,69	–	1 / 1	8,84 / 9,91	10,50 / 79,33	–
32768	0,42 / 0,57	3,74 / 5,6	4,25 / 40,81	–	0,96 / 1	8,44 / 9,75	10,38 / 79,24	–
65536	0,31 / 0,6	2,85 / 5,81	3,25 / 42,15	2,99 / 609,13	0,76 / 1	7,06 / 9,81	8,33 / 77,32	16,0 / 1189,8
131072	0,21 / 0,61	1,94 / 5,93	2,05 / 42,89	1,90 / 920,67	0,58 / 1	5,43 / 9,84	6,29 / 78,32	14,25 / 1745,19
262144	0,12 / 0,64	1,10 / 6,20	1,16 / 44,73	1,39 / 1118,76	0,37 / 1	3,41 / 10,34	3,84 / 82,01	10,75 / 2089,40
524288	0,06 / 0,67	0,55 / 6,43	0,58 / 46,35	0,60 / 1241,16	0,25 / 1	2,31 / 10,81	2,81 / 90,96	7,50 / 2501,32
1048576	0,03 / 0,69	0,27 / 6,63	0,29 / 47,90	0,30 / 1324,93	0,15 / 1	1,41 / 11,44	1,65 / 100,88	5,88 / 2877,91

Время скачивания (кольцевая/кольцевая со случайным соединением) 

Peers	Время скачивания в сети с неограниченной пропускной способностью	Время скачивания в сети с ограниченной пропускной способностью
1024	16,1 мин / 16,1 мин	16,1 мин / 16,1 мин
2048	17,9 мин / 17,8 мин	17,9 мин / 17,9 мин
4096	20,2 мин / 19,8 мин	20,2 мин / 19,8 мин
8192	23,6 мин / 22,2 мин	23,6 мин / 22,2 мин
16384	28,2 мин / 24,6 мин	28,2 мин / 24,6 мин
32768	36,9 мин / 26,9 мин	36,9 мин / 26,9 мин
65536	49,9 мин / 25,9 мин	49,9 мин / 26,2 мин
131072	73,5 мин / 25,3 мин	73,5 мин / 31,5 мин
262144	128,8 мин / 24,1 мин	128,8 мин / 34,0 мин
524288	255,8 мин / 23,2 мин	255,8 мин / 35,0 мин
1048576	511,15 мин / 22,5 мин	511,15 мин / 35,7 мин

Разницу видно невооружённым взглядом: увеличение кол-ва скачивающих в 1024 раза приводит к росту времени скачивания всего в чуть более чем 2 раза.

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