различаются по нескольким ключевым характеристикам. Во-первых, на работу протокола маршрутизации влияют цели, которые ставились разработчиком алгоритма. Во-вторых, различные виды алгоритмов по-разному используют ресурсы сети и маршрутизаторов. Наконец, алгоритмы маршрутизации применяют различные метрики, влияющие на выбор оптимальных маршрутов. Эти свойства алгоритмов маршрутизации будут проанализированы в следующих разделах.

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

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

Оптимальность;

Простота и минимальный объем передаваемой служебной информации;

Надежность и устойчивость алгоритма;

Быстрая сходимость;

Гибкость.

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

Кроме того, алгоритмы маршрутизации стараются сделать как можно более простыми. Иными словами, алгоритм маршрутизации должен эффективно выполнять свои функции с минимальными затратами на передачу служебной информации - как программными, так и аппаратными. Эффективность алгоритма особенно важна в том случае, когда реализующее его программное обеспечение работает на компьютере с ограниченными физическими ресурсами.

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

Кроме того, алгоритмы маршрутизации должны быстро сходиться. Под сходимостью понимается процесс согласования оптимальных маршрутов всеми маршрутизаторами. Когда в сети происходит такое событие, как выход из строя маршрутизатора или, наоборот, начало или возобновление его работы, другие маршрутизаторы распространяют по всем сетям сообщения об обновлении маршрутов, вследствие чего происходит повторное вычисление оптимальных маршрутов и согласование их между всеми маршрутизаторами. Если алгоритм маршрутизации медленно сходится, то это может привести к появлению петель маршрутизации или к недоступности части сети.

Формирование петли маршрутизации проиллюстрировано на рис. 6.3. Пакет поступает на маршрутизатор Router 1 в момент времени tl. Этот маршрутизатор уже получил сообщение об обновлении маршрута, и следовательно, ему известно, что следующим переходом на оптимальном маршруте к получателю является маршрутизатор Router 2, поэтому Router 1 пересылает пакет на маршрутизатор Router 2. Однако Router 2 еще не получил сообщение об обновлении маршрута, и, по его данным, следующим переходом на оптимальном маршруте к получателю является маршрутизатор Router 1. Соответственно, Router 2 пересылает пакет обратно на маршрутизатор Router 1. В результате пакет будет перемешаться между этими двумя маршрутизаторами, пока на маршрутизаторе Router 2 не будут обновлены маршруты или не будет превышено максимально допустимое количество переходов.

Рис. 6.3. Медленная сходимость и петли маршрутизации препятствуют прохождению пакетов

также должны быть гибкими, т.е. быстро и точно адаптироваться к различным сетевым условиям. Например, предположим, что один из сетевых сегментов вышел из строя. Такая проблема учитывается во многих алгоритмах маршрутизации. В такой ситуации необходимо быстро выбрать для всех маршрутов, обычно проходящих через этот сегмент, оптимальный обходной путь. Алгоритм маршрутизации должен по возможности адаптироваться к изменениям полосы пропускания, длины очереди на маршрутизаторе и сетевым задержкам, а также к другим параметрам.

Типы алгоритмов маршрутизации

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

Статическая или динамическая маршрутизация;

Наличие одного или нескольких маршрутов к одному получателю;

Линейная или иерархическая маршрутизация;

Выполнение алгоритма на исходном узле или на промежуточных маршрутизаторах;

Внутридоменная или междоменная маршрутизация;

Маршрутизация по состоянию канала или дистанционно-векторная маршрутизация.

Статическая и динамическая маршрутизация

Алгоритмы статической маршрутизации представляют собой не столько алгоритмы, сколько таблицы, составленные сетевым администратором прежде чем включить маршрутизаторы. Содержимое этих таблиц может быть изменено только сетевым администратором. Алгоритмы, использующие статические маршруты, просты и эффективно работают в сравнительно простых сетях с относительно предсказуемым характером передачи данных.

Поскольку системы статической маршрутизации не реагируют на изменения в сети, они, как правило, не подходят для современных крупных, постоянно изменяющихся сетей. Большинство используемых в настоящее время алгоритмов являются алгоритмами динамической маршрутизации, которые адаптируются к изменениям сетевой обстановки, анализируя поступающие сообщения об обновлении маршрутов. Если в сообщении указывается на изменения в сети, то программное обеспечение маршрутизации заново вычисляет маршруты и рассылает новые сообщения об обновлении маршрутов. Эти сообщения распространяются по сети, заставляя маршрутизаторы заною запускать алгоритмы маршрутизации и вносить соответствующие изменения в таблицы.

Иногда алгоритмы динамической маршрутизации целесообразно дополнить статическими маршрутами. Например, конечный маршрутизатор (т.е. тот, на который попадают все не поддающиеся маршрутизации пакеты) может служить хранилищем всех таких пакетов. Это гарантирует, что все сообщения будут так или иначе обработаны.

Единственный маршрут или несколько маршрутов

Некоторые сложные протоколы маршрутизации допускают существование нескольких маршрутов к одному получателю. В отличие от алгоритмов, вычисляющих только один маршрут, эти протоколы позволяют распределить потоки данных по нескольким каналам. Преимущества таких алгоритмов очевидны: они значительно ускоряют передачу данных и повышают ее надежность. Такую технологию обычно называют распределением нагрузки (load sharing).

Линейная и иерархическая маршрутизация

Одни алгоритмы маршрутизации работают в линейном пространстве, а другие строят иерархии маршрутов. В системах с линейной маршрутизацией (flat routing) все маршрутизаторы равноправны. В системах с иерархической маршрутизацией некоторые маршрутизаторы образуют аналог маршрутной магистрали. Пакеты поступают от периферийных маршрутизаторов на магистральные маршрутизаторы и передаются по магистрали, пока не достигнут зоны, где расположен получатель. Затем они с последнего магистрального маршрутизатора передаются получателю через один или несколько периферийных маршрутизаторов.

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

Основное преимущество иерархической маршрутизации состоит в том, что она повторяет структуру большинства компаний и поэтому соответствует структуре передачи их данных. Наиболее интенсивный обмен данными происходит внутри малых групп (доменов). Поскольку внутридоменным маршрутизаторам требуется информация только о маршрутизаторах, принадлежащих к их домену, их алгоритмы маршрутизации можно упростить и, соответственно, сократить количество сообщений об обновлении маршрутов.

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

В некоторых алгоритмах маршрутизации весь маршрут определяется узлом- источником. Обычно такой подход называется маршрутизацией на источнике (source muting). В системах с маршрутизацией на источнике маршрутизаторы выполняют только функции запоминания адресов и пересылки пакетов следующему узлу.

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

Внутридоменная и междоменная маршрутизация

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

по состоянию канала и дистанционно-векторные алгоритмы

по состоянию канала (link-state), которые также называют алгоритмами определения кратчайшего маршрута, распространяют информацию о маршрутах по всем узлам объединенной сети. Однако каждый маршрутизатор посылает только ту часть таблицы маршрутизации, которая описывает состояние его собственных каналов. В таких алгоритмах в таблице маршрутизации каждого маршрутизатора составляется картина всей сети. Дистанционно-векторные алгоритмы маршрутизации (также называемые алгоритмами Беллмана-Форда) тоже требуют от каждого маршрутизатора отправки всей таблицы маршрутизации или ее части, но только своим соседям. В сущности, алгоритмы маршрутизации по состоянию канала рассылают небольшие обновления всем остальным маршрутизаторам, а дистанционно-векторные алгоритмы отправляют больше информации, но только соседним маршрутизаторам. При использовании дистанционно-векторных алгоритмов (distance vector algorithm) маршрутизатор имеет информацию лишь о своих соседях.

Поскольку алгоритмы маршрутизации по состоянию канала сходятся быстрее, вероятность образования петель маршрутизации при их использовании несколько меньше, чем при использовании дистанционно-векторных протоколов. С другой стороны, алгоритмы маршрутизации по состоянию канала требуют большей мощности процессора и больше памяти. Поэтому алгоритмы маршрутизации по состоянию канала могут оказаться более дорогостоящими при реализации и поддержке. Протоколы маршрутизации по состоянию канала обычно более масштабируемы, чем дистанционно-векторные протоколы.

Метрики маршрутов

В таблицах маршрутизации содержится информация, используемая коммутирующим программным обеспечением для выбора наилучшего маршрута. Но как именно строятся эти таблицы? Какова природа содержащейся в них информации? Как алгоритмы маршрутизации определяют, что один маршрут предпочтительнее других?

Для определения оптимального маршрута алгоритмы маршрутизации используют множество различных метрик. В сложных алгоритмах маршрутизации выбор маршрута осуществляется по нескольким метрикам, образующим составную (гибридную) метрику. Для определения наилучшего маршрута используются следующие метрики:

Длина маршрута;

Надежность;

Задержка;

Полоса пропускания;

Затраты на передачу.

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

В контексте маршрутизации надежность алгоритма маршрутизации определяется надежностью канала связи (обычно выражаемой отношением количества переданных битов к количеству ошибок). В некоторых каналах сбои могут происходить чаще, чем в других. После сбоя одни каналы восстанавливаются быстрее и проще, другие - медленнее. При назначении рейтингов надежности могут быть учтены любые относящиеся к этому факторы. Такие рейтинги представляют собой числовые оценки, обычно назначаемые линиям связи сетевыми администраторами.

Задержка при маршрутизации представляет собой время, требуемое для доставки пакета по сети от источника к получателю. Величина задержки зависит от многих факторов, таких как полоса пропускания промежуточных линий связи, длина очереди на порту каждого маршрутизатора, переполнения на промежуточных линиях связи, а также физическое расстояние, которое необходимо пройти. Поскольку задержка является комбинацией нескольких важных параметров, эта метрика получила широкое распространение.

Полоса пропускания характеризует пропускную способность канала. При прочих равных условиях 10-мегабитовый канал Ethernet предпочтительнее, чем выделенная линия с полосой пропускания 64 Кбит/с. Хотя полоса пропускания характеризует максимальную пропускную способность канала, маршруты, проходящие по каналам с большей полосой пропускания, не всегда оказываются лучше маршрутов, проходящих по более медленным линиям. Например, если быстрый канал загружен больше, то для передачи по нему пакета получателю может потребоваться больше времени, чем при использовании более медленного, но менее загруженного канала.

Нагрузка характеризует степень занятости сетевого ресурса, например маршрутизатора. Используются различные способы определения нагрузки, в том числе по интенсивности использования процессора и по количеству обрабатываемых в секунду пакетов. Однако сам по себе мониторинг этих параметров может поглощать значительные ресурсы.

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

Сетевые протоколы

Данные маршрутизируемых протоколов передаются по объединенной сети с использованием протоколов маршрутизации. В этом контексте маршрутизируемые протоколы также называют сетевыми протоколами. Эти сетевые протоколы выполняют различные функции, необходимые для взаимодействия приложений пользователя на устройстве- источнике и на устройстве-получателе. Эти функции могут быть самыми разными, в зависимости от используемого стека (набора) протоколов. Сетевые протоколы работают на верхних пяти уровнях эталонной модели OSI: сетевом, транспортном, сеансовом, на уровнях представления и приложений.

Термины маршрутизируемый протокол (routed protocol) и протокол маршрутизации (routing protocol) часто ошибочно воспринимают как равноценные и взаимозаменяемые. Маршрутизируемыми являются протоколы, данные которых передаются по маршрутам объединенной сети, такие, например, как Internet Protocol (IP), DECnet, AppleTalk, Novell NetWare, OSI, Banyan VINES и Xerox Network System (XNS). Протоколы маршрутизации, напротив, представляет собой протоколы, реализующие алгоритмы маршрутизации. Иными словами, протоколы маршрутизации используются промежуточными системами для составления таблиц, по которым определяются маршруты маршрутизируемых протоколов. Протоколами маршрутизации являются такие протоколы, как Interior Gateway Routing Protocol (IGRP), Enhanced Interior Gateway Routing Protocol (Enhanced IGRP), Open Shortest Path First (OSPF), Exterior Gateway Protocol (EGP), Border Gateway Protocol (BGP), Intermediate System-to-Intermediate System (IS-IS) и Routing Information Protocol (RIP). Более подробно маршрутизируемые протоколы и протоколы маршрутизации будут рассмотрены в последующих главах.

Основные принципы управления сетями

введение

В данной главе описаны функции, общие для большинства архитектур и протоколов lf|. управления сетью. Здесь также представлены пять концептуальных областей управле- щ ния, опр^еленныхкЭДеждународной организацией по стандартизации (International Organization for Standardization - ISO). Подробнее эти технологии, протоколы и плат- * форм]ы управления сетьр рассматриваются в части VIII, "Управление сетями".

Что понимается под управлением сетью?

Под управлением се^ыо не всегда понимается одно и то же. В некоторых случаях pef| идет о единственном сетевом консультанте, который следит за работой сети при^омощи устаревщещ анализатора протоколов. В других случаях для управления сетью ислбльзует^ распределенная база данных, автоопрос сетевых устройств и вы- сокопрокзводител^йе рабочие станции, составляющие в реальном времени графи- ^ф^и-^зменений сетевой топологии и объема передаваемых данных. В общем смысле ^ под управлениемеетью понимают службу, использующую разнообразные средства, приложения и у<пт>ойсдаа, которые упрощают для сетевых менеджеров мониторинг и поддержку сетЬ’й|| щ

Историческая справка

начале 80-х годов прошлого века наблюдалось бурное развитие компьютерных ^ сетей. Осознав >экЬномическую выгоду и повышение производительности труда от применения сетевых технологий, компании стали создавать новые сети и расширять существующие почти с той же скоростью, с какой появлялись новые сетевые техно- логии и продукты. К середине 80-х годов XX века некоторые компании начали испытывать. трудности от применения слишком большого количества различных (иногда а несовместимых) сетевых технологий, и этих трудностей становилось все больше.

Проблемы, связанные с расширением сетей, влияют как на повседневное управление работой сети, так и на стратегическое планирование их развития. Каждая новая сетевая технология требует своих отдельных экспертов. В начале 80-х годов одна лишь потребность в обслуживающем персонале для управления большими разнородными сетями стала причиной кризиса во многих организациях. Возникла неотложная необходимость в средствах автоматизированного управления разнородными сетями (в том числе и в т.н. планировании пропускной способности сетей).

Архитектура системы управления сетью

В большинстве систем управления сетью используется одна и та же базовая структура и схема взаимодействия. На конечных станциях (управляемых устройствах), таких как компьютерные системы и другие сетевые устройства, работает программное обеспечение, позволяющее им посылать сообщения о возникающих проблемах (например, о превышении одного или нескольких граничных значений, определенных пользователем). Управляющие элементы запрограммированы таким образом, что они реагируют на получение этих сообщений одним или несколькими действиями, такими как оповещение оператора, запись в журнал событий, выключение системы или попытки ее автоматически восстановить.

Управляющие элементы также могут опрашивать конечные станции для того, чтобы проверить значения отдельных переменных. Агенты, работающие на управляемых устройствах, отвечают на все вопросы, независимо от того, являются ли они автоматическими или инициированы пользователем. Агенты представляют собой программные модули, которые сначала собирают информацию об управляемых устройствах, на которых они работают, затем сохраняют ее в специальной базе данных и предоставляют (самостоятельно или по запросу) управляющим элементам, принадлежащим системам управления сетью (Network Management Systems - NMS) по протоколу управления сетью, такому, например, как простой протокол управления сетью (Simple Network Management Protocol - SNMP) или информационный протокол общего управления (Common Management Information Protocol - CMIP). Управляющими прокси-серверами называются объекты, которые предоставляют управляющую информацию от имени других объектов. Типичная архитектура системы управления сетью показана на рис. 7.1.

Литература:

Руководство по технологиям объединенных сетей, 4-е издание. : Пер. с англ. - М.: Издательский дом «Вильяме», 2005. - 1040 с.: ил. – Парал. тит. англ.

Помазков Виталий Викторович

Описание

Маршрутизация - это действие перемещения информации по межсетевой сети из источника в маршрутизатор назначения (узел). Маршрутизация обычно выполняется с помощью специального устройства, называемого маршрутизатор. Маршрутизация является ключевой особенностью Интернета (беспроводной сети), поскольку она позволяет передавать сообщения с одного компьютера к другому и, в конечном итоге, достигнет целевой машины. Каждый промежуточный компьютер выполняет маршрутизацию, передавая сообщение на следующий компьютер. Часть этого процесса включает в себя анализ таблицы маршрутизации для определения наилучшего пути. Маршрутизация часто путается с мостом, который выполняет аналогичное ограничение. Основное различие между маршрутизацией и мостом является то, что мосты происходят на уровне 2 (канальный уровень), в то время как маршрутизация происходит на уровне 3 (сетевой уровень) эталонной модели OSI. Другая разница в том, что перемычка происходит на более низком уровне и, следовательно, является скорее аппаратным, тогда как маршрутизация происходит на более высоком уровне, где программный компонент более важен. Маршрутизация включает в себя два основных вида деятельности:

1. Определение оптимальных путей

2. Транспортировка информационных групп (обычно называемых пакетами) через межсетевую сеть. Роутеры рассматриваются как специализированные компьютеры, которые отправляют наши сообщения и тем, что каждый другой пользователь Интернета ускоряет их назначения вдоль тысяч пути. Маршрутизатор - это единственное устройство, которое видит каждое сообщение, отправленное любым компьютером на любой из компьютеров сетей. Таблица конфигурации представляет собой набор информации, в том числе:

1. Информацию о том, какие соединения приводят к определенным группам адресов.

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

3. Правила обработки как обычных, так и особых случаев трафика. Две важные задачи маршрутизаторов:

1. Маршрутизатор гарантирует, что информация не идет туда, где она не нужна.

2. Маршрутизатор гарантирует, что информация дойдет до предполагаемого адресата.

При выполнении этих двух заданий маршрутизатор нужен, при работе с двумя отдельными компьютерными сетями. Он объединяет две сети, передавая информацию от одной до другой, и в некоторых случаях выполняет переводы различных протоколов между двумя сетями. Он также защищает сети друг от друга, предотвращая трафик в одном случае для излишнего перетекания на другой. Поскольку количество сетей растет, таблица конфигурации для обработки трафика между ними растет, а вычислительная мощность маршрутизатора увеличивается. Некоторые авторы классифицируют алгоритмы маршрутизации в двух типах:

· Неадаптивные алгоритмы маршрутизации

· Адаптивные алгоритмы маршрутизации

Типы алгоритмов

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

1. Статический и динамический

2. Одноканальный и многоканальный

3. Плоский и иерархический

4. Централизованный и распределенный

5. Host-Intelligent and Router-intelligent

6. Внутри доменный и меж доменный

7. Link-State или Distance-vector

Примерами алгоритмов маршрутизации на расстоянии являются:

· Протокол маршрутизации информации (RIP)

· Протокол маршрутизации внутренних шлюзов (IGRP)

· расширенный протокол маршрутизации внутренних шлюзов (EIGRP)

Примерами алгоритма маршрутизации состояния канала являются:

· Сначала открыть самый короткий путь (OSPF)

· Промежуточная система (IS-IS).

Список литературы :

1. Yashpaul Singh, M.K. Soni, and A.Swamp, «Simulation study of Multipath Routing Algorithm in different situations», IJCSNS International Journal of computer science and network security,Vol.7,No.ll,pp.295-297,2007

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

Алгоритмы маршрутизации пытаются разработать таким образом, что­бы обеспечить самый короткий путь с минимальным временем доставки и наиболее полным использованием пропускной способности сети. Однако на эффективность работы алгоритма могут влиять также следующие ситуации: передача пакета в направлении, не обеспечивающем минимальное время доставки из-за перегрузки какого-то узла (перегрузка сети может происхо­дить из-за большого объема служебной информации, которая используется алгоритмом маршрутизации). Неоперативный учет изменения состояния сети, который обусловлен как отказами некоторых узлов и каналов, так и появлением новых узлов в связи с развитием сети. Для эффективной работы алгоритма необходимо каждый маршрутизатор снабжать информацией о текущей топологии сети, пропускной способности каналов. Любой маршру­тизатор работает в режиме неопределенности и пульсирующей нагрузки.

Таким образом, при разработке алгоритмов маршрутизации преследуются следующие цели:

Оптимальность – способность алгоритмов маршру­тизации выбирать «наилучший» маршрут;

Простота и низкие, непроизводительные затраты. Алгоритмы маршру­тизации должны выполнять свои функциональные возможности с минимальными затратами программного обеспечения;

Живучесть и стабильность – надежность функционирования в случае отказов аппаратуры;

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

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

На рис. 4.7 приведена классификация алгоритмов маршрутизации.

При случайной маршрутизации пакет, поступивший в маршрутизатор, выдается в любом одном направлении, кроме направления, откуда он по­ступил. Пакет совершает блуждание по сети, и с какой-то вероятностью достигнет назначения. При лавинной маршрутизации пакет передается во все направления, за исключением направления, откуда он поступил. Это приводит к перегрузке сети.

Рисунок 4.7

При маршрутизации по предыдущему опыту используется информация, которая накапливается в каждом маршрутизаторе (узле коммутации). Каж­дый пакет снабжен счетчиком, который определяет количество узлов, кото­рое он прошел. Накапливание этих данных позволяет создать таблицу, с помощью которой выбирается соответствующий маршрут. Этот алгоритм позволяет приспособиться к изменению топологии сети, но с большой за­держкой. При фиксированной маршрутизации алгоритм работает на основе анализа таблицы маршрутов, которая, как правило, создается сетевым ад­министратором, причем возможно составление таких таблиц с использова­нием альтернативных путей доставки информации к точке назначения. На­личие альтернативных путей позволяет повысить надежность сети при от­казе какого-либо из путей. Естественно, что статическая маршрутизация не позволяет учитывать изменяющуюся нагрузку сети, что приводит к повы­шению времени доставки пакета, если он попадает в перегруженный узел. Динамическая маршрутизация учитывает изменение топологии и состава сети. В этом случае каждый маршрутизатор получает информацию об из­менении топологии и изменении нагрузки в сети. При локальной маршру­тизации используется информация о состоянии не всей сети, а только опре­деленного конечного числа узлов, информация других узлов не учитывает­ся. Распределенная маршрутизация учитывает информацию, которая посту­пает из соседних узлов. Централизованная маршрутизация учитывает ин­формацию, поступающую из главного узла, причем каждый маршрутизатор передает информацию о своем состоянии в центральный узел, который ана­лизирует ее и передает каждому узлу в виде измененной таблицы маршрутизации. Гибридная маршрутизация предполагает использование как цен­трализованной, так и распределенной маршрутизации, чтобы не перегру­жать сеть служебной информацией.

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

Простая маршрутизация - способ маршрутизации, не изменяющийся при изменении топологии и состояния СПД. Обеспечивается разными алгоритмами, типичными из которых являются алгоритмы случайной и лавинной маршрутизации.

Рис. 58 - Классификация алгоритмов маршрутизации

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

Лавинная маршрутизация - передача пакета из узла во всех направлениях, кроме того, по которому поступил пакет. При этом, если узел связан с n другими узлами СПД, пакет передается в nнаправлениях, то есть размножается. Очевидно, что хотя бы одно направление обеспечит доставку пакета за минимальное время, то есть лавинная маршрутизация гарантирует малое время доставки, однако при этом резко ухудшается использование пропускной способности СПД из-за загрузки ее большим числом пакетов.

Маршрутизация по предыдущему опыту - передача пакета в направлении, выбираемом на основе потока, проходящего через узел. При этом пакеты, поступая в сеть, снабжаются адресами получателя и источника и счетчиком числа пройденных узлов (числа ретрансляционных участков). Пакет, пришедший в узел со значением счетчика 1, определяет соседний узел; пакет со значением счетчика 2 определяет узел, находящийся на расстоянии двух шагов, и т.д. Эти данные позволяют установить топологию сети и на ее основе построить таблицу для выбора маршрута. Постоянно анализируя число пройденных узлов, можно изменять таблицу маршрутов, если появился пакет с числом пройденных узлов, меньшим ранее зарегистрированного. Этот способ маршрутизации позволяет узлам приспосабливаться к изменению топологии сети, однако процесс адаптации протекает медленно и неэффективно. Метод изучения пути передачи пакетов используется для построения ряда модификаций алгоритмов простой маршрутизации.

Простая маршрутизация, не обеспечивая направленной передачи пакетов от источников к адресатам, имеет низкую эффективность! Основное ее достоинство - обеспечение устойчивой работы СПД при выходе из строя различных частей сети.

Фиксированная маршрутизация - способ выбора направления передачи по таблице маршрутизации, устанавливающей направление передачи для каждого узла назначения. Таблицы маршрутизации определяют кратчайшие пути от узлов к адресатам и вводятся в узлы связи от управляющего центра сети. Для слабо загруженных сетей этот способ маршрутизации дает хорошие результаты, но его эффективность падает по мере увеличения нагрузки на сеть. При отказе линий связи необходимо менять таблицу маршрутизации. При возникновении отказа по узлам сети рассылается управляющий пакет, содержащий сведения об отказе, реагируя на который, узлы меняют таблицы маршрутизации. Очевидно, что разработать способ фиксированной маршрутизации, обеспечивающей работоспособность сети при отказе многих линий, является чрезвычайно трудной задачей. К тому же фиксированная маршрутизация не позволяет адаптироваться к изменениям нагрузки, что приводит к значительным задержкам пакетов в СПД. Фиксированная маршрутизация может строиться на основе единого пути передачи пакетов между двумя абонентами. Такой способ называется однонаправленной маршрутизацией. Его недостаток - неустойчивость к отказам и перегрузкам. Для повышения устойчивости в таблицах маршрутизации указывается несколько возможных путей передачи пакета и вводится правило выбора целесообразного пути. Такой способ называется много направленной маршрутизацией.

Адаптивная маршрутизация - способ выбора направления передачи, учитывающий изменение состояния СПД. При адаптивной маршрутизации узлы СПД принимают решение о выборе маршрутов, реагируя на разного рода данные об изменении топологии и нагрузки. В идеальном случае каждый узел сети должен располагать полной информацией о текущем состоянии всех остальных узлов, топологии сети и длине очередей к каждому направлению в каждом узле. Однако, даже в этом идеальном случае задержки в СПД лишь немногим меньше, чем при фиксированной маршрутизации, таблицы которой определяют кратчайшие пути в сети и не изменяются при колебаниях нагрузки. Дело в том, что оптимальные маршруты, формируемые на основе самой «свежей» информации о распределении нагрузки в сети, становятся неоптимальными в последующие моменты времени, когда пакеты еще не достигли адресатов. Когда, например, сильно загруженные узлы получают информацию о том, что некоторая часть сети загружена слабо, они одновременно направляют пакеты в эту часть сети, создавая в сети, быть может, худшую ситуацию, чем предшествующая. Таким образом, алгоритмы адаптивной маршрутизации не обеспечивают оптимальности маршрутов. Однако выбор даже не оптимального, а близкого к нему маршрута приводит к значительному уменьшению времени доставки, особенно при пиковых нагрузках, а также к некоторому увеличению пропускной способности сети. Поэтому адаптивная маршрутизация получила широкое применение в вычислительных сетях, и в первую очередь в сетях с большим числом узлов связи (10 и более).

Алгоритмы адаптивной маршрутизации классифицируются по информации, используемой ими для принятия решений при назначении маршрутов. Локальная адаптивная маршрутизация основана на использовании информации, имеющейся в отдельном узле СПД. Эта информация включает в себя:

· таблицу маршрутизации;

· данные о текущем состоянии каналов (работают или нет);

· длину очередей пакетов, ожидающих передачи.

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

Распределенная адаптивная маршрутизация основана на использовании информации, получаемой от соседних узлов сети. Этот способ маршрутизации может реализоваться, например, следующим образом. Каждый узел сети формирует таблицы маршрутов ко всем узлам назначения, минимизирующие задержки в сети, причем для каждого маршрута указывается фактическое время передачи пакета в узел назначения. До начала работы сети это время оценивается исходя из топологии сети. В процессе работы сети узлы регулярно обмениваются с соседними узлами таблицами задержки. После обмена каждый узел пересчитывает задержки с учетом поступивших данных и длины очередей в самом узле. Пакет ставится в очередь к маршруту, который характеризуется минимальным временем доставки. Обмен таблицами задержки производится периодически или в том случае, если обнаруживаются существенные изменения задержки из-за изменения очередей на передачу или состояния линий связи вследствие отказа. Периодический обмен таблицами задержки значительно увеличивает загрузку сети, а асинхронный снижает. Однако в каждом случае загрузка остается весьма существенной, и к тому же сведения об изменении состояния узлов медленно распространяются по сети. Так, при обмене с интервалом 2/3 секунды время передачи данных составляет несколько секунд, и в этот период узлы направляют пакеты по старым путям, что может создать перегрузку в районе вышедших из строя компонентов сети.

Централизованная адаптивная маршрутизация основана на использовании информации, получаемой от центра маршрутизации. При этом каждый узел сети формирует сообщения о своем состоянии, длине очередей, работоспособности линий связи, и эти сообщения передаются в центр маршрутизации. Последний на основе полученных данных формирует таблицы маршрутизации, рассылаемые всем узлам сети. Неизбежные временные задержки при передаче данных в центр маршрутизации, формировании и рассылке таблиц приводят к потере эффективности централизованной маршрутизации, особенно в ситуациях, когда нагрузка сильно пульсирует. Поэтому централизованная маршрутизация по эффективности не превосходит локальную адаптивную, а кроме того, отличается специфическим недостатком - потерей управления сетью при отказе центра маршрутизации.

Гибридная адаптивная маршрутизация основана на использовании таблиц, периодически рассылаемых центром маршрутизации, в сочетании с анализом длины очередей в узлах. Если таблица маршрутизации, сформированная для узла связи центром, определяет единственное направление передачи пакета, то пакет передается именно в этом направлении. Если же таблица определяет несколько направлений, то узел выбирает направление в зависимости от текущих значений длин очередей по алгоритму локальной адаптивной маршрутизации. Гибридная маршрутизация компенсирует недостатки централизованной и локальной: маршруты, формируемые центром, являются устаревшими, но соответствуют глобальному состоянию сети; локальные алгоритмы являются «близорукими», но обеспечивают своевременность решений.

Протоколы маршрутизации

Этот протокол маршрутизации предназначен для сравнительно небольших и относительно однородных сетей (алгоритм Беллмана–Форда ). Протокол разработан в университете Калифорнии (Беркли). Маршрут здесь характеризуется вектором расстояния до места назначения. Предполагается, что каждый маршрутизатор является отправной точкой нескольких маршрутов до сетей, с которыми он связан. Описания этих маршрутов хранятся в специальной таблице, называемой маршрутной. Таблица маршрутизации RIP содержит по записи на каждую обслуживаемую машину (на каждый маршрут). Запись должна включать в себя:

· IP-адрес места назначения.

· Метрику маршрута (от 1 до 15; число шагов до места назначения).

· IP-адрес ближайшего маршрутизатора (gateway) по пути к месту назначения.

· Таймеры маршрута.

Первым двум полям записи мы обязаны появлению термина вектор расстояния (место назначения - направление; метрика - модуль вектора). Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы всем соседям - маршрутизаторам, с которыми связан непосредственно. Маршрутизатор - получатель просматривает таблицу. Если в таблице присутствуют новый путь или сообщение о более коротком маршруте, либо произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице.

В протоколе RIP сообщения инкапсулируются в udp-дейтограммы, при этом передача осуществляется через порт 520. В качестве метрики RIP использует число шагов до цели. Если между отправителем и приемником расположено три маршрутизатора (gateway), считается, что между ними 4 шага. Такой вид метрики не учитывает различий в пропускной способности или загруженности отдельных сегментов сети. Применение вектора расстояния не может гарантировать оптимальность выбора маршрута, ведь, например, два шага по сегментам сети Ethernet обеспечат большую пропускную способность, чем один шаг через последовательный канал на основе интерфейса RS-232.

Протокол RIP не способен обрабатывать три типа ошибок:

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

2. Для подавления нестабильностей RIP должен использовать малое значение максимально возможного числа шагов (<16).

3. Медленное распространение маршрутной информации по сети создает проблемы при динамичном изменении маршрутной ситуации (система не поспевает за изменениями). Малое предельное значение метрики улучшает сходимость, но не устраняет проблему.

Несоответствие маршрутной таблицы реальной ситуации типично не только для RIP, но характерно для всех протоколов, базирующихся на векторе расстояния, где информационные сообщения актуализации несут в себе только пары кодов: адрес места назначения и расстояние до него. Пояснение проблемы дано на рис. 59.

Рис. 59 - Возникновение циклических маршрутов

при использовании вектора расстояния

На верхней части рисунка показана ситуация, когда маршрутизаторы (GW) указывают маршрут до сети в соответствии со стрелками. На нижней части связь на участке GW1 <Сеть А> оборвана, а GW2 по-прежнему продолжает оповещать о ее доступности с числом шагов, равным 2. При этом GW1, восприняв эту информацию (если GW2 успел передать свою маршрутную информацию раньше GW1), может перенаправить пакеты, адресованные сети А, на GW2, а в своей маршрутной таблице будет характеризовать путь до сети А метрикой 3. При этом формируется замкнутая петля маршрутов. Последующая широковещательная передача маршрутных данных GW1 и GW2 не решит эту проблему быстро. Так, после очередного обмена путь от gw2 до сети А будет характеризоваться метрикой 5. Этот процесс будет продолжаться до тех пор, пока метрика не станет равной 16, а это займет слишком много циклов обмена маршрутной информацией.

Проблема может быть решена следующим образом. Маршрутизатор запоминает, через какой интерфейс получена маршрутная информация, и через этот интерфейс эту информацию уже не передает. В рассмотренном выше примере GW2 не станет посылать информацию о пути к сети А маршрутизатору GW1, от которого он получил эти данные. В этом случае в маршрутной таблице GW1 путь до А исчезнет сразу. Остальные маршрутизаторы узнают о недостижимости сети А через несколько циклов. Существуют и другие пути преодоления медленных переходных процессов. Если производится оповещение о коротком пути, все узлы-получатели воспринимают эти данные немедленно. Если же маршрутизатор закрывает какой-то путь, его отмена фиксируется остальными лишь по тайм-ауту. Универсальным методом исключения ошибок при маршрутизации является использование достаточно большой выдержки, перед тем как использовать информацию об изменении маршрутов. В этом случае к моменту изменения маршрута эта информация станет доступной всем участникам процесса маршрутизации. Но все перечисленные методы и некоторые другие известные алгоритмы, решая одну проблему, часто вносят другие. Многие из этих методов могут при определенных условиях вызвать лавину широковещательных сообщений, что также дезорганизует сеть. Именно малая скорость установления маршрутов в RIP (и других протоколах, ориентированных на вектор расстояния) и является причиной их постепенного вытеснения другими протоколами.

Рис. 60 - Формат сообщения RIP

Маршрут по умолчанию имеет адрес 0.0.0.0 (это верно и для других протоколов маршрутизации). Каждому маршруту ставится в соответствие таймер тайм-аута и «сборщика мусора». Тайм-аут-таймер сбрасывается каждый раз, когда маршрут инициализируется или корректируется. Если со времени последней коррекции прошло 3 минуты или получено сообщение о том, что вектор расстояния равен 16, маршрут считается закрытым. Но запись о нем не стирается, пока не истечет время «уборки мусора» (2мин). При появлении эквивалентного маршрута переключения на него не происходит, таким образом, блокируется возможность осцилляции между двумя или более равноценными маршрутами. Формат сообщения протокола RIP имеет вид, показанный на рис. 60. Поле версия для RIP равно 1 (для RIP-2 двум). Поле набор протоколов сети i определяет набор протоколов, которые используются в соответствующей сети (для Интернет это поле имеет значение 2). Поле расстояние до сети i содержит целое число шагов (от 1 до 15) до данной сети. В одном сообщении может присутствовать информация о 25 маршрутах. При реализации RIP можно выделить следующие режимы:

Рис. 61 - Формат сообщения RIP-2

RIP достаточно простой протокол, но, к сожалению, не лишенный недостатков:

· RIP не работает с адресами субсетей. Если нормальный 16-бит идентификатор ЭВМ класса B не равен 0, RIP не может определить, является ли ненулевая часть cубсетевым ID, или полным IP-адресом.

· RIP требует много времени для восстановления связи после сбоя в маршрутизаторе (минуты). В процессе установления режима возможны циклы.

· Число шагов важный, но не единственный параметр маршрута, да и 15 шагов не предел для современных сетей.

Протокол RIP-2 (RFC-1388, 1993 год) является новой версией RIP, которая в дополнение к широковещательному режиму поддерживает мультикастинг; позволяет работать с масками субсетей. На рис. 61 представлен формат сообщения для протокола RIP-2. Поле метка маршрута используется для поддержки внешних протоколов маршрутизации, сюда записываются коды автономных систем.

Протокол OSPF (Open Shortest Pass First, RFC-1245-48, RFC-1583-1587, алгоритмы предложены Дикстрой) является альтернативой RIP в качестве внутреннего протокола маршрутизации. OSPF представляет собой протокол состояния маршрута (в качестве метрики используется коэффициент качества обслуживания). Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов (переключателей) автономной системы. Протокол OSPF реализован в демоне маршрутизации gated, который поддерживает также RIP и внешний протокол маршрутизации BGP.

Автономная система (AS) может быть разделена на несколько областей, куда могут входить как отдельные ЭВМ, так и целые сети. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS. Сеть обычно имеет выделенный (designated) маршрутизатор, который является источником маршрутной информации для остальных маршрутизаторов AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. Если к месту назначения ведут два или более эквивалентных маршрута, информационный поток будет поделен между ними поровну. Переходные процессы в OSPF завершаются быстрее, чем в RIP. В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Ниже описан алгоритм Дикстры по выбору оптимального пути. На рис. 62 приведена схема узлов (A-J) со значениями метрики для каждого из отрезков пути. Анализ графа начинается с узла A (Старт). Пути с наименьшим суммарным значением метрики считаются наилучшими. Именно они оказываются выбранными в результате рассмотрения графа («кратчайшие пути»).

Рис. 62 - Иллюстрация работы алгоритма Дикстры

Качество сервиса (QoS) может характеризоваться следующими параметрами:

· пропускной способностью канала;

· задержкой (время распространения пакета);

· числом дейтограмм, стоящих в очереди для передачи;

· загрузкой канала;

· требованиями безопасности;

· типом трафика;

· числом шагов до цели;

· возможностями промежуточных связей (например, многовариантность достижения адресата).

Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т.е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (type of service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP-адресом и типом сервиса. Так как протокол не требует инкапсуляции пакетов, сильно облегчается управление сетями с большим количеством бриджей и сложной топологией (исключается циркуляция пакетов, сокращается транзитный трафик). Автономная система может быть поделена на отдельные области, каждая из которых становится объектом маршрутизации, а внутренняя структура снаружи не видна (узлы на рис. 62 могут представлять собой как отдельные ЭВМ или маршрутизаторы, так и целые сети). Этот прием позволяет значительно сократить необходимый объем маршрутной базы данных. В OSPF используется термин опорной сети (backbone) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.

На рис. 63 (см. также рис. 62) приведен пример выделения областей маршрутизации при ospf-маршрутизации в пределах автономной системы. На рис. 63 маршрутизаторы М4 и М2 выполняют функции опорной сети для других областей. В выделенных областях может быть любое число маршрутизаторов. Более толстыми линиями выделены связи с другими автономными системами.

Рис. 63 - Пример выделения областей при ospf-маршрутизации

в автономной системе (М - маршрутизаторы; c - сети)

При передаче OSPF-пакетов фрагментация нежелательна, но не запрещается. Для передачи статусной информации OSPF использует широковещательные сообщения Hello. Для повышения безопасности предусмотрена авторизация процедур.

Поле версия определяет версию протокола. Поле тип идентифицирует функцию сообщения. Поле длина пакета определяет длину блока в октетах, включая заголовок. Идентификатор области - 32-битный код, идентифицирующий область, которой данный пакет принадлежит. Все ospf-пакеты ассоциируются с той или иной областью. Большинство из них не преодолевает более одного шага. Пакеты, путешествующие по виртуальным каналам, помечаются идентификатором опорной области (backbone) 0.0.0.0. Поле контрольная сумма содержит контрольную сумму IP-пакета, включая поле типа идентификации . Контрольное суммирование производится по модулю 1. Поле тип идентификации может принимать значения 0 при отсутствии контроля доступа, и 1 при наличии контроля. Важную функцию в OSPF-сообщениях выполняет одно-октетное поле опции , оно присутствует в сообщениях типа Hello, объявление состояния канала и описание базы данных.

Рис. 64 - Формат заголовка сообщений для протокола

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

Протокол ospf использует сообщение типа Hello для взаимообмена данными между соседними маршрутизаторами.

Маршрутизаторы обмениваются сообщениями из баз данных OSPF, чтобы инициализировать, а в дальнейшем актуализовать свои базы данных, характеризующие топологию сети. Обмен происходит в режиме клиент-сервер. Клиент подтверждает получение каждого сообщения.

Сообщения об изменениях маршрутов могут быть вызваны следующими причинами:

1. Возраст маршрута достиг предельного значения (lsrefresh-time).

2. Изменилось состояние интерфейса.

3. Произошли изменения в маршрутизаторе сети.

4. Произошло изменение состояния одного из соседних маршрутизаторов.

5. Изменилось состояние одного из внутренних маршрутов (появление нового, исчезновение старого и т.д.)

6. Изменение состояния межзонного маршрута.

7. Появление нового маршрутизатора, подключенного к сети.

8. Вариация виртуального маршрута одним из маршрутизаторов.

9. Возникли изменения одного из внешних маршрутов.

10. Маршрутизатор перестал быть пограничным для данной as (например, перезагрузился).

Маршрутная таблица OSPF содержит в себе:

· IP-адрес места назначения и маску;

· тип места назначения (сеть, граничный маршрутизатор и т.д.);

· тип функции (возможен набор маршрутизаторов для каждой из функций TOS (Type of service));

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

· тип пути (характеризует путь как внутренний, межобластной или внешний, ведущий к AS);

· цена маршрута до цели;

· очередной маршрутизатор, куда следует послать дейтограмму;

· объявляющий маршрутизатор (используется для межобластных обменов и для связей автономных систем друг с другом).

Последовательность описания метрик задается величиной кода TOS. Таблица кодов TOS, принятых в OSPF протоколе приведена ниже на рис. 65:

Рис. 65 - Коды типа сервиса (TOS)

Преимущества OSPF:

1. Для каждого адреса может быть несколько маршрутных таблиц, по одной на каждый вид IP-операции (TOS).

2. Каждому интерфейсу присваивается безразмерная цена, учитывающая пропускную способность, время транспортировки сообщения. Для каждой IP-операции может быть присвоена своя цена (коэффициент качества).

3. При существовании эквивалентных маршрутов OSFP распределяет поток равномерно по этим маршрутам.

4. Поддерживается адресация субсетей (разные маски для разных маршрутов).

5. При связи точка-точка не требуется IP-адрес для каждого из концов. (Экономия адресов!).

6. Применение мультикастинга вместо широковещательных сообщений снижает загрузку не вовлеченных сегментов.

Недостатки:

1. Трудно получить информацию о предпочтительности каналов для узлов, поддерживающих другие протоколы, или со статической маршрутизацией.

2. OSPF является лишь внутренним протоколом.

Протокол IGRP разработан фирмой CISCO для своих многопротокольных маршрутизаторов в середине 80-х годов. IGRP представляет собой протокол, который позволяет большому числу маршрутизаторов координировать свою работу. Основные достоинства протокола (описание протокола взято из депозитария FTP.CISCO.COM/pub/igrp.doc):

· стабильность маршрутов даже в очень больших и сложных сетях;

· быстрый отклик на изменения топологии сети;

· минимальная избыточность. IGRP не требует дополнительной пропускной способности каналов для своей работы;

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

· учет частоты ошибок и уровня загрузки каналов;

· возможность реализовать различные виды сервиса для одного и того же набора информации.

Сегодняшняя реализация протокола ориентирована на TCP/IP. Однако базовая конструкция системы позволяет использовать IGRP и с другими протоколами. IGRP имеет некоторое сходство со старыми протоколами, например, с RIP и OSPF. Здесь маршрутизатор обменивается маршрутной информацией только с непосредственными соседями. Поэтому задача маршрутизации решается всей совокупностью маршрутизаторов, а не каждым отдельно.

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

IGRP используется в маршрутизаторах, которые имеют связи с несколькими сетями и выполняют функции переключателей пакетов. Когда какой-то объект в одной сети хочет послать пакет в другую сеть, он должен послать его соответствующему маршрутизатору. Если адресат находится в одной из сетей, непосредственно связанной с маршрутизатором, он отправляет этот пакет по месту назначения. Если же адресат находится в более отдаленной сети, маршрутизатор перешлет пакет другому маршрутизатору, расположенному ближе к адресату. Здесь также, как и в других протоколах, для хранения маршрутных данных используются специализированные базы данных.

Протокол IGRP формирует эту базу данных на основе информации, которую он получит от соседних маршрутизаторов. В простейшем случае находится один путь для каждой из сетей. Сегменты пути характеризуются используемым сетевым интерфейсом, метрикой и маршрутизатором, куда следует сначала послать пакет. Метрика - то число, которое говорит о том, насколько хорош данный маршрут. Это число позволяет сравнить его с другими маршрутами, ведущими к тому же месту назначения и обеспечивающими тот же уровень QOS. Предусматривается возможность (как и в OSPF) разделять информационный поток между несколькими доступными эквивалентными маршрутами. Пользователь может сам разделить поток данных, если два или более пути оказались почти равными по метрике, при этом большая часть трафика будет послана по пути с лучшей метрикой. Метрика, используемая в IGRP, учитывает:

· время задержки;

· пропускную способность самого слабого сегмента пути (в битах в сек);

· загруженность канала (относительную);

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

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

Среди параметров, которые контролируются, но не учитываются метрикой, находятся число шагов до цели и MTU (maximum transfer unit - размер пакета, пересылаемого без фрагментации). Расчет метрики производится для каждого сегмента пути.

Время от времени каждый маршрутизатор широковещательно рассылает свою маршрутную информацию всем соседним маршрутизаторам. Получатель сравнивает эти данные с уже имеющимися и вносит, если требуется, необходимые коррекции. На основании вновь полученной информации могут быть приняты решения об изменении маршрутов. Эта процедура типична для многих маршрутизаторов и этот алгоритм носит имя Белмана–Форда. (см. также описание протокола RIP, RFC-1058). Наилучший путь выбирается с использованием комбинированной метрики, вычисленной по формуле:

[(K1 / B e) + (K2 * D c)] r, (1)

где K1, K2 - константы;

B e = пропускная способность канала (в отсутствие загрузки) * *(1 – загрузка канала);

D c - топологическая задержка;

r - относительная надежность (% пакетов, успешно передаваемых по данному сегменту пути). Здесь загрузка измеряется как доля от 1.

Путь, имеющий наименьшую комбинированную метрику, считается лучшим. В такой схеме появляется возможность, используя весовые коэффициенты, адаптировать выбор маршрутов к задачам конечного пользователя.

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

Когда маршрутизатор включается, его маршрутные таблицы инициализируются оператором вручную или с использованием специальных файлов. На рис. 58 маршрутизатор S связан через соответствующие интерфейсы с сетями 2 и 3.

Рис. 66 - Схема сети

Таким образом, в исходный момент маршрутизатор S знает только о доступности сетей 2 и 3. За счет обмена информацией, полученной при инициализации и присланной позднее соседями, маршрутизаторы познают окружающий мир. Так, S спустя некоторое время получит информацию от маршрутизатора R о доступности сети 1 и от T - о сети 4. В свою очередь S проинформирует T о доступе к сети 1. Очень быстро информация о доступности дойдет до всех маршрутизаторов и разрозненные сети станут единым целым. Для пояснения выбора маршрута в условиях многовариантности рассмотрим схему на рис. 67

Рис. 67 - Пример сети с альтернативными маршрутами

Пусть каждый из маршрутизаторов уже вычислил комбинированную метрику для системы, изображенной на рис. 67. Для места назначения в сети 6 маршрутизатор A вычислит метрику для двух путей, через маршрутизаторы B и C. В действительности существует три маршрута из a в сеть 6:

Непосредственно в B;

В C и затем в B;

В C и затем в D.

Маршрутизатору A не нужно выбирать между двумя маршрутами через C. Маршрутная таблица в A содержит только одну запись, соответствующую пути к C. Если маршрутизатор A посылает пакет маршрутизатору C, то именно C решает, использовать далее путь через маршрутизаторы B или D.

Для каждого типа канала используется свое стандартное значение комбинированной задержки. Ниже приведен пример того, как может выглядеть маршрутная таблица в маршрутизаторе A для сети, изображенной таблице 6.

Таблица 6 - Пример маршрутной таблицы

Номер сети	Интерфейс	Следующий маршрутизатор	Метрика маршрута
Сеть 1	NW 1	Нет	Непосредственная связь
Сеть 2	NW 2	Нет	Непосредственная связь
Сеть 3	NW 3	Нет	Непосредственная связь
Сеть 4	NW 2	C
	NW 3	B
Сеть 5	NW 2	C
	NW 3	B
Сеть 6	NW 2	C
	NW 3	B

Для того чтобы обеспечить работу с большими и сложными сетями, в IGRP введены три усовершенствования алгоритма Белмана-Форда:

1. Для описания путей вместо простой, введена векторная метрика. Расчет комбинированной метрики проводится с использованием формулы (1). Применение векторной метрики позволяет адаптировать систему с учетом различных видов сервиса.

2. Вместо выбора одного пути с минимальной метрикой, информационный поток может быть поделен между несколькими путями с метрикой, лежащей в заданном интервале. Распределение потоков определяется соотношением величин комбинированной метрики. Таким образом, используются маршруты с комбинированной метрикой меньше некоторого предельного значения M, а также с метрикой меньше V*M, где V - значение вариации M (обычно задается оператором сети).

3. Существуют определенные проблемы с вариацией. Трудно определить стратегию использования вариации V>1 и избежать зацикливания пакетов. В современных реализациях V=1.

4. Разработан ряд мер, препятствующих осцилляциям маршрутов при изменении топологии сети.

Значение вариации, отличное от единицы, позволяет использовать одновременно два или более путей с разной пропускной способностью. При дальнейшем увеличении вариации можно разрешить не только более «медленные» сегменты пути, но и ведущие в обратном направлении, что приведет с неизбежностью к «бесконечному» циклическому движению пакетов.

Протокол маршрутизации IGRP предназначен для работы с несколькими типами сервиса (TOS) и несколькими протоколами. Под типами сервиса в TCP/IP подразумевается оптимизация маршрутизации по пропускной способности, задержке, надежности и т.д. Для решения этой задачи можно использовать весовые коэффициенты K1 и K2 (формула (1) данного раздела). При этом для каждого TOS подготавливается своя маршрутная таблица. Среди мер, обеспечивающих cтабильность топологии связей, следует отметить следующее правило, которое поясняется на приведенном ниже примере (рис. 68).

Рис. 68 - Пример сети для пояснения правил формирования

маршрутной информации

Маршрутизатор A сообщает B о маршруте к сети 1. Когда же B посылает сообщения об изменении маршрутов в A, он ни при каких обстоятельствах не должен упоминать сеть 1. Т.е. сообщения об изменении маршрута, направленные какому-то маршрутизатору, не должны содержать данных об объектах, непосредственно с ним связанных. Сообщения об изменении маршрутов должны содержать:

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

Пропускную способность каждой из сетей;

Топологическую задержку каждой из сетей;

Надежность передачи пакетов для каждой сети;

Загруженность канала для каждой сети;

MTU для каждой сети.

Следует еще раз обратить ваше внимание, что в IGRP не используется измерение задержек, измеряется только надежность и коэффициент загрузки канала. Надежность определяется на основе сообщений интерфейсов о числе ошибок.

Существует 4 временные константы, управляющие процессом распространения маршрутной информации (эти константы определяются оператором сети):

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

Время существования - если за это время не поступило никаких сообщений о данном маршруте, он считается нерабочим. Это время в несколько раз больше периода сообщений об изменениях (по умолчанию в 3 раза).

Время удержания - когда какой-то адресат становится недостижим, он переходит в режим выдержки. В этом режиме никакие новые маршруты, ведущие к нему, не воспринимаются. Длительность этого режима и называется временем удержания. Обычно это время в три раза дольше периода сообщений об изменениях маршрутов;

Время удаления - если в течение данного времени не поступило сообщений о доступе к данному адресату, производится удаление записи о нем из маршрутной базы данных (по умолчанию это время в 7 раз больше периода сообщений об изменениях маршрутов).

IGRP-сообщение вкладывается в IP-пакет, это сообщение имеет следующие поля:

version - номер версии протокола 4 байта, в настоящее время равен 1. Пакеты с другим номером версии игнорируются;

opcode код операции - определяет тип сообщения и может принимать значения:

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

Asystem - номер автономной системы. Согласно нормам Сisco маршрутизатор может входить в более чем одну автономную систему. В каждой AS работает свой протокол и они могут иметь совершенно независимые таблицы маршрутизации. Хотя в IGRP допускается «утечка» маршрутной информации из одной автономной системы в другую, но это определяется не протоколом, а администратором;

Ninterior, Nsystem, Nexterior - числа субсетей в локальной сети, в автономной системе и вне автономной системы, определяют числа записей в каждой из трех секций сообщения об изменениях;

checksum - контрольная сумма IGRP-заголовка и данных, для вычисления которой используется тот же алгоритм, что и в UDP, TCP и ICMP.

IGRP запрос требует от адресата прислать свою маршрутную таблицу. Сообщение содержит только заголовок. Используются поля version, opcode и asystem , остальные поля обнуляются. IP-пакет, содержащий сообщение об изменении маршрутов, имеет 1500 байт (включая IP-заголовок). Для описанной выше схемы это позволяет включить в пакет до 104 записей. Если требуется больше записей, посылается несколько пакетов. Фрагментация пакетов не применяется.

Ниже приведено описание структуры для маршрута:

Субполе описание маршрута Number определяет IP-адрес места назначения, для экономии места здесь используется только 3 его байта. Если поле задержки содержит только единицы, место назначения недостижимо.

Пропускная способность измеряется в величинах, обратных бит/сек, умноженных на 10 10 . (Т.е., если пропускная способность равна N Кбит/с, то ее измерением в IGRP будет 10000000/N.). Надежность измеряется в долях от 255 (т.е. 255 соответствует 100 %). Загрузка измеряется также в долях от 255, а задержка в десятках миллисекунд.

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

Комбинированная метрика в действительности вычисляется по следующей формуле (для версии Cisco 8.0(3)):

Метрика = * * .

Если K5 == 0, член надежности отбрасывается. По умолчанию в IGRP K1 == K3 == 1, K2 == K4 == K5 == 0, а загрузка лежит в интервале от 1 до 255.

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

Вид среды	Задержка	Пропускная способность
Спутник	200,000 (2 сек.)	20 (500 Мбит/c)
Ethernet	100 (1 мсек.)	1,000
1,544 Мбит/c	2000 (20 мсек.)	6,476
64 Кбит/c		156,250
56 Кбит/c		178,571
10 Кбит/c		1,000,000
1 Кбит/c		10,000,000

В начале 90-х годов разработана новая версия протокола IGRP - EIGRP с улучшенным алгоритмом оптимизации маршрутов, сокращенным временем установления и масками субсетей переменной длины. EIGRP поддерживает многие протоколы сетевого уровня. Рассылка маршрутной информации здесь производится лишь при измении маршрутной ситуации. Протокол периодически рассылает соседним маршрутизаторам короткие сообщения Hello. Получение отклика означает, что сосед функционален и можно осуществлять обмен маршрутной информацией. Протокол EIGRP использует таблицы соседей (адрес и интерфейс), топологические таблицы (адрес места назначения и список соседей, объявляющих о доступности этого адреса), состояния и метки маршрутов. Для каждого протокольного модуля создается своя таблица соседей. Протоколом используются сообщения типа hello (мультикастная адресация), подтверждение (acknowledgent), актуализация (update), запрос (query, всегда мультикастный) и отклик (reply, посылается отправителю запроса). Маршруты здесь делятся на внутренние и внешние - полученные от других протоколов или записанные в статических таблицах. Маршруты помечаются идентификаторами их начала. Внешние маршруты помечаются следующей информацией:

· Идентификатор маршрутизатора EIGRP, который осуществляет рассылку информации о маршруте.

· Номер AS, где расположен адресат маршрута.

· Метка администратора.

· Идентификатор протокола.

· Метрика внешнего маршрута.

· Битовые флаги маршрута по умолчанию.

Протокол EIGRP полностью совместим с IGRP, он обеспечивает работу в сетях IP, Apple Talk и Novell.

Протокол BGP (RFC-1267, BGP-3; RFC-1268; RFC-1467, BGP-4; -1265-66, 1655) разработан компаниями IBM и CISCO. Главная цель BGP - сократить транзитный трафик. Местный трафик либо начинается, либо завершается в автономной системе (AS); в противном случае - это транзитный трафик. Системы без транзитного трафика не нуждаются в BGP (им достаточно EGP для общения с транзитными узлами). Но не всякая ЭВМ, использующая протокол BGP, является маршрутизатором, даже если она обменивается маршрутной информацией с пограничным маршрутизатором соседней автономной системы. AS передает информацию только о маршрутах, которыми она сама пользуется. BGP - маршрутизаторы обмениваются сообщениями об изменении маршрутов (UPDATE-сообщения, рис. 69). Максимальная длина таких сообщений составляет 4096 октетов, а минимальная 19 октетов. Каждое сообщение имеет заголовок фиксированного размера. Объем информационных полей зависит от типа сообщения.

Рис. 69 - Формат BGP-сообщений об изменениях маршрутов

Поле маркер содержит 16 октетов. Маркер может использоваться для обнаружения потери синхронизации в работе BGP-партнеров. Поле длина имеет два октета и определяет общую длину сообщения в октетах, включая заголовок. Значение этого поля должно лежать в пределах 19-4096. Поле тип представляет собой код разновидности сообщения и может принимать следующие значения:

	OPEN	(открыть)
	UPDATE	(изменить)
	NOTIFICATION	(внимание)
	KEEPALIVE	(еще жив)

После того как связь на транспортном протокольном уровне установлена, первое сообщение, которое должно быть послано, - это OPEN. При его успешном прохождении партнер должен откликнуться сообщением KEEPALIVE («Еще жив»). После этого возможны любые сообщения. Кроме заголовка сообщение open содержит поля (рис. 70):

Рис. 70 - Формат сообщения open

Поле версия описывает код версии используемого протокола, на сегодня для BGP он равен 4. Двух-октетное поле моя автономная система определяет код AS отправителя. Поле время сохранения характеризует время в секундах, которое отправитель предлагает занести в таймер сохранения. После получения сообщения OPEN BGP - маршрутизатор должен выбрать значение времени сохранения. Обычно выбирается меньшее из полученного в сообщении open и значения, определенного при конфигурации системы (0–3сек). Время сохранения определяет максимальное время в секундах между сообщениями KEEPALIVE и UPDATE или между двумя UPDATE-сообщениями. Каждому узлу в рамках BGP приписывается 4-октетный идентификатор (BGP-identifier, задается при инсталляции и идентичен для всех интерфейсов локальной сети). Если два узла установили два канала связи друг с другом, то согласно правилам, должен быть сохранен канал, начинающийся в узле, BGP-идентификатор которого больше. Предусмотрен механизм разрешения проблемы при равных идентификаторах.

Вся маршрутная информация хранится в специальной базе данных RIB (routing information base). Маршрутная база данных BGP состоит из трех частей:

Так как разные BGP-партнеры могут иметь разную политику маршрутизации, возможны осцилляции маршрутов. Для исключения этого необходимо выполнять следующее правило: если используемый маршрут объявлен не рабочим (в процессе корректировки получено сообщение с соответствующим атрибутом), до переключения на новый маршрут необходимо ретранслировать сообщение о недоступности старого всем соседним узлам.

Протокол BGP позволяет реализовать маршрутную политику.

Политика отражается в конфигурационных файлах BGP. Маршрутная политика - это не часть протокола, она определяет решения, когда место назначения достижимо несколькими путями, политика отражает соображения безопасности, экономические интересы и пр. Количество сетей в пределах одной AS не лимитировано. BGP использует три таймера:

Connectretry (сброс при инициализации и коррекции; 120 сек).

Holdtime (пуск при получении команд Update или Keepalive; 90 сек).

Кeepalive (пуск при посылке сообщения Keepalive; 30 сек).

BGP отличается от RIP и OSPF тем, что использует TCP в качестве транспортного протокола. Две системы, использующие BGP, связываются друг с другом и пересылают посредством TCP полные таблицы маршрутизации. В дальнейшем обмен идет только в случае каких-то изменений. ЭВМ, использующая BGP, не обязательно является маршрутизатором. Сообщения обрабатываются только после того, как они полностью получены.

BGP является протоколом, ориентирующимся на вектор расстояния. Вектор описывается списком AS по 16 бит на AS. BGP регулярно (каждые 30сек) посылает соседям TCP-сообще-ния, подтверждающие, что узел жив (это не то же самое что «Keepalive» - функция в TCP). Если два BGP-маршрутизатора попытаются установить связь друг с другом одновременно, такие две связи могут быть установлены. Такая ситуация называется столкновением, одна из связей должна быть ликвидирована. При установлении связи маршрутизаторов сначала делается попытка реализовать высший из протоколов (например, BGP-4), если один из них не поддерживает эту версию, номер версии понижается.

Протокол BGP-4 является усовершенствованной версией (по сравнению с BGP-3). Эта версия позволяет пересылать информацию о маршруте в рамках одного IP-пакета. Концепция классов сетей и субсети находятся вне рамок этой версии. Для того чтобы приспособиться к этому, изменена семантика и кодирование атрибута AS_PASS. Введен новый атрибут LOCAL_PREF (степень предпочтительности маршрута для собственной AS), который упрощает процедуру выбора маршрута. Атрибут INTER_AS_METRICS переименован в MULTI_EXIT_DISC (4 октета; служит для выбора пути к одному из соседей). Введены новые атрибуты ATOMIC_AGGREGATE и AGGREGATOR , которые позволяют группировать маршруты. Структура данных отражается и на схеме принятия решения, которая имеет три фазы:

1. Вычисление степени предпочтения для каждого маршрута, полученного от соседней AS, и передача информации другим узлам местной AS.

2. Выбор лучшего маршрута из наличного числа для каждой точки назначения и укладка результата в LOC-RIB.

Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:

1. Статическими или динамическими

2. Одномаршрутными или многомаршрутными

3. Одноуровневыми или иерархическими

4. С интеллектом в главной вычислительной машине или в маршрутизаторе

5. Внутридоменными и междоменными

6. Алгоритмами состояния канала или вектора расстояний

Статические или динамические алгоритмы

Статические алгоритмы маршрутизации вообще вряд ли являются алгоритмами. Распределение статических таблиц маршрутизации устанавливается администратором сети до начала маршрутизации. Оно не меняется, если только администратор сети не изменит его. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в окружениях, где трафик сети относительно предсказуем, а схема сети относительно проста.

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

Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в масштабе реального времени. Они выполняют это путем анализа поступающих сообщений об обновлении маршрутизации. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации. Такие сообщения пронизывают сеть, стимулируя маршрутизаторы заново прогонять свои алгоритмы и соответствующим образом изменять таблицы маршрутизации. Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это уместно. Например, можно разработать "маршрутизатор последнего обращения" (т.е. маршрутизатор, в который отсылаются все неотправленные по определенному маршруту пакеты). Такой маршрутизатор выполняет роль хранилища неотправленных пакетов, гарантируя, что все сообщения будут хотя бы определенным образом обработаны.

Одномаршрутные или многомаршрутные алгоритмы

Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям; одномаршрутные алгоритмы не могут делать этого. Преимущества многомаршрутных алгоритмов очевидны - они могут обеспечить заначительно большую пропускную способность и надежность.

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

Некоторые алгоритмы маршрутизации оперируют в плоском пространстве, в то время как другие используют иерархиии маршрутизации. В одноуровневой системе маршрутизации все маршрутизаторы равны по отношению друг к другу. В иерархической системе маршрутизации некоторые маршрутизаторы формируют то, что составляет основу (backbone - базу) маршрутизации. Пакеты из небазовых маршрутизаторов перемещаются к базовым маршрутизаторам и пропускаются через них до тех пор, пока не достигнут общей области пункта назначения. Начиная с этого момента, они перемещаются от последнего базового маршрутизатора через один или несколько небазовых маршрутизаторов до конечного пункта назначения.

Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами, или автономными системами (AS), или областями. В иерархических системах одни маршрутизаторы какого-либо домена могут сообщаться с маршрутизаторами других доменов, в то время как другие маршрутизаторы этого домена могут поддерживать связь с маршрутизаторы только в пределах своего домена. В очень крупных сетях могут существовать дополнительные иерархические уровни. Маршрутизаторы наивысшего иерархического уровня образуют базу маршрутизации.

Основным преимуществом иерархической маршрутизации является то, что она имитирует организацию большинства компаний и следовательно, очень хорошо поддерживает их схемы трафика. Большая часть сетевой связи имеет место в пределах групп небольших компаний (доменов). Внутридоменным маршрутизаторам необходимо знать только о других маршрутизаторах в пределах своего домена, поэтому их алгоритмы маршрутизации могут быть упрощенными. Соответственно может быть уменьшен и трафик обновления маршрутизации, зависящий от используемого алгоритма маршрутизации.

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

Некоторые алгоритмы маршрутизации предполагают, что конечный узел источника определяет весь маршрут. Обычно это называют маршрутизацией от источника. В системах маршрутизации от источника маршрутизаторы действуют просто как устойства хранения и пересылки пакета, без всякий раздумий отсылая его к следующей остановке.

Другие алгоритмы предполагают, что главные вычислительные машины ничего не знают о маршрутах. При использовании этих алгоритмов маршрутизаторы определяют маршрут через объединенную сеть, базируясь на своих собственных расчетах. В первой системе, рассмотренной выше, интеллект маршрутизации находится в главной вычислительной машине. В системе, рассмотренной во втором случае, интеллектом маршрутизации наделены маршрутизаторы.

Компромисс между маршрутизацией с интеллектом в главной вычислительной машине и маршрутизацией с интеллектом в маршрутизаторе достигается путем сопоставления оптимальности маршрута с непроизводительными затратами трафика. Системы с интеллектом в главной вычислительной машине чаще выбирают наилучшие маршруты, т.к. они, как правило, находят все возможные маршруты к пункту назначения, прежде чем пакет будет действительно отослан. Затем они выбирают наилучший мааршрут, основываясь на определении оптимальности данной конкретной системы. Однако акт определения всех маршрутов часто требует значительного трафика поиска и большого объема времени.

Внутридоменные или междоменные алгоритмы

Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие - как в пределах доменов, так и между ними. Природа этих двух типов алгоритмов различная. Поэтому понятно, что оптимальный алгоритм внутридоменной маршрутизации не обязательно будет оптимальным алгоритмом междоменной маршрутизации.

Алгоритмы состояния канала или вектора расстояния

Алгоритмы состояния канала (известные также как алгоритмы "первоочередности наикратчайшего маршрута") направляют потоки маршрутной информации во все узлы объединенной сети. Однако каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния (известные также как алгоритмы Бэлмана-Форда) требуют от каждогo маршрутизатора посылки всей или части своей маршрутной таблицы, но только своим соседям. Алгоритмы состояния каналов фактически направляют небольшие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние маршрутизаторы.

Отличаясь более быстрой сходимостью, алгоритмы состояния каналов несколько меньше склонны к образованию петель маршрутизации, чем алгоритмы вектора расстояния. С другой стороны, алгоритмы состояния канала характеризуются более сложными расчетами в сравнении с алгоритмами вектора расстояний, требуя большей процессорной мощности и памяти, чем алгоритмы вектора расстояний. Вследствие этого, реализация и поддержка алгоритмов состояния канала может быть более дорогостоящей. Несмотря на их различия, оба типа алгоритмов хорошо функционируют при самых различных обстоятельствах.