|
Previous: 4.4.10 Протокол загрузки BOOTP
UP:
4.4 Интернет |
|
Previous: 4.4.10 Протокол загрузки BOOTP
UP:
4.4 Интернет |
4.4.11 Протоколы маршрутизации (обзор, таблицы маршрутизации, вектор расстояния)
Семенов Ю.А. (ГНЦ ИТЭФ)
| Номер раздела | Название раздела | Объем в страницах | Объем в кбайт |
| 4.4.11.1 | Внутренний протокол маршрутизации RIP | 5 | 5 |
| 4.4.11.2 | Протокол OSPF (алгоритм Дикстры) | 15 | 164 |
| 4.4.11.3 | Протокол IGRP | 7 | 28 |
| 4.4.11.4 | Внешний протокол маршрутизации BGP | 15 | 134 |
| 4.4.11.5 | Бесклассовая интердоменная маршрутизация (CIDR) | 1 | 4 |
| 4.4.11.6 | Автономные системы | 1 | 4 |
| 4.4.11.7 | Маршрутная политика | 6 | 17 |
| 4.4.11.8 | Язык описания маршрутной политики RPSL | 54 | 196 |
| 4.4.11.9 | Мультипротокольные расширения для BGP-4 | 7 | 27 |
| Дорожные указатели могут превратить шоссе в лабиринт
Станислав Ежи Лец, "Непричесанные мысли" |
Основная задача сетей - транспортировка информации от ЭВМ-отправителя к ЭВМ-получателю. В большинстве случаев для этого нужно совершить несколько пересылок. Проблему выбора пути решают алгоритмы маршрутизации. Если транспортировка данных осуществляется дейтограммами, для каждой из них эта задача решается независимо. При использовании виртуальных каналов выбор пути выполняется на этапе формирования этого канала. В Интернет с его IP-дейтограммами реализуется первый вариант (если не рассматривать виртуальные сети), а в ISDN и ATM - второй. Для решения проблемы маршрутизации используются специальные устройства, называемые маршрутизаторами.
| Маршрутизация подразумевает два параллельных процесса: подготовку маршрутной таблицы и переадресацию дейтограмм с помощью этой таблицы. Формирование маршрутной таблицы производится посредством протоколов маршрутизации или под воздействием инструкций сетевого администратора. |
Алгоритм маршрутизации должен обладать вполне определенными свойствами: надежностью, корректностью, стабильностью, простотой и оптимальностью. Последнее свойство не так прозрачно, как это может показаться на первый взгляд, все зависит от того, по какому или каким параметрам производится оптимизация. Эта задача иногда совсем не проста даже для сравнительно простых локальных сетей (смотри, например, рис. 4.4.11.1). Предположим, что поток данных между ЭВМ B и D, соединенных через концентратор (К) весьма высок, что окажет ощутимое влияние на скорость обмена между ЭВМ А и С. Но этот факт довольно трудно выявить, находясь в ЭВМ А или С. Внешне это проявится лишь как повышенная задержка и пониженная пропускная способность участка А-С.
Рис. 4.4.11.1
Среди параметров оптимизации может быть минимальная задержка доставки, максимальная пропускная способность, минимальная цена, максимальная надежность или минимальная вероятность ошибки.
Алгоритмы маршрутизации бывают адаптивными и неадаптивными. Вторые, осуществляя выбор маршрута, не принимают во внимание существующую в данный момент топологию или загрузку каналов. Такие алгоритмы называются также статическими. Адаптивные же алгоритмы предполагают периодическое измерение характеристик каналов и постоянное исследование топологии маршрутов. Выбор того или иного маршрута здесь производится на основании этих измерений.
Практически все методы маршрутизации базируются на следующем утверждении.
| Принцип оптимальности маршрута. Если маршрутизатор M находится на оптимальном пути от маршрутизатора I к маршрутизатору J, тогда оптимальный путь от М к J проходит по этому же пути. |
Чтобы убедиться в этом обозначим маршрут I-M R1, а M-J - R2. Если существует маршрут оптимальнее, чем R2, то он должен быть объединен с R1, чтобы образовать более оптимальный путь I-J, что противоречит исходному утверждению об оптимальности пути J-J. Следствием принципа оптимальности является утверждение, что оптимальные маршруты от всех отправителей к общему месту назначения образуют дерево, лишенное циклов (см. разделы "Протокол OSPF" и "Элементы теории графов"). Такое дерево (называется sink tree) может быть не единственным, могут существовать другие деревья с теми же длинами пути. А это, в свою очередь означает, что любой пакет будет доставлен за строго ограниченное время, пройдя однократно определенное число маршрутизаторов. Маршрутизатор всегда является корнем этого дерева. В реальных условиях отдельные узлы могут выходить из строя или отключаться, что вызывает существенные видоизменения дерева. Разные маршрутизаторы могут иметь свои представления о том, какое из возможных деревьев выбрать. Это является причиной того, что путь из точки А в точку Б может не совпадать с путем из точки Б в точку А.
Главным параметром при маршрутизации пакета в Интернет является IP-адрес его места назначения. Проблема оптимальной маршрутизации в современном Интернет, насчитывающем уже более миллиарда узлов, весьма сложна. Полная таблица маршрутов может содержать 109! записей (здесь ! означает знак факториала, а не выражение эмоций), что не по плечу не только сегодняшним ЭВМ. Внешние маршрутизаторы обычно ищут оптимальный путь между сетями, а не отдельными ЭВМ. Тем не менее, размеры маршрутных таблиц растут экспоненциально и традиционные схемы и решения рано или поздно станут неэффективны. В общем случае для формирования оптимального маршрута нужно владеть исчерпывающей информацией обо всех сетевых сегментах. Это реально только для локальных сетей малого или среднего размеров. Следует также учитывать, что ситуация в сети постоянно меняется и маршрутизаторы для решения их задач имеют ограниченные ресурсы времени. На практике оптимизация осуществляется для ограниченной области сегментов, тогда и объем данных, подлежащих обработке, сокращается на многие порядки. Понятно, что компромиссы здесь неизбежны и результирующий маршрут в этом случае отнюдь не всегда будет оптимальным. Сбор данных о сетевых сегментах и маршрутах выполняется путем обмена этой информацией между маршрутизаторами. Переадресация же дейтограммы должна осуществляться за время 1-20 миллисекунд, которое зависит от длины очереди в буфере.
| Одним из радикальных мер решения проблемы может стать географическая маршрутизация, которая станет возможной при массовом внедрении адресации IPv6. |
При географическом принципе каждая из стран получит равные по численности блоки IP-адресов (США и Андорра получат равное число адресов). Именно по этой причине при 32-битах адреса такая схема была неосуществима.
В начале 90-х годов было принято решение ввести понятие автономной системы (AS). Автономная система - это совокупность локальных сетей, имеющая одного администратора и единую маршрутную политику. Введение AS позволило несколько сократить размер маршрутных таблиц, так как маршруты можно было прокладывать уже не между локальными сетями, а между более крупными образованьями - автономными системами. Само название таких систем подчеркивает их независимость и только добровольное сотрудничество помогает всем участникам решать общие проблемы.
Обычный пользователь не задумывается и не должен задумываться над проблемами маршрутизации, но даже ему иногда может оказаться полезным понимать, что возможно, а что невозможно в Интернет.
IP делит все ЭВМ на маршрутизаторы и обычные ЭВМ (host), последние, как правило, не рассылают свои маршрутные таблицы. Предполагается, что маршрутизатор владеет исчерпывающей информацией о правильных маршрутах (хотя это и не совсем так). Обычная ЭВМ имеет минимальную маршрутную информацию (например, адрес маршрутизатора локальной сети и сервера имен). Автономная система может содержать множество маршрутизаторов, но взаимодействие с другими AS она осуществляет только через один маршрутизатор, называемый пограничным (border gateway, именно он дал название протоколу BGP). Пограничный маршрутизатор нужен лишь тогда, когда автономная система имеет более одного внешнего канала, в противном случае его функции выполняет порт внешнего подключения (gateway; поддержка внешнего протокола маршрутизации в этом случае не требуется). Здесь и далее используется достаточно простые на первый взгляд понятия внешних и внутренних каналов, внешних и внутренних протоколов или маршрутизаторов. Но такое разделение часто весьма условно. Поясню это на примере, представленном на рисунке 4.4.11.1a.
Рис. 4.4.11.1a
Может показаться, что проблема надумана, моя локальная сеть является внутренней, а все, что за ее пределами - внешнее. На рисунке показаны семь маршрутизаторов (R1-R7), один из них связывает эту систему с Интернет. К каждому маршрутизатору подключена одна или несколько субсетей (иначе бы маршрутизаторы были просто не нужны). Следует помнить, что вся эта система маршрутизаторов после подключения становится равноправной частью Интернет. С топологической точки зрения задача маршрутизации сводится к построению оптимального пути от ЭВМ отправителя к ЭВМ-получателю. В этом подходе все маршрутизаторы и узлы Интернет равноправны и деление их на внутренние и внешние условно. И, тем не менее, такое деление вполне оправдано. Связано это чисто с технологическими возможностями современных маршрутизаторов (и отчасти протоколов), с ограниченностью их памяти и быстродействия. Здесь нужно заметить, что, например, не всегда прямой путь от R5 к R6 является наилучшим, он может в частности иметь малую пропускную способность или быть сильно перегруженным. Что считать внутренним, а что внешним имеет и юридический аспект. Здесь возникают проблемы, связанные с разглашением частной информации о гражданах, бывают и более тяжелые случаи.
| Несколько лет назад разработчик почтовой системы PGP (Pretty Good Privacy) Фил Циммерман (США) был привлечен к суду за то, что способствовал распространению систем шифрования со слишком длинными ключами (больше чем это разрешено экспортными ограничениями), что создавало трудности американским спецслужбам. Сидеть бы ему в тюрьме, если бы не общественное мнение и умелые адвокаты. Последние убедили суд, что Циммерман ничего не экспортировал, он лишь положил программы на общедоступный сервер, а ушлые европейцы и шустрые китайцы копировали эти программы с его сервера. Вот их и надо привлекать к суду за нарушение экспортных законов. Это оказалось не по плечу могущественной американской Фемиде, они уж точно вовне и на них распространить законы США не так просто. Пограничные проблемы приходится решать и при борьбе с хакерами и другими компьютерными террористами и хулиганами. Современное законодательство в этой сфере пока несовершенно. |
Если адресат достижим более чем одним путем, маршрутизатор должен сделать выбор, этот выбор осуществляется на основании оценки маршрутов-кандидатов. Обычно каждому сегменту, составляющему маршрут, присваивается некоторая величина - оценка этого сегмента. Каждый протокол маршрутизации использует свою систему оценки маршрутов. Оценка сегмента маршрута называется метрикой. Здесь следует обратить внимание на то, что при выборе маршрута всем сегментам пути должны быть даны сопоставимые значения метрики. Недопустимо, чтобы одни сегменты оценивались числом шагов, а другие - по величине задержки в миллисекундах. В пределах автономной системы это обычно не создает проблем, ведь это зона ответственности одного администратора. Но в региональных сетях, где работает много администраторов, проблема выбора метрики может стать реальной трудностью. Именно по этой причине в таких сетях часто используется вектор расстояния, исключающий субъективность оценок метрики.
Помимо классической схемы маршрутизации по адресу места назначения, часто используется вариант выбора маршрута отправителем (данный вариант получил дальнейшее развитие при введении стандарта IPv6). В этом случае IP-пакет содержит соответствующий код опции и список промежуточных адресов узлов, которые он должен посетить по пути к месту назначения.
Существуют и другие схемы, например, использующие широковещательные методы адресации (flooding), где каждый приходящий пакет посылается по всем имеющимся исходящим каналам, за исключением того, по которому он получен. С тем чтобы исключить беспредельное размножение пакетов в заголовок вводится поле-счетчик числа шагов. В каждом узле содержимое поля уменьшается на единицу. Когда значение поля становится равным нулю, пакет ликвидируется. Исходное значение счетчика определяется размером субсети. Предпринимаются специальные меры против возможного зацикливания пакетов. Существует усовершенствованная версия широковещательной маршрутизации, называемая селективной широковещательной рассылкой. В этом алгоритме рассылка производится не по всем возможным направлениям, а только по тем, которые предположительно ведут в правильную сторону. Широковещательные методы не относятся к широко применимым. Но они используются там, где нужна предельно возможная надежность, например в военных приложениях, когда весьма вероятно повреждение тех или иных каналов. Данные методы могут использоваться лишь при формировании виртуального канала, ведь они всегда обеспечивают наикратчайший путь, так как перебираются все возможности. Если путь записывается в пакете, получатель может выбрать оптимальный проход и уведомить об этом отправителя.
Большинство алгоритмов учитывают топологию связей, а не их качество (пропускную способность, загрузку и пр.). Но существуют подходы к решению проблемы статической маршрутизации, учитывающие как топологию, так и загрузку (flow-based routing). В некоторых сетях потоки между узлами относительно стабильны и предсказуемы. В этом случае появляется возможность вычислить оптимальную схему маршрутов заранее. Здесь на основе теории массового обслуживания производится оценка средней задержки доставки для каждой связи. Топология маршрутов оптимизируется по значению задержки доставки пакета. Исходными данными при расчете считается описание топологии связей, матрица трафика для всех узлов Ti,j (в пакетах в секунду) и матрица пропускных способностей каналов Bi,j в битах в секунду. Задержка t для каждой из связей оценивается по формуле
ti,j = 1/(p*Bi,j - Ti,j),, где i и j - номера узлов.
где 1/Р - среднее значение ширины пакета в битах, произведение p*Bi,j выражается в пакетах в секунду, а t измеряется в мсек. Сформировав матрицу ti,j, можно получить граф кратчайших связей. Так как вычисления производятся не в реальном масштабе времени, особых трудностей здесь не возникает.
Статические протоколы (примером реализации статических протоколов может служить первая версия маршрутизатора Netblazer) предполагают, что любые изменения в маршрутные таблицы вносит администратор сети. Динамическая маршрутизация, обладая очевидными преимуществами, к сожалению, облегчает задачу хакеру, пытающемуся проникнуть в сеть.
| Хакер может имитировать работу маршрутизатора и вынудить посылку всех пакетов через его машину, объявив, что доступ ко всем узлам Интернет ближе или лучше через его рабочую станцию (этакий волшебный гиперканал!). По этой причине, если можно обойтись без динамической маршрутизации, лучше это сделать, ведь облегчение жизни хакерам в наши задачи не входит. |
Рассмотрим для примера сеть, изображенную на рис. 4.4.11.2.
Рис. 4.4.11.2 Схема для иллюстрации методики составления маршрутных таблиц.
G1, G2, G3 - Маршрутизаторы
Примитивная таблица маршрутизации для приведенного примера может иметь вид (для маршрутизатора g2):
| Сеть-адресат | Маршрут к этой сети |
| 193.0.0.0 | Прямая доставка |
| 193.148.0.0 | Прямая доставка |
| 192.0.0.0 | Через адрес 193.0.0.1 |
| 192.166.0.0 | Через адрес 193.148.0.7 |
Заметно сокращают размер маршрутной таблицы маршруты по умолчанию. В этой схеме сначала ищется маршрут в таблицах, а если он не найден, пакет посылается в узел, специально выбранный для данного случая. Так, когда имеется только один канал за рубеж, неудачный поиск в таблице маршрутов по России означает, что пакет следует послать по этому каналу и пусть там с ним разбираются. Маршруты по умолчанию используются обычно тогда, когда маршрутизатор имеет ограниченный объем памяти или по какой-то иной причине не имеет полной таблицы маршрутизации. Маршрут по умолчанию может помочь реализовать связь даже при ошибках в маршрутной таблице. Это может не иметь никаких последствий для малых сетей, но для региональных сетей с ограниченной пропускной способностью такое решение может повлечь серьезные последствия. Экономия на памяти для маршрутных таблиц - дурной стиль, который не доведет до добра. Например, из-за такого рода ошибки довольно долго пакеты из Ярославля в Москву шли через США, я уже не говорю о случае, когда машины, размещенные в соседних комнатах Президиума РАН, вели обмен через Амстердам (правда, это было достаточно давно). Алгоритм выбора маршрута универсален и не зависит от протокола маршрутизации, который используется лишь для формирования маршрутной таблицы. Общий алгоритм выбора оптимального маршрута на основе метрик сегментов пути сформулировал американский математик Дикстра в 1959 году. Описание алгоритма выбора маршрута представлено ниже:
| Извлечь IP-адрес (ID) места назначения из дейтограммы . Вычислить IP-адрес сети назначения (IN) |
Если сеть включает в себя субсети, то для каждой записи в маршрутной таблице производится побитная операция <И> для ID и маски субсети. Если результат этой операции совпадет с содержимым адресного поля сети, дейтограмма посылается серверу субсети. На практике при наличии субсетей в маршрутную таблицу добавляются соответствующие записи с масками и адресами сетей.
Одна из базовых идей маршрутизации заключается в том, чтобы сконцентрировать маршрутную информацию в ограниченном числе (в идеале в одном) узловых маршрутизаторов-диспетчеров. Эта замечательная идея ведет к заметному увеличению числа шагов при пересылке пакетов. Оптимизировать решение позволяет backbone (опорная сеть), к которой подключаются узловые маршрутизаторы. Любая AS подключается к backbone через узловой маршрутизатор.
"Прозрачные" backbone не работают с адресами класса С (все объекты такой сети должны иметь один адрес, а для c-класса число объектов слишком ограничено). "Прозрачные" мосты трудно диагностировать, так как они не следуют протоколу ICMP (команда ping не работает, в последнее время такие объекты снабжаются snmp-поддержкой). За то они позволяют перераспределять нагрузку через несколько маршрутизаторов, что невозможно для большинства протоколов.
Рис. 4.4.11.3.
В примере, приведенном на рис. 4.4.11.3, задача маршрутизации достаточно сложна. ЭВМ1,2 и ЭВМ6,1 можно связать многими путями: ЭВМ1,2 - GW1 - ЭВМ6,1; ЭВМ1,2 - GW2 - ЭВМ6,1; ЭВМ1,2 - GW3 - ЭВМ6,1; ЭВМ1,2 - GW4 - ЭВМ6,1; ЭВМ1,2 - GW1 - GW2 - GW3 - ЭВМ6,1; и т.д. Трафик между двумя географически близкими узлами должен направляться кратчайшим путем, вне зависимости от направления глобальных потоков. Так ЭВМ1,2 и ЭВМ1,1 должны соединяться через GW1. Маршрутизация через опорные сети (backbone) требует индивидуального подхода для каждого узла. Администраторы опорных сетей должны согласовывать свои принципы маршрутизации. Ситуация, когда узел не владеет исчерпывающей маршрутной информацией, в сочетании с использованием маршрутов по умолчанию может привести к зацикливанию пакетов. Например, если маршрут по умолчанию в GW1 указывает на GW2, а в GW2 на GW1, то пакет с несуществующим адресом будет циркулировать между GW1 и GW2 пока не истечет ttl (время жизни пакета), полностью блокируя канал. По этой причине желательно иметь полную таблицу маршрутизации, и, если не вынуждают обстоятельства, избегать использования маршрутов по умолчанию.
Рис. 4.4.11.4.
Протоколы маршрутизации отличаются друг от друга тем, где хранится и как формируется маршрутная информация. Оптимальность маршрута достижима лишь при полной информации обо всех возможных маршрутах, но такие данные потребуют слишком большого объема памяти. Полная маршрутная информация доступна для внутренних протоколов при ограниченном объеме сети. Чаще приходится иметь дело с распределенной схемой представления маршрутной информации. Маршрутизатор может быть информирован лишь о состоянии близлежащих каналов и маршрутизаторов.
Динамические протоколы (обычно используются именно они, наиболее известным разработчиком является компания CISCO):
В маршрутизаторе с динамическим протоколом (например, BGP-4) резидентно загруженная программа-драйвер изменяет таблицы маршрутизации на основе информации, полученной от соседних маршрутизаторов. В ЭВМ, работающей под UNIX и выполняющей функции маршрутизатора, эту задачу часто решает резидентная программа gated или routed (демон). Последняя - поддерживает только внутренние протоколы маршрутизации.
Применение динамической маршрутизации не изменяет алгоритм маршрутизации, осуществляемой на IP-уровне. Программа-драйвер при поиске маршрутизатора-адресата по-прежнему просматривает таблицы. Любой маршрутизатор может использовать два протокола маршрутизации одновременно, один для внешних связей, другой - для внутренних. Для стыковки внешнего маршрута с внутренним в большинстве протоколов предусматриваются специальные средства.
| Может возникнуть вопрос, откуда возникло ограничение на число внешних и внутренних протоколов маршрутизации? Главная причина - согласование метрик сетевых каналов. С внешними протоколами все относительно просто. Во-первых, их мало, во-вторых, практически все они используют для оценки каналов вектор расстояния, что потенциально может вообще снять рассматриваемое ограничение. А как быть с внутренней маршрутизацией? Ведь существуют протоколы, базирующиеся на векторе расстояния (RIP), и на состоянии канала (OSPF или IGRP). Предположим, что в одной зоне сети работает RIP, где канал оценивается числом шагов до цели, а в другой - OSPF с оценкой состояния канала, выполненной администратором сети. Если маршрут содержит фрагменты пути, пролегающие через обе указанные зоны, возникает проблема оценки такого пути. Как сложить метрики этих участков, ведь они несовместимы? В принципе задача имеет решение, для этого на границах зон с разными протоколами маршрутизации размещаются специальные маршрутизаторы, которые оптимизируют пути для каждого из протоколов (и зон) независимо. Но и в этом случае возможны трудно разрешимые ситуации. Один из таких вариантов показан на рис. 4.4.11.5. |
Рис. 4.4.11.5.
Пусть на рисунке 4.4.11.5 в сетевых зонах, обозначенных кругами используется протокол RIP, а в остальном пространстве - OSPF. ЭВМ обозначены пятиугольниками, внутренние маршрутизаторы прямоугольниками, а окрашенные прямоугольники отмечают пограничные маршрутизаторы зон. Любые маршруты из зоны А в зону Б проблем не вызовут, так как внутри зоны маршруты оптимизируются RIP, а между зонами - протоколом OSPF. Рассмотрим прокладку маршрута из зоны Б в зону В. Здесь следует рассмотреть варианты пути через зоны Г и Д. Важно то, что при выборе оптимального пути придется как-то учитывать метрики как OSPF-части пути, так и фрагменты транзитного пути внутри зон. При этом надо принять решение, с какими весами складывать метрики разных протоколов. Эта проблема снимается, если каждая зона имеет только один пограничный маршрутизатор. Маршрут прокладывается между пограничными маршрутизаторами, а различие маршрутов внутри зон игнорируется. Кстати именно эта логика лежит в основе рекомендации для автономной системы иметь только один пограничный маршрутизатор. Поясню это на примере, показанном на рис. 4.4.11.6.
Рис. 4.4.11.6.
Рассмотрим процедуру выбора пути от ЭВМ-1 к ЭВМ-2 из автономной системы AS1 в автономную систему AS2. Имеются метрики, характеризующие путь до маршрутизаторов GW1 и GW2 (M1 и M2). Существует метрика пути от GW1 и GW2 до автономной системы AS2 М3 и М4 (они совсем необязательно равны между собой). В результате мы имеем характеристики двух путей между означенными машинами М1, М3 и М2, М4). Если внутренним протоколом маршрутизации является OSPF или IGMP, то складывать М1 и М4 (соответственно М2 и М4) нельзя, так как в одном случае (М1, М2) это характеристики состояния каналов (администратор назначил их, например, равными 35 и 55), а во втором (М3,М4) - это число шагов до автономной системы AS2 (пусть они равны, например, 6 и 4). Задача сопоставления метрик в этом простом случае может оказаться не по плечу даже суперЭВМ. Примером такой задачи может служить подключение к Интернет узлов ЮМОС (Южная Московская Опорная Сеть), имеющих выход и в АТМ-сеть ПРАН-МГУ.
Если бы у AS1 был только один пограничный шлюз (например, GW1), то задача решалась бы автоматически. Другим подходом может быть деление всего Интернет на две части, одна делается доступной только через GW1, а вторая - через GW2.
Любая автономная система (AS, система маршрутизаторов, ЭВМ или сетей, имеющая единую политику маршрутизации) может выбрать свой собственный протокол маршрутизации.
Деликатной процедурой алгоритмов маршрутизации является рассылка маршрутной информации. Если предположить, что один маршрутизатор получил пакет с новыми данными, а другой нет (потерялся или еще не дошел), то эти два прибора будут использовать разное представление о топологии сети, что может привести к циклам пакетов, осцилляции маршрутов и другим неприятностям. Первое, что приходит в голову для синхронизации маршрутной картины сети - это широковещательная рассылка маршрутных данных. При этом каждому пакету можно присваивать порядковый номер. Анализ этого номера позволяет маршрутизатору избавляться от пакетов дубликатов и от кадров с устаревшей информацией. Получив новый пакет, маршрутизатор переадресует его на все свои интерфейсы кроме того, через который он пришел. Такой алгоритм может встать в тупик в случае переполнения номера пакета. Допустим, после номера N придет пакет с номером 1. В этом случае он будет отброшен как дубликат ранее пришедшего или как кадр, несущий устаревшие данные. Если использовать 32-разрядные номера пакетов, при частоте рассылки один пакет в секунду переполнение счетчика произойдет более чем через 136 лет. Такая угроза вряд ли кого-то напугает.
Другой проблемой является ситуация при которой маршрутизатор оказался временно отключен от сети переменного тока и был перезагружен. В этом случае он не будет знать, какой номер кадра следует ожидать. Кроме того, вполне реалистично предположить, что за 136 лет счетчик пакетов в маршрутизаторе может сбиться. Последствия могут оказаться плачевными.
Для решения всех этих проблем можно ввести помимо номера еще и возраст пакета и уменьшать его на единицу раз в секунду. Когда возраст станет равным нулю, маршрутная информация из маршрутизатора удаляется и процедура начинается с нуля.
Другим решением может быть схема, при которой входной пакет, предназначенный для рассылки, посылается соседям не сразу, а выдерживается некоторое время в буфере. Если за время выдержки придет очередной пакет, то их порядковые номера сравниваются. Если они равны, то дубликат отбрасывается. При разных номерах отбрасывается более старый. Для обеспечения надежности получение кадра с маршрутной информацией обязательно подтверждается.
Следует учитывать, что каждому сегменту пути может быть присвоено два значения метрики, по одному для каждого из направлений обмена.
Внутренний протокол маршрутизации IGP (Interior Gateway Protocol) определяет маршруты внутри автономной системы. Наиболее популярный IGP - RIP (Routing Information Protocol, RFC-1058), разработан Фордом, Фулкерсоном и Белманом (фирма XEROX) разработан в 1957-62 годах и использует в качестве метрики вектор расстояния. Протокол был базовым в рамках проекта ARPANET. В качестве метрики может выбираться время доступа, число пакетов в очереди, но обычно - это число шагов до места назначения. Если до цели имеется один промежуточный маршрутизатор, то число шагов считается равным 2. Расстояние до любого из соседей равно одному шагу. В этом протоколе всегда выбирается путь с наименьшим числом шагов до цели (наименьшее значение метрики). Маршрутизация на основе вектора расстояния в принципе позволяет получить положительный результат в любой ситуации, но она имеет одну особенность - процесс сходится быстро при обнаружении нового более короткого пути и работает крайне медленно при исчезновении пути.
| Алгоритм вектора расстояния неявно предполагает, что все каналы имеют равную пропускную способность. |
Существует более новый протокол OSPF (Open Shortest Pass First, RFC-1131, -1245, -1247, -1253, -1584, -1850, -2328, -2740). базирующийся на оценках состояний каналов. Как во всех маршрутных протоколах, использующих состояние канала, многое зависит от того, как вычисляется метрика. Если определяющим фактором выбрать полосу пропускания канала, то при определенных обстоятельствах могут возникнуть трудно преодолимые проблемы. Рассмотрим топологию сети, показанную на рис. 4.4.11.7.
Рис. 4.4.11.7. Пример топологии сети, допускающей осцилляцию маршрутов
Здесь две субсети А и Б соединены двумя каналами 1 и 2. Кружочками обозначены маршрутизаторы. Если в исходный момент времени основной поток между сетями протекает по каналу 2, он может оказаться перегружен, в то время как канал 1 получит меньшее значение метрики из-за отсутствия загрузки. При очередной оценке каналов будет принято решение переключить поток между сетями на канал 1. После этого будет перегружен канал 1 и так может повторяться до бесконечности. Такая ситуация называется осцилляцией маршрутов и ее желательно избегать. Маршрутные таблицы в маршрутизаторах актуализуются вдоль пути с заметными задержками и отнюдь не синхронно. Такие осцилляции могут в разы понизить пропускную способность сети, что необходимо учитывать, выбирая параметры протоколов маршрутизации.
На практике этого не происходит, так как метрики сегментам пути в OSPF присваивает сетевой администратор. Но можно ожидать, что появятся как внутренние, так и внешние протоколы маршрутизации на основе алгоритма состояния канала, которые будут исследовать параметры канала в реальном масштабе времени.
Наиболее старые системы (IGP) используют протокол HELLO. Протокол HELLO поддерживался фирмой DEC, в качестве метрики он использует время, а не число шагов до цели.
Протокол IGRP (Interior Gateway Routing Protocol) разработан компанией CISCO для больших сетей со сложной топологией и сегментами, которые обладают различной полосой пропускания и задержкой. Это внутренний протокол маршрутизации имеет некоторые черты сходства с OSPF.
IGRP использует несколько типов метрики, по одной на каждый вид QOS. Метрика характеризуется 32-разрядным числом. В однородных средах этот вид метрики вырождается в число шагов до цели. Маршрут с минимальным значением метрики является предпочтительным. Актуализация маршрутной информации для этого протокола производится каждые 90 секунд. Если какой-либо маршрут не подтверждает своей работоспособности в течение 270 сек, он считается недоступным. После семи циклов (630 сек) актуализации такой маршрут удаляется из маршрутных таблиц. IGRP аналогично OSPF производит расчет метрики для каждого вида сервиса (TOS) отдельно.
Для взаимодействия маршрутизаторов используются внешние протоколы (EGP - Exterior Gateway Protocols).
Одной из разновидностей EGP является протокол BGP (Border Gateway Protocol, RFC-1268 [BGP-3], RFC-1467 [BGP-4]).
Протокол IDPR (InterDomain Policy Routing Protocol, RFC-1477, -1479) представляет собой разновидность BGP-протокола. Протокол IS-IS (Intermediate System to Intermediate System Protocol, RFC-1195, -1142) является еще одним внутренним протоколом, который используется для маршрутизации CLNP (Connectionless Network Protocol
, RFC-1575, -1561, -1526). IS-IS имеет много общего с OSPF. Смотри также бесклассовый протокол маршрутизации CIDR (RFC-1467, -1517-20).Сразу после включения маршрутизатор не имеет информации о возможностях соседних маршрутизаторов. Статические маршрутные таблицы могут храниться в постоянной памяти или загружаться из какого-то сетевого сервера. По этой причине первейшей задачей маршрутизатора является получение маршрутной информации от соседей, а для начала выявление наличия соседей и их адресов. Для этой цели посылается специальный пакет Hello через каждый из своих внешних интерфейсов. В ответ предполагается получить отклик, содержащий идентификационную информацию соответствующего маршрутизатора. Когда два или более маршрутизаторов объединены через локальную сеть, ситуация несколько усложняется. Смотри рис. 4.4.11.8. Маршрутизаторы E, F, G и H подключены непосредственно к локальной сети, некоторые из них имеют связи с другими маршрутизаторами (сети, которые они обслуживают, на рисунке не показаны).
Одним из способов смоделировать локальную сеть - рассматривать маршрутизаторы E, F, G и H, как соединенные непосредственно, введя виртуальный узел сети L (выделен зеленым цветом). На правой части рисунка показан граф такой сети. Возможность прохода из узла F к G обозначена путем FLG. Для протоколов, учитывающих состояние канала, желательно иметь исчерпывающую информацию о нем (загрузка, задержка, пропускная способность, надежность, стоимость и т.д.). Некоторые из перечисленных параметров довольно легко измерить, например, задержку. Для этого вполне пригоден протокол ICMP. К сожалению многие из указанных параметров довольно сильно коррелированы и подвержены флуктуациям. В частности результаты измерения задержки зависят от загрузки канала (вариация времени ожидания в очереди).
Рис. 4.4.11.8. Маршрутизаторы, подключенные к локальной сети
Рассмотрим трафик на пути А-Н. Допустим на основании анализа состояния канала выбран путь через узел Е. В этом случае он может оказаться перегружен, что приведет к большим задержкам пакетов на пути А-Н. Последующий анализ ситуации может привести к тому, что более оптимальным может оказаться маршрут через узел F. Если будет принято решение переключить трафик на маршрут ACFH, может перегрузиться участок АСF и история повторится. Данный сценарий описывает типичную ситуацию с осцилляциями маршрута. Осцилляции маршрутов не так безобидны, как это может показаться.
К сожалению многие современные протоколы маршрутизации не имеют встроенных средств аутентификации (контроля доступа), что делает их уязвимыми для различных злоупотреблений.
В локальных или корпоративных сетях иной раз возникает необходимость разослать некоторую информацию всем остальным ЭВМ-пользователям сети (штормовое предупреждение, изменение курса акций, телеконференции с большим числом участников и т.д.). Отправителю достаточно знать адреса всех N заинтересованных пользователей и послать им соответствующее сообщение. Данная схема крайне не эффективна, ведь обычная широковещательная адресация предлагает решение в N раз лучше с точки зрения загрузки сети (посылается одно, а не N сообщений). Широковещательная адресация сработает, если в локальной сети нет маршрутизаторов, в противном случае широковещательные адреса МАС-типа заменяются на IP-адреса (что, впрочем, не слишком изящное решение) или применяется мультикастинг адресация. Для мультикастинг адресации в Интернет используются специальные адреса D-класса. Такие адреса позволяют организовать до 250 миллионов групп адресатов, функционирующих одновременно. При посылке пакета по такому адресу доставка не гарантируется и некоторые члены группы могут не получить этот пакет. Маршрутизация для мультикастинга представляет собой отдельную задачу. Ведь здесь надо проложить маршрут от отправителя к большому числу получателей. Традиционные методы маршрутизации здесь применимы, но до крайности не эффективны. Для целей выбора маршрута можно с успехом применить алгоритм "дерево связей" (spanning tree; не имеет циклических структур). Когда на вход маршрутизатора приходит широковещательный пакет, он проверяет, является ли интерфейс, через который он пришел, оптимальным направлением к источнику пакета. Если это так, пакет направляется через все внешние интерфейсы кроме того, через который он пришел. В противном случае пакет игнорируется (так как, скорее всего это дубликат). Этот алгоритм называется Reverse Path Forwarding (переадресация в обратном направлении). Пояснение работы алгоритма представлено на рис. 4.4.11.9 (прямоугольниками на рисунке обозначены маршрутизаторы). Секция I характеризует топологию сети. Справа показано дерево маршрутов для маршрутизатора I (sink tree). Секция III демонстрирует то, как работает алгоритм Reverse Path Forwarding. Сначала I посылает пакеты маршрутизаторам B, F, H, J и L. Далее посылка пакетов определяется используемым алгоритмом.
Рис. 4.4.11.9. Алгоритм Reverse Path Forwarding
При передаче мультимедиа информации используются принципиально другие протоколы маршрутизации. Здесь путь прокладывается от получателя к отправителю, а не наоборот. Это связано с тем, что там при доставке применяется мультикастинговый метод. Здесь, как правило, один отправитель посылает пакеты многим потребителям. При этом важно, чтобы размножение пакета происходило как можно ближе к кластеру адресатов. Такая стратегия иной раз удлиняет маршрут, но всегда снижает результирующую загрузку сети.
В последнее время все больше людей обзаводятся компактными переносимыми ЭВМ, которые они берут с собой в деловые поездки, и хотели бы использовать в привычном режиме для работы в Интернет. Конечно, можно заставить модем дозвониться до вашего модемного пула в офисе, но это не всегда лучшее решение как по надежности так и по цене. Пользователи с точки зрения их подвижности могут быть разделены на три группы:
Предполагается, что все эти пользователи имеют свою постоянную приписку к какой-то сети и соответствующий постоянный IP-адрес. (см. RFC-2794 "Mobile IP Network Access Identifier Extension for IPv4. P. Calhoun, C. Perkins. March 2000). На рис. 4.4.11.10 показана схема подключения подвижных пользователей к Интернет. В этой схеме предполагается наличие в каждой области сети Интернет внешнего агента, обеспечивающего доступ к этой зоне подвижных ЭВМ (на рисунке такой агент помечен надписью "чужая LAN"). Доступ может осуществляться через мобильную телефонную сеть. Предполагается также наличие соответствующего агента в "домашней" LAN, куда стационарно приписана данная ЭВМ. Домашний агент отслеживает все перемещения своих пользователей, в том числе и тех, кто подключается к "чужим" LAN.
Рис. 4.4.11.10. Схема подключения к Интернет подвижных объектов
Когда к локальной сети подключается новый пользователь (непосредственно физически или через модем сотовой телефонной сети), он должен там зарегистрироваться. Процедура регистрации включает в себя следующие операции:
Когда пользователь покидает зону обслуживания данной LAN или MAN, регистрация должна быть аннулирована, а ЭВМ должна быть автоматически зарегистрирована в новой зоне. Когда посылается пакет мобильному пользователю, "домашняя LAN", получив его, маршрутизирует пакет внешнему агенту, зарегистрировавшему данного пользователя. Этот агент переправит пакет адресату.
Процедуры переадресации выполняются с привлечением технологии IP-туннелей. Домашний агент предлагает отправителю посылать пакеты непосредственно внешнему агенту области, где зарегистрирована подвижная ЭВМ. Существует много вариантов реализации протокола с разным распределением функций между маршрутизаторами и ЭВМ. Существуют схемы и временным выделением резервного IP-адреса подвижному пользователю. Международный стандарт для решения проблемы работы с подвижными пользователями пока не разработан.
При широком внедрении IPv6 с практически неограниченным ресурсом адресов проблемы выделения IP-адреса вообще не будет.
В последнее время конфигурирование сетевого оборудования (маршрутизаторов, DNS и почтовых серверов усложнилось настолько, что это стало составлять заметную часть издержек при формировании коммуникационного узла. Заметного упрощения и удешевления маршрутизаторов можно ожидать при внедрении IPv6. Следующим шагом станет внедрение объектно-ориентированного языка описания маршрутной политики RPSL (Routing Policy Specification Language). Здесь конфигурирование маршрутизатора будет осуществляться на основе описанной маршрутной политики.
Теперь немного подробнее о наиболее популярных протоколах маршрутизации - RIP, OSPF, IGRP и BGP-4. Начнем с внутреннего протокола маршрутизации RIP.
Previous: 4.4.10 Протокол загрузки BOOTP
UP:
4.4 Интернет |
