Sign in to follow this  

Implementation of reliable UDP

This topic is 2546 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I am trying to implement a reliable layer over UDP, to use it in a multiplayer game via Internet...

I have come up with this 4 types of packets that can be sent:

(in all of them, duplicated packets are discarded)

Unreliable: Don't care if they arrive or not and in which order

Unreliable ordered: Don't care if they arrive or not, but do care about order and duplicates (ie. player movement)

Reliable: they need to arrive, but doesn't matter in which order (ie. weapons, explosions)

Reliable ordered: like tcp, should arrive and in order (ie. chat, rpc calls)

My idea is to put send them all via the same port (using UDP as transport protocol)...

What is the best way to do so? I have thought about integrating ACK packets (for both the reliable and reliable ordered) into all of the packets, but I am not sure if the unreliable packets will slow down the others...

Also, should I implement some sort of "flow control"? What happens if I just assume that the bandwidth is available and limit uploads to for example 64Kbps?

How should I "mux" everything? Should I use priority for each packet or something like that?

Thanks,
Gzaloprgm

Share this post


Link to post
Share on other sites
Messages are smaller than UDP packets. Each UDP packet contain many messages, possibly with different delivery classes. Each UDP packet contains a sequence number, so you can tell whether something has arrived or not. As a simplifying implementation, you can discard UDP packets that arrive out of order -- this means that 1) and 2) collapse into a single category. You just include the message in the next UDP packet, if it fits, and send it; end story.

Now, you have two queues (reliable, and reliable-ordered) and mark which messages are sent in which UDP packet. Each UDP response packet contains information about the last N received and dropped packets (typically as a "last received sequence number, and a bitmask of receives before then"). Based on this information, you can calculate which packets got dropped, once you get another packet through and acked. This lets you resend any reliable message that was in a presumed-dropped packet.

Finally, delivery of reliable packets happen right away on receipt, whereas delivery of reliable-in-order has to be predicated on a separate sequence number maintained per message. Thus, the send queue for reliable messages doesn't need sequence numbers (you just re-send when you detect a dropped packet that the thing was in, and drop from the queue when you detect a received packet). The reliable-in-order queue does need sequence numbers, and can deliver any packet at S+1 when it knows it has delievered S; repeat.

Share this post


Link to post
Share on other sites
Thanks for your fast answer...

I am not using a library mainly because I want to learn and I think it will be easier to debug the data if I know exactly how messages are sent, but I might use one of them in the future...

So basically the idea is that I should join every message into a 1KB or so packet (up to the MTU)?

What about flow control? Should I discard unreliable messages if I have already sent too many bytes per 100ms or something like that?

Thanks,
Gzaloprgm

Share this post


Link to post
Share on other sites
You can generally put 1400 bytes into each UDP packet without problems. Often, at least on good connections, you can go significantly higher than that (or NFS wouldn't work :-)

Sending a UDP packet every 100 milliseconds, and putting whatever you can fit into that, is probably a fine way to do it. Discard all unreliable messages that don't fit.

You can also throttle the size of the packet (send less per packet) and/or the packet rate, based on loss. Maybe reduce packet size 200 bytes per two packets lost you get within 20 packets, and add back 50 bytes per 10 non-lost packets in a row, or something like that. This is less robust than TCP (each lost packet halves the window size; each ack extends the window linearly) and may cause oscillation if multiple clients compete for the same bandwidth, but may be sufficient for a game where most data is real-time, and which can somewhat tune the quality level based on available bandwidth.

In general, a game should only send necessary data. If you can't send the necessary data in the necessary time interval, you're basically just screwed, and probably ought to consider dropping the connection, rather than trying to throttle back -- because all the queued traffic is supposed to be necessary, anyway!

I would consider not changing the size of the payload, or packet rate, at all; instead, I would drop the connection if I saw, say, 3 or more dropped packets in a 2 second interval.

Share this post


Link to post
Share on other sites
When I was writing a UDP transport library (called XPURL http://www.replicanet.com/assets/docs/Main/html/XPURL.html ) I found it advantageous to include an outgoing per connection bandwidth as well as a global outgoing bandwidth. Then the data packet sends for all types of data would get merged into their relevant outgoing buffers up to the maximum packet size, or until the buffer age reached a configured value. Then the data would get sent.

If the connection send limit or global limit was reached then I would start to drop sending the least reliable packet types first.
I also found it useful to allow the ACK/resend times to be configured, for some projects and platforms this was needed because some platforms like to have a short broken connection timeout, some platforms like to have more robust connections and therefore longer timeout periods.

Lastly, I found it extremely useful to route all the muxed/merged packet sending through a low level network emulation layer. If this was enabled it would let me test various packet loss, jitter and latency. This meant I could simulate a connection from the UK to the US or Asia without actually needing endpoints at those locations. http://www.replicanet.com/assets/docs/Main/html/classRNReplicaNet_1_1NetworkEmulation.html

Being able to simulate different network conditions will help you find bugs in your connection and game code.

Share this post


Link to post
Share on other sites
A fifth delivery method that is sometimes useful is "Reliable sequenced"; ie. resend lost packets, but drop late arrivals. Potentially wasteful, but useful for values which are updated seldom and you don't want to leave the user with an old value for too long ("health" for example).

Regarding flow control, I experimented alot with a per-packet selective repeat sliding window but never got it to work well across all reliability contracts. Currently I use a window per channel; where each channel implements a specific reliability contract.

Share this post


Link to post
Share on other sites
Fenghus, is what you mean "eventually consistent" reliability?
Specifically, you will at some point be put in sync with the other end, but you may have missed transition states in between.
I've found that such a guarantee is much more useful for the particular data you're dealing with, rather than the low-level packets. Although, if you map data items to channels in a 1:1 manner, then it might be useful to have that same layer of guarantee in the channel.

Share this post


Link to post
Share on other sites
Yes, that's precisely what I meant. For Lidgren I've implemented the guarantee per-message (not packet). I agree it would really be best to apply it "per-data" since mixing multiple kinds of datas in the same channel will break the eventually consistent guarantee. A compromise is having multiple channels for each delivery method (32 in my case) to allow for a number of kinds of data to use the guarantee using a 1:1 mapping like you wrote :-)

[Edited by - fenghus on December 23, 2010 2:59:23 PM]

Share this post


Link to post
Share on other sites

This topic is 2546 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this