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

дистанционно-векторный алгоритм (Distance Vector Algorithms, DVA), измеряется в хопах.

алгоритм состояния связей (Link State Algorithms, LSA), измеряется в тиках (ticks).

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

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

В начале 90-х годов фирма Cisco Systems представила усовершенствованный протокол IGRP (Enhanced IGRP - EIGRP), в котором попыталась объединить преимущества протоколов маршрутизации с учетом состояния каналов (link-state) и протоколов маршрутизации на основе длины векторов (distance-vector). Протокол EIGRP основан на алгоритме обновления Diffusing-Update Algorithm (DUAL), определяющем процедуру принятия решений при вычислении всех маршрутов. Используя метрики, DUAL выбирает наиболее эффективные и свободные от петель пути и вносит их в таблицу маршрутов в качестве наилучших и возможных запасных. Если основной маршрут становится недоступным, то задействуется запасной. Это позволяет избежать повторного выполнения алгоритма в случае отказа какой-либо линии связи и уменьшить время сходимости. Для выявления соседей протокол EIGRP использует короткие сообщения "Hello". Пока маршрутизатор получает такие сообщения от соседних маршрутизаторов, он "считает", что они работают и могут передавать информацию о маршрутах. Применяя протокол Reliable Transport Protocol, EIGRP обеспечивает гарантированную доставку сообщений об обновлениях маршрутов, не "полагаясь" при этом на широковещательную передачу.

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

Протокол Open Shortest Path First (OSPF) был создан Инженерной проблемной группой Internet (Internet Engineering Task Force - IETF) в конце 80-х годов, когда стало очевидным, что RIP не способен обслуживать большие неоднородные сети. Этот открытый стандартный протокол поддерживают все основные производители маршрутизаторов. Он является классическим протоколом маршрутизации с учетом состояния каналов (link-state), но обеспечивает маршрутизацию только трафика IP.

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

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