Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 69
Текст из файла (страница 69)
Старший и младший биты образующего многочлена должны быть равны 1. Для вычисления CRC для некоторогокадра из m бит, соответствующего полиному M(x), необходимо, чтобы этот кадр былдлиннее образующего многочлена. Идея состоит в добавлении CRC в конец кадратаким образом, чтобы получившийся многочлен делился на образующийся многочленG(x) без остатка. Получатель, приняв кадр, содержащий контрольную сумму, пытаетсяразделить его на G(x). Ненулевой остаток от деления означает ошибку.Алгоритм вычисления CRC при этом может быть следующим:1. Пусть r — степень многочлена G(x). Добавим r нулевых бит в конец кадра так,чтобы он содержал m + r бит и соответствовал многочлену x rM(x).2. Разделим по модулю 2 битовую строку, соответствующую многочлену x rM(x), набитовую строку, соответствующую образующему многочлену G(x).3.
Вычтем по модулю 2 остаток от деления (он должен быть не более r бит) из битовой строки, соответствующей многочлену x rM(x). Результат и будет передаваемымкадром, который мы будем называть многочленом T(x).На рис. 3.9 показаны вычисления для кадра 1101011111 и образующего многочленаG(x) = x4 + x + 1.Должно быть очевидно, что многочлен 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.Получатель делит принятый кадр с контрольной суммой на образующий многочленG(x), то есть он вычисляет [T(x) + E(x)]/G(x). T(x)/G(x) равно 0, поэтому результатвычислений просто равен E(x)/G(x). Ошибки, которые случайно окажутся кратнымиобразующему многочлену G(x), останутся незамеченными, остальные ошибки будутобнаружены.Если происходит единичная ошибка, то E(x) = x i, где i означает номер ошибочногобита. Если образующий многочлен G(x) содержит два или более члена, то E(x) никогда не будет делиться на него без остатка, поэтому будут обнаружены все единичныеошибки.В случае двух изолированных однобитовых ошибок E(x) = x i + x j, где i > j, этоможно также записать в виде: E(x) = x j(x i‑j + 1). Если предположить, что образующиймногочлен G(x) не делится на x, то достаточным условием обнаружения всех двойныхошибок будет неделимость на G(x) многочлена x k + 1 для любого k от 1 до максимального значения i – j, то есть до максимальной длины кадра.
Известны простые238 Глава 3. Канальный уровеньмногочлены с небольшими степенями, обеспечивающие защиту для длинных кадров.Например, многочлен x15 + x14 + 1 не является делителем для x k + 1 для любого k от1 до 32 768.Рис. 3.9. Пример вычисления CRCЕсли ошибка затронет нечетное количество бит в кадре, многочлен E(x) будет содержать нечетное число членов (например, x5 + x 2+ 1, но не x2 + 1). Интересно, чтов системе арифметических операций по модулю 2 многочлены с нечетным числом членов не делятся на x + 1. Если в качестве образующего выбрать многочлен, делящийсяна x + 1, то с его помощью можно обнаружить все ошибки, состоящие из нечетногоколичества инвертированных битов.И наконец, что наиболее важно, полиномиальный код с r контрольными битамибудет обнаруживать все пакеты ошибок длиной ≤ r.
Пакет ошибок длиной k можетбыть представлен в виде многочлена x i(x k‑1 +…+ 1), где i определяет, насколько далекоот правого конца кадра располагается пакет ошибок. Если образующий многочленG(x) содержит член x0, то x i не будет его множителем, поэтому если степень выражения в скобках меньше степени G(x), то остаток от деления никогда не будет нулевым.Если длина пакета ошибок равна r + 1, то остаток от деления будет нулевым тогдаи только тогда, когда пакет ошибок будет идентичен G(x).
По определению пакета илипоследовательности ошибок, его первый и последний биты должны быть равны 1, поэтому будет ли он совпадать с образующим многочленом, будет зависеть от r – 1 промежуточных битов. Если все комбинации считать равновероятными, то вероятностьтакой нераспознаваемой ошибки будет равна (1/2)r–1.3.3. Элементарные протоколы передачи данных на канальном уровне 239Также можно показать, что при возникновении пакета ошибок длиннее 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����������������������������������������������и др., 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).Остальные процессы канального уровня и процессы сетевого уровня — на центральномпроцессоре. Они являются частью операционной системы, причем программное обеспечение процесса канального уровня зачастую принимает форму драйвера устройства. Однако другие варианты реализации также возможны (например, три процесса,выполняющиеся на специальном устройстве, называемом сетевым ускорителем, илина ЦП с частотой, определяемой программно).
В действительности, оптимальная реализация в каждый период развития технологий своя и зависит от имеющихся технических возможностей. В любом случае, представление трех уровней в виде отдельныхпроцессов будет служить поддержанию концептуальной чистоты обсуждения, а такжеподчеркнет независимость уровней.240 Глава 3. Канальный уровеньРис. 3.10. Реализация физического, канального и сетевого уровнейДругим ключевым допущением будет то, что машина A хочет послать на машину Bдлинный поток данных, используя надежный, ориентированный на соединение сервис.Позднее мы рассмотрим случай, при котором одновременно машина B также хочетпослать данные на машину A.
Предполагается, что у машины A имеется бесконечныйисточник данных, готовых к отправке, и что ей никогда не требуется ждать готовностиданных. Когда канальный уровень машины A запрашивает данные, сетевой уровеньвсегда готов их ему предоставить. (Это ограничение также будет потом отброшено.)Также предполагается, что компьютеры не выходят из строя. При передаче могутвозникать ошибки, но не проблемы, связанные с поломкой оборудования или случайной перезагрузкой.При рассмотрении канального уровня пакет, передаваемый ему по интерфейсу сетевым уровнем, рассматривается как чистые данные, каждый бит которых должен бытьдоставлен сетевому уровню принимающей машины.
Тот факт, что сетевой уровеньпринимающей машины может интерпретировать часть этого пакета как заголовок, некасается канального уровня.Получив пакет, канальный уровень формирует из пакета кадры, добавляя заголовоки концевик (см. рис. 3.1). Таким образом, кадр состоит из внедренного пакета, некоторой служебной информации (в заголовке) и контрольной суммы (в концевике).
Затемкадр передается канальному уровню принимающей машины. Мы будем предполагатьналичие соответствующих библиотечных процедур, например to_physical_layer дляотправки кадра и from_physical_layer для получения кадра. Эти процедуры вычисляют и добавляют или проверяют контрольную сумму (обычно это делается аппаратно),так что протоколы, о которых мы говорим в этом разделе, могут не беспокоиться обэтом. Они могут применять, например, алгоритм циклических кодов, обсуждавшийсяв предыдущем разделе.Вначале получатель ничего не должен делать. Он просто сидит без дела, ожидая,что что-то произойдет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
