Handling Congestion
Hello, I'm developing a real-time game using both UDP and TCP. I'm trying to deal with the situation where I can't send as much data as I'd like due to low bandwidth.
Right now I'm checking the return value of my send and sendto functions. If I couldn't send the whole message, I mark the connection as "congested". After 20-50 milliseconds have passed, I set it back to "uncongested". I don't send more data while the congested flag is set. This seems very crude to me. If I need to send a large packet, I may never be able to send it without triggering my congestion mechanism. And I may be falsely declaring the system as congested when it can send more data.
And I'm not interested in sending partial messages anyways, right now I just discard them. What do you recommend to deal with this problem?
I use a bit packet system so breaking messages and setting up a first in first out queue probably wouldn't be a problem for separating data over a time. What is your congestion point? How many bytes?
http://gpwiki.org/index.php/Binary_Packet
I wouldn't just drop packets though. I mean that is extremely crude. Just send the data, or detect if a congestion might happen, then just delay certain state changes. Set up a priority system maybe like:
playerObject.SerializeChangedData(&packet, priority);//priority = 4, there's been some lag and you only want to send the most important things, like position data or health.
then inside set up a crude checking system:
if(priority <= 4 && healthChanged)//stuff the health variable in
if(priority <= 5 && posChanged)//stuff the position data into the packet
if(priority <= 1 && statsChanged)//if the bandwidth isn't bad send the stats of this character...
you can find priority by how close the player may be to another player or by tons of other data. For instance, friendly players don't have to be updated as often in some game types.
just an idea. Not sure how much bandwidth you wanna shave off.
http://gpwiki.org/index.php/Binary_Packet
I wouldn't just drop packets though. I mean that is extremely crude. Just send the data, or detect if a congestion might happen, then just delay certain state changes. Set up a priority system maybe like:
playerObject.SerializeChangedData(&packet, priority);//priority = 4, there's been some lag and you only want to send the most important things, like position data or health.
then inside set up a crude checking system:
if(priority <= 4 && healthChanged)//stuff the health variable in
if(priority <= 5 && posChanged)//stuff the position data into the packet
if(priority <= 1 && statsChanged)//if the bandwidth isn't bad send the stats of this character...
you can find priority by how close the player may be to another player or by tons of other data. For instance, friendly players don't have to be updated as often in some game types.
just an idea. Not sure how much bandwidth you wanna shave off.
Yeah, all my data is sent in binary form. I try to reduce it as much as possible on my own, then I run it through zlib. If zlib could compress it further, I send '1' at the front of my message, followed by the compressed version. Otherwise, I send '0' followed by the uncompressed version. (zlib can actually increase the size of data if it's already very random or has a small size)
My problem is this: how can I tell how many bytes can be sent without blocking? I've been looking at poll and select, but they only seem indicate 'writable' or 'non-writable'. Doesn't seem useful, I can figure that out by trying to send and getting a 0 or negative value.
If I knew my limitations beforehand, then I could send the most important data, as you say. Or maybe it would be better to wait to see if the number of 'sendable' bytes increases at a later time? Because if I keep sending the most important data and completely using all bandwidth, the less important stuff might never be sent...
But then again, maybe this is a slow link and I'll NEVER be able to send a single packet with everything? So confusing!
My problem is this: how can I tell how many bytes can be sent without blocking? I've been looking at poll and select, but they only seem indicate 'writable' or 'non-writable'. Doesn't seem useful, I can figure that out by trying to send and getting a 0 or negative value.
If I knew my limitations beforehand, then I could send the most important data, as you say. Or maybe it would be better to wait to see if the number of 'sendable' bytes increases at a later time? Because if I keep sending the most important data and completely using all bandwidth, the less important stuff might never be sent...
But then again, maybe this is a slow link and I'll NEVER be able to send a single packet with everything? So confusing!
Quote:Right now I'm checking the return value of my send and sendto functions. If I couldn't send the whole message, I mark the connection as "congested".
TCP already does congestion control on its own. Btw: 50 milliseconds to clear congestion isn't sufficient time for Internet connections. What not sending all the data means for TCP, is that your send buffer is full, which will typically be at least dozens of kilobytes in the queue. 50 milliseconds isn't enough to let that drain except for LAN connections.
For UDP, your suggestion won't work at all, because UDP packets are always accepted and never acknowledged (unless the local interface is congested). You have to do congestion control by putting control information in your own protocol on top of UDP, and looking at where you get acknowledge and packet drops.
I hear you. So if I ever wanted to send latency-sensitive data over TCP, I'd have to define some minimum bandwidth amount to run my game. And if your network doesn't have this bandwidth, dozens of kilobytes of data will back up before I can detect it, causing multiple seconds of lag.
Is this how commercial games operate? I notice a lot of them use TCP. For example, World of WarCraft. I guess it makes sense, these days most packet losses occur because of congestion, not interference. If you keep your send rate low, the packet drop rate (and retransmission rate) might be acceptable. I wonder how wireless users like real-time TCP? Can be lots of interference there.
For UDP, congestion on the outgoing link is all I was aiming for.
Is this how commercial games operate? I notice a lot of them use TCP. For example, World of WarCraft. I guess it makes sense, these days most packet losses occur because of congestion, not interference. If you keep your send rate low, the packet drop rate (and retransmission rate) might be acceptable. I wonder how wireless users like real-time TCP? Can be lots of interference there.
For UDP, congestion on the outgoing link is all I was aiming for.
I went with manual bandwidth control via UDP (TCP is somewhat pointless, since it handles most of it itself, and what it doesn't, isn't really useful)
Backend pushes messages (4 - 400 bytes) to each clients queue.
Server then has several worker threads which run through these clients in round-robin fashion and send as much data as possible.
Server is designed to throttle between 1k and MAX bytes per second. MAX is determined by total outgoing bandwidth and number of clients.
When it's each client's turn, worker requests a certain ammount of bytes. I have 3 priorities going:
- Protocol level (send immediately, without regard to bandwidth) used for acks, and other low level data
- Immediate unreliable (sent immediately, with bandwidth consideration, if late, congested, these are dropped) used for some position updates, and some optional messages
- Reliable (sent whenever bandwidth is available, never dropped). If any of the messages doesn't arrive in either direction after several resends, and sequence cannot be re-established, the connection is dropped.
I have some hints about clients performance. One is the round-trip time, acks are sent immediately, so this gives me pretty accurate guess at latency, as well as overall connection quality.
Connection to each client starts slowly at 1.5k/sec limit, then it's throttled up, until it reaches MAX or client starts dropping packets, at which point client's rate is halved, and the process throttling restarts.
This isn't optimal, and likely isn't suitable for cases where most of traffic is real-time. In my case, reliable layer is used for world state synchronization, and as such can take some time in busy areas, and client can't do much about it but download full state.
Once synchronized, each clients receives deltas only, which represent considerably less traffic than initial sync.
Average traffic after synchronization is 0.1kb/sec upstream, 1.5k downstream.
So far, the only problems I did encounter was filling up of clients send queue, which isn't a problem in itself, but it makes buffering much more annoying. Each queue needs to be dynamic, since during initial sync or load spikes the ammount of queued messages can aproach or even exceed 1 meg (making it unviable to have a static buffer per client - 500-1 gig of ram just for buffers).
I was looking into guessing client's bandwidth, but didn't find anything reliable enough, so I simply guess based on dropped packets.
Backend pushes messages (4 - 400 bytes) to each clients queue.
Server then has several worker threads which run through these clients in round-robin fashion and send as much data as possible.
Server is designed to throttle between 1k and MAX bytes per second. MAX is determined by total outgoing bandwidth and number of clients.
When it's each client's turn, worker requests a certain ammount of bytes. I have 3 priorities going:
- Protocol level (send immediately, without regard to bandwidth) used for acks, and other low level data
- Immediate unreliable (sent immediately, with bandwidth consideration, if late, congested, these are dropped) used for some position updates, and some optional messages
- Reliable (sent whenever bandwidth is available, never dropped). If any of the messages doesn't arrive in either direction after several resends, and sequence cannot be re-established, the connection is dropped.
I have some hints about clients performance. One is the round-trip time, acks are sent immediately, so this gives me pretty accurate guess at latency, as well as overall connection quality.
Connection to each client starts slowly at 1.5k/sec limit, then it's throttled up, until it reaches MAX or client starts dropping packets, at which point client's rate is halved, and the process throttling restarts.
This isn't optimal, and likely isn't suitable for cases where most of traffic is real-time. In my case, reliable layer is used for world state synchronization, and as such can take some time in busy areas, and client can't do much about it but download full state.
Once synchronized, each clients receives deltas only, which represent considerably less traffic than initial sync.
Average traffic after synchronization is 0.1kb/sec upstream, 1.5k downstream.
So far, the only problems I did encounter was filling up of clients send queue, which isn't a problem in itself, but it makes buffering much more annoying. Each queue needs to be dynamic, since during initial sync or load spikes the ammount of queued messages can aproach or even exceed 1 meg (making it unviable to have a static buffer per client - 500-1 gig of ram just for buffers).
I was looking into guessing client's bandwidth, but didn't find anything reliable enough, so I simply guess based on dropped packets.
My implementation is somewhat similar - I have a subsystem with a dynamic queue for each client.
But I only have two classes of traffic: UDP (send immediately regardless of bandwidth) and TCP (gets added to the queue and re-sent later if we couldn't send now).
I periodically update the state with UDP. UDP only ever sends the state that changed since the previous UDP update.
With TCP, I periodically send the entire game state "in the background". This may take a second or two. When the client receives the TCP state, it only uses the parts of the state that haven't been updated by UDP in the meantime. The rest is discarded. This way I can synchronize without introducing lag.
Right now I can't say that I'm interested in implementing my own congestion control over UDP. So my tentative plan is to keep UDP transmissions sufficiently low-bandwidth so that dial up users can play. Just drop the UDP congestion issue completely, use a fixed send rate.
And I'll try to gradually increase my TCP bandwidth until I can't send, and then drop the send rate. A pity there's no way to do this without adding massive amounts of lag.
Thanks for all the help!
But I only have two classes of traffic: UDP (send immediately regardless of bandwidth) and TCP (gets added to the queue and re-sent later if we couldn't send now).
I periodically update the state with UDP. UDP only ever sends the state that changed since the previous UDP update.
With TCP, I periodically send the entire game state "in the background". This may take a second or two. When the client receives the TCP state, it only uses the parts of the state that haven't been updated by UDP in the meantime. The rest is discarded. This way I can synchronize without introducing lag.
Right now I can't say that I'm interested in implementing my own congestion control over UDP. So my tentative plan is to keep UDP transmissions sufficiently low-bandwidth so that dial up users can play. Just drop the UDP congestion issue completely, use a fixed send rate.
And I'll try to gradually increase my TCP bandwidth until I can't send, and then drop the send rate. A pity there's no way to do this without adding massive amounts of lag.
Thanks for all the help!
Quote:For UDP, congestion on the outgoing link is all I was aiming for.
Well, the part of the outgoing link that matters is the gateway/router/firewall/DSL modem/whatever. Your computer will have a 100 Mbps or 1 Gbps link to that gateway. UDP will only show packet not sent if you're saturating that 1 Gbps link.
Most game define a minimum bandwidth you need to play, and design to that bandwidth. When the game wants to use more bandwidth, it might push more out, and measure whether there's loss or not.
Btw: when you're saying "send as much as possible" to a client, I hope that means "pack as many messages as possible into a target-size UDP datagram." Sending more than one UDP datagram at the same time is wasteful on overhead.
Quote:UDP will only show packet not sent if you're saturating that 1 Gbps link.I understand. I was thinking of dial-up users here. My send rate should never be anything like high enough to swamp a network card.
Quote:when you're saying "send as much as possible" to a client, I hope that means "pack as many messages as possible into a target-size UDP datagram."
My thinking was: If bandwidth is plentiful, the server sends state updates 20 times per second.
If the connection can't handle this, reduce the send rate as low as 10 times per second.
And if I can't even send 10 times per second, start omitting less important info from the packet.
In this way, performance could degrade gracefully as bandwidth declines. Now I'm thinking more along the lines of fixed send rates, and perhaps an option in the game to switch between high speed and dial up connections.
Your congestion scheme should also have signals to send upwards to the server's simulation layer, so that when a slowdown occurs (and is detected) that layer can start decreasing/throttling the quantity of interactions: ie- stop NPCs beating on players, send simpler environmental updates, shrink the radius of object uptdates that a player can see (and is sent), increasing the interval length of the simulations resolution cycles, etc... You wont have to decide what to discard, when the simulation itself is generating less game dats.
Top down countermeasures cutting back on new data generation can be more effective
when trying to recover/restabalize the system.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement