Introduction to the

KCP is a reliable transport protocol, code volume is small, used to learn reliable transport protocol is very good choice. In KCP you can see the implementation of sliding window, congestion window, four stages of congestion control etc. There are many articles about KCP on the web, but this article focuses on six features that the author mentioned in the wiki.

RTO doubled vs not doubled
UNA vs ACK+UNA
Selective retransmission vs. total retransmission
The fast retransmission
Delayed ACK versus non-delayed ACK
Non concession flow control

The following analysis one by one, if there is wrong, please add more corrections.

RTO doubled vs not doubled

TCP timeout calculation is RTOx2, so three consecutive packet loss will become RTOx8, which is very horrible, while KCP starts the fast mode not x2, but x1.5 (the experiment proves that 1.5 is relatively good), which improves the transmission speed.

Ikcp_flush:

// flush data segments
for(p = kcp->snd_buf.next; p ! = &kcp->snd_buf; p = p->next) { IKCPSEG *segment = iqueue_entry(p, IKCPSEG, node);int needsend = 0;
    if (segment->xmit == 0)   // Send the current packet for the first time
    {
        needsend = 1;
        segment->xmit++;
        segment->rto = kcp->rx_rto;
        segment->resendts = current + segment->rto + rtomin;  // Set the timeout period
    }
    else if (_itimediff(current, segment->resendts) >= 0)
    {
        // Timeout (RTO) When an ACK is received in the future, the rTO is retransmitted after timeout
        needsend = 1;
        segment->xmit++;
        kcp->xmit++;
        if (kcp->nodelay == 0)
        {
            segment->rto += kcp->rx_rto;                / / rto doubled
        }
        else
        {
            segment->rto += kcp->rx_rto / 2;            / / rto * 1.5
        }
        segment->resendts = current + segment->rto;
        lost = 1;                                       // A packet loss occurs on the network}}Copy the code

UNA vs ACK+UNA

ARQ model has two kinds of responses, UNA (all packets before this number have been received, such as TCP) and ACK (the packets with this number have been received). Using UNA alone will lead to all retransmission, and using ACK alone will cost too much to lose. In previous protocols, one of the two is selected. KCP header information:

Conv :4 bytes, connection number
CMD: 1 byte
FRG :1 byte, the number of fragments. User data may be sent in multiple KCP packets
WND :2 bytes. The size of the receiving window. The sending window of the sender cannot exceed the value given by the receiver
Ts :4 bytes, timestamp, timestamp
Sn: indicates the serial number of 4 bytes
Una :4 bytes, the next sequence number that can be received, also known as the confirmation number. For example, if you receive a packet whose sn is 10, una is 11
Len: the length of user data is 4 bytes

You can see that there are both SN and UNA in the packet header. This is the way KCP sends the message from the receiver to the sender by ACK+ una.

Selective retransmission vs. total retransmission

When TCP loses a packet, all the data starting from the lost packet is retransmitted. KCP is selective retransmission, only the really lost packets are retransmitted.

This feature is related to the above ACK+UNA feature. When the sender receives a reply from the receiver, it removes the packets before UNA from snd_buf according to UNA. When the sender receives an ACK reply, it removes the packets with the serial number sn from snd_buf. In packet loss retransmission and fast retransmission, only unreceived packets are retransmitted.

int ikcp_input(ikcpcb *kcp, const char *data, long size)
{
    while (1)
    {
        IUINT32 ts, sn, len, una, conv;
        IUINT16 wnd;
        IUINT8 cmd, frg;
        IKCPSEG *seg;
        
        if (size < (int)IKCP_OVERHEAD) break;

        data = ikcp_decode32u(data, &conv);
        if(conv ! = kcp->conv)return - 1;

        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);
        
        kcp->rmt_wnd = wnd;
        ikcp_parse_una(kcp, una);       // Delete the packets received by the peer through una
        ikcp_shrink_buf(kcp);           // Reset the sequence number snd_una of the package to be confirmed
        
        if (cmd == IKCP_CMD_ACK)    // The ACK packet was received
        {
            if (_itimediff(kcp->current, ts) >= 0)
            {
                // Calculate the RTO by RTT
                ikcp_update_ack(kcp, _itimediff(kcp->current, ts));     
            }
            ikcp_parse_ack(kcp, sn);    // Delete the current sn package
            ikcp_shrink_buf(kcp);       // Reset the sequence number snd_una of the package to be confirmed}}}Copy the code

Ikcp_parse_una delete package ikcp_parse_una

static void ikcp_parse_una(ikcpcb *kcp, IUINT32 una)
{
    // Delete the received packets from the send queue snd_buf according to UNA
    struct IQUEUEHEAD *p, *next;
    for(p = kcp->snd_buf.next; p ! = &kcp->snd_buf; p = next) { IKCPSEG *seg = iqueue_entry(p, IKCPSEG, node); next = p->next;if (_itimediff(una, seg->sn) > 0)  // Delete all items smaller than una
        {
            iqueue_del(p);
            ikcp_segment_delete(kcp, seg);
            kcp->nsnd_buf--;
        }
        else
        {
            break; }}}Copy the code

Delete package ikcp_parse_ack with sn in ACK package

static void ikcp_parse_ack(ikcpcb *kcp, IUINT32 sn)
{
    // Delete the received packets from the send queue snd_buf according to ack
    struct IQUEUEHEAD *p, *next;
    
    for(p = kcp->snd_buf.next; p ! = &kcp->snd_buf; p = next) { IKCPSEG *seg = iqueue_entry(p, IKCPSEG, node); next = p->next;if (sn == seg->sn) // Delete the serial number only when the serial number is equal
        {
            iqueue_del(p);
            ikcp_segment_delete(kcp, seg);
            kcp->nsnd_buf--;
            break;
        }
        if (_itimediff(sn, seg->sn) < 0)  // Break the loop quickly
        {
            break; }}}Copy the code

The fast retransmission

The sender sends 1,2,3,4, and 5 packets, and then receives the remote ACK: 1, 3,4, and 5. When receiving ACK3, KCP knows that 2 has been skipped once, and when receiving ACK4, KCP knows that 2 has been skipped twice. At this time, KCP can consider that no. 2 is lost.

Ikcp_flush ikcp_flush

int resent = (kcp->fastresend > 0)? (IUINT32)kcp->fastresend : 0xffffffff;

// flush data segments
for(p = kcp->snd_buf.next; p ! = &kcp->snd_buf; p = p->next) { IKCPSEG *segment = iqueue_entry(p, IKCPSEG, node);int needsend = 0;
    if (segment->xmit == 0)   // Send the current packet for the first time{... }else if (_itimediff(current, segment->resendts) >= 0) / / rto timeout{... lost =1;                                       // A packet loss occurs on the network
    }
    else if (segment->fastack >= resent)    // Fast retransmission
    {
        needsend = 1;
        segment->xmit++;
        segment->fastack = 0;
        segment->resendts = current + segment->rto;
        change++;
    }

    if(needsend) { ... }}...// update ssthresh
if (change)     
{
    // Fast retransmission occurs. After adjusting the slow start threshold and congestion window, the fast recovery phase is entered
    IUINT32 inflight = kcp->snd_nxt - kcp->snd_una;   // The number of packets being transmitted on the network
    kcp->ssthresh = inflight / 2;               // The slow start threshold is reduced to half of the current send window
    if (kcp->ssthresh < IKCP_THRESH_MIN)
        kcp->ssthresh = IKCP_THRESH_MIN;
    kcp->cwnd = kcp->ssthresh + resent; // The congestion window is also halved. But why add resent?
    kcp->incr = kcp->cwnd * kcp->mss;
}
Copy the code

Delayed ACK versus non-delayed ACK

In order to make full use of the bandwidth, TCP delays sending ACK (NODELAY is not used). In this way, the timeout calculation will calculate a large RTT time and prolong the judgment process of packet loss. The delay of SENDING ACK of KCP can be adjusted.

Ikcp_input is called after the receiving end receives the packet. The source code is as follows:

if (cmd == IKCP_CMD_PUSH)      // The packet is received
{
    if (_itimediff(sn, kcp->rcv_nxt + kcp->rcv_wnd) < 0) // Check the serial number validity
    {
        // Stores the ACK to be sent and then sends it on the next flush. If an ACK is not sent immediately, it is a feature of delaying the sending of an ACK
        // The delay is between 0ms and the set flush interval
        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);
            }

            // Store the received packages in the rcv_buf sequence from small to large
            // The data packets stored in rcv_buf may be continuous or discontinuous
            // When packets are continuous, move from rcv_buf to nRCV_que and update RCv_nxtikcp_parse_data(kcp, seg); }}}Copy the code

Let’s analyze ikcp_ACK_push for the processing of ack to be sent

static void ikcp_ack_push(ikcpcb *kcp, IUINT32 sn, IUINT32 ts)
{
    size_t newsize = kcp->ackcount + 1;
    IUINT32 *ptr;

    if (newsize > kcp->ackblock)
    {
        // If the capacity is insufficient, expand the capacity. The capacity is doubled each time
        // the order is 8,16,32,64, etc. } ptr = &kcp->acklist[kcp->ackcount *2];
    ptr[0] = sn;    // Store the serial number of the received packet and the time when the packet was sent
    ptr[1] = ts;    // Return the packet sending time, and the sender uses it to calculate RTT
    kcp->ackcount++;
}
Copy the code

Send in ikcp_flush

// flush acknowledges
count = kcp->ackcount;
for (i = 0; i < count; i++)     / / an ack
{
    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); // Get sn and ts from acklist
    ptr = ikcp_encode_seg(ptr, &seg);
}

kcp->ackcount = 0;
Copy the code

Non concession flow control

KCP normal mode uses the same fair concession rule as TCP, that is, the size of the send window is determined by four factors: the size of the send cache, the size of the remaining receive cache at the receiving end, packet loss, return concession and slow start. However, when transmitting small data with high timeliness requirements, you can choose to skip the last two steps through the configuration and use only the first two items to control the transmission frequency. At the expense of fairness and bandwidth utilization, the effect of smooth transmission with BT on is achieved.

In short, the number of packets that can be sent by a sender using TCP = STD ::min(sending window, receiving window on the receiver, congestion window). However, the number of packets that can be sent by the sender = STD ::min(sending window, receiving window of the receiver) is determined by two factors, and network congestion is directly ignored by KCP.

Also in ikcp_flush

// calculate window size
cwnd = _imin_(kcp->snd_wnd, kcp->rmt_wnd);
if (kcp->nocwnd == 0) {
    cwnd = _imin_(kcp->cwnd, cwnd);
}
// When nocwnd is set to 1, the network congestion control is disabled
// When interval is set to a minimum of 10ms and ikcp_flush is not updated, the send window is not changed
Copy the code

data

Complete source analysis link

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

KCP technical features source analysis

Introduction to the

RTO doubled vs not doubled

UNA vs ACK+UNA

Selective retransmission vs. total retransmission

The fast retransmission

Delayed ACK versus non-delayed ACK

Non concession flow control

data

KCP technical features source analysis

Introduction to the

RTO doubled vs not doubled

UNA vs ACK+UNA

Selective retransmission vs. total retransmission

The fast retransmission

Delayed ACK versus non-delayed ACK

Non concession flow control

data

Related Posts

GRPC: Use Buf to quickly compile GRPC proto files

Learn TensorFlow, PyTorch, Machine learning, Deep learning, and data structures! Attached download link! .

Design Patterns Learning 01(Java Implementation) — Overview and taxonomy of design patterns