[2019] Packet Reordering - Technical Post

We recently tracked down, with the help of an internet service provider (ISP) and one of our hosting providers, a networking issue that could be contributing to some of the lag and packet loss that players with certain ISPs are experiencing. This post is to provide some technical details about the problem and how we’re planning to fix it.

 

The issue relates to how UDP network packets can be delivered to their destination in a different order than they were sent. This is a protocol that all programs using UDP for networking have to deal with, and Fortnite, by way of Unreal Engine 4, does handle it, but not as efficiently as it could.

 

To help understand the issue, here’s a simplified version of the high-level sequence of events that occur in a single frame in-game.

 

1. Try to read a packet from the network, if one is available, go to #2. Otherwise, skip to #4.

2. If the packet read was sent before a packet we’ve already processed, discard it. Otherwise, process it normally.

3. Go back to #1.

4. Advance the game simulation and wait for the next frame.

 

We can do the test in #2 because the sender writes a sequence number into each packet they send, and the receiver records this number for the last packet it successfully processed. Discarding packets with lower sequence numbers is important for keeping the game simulation consistent, as well as for security reasons - we can’t just process every single packet regardless of when it’s received.

 

Now, consider a case where the packets the game receives are out-of-order. For example, if the received sequence is 1, 3, 2, 4, following the steps above, we would process packet 1, then 3, discard 2, then process 4.

Discarding packets here is generally OK, because we have mechanisms to retransmit packets if needed - but this retransmission takes time, so in effect it causes increased latency for whatever actions would have been triggered by processing that packet.

 

However, the game did receive every packet the sender sent, and it technically could have processed packet #2, so dropping it might seem wasteful - and it is!

 

If the out-of-order packets are all received on the same game frame, we should be able to sort them into the correct order before fully processing them. Consider this revised processing loop:

 

1. Read all packets available from the network. If any are available, go to #2. Otherwise, skip to #4.

2. Sort all packets received by their sequence numbers.

3. Process all the packets in their now-sorted order.

4. Advance the game simulation and wait for the next frame.

 

Now, we can process all the packets received in the example above without discarding any and paying for the re-transmission time of whatever data packet #2 contained!

 

We hope to have the revised processing method implemented in the v8.10 update but will update you on the timing for the fix closer to the release of that patch.

 

-Ryan Gerleve: Lead Networking Programmer

External link →