Средства и методы разработки

Фонтанные коды. Хочется передать некоторый объём текстовых данных через IP-сеть по UDP-протоколу. Объём данных достаточно большой, десятки килобайт. Этого достаточно, чтобы практически заметить такие эффекты, как пропадание отдельных пакетов или перестановку пакетов местами. Какие возможны варианты? Очевидно: 1) использовать протокол с квитированием, наподобии X-modem, например, TFTP; 2) дополнять данные контрольным кодом и перезапрашивать целиком в случае несовпадения (проще, чем протокол с квитированием); 3) использовать какую-либо форму "фонтанного кода" (https://en.wikiped …ki/Luby_transform_code) для передачи данных и надеяться, что в большинстве случаев возможно переупорядочивание и восстановление потерянных пакетов на принимающей стороне (в крайнем случае возможен перезапрос, как в пункте 2). Понятно, что вариант 1 в общем случае -- лучший. Но в силу ряда причин (например, в промежутке есть некоторое уже существующее ПО которое уже умеет только запрашивать по команде и сохранять вывод) хочется рассмотреть вариант 3. Допустим, что число избыточных блоков будет до 50% от исходного, т.е. объём передаваемых данных увеличивается всего в 1.5 раза. Допустим так же, что исходные данные будут побиты на блоки объёмом в ~512 байт, далее согласно алгоритму будут отправлены блоки проксоренные с рядом других блоков и снабжённые заголовком, в котором указываются списки блоков принявшие участие в проксоривании. И каждый такой блок отправится в отдельном пакете. Очевидно, кстати, что даже при 0% избыточных блоков такой алгоритм уже защищает от перестановки блоков местами. Вопрос, какой способ проксоривания, каких блоков с какими и в каких количествах, наиболее оптимален. Оригинальный алгоритм предусматривает, что для каждого отправляемого блока выбирается как случайное число исходных проксориваемых блоков, так и случайные их номера. Со случайностями оно, конечно, хорошо работает на больших числах блоков, но когда избыточных блоков немного то запросто может дать результат очень далёкий от оптимального. Очевидны крайние случаи: если избыточность 0%, то проксоривается 1 блок (т.е. не ксорится ничего). Если избыточность в 1 блок, то оптимальным вариантом является добавить блок проксоривающий все прочие блоки (тогда он может заместить любой один потерянный блок). Можно ли как-то продолжить эти рассуждения? Например, при избыточности в два блока, нет смысла во втором точно таком же проверочном блоке, он должен чем-то отличаться. Например, если он будет ксорить только половину входных блоков, то сможет заместить любой из этих блоков. И тогда можно терять уже два блока, один из которых не должен входит в число проксоренных для второго избыточного блока. Можно продолжить далее и получить большее число избыточных блоков, первый из которых ксорит все N входных блоков, второй первую половину, третий первую и третью четверть... последний половину блоков через один. Например для восьми входных блоков можно получить:

      блок 0:  +   .   .   .   .   .   .   .
      блок 1:  .   +   .   .   .   .   .   .
      блок 2:  .   .   +   .   .   .   .   .
      блок 3:  .   .   .   +   .   .   .   .
      блок 4:  .   .   .   .   +   .   .   .
      блок 5:  .   .   .   .   .   +   .   .
      блок 6:  .   .   .   .   .   .   +   .
      блок 7:  .   .   .   .   .   .   .   +
пров. блок 1:  x   x   x   x   x   x   x   x
пров. блок 2:  x   x   x   x   .   .   .   .
пров. блок 3:  x   x   .   .   x   x   .   .
пров. блок 4:  x   .   x   .   x   .   x   .

Мне начинает казаться, это какой-то код Рида-Соломона... Для других размеров получается log2(N)+1 проверочных (избыточных) блоков для N входных блоков. В случае восьми изначальных блоков, добавляется 4 проверочных блока, в случае 16-и -- 5 проверочных блоков и т.п. В случае 8-ми изначальных блоков и 4-х проверочных можно потерять до 4-х любых блоков и информация может быть восстановлена. Но насколько оптимален такой способ формирования избыточных блоков? И самое главное, непонятно как дальше увеличивать избыточных блоков, хотелось бы больше, чем log2(N), что-то прямо-пропорциональное N (но не сильно большее). Исходя из того, что для каждого входного блока есть небольшая вероятность его пропажи. И потом неудобно, как-то уравнения эти решать, что понять чего с чем ксорить для восстановления блоков. По-моему я что-то упускаю, может кто подскажет. Уж очень матрица, практически буквально, напоминает такую же матрицу Хэмминга (только там минимизируется расстояние) или BCH, или коды Рида-Соломона. Но хотелось бы какой-то простейший способ. Есть современные сложные алгоритмы описанные в RFC например, но их проблема в том, что они громоздкие и сложные.