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