сколько байт занимает в ethernet циклический избыточный код

Циклический избыточный код

Содержание

Алгоритм CRC [ ]

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

Каждому конечному двоичному набору данных взаимооднозначно сопоставляется двоичный многочлен , последовательность коэффициентов которого представляет из себя исходную последовательность. Например, десятичное число 90 (1011010 в двоичной записи) соответствует многочлену:

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

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

Таким образом, контрольная сумма CRC с порождающим многочленом степени N есть битовая последовательность длины N, представляющая многочлен, получившийся в остатке при делении исходного многочлена (представляющего входной поток бит) на порождающий многочлен:

— контрольный код многочлена . — исходный многочлен. — порождающий многочлен. — степень порождающего многочлена.

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

Ниже представлены реализации получения некоторых CRC для многочленов степени 8 (CRC-8), 16 (CRC-16) и 32 (CRC-32).

Формализованный алгоритм расчёта CRC16 [ ]

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

Из файла берется первое слово. В зависимости от того, равен ли старший бит этого слова “1” или нет, выполняем (или нет) операцию XOR на полином. Полученный результат, вне зависимости от того, выполнялась ли операция XOR, сдвигаем на один бит влево (т.е. умножаем на 2). После сдвига (умножения) теряется старый старший бит, а младший бит освобождается (обнуляется). На место младшего бита загружается очередной бит из файла. Операция повторяется до тех пор, пока не загрузится последний бит файла.

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

Источник

Циклический избыточный код

Содержание

Введение

Помехоустойчивое кодирование

Первые попытки создания кодов с избыточной информацией начались задолго до появление современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

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

Контрольная сумма

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

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

Математическое описание

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

Каждой конечной последовательности битов взаимно однозначно сопоставляется двоичный полином , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

Количество различных многочленов степени меньшей равно , что совпадает с числом всех двоичных последовательностей длины .

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

— многочлен, представляющий значение CRC. — многочлен, коэффициенты которого представляют входные данные. — порождающий многочлен. — степень порождающего многочлена.

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

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2 N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.

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

Вычисление CRC

Параметры алгоритма

Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе. Существует огромное множество многочленов, участвующих в формировании cyclic reduntancy code; многие из них указаны в конце статьи.

Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров — информационных ячеек, используемых для вычисления численного значения хэша. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 — битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.

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

Описание процедуры

Из файла берется первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

Наиболее используемые и стандартизованные полиномы

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу. [1] [5]

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа ученых занималась исследованием порождающих многочленов разрядности до 16, [1] 24 и 32 бит, [6] [7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния. [7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

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

Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

Попытки описания алгоритмов CRC

Примеры спецификаций некоторых алгоритмов CRC

Примеры программ для вычисления CRC на языке C

Источник

Всё, что вы хотели знать о Ethernet фреймах, но боялись спросить, и не зря

Статья получилась довольно объёмная, рассмотренные темы — форматы Ethenet фреймов, границы размеров L3 Payload, эволюция размеров Ethernet заголовков, Jumbo Frame, Baby-Giant, и много чего задето вскользь. Что-то вы уже встречали в обзорной литературе по сетям передачи данных, но со многим, однозначно, не сталкивались, если глубоко не занимались изысканиями.

Начнём с рассмотрения форматов заголовков Ethernet фреймов в очереди их появления на свет.

Форматы Ehternet фреймов.

1) Ethernet II

Рис. 1

Preamble – последовательность бит, по сути, не являющаяся частью ETH заголовка определяющая начало Ethernet фрейма.

DA (Destination Address) – MAC адрес назначения, может быть юникастом, мультикастом, бродкастом.

SA (Source Address) – MAC адрес отправителя. Всегда юникаст.

E-TYPE (EtherType) – Идентифицирует L3 протокол (к примеру 0x0800 – Ipv4, 0x86DD – IPv6, 0x8100- указывает что фрейм тегирован заголовком 802.1q, и т.д. Список всех EtherType — standards.ieee.org/develop/regauth/ethertype/eth.txt )

Payload – L3 пакет размером от 46 до 1500 байт

FCS (Frame Check Sequences) – 4 байтное значение CRC используемое для выявления ошибок передачи. Вычисляется отправляющей стороной, и помещается в поле FCS. Принимающая сторона вычисляет данное значение самостоятельно и сравнивает с полученным.

Данный формат был создан в сотрудничестве 3-х компаний – DEC, Intel и Xerox. В связи с этим, стандарт также носит название DIX Ethernet standard. Данная версия стандарта была опубликована в 1982г (первая версия, Ehernet I – в 1980г. Различия в версиях небольшие, формат в целом остался неизменным). В 1997г. году данный стандарт был добавлен IEEE к стандарту 802.3, и на данный момент, подавляющее большинство пакетов в Ethernet сетях инкапсулированы согласно этого стандарта.

2) Ethernet_802.3/802.2 (802.3 with LLC header)

Рис. 2

Как вы понимаете, комитет IEEE не мог смотреть спокойно, как власть, деньги и женщины буквально ускользают из рук. Поэтому, занятый более насущными проблемами, за стандартизацию технологии Ethernet взялся с некоторым опозданием (в 1980 взялись за дело, в 1983 дали миру драфт, а в 1985 сам стандарт), но большим воодушевлением. Провозгласив инновации и оптимизацию своими главными принципами, комитет выдал следующий формат фрейма, который вы можете наблюдать на Рисунке 2.

Первым делом обращаем внимание на то, что “ненужное” поле E-TYPE преобразовано в поле Length, которое указывало на количество байт следующее за этим полем и до поля FCS. Теперь, понять у кого длинее можно было уже на втором уровне системы OSI. Жить стало лучше. Жить стало веселее.

Но, указатель на тип протокола 3его уровня был нужен, и IEEE дало миру следующую инновацию — два поля по 1 байту — Source Service Access Point(SSAP) и Destination Service Access Point (DSAP). Цель, таже самая, – идентифицировать вышестоящий протокол, но какова реализация! Теперь, благодаря наличию двух полей в рамках одной сессии пакет мог передаваться между разными протоколами, либо же один и тот же протокол мог по разному называться на двух концах одной сессии. А? Каково? Где ваше Сколково?

Замечание: В жизни же это мало пригодилось и SSAP/DSAP значения обычно совпадают. К примеру SAP для IP – 6, для STP — 42 (полный список значений — standards.ieee.org/develop/regauth/llc/public.html)

Не давая себе передышки, в IEEE зарезервировали по 1 биту в SSAP и DSAP. В SSAP под указание command или response пакета, в DSAP под указание группового или индивидуального адреса (см. Рис. 6). В Ethernet сетях эти вещи распространения не получили, но количество бит в полях SAP сократилось до 7, что оставило лишь 128 возможных номера под указание вышестоящего протокола. Запоминаем этот факт, к нему мы ещё вернёмся.

Было уже сложно остановиться в своём стремлении сделать лучший формат фрейма на земле, и в IEEE фрейм формате появляется 1 байтное поле Control. Отвечающее, не много, не мало, за Connection-less или же Connection-oriented соединение!

Выдохнув и осмотрев своё детище, в IEEE решили взять паузу.

Замечание: Рассматриваемые 3 поля — DSAP, SNAP и Control и являются LLC заголовком.

3) «Raw» 802.3

Рис. 3

Данный «недостандарт» явил в мир Novell. Это были лихие 80-ые, все выживали, как могли, и Novell не был исключением. Заполучив ещё в процессе разработки спецификации стандарта 802.3/802.2, и лёгким движением руки выкинув LLC заголовок, в Novell получили вполне себе неплохой фрейм формат (с возможность измерения длины на втором уровне!), но одним существенным недостатком – отсутствием возможности указания вышестоящего протокола. Но, как вы уже могли догадаться, работали там ребята не глупые, и по здравому размышлению выработали решение – «а обратим ка мы свои недостатки в свои же достоинства», и ограничили этот фрейм-формат исключительно IPX протоколом, который сами же и поддерживали. И задумка хорошая, и план был стратегически верный, но, как показала история, не фортануло.

4) 802.3 with SNAP Header.

Время шло. В комитет IEEE приходило осознание того, что номера протоколов и деньги кончаются. Благодарные пользователи засыпали редакцию письмами, где 3-х байтный LLC заголовок ставился в один ряд с такими великими инновациями человечества, как оборудование собаки 5ой ногой, или же с рукавом, который можно использовать для оптимизации женской анатомии. Выжидать дальше было нельзя, настало время заявить о себе миру повторно.

Рис. 4

И в помощь страждущим от нехватки номеров протоколов (их всего могло быть 128 – мы упоминали), IEEE вводит новый стандарт фрейма Ethernet SNAP (Рис. 4). Основное нововведение — добавление 5-ти байтного поля Subnetwork Access Protocol (SNAP), которое в свою очередь состоит из двух частей – 3х байтного поля Organizationally Unique Identifier (OUI) и 2х байтного Protocol ID (PID) — Рис. 5.

Рис. 5

OUI или же vendor code – позволяет идентифицировать пропиетарные протоколы указанием вендора. К примеру, если вы отловите WireShark`ом пакет PVST+, то в поле OUI увидите код 0x00000c, который является идентификатором Cisco Systems (Рис. 6).

Рис. 6

Замечание: Встретить пакет с инкапсуляцией в формат фрейма 802.3 SNAP довольно легко и сейчас – это все протоколы семейства STP, протоколы CDP, VTP, DTP.

Поле PID это, по сути, то же поле EtherType из DIX Ethernet II — 2 байта под указание протокола вышестоящего уровня. Так как ранее, для этого использовались DSAP и SSAP поля LLC заголовка, то для указания того, что тип вышестоящего протокола нужно смотреть в поле SNAP, поля DSAP и SSAP принимают фиксированное значение 0xAA (также видно на Рис. 6)

Замечание: При использовании для переноса IP пакетов формата фрейма LLC/SNAP, IP MTU снижается с 1500 до 1497 и 1492 байт соответственно.

По заголовкам в формате фрейма в принципе всё. Хотел бы обратить внимание на ещё один момент в формате фрейма – размер payload. Откуда взялся этот диапазон — от 46 до 1500 байт?

Размер L3 Payload.

Откуда взялось нижнее ограничение, знает, пожалуй, каждый, кто хотя бы читал первый курикулум CCNA. Данное ограничение является следствием ограничения в размер фрейма в 64 байта (64 байта – 14 байт L2 заголовок — 4 байта FCS = 46 байт ) накладываемого методом CSMA/CD – время требуемое на передачу 64 байт сетевым интерфейсом является необходимым и достаточным для определения коллизии в среде Ethernet.
Замечание: В современных сетях, где возникновение коллизий исключено, данное ограничение уже не актуально, но требование сохраняется. Это не единственный «аппендикс» оставшийся с тех времен, но о них поговорим в другой статье.

Замечание: Фреймы меньше 64 байт называются Runts, фреймы больше 1518 байт называются Giants. Просмотреть кол-во таких фреймов полученных на интерфейсе можно командой show interface gigabitEthernet module/number и show interface gigabitEthernet module/number counters errors. Причём до IOS 12.1(19) в счётчики шли как фреймы с неверным, так и верным CRS (хотя вторые не всегда дропались – зависит от платформы и условий). А вот начиная с 12.1.(19) отображаются в этих счётчиках только те runt и giant фреймы, которые имеют неверный CRS, фреймы меньше 64 байт, но с верным CRS (причина возникновения обычно связана с детегированием 802.1Q или источником фреймов, а не проблемами физического уровня) с этой версии попадают в счётчик Undersize, дропаются они, или же форвардятся дальше, зависит от платформы.

Эволюция размеров Ethernet заголовков.

Все эти фреймы увеличенного размера группируются под одни именем – Baby-Giant frames. Негласное верхнее ограничение по размерам для Baby-Giant – это 1600 байт. Современные сетевые интерфейсы будут форвардить эти фреймы, зачастую, даже без изменения значения HW MTU.

Отдельно обратим внимание на спецификации 802.3AS — увеличивает максимальный размер фрейма до 2000 (но сохраняет размер MTU в 1500 байт!). Увеличение приходится на заголовок и трейлер. Изначально увеличение планировалось на 128 байт – для нативной поддержки стандартом 802.3 вышеперечисленных расширений, но в итоге сошлись на 2х тысячах, видимо, чтобы два раза не собираться (или как говорят в IEEE – this frame size will support encapsulation requirements of the foreseeable future). Стандарт утвержден в 2006 году, но кроме как на презентациях IEEE, я его не встречал. Если у кого есть что добавить здесь (и не только здесь) – добро пожаловать в комменты. В целом тенденция увеличения размера фрейма при сохранении размера PAYLOAD, порождает у меня в голове смутные сомнения в правильности выбранного направления движения.

Замечание: Немного в стороне от перечисленного обосновался FCoE фрейм – размер фрейма до 2500 байт, зачастую, эти фреймы называются mini-jumbo. Для их саппорта необходимо включать поддержку jumbo-frame.

Замечание: Верхнее ограничение размера есть и у Jumbo MTU. Оно определяется размером поля FCS (4 байт) и алгоритмом Cyclic Redundancy Check и равняется 11 455 байт. На практике же, Jumbo MTU обычно ограничен размером в 9216 байт, на некоторых платформах в 9000 байт, на более старом железе в 8092 байт (речь о Cisco).

Фух, в принципе всё. Что хотел рассмотреть по теории, рассмотрели. По конфигурации размеров MTU и теории с финтами стоящими за этими тремя буквами, прошу в мою прошлую статью – «Maximum Transmission Unit (MTU). Мифы и рифы».

Источник