Yet another interesting problem

I suppose what I'd do is build an additional queue that says, for example:
"packet 3 contained messages 2 through 3"
"packet 4 contained messages 2 through 4"
"packet 5 contained messages 2 through 4" (c: 21, get an ack for 4, delete the part of this queue that has the high message that packet 4 contained, which is "4"... deleting packet queue 3 through 5)
"packet 6 contained messages 5 through 6" (c: 20, acking 3... dropping this)
"packet 7 contained messages 5(changed to 7) through 7" (c: 23, get an ack for 6... 5 got killed. Packet queue containing "6" removed... We now have to update queue positions 7 and 8, setting their "low" value to "7", because we know the client got 5 and 6...)
"packet 8 contained messages 5 (changed to 7) through 8"

Does this solution seem better? I quickly typed it up, I'm not sure if it's badly flawed.

Don't allow queuing messages that you don't have space for in the queue.

In your example, if the head end currently has copies of messages 2 through 5, how could message 6 even have been sent to the other end? Instead, you should return "can't send" to the place trying to enqueue more reliable data than there's space for; this is akin to non-blocking TCP sockets.

If "can't send", then I'd think important data, like "I found Blue Team's weapons stash" might not get through, because perhaps a buildup in other messages...

From the looks of the doc about Quake 3's networking, a packet always containing what changed since the last client ack (in this case, important messages about stuff), would have to hold absolutely everything.

[Edited by - matt_j on April 9, 2005 9:48:10 PM]

If you really need to queue all of that data, then you need to make the queue big enough. There's no way around that. You can't do what you can't do.

Now, if you're on a PC, it just doesn't matter -- you have 1000 times more memory than bandwidth. Queue everything. Keep an eye on the queue size -- if it starts becoming big, it means that the other end just isn't keeping up, and you're choking it. Send less data.

The queue size doesn't really concern me, it's the MTU. I'm not putting more than 1400 bytes in a packet, which means in a nasty scenario, not everything in the queue will be able to fit.

What is the rule that says that all of the queued data has to fit in a single MTU? And you don't even know what the MTU will be -- modems still exist, and often have MTUs around 576 bytes or so.

The whole point of a queue is that, well, stuff sits there and waits, until it can be sent. If you have a reliable, in-order queue, then you will have to take things off of the queue, and feed into your packet, until the packet is full. Mark the things as pending, and record what packet ID they were sent in. When you get an ack for a packet, remove the things from the queue. Because you have to worry about loss, you have to be able to have more than a single packet outstanding anyway. Because you have to worry about re-ordering and duplication, you have to re-order and possibly queue the data on the receiving end. That's the nature of a reliable, in-order system over an unreliable network.

I wonder why I didn't think of this...
eg, command 312 was sent in packet 12

When we get a ack for packet 12, remove any command with this packet id.

Thank you, hplus0603. Perhaps one day I will be a guru like you, and I can help others. (Don't laugh, please...)

EDIT: Should there be some wait time on each command before it is sent agaon, before it is sent again, so we don't wait too long for an ack? I'd give it about 1000 ms, perhaps?

The timeout you use determines how quickly you recover from a dropped packet. Meanwhile, if the other end has some temporary problem ("loading, please wait") and can't ack packets, you don't want to flood the network with packets.

I would measure the RTT, and wait 1.5x RTT before re-sending, then back off to 3x, 4.5x, ... For comparision: Ethernet will do exponential back-off, but I think that's too conservative for a real-time game system (and the loss parameters are quite different).

Retransmission Timeout Algorithms (RTO):
Congestion Avoidance and Control
RFC2988
RTO with Weighted Medians
TCP Design
TCP Traffic Control
Retransmit Timer

The RTO calculation for TCP is relatively easy to implement (can be done in integer or float) and can be tuned for your application. Studying the TCP design can help understand all the elements you'll need for a reliable UDP protocol. You'll leave out or change the elements that make TCP slow/unsuitable for real-time games.

How do you know if your RTO is working well? Graph your RTT and throughput (bytes/sec) in real-time, while your protocol test suite is running (later, test in your game). Artificially drop and delay packets (e.g. DummyNet) and watch your graph(s). A good design will graph RTT as a "slow convex buildup to fast concave dropoff wave" during dropout/increased packet delay periods (See the graphs on the last link above).

This is hopefully my last question, as I'm not sure about the reciever logic.

Suppose we have:

message 1 - last in sequence 1
message 2 - last in sequence 1
message 3 - last in sequence 1

A packet with sequence 1 is sent, and we wait. In the meantime,

message 4
message 5

now exist.

Should
a) send this packet, marking message 4 and 5 with 'last in sequence 2'?
or
b) Wait for an ack of sequence 1, and then continue on. If we wait too long, resend that data

b) Seems the least problematic, and leads me to believe that the game should be highly optimized in a way that avoids depending on reliable messages.

On the other hand, with a), the message queues could end up being filled with "ack packet X" messages, and if packet X arrives before packet X-n, the reciever would somehow have to know if it's valid or not, eg an object is created in 1, and referenced in 2 (maybe not the best example), but 2 arrives before 1... I suppose in this case, drop packet 2 because 1 hasn't arrived, and don't ack any packet. Sadly, this means the message timeout period has to go by, so a reliable command will take longer.

...I can see that timing will have little to do with anything at this point. If the player pushes the "fire" button, there's no point in sending it as a reliable message. This leaves me wondering about sound effects and explosions, etc... However, I'll leave that up to the game, not the engine.

Quote:

Original post by matt_j ...I can see that timing will have little to do with anything at this point.

Timing is critical.

Quote:

Original post by matt_j If the player pushes the "fire" button,there's no point in sending it as a reliable message.

Such events must be sent reliably.

Since writing a reliable UDP system is not simple (It's highly recommended that you read through the links on RTO/TCP design), you might want to create your game-network interface with a non-reliable and a reliable API. For your first implementation use UDP for position updates, and TCP (with TCP_NO_DELAY enabled) for reliable messages. Once your game is nearing completion, and if you find that TCP does not work well (or firewall isues, etc.), you can tailor a special UDP version as needed. There are also toolkits such as RakNet (supporting reliable UDP), which appear to be free.

Quote:

Original post by John Schultz Quote: Original post by matt_j ...I can see that timing will have little to do with anything at this point. Timing is critical.

I'm going to play dumb here, so maybe I can get a useful answer that makes what I'm thinking sound stupid:

Alright, but if a packet with the "fire" command is dropped? We wait like 300 to 1000 ms or until we get the ack for that packet? The same can apply to "spawn projectile"

Edit:I know I'm probably being difficult, and I'm telling myself to stop trying to be Carmack (that time will come later), and focus on just getting my present game to work, knowing that it won't overload the network architecture.

Quote:

Original post by matt_j Quote: Original post by John Schultz Quote: Original post by matt_j ...I can see that timing will have little to do with anything at this point. Timing is critical. I'm going to play dumb here, so maybe I can get a useful answer that makes what I'm thinking sound stupid: Alright, but if a packet with the "fire" command is dropped? We wait like 300 to 1000 ms or until we get the ack for that packet? The same can apply to "spawn projectile" Edit:I know I'm probably being difficult, and I'm telling myself to stop trying to be Carmack (that time will come later), and focus on just getting my present game to work, knowing that it won't overload the network architecture.

Yes, bad things can happen if packets are dropped, such as longer delays before events take effect (due to resends). However, worse things happen if critical events are permanently lost: states will get out of sync. For example, a chain gun, flame thrower, or rocket/guided-missile are enabled via the "fire" command. The weapon may stay on for some time, and a "victim" would either not know they are getting hit, or they would take damage (via subsequent damage events from the server) and not know why.

When the network gets congested and packets are lost (or when there is a burst of game traffic due to many network events occuring at once), the best thing to do is to degrade gracefully (things slow down, but everyone will know what is going on and get used to it).

You'll have a better idea of how to create a reliable UDP system after you've written a complete game/real-time application using UDP for disposable/time-sensitive (position updates) packets and TCP for reliable/critical game events.

Again, if you wrap your game=>network API around UDP+TCP, you can change the underlying system later if necessary. This will allow you to get your game done without worrying about an optimal network layer. Once the game is nearly complete you'll have a better idea as to how to optimize the network layer. If it is necessary to improve the network layer, you can write a custom-tailored reliable UDP (read the RTO/TCP design links earlier in this thread: very helpful!), or use an existing reliable UDP system.

Do you mean that in a 32 player game, if one player has a bad connection, degrade (slow down) the game for the other 31 players to let him catch up? I can see it in an RTS game, but for a FPS shooter?

Quote:

Original post by fenghus Do you mean that in a 32 player game, if one player has a bad connection, degrade (slow down) the game for the other 31 players to let him catch up? I can see it in an RTS game, but for a FPS shooter?

Only the slow player with the bad connection should slow down. If the path from the server to all the clients degrades, all the clients should slow down. Slow down means reduction of position (and/or non-critical data) updates so that the reliable event queues can drain. I call this state "reliable recovery mode" (RRM). The degraded player's world view is already askew due to events showing up lagged, so it's OK cut data further to catch up (Voice packets should also be disabled during RRM). Once out of RRM (reliable event queues drained back to a safe level), position and voice updates resume and play continues normally. If the reliable event network queue(s) fill up, you have to disconnect the player or clear the queue and completely reset their state (the equivalent of a fresh post join state). Action/FPS games should keep reliable events to a minimum (event frequency and size) to prevent the need to enter RRM during network congestion.