Yet another interesting problem
Author
I'm using UDP, and packets are sent every 50 ms from both ends (at the moment, anyway).
Each end (client and server) have a reliable message queue. Each message has a sequence ID.
For example, the server will fill packets up starting with the oldest sequence ID needed to update the client according to its last acked sequence ID, and work its way to the newest.
Problem... Suppose a bad connection and really large messages:
Server (sequence = 8): has messages queued for sequences 2 through 8, as the client hasn't acked for a while. Only messages with IDs 2 through 4 can fit in a packet, and there's no room for anything with ID 5 or higher.
Client acks "6"... like I just said, the server could have only fit info for messages with IDs 2 through 4, so assuming the client got information up to 6 is wrong...
What is a good way around this problem?
Edit: It looks like Quake 2 (and possibly Quake 3) is only capable of sending one reliable message at once. Maybe this is a better solution, but sacrificing speed?
[Edited by - matt_j on April 12, 2005 9:10:26 PM]
Author
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.
"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.
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.
Author
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]
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.
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.
Author
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.
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.
Author
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?
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).
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).
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 topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
