本篇自我总结

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

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

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

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

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

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

1
2
3
4
5
6

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的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
}

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

1

const int index = sequence % BufferSize;

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

1
2
3
4
5
6

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

本篇自我总结

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

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

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

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

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

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

本篇基本术语

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。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

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

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  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毫秒了就重新发送。我只是列举适合我自己的方案！

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

1
2
3
4
5
6
7
8
9
10
11
12

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，这样我们就准备好接收下一个块了。

1
2
3
4
5
6
7
8
9
10
11

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攻击完全不可能的。

本篇自我总结

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

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

每台计算机(路由器)会沿着路由强制要求数据包的大小会有一个最大的上限，这个上限就是所谓的最大传输单元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];
};

自我总结本篇概要

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

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

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

  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来得到最初的浮点值.

  1 2 3 4 5 6 7 8 9

  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年那样在字节的级别对缓冲区进行处理。
• 要注意防止恶意数据包的问题 ：
  • 我们需要实现一个方法来判断整数值是否超出预期范围，如果超出了就要中止网络包的读取和解析，因为会有一些不怀好意的人给我们发送恶意网络包希望我们的程序和内存崩溃掉。网络包的读取和解析的中止必须是自动化的，而且不能使用异常处理，因为异常处理太慢了会拖累我们的程序。
  • 如果独立的读取和写入函数是手动编解码的，那么维护它们真的是一个噩梦。我们希望能够为包一次性的编写好序列化代码并且没有任何运行时的性能消耗（主要是额外的分支、虚化等等）。
• 我们为了不想自己手动检查各种可能会被攻击的地方， 需要实现检查自动化， 在下一篇文章 构建游戏网络协议二之序列化策略 里将会说。
  . . .

原文

原文出处

原文标题 : Reading and Writing Packets (Best practices for reading and writing packets)

Introduction

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

In this article we’re going to explore how AAA multiplayer games like first person shooters read and write packets. We’ll start with text based formats then move into binary hand-coded binary formats and bitpacking.

At the end of this article and the next, you should understand exactly how to implement your own packet read and write the same way the pros do it.

自我总结

状态同步的要点为 :

• input+state : 既通过网络发送输入信息又会发送状态信息来进行同步
• 发送端
  • 优先级累加器 : 只发送一些重要的实体状态更新, 而不是所有都发. 如果遇到一个物体的状态更新信息不合适放到这个数据包里面，那么就跳过这个物体并尝试下一个。当你序列化完这个数据包以后，将那些已经在这帧更新过的物体在优先级累加器里面的值重置为0，但是那些没有在这帧更新过的物体在优先级累加器里面的值则保持不变。
• 接收端
  • 抗网络抖动 : 做一个jitter buffer来缓冲数据, 然后以相同时间的间隔均匀取出
  • 应用状态更新 : 一旦你的数据包从抖动缓冲器里面出来，你该在状态更新直接应用这些信息进行仿真。
• 对两边都量化(这里的量化指的是<<网络物理模拟五之快照压缩>>说的量化压缩技术) : 如果只有接收端用了量化的数据, 那接收端模拟的结果很可能与发送端不同, 所以要对两边都量化来避免发送端和接收端模拟的差异
• 长时间丢包的平滑处理 : 对于不同的网络断开时间用不同的平滑因子, 来自适应误差
• 增量压缩 :
  • 相对编码 : 在数据包的包头里面发送最近确认的数据包的序列号（这个数据是从可靠的确认系统里面得到的）然后对每个物体编码相对这个基准帧的偏移量
  • 绝对编码

原文

原文出处

原文标题 : State Synchronization (Keeping simulations in sync by sending state)

Introduction

Hi, I’m Glenn Fiedler and welcome to Networked Physics.

In the previous article we discussed techniques for compressing snapshots.

In this article we round out our discussion of networked physics strategies with state synchronization, the third and final strategy in this article series.

State Synchronization

What is state synchronization? The basic idea is that, somewhat like deterministic lockstep, we run the simulation on both sides but, unlike deterministic lockstep, we don’t just send input, we send both input and state.

This gives state synchronization interesting properties. Because we send state, we don’t need perfect determinism to stay in sync, and because the simulation runs on both sides, objects continue moving forward between updates.

This lets us approach state synchronization differently to snapshot interpolation. Instead of sending state updates for every object in each packet, we can now send updates for only a few, and if we’re smart about how we select the objects for each packet, we can save bandwidth by concentrating updates on the most important objects.

So what’s the catch? State synchronization is an approximate and lossy synchronization strategy. In practice, this means you’ll spend a lot of time tracking down sources of extrapolation divergence and pops. But other than that, it’s a quick and easy strategy to get started with.

自我总结

快照压缩技术的要点为 :

• 压缩Orientation数据 : 利用四元数的”最小的三个分量”性质:x^2+y^2+z^2+w^2 = 1 来在传输的时候丢弃一个分量并在网络的另外一端对整个四元数进行重建
• 压缩线性速度和Postion数据 : 把他们限制在某个范围内, 就可以用这个范围的最大值所占用的比特位数来保存这两种数据了, 而不用一个超大的数来保证可以保存他们的最大值了(占用超多bit位)
• 增量压缩

. . .

原文

原文出处

原文标题 : Snapshot Compression (Advanced techniques for optimizing bandwidth)

Introduction

Hi, I’m Glenn Fiedler and welcome to Networked Physics.

In the previous article we sent snapshots of the entire simulation 10 times per-second over the network and interpolated between them to reconstruct a view of the simulation on the other side.

The problem with a low snapshot rate like 10HZ is that interpolation between snapshots adds interpolation delay on top of network latency. At 10 snapshots per-second, the minimum interpolation delay is 100ms, and a more practical minimum considering network jitter is 150ms. If protection against one or two lost packets in a row is desired, this blows out to 250ms or 350ms delay.

This is not an acceptable amount of delay for most games, but when the physics simulation is as unpredictable as ours, the only way to reduce it is to increase the packet send rate. Unfortunately, increasing the send rate also increases bandwidth. So what we’re going to do in this article is work through every possible bandwidth optimization (that I can think of at least) until we get bandwidth under control.

Our target bandwidth is 256 kilobits per-second.

自我总结

快照插值这种游戏同步技术的要点为 :

• 视觉模拟 : 每帧从网络的发送侧捕获所有相关状态的快照，并将其传输到网络的接收侧，在那里我们将试图重建一个视觉上近似合理的模拟
  • 缓冲区 : 内插值之前会缓冲一段合适的时间来处理网络抖动
  • 内插值Interpolation : 处理快照之间的拉扯
    • 线性插值
    • Hermite插值
  • 外插值Extrapolation (文中翻译为”预测”或”推测”) : 不可行, 因为外插值无法精准预测刚体运动以及各种物理
• 降低延迟 : 因为我们发送的快照的频率比较低，这样会带来的一个问题就是对快照进行插值的话会在网络延迟的基础上还要增加插值带来的延迟. 所以我们需要增加发送速率, 为了提高发送速度我们需要压缩快照数据技术的配合, 不然占用太多带宽了
• 减少宽带占用 : 因为所有需要在快照中包含所有实体信息, 所以数据量相当大, 得用各种方法压缩快照数据(网络物理模拟五之快照压缩)

. . .

原文

原文出处

原文标题 : Snapshot Interpolation (Interpolating between snapshots of visual state)

Introduction

Hi, I’m Glenn Fiedler and welcome to Networked Physics.

In the previous article we networked a physics simulation using deterministic lockstep. Now, in this article we’re going to network the same simulation with a completely different technique: snapshot interpolation.

Background

While deterministic lockstep is very efficient in terms of bandwidth, it’s not always possible to make your simulation deterministic. Floating point determinism across platforms is hard.

Also, as the player counts increase, deterministic lockstep becomes problematic: you can’t simulate frame n until you receive input from all players for that frame, so players end up waiting for the most lagged player. Because of this, I recommend deterministic lockstep for 2-4 players at most.

So if your simulation is not deterministic or you want higher player counts then you need a different technique. Snapshot interpolation fits the bill nicely. It is in many ways the polar opposite of deterministic lockstep: instead of running two simulations, one on the left and one on the right, and using perfect determinism and synchronized inputs keep them in sync, snapshot interpolation doesn’t run any simulation on the right side at all!

自我总结

帧同步要点如下 :

• 确定性 : 去除随机数
• 缓冲 : 因为数据包并不是均匀地到达, 所以要做一个缓冲区, 然后再均匀地取出
• 不用TCP : 因为我们的数据对时间非常敏感, 不接受到第n个输入包就无法继续模拟第n帧, 而TCP的确认机制以及重传机制当我们丢包时, 我们只能暂停等待它重发造成卡顿
• 用UDP :
  • 发送冗余数据 : 因为帧同步只发送玩家input数据, 而input包是很小的, 所以发冗余也不会很大
  • 增量包 : 加一个bit来标志跟上一个包的比较结果, 如果这个包跟上个包一致则只发送一个1, 如果不一致则发送0和这个包的完整数据
• 帧同步的缺点 :
  • 等的人太多 : 因为你要收到所有玩家对应帧的输入才能对这一帧进行模拟.在实践中，这意味着每个人必须等待最滞后的那个玩家.人越多等得越久, 所以帧同步不适合mmo.
  • 比较耗性能 : 因为帧同步技术的话, 在客户端中，每个对象都要执行所有的物理之类的运算; 而状态同步可以只同步当前玩家周围对象的状态, 不需要同步所有对象

. . .

原文

原文出处

原文标题 : Deterministic Lockstep (Keeping simulations in sync by sending only inputs)

Introduction

Hi, I’m Glenn Fiedler and welcome to Networked Physics.

In the previous article we explored the physics simulation we’re going to network in this article series. In this article specifically, we’re going to network this physics simulation using deterministic lockstep.

Deterministic lockstep is a method of networking a system from one computer to another by sending only the _inputs_that control that system, rather than the state of that system. In the context of networking a physics simulation, this means we send across a small amount of input, while avoiding sending state like position, orientation, linear velocity and angular velocity per-object.

The benefit is that bandwidth is proportional to the size of the input, not the number of objects in the simulation. Yes, with deterministic lockstep you can network a physics simulation of one million objects with the same bandwidth as just one.

While this sounds great in theory, in practice it’s difficult to implement deterministic lockstep because most physics simulations are not deterministic. Differences in floating point behavior between compilers, OS’s and even instruction sets make it almost impossible to guarantee determinism for floating point calculations.

原文出处

Introduction to Networked Physics

Introduction

Hi, I’m Glenn Fiedler and welcome to the first article in Networked Physics.

In this article series we’re going to network a physics simulation three different ways: deterministic lockstep, snapshot interpolation and state synchronization.

But before we get to this, let’s spend some time exploring the physics simulation we’re going to network in this article series:

Here I’ve setup a simple simulation of a cube in the open source physics engine ODE. The player moves around by applying forces at its center of mass. The physics simulation takes this linear motion and calculates friction as the cube collides with the ground, inducing a rolling and tumbling motion.

This is why I chose a cube instead a sphere. I want this complex, unpredictable motion because rigid bodies in general move in interesting ways according to their shape.