Исследование процессов маршрутизации

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Федеральное агентство железнодорожного транспорта

Уральский государственный университет путей сообщения

Кафедра Автоматики, телемеханики и связи на ж. д. транспорте

Курсовой проект

по дисциплине: «Передача дискретной информации»

на тему: «Исследование процессов маршрутизации»

Екатеринбург

2012

Содержание

1. Алгоритм поиска кратчайшего пути

2. Исходные данные

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

4. Алгоритм Белмана-Форда

5. Компоненты маршрутизации

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

7. Протоколы обмена маршрутной информацией

8. Протокол RIP

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

1. Алгоритмы поиска кратчайшего пути

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

Граф состоит из объектов двух типов: вершин (vertices) или узлов (nodes) и ребер (edges) или связей (links), при этом каждое ребро графа определяется как неупорядоченная пара вершин. При изображении графов вершины представляются точками или кружками, а ребра -- линиями, соединяющими вершины. Величина графа характеризуется количеством вершин |V|, называемым порядком (order) графа, а число ребер называется размером (size) графа. Граф также часто представляется в виде матрицы смежности (adjacency matrix). Вершины нумеруются произвольным образом от 1 до |V|.

Два ребра, инцидентные одной и той же паре вершин, называются параллельными (parallel). Ребро, инцидентное всего одной вершине, называется петлей (loop). Граф, в котором отсутствуют петли и параллельные ребра, называется простым графом (simple graph).

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

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

2. Исходные данные

Вариант № 122

Рисунок 2 — Матрица смежности

Рисунок 2.1 — Взвешенный ориентировочный граф

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

Алгоритм находит кратчайшие пути от данной вершины-источника до всех остальных вершин, перебирая пути в порядке увеличения их длин. Работа алгоритма проходит поэтапно. К k-му шагу алгоритм находит k кратчайших (с наименьшей стоимостью) путей к k вершинам, ближайшим к вершине-источнику. Эти вершины образуют множество Т. На шаге (k + 1) к множеству Т добавляется вершина, ближайшая к вершине-источнику среди вершин, не входящих во множество Т. При добавлении каждой новой вершины к множеству Т определяется путь к ней от источника. Дерево -- связующее дерево для вершин, принадлежащих множеству Т, включая ребра, входящие в пути с наименьшей стоимостью от вершины s до каждой вершины множества Т. Введем обозначения: N — множество вершин сети; s — вершина-источник; Т — множество вершин, уже обработанных алгоритмом; L (n) — минимальная стоимость пути от вершины s до вершины п, известного на данный момент алгоритму (по завершении работы алгоритма это минимальная стоимость пути от вершины s до вершины п). Алгоритм состоит из трех шагов. Шаги 2 и 3 повторяются до тех пор, пока множество T не совпадет с множеством N. Это значит, что шаги 2 и 3 повторяются, пока для всех вершин сети не будут найдены окончательные пути.

1. Инициализация.

Т = Дерево = {s}, то есть множество исследованных вершин состоит пока что только из вершины-источника. Стоимости начальных путей к соседним вершинам представляют собой просто стоимости линий связи.

2. Получить следующую вершину.

Найти следующую вершину, не принадлежащую множеству T и имеющую путь от вершины s с минимальной стоимостью, и включить эту вершину во множество T и в Дерево. Кроме того, к дереву добавляется ребро, инцидентное этой вершине и вершине множества T, входящей в путь с минимальной стоимостью. То есть находим вершину x Т такую, что

L (x) = min L (j)

jT

Добавить вершину х к множеству T и к дереву; добавить к дереву ребро, инцидентное вершине х, составляющее компонент пути L (x) с минимальной стоимостью — последний ретрансляционный участок пути.

3. Обновить путь с минимальной стоимостью.

L (n) = min[L (n), L (x) + w (x, п)] для всех пТ.

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

Таблица 1 — Результаты работы алгоритма Дейкстры для заданного графа

Итерация

Т

L (2)

Путь

L (3)

Путь

L (4)

Путь

L (5)

Путь

L (6)

Путь

1

{1}

?

1−2

?

-

?

-

1

1−5

1

1−6

2

{1,5}

?

1−2

?

2

-

1−5-3

?

2

-

1−5-4

?

1−5

1

1−6

3

{1,5,6}

3

1−2

2

3

1−5-3

1−6-3

2

1−5-4

?

1−5

1

1−6

4

{1,5,6,3}

3

8

1−2

1−5-3−2

2

1−5-3

2

1−5-4

?

1−5

1

8

1−6

1−5-3−6

5

{1,5,6,3,4}

3

8

1−2

1−5-4−2

2

1−5-3

2

1−5-4

1

1−5

1

1−6

6

{1,5,6,3,4,2}

3

1−2

2

10

1−5-3

1−2-3

2

10

1−5-4

1−2-4

1

1−5

1

1−6

ИТОГ

3

1−2

2

1−5-3

2

1−5-4

1

1−5

1

1−6

Рисунок 3 — Применение алгоритма Дейкстры к графу, представленному на рис. 2. 1

4. Алгоритм Беллмана-Форда

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

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

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

s -вершина-источник;

w (i, j) — стоимость линии от вершины i до вершины j, причем w (i, j) = 0 или w (i, j) =, если две вершины не соединены напрямую, и w (i, j) => 0, если две вершины соединены напрямую;

h — максимальное количество ребер в пути на текущем шаге алгоритма;

Lh (n) — минимальная стоимость пути от вершины s до вершины п при условии, что этот путь состоит не более чем из h ребер.

Алгоритм состоит из двух шагов. Шаг 2 повторяется до тех пор, пока стоимости путей не перестанут изменяться.

1. Инициализация:

L0(n) = для всех п s,

Lh (s) = 0 для всех h.

2. Обновление. Для каждого последовательного h >= 0 и для каждого пs вычислить

Lh+1(n) — min[Lh (j) + w (j, n)].

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

При h = К для каждой вершины-получателя п алгоритм сравнивает потенциальный путь от вершины s до вершины п длиной К + 1 с путем, существовавшим к концу предыдущей итерации. Если предыдущий более короткий путь обладает меньшей стоимостью, то он сохраняется. В противном случае сохраняется новый путь от вершины s до вершины п длиной К + 1. Этот путь состоит из пути длиной К от вершины К до некоей вершины j и прямого участка от вершины j до вершины п. В этом случае используемый путь от вершины s до вершины j представляет собой путь, состоящий из К ретрансляционных участков, найденный на предыдущей итерации. По завершении работы алгоритма вычисляется связующее дерево графа.

В таблице 2 и на рисунке 4 показан результат применения этого алгоритма к графу, представленному на рисунке 2.1.

Таблица 2 — Результаты работы алгоритма Беллмана-Форда для заданного графа

h

Т

L (2)

Путь

L (3)

Путь

L (4)

Путь

L (5)

Путь

L (6)

Путь

1

1

?

1−2

?

-

?

-

1

1−5

1

1−6

2

1−2

1−5

1−6

?

1−2

?

10

2

3

-

1−2-3

1−5-3

1−6-3

?

10

2

-

1−2-4

1−5-4

?

1−5

1

1−6

3

1−5-3

1−5-4

3

8

8

1−2

1−5-3−2

1−5-4−2

2

1−5-3

2

1−5-4

?

1−5

1

8

1−6

1−5-3−6

ИТОГ

3

1−2

2

1−5-3

2

1−5-4

1

1−5

1

1−6

Рисунок 4 — Применение алгоритма Беллмана-Форда к графу, приведенному на рис. 2. 1

5. Компоненты маршрутизации

Маршрутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. При этом, как правило, на пути встречается, по крайней мере, один узел.

Маршрутизация включает в себя два основных компонента: определение оптимальных трактов маршрутизации и транспортировка информационных групп (обычно называемых пакетами) через объединенную сеть. Коммутацией — это транспортировка информационных групп через объединенную сеть.

Цель маршрутизации — доставка пакетов по назначению с максимальной эффективностью. Чаще всего эффективность выражена взвешенной суммой времен доставки сообщений при ограничении снизу на вероятность доставки. Маршрутизация сводится к определению направлений движения пакетов в маршрутизаторах.

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

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

Цели разработки алгоритмов маршрутизации

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

1. Оптимальность

2. Простота и низкие непроизводительные затраты

3. Живучесть и стабильность

4. Быстрая сходимость

5. Гибкость

1. Оптимальность

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

2. Простота и низкие непроизводительные затраты

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

3. Живучесть и стабильность

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

4. Быстрая сходимость

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

К типам алгоритмов маршрутизации относят:

1. статический или динамический;

2. одномаршрутный или многомаршрутный;

3. одноуровневый или иерархический;

4. с интеллектом в главной вычислительной машине или в роутере;

5. внутридоменный и междоменный;

6. алгоритм состояния канала или вектора расстояний.

Рассмотрим подробнее каждый тип алгоритма маршрутизации.

1. Статические или динамические алгоритмы

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

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

2. Одномаршрутные или многомаршрутные алгоритмы

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

3. Одноуровневые или иерархические алгоритмы

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

4. Алгоритмы с интеллектом в главной вычислительной машине или в роутере

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

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

5. Внутридоменные или междоменные алгоритмы

Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие — как в пределах доменов, так и между ними.

6. Алгоритмы состояния канала или вектора расстояния

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

К основным показателям алгоритмов (метрики) относят:

· длина маршрута;

· надежность;

· задержка;

· ширина полосы пропускания;

· нагрузка;

· стоимость связи.

Длина маршрута

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

Надежность

Надежность, в контексте алгоритмов маршрутизации, относится к надежности каждого канала сети.

Задержка

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

Полоса пропускания

Полоса пропускания является оценкой максимально достижимой пропускной способности канала.

7. Протокол обмена маршрутной информацией

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

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

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

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

Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP.

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

Протоколом, основанным на алгоритме состояния связей, в стеке TCP/IP является протокол OSPF.

8. Протокол RIP

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

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

Реализация протокола RIP

Существуют две версии протокола RIP: RIP-1 и RIP-2. Версия 2 имеет некоторые усовершенствования, как то: возможность маршрутизации сетей по модели CIDR (кроме адреса сети передается и маска), поддержка мультикастинга, возможность использования аутентификации RIP-сообщений и др.

Типы и формат сообщений

В протоколе RIP имеются два типа сообщений, которыми обмениваются маршрутизаторы:

· ответ (response) — рассылка вектора расстояний;

· запрос (request) — маршрутизатор (например, после своей загрузки) запрашивает у соседей их маршрутные таблицы или данные об определенном маршруте.

Рассмотрим работу протокола RIP

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

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

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

· некорректный элемент игнорируется;

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

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

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

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

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

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

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

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

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

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

2. RFC 1058. Routing Information Protocol

ПоказатьСвернуть
Заполнить форму текущей работой