Таненбаум Э. Компьютерные сети

Подождите немного. Документ загружается.

274 Глава 3. Уровень передачи данных

Петри, состоящая из двух позиций, Аи В, изображенных в виде кружков. В дан-

ный момент система находится в состоянии А, отмеченном маркером (жирной

точкой) в позиции А. Переход обозначается вертикальной или горизонтальной

чертой. У каждого перехода может быть ноль или несколько входящих дуг, иду-

щих от своих исходных позиций, а также ноль или несколько исходящих дуг, на-

правляющихся к выходным позициям.

Рис. 3.15. Сеть Петри из двух позиций и двух переходов

Переход называется разрешенным, если имеется хотя бы один маркер на его

входных позициях. Любой разрешенный переход может возбуждаться по жела-

нию, удаляя маркер со всех исходных позиций и размещая их на всех выходных

позициях. Количество маркеров на исходных и выходных позициях не обязано

совпадать. Если разрешены два или более переходов, произойти может любой из

них. Благодаря недетерминированности выбора перехода, который произойдет,

сети Петри могут использоваться для моделирования протоколов. Сеть Петри,

изображенная на рис. 3.15, детерминирована и может применяться для модели-

рования любого двухфазного процесса (например, поведения ребенка: поел, по-

спал, опять поел, опять поспал, и т. д.). Как и при любом моделировании, лиш-

ние детали игнорируются.

На рис. 3.16 показана сетевая модель Петри, соответствующая графу, описан-

ному в листинге 3.4. В отличие от конечного автомата, здесь нет составных со-

стояний. Состояния отправителя, получателя и канала изображаются отдельно.

Переходы 1 и 2 соответствуют обычной и повторной (по тайм-ауту) передаче

кадра 0. Переходы 3 и 4 означают то же самое, но для кадра 1. Переходы 5, 6 и 7

соответствуют потере кадра 0, подтверждения и кадра 1. Переходы 8 и 9 означа-

ют приход к получателю кадра с неверным номером. Переходы 10 и 11 обознача-

ют получение принимающей машиной следующего кадра и передачу его сетево-

му уровню.

Сети Петри, так же как и конечные автоматы, могут применяться для обнару-

жения ошибок в протоколах. Например, если какая-нибудь последовательность

переходов будет включать переход 10 дважды без перехода 11 между ними, это

будет означать, что протокол неверен. Концепция тупиков в сети Петри также

мало отличается от своего аналога в модели машины конечных состояний.

Сети Петри могут представляться в виде набора алгебраических формул, на-

поминающих грамматические правила. Каждому переходу соответствует одно

правило грамматики. Каждое такое правило описывает входные и выходные по-

зиции перехода. Поскольку на рис. 3.16 изображено И переходов, то и граммати-

ка имеет 11 правил. Пронумеруем правила таким образом, чтобы каждое из них

соответствовало переходу с тем же номером. Грамматика сети Петри, изображен-

ной на рис. 3.16, представлена ниже:

Верификация протоколов 275

АС

1: BD

2: A-

3: AD

4: В -> В

5: С ->

6: D -*

7: Е ->

8: CF -» DF

9: EG -> DG

10:

CG -> DF

11:

EF -> DG

Передача

кадра О

Ожидания

подтверждения О

Передача

кадра 1

Ожидания

подтверждения 1

С: Кадр 0 на линии

D: Подтверждение на линии

Е: Кадр 1 на линии

Обработка

кадра О

Ожидание

кадра 1

Обработка

кадра 1

Ожидание

кадра 0

7 Потеря

Состояния

отправителя

Состояние

канала

Состояние

получателя

Рис. 3.16. Сетевая модель Петри для протокола 3

Интересно, что нам удалось компактно описать довольно сложный протокол

набором из 11 элементарных правил грамматики, легко реализуемых компью-

терной программой.

Текущее состояние сети Петри представляется неупорядоченным набором по-

зиций, каждая из которых появляется в наборе столько раз, сколько фишек в ней

имеется. Любое правило из грамматики, имеющее левую часть, может активиро-

ваться, удаляя свои левые позиции из текущего состояния сети и добавляя свои

правые (выходные) позиции к текущему состоянию. Текущее состояние (марки-

ровка) сети, изображенной на рис. 3.16, — ACG, поэтому, например, правило 10

276 Глава 3. Уровень передачи данных_

(CG —> DF) может быть применено, а правило 3 {AD -» BE) — нет, потому что D

не имеет маркера.

Примеры протоколов передачи данных

В следующих разделах мы рассмотрим некоторые широко используемые прото-

колы передачи данных. Первый из них, классический бит-ориентированный про-

токол HDLC, часто употреблялся во многих сетях. Второй, РРР, — это протокол

уровня передачи данных, используемый при подключении к Интернету домаш-

них компьютеров.

HDLC — высокоуровневый протокол

управления каналом

В данном разделе мы рассмотрим группу тесно связанных друг с другом протоко-

лов, немного устаревших, но все еще широко применяемых в сетях. Все они про-

изошли от одного протокола передачи данных, применявшегося в разработанных

компанией IBM мейнфреймах, — этот протокол называется SDLC (Synchronous

Data Link Control — синхронное управление каналом). После разработки прото-

кола SDLC корпорация IBM представила его на рассмотрение институтов ANSI

и ISO для утверждения в качестве стандарта США и международного стандарта

соответственно. ANSI модифицировал протокол в ADCCP (Advanced Data

Communication Control Procedure — усовершенствованная процедура управле-

ния информационным обменом), a ISO переделала его в HDLC (High-level Data

Link Control — высокоуровневый протокол управления каналом). После этого

протокол был принят комитетом CCITT, который адаптировал HDLC для своего

протокола доступа к каналу LAP (Link Access Procedure — процедура доступа к

каналу), являющегося частью стандарта сетевого интерфейса Х.25, однако затем

снова изменил его на LAPB, повысив его совместимость с более поздней версией

HDLC. Что хорошо в стандартах, так это то, что у вас всегда есть из чего выбрать.

Если же вас не устраивает ни один из имеющихся стандартов, вы можете просто

подождать появления новой модели в новом году.

В основе всех этих протоколов лежат одни и те же принципы. Все они являют-

ся бит-ориентированными, и во всех применяется битовое заполнение, обеспечи-

вающее прозрачность данных. Они различаются только в незначительных, но, тем

не менее, вызывающих раздражение деталях. Последующее обсуждение бит-ори-

ентированных протоколов нужно рассматривать как общее введение. Специфиче-

ские детали протоколов приводятся в соответствующих официальных описаниях.

Во всех бит-ориентированных протоколах используется формат кадра, пока-

занный на рис. 3.17. Поле Address (адрес) чрезвычайно важно для линий с не-

сколькими терминалами, где оно используется для идентификации одного из

терминалов. В двухточечных сетях это поле иногда используется, чтобы отли-

чать команды от ответов.

Примеры протоколов передачи данных 277

Поле Control (управляющей информации) используется для хранения поряд-

ковых номеров, подтверждений и других служебных данных, как будет показано

далее.

01111110

Адрес

Управляющее

поле

i 0

Данные

Контрольная

сумма

0 1111110

Биты

Рис. 3.17. Формат кадра бит-ориентированных протоколов

Поле Data (данные) может содержать произвольную информацию. Оно мо-

жет быть любой длины, хотя эффективность контрольной суммы снижается с

увеличением длины кадра из-за увеличения вероятности многочисленных паке-

тов ошибок.

Поле Checksum (контрольная сумма) является разновидностью циклического

избыточного кода, который мы рассматривали в разделе «Коды с обнаружением

ошибок».

В качестве заголовка и концевика кадра используется флаговый байт

(01111110). В линиях «точка — точка», которые в текущий момент времени про-

стаивают, флаговые последовательности передаются постоянно. Кадр минималь-

ного размера состоит из трех полей, занимающих в общей сложности 32 бита, не

считая флаги в начале и в конце.

Все кадры можно разделить на три категории: информационные, суперви-

зорные и ненумерованные. Содержимое поля Control для этих трех типов кад-

ров показано на рис. 3.18. Протокол использует скользящее окно с 3-битовым

порядковым номером. В каждый момент времени в сети может находиться не бо-

лее семи неподтвержденных кадров. Поле Seq на рис. 3.18, а содержит порядко-

вый номер кадра. Поле Next является пересылаемым вместе с кадром подтвер-

ждением. Однако все протоколы придерживаются соглашения о том, что вместо

номера последнего правильно принятого кадра в поле Next пересылается номер

первого не принятого кадра (то есть следующего ожидаемого кадра). Впрочем,

номер кадра, используемого для подтверждения, не принципиален. Важно лишь,

чтобы все участники придерживались одного и того же соглашения.

Биты

Seq

P/F

Туре

P/F

Туре

P/F

Modifier

Рис. 3.18. Управляющее поле: информационного кадра (а); супервизорного кадра (б);

ненумерованного кадра (в)

278 Глава 3. Уровень передачи данных

Бит P/F означает Poll/Final (Опрос/Финальный). Он используется, когда

компьютер (или концентратор) опрашивает группу терминалов. В случае значе-

ния Р компьютер предлагает терминалу посылать данные. Во всех кадрах, кроме

последнего, посылаемых терминалом, бит P/F устанавливается в Р. В последнем

кадре этот бит устанавливается в F.

Некоторые протоколы используют бит P/F, чтобы заставить другую машину

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

Этот бит также изредка используется в ненумерованных кадрах.

Тип супервизорного кадра указывается с помощью значения поля Туре. Если

Туре = 0, значит, данный кадр является подтверждением. Он официально назы-

вается RECEIVE READY (к приему готов). Такой кадр сообщает номер следующего

ожидаемого кадра и применяется при отсутствии попутного потока данных для

передачи подтверждения.

Туре = 1 является признаком отрицательного подтверждения, официально на-

зывающегося REJECT (отказ). Он применяется для сообщения об обнаружении

ошибки передачи. Поле Next в этом случае содержит номер первого неверно по-

лученного кадра (то есть первого кадра, который следует переслать повторно).

Отправитель должен переслать повторно все неподтвержденные кадры, начиная

с кадра с номером Next. Эта стратегия больше напоминает протокол 5, нежели

протокол 6.

Туре - 2 означает RECEIVE NOT READY (к приему не готов). При этом, как и в слу-

чае RECEIVE READY, подтверждается прием всех кадров вплоть до Next-i, однако от-

правителю сообщается, что передачу следует приостановить. Сигнал неготовно-

сти к приему предназначен не для использования в качестве альтернативы схеме

скользящих окон, а для обозначения наличия у получателя каких-либо времен-

ных проблем, например отсутствия свободной памяти в буферах. Когда получа-

тель сможет продолжить работу, он пошлет сигнал готовности, отказа или дру-

гой управляющий кадр.

Туре = 3 означает SELECTIVE REJECT (выборочный отказ). Такой байт представ-

ляет собой запрос повторной передачи только указанных кадров. В этом он боль-

ше похож на протокол 6, чем на протокол 5, и поэтому наиболее полезен, когда

размер окна отправителя не превышает половины количества используемых по-

рядковых номеров. Таким образом, если получатель хочет сохранить в буфере

несвоевременные кадры для последующего использования, он может запросить

повторную передачу любого кадра с помощью SELECTIVE REJECT. Протоколы

HDLC и ADCCP поддерживают этот тип кадра, а протоколы SDLC и LAPB —

нет, то есть в этих протоколах нет команды выборочного отказа, а кадры типа 3

не используются.

Третий класс кадров составляют ненумерованные кадры. Иногда они приме-

няются для служебных целей, но могут переносить и данные, когда требуется

ненадежный, не требующий соединения сервис. В отличие от предыдущих двух

классов, в которых различные бит-ориентированные протоколы были почти иден-

тичными, в вопросе использования ненумерованных кадров они очень сильно

различаются. Для обозначения типа кадра зарезервировано 5 бит, однако исполь-

зуются значительно меньше, чем 32 возможных комбинации.

Примеры протоколов передачи данных

279

Все протоколы поддерживают команду DISC (DISConnect — прервать связь),

позволяющую предупредить, что машина скоро будет выключена (например, для

профилактического обслуживания). Также имеется команда, позволяющая ма-

шине, только что вернувшейся в подключенный режим (on-line), заявить о своем

присутствии и принудительно обнулить все порядковые номера. Эта команда на-

зывается SNRM (Set Normal Response Mode — установить нормальный режим отве-

та). К сожалению, этот «нормальный режим» является чем угодно, но не нормой.

Это несбалансированный (то есть асимметричный) режим, при котором один ко-

нец линии является ведущим (master), а другой — ведомым (slave). Команда SNRM

появилась еще в те времена, когда обмен данными означал общение примитив-

ного терминала с компьютером, которое, конечно, было асимметричным. Чтобы

лучше учитывать ситуацию равноправных партнеров, в протоколы HDLC и LAPB

была добавлена команда SABM (Set Asynchronous Balanced Mode — установить

асинхронный сбалансированный режим), которая инициализирует линию и объ-

являет равенство сторон. Кроме того, в этих протоколах имеются дополнитель-

ные команды SABME и SNRME, которые отличаются от SABM и SNRM только

тем, что вводят расширенный формат кадров с 7-битовым порядковым номером

вместо 3-битового.

Третьей командой, поддерживаемой всеми этими протоколами, является FRMR

(FRaMe Reject — отклонить кадр), применяющаяся, когда приходит кадр с вер-

ной контрольной суммой, но недопустимой семантикой. Например, супервизор-

ный кадр типа 3 в протоколе LAPB, кадр длиной менее 32 бит, недопустимый

управляющий кадр или подтверждение кадра, находящегося вне пределов окна

и т. д. Данные включают управляющее поле неправильного кадра, параметры ок-

на и набор битов, указывающих тип ошибки.

Управляющие кадры могут быть повреждены или потеряны так же, как и ин-

формационные кадры, поэтому им также нужны подтверждения. Для этой цели

предназначен специальный служебный кадр, называемый UA (Unnumbered

Acknowledgement — ненумерованное подтверждение). Поскольку неподтвержден-

ным может быть только один управляющий кадр, то не возникает вопроса о том,

какой именно служебный кадр подтверждается.

Остальные управляющие кадры занимаются инициализацией, опросом и со-

общением состояния. Есть также управляющий кадр, который может содержать

произвольную информацию, UI (Unnumbered Information). Эта информация не

передается на сетевой уровень, но получается и обрабатывается самим уровнем

передачи данных.

Несмотря на широкое распространение, протокол HDLC имеет большое ко-

личество недостатков. Обсуждение ряда проблем, связанных с этим протоколом,

см. в (Fiorini и др., 1994).

Уровень передачи данных в Интернете

Интернет состоит из отдельных машин (хостов и маршрутизаторов) и связываю-

щей их коммуникационной инфраструктуры. В пределах одного здания для со-

единения широко применяются локальные сети, но на больших территориях ин-

280 Глава 3. Уровень передачи данных

фраструктура строится на основе выделенных линий, соединяющих отдельные

машины по принципу «точка —точка». Локальные сети будут рассматриваться в

главе 4, здесь же мы обсудим протоколы передачи данных, используемые для ли-

ний «точка — точка» в Интернете.

На практике соединение «точка — точка» используется прежде всего в двух

ситуациях. Во-первых, у тысяч организаций есть по одной или по несколько ло-

кальных сетей, в каждой из которых есть несколько хостов (персональных компь-

ютеров, рабочих станций пользователя, серверов и т. д.) наряду с маршрутизато-

рами (или функционально близких к ним мостов). Маршрутизаторы часто

соединяются магистральной локальной сетью. Обычно вся связь с внешним ми-

ром осуществляется через один или два маршрутизатора, связанных выделенны-

ми линиями «точка—точка» с удаленными маршрутизаторами. Именно эти мар-

шрутизаторы вместе с выделенными линиями образуют подсети, из которых

состоит Интернет.

Еще одна важная роль, которую соединения «точка — точка» играют в Интер-

нете, заключается в том, что они связывают миллионы индивидуальных пользо-

вателей с помощью модемов и телефонных линий. Обычно пользователь дозва-

нивается со своего домашнего компьютера до поставщика услуг Интернета или,

как его еще называют, провайдера, и работает как полноценный интернет-хост.

Этот метод отличается от использования выделенной линии между персональ-

ным компьютером и маршрутизатором только лишь тем, что, когда пользователь

заканчивает сеанс связи, соединение прерывается. Домашний персональный

компьютер, звонящий поставщику услуг Интернета, изображен на рис. 3.19. Мо-

дем показан в данном случае как внешнее устройство, однако современные ком-

пьютеры могут быть укомплектованы и внутренними модемами.

Дом пользователя

I Персональный

компьютер

Офис поставщика услуг Интернета

Модемы

Клиентский процесс,

использующий TCP/IP!

Телефонная

линия

ТСРЛР-соединение,

использующее SLIP

или РРР

Маршрутизатор Процесс

маршрутизации

Рис. 3.19. Домашний персональный компьютер, действующий как хост Интернета

Как для соединения двух маршрутизаторов по выделенной линии, так и для

соединения маршрутизатора с хостом требуется протокол, который бы зани-

мался формированием кадров, обработкой ошибок и другими функциями уров-

ня передачи данных, рассматривавшимися в данной главе. Одним из таких про-

Примеры протоколов передачи данных 281

токолов, широко распространенным в Интернете, является РРР. Рассмотрим

его.

РРР — протокол двухточечного соединения

В Интернете двухточечные протоколы применяются очень часто в самых разных

случаях, включая обеспечение соединения между маршрутизаторами, между поль-

зователями и провайдерами. Обсуждаемый далее протокол называется РРР

(Point-to-Point Protocol — протокол передачи от точки к точке), описан в

RFC 1661 и доработан в некоторых более поздних документах RFC (например,

RFC 1662 и 1663). Протокол РРР выполняет обнаружение ошибок, поддержива-

ет несколько протоколов, позволяет динамически изменять IP-адреса во время

соединения, разрешает аутентификацию, а также имеет ряд других свойств.

Протокол РРР обеспечивает следующий набор методов:

1. Метод формирования кадров, однозначно обозначающий конец одного кадра

и начало следующего. Формат кадров также обеспечивает обнаружение оши-

бок.

2. Протокол управления каналом, позволяющий устанавливать каналы связи,

тестировать их, договариваться о параметрах их использования и снова от-

ключать их, когда они не нужны. Этот протокол называется LCP (Link Cont-

rol Protocol). Он поддерживает синхронные и асинхронные линии, бит- и байт-

ориентированное кодирование.

3. Способ договориться о параметрах сетевого уровня, который не зависит от

используемого протокола сетевого уровня. Для каждого поддерживаемого се-

тевого уровня этот метод должен иметь свой сетевой протокол управления

(NCP, Network Control Protocol).

Чтобы посмотреть, как все это работает вместе, рассмотрим типичный сцена-

рий, когда домашний пользователь звонит поставщику услуг Интернета, чтобы

превратить тем самым свой домашний компьютер во временный хост. Сначала

персональный компьютер звонит через модем на маршрутизатор провайдера. Пос-

ле того, как,модем маршрутизатора ответит на звонок и установит физическое

соединение, персональный компьютер посылает маршрутизатору серию LCP-na-

кетов в поле данных пользователя одного или нескольких РРР-кадров. Эти па-

кеты и ответы на них определяют параметры протокола РРР.

После того как обе стороны согласовывают параметры, посылается серия NCP-

пакетов для настройки сетевого уровня. Обычно персональный компьютер жела-

ет запустить стек протоколов TCP/IP, для чего ему нужен IP-адрес. На всех поль-

зователей IP-адресов не хватает, поэтому обычно у каждого поставщика услуг

Интернета имеется целый набор таких адресов, и он динамически назначает их

каждому присоединившемуся персональному компьютеру на время сеанса свя-

зи. Если у провайдера есть п IP-адресов, он может одновременно подключить к

Интернету до п машин, однако общее количество его клиентов может быть во

много раз больше. Для назначения IP-адреса используется протокол NCP для IP.

После этого персональный компьютер фактически становится хостом Интер-

нета и может посылать и принимать IP-пакеты так же, как и постоянные хосты.

282 Глава 3. Уровень передачи данных

Примеры протоколов передачи данных Z83

Когда пользователь заканчивает сеанс связи, NCP используется, чтобы разорвать

соединение сетевого уровня и освободить IP-адрес. Затем LCP используется для

разрыва соединения уровня передачи данных. Наконец, компьютер дает модему

команду повесить трубку, чем освобождает линию на физическом уровне.

Чтобы не изобретать велосипед, был выбран формат кадра РРР, близкий к

формату кадра HDLC. В отличие от бит-ориентированного протокола HDLC, РРР

является байт-ориентированным. В частности, в РРР применяется символьное

заполнение на модемных телефонных линиях, поэтому все кадры состоят из це-

лого числа байтов. С помощью протокола РРР невозможно послать кадр, состоя-

щий из 30,25 байт, как это можно было сделать в протоколе HDLC. Кадры РРР

могут посылаться не только по телефонным линиям, но и по сети SONET или по

настоящим бит-ориентированным HDLC-линиям (например, по линиям, соеди-

няющим маршрутизаторы). Формат кадра РРР показан на рис. 3.20.

Байты

1 или 2 Переменный 2 или 4

Flag

01111110

Address

11111111

Control

00000011

Protocol

•и-

Payload

•И-

Checksum

Flag

01111110

Рис. 3.20. Полный формат кадра РРР для работы в ненумерованном режиме

Все РРР-кадры начинаются со стандартного флагового байта протокола

HDLC (01111110). Если такой байт встречается в поле данных, то применяется

символьное заполнение. Следом за ним идет поле Address (адрес), которому все-

гда присваивается двоичное значение 11111111, что означает, что все станции

должны принимать этот кадр. Использование такого адреса позволяет избежать

необходимости назначения адресов передачи данных.

За полем адреса следует поле Control, его значение по умолчанию равно

00000011. Это число означает ненумерованный кадр. Другими словами, РРР по

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

номеров и подтверждений. В зашумленных каналах, например при беспроводной

связи, может применяться надежная передача с порядковыми номерами. Детали

этого описаны в RFC 1663, но на практике такой способ применяется редко.

Так как в конфигурации по умолчанию поля Address и Control являются кон-

стантами, протокол LCP предоставляет возможность двум сторонам договориться

0 возможности пропускать оба поля и сэкономить, таким образом, по 2 байта на

кадр.

Четвертое поле кадра РРР — Protocol (протокол). Оно определяет тип пакета,

содержащегося в поле данных (Payload). Определены коды для протоколов LCP,

NCP, IP, IPX, AppleTalk и др. Номера протоколов сетевого уровня, например, IP,

IPX, OSI CLNP, XNS, начинаются с бита 0. С бита 1 начинаются коды, исполь-

зуемые для переговоров об использовании других протоколов. К ним относятся

LCP, а также различные протоколы NCP для каждого поддерживаемого прото-

кола сетевого уровня. Размер поля Protocol по умолчанию составляет 2 байта, од-

нако путем переговоров с помощью LCP этот размер может быть уменьшен до

1 байта.

Поле Payload (поле полезной нагрузки, или поле данных) может быть пере-

менной длины, вплоть до некоего оговоренного максимального значения. Если

размер не оговорен во время установки соединения при помощи LCP, то по

умолчанию он может составлять до 1500 байт. При необходимости данные поль-

зователя могут дополняться специальными символами.

Следом за полем Payload располагается поле Checksum (контрольная сумма),

которое в обычном состоянии занимает 2 байта, но в случае необходимости по

договоренности может занимать 4.

Итак, РРР является механизмом формирования кадров, поддерживающим

различные протоколы, которым можно пользоваться при модемных соединени-

ях, в последовательных по битам линиях HDLC, сетях SONET и других физиче-

ских средах. РРР поддерживает обнаружение ошибок, переговоры о параметрах,

сжатие заголовков, а также, по желанию, надежное соединение с использованием

кадров HDLC.

Рассмотрим теперь способы установления и разрыва соединения. Упрощен-

ная диаграмма на рис. 3.21 показывает фазы, через которые проходит линия свя-

зи при ее установлении, использовании и разъединении. Эта последовательность

применима как к соединению с помощью модемов, так и к соединениям между

маршрутизаторами.

Носитель

обнаружен

Обе стороны договорились

о параметрах

Аутентификация

успешная

Носитель

освобожден

Готово

Конфигурация

NCP

Рис. 3.21. Упрощенная фазовая диаграмма установки и разрыва соединения

Начальное состояние протокола таково: линия отключена (DEAD), физический

носитель отсутствует, соединения на физическом уровне не существует. После того

как физическое соединение установлено, линия переходит в состояние ESTABLISH

(установка). В этот момент начинаются переговоры о параметрах с помощью про-

токола LCP. При успешном результате переговоров линия переходит в фазу

284 Глава 3. Уровень передачи данных

Резюме

285

AUTHENTICATE (идентифицировать). Теперь обе стороны по желанию могут

проверить, кем является собеседник. При переходе к фазе NETWORK (сеть)

включается соответствующий протокол NCP для настройки сетевого уровня. Ес-

ли настройка проходит успешно, линия переходит в фазу OPEN (открытая), при

этом может осуществляться передача данных. Когда передача данных закончена,

линия переходит к фазе TERMINATE (завершение), а затем снова в состояние

DEAD (отключена), когда физическое соединение разрывается.

Протокол LCP используется для переговоров об используемых параметрах

уровня передачи данных во время установочной фазы (ESTABLISH). Причем в

его ведении находятся отнюдь не сами обсуждаемые параметры, а механизм пе-

реговоров. Он предоставляет способ инициировать процесс подачи предложения

и поддерживает ответный процесс принятия или отказа от поданного предложе-

ния целиком или частично. Кроме того, он предоставляет методы проверки каче-

ства линии, чтобы договаривающиеся процессы могли решить, стоит ли вообще

устанавливать соединение на этой линии. Наконец, протокол LCP позволяет от-

ключить линию, если она больше не используется.

В RFC 1661 определены одиннадцать типов LCP-пакетов. Они приведены

в табл. 3.1. Четыре первых типа, имена которых содержат слово Configure- (кон-

фигурировать), позволяют инициатору переговоров (I) предложить значения па-

раметров, а ответчику (R) принять или отказаться от них. В последнем случае

ответчик может выдвинуть встречное заявление о том, что он вообще не хочет

вести переговоры. Обсуждаемые параметры и их значения являются частью

LCP-пакета.

Коды, начинающиеся со слова Terminate (завершить), используются для от-

ключения линии, когда она перестает использоваться. Коды Code-reject (код от-

вергнут) и Protocol-reject (протокол отвергнут) применяются ответчиком для со-

общения, что он получил что-то непонятное. Это может означать, что произошла

ошибка при передаче пакета или инициатор и ответчик используют разные вер-

сии протокола LCP. Пакеты, названия которых начинаются с Echo (эхо), приме-

няются для проверки качества линии. И наконец, Discard-request используется

для отладки. Если ему удается пройти по линии, он просто игнорируется ответ-

чиком, чтобы не мешать человеку, осуществляющему отладку.

Таблица 3.1. Типы LCP-пакетов

Имя

Направление

Описание

Имя

Направление

Описание

Configure-request

Configure-ack

Configure-nak

Configure-reject

Terminate-request

Terminate-ack

Code-reject

Protocol-reject

Предложение о параметрах

и их значениях

Все предложенные параметры приняты

Некоторые параметры не приняты

Некоторые параметры не обсуждаются

Запрос на отключение линии

Согласие на отключение линии

Получен неизвестный запрос

Запрошен неизвестный протокол

Echo-request

Echo-reply

Discard-request

Запрос на обратную пересылку кадра

Согласие на обратную пересылку кадра

Предложение проигнорировать этот кадр

(для тестирования)

Обсуждаемые параметры могут включать установку максимального размера

поля полезной нагрузки информационных кадров, разрешение аутентификации,

выбор используемого протокола, разрешение на проверку качества линии во

время нормальной работы, а также выбор различных параметров сжатия заго-

ловков.

О протоколах NCP можно рассказать не так уж много. Каждый из них исполь-

зуется со своим сетевым протоколом и позволяет осуществлять переговоры о па-

раметрах, специфичных для своего протокола. Например, для протокола IP важ-

нейшим свойством является возможность назначения динамического IP-адреса.

Резюме

Задачей уровня передачи данных является преобразование необработанного по-

тока битов, поступающего с физического уровня, в поток кадров, которые может

использовать сетевой уровень. Используются различные методы кадрирования,

включая подсчет символов, символьное и битовое заполнение. Протоколы уров-

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

осуществляется для повторной передачи потерянных или испорченных кадров.

Во избежание опережения медленного приемника быстрым отправителем приме-

няется контроль потока. Механизм скользящих окон широко используется для

объединения контроля ошибок и управления потоком.

Протоколы скользящего окна можно классифицировать по размеру окна при-

емника и отправителя. Для протокола с ожиданием оба окна имеют единичный

размер. Когда размер окна отправителя больше 1 — например, так делают для

уменьшения затрат времени на ожидание подтверждения при большой задержке

распространения сигнала по линии, — получатель может либо отвергать все кад-

ры, кроме ожидаемого, либо накапливать поступающие кадры в буфере до тех

пор, пока они не понадобятся.

Мы рассмотрели в этой главе ряд примеров протоколов. Протокол 1 предна-

значен для идеальной среды передачи, в которой отсутствуют ошибки, и для

идеального приемника, который может обработать входящий поток любого раз-

мера. В протоколе 2 все еще предполагается, что среда не порождает ошибки при

передаче, но в данном протоколе уже присутствует контроль потока. Протокол 3

обрабатывает ошибки при помощи порядковых номеров кадров и алгоритма с

ожиданием. Протокол 4 предоставляет возможность двунаправленной передачи

и использует концепцию комбинированных пакетов. В протоколе 5 используют-

ся скользящие окна с возвратом на п. Наконец, протокол 6 отличается примене-

нием метода выборочного повтора и отрицательных подтверждений (NAK).

286 Глава 3. Уровень передачи данных

Протоколы можно моделировать разными способами, позволяющими проде-

монстрировать их корректность (или ее отсутствие). Модели конечных автома-

тов и сетей Петри используются именно для этих целей.

Многие сети построены на бит-ориентированных протоколах уровня переда-

чи данных — SDLC, HDLC, ADCCP или LAPB. Все они используют флаговые

байты, ограничивающие кадры, и битовое заполнение, предотвращающее слу-

чайное появление флаговых байтов среди данных пользователя. Также все они

используют метод скользящего окна для контроля потока. В Интернете в качест-

ве основного протокола линий «точка — точка» используется РРР.

Вопросы

1. Сообщение верхнего уровня разбито на 10 кадров, у каждого из которых шанс

дойти до назначения без повреждений составляет 80 %. Если уровень переда-

чи данных не обеспечивает проверки ошибок, сколько раз в среднем потребу-

ется пересылать все сообщение?

2. В протоколе уровня передачи данных используется следующее кодирование

символов:

А: 01000111; В: 11100011; FLAG: 01111110; ESC: 11100000,

Как в двоичных кодах будет выглядеть кадр, состоящий из четырех симво-

лов — А, В, ESC, FLAG, при использовании каждого из следующих методов

кадрирования:

• подсчет символов;

• флаговые байты с символьным заполнением;

• начальные и конечные флаговые байты с битовым заполнением.

3. В потоке данных, для которого применяется алгоритм символьного заполне-

ния, встречается следующий фрагмент данных:

А В ESC С ESC FLAG FLAG D.

Каким будет выходной поток после заполнения символами?

4. Один из ваших однокурсников, большой скряга, предположил, что использо-

вать после концевого флагового байта кадра начальный флаговый байт сле-

дующего кадра — слишком расточительно, вполне можно обойтись флаговым

байтом. Таким образом можно сэкономить передачу одного байта. Вы согла-

ситесь с ним?

5. Каким будет на выходе после применения битового заполнения на уровне пе-

редачи данных следующий поток бит: 0111101111101111110?

6. Может ли потеря, вставка или изменение одного бита при использовании би-

тового заполнения вызвать не обнаруживаемую контрольной суммой ошиб-

ку? Если нет, почему? Если да, то каким образом? Влияет ли на результат

длина используемой контрольной суммы?

7. При каких обстоятельствах протокол без обратной связи (например, с кодом

Хэмминга) может быть предпочтительнее протоколов с обратной связью, об-

суждаемых в данной главе?

Вопросы 287

8. Для обеспечения большей надежности, нежели та, которую предоставляет

единственный бит четности, в некотором методе обнаружения ошибок один

бит четности суммирует все четные биты, а другой — все нечетные. Каково

будет в этом случае расстояние кода по Хэммингу?

9. При помощи кода Хэмминга передаются 16-битные сообщения. Сколько кон-

трольных битов потребуется для того, чтобы приемник гарантированно мог

обнаруживать и исправлять одиночные битовые ошибки? Как будет выгля-

деть код для передачи следующего сообщения: 1101001100110101? Предпола-

гается, что код Хэмминга использует проверку четных битов.

10. С помощью кода Хэмминга с проверкой на четность необходимо закодиро-

вать байт, двоичное значение которого равно 10101111. Как будет выглядеть

эта последовательность после кодирования?

11. Приемник получает 12-битную последовательность в коде Хэмминга, ее ше-

стнадцатеричное значение равно 0xE4F. Как (в шестнадцатеричном виде) вы-

глядела исходная последовательность? Предполагается, что ошибочным мо-

жет быть только 1 бит.

12. Один из способов обнаружения ошибок заключается в передаче данных в ви-

де блока из п рядов по k бит с добавлением битов четности к каждому ряду и

каждой строке. Будет ли такая схема обнаруживать все одиночные ошибки?

Двойные ошибки? Тройные ошибки?

13. В блоке битов из п рядов и k строк для обнаружения ошибок используются

горизонтальные и вертикальные биты четности. Какова вероятность того, что

инверсия 4 битов не будет обнаружена?

14. Чему равен остаток от деления х

+ X" + 1 на образующий многочлен X" + 1 ?

15. Поток бит 10011101 передается с использованием стандартного метода цик-

лического избыточного кода (CRC), описанного в тексте. Образующий мно-

гочлен равен х

••'+ 1. Какая битовая последовательность будет реально переда-

ваться? Предполагается, что третий бит слева при передаче инвертировался.

Докажите, что эта ошибка будет обнаружена приемником.

16. В протоколах передачи данных CRC почти всегда помещается в конце кадра,

а не в заголовке. Почему?

17. Скорость передачи данных в канале составляет 4 Кбит/с, а время распростра-

нения сигнала — 20 мс. При каком размере кадров эффективность протокола

с ожиданиями составит по меньшей мере 50 %?

18. Кабель Т1 длиной 3000 км используется для передачи 64-байтовых кадров

при помощи протокола 5. Если задержка распространения сигнала составляет

6 мкс/км, сколько бит следует отвести на порядковые номера кадров?

19. Может ли отправитель при использовании протокола 3 начать передачу, ко-

гда таймер уже запущен? Если да, то как такое может произойти? Если нет,

почему это невозможно?

288 Глава 3. Уровень передачи данных

Вопросы 289

20. Представьте себе протокол скользящего окна, в котором используется так

много битов на порядковые номера кадров, что номера никогда не использу-

ются дважды. Какое соотношение должно связывать четыре границы окна и

размер окна?

21. Предположим, что в процедуре between протокола 5 вместо условия а < Ъ < с

проверяется условие а < b < с. Как это повлияет на правильность протокола и

его эффективность? Поясните свой ответ.

22. Когда прибывает информационный кадр, протокол 6 проверяет, отличается

ли номер кадра от ожидаемого и равна ли переменная nojiak значению true.

При выполнении обоих условий посылается NAK. В противном случае запус-

кается вспомогательный таймер. Предположим, что в тексте программы про-

пущен оператор else. Повлияет ли это на правильность работы протокола?

23. Предположим, что из конца текста программы протокола 6 удалены три стро-

ки цикла while. Повлияет ли это на правильность работы протокола или же

только на его быстродействие? Поясните свой ответ.

24. Предположим, что оператор case, обрабатывающий случай ошибки контроль-

ной суммы, убран из блока switch в протоколе 6. Как это повлияет на работу

протокола?

25. В протоколе 6 в программе, обрабатывающей событие прихода кадра frame_

arrival, есть раздел, используемый для отрицательных подтверждений (NAK).

Этому участку программы передается управление, когда получаемый кадр яв-

ляется NAK, а также при выполнении другого условия. Приведите пример сце-

нария, в котором наличие этого условия является важным.

26. Представьте, что вы разрабатываете программное обеспечение уровня переда-

чи данных для линии, по которой данные поступают к вам, но не от вас. Дру-

гая сторона использует протокол HDLC с 3-битным порядковым номером и

размером окна в 7 кадров. Вы хотите для увеличения эффективности буфери-

зировать как можно большее число кадров, однако изменение программы пе-

редающей стороны не допускается. Можно ли использовать окно получателя

размером более 1 и, тем не менее, гарантировать правильность работы прото-

кола в любых ситуациях? Если да, то какой максимальный размер окна мо-

жет быть использован?

27. Протокол 6 применяется на безошибочной линии со скоростью 1 Мбит/с.

Максимальный размер кадра 1000 бит. Новые пакеты формируются пример-

но раз в секунду. Интервал тайм-аута установлен на период 10 мс. Если от-

ключить специальный таймер подтверждений, то будут происходить лишние

тайм-ауты. Сколько раз в среднем будет передаваться одно сообщение?

28. В протоколе 6 значение MAX_SEQ=2" - 1. Хотя это условие, очевидно,

желательно для эффективного использования битов заголовка, важность его

не была показана. Будет ли протокол корректно работать, например, при

MAX_SEQ=4?

29. Кадры длиной 1000 бит посылаются по спутниковому каналу с пропускной

способностью 1 Мбит/с. Подтверждения всегда посылаются в информацион-

ных кадрах. Заголовки кадров очень короткие. Используются 3-битовые по-

рядковые номера. Какой будет максимальная эффективность использования

канала при применении:

1) протокола с ожиданием;

2) протокола 5;

3) протокола 6.

30. Какая часть пропускной способности канала теряется на заголовки и повтор-

ные передачи при использовании протокола 6 на сильно загруженном спут-

никовом канале с пропускной способностью 50 Кбит/с. Кадры данных состоят

из 40-битовых заголовков и 3960 бит данных. Время распространения сигна-

ла от Земли до спутника составляет 270 мс. Кадры АСК никогда не посыла-

ются. Размер кадров NAK равен 40 бит. Вероятность ошибки для кадра данных

составляет 1 %, а для кадра NAK она пренебрежимо мала. Порядковые номера

занимают 8 бит.

31. Предположим, что безошибочный спутниковый канал с пропускной способ-

ностью 64 Кбит/с используется для пересылки 512-байтных кадров данных в

одном направлении с очень короткими подтверждениями, идущими в обрат-

ном направлении. Какова будет максимальная скорость передачи данных при

размере окна, равном 1, 7, 15 и 127? Время распространения сигнала от Земли

до спутника — 270 мс.

32. Кабель длиной в 100 км работает на скорости Т1. Скорость распространения

сигнала равна 2/3 от скорости света в вакууме. Сколько бит помещается в ка-

беле?

33. Протокол 4 моделируется при помощи модели конечных автоматов. В сколь-

ких состояниях может находиться каждая машина? Канал связи? Вся систе-

ма (две машины и канал)? Ошибки контрольных сумм игнорировать.

34. Покажите последовательность переходов на сетевой модели Петри, изобра-

женной на рис. 3.16, соответствующую последовательности состояний (000),

(01А), (01-), (010), (01А) на рис. 3.14. Объясните, что при этом происходит.

35. Постройте сетевую модель Петри по следующим правилам переходов: АС-+В,

В-ьАС, CD-^E и E-+CD. По сетевой модели Петри постройте модель конечно-

го автомата с состояниями, достижимыми из начального состояния ACD. Ка-

кие хорошо известные принципы кибернетики моделирует эти правила пере-

хода?

36. Основные идеи протоколов РРР и HDLC очень близки. Чтобы случайно

встретившийся в поле данных флаговый байт не вызвал ошибки синхрониза-

ции кадров, в протоколе HDLC используется битовое заполнение. Назовите

хотя бы одну причину, по которой в протоколе РРР вместо этого применяет-

ся символьное заполнение.

37. Каковы минимальные накладные расходы при пересылке IP-пакета по прото-

колу РРР? Учитывайте только накладные расходы самого протокола РРР,

а не заголовки протокола IP.

290 Глава 3. Уровень передачи данных

38. Целью данного упражнения является реализация механизма обнаружения

ошибок с помощью стандартного алгоритма циклического избыточного кода

(CRC), описанного в тексте. Напишите две программы: генератор (generator)

и верификатор (verifier). Программа-генератор считывает со стандартного

устройства ввода и-битное сообщение из нулей и единиц, представленных

в виде строки ASCII-текста. Вторая строка является ^-битным многочленом

(также в ASCII). На устройстве вывода печатается текст из п + k нулей и еди-

ниц, представляющий собой сообщение, подлежащее пересылке. Затем печата-

ется многочлен в том же виде, в каком он был считан. Программа-верифика-

тор считывает результат работы генератора и выводит сообщение, в котором

сообщается, корректен ли данный результат. Наконец, напишите программу

(alter), вносящую сбой, а именно инвертирующую только один бит первой

строки в зависимости от аргумента (например, порядкового номера бита, пред-

полагая, что слева располагается бит с номером 1). Все остальные данные пере-

даются без изменений. Набрав в командной строке generator <file | verifier

пользователь должен увидеть сообщение о том, что данные переданы кор-

ректно. Набрав generator <file | alter arg | verifier пользователь должен по-

лучить сообщение об ошибке при передаче.

39. Напишите программу для моделирования поведения сети Петри. Программа

должна считывать правила переходов и список состояний, соответствующих

сетевому уровню, передающему или принимающему новый пакет. Из началь-

ного состояния, также считываемого программой, программа должна случайно

выбирать переходы, проверяя возможность ситуации, когда один хост примет

два сообщения, и при этом другой хост между этими событиями не выпустит

нового сообщения.

Глава 4

Подуровень управления

доступом к среде

• Проблема распределения канала

• Протоколы коллективного доступа

• Сеть Ethernet

• Беспроводные локальные сети

• Широкополосные беспроводные сети

• Bluetooth

• Коммутация на уровне передачи данных

• Резюме

• Вопросы

Как уже указывалось в главе 1, все сетевые технологии могут быть разделены на

две категории: использующие соединения от узла к узлу и сети с применением

широковещания. Эта глава посвящена широковещательным сетям и их протоко-

лам.

Главной проблемой любых широковещательных сетей является вопрос о том,

как определить, кому предоставить канал, если пользоваться им одновременно

хотят несколько компьютеров. Для примера представьте себе конференцию, в ко-

торой принимают участие шесть человек, причем каждый использует свой теле-

фон. Все они соединены таким образом, что каждый может слышать всех осталь-

ных. Весьма вероятно, что когда один из них закончит свою речь, сразу двое или

трое начнут говорить одновременно, тем самым создав неловкую ситуацию. При

личной встрече подобные проблемы предотвращаются внешними средствами, на-

пример поднятием руки для получения разрешения говорить. Когда доступен

лишь один канал, определить, кто может говорить следующим, значительно труд-

нее. Для решения этой проблемы разработано много протоколов, которые и бу-

дут обсуждаться в данной главе. В литературе широковещательные каналы иногда

292 Глава 4. Подуровень управления доступом к среде

называют каналами с множественным доступом, или каналами с произвольным

доступом.

Протоколы, применяющиеся для определения того, кто будет говорить сле-

дующим, относятся к подуровню уровня передачи данных, называемому MAC

(Medium Access Control — управление доступом к среде). Подуровень MAC осо-

бенно важен в локальных сетях, так как почти все они используют канал множе-

ственного доступа. В глобальных сетях, напротив, применяются двухточечные

соединения. Исключением являются только спутниковые сети. Поскольку кана-

лы множественного доступа тесно связаны с локальными сетями, в данной главе

в основном будут описываться локальные сети, а также некоторые вопросы, на-

прямую не связанные с темой подуровня MAC.

Технически подуровень управления доступом к среде является нижней ча-

стью уровня передачи данных, поэтому логичнее было бы изучить сначала его,

а затем протоколы «точка—точка», рассмотренные в главе 3. Тем не менее, боль-

шинству людей понять протоколы, включающие многих участников, легче после

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

рассмотрении уровней мы слегка отклонились от строгого следования снизу

вверх по иерархической лестнице.

Проблема распределения канала

Центральной проблемой, обсуждаемой в этой главе, является распределение од-

ного широковещательного канала между многочисленными пользователями,

претендующими на него. Сначала мы в общих чертах рассмотрим статические и

динамические схемы распределения канала. Затем обсудим несколько конкрет-

ных алгоритмов.

Статическое распределение канала

в локальных и региональных сетях

Традиционным способом распределения одного канала — например, телефонного

кабеля — между многочисленными конкурирующими пользователями является

FDM (Frequency Division Multiplexing — частотное уплотнение). При наличии

N пользователей полоса пропускания делится на N диапазонов одинаковой ши-

рины (см. рис. 2.27), и каждому пользователю предоставляется один из них. По-

скольку при такой схеме у каждого оказывается свой личный частотный диа-

пазон, то конфликта между пользователями не возникает. При небольшом

количестве абонентов, каждому из которых требуется постоянная линия связи

(например, коммутаторы операторов связи), частотное уплотнение предоставля-

ет простой и эффективный механизм распределения.

Однако при большом и постоянно меняющемся количестве отправителей

данных или пульсирующем трафике частотное уплотнение не может обеспечить

достаточно эффективное распределение канала. Если количество пользователей

в какой-либо момент времени меньше числа диапазонов, на которые разделен

Проблема распределения канала 293

спектр частот, то большая часть спектра не используется и тратится попусту. Ес-

ли, наоборот, количество пользователей окажется больше числа доступных диа-

пазонов, то некоторым придется отказать в доступе к каналу, даже если абонен-

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

Однако даже если предположить, что количество пользователей можно ка-

ким-то способом удерживать на постоянном уровне, то разделение канала на ста-

тические подканалы все равно является неэффективным. Основная проблема

здесь состоит в том, что если какая-то часть пользователей не пользуется кана-

лом, то эта часть спектра просто пропадает. Они сами при этом занимают линию,

не передавая ничего, и другим не дают передать данные. Кроме того, в большин-

стве компьютерных систем трафик является чрезвычайно неравномерным

(вполне обычным является отношение пикового трафика к среднему как 1000:1).

Следовательно, большую часть времени большая часть каналов не будет исполь-

зоваться.

То, что характеристики статического частотного уплотнения оказываются не-

удачными, можно легко продемонстрировать на примере простых вычислений

теории массового обслуживания. Для начала сосчитаем среднее время задержки

Г для канала с пропускной способностью С бит/с, по которому прибывают X кад-

ров в секунду. Длина кадров является случайной величиной с экспоненциально

распределенной плотностью вероятности, среднее значение которой равно

1/ц бита на кадр. При таких параметрах скорость прибытия составляет X кадров

в секунду, а скорость обслуживания — \х.С кадров в секунду. Теория массового

обслуживания говорит о том, что пуассоновское время прибытия и обслужива-

ния равно

\iC-k

Пусть, например, пропускная способность С равна 100 Мбит/с, средняя дли-

на кадра 1/ц = 10 000 бит, скорость прибытия кадров X = 5000 кадров в секунду.

Тогда Т = 200 мкс. Обратите внимание: если бы мы не учли задержки при фор-

мировании очереди и просто посчитали, сколько времени нужно на передачу

кадра длиной 10 000 бит по сети с пропускной способностью 100 Мбит/с, то по-

лучили бы неправильный ответ: 100 мкс. Это число приемлемо лишь при отсут-

ствии борьбы за канал.

Теперь давайте разделим канал на N независимых подканалов, у каждого из

которых будет пропускная способность C/N бит/с. Средняя входная скорость в

каждом подканале теперь будет равна X/N кадров в секунду. Сосчитав новое зна-

чение средней задержки Г, получим:

1 N

Т -

NT.

(4.1)

\i(C/N)-(\/N) ц

Это означает, что при использовании частотного уплотнения значение средней

задержки стало в N раз хуже значения, которое было бы в канале, если бы все

кадры были каким-то волшебным образом организованы в одну общую очередь.