Байт-стаффинг в каналах передачи данных

Аннотация

Длинная и нудная статья, которая описывает проблемы передачи пакетных данных посредством последовательного порта (виртуального последовательного порта) и описывает один из способов решения проблемы «слипания» пакетов при плотном трафике. Статья рассчитана на уровень продвинутых разработчиков. Кроме того, в ней совсем нет картинок.

Проблема

Многие электронные устройства в процессе своей работы передают полученные данные в компьютер.

Такими устройствами могут быть различные датчики. Например, датчики температуры, датчики влажности, датчики давления и так далее. Это могут быть различные геофизические зонды для измерения геометрического положения ствола скважины, магнитного поля земли, магнитной и/или электрической проницаемости среды, измерители гамма-фона и так далее. В последние время я соприкоснулся с темой радио-частотного сниффера. Сниффер — это такое устройство, которое «вынюхивает» что делается в эфире (англ. to sniff = нюхать). Сниффер — двольно-таки примитивное устройство, которое просто принимает радио-пакеты и тупо, без какой-либо обработки, передаёт их в компьютер.

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

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

Вообще, известны две разновидности передачи данных: в виде ASCII-строк, и в виде бинарного кода. (Те, кто знакомы с темой MODBUS сразу идентифицируют их MODBUS ASCII и MODBUS RTU.)

ASCII-передача хороша тем, что почти все символы печатные. Таким образом, если такой ASCII-поток данных направить на терминал, то на экране терминала (или на бумаге, если принтер работает в качестве терминала) можно сразу видеть принимаемые сообщения. Это удобно, хотя и не очень рационально с точки зрения экономии трафика.

Следует отметить, что каждый пакет (каждый блок данных) при ASCII-обмене имеет чёткие границы. Окончанием пакета является символ новой строки. Каждое новое сообщение (новая строка) начинается от края экрана. Если передаваемые строки меньше, чем ширина экрана, то перепутать начало-конец блока данных практически не возможно!

Ведь, казалось бы, ASCII-обмен — благо. Подключился к такой линии связи своим логгером и получай на экране лог. Причём, для подключений никаких дополнительных телодвижений делать не надо — не надо никаких программ-расшифровщиков. Просто подключился — и сразу всё, что «бежит» по линии связи, будет отображаться на экране или писаться в файл, который потом можно будет посмотреть любым текстовым редактором. Не жизнь — песня!

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

Первое, что приходит на ум — передавать данные не в «человеческом» виде, а в машинном. То есть передавать данные не в виде ASCII-строк, а гнать данные в виде двоичного потока.

Например, нам нужно передать число 10000. Если передавать его в ASCII-виде, то нам сначала понадобится преобразовать его в этот ASCII-вид. То есть затратить на это преобразование время микроконтроллера. Затем по линии связи нужно передать пять байт (пять символов: одна единица и четыре нуля). На приёмном конце (то есть — в компьютере) распознать эти пять символов и снова превратить их число. Для преобразования одного числа из двоичного формата в ASCII-строку, а потом обратно, может быть надо не так уж и много времени. Но что делать, если таких чисел не просто много, а очень много? Ведь тогда получится, что большая доля процессорного времени уйдет как раз на такие-вот преобразования. К тому же и размер трафика тоже возрастёт.

Можно поступить проще — не заниматься преобразованиями туда-обратно, а сразу передать это число в машинном формате. К стати, число 10000 в памяти микроконтроллера, а также в памяти компьютера занимает всего два байта. Иначе говоря, по линии связи будет передано не пять, а два байта. Таким образом, пропускная способность системы повысится в 2.5 раза.

Ура?

Не, не «Ура!» Здесь окопались две проблемы.

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

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

Просто гнать с одного устройства на другое двоичный код не получиться. А ну как в процессе передачи пройдёт какая-нибудь помеха, и один байт потеряется. И что тогда? А тогда произойдёт следующее — произойдёт рассинхронизация по байтам.

Допустим, передающее устройство передаёт вот такую последовательность чисел (здесь и далее числа представлены в HEX-формате):

0001 0002 0003 0004 0005 0006 0007 и так далее

На линии связи эти числа будут выглядеть в виде следующей последовательности байт:

01 00 02 00 03 00 04 00 05 00 06 00 07 …

Сначала передаётся младший байт числа, затем старший.

Принимающее устройство принимает этот поток байтов и объединяет их по-парно:

01_00 02_00 03_00 04_00 05_00 06_00 07_00 …

Я поставил символ подчеркивания между байтами, которые будут объединены вместе. После объединения смежных байтов мы получим поток следующих чисел:

0001 0002 0003 0004 0005 0006 0007 …

Как видите, информация до получателя дошла благополучно.

А что будет, если во время передачи седьмого байта проскочит сильная помеха?

01 00 02 00 03 00 xx 00 05 00 06 00 07 …

Байт исказиться и будет откинут. То есть наша последовательность будет лежать в приёмном буфере уже в таком виде:

01 00 02 00 03 00 00 05 00 06 00 07 …

Приёмное устройство объединит смежные байты

01_00 02_00 03_00 00_05 00_06 00_07 …

и на выходе мы получим:

0001 0002 0003 0500 0600 0700 …

То есть вместо последовательности чисел 1, 2, 3, 4 , 5, 6, 7 … мы получим последовательность 1, 2, 3, 1280, 1536, 1792 …

😦

И такое враньё будет продолжаться до тех пор, пока приёмник не «потеряет» ещё один байт. Только с потерей второго байта синхронизация восстановиться.

Я рассматривал случай передачи двух-байтовых чисел. А если нам предстоит передавать не двух-байтовые числа, а 300-байтовые структуры? Это что, получается, что пока приёмник не потеряет ещё 299 байтов, синронизация не восстановится?

Ответ — да, именно так!

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

Таким образом, нам нужно как-то обозначать границы блоков (границы пакетов). А это и есть вторая проблема. Тут тоже не всё гладко. Но выход есть.

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

Можно дополнительно прибегнуть к передаче в начале пакета его длинны. То есть перед тем как передать 100 байт, мы предварительно передаём число 100. Тогда на приёмном конце (комп) нужно просто принять указанное количество байт — это и будет являться пакетом. А остальные байты, принимаемые после этих 100 байт — это будет уже другой пакет. Вроде бы всё хорошо. И такой способ передачи пакетов тоже работает и тоже частенько используется на практике.

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

Проблемы выплывают, когда пауза между пакетами очень короткая. (Слово «короткая» — не научное, но об этом в следующем абзаце.) Это приводит к тому, что пакеты могут «склеиваться». Причём «склейкой» пакетов может заниматься не только микроконтроллер, но и сам компьютер с его практически неограниченной вычислительной мощностью. Вот, где неожиданность! Чуть ниже я расскажу, как такое может случаться.

Но сначала давайте разберёмся что значит «достаточно большая пауза» и что значит «короткая пауза»? Какую паузу считать большой, а какую — короткой? Какой критерий для оценки?

Понятно, чем длиннее пауза между пакетами, тем легче их различать. Но такое определение попахивает фанатизмом. А нам бы хотелось иметь более чёткие представления о временнЫх границах между пакетами. Хотелось бы знать — а сколько это в миллисекундах или в длительностях передачи одного бита или символа?

Я не очень помню откуда (но в принципе — «Гугл знает!», при желании можно нагуглить) пошло следующее значение, но я всегда ориентировался на значение 3.5 временных интервала передачи одного символа (равно — одного байта).

Например, передача данных осуществляется на скорости 115200 Бод. Значит, передача одно бита занимает 8.68 мкс. На передачу одного байта, плюс стартовый и плюс стоповый биты будет затрачено 86.8 мкс. Таким образом, если при приёме возникает пауза между принимаемыми байтами более 3.5 * 86.8 = 303.8 мкс, то можно считать, что передача пакета закончена, и следующий байт, который будет принят, — он будет принадлежать уже другому пакету.

Забавно отметить, что у микроконтроллеров STM32 в USART-ах предусмотрен регистр, который можно поместить заданное значение паузы, и, в случае превышения этой паузы при приёме потока данных, возникнет соответствующее прерывание. То есть решение задачи по обнаружению пауз между пакетами перенесено на аппаратный уровень — пользуйтесь на здоровье! Я лично — пользуюсь. Это очень удобно.

Всё хорошо. Но нам нужно принимать пакеты на стороне компа. А вот тут нас подстерегает очень неприятная засада.

Дело в том, что если бы современные компьютеры работали под операционной системой типа DOS, то проблемы бы не было. Но почти все современные компьютеры работают под управлением либо Виндовс, либо Линукс. А эти операционки являются многозадачными.

Чем это плохо. Многозадачность, подразумевает присутствие с системе нескольких задач — выражаясь более точно — нескольких процессов. У каждого процесса имеется как минимум один поток исполнения. Каждому потоку операционная система выделяет небольшой промежуток процессорного времени для его исполнения. Как правило, это 10 миллисекунд. Затем система переключает процессор на другой поток. Итак по кругу.

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

Вообще, надо оговорится, что в любой операционной системе существует система приоритетов потоков. Но я не хотел бы касаться этой темы, так как она не упростит, а наоборот усложнит рассмотрение проблемы «слипания» информационных пакетов при их приёме.

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

Пользовательская программа получает данные не из последовательного порта непосредственно, а из драйвера последовательного порта. Это значит, что драйвер, прежде чем отдать порцию данных (Обращаю внимание — не пакет, а именно порцию данных!) пользовательской программе по её запросу, он (драйвер) сначала принимает поток данных от последовательного порта и складывает эти байты в свой буфер.

Драйвер последовательного порта работает с потоком байтов, но не с пакетами. Он понятия не имеет о пакетах — где или чем они начинаются и чем заканчиваются. Этими вопросами как правило занимаются пользовательские программы.

Вообще, когда речь идет о потоке, то понятие времени становится эфемерным. У потока вообще нет времени — там есть просто поток байтов. И все те ухищрения по программному обнаружению пауз между приёмом байтов — это не очень надёжно. Читайте дальше!

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

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

Программа, вызывая функцию драйвера, отдаёт ему управление.

Управление же вернётся в программу в двух случаях:

  1. когда драйвер способен вернуть запрошенное количество байт
  2. когда кончится время ожидания (случится так называемый таймаут)

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

Хороший вопрос — какое время следует задать?

Хороший ответ — а какое время ни задай, всё равно плохо!

Почему так, давайте разбираться. Если мы зададим очень короткое время, ну, допустим 1 мкс, то получиться, что мы каждый раз будем получать по одному байту, либо драйвер будет нам возвращать управление по таймауту. То есть мы будем принимать либо один байт, либо ноль. Но зато мы в своей пользовательской программе сможем сами отслеживать длительные паузы между пакетами. Для этого только нужно будет написать кое-какой код. Но мы же с вами — программисты! Напишем.

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

Хорошо, тогда пусть таймаут будет достаточно большим. Допустим, 100 мс. В этом случае программа будет возвращать нам куски информационного потока той длины (в байтах), которую мы заказали.

И это будет работать! И это часто используется на практике. Но не в нашем случае! Мы предполагаем, что в линии связи не может произойти сбой. А ну как он произойдёт! И что тогда?

В случае сбоя мы потеряем один байт. Если специально не отслеживать ситуации потерянных, то получается, что при обращении из пользовательской программы к драйверу, программа получит «укороченный» на один байт пакет (возврат произойдёт по таймауту) и тогда его можно просто откинуть. Другой исход — программа получит все байты, сколько она запросила, но тогда окажется, что в последнем байте пакета будет находиться первый байт следующего пакета.

Опаньки!

И как распознать такую ситуацию? Как узнать сколько байт «испортилось» при пересылке — один, два? Или десять?

Если же пойти по пути прописывать отслеживания пользовательской программой и обработку ситуаций приёма «битых» байтов, то я уже не знаю, что это вообще будет. Ясно только одно — в хорошо написанных системах так быть не должно.

Я могу ещё долго описывать «Страдания Вертера», но вряд ли это будет кому-то интересно. Понятно, что при передачи пакетов посредством последовательного порта есть определённые трудности. Причём, проблема сильно возрастает если канал используется на грани своих возможностей или пакеты не имеют предсказуемого времени прихода.

С непредсказуемостью времени поступления пакетов я столкнулся при изготовлении радиочастотного сниффера. Что там делается в эфире — одному богу известно! Столкновение радиопакетов (коллизии) — это нормальное явление. В случае столкновения сниффер просто откинет те, что он напринимал и проблем нет. А вот когда он принимает два и более пакетов, идущих почти вплотную друг за другом, а потом отправляет их в комп в виде непрерывного потока данных, возникает очень большая проблема.

Учитывая, что обмен между сниффером и компом ведётся на скорости 115200 Бод, а приём радиопакетов осуществляется на скорости 250 кБод, то понятно, что иногда случаются такие моменты, когда в буфере микроконтроллера могу находится несколько пакетов. И если ничего не предпринимать, то это неизбено приведёт к их «слипанию».

В принципе, скорости 115.2 кБод для передачи пакетов в комп — вполне достаточно. Сложность в том, что радиопакеты поступают в сниффер нерегулярно, а спорадически. То есть то густо, то пусто.

Самое простое решение — это увеличить скорость передачи по последовательному каналу до 460.8 кБод. (Скорость 230.4 кБод проблему не снимет по понятным причинам.) Но не всякий последовательный порт (в том числе виртуальный последовательный порт, завёрнутый в USB) способен работать на такой скорости. А хотелось бы универсальности.

Другой вариант — на стороне микроконтроллера организовывать паузы между пакетами, которые дадут гарантированное различие пакетов. Хорошо. Вопрос — так какой же величины должны быть эти паузы?

Помните, я говорил о работе операционных систем? Я говорил, что исполняемому потоку выделяется квант времени в 10 мс.

Если я сделаю длительность паузы между пакетами менее 10 мс, (ну, допустим, 2 мс), то вполне может случится такая ситуация, когда управление в компе будет перехвачено какой-то третьей программой, и пользовательская программа не сможет вовремя вычитать из драйвера информацию. Тогда получиться, что драйвер последовательного порта, положит два или несколько пакетов в буфер. А если при пересылке какого-то из пакетов ещё примется хотя бы один «битый» байт, то получиться, что придётся выкидывать вообще всё, что есть в буфере.

Если паузу между передачей пакетов делать более 10 мс, то пакеты удастся различать. Но тогда возникает лёгкое недоумение — а это что за система такая «тормознутая» получится, что у неё могут быть паузы по 10 и более мс? Это с какой реальной скоростью она будет передавать информацию? В общем, опять какая-то фигня.

Но выход, как ни странно, из этой западни есть!

 

Решение проблемы

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

А очень просто — нужно решать проблему с методом байт-стаффинга.

Англоязычное слово stuffing подразумевает действие по набивке чего либо какой-либо хренью. Например, набивать подушку пером, закидывать в избирательные урны фальшивые бюллетени. Мы же будем заталкивать в наш поток данных «байтовый хлам». Этот «хлам» нам не нужен, но он сильно помогает различать границы пакетов.

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

Однако, следует заметить, что все потоки данных — разные. например, при передаче каких-либо компьютерных программ в (качестве данных) байт со значением 00 наверняка будет встречаться чаще, чем байт со значением C3 или 45. Ну, ещё раз — надо смотреть!

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

Допустим, в качестве стафф-байта я выбрал байт со значением 00. Это значит, что теперь это байт как бы выпал из набора байт, которые могут быть в моём информационном потоке. Но зато я получил однозначное обозначение границы пакетов.

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

Молодые люди наверно уже не знают, а вот старики наверняка помнят что такое Esc-последовательности. Так вот, стафф-байт — это ничто иное как тот же самый байт ESC (16-ричное значение 1B). Разве что значение стафф-байта может быть какое-то свое, не стандартное.

Назначение Esc-байта и стафф-байта одинаковое — временно изменить интерпретацию следующего за ним байта. Таким образом, теперь я могу после стафф-байта передавать ещё один байт, который позволит мне сделать целую кучу полезных дел.

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

Итак, пусть вместо нулевого информационного байта (00) передаётся последовательность из двух байт: 00 00. А в качестве границы между пакетами будем передавать последовательность из двух байт 00 01. Оставшиеся комбинации последовательностей из двух байтов (от 00 02 по 00 FF) будем считать ошибочными.

И в самом деле, если программы написаны без ошибок, то таких последовательностей быть не может. Такие последовательности могут возникнуть, если при передаче проскочит помеха и изменит значение байта. Ну дак! Это и есть — «битый» байт. Какая разница — где это битый байт получился — во время приёма обычных байтов, или во время стаффинга. Однозначно — полученный пакет в мусорную корзину!

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

При реализации сниффера я поступил несколько по другому. Я назначил последовательность байт 00 01 как начало пакета, а последовательность байт 00 02 — как конц пакета.

Таким образом при передаче каждого пакета через USART микроконтроллер сначала передаёт два байта 00 01. Затем следует передача содержимого пакета. Причём, если в пакете встретился байт 00, то он заменяется на два байта 00 00. И в конце пакета пакета передаётся ещё два байта 00 02.

На приёмном конце при получении байтов происходит декодирование потока. Если в потоке встретился байт со значением 00, то смотрится значение следующего байта. Если значение следующего байта равно 00, то эти два байта заменяются на один байт — 00, который и записывается в буфер пакета.

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

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

Если же был принят байт с каким-то иным значением, то это означает, что где-то произошёл сбой. Следующие байты можно не принимать. А уже принятые и записанные в буфер, можно объявить как «битый пакет». Далее нужно тупо ждать последовательности 00 01, которая означает начало пакета.

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

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google photo

Для комментария используется ваша учётная запись Google. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s