Анализ принципа работы сетевого протокола передачи kcp

TCP/IP

1 Обзор

При разработке игр, особенно игр MOBA (многопользовательская онлайн-арена), необходимо контролировать задержку. Но для традиционного TCP (дружественного к сети, отличного) он не способствует передаче пакетов в реальном времени, потому что его повторная передача тайм-аута и контроль перегрузки удобны для сети, и нет никаких преимуществ для производительности наших пакетов в реальном времени. . Поэтому, как правило, необходимо реализовать набор собственных сетевых протоколов на основе UDP для обеспечения надежной передачи пакетов в режиме реального времени. На самом деле, это значит пожертвовать удобством TCP, пожертвовать пропускной способностью и обменять пространство на время. На основе UDP в Интернете есть несколько отличных протоколов, таких как KCP. Сегодня мы кратко рассмотрим, как это реализовано и как его можно интегрировать в наши существующие проекты.Git-адрес автора проекта

2. Принцип реализации

KCP представляет собой простую реализацию алгоритма и не включает никаких базовых вызовов. Нам нужно только зарегистрировать функцию обратного вызова KCP при вызове системы UDP, и тогда ее можно будет использовать. Таким образом, его можно понимать как протокол прикладного уровня. Сравните TCP:

  • Удвойте RTO TCP. Концепция ужасает. ККП в 1,5 раза.
  • Выборочная повторная передача, при которой передаются только потерянные пакеты.
  • Быстрая повторная передача, не будет ждать до времени ожидания. Перезагрузка по умолчанию
  • TCP задержит отправку ACK. ККП можно установить
  • Безконцессионное управление потоком. Окно отправки может зависеть только от размера буфера отправки и оставшегося размера буфера приема в приемнике.

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

3. Анализ исходного кода

Прежде всего, мы должны пойти на github, чтобы увидеть, как его использовать, прежде чем анализировать. На самом деле это очень просто: инициализация объекта kcp и последующая реализация функции обратного вызова на самом деле реализуют его собственный базовый системный вызов UDP. Каждый раз, когда мы отправляем пакет через KCP, он будет вызывать этот callback. После того, как UDP получит пакет, вызовите функцию ikcp_input. Наконец, нам нужно только отправлять и получать данные через ikcp_send и ikcp_recv.

Прежде чем смотреть на код, посмотрите на структуру пакета KCP, Segement

struct IKCPSEG
{
   struct IQUEUEHEAD node;
   IUINT32 conv;     //会话编号，两方一致才会通信
   IUINT32 cmd;      //指令类型，四种下面会说
   IUINT32 frg;      //分片编号 倒数第几个seg。主要就是用来合并一块被分段的数据。
   IUINT32 wnd;      //自己可用窗口大小    
   IUINT32 ts;
   IUINT32 sn;       //编号 确认编号或者报文编号
   IUINT32 una;      //代表编号前面的所有报都收到了的标志
   IUINT32 len;
   IUINT32 resendts; //重传的时间戳。超过当前时间重发这个包
   IUINT32 rto;      //超时重传时间，根据网络去定
   IUINT32 fastack;  //快速重传机制，记录被跳过的次数，超过次数进行快速重传
   IUINT32 xmit;     //重传次数
   char data[1];     //数据内容
};

KCP через эти поля пакетов данных стабильная связь может быть сделана для разных точек оптимизации. Из вышеуказанных полей можно увидеть KCP, достигаемый с помощью селективного ACK UNA и RETRANSMISSE.

Сначала посмотрим на логику отправки пакетов, мы будем вызывать метод ikcp_send.

Этот метод сначала оценивает поток kcp. И попробуйте дописать пакет к предыдущему абзацу, если это возможно. В противном случае выполняется передача фрагмента.

    if (len <= (int)kcp->mss) count = 1;
     else count = (len + kcp->mss - 1) / kcp->mss;
     if (count >= (int)IKCP_WND_RCV) return -2;
     if (count == 0) count = 1;
     // fragment
     for (i = 0; i < count; i++) {
         int size = len > (int)kcp->mss ? (int)kcp->mss : len;
         seg = ikcp_segment_new(kcp, size);
         assert(seg);
         if (seg == NULL) {
             return -2;
         }
         if (buffer && len > 0) {
             memcpy(seg->data, buffer, size);
         }
         seg->len = size;
         seg->frg = (kcp->stream == 0)? (count - i - 1) : 0;
         iqueue_init(&seg->node);
         iqueue_add_tail(&seg->node, &kcp->snd_queue);
         kcp->nsnd_que++;
         if (buffer) {
             buffer += size;
         }
         len -= size;
     }

     return 0;

В приведенной выше логике кода count на самом деле является количеством осколков пакета. Затем выполните цикл для создания сегмента.Структура данных сегмента в основном предназначена для сохранения информации о пакете фрагмента. Например, eg->frg сохраняет номер текущего шарда. звонить послеiqueue_add_tailМетод передает сегмент в очередь отправки. Эти методы реализуются через определения макросов. По сути, это операция со связанным списком. Очередь — это двусвязный список. Логика проста. Затем на этом этапе осколки данных помещаются в очередь. Где реализована конкретная логика отправки? Продолжайте смотреть вниз.

Давайте посмотрим на логику обратного вызова, который на самом деле является методом ikcp_output, который будет вызываться в ikcp_flush. То есть, чем занимается ikcp_output, так это окончательная передача данных. Как это управляется? Сначала я рассмотрю этот метод.

  1. Этот метод сначала отправляет подтверждение. Перебрать все acks. Вызовите метод ikcp_output для отправки.
    count = kcp->ackcount;
     for (i = 0; i < count; i++) {
         size = (int)(ptr - buffer);
         if (size + (int)IKCP_OVERHEAD > (int)kcp->mtu) {
             ikcp_output(kcp, buffer, size);
             ptr = buffer;
         }
         ikcp_ack_get(kcp, i, &seg.sn, &seg.ts);
         ptr = ikcp_encode_seg(ptr, &seg);
     }

     kcp->ackcount = 0;
  1. Определите, требуется ли в данный момент обнаружение окна, потому что, если окно равно 0, данные не могут быть отправлены, поэтому необходимо выполнить обнаружение окна. После обнаружения, при необходимости, установите время окна обнаружения. Отправьте запрос на проверку окна или запрос на восстановление окна. Главное — запросить размер окна пира и сообщить размер удаленного окна.
if (kcp->rmt_wnd == 0) {
   if (kcp->probe_wait == 0) {
      kcp->probe_wait = IKCP_PROBE_INIT;
      kcp->ts_probe = kcp->current + kcp->probe_wait;
   }  
   else {
      if (_itimediff(kcp->current, kcp->ts_probe) >= 0) {
         if (kcp->probe_wait < IKCP_PROBE_INIT) 
            kcp->probe_wait = IKCP_PROBE_INIT;
         kcp->probe_wait += kcp->probe_wait / 2;
         if (kcp->probe_wait > IKCP_PROBE_LIMIT)
            kcp->probe_wait = IKCP_PROBE_LIMIT;
         kcp->ts_probe = kcp->current + kcp->probe_wait;
         kcp->probe |= IKCP_ASK_SEND;
      }
   }
}  else {
   kcp->ts_probe = 0;
   kcp->probe_wait = 0;
}

Поместите результат в сегмент, когда закончите. .

  1. Расчет доступного размера окна для этой передачи определяется несколькими факторами, и KCP можно настроить выборочно. Вы можете не включать окно управления потоком.
  2. Помещение сообщения из очереди отправки в буфер отправки фактически является окном отправки. То есть все отправленные данные будут находиться в этом буфере. Перед отправкой данных также необходимо установить соответствующие времена повторной передачи и интервал.
    while (_itimediff(kcp->snd_nxt, kcp->snd_una + cwnd) < 0) {
         IKCPSEG *newseg;
         if (iqueue_is_empty(&kcp->snd_queue)) break;
         newseg = iqueue_entry(kcp->snd_queue.next, IKCPSEG, node);
         iqueue_del(&newseg->node);
         iqueue_add_tail(&newseg->node, &kcp->snd_buf);
         kcp->nsnd_que--;
         kcp->nsnd_buf++;
         newseg->conv = kcp->conv;
         newseg->cmd = IKCP_CMD_PUSH;
         newseg->wnd = seg.wnd;
         newseg->ts = current;
         newseg->sn = kcp->snd_nxt++;
         newseg->una = kcp->rcv_nxt;
         newseg->resendts = current;
         newseg->rto = kcp->rx_rto;
         newseg->fastack = 0;
         newseg->xmit = 0;
     }

Эта логика относительно проста, по сути, seg берется из очереди окна отправки. Затем установите соответствующие параметры. И обновите буферную очередь. и размер буферной очереди. Если установлен узел, время повторной передачи *2 становится равным 1,5.

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

Логика тоже очень проста

  • Если пакет передается впервые, отправьте его напрямую.
  • Если время повторной передачи пакета достигнуто, передайте его снова и запишите флаг потери.
  • Если количество пропусков превышает фастэк, повторите передачу.

По сути, lost и change — это поля, используемые для обновления размера окна. И два алгоритма обновления разные.

if (segment->xmit == 0) {
   needsend = 1;
   segment->xmit++;
   segment->rto = kcp->rx_rto;
   segment->resendts = current + segment->rto + rtomin;
}
else if (_itimediff(current, segment->resendts) >= 0) {
   needsend = 1;
   segment->xmit++;
   kcp->xmit++;
   if (kcp->nodelay == 0) {
      segment->rto += kcp->rx_rto;
   }  else {
      segment->rto += kcp->rx_rto / 2;
   }
   segment->resendts = current + segment->rto;
    //记录包丢失
   lost = 1;
}
else if (segment->fastack >= resent) {
   if ((int)segment->xmit <= kcp->fastlimit || 
      kcp->fastlimit <= 0) {
      needsend = 1;
      segment->xmit++;
      segment->fastack = 0;
      segment->resendts = current + segment->rto;
      //用来标示发生了快速重传  
      change++;
   }
}

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

Прочитав этот метод сброса, мы в основном понимаем логику отправки данных. Тогда посмотрите, где он это называет.

На самом деле, он вызывается в методе ikcp_update.Этот метод должен вызываться неоднократно прикладным уровнем.Как правило, это может быть 10 мс и 100 мс.Время будет определять характер передачи данных в реальном времени. Другими словами, он будет периодически обновлять данные очереди, чтобы оценить окно отправки или данные, которые необходимо повторно передать, и отправить данные через базовый UDP. В этом методе нет никакой логики.

void ikcp_update(ikcpcb *kcp, IUINT32 current)
{
     IINT32 slap;
     kcp->current = current;
     if (kcp->updated == 0) {
         kcp->updated = 1;
         kcp->ts_flush = kcp->current;
     }
     slap = _itimediff(kcp->current, kcp->ts_flush);
     if (slap >= 10000 || slap < -10000) {
         kcp->ts_flush = kcp->current;
         slap = 0;
     }
     if (slap >= 0) {
         kcp->ts_flush += kcp->interval;
         if (_itimediff(kcp->current, kcp->ts_flush) >= 0) {
             kcp->ts_flush = kcp->current + kcp->interval;
         }
         ikcp_flush(kcp);
     }
}

Давайте посмотрим на базовый метод приема данных ikcp_input.

Этот метод вызывается после того, как базовый UDP получил сетевые данные. По сути, это анализ соответствующих данных. В KCP существует четыре основных формата сообщений: сообщение ACK, сообщение данных, сообщение окна обнаружения и сообщение окна ответа.

  1. Первый заключается в анализе соответствующих данных заголовка, которые составляют около 24 байт.
data = ikcp_decode8u(data, &cmd);
data = ikcp_decode8u(data, &frg);
data = ikcp_decode16u(data, &wnd);
data = ikcp_decode32u(data, &ts);
data = ikcp_decode32u(data, &sn);
data = ikcp_decode32u(data, &una);
data = ikcp_decode32u(data, &len);
size -= IKCP_OVERHEAD;


kcp->rmt_wnd = wnd;
ikcp_parse_una(kcp, una);
ikcp_shrink_buf(kcp);

Затем вызовите методы ikcp_parse_una и ikcp_shrink_buf в соответствии с полями. Первый заключается в анализе una, чтобы определить, какие другие стороны получили отправленные пакеты данных. Если получено непосредственно повторно принять окно для удаления. Последний — send_una для обновления kcp. send_una означает, что было подтверждено получение предыдущего пакета.

  1. Если это команда ACK, она фактически выполняет некоторую обработку.

ikcp_update_ack предназначен в основном для обновления некоторых параметров kcp, включая rtt и rto, Прежде всего, метод ikcp_parse_ack предназначен в основном для удаления соответствующего сегмента в очереди на отправку согласно sn. Затем обновите максак и время и запишите лог

if (cmd == IKCP_CMD_ACK) {
   if (_itimediff(kcp->current, ts) >= 0) {
      ikcp_update_ack(kcp, _itimediff(kcp->current, ts));
   }
   ikcp_parse_ack(kcp, sn);
   //根据snd队列去更新una     
   ikcp_shrink_buf(kcp);
   if (flag == 0) {
      flag = 1;
      maxack = sn;
      latest_ts = ts;
   }  else {
      if (_itimediff(sn, maxack) > 0) {
      #ifndef IKCP_FASTACK_CONSERVE
        //记录最大ACK
         maxack = sn;
         latest_ts = ts;
      #else
         if (_itimediff(ts, latest_ts) > 0) {
            maxack = sn;
            latest_ts = ts;
         }
      #endif
      }
   }
//打印日志
}
  1. Если пакет данных получен, логика на самом деле очень проста.Это обнаружение данных и помещение действительных данных в очередь приема.Во-первых, нужно определить, является ли пакет данных действительным.Если это так, построить сегмент. Вставьте данные. , а затем вызовите метод ikcp_parse_data. Логика этого метода также относительно проста, по сути, заключается в том, чтобы судить, является ли он действительным, если он был получен, он будет отброшен, в противном случае он будет вставлен в очередь приема в соответствии с sn (номером) .
else if (cmd == IKCP_CMD_PUSH) {
   if (ikcp_canlog(kcp, IKCP_LOG_IN_DATA)) {
      ikcp_log(kcp, IKCP_LOG_IN_DATA, 
         "input psh: sn=%lu ts=%lu", (unsigned long)sn, (unsigned long)ts);
   }
   if (_itimediff(sn, kcp->rcv_nxt + kcp->rcv_wnd) < 0) {
      ikcp_ack_push(kcp, sn, ts);
      if (_itimediff(sn, kcp->rcv_nxt) >= 0) {
         seg = ikcp_segment_new(kcp, len);
         seg->conv = conv;
         seg->cmd = cmd;
         seg->frg = frg;
         seg->wnd = wnd;
         seg->ts = ts;
         seg->sn = sn;
         seg->una = una;
         seg->len = len;
         if (len > 0) {
            memcpy(seg->data, data, len);
         }
         ikcp_parse_data(kcp, seg);
      }
   }
}
  1. Если это пакет, который запрашивает размер окна. На самом деле это метка, потому что заголовок каждого kcp имеет размер win. Все, что осталось, — обновить перегрузку и размер окна в зависимости от состояния сети.

4. Резюме

Глядя на реализацию kcp, на самом деле обнаруживается, что она похожа на TCP транспортного уровня, но тонко настроена и управляема. Например, жертвуя управлением потоком, чтобы обеспечить передачу пакетов данных в режиме реального времени. Или ускорить ретрансляцию и так далее. Существует также выборочная ретрансляция через una и ack. В целом, определенные преимущества в области синхронизации игровых кадров или передачи данных в реальном времени у него все же есть.

Категории