Error correction codes for faster and more reliable network communications

[ioquake]

Error correction codes for faster and more reliable network communications

[lrq3000]

Followup: this presentation is probably a lot more meaningful (main point is summarized in the slides "Game Packet Types"): https://github.com/catid/shorthair/blob/master/docs/ErasureCodesInSoftware.pdf

Currently, all actions are sent via "Ordered, Unreliable UDP" like player positions, which is advised by the author. But non-instant weapons such as rockets are very close to the "Bomb fired" example and could benefit from "Unordered, 99% Reliable UDP". And actually, I think that players positions could also benefit from this type of UDP packets, since essentially this could avoid jittering and false predictions, which is the main problem of network communications in real time games such as ioq3.

[lrq3000]

Re-followup: a generic implementation of Reed-Solomon is available in the Linux Kernel, and there's a userspace port here:

https://github.com/tierney/reed-solomon

It's in C, it's portable, well-tested and under GPLv2, so it should be all clear for use.

[NuclearMonster]

this sounds useful but possibly outside the scope of this project to implement. I would love to see a PR to discuss.

[lrq3000]

Thank you @timedoctor :) I don't have enough time right now, maybe I'll give it a shot someday, but using a third-party reed-solomon library like the one above, it would mainly just be a call to encode udp packets before sending, and decoding upon reception (+ adding error correction parameters in the configstring sent from server).

[lrq3000]

Here is a c-only library under GPL, so totally compatible with ioq3: http://rscode.sourceforge.net/

[lrq3000]

Help needed, if any UDP expert out there, we can make a patch very quickly!

I'm giving it a try, but I'm not sure I'll succeed because I have no idea how to work with network packets of ioq3, but I know reed-solomon error correction code. So I'll document here my advances so someone else can pickup from where I stop if I fail. Hopefully, all the reed-solomon ecc part will be covered, only will remain the network packets implementation ;)

Reading the documentation, the NetChan packets are constructed like this:

Current NetChan design: raw message → Huffman compression → encoding → [optional fragmentation] → netchan packet headers added → UDP send

Ideally, ecc encoding should be placed at the very end, after any other encoding and just before UDP send, in order to allow for maximum decoding:

Proposed NetChan+ECC design: raw message → Huffman compression → encoding → [optional fragmentation] → netchan packet headers added → ECC encoding → UDP send

Indeed, if you do ecc encoding before, then at packet reception, the decoding might fail before the ecc can kick in because of other decoding steps like huffman decompression for example! Whereas if ecc encoding is placed last, the ecc decoding will kick in first, being able to correct both the netchan packet headers, the per-client encoding and huffman decompression (and the raw message of course):

Proposed NetChan+ECC decoding: UDP receive → ECC decoding → netchan packet headers read → [optional defragmentation] → per-client decoding → Huffman decompression → raw message

In other words: ecc decoding protects every steps that are after (but not before).

About the technical implementation, here is the outline:

• The rscode library provides a great and short starting example to implement ecc correction with their library.
• Encoding step: just before UDP send, compute ecc symbols to append to the NetChan message.
• Decoding step: at UDP reception, split the message to recover the original message and separate the ecc symbols (normally it's always the same number of symbols). Then simply use the ecc symbols to correct the message. check_syndrome() != 0 can be used to check if the message needs correction, and if the correction is successful at the end (by trying to redecode the corrected message using the same ecc symbols, the syndromes should be equal to 0 if there is no error).

[lrq3000]

The ECC encoding should be implemented in Netchan_Transmit() and Netchan_TransmitNextFragment() I think, so that it would be totally agnostic to the content.

[lrq3000]

There is a limitation with the rscode library (and with any Reed-Solomon codec): it's limited to 256 bits. Since MAX_PACKETLEN is 1300, this means that we will have to compute the ecc symbols in chunks of 256-nb_of_ecc_symbols bits.

So now I think we should add a new function MSG_WriteDataWithECC and MSG_ReadDataWithECC which would write or read chunks of 28 bits data and then append 4 ecc symbols. This would implement the CD-ROM correction scheme (the first stage at least).

[lrq3000]

See PR #266 for the rest of the discussion and a proof of concept implementation. This should work, but is untested, as I'm sure I'm missing a few nitty gritty details about networking requirements here and there. If you know ioq3 networking and are interested, please help! :D