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

многочлены с небольшими степенями, обеспечивающие защиту для длинных кадров. Например, многочлен 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). Остальные процессы канального уровня и процессы сетевого уровня — на центральном процессоре. Они являются частью операционной системы, причем программное обеспечение процесса канального уровня зачастую принимает форму драйвера устройства. Однако другие варианты реализации также возможны (например, три процесса, выполняющиеся на специальном устройстве, называемом сетевым ускорителем, или на ЦП с частотой, определяемой программно). В действительности, оптимальная реализация в каждый период развития технологий своя и зависит от имеющихся технических возможностей. В любом случае, представление трех уровней в виде отдельных процессов будет служить поддержанию концептуальной чистоты обсуждения, а также подчеркнет независимость уровней.