KCP

如果你已经看过KCP项目的README，那这篇文章前两个小节就不用看了。如果你没看过，那务必先看看: KCP

简介

可靠的传输协议，实现的方式有很多种。最简单的，发送送每帧把没收到回复的数据包再发一次也行。但这并不一定合理，带宽消耗听起来就很严重。而TCP本身的带宽利用率是最高的，但延迟却很高。

低带宽和低延迟是两个矛盾的目标。低带宽依赖于更准确的丢包判定算法，而对丢包判定来说，往往没收到回复的时间越久，丢失的概率越高。如果加上对整个网络环境的考虑，也就是拥塞控制，那每个人都有责任让自己慢下来一点。

KCP是对标经典TCP的一种可靠传输协议，跟TCP不一样，设计上更偏向于追求更低的传输延迟，而不是更高的带宽利用率。因此对延迟敏感的项目很有帮助，例如实时游戏、视频直播。

特性

贯彻对低延迟的追求，KCP实现了以下特性。

快速重传

一般的丢包判定是设定一个超时时间，也就是RTO。当过了RTO还没收到对端的回复，就认为数据已经丢失，可以发起重传。但这个RTO起码是一个RTT，所以延迟起码是1.5个RTT。TCP的实现甚至给RTO设了一个200ms的下限，知道为什么慢了吧。

于是就想方法实现一个不依赖超时的快速重传机制。

TCP的做法是当收到3个重复的ACK编号时，不需要等待超时，马上发起重传。得益于上面的每个包单独ACK，KCP也实现了一套快速重传，它记录了每个包被跳过的次数，当被跳过2次时，就认为已经丢了。

"发送端发送了1,2,3,4,5几个包，然后收到远端的ACK: 1, 3, 4, 5，当收到ACK3时，KCP知道2被跳过1次，收到ACK4时，知道2被跳过了2次，此时可以认为2号丢失，不用等超时，>直接重传2号包，大大改善了丢包时的传输速度。"

只要发送方的发包频率比较高，那这种判定通常就会比RTO来得快。

从UE网络部分的文档来看，它也是类似的机制，而且更为激进，只要跳过1次，就判定为丢包。而UE类的游戏，通常每帧都会传输数据，所以数据包的间隔也就33ms或者更短16ms，如果发送了1/2/3，而收到了1/3的回复，那不考虑网络波动，只需要rtt+16+16即可判定2丢失。

RTO不翻倍

TCP在发生超时时，会将下一次重传超时设为当前的2倍，指数级增长。KCP快速模式下只会翻1.5倍，重传会更及时一些。

UNA + ACK

TCP只有UNA(Unknown Ack)，所以丢失时只能重传UNA之后的所有包。而如果光用单独ACK，由于ACK包也可能丢失，会导致发送方非必要的重传。KCP选择全都要，实现了选择性重传，代价是多了一些ACK包（一个interval里的ACK会合并发送）。

非退让流控

TCP有一套拥塞控制算法，避免加剧网络拥堵，简单来说就是在检测到拥堵时放缓自己的发包频率。而KCP可以选择关闭拥塞控制。虽然有失公平，但是如果认为自己的数据量非常小，并非网络拥堵的元凶，那勉强可以算是关掉的合理性吧。

另外，TCP的网络拥塞判断依据是有没有发生丢包，但在当前的移动网络环境下，并不准确，有可能只是基站到手机的信道质量太差导致的丢包，根本就没有发生网络拥堵，这个时候降低发包频率无济于事。谷歌实现了一个新TCP版本，使用新的BBR算法去进行拥塞控制，有兴趣可以了解一下。

特性实现细节

在ikcp_flush中可以看到非退让流控、RTO不翻倍、快速重传、UNA、ACK打包，顺便可以看到TCP经典拥塞控制的实现。

	// flush acknowledges
	count = kcp->ackcount;
	for (i = 0; i < count; i++) {
		size = (int)(ptr - buffer);
		// kcp update interval内的ACK打包发送
		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);
	}

	// ...

	// calculate window size
	cwnd = _imin_(kcp->snd_wnd, kcp->rmt_wnd);
	// 关了拥塞控制，就仅由双方的窗口来决定发送上限
	if (kcp->nocwnd == 0) cwnd = _imin_(kcp->cwnd, cwnd);

	// ...

	// 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) {
			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) {
				// rto翻倍，相当于乘以2
				segment->rto += _imax_(segment->rto, (IUINT32)kcp->rx_rto);
			}	else {
				// 看来nodelay设为2可以用最新的rto来退让
				IINT32 step = (kcp->nodelay < 2)? 
					((IINT32)(segment->rto)) : kcp->rx_rto;
				// rto不翻倍，仅乘1.5
				segment->rto += step / 2;
			}
			segment->resendts = current + segment->rto;
			// 记录出现超时，后面更新拥塞窗口
			lost = 1;
		}
		else if (segment->fastack >= resent) {
			// 快速重传，最多触发fastlimit次，超过限制就代表其实已经很堵了
			if ((int)segment->xmit <= kcp->fastlimit || 
				kcp->fastlimit <= 0) {
				needsend = 1;
				segment->xmit++;
				segment->fastack = 0;
				segment->resendts = current + segment->rto;
				// 记录出现快速重传，后面更新拥塞窗口
				change++;
			}
		}

		if (needsend) {
			int need;
			segment->ts = current;
			segment->wnd = seg.wnd;
			// 每个数据包都带上UNA
			segment->una = kcp->rcv_nxt;
			// ...
		}
	}

	// update ssthresh
	if (change) {
		// tcp第二版的实现，快速恢复
		IUINT32 inflight = kcp->snd_nxt - kcp->snd_una;
		kcp->ssthresh = inflight / 2;
		if (kcp->ssthresh < IKCP_THRESH_MIN)
			kcp->ssthresh = IKCP_THRESH_MIN;
		kcp->cwnd = kcp->ssthresh + resent;
		kcp->incr = kcp->cwnd * kcp->mss;
	}

	if (lost) {
		// tcp第一版的实现，cwnd直接重置为1，进行慢启动
		kcp->ssthresh = cwnd / 2;
		if (kcp->ssthresh < IKCP_THRESH_MIN)
			kcp->ssthresh = IKCP_THRESH_MIN;
		kcp->cwnd = 1;
		kcp->incr = kcp->mss;
	}

	if (kcp->cwnd < 1) {
		kcp->cwnd = 1;
		kcp->incr = kcp->mss;
	}

在ikcp_input中可以看到单独ACK。

		// 处理应用层数据，也就是ikcp_send发送的数据
		else if (cmd == IKCP_CMD_PUSH) {
			// 如果在接收范围之内
			if (_itimediff(sn, kcp->rcv_nxt + kcp->rcv_wnd) < 0) {
				// 单独ACK，但是会等到ikcp_flush时才组装发送
				ikcp_ack_push(kcp, sn, ts);
				// 如果这个if不通过，就代表是重复包，回个ack就可以了，不用真正处理
				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);
				}
			}

顺带看到TCP经典的RTO计算实现。

static void ikcp_update_ack(ikcpcb *kcp, IINT32 rtt)
{
	IINT32 rto = 0;
	if (kcp->rx_srtt == 0) {
		kcp->rx_srtt = rtt;
		kcp->rx_rttval = rtt / 2;
	}	else {
		long delta = rtt - kcp->rx_srtt;
		if (delta < 0) delta = -delta;
		kcp->rx_rttval = (3 * kcp->rx_rttval + delta) / 4;
		kcp->rx_srtt = (7 * kcp->rx_srtt + rtt) / 8;
		if (kcp->rx_srtt < 1) kcp->rx_srtt = 1;
	}
	// 理想下rto应该等于当其时的rtt。假设rtt是固定的，那其实rto直接等于rtt即可。
	// 但rtt不断变化，所以要预测接下来的rtt会是多少，于是用方差来跟踪差异。
	// 默认取4倍的方差作为余量，而这里跟kcp->interval作_imax_，是假设对端的interval选择跟自己一样，
	// 而rtt实际上包含了[0, interval]区间内的延迟，所以接下来的rtt有可能跟当前rtt最大相差interval。
	rto = kcp->rx_srtt + _imax_(kcp->interval, 4 * kcp->rx_rttval);
	kcp->rx_rto = _ibound_(kcp->rx_minrto, rto, IKCP_RTO_MAX);
}