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

Is there any reason you're not using an existing library which already handles this?

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.

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

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.

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.

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.