Error correction codes for faster and more reliable network communications

[lrq3000]

This is an enhancement proposal.

Currently the ioq3 engine uses replication of UDP packets to ensure that the communication is reliable.

However, a more reliable, faster way and using less bandwidth than replication would be to use error correcting codes, with the only cost being a bit more CPU consumption on the server and on the client sides.

For example, this C++ library could be a good starting point (it's exactly about using error correcting codes for reliable UDP communications, but it's in CPP...): https://github.com/catid/shorthair

There are a lot of other C libraries implementing Reed-Solomon, so that reinventing the wheel should not be necessary here. But shorthair is a good example for the actual implementation for UDP packets management, even if another library is used in the end.

As stated by the shorthair project:

Advantages of using erasure codes in online games:

• 50% faster delivery over UDP than over TCP
• 50% less bandwidth used than naive redundancy
• 50% better recovery rate than parity redundancy

Also, this library shows how to compute the ecc rate to achieve the target loss rate, so that a server configurable variable could be advantageously added for servers admins to setup the loss rate they are expecting. This rate would then be sent to the clients inside the connection string along with other variables.

I do not see ECC as a replacement for the current replication scheme of UDP packet, but it could be a complement (because anyway if an UDP packet was already received, it will be discarded). This would probably allow for smoother gameplay across long distances such as EU players on a US server.

[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