От переводчика: У меня возникла необходимость разобраться с работой UDP-сокетов в неблокирующем режиме в java и создать свой собственный класс для работы с сетевыми соединениями на их основе. К сожалению, толковой русскоязычной документации на эту тему я не нашёл. Зато наткнулся на несколько попыток на хабре осветить тему создания надёжного соединения поверх UDP. В том числе и перевод нескольких статей Гленна Фидлера, сделанный пользователем bvasilyev. И хотя статьи рассматривают создание подобного подключения для применения его в играх (не совсем то, что мне необходимо), а также языком реализации является не java, а c++, они стали для меня отправной точкой. К сожалению bvasilyev около года назад прервал перевод данного цикла, а самое интересное осталось на языке оригинала. Поэтому я решил перевести четвёртую статью цикла и переписать реализацию виртуального соединения из третей статьи цикла на java (чуть позже выложу). Ну а для того, чтоб данной статьёй мог воспользоваться кто-либо, кроме меня, выкладываю её здесь. Профессиональным переводом, к сожалению, никогда не занимался, всегда изучал англоязычную документацию. Но в данном случае, из-за многочисленного употребления некоторых слов в совершенно различных значениях, а также в роли наименования всевозможных определений, неоднократно — в пределах одного предложения, счёл более целесообразным осуществить перевод, а после уже работать с текстом на привычном для себя языке. Поправки и аргументированные предложения приветствуются.
Первая статья
Вторая статья
Третья статья
(напомню: переведены bvasilyev)
Надежность, упорядочивание и избежание перегрузок поверх UDP
Вступление
Привет, меня зовут Гленн Фидлер и я приветствую вас в своей четвёртой статье из цикла “Сетевое программирование для разработчиков игр”.
В предыдущей статье, мы создали свою собственную концепцию виртуального соединения на основе UDP.
Теперь мы будем добавлять надёжность, упорядоченность и предотвращение перегрузок к нашему виртуальному UDP соединению.
Это, безусловно, самая сложная часть низкоуровневой сетевой работы в играх, так что эта статья будет весьма насыщенной, поэтому пристегнулись и поехали!
Проблемы с TCP
Те из вас, кто знаком с TCP, знают, что он уже имеет свою внутреннюю концепцию соединений, с надёжной и упорядоченной системой передачи пакетов и предотвращением перегрузок, так зачем же мы пишем свою собственную мини версию TCP на основе UDP?
Проблема в том, что мультиплеерные игры жанра «Action» опираются на постоянный поток пакетов, отправляемых с частотой от 10 до 30 пакетов в секунду, и по большей части, данные, содержащиеся в эти пакеты настолько чувствителен ко времени, что только самые свежие данные полезны. Это включает в себя данные с устройств ввода игроков, ориентацию положение и скорость каждого персонажа, и состояние физики объектов игрового мира.
Проблемой TCP является его абстрактная доставка данных в угоду надежного упорядоченного потока. Из-за этого, если пакет теряется, TCP должен остановиться и ждать повторной пересылки данного пакета. Это прерывает постоянный поток пакетов, из-за чего более поздние пакеты должны ждать в очереди до тех пор, пока повторно отправленный пакет не будет получен, что даёт возможность выстроить пакеты в правильном порядке.
Что нам нужно, так это другой тип надежности. Вместо того, чтобы рассматривать все данные как надёжно упорядоченный поток, мы хотим, отправлять пакеты с постоянной скоростью и получать уведомления, о их приёме другим компьютером. Это позволяет доставлять чувствительные ко времени данные не дожидаясь повторно отправленных пакетов, в то же время предоставляя нам возможность принимать решения о том, как обрабатывать потерю пакетов на уровне приложений.
Создать надёжную систему с заданными свойствами используя TCP не представляется возможным, поэтому у нас нет иного выхода, кроме как создать свою собственную поверх UDP.
К сожалению, надежность не единственное, что мы должны переписать. Это потому, что TCP также обеспечивает предотвращение перегрузки, так что он может динамически изменять скорость передаваемых данных, в соответствии с свойствами соединения. Например, TCP посылает меньше данных используя модем 28.8k, чем это было бы по линии T1, и он в состоянии делать это, не зная заранее, типа соединения!
Порядковые номера
Теперь вернемся к надежности!
Цель нашей системы надежности проста: мы хотим знать, какие пакеты достигают другой стороны соединения.
Во-первых, нам нужен способ идентифицировать пакеты.
Что, если мы добавим понятие «идентификатор пакета»? Пускай это будет целым числом. Мы могли бы начать это с нуля, и с каждым пакетом, который мы посылаем, увеличивать это число на единицу. Первый пакет, который мы отправили бы, был бы «пакет 0», а 100-й отправленный пакет — «пакет 99».
На самом деле это довольно распространенный метод. Это даже используется в TCP! Эти пакетные идентификаторы называются порядковыми номерами. И хоть мы не собираемся реализовать надежность именно так, как это делает TCP, имеет смысл использовать ту же терминологию, поэтому, с этого момента, мы будем называть их порядковыми номерами.
Поскольку UDP не гарантирует порядка пакетов, 100 принятых пакетов не обязательно означает, что 100 пакетов отправлено. Отсюда следует, что нам нужно вставить порядковый номер где-то в пакете, так что б компьютер на другом конце соединения знал, какой именно этот пакет.
У нас уже есть простой заголовок пакета для виртуального соединения из предыдущей статьи, так что мы просто добавим порядковый номер в заголовок. Выглядеть это будет так:
[uint protocol id]
[uint sequence]
(packet data…)
Теперь, когда компьютер на другой стороне соединения получает пакет, он знает его порядковый номер, присвоенный компьютером-отправителем.
Acks
Теперь, когда мы можем идентифицировать пакеты используя порядковые номера, наш следующий шаг состоит в том, чтобы другая сторона соединения знала, какие пакеты мы получаем.
Логически это довольно просто, нужно всего лишь принять к сведению порядковый номер каждого полученного пакета, и отправить эти порядковые номера обратно на компьютер, который послал их.
Поскольку мы постоянно обмениваемся пакетами между двумя машинами, мы можем просто добавить ack в заголовок пакета, как мы это сделали с порядковым номером:
[uint protocol id]
[uint sequence]
[uint ack]
(packet data...)
Наш общий подход заключается в следующем:
- Каждый раз, когда мы посылаем пакет мы увеличиваем локальный порядковый номер.
- Когда мы получаем пакет, мы сравниваем порядковый номер пакета с порядковым номером недавно принятого пакета, называемый удалённым порядковым номером. Если номер принятого пакета больше, мы обновляем удаленный порядковый номер и устанавливаем его равным порядковому номеру принятого пакета.
- Когда мы составляем заголовки пакетов, локальный порядковый номер становится порядковым номером пакета, а удаленный порядковый номер становится ack.
Эта простая ack система работает при условии, что на каждый пришедший пакет есть отправленный пакет.
Но что делать, если пакеты идут так, что два пакета прибыли прежде, чем мы отправим пакет? У нас есть место только для одного ack на пакет, так что же нам делать?
Теперь рассмотрим случай, когда одна сторона соединения посылает пакеты более быстрыми темпами. Если клиент отправляет 30 пакетов в секунду, а сервер посылает лишь 10 пакетов в секунду, мы должны, поместить по крайней мере 3 ack в каждом пакете, отравленном с сервера.
Давайте ещё более усложним! Что если пакет, содержащий ack, утерян? Компьютер, который послал исходный пакет будет думать, что он затерялся, тогда как на самом деле он был получен!
Похоже, мы должны сделать нашу надежную систему… более надежной!
Надёжные Acks
Здесь мы отойдём от протокола TCP.
Что делает TCP удерживая сдвигающееся окно для ack отправленного с пакетом со следующим порядковым номером — он ожидает получить его в заданном порядке. Если протокол TCP не получает подтверждение приема ack для данного пакета, он останавливается и отправляет пакет с этим порядковым номером снова. Это именно то поведение, которого мы хотим избежать!
Таким образом, в нашей надежной системе, мы никогда повторно не отправим пакет с данным порядковым номером. Мы отсылаем пакет с номером n ровно один раз, далее мы посылаем n + 1, n + 2 и так далее. Если пакет n был потерян, то мы никогда не остановимся чтобы отправить его повторно, мы оставим этоо приложению для того, чтоб оно сформировало новый пакет, содержащий данные, которые были потеряны, если это необходимо, и этот пакет отправляется с новым порядковым номером.
Так как мы делаем вещь отличную от TCP, то теперь возможны пропуски (дыры) в наборе пакетов для которых мы отправляем ack, так что теперь уже не достаточно просто передавать порядковый номер последнего пакета, который мы получили.
Мы должны поместить несколько ack в один пакет.
Сколько ack нам необходимо?
Как упоминалось ранее, мы имеем случай, когда одна сторона соединения посылает пакеты быстрее, чем другая. Давайте предположим, что в худшем случае одна сторона отправляет не менее 10 пакетов в секунду, в то время как другая не более 30. В этом случае, среднее число ack которое нам необходимо в каждом пакете 3, но если пакеты приходят небольшими кучами, то нам может понадобиться больше. Допустим, 6-10 в худшем случае.
Как быть с теми ack, которые не были получены из-за того, что пакет, содержащий их, был утерян?
Чтобы решить эту проблему, мы собираемся использовать классическую сетевую стратегию использования избыточности, чтобы победить потерю пакетов!
Пускай каждый пакет содержит 33 ack, и это будет не возможность содержать до 33, а всегда 33. Таким образом, для любого определённого ack, мы с избыточностью отправим его до 32 дополнительных раз, в том случае, если один пакет с ack не смог пройти!
Но как мы можем отправить 33 подтверждения в пакете? Ведь по 4 байта на каждый ack это 132 байта!
Хитрость заключается в том, чтобы представлять идущие до “ack” 32 других ack при помощи битового поля:
[uint protocol id]
[uint sequence]
[uint ack]
[uint ack bitfield]
(packet data...)
Мы определим «битовое поле ack» так, что каждый его бит соответствует ack тех 32-х порядковых номеров, которые идут перед нашим «ack». Пускай наш «ack» 100. Если первый бит «битового поля ack» установлен, то пакет также включает в себя ack для пакета 99. Если второй бит установлен, то будет подтверждён и пакет 98. Это проходит весь путь из 32 бит до пакета 68.
Наш скорректированный алгоритм будет выглядеть следующим образом:
- Каждый раз, когда мы посылаем пакет мы увеличиваем локальный порядковый номер.
- Когда мы получаем пакет, мы сравниваем порядковый номер пакета с удалённым порядковым номером. Если номер принятого пакета больше, мы обновляем удаленный порядковый номер и устанавливаем его равным порядковому номеру принятого пакета.
- Когда мы составляем заголовки пакетов, локальный порядковый номер становится порядковым номером пакета, а удаленный порядковый номер становится ack. Битовое поле ack рассчитывается просмотром очереди из 33 пакетов, содержащих порядковые номера в диапазоне [удаленный порядковый номер – 32, удаленный порядковый номер]. Мы устанавливаем бит n в битовом поле ([1,32]) в «1» если порядковый номер пакета равный «удалённый порядковый номер – n» находится в очереди полученных.
- Кроме того, когда получен пакет, сканируется битовое поле ack, и если бит n установлен, то мы подтверждаем порядковый номер пакета n, если он не был подтверждён до этого.
С этой улучшенной версией алгоритма вам придётся потерять 100% пакетов на протяжении более чем секунды для того, чтоб начались потери ack.
Обнаружение потерянных пакетов
Теперь, когда мы знаем, что пакеты получены другой стороной соединения, как мы обнаружим потерю пакетов?
Хитрость здесь в том, что ack возвращаются к нам, и мы говорим: если мы не получили подтверждения в течение определённого времени, значит пакет считается потерянным.
Учитывая то, что мы посылаем не более 30 пакетов в секунду, и мы избыточно отправляем подтверждение примерно 30 раз, если вы не получаете ack для пакета в течение одной секунды, то очень вероятно, что пакет был потерян.
Итак, при таком трюке с битами, мы можем быть на 100% уверены в том, какие пакеты дошли и с достаточной долей уверенности предполагать тот набор пакетов, который не был получен.
Следствием этого является то, что все данные, которые вы повторно отправляете с помощью этой техники надежности, должны иметь свой собственный идентификатор сообщения, так что если вы получите их несколько раз, вы можете отказаться от них. Это может быть сделано на уровне приложения.
Обработка обнуления порядковых номеров
Обсуждение порядковых номеров и подтверждений не будет полным без освещения вопроса обнуления порядковых номеров!
Порядковые номера и ack – 32-битные целые числа без знака, поэтому они находятся в диапазоне [0,4294967295]. Это очень большое количество! Настолько большое, что если вы посылаете 30 пакетов в секунду, то потребуется более четырех с половиной лет для исчерпания этого диапазона и необходимости обнуления порядковых номеров.
Но, возможно, вы хотите, сэкономить полосу пропускания, и сократить ваши порядковые номера и ack до 16-битных целых чисел. Вы экономите 4 байта в каждом пакете, но теперь диапазон будет исчерпан всего за полчаса!
Так как мы справимся с этим?
Хитрость заключается в том, чтобы понять, что, если текущий порядковый номер уже очень велик, а следующий порядковый номер, который поступил, очень мал, то вы должны начать повторный отсчёт порядковых номеров. Так что, хотя новый порядковый номер численно меньше, чем текущее значение порядкового номера, на самом деле он представляет собой более поздний пакет.
Например, предположим, что мы кодируем порядковые номера одним байтом (не рекомендуется кстати :)), тогда их обнуление произошло бы после 255:
... 252, 253, 254, 255, 0, 1, 2, 3, ...
Чтобы справиться в этом случае нам нужна новая функция, которая знает о том, что порядковые номера обнулятся после 255, так что 0, 1, 2, 3, считаются более поздними, чем 255. В противном случае, наша система надежности перестает работать после получения пакета 255.
Вот эта функция:
bool sequence_more_recent( unsigned int s1,
unsigned int s2,
unsigned int max)
{
return
( s1 > s2 ) &&
( s1 - s2 <= max/2 )
||
( s2 > s1 ) &&
( s2 - s1 > max/2 );
}
Эта функция работает путем сравнения двух чисел и их разности. Если их разность меньше половины максимального значения порядкового номера, то они должны быть близко друг к другу — таким образом, мы просто проверяем, больше ли одно число чем другое, как обычно. Однако, если они далеко друг от друга, их разность будет больше, чем половина максимального значения порядкового номера, тогда, парадоксальным образом, мы будем считать меньший порядковый номер, чем текущий порядковый номер, более поздним.
Это прозрачным образом позволяет обрабатывать обнуление порядковых номеров, таким образом 0,1,2 считаются более поздними чем 255.
Так просто и элегантно!
Убедитесь, что вы включили это в любую обработку последовательностей порядковых номеров, которую вы делаете.
Предотвращение перегрузки
В то время как мы решили вопросы с надежностью, есть еще вопрос предотвращения перегрузки. TCP обеспечивает предотвращение перегрузки как часть пакета надежности TCP, но UDP не имеет никаких средств предотвращений перегрузки!
Если мы просто будем посылать пакеты без какого-либо контроля потока, мы рискуем зафлудить соединение и вызывать сильную задержку (более двух секунд!), так как буфера маршрутизаторов между нами и другим компьютером будут перегружены. Так произойдёт потому, что маршрутизаторы будет очень стараться доставить все отправленные нами пакеты и поэтому будут помещать их в очередь буфера до тех пор, пока не посчитают, что пакеты пора отбрасывать.
Хотя было бы неплохо, если бы мы могли сказать маршрутизаторам, что наши пакеты очень чувствительны к временным задержкам и должны быть отброшены вместо буфферизации если маршрутизатор перегружен, мы не можем сделать это без переписывания программного обеспечения для всех маршрутизаторов в мире!
Так вместо этого, мы должны сосредоточиться на том, что мы можем реально сделать что бы избежать переполнения канала связи в первую очередь.
Способ сделать это — реализовать наш собственный основной алгоритм предотвращения перегрузки. И я подчеркиваю — основной! Так же как и с надежностью, у нас нет надежды с первой попытки придумать что-то подходящее чем в TCP, так что давайте делать его как можно более простым.
Измерение времени прохождения (Round Trip Time – RTT)
Поскольку всё предотвращение перегрузки сводится к тому, чтобы избежать перегрузки соединения и повышения времени прохождения (RTT), то выходит, что наиболее важным показателем перегружаем мы канал или нет, является само RTT.
Нам нужен способ для измерения RTT нашего соединения.
Вот основная техника:
- Для каждого отправляемого пакета, мы добавляем запись, содержащюю кроме порядкового номера пакета ещё и время его отправления.
- Каждый раз, когда мы получаем ack, мы смотрим эту запись и находим разницу по локальному времени между временем получения ack, и временем отправки пакета. Это время RTT для этого пакета.
- Т.к. приход пакетов варьируется с джиттером (джиттер — фазовое дрожание цифрового сигнала данных — нежелательные фазовые и/или частотные случайные отклонения передаваемого сигнала) сети, мы должны сгладить это значение, чтобы обеспечить показатель, имеющий практическое значение, так что каждый раз, когда мы получаем новый RTT мы вычисляем в процентном соотношении разницу между нашим текущим RTT и RTT пакета. 10%, по моему мнению, кажется хорошим на практике. Это называется экспоненциально сглаженное скользящее среднее, и это имеет эффект сглаживания отклонений в RTT.
- Для того, чтобы очередь отправленных пакетов не росла постоянно, мы будем отменять отправку пакетов, когда они превысят некоторое максимально ожидаемое RTT. Как уже говорилось в предыдущем разделе о надёжности, довольно вероятно, что любой пакет, на который в течение секунды не пришёл ack, был потерян, поэтому одна секунда – это хорошее значение для максимума RTT.
Теперь у нас есть RTT и мы можем использовать его в качестве метрики, чтобы вести наше предотвращение перегрузки. Если RTT становится слишком большим, мы отправляем данные реже, если оно в допустимых пределах, мы можем попытаться отправить данные чаще.
Простое двоичное предотвращение перегрузки
Как уже говорилось ранее, давайте не будем ненасытными, мы реализуем очень простое предотвращение перегрузки. Это предотвращение перегрузки имеет два режима. Хороший и плохой. Я называю это простым двоичным предотвращением перегрузки.
Давайте предположим, что вы посылаете пакеты определенного размера, скажем, 256 байт. Вы хотели бы отправить эти пакеты в 30 раз в секунду, но если условия плохие, вы можете снизить темп отправки до 10 раз в секунду.
Так пакеты по 256 байт 30 раз в секунду дадут скорость около 64 кбит/сек, и 10 раз в секунду примерно в 20 кбит/сек. Не существует в мире широкополосного подключения к сети, которые не может справиться, по крайней мере с 20kbit/сек, так что мы будем двигаться вперед с этим допущением. В отличие от TCP, который приспособлен вообще для любого устройства с любой полосой пропускания приема/передачи, мы собираемся сделать минимальное допущение пропускной способности для устройств, участвующих в нашем соединении.
Таким образом, основная идея заключается в следующем. Когда сетевые условия «хорошие» мы отправляем 30 пакетов в секунду, и когда сетевые условия «плохие» мы опускаемся до 10 пакетов в секунду.
Конечно, вы можете определить «хорошо» и «плохо» так, как вам нравится, но я получил хорошие результаты, учитывая только RTT. Например, если RTT превышает некоторый порог (скажем, 250ms), то вы знаете, что вероятно перегружаете соединение. Конечно, это предполагает, что никто не будет превышать 250 мс, в обычных условиях без перегрузки соединения, которые являются разумными, учитывая наши требования к широкополосной связи.
Как переключаться между хорошо и плохо? Алгоритм, который мне нравится использовать, работает следующим образом:
- Если вы в настоящее время в хорошем режиме, и условия ухудшаются, сразу же переходите в плохой режим.
- Если вы находитесь в плохом режиме, и условия были хорошими для определенного периода времени 't', тогда возвращаетесь в хороший режим.
- Чтобы избежать быстрого переключения между хорошим и плохим режимами, если вы перешли из хорошего режима в плохой за 10 секунд, удвойте время 't', через которое плохой режим сможет вернуться к хорошему. Ограничьте максимальное значение времени 't' каким-то максимумом, скажем, 60 секунд.
- Чтобы избежать обрыва хорошего режима связи, когда он имеет кратковременные периоды плохого соединения, за каждые 10 секунд, которые соединение находится в хорошем режиме, вдвое сокращайте время 't'. Ограничьте минимальное значение времени 't' каким-то минимумом, скажем, 1 секунда.
С этим алгоритмом вы будете быстро реагировать на плохие условия и снизите частоту отправки пакетов до 10 в секунду, избегая перегрузки канала. Вы также будете консервативно пытаться перейти в хороший режим, и сохранять более высокую частоту отправки пакетов — 30 в секунду, в то время как сетевые условия хорошие.
Конечно, вы можете реализовать гораздо более сложные алгоритмы. Так % потери пакетов может быть принят во внимание, как метрика и, даже, значение сетевого джиттера (время дисперсии в пакетных подтверждениях), а не только RTT.
Вы также можете проявить больше жадности с предотвращениями перегрузки, и попытаться узнать, когда вы можете отправить данные на гораздо более высокой пропускной способности (например, LAN), но вы должны быть очень осторожны! С увеличением жадности возникает больший риск перегрузки соединения!
Вывод
Наша новая система надежности позволяет нам отправлять устойчивый поток пакетов и уведомляет нас, какие пакеты были получены. Из этого мы можем делать выводы о потерянных пакетах и заново отправить данные, которые не были получены, если это необходимо.
Поверх этого у нас есть простая система предотвращения перегрузки, которая осуществляет переключение между отправкой пакетов 10 и 30 раз в секунду, в зависимости от сетевых условий, поэтому мы не перегружаем соединение.
Есть много реализаций слишком специфических деталей, чтоб упоминать их в этой статье, поэтому убедитесь, что вы просмотрите исходный код примера, чтобы увидеть, как все это реализуется.
Надежность, упорядочивание и предотвращения перегрузки, пожалуй, самый сложный аспект сетей низкого уровня.
Автор: fanta_clauss
