Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Деление чисел осуществляется в точности так же, как и деление обычных двоичных чисел, с той разницей, что вычитание производится снова по модулю 2. Говорят, что делитель «уходит» в делимое, если в делимом столько же бит, сколько в делителе.

При использовании циклического кода отправитель и получатель должны сначала договориться насчет образующего многочлена, G(x). Старший и младший биты образующего многочлена должны быть равны 1. Для вычисления CRC для некоторого кадра из m бит, соответствующего полиному M(x), необходимо, чтобы этот кадр был длиннее образующего многочлена. Идея состоит в добавлении CRC в конец кадра таким образом, чтобы получившийся многочлен делился на образующийся многочлен G ( x ) без остатка. Получатель, приняв кадр, содержащий контрольную сумму, пытается разделить его на G(x). Ненулевой остаток от деления означает ошибку.

Должно быть очевидно, что многочлен T(x) делится (по модулю 2) на G(x) без остатка. В любом случае, если вы уменьшите делимое на остаток, то результат должен делиться без остатка. Например, в десятичной системе счисления, если разделить 210 278 на 10 941, то остаток от деления будет равен 2399. Если вычесть 2399 из 210 278, то результат (207 879) будет делиться на 10 941 без остатка.

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

многочлены с небольшими степенями, обеспечивающие защиту для длинных кадров. Например, многочлен x 15+ x 14+ 1 не является делителем для x k + 1 для любого k от

1 до 32 768.

Рис. 3.9.Пример вычисления CRC

Если ошибка затронет нечетное количество бит в кадре, многочлен E(x) будет содержать нечетное число членов . Интересно, что

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

И наконец, что наиболее важно, полиномиальный код с r контрольными битами будет обнаруживать все пакеты ошибок длиной . Пакет ошибок длиной k может быть представлен в виде многочлена , где i определяет, насколько далеко

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

ния в скобках меньше степени G(x), то остаток от деления никогда не будет нулевым.

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

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

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

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

Хотя алгоритм вычисления CRC может показаться сложным, Питерсон (Peterson) и Браун (Brown) в 1961 году показали, что может быть создана простая схема для аппаратной проверки и подсчета CRC на основе сдвигового регистра. Эта схема до сих пор повсеместно применяется на практике. Десятки сетевых стандартов работают на основе кодов CRC, включая почти все локальные сети (такие как Ethernet, 802.11) и двухабонентские системы (пакеты, пересылаемые по связям SONET).

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

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

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