One bit broke, another lost: data transfer task

Hello, Habr!

Picture from here

I propose the following problem as a training for the brain:

Two cars communicate with each other. Send each other digital data, naturally zeros and ones. Only the channel between them is not very: the bits are regularly distorted, then disappear altogether. Suppose our channel of 20 bits on average breaks one bit, the other one loses . And now we write the algorithm, the most optimally transmitting this data.

It is necessary to find a compromise between the overhead projector over the network payload, and the operation time of the transmitting and receiving machines. And if the distorted bits can be repaired using known or self-written correction algorithms, then for the bits that have been lost or not reached by the receiving machine, it will be necessary to organize a re-sending. But the request for re-sending from the host machine can also be lost ... Do you feel the challenge?
')
You say, serious guys from IEEE and related organizations have come up with everything for a long time, and you will be right. But when did it stop re-inventing, just for lulz? And to get out for a while from a comfort zone of reliable and simple sockets (Without looking at any RFC )? Moreover, we will do this in JavaScript, in the browser, without third-party libraries, it is still desirable that it fit into one screen:

Right here

I understand the prejudiced attitude of many towards JavaScript, but it’s only possible to embed it in a browser in 5 minutes and make it possible to edit and execute it. Simple basic syntax, write as if in pseudo code.

All code is executed locally. CodeMirror for code editor is connected. We write the contents of two functions that are periodically called on the transmitting (Sender \ Source) and receiving (Receiver \ Destination) machines.

We have a current context with as many as 5 methods:

 var runs = this.counter(); 

A count of how many times the base function was called. It helps to navigate in time, for example, for counting timeouts.

 var frame = this.getPayload(n); 

Available on the transmitting machine. Reads and returns the next n bits of the payload.

 this.write(frame); 

Pass a frame , which is an array of bits, to another machine. Passing through the transmission channel, the message may be distorted.

 var frame = this.read(n); 

Reads up to n bits from the incoming network buffer. If nothing, returns an empty array.

 this.acceptPayload(frame); 

Available on the host machine. Places frame in the resulting array.

If the main function returns true , then it wants to be called again in the future. Otherwise, the machine completes its execution. On the receiving machine, the integrity check of the received data is invoked, and the overhead head is calculated.

I added some source code examples:

• Tutorial - a slightly more detailed description of the capabilities of transmitting and receiving machines.
• No Corrections is the simplest algorithm that does not monitor the integrity of the transmitted data. Overhead is absent, but integrity leaves much to be desired.
• Naive 900% Overhead - I think that is clear from the name. Helmet without rushing one bat duplicated ten times. It works more or less stably (although the integrity is rarely broken), but the overhead of network load is 900%.
• + resend requests is an uncomplicated option proposed by haldagan , although it does not provide 100% integrity, but reduces the overhead projector to ~ 550% and tries to correct errors by requesting re-sending.

Between the first idea and the last point (first version) of this article, it’s still less than 12 hours, so don’t blame me if you missed it. Write, I will correct as quickly as possible.

UPD: here and my version arrived in time for a concise analysis:

• Author's proposal sends short messages with error detection codes, resublishes on request. Incorrectly corrupted data of about 3 bits to 10 ⁷