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

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

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

физическую топологию от логической. Был разработан новый формат кадров

(стандарт 802.1Q), который позволил упростить процесс внедрения виртуаль-

ных сетей в организациях.

Вопросы

1. Для решения задачи используйте формулу, приведенную в данной главе, за-

писав ее в общем виде. Кадры для передачи прибывают случайным образом

на 100-мегабитный канал. Если в момент прибытия канал оказывается занят,

кадр ставится в очередь ожидания. Длина кадра распределяется по экспонен-

циальному закону с математическим ожиданием, равным 10 000 бит/кадр.

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

держку (включая время ожидания в очереди и время передачи) кадра средней

длины.

1) 90 кадров/с;

2) 900 кадров/с;

3) 9000 кадров/с.

2. Группа из N станций совместно использует канал чистой системы ALOHA,

работающий со скоростью 56 Кбит/с. Каждая станция передает 1000-битный

кадр в среднем каждые 100 с, даже если предыдущий кадр еще не был пере-

дан (например, станции могут буферизировать исходящие кадры). Каково

максимальное значение N?

3. Сравните время задержки чистой и дискретной систем ALOHA при низкой

нагрузке. У какой из систем это время будет меньшим? Поясните свой ответ.

4. 10 000 станций соревнуются за право использования единственного канала

дискретной системы ALOHA. В среднем одна станция делает 18 запросов в

час. Длительность интервала равна 125 мкс. Какова приблизительная сум-

марная загруженность канала?

5. Большая группа пользователей системы ALOHA формирует 50 запросов в се-

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

валы по 40 мс.

1) Каковы шансы успеха с первой попытки?

2) Какова вероятность того, что перед успехом произойдет ровно k столкно-

вений?

3) Чему равно среднее число попыток передачи?

6. Измерения канала дискретной системы ALOHA с бесконечным числом пользо-

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

1) Какова загрузка канала G?

2) Чему равна производительность канала?

3) Канал перегружен или недогружен?

Вопросы 395

7. В дискретной системе ALOHA с бесконечным числом пользователей средний

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

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

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

8. Сколько времени в худшем случае придется ожидать начала передачи стан-

ции s, если в локальной сети применяется:

1) базовый протокол бит-карты;

2) протокол Мока (Мок) и Уорда (Ward) с перестановкой номеров виртуаль-

ных станций?

9. В локальной сети используется вариант двоичного обратного отсчета Мока

(Мок) и Уорда (Ward). В некоторый момент времени десять станций имеют

следующие виртуальные номера: 8, 2, 4, 5, 1, 7, 3, 6, 9, 0. Следующими пере-

дающими станциями являются 4, 3 и 9. Какими будут новые виртуальные но-

мера станций после того, как эти три станции закончат свою передачу?

10. Шестнадцать станций, пронумерованных от 1 до 16, соревнуются за право ис-

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

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

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

готовыми к передаче?

11. Группа из 2" станций использует протокол движения по адаптивному дереву

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

рый момент времени 2 станции оказываются готовыми к передаче. Чему рав-

но минимальное, максимальное и среднее число интервалов времени, необхо-

димое для прохождения по дереву, если 2" много больше 1?

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

токолы, как МАСА, вместо CSMA/CD. При каких условиях было бы возмож-

но вместо МАСА использовать CSMA/CD?

13. Какие есть общие свойства у протоколов доступа к каналу WDMA и GSM?

(Для ответа на этот вопрос см. главу 2, в которой рассказывается о системе

GSM.)

14. Шесть станций, отмеченных буквами А — F, взаимодействуют друг с другом

по протоколу МАСА. Возможна ли ситуация двух одновременных передач

данных? Ответ поясните.

15. В семиэтажном офисном здании на каждом этаже расположено по 15 офисов.

В каждом офисе на стене установлен разъем для подключения терминала, так

что в вертикальной плоскости эти разъемы образуют четырехугольную сетку

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

Предполагая, что можно проложить кабель по прямой между любой парой

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

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

1) конфигурации «звезда» с одним маршрутизатором посередине;

2) сети 802.3.

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

16. Чему равна скорость в бодах стандартной локальной сети Ethernet со скоро-

стью 10 Мбит/с?

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

' ности: 0001110101?

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

довательности из предыдущего задания? Предполагается, что вначале линия

находится в низком состоянии сигнала.

19. В сети с протоколом CSMA/CD (не 802.3) длиной 1 км со скоростью переда-

чи данных 10 Мбит/с скорость распространения сигнала составляет 200 м/мкс.

Длина кадров данных равна 256 бит, включая 32 бита заголовка, контроль-

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

пешной передачи кадра резервируется для передачи получателем 32-битового

кадра с подтверждением. Какова эффективная скорость передачи данных без

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

20. Две станции в сети с протоколом CSMA/CD пытаются передавать длинные

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

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

Какова вероятность того, что борьба закончится в k-u раунде, и чему равно

среднее число раундов в периоде состязания?

21. Как создать сеть CSMA/CD, работающую на скорости 1 Гбит/с по кабелю

длиной в 1 км, без повторителей? Скорость распространения сигнала в кабе-

ле равна 200 000 км/с. Чему равен минимальный размер кадра в этой сети?

22. IP-пакет необходимо передать по сети Ethernet. Длина пакета — 60 байт, вклю-

чая все служебные поля. Если не используется LLC, необходимо ли заполне-

ние Ethernet-кадра? Если да, то сколькими байтами?

23. Кадры Ethernet должны быть не короче 64 байт для того, чтобы в случае кол-

лизии на дальнем конце провода передатчик все еще передавал тот же самый

кадр. В сетях типа «быстрый Ethernet» минимальный размер кадра также ра-

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

ческом варианте Ethernet. Каким образом в системе удалось сохранить преж-

ний минимальный размер кадра?

24. В некоторых изданиях можно прочесть, что максимальный размер кадра Ether-

net равен 1518 байтам (а не 1500 байтам). Ошибаются ли авторы этих изда-

ний? Ответ поясните.

25. Спецификация 1000Base-SX предписывает генератору тактов работать с час-

тотой 1250 МГц, хотя гигабитный Ethernet рассчитан на максимальную ско-

рость1 Гбит/с. Как вы думаете, это завышение частоты является следствием

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

26. Сколько кадров в секунду может обрабатывать гигабитный Ethernet? Хоро-

шо подумайте перед тем, как отвечать. Подсказка: имеет значение тот факт,

что это именно гигабитный Ethernet.

27. Назовите две сетевые технологии, позволяющие паковать кадры друг за дру-

гом. Чем выгодно такое свойство?

Вопросы 397

28. На рис. 4.24 показаны четыре станции: А, В, С и D. Как вы думаете, какая из

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

29. Пусть по 11-мегабитной локальной сети 802.11b передаются друг за другом по

радиоканалу 64-байтные кадры с вероятностью ошибки 10~

на бит. Сколько

кадров в секунду в среднем будет искажаться при передаче?

30. Сеть стандарта 802.16 обладает каналом с шириной полосы пропускания

20 МГц. Сколько бит в секунду можно отправлять по ней абоненту?

31. Стандарт IEEE 802.16 описывает четыре класса сервисов. Какой из них луч-

ше всего подходит для передачи несжатого видео?

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

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

редачи.

33. На рис. 4.32 видно, что устройство системы Bluetooth может находиться од-

новременно в двух пикосетях. Почему одно и то же устройство не может яв-

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

34. На рис. 4.22 показано несколько протоколов физического уровня. Какой из

них больше всего напоминает протокол физического уровня Bluetooth? В чем

состоит основная разница этих двух протоколов?

35. Bluetooth поддерживает два типа соединений главного узла с подчиненным.

Как они называются и для чего используются?

36. Сигнальные кадры в варианте стандарта 802.11 со скачкообразными измене-

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

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

37. Рассмотрите объединенные сети на рис. 4.40. Предположим, хосты А иВ рас-

положены в ЛВС 1, С - в ЛВС 2, a D - в ЛВС 8. Изначально хэш-таблицы

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

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

изойдут следующие события:

1) Л отправляет данные для D;

2) С отправляет данные для А;

3) D отправляет данные для С;

4) D переходит в ЛВС 6;

5) D отправляет данные для А?

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

в расширенной ЛВС является то, что некоторые мосты могут вообще не уча-

ствовать в работе системы. Найдите три таких моста на рис. 4.40. Есть ли ка-

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

они бездействуют?

39. Допустим, у коммутатора имеются сетевые платы с четырьмя входами. Часто

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

лен на другую линию, подключенную к той же плате. Что должно быть пред-

принято разработчиками платы для оптимизации работы при такой ситуации?

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

40. Коммутатор, предназначенный для работы с быстрым Ethernet, имеет объеди-

нительную плату, которая может передавать данные со скоростью 10 Гбит/с.

Сколько кадров в секунду может быть обработано таким коммутатором?

41. Рассмотрите сеть, показанную на рис. 4.45, а. Если машина/неожиданно ста-

нет «белой», необходимо ли будет вносить какие-либо изменения в марки-

ровку? Если да, то какие?

42. Опишите вкратце разницу между коммутаторами с ожиданием и сквозными

коммутаторами.

43. Коммутаторы с ожиданием имеют преимущество перед сквозными коммута-

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

44. Чтобы виртуальная сеть заработала, мостам и коммутаторам нужны конфигу-

рационные таблицы. А что если в виртуальных сетях, показанных на рис. 4.45, а,

использовать вместо моноканала концентраторы? Понадобятся ли им конфи-

гурационные таблицы? Ответ поясните.

45. На рис. 4.46 коммутатор обычного оконечного домена (справа) является ВЛВС-

совместимым. Можно было бы поставить здесь обычный коммутатор? Ответ

поясните.

46. Напишите программу, симулирующую поведение протокола CSMA/CD в сис-

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

налу кадра. Программа должна выводить временные метки тех моментов, ко-

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

часы изменяют свое состояние каждый такт (51,2 мкс), и обнаружение колли-

зии с отправкой преднамеренной помехи, сообщающей об этом, также зани-

мает один такт. Все кадры имеют максимально допустимую длину.

Глава 5

Сетевой уровень

• Вопросы проектирования сетевого уровня

• Алгоритмы маршрутизации

• Алгоритмы борьбы с перегрузкой

• Качество обслуживания

• Объединение сетей

• Сетевой уровень в Интернете

• Резюме

• Вопросы

Сетевой уровень занимается разработкой маршрутов доставки пакетов от отпра-

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

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

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

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

переместить кадры с одного конца провода на другой. Таким образом, сетевой

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

Данных по всему пути от одного конца до другого.

Для достижения этих целей сетевой уровень должен обладать информацией

о топологии подсети связи (то есть о множестве всех маршрутизаторов) и выби-

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

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

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

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

В данной главе мы рассмотрим все эти аспекты и проиллюстрируем их прежде

всего на примере Интернета и его протокола сетевого уровня — IP, хотя и бес-

проводные сети мы также рассмотрим.

400 Глава 5. Сетевой уровень

Вопросы проектирования сетевого уровня 401

Вопросы проектирования сетевого уровня

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

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

сервисы, предоставляемые транспортному уровню, и внутреннее строение подсети.

Метод коммутации пакетов с ожиданием

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

новить в памяти окружение, в котором ему приходится функционировать. Оно

показано на рис. 5.1. Основными компонентами системы являются устройства

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

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

занные вне овала. Хост Н1 напрямую соединен по выделенной линии с одним из

маршрутизаторов оператора связи, А. Хост Н2, напротив, находится в ЛВС с мар-

шрутизатором F, принадлежащим клиенту, который с ним работает. Этот мар-

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

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

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

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

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

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

шрутизаторах операторов связи (а основным предметом рассмотрения будут

именно алгоритмы).

Маршрутизатор

Оборудование

оператора связи

Процесс Р2

Процесс Р1

ЛВС

Пакет

Рис. 5.1. Окружение, в котором функционируют протоколы сетевого уровня

Система работает следующим образом. Хост, у которого есть пакет для переда-

чи, посылает его либо на ближайший маршрутизатор своей ЛВС, либо по двух-

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

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

передается по цепочке маршрутизаторов, которая в итоге приводит к пункту на-

значения. Такой механизм называется коммутацией пакетов с ожиданием, и мы

уже рассматривали его в предыдущих главах.

Сервисы, предоставляемые

транспортному уровню

Сетевой уровень предоставляет транспортному уровню сервисы в виде интер-

фейса между сетевым и транспортным уровнями. Важным вопросом является то,

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

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

• Сервисы сетевого уровня не должны зависеть от технологии маршрутиза-

тора.

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

пологии присутствующих подсетей с маршрутизаторами.

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

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

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

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

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

ется в яростную борьбу между двумя непримиримыми группировками. В центре

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

вой уровень — ориентированные на соединение или не требующие соединений.

Один лагерь (представленный Интернет-сообществом) заявляет, что работа

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

пакетов и больше ни в чем. С их точки зрения (основанной на примерно тридца-

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

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

Хосты должны учитывать это и защищаться от ошибок своими силами (то есть

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

управлять потоком.

Из этого следует, что сетевой сервис должен быть сервисом, не требующим

установки соединения и состоящим в основном из примитивов SEND PACKET (по-

слать пакет) и RECEIVE PACKET (принять пакет). В частности, сюда нельзя включать

упорядочивание пакетов и контроль потока — все равно эти действия будет вы-

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

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

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

шествующих пакетов.

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

сеть должна предоставлять надежный, ориентированный на соединение сервис.

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

всему миру — это серьезный аргумент в их пользу. По их мнению, качество об-

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

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

Когда дело касается трафика реального масштаба времени — например, передачи

голоса и видео.

402 Глава 5. Сетевой уровень

Примерами технологий, защищаемых каждой из сторон, являются Интернет

и ATM. Интернет предоставляет не требующие установления соединения серви-

сы сетевого уровня, а система ATM — ориентированные на соединение. Интерес-

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

все более важным, а Интернет при этом активно развивается. В частности, как

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

висами, ориентированными на соединение. Вообще-то мы уже даже намекали на

это, когда рассматривали виртуальные сети в главе 4.

Реализация сервиса без установления

соединения

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

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

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

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

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

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

по аналогии с телеграммами, а подсети, соответственно, — дейтаграммными. При

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

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

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

лом, по аналогии с физическими каналами, устанавливаемыми в телефонной

системе. Подсеть при этом называется подсетью виртуального канала. В этом

разделе мы обсудим дейтаграммные подсети; в следующем разделе — подсети

виртуального канала.

Рассмотрим принцип работы дейтаграммных подсетей. Пусть процесс Р1

(рис. 5.2) хочет послать длинное сообщение для Р2. Он передает свое послание

транспортному уровню, сообщает ему о том, что доставить данные необходимо

процессу Р2, выполняющемуся на хосте Н2. Код транспортного уровня исполня-

ется на хосте Н1; более того, обычно он является частью операционной системы.

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

де оно передается на сетевой уровень. Обычно это просто еще одна процедура

операционной системы.

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

пакета, поэтому сетевой уровень должен разбить его на четыре пакета (1, 2, 3 и 4)

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

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

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

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

сов назначения. Каждая запись таблицы состоит из двух полей: пункт назначе-

ния (адресат) и выходящая линия для данного адресата. Во втором поле могут

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

тизатором. Так, например, на рис. 5.2 у маршрутизатора А имеются только две

исходящие линии — ведущие к В и к С, поэтому все входящие пакеты должны

Вопросы проектирования сетевого уровня 403

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

ются адресатами. Изначальная таблица маршрутизации А показана на рисунке

под соответствующей надписью.

Пакет

Маршрутизатор

Л.

Оборудование

оператора связи

Н2

' Процесс Р2

Процесс Р1

ЛВС

Таблица маршрутизатора А

В начале

В конце

Таблица Таблица

маршрутизатора С маршрутизатора Е

в: в

с;

Назначение Линия

Рис. 5.2. Маршрутизация внутри дейтаграммной подсети

Пакеты 1, 2 и 3, прибывая на маршрутизатор А, кратковременно сохраняются

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

сумме. Затем в соответствии с таблицей А все они пересылаются на маршрутиза-

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

локальной сети, F. Когда он прибывает на F, он инкапсулируется в кадр уровня

передачи данных и передается на хост Н2 по локальной вычислительной сети.

Пакеты 2 и 3 следуют по тому же маршруту.

Однако с пакетом 4 связана несколько иная история. После прибытия на А он

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

ется F, как и у первых трех пакетов. По каким-то своим причинам маршрутиза-

тор А решил послать пакет 4 по новому маршруту. Может быть, это стало следст-

вием затора где-то на линии АСЕ, возникшего при пересылке трех пакетов,

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

казана под надписью «В конце»). Алгоритм, управляющий таблицами маршру-

тизации и принимающий решения, называется алгоритмом маршрутизации.

Именно изучению алгоритмов маршрутизации будет уделено основное внима-

ние в этой главе.

404 Глава 5. Сетевой уровень

Вопросы проектирования сетевого уровня 405

Реализация сервиса с установлением

соединения

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

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

своего маршрута для каждого пакета, как было показано на рис. 5.2. Вместо этого

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

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

енных в маршрутизаторы. Один и тот же маршрут используется для всего трафи-

ка, проходящего через данное соединение. Именно так работает телефонная сис-

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

существование. При использовании сервиса, ориентированного на установление

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

В качестве примера рассмотрим ситуацию, изображенную на рис. 5.3. Хост

Н1 установил соединение с хостом Н2. Это соединение запоминается и становит-

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

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

ния 1 пришел с хоста Н1, то его нужно направить на С с идентификатором со-

единения 1. Точно так же первая запись С направляет пакет на Е все с тем же

идентификатором соединения 1.

НЗ

Оборудование

Маршрутизатор оператора связи

• Процесс РЗ \

Н2_

7"\Д~Процесс Р2

Процесс Р1

Таблица

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

ЛВС

Таблица

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

Н1; 1

нз: 1

С; 1

Таблица

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

А ; 1

~А~\Т

Е; 1

Е\ 2

С; 1

"сТТ

F; 1

Г7"!

Вход Выход

Рис. 5.3. Маршрутизация в подсети виртуального канала

Теперь рассмотрим, что будет, если хост НЗ захочет установить соединение

с Н2. Он выбирает идентификатор соединения 1 (у него просто нет выбора, по-

скольку это на данный момент единственное существующее соединение) и про-

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

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

конфликт, потому что если А еще может отличить пакеты соединения 1, пришед-

шие с Н1, от пакетов соединения 1, пришедших с НЗ, то С такой возможности не

имеет. По этой причине А присваивает новый идентификатор соединения исхо-

дящему трафику и тем самым создает второе соединение. Предотвращение кон-

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

на возможность изменения идентификаторов соединения в исходящих пакетах.

Иногда это называется коммутацией меток.

Сравнение подсетей виртуальных каналов

и дейтаграммных подсетей

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

ников. Попробуем обобщить аргументы обеих сторон. Основные аспекты сведе-

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

таблицы.

Таблица 5.1. Сравнение виртуальных каналов и дейтаграмм

Проблема

Дейтаграммы

Виртуальные каналы

Установка канала

Адресация

Информация

о состоянии

Маршрутизация

Эффект от выхода из

строя маршрутизатора

Борьба с перегрузкой

Не требуется

Каждый пакет содержит

полный адрес отправителя

и получателя

Подсеть не содержит

информации о состоянии

Маршрут каждого пакета

выбирается независимо

Никакого, кроме

потерянных пакетов

Трудно реализовать

Требуется

Каждый пакет содержит короткий

номер виртуального канала

Каждый виртуальный канал

требует места в таблице подсети

Маршрут выбирается при

установке виртуального канала.

Каждый пакет следует по этому

маршруту

Все виртуальные каналы,

проходившие через отказавший

маршрутизатор, прекращают

существование

Легко реализуется при наличии

достаточного количества

буферов для каждого

виртуального канала

Оба подхода к созданию подсетей в ряде вопросов находят некие компромис-

сы. Во-первых, существует компромисс между внутренней памятью маршрути-

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

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

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

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

ность сети. Однако для хранения в маршрутизаторе больших таблиц с адресами

Может потребоваться много памяти.

406 Глава 5. Сетевой уровень

Алгоритмы маршрутизации 407

Второй компромисс — между временем установки соединения и временем об-

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

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

вается проще и быстрее, чем в дейтаграммной подсети.

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

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

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

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

собность и мощность маршрутизатора будут предоставлены. В дейтаграммной

подсети предотвращение заторов реализовать значительно сложнее.

В системах обработки транзакций (например, при запросе магазина на вери-

фикацию кредитной карты) накладные расходы на установку соединения и уда-

ление виртуального канала могут сильно снизить потребительские свойства сети.

Если объем информации, передаваемой во время одного соединения, невелик, то

использование виртуального канала не имеет смысла. Однако в данной ситуации

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

вручную и не разрываемые месяцами и даже годами.

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

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

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

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

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

мент на маршрутизаторе (а возможно, лишь некоторые из них, в зависимости от

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

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

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

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

Алгоритмы маршрутизации

Основная функция сетевого уровня заключается в выборе маршрута для пакетов

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

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

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

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

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

лью при проектировании сетевого уровня.

Алгоритм маршрутизации реализуется той частью программного обеспече-

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

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

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

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

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

все информационные пакеты следуют по выбранному маршруту. Последний

случай иногда называют сеансовой маршрутизацией, так как маршрут остается

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

гистрации на терминале или передачи файла).

Полезно понимать разницу между маршрутизацией, при которой системе

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

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

шрутизатор как устройство, в котором функционируют два процесса. Один из

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

тизации исходящую линию. Такой процесс называется пересылкой. Второй про-

цесс отвечает за заполнение и обновление таблиц маршрутизации. Именно здесь

в игру вступает алгоритм маршрутизации.

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

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

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

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

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

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

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

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

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

поломке маршрутизатора.

Алгоритм маршрутизации должен также обладать устойчивостью. Существу-

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

сия, независимо от того, как долго они работают. Такие цели, как справедливость

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

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

Для примера рассмотрим ситуацию, показанную на рис. 5.4. Предположим, что

трафик между станциями Аи А', В и В', а также С и С настолько интенсивный,

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

максимизировать общий поток данных, трафик между станциями X и X' следо-

вало бы совсем отключить. Однако станции X и Х\ скорее всего, имеют другую

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

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

нием канала в глобальном смысле.

А' В' С

Рис. 5.4. Конфликт справедливости и оптимальности

408 Глава 5. Сетевой уровень

Алгоритмы маршрутизации 409

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

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

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

щую пропускную способность сети. Однако эти цели также противоречат друг

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

водительности предполагает долгое стояние в очередях. В качестве компромисса

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

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

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

ность.

Алгоритмы выбора маршрута можно разбить на два основных класса: адап-

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

маршрута топологию и текущее состояние сети и не измеряют трафик на лини-

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

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

во время загрузки сети. Такая процедура иногда называется статической марш-

рутизацией.

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

при изменении топологии и также часто в зависимости от загруженности линий.

Адаптивные алгоритмы отличаются источниками получения информации (такие

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

ры, либо глобальными, если это вообще все маршрутизаторы сети), моментами

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

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

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

ожидаемое время пересылки). В следующих разделах мы обсудим различные ал-

горитмы маршрутизации, как статические, так и динамические.

Принцип оптимальности маршрута

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

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

зависимости от топологии или трафика. Такой основополагающей идеей являет-

ся принцип оптимальности. В соответствии с этим принципом, если маршрутиза-

тор В располагается на оптимальном маршруте от маршрутизатора А к маршру-

тизатору С, то оптимальный маршрут от маршрутизатора В к маршрутизатору С

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

маршрута от маршрутизатора А к маршрутизатору В как r

а остальную часть

маршрута — г

. Если бы существовал более оптимальный маршрут от маршрути-

затора В к маршрутизатору С, чем г

, то его можно было объединить с r

чтобы

улучшить маршрут от маршрутизатора А к маршрутизатору С, что противоречит

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

{

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

Прямым следствием принципа оптимальности является возможность рас-

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

кам в виде дерева. Такое дерево называется входным деревом. Оно изображено

на рис. 5.5. Расстояния измеряются количеством транзитных участков. Обратите

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

ной сети могут существовать несколько входных деревьев с одинаковыми длина-

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

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

Рис. 5.5. Подсеть (а); входное дерево для маршрутизатора В (б)

Поскольку входное дерево действительно является деревом, оно не содержит

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

ло пересылок. На практике все это не так просто. Линии связи и маршрутизато-

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

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

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

рает ли маршрутизатор информацию для вычисления входного дерева сам или

эта информация каким-то другим образом поступает к нему. Мы вскоре рассмот-

рим этот вопрос. Тем не менее, принцип оптимальности и входное дерево — это

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

.ных алгоритмов маршрутизации.

Выбор кратчайшего пути

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

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

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

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

связью). При выборе маршрута между двумя маршрутизаторами алгоритм про-

сто находит кратчайший путь между ними на графе.

Концепция кратчайшего пути требует некоторого пояснения. Один из спосо-

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

В таком случае пути ABC и ABE на рис. 5.6 имеют одинаковую длину. Можно из-

мерять расстояния в километрах. В таком случае окажется, что путь ABC значи-

•тельно длиннее пути ABE (предполагается, что рисунок изображен с соблюдени-

ем масштаба).

410 Глава 5. Сетевой уровень

В 7

(2,

А)

С {со,-)

D (=о, -)

(2,

А)

(9,

В)

(2.

А)

(9,

В)

(2,

(9,

£) ЪО(»,-)

(5.

С)

(2,

А)

Н («.,-)

(9,

в(5,£)

/Н(8,/=)

Рис. 5.6. Первые пять шагов вычисления кратчайшего пути отД к D.

Стрелка указывает на рабочий узел

Однако помимо учета количества транзитных участков и физической длины

линий возможен учет и других параметров. Например, каждой дуге графа можно

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

определяемые каждый час с помощью передачи специального тестового пакета.

В таком графе кратчайший путь определяется как самый быстрый путь, а не путь

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

отдельных отрезков кабеля.

В общем случае параметры дуг графа являются функциями расстояния, про-

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

очереди, измеренной величины задержки и других факторов. Изменяя весовую

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

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

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

узлами графа. Один из них был создан знаменитым Дейкстрой (Dijkstra) в 1959 году.

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

по наилучшему известному пути. Вначале пути неизвестны, поэтому все узлы

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

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

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

Алгоритмы маршрутизации 411

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

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

няется.

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

правленный граф (рис. 5.6, а), где весовые коэффициенты соответствуют, напри-

мер, расстояниям. Мы хотим найти кратчайший путь от А к D. Для начала мы

черным кружком помечаем узел А как постоянный. Затем мы исследуем все со-

седние с ним узлы, указывая около них расстояние до узла А. Если отыскивается

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

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

зом, позднее можно восстановить весь путь. Рассмотрев все соседние с А узлы,

мы помечаем ближайший узел как постоянный, как показано на рис. 5.6, б. Этот

узел становится новым рабочим узлом.

Теперь мы повторяем ту же процедуру с узлом В, исследуя все его соседние

узлы. Если сумма расстояния от узла В и значения отметки в узле В (расстояния

от А до В) оказывается меньше, чем отметка у исследуемого узла (уже найденное

другим путем расстояние от А), это значит, что найден более короткий путь, по-

этому пометка узла изменяется.

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

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

менной отметкой. Этот узел помечается как постоянный и становится текущим

рабочим узлом. На рис. 5.6 показаны первые пять этапов работы алгоритма.

Чтобы понять, как работает алгоритм, посмотрим на рис. 5.6, в. На данном

этапе узел Е только что был отмечен как постоянный. Предположим, что сущест-

вует более короткий путь, нежели ABE, например AXYZE. В этом случае есть две

возможности — либо узел Z уже сделан постоянным, либо еще нет. Если да, зна-

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

но, рабочим узлом. В этом случае путь AXYZE уже исследовался.

Теперь рассмотрим случай, когда узел Z все еще помечен как временный.

В этом случае отметка узла Z либо больше или равна пометки узла Е, либо мень-

ше ее. В первом случае путь AXYZE не может быть короче, чем путь ABE. Если

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

стоянным раньше узла Е, и узел Е проверялся бы с узла Z.

Этот алгоритм приведен в листинге 5.1. Глобальные переменные п и dist опи-

сывают граф и инициализируются раньше, чем вызывается shortest_path. Един-

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

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

s, а от конечного узла t Поскольку в однонаправленном графе кратчайший путь

от t к s тот же самый, что и от s к t, не имеет значения, с какого конца начинать.

(Если только не существует несколько кратчайших путей. В таком случае, двига-

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

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

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

копируется в выходную переменную path, он инвертируется. С помощью ревер-

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

путь, идущий в нужную сторону.

412 Глава 5. Сетевой уровень

Алгоритмы маршрутизации 413

Листинг 5.1. Алгоритм Дейкстры вычисления кратчайшего пути по графу

Idefine MAX_NODES 1024 /* максимальное количество узлов */

idefine INFINITY 1000000000 /* число, большее длины максимального пути */

int n. dist[MAX_NODES][MAX_NODES]: /* dist[i][j] - это расстояние от i до j */

void shortest_path(int s, int t. int path[])

{ struct state { /* рабочий путь */

int predecessor: /* предыдущий узел */

int length; /* расстояние от источника до этого узла */

enum {permanent, tentative} label: /* метка состояния */

} state[MAXJODES];

int i. k, min;

struct state *p;

for (p - &state[0]: p < &state[n]; p++) { /* инициализировать состояние */

p->predecessor = -1;

p->length = INFINITY;

p->label - tentative;

}

state[t].length = 0; state[t].label

k - t;

{

for (i - 0; i

n: i++)

if (dist[k][i] !- 0

permanent;

/* k - начальный рабочий узел */

/* Есть ли лучший путь от к? */

/* У этого графа п узлов */

stated].label — tentative) {

{

if (state[k].length + dist[k][i] < stated].length) {

stated].predecessor - k;

stated].length - state[k].length + dist[k][1];

}

/* Найти узел, помеченный как предварительный с наименьшей меткой */

к - 0; min - INFINITY;

for (1

0: 1

n: i++)

• ' if (stated].label — tentative && stated].length < min) {

min - stated].length;

к -i;

}

state[k].label - permanent;

} while (k !- s);

/* Копировать путь в выходной массив */

1 -

к - s;

do (path[i++] - к; к - state[k].predecessor; } while (к >- 0);

Заливка

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

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

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

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

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

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

уменьшаемого при прохождении каждого маршрутизатора. Когда значение этого

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

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

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

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

данной подсети.

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

ключается в учете проходящих через маршрутизатор пакетов. Это позволяет не

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

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

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

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

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

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

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

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

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

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

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

действенно подытоживает его.

На практике чаще применяется вариант данного алгоритма под названием

выборочная заливка. В этом алгоритме маршрутизаторы посылают пакеты не по

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

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

идущей на восток, если только топология сети не представляет собой лабиринт

и маршрутизатор не знает об этом.

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

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

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

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

деленных базах данных иногда бывает необходимо одновременно обновить все

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

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

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

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

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

формируемых самим алгоритмом заливки.

Маршрутизация по вектору расстояний

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

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

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

ются два метода: маршрутизация по вектору расстояний и маршрутизация с уче-

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

рой метод.