Protocol Bandwidth Optimisation

[mh]

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: Select all

		// 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: Select all

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

Sample implementation for client-side:

Code: Select all

	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!

[metlslime]

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.

[mh]

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: Select all

// 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?

[mh]

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.

[metlslime]

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.

[mh]

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.

[frag.machine]

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.

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.

[Spike]

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.

[Urre]

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.

[Spike]

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.

[Urre]

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.

[LordHavoc]

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+.

[Entar]

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

[mh]

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...

[Entar]

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.