Лекции / Алгоритмы_маршрутизации_лекция_05-12-2018_кратко

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

Алгоритмы маршрутизации должны удовлетворять следующим требованиям:

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

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

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

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

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

Все алгоритмы маршрутизации классифицируются по следующим признакам:

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

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

• Алгоритмы фиксированной (статической) маршрутизации.

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

• Алгоритмы простой маршрутизации.

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

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

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

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

• Алгоритмы адаптивной (динамической) маршрутизации.

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

• дистанционно-векторные (Distance Vector Algorithm, DVA);

• алгоритмы состояния связей (Link State Algorithm, LSA);

Алгоритмы состояния связей направляют потоки маршрутной информации во все узлы сети. Однако каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных связей. «Широковещательная» рассылка (передача пакета всем непосредственным соседям маршрутизатора) используется здесь только при изменениях состояния связей, что происходит не так часто. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети. Распространяемая по сети информация состоит из описания связей различных типов: маршрутизатор – маршрутизатор, маршрутизатор – сеть.

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

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

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

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

Внутренние протоколы маршрутизации rip и ospf

Протокол RIP (RoutingInformationProtocol) представляет собой один из первых протоколов обмена маршрутной информацией, однако до сих пор чрезвычайно распространен в вычислительных сетях. Помимо версии RIP для сетей TCP/IP, существует версия RIP для сетей IPX/SPX компании Novell [6].

В этом протоколе все сети имеют номера, а все маршрутизаторы – идентификаторы. Протокол RIP широко использует понятие «вектор расстояний». Вектор расстояний представляет собой набор пары чисел, являющихся номерами сетей и расстояниями до них в хопах (табл. 2.13).

Таблица 2.13 – Пример таблицы маршрутизации протокола RIP

Номер сети	Следующий маршутизатор	Порт	Расстояние
201.36.14.0	201.36.14.3	1	1
132.11.0.0	132.11.0.7	2	1
194.27.18.0	194.27.18.1	3	1

Векторы расстояний распространяются маршрутизаторами по сети, и через несколько шагов каждый маршрутизатор имеет данные о достижимых для него сетях и о расстоянии до них. Если связь с какой-либо сетью обрывается, то маршрутизатор отмечает этот факт тем, что присваивает элементу вектора, соответствующему расстоянию до этой сети, максимально возможное значение, которое имеет специальный смысл – «связи нет». Таким значением в протоколе RIP является число 16. Маршрутная информация об известной маршрутизатору сети не передается тому маршрутизатору, от которого она пришла.

Для каждой записи в таблице маршрутов существует время жизни, контролируемое таймером. Если для любой конкретной сети, внесенной в таблицу маршрутов, в течение 180 секунд не получен вектор расстояний, подтверждающий или устанавливающий новое расстояние до данной сети, то сеть будет отмечена как недостижимая (расстояние равно бесконечности). Через определенное время модуль RIP производит «сборку мусора», то есть удаляет из таблицы маршрутов все сети, расстояние до которых бесконечно.

При получении сообщения типа «ответ» для каждого содержащегося в нем элемента вектора расстояний модуль маршрутизатора RIP выполняет следующие действия [17]:

1) проверяет корректность адреса сети и маски, указанных в сообщении;

2) проверяет, не превышает ли метрика (расстояние до сети) бесконечность;

3) игнорирует некорректный элемент, если метрика превышает;

4) увеличивает значение метрики на 1, если метрика меньше бесконечности;

5) производит поиск сети, указанной в рассматриваемом элементе вектора расстояний, в таблице маршрутов.

Поиск сети осуществляется в соответствии со следующей логикой:

1) если запись о такой сети в таблице маршрутов отсутствует и метрика в полученном элементе вектора меньше бесконечности, сеть вносится в таблицу маршрутов с указанной метрикой; в поле Следующий маршрутизатор заносится адрес маршрутизатора, приславшего сообщение; запускается таймер для этой записи в таблице;

2) если искомая запись присутствует в таблице с метрикой больше, чем объявленная в полученном векторе, в таблицу вносятся новые метрика и, соответственно, адрес следующего маршрутизатора; таймер для этой записи перезапускается;

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

Во всех прочих случаях рассматриваемый элемент вектора расстояний игнорируется.

Сообщения типа «ответ» рассылаются модулем RIP каждые 30 секунд по широковещательному или мультикастинговому адресу; рассылка «ответа» может происходить также вне графика, если маршрутная таблица была изменена (triggeredresponse). Стандарт требует, чтобы triggeredresponse рассылался не мгновенно после изменения таблицы маршрутов, а через случайный интервал длительностью от 1 до 5 секунд. Эта мера позволяет несколько снизить нагрузку на сеть.

Итак, можно выделить основные показатели протокола RIP:

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

2) сегодня наиболее часто применяется вторая версия протокола (RIP-2);

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

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

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

Протокол OSPF (OpenShortestPathFirst – выбор кратчайшего пути первым) является достаточно современной реализацией алгоритма состояния связей (он принят в 1991 году) и обладает многими качествами, ориентированными на применение в больших гетерогенных сетях [28].

Как и все протоколы маршрутизации, основанные на алгоритме состояния свя­зей, OSPF разбивает процесс построения таблицы маршрутизации на два этапа.

На первом этапе каждый маршрутизатор строит граф связей сети, в котором вер­шинами являются маршрутизаторы и IP-сети, а ребрами – интерфейсы маршрутизаторов. Все маршрутизаторы обмениваются со своими сосе­дями той информацией о графе сети, которой располагают к данному мо­менту. Этот процесс похож на процесс распространения векторов расстояний до сетей в протоколе RIP, однако сама информация качественно иная – это инфор­мация о топологии сети. Сообщения, с помощью которых распространяется то­пологическая информация, называются объявлениями о состоянии связей сети (LinkStateAdvertisements, LSA). Кроме того, при передаче топологической ин­формации OSPF-маршрутизаторы ее не модифицируют, как это делают RIP-маршрутизаторы, а передают в неизменном виде. В результате, все маршрутиза­торы сети располагают идентичными сведениями о графе сети, которые хранят­ся в базе данных о топологии сети.

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

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

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

Если же состояние сети не меняется, то объявления о связях не генерируются и таблицы маршрутизации не корректируются, что экономит пропускную спо­собность сети и вычислительные ресурсы маршрутизаторов. Однако у этого пра­вила есть исключение: каждые 30 минут OSPF-маршрутизаторы обмениваются всеми записями базы данных топологической информации, то есть синхронизи­руют их для более надежной работы сети (так как этот период достаточно боль­шой, то данное исключение незначительно сказывается на работе сети) [33].

Маршрутизаторы соединены как с локальными сетями, так и непосредственно между собой глобальными двухточечными линиями связи, например канала­ми Т1. Протокол OSPF в своих объявлениях распространяет информацию о свя­зях двух типов: маршрутизатор–маршрутизатор и маршрутизатор–сеть.

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

Протокол OSPF поддерживает стандартные для многих протоколов значения расстояний для метрики, отра­жающей пропускную способность (для сети Ethernet она равна 10, для FastEthernet – 1, для канала Т1 – 65, для канала 56 Кбит/с – 1785 и т. д.).

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

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

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

2) при выборе маршрута OSPF-маршрутизаторы используют метрику, учитывающую пропускную способность составных сетей;

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

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

Внешний шлюзовый протокол bgp

Пограничный шлюзовой протокол BGP (Border Gateway Protocol) версии 4 является сегодня основным протоколом обмена маршрутной информацией меж­ду автономными системами Интернета. Протокол BGP пришел на смену протоколу EGP (в данном случае – название конкретного протокола маршрутизации. На­помним, что EGP служит также названием класса внешних шлюзовых протоколов, ис­пользуемых для маршрутизации между автономными системами), использовавшемуся в тот период, когда Интернет имел единственную магистраль.

Эта магистраль являлась центральной автономной системой, к которой присоединялись в соответствии с древовидной топологией все остальные автономные системы. Так как между автономными системами при такой структуре петли исключались, протокол EGP «не предпринимал никаких мер» для того, чтобы исключить зацикливание маршрутов [13].

Поясним основные принципы работы BGP на примере (рис. 2.14).

Рис. 2.14 – Поиск маршрута между автономными системами с помощью протокола BGP

В каждой из трех автономных систем (AS 1021, AS 363 и AS 520) имеется не­сколько маршрутизаторов, исполняющих роль внешних шлюзов, на которых работает протокол BGP, – с его помощью они общаются между собой.

Маршрутизатор взаимодействует с другими маршрутизаторами по протоколу BGP только в том случае, если администратор явно указывает при конфигурирова­нии, что эти маршрутизаторы являются его соседями. Например, маршрутизатор EG1 в рассматриваемом примере будет взаимодействовать по протоколу BGP с маршрутизатором EG2 не потому, что эти маршрутизаторы соединены двух­точечным каналом, а потому, что при конфигурировании маршрутизатора EG1 в качестве соседа ему был указан маршрутизатор EG2 (с адресом 194.200.30.2). Аналогично, при конфигурировании маршрутизатора EG2 его соседом назначается маршрутизатор EG1 (с адресом 194.200.30.1).

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

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

На рис. 2.14 также отображены две реализации протокола BGP (внутренняя и внешняя), которые отличаются инструкциями, обмениваемыми друг с другом маршрутизаторами. Реализация протокола, при которой маршрутизаторы, принадлежащие к одной автономной системе, устанавливают сеанс связи BGP, называется внутренней (Interior BGP, iBGP), в отличие от основной, внешней (Exterior BGP, eBGP), где соединяются маршрутизаторы различных автономных систем.

Для установления сеанса с указанными соседями BGP-маршрутизаторы исполь­зуют протокол TCP. При установлении BGP-сеанса могут приме­няться разнообразные способы аутентификации маршрутизаторов, повышаю­щие безопасность работы автономных систем.

Основным сообщением протокола BGP является сообщение UPDATE (обновить), с помощью которого маршрутизатор сообщает маршрутизатору соседней авто­номной системы о достижимости сетей, относящихся к его автоном­ной системе.

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

В одном сообщении UPDATE можно объявить о новом маршруте или аннулировать несколько устаревших (под маршрутом в BGP по­нимается последовательность автономных систем, которую нужно пройти на пути к указанной в адресе сети) [14].

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