Книга Компьютерные сети. 6-е изд. - Эндрю Таненбаум

941 без остатка.

Теперь проанализируем возможности этого метода. Какие ошибки он способен обнаружить? Представим, что произошла ошибка при передаче фрейма и вместо многочлена T(x) получатель принял T(x) + E(x). Каждый единичный бит много­члена E(x) соответствует инвертированному биту в пакете. Если в многочлене E(x) k бит равны 1, это значит, что произошло k однобитных ошибок. Отдельный пакет ошибок характеризуется единицей в начале, комбинацией нулей и единиц и конечной единицей; остальные биты равны 0.

Получатель делит принятый фрейм с контрольной суммой на образующий многочлен G(x), то есть вычисляет [T(x) + E(x)]/G(x). T(x)/G(x) равно 0, поэтому результат вычислений равен E(x)/G(x). Ошибки, которые случайно окажутся кратными образующему многочлену G(x), останутся незамеченными, остальные будут обнаружены.

Если происходит однобитная ошибка, то E(x) = xi, где i — номер ошибочного бита. Если образующий многочлен G(x) содержит два или более члена, то E(x) никогда не будет делиться на него без остатка, поэтому будут обнаружены все однобитные ошибки.

В случае двух изолированных однобитных ошибок E(x) = xi + xj, где i > j. Это также можно записать в виде E(x) = xj(xi – j + 1). Предположим, что G(x) не делится на x. Тогда достаточное условие обнаружения всех двойных ошибок — неделимость многочлена xk + 1 на G(x) для любого k от 1 до максимального значения i – j (то есть до максимальной длины фрейма). Известны простые многочлены с небольшими степенями, обеспечивающие защиту для длинных фреймов. Например, многочлен x15 + x14 + 1 не является делителем для xk + 1 для любого k от 1 до 32 768.

Если ошибка затронет нечетное количество битов во фрейме, многочлен E(x) будет содержать нечетное число членов (например, x5 + x2+ 1, но не x2 + 1). Интересно, что в системе арифметических операций по модулю 2 многочлены с нечетным числом членов не делятся на x + 1. Если в качестве образующего выбрать многочлен, который делится на x + 1, то с его помощью можно обнаружить все ошибки, состоящие из нечетного количества инвертированных битов. Как показывает статистика, уже за счет этого можно обнаружить половину имеющихся ошибок.

И наконец, что наиболее важно, полиномиальный код с r контрольными битами будет обнаруживать все пакеты ошибок длиной ≤ r. Пакет ошибок длиной k может быть представлен в виде многочлена xi(xk-1 +…+ 1), где i определяет, насколько далеко от правой границы фрейма располагается пакет ошибок. Если образующий многочлен G(x) содержит член x0, то xi не будет его множителем. Поэтому если степень выражения в скобках меньше степени G(x), то остаток от деления никогда не будет нулевым.

Если длина последовательности ошибок равна r + 1, то остаток от деления будет нулевым, только если последовательность идентична G(x). По определению, первый и последний биты последовательности должны быть равны 1, поэтому ее совпадение с образующим многочленом зависит от r – 1 промежуточных битов. Если все комбинации считать равновероятными, то возможность такой нераспознаваемой ошибки равна (1/2)r–1.

Также следует отметить, что при возникновении пакета ошибок длиннее r + 1 битов или нескольких коротких пакетов вероятность пропуска ошибки составляет (1/2)r при условии, что все комбинации битов равновероятны.

Некоторые образующие многочлены стали международными стандартами. Один из них применяется в IEEE 802 (он основан на многочлене, используемом в Ethernet):

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1.

Помимо других полезных свойств, этот многочлен обладает способностью обнаруживать любые пакеты ошибок длиной не более 32 бит и все пакеты, дающие нечетное число битов. Начиная с 1980-х годов он применяется очень широко. И все же его нельзя назвать наилучшим. Выполнив обстоятельные компьютерные вычисления, Кастаньоли и др. (Castagnoli et al., 1993) и Купман (Koopman, 2002) обнаружили самые эффективные коды CRC. Расстояние Хэмминга, соответствующее сообщениям обычной длины, для них равно 6, в то время как для CRC-32 стандарта IEEE оно равняется всего 4.

Хотя алгоритм вычисления CRC может показаться сложным, Петерсон и Браун (Peterson and Brown, 1961) продемонстрировали, что можно создать простую схему для аппаратной проверки и подсчета CRC на основе схемы с регистром сдвига. В дальнейшем с регулярной периодичностью появлялись более новые и более быстрые реализации (см. работу Митры и Найека; Mitra and Nyack, 2017). CRC до сих пор применяется на практике повсеместно в аппаратном обеспечении. Десятки сетевых стандартов работают на основе кодов CRC, включая почти все LAN (например, Ethernet, 802.11) и линии связи «точка-точка» (пакеты, пересылаемые по SONET).

3.3. Элементарные протоколы передачи данных на канальном уровне

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

3.3.1. Исходные упрощающие допущения

Независимые процессы. Для начала предположим, что физический, канальный и сетевой уровни являются независимыми процессами, которые взаимодействуют между собой путем передачи сообщений. Типичная реализация показана на илл. 3.10. Процесс физического уровня и часть процесса канального уровня выполняются на специальном оборудовании: сетевой интерфейсной карте (Network Interface Card, NIC). Остальная часть процесса канального уровня и процесс сетевого уровня осуществляются на центральном процессоре (ЦП), являясь частью операционной системы. При этом программное обеспечение процесса канального уровня зачастую принимает вид драйвера устройства. Также возможны другие варианты реализации, например, три процесса, выполняющиеся на сетевом ускорителе или на ЦП с программно определяемой частотой. На самом деле оптимальная реализация меняется с течением времени

Илл. 3.10. Реализация физического, канального и сетевого уровней

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

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

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