基于UDP的帧同步网络方案（基础）

        帧同步会高频次的上报和下发逻辑帧，所以网络方案非常重要，TCP协议的优势在于有序、可靠、有连接，但是由于较为保守的超时重传方案、过大的包头，会给帧同步带来比较高的延迟和较大的数据流量，而UDP是较为精简的网络协议，不保证时序、不保证可靠性、无连接，但是这些都可以自行实现、定制，并且包头较小，可以说是帧同步较为理想的网络协议。但是直接用UDP的话，肯定是不能满足帧同步的需求的，帧同步要求 ：相同的输入一定会有相同的输出，所以网络包是不可丢弃的，网络包的时序也要保证一致，所以UDP必须实现最基础的这两个功能才行。

        首先是时序，这个比较好解决，给每个网络包都定义一个自增序号，收消息的时候检查序号是否连续，不连续的话，暂时不处理，等序号连续了才处理。为了实现处理的消息有序，我们将消息包头定义为下面这样的数据结构：

*  ReliableData 数据包格式 ps:每个data大小不得超过255 只用8位来表示
* | CRC - 16bit | TYPE - 4BIT | IsLittleEndian - 1BIT | Empty - 3BIT | ACK -  16BIT | SEQ - 16BIT | | DataSize - 8bit | Data |

正常的CRC为32位，这里采用16位算法，节约包头大小，然后是4位的包类型，分为可靠包、Ping包、纯ACK包三种类型，1位的大小端标志，3个预留位，ACK为本地已接收到的有序的最新消息的序号（告诉对方在这个序号以前的消息不用再发给我了），SEQ为当前这条消息的序号，DataSize为消息大小，至于为什么只留8位，后面再说；最后的Data位消息体内容。这样设计下来，整个包头为64bit，相对与TCP的近200bit来说，还是节省了不少。

        接收到消息的时候处理算法如下：

if (type == (byte)NXUdp.UDPPackageType.ReliableData)
            {
                int messageCount = 0;
                while (true)
                {
                    ushort seq = stream.ReadUShort();
                    int dataSize = stream.ReadByte();
                    if (dataSize == -1)
                        break;      // 读完了
                    if (seq > _recvAck.Value)
                    {
                        var current = _recvMsgQuene.First;
                        while (current != null)
                        {
                            var curNode = current.Value;
                            if (seq == curNode.Seq                      // 重复的消息
                                || seq < curNode.Seq)                   // 插入的消息
                                break;
                            current = current.Next;
                        }
                        if (current != null && current.Value.Seq == seq)
                        {
                            // 这个包已经收到过了 丢弃
                            stream.Seek(dataSize, SeekOrigin.Current);
                        }
                        else
                        {
                            var node = _buffers.Alloc(stream.GetBuffer(),  (int)stream.Position, dataSize);
                            stream.Seek(dataSize, SeekOrigin.Current);
                            var msg = new NXUdpMessage(seq, node);
                            if (current == null) _recvMsgQuene.AddLast(msg);
                            else _recvMsgQuene.AddBefore(current, msg);
                            hasNewReliableData = true;
                        }
                    }
                    else
                    {
                        // 这个包过时了 丢弃
                        stream.Seek(dataSize, SeekOrigin.Current);
                    }
                    recvLog.AppendFormat(" Msg[{0}] Seq:{1} Length:{2}",  messageCount, seq, dataSize);
                    ++messageCount;
                }
            }

_recvMsgQuene是消息队列，这里是做了一次插入算法，将比原来链表中Seq大的消息插入到链表中，至于相同的Seq和较小的Seq则进行忽略。

这样链表保证Seq是一个由小到大的顺序。得到了这个链表之后就要对这个链表进行遍历，然后取出消息：

        private void UpdateRecvMessage()
        {
            if (!IsConnect) return;
            var current = _recvMsgQuene.First;
            while (current != null)
            {
                var curNode = current.Value;
                if (_recvAck.IsNext(curNode.Seq))
                {
                    _recvAck.Set(curNode.Seq);
                    OnReceiveMsgEvent?.Invoke(curNode, _buffers);
                    _buffers.Free(curNode.Pos);
                    current = current.Next;
                    _recvMsgQuene.RemoveFirst();
                }
                else  // 因为是个有序的  只要不等于 就可以break了
                {
                    break;
                }
            }
        }

这里就非常简单了，_recvAck是表示当前已经处理的最新一条消息的Seq，每次取出一个消息就检测一下是否是_recvAck的下一条消息，如果是的话，就进行处理，如果不是的话，后面的消息也不用处理了，说明中间一定少收了某些消息，为保证时序，我们必须等待中间的消息收到了以后才能处理剩下的消息。

以上就是保证接收时序的核心算法，这块相对简单，总结起来就是，发送的时候带序号，接收的时候丢到链表里面，顺序处理。

 

然后另外一个就是超时重传，TCP是自带超时重传功能的，但是为了保证网络的畅通，TCP的设计者不希望过于占用网络资源，所以重传算法设计得比较保守。先介绍几个概念：

RTO：重传超时时间，当发送的数据包时间超过RTO以后，会触发重传机制，这个值设置得过小，会导致频繁触发重传，而设置得过大，又会导致重传不及时，要解决这个问题，就要先介绍另外一个概念RTT。

RTT：一次消息在网络上的往返时间，这个时间是动态的，每次发出消息的时候根据网络状况的不同、选择的链路不同，都不一样。

而RTO就是需要根据RTT去动态计算出来，我们首先要拿到 一次性收发到的消息的平均RTT，然后根据公式计算出RTO，计算公式网上一大堆，原理就是根据最新的RTT和平均RTT进行加权，最终得出RTO。但是如果一个包第一次重传依旧超时，怎么办？可能是RTO设置得不合理，不够大，也可能是网络确实不通，这时候为了避免占用过多的网络资源，引入了Karn算法，这种算法说起来更简单，就是针对这种重传的包，第二次重传的RTO=a*RTO，TCP协议中，这里的a=2。

分析完TCP协议的超时重传算法，就开始设计我们自己的超时重传算法了，在这里我们发现TCP协议的重传算法在大框架上考虑得比较周到，但是细节上还是有不少可优化的点，例如动态RTO的计算公式、Karn算法中的a值等，都可以做一些优化，例如我们可以把a设置为1.5，或者更小 ，让协议包能快速重传。

不过我现在写的这一套NXUdp没有做动态计算RTO的算法，RTO现在写死了，只是做了重传机制，后续优化的时候考虑将动态RTO加入进来。

        private bool UpdateSendMessage()
        {
            if (!IsConnect) return false;
            if (_sendMsgQuene.Count == 0) return false;
            bool sendMessage = false;
            _sendMessageFlushList.Clear();
            var cur = _stopWatch.ElapsedMilliseconds;
            var totalSize = 0;
            var current = _sendMsgQuene.First;
            while (current != null)
            {
                var msg = current.Value;
                if (cur - msg.LRto > _udp.GetRto())
                {
                    totalSize += msg.Length;
                    if (totalSize > NXUdp.MAX_PAK_SIZE)
                    {
                        _udp.Send(this, NXUdp.UDPPackageType.ReliableData,  _sendMessageFlushList, _recvAck.ToUInt16(), _buffers);
                        _sendMessageFlushList.Clear();
                        totalSize = msg.Length;
                        sendMessage = true;
                    }
                    msg.LRto = cur;
                    _sendMessageFlushList.Add(msg);
                    current = current.Next;
                }
            }
            if (_sendMessageFlushList.Count != 0)
            {
                _udp.Send(this, NXUdp.UDPPackageType.ReliableData,  _sendMessageFlushList, _recvAck.ToUInt16(), _buffers);
                _sendMessageFlushList.Clear();
                sendMessage = true;
            }
            return sendMessage;
        }

这里做了一点优化，我将需要重传的包都尽可能的打包成一个UDP包一次性发送出去，节约包头大小。