Понятие протокола, и связанные с ним понятия
| Вид материала | Документы |
- Программа курса лекций, 33.31kb.
- А, а также связанные с этим сервисы, частично или полностью через пакетные сети, 211.32kb.
- Тема Основные понятия о правовых явлениях, 165.32kb.
- Контрольная работа по предмету «Логика», 57.32kb.
- Понятия налоги и налогообложение. Налоговая система понятие налога и сбора. Принципы, 2182.16kb.
- Задачи: Продолжить формирование понятия о внутренней среде и ее компонентах. Раскрыть, 161.91kb.
- Естественные науки 14 апреля с 10. 00 до 17., 82.95kb.
- Словари профессий, 47.56kb.
- Программа форума «служба протокола» день первый (02. 06. 2011г., четверг), 114.5kb.
- Программа форума «служба протокола» день первый (02. 06. 2011г., четверг), 107.69kb.
Маршрутизация. Общие положения.
Общее понятие о маршрутизации.
Передача сообщений в больших по территориальному охвату, сложных и неоднородных по структуре сетях, где, как правило, существует несколько путей передачи информации от отправителя к получателю, проблема выбора пути передачи информации становится достаточно сложной.
Проблему выбора пути решают алгоритмы маршрутизации. Если транспортировка данных осуществляется дейтограммами, для каждой из них эта задача решается независимо. При использовании виртуальных каналов выбор пути выполняется на этапе формирования этого канала. В TCP/IP сетях с их дейтограмным режимом передачи IP-пакетов реализуется первый вариант, а, например, в X.25 сетях - второй.
Алгоритм маршрутизации должен обладать вполне определенными свойствами: надежностью, корректностью, стабильностью, простотой и оптимальностью.
Оптимальность – понятие не столь простое, как может показаться, поскольку все зависит от того, по какому или каким параметрам производится оптимизация.
Критерии оптимальности, очевидно, могут быть разными для разных видов трафика.
Среди параметров оптимизации может быть минимальное число промежуточных узлов (и, следовательно, минимальное количество сетей и/или каналов связи, через которые осуществляется передача), минимальная задержка доставки, максимальная пропускная способность, минимальная цена, максимальная надежность или минимальная вероятность ошибки.
Алгоритмы маршрутизации бывают адаптивными (динамическими) и статическими (неадаптивными). Последние, осуществляя выбор маршрута, не принимают во внимание изменения топологии или загрузку каналов. Они предполагают, что все изменения в маршрутную таблицу вносит администратор сети, который все предусмотрел заранее (администратор всегда прав!). Адаптивные же алгоритмы предполагают периодическое измерение характеристик каналов и постоянное исследование топологии маршрутов. Выбор того или иного маршрута здесь производится на основании этих измерений.
В этом случае необходима какая-то процедура обмена информацией о состоянии сети между маршрутизаторами, а это создает дополнительную нагрузку на сеть, в некоторых случаях весьма значительную, что также следует учитывать при выборе алгоритма маршрутизации.
IP делит все ЭВМ на маршрутизаторы (router, или gateway – шлюзы) и обычные ЭВМ (узлы, host), последние, как правило, не рассылают свои маршрутные таблицы. Предполагается, что маршрутизатор владеет исчерпывающей информацией о правильных маршрутах (хотя это не совсем так). Обычная ЭВМ имеет минимальную маршрутную информацию (например, адреса маршрутизатора локальной сети и сервера имен).
Проблема оптимальной маршрутизации в современном Интернет, насчитывающем десятки миллионов сетей, весьма сложна. Полная таблица всех оптимальных маршрутов здесь может содержать более 107! записей.
Наличие большого количества протоколов маршрутизации показывает, что ни один из них не удовлетворяет всем требованиям, которые предъявляются к протоколу маршрутизации в различных условиях.
В ряде случаев на одном маршрутизаторе может работать 2 или более протоколов маршрутизации. Разумеется, разные протоколы используются для разных адресов, например, один для локальных, другой для удаленных. Наличие различных протоколов, одновременно используемых в одной сети, создает проблему согласования. Эта проблема в интернете разрешается через механизм автономных систем.
Автономная система может содержать множество маршрутизаторов, взаимодействующих между собой по разным протоколам. Согласование их использования внутри АС – в компетенции ее администратора, но взаимодействие с другими автономными системами она осуществляет только через специальные маршрутизаторы, называемые пограничными (border gateway, отсюда название протокола BGP), в соответствии с единым для всех АС протоколом (в настоящее время это протокол BGP-4).
Нужно четко разделять работу протоколов маршрутизации, которые формируют маршрутные таблицы, и процесс маршрутизации пакетов, когда эти таблицы используются.
Используют маршрутные таблицы все маршрутизаторы, а в усеченном виде – и оконечные узлы. А вот формированием маршрутных таблиц некоторые маршрутизаторы могут и не заниматься, получая ее в готовом виде от другого маршрутизатора (диспетчера маршрутов), либо таблицы могут формироваться вручную администратором (статическая маршрутизация, например, в X.25).
Если адресат достижим более чем одним путем, маршрутизатор должен сделать выбор, этот выбор осуществляется на основании оценки маршрутов-кандидатов. Обычно каждому сегменту, составляющему маршрут, присваивается некоторая величина – метрика (оценка) этого сегмента. Каждый протокол маршрутизации использует свою систему оценки маршрутов. Здесь следует обратить внимание на то, что при выборе маршрута всем сегментам пути должны быть даны сопоставимые значения метрики. Ряд протоколов, например, OSPF, ведут несколько метрик связей, по одной для каждого поддерживаемого типа сервиса (IP – минимизация задержки, максимизация пропускной способности и максимизация надежности, минимизация стоимости), но для каждого пакета метрика, выбранная на основании запрошенного типа сервиса, должна применяться последовательно.
Большинство алгоритмов учитывают топологию связей, реже их качество (пропускную способность), и очень редко – загрузку. Но существуют подходы к решению проблемы статической маршрутизации, учитывающие как топологию, так и загрузку (flow-based routing). В некоторых сетях потоки между узлами относительно стабильны и предсказуемы. В этом случае появляется возможность вычислить оптимальную схему маршрутов заранее. Здесь на основе теории массового обслуживания производится оценка средней задержки доставки (или другого параметра, по которому требуется оптимизация) для каждой связи. Топология маршрутов оптимизируется по значению выбранного параметра (например, минимальной задержки доставки пакета).
Маршрутизация пакетов по таблицам и без таблиц.
Помимо маршрутизации с использованием таблиц, существуют ряд методов маршрутизации, обходящихся без таблиц.
По локальным сетям нам уже знакомы лавинная маршрутизация и маршрутизация от источника.
Лавинная маршрутизация в чистом виде даже в локальных сетях создает проблемы, связанные с перегрузкой сетей и каналов связи многочисленными копиями одного и того же сообщения, а также с возможностью зацикливания пакетов, если топология это допускает. В региональных и глобальных сетях накладные расходы, связанные с лавинной маршрутизацией, слишком велики, поэтому в чистом виде она в этих сетях не используется. Тем не менее, в варианте селективной широковещательной рассылки, когда рассылка производится не по всем возможным направлениям, а только по тем, которые предположительно ведут в правильную сторону, она все же применяется там, где нужна предельно возможная надежность, например в военных приложениях, когда весьма вероятно повреждение тех или иных каналов. Подобные методы могут использоваться при формировании виртуального канала – они всегда обеспечивают наикратчайший путь, так как перебираются все возможности, а накладные расходы на выбор пути компенсируются оптимальностью соединения.
В TCP/IP рудиментом лавинной маршрутизации является система маршрутов по умолчанию. Если для данного адреса отсутствует запись в маршрутной таблице, пакет передается маршрутизатору по умолчанию. Во многих случаях это разумный подход, например, узел всегда посылает пакеты, предназначенные удаленным узлам, маршрутизатору своей локальной сети, адреса, неразешимые в рамках автономной системы – пограничному маршрутизатору этой системы и т.д.. Маршруты по умолчанию заметно сокращают размер маршрутной таблицы. Маршрут по умолчанию может помочь реализовать связь даже при ошибках в маршрутной таблице. Но осторожно! Помимо знакомой нам опасности зацикливания, маршрут, образовавшийся с использованием маршрутизации по умолчанию вполне может быть далек от оптимального. Экономия на памяти для маршрутных таблиц – дурной стиль, который не доведет до добра. Это может не иметь никаких последствий для малых сетей, но для региональных сетей с ограниченной пропускной способностью такое решение может повлечь серьезные последствия. Из-за отсутствия записи в таблице о какой-то локальной сети, предназначенные ей пакеты могут быть отправлены куда угодно, хоть на другой конец света. Например, из-за такого рода ошибки довольно долго пакеты из Ярославля в Москву шли через США, Известен случай, когда машины, размещенные в соседних комнатах Президиума РАН, вели обмен через Амстердам.
Другой известный нам алгоритм – маршрутизация в режиме от источника. В этом случае информация о маршруте передачи пакета записывается в самом пакете (в IP – в поле опций), маршрутизатору остается из нее извлечь очередной адрес, модифицировать указатель и отправить пакет по извлеченному адресу. Поскольку путь записывается в пакете, получатель может выбрать оптимальный маршрут по своим критериям маршрут и уведомить об этом отправителя. В IP маршрутизацию от источника реализуют три опции:
Тип 7 Record Route (Записать маршрут)
00000111 длина (1байт) указатель (1байт) данные о маршруте
Опция записи маршрута дает средства для записи маршрута IP пакета.
Опция начинается с кода типа. Второй байт определяет длину опции, которая учитывает код типа опции, сам себя, байт указателя и длину данных о маршруте. Третий байт является указателем на данные маршрута. Указатель определяет байт, с которого начинается следующее поле для размещения адреса маршрута.
Указатель отсчитывается от начала рассматриваемой опции, а его наименьшее допустимое значение - 4.
Записываемый маршрут состоит из серии IP адресов. Каждый IP адрес - это 32 бита или 4 байта. Если указатель больше, чем длина опции, то поле с записываемым маршрутом заполнено. Хост-компьютер, создающий эту опцию, должен зарезервировать поле с данными о маршруте и достаточным размером, с тем, чтобы оно вместило все ожидаемые адреса. Размер этой опции не изменяется при добавлении адресов. Первоначальное содержимое поля под данные о маршруте должно быть нулевым.
Когда IP модуль направляет пакет, он проверяет ее на присутствие рассматриваемой опции с записываемым маршрутом. Если она присутствует, то он вставляет свой собственный IP-адрес в качестве распознанного во внешней среде, куда этот пакет направлен. Вставка осуществляется в опцию записи маршрута, в то место, на которое указывает байт указателя. Указатель затем увеличивается на 4.
Если поле с данными о маршруте уже заполнено (указатель превышает длину), то пакет направляется без вставки адреса в опцию заполняемого маршрута. Если имеется некоторое пространство, но недостаточное для вставки полного адреса, то исходный пакет считается ошибочным и уничтожается. И в том, и в другом случае на хост-отправитель направляется ICMP сообщение о проблеме с параметром.
При фрагментации не копируется, присутствует лишь в первом фрагменте. В пакете присутствует не более одного раза.
Тип 137 Strict Source and Record Route
(Точный отправитель и записать маршрут)
10001001 длина указатель данные о маршруте
Опция "уточнить отправитель и записать маршрут" (SSRR) дает средства отправителю IP пакета для поддержания информации о маршрутизации, которая должна использоваться шлюзами при передаче пакета по назначению, а также для записи этой информации.
Опция начинается с кода типа. Второй байт – длина опции, которая учитывает код типа опции и байт длины, байт указателя. Третий байт является указателем на данные маршрута, определяющим байт, с которого начинается следующий адрес отправителя, подлежащий обработке. Указатель отсчитывается с начала этой опции, а наименьшее допустимое значение указателя - 4.
Данные о маршруте состоят из серии IP адресов. Каждый IP адрес - это 32 бита или 4 байта. Если указатель превышает длину, то маршрут отправителя пуст (записываемый маршрут полон), а маршрутизация основывается на значении поля с адресом получателя.
Если адрес в поле адреса получателя достигнут, а указатель не превышает длины, то следующий адрес в маршруте отправителя замещает адрес в поле с адресом получателя, а записанный адрес маршрута замещает только что использованный адрес отправителя, указатель увеличивается на 4.
Записанный адрес маршрута - это собственный IP-адрес Internet - модуля, как он был бы распознан во внешней среде, куда этот пакет направляется. Эта процедура замещения маршрута отправителя записанным маршрутом (хотя в обратном порядке он должен использоваться как маршрут отправителя) означает, что опция (и весь IP заголовок) сохраняет постоянный размер при прохождении пакета через IP систему.
Эта опция является точным маршрутом отправителя, поскольку шлюз или IP хост должен посылать данный пакет непосредственно на следующий адрес в маршруте отправителя через напрямую соединенную сеть, на адрес, показывающий следующий шлюз или хост, указанный в маршруте.
Опция должна копироваться при фрагментации. Появляется не более одного раза в пакете.
Тип 131 Loose Source and Record Route
(Потеря отправителя и запись маршрута)
10000011 длина указатель данные о маршруте
Опция потери отправителя и записи маршрута (LSRR) обеспечивает средства, позволяющие отправителю IP пакета передавать информацию, используемую шлюзами при передаче пакетов по назначению, а также записывать информацию о маршруте.
Опция начинается с кода типа. Второй байт - байт длины, которая учитывает код типа опции и сам себя, а также байт указателя.
Третий байт является указателем на данные о маршруте, он определяет байт, с которого начинается следующий адрес отправителя, подлежащий обработке. Указатель отсчитывается от начала рассматриваемой опции, а его наименьшее допустимое значение - 4.
Данные о маршруте состоят из ряда IP адресов. Каждый IP адрес - это 32 бита или 4 байта. Если указатель превышает длину, то маршрут отправителя пуст (поле с записями маршрута заполнено), а маршрутизация должна основываться на значениях поля с адресом получателя.
Если адрес, записанный в поле адреса получателя, достигнут, а указатель не превысил длину, то следующий адрес в маршруте отправителя замещает адрес в поле с адресом получателя. Записанный адрес маршрута заменяет только что использованный адрес отправителя, а указатель увеличивается на 4.
Эта опция называется потерей маршрута отправителя (loose source route), поскольку шлюз или IP хост могут использовать любые маршруты через любое количество других промежуточных шлюзов для достижения следующего адреса в рассматриваемом маршруте. Такой режим позволяет обойти ограничение на длину маршрута, определяемое максимум 40 байтами поля опций, что позволяет указать только 9 адресов. При фрагментации опция должна копироваться. В пакете она должна появляться не более одного раза.
Маршрутизация, управляемая событиями – режим, при котором передача производится по маршруту, который до того приводил к успеху. Также могут приниматься во внимание другие события, происходящие при передаче пакетов в сеть. Не является самостоятельным режимом, но может применяться в комбинации с другими. Фактически, как и маршрутизация по умолчанию, она в IP-маршрутизаторах применяется совместно с табличной. Пример события, понуждающего IP-узел внести изменения в таблицу независимо от протокола маршрутизации – сообщение ICMP о переадресации.
В IP сетях предполагается, что путь передаваемого пакета (если не используется опция маршрутизации от источника) определяется пошагово. Каждый узел, через который проходит пакет, начиная с отправителя, выбирает, какому следующему узлу его направить (фактически, кроме отправителя и получателя, все промежуточные узлы на маршруте являются маршрутизаторами).
Алгоритм выбора следующего маршрутизатора универсален и не зависит от протокола маршрутизации, который используется для формирования маршрутной таблицы:
Извлечь IP-адрес (ID) места назначения из пакета.
Вычислить IP –адрес сети назначения (IN)
IF IN соответствует какому-либо адресу локальной сети, непосредственно подключенной к данному узлу, послать пакет по этому адресу;
ELSE IF IN присутствует в маршрутной таблице, то послать пакет к маршрутизатору, указанному в таблице;
ELSE IF описан маршрут по умолчанию, то послать пакет к этому маршрутизатору;
ELSE выдать сообщение об ошибке маршрутизации (сеть недоступна).
Если сеть включает в себя подсети, то для каждой записи в маршрутной таблице производится побитная операция <И> для ID и маски подсети. Если результат этой операции совпадет с содержимым адресного поля сети, пакет посылается серверу подсети. При наличии подсетей в маршрутную таблицу добавляются соответствующие записи с масками и адресами сетей.
Совпадающих записей, вообще говоря, может быть несколько, поскольку маска может быть любой, от 0 (для маршрутизатора по умолчанию, наложение маски 0 на любой адрес дает 0), до 255.255.255.255 (все единицы – это случай, когда маршрут ведет к узлу, адресуемому отдельно от остальных узлов своей сети/подсети). Если совпадений несколько, выбирается тот маршрут, маска которого старше (содержит больше единиц).
Адрес в таблице маршрутизации соответствует либо самому конечному узлу-получателю (если он находится в сети, подключенной к одному из портов данного маршрутизатора), либо следующему маршрутизатору на оптимальном пути. Полный маршрут, ради экономии места, в таблице не храниться. В зависимости от алгоритма маршрутизации, маршрутизатор может его и не знать, поскольку он может быть построен последовательно шаг за шагом каждым маршрутизатором.
Такой подход базируется на следующем утверждении (принцип оптимальности). Если маршрутизатор M находится на оптимальном пути от маршрутизатора I к маршрутизатору J, то оптимальный путь от М к J проходит по этому пути. Действительно, обозначим оптимальный маршрут I-M R1, а M-J – R2. Если существует маршрут M-J оптимальнее, чем R2, то он должен быть объединен с R1, чтобы образовать оптимальный путь I-J, что противоречит исходному утверждению об оптимальности пути R1+R2.
Следствием принципа оптимальности является утверждение, что оптимальные маршруты от всех отправителей к общему месту назначения образуют дерево, лишенное циклов (sink tree). Это, в свою очередь означает, что любой пакет будет доставлен за строго ограниченное время, пройдя строго определенное число маршрутизаторов. Правда, в общем случае, такое дерево может быть не единственным, могут существовать другие деревья с теми же длинами пути. С такой проблемой мы уже встречались в курсе СТТ при рассмотрении алгоритма покрывающего дерева для прозрачных коммутаторов, когда для выбора единственного дерева приходилось задействовать идентификаторы коммутаторов и портов.
Исходя из описания принципа IP-маршрутизации, маршрутная таблица должна включать в себя, по крайней мере, следующие поля:
- IP адрес сети назначения;
- маску для сети назначения;
- IP адрес следующего маршрутизатора, и номер порта (интерфейса), через который он достижим (Next Hop). Здесь возможны варианты, например, IP адрес маршрутизатора не нужен для непосредственно подключенной сети, либо для канала точка-точка, соединяющего два маршрутизатора.
Кроме того, таблица может включать в себя другие поля, например, метрику маршрута, признак источника информации, время жизни (для динамических записей), признак, что пакеты с такими адресами следует обрабатывать особым способом (скажем, отбрасывать, либо упаковывать в другой пакет и отправлять по определенному адресу, проверять определенные поля пакета и действовать по результатам проверки и т.д.). Список дополнительных полей может меняться от маршрутизатора к маршрутизатору.
Создание и модификация таблиц маршрутной информации. Виды протоколов маршрутизации.
В случае статической маршрутизации все записи таблиц маршрутизации создаются и изменяются исключительно администратором сети.
В маршрутизаторе с динамическим протоколом резидентно загруженная программа-драйвер изменяет таблицы маршрутизации на основе информации, полученной от соседних маршрутизаторов. Например, в ЭВМ, работающей под управлением ОС UNIX и выполняющей функции маршрутизатора, эту задачу часто решает резидентная программа gated или routed (демоны). Последняя поддерживает только внутренние протоколы маршрутизации.
Сразу после включения маршрутизатор не имеет информации о возможностях соседних маршрутизаторов. Статические маршрутные таблицы могут храниться в постоянной памяти, на жестком диске, или загружаться из какого-то сетевого сервера. По этой причине первейшей задачей маршрутизатора является получение маршрутной информации от соседей, для начала выявление наличия соседей и их адресов. Для этой цели посылается специальный пакет Hello через каждый из своих внешних интерфейсов. В ответ предполагается получить отклик, содержащий идентификационную информацию соответствующего маршрутизатора. Примитивным вариантом такого протокола обмена информацией о маршрутах являются известные нам ICMP сообщения Router Advertisement (Тип 9) и Router Advertisement Request (Тип 10).
Когда два или более маршрутизаторов объединены через локальную сеть, ситуация несколько усложняется. Во-первых, теперь для данной локальной сети можно назначить несколько маршрутизаторов по умолчанию, а это создает проблемы с фильтрацией дубликатов. Во-вторых, при этом возможны осциляции маршрутов, если маршрутизаторы анализируют их загруженность, а это может привести к сложным эффектам, которые могут понизить пропускную способность в разы.
Существуют две большие группы алгоритмов маршрутизации – дистанционно-векторные алгоритмы и алгоритмы состояния связей.
Примером первой группы является протокол RIP.
Маршрут здесь характеризуется вектором расстояния до места назначения. Предполагается, что каждый маршрутизатор является отправной точкой нескольких маршрутов до сетей, с которыми он связан. Описания этих маршрутов хранятся в специальной таблице, называемой маршрутной. Таблица маршрутизации RIP изначально содержит по записи на каждую непосредственно подключенную сеть или канал (на каждый маршрут). Информация о непосредственно подключенных сетях хранится на жестком диске, а их работоспособность (шире – режим работы) определяется средствами уровня сетевых интерфейсов. На основании этой информации определяется метрика пути в каждую сеть. Свою минимальную таблицу маршрутизатор широковещательно передает всем связанным с ним маршрутизаторам. При этом информация о каждой сети включает номер и маску сети, IP-адрес маршрутизатора, заявляющего о ней, и метрику, с которой она достижима.
Последним двум полям записи мы обязаны появлению термина вектор расстояния (место назначение – направление; метрика – модуль вектора).
Маршрутизатор-получатель просматривает таблицу. Если в таблице присутствует новый путь (к ранее неизвестной сети), эти изменения фиксируются получателем в своей маршрутной таблице. При этом он фиксирует, через какой маршрутизатор достижима сеть, метрику (измененную с учетом метрики сети, через которую он связан с объявившим ее маршрутизатором), и время получения сообщения.
Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы (уже не минимальной) всем соседям-маршрутизаторам, с которыми связан непосредственно. Маршрутизатор-получатель просматривает таблицу. Если в таблице присутствует новый путь или сообщение о более коротком маршруте, или произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице. Тайм-аут-таймер сбрасывается каждый раз, когда маршрут инициализируется или корректируется, или подтверждается. Если со времени последней коррекции прошло 3 минуты или получено сообщение о том, что вектор расстояния равен 16, маршрут считается закрытым. Но запись о нем не стирается, пока не истечет время "уборки мусора" (2мин). При появлении эквивалентного маршрута переключения на него не происходит, таким образом, блокируется возможность осцилляции между двумя или более равноценными маршрутами.
Постепенно все маршрутизаторы сети узнают обо всех подсетях и выбирают маршрутизатор, которому следует передавать пакеты для этой сети. При этом полного маршрута к сети (кроме непосредственно подключенных) ни один маршрутизатор не знает – только метрику и следующий маршрутизатор11.
Это упрощает алгоритм, но во многих случаях это та простота, про которую говорят, что она хуже воровства. В частности, это создает проблемы с обновлением устаревшей маршрутной информации, и может в ряде случаев приводить к зацикливанию маршрутов. Проблемы дистанционно-векторных алгоритмов мы рассмотрим ниже на примере протокола RIP.
Алгоритмы маршрутизации, основанные на состоянии связей, например, OSPF (Open Shortest Pass First, RFC-1245-48, RFC-1583-1587) передают друг другу полную информацию о топологии сети. OSPF представляет собой протокол состояния маршрута (в качестве метрики используется коэффициент качества обслуживания). Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов автономной системы. Протокол OSPF реализован в демоне маршрутизации gated, который поддерживает также RIP и внешний протокол маршрутизации BGP.
Автономная система может быть разделена на несколько областей, куда могут входить как отдельные ЭВМ, так и целые сети. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS. Сеть обычно имеет выделенный (designated) маршрутизатор, который является источником маршрутной информации для остальных маршрутизаторов AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. Если к месту назначения ведут два или более эквивалентных маршрута, информационный поток будет поделен между ними поровну. Для дистанционно-векторных протоколов такое обычно невозможно – слишком велик риск зацикливания пакетов. Переходные процессы в OSPF завершаются быстрее, чем в RIP. В процессе выбора оптимального маршрута анализируется ориентированный граф сети.
Маршрутизация для мультикастинга представляет собой отдельную задачу. Ведь здесь надо проложить маршрут от отправителя к большому числу получателей. Традиционные методы маршрутизации здесь применимы, но до крайности не эффективны. Здесь для целей выбора маршрута можно с успехом применить алгоритм "расширяющееся дерево" (spanning tree; не имеет циклических структур). Когда на вход маршрутизатора приходит широковещательный пакет, он проверяет, является ли интерфейс, через который он пришел, оптимальным направлением к источнику пакета. Если это так, пакет направляется через все внешние интерфейсы кроме того, через который он пришел. В противном случае пакет игнорируется (поскольку это, скорее всего, дубликат). Этот алгоритм называется Reverse Path Forwarding (переадресация в обратном направлении). Желательно также, чтобы дерево разветвлялось возможно ближе к получателям, даже если это удлиняет маршрут.