本篇自我总结

本篇主要讲了数据包的分包和重组问题, 到底数据包多大才好呢?是不是越大越好呢?包太大了怎么办呢?
请看总结, 不明之处再看文中具体讲解.

为什么需要做这个可靠UDP协议

网络协议在动作游戏类型（FPS）中的典型特征就是一个持续发送的数据包，在两个方向上以稳定的速度如20或30包每秒发送。这些数据包都包含有不可靠的无序数据例如t时间内的世界状态；所以，当一个数据包丢失，重新发送它并不是特别有用。当重新发送的数据包到达时，时间t已经过去了。

所以这就是我们将要实现可靠性的现状。对于我们90%的数据包，仅丢弃并不再重新发送它会更好。对于10%或更少（误差允许范围内）的情况，我们确实需要可靠性，但这样的数据是非常罕见的，很少被发送而且比不可靠的数据的平均大小要小得多。这个使用案例适用于所有过去十五年来发布的AAA级的FPS游戏。

应答系统是实现可靠UDP的最重要的部分

为实现数据包层级的应答，在每个包的前面添加如下的报头：

struct Header
{
    uint16_t sequence;
    uint16_t ack;
    uint32_t ack_bits;
};

这些报头元素组合起来以创建应答系统：

• sequence 是一个数字，随每个数据包发送而增长（并且在达到65535后回往复）。
• ack 是从另一方接收到的最新的数据包序列号。
• ack_bits 是一个位字段，它编码与ack相关的收到的数据包组合：如果位n已经设置，即 ack– n 数据包被接收了。

ack_bits 不仅是一个节省带宽的巧妙的编码，它同样也增加了信息冗余来抵御包的丢失。每个应答码要被发送32次。如果有一个包丢失了，仍然有其他31个包有着相同的应答码。从统计上来说，应答码还是非常有可能送达的。

但突发的传送数据包的丢失还是有可能发生的，所以重要的是要注意：

• 如果你收到一个数据包n的应答码，那么这个包肯定已经收到了。
• 如果你没有收到应答码，那么这个包就很有可能 没有被收到。但是…它也许会是，仅是应答码没有送达。这种情况是极其罕见的。

以我的经验，没有必要设计完善的应答机制。在一个极少丢应答码的系统上构建一个可靠性系统并不会增加什么大问题。

发送方如何追踪数据包是否已经被应答

为实现这个应答系统，我们在发送方还需要一个数据结构来追踪一个数据包是否已经被应答，这样我们就可以忽略冗余的应答（每个包会通过 ack_bits多次应答)。我们同样在接收方也还需要一个数据结构来追踪那些已经收到的包，这样我们就可以在数据包的报头填写ack_bits的值。

const int BufferSize = 1024;
 
uint32_t sequence_buffer[BufferSize];
 
struct PacketData
{
    bool acked;
};
 
PacketData packet_data[BufferSize];
 
PacketData * GetPacketData( uint16_t sequence )
{
    const int index = sequence % BufferSize;
    if ( sequence_buffer[index] == sequence )
        return &packet_data[index];
    else
        return NULL;
}

你在这可以看到的窍门是这个滚动的缓冲区是以序列号来作为索引的：

const int index =sequence % BufferSize;

当条目被顺序添加，就像一个被发送的队列，对插入所需要做的就是把这个序列缓冲区的值更新为新的序列号并且在该索引处重写这个数据：

PacketData & InsertPacketData( uint16_t sequence )
{
    const int index = sequence % BufferSize;
    sequence_buffer[index] = sequence;
    return packet_data[index];
}

原文

原文出处

原文标题 : Reliable Ordered Messages (How to implement reliable-ordered messages on top of UDP)

Introduction

Hi, I’m Glenn Fiedler and welcome to Building a Game Network Protocol.

Many people will tell you that implementing your own reliable message system on top of UDP is foolish. After all, why reimplement TCP?

But why limit ourselves to how TCP works? But there are so many different ways to implement reliable-messages and most of them work nothing like TCP!

So let’s get creative and work out how we can implement a reliable message system that’s better and more flexible than TCP for real-time games.

Different Approaches

A common approach to reliability in games is to have two packet types: reliable-ordered and unreliable. You’ll see this approach in many network libraries.

The basic idea is that the library resends reliable packets until they are received by the other side. This is the option that usually ends up looking a bit like TCP-lite for the reliable-packets. It’s not that bad, but you can do much better.

The way I prefer to think of it is that messages are smaller bitpacked elements that know how to serialize themselves. This makes the most sense when the overhead of length prefixing and padding bitpacked messages up to the next byte is undesirable (eg. lots of small messages included in each packet). Sent messages are placed in a queue and each time a packet is sent some of the messages in the send queue are included in the outgoing packet. This way there are no reliable packets that need to be resent. Reliable messages are simply included in outgoing packets until they are received.

The easiest way to do this is to include all unacked messages in each packet sent. It goes something like this: each message sent has an id that increments each time a message is sent. Each outgoing packet includes the start message id followed by the data for n messages. The receiver continually sends back the most recent received message id to the sender as an ack and only messages newer than the most recent acked message id are included in packets.

This is simple and easy to implement but if a large burst of packet loss occurs while you are sending messages you get a spike in packet size due to unacked messages.

You can avoid this by extending the system to have an upper bound on the number of messages included per-packet n. But now if you have a high packet send rate (like 60 packets per-second) you are sending the same message multiple times until you get an ack for that message.

If your round trip time is 100ms each message will be sent 6 times redundantly before being acked on average. Maybe you really need this amount of redundancy because your messages are extremely time critical, but in most cases, your bandwidth would be better spent on other things.

The approach I prefer combines packet level acks with a prioritization system that picks the n most important messages to include in each packet. This combines time critical delivery and the ability to send only n messages per-packet, while distributing sends across all messages in the send queue.

Packet Level Acks

To implement packet level acks, we add the following packet header:

struct Header
{
    uint16_t sequence;
    uint16_t ack;
    uint32_t ack_bits;
};

These header elements combine to create the ack system: sequence is a number that increases with each packet sent, ack is the most recent packet sequence number received, and ack_bits is a bitfield encoding the set of acked packets.

If bit n is set in ack_bits, then ack - n is acked. Not only is ack_bits a smart encoding that saves bandwidth, it also adds redundancy to combat packet loss. Each ack is sent 32 times. If one packet is lost, there’s 31 other packets with the same ack. Statistically speaking, acks are very likely to get through.

But bursts of packet loss do happen, so it’s important to note that:

1. If you receive an ack for packet n then that packet was definitely received.




2. If you don’t receive an ack, the packet was most likely not received. But, it might have been, and the ack just didn’t get through. This is extremely rare.

In my experience it’s not necessary to send perfect acks. Building a reliability system on top of a system that very rarely drops acks adds no significant problems. But it does create a challenge for testing this system works under all situations because of the edge cases when acks are dropped.

So please if you do implement this system yourself, setup a soak test with terrible network conditions to make sure your ack system is working correctly. You’ll find such a soak test in the example source code for this article, and the open source network libraries reliable.io and yojimbo which also implement this technique.

Sequence Buffers

To implement this ack system we need a data structure on the sender side to track whether a packet has been acked so we can ignore redundant acks (each packet is acked multiple times via ack_bits. We also need a data structure on the receiver side to keep track of which packets have been received so we can fill in the ack_bits value in the packet header.

The data structure should have the following properties:

• Constant time insertion (inserts may be random, for example out of order packets…)


• Constant time query if an entry exists given a packet sequence number


• Constant time access for the data stored for a given packet sequence number


• Constant time removal of entries

You might be thinking. Oh of course, hash table. But there’s a much simpler way:

const int BufferSize = 1024;

uint32_t sequence_buffer[BufferSize];

struct PacketData
{
    bool acked;
};

PacketData packet_data[BufferSize];

PacketData  GetPacketData( uint16_t sequence )
{
    const int index = sequence % BufferSize;
    if ( sequence_buffer[index] == sequence )
        return &packet_data[index];
    else
        return NULL;
}

As you can see the trick here is a rolling buffer indexed by sequence number:

const int index = sequence % BufferSize;

This works because we don’t care about being destructive to old entries. As the sequence number increases older entries are naturally overwritten as we insert new ones. The sequence_buffer[index] value is used to test if the entry at that index actually corresponds to the sequence number you’re looking for. A sequence buffer value of 0xFFFFFFFF indicates an empty entry and naturally returns NULL for any sequence number query without an extra branch.

When entries are added in order like a send queue, all that needs to be done on insert is to update the sequence buffer value to the new sequence number and overwrite the data at that index:

PacketData & InsertPacketData( uint16_t sequence )
{
    const int index = sequence % BufferSize;
    sequence_buffer[index] = sequence;
    return packet_data[index];
}

Unfortunately, on the receive side packets arrive out of order and some are lost. Under ridiculously high packet loss (99%) I’ve seen old sequence buffer entries stick around from before the previous sequence number wrap at 65535 and break my ack logic (leading to false acks and broken reliability where the sender thinks the other side has received something they haven’t…).

The solution to this problem is to walk between the previous highest insert sequence and the new insert sequence (if it is more recent) and clear those entries in the sequence buffer to 0xFFFFFFFF. Now in the common case, insert is very close to constant time, but worst case is linear where n is the number of sequence entries between the previous highest insert sequence and the current insert sequence.

Before we move on I would like to note that you can do much more with this data structure than just acks. For example, you could extend the per-packet data to include time sent:

struct PacketData
{
    bool acked;
    double send_time;
};

With this information you can create your own estimate of round trip time by comparing send time to current time when packets are acked and taking an exponentially smoothed moving average. You can even look at packets in the sent packet sequence buffer older than your RTT estimate (you should have received an ack for them by now…) to create your own packet loss estimate.

Ack Algorithm

Now that we have the data structures and packet header, here is the algorithm for implementing packet level acks:

On packet send:

1. Insert an entry for for the current send packet sequence number in the sent packet sequence buffer with data indicating that it hasn’t been acked yet




2. Generate ack and ack_bits from the contents of the local received packet sequence buffer and the most recent received packet sequence number




3. Fill the packet header with sequence, ack and ack_bits




4. Send the packet and increment the send packet sequence number

On packet receive:

1. Read in sequence from the packet header




2. If sequence is more recent than the previous most recent received packet sequence number, update the most recent received packet sequence number




3. Insert an entry for this packet in the received packet sequence buffer




4. Decode the set of acked packet sequence numbers from ack and ack_bits in the packet header.




5. Iterate across all acked packet sequence numbers and for any packet that is not already acked call OnPacketAcked( uint16_t sequence ) and mark that packet as acked in the sent packet sequence buffer.

Importantly this algorithm is done on both sides so if you have a client and a server then each side of the connection runs the same logic, maintaining its own sequence number for sent packets, tracking most recent received packet sequence # from the other side and a sequence buffer of received packets from which it generates sequence, ack and ack_bits to send to the other side.

And that’s really all there is to it. Now you have a callback when a packet is received by the other side: OnPacketAcked. The main benefit of this ack system is now that you know which packets were received, you can build any reliability system you want on top. It’s not limited to just reliable-ordered messages. For example, you could use it to implement delta encoding on a per-object basis.

Message Objects

Messages are small objects (smaller than packet size, so that many will fit in a typical packet) that know how to serialize themselves. In my system they perform serialization using a unified serialize functionunified serialize function.

The serialize function is templated so you write it once and it handles read, write and measure.

Yes. Measure. One of my favorite tricks is to have a dummy stream class called MeasureStream that doesn’t do any actual serialization but just measures the number of bits that would be written if you called the serialize function. This is particularly useful for working out which messages are going to fit into your packet, especially when messages themselves can have arbitrarily complex serialize functions.

struct TestMessage : public Message
{
    uint32_t a,b,c;

    TestMessage()
    {
        a = 0;
        b = 0;
        c = 0;
    }

    template <typename Stream> bool Serialize( Stream & stream )
    {
        serialize_bits( stream, a, 32 );
        serialize_bits( stream, b, 32 );
        serialize_bits( stream, c, 32 );
        return true;
    }

    virtual SerializeInternal( WriteStream & stream )
    {
        return Serialize( stream );
    }

    virtual SerializeInternal( ReadStream & stream )
    {
        return Serialize( stream );
    }

    virtual SerializeInternal( MeasureStream & stream )
    {
        return Serialize( stream );
    }
};

The trick here is to bridge the unified templated serialize function (so you only have to write it once) to virtual serialize methods by calling into it from virtual functions per-stream type. I usually wrap this boilerplate with a macro, but it’s expanded in the code above so you can see what’s going on.

Now when you have a base message pointer you can do this and it just works:

Message  message = CreateSomeMessage();
message->SerializeInternal( stream );

An alternative if you know the full set of messages at compile time is to implement a big switch statement on message type casting to the correct message type before calling into the serialize function for each type. I’ve done this in the past on console platform implementations of this message system (eg. PS3 SPUs) but for applications today (2016) the overhead of virtual functions is neglible.

Messages derive from a base class that provides a common interface such as serialization, querying the type of a message and reference counting. Reference counting is necessary because messages are passed around by pointer and stored not only in the message send queue until acked, but also in outgoing packets which are themselves C++ structs.

This is a strategy to avoid copying data by passing both messages and packets around by pointer. Somewhere else (ideally on a separate thread) packets and the messages inside them are serialized to a buffer. Eventually, when no references to a message exist in the message send queue (the message is acked) and no packets including that message remain in the packet send queue, the message is destroyed.

We also need a way to create messages. I do this with a message factory class with a virtual function overriden to create a message by type. It’s good if the packet factory also knows the total number of message types, so we can serialize a message type over the network with tight bounds and discard malicious packets with message type values outside of the valid range:

enum TestMessageTypes
{
    TEST_MESSAGE_A,
    TEST_MESSAGE_B,
    TEST_MESSAGE_C,
    TEST_MESSAGE_NUM_TYPES
};

// message definitions omitted

class TestMessageFactory : public MessageFactory
{
public:

    Message  Create( int type )
    {
        switch ( type )
        {
            case TEST_MESSAGE_A: return new TestMessageA();
            case TEST_MESSAGE_B: return new TestMessageB();
            case TEST_MESSAGE_C: return new TestMessageC();
        }
    }

    virtual int GetNumTypes() const
    {
        return TEST_MESSAGE_NUM_TYPES;
    }
};

Again, this is boilerplate and is usually wrapped by macros, but underneath this is what’s going on.

Reliable Ordered Message Algorithm

The algorithm for sending reliable-ordered messages is as follows:

On message send:

1. Measure how many bits the message serializes to using the measure stream




2. Insert the message pointer and the # of bits it serializes to into a sequence buffer indexed by message id. Set the time that message has last been sent to -1




3. Increment the send message id

On packet send:

1. Walk across the set of messages in the send message sequence buffer between the oldest unacked message id and the most recent inserted message id from left -> right (increasing message id order).




2. Never send a message id that the receiver can’t buffer or you’ll break message acks (since that message won’t be buffered, but the packet containing it will be acked, the sender thinks the message has been received, and will not resend it). This means you must never send a message id equal to or more recent than the oldest unacked message id plus the size of the message receive buffer.




3. For any message that hasn’t been sent in the last 0.1 seconds and fits in the available space we have left in the packet, add it to the list of messages to send. Messages on the left (older messages) naturally have priority due to the iteration order.




4. Include the messages in the outgoing packet and add a reference to each message. Make sure the packet destructor decrements the ref count for each message.




5. Store the number of messages in the packet n and the array of message ids included in the packet in a sequence buffer indexed by the outgoing packet sequence number so they can be used to map packet level acks to the set of messages included in that packet.




6. Add the packet to the packet send queue.

On packet receive:

1. Walk across the set of messages included in the packet and insert them in the receive message sequence buffer indexed by their message id.




2. The ack system automatically acks the packet sequence number we just received.

On packet ack:

1. Look up the set of messages ids included in the packet by sequence number.




2. Remove those messages from the message send queue if they exist and decrease their ref count.




3. Update the last unacked message id by walking forward from the previous unacked message id in the send message sequence buffer until a valid message entry is found, or you reach the current send message id. Whichever comes first.

On message receive:

1. Check the receive message sequence buffer to see if a message exists for the current receive message id.




2. If the message exists, remove it from the receive message sequence buffer, increment the receive message id and return a pointer to the message.




3. Otherwise, no message is available to receive. Return NULL.

In short, messages keep getting included in packets until a packet containing that message is acked. We use a data structure on the sender side to map packet sequence numbers to the set of message ids to ack. Messages are removed from the send queue when they are acked. On the receive side, messages arriving out of order are stored in a sequence buffer indexed by message id, which lets us receive them in the order they were sent.

The End Result

This provides the user with an interface that looks something like this on send:

TestMessage  message = (TestMessage) factory.Create( TEST_MESSAGE );
if ( message )
{
    message->a = 1;
    message->b = 2;
    message->c = 3;
    connection.SendMessage( message );
}

And on the receive side:

while ( true )
{
    Message  message = connection.ReceiveMessage();
    if ( !message )
        break;

    if ( message->GetType() == TEST_MESSAGE )
    {
        TestMessage  testMessage = (TestMessage) message;
        // process test message
    }

    factory.Release( message );
}

Which is flexible enough to implement whatever you like on top of it.

译文

译文出处

互联网的通信安全，建立在 SSL/TLS 协议之上。

本文简要介绍 SSL/TLS 协议的运行机制。文章的重点是设计思想和运行过程，不涉及具体的实现细节。如果想了解这方面的内容，请参阅 RFC 文档。

. . .

写到一半发现论坛的热门帖子里官方写了个u3d的demo源码解析, 内容几乎重复, u3d跟ue4的demo框架流程几乎都是差不多的, 直接给出官方帖子的链接好了, 尴尬:
http://bbs.kbengine.org/forum.php?mod=viewthread&tid=166

本篇自我总结

有了本系列上篇文章中的分包和重组系统为何还要这个发送大块数据系统?是否是多余的?是雷同的吗?
请看总结概要理清思路, 再细看文章.

为什么需要做这个发送大块数据系统

第一眼看上去，这种替代性的技术似乎非常类似于数据包的分包和重组，但是它的实现是完全不同的。这种实现上的差异的目的是为了解决数据包分包和重组的一个关键弱点 : 一个片段的丢失就会导致整个数据包都要被丢弃掉然后重新分包重发。

你可能需要这样做的一些常见的例子包括：客户端在首次加入的时候，服务器需要下发一个大的数据块给客户端(可能是世界的初始状态)、一开始用来做增量编码的基线或者是在一个多人在线网络游戏里面客户端在加载界面所等待的大块数据。

在这些情况下非常重要的是不仅要优雅地处理数据包的丢失，还要尽可能的利用可用的带宽并尽可能快的发送大块数据。

这个发送大块数据系统大致可以理解为是一个在原来分包和重组系统的基础上增加了分包确认功能, 也就是说增加了可靠性的部分.

本篇基本术语

In this new system blocks of data are called chunks. Chunks are split up into slices. This name change keeps the chunk system terminology (chunks/slices) distinct from packet fragmentation and reassembly (packets/fragments).

• 块 : 在这个新系统中，大块的数据被称为”块”(chunks)
• 片段 : 而块被分成的分包被称为”片段”(slices)

数据包的结构设计

这个系统在网络上发送的数据包类型一共有两种类型：

• Slice packet片段数据包 : 这包括了一个块的片段，最多大小为1k。

  const int SliceSize = 1024; const int MaxSlicesPerChunk = 256; const int MaxChunkSize = SliceSize MaxSlicesPerChunk; struct SlicePacket : public protocol2::Packet { uint16_t chunkId; int sliceId; int numSlices; int sliceBytes; uint8_t data[SliceSize]; template <typename stream> bool Serialize( Stream & stream ) { serialize_bits( stream, chunkId, 16 ); serialize_int( stream, sliceId, 0, MaxSlicesPerChunk - 1 ); serialize_int( stream, numSlices, 1, MaxSlicesPerChunk ); if ( sliceId == numSlices - 1 ) { serialize_int( stream, sliceBytes, 1, SliceSize ); } else if ( Stream::IsReading ) { sliceBytes = SliceSize; } serialize_bytes( stream, data, sliceBytes ); return true; } };

• Ack packet确认数据包 : 一个位域bitfield指示哪些片段已经收到, we just send the entire state of all acked slices in each ack packet. When the ack packet is received (including the slice that was just received).

  struct AckPacket : public protocol2::Packet { uint16_t chunkId; int numSlices; bool acked[MaxSlicesPerChunk]; bool Serialize( Stream & stream ) { serialize_bits( stream, chunkId, 16 ); serialize_int( stream, numSlices, 1, MaxSlicesPerChunk ); for ( int i = 0; i < numSlices; ++i ) serialize_bool( stream, acked[i] ); return true; } }; } };

发送方的实现

与之前文章介绍的数据包的分包和重组系统不同，块系统在同一时间只能由一个块正在传输。
发送方的策略是：

• 持续的发送片段数据包，直到所有的片段数据包都被确认。
• 不再对已经确认过的片段数据包进行发送。

对于发送方而言有一点比较微妙，实现一个片段数据包重新发送的最小延迟是一个很棒的主意，如果不这么做的话，就可能会出现这种一样情况，对于很小的块数据或者一个块的最后几个片段数据包，很容易不停的发送它们把整个网络都塞满。正是因为这一原因，我们使用了一个数组来记录每个片段数据包的上一次发送时间。重新发送延迟的一个选择是使用一个估计的网络往返时延，或者只有在超过上一次发送时间网络往返时延*1.25还没有收到确认数据包的情况才会重新发送。或者，你可以说“这根本就无所谓”，只要超过上一次发送时间100毫秒了就重新发送。我只是列举适合我自己的方案！

我们使用以下的数据结构来描述发送方：

class ChunkSender
{
    bool sending;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numAckedSlices;
    int currentSliceId;
    bool acked[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
    double timeLastSent[MaxSlicesPerChunk];
};

接收方的实现思路

首先，接收方的设置会从块0开始。当一个片段数据包从网络上传递过来，并且能够匹配这个块id的话，“receiving”状态会从false翻转为true，第一个片段数据包的数据会插入” chunkData“变量的合适位置，片段数据包的数量会根据第一个片段数据包里面的数据进行正确的设置，已经接收到的片段数据包的数量会加一，也就是从0到1，针对每个片段数据包的接收标记里面对应这个片段数据包的项会变为true。

随着这个块数据的其他片段数据包的到来，会对每一个片段数据包进行检测，判断它们的id是否与当前块的id相同，如果不相同的话就会被丢弃。如果这个片段数据包已经收到过的话，那么这个包也会被丢弃。否则，这个片段数据包的数据会插入” chunkData“变量的合适位置、已经接收到的片段数据包的数量会加一、针对每个片段数据包的接收标记里面对应这个片段数据包的项会变为true。

这一过程会持续进行，直到接收到所有的片段数据包。一旦接收到所有的片段数据包（也就是已经接收到的片段数据包的数量等于片段数据包的数量的时候），接收方会把“receiving “状态改为false，而把”readyToRead“状态改为true。当”readyToRead”状态为true的时候，所有收到的片段数据包都会被丢弃。在这一点上，这个处理过程通常非常的短，会在收到片段数据包的同一帧进行处理，调用者会检查”我有一块数据要读取么？“并处理块数据。然后会重置数据块接收器的所有数据为默认值，除了块数据的id从0增加到1，这样我们就准备好接收下一个块了。

class ChunkReceiver
{
    bool receiving;
    bool readyToRead;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numReceivedSlices;
    bool received[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
};

防DDos

如果你对每个收到的片段数据包都会回复一个确认数据包的话，那么发送方能够构造一个很小的片段数据包发送给你，而你会回复一个比发送给你的片段数据包还大的确认数据包，这样你的服务器就变成了一个可以被人利用来进行DDos放大攻击的工具。

永远不要设计一个包含对接收到的数据包进行一对一的映射响应的协议。让我们举个简单例子来说明一下这个问题。如果有人给你发送1000个片段数据包，永远不要给他回复1000个确认数据包。相反只发一个确认数据包，而且最多每50毫秒或者100毫秒才发送一个确认数据包。如果你是这样设计的话，那么DDos攻击完全不可能的。

原文

原文出处

原文标题 : Sending Large Blocks of Data (How to send blocks quickly and reliably over UDP)

Introduction

Hi, I’m Glenn Fiedler and welcome to Building a Game Network Protocol.

In the previous article we implemented packet fragmentation and reassembly so we can send packets larger than MTU.

This approach works great when the data block you’re sending is time critical and can be dropped, but in other cases you need to send large blocks of quickly and reliably over packet loss, and you need the data to get through.

In this situation, a different technique gives much better results.

Background

It’s common for servers to send large block of data to the client on connect, for example, the initial state of the game world for late join.

Let’s assume this data is 256k in size and the client needs to receive it before they can join the game. The client is stuck behind a load screen waiting for the data, so obviously we want it to be transmitted as quickly as possible.

If we send the data with the technique from the previous article, we get packet loss amplification because a single dropped fragment results in the whole packet being lost. The effect of this is actually quite severe. Our example block split into 256 fragments and sent over 1% packet loss now has a whopping 92.4% chance of being dropped!

Since we just need the data to get across, we have no choice but to keep sending it until it gets through. On average, we have to send the block 10 times before it’s received. You may laugh but this actually happened on a AAA game I worked on!

To fix this, I implemented a new system for sending large blocks, one that handles packet loss by resends fragments until they are acked. Then I took the problematic large blocks and piped them through this system, fixing a bunch of players stalling out on connect, while continuing to send time critical data (snapshots) via packet fragmentation and reassembly.

Chunks and Slices

In this new system blocks of data are called chunks. Chunks are split up into slices. This name change keeps the chunk system terminology (chunks/slices) distinct from packet fragmentation and reassembly (packets/fragments).

The basic idea is that slices are sent over the network repeatedly until they all get through. Since we are implementing this over UDP, simple in concept becomes a little more complicated in implementation because have to build in our own basic reliability system so the sender knows which slices have been received.

This reliability gets quite tricky if we have a bunch of different chunks in flight, so we’re going to make a simplifying assumption up front: we’re only going to send one chunk over the network at a time. This doesn’t mean the sender can’t have a local send queue for chunks, just that in terms of network traffic there’s only ever one chunk in flight at any time.

This makes intuitive sense because the whole point of the chunk system is to send chunks reliably and in-order. If you are for some reason sending chunk 0 and chunk 1 at the same time, what’s the point? You can’t process chunk 1 until chunk 0 comes through, because otherwise it wouldn’t be reliable-ordered.

That said, if you dig a bit deeper you’ll see that sending one chunk at a time does introduce a small trade-off, and that is that it adds a delay of RTT between chunk n being received and the send starting for chunk n+1 from the receiver’s point of view.

This trade-off is totally acceptable for the occasional sending of large chunks like data sent once on client connect, but it’s definitely not acceptable for data sent 10 or 20 times per-second like snapshots. So remember, this system is useful for large, infrequently sent blocks of data, not for time critical data.

Packet Structure

There are two sides to the chunk system, the sender and the receiver.

The sender is the side that queues up the chunk and sends slices over the network. The receiver is what reads those slice packets and reassembles the chunk on the other side. The receiver is also responsible for communicating back to the sender which slices have been received via acks.

The netcode I work on is usually client/server, and in this case I usually want to be able to send blocks of data from the server to the client and from the client to the server. In that case, there are two senders and two receivers, a sender on the client corresponding to a receiver on the server and vice-versa.

Think of the sender and receiver as end points for this chunk transmission protocol that define the direction of flow. If you want to send chunks in a different direction, or even extend the chunk sender to support peer-to-peer, just add sender and receiver end points for each direction you need to send chunks.

Traffic over the network for this system is sent via two packet types:

• Slice packet - contains a slice of a chunk up to 1k in size.


• Ack packet - a bitfield indicating which slices have been received so far.

The slice packet is sent from the sender to the receiver. It is the payload packet that gets the chunk data across the network and is designed so each packet fits neatly under a conservative MTU of 1200 bytes. Each slice is a maximum of 1k and there is a maximum of 256 slices per-chunk, therefore the largest data you can send over the network with this system is 256k.

const int SliceSize = 1024;
const int MaxSlicesPerChunk = 256;
const int MaxChunkSize = SliceSize  MaxSlicesPerChunk;

struct SlicePacket : public protocol2::Packet
{
    uint16_t chunkId;
    int sliceId;
    int numSlices;
    int sliceBytes;
    uint8_t data[SliceSize];

    template <typename Stream> bool Serialize( Stream & stream )
    {
        serialize_bits( stream, chunkId, 16 );
        serialize_int( stream, sliceId, 0, MaxSlicesPerChunk - 1 );
        serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
        if ( sliceId == numSlices - 1 )
        {
            serialize_int( stream, sliceBytes, 1, SliceSize );
        }
        else if ( Stream::IsReading )
        {
            sliceBytes = SliceSize;
        }
        serialize_bytes( stream, data, sliceBytes );
        return true;
    }
};

There are two points I’d like to make about the slice packet. The first is that even though there is only ever one chunk in flight over the network, it’s still necessary to include the chunk id (0,1,2,3, etc…) because packets sent over UDP can be received out of order.

Second point. Due to the way chunks are sliced up we know that all slices except the last one must be SliceSize (1024 bytes). We take advantage of this to save a small bit of bandwidth sending the slice size only in the last slice, but there is a trade-off: the receiver doesn’t know the exact size of a chunk until it receives the last slice.

The other packet sent by this system is the ack packet. This packet is sent in the opposite direction, from the receiver back to the sender. This is the reliability part of the chunk network protocol. Its purpose is to lets the sender know which slices have been received.

struct AckPacket : public protocol2::Packet
{
    uint16_t chunkId;
    int numSlices;
    bool acked[MaxSlicesPerChunk];

    bool Serialize( Stream & stream )
    {
        serialize_bits( stream, chunkId, 16 );
        serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
        for ( int i = 0; i < numSlices; ++i )
        {
            serialize_bool( stream, acked[i] ); return true; } };
        }
    }
};

Acks are short for ‘acknowledgments’. So an ack for slice 100 means the receiver is acknowledging that it has received slice 100. This is critical information for the sender because not only does it let the sender determine when all slices have been received so it knows when to stop, it also allows the sender to use bandwidth more efficiently by only sending slices that haven’t been acked.

Looking a bit deeper into the ack packet, at first glance it seems a bit redundant. Why are we sending acks for all slices in every packet? Well, ack packets are sent over UDP so there is no guarantee that all ack packets are going to get through. You certainly don’t want a desync between the sender and the receiver regarding which slices are acked.

So we need some reliability for acks, but we don’t want to implement an ack system for acks because that would be a huge pain in the ass. Since the worst case ack bitfield is just 256 bits or 32 bytes, we just send the entire state of all acked slices in each ack packet. When the ack packet is received, we consider a slice to be acked the instant an ack packet comes in with that slice marked as acked and locally that slice is not seen as acked yet.

This last step, biasing in the direction of non-acked to ack, like a fuse getting blown, means we can handle out of order delivery of ack packets.

Sender Implementation

Let’s get started with the implementation of the sender.

The strategy for the sender is:

• Keep sending slices until all slices are acked


• Don’t resend slices that have already been acked

We use the following data structure for the sender:

class ChunkSender
{
    bool sending;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numAckedSlices;
    int currentSliceId;
    bool acked[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
    double timeLastSent[MaxSlicesPerChunk];
};

As mentioned before, only one chunk is sent at a time, so there is a ‘sending’ state which is true if we are currently sending a chunk, false if we are in an idle state ready for the user to send a chunk. In this implementation, you can’t send another chunk while the current chunk is still being sent over the network. If you don’t like this, stick a queue in front of the sender.

Next, we have the id of the chunk we are currently sending, or, if we are not sending a chunk, the id of the next chunk to be sent, followed by the size of the chunk and the number of slices it has been split into. We also track, per-slice, whether that slice has been acked, which lets us count the number of slices that have been acked so far while ignoring redundant acks. A chunk is considered fully received from the sender’s point of view when numAckedSlices == numSlices.

We also keep track of the current slice id for the algorithm that determines which slices to send, which works like this. At the start of a chunk send, start at slice id 0 and work from left to right and wrap back around to 0 again when you go past the last slice. Eventually, you stop iterating across because you’ve run out of bandwidth to send slices. At this point, remember our current slice index via current slice id so you can pick up from where you left off next time. This last part is important because it distributes sends across all slices, not just the first few.

Now let’s discuss bandwidth limiting. Obviously you don’t just blast slices out continuously as you’d flood the connection in no time, so how do we limit the sender bandwidth? My implementation works something like this: as you walk across slices and consider each slice you want to send, estimate roughly how many bytes the slice packet will take eg: roughly slice bytes + some overhead for your protocol and UDP/IP header. Then compare the amount of bytes required vs. the available bytes you have to send in your bandwidth budget. If you don’t have enough bytes accumulated, stop. Otherwise, subtract the bytes required to send the slice and repeat the process for the next slice.

Where does the available bytes in the send budget come from? Each frame before you update the chunk sender, take your target bandwidth (eg. 256kbps), convert it to bytes per-second, and add it multiplied by delta time (dt) to an accumulator.

A conservative send rate of 256kbps means you can send 32000 bytes per-second, so add 32000 dt to the accumulator. A middle ground of 512kbit/sec is 64000 bytes per-second. A more aggressive 1mbit is 125000 bytes per-second. This way each update you accumulate a number of bytes you are allowed to send, and when you’ve sent all the slices you can given that budget, any bytes left over stick around for the next time you try to send a slice.

One subtle point with the chunk sender and is that it’s a good idea to implement some minimum resend delay per-slice, otherwise you get situations where for small chunks, or the last few slices of a chunk that the same few slices get spammed over the network.

For this reason we maintain an array of last send time per-slice. One option for this resend delay is to maintain an estimate of RTT and to only resend a slice if it hasn’t been acked within RTT * 1.25 of its last send time. Or, you could just resend the slice it if it hasn’t been sent in the last 100ms. Works for me!

Kicking it up a notch

Do the math you’ll notice it still takes a long time for a 256k chunk to get across:

• 1mbps = 2 seconds


• 512kbps = 4 seconds


• 256kbps = 8 seconds :(

Which kinda sucks. The whole point here is quickly and reliably. Emphasis on quickly. Wouldn’t it be nice to be able to get the chunk across faster? The typical use case of the chunk system supports this. For example, a large block of data sent down to the client immediately on connect or a block of data that has to get through before the client exits a load screen and starts to play. You want this to be over as quickly as possible and in both cases the user really doesn’t have anything better to do with their bandwidth, so why not use as much of it as possible?

One thing I’ve tried in the past with excellent results is an initial burst. Assuming your chunk size isn’t so large, and your chunk sends are infrequent, I can see no reason why you can’t just fire across the entire chunk, all slices of it, in separate packets in one glorious burst of bandwidth, wait 100ms, and then resume the regular bandwidth limited slice sending strategy.

Why does this work? In the case where the user has a good internet connection (some multiple of 10mbps or greater…), the slices get through very quickly indeed. In the situation where the connection is not so great, the burst gets buffered up and most slices will be delivered as quickly as possible limited only by the amount bandwidth available. After this point switching to the regular strategy at a lower rate picks up any slices that didn’t get through the first time.

This seems a bit risky so let me explain. In the case where the user can’t quite support this bandwidth what you’re relying on here is that routers on the Internet strongly prefer to buffer packets rather than discard them at almost any cost. It’s a TCP thing. Normally, I hate this because it induces latency in packet delivery and messes up your game packets which you want delivered as quickly as possible, but in this case it’s good behavior because the player really has nothing else to do but wait for your chunk to get through.

Just don’t go too overboard with the spam or the congestion will persist after your chunk send completes and it will affect your game for the first few seconds. Also, make sure you increase the size of your OS socket buffers on both ends so they are larger than your maximum chunk size (I recommend at least double), otherwise you’ll be dropping slices packets before they even hit the wire.

Finally, I want to be a responsible network citizen here so although I recommend sending all slices once in an initial burst, it’s important for me to mention that I think this really is only appropriate, and only really borderline appropriate behavior for small chunks in the few 100s of k range in 2016, and only when your game isn’t sending anything else that is time-critical.

Please don’t use this burst strategy if your chunk is really large, eg: megabytes of data, because that’s way too big to be relying on the kindness of strangers, AKA. the buffers in the routers between you and your packet’s destination. For this it’s necessary to implement something much smarter. Something adaptive that tries to send data as quickly as it can, but backs off when it detects too much latency and/or packet loss as a result of flooding the connection. Such a system is outside of the scope of this article.

Receiver Implementation

Now that we have the sender all sorted out let’s move on to the reciever.

As mentioned previously, unlike the packet fragmentation and reassembly system from the previous article, the chunk system only ever has one chunk in flight.

This makes the reciever side of the chunk system much simpler:

class ChunkReceiver
{
    bool receiving;
    bool readyToRead;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numReceivedSlices;
    bool received[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
};

We have a state whether we are currently ‘receiving’ a chunk over the network, plus a ’readyToRead’ state which indicates that a chunk has received all slices and is ready to be popped off by the user. This is effectively a minimal receive queue of length 1. If you don’t like this, of course you are free to add a queue.

In this data structure we also keep track of chunk size (although it is not known with complete accuracy until the last slice arrives), num slices and num received slices, as well as a received flag per-slice. This per-slice received flag lets us discard packets containing slices we have already received, and count the number of slices received so far (since we may receive the slice multiple times, we only increase this count the first time we receive a particular slice). It’s also used when generating ack packets. The chunk receive is completed from the receiver’s point of view when numReceivedSlices == numSlices.

So what does it look like end-to-end receiving a chunk?

First, the receiver sets up set to start at chunk 0. When the a slice packet comes in over the network matching the chunk id 0, ‘receiving’ flips from false to true, data for that first slice is inserted into ‘chunkData’ at the correct position, numSlices is set to the value in that packet, numReceivedSlices is incremented from 0 -> 1, and the received flag in the array entry corresponding to that slice is set to true.

As the remaining slice packets for the chunk come in, each of them are checked that they match the current chunk id and numSlices that are being received and are ignored if they don’t match. Packets are also ignored if they contain a slice that has already been received. Otherwise, the slice data is copied into the correct place in the chunkData array, numReceivedSlices is incremented and received flag for that slice is set to true.

This process continues until all slices of the chunk are received, at which point the receiver sets receiving to ‘false’ and ‘readyToRead’ to true. While ‘readyToRead’ is true, incoming slice packets are discarded. At this point, the chunk receive packet processing is performed, typically on the same frame. The caller checks ‘do I have a chunk to read?’ and processes the chunk data. All chunk receive data is cleared back to defaults, except chunk id which is incremented from 0 -> 1, and we are ready to receive the next chunk.

Conclusion

The chunk system is simple in concept, but the implementation is certainly not. I encourage you to take a close look at the source code for this article for further details.

译文

译文出处

本篇自我总结

本篇主要讲了数据包的分包和重组问题, 到底数据包多大才好呢?是不是越大越好呢?包太大了怎么办呢?
请看总结, 不明之处再看文中具体讲解.

为什么需要做这个分包和重组系统

每台计算机(路由器)会沿着路由强制要求数据包的大小会有一个最大的上限，这个上限就是所谓的最大传输单元MTU。如果任意一个路由器收到一个数据包的大小超过这个最大传输单元的大小，它有这么两个选择，a)在IP层对这个数据包进行分包，并将分包后的数据包继续传递，b)丢弃这个数据包然后告诉你数据包被丢弃了，你自己负责摆平这个问题。

实例 : 这儿有一个我会经常遇到的情况。人们在编写多人在线游戏的时候，数据包的平均大小都会非常的小，让我们假设下，这些数据包的平均大小大概只有几百字节，但时不时会在他们的游戏中同时发生大量的事情并且发出去的数据包会出现丢失的情况，这个时候数据包会比通常的情况下要大。突然之间，游戏的数据包的大小就会超过最大传输单元的大小，这样就只有很少一部分玩家能够收到这个数据包，然后整个通信就崩溃了。

本篇基本术语

• 数据包packets
• 分包fragments

分包的数据结构

我们将允许一个数据包最多可以分成256个数据包，并且每个分包后的数据包的大小不会超过1024个字节。这样的话，我们就可以通过这样一个系统来发送大小最大为256k的数据包

[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)  
[sequence] (16 bits)  // 数据包序号
[packet type = 0] (2 bits)
[fragment id] (8 bits) // 分包ID
[num fragments] (8 bits)
[pad zero bits to nearest byte index] // 用于字节对齐的bits
<fragment data>

发送分包后的数据包

发送分包以后的数据包是一件非常容易的事情。如果数据包的大小小于保守估计的最大传输单元的大小。那么就按正常的方法进行发送。否则的话，就计算这个数据包到底该分成多少个1024字节的数据包分包，然后构建这些分包并按照之前发送正常数据包的方法进行发送。

发送出去以后也不记录发送的数据包的内容，这种发送以后不记录发送的数据包的内容的方法有一个后果，就是数据包的任意一个分包如果丢失的话，那么整个数据包就都要丢弃。随着分包数量的增加，整个数据包被丢弃的概率也随之增加.由此可见，当你需要发送要给256K的数据包的时候要发送256个分包，如果有一个分包丢失的话，你就要重新把这个256k的数据包再分一次包然后再发送出去。

什么时候用这个分包和重组系统呢

因为发送出去以后也不记录发送的数据包, 随着分包数量的增加，整个数据包被丢弃的概率也随之增加, 而一个片段的丢失就会导致整个数据包都要被丢弃掉.所以我建议你要小心分包以后的数量。

这个分包和重组系统最好是只对2-4个分包的情况进行使用，而且最好是针对那种对时间不怎么敏感的数据使用或者是就算分包lost了也无所谓的情况。绝对不要只是为了省事就把一大堆依赖顺序的事件打到一个大数据包里面然后依赖数据包的分包和重组机制进行发送。这会让事情变得更加麻烦。

数据包分包和重组系统的关键弱点是一个片段的丢失就会导致整个数据包都要被丢弃掉, 想要解决这个弱点得使用大块数据发送策略, 见下一篇文章 构建游戏网络协议四之发送大块数据.

接收分包后的数据包

之所以对分包后的数据包进行接收很困难的原因是我们不仅需要给缓冲区建立一个数据结构还要把这些分包重组成原始的数据包，我们也要特别小心如果有人试图让我们的程序产生崩溃而给我们发送恶意的数据包。

要非常小心检查一切可能的情况。除此之外，还有一个非常简单的事情要注意：让分包保存在一个数据结构里面，当一个数据包的所有分包都到达以后（通过计数来判断是否全部到达），将这些分包重组成一个大的数据包，并把这个重组后的大数据包返回给接收方。

什么样的数据结构在这里是有意义的?这里并没有什么特别的数据结构!我使用的是一种我喜欢称之为序列缓冲区的东西。我想和你分享的最核心的技巧是如何让这个数据结构变得高效：

const int MaxEntries = 256;
 
struct SequenceBuffer
{
    bool exists[MaxEntries];
    uint16_t sequence[MaxEntries];
    Entry entries[MaxEntries];
};

原文

原文出处

原文标题 : Packet Fragmentation and Reassembly (How to send and receive packets larger than MTU)

Introduction

Hi, I’m Glenn Fiedler and welcome to Building a Game Network Protocol.

In the previous article we discussed how to unify packet read and write into a single serialize function and added a bunch of safety features to packet read.

Now we are ready to start putting interesting things in our packets and sending them over the network, but immediately we run into an interesting question: how big should our packets be?

To answer this question properly we need a bit of background about how packets are actually sent over the Internet.

Background

Perhaps the most important thing to understand about the internet is that there’s no direct connection between the source and destination IP address. What actually happens is that packets hop from one computer to another to reach their destination.

Each computer along this route enforces a maximum packet size called the maximum transmission unit, or MTU. According to the IP standard, if any computer recieves a packet larger than its MTU, it has the option of a) fragmenting that packet, or b) dropping the packet.

So here’s how this usually goes down. People write a multiplayer game where the average packet size is quite small, lets say a few hundred bytes, but every now and then when a lot of stuff is happening in their game and a burst of packet loss occurs, packets get a lot larger than usual, going above MTU for the route, and suddenly all packets start getting dropped!

Just last year (2015) I was talking with Alex Austin at Indiecade about networking in his game Sub Rosa. He had this strange networking bug he couldn’t reproduce. For some reason, players would randomly get disconnected from the game, but only when a bunch of stuff was going on. It was extremely rare and he was unable to reproduce it. Alex told me looking at the logs it seemed like packets just stopped getting through.

This sounded exactly like an MTU issue to me, and sure enough, when Alex limited his maximum packet size to a reasonable value the bug went away.

MTU in the real world

So what’s a reasonable maximum packet size?

On the Internet today (2016, IPv4) the real-world MTU is 1500 bytes.

Give or take a few bytes for UDP/IP packet header and you’ll find that the typical number before packets start to get dropped or fragmented is somewhere around 1472.

You can try this out for yourself by running this command on MacOS X:

ping -g 56 -G 1500 -h 10 -D 8.8.4.4

On my machine it conks out around just below 1500 bytes as expected:

1404 bytes from 8.8.4.4: icmp_seq=134 ttl=56 time=11.945 ms
1414 bytes from 8.8.4.4: icmp_seq=135 ttl=56 time=11.964 ms
1424 bytes from 8.8.4.4: icmp_seq=136 ttl=56 time=13.492 ms
1434 bytes from 8.8.4.4: icmp_seq=137 ttl=56 time=13.652 ms
1444 bytes from 8.8.4.4: icmp_seq=138 ttl=56 time=133.241 ms
1454 bytes from 8.8.4.4: icmp_seq=139 ttl=56 time=17.463 ms
1464 bytes from 8.8.4.4: icmp_seq=140 ttl=56 time=12.307 ms
1474 bytes from 8.8.4.4: icmp_seq=141 ttl=56 time=11.987 ms
ping: sendto: Message too long
ping: sendto: Message too long
Request timeout for icmp_seq 142

Why 1500? That’s the default MTU for MacOS X. It’s also the default MTU on Windows. So now we have an upper bound for your packet size assuming you actually care about packets getting through to Windows and Mac boxes without IP level fragmentation or a chance of being dropped: 1472 bytes.

So what’s the lower bound? Unfortunately for the routers in between your computer and the destination the IPv4 standard says 576. Does this mean we have to limit our packets to 400 bytes or less? In practice, not really.

MacOS X lets me set MTU values in range 1280 to 1500 so considering packet header overhead, my first guess for a conservative lower bound on the IPv4 Internet today would be 1200 bytes. Moving forward, in IPv6 this is also a good value, as any packet of 1280 bytes or less is guaranteed to get passed on without IP level fragmentation.

This lines up with numbers that I’ve seen throughout my career. In my experience games rarely try anything complicated like attempting to discover path MTU, they just assume a reasonably conservative MTU and roll with that, something like 1000 to 1200 bytes of payload data. If a packet larger than this needs to be sent, it’s split up into fragments by the game protocol and re-assembled on the other side.

And that’s exactly what I’m going to show you how to do in this article.

Fragment Packet Structure

Let’s get started with implementation.

The first thing we need to decide is how we’re going to represent fragment packets over the network so they are distinct from non-fragmented packets.

Ideally, we would like fragmented and non-fragmented packets to be compatible with the existing packet structure we’ve already built, with as little overhead as possible in the common case when we are sending packets smaller than MTU.

Here’s the packet structure from the previous article:

[protocol id] (64 bits) // not actually sent, but used to calc crc32
[crc32] (32 bits)
[packet type] (2 bits for 3 distinct packet types)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

In our protocol we have three packet types: A, B and C.

Let’s make one of these packet types generate really large packets:

static const int MaxItems = 4096 * 4;

struct TestPacketB : public Packet
{
    int numItems;
    int items[MaxItems];

    TestPacketB() : Packet( TEST_PACKET_B )
    {
        numItems = random_int( 0, MaxItems );
        for ( int i = 0; i < numItems; ++i )
            items[i] = random_int( -100, +100 );
    }

    template <typename Stream> bool Serialize( Stream & stream )
    {
        serialize_int( stream, numItems, 0, MaxItems );
        for ( int i = 0; i < numItems; ++i )
        {
            serialize_int( stream, items[i], -100, +100 );
        }
        return true;
    }
};

This may seem somewhat contrived but these situations really do occur. For example, if you have a strategy where you send all un-acked events from server to client and you hit a burst of packet loss, you can easily end up with packets larger than MTU, even though your average packet size is quite small.

Another common case is delta encoded snapshots in a first person shooter. Here packet size is proportional to the amount of state changed between the baseline and current snapshots for each client. If there are a lot of differences between the snapshots the delta packet is large and there’s nothing you can do about it except break it up into fragments and re-assemble them on the other side.

Getting back to packet structure. It’s fairly common to add a sequence number at the header of each packet. This is just a packet number that increases with each packet sent. I like to use 16 bits for sequence numbers even though they wrap around in about 15 minutes @ 60 packets-per-second, because it’s extremely unlikely that a packet will be delivered 15 minutes late.

Sequence numbers are useful for a bunch of things like acks, reliability and detecting and discarding out of order packets. In our case, we’re going to use the sequence number to identify which packet a fragment belongs to:

[protocol id] (64 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type] (2 bits)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

Here’s the interesting part. Sure we could just add a bit is_fragment to the header, but then in the common case of non-fragmented packets you’re wasting one bit that is always set to zero.

What I do instead is add a special fragment packet type:

enum TestPacketTypes
{
    PACKET_FRAGMENT = 0,     // RESERVED
    TEST_PACKET_A,
    TEST_PACKET_B,
    TEST_PACKET_C,
    TEST_PACKET_NUM_TYPES
};

And it just happens to be free because four packet types fit into 2 bits. Now when a packet is read, if the packet type is zero we know it’s a fragment packet, otherwise we run through the ordinary, non-fragmented read packet codepath.

Lets design what this fragment packet looks like. We’ll allow a maximum of 256 fragments per-packet and have a fragment size of 1024 bytes. This gives a maximum packet size of 256k that we can send through this system, which should be enough for anybody, but please don’t quote me on this.

With a small fixed size header, UDP header and IP header a fragment packet be well under the conservative MTU value of 1200. Plus, with 256 max fragments per-packet we can represent a fragment id in the range [0,255] and the total number of fragments per-packet [1,256] with 8 bits.

[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>

Notice that we pad bits up to the next byte before writing out the fragment data. Why do this? Two reasons: 1) it’s faster to copy fragment data into the packet via memcpy than bitpacking each byte, and 2) we can now save a small amount of bandwidth by inferring the fragment size by subtracting the start of the fragment data from the total size of the packet.

Sending Packet Fragments

Sending packet fragments is easy. For any packet larger than conservative MTU, simply calculate how many 1024 byte fragments it needs to be split into, and send those fragment packets over the network. Fire and forget!

One consequence of this is that if any fragment of that packet is lost then the entire packet is lost. It follows that if you have packet loss then sending a 256k packet as 256 fragments is not a very good idea, because the probability of dropping a packet increases significantly as the number of fragments increases. Not quite linearly, but in an interesting way that you can read more about here.

In short, to calculate the probability of losing a packet, you must calculate the probability of all fragments being delivered successfully and subtract that from one, giving you the probability that at least one fragment was dropped.

1 - probability_of_fragment_being_delivered ^ num_fragments

For example, if we send a non-fragmented packet over the network with 1% packet loss, there is naturally a ¹⁄₁₀₀ chance the packet will be dropped.

As the number of fragments increase, packet loss is amplified:

• Two fragments: 1 - (⁹⁹⁄₁₀₀) ^ 2 = 2%


• Ten fragments: 1 - (⁹⁹⁄₁₀₀) ^ 10 = 9.5%


• 100 fragments: 1 - (⁹⁹⁄₁₀₀) ^ 100 = 63.4%


• 256 fragments: 1 - (⁹⁹⁄₁₀₀) ^ 256 = 92.4%

So I recommend you take it easy with the number of fragments. It’s best to use this strategy only for packets in the 2-4 fragment range, and only for time critical data that doesn’t matter too much if it gets dropped. It’s definitely not a good idea to fire down a bunch of reliable-ordered events in a huge packet and rely on packet fragmentation and reassembly to save your ass.

Another typical use case for large packets is when a client initially joins a game. Here you usually want to send a large block of data down reliably to that client, for example, representing the initial state of the world for late join. Whatever you do, don’t send that block of data down using the fragmentation and re-assembly technique in this article.

Instead, check out the technique in next article which handles packet loss by resending fragments until they are all received.

Receiving Packet Fragments

It’s time to implement the code that receives and processed packet fragments. This is a bit tricky because we have to be particularly careful of somebody trying to attack us with malicious packets.

Here’s a list of all the ways I can think of to attack the protocol:

• Try to send out of bound fragments ids trying to get you to crash memory. eg: send fragments [0,255] in a packet that has just two fragments.




• Send packet n with some maximum fragment count of say 2, and then send more fragment packets belonging to the same packet n but with maximum fragments of 256 hoping that you didn’t realize I widened the maximum number of fragments in the packet after the first one you received, and you trash memory.




• Send really large fragment packets with fragment data larger than 1k hoping to get you to trash memory as you try to copy that fragment data into the data structure, or blow memory budget trying to allocate fragments




• Continually send fragments of maximum size (²⁵⁶⁄₂₅₆ fragments) in hope that it I could make you allocate a bunch of memory and crash you out. Lets say you have a sliding window of 256 packets, 256 fragments per-packet max, and each fragment is 1k. That’s 64 mb per-client.




• Can I fragment the heap with a bunch of funny sized fragment packets sent over and over? Perhaps the server shares a common allocator across clients and I can make allocations fail for other clients in the game because the heap becomes fragmented.

Aside from these concerns, implementation is reasonably straightforward: store received fragments somewhere and when all fragments arrive for a packet, reassemble them into the original packet and return that to the user.

Data Structure on Receiver Side

The first thing we need is some way to store fragments before they are reassembled. My favorite data structure is something I call a sequence buffer:

const int MaxEntries = 256;

struct SequenceBuffer
{
    uint32_t sequence[MaxEntries];
    Entry entries[MaxEntries];
};

Indexing into the arrays is performed with modulo arithmetic, giving us a fast O(1) lookup of entries by sequence number:

const int index = sequence % MaxEntries;

A sentinel value of 0xFFFFFFFF is used to represent empty entries. This value cannot possibly occur with 16 bit sequence numbers, thus providing us with a fast test to see if an entry exists for a given sequence number, without an additional branch to test if that entry exists.

This data structure is used as follows. When the first fragment of a new packet comes in, the sequence number is mapped to an entry in the sequence buffer. If an entry doesn’t exist, it’s added and the fragment data is stored in there, along with information about the fragment, eg. how many fragments there are, how many fragments have been received so far, and so on.

Each time a new fragment arrives, it looks up the entry by the packet sequence number. When an entry already exists, the fragment data is stored and number of fragments received is incremented. Eventually, once the number of fragments received matches the number of fragments in the packet, the packet is reassembled and delivered to the user.

Since it’s possible for old entries to stick around (potentially with allocated blocks), great care must be taken to clean up any stale entries when inserting new entries in the sequence buffer. These stale entries correspond to packets that didn’t receive all fragments.

And that’s basically it at a high level. For further details on this approach please refer to the example source code for this article.

Click here to get the example source code for this article series.

Test Driven Development

One thing I’d like to close this article out on.

Writing a custom UDP network protocol is hard. It’s so hard that even though I’ve done this from scratch at least 10 times, each time I still manage to fuck it up in a new and exciting ways. You’d think eventually I’d learn, but this stuff is complicated. You can’t just write low-level netcode and expect it to just work.

You have to test it!

My strategy when testing low-level netcode is as follows:

• Code defensively. Assert everywhere. These asserts will fire and they’ll be important clues you need when something goes wrong.




• Add functional tests and make sure stuff is working as you are writing it. Put your code through its paces at a basic level as you write it and make sure it’s working as you build it up. Think hard about the essential cases that need to be property handled and add tests that cover them.




• But just adding a bunch of functional tests is not enough. There are of course cases you didn’t think of! Now you have to get really mean. I call this soak testing and I’ve never, not even once, have coded a network protocol that hasn’t subsequently had problems found in it by soak testing.




• When soak testing just loop forever and just do a mix of random stuff that puts your system through its paces, eg. random length packets in this case with a huge amount of packet loss, out of order and duplicates through a packet simulator. Your soak test passes when it runs overnight and doesn’t hang or assert.




• If you find anything wrong with soak testing. You may need to go back and add detailed logs to the soak test to work out how you got to the failure case. Once you know what’s going on, stop. Don’t fix it immediately and just run the soak test again.




• Instead, add a unit test that reproduces that problem you are trying to fix, verify your test reproduces the problem, and that it problem goes away with your fix. Only after this, go back to the soak test and make sure they run overnight. This way the unit tests document the correct behavior of your system and can quickly be run in future to make sure you don’t break this thing moving forward when you make other changes.




• Add a bunch of logs. High level errors, info asserts showing an overview of what is going on, but also low-level warnings and debug logs that show what went wrong after the fact. You’re going to need these logs to diagnose issues that don’t occur on your machine. Make sure the log level can be adjusted dynamically.




• Implement network simulators and make sure code handles the worst possible network conditions imaginable. 99% packet loss, 10 seconds of latency and +/- several seconds of jitter. Again, you’ll be surprised how much this uncovers. Testing is the time where you want to uncover and fix issues with bad network conditions, not the night before your open beta.




• Implement fuzz tests where appropriate to make sure your protocol doesn’t crash when processing random packets. Leave fuzz tests running overnight to feel confident that your code is reasonably secure against malicious packets and doesn’t crash.




• Surprisingly, I’ve consistently found issues that only show up when I loop the set of unit tests over and over, perhaps these issues are caused by different random numbers in tests, especially with the network simulator being driven by random numbers. This is a great way to take a rare test that fails once every few days and make it fail every time. So before you congratulate yourself on your tests passing 100%, add a mode where your unit tests can be looped easily, to uncover such errors.




• Test simultaneously on multiple platforms. I’ve never written a low-level library that worked first time on MacOS, Windows and Linux. There are always interesting compiler specific issues and crashes. Test on multiple platforms as you develop, otherwise it’s pretty painful fixing all these at the end.




• This about how people can attack the protocol. Implement code to defend against these attacks. Add functional tests that mimic these attacks and make sure that your code handles them correctly.

This is my process and it seems to work pretty well. If you are writing a low-level network protocol, the rest of your game depends on this code working correctly. You need to be absolutely sure it works before you build on it, otherwise it’s basically a stack of cards.

In my experience, game neworking is hard enough without having suspicions that that your low-level network protocol has bugs that only show up under extreme network conditions. That’s exactly where you need to be able to trust your code works correctly. So test it!

译文

译文出处

[protocol id] (64 bits) // not actually sent, but used to calc crc32
[crc32] (32 bits)
[packet type] (2 bits for 3 distinct packet types)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

[protocol id] (64 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type] (2 bits)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>

[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>

自我总结本篇概要

• 读取数据的时候要特别小心， 因为可能会有攻击者发送过来的恶意的数据包以及错误的包， 在写入数据的时候你可能会轻松很多，因为如果有任何事情出错了，那几乎肯定是你自己导致的错误

• 统一的数据包序列化功能 ：诀窍在于让流类型的序列化函数模板化。在我的系统中有两个流类型：ReadStream类和WriteStream类。每个类都有相同的一套方法，但实际上它们没有任何关系。一个类负责从比特流读取值到变量中，另外一个类负责把变量的值写到流中。
  在模板里类似这样写, 通过 Stream::IsWriting 和 Stream::IsReading 模板会自动区分,然后帮你生产你想要的代码, 简洁漂亮

  class WriteStream { public: enum { IsWriting = 1 }; enum { IsReading = 0 }; // ... }; class ReadStream { public: enum { IsWriting = 0 }; enum { IsReading = 1 }; // .. } template <typename Stream> bool serialize( Stream & stream, float & value ) { union FloatInt { float float_value; uint32_t int_value; }; FloatInt tmp; if ( Stream::IsWriting ) tmp.float_value = value; bool result = stream.SerializeBits( tmp.int_value, 32 ); if ( Stream::IsReading ) value = tmp.float_value; return result; }

• 边界检查和终止读取 ： 把允许的大小范围也传给序列化函数而不仅仅是所需的比特数量。

• 序列化浮点数和向量 ： 计算机根本不知道内存中的这个32位的值到底是一个整数还是一个浮点数还是一个字符串的部分。它知道的就是这仅仅是一个32位的值。代码如下(可以通过一个联合体来访问看上去是整数的浮点数).
  有些时候，你并不想把一个完整精度的浮点数进行传递。那么该如何压缩这个浮点值？第一步是将它的值限制在某个确定的范围内然后用一个整数表示方式来将它量化。
  举个例子来说，如果你知道一个浮点类型的值是在区间[-10,+10]，对于这个值来说可以接受的精确度是0.01，那么你可以把这个浮点数乘以100.0让它的值在区间[-1000,+1000]并在网络上将其作为一个整数进行序列化。而在接收的那一端，仅仅需要将它除以100.0来得到最初的浮点值.

  union FloatInt { float float_value; uint32_t int_value; }; FloatInt tmp; tmp.float_value= 10.0f; printf(“float value as an integer: %x\n”, tmp.int_value );

• 序列化字符串和数组 : 为什么要费那么大精力把一个字节数组按比特打包到你的比特流里?为什么不在序列化写入之前进行按字节进行对齐？Why not align to byte so you can memcpy the array of bytes directly into the packet?
  如何将比特流按字节对齐？只需要在流的当前位置做些计算就可以了，找出还差写入多少个比特就能让当前比特流的比特数量被8整除，然后按照这个数字插入填充比特（比如当前比特流的比特数量是323，那么323+5才能被8整除，所以需要插入5个填充比特）。对于填充比特来说，填充的比特值都是0，这样当你序列化读取的时候你可以进行检测，如果检测的结果是正确的，那么就确实是在读取填充的部分，并且填充的部分确实是0。一直读取到下一个完整字节的比特起始位置（可以被8整除的位置）。如果检测的结果是在应该填充的地方发现了非0的比特值，那么就中止序列化读取并丢弃这个数据包。

• 序列化数组的子集 : 当实现一个游戏网络协议的时候，或早或晚总会需要序列化一个对象数组然后在网络上传递。比如说服务器也许需要把所有的物体发送给客户端，或者有时候需要发送一组事件或者消息。如果你要发送所有的物体到客户端，这是相当简单直观的，但是如果你只是想发送一个数组的一个子集怎么办？
  最先想到也是最容易的办法是遍历数组的所有物体然后序列化一个bool数组，这个bool数组标记的是对应的物体是否通过网络发送。如果bool值为1那么后面会跟着物体的数据，否则就会被忽略然后下一个物体的bool值取决于流的下一个值。
  如果有大量的物体需要发送，举个例子来说，整个场景中有4000个物体，有一半的物体也就是2000个需要通过网络进行发送。每个物体需要一个序号，那么就需要2000个序号，每个序号需要12比特。。。。这就是说数据包里面24000比特或者说接近30000比特（几乎是30000，不是严格是，译注：原文如此）的数据被序号浪费掉了.
  可以把序号的编码方式修改下来节省数据，序号不再是全局序号，而是相对上一个物体的相对序号。
• 如何应对恶意数据包和错误包 : 如果某些人发送一些包含随机信息的恶意数据包给你的服务器。你会不会在解析的时候把服务器弄崩溃掉？
  有三种技术应对 :
  • 协议ID : 在你的数据包里面包含协议ID。一般典型的做法是，头4个字节你可以设定一些比较罕见而且独特的值，你可以通过这３２比特的数据判断出来根本就不是你的应用程序的包，然后就可以直接丢弃了。
  • CRC32 : 对你的数据包整体做一个CRC32的校验，并把这个校验码放到数据包的包头。可以不发送这个协议ID，但是发送方和接收方提前确认过这个协议ID是什么，并在计算数据包CRC32值的时候装作这个数据包带上了这个协议ID的前缀来参与计算。这样如果发送方使用的协议ID与接收方不一致的时候，CRC32的校验就会失败，这将为每个数据包节省4个字节.
  • 序列化检测 : 是在包的中间，在一段复杂的序列化写入之前或者之后写上一个已知的32比特整数，并在另外一端序列化读取的时候用相同的值进行检测判断。如果序列化检查值是不正确的，那么就中止序列化读取并丢弃这个数据包。
    . . .

自我总结

这篇文章只是介绍, 之后的文章才是正题. 此篇文章大体介绍了 :

• 文本格式传输的低效率问题， 为了可读性而产生了太多冗余无用数据
• 为什么不用目前已经有了的库比如Protocol Buffers：因为我们不需要版本信息，也不需要什么跨语言的支持。所以让我们直接忽略掉这些功能并用我们自己的不带属性的二进制流进行代替，在这个过程中我们可以获得更多的控制性和灵活性
• 要注意大小端的问题
• 实现一个位打包器， 工作在32位或者64位的级别， 而不是是工作在字节这个级别。因为现代机器对这个长度进行了专门的优化而不应该像1985年那样在字节的级别对缓冲区进行处理。
• 要注意防止恶意数据包的问题 ：
  • 我们需要实现一个方法来判断整数值是否超出预期范围，如果超出了就要中止网络包的读取和解析，因为会有一些不怀好意的人给我们发送恶意网络包希望我们的程序和内存崩溃掉。网络包的读取和解析的中止必须是自动化的，而且不能使用异常处理，因为异常处理太慢了会拖累我们的程序。
  • 如果独立的读取和写入函数是手动编解码的，那么维护它们真的是一个噩梦。我们希望能够为包一次性的编写好序列化代码并且没有任何运行时的性能消耗（主要是额外的分支、虚化等等）。
• 我们为了不想自己手动检查各种可能会被攻击的地方， 需要实现检查自动化， 在下一篇文章 构建游戏网络协议二之序列化策略 里将会说。
  . . .

感觉之前的博客已经整理了大多数之前的关于基础的私人笔记, 现在应该可以讨论一下实操的东西了.
先来一发之前的kbe在ubuntu下的编译笔记吧, 因为官方对于ubuntu下的kbe编译文档是有问题的.

. . .