5
\$\begingroup\$

Like most people on this exchange concerned with UDP client server connections, I've gone through the Gaffer on Games article about implementing reliability. I understand how the ordering and acks and what not works (I think).

My issue is, some packets need to be re-sent until they are received, such as a packet stating that an entity has been created in the world. Others, such as updating the location of an entity don't need to be re-sent if a newer packet containing location data has already been sent.

What if, say, an entity is created and destroyed within a second. Say the create packet is lost but the destroy packet is received. The client has been told to destroy a non existent entity. If it just ignores this, when the create packet is re-sent, the entity will never be destroyed causing inconsistency.

All of this is per-client, so the actual game code should know nothing about it, only the networking code.

So how should this be handled? Do I flag certain packet types as resend. Do I send send a field in all dependent packets saying they depend on packet number x? Neither seem very elegant.

\$\endgroup\$
1
\$\begingroup\$

If the client receives a destroy packet without receiving the create packet, then it should know that it is out of sequence. The client won't have a record of the entity. Queue it until the create packet is received.

As you said, some packet types are sequence dependent and others are not. The client should know the protocol.

Another option is to send the create and destroy as a single event in the same packet if the original create packet hasn't been ack'd yet. This would depend on the protocol you define. You might have an extra bit in your create packet that indicates if the entity has also been destroyed, if there is no other information associated with the destroy event. You might also allow sending multiple events per packet for certain event types like create/destroy or even for all event types though if the data is variable length, then you will need a way to delimit the events in your packets.

If the server sends a new (as in different sequence ID) create/destroy packet but meanwhile the client does receive and ack the original create packet, it should know from the entity ID that it's a duplicate, regardless of the sequence ID being different. So it would just ignore the new create event and apply the destroy only.

\$\endgroup\$
  • \$\begingroup\$ So in the event that the create packet is not akced but the destroy is, the server re-sends the create packet with a new sequence ID. The client then receives this, and knowing that the destroy packet has the same entity ID, knows that the create must have come before the destroy (despite the new sequence id). This makes sense to me, is it correct? \$\endgroup\$ – Zwander Sep 3 '15 at 3:06
  • \$\begingroup\$ You should really really avoid implementing a reliability mechanism within UDP flows. The reason being that TCP will almost certainly provide a better transport layer if you do indeed require reliability and/or ordering within your messages. It turns out reliability is super complicated! Implementing your own is not only a daunting task, but a useless endeavor. TCP has been heavily researched and improved over the years it's unlikely a handmade reliability mechanism in UDP will serve you as well. \$\endgroup\$ – Alex Sherman Sep 3 '15 at 5:15
  • \$\begingroup\$ @Zwander The sequence ID should identify the order of the unique events (messages), not the packets. It doesn't matter how many times you resend the same create event, it's still identical and occurred at a specific point in the timeline. An ack for any one of the duplicate events should be sufficient to satisfy the server for all of them, otherwise the server needs to track all the duplicates too. What if the server sends 100 duplicate packets and the client acks the first one, but was just slow? The server needs to know which event is being ack'ed, not which packet. \$\endgroup\$ – Fuzzy Logic Sep 3 '15 at 7:24
  • \$\begingroup\$ @FuzzyLogic Quote from the article: "So in our reliability system, we never resend a packet with a given sequence number. We sequence n exactly once, then we send n+1, n+2 and so on. We never stop and resend packet n if it was lost, we leave it up to the application to compose a new packet containing the data that was lost, if necessary, and this packet gets sent with a new sequence number." Basically, never resend the same sequence #. To be honest, I don't see why. I agree that sending the same sequence number makes a lot more sense. \$\endgroup\$ – Zwander Sep 3 '15 at 8:24
  • \$\begingroup\$ @Zwander If you always use a new sequence ID for every packet then you also need to send a unique message ID as well so you can keep track of the order of events (IE 4+4 bytes). You can still track packet sequence if you only increment per event by including a retry counter which can be a smaller int since it resets for every unique message. 1 or 2 bytes to count duplicates is enough, instead of 4 bytes for a completely separate message ID (IE 4+1 byte). The packet ID then becomes two-part but does not track the order of the actual packets in the stream, which you don't care about anyway. \$\endgroup\$ – Fuzzy Logic Sep 3 '15 at 17:37
0
\$\begingroup\$

You should consider using a mix of TCP and UDP flows and add a layer of abstraction over a raw UDP packet like a "message." Then, similar to the Steam API if you're familiar with it, you can expose functions like sendReliable(message, destinationClient) and sendUnreliable(message, destinationClient). Reliable messages can be passed through the TCP stream, and yes you should in fact use TCP streams if the data being sent needs to be reliable or maintain order. Turns out implementing a reliable message protocol in UDP will basically be implementing a worse version of TCP.

You then can decide which data is sent in which way. You're right to send stuff like position updates over UDP, only the latest update is useful and if one is lost there's no reason to resend it. Anything that requires order and/or reliability definitely should probably be sent over TCP.

\$\endgroup\$
  • \$\begingroup\$ I can see the advantages of doing this. Definitely for things such as chat that are not latency dependent. From my reading however, the "worse version of TCP" also happens to be a "faster version of TCP". It maintains a weak ordering system (all that is necessary) and prevents lockups. \$\endgroup\$ – Zwander Sep 4 '15 at 0:49
0
\$\begingroup\$

I don't recommend using TCP for reliable transport in games - the latency is too high, and the overhead of the transport will chew up your bandwidth. Instead you need to implement a reliable messaging system on top of UDP that uses ACKs to handle the sending and resending of messages. Consider the following situation - two machines are sending state information back and forth.

Machine A on Seq#100 creates object. In the packet it sends out, labelled #100, it includes the message.

Machine B receives the packet, and respond with the ACK of seq# 100. It creates the object.

Machine A receives the ACK of 100.

Later, Machine A destroys the object on seq# 200 and the same thing happens. A packet goes out with seq#200, Machine B acks it, and Machine A receives the ack.

This is great but how does it help us? Well if Machine B never receives seq#100, it can't ACK it, so machine A continues to send all the messages from previous sequence numbers until the ack is received - so seq# 101 has the create in it, seq#102 has the create in it, etc, until the ACK is received. In fact, because of latency, seq#101 is likely created and sent before the ack for 100 could ever be received, which helps decrease latency.

Should the ACK from Machine B to machine A be lost, then Machine A keeps sending the message until an ACK is received - it can't assume it has been received so it has no other choice but to do so.

Now if there is such dramatic packet loss that nothing is ack'ed since #100 when the object is destroyed, then the outgoing packet will contain both the create AND the destroy data, which is perfect. The messages should be put into the packet in sequence number order, so they maintain their timeline.

The key here is to put your messages into a queue, sorted by time, and to send the messages out until they are acknowledged. By having them in a queue, you add new messages to the back, and prune old messages from the front. Adding them is easy because they are always sorted in the queue. Further, the ACK sent from machine B to machine A should be bundled with whatever data that machine B needs to send back - there is no point to make a distinct packet - that's a waste of bandwidth.

Note that this is only for reliable messages. Unreliable messages work into this system just fine but are only sent on the seq# they are generated- they are not held onto and resent for multiple frames.

What I like about this system is that your create/destroy messages are kept in sync with the packet data for position, health, etc. which would be included in the same packet.

In a peer to peer game each peer would send the same data, so the packet layout might look like this:

Sequence # Acked Sequence # Number of messages in the packet each message additional payload data such as delta compressed snapshot data

Packet size grows as latency increases, but there are some ways to help mitigate that, such as slowing down the frequency you send packets at. I think Gaffer talks about that strategy.

I hope some of this makes sense.

\$\endgroup\$
  • 2
    \$\begingroup\$ Would like some feedback on the down votes please. \$\endgroup\$ – Steven Sep 3 '15 at 15:23
  • \$\begingroup\$ My guess is the school of "don't reinvent the wheel" down voted it. Problem is that for games TCP is more of a flat tire: high latency, no throttling, no control over priority. Naively implemented games like some of the Voxel-world types seem to cause a lot of lag when the server is flooding the network connection with massive amount of chunk data in an uncontrolled fashion over TCP. Implementing your own reliable/unreliable protocol over UDP lets you prioritize and smooth out these things with a minimal of effort once you get comfortable with ACK/Sequence queues. \$\endgroup\$ – Stephane Hockenhull Sep 5 '15 at 17:49
  • \$\begingroup\$ Also would like to add that by using UDP (or similar lower-level packets) you can time your packets to minimize loss in controlled and semi-controlled environments. By sending 1 packet every N ms with proper timing will minimize loss on a LAN (both wired and wireless) by reducing collisions and smarter network appliances (routers/switches) can prioritize infrequent/periodic UDP traffic versus TCP traffic. \$\endgroup\$ – Stephane Hockenhull Sep 5 '15 at 17:58
  • \$\begingroup\$ TCP is not "higher latency" than UDP, when you disable Nagle queueing. You certainly can have your cake and eat it to though, implement your message system on top of TCP. You can have your throttling, your priority control AND reliability. The bottom line is, if you require that messages arrive reliably and in the order you send them, you in general cannot do better than TCP. \$\endgroup\$ – Alex Sherman Oct 2 '15 at 5:30
  • \$\begingroup\$ To provide feedback to Steven, which I apologize for not doing sooner, here goes. That solution, which Gaffer does mention and quickly throws away because of its huge limitations, does not work for actual scale games. Let's do some quick math, assume a network path with bandwidth = 10Mb/s, RTT = 200ms. Your game produces data at a conservative 800kb/s, let's a 1000 byte packet every 10 ms. You won't receive an ack to stop sending packets until T = 200ms. For simplicity, assuming you don't process acks until you send out your current load of packets, you're now sending data at a crazy 16mb/s. \$\endgroup\$ – Alex Sherman Oct 2 '15 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.