|
本文为作者原创或翻译，转载请注明，不得用于商业用途。 作者：rellikt@gmail.com 首发链接：http://blog.csdn.net/rellikt/archive/2010/09/18/5892763.aspx 简介又是新的一周了，上周我简单介绍了一下FPS中用到的一些经常用来隐藏延迟的技术。这周我想继上次的UDP虚拟连接后，再进一步的介绍一下可靠传输和流量控制的内容。这篇的内容有可能会比较多，比较复杂，大家请耐心阅读。如果有空，最好能够调试本文所带的代码示例包，以加深印象。 TCP带来的问题 我相信对于熟悉TCP的读者来说，连接，可靠传输，流量控制并不是什么陌生的话题，既然TCP连接已经有了这些特性，我们为什么要自己去在UDP上面实现一层，来模仿TCP呢？这是不是典型的“发明轮子”呢？ 其实不然，我们在前面的博客中已经说过了，TCP对于我们高即时性的游戏有两个致命的缺点：一是无法订制丢包处理，我们在丢包的时候只能等待，无法忽略，而事实上在FPS类游戏中很多时候我们只关心即时数据，对于那些丢包，如果很久还没到，我们往往可以通过插值等手段直接忽略。TCP的自动封包属性使我们对于这种情况完全无法优化。另外一点就是TCP是一个数据流的概念，对于数据流的控制TCP在底层会进行帮我们进行优化管理，比如在56k猫上的传输数据和在60m宽带上传输的数据封包是完全不同的，这也导致了TCP和UDP在混和使用的时候会影响UDP的性能。 by rellikt 鉴于这两点其实都是TCP的核心功能所决定的，所以我们需要自己实现一层基于UDP的可靠传输协议，并且我们的协议还必须要有自己的数据流控制。这样我们在游戏中就可以对输入，位置等即时性很强的数据采用非可靠的UDP协议，自己优化处理丢包，乱序等情况。而那些时序性很强的操作，则可以使用我们自己实现的可靠传输协议来完成。另外对于发送速率的控制也可以让我们优先级比较高的通信拥有比较好的带宽资源。 序列标识位（squence number）现在先让我们回到可靠性上来！ 对于可靠性来说主要有两点的情况需要处理：一是丢包，一是乱序。 对于乱序：其实我们需要的是给每一个包一个序列标识，就像排队领号一样，有了这个标识，我们就能知道哪个包是先到的，包在数据流中的具体位置属性。 那么我们是不是可以给每个包加一个数据段叫packet_id呢？如果说这个packet_id是int型的，那么我们第一个到达的包就可以编号为0，第100个到达的包的编号就可以是100. 其实说起来在TCP中这种技术就已经被采用了，不过TCP叫这个字段为序列码（squence number）。我们虽然不想实现TCP，但是TCP用到的一些技术概念还是很值得借鉴的。我们以后也叫这个字段序列码吧。 我们知道UDP不是可靠传输，所以发送端发出去的第100个包，并不能保证在接收端也是在第100个收到，所以我们这个字段需要被嵌入到数据包中。这样接收端才能明确了解包的顺序。 我们在前面的博客中已经介绍了数据封包的概念。如果我们要加入序列码字段，我们的包可能看起来会是这样的。 [uint protocol id] [uint sequence] (packet data...) 这样接收端就可以在解码的时候知道封包的序列码了。 by rellikt 确认位（Acks）我们既然已经有了序列码，我们的数据的乱序问题就能保证了，接下来就是保证重发机制了，既丢包的情况处理。 一般来说既然丢包了，那就得重发，而发送端怎么知道要重发呢？我们现实生活对于重要邮件，一般会需要收件人给回执。对于网络发包来说，我们要解决这个问题，也就是要实现这种回执机制。 事实上，最简单的解决办法是我们可以在每个发回去的包里面带上一个确认位（ack），事实上我们的发送端和接受端是在不停的互相交互的，我们只需要在两端的封包中加入一个ack位，就可以模拟这个回执系统。现在我们的封包大概会像这样： [uint protocol id] [uint sequence] [uint ack] (packet data...) 我们发包和收包的时候的一般流程大致会是这样：
这简陋的回执系统是建立在类似我们写邮件的模型上的一个系统，这个回执系统的一个特点就是必须要求双方是回合制的通信，既发送与接受能一一配对。 事实上我们的游戏中的通信系统肯定不是这样的，可能我们一端的发送速率是30包/秒，另外一端的发送速率是15包/秒。这样的话，15包/秒的那端肯定没办法确认对面来的所有的包。另外如果我们有一个包丢了，那么我们就会连带丢失这个包的确认位所确认的那个包。这样必然导致不必要的重发。 这个系统看来暂时是不适合我们现在的游戏需求的，我们需要完善的回执系统！by rellikt 可靠的确认位既然简陋的回执系统不给力，我们自然而然会想去抄袭TCP那套完善的回执系统。那就让我们先来看看TCP是怎么做的。 这里顺便科普一下TCP著名的滑动窗口概念。当我们遇到一个长串序列需要维护分析的时候，我们一般不会一次将整个序列载入，我们会自己先建立一个合适的短序列的数据结构，然后把长序列中的一段拷贝到我们自己的数据结构中，我们每次维护分析这个短序列中的部分，然后把这部分维护分析过的部分弹出数据结构，把待处理长序列中接下来的一段合适的部分接进来，然后重复上面的流程。如果把长序列比喻成一个房子，这个短序列就是这个房子的一小窗口，我们可以通过这个短序列窥见房子的一部分，对短序列做弹出接入操作的时候就是这个窗口滑动的过程。 TCP做的就是对收到的包和要发送的包分别维护一个滑动窗口，发包的确认位一般就是下一个预期收包的序列码。如果TCP在收包的时候没有收到一个当前包的确认，TCP就会停止窗口滑动，重发该窗口的包。关于TCP的详细介绍论文有很多，这里有一个简单的flash，有兴趣的读者可以自己去翻阅更多论文，这里不做展开。事实上我们正是要避免这种等待重发机制。等待不是我们游戏中需要的。 在我们发包系统中，我们不会进行等待重发，也就是说我们的序列中即使有重发也是追加补发，我们的序列码是唯一的，不会有两个包拥有同一个序列码。至于数据排序处理的问题可以交给上层去处理。 既然我们不会做等待重发，那么很自然我们的数据流上一旦出现丢包，就会有一个我们不会去弥补的空缺。由于有这种空缺的存在，我们简单的发送最新收到的包的序列码就是有问题的。 我们需要在一个确认位中包含多个序列码。那我们到底包含多少序列码才合适呢？ 一般来说我们会让任何一方保持10包/秒的发包率，而在信息高峰的时候，我们有时候会达到60包/秒的峰值。这样说来，我们可能需要在一个包中确认大约最多6到7个包的回执。当然我们为了以防万一还要多留点余地。这样吧，一个包算它带32个回执好了。一个确认位4bytes，32个确认位大概128个bytes！如果我们只是简单的增加确认位，我们的包头就会大到我们无法容忍的地步了。 这里我们有一个小技巧，既然确认的都是前面连续的包我们其实不需要把所有的包的序列码都加进去，只需要加入一个最新的序列码，用一个32位的整形来表示这个最新的序列码前面32个包的回执情况就行了。我们把这位称为bitfield，现在我们的封包应该是这样的了。 [uint protocol id] [uint sequence] [uint ack] [uint ack bitfield] (packet data...) 我们假设ack位的序列码是100，bitfield中是0X77FF那么我们就可以认为68到100这32个包中间，100缺了，92缺了，其他包都到达了。 我们现在改良了的回执系统大概会是这样的：
这个算法是很有效的，我们可以很好的使用这个算法来完成需要的回执系统。 丢包确认既然我们已经建立了回执系统，那么我们就可以用这个回执系统来检测丢包了。事实上，一般我们的做法就是在等待一段时间后，如果还没有收到发包的确认的话，我们就会认为丢包。如果仔细思考我们上面的回执系统，我们可以发现我们能够收到的回执确认范围也就是32个。所以一般情况下，我们可以认为在比如1s内还没收到的包为丢失。事实上我们能确认的只有包未到达，而不是包已经丢失。 另外对于重复收包，我们可以在每个包中都加入一个标识来确认，而删除重发包的行为逻辑则可以在上层逻辑中进行判断。by rellikt 序列码环状重用和滑动窗口一样，这又是一个经典的话题。 我们知道一个unsigned int的范围是0到2^32-1(大约40多亿)。我们如果用unsigned int做序列码，假设我们1秒30个包的发，我们可以发4年半。这肯定是很够用了。但是如果为了带宽考虑我们把32位的序列码做成16位的，那么我们每个包就可以少用4bytes。但是现在我们的序列码就只能用半个小时了。我们该怎么半呢？ 答案其实很简单，在溢出以后，我们的序列码又会从255跳回到0,1,2……我们只需要重新定义一下比较函数就可以了。比如这样： inline bool sequence_more_recent( unsigned int s1, unsigned int s2, unsigned int max_sequence ) { return ( s1 > s2 ) && ( s1 - s2 <= max_sequence/2 ) || ( s2 > s1 ) && ( s2 - s1 > max_sequence/2 ); } 用上面这个函数我们就可以很方便的完成序列码环状重用了。 by rellikt 流量控制我们已经解决了可靠性的问题了。接下来我们看看数据流控制的问题。TCP中已经为我们实现好了一套流量控制和拥塞回避机制。我们不需要做任何操心。但是UDP没有！ 我们如果只是简单的不做任何流量控制的发包，我们很可能会在峰值的时候把带宽给塞爆，然后接下来的数据包拥堵就会让你体验到2s+的延迟了。是的信息高速公路和现实一样也会堵车。每个路由都会努力尽量把包送达，因此在包多的时候，他们会把包排队压入缓冲，在条件允许的时候再发，只有在缓冲不够的时候他们才丢包，然后延迟丢包就这么出现了。 我们不可能告诉路由器，我们的包要优先送达的，不想要延迟。当然你可以去买个VPN，这样就相当自己开了一条专用高速。但是我们还是要考虑一般人的情况。 事实上我们需要实现自己的流量控制算法，来避免这种拥堵。我们不可能一上来就和TCP一样实现一个刚健的流量控制系统。和前面的回执系统一样，我们先来实现一个最简单的流量控制系统。 测定延迟（Round Trip Time aka RTT) 我们做流量控制的初衷就是要防止网络数据洪峰造成的超级延迟。既然要防止超级延迟，那我们首先要有一个正常延迟的概念。我们需要一种方法来测定延迟。 下面是我们会采用的一些基本测定延迟的方法：
我们现在有了我们自己能够维护的一个RTT了，接下来我们就可以用这个RTT来做流量控制了。我们的原则就是RTT变大的时候加快发包率，RTT减小的时候减少发包率。 简易流量控制接下来我们看看怎么实现一个简易的流量控制系统吧。 比如说我们现在每个包大概有256bytes，然后我们打算把发包的最高峰值订制在30包/秒，谷值订制在10包/秒。就是说在峰值的时候我们大概会占用64kbits/s，谷值的时候我们大概会占用20kbits/s。我们的基本概念就是在网络条件不好的时候用谷值来发包，在网络条件好的条件下用峰值来发包。 怎么来衡量网络条件好坏呢？我们这里可以通过我们前面得到的RTT来进行判断。比如RTT超过250ms了就算差，RTT小于250ms了就算好。下面是我们可以采用的一些基本的算法：
上述简单算法就可以基本搞定一个简单的流量控制了，当然你可以写出更完善的算法，比如把丢包率，发包回执率都算在里面。这样当然会更加健壮。by rellikt 你也可以把算法改的层次更丰富，更为贪心。但是贪心的后果往往会造成拥塞，当心了。 结论上面我们简单实现了我们需要的可靠传输和流量控制。这里只是基础入门，想要深入的话，还有很多论文可以参阅。本文附带的示例代码在这里大家有兴趣的可以参阅。但是如果要把这代码引入到现实产品中可能还是要做一定的休整。 希望大家能够享受阅读代码的乐趣。 by rellikt |
|
|
