Sign in to follow this  

"The Quake3 Networking Model" Question

This topic is 4711 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I just read this article at http://www.bookofhook.com/Article/GameDevelopment/TheQuake3NetworkingModel.html and I'am trying to understand why: "server sends sequenced game state updates that are delta compressed from the last acknowledged game state the client received". If "first person" side does client side prediction, what does it matter, how other third person players had moved till I got new game-state update? OK, I missed few updates, made prediction for them (possible got some of them wrong) but now with new update packet I can fix it all. So why would I need all that game-state updates I missed? If "Dropped packets are handled implicitly..." why it is so important to send them? Thanks.

Share this post


Link to post
Share on other sites
You seem to be asking whether the Quake 3 model re-sends dropped packets.

The answer is that it does not.

For each packet that DOES get through, the other end acknowledges in their next packet. This way, the two can share a common baseline for delta compression.

Delta compression is used to minimize the amount of data sent; movement as a delta from where you were half a second ago can be sent with fewer bits than movement in an absolute (world-space) coordinate frame.

Share this post


Link to post
Share on other sites
just wondering but why doesn t he include visiblility calculations to the networking system?

do you really have to know whats going on 4 blocks behind you?

Share this post


Link to post
Share on other sites
In Quake, it's possible to turn 180 degrees with a flick of the wrist (skilled players do this all the time). The levels are usually fairly small, too. And there are ranged weapons (such as rocket launcher) that you absolutely need to know about wherever they are on the map. Thus, typical FPS-es don't do visibility filtering much.

Share this post


Link to post
Share on other sites
What is still a mystery for me is if server generates one update packet and send it to all clients, so if just one client does not get some packet - server now have to increase delta range.

For instance:
Server sent delta(Pos(1) - Pos(0)).
Got ack from all clients.

Server sent delta(Pos(2) - Pos(1)).
Did not get ack from only one client-A.

Now Server sends to all delta(Pos(3) - Pos(1)).
...

So the delta range can grow is'n it ?

Share this post


Link to post
Share on other sites
Well, i may be wrong but as far as i understand it, you have to store the last ack for every client independently. So in your case you would send delta(Pos(3)-Pos(2)) to all clients except client A and delta(Pos(3)-Pos(1)) to client A only.

Quote:

So the delta range can grow is'n it ?

Yes, that's right.

Now i have another question: How about more data consuming things like chat messages? Would you send them again and again in every packet until you receive an ack for at least one of those packets containing the chat message? Or is it better to send those only something like every 10th frame? But wouldn't that break the delta compression mechanism?

Share this post


Link to post
Share on other sites
Please correct me if I'm wrong but I was sure that if server

1. Prepare data for client.
2. Add CRC
3. Encript packet

for each client that would be some waste of time/performance(more latency).
I thought server could send the same data packet for everyone.

Share this post


Link to post
Share on other sites
Quote:
Original post by Basiror
just wondering but why doesn t he include visiblility calculations to the networking system?

do you really have to know whats going on 4 blocks behind you?


I don't know about Q3, but Half Life (and probably HL2) does do a PVS check. This is mostly useful for preventing wallhacks.

Share this post


Link to post
Share on other sites
Quote:
Now i have another question: How about more data consuming things like chat messages? Would you send them again and again in every packet until you receive an ack for at least one of those packets containing the chat message? Or is it better to send those only something like every 10th frame? But wouldn't that break the delta compression mechanism?

I think the easiest way round that one would be to keep a TCP socket open for non-time-critical (but still important) data. That way you can blame the service provider for any missing chat packets [grin]

Share this post


Link to post
Share on other sites
Barabashka: The server has to send data to each client independently (at least in the client/server model) because each client needs a different, small part of the overall game state. To build a packet that you could simple fire off to each client would require a whole heck of a lot more data, which is a huge waste of bandwidth. Since server power is easier to scale than bandwidth, we pass the hit onto the server instead.

Also note that, as currently implemented, the Q3 network model has a nasty flaw: one laggy/poor client connection can quickly slow the whole server down. This is because each time a client lags, it forces the server to send more data on the next pass. If this continues for too long, eventually the server is trying to send a whole heck of a lot of data to that client in order to catch it up. This ends up lagging every other connection, which creates a very nasty vicious cycle. They could've implemented a per-socket throttle, but for whatever reason didn't.

A far more interesting network model (IMHO), is the one they used in Tribes 2. I can't seem to find the bookmark, but google should provide the answers.

Share this post


Link to post
Share on other sites
Quote:
for each client that would be some waste of time/performance


As long as your connection can fit on a 56k modem, or even most actual broadband connections, the encryption of the data won't be a major CPU hog on the server. The amount of data (5 kilobytes per second per player, tops?) is miniscule compared to the actual throughput of modern CPUs (5 GIGAbytes per second of memory throughput -- that's a factor of a million!).

You don't need to add your own CRC, because UDP already does that for you. You might want to sign the packet, though -- typically, you'll want to use an encryption mechanism that can both sign and encrypt in the same go, although re-signing when the packet is already in the cache is really cheap.

Now, that being said, I don't recommend encrypting your data sent from the server. Signing is more important than encryption. Encryption doesn't actually give you any more security, because anything that the client can present to the user, the user can (by definition) figure out how to decrypt.

Quote:
How about more data consuming things like chat messages? Would you send them again and again in every packet until you receive an ack for at least one of those packets containing the chat message? Or is it better to send those only something like every 10th frame? But wouldn't that break the delta compression mechanism?


I'm assuming the delta is not a raw, per-byte delta compression, but instead a data structure aware, variable-bit-length delta compression mechanism. Thus, it would delta-compress each individual position, heading, and other datum within the packet. Tacking on chat, or not, in the same packet does not affect that compression.

If a server gets laggy when a single player is falling behind, then that server is running with too many players for the size connection it has. That's hardly a fault of the game, rather of the operator. You have to design in enough headroom in your system (hardware/hosting) to deal with hiccups, or it's never going to stay stable.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
If a server gets laggy when a single player is falling behind, then that server is running with too many players for the size connection it has. That's hardly a fault of the game, rather of the operator. You have to design in enough headroom in your system (hardware/hosting) to deal with hiccups, or it's never going to stay stable.


Unless, of course the lag is caused by the client connection, which is not in the operators control. One can even picture a DOS attack based on this: a custom client designed to connect to a server and simulate lost packets and high latency, slowing down the game for everyone. From this perspective, it's the game's responsibility to minimize the impact of a single bad client on everyone else.

Share this post


Link to post
Share on other sites
Quote:
Unless, of course the lag is caused by the client connection


A single player lagging should not affect the other players, even if that player needs more bandwidth (i e, the benefits of delta compression shrink). There is an upper bound on the size of a state update, which is one-over-delta-compression-ratio. Typically, you might get 50% of delta compression, so one laggy client would be the same as two non-laggy clients. If you don't have space for at least one more non-laggy client on your server, I believe you're running with too little headroom.

Share this post


Link to post
Share on other sites
Quote:
Original post by Morbo
Also note that, as currently implemented, the Q3 network model has a nasty flaw: one laggy/poor client connection can quickly slow the whole server down. This is because each time a client lags, it forces the server to send more data on the next pass. If this continues for too long, eventually the server is trying to send a whole heck of a lot of data to that client in order to catch it up. This ends up lagging every other connection, which creates a very nasty vicious cycle. They could've implemented a per-socket throttle, but for whatever reason didn't.


this is wrong.

one client's sucky connection cannot lag anyone else. ever. period.

per socket throttling (rather per client) is implemented. indisputable fact. all packets to each individual client obey rate settings, always. if the data to be sent would exceed the rate, their snaps are delayed so they will always stay under the client rate setting.

client lost packets, etc also do not generate any more work for the server. snaps are generated fresh every frame, regardless of whether a client acknowledged them or not. large snaps are typical when clients enter new clusters or when a bunch of new entities are spawned, so theres no difference really for snaps from dropped frames vs snaps from "normal" gameplay.

Share this post


Link to post
Share on other sites
just to make sure if i got this right

instead of sending the client the coordinates ... of a player you send the curpos-laspos so your numbers get much smaller and you spare a few bits

analog for the rest of the gamestate data


what about values that didn t change considerably? e.g. a angle differs only 1 degree or if a player is 72 units large and the positio differs only a few units 0-4?

you wouldn t update in this case right?


i would implement a 16 oder 32 integer at the top of the gamestate where i set flags whether this variable has changed or not

how often do you update gamestates per second 6 8 12 times?

Share this post


Link to post
Share on other sites
That's not what delta means, at least not for the Quake 2 and Half-Life protocols. Quake 3 might be different, but I really doubt it, because it only makes things more complicated.

Delta simply means that of any structure (e.g. entity data) only the fields that have changed since the last acknowledge state are sent. The fields that did change are sent in their entirety. So the data that updates a structure has a small header bitfield indicating which fields are resent, followed by the data itself.

Fields are always updated if changed, even if the changes are minor. However, at least Half-Life uses bit packing and is rather aggressive about how many bits per field are used. IIRC game updates are sent at a fixed rate, while the client sends commands at the client frame rate.

cu,
Prefect

Share this post


Link to post
Share on other sites
Quote:
Original post by Basiror
how often do you update gamestates per second 6 8 12 times?


sv_fps determines the number of updates per second the server will try to send. its usually 20 in quake3.

Share this post


Link to post
Share on other sites
Quote:
Original post by Prefect
That's not what delta means, at least not for the Quake 2 and Half-Life protocols. Quake 3 might be different, but I really doubt it, because it only makes things more complicated.


I thought that delta compression algorithm is all about sending differences and not all data. Using delta u can pack position (x,y,z data) with very good accuracy, but still bit packing is very useful.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Barabashka
Quote:
Original post by Prefect
That's not what delta means, at least not for the Quake 2 and Half-Life protocols. Quake 3 might be different, but I really doubt it, because it only makes things more complicated.


I thought that delta compression algorithm is all about sending differences and not all data. Using delta u can pack position (x,y,z data) with very good accuracy, but still bit packing is very useful.


Quake3 uses delta compression at a different level in the protocol layers.

"delta comrpession of text" == you look at which bytes have changed between two sets of bytes, and send only the difference, or delta

"delta compression of quake3 high-level application protocol" == don't worry if the client failed to receive some information that is critical, and DON'T resend it - check to see if that information has now been "overwritten" by mroe recent information since you sent it, and only send the newer information.

This is called "delta" compression because...you are sending deltas of the server's and client's FSMs. The server keeps track of what state it knows the client is in "at least" and does a delta-compare of that FSM to the "true" FSM of the server.

So. "delta compression" is a term so generic it has multiple unrelated meanings even in the same niche of networking :).

The point of Q3 networking is not to "reduce the amount of data needed to encode the postiion etc" but instead to "reduce the number of packets that have to be transmitted when there is packet loss". It's "solving" the problem of connections with high packet loss.

The base case without this is that you have to re-send every change of state until it's acknowledge, otherwise the FSM's get out of synch. The q3 model is cunning and novel, enough for one to say that id have finally got competent network programmers capable of doing good stuff. But it's not especially amazing - a lot of people would come up with the same idea to solve the FSM-synch problems. Compared to id's historic incompetence at network programming (quake 1 - oh my god!), it is pretty amazing ;)

redmilamber

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
"delta compression of quake3 high-level application protocol" == don't worry if the client failed to receive some information that is critical, and DON'T resend it - check to see if that information has now been "overwritten" by mroe recent information since you sent it, and only send the newer information.
redmilamber


As I understand if q3 don't resends some critical data, how do they deal with
the case when some client started to fire weapon and this packet lost ?
Or it's just the server side ?

Unreal do resend critical packets like this one, don't they ?

Share this post


Link to post
Share on other sites
well usually servers have equal up and down streams and the upstream of a client usually isn t limited

the problem is the increasing amount of data you need to send the more clients connect to your game



ok now we have heart both delta compression concepts quake3/hl

so id go with this

i include a header into the packet to tell the client which bitpacking formats to use for the delta compressed gamestates

e.g.

i check to get the minimum required amount of bits to encode the delta vectors

positions should cost the most space in a packet i think

then i i bitpack the delta packet based on the gained information of bits/variable

if these packets are above a certain size 300 byte for example i apply a huffman compression


only one thing that s unclear is how did they initially sync a player with the network? you once send the gamestate when you connect which takes a few kbs

so you miss a few packets and lag a few seconds at the start up
if you manage to sync at all

Share this post


Link to post
Share on other sites
I obviously don't know all the details of Quake 3 networking, but Quake 2 already implemented all the tricks that have been attributed to Quake 3 in this thread so far. In fact, I believe Quakeworld did it, too. That's not to say the networking code hasn't improved in Quake 3, but the improvements are probably in less obvious areas, such as latency compensation.

Quote:

well usually servers have equal up and down streams and the upstream of a client usually isn t limited


Huh? The typical case for normal internet connections is that upstream <= downstream. But I believe you meant downstream, anyway.

cu,
Prefect

Share this post


Link to post
Share on other sites

This topic is 4711 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this