[网络协议]Linux系统下基于IO多路复用的大规模可靠UDP服务器的实现（三）

七、可靠性UDP的优化细节

????????4.5章节中，我们提到了KCP本身的优化提高，由于可靠性UDP是这个方案是否优秀的关键，而各种可靠UDP协议中都有TCP算法的影子，所以下面我们再仔细的谈一下这个部分。按照惯例我们从基础知识谈起。

1）路由器技术

????????随着现代路由器技术的发展，已经从第一代发展到第五代、第六代，详见百度百科的《路由器技术》，从淘宝上可以看到各个路由器的价格和外观。一条链路上可能由各种路由器、网关、WiFi等设备组成，而同一时间段发送的消息包可能有多条链路。

????????路由器产生拥塞丢包的两大主要原因是CPU过载、或者缓存满，详见《路由器不定时丢包原因和解决方法》和《网络丢包的四大原因和修复方法》等文章。如果要是UDP协议，还有可能是运营商基于安全等考虑的限制，详见《为什么高防服务器要封国外，UDP》。如果是延时过大，有可能是bufferbloat问题，详见《实验1：tcp+路由器队列（过大）》，实际证明大缓冲区并不一定能带来网络状况的改善，可以会造成bufferbloat问题，详见《Enhancing TCP performance in networks with small buffers》和《深夜聊聊Bufferbloat以及TCP BBR》。另外还有一种丢包的原因是前端（接收端）拥塞，这个我们会在后面谈到。

????????实践证明，不管路由器处理的多么快，如果对于网络的使用没有节制，也可以轻松把路由器拥塞至死，详见《netdev 第二天：从网络代码中移除“尽可能快”这个目标》。为了避免网络拥塞和公平，我们需要了解TCP Pacing：《Understanding the Performance of TCP Pacing》，我们所有的设计思路，也是本着够用就行，并不是越快越好，所有说自己传输速度多么快的协议（无限贪婪），都不见得是好协议。目前的TCP一般使用AIMD（Additive Increase Multiplicative Decrease）策略来保证公平性，亦即“加性增窗”和“乘性减窗”，伪代码逻辑是（其数学逻辑见下节）：

if(Not_Loss_Packet) {
??? CongWin++;
}
else {
??? CongWin=[CongWin/2]; //[]的意思是取整
}

????????如果路由器发生不得不丢包的情况，可能是队列先进先出的Droptail：直接尾部丢弃；分布转发的RED(Random Early Detection)：随机头部丢弃；CoDel：等待时间过长丢弃，缺省5ms。RTT小但是缺丢包的原因可能是前者，RTT变大并且丢包的原因可能是后者。RED和CoDel的详细说明见《TSQ/CoDel队列管理以及TCP BBR如何解决Bufferbloat问题》。

????????所以，分析丢包原因对于拥塞避免会有一定的帮助。

2）无线通信技术

????????Wi-Fi是无线通信技术之一，提供Wi-Fi信号的无线路由器往往处于服务器到客户端链路的最后一公里，然后直接链接手机、PAD等客户端终端设备，由于采用的是抢占的方式，这里也是最有可能丢包的位置。

????????丢包的形式可能是随机丢包（RandomLoss，例如信号弱会导致丢失1%-2%的包），突发丢包（BurstLoss，如切换设备可能会导致一段时间的包全部丢失），包的重新排序（PacketReordering）。丢包的原因可能由于接入者过多空口资源不足、信号源较远或者切换、其他设备干扰、设置问题、长时间使用设备过热等等造成频繁丢包。

????????如果服务器端开启BBR后还有可能加重上述问题：BBR.BtlBw Max过滤器窗口的长度BtlBwFilterLen = 10个往返，在足够长并且稳定的前提下会有比较好的效果，但是在Wi-Fi、蜂窝等经常有较大波动的环境里性能可能会受到较大影响。中科院网络新媒体工程技术研究中心的《BBR拥塞控制算法在无线网络中的性能改进》专注BBR算法在最后一公里的问题，也是不错的文章（如果无法查看请在百度网盘下载链接: 提取码: utf5）。

????????4/5G虽然也是无线通信技术，但是由于采用双工、基站自动重发HARQ（FEC+ARQ）、等技术，所以效果较好稳定性高。

????????另外在无线网络中TCP链接还有显式路由失败通知TCP-RFN，显式路由失效通知TCP-ELFN，失序检测与相应TCP-DOOR。由于跟本文关系不大，不多做介绍。

????????所以，由客户端发起的各种环境探测也是有必要的。

3）TCP拥塞避免

????????可靠UDP的实现也要借鉴TCP拥塞避免算法，这是一篇避免网络拥塞较著名的论文《Congestion Avoidance and Control》。这里，也有很多的拥塞控制算法介绍：《数据传输中的拥塞控制》。AWS官网上的一篇教新的文章《从流量控制算法谈网络优化 – 从 CUBIC 到 BBRv2 算法》对各主要算法都有简要介绍和测试效果对比，其中介绍到的BBRv2还没有被Linux内核收录。

????????另外介绍两个具体的拥塞算法：《TCP Westwood演算法之研究与实作》（如果无法查看请在百度网盘下载链接: 提取码: sc6d）和《TCP拥塞控制之：BBR》，要深入理解BBR，还可以参考《Google BBR拥塞控制算法背后的数学解释》。实践证明，在网络状况比较好的情况下，经典的Cubic算法就够用了，在有一些丢包情况发生时，BBR算法会占据优势。其中BBR算法中有一个概念叫BDP(Bandwidth Delay Product)，就是带宽和延时的乘积，BBR算法的核心就是实时计算带宽，而我们自己做可靠性UDP传输协议，也需要计算该值，该值其实就是说带宽越大、延时越大（距离远），BDP的值就越大，inflight的包就越多，cwnd就越大。例如：测量带宽是 100Mbps，延迟是 100ms，那么计算公式为BDP = 100Mbps * 100ms = (100 / 8) * (100 / 1000) = 1.25MB，如果想最大限度提升吞度量，接收端窗口recv_wnd的大小不应小于 1.25MB。

????????实践过程中应该根据需要采用合适的拥塞算法，如果采用BBR算法则应该完善WiFi问题。

4）延时和带宽计算

????????能随时的计算出网络带宽，并且根据最大带宽发包，看起来是最快速的算法了，所以计算延时和带宽是比较重要的。其中延时计算比较简单，关于BBR带宽计算其实就是发送包的总量/发送时间，详见：《BBR即时带宽的计算》。

????????计算带宽伪代码逻辑如下（更确切的代码可以在内核中找到net\ipv4\tcp_bbr.c）：

function onAck(packet)
??? rtt = now - packet.sendtime
??? update_min_filter(RTpropFilter, rtt)
??? delivery_time = now
??? deliveryRate = (delivered - packet.delivered)/(now - packet.delivered_time)
??? if (deliveryRate > BtlBwFilter.curentMax || !packet.app_limited)
??????? update_max_filter(BtlBwFilter, deliveryRate)
??? if (app_limited_until > 0)
??????? app_limited_until -= packet.size

function send(packet)
??? bdp = BtlBwFilter.currentMax*RTpropFilter.currentMin
??? if (inflight >= cwnd_gain*bdp)
??????? //wait for ack or timeout
??????? return
??? if (now >= nextSendTime)
??????? packet = nextPacketToSend()
??????? if (!packet)
??????????? app_limited_until = inflight
?? ?????????return
??????? packet.app_limited = (app_limited_until > 0)
??????? packet.sendtime = now
??????? packet.delivered = delivered
??????? packet.delivered_time = delivered_time
??????? ship(packet)
??????? nextSendTime = now + packet.size/(pacing_gain * BtlBwFilter.currentMax)
??? timerCallbackAt(send, nextSendTime)

????????另外也有不少论文讨论带宽计算各种算法：北邮 杨帆的《网络带宽测量算法的研究》（如果无法查看请在百度网盘下载链接: 提取码: kabt）。姜立柱的《网络带宽测量算法的研究》（如果无法查看请在百度网盘下载链接: 提取码: gv2c）

????????以上拥塞、丢包等等都是基于网络层面的，丢包的位置大多数处于快到客户端的路由器上（wifi、大厦/小区中继），但无论是任何情况，对于服务器和客户端都是完全未知的，只能根据推测由服务器端调整相关参数。下面介绍一下客户端可以做点什么。

5）Zero Window Update

????????有几种丢包是发生在客户端本身的，例如：wifi信号受到干扰、客户端缓冲区不足、进程被杀掉等等。当客户端缓冲区不足的时候，会出现Zero Window，返回的ack消息会告诉发送端recv_window=0，或者服务器端主动发送的探测包未响应，这时候整个发送流会暂停。等客户端的缓冲区腾出空间后，就会发生Window Update事件，此时客户端应该尽快让服务器端知道客户端已经又可以收包了和recv_window的大小。参考文章《关于TCP Zero Window Update感知的非常棒的优化》。

6）我们还能做什么

????????由于上层应用不同，为达到更好的效果，我们还可以做一些更细致的工作，来辅助相关算法做更细致的策略决策：

消息包按协议分组，人类最快反应速度是100ms，奥运会的百米比赛规定运动员的反应不得低于100ms，在CS等依靠反应的经济游戏中，高手中大多数人的反应在200ms左右（有依靠声音辨别方向的可以到200ms以下），我们可以根据RTT值和具体业务需求把消息包分成不/需要立即发送的，丢包不/需要重传的，丢包后采用快速重传/超时重传的…等等；

减少ACK包，根据观察，ACK类型的消息包在网络上占30%左右。所以可以尝试各种减少ACK包的办法，除了采用SACK和DSACK外，在收到消息并且要返回ACK包的时候，也可以观察一下发送队列是否有将要发送的消息包，如果有的话可以让发送消息包顺路带回ACK；

减少包的数量，由于UDP拥塞丢包是以包为单位的，大一些的包跟小一些的包被丢弃的概率近似，所以理论来上说大一些的包会更好，所以我们尽量合并即将发送的包只要不超过mss值就好，如果超过了KCP底层也会分段；

本地网络环境探测，例如前端处于WIFI/4G/5G/LAN何种环境下、网络是否通畅、信号强弱、是否切换等等，将这些信息报告给服务器端，有助于服务器算法判断；

可用带宽测量，通常服务器的网络带宽都会大于客户端，所以也可以对前端的可用带宽进行测量来约束最大下行流量，相关论文和算法有很多，例如《端到端的可用带宽测量方法》（如果无法查看请在百度网盘下载链接: 提取码: mabp），还有《面向实时应用的可用带宽自适应测量方法》，服务器端可以根据前端可用带宽做出决策；

丢包探测，我们可以用这种方法来发现哪里是链路层丢包最大的位置，在Cisco和Linux下默认使用UDP traceroute，Windows下默认使用ICMP traceroute，TCP traceroute可以用tracetcp等程序实现，详见《TCP/UDP/ICMP Traceroute的原理及区别》，除了探测路由外，还可以探测丢包和RTT等，TCP详见《动手写一个探测网络质量(丢包率/RTT/队形等)的工具》，UDP丢包探测详见《UDP-jitter测试配置举例》等，我们可以在服务器端同机房，部署一台专门用于探测的公用服务器，以免对应用产生影响；

增窗探测，有的应用例如MMO类型的网络游戏或者ROK手游，平时的时候上下行流量都不高，占用带宽不大，但是在活动开始的时候下行消息突然骤增，往往会因此造成拥塞丢包。增窗探测虽然很少有人研究，但是在必要的时候向公用探测服务器发送增窗探测请求，有时候也是可以采用的方法；

消息包压缩，如果带宽不足，我们可以把消息包进行压缩，常见的算法有zstd、lz4、gzip、snappy、zlib等等。可以根据压缩率、吞吐率选择合适的算法，但需要注意较小的包压缩后效果不一定理想。对于不需要实时发送的消息包可以合并后压缩；

NAT穿透，也称P2P，可以让客户端相互建立连接，对于不严格的数据，例如视频信息等，甚至可以用P2P的方式来传输，这样可以大大节省服务器带宽。如果两个客户端距离很近，效果可能比直接从服务器传送更好。对于UDP来说，比TCP更容易实现NAT穿透。开源代码比较多，这里有一份NAT穿透例子代码，技术说明文档。Libtorrent也是一个不错的p2p协议开源库；

机器学习，深度学习和卷积神经网络（以下简称深度学习）用于解决网络拥塞，这是一个很新的领域，相关论文有《一种信息中心网络中基于深度学习的自适应拥塞控制方法》（如果无法查看请在百度网盘下载链接: 提取码: n45n），《基于深度学习的TCP拥塞控制版本识别方法和装置》。

????????从原理上看，深度学习用于解决拥塞的方法的输入是以往一个小的时间段的服务器各个配置参数、环境情况和网络流量、丢包等效果的向量，输出是部分可以动态调整的参数具体数值，所以，这应该是一个非结构化数据的无监督（无标签）学习，并且是一个回归问题，看起来似乎能运转良好，但是由于拥塞时服务器端/客户端并不知道网络上到底发生了什么，往往表现就是丢包，而原因可能千差万别，所以会出现学习不足、同样现象但是原因复杂且多种因素相互交叠的情况（我不知道这种情况的专业名词，所以下面仔细解释一下），比如深度学习样本数据图片中有羊、天鹅、猞猁这三种动物，验证集中却有狞猫，计算机就会把狞猫识别成猞猁，而将狞猫加入学习样本之后，验证集中又出现了兔狲、草豹、花豹、、、都加进去之后又出现鸭子、天鹅，并且几乎无穷无尽，这跟用深度学习去判断股票涨跌的情形类似，即便软件的设计者考虑了与股市相关的所有情况，但是未来总是有可能会出现新的突发因素来影响股市（例如各种黑天鹅事件），几乎没有规律，无法收敛，几乎无法完善价值评估函数，几乎无法梯度下降来使损失函数最小，整个系统可能是非独立熵增的。某个股票发现预测错误后还可以用网络爬虫搜寻与之相关的所有信息，而发生拥塞的绝大部分情况对前后端都是未知的，预测错误了也很可能无法找到原因。这种情况也可以理解成为：本身就压根没有解决网络拥塞的数学期望值。这位同学《网络拥塞控制和增强学习初瞰》也遇到了类似的问题，文中的QTCP也希望用增强的Q学习框架与TCP设计来解决拥塞问题，但是都没有成果。例如，在某种网络情况下，明明增大cwnd效果会更好，但是增大了cwnd后却突然出现服务器端无法察觉到原因的丢包，导致会误以为此时增大cwnd是错误的。

????????对于这种情况，我们必须如下应对：1）用于学习的数据集必须在稳定的已知的环境下产生（例如用网络损伤仪），不要由多种未知的情况造成拥塞，这样可以有效的减少深度神经网络的层数和让评估函数不会过于复杂；2）有限范围应用，即在某个前端预测值发生若干次错误等情况下，放弃掉深度学习算法而采用传统算法；3）动态反向传播，即发现错误后立即向前反馈，汇报损失，调整策略，详见论文《动态递归模糊神经网络及其BP学习算法(Dynamic fuzzy neural network and its dynamic back propagation algorithm)》

Linux系统下基于IO多路复用的大规模可靠UDP服务器的实现（一）

Linux系统下基于IO多路复用的大规模可靠UDP服务器的实现（二）