Index | FAQ | Search | Memberlist | Usergroups | Profile | Log in to check your private messages | Log in | Register

Protocol Bandwidth Optimisation

| Inside3d Forums Forum Index -> Engine Programming

View previous topic :: View next topic
Author | Message
--- | ---
mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Sat Aug 02, 2008 7:25 pm Post subject: Protocol Bandwidth Optimisation |

I've split this from the general protocol discussion thread so that we don't confuse things. Two things come to mind that could be used to optimise the bandwidth usage. First is a non-breaking change, the second is a breaking change and would require a protocol version update.
Disclaimer: It's possible that other engines may have done either or both of these before. If so, shout out about what you did and how you did it; sharing the information will help formulate a standard and make it easier for everyone.
Idea 1 - Origin and Angles Updates
These are stored as floats internally on both the server side and client side. However, for transmission, Origin is demoted to a short and angles to a byte. When comparing against the basline to determine if an update is required, demote the values and do the comparison with the demoted values.
Angles would look something like this:

Code:
// ugh - the U_ANGLE bits aren't consecutive! int U_ANGLE_BITS[] = {U_ANGLE1, U_ANGLE2, U_ANGLE3}; // check angles for (i = 0; i < 3; i++) {
// the angles are decomposed into bytes for transmission, so here we check the byte values that will
// be actually transmitted!!!
if (((int) ent->v.angles[i] * 256 / 360) & 255 != ((int) ent->baseline.angles[i] * 256 / 360) & 255)
bits |= U_ANGLE_BITS[i];
}

Under the old way, a small change in angles could theoretically cause an update to be transmitted, but after being demoted to a byte, it maywell be the case that the update has no effect! This way, such a small change that has no effect is not transmitted.
E.g. an angles change from 120 to 120.5 would cause an update, but both would arrive at the client as 120.
I'm not sure how often this actually happens in the real world, but it seems a sensible thing to do anyway.
The nice thing about this change is that it can be made without breaking compatibility.
Idea 2 - Baseline Comparison
This is a breaking change.
On signon, Quake sends a baseline to the client, and also stores the baseline on the server. Each server-side update, the baseline is compared with the current value, and if it's changed, it's transmitted. On the client side, if an update is read it's used, otherwise the baseline is used.
One obvious failing of this is that the baseline relates to when the entity is spawned. In the case of dead bodies, certain doors and plats, pickup boxes (spawn above the floor then drop to it) and certain others, there will always be an update sent, even though the entity state has not changed since the last update.
The proposed change is to compare with the previous state instead of with the initial baseline. This involves storing any state changes back to the baseline on both the server side and client side, so that if no change is detected, the baseline will be correct for the previous state.
It's required on the client side as well as on the server side, so that if a server side update is not sent, the client side will fall back to a correct previous state rather than to an initial spawn state.
Sample implementation for server side:

Code:
if (ent->baseline.frame != ent->v.frame) { bits |= U_FRAME; ent->baseline.frame = ent->v.frame; }

Sample implementation for client-side:

Code:
if (bits & U_FRAME) { ent->frame = MSG_ReadByte (); ent->baseline.frame = ent->frame; }
else
ent->frame = ent->baseline.frame;

__________________________________
So it's over to you lot for discussion!
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines

Back to top |

metlslime Joined: 05 Feb 2008 Posts: 177 |

Posted: Sat Aug 02, 2008 10:33 pm Post subject: mh: |

nice, the first idea seems like a good optimization, in fact it's a good general move to suppress changes that are too small to survive the downgrading to a byte or short. Anything we can do to slightly reduce packet overflows is good. the second idea is only really possible in a system that also has the client acknowledging when it has received a packet, since otherwise a dropped packed would result in the client having a wrong baseline, which could linger for quite a while if that attribute is not updated for a long time -- for example if a monster dies, and the last frame of its death animation is in a dropped packet, it will be dead, but in the wrong frame, forever. Then the server needs to store old frames so that when a client acknowledges a frame, the server knows what to do.
you could try sending the new baseline as a reliable packet, say, every 10 seconds or so, separate from the stream of unreliable updates, and have the server wait until that packet has been received before using that new baseline, though that means that that there'd be a few frames where the client thinks the new baseline is acknowledged, but the server doesn't, so the data is out of sync.
These are the sorts of issues that a more advanced protocol like dp7 has solved, but if we want to use protocol 15 as a base, probably isn't worth it.

Back to top |

mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Sat Aug 02, 2008 11:59 pm Post subject: |

Hmmmm, that's quite true. Let's see, the really critical ones are origin, angles and frame, so an alternative option would be to cycle through them and not change the baseline for a different one of them each time. This could probably only need to happen on the server, and would give a better chance of surviving dropped packets with a reasonably intact and up to date state on the client.
Yup, just tried it and it at least doesn't blow things up.
Looks something like this:

Code:
// this outside the edicts loop static int baseline_cycle = 0; // this inside the edicts loop // store current values back to baseline if (baseline_cycle != 0) ent->baseline.frame = ent->v.frame;
if (baseline_cycle != 1) ent->baseline.origin[0] = ent->v.origin[0];
if (baseline_cycle != 2) ent->baseline.origin[1] = ent->v.origin[1];
if (baseline_cycle != 3) ent->baseline.origin[2] = ent->v.origin[2];
if (baseline_cycle != 4) ent->baseline.angles[0] = ent->v.angles[0];
if (baseline_cycle != 5) ent->baseline.angles[1] = ent->v.angles[1];
if (baseline_cycle != 6) ent->baseline.angles[2] = ent->v.angles[2];
// back outside the loop again, also change the packet overflow return to a break
if ((++baseline_cycle) > 6) baseline_cycle = 0;

I take the point about DP7, but so long as it remains relatively undocumented, it doesn't really stand a chance, does it?
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines
Last edited by mh on Sun Aug 03, 2008 12:16 am; edited 1 time in total

Back to top |

mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Sun Aug 03, 2008 12:02 am Post subject: |

By the way (and not looking to bump my post count at all, oh no siree) there's a buffer overrun vulnerability in the stock ID code. The max entity packet size is 18 bytes, but it just checks for an overflow on 16. That needs to be fixed too.
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines

Back to top |

metlslime Joined: 05 Feb 2008 Posts: 177 |

Posted: Sun Aug 03, 2008 8:53 am Post subject: mh: |

I too noticed that 16 vs. 18 mistake recently, but I don't think it won't cause an actual buffer overrun, because SZ_GetSpace will catch it. Also, not sure i understand your revised idea regarding baselines, it seems like this will, at best, cause about 1 in 7 changes to get sent in two consecutive packets, and the rest will still get sent only once and then assumed as a baseline -- and even sending twice is no guarantee.

Back to top |

mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Sun Aug 03, 2008 10:53 am Post subject: |

Let me revisit it, it was late at night! The intention is to let the previous state on the server get a little bit out of date, so that when the next update comes along it's forced roughly 3 times a second for each critical item. _________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines

Back to top |

frag.machine Joined: 25 Nov 2006 Posts: 728 |

Posted: Sun Aug 03, 2008 4:29 pm Post subject: Re: mh: |

metlslime wrote:
the second idea is only really possible in a system that also has the client acknowledging when it has received a packet, since otherwise a dropped packed would result in the client having a wrong baseline, which could linger for quite a while if that attribute is not updated for a long time -- for example if a monster dies, and the last frame of its death animation is in a dropped packet, it will be dead, but in the wrong frame, forever. Then the server needs to store old frames so that when a client acknowledges a frame, the server knows what to do.

BTW according to this Quake 3 works in a very similar way. I have my doubts if this approach is suitable to a single player oriented protocol though.

metlslime wrote:
you could try sending the new baseline as a reliable packet, say, every 10 seconds or so, separate from the stream of unreliable updates, and have the server wait until that packet has been received before using that new baseline, though that means that that there'd be a few frames where the client thinks the new baseline is acknowledged, but the server doesn't, so the data is out of sync.

OR, by comparing simple baseline checksums client and server could determine the need to send a new baseline.
_________________
frag.machine - Q2K4 Project
http://fragmachine.quakedev.com/

Back to top |

Spike Joined: 05 Nov 2004 Posts: 944 Location: UK |

Posted: Mon Aug 04, 2008 8:00 am Post subject: |

The strengths/weaknesses of many protocols come down to just how they transfer entities (the QW/NQ split is not entirely backwards compatible, and is the main reason modders still don't much like QW - because many features were stripped). But if you want backwards compatible protocols then the major optimisations come from entities.
The original Quake protocol has only a baseline. Every single frame, all entities that are visible are resent deltaed from that baseline. There is no context other than the current state of the entities and the baseline. If you read the documentation somewhere, you'll see that they claim it to be a deltaed protocol. Presumably they didn't even have baselines at one point. Hurrah for LANs.
This copes with packetloss nicely though. :D
Just a shame that each update clogs that 56k modem for half a second each packet. Or longer.
The Quakeworld protocol has 64 different versions of each entity.
The client acknoledges the packet sent by the server, the server sends the differences between the ones that were sent in that packet. New entities are deltaed from the baseline. Drop too many packets and the entities are resent from baselines again.
This works well for reducing apparent latency. A dropped packet will not be noticed beyond the next packet that did arrive.
But on a high latency link, you'll receive the same updates 5 times in a row.
An individual entity will never be half updated.
Note that quakeworld's protocol implements rate limiting as actual dropped packets. :)
Quakeworld was really designed for 300ms ping and 10% packetloss...
Make for AOL!
The DP5+ protocol is slightly different. I wish I could fully remember how it works, so I might be slightly wrong here. Ultimately it only resends entities that are known to have been dropped.
This exhibits worse behaviour when you have packetloss as any dropped packets will not be resent until the next one has arrived and been then acked and received by the server also.
I'd say more, but my memory of the protocol is hazy.
I *think* an entity can be half-updated if there was packetloss.
The (expected) CSQC protocol works similarly to DP5+. The versions are used to remember which version was last sent to the client. The server saves the packet index and the version each time it sends an entity to the client. If the client's sequence numbers indicate a dropped packet, the server resends any entities with a still-unchanged version number with that sequence.
A rapidly moving object will be updating its version number frequently. Its true that the entire entitiy is resent each time the version changes, but with things like rockets, the only actual data expected to be in the packet are its type, origin, and direction. (actually, csqc expects rockets+nails to be sent as source+direction, and to have their version updated only twice - once at spawn, once at removal). Players end up with constantly changing angles and origin anyway. The extra redundancy makes little difference.
Entity updates will be seen updating fully. But only when they actually update. You won't get a half-way changed csqc entity (unless you use multiple ents for a single 'object'). This is part of the justification for having a seperate entity mechanism.
Note that QuakeWorld also sends players using a seperate mechanism from enitities (unless using csqc for players, of course).
Also note that the nq protocol resends the ammo counts every packet (QW and DP5+ do not).
QuakeWorld also never sends the current time across the network, while NQ sends the time in every unreliable packet. This is a hinderance to smooth animations however. But for some reason, sending 77 packets every second (vs 20?) kinda negates the need.
_________________
What's a signature?

Back to top |

Urre Joined: 05 Nov 2004 Posts: 1073 Location: Sweden |

Posted: Mon Aug 04, 2008 1:25 pm Post subject: |

There will be a CSQC protocol? Cool. Speaking of which, and as it's related to networking, I'll say it here. I recently realised I quite dislike the fact that CSQC always sends the entire entity, it seems unnecessary to me. Is there really no way to redesign that to be able to send partial updates, coupled with some sort of recieve confirmation, so packetloss isn't fatal. Like, create packets which stay in memory and keep being resent at regular intervals until a confirmation about recieval from the client is intercepted, and check packet versioning on the client to make sure old values don't overwrite newer ones in case an old packet is recieved after a newer one.
_________________
Look out for Twigboy

Back to top |

Spike Joined: 05 Nov 2004 Posts: 944 Location: UK |

Posted: Mon Aug 04, 2008 9:42 pm Post subject: |

I guess my previous post was simply meaningless babble because it didn't have a summary. Unless you're sending entities via the reliable channel, any delta updates have to be based upon what is sent. Different protocol designs do different things best, which makes standardization a little tricky.
Regarding non-q1 engines. Q2's protocol is like QuakeWorld's, except other players are no longer special, and timing information is sent to allow for interpolation at lower packet rates. The state information on the server forms a cyclic array shared between all clients/entities, although on the wire this isn't really important.
Q3's protocol again bears similarities to the QW mechanisms. Except bitwise. The delta itself is different though, as Q3 has more fields that can be sent. It basically sends all the fields of an entity between, eg, origin_x and modelindex. Its a lot more generic in that the fields are specified by a data structure rather than in code.
Regarding the CSQC entity protocol, I admit that it would be nice to have some greater control over initial data sets. So that things that will never change are never spammed. But here's the problem, consider you want to apply it to a player. Imagine that you want to send their custom model name only when they're first seen. What happens if that initial packet is lost? Well, randomly, that player would have a default model. You could only resend on aknoledgement, but then you'd have an entity arriving sent (remember, players change every single frame) without its initial data. Okay, you could make your qc mod cope with that. You can't draw the player yet until you know their model, so your other player is invisible for a bit (consider teleporting somewhere, you'd get a large paket which is more likly to be dropped than the trailing packets). But ultimatly you'd have a lot of mods written and tested on lans where packetloss simply does not occur. It would be all too easy.
Alternatively what if you spam it every single frame until its acknowledged?... Well, you've not really gained that much. Yes, it can be done, but tbh, csqc already baffles enough people without the special cases. :)
In QC version 1.0, the csqc will have access to the engine deltaed entities. CSQC mods will still be recommended to use shared entities for rockets and nails. I'm not entirely sure which fields are going to be sent, but origins and angles will be interpolated for you. Effects can be disabled if you wish to add them yourself (or if you want to reuse the effects field, but beware muzzleflashes).
I have no idea about custom fields yet. I might specify a deltaing system for custom fields a-la q3, although the current version of fte uses the existing deltas.
But yeah, with csqc's shard entities, the biggest strength of it is that you can send rockets and nails with two update, and a single removal. 3 packets. whereas currently a nail/rocket is sent every single frame. This makes them more efficient than lightning guns, and certainly more efficient than NQ shotguns. Talking about shotguns, you can again use a CSQC entity to specify the spread of the pellets, but you need predefined splatter patterns to make it efficient. Lightning gun spam can be set with a single flag on the user. Eg, if you add visible weapons and they're in a firing frame with the lightning gun selected, you know you need to draw a lightning beam too. This saves you 6 coords per entity frame. It's 280 bytes per second in DP7, as an example. And thats ignoring that you can do sound too.
Q3's netcode is so much better than Q1's because a) it has proper compression (moot if you use DP). b) it has clientside gamecode which can interpret the events in an efficient way. In Q3, rockets are sent as the initial firing event, and an explosion. Nothing more needed. Ultimatly to make quake playable in crowded rooms is to stop those friggin nailguns from spamming the entire world. Great. 32 players all firing 10 nails a second. 320 new nails a second updating 20 times a second for 3 seconds until they hit a wall. That is a heck of a lot of updates. And Q3 doesn't suffer from that so much (mm, plasma gun). And CSQC mods have the option to avoid it too.
_________________
What's a signature?

Back to top |

Urre Joined: 05 Nov 2004 Posts: 1073 Location: Sweden |

Posted: Mon Aug 04, 2008 11:30 pm Post subject: |

Cool stuff Spike. LordHavoc briefly mentioned a .ChannelFlags field briefly in #darkplaces recently, which would contain a byte about what's being updated, and the csqc would intercept it and thus know which fields to update. I'm not sure about the specifics. Trying to get him here to comment.
_________________
Look out for Twigboy

Back to top |

LordHavoc Joined: 05 Nov 2004 Posts: 243 Location: western Oregon, USA |

Posted: Tue Aug 05, 2008 4:48 am Post subject: |

Urre wrote:
Cool stuff Spike. LordHavoc briefly mentioned a .ChannelFlags field briefly in #darkplaces recently, which would contain a byte about what's being updated, and the csqc would intercept it and thus know which fields to update. I'm not sure about the specifics. Trying to get him here to comment.

Not a byte, an int (well, 24 bits).
The idea being that the qc can bump .Version and set flags for changed properties, and the engine will mark all those flags as needing sending.
Then when SendEntity is called the active flags that need to be sent (either due to the .Version bump and the .ChannelFlags bits, or due to packet loss causing some of them to be reflagged) will be provided in a parameter, which it can WriteByte or WriteShort or similar if it wishes to, and the read function just does the same to find out what's included, basically identical to all quake protocols.
The alternative way I can think of to generate the flags is to have a whole array of .Version fields, one for each field.
Keep in mind this only works if you don't interpret the version as reason to re-send on packet loss, instead relying on bit tracking (like DP5+ protocol), where bits are restored if a packetlog of a lost packet indicates a bit was set and no later packetlog had that bit set (after all, a later packet would have arrived sooner than any resend attempt).
DP5+ are the protocols I am proud of, CSQC's protocol flaw is the lack of .ChannelFlags, otherwise it would be universally superior to DP5+.

Back to top |

Entar Joined: 05 Nov 2004 Posts: 422 Location: At my computer |

Posted: Tue Aug 05, 2008 7:59 pm Post subject: |

mh: I tried your idea of checking whether an angle change, once converted to a byte, will make any difference, and added a Console print in cases that it caught bits that were not useful but would otherwise have been added. It caught more than I expected, though not a gigantic bunch. I deem it a useful addition
_________________
woh... feelin woozy... too much cider...
http://entar.quakedev.com
games fascination - My Game Development Blog/Journal

Back to top |

mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Wed Aug 06, 2008 12:56 pm Post subject: |

That confirms my suspicions that a lot of those updates weren't really necessary. I do hope you caught the parentheses I'd left out above, by the way... _________________ DirectQ Engine - New release 1.8.666a, 9th August 2010 MHQuake Blog (General)
Direct3D 8 Quake Engines

Back to top |

Entar Joined: 05 Nov 2004 Posts: 422 Location: At my computer |

Posted: Thu Aug 07, 2008 2:09 am Post subject: |

mh wrote:
That confirms my suspicions that a lot of those updates weren't really necessary. I do hope you caught the parentheses I'd left out above, by the way...

Well, I actually took the idea and made it work in my engine (which is just slightly different, as it adds +0.5 so as to round to the nearest whole number, rather than always round down). I basically just compared the values based on what would be sent across the server.
_________________
woh... feelin woozy... too much cider...
http://entar.quakedev.com
games fascination - My Game Development Blog/Journal

Back to top |

Display posts from previous:

| Inside3d Forums Forum Index -> Engine Programming | All times are GMT
Page 1 of 1

Jump to:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2004 phpBB Group