Исследование алгоритмов маршрутизации в вычислительных сетях

Курсовая работа 
«Исследование алгоритмов маршрутизации в вычислительных сетях»
     
     
     
     

Содержание

Содержание	2
Введение	3
1. Исследование предметной области	5
1.1. Глобальная сеть Интернет	5
1.2. Основные параметры динамического протокола маршрутизации	8
1.3. Маршрутизация внутреннего шлюза	11
1.3.1. Протокол RIP	13
1.3.2. Протокол OSPF	15
2. Современные алгоритмы маршрутизации	17
2.1. Метод маршрутизации на основе алгоритма Дейкстры	17
2.2. Поиск пары кратчайших независимых по рёбрам путей  методом Суурбалле	20
2.3. Поиск пары кратчайших независимых по вершинам путей методом Суурбалле	24
2.4. Многопутевая маршрутизация методом Шольмайера	26
2.5. Многопутевая маршрутизация методом Райхерта	27
3 Современные проблемы исследуемой области	31
3.1 Основные типы сбоев в компьютерных сетях	31
3.2. Недостатки современной IP маршрутизации	33
Заключение	36
Список использованной литературы	37
     

Введение
     
     Практически с первым соединением двух компьютеров друг с другом, которые находятся на расстоянии появилось общее понятие сети. Сеть представляет собой совокупность оконечных устройств связи, которые объединены каналами передачи данных и коммутирующими устройствами (узлами сети), что обеспечивает обмен данными между всеми оконечными устройствами.
     Существуют как локальные так и глобальные сети. Локальные сети обычно объединяют в сеть компьютеры, расположенные в одном здании или нескольких зданиях или даже в пределах одной комнаты. Глобальная же компьютерная сеть может объединять множество локальных сетей, которые разбросаны по всему миру. Примером такой сети является Интернет (Internet).
     Определение термина Интернет было дано 24.10.1995 года Федеральным советом США по компьютерным сетям (FNC - Federal Networking Council): «Internet - это глобальная информационная система, которая логически соединена посредством адресного пространства, основанного на протоколе IP (Internet Protokol) или заменяющих его протоколов, способна поддерживать передачу данных посредством протокола ТСР (Transmission Contrel Protocol) или заменяющих его протоколов, обеспечивает, использует или делает доступными услуги по передаче данных и соответствующую инфраструктуру».
     Устройства, которые обеспечивают передачу данных между различными сетями, называют маршрутизаторами, к тому же они определяют наилучший путь для передачи этих данных.
     Для обмена информацией в Интернет необходимо знать адрес отправителя и адрес получателя. Обычно для этого используется протокол сетевого уровня – IP. Длина IP-адреса по версии 4 составляет 32 бита, нетрудно посчитать, что количество адресов примерно равно 4,23 миллиарда. Довольно небольшое количество, учитывая, что если надо организовать обмен данными между всеми устройствами (компьютеры, принтеры, серверы и т.д.), то необходимо выделить IP-адрес каждому устройству, к тому же эти адреса платные.
     Использование маршрутизатора позволяет более рационально назначать IP-адреса. Приведем самый простой пример. Есть локальная сеть, состоящая из N компьютеров, которым необходим выход в глобальную сеть. Каждому устройству присваивают частный IP-адрес (диапазон адресов, который не используется в глобальных сетях) и подключают к маршрутизатору. На WAN-интерфейсе прописывается только один внешний IP-адрес. К LAN-интерфейсам подключены все компьютеры. Далее включают механизм NAT – это процесс трансляции локальных адресов во внешние. Благодаря этому процессу компьютер получает доступ в Интернет.
     Для маршрутизации используются таблицы маршрутизации и протоколы, которые реализуют алгоритмы маршрутизации, чтобы определить наиболее рациональный путь для пересылки пакета данных. Протоколы маршрутизации могут делиться по типу взаимодействия между сетями. Внутренний протокол маршрутизации – протокол, служащий для обмена данными внутри автономной системы, например: RIP, OSPF и EIGRP; внешний протокол маршрутизации – протокол, служащий для обмена данными между автономными системами, например: BGP. Внутренние протоколы маршрутизации могут использовать алгоритм маршрутизации на основе вектора расстояний или на основе состояния канала.
     Цель данной работы провести исследование различных алгоритмов маршрутизации. Для успешной реализации поставленной задачи необходимо провести аналитический обзор литературы по исследуемой проблеме.
     
     
     

1. Исследование предметной области
1.1. Глобальная сеть Интернет
     
     С точки зрения маршрутизации Интернет состоит из большого количества автономных систем (АБ), которые представляют собой логически ограниченные области. Каждая автономная система управляется своей организацией и может использовать внутри свой алгоритм маршрутизации или несколько различных алгоритмов маршрутизации. Совокупность маршрутизаторов и сетей, использующих один и тот же алгоритм маршрутизации, называется доменом маршрутизации. Таким образом, автономная система может состоять из одного или нескольких доменов маршрутизации (рисунок 1.1). Однако чёткого различия между этими понятиями нет, и их часто применяют взаимозаменяемо [3].
     

Рисунок 1.1 - Пример автономной системы с несколькими доменами
маршрутизации
     
     В связи с выше описанной архитектурой протоколы маршрутизации можно подразделить на две категории: внутренние (Interior) и внешние (Exterior). Протоколы, обеспечивающие маршрутизацию внутри автономной системы, называются протоколами внутреннего шлюза или внутридоменными (IGP - Interior Gateway Protocol), а протоколы, обеспечивающие маршрутизацию между различными автономными системами, называются протоколами внешнего шлюза (Exterior Gateway Protocol) [4].
     Внутри корпоративной сети могут одновременно функционировать несколько протоколов внутреннего шлюза, отслеживающих маршруты к подсетям в пределах автономной системы. Маршрутизаторы, поддерживающие один и тот же протокол внутреннего шлюза, обмениваются информацией друг с другом в пределах одного домена маршрутизации. На границе доменов маршрутизации или автономных систем располагаются так называемые граничные маршрутизаторы (Border router). Они поддерживают несколько протоколов маршрутизации с целью обеспечения соединения доменов маршрутизации или автономных систем. Так на рисунок 1.1 показан маршрутизатор R1, который соединяет два домена маршрутизации внутри одной автономной системы, и маршрутизаторы R2 и R3, являющиеся граничными маршрутизаторами автономных систем AS 1 и AS2 соответственно.
     Граничные маршрутизаторы различных автономных систем поддерживают, во-первых, какой-либо протокол внутреннего шлюза через интерфейсы внутри своей «родной» автономной системы, и, во-вторых, какой-либо протокол внешнего шлюза через внешние интерфейсы, соединяющие собственную AS с удалённой AS. Протоколы внешнего шлюза распознают только автономные системы в иерархии маршрутизации и игнорируют протоколы внутреннего шлюза. Наиболее известным и широко распространённым протоколом внешнего шлюза, используемым в Интернет, является BGP (Border Gateway Protocol) [3-5]. Сильное влияние на работу протоколов внешнего шлюза оказывает тот факт, что автономные системы принадлежат различным владельцам. Между владельцами, как правило, заключается специальный договор о предоставляемом качестве обслуживания. Соответственно, протокол внешнего шлюза должен учитывать содержание этого договора в процессе построения маршрута. Маршрутизация внешнего шлюза является самостоятельной и очень обширной темой для научных исследований, мы же сосредоточим наши усилия на маршрутизации внутреннего шлюза.
     Структуры ЛВС могут иметь несколько разновидностей. Виды этих структур подразделяют:
     «звезда» - в этой структуре все элементы системы подключены к единому центральному узлу;
     кольцо – где элементы связаны друг с другом последовательно, по замкнутой цепи;
     шина - передача информации осуществляется по коммуникационному пути, доступному всем устройствам.
     При проектировании сети я решил использовать топологию типа «звезда», так как:
     Топология в виде звезды даёт наибольшее быстродействие из всех топологий вычислительных сетей, благодаря передаче данных между рабочими станциями через центральный узел (разумеется здесь предъявляются серьёзные требования к его производительности) по отдельным линиям, которые используются только этими рабочими станциями.
     Упрощается кабельное соединение, поскольку с узлом связана каждая  рабочая станция. 
     Малая частота запросов, по сравнению с достигаемой в других топологиях, передачи информации от одной станции к другой. При выходе из строя одной из машин, сеть остается работоспособной. 
     Центральный узел управления - файловый сервер может реализовать оптимальный механизм защиты против несанкционированного доступа к информации. Вся вычислительная сеть может управляться из ее центра.
Варианты данных топологий приведены на рисунок 1.2.

Рисунок 1.2 – Топологии компьютерных сетей
      
      Наращивание количества узлов в сети типа «звезда» ограничено количеством портов концентратора. ЛВС строится с использованием нескольких концентраторов, которые иерархически соединяются между собой связями типа звезда. Данный тип топологии называется «иерархическая звезда». Иерархическая звезда в настоящее время является самым распространенным типом топологии связей, как в локальных, так и глобальных сетях.
     
1.2. Основные параметры динамического протокола маршрутизации
     
     Перед тем как непосредственно перейти к современным протоколам маршрутизации, необходимо рассмотреть несколько факторов, помогающих динамическим протоколам маршрутизации определить предпочтительный или кратчайший маршрут к определённому пункту назначения. К таким факторам относятся метрики и алгоритмы маршрутизации.
     Метрики маршрутизации — это переменные параметры (показатели) сети, на основании которых принимается решение о выборе маршрута. Для некоторых протоколов маршрутизации эти метрики являются статическими величинами и не могут изменяться. При использовании других протоколов маршрутизации эти значения могут назначаться администраторами сети. В большинстве случаев к метрикам относятся следующие показатели: длина маршрута или число пересылок (hop); ширина полосы пропускания (bandwidth); задержка (delay); надёжность (reliability); нагрузка сети (load) и стоимость связи (cost)[6].
     
Длина маршрута
     
     Длина маршрута - это показатель, используемый для определения расстояния до пункта назначения на основании количества пересылок дейтаграммы, т.е. числа сетей, через которые проходит дейтаграмма до пункта назначения. Каждый раз, когда маршрутизатор направляет дейтаграмму в очередной сегмент, считается одной пересылкой. Протоколы маршрутизации, которые отслеживают число пересылок как первостепенный показатель (метрика длины маршрута), решают, что наилучший или предпочтительный маршрут в пункт назначения - это маршрут, содержащий наименьшее число пересылок.
     
Ширина полосы пропускания
     
     Пропускная способность полосы пропускания измеряется в битах, переданных в секунду. Каналы связи, которые поддерживают более высокую полосу пропускания, являются более предпочтительными по сравнению с более медленными каналами связи.
     
Надёжность
     
     Этот показатель может быть сконфигурирован как фиксированное значение администратором сети, однако, как правило, он определяется динамически в пределах заданного отрезка времени. Маршрутизаторы отслеживают присоединённые каналы и сообщают о возникающих проблемах, таких как неисправность линий связи, ошибки интерфейсов, потерии дейтаграмм и т.д. Каналы с наибольшим числом проблем рассматриваются как менее надёжные по сравнению с другими и поэтому маршруты по ним считаются нежелательными. Значение надёжности обычно измеряется в пределах от 1 до 255, где 255 — показатель наивысшей надёжности [3].
     
Нагрузка
     
     Нагрузка сети является переменным значением и измеряется объёмом трафика в данном канале за промежуток времени (обычно за 5 секунд) в процентах от общего объёма трафика канала [3]. По мере увеличения трафика нагрузка на канал возрастает.
     
Стоимость
     
     Администраторы сети могут влиять на принятие решений маршрутизаторами о наилучших маршрутах путём установки произвольных значений метрики стоимости каналов на протяжении всего пути пакетов. Эти произвольные значения обычно представляют собой целые числа. При этом низкие значения метрик обозначают лучшие маршруты.
     
1.3. Маршрутизация внутреннего шлюза
     
     Протоколы маршрутизации делятся на две основные категории по типу алгоритмов лежащих в их основе: протоколы вектора расстояния и протоколы состояния канала.
     Алгоритмы вектора расстояния действуют следующим образом [4]. Каждый маршрутизатор содержит таблицу со всеми известными кратчайшими путями к получателю. Каждая таблица содержит запись для каждого узла-получателя сети, в которой указаны имя оптимального сетевого интерфейса для отправления дейтаграммы к заданному получателю и расстояние до этого получателя, которое, как правило, определяется числом пересылок до него или какой-либо другой метрикой. Для обновления данных этих таблиц производится периодический обмен информацией с соседними маршрутизаторами. Если маршрутизатор узнаёт, что один из соседей знает более короткий маршрут к получателю, то он заменяет данные в своей таблице на новые. Алгоритмы вектора расстояния легко реализовать и они обладают тем преимуществом, что каждому маршрутизатору достаточно знать только всех своих соседей, а не всю топологию сети. В полностью статичной среде протоколы вектора расстояния могут работать весьма успешно, в динамической же среде им это не всегда удаётся, так как при изменении маршрутов информация недостаточно быстро распространяется от одного маршрутизатора к другому, при этом некоторые маршрутизаторы могут содержать неправильную информацию. Кроме того, служебные сообщения, которыми обмениваются Маршрутизаторы, достаточно велики, так как они содержат данные о всех маршрутизаторах. Объём передаваемой при этом служебной информации может достигать огромных размеров.
     Алгоритмы маршрутизации состояния канала более хорошо приспособлены к изменениям, происходящим в сети. Каждый маршрутизатор, использующий подобный протокол маршрутизации, прежде всего пытается получить информацию о соседях. Для этого он посылает специальное «HELLO» сообщения по всем исходящим линиям. Соседние маршрутизаторы отвечают ему аналогичным сообщением. Алгоритм маршрутизации состояния канала требует от каждого маршрутизатора знания или обоснованной оценки задержки для всех линий связи со своими соседями. Наиболее просто это можно сделать, послав специальное сообщение «ECHO», на которое другая сторона должна немедленно ответить. После этого отправитель может получить приемлемое время задержки, разделив время пересылки сообщения туда и обратно на два. Посылая это сообщение несколько раз и используя среднее арифметическое, отправитель может получить более точный результат. После этого маршрутизатор создаёт сообщение, содержащее всю собранную информацию и широковещательно рассылает его по всем линиям. Каждое сообщение состояния линий содержит порядковый номер, что помогает использовать только поступающую новую и игнорировать устаревшую информацию. В результате вышеописанных действий каждый маршрутизатор обладает информацией о топологии и характеристиках всех линиях связи данного домена сети. На основе имеющейся информации маршрутизатор может вычислить кратчайший путь ко всем остальным маршрутизаторам с помощью локального применения какого- либо алгоритма (наиболее часто используется алгоритм нахождения кратчайшего пути Дейкстры). Одним из основных преимуществ алгоримов маршрутизации состояния канала является то, что каждый маршрутизатор вычисляет кратчайшие пути самостоятельно, используя данные, которые не зависят от вычислений промежуточных машин. Так как сообщения о состоянии линий распостраняются без изменений, то возникающие проблемы легко локализовать. Сообщения, которыми обмениваются маршрутизаторы состояния канала, значительно меньше сообщений, которыми обмениваются маршрутизаторы вектора расстояния. Таким образом, протоколы маршрутизации состояния канала лучше приспособлены для больших сетей, чем протоколы маршрутизации вектора расстояния.
     Рассмотрим основные протоколы этих типов, используемые для маршрутизации внутреннего шлюза.
     
1.3.1. Протокол RIP
     
     Протокол маршрутизации RIP — это протокол вектора расстояния маршрутизации внутреннего шлюза. Он определён в документах RFC 1058 (RIP version 1) и RFC 2453 (RIP version 2). Работа протокола основана на широковещательной рассылке. Маршрутизаторы одного и того же сегмента обмениваются сообщениями о корректировках с помощью широковещательной рассылки, которую они осуществляют каждые 30 секунд. Каждый маршрутизатор имеет свой таймер, управляющий рассылками сообщений. Максимальное число пересылок для этого протокола равно 15 [6]. Эти сообщения содержат полные копии таблиц маршрутизации, независимо от того, имеются ли изменения в сети или нет. Каждый маршрутизатор должен обработать полученные сообщения, дождаться завершения 30 секундного периода и лишь затем послать собственное сообщение. При этом после получения оповещения о произошедших в сети изменениях маршрутизатор, прежде чем изменить собственную таблицу маршрутизации, дождётся дополнительного пятикратного подтверждения (180 секунд). Аналогично обстоит ситуация с отказами маршрутизаторов. Маршрутизатор считает другой маршрутизатор вышедшим из строя, только если тот не получает от него сообщений дольше чем в течение 180 секунд. В связи с этим время сходимости может быть очень большим.
     В качестве метрики RIP использует только число пересылок до пункта назначения, т.е. если существует несколько маршрутов к пункту назначения, то маршрутизатор выбирает кратчайший (в основе работы протокола лежит алгоритм выбора наилучшего маршрута Форда- Фалкерсона). Однако такой упрощённый метод выбора пути, основанный на одной метрике, далеко не всегда обеспечивает лучший результат. Например, допустим, что существуют два маршрута к пункту назначения. Первый состоит из трёх участков с пропускной способностью 100 Мбит/с, а второй состоит из двух участков с пропускной способностью 10 Кбит/с каждый. Протокол RIP выберет маршрут с наименьшим числом пересылок, для данного случая это будет маршрут с более низкой скоростью передачи данных.
     
     Таким образом, можно выделит следующие недостатки протокола RIP:
* Очень большое время сходимости. Данный протокол не способен оперативно реагировать на динамические изменения, происходящие в сети.
* Максимальная длина возможного маршрута равна 15 пересылкам. Следовательно, протокол плохо подходит для использования в больших сетях.
* Основан на широковещательной рассылке сообщений, посылает полные таблицы маршрутизации, даже если в сети нет изменений. Это увеличивает нагрузку на каналы передачи данных.
* Склонен к образованию циклов маршрутизации [5].
     Не смотря на то, что большинство других протоколов маршрутизации более эффективно выбирают маршрут и обладают большей гибкостью, протокол RIP v1 остаётся наиболее популярным, в основном благодаря простоте настройки.
     Вторая версия протока RIP была разработа с целью преодоления недостатков первой версии. Основными отличительными особенностями версии 2 протокола RIP являются: поддержка аутентификации и бесклассовых сетей (VLSM), а также возможность использования для маршрутизаторов при обмене информацией не только широковещательной, но и многоадресной рассылки. Однако основные недостатки, присущие первой версии, сохранились и во второй. Поэтому протокол не нашёл широкого распространения.
     
1.3.2. Протокол OSPF
     
     Протокол маршрутизации OSPF (Open Shortest Path First) является протоколом маршрутизации с учётом состояния каналов. Он определён в документе
     RFC 1583 [7]. В основе работы протокола OSPF лежит представление о множестве сетей, маршрутизаторов и линий связи в виде направленного графа, в котором каждой дуге поставлена в соответствие её цена. OSPF обеспечивает все маршрутизаторы сети полной информацией о топологии автономной системы. Каждый маршрутизатор может затем определить кратчайший маршрут (с точки зрения выбранной метрики) до каждого конечного пункта назначения и сохранить соответствующий IP адрес сетевого интерфейса для следующего шага в локальную таблицу маршрутизации. Алгоритм нахождения кратчайшего маршрута (Алгоритм Дейкстры), лежащий в основе этого протокола, автоматически гарантирует отсутствие циклов в маршрутизации, так как маршрут, содержащий цикл маршрутизации, не может быть короче другого маршрута без цикла.
     При построении маршрутов протокол OSPF может использовать несколько метрик: ширину полосы пропускания, надёжность, нагрузку и задержку. Чаще всего OSPF использует лишь ширину полосы пропускания [12].
     В обычном режиме работы, если существует несколько кратчайших маршрутов одинаковой стоимости, то обычно выбирается первый из них, но выбор непредсказуем, потому что использование различных реализаций алгоритма может приводить к различным результатам [6].
     OSPF может также работать совместно с протоколом Equal-Cost Multi- Path (ЕСМР), который описан в стандарте IETF RFC 2992. Тогда если до пункта назначения имеется несколько маршрутов с одинаковой стоимостью, то маршрутизаторы могут использовать все эти маршруты. Балансировка нагрузки по ним происходит автоматически, а именно - трафик распределяется на равные доли. Если же маршруты имеют различную стоимость, то OSPF требует ручной настройки. ЕСМР чаще всего используется совместно протоколом маршрутизации OSPF, но многие современные маршрутизаторы поддерживают также совместную работу ЕСМР с другими протоколами маршрутизации, такими как RIP, BGP и IS-IS.
     Маршрутизаторы OSPF обмениваются с соседями приветственными сообщениями каждые 10 секунд. Маршрутизатор считает своего соседа вышедшим из строя, если не получет от него приветственного сообщения в течение четырёх интервалов, т.е. только после 40 секунд с момента отказа соседнего маршрутизатора.
     После обнаружения разрывов соединений или появления новых маршрутов в сети маршрутизаторы быстро адаптируются к этим изменениям. Когда маршрутизатор обнаруживает разрыв соединения или новый канал, он сразу же генерирует сообщение о корректировке, инициируя лавинную рассылку.
     OSPF обладает многими преимуществами по сравнению с протоколами вектора состояния [11]. Например, OSPF использует многоадресную рассылку вместо широковещательной для распространения маршрутной информации среди соседних маршрутизаторов. Сообщения о корректировках посылаются, только если в сети происходят изменения, т.е. периодическая рассылка отсутствует, а все сообщения являются инициированными. Причём сообщения рассылаются всем маршрутизаторам OSPF (лавинная рассылка), что сокращает время сходимости. Каждое сообщение о корректировке включает в себя только изменение маршрутной информации, а не всю таблицу маршрутизации. Благодаря отсутствию ограничения на максимальное числом пересылок протокол OSPF способен работать в больших сетях.
     

2. Современные алгоритмы маршрутизации
     
     Для того, чтобы усовершенствовать существующие механизмы маршрутизации, необходимо рассмотреть их более подробно. Ниже приводятся ряд ниболее широко применяемых алгоритмов. Первый из них - это алгоритм Дейкстры [12, 13], лежащий в основе протокола OSPF и широко используемый в других алгоритмах маршрутизации. Два алгоритма Суурбалле предназначены для многопотоковой маршрутизации. Первый из них позволяет строить маршруты, независимые по рёбрам, а второй - по узлам. Особенностью этих двух алгоритмов является то, что они могут быть использованы только для маршрутизации с использованием адреса источника. Почти все существующие на данный момент алгоритмы многопутевой маршрутизации предназначены именно для этого типа маршрутизации. К сожалению, у маршрутизации с использованием адреса источника есть очень существенный недостаток, так как маршрутизатор должен анализировать ещё и адрес отправителя пакета, то это приводит к многократному увеличению таблиц маршрутизации. Следовательно, маршрутизация с учётом адреса источника малопригодна для больших сетей.
     
2.1. Метод маршрутизации на основе алгоритма Дейкстры
     
     Алгоритм Дейкстры [12] широко используется для маршрутизации. Он лежит в основе работы протокола маршрутизации OSPF, а также используется многими алгоритмами маршрутизации. Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, Е) с исходной вершиной S, в котором длины (веса) всех рёбер неотрицательны: для всех . Если требуется найти кратчайший путь между двумя вершинами, то алгоритм прекращает работу, когда такой путь найден. Обозначим исходную вершину как S, а конечную вершину как Z.
     Проведём ряд обозначений. Пусть  - это расстояние (стоимость пути) до вершины от исходной вершины S. Она равна сумме длин (весов) рёбер на протяжении возможного пути из вершины S к вершине U. При этом .  это вершина-предшественница вершины U на пути от S к Z.
     Алгоритм включает в себя следующие шаги:
     
     Шаг 1.
     Положим , 
     Обозначим: = множество соседних вершин вершины U;
      = длина (вес) ребра от вершины U к вершине W.
     Если , то положим ,
     Иначе  (большое, но конечное число).
     Обозначим: V’=V-{S}, где V - это множество всех вершин в заданном графе.
     .
     
Шаг 2.
     а) Найдём такое, что 
     Положим V' = V' - {W}.
     Если W= Z, то Стоп; иначе выполнить Шаг 3.
     
Шаг 3.
     и если ,
     To положить: и p(U) = W.
     Выполнить Шаг 2.
     
     На первом шаге алгоритма расстояние от любой вершины графа (кроме S) до вершины S инициализируется значением Big_number. После этого алгоритм чередует шаги 1 и 2. Обновление значения расстояния происходит на шаге 3 путём проверки соседей вершины, выбранной на шаге 2а; проверка ограничена только теми вершинами, которые принадлежат множеству V' . После того как значение расстояния для вершины обновлено, эта вершина становится вершиной-предшественницей на шаге 3.
     Если вершина была выбрана на шаге 2а, то кратчайший путь до этой вершины от вершины S найден. Алгоритм находит кратчайший путь к ближайшей вершине от вершины S, затем вторую ближайшую вершину, и так далее до тех пор, пока вершина Z не будет выбрана на шаге 2с. В этот момент искомый кратчайший путь до вершины Z найден, и длина этого пути равна текущему значению d(Z).
     Если шаг 2с заменить на «Если V' пусто, то Стоп», то алгоритм найдёт кратчайший путь от вершины S до каждой вершины графа. Найденный набор всех кратчайших путей называется деревом кратчайших путей с корнем в вершине S. Данное дерево используется как протоколом OSPF, так и протоколом ЕСМР.
     Рабочей группой по вопросам маршрутизации (Routing Area Working Group - RTGWG), осуществляющей свою деятельность в рамках организации IETF, была предложена модификация алгоритма Дейкстры, которая в данной диссертации будет наименоваться модифицированный алгоритм ЕСМР. Суть модификации состоит в том, что графы маршрутизации содержат не только кратчайшие пути, построенные при помощи алгоритма Дейкстры, но также и рёбра, направленные от более дальних узлов к более ближним. Цель данной модификации состоит в том, чтобы обеспечить многопутевую маршрутизацию для как можно большего числа узлов, не создавая при этом петель маршрутизации. Практически это реализуется в виде дополнительного шага для каждого получателя:
     
Шаг 4.
     Для всех 
     Если d(U)>d(W), то добавить в итоговый граф маршрутизации ориентированное ребро (U, W).
     Время работы алгоритма Дейкстры . Время работы модифицированного алгоритма ЕСМР составляет .
     К достоинствам представленных в данном разделе алгоритмов необходимо отнести то, что они всегда строят графы маршрутизации, содержащие кратчайшие пути, а также их скорость работы. Недостатком же является то, что представленные алгоритмы не способны обеспечить многопутевой маршрутизацией все узлы в графе.
     
2.2. Поиск пары кратчайших независимых по рёбрам путей 
методом Суурбалле
     
     Данный алгоритм [15] основан на двухкратном использовании алгоритма Дейкстры в сочетании с преобразованием исходного графа. Алгоритм включает в себя следующие шаги для нахождения двух независимых по рёбрам путей из вершины S до вершины Z:
     
Шаг 1. 
     а) Для заданного графа G = (V,Е) выполнить следующее преобразование:
     
     для всех рёбер графа G, где - это длина ребра UW, и d(K) обозначает длину кратчайшего пути от начальной вершины S до вершины К. Данное преобразование графа приводит к тому, что длина всех рёбер графа, являющихся частью дерева кратчайших путей с корнем в вершине S, становится равной нулю. Длина же остальных рёбер остаётся больше нуля.
     b) Применить алгоритм Дейкстры для нахождения d(K) (длины кратчайшего пути от вершины S до вершины К) .
     
Шаг 2.
     Удалить все те дуги вдоль кратчайших путей, которые направлены к начальной вершине Б. Изменить направление оставшихся дуг (имеющих нулевую длину) кратчайших путей так, чтобы они стали направлены в сторону вершины Б.
     
Шаг 3.
     Применить алгоритм Дейкстры ещё раз, чтобы найти кратчайший путь от от начальной вершины Б до конечной вершины X для полученного после преобразования графа G’.
     
Шаг 4. 
     Преобразовать имеющийся граф к начальному графу. Удалить дуги, являющиеся частью обоих найденных путей из вершины S к вершине Z. После этого искомые пути найдены.
     

Рисунок 1.2 - Двунаправленный взвешенный граф.
     

Пример 1.1
     
     Найти два кратчайших независимых по рёбрам пути от вершины S к вершине Z для графа, изображённого на рисунке 1.2, при помощи алгоритма Суурбалле.

Рисунок 1.3 - Граф G’, полученный преобразованием длины рёбер графа G.
     
     Цифры в скобках соответствуют длине кратчайшего пути от вершины S.
     
Шаг 1.
     
     Рисунок 1.3 демонстрирует результат преобразования графа, приведённого на еисуноке 1.2. Цифры, представленные в скобках около вершин на рисунке 1.3, соответствуют длинам кратчайших путей до этих вершин от вершины S. Кратчайшим путём от вершины S до вершины Z является путь SBCZ  длиной 3.
     

     Рисунок 1.4 - Граф, полученный преобразованием графа С.
     
Шаг 2. 
     
     На рисунке 1.4 изображён модифицированный граф после удаления дуг ZC, CB и BS, и последующей за ним смены направления дуг с нулевой длиной SB, ВС и CZ.
     
Шаг 3. 
     
     Кратчайший путь от S к Z для графа на рисунке 1.4, который может быть найден при помощи алгоритма Дейкстры, это путь SFCBEZ длиной 2.
     
Шаг 4.
     
     В начальном графе (рисунк 1.2) общая часть двух путей SBCZ и SFCBEZ - это ребро ВС. Если его удалить, то образуются два пути SFCZ и SBEZ.
     

2.3. Поиск пары кратчайших независимых по вершинам путей методом Суурбалле
     
     Данный алгоритм [15] основан на применении разбиения вершин графа. Алгоритм включает в себя следующие шаги:
     
Шаг 1. 
     Для заданной пары вершин S и Z найти кратчайший путь с использованием алгоритма Дейкстры. Рассмотрим работу алгоритма на примере графа, изображённого на рисунке. 1.2.
     
Шаг 2. 
     Заменить дуги вдоль кратчайшего пути дугами нулевой длины, направленными к цели. Для рассматриваемого примера кратчайшим путём из S до Z является SBCZ.
     
Шаг 3. 
     Разбить каждую вершину кратчайшего пути (кроме начальной и конечной) на две вершины, соединённые дугой нулевой длины. Направить эту дугу по направлению к цели. Заменить каждое внешнее ребро, соединённое с вершиной кратчайшего пути двумя дугами той же длины, что и внешнее ребро, таким образом, чтобы одна дуга начиналась в одном из новообразованных узлов, а другая заканчивалась в его близнеце. При этом дуги должны быть направлены таким образом, чтобы не образовывать цикла. Рисунок 1.5 демонстрирует граф, полученный после выполнения шага 3. Вершина В была разбита на В’ и В’’ а вершина С на C’ и C’’.

Рисунок 1.5. Модифицированный граф G' после применения третьего шага алгоритма Суурбалле для поиска двух кратчайших путей, независимых по вершинам.
     
Шаг 4.
     
     Применить алгоритм Дейкстры вторично и найти второй кратчайший путь. Для рассматриваемого примера это будет SFCGZ. Таким образом, два независимых по вершинам пути от вершины S к вершине Z для графа, изображённого на рисунке 1.2, найдены: это SBCZ и SFCGZ.
     Данный алгоритм, как и предшествующий, обладает одним существенным недостатком: он не может быть использован для маршрутизации по адресу получателя.
     

2.4. Многопутевая маршрутизация методом Шольмайера
     
     Работа алгорима[16] состоит из следующей последовательности шагов:
     1. Инициализировать множество всех узлов, которые имеют прямую дугу к адресату d. Инициализировать R этими прямыми дугами.
     2. Проверить, связаны ли узлы в S1 непосредственно, и выбрать одну из этих связей как дугу-джокер для адресата d.
     3. Сохранить узел адресата и эти два узла джокера (которые являются теперь O2 узлами) в списке LO2 O2 узлов и удалить их из S1.
     4. Проверить, имеют ли остающиеся в S1 узлы связь с одним из узлов, уже содержащимся в LO2. Если да, то добавить соответсвующую прямую дугу в R и переместить узел из S1 к L02.
     5. Повторить шаг 4, если S1 не пуст.
     6. Проверить, имеют ли остающиеся в сети узлы, которые еще не содержатся в LO2, связи с двумя узлами в LO2. Если да, добавить соответствующие дуги к R и добавить узел к LO2.
     7. Повторять шаг 6 до тех пор, пока все узлы сети (кроме адресата) не будут содержатся в LO2.
     Этот алгоритм может успешно применяться только для использования с теми топологиями компьютерных сетей, для которых можно построить многопутевую маршрутизацию с использованием только одного джокера для каждого адресата.
     Сложность вычисления всех маршрутизаций с этим алгоритмом О .
     
     
2.5. Многопутевая маршрутизация методом Райхерта

Классификация дуг
     
     Следующее определение полезно для более точного описания сети и графов маршрутизации.
     
Определение 1.1 (Классификация дуг)
     Дана сеть N = (V, Е) и узел-адресат , каждому узлу может быть присвоена метка числа пересылок  от узла и к узлу адресата d. Дуги  тогда классифицированы следующим образом:
     1) Если , тогда - прямая дуга (относительно
 адресата d)
     2) Если , тогда  - кольцевая дуга (относительно 
адресата d).
     3) Если , тогда - обратная дуга (относительно 
адресата d).
     Самый короткий путь содержит только прямые дуги. Инверсия прямой дуги - это обратная дуга, и наоборот, в то время как инверсия кольцевой дуги остаётся кольцевой дугой.
     Алгоритм, описанный в данном подразделе, использует как входные параметры сеть N = (V, Е) и узел-адресат . Результатом работы алгорит.......................