介绍

都是自描述性的且项目无关的, 可以直接放心使用.

. . .

介绍

其实不用继承 UObject 也可以生成一个 actor,

关键的点就是拿到 UWorld ,
所以只要从一个拥有 UWorld 的虚幻相关实例中传递它的 UWorld 给一个原生 C++ 类也可以.

示例代码

. . .

本篇自我总结

这篇文章网上找不到翻译, 我也没时间详细翻译, 大概总结一下吧.
本篇主要讲了把本系列之前五篇文章的技术应用到实战中处理客户端与服务器的的连接.
请看总结, 不明之处再看文中具体讲解.

简单的连接协议

First up we have the client state machine.
The client is in one of three states:

• Disconnected
• Connecting
• Connected

The goal is to create an abstraction on top of a UDP socket where our server presents a number of virtual slots for clients to connect to.

When a client requests a connection, it gets assigned to one of these slots.

If a client requests connection, but no slots are available, the server is full and the connection request is denied.

On the server, we have the following data structure:

const int MaxClients = 64;

class Server
{
    int m_maxClients;
    int m_numConnectedClients;
    bool m_clientConnected[MaxClients];
    Address m_clientAddress[MaxClients];
};

这个简单协议存在的问题

• 易被攻击者利用我们的服务器当做DDos放大攻击的工具
• 攻击者可以很轻松的占满我们的client slots
• Traffic between the client and server can be read and modified in transit by a third party.
• 一旦被攻击者知道了客户端或者服务器的地址, 他就可以伪装服务器或客户端来欺骗对方获取利益
• 没有一个明确的断开连接的方式, 只能等time out

这些问题需要用授权系统和加密系统来解决.

如何改进这个连接协议

• we no longer accept client connections immediately on connection request, instead we send back a challenge packet, and only complete connection when a client replies with information that can only be obtained by receiving the challenge packet.

• 为了防止攻击者利用我们的服务器当做DDos放大攻击的工具, 我们让客户端发的包比服务器发的包要大些.

• We’ll add some unique random identifiers, or ‘salts’, to make each client connection unique from previous ones coming from the same IP address and port.

• 一旦彼此连接上之后, 就用 client salt 和 server salt 的异或值来标识彼此.

• 以上的防御措施让我们的服务器做到了 no longer able to be used as port of DDoS amplification attacks, and with a trivial xor based authentication, 但对于一个经验丰富的会抓包分析的攻击者来说, 还存在以下问题 :

  • This attacker can read and modify packets in flight.
  • This breaks the trivial identification based around salt values…
  • giving an attacker the power to disconnect any client at will.

To solve this, we need to get serious with cryptography to encrypt and sign packets so they can’t be read or modified by a third party.

原文

原文出处

原文标题 : Client Server Connection (How to create a client/server connection over UDP)

Introduction

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

So far in this article series we’ve discussed how games read and write packets, how to unify packet read and write into a single function, how to fragment and re-assemble packets, and how to send large blocks of data over UDP.

Now in this article we’re going to bring everything together and build a client/server connection on top of UDP.

Background

Developers from a web background often wonder why games go to such effort to build a client/server connection on top of UDP, when for many applications, TCP is good enough.

These days even web servers are transitioning to UDP via Google’s QUIC. If you still think TCP is good enough for time critical data in 2016, I encourage you to put that in your pipe and smoke it :)

The reason is that games send time critical data.

Why don’t games use TCP for time critical data? The answer is that TCP delivers data reliably and in-order, and to do this on top of IP (which is unreliable, unordered) it holds more recent packets hostage in a queue while older packets are resent over the network.

This is known as head of line blocking and it’s a huuuuuge problem for games. To understand why, consider a game server broadcasting the state of the world to clients 10 times per-second. Each client advances time forward and wants to display the most recent state it receives from the server.

But if the packet containing state for time t = 10.0 is lost, under TCP we must wait for it to be resent before we can access t = 10.1 and 10.2, even though those packets have already arrived and contain the state the client wants to display.

Worse still, by the time the resent packet arrives, it’s far too late for the client to actually do anything useful with it. The client has already advanced past 10.0 and wants to display something around 10.3 or 10.4!

So why resend dropped packets at all? BINGO! What we’d really like is an option to tell TCP: “Hey, I don’t care about old packets being resent, by they time they arrive I can’t use them anyway, so just let me skip over them and access the most recent data”.

Unfortunately, TCP simply does not give us this option :(

All data must be delivered reliably and in-order.

This creates terrible problems for time critical data where packet loss and latency exist. Situations like, you know, The Internet, where people play FPS games.

Large hitches corresponding to multiples of round trip time are added to the stream of data as TCP waits for dropped packets to be resent, which means additional buffering to smooth out these hitches, or long pauses where the game freezes and is non-responsive.

Neither option is acceptable for first person shooters, which is why virtually all first person shooters are networked using UDP. UDP doesn’t provide any reliability or ordering, so protocols built on top it can access the most recent data without waiting for lost packets to be resent, implementing whatever reliability they need in radically different ways to TCP.

But, using UDP comes at a cost:

UDP doesn’t provide any concept of connection.

We have to build that ourselves. This is a lot of work! So strap in, get ready, because we’re going to build it all up from scratch using the same basic techniques first person shooters use when creating their protocols over UDP. You can use this client/server protocol for games or non-gaming applications and, provided the data you send is time critical, I promise you, it’s well worth the effort.

Client/Server Abstraction

The goal is to create an abstraction on top of a UDP socket where our server presents a number of virtual slots for clients to connect to:

When a client requests a connection, it gets assigned to one of these slots:

If a client requests connection, but no slots are available, the server is full and the connection request is denied:

Once a client is connected, packets are exchanged in both directions. These packets form the basis for the custom protocol between the client and server which is game specific.

In a first person shooter, packets are sent continuously in both directions. Clients send input to the server as quickly as possible, often 30 or 60 times per-second, and the server broadcasts the state of the world to clients 10, 20 or even 60 times per-second.

Because of this steady flow of packets in both directions there is no need for keep-alive packets. If at any point packets stop being received from the other side, the connection simply times out. No packets for 5 seconds is a good timeout value in my opinion, but you can be more aggressive if you want.

When a client slot times out on the server, it becomes available for other clients to connect. When the client times out, it transitions to an error state.

Simple Connection Protocol

Let’s get started with the implementation of a simple protocol. It’s a bit basic and more than a bit naive, but it’s a good starting point and we’ll build on it during the rest of this article, and the next few articles in this series.

First up we have the client state machine.

The client is in one of three states:

• Disconnected


• Connecting


• Connected

Initially the client starts in disconnected.

When a client connects to a server, it transitions to the connecting state and sends connection request packets to the server:

The CRC32 and implicit protocol id in the packet header allow the server to trivially reject UDP packets not belonging to this protocol or from a different version of it.

Since connection request packets are sent over UDP, they may be lost, received out of order or in duplicate.

Because of this we do two things: 1) we keep sending packets for the client state until we get a response from the server or the client times out, and 2) on both client and server we ignore any packets that don’t correspond to what we are expecting, since a lot of redundant packets are flying over the network.

On the server, we have the following data structure:

const int MaxClients = 64;

class Server
{
    int m_maxClients;
    int m_numConnectedClients;
    bool m_clientConnected[MaxClients];
    Address m_clientAddress[MaxClients];
};

Which lets the server lookup a free slot for a client to join (if any are free):

int Server::FindFreeClientIndex() const
{
    for ( int i = 0; i < m_maxClients; ++i )
    {
        if ( !m_clientConnected[i] )
            return i;
    }
    return -1;
}

Find the client index corresponding to an IP address and port:

int Server::FindExistingClientIndex( const Address & address ) const
{
    for ( int i = 0; i < m_maxClients; ++i )
    {
        if ( m_clientConnected[i] && m_clientAddress[i] == address )
            return i;
    }
    return -1;
}

Check if a client is connected to a given slot:

bool Server::IsClientConnected( int clientIndex ) const
{
    return m_clientConnected[clientIndex];
}

… and retrieve a client’s IP address and port by client index:

const Address & Server::GetClientAddress( int clientIndex ) const
{
    return m_clientAddress[clientIndex];
}

Using these queries we implement the following logic when the server processes a connection request packet:

• If the server is full, reply with connection denied.




• If the connection request is from a new client and we have a slot free, assign the client to a free slot and respond with connection accepted.




• If the sender corresponds to the address of a client that is already connected, also reply with connection accepted. This is necessary because the first response packet may not have gotten through due to packet loss. If we don’t resend this response, the client gets stuck in the connecting state until it times out.

The connection accepted packet tells the client which client index it was assigned, which the client needs to know which player it is in the game:

Once the server sends a connection accepted packet, from its point of view it considers that client connected. As the server ticks forward, it watches connected client slots, and if no packets have been received from a client for 5 seconds, the slot times out and is reset, ready for another client to connect.

Back to the client. While the client is in the connecting state the client listens for connection denied and connection accepted packets from the server. Any other packets are ignored.

If the client receives connection accepted, it transitions to connected. If it receives connection denied, or after 5 seconds hasn’t received any response from the server, it transitions to disconnected.

Once the client hits connected it starts sending connection payload packets to the server. If no packets are received from the server in 5 seconds, the client times out and transitions to disconnected.

Naive Protocol is Naive

While this protocol is easy to implement, we can’t use a protocol like this in production. It’s way too naive. It simply has too many weaknesses to be taken seriously:

• Spoofed packet source addresses can be used to redirect connection accepted responses to a target (victim) address. If the connection accepted packet is larger than the connection request packet, attackers can use this protocol as part of a DDoS amplification attack.




• Spoofed packet source addresses can be used to trivially fill all client slots on a server by sending connection request packets from n different IP addresses, where n is the number of clients allowed per-server. This is a real problem for dedicated servers. Obviously you want to make sure that only real clients are filling slots on servers you are paying for.




• An attacker can trivially fill all slots on a server by varying the client UDP port number on each client connection. This is because clients are considered unique on an address + port basis. This isn’t easy to fix because due to NAT (network address translation), different players behind the same router collapse to the same IP address with only the port being different, so we can’t just consider clients to be unique at the IP address level sans port.




• Traffic between the client and server can be read and modified in transit by a third party. While the CRC32 protects against packet corruption, an attacker would simply recalculate the CRC32 to match the modified packet.




• If an attacker knows the client and server IP addresses and ports, they can impersonate the client or server. This gives an attacker the power to completely a hijack a client’s connection and perform actions on their behalf.




• Once a client is connected to a server there is no way for them to disconnect cleanly, they can only time out. This creates a delay before the server realizes a client has disconnected, or before a client realizes the server has shut down. It would be nice if both the client and server could indicate a clean disconnect, so the other side doesn’t need to wait for timeout in the common case.




• Clean disconnection is usually implemented with a disconnect packet, however because an attacker can impersonate the client and server with spoofed packets, doing so would give the attacker the ability to disconnect a client from the server whenever they like, provided they know the client and server IP addresses and the structure of the disconnect packet.




• If a client disconnects dirty and attempts to reconnect before their slot times out on the server, the server still thinks that client is connected and replies with connection accepted to handle packet loss. The client processes this response and thinks it’s connected to the server, but it’s actually in an undefined state.

While some of these problems require authentication and encryption before they can be fully solved, we can make some small steps forward to improve the protocol before we get to that. These changes are instructive.

Improving The Connection Protocol

The first thing we want to do is only allow clients to connect if they can prove they are actually at the IP address and port they say they are.

To do this, we no longer accept client connections immediately on connection request, instead we send back a challenge packet, and only complete connection when a client replies with information that can only be obtained by receiving the challenge packet.

The sequence of operations in a typical connect now looks like this:

To implement this we need an additional data structure on the server. Somewhere to store the challenge data for pending connections, so when a challenge response comes in from a client we can check against the corresponding entry in the data structure and make sure it’s a valid response to the challenge sent to that address.

While the pending connect data structure can be made larger than the maximum number of connected clients, it’s still ultimately finite and is therefore subject to attack. We’ll cover some defenses against this in the next article. But for the moment, be happy at least that attackers can’t progress to the connected state with spoofed packet source addresses.

Next, to guard against our protocol being used in a DDoS amplification attack, we’ll inflate client to server packets so they’re large relative to the response packet sent from the server. This means we add padding to both connection request and challenge response packets and enforce this padding on the server, ignoring any packets without it. Now our protocol effectively has DDoS minification for requests -> responses, making it highly unattractive for anyone thinking of launching this kind of attack.

Finally, we’ll do one last small thing to improve the robustness and security of the protocol. It’s not perfect, we need authentication and encryption for that, but it at least it ups the ante, requiring attackers to actually sniff traffic in order to impersonate the client or server. We’ll add some unique random identifiers, or ‘salts’, to make each client connection unique from previous ones coming from the same IP address and port.

The connection request packet now looks like this:

The client salt in the packet is a random 64 bit integer rolled each time the client starts a new connect. Connection requests are now uniquely identified by the IP address and port combined with this client salt value. This distinguishes packets from the current connection from any packets belonging to a previous connection, which makes connection and reconnection to the server much more robust.

Now when a connection request arrives and a pending connection entry can’t be found in the data structure (according to IP, port and client salt) the server rolls a server salt and stores it with the rest of the data for the pending connection before sending a challange packet back to the client. If a pending connection is found, the salt value stored in the data structure is used for the challenge. This way there is always a consistent pair of client and server salt values corresponding to each client session.

The client state machine has been expanded so connecting is replaced with two new states: sending connection request and sending challenge response, but it’s the same idea as before. Client states repeatedly send the packet corresponding to that state to the server while listening for the response that moves it forward to the next state, or back to an error state. If no response is received, the client times out and transitions to disconnected.

The challenge response sent from the client to the server looks like this:

The utility of this being that once the client and server have established connection, we prefix all payload packets with the xor of the client and server salt values and discard any packets with the incorrect salt values. This neatly filters out packets from previous sessions and requires an attacker to sniff packets in order to impersonate a client or server.

Now that we have at least a basic level of security, it’s not much, but at least it’s something, we can implement a disconnect packet:

And when the client or server want to disconnect clean, they simply fire 10 of these over the network to the other side, in the hope that some of them get through, and the other side disconnects cleanly instead of waiting for timeout.

Conclusion

We now have a much more robust protocol. It’s secure against spoofed IP packet headers. It’s no longer able to be used as port of DDoS amplification attacks, and with a trivial xor based authentication, we are protected against casual attackers while client reconnects are much more robust.

But it’s still vulnerable to a sophisticated actors who can sniff packets:

• This attacker can read and modify packets in flight.




• This breaks the trivial identification based around salt values…




• … giving an attacker the power to disconnect any client at will.

To solve this, we need to get serious with cryptography to encrypt and sign packets so they can’t be read or modified by a third party.

main

看起来似乎所有的组件都有一个这样的宏(KBENGINE_MAIN)来包裹main函数

intKBENGINE_MAIN(intargc, char* argv[])
{
	ENGINE_COMPONENT_INFO&info = g_kbeSrvConfig.getXXX();
	returnkbeMainT<XXX>(argc, argv, YYY, info.externalPorts_min, 
		info.externalPorts_max, info.externalInterface, 0, info.internalInterface);
}

. . .

本篇自我总结

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

为什么需要做这个可靠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.

译文

译文出处