Компьютерные сети. 6-е изд.

И наконец, что наиболее важно, полиномиальный код с 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 запрашивает данные, сетевой уровень их сразу же предоставляет. (Это ограничение позже будет отброшено.)

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