Востановить небольшое количество потерянных пакетов

Есть некое устройство, которое собирает информацию от датчиков и отправляет в сеть.
Поскольку информации немного, то хочется объединять по несколько замеров и отправлять одним пакетом, чтобы уменьшить нагрузку на сеть.
Но очень не желательно чтобы пакет потерялся, хоть вероятность такого печального события порядка 1%. Делать квитирование крайне не хочется.

А хочется добавить к результатам замеров какой-то код(10-20% от полезной информаци), чтобы в случае потери пакета по кодам из следующих пакетов можно было его полностью востановить. Ну а вопрос собственно в том, как такое организовать?!

 

Если tcp пакет не дошёл, значит связь оборвалась. Единственное что можно сделать, это возобновить передачу после восстановления, всё. ^)

 

Booster не, там есть всякие хитрые кодирования, позволяющие восстанавливать потеряную информацию. Black_mirror глянь в гугле - полюбому такие алгоритмы кодирования есть, только я уже всё это забыл.

 

Зачем тут хитрые (помехоустойчивые) кодирования, если TCP гарантирует доставку пакета.
Если на канальном уровне пакет потерялся, не будет подтверждения от принимающей стороны и пакет шлётся отправителем повторно.
Это всё происходит абсолютно прозрачно для более высоких уровней.

 

cppasm

кто сказал, что устройство юзает TCP и вообще может себе это позволить?

 

А кто сказал что нет?
Пусть автор этот момент прояснит, там видно будет.

 

На udp тоже можно сделать гарантированную доставку. Отправлять порциями и не надо огород городить.

 

Используемый протокол - UDP, только пакеты отправляются на multicast-адрес и получателей может быть несколько, по этим причинам TCP и квитирование на мой взгляд пролетают. Памяти в устройстве не особо много, поэтому коды Рида-Соломона пролететь могут тоже. Вообще задачу можно рассматривать как востановление в некотором слове(с присоединённым кодом) нескольких символов, причём позиции стёртых символов известны(потому что все пакеты можно пронумеровать).

 

cppasm
TCP не гарантирует доставку.

Если не считать провисания в несколько секунд абсолютно прозрачно.

Black_mirror
Дублируй в каждом следующим сообщении предыдущий.
т.е
_1 12 23 34 45

 

циклический код гарантирует исправление одной ошибки (те ошибки в одном бите передаваемого Nбит слова) и элементарно кодируется/декодируется

 

Pavia
Слишком неэффективно.

qqwe
Одну ошибку можно исправить добавив всего лишь бит чётности(хотя это тоже можно считать циклическим кодом).

Мне вообще кажется, что добавив k-символов циклического кода можно будет востановить k потерянных символов, если полином порождает последовательность длиной 2^k-1, потому что позиции ошибок нам известны, и только одна их компинация даст нужный остаток при делении.

 

Не обязательно делать обязательное квитирование. Можно высылать пакеты и просто слушать. Если придет запрос повторной передачи (пакет пришел битым) - передать битый пакет заново.

Вообще все зависит от конкретики: размер передаваемых данных, ожидаемый уровень сбоев, вид сбоев (битый бит/потеря 1..N байт и так далее).

Также бывают подстраивающиеся под уровень сбоев протоколы (если качество линии плавает).

 

PSR1257
Память устройства не позволит организовать буфер более чем на 1 секунду работы, за это время устройство может не успеть получить запрос на повторную передачу, поскольку сервер, принимающий данные от устройств, работает под виндой и как он написан это еще вопрос.

Пакеты битыми не приходят, они либо приходят целыми, либо не приходят вообще.

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

 

Black_mirror

Смахивает на одно из этих сферических у-в типа COM->IP

Не ф полне понятно что там тварицца на канальном уровне. Если это COM-порт, то передача подразумевает всякие там стоп-биты (контроль внутри линии).

А где происходит потеря пакетов? Может сервер тупо пропускает их а у-во на самом деле исправно все передает?

Компрессия пакетов и дублирование передачи (как предлагали выше)?

 

8-разрядные коды Рида Соломона много памяти не отожрут.
Таблицы логарифмов и антилогарифмов займут вместе 512 байт.

Далее на выбор.
Матричный код потребует скажем матрицу 100x10 т.e. кило рама, сам же исполняемый код пару-другую строк. Кубическое декодирование возможно очевидным методом гаусса, парадоксальное квадратичное декодирование тоже возможно, но требует специального изучения.

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

 

Зачем писать если не знаешь?
Хоть бы ту же Википедию почитал: http://ru.wikipedia.org/wiki/TCP

Бит чётности позволит определить ошибку, но не исправить.
К примеру ты получил 8 бит и бит чётности, увидел что есть ошибка.
Но ты не знаешь в каком именно бите - исправить не можешь.

 

Я смотрю тут сплошные знатоки исправляющих кодов собрались =)
Я (увы и ах) в вопросе не секу ни разу, но, подумав, поимел такую идею. Если мы хотим увеличить пакет в k раз (+20% -- это значит k==1.2), то задаёмся константой N=1/(1-k).
Каждый i-тый пакет разобьём на равные части p[0], p[1], ..., p[N-1] и допишем код, который считается так

Код (Text):

1. p[i].code = 0;
2. for (k = 0; k < N; k ++)
3.     p[i].code ^= p[i-k-1][k];

По этому коду вполне можно восстановить.
Пруф:

Код (Text):

1. #include <stdio.h>
2. #include <unistd.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include <time.h>
6. #include <fcntl.h>
7.  
8. #define N  5
9.  
10. struct packet
11. {
12.     int count;
13.     char data[N];
14.     char code;
15. };
16.  
17. int read_packet (struct packet *p)
18. {
19.     static int pcount = 0;
20.     int res;
21.     static char buf[N*N];
22.     static char *ptr = buf;
23.     do {
24.         res = read (STDIN_FILENO, p->data, sizeof (p->data));
25.     } while (res < 4 && res > 0);
26.     if (res < 4) {
27.         fprintf (stderr, "eof reached\n");
28.         return 0;
29.     }
30.     if (pcount >= N) {
31.         p->code = 0;
32.         fprintf (stderr, "code = 0");
33.         for (int i = 0; i < N; i ++) {
34.             fprintf (stderr, "^`%c'", buf[N*(N-i-1) + i]);
35.             p->code ^= buf[N*(N-i-1) + i];
36.         }
37.         fprintf (stderr, "\n");
38.         memmove (buf, buf + sizeof (p->data), (N-1)*sizeof (p->data));
39.         ptr -= N;
40.     }
41.     memcpy (ptr, p->data, sizeof (p->data));
42.     p->count = pcount ++;
43.     ptr += N;
44.     if (pcount % (2 * N) == N + 2) {
45.         fprintf (stderr, "oops. one packet lost ;)\n");
46.         memcpy (p->data, "66666", sizeof (p->data));
47.         return -1;
48.     }
49.     return 1;
50. }
51.  
52.  
53. int main ()
54. {
55.     int i;
56.     struct packet p;
57.     int res;
58.     char buf[N*(N+1)];
59.     int rip = 0;    /* recover in progress */
60.  
61.     for (i = 0; i <= N; i ++) {
62.         if (read_packet (&p) <= 0) {
63.             fprintf (stderr, "Hmm... seems like a transfer error."
64.                 " We are not prepared yet. :(\n");
65.             exit (1);
66.         }
67.         write (STDOUT_FILENO, p.data, sizeof (p.data));
68.         memcpy (buf + i*(sizeof (p.data)), p.data, sizeof (p.data));
69.     }
70.     while ((res = read_packet (&p))) {
71.         memmove (buf, buf+sizeof (p.data), sizeof (p.data)*N);
72.         memcpy (buf+sizeof(p.data)*N, p.data, sizeof(p.data));
73.         if (res < 0) {
74.             if (rip) {
75.                 fprintf (stderr, "OMG! second packet lost"
76.                     " while we are recovering!!\n");
77.                 exit (1);
78.             }
79.             rip = 1;
80.             continue;
81.         } else if (!rip) {
82.             write (STDOUT_FILENO, p.data, sizeof (p.data));
83.             continue;
84.         }
85.         i = (N - rip) * sizeof (p.data) + rip - 1;
86.         buf[i] = p.code;
87.         int k = (N - 1) * sizeof (p.data);
88.         fprintf (stderr, "buf=%.*s\n", N*(N+1), buf);
89.         fprintf (stderr, "recovering char as: 0x%hhx", p.code);
90.         for (int j = 0; j < N; j ++, k -= N - 1)
91.             if (i != k) {
92.                 buf[i] ^= buf[k];
93.                 fprintf (stderr, "^`%c'", buf[k]);
94.             }
95.         fprintf (stderr, "\n");
96.         if (rip ++ == N) {
97.             rip = 0;
98.             write (STDOUT_FILENO, buf, sizeof (buf));
99.         }
100.     }
101. }

Работает как cat, но:
1. надо чтобы количество байт входного потока делилось бы на N
2. флудит в stderr

Может не самая удачная идея, но поскольку никто не в состоянии предложить чего-либо лучше...

ps. Я вот всё думаю: а как бы от буфера под уже принятые пакеты размером N*(N+1) байт избавиться. Есть мысли, но они какие-то сильно неопределённые и абстрактные. Кстати если избавиться, то можно будет без уродских memmove и memcpy обойтись, причём не высчитывая индексы по модулю.

 

PSR1257
Потеря происходит в ethernet-маршрутизаторе, вернее даже не совсем потеря, пакет всё же приходит, но на ~500 позже чем должен, и такое случается регулярно примерно с 3 пакетами из 500. Компрессия пакетов это слишком навороченно, к тому же от некоторых датчиков данные более на шум похожи, более чем в 2 раза их вряд ли пожать можно.

persicum
Спасибо, это вселяет оптимизм, правда пока я вроде нашёл решение проще, но если не сработает, буду с кодами Рида-соломона разбираться.

cppasm
Здесь особенность в том, что пакеты только теряются, но не искажаются, то есть какие биты искажены мы знаем, поэтому даже простая чётность позволяет исправить ошибку.

r90
Это как раз и есть метод с добавлением одного бита чётности)

Вот пример как можно исправлять ошибки при помощи CRC. Пусть каждое сообщение состоит их символов abcdefg. Первые 4 символа инфомационные, а последние три - расчитанный CRC. Сами сообщения расположенны вертикально, но для расчётов берётся по 1 биту из 4х последовательно идущих собщений, и CRC кладётся в 3 следующих сообщения, распоожение бит указано большими буквами:

Код (Text):

1. aAaaaaaaa
2. bbBbbbbbb
3. cccCccccc
4. ddddDdddd
5. eeeeeEeee
6. ffffffFff
7. gggggggGg

Далее берём полином p=x^3+x+1, или 1011 ввиде строки коэффициентов. Остатки от деления x^n на данный полином будут равны:
x^6 mod p = 101
x^5 mod p = 111
x^4 mod p = 110
x^3 mod p = 011
x^2 mod p = 100
x^1 mod p = 010
x^0 mod p = 001
Первые 4 будут соответствовать информационным битам, а последние 3 вычисленному CRC.

Для строки 1001, CRC=1*101 + 0*111 + 0*110 + 1*011 = 110. то есть ABCDEFG=1001110. Допустим у нас потерялись пакеты содержащие C,D и G. То есть мы имеем строку 10CD11G. Иными словами у нас есть система уравнений C*110+D*011+G*001=1*101+0*111+1*100+1*010=011 с термя неизвестными. Матрица коэффициентов у нас имеет вид:
110
011
001
Правая обратная к ней будет:
111
011
001
Умножая 011 на обратную матрицу получим 011, то есть CDG=011. Как эти рассуждения на пальцах перевести в математический вид я не знаю, но мне кажется что метод будет работать, то есть если добавить CRC содержащий k бит, то можно будет востановить k потерянных пакетов на каждые n+k, при условии длина периода не менее n+k, где n-количество пакетов из которых мы берём информационные биты.

 

Что-то меня с примером переглючило, то ли матрицу обратную не правильно нашёл, то ли этот метод в принципе не работает, в общем нужно с начала программу написать, а потом смотреть что получается.

 

Хотя вроде нашёл где переглючило, я 011 на правую обратную не правильно умножил, должно получиться CDG=010.