От переводчика: Это перевод третьей статьи из цикла «Networking for game programmers». Мне очень нравится весь цикл статей, плюс всегда хотелось попробовать себя в качестве переводчика. Возможно, опытным разработчикам статья покажется слишком очевидной, но, как мне кажется, польза от нее в любом случае будет.
Первая статья — http://habrahabr.ru/post/209144/
Вторая статья — http://habrahabr.ru/post/209524/
Виртуальные соединения поверх UDP
Введение
Привет. Меня зовут Гленн Фидлер и я приветствую вас в третьей статье из цикла “Сетевое программирование для разработчиков игр”.
В предыдущей статье мы разобрались, как отправлять и принимать пакеты, используя протокол UDP.
Так как UDP не поддерживает соединения, один UDP сокет может быть использован для обмена пакетами с любым числом удаленных компьютеров. Однако в многопользовательских играх, как правило, мы обмениваемся информацией только с несколькими узлами.
В качестве первого шага к реализации системы соединений, мы рассмотрим наиболее простой случай: создание виртуального соединения между двумя компьютерами.
Но сначала, нам нужно более плотно разобраться, как работает интернет.
Интернет — это не набор труб
В 2006 году сенатор Тед Стивенс вошел в историю интернета со своей знаменитой речью об Акте Сетевого Нейтралитета:
“Интернет — это не штука, в которую можно что-то положить. Не большой грузовик. Это набор труб”.
Когда я только начинал пользоваться интернетом, я думал точно так же, как Тед. Сидя в компьютерном классе Сиднейского Университета в 1995 году, я “серфил в интернете” с помощью новомодной штуки, которая называлась Netscape Navigator, и не имел ни малейшего понятия, что там происходило на самом деле.
Тогда я думал, что каждый раз, когда я подключался к какому-либо сайту, создавалось настоящее подключение, как при телефонном разговоре. И я думал — сколько стоит подключиться к сайту? Тридцать центов? Доллар? Станет ли кто-нибудь из университета требовать с меня деньги за подключения по межгороду? :)
Конечно, сейчас это все звучит просто смешно.
Нет никакого пульта, который где-то стоит и напрямую соединяет вас телефонным проводом с другим компьютером, к которому вы хотите подключиться, ни наборов труб, о которых рассказывал нам сенатор Стивенс.
Без прямых подключений
Вместо всего этого, ваши данные пересылаются по протоколу IP в пакетах, которые бегут от компьютера к компьютеру.
Пакет может пройти через несколько узлов, пока не достигнет адресата. Вы не можете знать заранее количество этих узлов, так как оно меняется динамически, в зависимости от того, как сеть решает направить пакеты. Даже если отправите два пакета A и B по одному и тому же адресу, они могут пойти разными путями. В этом, кстати говоря, и заключается причина отсутствия гарантии доставки пакетов по порядку в UDP.
В unix-подобных системах можно изучить маршруты пакетов утилитой “traceroute”, передав ей имя хоста или IP адрес.
В windows вместо “traceroute” используется “tracert”.
Попробуйте проанализировать маршруты до нескольких сайтов, например:
traceroute slashdot.org
traceroute amazon.com
traceroute google.com
traceroute bbc.co.uk
traceroute news.com.au
Посмотрите на результаты работы утилиты, и вы, думаю, сразу убедитесь, что нет никаких прямых подключений к сайтам.
Как происходит доставка пакетов
В первой статье цикла я привел простую аналогию процесса доставки пакетов — как передача записки от одного человека к другому в комнате, полной народу.
Хотя эта аналогия и отображает общую идею, но она слишком упрощена. Интернет — это не простая одноранговая сеть, а сеть сетей. И, конечно, нам нужно передавать записки не в пределах комнаты, а в любую точку мира!
Очевидно, много лучшей аналогией является… почтовая служба!
Когда вы хотите отправить кому-то письмо, вы кладете его в почтовый ящик, и при этом вы уверены, что оно придет по адресу. Для вас не важно, как именно оно будет доставлено, а важен сам факт доставки. Конечно, кто-то должен физически доставить письмо — но каким образом?
Очевидно, что почтальон не сам будет доставлять ваше письмо — почтовая служба это тоже не набор труб :). Вместо этого, он отнесет ваше письмо в почтовое отделение для последующей обработки.
Если адресат письма живет в том же районе, что и вы, то в почтовом отделении ваше письмо просто отдадут другому почтальону, и он сам отнесет его. Но если нет, то начинается уже более интересный процесс. Ваше местное почтовое отделение не может доставить письмо самостоятельно, и оно передает его “выше” по иерархии — в региональное отделение или почтовый центр в аэропорту, в случае, если адресат находится далеко. В идеальном случае ваше письмо повезут в большом грузовике (отсылка к речи того сенатора — прим. перев.).
Давайте рассмотрим сложный случай — скажем, мы отправляем письмо из Лос-Анджелеса в Сидней в Австралии. Местное почтовое отделение получает письмо, определяет, что оно должно быть доставлено за рубеж, и пересылает его в почтовый центр в аэропорту Лос-Анджелеса. Там снова обрабатывают адрес назначения письма, и отправляют его ближайшим рейсом до Сиднея.
Самолет с письмом садится в Сиднее, где вступает в работу новая почтовая служба, и проделывает все те же операции, но в обратном порядке. Письмо идет “вниз” по иерархии, от общего к частному. Из пункта сортировки почты в аэропорту оно попадает в региональный офис, который, в свою очередь, пересылает его местному почтовому отделению, и, в конце концов, почтальон (с забавным акцентом) отдает письмо в руки адресату. Чудесно! :)
Подобно тому, как почтовое отделение определяет, как доставлять письмо, на основе анализа адреса получателя, пакеты в сети доставляются на основе анализа IP адреса. Сам процесс определения маршрута передачи пакета довольно сложен, но основная идея заключается в том, что каждый роутер — это такой же компьютер, у которого имеется таблица маршрутизации, которая определяет, куда отправлять пакеты с определенными адресами назначения, и адресом шлюза по умолчанию, которому надо отправлять пакеты, для которых не нашлось соответствующей записи в таблице маршрутизации. Все это вместе и составляет ту самую “сеть сетей” — интернет.
Настройка таблиц маршрутизации — это задача сетевых администраторов, а не разработчиков (то есть нас). Но если вы хотите больше об этом узнать, то в этой статье из журнала ars technica есть много интересной информации о том, как сети обмениваются пакетами с использованием пиринга и пиринговых соглашений. Также можно еще почитать о таблицах маршрутизации в этом linux faq, и о протоколе граничного шлюза (BGP) в wikipedia, который автоматически определяет, как переправлять пакеты между сетями — что делает интернет по-настоящему распределенной системой с возможностью динамического обхода поврежденных каналов связи.
Виртуальные соединения
Теперь вернемся к теме соединений.
Если вы уже работали с TCP сокетами, то вы знаете, что работа с ними похожа на работу с соединениями, однако, так как TCP работает поверх IP, а IP может только пересылать отдельные пакеты, в TCP должен быть реализован механизм виртуальных соединений.
А если в TCP реализован механизм виртуальных соединений, значит, мы можем реализовать его и с помощью UDP.
Также, давайте определим термин “виртуальное соединение” как обмен UDP пакетами между двумя компьютерами с фиксированной частотой — скажем, десять пакетов в секунду. Пока обмен пакетами продолжается, виртуальное соединение считается установленным.
У соединения есть два конца:
- Первый компьютер ожидает соединения от другого компьютера — этот компьютер будет называться сервером.
- Второй компьютер подключается к серверу с определенным IP адресом и портом. Этот компьютер будет называться клиентом.
В нашем случае только один клиент сможет подключаться к серверу единовременно. В следующих статьях мы доработаем код таким образом, чтобы сервер мог поддерживать сразу несколько соединений. Также мы предполагаем, что сервер всегда будет иметь публичный IP адрес, и клиент может подключаться к нему напрямую. Тему работы через NAT мы также обсудим в следующих статьях.
ID протокола
Так как UDP сам по себе не поддерживает соединения, UDP сокет может принимать пакеты с любого компьютера.
Нам нужно ограничить это поведение таким образом, чтобы сервер принимал пакеты только от своих клиентом, а клиент — только от сервера. И при этом мы не можем просто фильтровать пакеты по адресу отправителя, так как сервер не может знать адреса клиентов заранее. Поэтому в начало каждого UDP пакета мы добавим небольшой заголовок длиной в 32 бита, в котором будет хранится уникальный идентификатор протокола.
[ID протокола типа uint]
(данные пакета...)
Идентификатор протокола — это просто уникальное число, выбранное для нашего протокола. Как только UDP сокет примет пакет, он сразу должен проанализировать первые четыре байта пакета. Если данные не соответствуют нашему идентификатору, то пакет отбрасывается. Если соответствуют, то эти четыре байта обрезаются, и остальные данные пакета передаются на обработку.
Выбрать идентификатор протокола нужно так, чтобы он с достаточной степенью вероятности был уникальным — например, можно взять хеш от названия игры и номера версии протокола. Хотя впрочем, вы можете взять любое число, какое захотите. Смысл всей идеи с точки зрения нашего протокола состоит в том, чтобы отбрасывать пакеты, в которых нет нашего выбранного идентификатора.
Определение наличия соединения
Далее нам необходимо придумать способ определения наличия соединения.
Конечно, мы могли бы придумать какую-нибудь сложную схему с “рукопожатиями” и пересылкой нескольких UDP пакетов туда и обратно. Например, такую: клиент посылает серверу пакет “Запрос соединения”, и сервер отвечаем ему либо пакетом “Соединение установлено”, либо “Занят”, если клиент пытается подключится к серверу, у которого уже есть соединение с другим клиентом.
… или же мы могли бы просто запрограммировать сервер таким образом, чтобы после приема первого пакета с правильным идентификатором протокола он сразу считал, что соединение установлено.
В этом случае клиент может просто начинать пересылать серверу пакеты (считая, что соединение уже установлено), и, когда сервер примет первый пакет, он сохранит IP адрес и порт клиента, и тоже начнет отсылать пакеты.
При этом сам клиент, естественно, заранее знает IP адрес и порт сервера, так как он подключается первым. Поэтому когда клиент получает пакеты в ответ от сервера, он может фильтровать их уже по адресу. Аналогично и сервер после получения первого пакета от клиента может взять адрес и порт клиента из функции “recvfrom”, и фильтровать все остальные пакеты, которые будут приходить не от клиента.
Мы можем воспользоваться такой схемой потому, что у нас имеется только два компьютера для соединения. В будущих статьях мы усовершенствуем нашу реализацию соединений таким образом, чтобы она поддерживала обмен данных между более чем двумя компьютерами (по типу клиент-сервер или peer-to-peer), и усовершенствуем придуманный алгоритм фильтрации соединений.
Но пока не будем усложнять все больше, чем нужно.
Определение отключения
А как нам определить отключение?
Ну, раз уж мы определили подключение как процесс передачи пакетов, то мы можем и определить отключение как отсутствие передачи пакетов.
Чтобы определить, в свою очередь, отсутствие передачи пакетов, мы должны следить за количеством секунд с момента приема последнего пакета от другой стороны, причем на обоих компьютерах.
Каждый раз при приеме пакета от другого компьютера мы обнуляем этот счетчик, а в каждом новом цикле игры мы увеличиваем его значение на количество секунд, прошедших с последнего цикла.
Если счетчик превысит какой-то порог, например, десять секунд, мы считаем это “тайм-аутом” соединения и закрываем его.
Этот алгоритм также учитывает тот случай, когда клиент пытается подключиться к серверу, у которого уже есть соединение с другим клиентом. Так как у сервера уже есть соединение, он отбрасывает все пакеты с других адресов, кроме адреса подключенного клиента, и поэтому второй клиент (тот, который пытается подключится) не получает ответных пакетов от сервера, и его соединение отключается по тайм-ауту.
Заключение
Итак, вот то, что требуется для создания виртуального подключения: алгоритм установки соединения, фильтрация не участвующих в соединении пакетов, и механизм тайм-аутов для определения отключений.
Наше подключение настолько же реально, как и любое TCP подключение, и пакета UDP пакетов, которого оно обеспечивает, вполне достаточно для использования в нашем будущем многопользовательском экшене.
В статье мы также немного разобрали, как работает маршрутизация пакетов в интернете. К примеру, мы узнали причину, по которой UDP пакеты иногда приходят не в правильном порядке — потому что они могут пойти разными маршрутами на уровне IP. Посмотрите на карту интернета — не чудо ли, что пакеты вообще куда-либо доходят? Если вы хотите получше разобраться во всем этом, хорошей отправной точкой может стать эта статья на wikipedia.
Теперь, когда у нас есть механизм виртуальных подключений по UDP, мы можем легко реализовать обмен данными между клиентом и сервером для нашей многопользовательской игры — и без использования TCP.
Пример реализации вы можете посмотреть в исходном коде для этой статьи.
Это простое клиент-серверное приложение, которое производит обмен пакетами с частотой в 30 пакетов в секунду. Вы можете запустить сервер на любой машине, но с публичным IP адресом, так как “проброс” пакетов через NAT пока еще не поддерживается.
Запустить клиент можно следующим образом:
./Client 205.10.40.50
В этом случае он будет пытаться подключиться к серверу по адресу, который вы укажете в командной строке. По умолчанию, если вы не укажете ничего, он будет пытаться подключиться к 127.0.0.1.
Если один клиент будет подключен к серверу, вы можете попытаться запустить еще одного клиента, и тогда вы увидите, что он не сможет подключиться — так и задумано. В данной реализации к серверу может быть подключен только один клиент.
Также вы можете попробовать остановить клиент или сервер, когда между ними установлено подключение, и тогда вы заметите, что через десять секунд приложение на другой стороне отключится по тайм-ауту. Когда отключается клиент, управление возвращается командной оболочке, а когда отключается сервер — он возвращается в состояние ожидания подключений от других клиентов.
Автор: bvasilyev
