tanenbaum_seti_all.pages (525408), страница 63
Текст из файла (страница 63)
Чтобы показать, что никакой многочлсн с нечетным количеством члснов пе делится на х+ 1, предположим, что многочлсн Е(х) содержит нечетное количество членов и дслится пах + 1. Таким образом, Е(х) можст быть представлен в виде произведения Е(х) = (х+ 1)Я(х). Вычислим значение данного многочлсна для х = 1: Е(1) = (1 + 1)Я(1). Поскольку 1 + 1 = О (по модулю 2), то Е(1) должен быть равен О. Однако если многочлсн Е(х) содержит нсчстнос количество членов, то замена всех х на 1 будет всегда давать в результате 1, Следовательно, не существует многочлсна с нечетным количеством членов, делящегося на х + 1.
И наконец, что наиболсс важно, полнномиэльный код с г контрольными битами будет обнаруживать все пакеты ошибок длиной < и Пакет ошибок длиной Ф может быть представлен в виде многочлена х'(х" ' +...+ 1), где 1 опрсделяст, насколько далеко от правого конца кадра располагается пакет ошибок. Если образующий многочлен С(х) содержит член хо, то х' нс будет его множителем, поэтому если степень выражения в скобках меньше стспснн С(х), то остаток от дслсния никогда не будет нулевым. Если длина пакета ошибок равна г+ 1, то остаток от деления будет нулевым тогда и только тогда, когда пакет ошибок будет идснтичсн С(х).
По определению пакета ошибок, сто первый и последний биты должны быть равны 1, поэтому бу- 240 Глава 3. Уровень передачи данных дет ли он совпадать с образующим многочленом, будет зависеть от г — 1 промежуточных битов. Если все комбинации считать равновероятпыми, то вероятность такой нераспознаваемой ошибки будет равна (1/2)' ', Также можно показать, что при возникновении пакета ошибок длиннее г+! битов или нескольких коротких паке~он вероятность пропуска ошибки составляет (1/2)" при условии, что все комбинации битов равновероятны. Некоторые образующие многочлепы стали международными стандартами. Вот, например, полипом, использующийся в 1ЕЕЕ 802: хм е хм + хлз -» хм е хм + хи + хи + хм + хл + х' + хз + х4 + х2 + х~ + 1.
Среди других его полезных свойств имеется и такое: этот многочлен позволяет определяться лк>бые пакеты ошибок длиной нс более 32 бит и пакеты, дающие нечетное шсло бит. Хотя алгоритм вычисления контролыюй суммы может показаться сложным, Питерсон (Рсгегзоп) и Браун (Вгожп) в 1961 году показали, что может быть создана простая схема для аппаратной проверки и подсчета контрольных сумм на основе сдвпгового регистра. Эта схема до сих пор применяется почти во всей аппаратуре ЛВС, а иногда и двухабонеитских систем.
В течение десятилетий предполагалось, что кадры, контрольные суммы которых вычисляются, содержат случайныс биты. Все исследования алгоритмов подсчета контрольных сумм основывались иа этом предположении. Недавние исследования реальных данных показали, что зти предположения были совершенно неверными.
Как следствие, при некоторых обстоятельствах вероят~юсть прохождения необнаруженных ошибок оказалась значительно выше, чем считалось ранее (Раггг1г1яе и др., 1995). Элементарные протоколы передачи данных Знакомство с протоколами мы начнем с рассмотрения трех протоколов возрастающей сложности. Симулятор этих и следующих протоколов заинтересованные читатели могут найти на всб-сайте (см. предисловие). Прежде чем приступить к изучению протоколов, полезно высказать некоторые допу»пения, лежащие в основе данной модели связи. Для начала мы предполагаем, что па физическом уровне, уровне передачи данных и сетевом уровне находятся независимые процессы, общающиеся с помощью передачи друг другу сообщений.
Во многих случаях процессы физического уровня и уровня передачи данных будут работать на процессоре внутри специальной сетевой микросхемы ввода-вывода, а процесс сетевого уровня — на центральном процессоре. Однако другие варианты реализации также возможны (например, три процесса внутри одной микросхемы ввода-вывода; физический уровень и уровень передачи данных, вызываемые как процедуры процессом сетевого уровня, и т. д.). В любом случае, представление трех уровней в виде отдельных процессов будет служить поддержанию концептуальной чистоты обсуждения, а также подчеркнет независимость уровней.
Элементарные протоколы передачи данных 241 Другим ключевым допущением будет то, что машина А хочет послать на машину В длинный поток данных, используя надежный ориентированный на соединение сервис. Позднее мы рассмотрим случай, при котором одновременно машина В также хочет послать данные на машину А. Предполагается, что у машины А имеется бесконечный источник данных, готовых к отправке, и что ей никогда не требуется ждать готовности данных. Когда уровень передачи данных машины А запрашивает данные, сетевой уровень всегда готов их ему предоставить. (Это ограничение также будет потом отброшено.) Также предполагается, что компьютеры не выходят из строя. При передаче могут возникать ошибки, но не проблемы, связанные с поломкой оборудования или случайным сбросом.
При рассмотрении уровня передачи данных пакет, передаваемый ему по интерфейсу сетевым уровнем, рассматривается как чистые данные, каждый бит которых должен бьп ь доставлен сетевому уровню принимающей машины. Тот факт, что сетевой уровень принимающей машины может интерпретировать часть этого пакета как заголовок, пе касается уровня передачи данных.
Получив пакет, уровень передачи данных формирует из пакета кадры, добавляя заголовок и концевик пакета передачи данных (см. рис. ЗА). Таким образом, кадр состоит из внедренного пакета, некоторой служебной информации (в заголовке) и контрольной суммы (в концевике). Затем кадр передается уровню передачи данных принимающей машины. Мы будем прсдполагать наличие соотвстствуюгцих библиотечных процедур, например, го рйуюсз1 1ауег для отправки кадра и ггоа рйую са1 1ауег для получения кадра. Передающая аппаратура вычисляет и добавляет контрольную сумму (создавая концевик), так что уровень передачи данных может нс беспокоиться об этом. Например, может использоваться алгоритм циклических кодов, обсуждавшийся в предыдущем разделе.
Вначале получатель ничего не должен делать. Он просто сидит без дела, ожидая, что что-то произойдет. В приводимых в данной главе примерах протоколов ожидание событий уровнем передачи данных обозначается вызовом процедуры нз1Г тог етел11ьечепс). Эта процедура возвращает управление, только когда чтото происходит (например, прибывает кадр). При этом переменная ечелг сообшает, что именно случилось. Наборы возможных событий отличаются в разных протоколах и поэтому будут описываться для каждого протокола отдельно. Следует заметить, что в действительности уровень передачи данных не находится в холостом цикле ожидания событий, как мы предположили, а получает прерывание, когда это событие происходит. При этом он приостанавливает свои текущие процессы и обрабатывает пришедший кадр, Тем не менее, для простоты мы проигнорируем эти детали и предположим, что уровень передачи данных все свое время посвящает работе с одним каналом. Когда приемная машина получает кадр, аппаратура вычисляет его контрольную сумму.
Если она неверна (то есть при передаче возникли ошибки), то уровень передачи данных получает соответствующую информацию (еоелг=скзшп егг). Если кадр прибывает в целости, уровню передачи данных об этом также сообщается (еоелг=ггате агг1на1), после чего он может получить этот кадр у физического уровня с помощью процедуры тгоя рйуз1са1 1зуег. Получив неповрежденный 242 Глава 3. Уровень передачи данных кадр, уровень передачи данных проверяет управляющую информацию, находящуюся в заголовке кадра, и если всс в порядке, часть этого кадра передается сетевому уровню. Заголовок кадра не передается сетевому уровню ни при каких обстоятельствах. Для запрета передачи сетевому уровню любой части заголовка калра есть веская причина: поддержание полного разделения сетевого уровня и уровня передачи данных. До тех пор, пока сетевой уровень ничего не знает о формате кадра и протоколе уровня передачи данных, изменения формата и протокола не потребуют изменений программного обеспечения сетевого уровня.
Поддержание строгого интерфейса между сетевым уровнем и уровнем передачп данных значитсльно упрощает разработку программ, так как протоколы различных уровней могут развиваться независимо. В листинге ЗА показаны некоторые объявления (на языке С), общие для многих протоколов, обсуждаемых далее. Определены пять структур данных: Ьоо1еал, зец пг, расхег, 1гаве К~не и тгаае. Тин Ьоо1еал представляет собой персчнсляемый тип, переменныс которого могут принимать значения сгибе или 1з1зе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
