02 Июля

Вся эта войнушка сертифицированного специалиста вокуруг Хемминга напомнила мне старую историю, давности, эдак, семилетней или около того. В те времена передача файлов посредством модема ещё представляла интерес и кроме SLIP/PPP по модемам бегали протоколы ZModem, Janus и т.д., и т.п.

С ними бегали и проблемы. Протоколы, чаще всего, писались на Западе, а это и нынче-то не слишком похоже на наши условия, а уж тогда... чего стоит одна лишь эпопея с попыткой внедрить в сознание западного программера мысль, что модем может терять связь вот просто так, сам по себе. И не ввиду невероятного стечения обстоятельств, или, скажем, прилёта гантель со шкафа, а, наоборот, совершенно ожиданным и регулярным образом. Мужик, которому это втюхивали, воспринимал информационный поток как сплошной сюр. То есть соглашался, что в принципе такое возможно, но в природе - нет, не бывает.

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

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

Пока модемы общаются принимающая сторона ничего, собственно, не принимает. Ждёт она секунд 20-30, а там терпение у неё лопается. "Что-то", говорит она стороне передающей, "нет от тебя блока номер 3213. Пошли-ка его ещё разок.". Понятно, что этот глас сознания становится в очередь к модему и никуда пока не идёт - у модемов всё ещё разборки с АТС. Принимающая сторона терпит ещё чуток и снова возбухает - "Где мой блок номер 3213? Подать!". Тем временем передающая сторона уже насовала в буфер своему модему и 3213, и 3214, и 3215 - всё засунула, что влезло.

И вот, ура, приходит долгожданная радость - или хрип пропадает, или модемы обучаются с ним сосуществовать, понизив скорость, но, ура, до приёмника доходят заждавшиеся в буфере 3213-3215. А до передатчика... ну правильно - застрявший было в очереди запрос на 3213. Две штуки. Или три. Он, как честный вася, и передаёт в ответ блок 3213. Две штуки. Или три. А поскольку он туп, как пробка, то дальше пойдут 3214 и 3215 и всё, что успело запихаться в буфер во время затыка.

Эффект потрясающий. Из-за задержки в 30 секунд мы теряем не только эти полминуты, но и время на пустую перепосылку всего, что поместилось в буфера модема, ОС и программы передачи данных. Это способно легко увеличить потери от задержек на 200-500% только потому, что западные программисты нетерпеливы. А если задержки передачи следуют регулярно, то бардак суммируется и эффективная скорость падает до буквально черепашьей - порой, десятки байт в секунду!

Другой мерзкий эффект - размер блока данных. Поскольку данные передаются в пакетах и у каждого пакета есть служебная информация, размер пакета важен. Если пакет мал, накладные расходы на служебку велики. Неэффективно. А если он велик, то ошибка в одном байте угробит массу информации, которую придётся посылать повторно. Тоже неприятно. Чтобы с этим бороться, придумали динамический размер пакета. Много ошибок - делаем малый пакет. Мало - шлём большой. Нужно ли говорить, что западные протоколы грешили перебором с размером пакета и совершенно безосновательно его завышали. То есть это для нас безосновательно - у них-то всё было нормально.

Короче, стало ясно. что нужен свой протокол передачи данных. На этом фронте мной были предприняты две попытки подхода к весу. Увы, обе, как выяснилось, академические :-), но всё равно любопытные.

Первая базировалась на идее "не будем повторять лишнее". Я спроектировал и написал протокол, который при потере приёмником блока номер N не начинал сдуру повторять отправку блока N+1 и так далее, а обходился только одним повтором. Как ни странно, реализация идеи оказалась не так уж тривиальна, как кажется с первого взгляда. Жизнь проектировщика протоколов осложняет тот факт, что в линии портится не только то, что идёт от передатчика к приёмнику, но и летящие назад квитанции. С квитированием и случились проблемы. Например, выяснилось, что приёмник должен докладать передатчику и что он НЕ получил, и что он ДА, спасибо, получил. Иначе возможность потери сообщения о неполучении привносит в логику работы целую прорву неопределённости, с которой довольно неприятно бороться. В итоге я пришёл к схеме, в которой передающая сторона держала карту вероятности получения данного блока приёмником. Вероятность росла при каждой передаче блока (но не до 1), и выставлялась в чёткие 0 или 1 при получении достоверной информации от приёмника. Понятно, что передатчик первым делом передавал блоки, вероятность принятости которых была минимальна.

Удивительно, но вся эта белиберда даже работала, жаль вот только время передачи файлов вышло, а с ним ушёл и спрос на такие протоколы.

Тем не менее, была вторая попытка, которая не дошла до реализации (по аналогичной причине), но в принципе куда интереснее. До неё я дошёл после игр с Хеммингом и восстановлением ошибок. Обдумывая с сослуживцами возможности кода Рида-Соломона, мы решили, что из этого кода вынуто не всё, что можно, и нашли математика, который занимался сходными проблемами. В разговоре с ним и родилась идея построения протокола не с повторами неправильно принятой информации, а с... досылкой избыточности! Что есть код, исправляющий ошибки? Это, по крайней мере, в некоторых реализациях, извлечённая из информации информация же, которая может быть использована для восстановления оригинала, если в нём что-либо испортится.

Что любопытно - как правило, определить, испорчен блок или нет - легко. Считается, что CRC32 (4 байта на, скажем, килобайт) делает это вполне надёжно. Теперь существенный момент. Если блок сильно испорчен, то есть так, что известные нам алгоритмы его не "починят", то придётся передавать его заново весь. Но если потерян лишь бит, то обидно тащить целый килобайт. Нельзя ли дослать вдогон ему контрольную информацию, сообразно которой его "починить"? Если да (а так выходило, что это возможно), то было бы логично делать так. Отправлять сначала блок, защищённый сложной контрольной суммой. Сумма эта должна не просто говорить, побит он жизнью, или нет, а и отвечать на вопрос - сильно ли. И если несильно - то мы запрашиваем у передатчика перепосылку не всего блока, а лишь построенного из него восстанавливающего кода, с помощью которого битый блок и чиним. Конечно, нам может сильно не повезти и в процессе передачи испортится и восстанавливающий код. Увы, тогда придётся, вероятно, делать оргвыводы и возвращаться к методам перепосылки. Но на случайных всплесках помех сия метода должна бы работать весьма эффективно.

Проверить это предположение не сложилось, но любопытство осталось. Категорически академическое. В TCP пакеты не портятся - просто не приходят и всё. :-)

Вот. Предлагаю идею на поругание. :-)

Получил на днях релиз 4.5 BeOS. Не нашёл ни одного свободного раздела и уж было сел записывать сидюки и вычищать место, как...

Ввыдался случай помогать другу ставить Linux. В процессе постановки оного я так удачно двинул ногой по столу с компьютером, что тот упал. В переносном смысле. Перезагрузился. Момент оказался на редкость удачным - rpm (менеджер пакетов - инсталлятор, короче) как раз ковырялся в своей базе, и перезагрузка подействовала на него нехорошо. Оправиться от испуга он не смог, что-то там покривилось... пара попыток его вразумить не помогла и было решено установку начать с нуля, ибо проще всего. Тут и пришла в голову мысль - а не попробовать ли пока новый BeOS - место есть, желание - тоже...

Нельзя сказать, чтобы я успел изрядно покопаться с 4.5, но одно могу сказать чётко: с инсталляцией, загрузчиком и драйверами стало заметно лучше. Загрузчик просто шикарен - это, по большей части, выпендрёж, но в самом-самом начале загрузки экран переходит в графику, рисуются тусклые иконки, символизирующие основные этапы загрузки (ядро, драйвера, сеть, графика и т.п. - с десяток) и по мере прохождения оных этапов иконки подсвечиваются. Смех смехом, но, вероятно, это - довольно информативная подсказка - где искать проблемы, если система не грузится.

Единственный вопрос, который я получил при запуске - куда, собственно, ставиться и форматировать ли это. Всё встало само - звук сразу же заработал, графика тоже - осталось лишь переключить потом дисплей на нужное разрешение, глубину цвета и частоту развёртки.

Из неудач - не получилось выйти в Интернет через модем (всё происходит, но когда она считает, что дозвонилась, пинг не идёт), но у нас не было избытка времени выяснить, ОС виновата, или же мы. Далее, не оказалось драйвера для имеющегося принтера (Epson Stylus), хотя, возможно один из наличествующих и подойдёт...

Общее ощущение - система стала заметно более хорошо совместима с Интеловской платформой и проще в инсталляции.

Из неопробованного. Есть софт для поддержки некоторых цифровых камер. Система знает про USB - пока лишь мыши, клавиатуры и принтера. Поддерживаются форматы MPEG, QuickTime, AVI, WAV, AIFF, AU. Встроены некоторые популярные аудио- и видео-кодеки. В броузере появился экспериментальный javascript. Есть клиент для Microsoft Network.

Из внутрисистемного. Новый звуковой API спецально для игр. Говорят, что сделан специально под Quake 3... В ядре - победа довольно серьёзного плана. Теперь задержка переключения контекста снижена до 250 микросекунд и, мало того, заявлены определённые гарантии этого, то есть, хоть я с трудом в такое верю, кажется под BeOS нельзя написать даже драйвер, который запрёт систему. Хотел бы я поподробнее в этом разобраться. Может, после отпуска...

PS: На beos.com - новый дизайн.

PPS: А знаете, что мне больше всего нравится в BeOS? Что там есть Plug'n'Play, но... он правильно работает.

Наверное, это надо, несмотря на закрытость темы, опубликовать:

"Alexander Krutskikh не работает и никогда не работал в компании "Анкей/Смарттехнологии" - разработавшей и установившей систему Автоматизированной оплаты проезда в Московском метрополитене (см. www.smartek.ru), поэтому просьба не считать его идиотские реплики мнением создателей системы." -- Стругатский Андрей, системный администратор Группа Смарт Технологий.

И ещё - Alexander Krutskikh обещал, что если тема не будет закрыта, у меня будут проблемы. :-) Прелесть. Нет, право, давно я не получал столько положительных эмоций! :-)

Всё, у нас нет больше рекламы, которую мы должны крутить, зато есть дикое желание отдохнуть. Нет более никаких сил, а значит - у нас каникулы. До нашего отъезда из Москвы возможны нерегулярные выходы выпусков dz online, а уж после отъезда - разве что чудом. Отъезд будет обозначен отдельно, но предположительно - в районе 12-15 чисел.

На Прописях - "Охота за пикселями", обзор цифровых камер от Глеба Кащеева. А на сайте "Мира Интернет" - интервью с Дмитрием Завалишиным. :) Действительно хорошее интервью.