Системы и сети передачи данных на железнодорожном транспорте

Автор работы: Пользователь скрыл имя, 28 Мая 2013 в 17:46, курсовая работа

Краткое описание

Компьютерные сети, как правило, представляются в виде графов, при этом коммутаторы и маршрутизаторы сетей являются узлами графа, а линии связи представляют собой р алгоритм Беллмана- Форда),
ебра графа. Для объединенной сети, такой как Интернет или интранет, представление ее в виде ориентированного графа также является приемлемым. В этом случае каждой вершине соответствует маршрутизатор.

Содержание

1. Алгоритмы поиска кратчайшего пути…………………………..3
1.1. Исходные данные………………………………………………….…....5
1.2. Алгоритм Дейкстры……………………………………………..…….6
1.3. Алгоритм Беллмана-Форда…………………………………………10
1.4. Расчет пути с минимальным количеством переходов…...……13
1.5. Выводы………………….………………………………………………..14
2. Маршрутизация……………………………………………………15
2.1 Основы маршрутизации……………………….…………………………15
2.2 Характеристика протокола RIP…………..……….…………………18
2.3 Схема сети…………………………………………..………………………20
2.4 Построение маршрутных таблиц………………..……………………20
2.5. Адаптация к изменениям состояния сети……………………………26
2.5.1. Проблемы адаптации RIP………………………………………………26
2.5.2 Отключение тупиковой сети…………………………………………...27
2.5.3 Технологии ускорения сходимости……………………………………..28
Заключение………………………………………………………………32
Список использованной литературы…………………………………33

Скачать в ZIP архиве (307.72 Кб) Сколько стоит заказать работу?
Вложенные файлы: 1 файл

курсовой сспд.docx

— 318.51 Кб (Скачать файл)

Таблица 1 Алгоритм выбора маршрута с минимальной стоимостью по Дейкстре

 

Покажем по этапам применение алгоритма к графу:

 

 

 

T={1}                                                                    T={1,5}

T={1,5,4}                                                       T={1,5,4,2}

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

Рисунок 1.2 Применение алгоритма Дейкстры

 

 

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

 

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

  • 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

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

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

   В табл. 2 показан результат применения этого алгоритма к графу, представленному на рис. 8, в котором в качестве вершины s выбираем: вершину V1. На каждом шаге алгоритм находит путь с минимальной стоимостью, максимальное число ретрансляционных участков в котором равно h. После последней итерации алгоритм находит путь с минимальной стоимостью к каждой вершине, а также вычисляется стоимость этого пути. Та же процедура может быть применена к вершине V2 и т. д. Результаты работы алгоритмов Дейкстры и Беллмана - Форда совпадают.

 

h

L(2)

Путь

L(3)

Путь

L(4)

Путь

L(5)

Путь

L(6)

Путь

0

  ∞

    -

 ∞

-

 ∞

-

 ∞

-

 ∞

-

1

 ∞

 

-

7

 

1-3

2

1-4

1

1-5

 ∞

-

2

6

8

1-5-2

1-4=2

7

8

1-3

1-4-3

2

14

1-4

1-3-4

1

 

1-5

 

 

8

11

1-5-6

1-3-6


 

Таблица 2 Алгоритм выбора маршрута с минимальной стоимостью по Беллману-Форду

                     h=1                                                        h=2

 

Рисунок 1.3 Применение алгоритма Беллмана-Форда.

 

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

Рисунок.1.4 Неориентированный, невзвешенный граф

 

Исходная  матрица:

      V1 V2 V3 V4 V5 V6

V1  0   0    1    1    1    0

V2  0   0    0    1    1    0

V3  1   0    0    1    0    1

V4  1   1    1    0    0    0

V5  1   1    0    0    0    1

V6  0   0    1    0    1    0

 

 

Произведем поиск кратчайшего  пути по алгоритму Дейкстры.

 

 

 

№

     T

L(2)

Путь

L(3)

Путь

L(4)

Путь

L(5)

Путь

L(6)

Путь

1

{1}

∞

-

1

1-3

1

1-4

1

1-5

∞

-

2

{1;3}

∞

-

1

1-3

1

2

1-4

1-3-4

1

1-5

∞

2

-

1-3-6

3

{1;3;4}

∞

2

-

1-4-2

1

2

1-3

1-4-3

1

2

1-4

1-3-4

1

1-5

2

1-3-6

4

{1;3;4;5}

2

2

1-4-2

1-5-2

1

1-3

1

1-4

1

1-5

2

2

1-3-6

1-5-6

5

{1;3;4;5;2}

2

3

1-4-2

1-3-4-2

1

4

1-3

1-5-2-4-3

2

3

1-3-4

1-5-2-4

1

 

3

1-5

 

1-4-2-5

2

1-3-6

6

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

2

 

1-4-2

1

1-3

1

1-4

1

1-5

2

1-3-6


 

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

T={1}                                                                                        T={1;3}

T={1;3;4}                                                                                     T={1;3;4;5}

T={1;3;4;5;2}                                                                               T={1;3;4;5;2;6}

Рисунок 1.4.1 Применение алгоритма Дейкстры для неориентированного невзвешенного графа.

 

1.5 Выводы

 

   В  итоге оба алгоритма поиска  кратчайшего пути привели нас  к одинаковому результату. Но  по алгоритму Беллмана-Форда результата  мы достигли быстрее.

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

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

 

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

 

 

2.1.Основы маршрутизации

 

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

Алгоритмы маршрутизации включают процедуры:

- измерение и оценивание параметров  сети;

- принятие решения о рассылке  служебной информации;

- расчет таблиц маршрутизации  (ТМ);

- реализация принятых маршрутных  решений.

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

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

   Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно.

Алгоритм Беллмана-Форда относится  к алгоритмам DVA (Distance Vector Algorithms). В DVA рельеф Ra(d) - это оценка кратчайшего пути от узла a к узлу d. Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В ТМ узла а каждому из остальных узлов отводится одна строка со следующей информацией:

- узел назначения;

- длина кратчайшего пути;

- номер N ближайшего узла, соответствующего кратчайшему пути;

- список рельефов от а к d через каждый из смежных узлов.

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

   Находит применение еще один алгоритм маршрутизации - IGRP (Interior Gateway Routine Protocol), разработанный фирмой Cisco. Он аналогичен алгоритму RIP, но развивает его в направлениях: а) возможны различные метрики (целевые функции); б) трафик может распределяться по нескольким каналам с близкими значениями метрики.

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

 

2.2.Характеристика протокола  RIP

 

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

   Вектором  расстояний называется набор пар ("Сеть", "Расстояние до этой сети"), извлеченный из таблицы маршрутов. Расстояние до сети, к которой маршрутизатор подключен непосредственно, примем равным 1.

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

   Протокол RIP (Routing Information Protocol) описан в документе RFC 1058. Он представляет собой один из старейших протоколов обмена маршрутной информацией между маршрутизаторами в сети, построенной на базе протокола IP. Помимо версии протокола RIP для сетей IP существует также версия этого протокола для сетей IPX/SPX компании Novell. Сообщения об обновлении таблиц маршрутизации в этом протоколе касаются только устройств, которые разделяют общую сеть. Эти устройства называются соседями. В этом протоколе все сети имеют номера. При этом способ образования номера зависит от используемого в сети протокола сетевого уровня. А все маршрутизаторы имеют свои идентификаторы.

Информация о работе Системы и сети передачи данных на железнодорожном транспорте