cbloom rants 05-20-13 - Thoughts on Data Compression for MMOs
cbloom rants 08-08-13 - Oodle Static LZP for MMO network compression
cbloom rants 08-19-13 - Sketch of multi-Huffman Encoder
What I'm doing for UDP packet is static model compression. That is, you pre-train some model based on a capture of typical network data. That model is then const and can be just written out to a file for use in your game. At runtime, you read the model from disk, then it is const and shared by all network channels. This is particularly desirable for large scale servers because there is no per-channel overhead, either in channel startup time or memory use.
(ASIDE : Note that there is an alternative for UDP, which is to build up a consistent history between the encoder and decoder by having the decoder send back "acks", and then making sure the encoder uses only ack'ed packets as history, etc. etc. An alternative is to have the encoder mark packets with a description of the history used to encode them, and then when the decoder gets them if it doesn't have the necessary history it drops the packet and requests it be resent or something. I consider these a very bad idea and Oodle won't do them; I'm only looking at UDP compression that uses no transmission history.)
Call for test data! I currently only have a large network capture from one game, which obviously skews my results. If you make a networked game and can provide real-world sample data, please contact me.
Now for a mess of numbers comparing the options.
UDP compression of packets (packet_test.bin)
order-0 static huffman : 371.1 -> 234.5 average
(model takes 4k bytes)
order-0 static multi-huffman (32 huffs) : 371.1 -> 209.1 average
(model takes 128k bytes)
order-2 static arithmetic model : 371.0 -> 171.1 average
(model takes 549444 bytes)
OodleStaticLZP for UDP : 371.0 -> 93.4 average
(model takes 13068456 bytes)
In all cases there is no per-channel memory use.
OodleStaticLZP is the recommended solution.
For comparison, the TCP compressors get :
LZB16 models take : 131072 bytes per channel
LZB16 [sw16|ht14] : 371.0 -> 122.6 average
LZNib models take : 1572864 bytes per channel
LZnib [sw19|ht18] : 371.0 -> 90.8 average
LZP models take : 104584 bytes per channel, 12582944 bytes shared
LZP [8|19] : 371.0 -> 76.7 average
zlib uses around 400k per channel
zlib -z3 : 371.0 -> 121.8 average
zlib -z6 : 371.0 -> 111.8 average
For MMO type scenarios (large number of connections, bandwidth is important), LZP is a huge win. It gets great compression with low per-channel
memory use. The other compelling use case is LZNib when you are sending large packets (so per-byte speed is important) and have few connections
(so per-channel memory use is not important); the advantage of LZNib is that it's quite fast to encode (faster than zlib-3 for example) and gets
pretty good compression.
To wrap up, logging the variation of compression under some options.
LZPUDP can use whatever size of static dictionary you want. More dictionary = more compression.
LZPUDP [dic mb | hashtable log2]
LZPUDP [4|18] : 595654217 -> 165589750 = 3.597:1
1605378 packets; 371.0 -> 103.1 average
LZPUDP [8|19] : 595654217 -> 154353229 = 3.859:1
1605378 packets; 371.0 -> 96.1 average
LZPUDP [16|20] : 595654217 -> 139562083 = 4.268:1
1605378 packets; 371.0 -> 86.9 average
LZPUDP [32|21] : 595654217 -> 113670899 = 5.240:1
1605378 packets; 371.0 -> 70.8 average
And MultiHuffman can of course use any number of huffmans.
MultiHuffman [number of huffs | number of random trials]
MultiHuffman [1|8] : 66187074 -> 41830922 = 1.582:1
178376 packets; 371.1 -> 234.5 average, H = 5.056
MultiHuffman [2|8] : 66187074 -> 39869575 = 1.660:1
178376 packets; 371.1 -> 223.5 average, H = 4.819
MultiHuffman [4|8] : 66187074 -> 38570016 = 1.716:1
178376 packets; 371.1 -> 216.2 average, H = 4.662
MultiHuffman [8|8] : 66187074 -> 38190760 = 1.733:1
178376 packets; 371.1 -> 214.1 average, H = 4.616
MultiHuffman [16|8] : 66187074 -> 37617159 = 1.759:1
178376 packets; 371.1 -> 210.9 average, H = 4.547
MultiHuffman [32|8] : 66187074 -> 37293713 = 1.775:1
178376 packets; 371.1 -> 209.1 average, H = 4.508
On the test data that I have, the packets are pretty homogenous, so more huffmans is not a huge win.
If you had something like N very different types of packets, you would expect to see big wins as you go up to N
and then pretty flat after that.
Public note to self : it would amuse me to try ACB for UDP compression. ACB with dynamic dictionaries is not Pareto because it's just too slow to update that data structure. But with a static precomputed suffix sort, and optionally dynamic per-channel coding state, it might be good. It would be slower & higher memory use than LZP, but more compression.
I wonder what you do at the higher level to keep it from becoming too complicated.
ReplyDeleteThat is to say, you probably try to pack source data that is like 4x as long as whatever you think your MTU is, and almost always it ends up being the right size. But if it doesn't... I guess you either do a fallback re-pack of two separate packets or else make your protocol have extended sockets.
I am kinda interested that people are still using UDP. I thought there were just too many problems with NATs and whatever these days and people just gave up and use TCP? Is that not actually true?
Actually, you have to use UDP if you do peer-to-peer because you can't do NAT traversal/punchthrough with TCP (well, some crazy researchers have tried, but it's not very reliable). There are still a lot of p2p apps, including tons of games obviously, but also most video/audio chat apps (that's where libjingle comes from), etc.
ReplyDelete" I am kinda interested that people are still using UDP. I thought there were just too many problems with NATs and whatever these days and people just gave up and use TCP? Is that not actually true? "
ReplyDeleteI had also been under the impression that games were moving to TCP these days, but after the first post in this series (see the comments) I did an informal survey of the game devs I could contact, and it seems the majority are still UDP.
(the big exception is the most important MMO's which are TCP)
Lots of people that I talked to who are using UDP told me they are "considering TCP for future products" because of the obvious advantages, but are hesitant to make the jump.
Decent data gathering :
ReplyDeletehttp://www.iis.sinica.edu.tw/~swc/pub/tcp_in_games.html