构建游戏网络协议三之数据包的分包和重组

Posted on | In

本篇自我总结

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

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

每台计算机(路由器)会沿着路由强制要求数据包的大小会有一个最大的上限，这个上限就是所谓的最大传输单元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了也无所谓的情况。绝对不要只是为了省事就把一大堆依赖顺序的事件打到一个大数据包里面然后依赖数据包的分包和重组机制进行发送。这会让事情变得更加麻烦。

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

接收分包后的数据包

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

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

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

1
2
3
4
5
6
7
8
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 1⁄100 chance the packet will be dropped.


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


  • Two fragments: 1 - (99⁄100) ^ 2 = 2%

  • Ten fragments: 1 - (99⁄100) ^ 10 = 9.5%

  • 100 fragments: 1 - (99⁄100) ^ 100 = 63.4%

  • 256 fragments: 1 - (99⁄100) ^ 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 (256⁄256 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!

译文

译文出处

译者：崔嘉艺(milan21) 审校：崔国军（星际迷航）

大家好，我是格伦·菲德勒。欢迎大家阅读系列教程《构建游戏网络协议》的第三篇文章。在之前的文章中，我们讨论了如何将数据包的读取和写入用一个单独的序列化函数来实现。


现在我们要开始把一些有趣的事情放到这些数据包中，,但正如你即将开始编码的令人惊叹的多人在线动作、第一人称射击、大型多人在线角色扮演游戏、多人在线战术竞技游戏会发生的那样，当你以每秒120次的频率发送8k大小的数据包，游戏网络中会传来一个声音呼喊着你:“不要发送超过1200字节大小的数据包!”

但是都已经2016年了，你真的要注意最大传输单元这个东西么?

不幸的是，答案是是的！


最大传输单元MTU

你可能已经听说过最大传输单元了。在网络程序员中流传着大量有关最大传输单元问题的故事。那么这到底是怎么回事呢？究竟什么是最大传输单元?为什么你要在乎最大传输单元这个事情？

当你通过互联网来发送数据包的时候到底背后发生了什么？这些数据包要从一台计算机(路由器)跳到另一个计算机(路由器)上，如此往复多次才能到达自己的目的地。这是一个分组交换网络具体如何运作的方式。在大部分时间里，它的工作方式不像是在源和目的地之间存在一条直接的连接。


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


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


就在去年(2015年)，我与亚历克斯·奥斯汀在Indiecade谈论他的游戏” Sub Rosa “中的网络部分。他遇到了一些奇怪的无法重现的网络bug。出于某种原因，一些客户端（在所有玩家里面总是有那么一个或者两个）会随机的从游戏中断开连接并且其他人都能够正常游戏。查看日志的话，亚历克斯又觉得一切都是正常的，只是看上去好像数据包突然停止进行传递了。


对我来说，这听上去就像是一个最大传输单元所引起的问题，并且我非常确信。当亚历克斯把他最大的数据包大小限制在一个合理的值之内，这个bug就再也没有出现了。



真实世界中的最大传输单元MTU

所以什么是“一个合理的数据包的大小”？

在今天的互联网上(2016年，还是基于IPv4)，典型的最大传输单元的大小是1500字节。在UDP/IP数据包的包头添加或者去掉几个字节，你会发现在数据包开始出现被丢弃或者被分包情况的一个典型的边界值是1472。

你可以自己在MacOS X尝试运行下下面这个命令：

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

在我的机器上，这个结果在略微低于1500字节的大小上下浮动，符合预期：

1404bytes from 8.8.4.4: icmp_seq=134 ttl=56 time=11.945 ms

1414bytes from 8.8.4.4: icmp_seq=135 ttl=56 time=11.964 ms

1424bytes from 8.8.4.4: icmp_seq=136 ttl=56 time=13.492 ms

1434bytes from 8.8.4.4: icmp_seq=137 ttl=56 time=13.652 ms

1444bytes from 8.8.4.4: icmp_seq=138 ttl=56 time=133.241 ms

1454bytes from 8.8.4.4: icmp_seq=139 ttl=56 time=17.463 ms

1464bytes from 8.8.4.4: icmp_seq=140 ttl=56 time=12.307 ms

1474bytes from 8.8.4.4: icmp_seq=141 ttl=56 time=11.987 ms

ping:sendto: Message too long

ping:sendto: Message too long

Requesttimeout for icmp_seq 142

为什么是1500字节？这是MacOS X上默认的最大传输单元的大小。这也是Windows平台上默认的最大传输单元的大小。所以现在我们对数据包的大小有了一个上限（也就是不能超过这个默认的最大传输单元的大小），假如你真的关心数据包通过Windows平台或者Mac平台进行传播而不希望数据包在IP层进行分包或者有被丢弃的可能的话，那么就要保证数据包的大小不能超过这个上限：1472个字节。


那么这个最大传输单元的大小的下限是多少呢？MacOS X允许设置的最大传输单元的大小的值是在1280到1500，所以我对现在互联网上通过IPv4进行传播的数据包的最大传输单元的大小的下限有一个比较保守的估计，就是1200字节。如果是在通过IPv4进行传播的情况下这个比较保守的大传输单元的大小的下限也会是一个很好的估计值，任意数据包只要大小小于1280字节都能保证在没有IP层分包的情况下顺利的传播。


这个估计与我在职业生涯中感受到的情况是比较一致的。以我的经验来看，很少有游戏会试图做这些复杂的事情，诸如尝试发现路径上的最大传输单元的大小之类的，它们一般都是假定一个合理又保守的最大传输单元的大小然后一直遵循这个值。如果出现一个要发送的数据包比这个保守的最大传输单元的大小要大的情况，游戏协议会将这个数据包分成几个包然后在网络的另外一侧进行重组。

而这正是我要在这篇文章里面要向你传授的内容。


分包后的数据包的结构

让我们从决定该对网络上传输的数据分包后采用什么的结构进行表示来开始构建我们的数据包分包和重组机制。在理想状态下，我们希望分包以后的数据包和未分包的数据包兼容我们现在已经建立好的数据包结构，这样当我们发送小于最大传输单元的大小的数据包的时候，网络协议没有任何多余的负载。

下面是在前一篇文章结束的时候得到的数据包的结构：



[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)


在我们这个例子之中，我们一共有三个数据包的类型，分别是Ａ、Ｂ和Ｃ。

让我们用这三个数据包类型中的一个制造一个比最大传输单元的大小还要大一些的数据包：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static const int MaxItems = 4096 * 4;
struct TestPacketB : public protocol2::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;
}
};


这可能看起来不怎么自然，但在现实世界中这些情况真的会发生。举个简单的例子来说，如果你有一个策略，这个策略是从服务器往客户端发送所有的未确认的事件，你会得到一组可信赖也有序的事件，但是也会遇到大量数据包的丢失的情况，你会轻易的遇到数据包比最大传输单元的大小还要大的情况，即使你的数据包的平均大小非常小。（译注：这是由于丢包重传导致的不停重发，而重发的数据包在UDP或者TCP上会进行合并。所以即使数据包的平均大小远小于最大传输单元的大小，但是由于大量这样的数据包的合并，还是很容易出现超过最大传输单元的大小的情况）。


在大多数的情况下，通过实现这么一个策略：在一个数据包里面只包含很少一组事件或者状态更新来避免数据包的大小超过最大传输单元的大小，采用这种策略以后可以有效的规避上面的那种情况。这种规划在很多情况下都工作的很棒。。。但是有一种情况下这种策略也是存在问题的，这种情况就是增量编码。


由一个增量编码器创建的数据包的大小是与当前状态与之前状态之间所发生的状态变化的数量成正比的。如果这两个状态之间有大量的不同的话，那么增量也将很大并且你对这种情况其实是没有什么办法的。如果出现一个增量恰好比最大传输单元的大小要大的情况，当然这是一个坏运气下才会出现的情况，但是你仍然要发送这个超过最大传输单元的大小的数据包！所以你可以看到，在增量编码的情况下，你真的不能限制数据包的最大大小一定小于最大传输单元的大小，在这种情况下，数据包的分包和重组策略就有了用武之地。


让我们回到数据包的结构上面来。在每个数据包的包头的地方添加一个序号是一种非常常见的做法。这并没有什么复杂的。这只是一个数据包的序号，会在每个数据包进行发送的时候依次加一。举个例子来说，就是0、1、2、3这么简单。我喜欢用16比特来表示这个序号，即使在每秒发送60个数据包的情况下，只要15分钟序号就会被用完一遍，需要再次从头开始重用，但是这么做也没有什么关系，主要是因为你在网络上收到一个15分钟之前发送出去的数据包是一个非常罕见的事情，所以你很少会有机会困惑这到底是一个新的数据包还是一个旧的数据包（因为IP层在包头的地方有个跳转计数，超出一定跳转次数的数据包会被丢弃掉，所以基本不用担心这种情况）。如果你确实关心这个问题的话，请使用32比特的序号进行代替。


无论你选择用多少比特来表示这个序号，它们对于很多事情都是有用的，比如说可依赖性、检测和丢弃乱序的数据包等等。除此之外，我们需要一个数据包序号的原因是在对数据包进行分包的时候，我们需要某个方法来确定这个数据包的分包到底是属于哪个数据包的。

所以，让我们在我们的数据包的结构里面加上序号这个东西：



[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)


这是最有趣的部分。我们可以在数据包的头部只添加一个比特的标识 is_fragment，但是对于通常情况下根本不需要分包的数据包来说，你就浪费了一个比特，因为它总是要被置为0。这不是很好。

相反，我的选择是在数据包的结构里面添加了一个特殊的”分包后的数据包“的类型：

?
1
2
3
4
5
6
7
8
enum TestPacketTypes
{
PACKET_FRAGMENT = 0, // RESERVED
TEST_PACKET_A,
TEST_PACKET_B,
TEST_PACKET_C,
TEST_PACKET_NUM_TYPES
};

这恰好不需要占据任何的空间，是因为四个数据包类型正好可以用两个比特来表示，而这两个比特的空间已经用于表示数据包类型了，我们只是在原来的枚举上新加了一个类型。这么处理以后，每次当我们读取一个数据包的时候，如果这个数据包的类型是0的话，我们就知道这个数据包是一个特殊的分包以后的数据包，它的内存布局可以通过数据包的类型得知，否则的话，我们就走回原来的通用的对非分包的数据包进行读取和处理的方法。

让我们设计下这个分包后的数据包看起来应该是什么样子的。我们将允许一个数据包最多可以分成256个数据包，并且每个分包后的数据包的大小不会超过1024个字节。这样的话，我们就可以通过这样一个系统来发送大小最大为256k的数据包，这对于任意系统任意情况来说都应该是足够的，但是这只是我个人的一个看法，如果有特殊的情况，还请结合实际情况进行具体分析。

有了这么一个不大的固定大小的数据包包头结构，再加上UDP的包头结构以及IP的包头结构，一个分包以后的数据包会小于之前我们保守估计的最大传输单元的大小：1200字节。除此之外，因为一个数据包最多可以分包成256个数据包，我们可以用【0，255】这个范围来表示分包的id和序号，这样每个分包里面还需要有8比特来表示这个序号。



[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>


请注意，我们把这几个比特对齐到了下一个字节，然后才把对齐以后的数据写入到数据包里面。我们为什么要这么做？这么做其实是有两个原因的: 1) 这么处理以后可以通过memcpy函数更快的把分包的数据拷贝到数据包里面而不需要使用位打包器来对每个字节进行处理。2) 我们通过不发送分包数据的大小节省了一小部分带宽。我们可以通过从数据包的整体大小减去分包数据起始位置的字节序号来推断出这个分包的大小。


发送分包以后的数据包

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

这种发送以后不记录发送的数据包的内容的方法有一个后果，就是数据包的任意一个分包如果丢失的话，那么整个数据包就都要丢弃。由此可见，当你需要发送要给256K的数据包的时候要发送256个分包，如果有一个分包丢失的话，你就要重新把这个256k的数据包再分一次包然后再发送出去。这绝对不是一个好主意。

这显然是一个很糟糕的办法，因为随着分包数目的增多，发生丢失的概率肯定是显著的增大。这种增长关系不是线性的，而是一种相当复杂的关系，如果你对这个计算感兴趣的话，你可以读下这篇文章。

简而言之，如果你要计算一个数据包会被丢弃的概率，你必须要计算所有分包被成功发送到目的地的概率，然后从1中减去这个概率，得到的结果就是至少有一个分包丢失的概率。

下面这个公式可以用来计算因为分包丢失导致整个数据包被丢弃的概率：

＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼

1- ( probability of fragment being delivered ) ^ num_fragments

＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼＼

让我们举个简单的例子对上面这个公式进行说明，如果我们发送的一个不需要分包的数据包，如果它在网络上传说的时候丢失的概率是1%，那么只有百分之一的概率会出现这个数据包被丢弃的情况，或者我们不要嫌麻烦，把这些数据代入到上面这个公式里面: 1 – (99/100) ^ 1 = 1/100 = 1%。

随着分包数量的增加，整个数据包被丢弃的概率也随之增加：

  • 两个分包的情况： 1 – (99/100) ^ 2 = 2%。
  • 十个分包的情况： 1 – (99/100) ^ 10 = 9.5%。
  • 一百个分包的情况： 1 – (99/100) ^ 100 = 63.4%。
  • 二百五十六个分包的情况： 1 – (99/100) ^ 256 = 92.4%。

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

大数据包的另外一种典型的用途是当客户端新连入一个游戏服务器的时候。游戏服务器通常会把大块的数据以一种可靠的方式下发给客户端。对于后期才加入的客户端而言，这些大块的数据也许代表了世界的初始状态。无论这些数据包含了怎么样的信息，请不要使用本篇文章的分包技巧来给客户端下发大块的数据。相反，请查阅这个系列教程的下篇文章，在那篇文章里面将讲解如何在有数据包可能发生丢失的情况下，快速可靠的发送大块的数据直到这些大块的数据完全被确认接收。



对分包后的数据包的接收

尽管发送分包以后的数据包是一件相同简单的事情，但是对分包后的数据包进行接收就相对需要技巧了。

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



[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>


下面列出的是我能想到的如何攻击你的协议以便让你的服务器崩溃的所有方法：

  • 尝试发送分包ID在一个限制范围内的分包，看看能不能让你的程序崩溃。举个例子来说，也许这个数据包只有两个分包，但是我会发送多个分包ID在【０，２５５】之内的分包。
  • 发送一个数据包，让我们假设这个书包的最大分包数量是2，然后发送多个属于这个数据包的分包，但是在分包的数据包报头里面把最大分包的数量改为256，来希望你在接收完第一个分包以后，不会发现分包的最大数量信息被改变了，这样就有可能造成你的内存崩溃。
  • 发送非常大的分包，让分包里面的数据超过1k，测试下你在试图把分包数据拷贝到数据结构的时候是否有良好的判断，如果没有良好的判断的话，这也许会让你的内存崩溃，或者占用大量的内容让你在分配新的分包的时候没有空间。
  • 持续的给你的程序发送最大分包数目的分包（也就是如果最大分包数目是256的话，就持续不断的发送分包ID是256的数据包），希望你会分配大量的内容来容纳这些分包然后让你的内存崩溃。让我们假设你的程序中有一个滑动窗口，这个滑动窗口有256个数据包，每个数据包最多可以有256个分包，每个分包预留的空间是1k。那么也就是会给每个客户端预留67,108,864字节或者64mb的空间。我可以通过这种方法让服务器崩溃么？我能用一堆大小有趣的分包来耗尽的你地址空间的heap空间么？因为服务器的程序是你来设计实现的，所以只有你才知道这个问题的确切答案。它取决于你的内存预算以及如何分配内存来存储分包。如果你考虑过了觉得这会是一个问题，那么就限制下缓冲区中分包的数目或考虑减少每个数据包的分包的最大数目。考虑给每个分包静态分配数据结果或者使用一个内存池来减少内存碎片。


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


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

?
1
2
3
4
5
6
7
8
const int MaxEntries = 256;
struct SequenceBuffer
{
bool exists[MaxEntries];
uint16_t sequence[MaxEntries];
Entry entries[MaxEntries];
};


这里面有几件事情值得注意。首先，使用类似数组的结构可以允许对给定条目是否存在于一个序列缓冲区的存在性进行快速测试并且将测试结果进行缓存，即使每个数据包的条目结构是非常大的（而且这种结构对于数据包的分包和重组来说是非常棒的）。

那么我们该如何使用这个数据结构？当你接收到一个分包以后的数据包以后，这个数据包会携带一个序号指定它是属于哪个数据包的分包。这个序号会随着发送而不停的增大(所有序号全部用完导致发生环绕除外)， 所以最关键的技巧是你要对序号进行散列让散列后的序号进入一个数组中某个给定的位置，具体处理过程如下所示：

int index = sequence % MaxEntries;

现在你可以用O(1)的时间复杂度进行一个快速测试，来通过序号看下一个给定的条目是否存在，并且判断下这个条目是否和你想要读取或者写入的数据包序号相匹配。也就是说，你既需要测试存在性又需要测试序号是否是预期的序号，这是因为所有的序号都是有效的数字(比如说是0)，还有就是因为根据一个特定的数据包序号查找到的条目可能是存在的，但是它属于过去的一个序号（比如说，这是某个其他的序号，但是恰巧通过取模的计算得到相同的序号）。

所以当一个新的数据包的第一个分包到达的时候，你需要把数据包的序号散列成一个索引，如果发现这个索引对应的内容还不存在的话，你需要设置exists[index] = 1，并设置sequence[index]来匹配你正在处理的数据包，并把这个分包储存在序号缓冲区对应的条目里面。这样当下一次有分包实际到达的时候，你会得到相同的序号，然后得到一个相当的索引，在查找的时候会发现对应这个索引的内容已经存在了，并且这个条目的序号正好能和刚刚接收到的数据包的序号匹配，所以你就可以把这个分包累加到这个条目上，这个过程会一直重复直到这个数据包的所有分包都被接收到为止。

如果从比较抽象的层次来解释这个事情的话，基本原理大概就是这样的。这种方法的一个更完整的解释请参阅本文的示例源代码。在地址https://www.patreon.com/gafferongames可以获取本系列文章示例的源代码。


网络协议的测试驱动开发

还有一件事情我想在文章的末尾进行补充说明。我感觉如果我不向我的读者提及这个方法的话，就是对他们的一个伤害。

编写一个定制的网络协议是非常困难的。这个过程是如此的苦难以至于我从头开始至少编写了10次网络协议，但是每次我都觉得我在用一种全新的有趣的方法在做这个事情。也许你会认为是我在挑战自己，用一些新奇的方法来实现这个过程，但其实是这个过程太复杂了，完全没有办法按照预期的那样写完代码就期待它们能够正确的工作。你需要对写出来的代码进行测试！


当编写底层网络协议层的代码的时候，我的策略是:

1、防御性编程。在一切可能的地方进行断言。当某些地方出现错误的时候这些断言会起作用，并且将成为查找问题的重要线索。

2、添加函数的功能测试，确保它们是如你的预期那样工作的。把你的代码放到一个可以运行和测试的环境下，这样可以不时地对它们进行测试以便可以确保它一直会像你起初创建它们时候那样良好的工作。仔细考虑有哪些情况需要正确的处理并给这些情况添加测试。

3、虽然函数测试非常有必要，但是只是添加一些函数测试是远远不够的。无论如何都有遇到你没有预料到的情况! 现在你必须把它们放到一个真实的环境下看看到底会发生什么。我把这个称之为浸泡测试，并且在我之前编写网络协议的过程中还从来没有过在浸泡测试的过程中没有发现问题的情况。浸泡测试只是在不停的循环，并会随机的做一些事情让你的系统在它的空间中处理一些情况，让我们举些简单的例子对它进行一些简单的说明，比如说构造出随机长度的数据包，而且这些数据包有一个非常高的丢失率，通过数据包模拟器发出的大量乱序并且重复的数据包等等。如果你的程序能够在一晚上的时间里面不挂起或者遇到断言，那么就算你的程序通过了浸泡测试。

4、如果你的程序在浸泡测试的过程中发现了某些问题。你可能需要在代码里面添加一些详细的日志以便下次在浸泡测试的时候如果遇到了同样的问题你可以找到出现问题的原因。一旦你知道发生了什么，就可以停止了。不要立即的修复这个问题并且再次运行浸泡测试。这种做法非常的愚蠢。相反，利用单元测试来不停的重现你需要修复的问题，确保单元测试能够重现问题，而且这个问题因为你的修复已经彻底修好了。只有在这样的处理流程之后，才能回到浸泡测试并确保程序在浸泡测试能正常运转一整夜。通过这种方式，单元测试能够记录你的系统的正确的行为并且在以后需要的时候可以快速的运行起来，确保当你做其他改变的时候不会导致一些原来修过的问题重复的出现。


这就是我的数据包分包和重组的处理流程了，它似乎工作的不错。如果你在进行一些底层的网络协议的设计，你的游戏的其他的部分将依赖于底层的网络协议的设计。在你继续构建其他的功能之前，你需要绝对的确认底层的网络协议是否能够正常的工作，否则就像一堆胡乱堆积的卡片，很容易就散架了。多人在线游戏的网络部分是非常困难的，如果不小心设计的话，很容易就会出现底层网络协议可能无法正常的工作或者存在缺陷。所以请确保你是知道你的底层网络协议是如何工作的！

即将到来的文章的预告

下一篇文章是: 《发送大块的数据》

请继续阅读本系列的下一篇文章，在哪篇文章里面我将向你展示如何通过数据包快速可信赖的发送大块的数据，如果其中一块数据丢失了也不需要丢弃整个数据包！

如果你觉得这篇文章有价值的话，请在patreon上支持我的写作，这样我会写的更快。你可以在BSD 3.0许可下访问到这篇文章里面的代码。非常感谢你的支持！


【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。