In this case we would need some further reliability infrastructure at the "message" level. That is, we would need to buffer out-of-order messages until dropped messages arrive, and we would need to reject message duplicates in the instance that the original "dropped" packet eventually makes its way across the wire.

Yes, absolutely!

This is why there's typically several classes of delivery guarantee across different logical channels over a physical UDP connection:

- maybe delievered, maybe duplicated, maybe out of order -- implementation is to just deliver as soon as a packet comes in (this is least useful)
- maybe delivered, not duplicated, not out of order -- delivered assuming the incoming packet is later than the previous incoming packet (this is most useful)
- guaranteed delivery, not duplicated, maybe out of order -- each guaranteed message is delivered when the packet shows up, but de-duplicated if there's re-sends (lost acks)
- guaranteed delivery, not duplicated, not out of order -- this is similar to TCP, and requires the most buffering and state management

Only the last reliability type requires buffering actual messages on the receiving end; the others can make delivery decisions based only on sequence numbers (and, for the case of reliable, per-channel sequence numbers.)
Also, with reliable channels, you typically keep the reliability information on a per-message-channel basis, rather than a per-packet-stream basis.

Thanks, this information has been very helpful! I ended up going with hplus0603's method and just dropping packets which come out of order, and resending the moment I detect the missing ACK - greatly simplifies things.

On the topic of reliability/ordering of messages, I had a thought today. This would probably have way too much overhead/be impractical, but have any games implemented a dependency graph for message ordering, rather than simply an ordered stream? An approach might work somewhat as follows:
- Each message would have an ID (probably 2 bytes, maybe with some upper bits being used as flags)
- Each message would be sent with a list of IDs it depends on (this would be the overhead-y part!)
- When messages are received, their dependency graph is evaluated, and they are only executed after all dependencies have been executed
- When the sender determines that all messages that a message is dependent on have been processed, the dependencies are removed to reduce dependency list length. To do this, examine incoming ACKs and figure out which messages must have been executed.

Example of why the last point is important: suppose you spawn an enemy and then much later it gets killed. The "enemy killed" message should be dependent on the "enemy spawned" message, but in order for that to work the receiver needs to keep track of the "enemy spawned" message for a long time! But if you can confirm using ACKs that the "enemy spawned" message was already executed, you can just forget about it. And if you hang onto dependencies for a long time, you'll have issues when the 2-byte message IDs wrap around.

This is just the more general extension of having multiple message channels each with independent ordering. Of course, the cost is probably extremely high. Anyone done something like this before?

That's an interesting idea, and I have not seen it done before. I wonder how different in practice it would be compared to a per-channel ordering dependency.

Implement it and ship a large game and then let us know how it turns out :-)