Один бит сломал, другой потерял: задачка по передаче данных

Здравствуй, Хабр!

Картинка отсюда

Предлагаю в качестве тренировки для мозга следующую задачку:

Общаются между собой две машины. Шлют друг другу цифровые данные, натурально нули и единицы. Только канал между ними не очень: биты регулярно то искажаются, то пропадают вовсе. Допустим, наш канал из 20 бит в среднем один бит ломает, другой теряет. А теперь пишем алгоритм, наиболее оптимально эти данные передающий.

Нужно найти компромисс между оверхедом над полезной нагрузкой сети, и временем работы передающей и принимающей машин. И если искаженные биты можно чинить, используя известные или самописные алгоритмы коррекции, то для потерянных, так и не дошедших до принимающей машины битов, нужно будет организовывать повторную отправку. А ведь запрос о повторной отправке от принимающей машины тоже может потеряться… Чувствуете челлендж?

Вы скажете, серьезные ребята из IEEE и смежных организаций уже всё давно придумали, и будете правы. Но когда это мешало переизобретать, just for lulz? И вылезти ненадолго из зоны комфорта надежных и простых сокетов (Не подсматривая какие-нибудь RFC)? Тем более, делать это будем на JavaScript, в браузере, без сторонних библиотек, еще желательно чтобы на один экран влезло:

Вот прямо тут

Понимаю предвзятое отношение многих к JavaScript, однако его единственного можно за 5 минут встроить в браузер и дать возможно редактировать и исполнять. Несложный базовый синтаксис, пишешь будто на псевдкоде.

Весь код исполняется локально. Подключен CodeMirror для редактора кода. Пишем содержимое двух функций, периодически вызываемых на передающей (Sender \ Source) и принимающей (Receiver \ Destination) машинах.

В нашем распоряжении контекст this, имеющий аж 5 методов:

var runs = this.counter();

Счетчик того, сколько раз была вызвана основая функция. Помогает ориентироваться во времени, для отсчета таймуатов например.

var frame = this.getPayload(n);

Доступен на передающей машине. Считывает и возвращает следующие n бит полезной нагрузки.

this.write(frame);

Передает frame, являющийся массивом бит, другой машине. Проходя по каналу передачи, сообщение, возможно, будет искажено.

var frame = this.read(n);

Считывает из входящего сетевого буфера до n бит. Если ничего нет, вернет пустой массив.

this.acceptPayload(frame);

Доступен на принимающей машине. Помещает frame в результирующий массив.

Если основная функция вернет true, значит она хочет быть вызвана еще раз в будущем. Иначе, машина завершает свое исполнение. На принимающей машине вызовется проверка целостности принятых данных, а также подсчитается оверхед.

Я добавил несколько примеров исходного кода:

• Tutorial — чуть более подробное описание возможностей передающих и принимающих машин.
• No Corrections — простейший алгоритм, не следящей за целостностью передаваемых данных. Оверхед отсутствует, но целостность оставляет желать лучшего.
• Naive 900% Overhead — думаю, понятно из названия. Шлем не торопясь по одному биту, продублированному десять раз. Работает более-менее стабильно (хотя изредка целостность нарушалась), но оверхед по нагрузке сети 900%.
• + resend requests — несложный вариант, предложенный haldagan, хоть и не обеспечивающий 100% целостности, но уменьшающий оверхед до ~550% и пытающийся корректировать ошибки запросом о переотправке.

Между первой идеей и последней точкой (первой версии) этой статьи пока что еще прошло меньше 12 часов, так что не обессудьте, если что пропустил. Пишите, поправлю как можно оперативней.

UPD: вот и мой вариант подоспел к шапочному разбору:

• Author's proposal отправляет короткие сообщения с кодами обнаружения ошибок, переподает по запросу. Неисправимо искаженных данных примерно 3 бит на 10⁷