тройка семёрка ace

какие ограничения?

зы. троируй каждый пакет после отправки по 7 пакетов то есть

вместо

abcdefghijklmnopqrstu

посылай

abcdefgabcdefgabcdefghijklmnhijklmnhijklmnopqrstuopqrstuopqrstu

Буду применять в ip сетях

TCP/IP гарантирует целостную доставку в правильном порядке. А что ты собрался изобретать — не понятно.

Загляни для начала сюда и сюда.

sequence number

beastie

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

Конечно спасибо за столь высокий уровень развитой телепатии. Но вопрос не про TCP, а про пакеты в отдельности. И кстати про TCP для справки: при потерях - 10%, скорость на TCP падает где-то в 10 раз.

sequence number

А ты думаешь как я понимаю что пакет потерялся? При помощи магии?

А серебряной пули и не бывает. Ты уж определись, что тебе важнее целостная доставка или скорость.

Проясни пожалуйста свой хитрый план. Ты переизобретаешь TCP в порыве NIH-синдрома или просто интересуешься?

А ты думаешь как я понимаю что пакет потерялся? При помощи магии?

Ну да. Магия называется буфер приема.

На всякий случай - у тебя кроме потерь пакетов может быть и их дублирование

beastie

Загляни для начала сюда и сюда.

Это все я смотрел, алгоритмов море. Но вот не все они подходят в моём случае. Я сейчас просматриваю их, но пока нашел только алгоритмы которые полезны когда данные представлены потоком битов. Тот же Хэмминг мне не подходит.

Да, магии и CRC:

• Packet #1 arrives, expect Packet #1 ... ok
• Packet #2 arrives, expect Packet #2 ... ok
• Packet #4 arrives, expect Packet #3 ... ups, something is missing

На всякий случай - у тебя кроме потерь пакетов может быть и их дублирование

от дупов, как раз предложенный тобою seq_num, а от повреждения контрольная сумма.

Пакетные данные и не подходит Хемминг, звучит занятно.
Задачу ты размытую написал, что нужно в итоге? Самовостановление? Гарантированная доставка данных? Тупая проверка целостности? Это разные задачи и разные подходы

Ты переизобретаешь TCP в порыве NIH-синдрома или просто интересуешься?

На тему работы tcp в условиях больших потерь (Статью можешь не читать, просто посмотри на график как падает скорость: http://www.extremetech.com/computing/138424-increasing-wireless-network-speed-by-1000-by-replacing-packets-with-algebra
Можешь сабстрогироваться от tcp меня интересуют просто пакеты и потери.

Задачу ты размытую написал, что нужно в итоге? Самовостановление? Гарантированная доставка данных? Тупая проверка целостности? Это разные задачи и разные подходы

В общем, мне нужно, восстановление пакетов в условиях потерь не более 5%.

Коды Хемминга, если я ничего не путаю. Почитай теорию - там много всего интересного.

Обычно на первом курсе дискретки проходят.

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

Тот же Хэмминг мне не подходит

Если вам не лень будет написать обоснование, почему Хемминг вам не подходит, тогда попробую конкретно под вашу задачу что-нибудь подсказать.

Пакетные данные и не подходит Хемминг, звучит занятно.

Судя из описания алгоритма, он нацелен на восстановление отдельных битов в последовательности. Чтобы вставить контрольные биты процессору нужно будет сделать очень много операций. В том же предложенном мною алгоритме будет только суммирование которое является очень оптимизированной операцией.

trex6

почему Хемминг вам не подходит,

Я пока не понял как его применить так чтобы он работал быстрее того что я предложил в теме.

Также я хочу услышать комментарии к предложенному мною алгоритму.

qulinxao

какие ограничения?

зы. троируй каждый пакет после отправки по 7 пакетов то есть

Потери не так велики чтобы отправлять в 3 раза больше данных. Условия потерь не более 5%.

Мну в курсе. Просто, как практик, указываю на готоыве решение и пытаюсь разобраться в поставленных задачах.

ТС'у: глянь на спутниковую коммуникацию — там как раз узкий канал и высокая латенция, когда проще просчитать, а не переслать, потерянный пакет. И соответственно на алгоритмах коррекции и экономных протоколах там уже не одну челюсть об гранит науки съели.

от повреждения контрольная сумма

Ты собираешься изобретать свой протокол прямо поверх ip? В udp уже есть checksums

от дупов, как раз предложенный тобою seq_num

От потерь. Тебе нужно будет просить эндпойнт перепослать данные которые потерялись

Тот же Хэмминг мне не подходит.

всем значит подходит, а вам нет ? :-) IRL битые ip-пакеты в основной массе доходят до получателя а не выкидываются на промежуточных роутерах.

отвлекись от сетей - посмотри как разносятся данные в raid массивах; в принципе похрен же куда класть избыточные данные - на разные диски или в разные пакеты; ну получишь 1 лишний пакет на каждые 5 - ничего страшного..

сами по себе пакеты придётся делать поменьше (чем он меньше тем выше шанс проскочить); перед отправкой возможно перемешивать (в реальных каналах порча данных не является независимым событием - вероятность того что следующий за битым пакетом тоже поломается достаточно высока)

Вы плохо осмыслили алгоритм, какое нафик восстановление контрольных бит, в пакет закладывается избыточность и если пакет подлежит восстановлению, то восстанавливает данные и не важно где была ошибка в битах данных или в контрольных.
Советую начать экскурс отсюда - http://ru.wikipedia.org/wiki/Обнаружение_и_исправление_ошибок
Заодно определитесь какой метод восстановления вам подходит, хемминг с какого-то момента становится слишком накладным. А методов восстановления целая куча

дополнительный пакет который содержит сумму

http://ru.wikipedia.org/wiki/Код_Рида_—_Соломона

Вы плохо осмыслили алгоритм

Вы похоже не можете битовый алгоритм от блочного отличить.

i-rinat

дополнительный пакет который содержит сумму

http://ru.wikipedia.org/wiki/Код_Рида_—_Соломона

Похоже то что надо. Уже изучаю примеры.

Я сейчас плакать начну. Расскажи мне где ты там увидел битовый. А еще расскажи нам гуру, уж не из битов ли состоят блоки. А так же нам всем интересно, когда тебе Хемминг запретил использовать его алгоритм на n количестве бит в последовательности. Ты или шапку исправь или перестань шлангом прикидываться, сам задачу составил в пакетах данных.

и sha512 туда впилить, ведь могут быть коллизии хешей...

Конечно спасибо за столь высокий уровень развитой телепатии. Но вопрос не про TCP, а про пакеты в отдельности.

При двусторонней связи sequence number-а и перезапроса достаточно. Как вариант можно после каждых N пакета посылать xor этих N пакетов. Это легко сделать, и оверхед всего лишь 100/N процентов. Зато в случае потери одного из пакетов его можно будет восстановить по остальным пакетам и пакету-сумме. sequence number-ы при этом всё равно нужны, чтобы сдетектить потерю.

И кстати про TCP для справки: при потерях - 10%, скорость на TCP падает где-то в 10 раз.

Зависит от выбранного congestion-модуля в настройках ядра. Например Tweaking Linux TCP Stack for Lossy Wireless Networks

http://ru.wikipedia.org/wiki/Код_Рида_—_Соломона

Похоже то что надо. Уже изучаю примеры.

Имхо, это оверкилл для такой задачи, обычного xor-пакета достаточно.

уверен существует АДАПТИВНЫЙ протокол который варьирует избыточность пакетов ( случайность повтора некоторого(глубина тут тоже варьируется) уже отправленного пакета) по мере улучшения/ухудшения среды передачи ( ну очевидно должна быть петля для узнавания отправителем какое качество среды)

для 5% попробуй ( палец пол потолок) повторять каждый(случайный один из ) 13 пакет - насколько снизится вероятность не прихождения некоторого пакета , что будет стоит принимающему отдельного запроса на пакет или как оно там устроенно.

anonymous

При двусторонней связи sequence number-а и перезапроса достаточно. Как вариант можно после каждых N пакета посылать xor этих N пакетов. Это легко сделать, и оверхед всего лишь 100/N процентов. Зато в случае потери одного из пакетов его можно будет восстановить по остальным пакетам и пакету-сумме. sequence number-ы при этом всё равно нужны, чтобы сдетектить потерю.

Да, думаю xor самое оно.

anonymous

Зависит от выбранного congestion-модуля в настройках ядра.

Былаб моя воля, я б уже multipath tcp во всем интернете внедрил.

Какой сейчас самый быстрый и прогрессивный метод избыточного кодирования

коды Рида-Соломона.

кто-нибудь знает название описанного мною алгоритма?

тоже код Рида-Соломона над полем Галуа 2. Самый тривиальный случай, расстояние между кодами равно 2, число найденных и исправленных ошибок равно 1 и 1. Число бит в исходном коде любое r, число дополнительных бит 1.

все RS коды работают точно также, только поле большего порядка(в CD-ROM например GF(256)).

это мажоритарный метод. Устарел лет 50 назад.

Как вариант можно после каждых N пакета посылать xor этих N пакетов. Это легко сделать, и оверхед всего лишь 100/N процентов.

Да, думаю xor самое оно.

это тупик на самом деле :-) при ошибке или потере xor-пакета бракуется вся проверяемая группа, то есть надёжность выше не становится а избыточность вводится. Изменяется только «скважность» потерь - в вашем 5-ти процентном случае будет браковаться не 1/20 пакетов в потоке, а 1/20 групп из N пакетов, что вообще говоря один хрен :-)

Я пока не понял как его применить так чтобы он работал быстрее того что я предложил в теме.

он работает медленнее, т.к. это тот же метод, только применённый дважды. Потому он позволяет исправить не одну ошибку, а две(обычно). Или даже больше, если повезёт. Исправить можно любые ошибки, которые не лежат на одной вертикали и горизонтали. Дополнительных битов тоже больше. Число их равно сумме вертикалей и горизонталей. Для 64и битов нужно 8+8 дополнительных бит. Ещё этот код может не только исправлять дефектные биты, но И искать их. (простая сумма из первого поста позволяет исправить ИЛИ найти битый бит)

Былаб моя воля, я б уже multipath tcp во всем интернете внедрил.

внедри у себя sctp :-) раз уж такие шаткие каналы

в вашем 5-ти процентном случае будет браковаться не 1/20 пакетов в потоке, а 1/20 групп из N пакетов, что вообще говоря один хрен :-)

Какая глупость. Зачем отбраковывать всю группу? Потери детектятся по sequence number-ам, и отбраковываются только те пакеты, которые вообще не пришли. Просто если в группе потерялся только один пакет, то он будет восстановлен. Если потерялось 2+ пакета, то их не восстановить, но зачем выкидывать те, что уже пришли?

Былаб моя воля, я б уже multipath tcp во всем интернете внедрил.

На весь интернет повлиять не получится, но подгрузка другого congestion-модуля на своей машине мне в своё время очень помогала.

это тупик на самом деле :-) при ошибке или потере xor-пакета бракуется вся проверяемая группа

Нет. У него ещё есть CRC. Т.е. если есть ошибка _только_ в xor пакете, то все CRC хорошие, и xor пакет не нужен.

Проблема ТСа в том, что обычно пакеты бьются группами, скажем по 2шт подряд. Если пакетов 20+1, то вероятность поймать такую группу равна 95%, и вот эта двойная ошибка похерит всю группу.

IRL используют перемежение, т.е. передают пакеты не подряд, а 0,21,42,63,84, и т.д. Потому соседняя ошибка оказывается гарантированна размазана по разным группам (если она не длиннее одной группы конечно). Но это сильно увеличивает латентность, и годно если только нам нужно передать поток не менее чем из N² пакетов, где N длинна группы.

морально да. как эвристика и решение стиля 80% сейчас 20% после захвата поляны ( да и то если) вполне норм.

вполне норм.

ну учитывая свою исключительную тупизну(реализуется чуть-ли не на механических реле), то да, для многих применений потянет. Да и чипы тоже копейки стоят.

Но проблема этой ерунды в том, что того же эффекта можно добиться намного дешевле. Очевидная оптимизация: CRC каждого блока. И блоков не 3, а 2. Это ещё и увеличивает скорость вдвое (можно читать сразу два блока, например сразу два HDD, если ошибок почти нет. Если ошибка изредка и будет, нужно просто брать тот блок, где её нет). Это я «придумал» RAID-1.

Если потерялось 2+ пакета, то их не восстановить, но зачем выкидывать те, что уже пришли?

Ну да, выкидывать их незачем т.к. например для видеопотока потери не так критичны.

Отправляй в каждом пакете данные из N предыдущих пакетов.

Конечно спасибо за столь высокий уровень развитой телепатии. Но вопрос не про TCP, а про пакеты в отдельности. И кстати про TCP для справки: при потерях - 10%, скорость на TCP падает где-то в 10 раз.

Это зависит , то алгоритма работы , погуглите по cubic и htcp

Почитай, и все вопросы отпадут: http://lib.mexmat.ru/books/1451

Помню в институте была у нас курсовая (реализация на ассемблере такого алгоритма). Единственное что помню два «ключевых слова»: Ху и Блейхут.