Также следует отметить, что при возникновении пакета ошибок длиннее 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 запрашивает данные, сетевой уровень их сразу же предоставляет. (Это ограничение позже будет отброшено.)
Надежные устройства и процессы. Также предполагается, что компьютеры не выходят из строя. При передаче могут возникать ошибки, но не проблемы, связанные с поломкой оборудования или случайной перезагрузкой.
С точки зрения канального уровня пакет, полученный по интерфейсу от сетевого уровня, рассматривается как чистые данные, и каждый бит должен быть доставлен сетевому уровню принимающего устройства. Тот факт, что он может интерпретировать часть пакета как заголовок, не касается канального уровня.
3.3.2. Базовая схема передачи и приема данных
Получив пакет от сетевого уровня отправителя, канальный уровень формирует из него фрейм, добавляя заголовок и трейлер (см. илл. 3.1). Таким образом, фрейм состоит из встроенного пакета, некоторой служебной информации (в заголовке) и контрольной суммы (в трейлере). Затем фрейм передается канальному уровню целевого устройства. Мы будем исходить из наличия подходящих библиотечных процедур, например to_physical_layer для отправки фрейма и from_physical_layer для его получения. Они вычисляют и добавляют или проверяют контрольную сумму (обычно это делается аппаратно), так что при разработке протоколов, представленных в этом разделе, можно об этом не беспокоиться. К примеру, они могут использовать рассмотренный ранее алгоритм CRC (циклический избыточный код).
Изначально получатель ничего не должен делать, он просто ожидает. В протоколах, рассматриваемых в этой главе, ожидание событий канальным уровнем происходит путем вызова процедуры wait_for_event(&event). Эта процедура возвращает управление, только когда что-то происходит (например, получение фрейма). При этом переменная event сообщает, что именно случилось. Наборы возможных событий отличаются в разных протоколах, поэтому будут описываться для каждого протокола отдельно. Следует отметить, что на практике канальный уровень не находится в холостом цикле ожидания событий (согласно нашему допущению), а получает прерывание, когда это событие происходит. При этом он приостанавливает текущие процессы и обрабатывает полученный фрейм. Но для простоты мы проигнорируем эти детали и будем исходить из того, что канальный уровень все свое время посвящает работе с одним каналом.
Когда принимающая сторона получает фрейм, контрольная сумма вычисляется заново. Если она неверна (то есть при передаче возникли ошибки), канальный уровень получает соответствующую информацию (event=cksum_err). Если фрейм приходит без ошибок, канальному уровню об этом также сообщается (event=frame_arrival), после чего он может получить этот фрейм у физического уровня с помощью процедуры from_physical_layer. Получив неповрежденный фрейм, канальный уровень проверяет управляющую информацию, находящуюся в заголовке, и если все в порядке, часть фрейма передается сетевому уровню; заголовок фрейма не передается ни при каких обстоятельствах.
Для запрета передачи сетевому уровню любой части заголовка фрейма есть веская причина: необходимо обеспечить полное разделение сетевого и канального уровней. До тех пор пока сетевой уровень ничего не знает о формате фрейма и протоколе канального уровня, их изменения не потребуют смены программного обеспечения самого сетевого уровня. Это происходит только при установке на компьютер новой сетевой карты. Поддержание жестко заданного интерфейса между сетевым и канальным уровнями значительно упрощает разработку программ, так как протоколы различных уровней могут развиваться независимо.
На илл. 3.11 показаны некоторые объявления (на языке C), общие для многих протоколов, обсуждаемых ниже. Выделяются пять типов данных: boolean, seq_nr, packet, frame_kind и frame. Тип boolean представляет собой перечисляемый тип, переменные которого могут принимать значение true или false. Тип seq_nr является целым без знака, используемым для нумерации фреймов, благодаря которой их можно различать. Нумерация идет от 0 до числа MAX_SEQ включительно, определяемого для конкретного протокола. Тип packet — это единица информации, используемая при обмене данными между сетевым и канальным уровнями одного компьютера или двумя сетевыми уровнями. В нашей модели пакет всегда состоит из MAX_PKT байт, хотя на практике он обычно имеет переменную длину.