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

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

Содержание

Введение

Глава 1. Общие сведения

.1 Маршрутизация

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

.3 Теория графов

Глава 2. Анализ алгоритмов маршрутизаций

.1 Анализ алгоритма Дейкстры

.2 Анализ алгоритма Флойда

Глава 3. Разработка алгоритмов маршрутизации

.1 Разработка алгоритма маршрутизации Дейкстры

.1.1 Таблица кратчайших путей и маршрутов

.2 Разработка алгоритма маршрутизации Флойда

.2.1 Таблица кратчайших путей и маршрутов

.3 Сравнительный анализ алгоритмов маршрутизации

Заключение

Список использованной литературы

Введение

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

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

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

·        алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);

Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.

Таким образом, задачи данной работы можно сформулировать следующим образом:

·        Ознакомиться с управлением процессами маршрутизации пакетов, передаваемых через сеть.

·        Изучить теорию выбора кратчайших путей и ее методов.

·        Написать программу, отладить и решить ее на ПК.

·        Получить таблицу кратчайших путей и маршрутов методом Дейкстры и Флойда.

Глава 1. Общие сведения

1.1    Маршрутизация

Маршрутизация (англ. Routing) - процесс определения маршрута следования информации в сетях связи.

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

Статическими маршрутами могут быть:

маршруты, не изменяющиеся во времени;

маршруты, изменяющиеся по расписанию;

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

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

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

1.3   
Теория графов

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

Дадим теперь более формально основное определение теории графов. Граф G есть упорядоченная пара (V,E), где V - непустое множество вершин, E - множество пар элементов множества V, пара элементов из V называется ребром. Упорядоченная пара элементов из V называется дугой.

Если ребра имеют направление, то граф называется ориентированным (орграфом); в противном случае он неориентированный. Если в графе есть ребро C из вершины A в вершину B, то говорят, что ребро C инцидентно вершинам A и B, а также что вершина A смежна с вершиной B.

Рис 1. Примеры графов

Рис 2. Пример полного и двудольного графа.

Глава 2. Анализ алгоритмов маршрутизации

Алгоритмы маршрутизации классифицируются на статические и динамические (рис. 3). Т.е алгоритмы, которые явно не причисляются к этим типам, определяют стратегию маршрутизации, не определяя конкретные принципы построения протоколов.

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

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

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

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

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

Динамические алгоритмы для оценки оптимальности пути используют механизм метрик. Метрикой для дистанционно-векторной маршрутизации является число отрезков сети (хопов) между отравителем и получателем. На основании данной метрики выбирается оптимальный маршрут, локально используя алгоритм Дийкстры. Данный метод глобально использовался в коммерческих сетях и сетях общего назначения до начала 80х годов XX века. Данный алгоритм имеет ряд недостатков, главным из которых является проблема счета до бесконечности. Практическая реализация алгоритма выполнена в. виде протокола RIP. Сейчас же данный метод уступил место более совершенным, но его еще поддерживает подавляющий процент выпускаемого оборудования, операционных систем (MVS, Unix, семейство MSWindowsServer).

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

2.1     Анализ алгоритма Дейкстры

Алгори́тм Де́йкстры - алгоритм на графах, изобретённый нидерландским учёным Э. Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

Алгоритм Де́йкстры пошагово.

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

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

Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Рис. 4

Рис. 5

Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Рис. 7

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Рис. 8

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Рис. 9

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Рис. 10

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.

Рис. 11

Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.

Рис. 12

Рис. 13

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Рис. 14

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Рис. 15

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачёркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачеркнутыми, если до них нельзя добраться. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.

.2 Анализ алгоритма Флойда

Алгоритм Флойда - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом, хотя в 1959 году Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

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

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 1). Если выполняется неравенство d_ij + d_jk <d_ik, то целесообразно заменить путь i ->k путем i ->j ->k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.16. Треугольный оператор

Алгоритм Флойда требует выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояния D₀ и матрицу последовательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:

Рис. 17. Начальная ситуация

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_ijматрицы D_k-1. Если выполняется неравенство d_ik + d_kj <d_ij, (i<>k, j<>k, i<>j), тогда выполняем следующие действия:

создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij на сумму d_ik + d_kj,

создаем матрицу S_k путем замены в матрице S_k-1 элемента s_ij на k. Полагаем k = k + 1 и повторяем шаг k.

Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу D_k-1 так, как она показана на рисунке 3. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами: