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

Содержание Введение

• Глава 1. Общие сведения
• 1.1 Маршрутизация
• 1.2 Алгоритмы маршрутизации
• 1.3 Теория графов
• Глава 2. Анализ алгоритмов маршрутизаций
• 2.1 Анализ алгоритма Дейкстры

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

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

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

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

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

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

3.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

Рис. 6

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

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

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

Рис. 18. Иллюстрация алгоритма Флойда

После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам.

Расстояние между узлами i и j равно элементу d_ij в матрице D_n.

Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i ->k ->j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

Пример. Найдем для сети, показанной на рисунке 4, кратчайшие пути между любыми двумя узлами. Расстояние между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны:

Рис. 19. Пример сети

Шаг 0. Начальные матрицы D₀ и S₀ строятся непосредственно по заданной схеме сети. Матрица D₀ симметрична, за исключением пары элементов d₃₅ и d₅₃, где d₅₃ равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:

Рис. 20. Начальное состояние

Шаг 1. В матрице D₀ выделены ведущие строка и столбец (k = 1). Двойной рамкой представлены элементы d₂₃ и d₃₂, единственные среди элементов матрицы D₀, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D₀ и S₀ получить матрицы D₁ и S₁, выполняем следующие действия.

Заменяем d₂₃ на d₂₁ + d₁₃ = 3 + 10 = 13 и устанавливаем s₂₃ = 1.

Заменяем d₃₂ на d₃₁ + d₁₂ = 10 + 3 = 13 и устанавливаем s₃₂ = 1.

Матрицы D₁ и S₁ имеют следующий вид:

Рис. 21. Матрицы D₁ и S₁

Шаг 2. Полагаем k = 2; в матрице D₁ выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D₁ и S₁, выделенным двойной рамкой. В результате получаем матрицы D₂ и S₂:

Рис. 22. Матрицы D₂ и S₂

Шаг 3. Полагаем k = 3; в матрице D₂ выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D₂ и S₂, выделенным двойной рамкой. В результате получаем матрицы D₃ и S₃:

Рис. 23. Матрицы D₃ и S₃

Шаг 4. Полагаем k = 4, ведущие строка и столбец в матрице D₃ выделены. Получаем новые матрицы D₄ и S₄:

Рис. 24. Матрицы D₄ и S₄

Шаг 5. Полагаем k = 5, ведущие строка и столбец в матрице D₄ выделены. Никаких действий на этом шаге не выполняем; вычисления закончены.

Конечные матрицы D₄ и S₄ содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d₁₅ = 12.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда s_ij = j. В противном случае узлы i и jсвязаны, по крайней мере, через один промежуточный узел. Например, поскольку s₁₅ = 4 и s₄₅ = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5. Но так как s₁₄ не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s₁₄ = 2 и s₂₄ = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку s₁₂ = 2 и s₂₄ = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12 километрам.

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

3.1 Разработка алгоритма маршрутизации Дейкстры Рис. 25. Блок схема Алгоримтма Демйкстры

Алгоримтм Демйкстры реализован на языке программирования C#

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

namespace ConsoleApplication18

{

class Program

{

sealed public class Node

{

public List

Links { get; set; }

public Node ()

{

Links = new List

();

}

}

sealed public class Link

{

public double Distance { get; set; }

public string Node { get; set; }

}

sealed public class Description

{

publicbool Visited { get; set; }

public double Distance { get; set; }

public Description ()

{

Visited = false;

Distance = double. PositiveInfinity;//+8

}

}

sealed public class Graph

{

private Dictionary nodes;

public Graph ()

{

nodes = new Dictionary ();

}

public void AddNode (string name)

{

nodes.Add (name, new Node ());

}

public void AddLinkToNode (string start, string end, double distance, boolisOriented)

{

nodes[start]. Links. Add (new Link { Node = end, Distance = distance });

if (!isOriented)

nodes[end]. Links. Add (new Link { Node = start, Distance = distance });

}

public double FindShortestDistance (string start, string end)

{

// АлгоритмДейкстры

Dictionary info = new Dictionary (this.nodes.Count);

foreach (string current in this.nodes.Keys)

info.Add (current, new Description ());//visited, distance

info[start]. Distance = 0;

// Пока все вершины непосещенные

while (!info.Select (x =>x.Value.Visited).Aggregate ((x, y) => x & y))

{

// Находим непосещенную вершину с минимальной меткой

string current = info. Where (x => !x.Value.Visited

&&x.Value.Distance == info. Where (y => !y.Value.Visited).Min (y =>y.Value.Distance))

.First ().Key;

// Находим все непосещенные соседние вершины для текущей вершины

List

neighbors = nodes[current]. Links. Where (x => !info[x.Node]. Visited).ToList ();

// Рассматриваем новую длину пути для каждой соседней вершины

foreach (Link link in neighbors)

{

double distance = info[current]. Distance + link. Distance;

if (info[link.Node]. Distance > distance)

info[link.Node]. Distance = distance;

}

// Отмечаем текущую вершину как посещенная.

info[current]. Visited = true;

}

return info[end]. Distance;

}

}

static void Main ()

{

int count = 10;

string[] names = { «1», «2», «3», «4», «5», «6», «7», «8», «9», «10» };

Graphgraph = newGraph ();

// Заполнениеграфавершинами.

for (inti = 0; i< count; ++i)

graph.AddNode (names[i]);

// Создание у вершин связей.

// Последнее значение говорит о том, что эта связь двунаправленная.

graph.AddLinkToNode («1», «2», 7, false);

graph.AddLinkToNode («1», «3», 9, false);

graph.AddLinkToNode («1», «6», 14, false);

graph.AddLinkToNode («2», «3», 10, false);

graph.AddLinkToNode («2», «4», 15, false);

graph.AddLinkToNode («3», «4», 11, false);

graph.AddLinkToNode («3», «6», 2, false);

graph.AddLinkToNode («4», «5», 6, false);

graph.AddLinkToNode («5», «6», 9, false);

graph.AddLinkToNode («6», «7», 11, false);

graph.AddLinkToNode («7», «9», 9, false);

graph.AddLinkToNode («8», «4», 4, false);

graph.AddLinkToNode («8», «5», 6, false);

graph.AddLinkToNode («9», «5», 14, false);

graph.AddLinkToNode («9», «6», 16, false);

graph.AddLinkToNode («9», «10», 15, false);

graph.AddLinkToNode («10», «5», 18, false);

Console.Write («Маршрутиз 1 в 2 = «);

Console.WriteLine (graph.FindShortestDistance («1», «2»));

Console.Write («Маршрутиз 1 в 3 = «);

Console.WriteLine (graph.FindShortestDistance («1», «3»));

Console.Write («Маршрутиз 1 в 4 = «);

Console.WriteLine (graph.FindShortestDistance («1», «4»));

Console.Write («Маршрутиз 1 в 5 = «);

Console.WriteLine (graph.FindShortestDistance («1», «5»));

Console.Write («Маршрутиз 1 в 6 = «);

Console.WriteLine (graph.FindShortestDistance («1», «6»));

Console.Write («Маршрутиз 1 в 7 = «);

Console.WriteLine (graph.FindShortestDistance («1», «7»));

Console.Write («Маршрутиз 1 в 8 = «);

Console.WriteLine (graph.FindShortestDistance («1», «8»));

Console.Write («Маршрутиз 1 в 9 = «);

Console.WriteLine (graph.FindShortestDistance («1», «9»));

Console.Write («Маршрутиз 1 в 10 = «);

Console.WriteLine (graph.FindShortestDistance («1», «10»));

Console.ReadKey ();

}

}

}

3.1.1 Таблица кратчайших путей и маршрутов Маршрут из 1 в 2 = 7

Маршрут из 1 в 3 = 9

Маршрут из 1 в 4 = 20

Маршрут из 1 в 5 = 20

Маршрут из 1 в 6 = 11

Маршрут из 1 в 7 = 22

Маршрут из 1 в 8 = 24

Маршрут из 1 в 9 = 27

Маршрут из 1 в 10 = 38

Рис. 26. Граф. Пример сети для алгоритма Дейкстры.

3.2 Разработка алгоритма маршрутизации Флойда Рис. 27. Блок схема алгоритма Флойда.

Алгоритма Флойда реализован на языке программирования C#.

using System;

namespaceАлгоритм_Флойда

{

class Program

{

static void Main ()

{

int[,] array = new int[6, 6]

{ // 1 2 3 4 5 6

/*1*/{0, 2, 9999, 3, 6, 9999},

/*2*/{9999, 0, 4, 7, 9999, 4 },

/*3*/{3, 9, 0, 5, 9999, 2 },

/*4*/{9999, 6, 9999, 0, 2, 9999},

/*5*/{7, 9999, 2, 4, 0, 7 },

/*6*/{5, 2, 9999, 9999, 2, 0 }

};

inti, j, k;

for (i= 0; i< 6; i++)

for (j = 0; j < 6; j++)

for (k = 0; k < 6; k++)

if (array[i, k] > array[i, j] + array[j, k])

array[i, k] = array[i, j] + array[j, k];

// Вывод измененной матрицы смежности

Console.WriteLine («Алгоритм Флойда: n»);

for (i = 0; i< 6; i++)

{

for (j = 0; j < 6; j++)

Console.Write (array[i, j] + ««);

Console.WriteLine ();

} Console. ReadLine ();

}}}

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

Рис. 28. Граф. Пример сети для алгоритма Флойда.

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

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

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

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

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

Заключение

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

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

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

алгоритм маршрутизация сеть граф

1. Столлингс В. Современные компьютерные сети. — 2003

2. Автоматические системы коммутации: Учебник для вузов / Иванова О. П., Копп М. Ф., Кохонова З. С., Метельский Г. Б.; Под ред. О. Н Ивановой 2-е изд., доп. и перераб. М.: Связь, 1978. — 624с., ил.

3. Семенов Ю. А. Протоколы и ресурсы Internet. Радио и связь, 1996 г.

4. Владимир Плешаков, CISCO Internetworking Technology Overview.

5. Электронная энциклопедия Wikipedia.