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

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

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

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

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

Получив пакет, канальный уровень формирует из пакета кадры, добавляя заголовок и концевик (см. рис. 3.1). Таким образом, кадр состоит из внедренного пакета, некоторой служебной информации (в заголовке) и контрольной суммы (в концевике). Затем кадр передается канальному уровню принимающей машины. Мы будем предполагать наличие соответствующих библиотечных процедур, например tO_physical_layer для отправки кадра и from_physical_l ayer для получения кадра. Эти процедуры вычисляют и добавляют или проверяют контрольную сумму (обычно это делается аппаратно), так что протоколы, о которых мы говорим в этом разделе, могут не беспокоиться об этом. Они могут применять, например, алгоритм циклических кодов, обсуждавшийся в предыдущем разделе.

Вначале получатель ничего не должен делать. Он просто сидит без дела, ожидая, что что-то произойдет. В приводимых в данной главе примерах протоколов ожидание событий уровнем передачи данных обозначается вызовом процедуры wait_for_ event(&event). Эта процедура возвращает управление, только когда что-то происходит (например, прибывает кадр). При этом переменная event сообщает, что именно случилось. Наборы возможных событий отличаются в разных протоколах и поэтому будут описываться для каждого протокола отдельно. Следует заметить, что в действительности канальный уровень не находится в холостом цикле ожидания событий, как мы предположили, а получает прерывание, когда это событие происходит. При этом он приостанавливает свои текущие процессы и обрабатывает пришедший кадр. Тем не менее для простоты мы проигнорируем эти детали и предположим, что канальный уровень все свое время посвящает работе с одним каналом.

Листинг 3.1. Общие объявления для последующих протоколов. Объявления располагаются в файле protocol.h

Листинг 3.1 (продолжение)

Когда принимающая машина получает кадр, контрольная сумма вычисляется заново. Если контрольная сумма в кадре неверна (то есть при передаче возникли ошибки), то канальный уровень получает соответствующую информацию (event=cksum_err). Если кадр прибывает в целости, канальному уровню об этом также сообщается (event=frame_arri val), после чего он может получить этот кадр у физического уровня с помощью процедуры from_physical_layer. Получив неповрежденный кадр, канальный уровень проверяет управляющую информацию, находящуюся в заголовке кадра, и если все в порядке, часть этого кадра передается сетевому уровню. Заголовок кадра не передается сетевому уровню ни при каких обстоятельствах.

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