Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

Вариант 547 0 0 0 6 0 4 0 0 7 2 2 0 0 1 0 5 0 5 1 1 5 0 0 0 0 5 0 0 0 6 8 0 1 0 8 0 Рисунок 1 ~ Взвешенный ориентированный граф п

Работа добавлена на сайт samzan.net:

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 2.6.2024

Содержание

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

1.1. Исходные данные
1.2. Алгоритм Дейкстры
1.3. Алгоритм Беллмана-Форда
1.4. Расчет пути с минимальным количеством переходов
1.5. Выводы

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

2.1. Основы маршрутизации
2.2. Протокол RIP
2.3. Схема сети
2.4. Построение маршрутных таблиц
2.5. Адаптация к изменениям состояния сети
2.5.1. Проблемы адаптации RIP
2.5.2. Отключение тупиковой сети

2.6. Технологии ускорения сходимости

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

1.1 Исходные данные

Вариант № 547
0 0 0 6 0 4
0 0 7 2 2 0
0 1 0 5 0 5
1 1 5 0 0 0
0 5 0 0 0 6
8 0 1 0 8 0

Рисунок 1 – Взвешенный ориентированный граф, построенный по матрице смежности

1.2 Алгоритм дейкстры

Алгоритм Дейкстры может быть сформулирован следующим образом. Алгоритм находит кратчайшие пути от данной вершины-источника до всех остальных вершин, перебирая пути в порядке увеличения их длин. Работа алгоритма проходит поэтапно. К k-му шагу алгоритм находит k кратчайших (с наименьшей стоимостью) путей к k вершинам, ближайшим к вершине-источнику. Эти вершины образуют множество Т. На шаге (k + 1) к множеству Т добавляется вершина, ближайшая к вершине-источнику среди вершин, не входящих во множество Т. При добавлении каждой новой вершины к множеству Т определяется путь к ней от источника. Формально этот алгоритм может быть определен следующим образом. Введем обозначения:

N — множество вершин сети;
s — вершина-источник;
Т— множество вершин, уже обработанных алгоритмом;
Дерево — связующее дерево для вершин, принадлежащих множеству Т, включая ребра, входящие в пути с наименьшей стоимостью от вершины s до каждой вершины множества Т;
w(i,j) — стоимость линии от вершины i до вершины j, причем w(i,j) = 0 или w(i,j) = ∞, если две вершины не соединены напрямую, и w(i,j) => 0, если две вершины соединены напрямую;
L(n) — минимальная стоимость пути от вершины s до вершины n, известного на данный момент алгоритму (по завершении работы алгоритма это минимальная стоимость пути от вершины s до вершины n).

Алгоритм состоит из трех шагов. Шаги 2 и 3 повторяются до тех пор, пока множество T не совпадет с множеством N. Это значит, что шаги 2 и 3 повторяются, пока для всех вершин сети не будут найдены окончательные пути.

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

Т = Дерево = {s},

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

L(n) = w(s, n) для n ≠ s,

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

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

L(x) = min L(j)

j∉T

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

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

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

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

Алгоритм завершает работу, когда все вершины добавлены к множеству Т.

Таким образом, для работы алгоритма требуется |V| итераций. К моменту окончания работы алгоритма значение L(x), поставленное в соответствие каждой вершине x представляет собой минимальную стоимость (длину) пути от вершины s до вершины х. Кроме того, Дерево представляет собой связующее дерево исходного ориентированного графа, определяющее пути с минимальной стоимостью от вершины s до всех остальных вершин.

На каждой итерации при выполнении шагов 2 и 3 к множеству T добавляется одна новая вершина, а также находится путь с минимальной стоимостью вершины s до этой вершины. Другими словами, на каждой итерации к множеству добавляется вершина х, а значение L(x) на этот момент времени представляет собой минимальную стоимость пути от вершины s до вершины х. Более того, путь с минимальной стоимостью определяется уникальным путем от вершины s, вершины х во множестве Т. Этот путь проходит только по вершинам, принадлежащим множеству Т. Чтобы понять это, рассмотрим следующую цепочку рассуждений. Вершина х, добавляемая на первой итерации, должна быть смежной с вершиной и не должно существовать другого пути к вершине х с меньшей стоимостью. Если вершина х не является смежной с вершиной s, тогда должна существовать другая вершина, смежная с вершиной s, представляющая собой первый транзитный участок пути с минимальной стоимостью к вершине х. В этом случае при выборе вершины, добавляемой к множеству Т, предпочтение будет отдано этой вершине, а не вершине х. Если вершина х является смежной с вершиной s, но путь s — х не является путем с наименьшей стоимостью от вершины s до вершины х, то это значит, что существует другая смежная с вершиной s вершина у, находящаяся на пути с минимальной стоимостью, и при выборе добавляемой к множеству Т вершины предпочтение будет отдано вершине у, а не вершине х. После выполнения k итераций во множество T войдут k вершин и будет найден путь с минимальной стоимостью от вершины s до каждой из этих вершин. Теперь рассмотрим все возможные пути от вершины s до вершин, не входящих в множество Т. Среди этих путей существу один путь с минимальной стоимостью, проходящий исключительно по вершинам, принадлежащим множеству Т, заканчивающийся линией, непосредственно связывающей некую вершину множества Т с вершиной, не принадлежащей множеству Т. Эта вершина добавляется к множеству Т, а соответствующий путь считается путем с наименьшей стоимостью к данной вершине.

Ниже показан результат применения данного алгоритма к графу, представленному в исходных данных. В данном случае в качестве вершины s выбирается вершина V1. Ребра, выделенные жирными линиями, показывают связующее дерево для этого графа. Значения в каждой окружности представляют собой текущие оценки величины L(x) для каждой вершины х. Вершина затеняется при добавлении к множеству T.

Таблица 1 – Алгоритм Дейкстры

Итерация	Т	L2	Путь	L3	Путь	L4	Путь	L5	Путь	L6	Путь
1	{1}	∞	-	∞	-	6	1-4	∞	-	4	1-6
2	{1, 6}	∞	-	∞	-	6	1-4	∞	-	4	1-6
∞	-	5	1-6-3	6	1-4	12	1-6-5	4	1-6
3	{1, 6, 3}	∞	-	5	1-6-3	6	1-4	12	1-6-5	4	1-6
6	1-6-3-2	5	1-6-3	10	1-6-3-4	12	1-6-5	4	1-6
4	{1, 6, 3, 4}	6	1-6-3-2	5	1-6-3	6	1-4	12	1-6-5	4	1-6
7	1-4-2	5	1-6-3	6	1-4	12	1-6-5	4	1-6
5	{1, 6, 3, 4, 2}	6	1-6-3-2	5	1-6-3	6	1-4	12	1-6-5	4	1-6
6	1-6-3-2	5	1-6-3	6	1-4	8	1-6-3-2-5	4	1-6
6	{1, 6, 3, 4, 2, 5}	6	1-6-3-2	5	1-6-3	6	1-4	8	1-6-3-2-5	4	1-6

Рисунок 2 - Связующие дерево на 1 итерации

Рисунок 3- Связующие дерево на 2 итерации

Рисунок 4- Связующие дерево на 3 итерации

Рисунок 5- Связующие дерево на 4 итерации

Рисунок 6 - Связующие дерево на 5 итерации

Рисунок 7 - Связующие дерево на 6 итерации

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

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

s — вершина-источник;
w(i,j) — стоимость линии от вершины i до вершины j, причем w(i, j) = 0 или w(i,j) = ∞, если две вершины не соединены напрямую, и w(i,j) => 0, если две вершины соединены напрямую;
h — максимальное количество ребер в пути на текущем шаге алгоритма;
Lh(n) — минимальная стоимость пути от вершины s до вершины n при условии, что этот путь состоит не более чем из h ребер.

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

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

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

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

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

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

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

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

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

Таблица 2 – Алгоритм Беллмана-Форда

h	L2	Путь	L3	Путь	L4	Путь	L5	Путь	L6	Путь
0	∞	-	∞	-	∞	-	∞	-	∞	-
1	∞	-	∞	-	6	1-4	∞	-	4	1-6
2	∞	-	∞	-	6	1-4	∞	-	4	1-6
7	1-4-2	11	1-4-3							1-4
		5	1-6-3			12	1-6-5			1-6
3	7	1-4-2	5	1-6-3	6	1-4	12	1-6-5	4	1-6
						9	1-4-2-5			1-4-2
6	1-6-3-2			10	1-6-3-4					1-6-3
17	1-6-5-2									1-6-5
4	6	1-6-3-2	5	1-6-3	6	1-4	9	1-4-2-5	4	1-6
				8	1-6-3-2-4	8	1-6-3-2-5			1-6-3-2
								15	1-4-2-5-6	1-4-2-5
5	6	1-6-3-2	5	1-6-3	6	1-4	8	1-6-3-2-5	4	1-6

Рисунок 8 - Связующее дерево при шаге h=1

Рисунок 9 - Связующее дерево при шаге h=2

Рисунок 10 - Связующее дерево при шаге h=3

Рисунок 11 - Связующее дерево при шаге h=4

Рисунок 12 - Связующее дерево при шаге h=5

1.4 Расчёт пути с минимальным количеством переходов

Неориентированный невзвешенный граф, сформированный из исходного графа изображен на рисунке

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

Матрица смежности для неориентированного невзвешенного графа:

Ниже показан результат применения алгоритма Беллмана-Форда к графу, представленному неориетированного невзвешенного графа, сформированного из исходного, в котором в качестве вершины s выбрана вершина V1.

Таблица 3. Расчет пути с минимальным количеством переходов

h	L2	Путь	L3	Путь	L4	Путь	L5	Путь	L6	Путь
0	∞	-	∞	-	∞	-	∞	-	∞	-
1	∞	-	∞	-	1	1-4	∞	-	1	1-6
2	∞	-	∞	-	1	1-4	∞	-	1	1-6
2	1-4-2	2	1-4-3							1-4
		2	1-6-3			2	1-6-5			1-6
3	2	1-4-2	2	1-4-3	1	1-4	2	1-6-5	1	1-6
		3	1-4-2-3			3	1-4-2-5			1-4-2
3	1-4-3-2							3	1-4-3-6	1-4-3
3	1-6-5-2									1-6-5
4	2	1-4-2	2	1-4-3	1	1-4	2	1-6-5	1	1-6

Рисунок 14 - связующее дерево при шаге h=1

Рисунок 15 - связующее дерево при шаге h=1

Рисунок 16 - связующее дерево при шаге h=1

Рисунок 17 - связующее дерево при шаге h=1

1.5 Выводы по главе 1

1) По матрице смежности, полученной из исходных данных построили взвешенный ориентированный граф.

2) Для исходного графа нашли кратчайшие пути от вершины-источника до всех остальных вершин, применив алгоритм Дейкстры и алгоритм Беллмана-Форда.

3) Результат работы алгоритмов изображен в рисунках и таблицах.

4) Результаты работы обоих алгоритмов совпадают.

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

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

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

В общедоступном значении слова маршрутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. При этом, как правило, на пути встречается по крайней мере один узел. Маршрутизация часто противопоставляется объединению сетей с помощью моста, которое, в популярном понимании этого способа, выполняет точно такие же функции. Основное различие между ними заключается в том, что объединение с помощью моста имеет место на Уровне 2 эталонной модели ISO, в то время как маршрутизация встречается на Уровне 3.

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

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

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

Оптимальность
Простота и низкие непроизводительные затраты
Живучесть и стабильность
Быстрая сходимость
Гибкость

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

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

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

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

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

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

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

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

Типы алгоритмов

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

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

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

Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельства сети в масштабе реального времени. Они выполняют это путем анализа поступающих сообщений об обновлении маршрутизации. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации. Такие сообщения пронизывают сеть, стимулируют роутеры заново прогонять свои алгоритмы и соответствующим образом изменять таблицы маршрутизации. Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это уместно. Например, можно разработать "роутер последнего обращения" (т.е. роутер, в который отсылаются все неотправленные по определенному маршруту пакеты). Такой роутер выполняет роль хранилища неотправленных пакетов, гарантируя, что все сообщения будут хотя бы определенным образом обработаны.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Показатели алгоритмов (метрики)

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

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

Надежность

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

Задержка

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

Ширина полосы пропускания

Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал Ethernet 10 Mbps предпочтителен любой арендованной линии с полосой пропускания 64 Кбайт/сек. Хотя полоса пропускания является оценкой максимально достижимой пропускной способности канала, маршруты, проходящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие каналы.

Нагрузка
Стоимость связи

2.2 Протокол RIP

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

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

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

Протокол RIP построен с использованием алгоритма маршрутизации, известного как алгоритм длины вектора. Данный алгоритм получил свое название в результате его возможности вычислять наилучший маршрут в том случае, если в качестве информации, которой обмениваются маршрутизаторы, выступает список достижимых сетей и расстояния до них. Алгоритм основывается на предположении, что каждый маршрутизатор может вычислить маршрут и соответствующее расстояние до каждой сети с помощью выбора соседа, имеющего наикратчайший путь. Этот алгоритм хорошо работает в небольших сетях. В больших сетях он «засоряет» каналы связи широковещательным трафиком. Изменения в сетевой топологии могут быть обработаны по этому алгоритму не всегда корректно, так как маршрутизаторы не имеют точного представления о топологии связей в сети, а располагают только обобщенной информацией, полученной от соседей. Работа маршрутизатора с таким протоколом напоминает работу моста.

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

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

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

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

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

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

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

2.3. Схема сети

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

Рисунок 18. Схема сети

2.4. Построение маршрутных таблиц

В начальный момент маршрутизаторы знают только о своих непосредственно подключенных сетях. Рассылку начинает маршрутизатор R1.

Таблица 4. Маршрутная таблица в начальный момент времени

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	14	-	1
16	-	1
R2	23	-	1
24	-	1
25	-	1
R3	23	-	1
34	-	1
36	-	1
R4	14	-	1
24	-	1
34	-	1
40	-	1
R5	25	-	1
56	-	1
R6	16	-	1
36	-	1
56	-	1

Таблица 5. R1R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R4	14	-	1
24	-	1
34	-	1
40	-	1
14	R1	2
16	R1	2
R6	16	-	1
36	-	1
56	-	1
14	R1	2
16	R1	2

Таблица 6. R2R3, R4, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R3	23	-	1
34	-	1
36	-	1
23	R2	2
24	R2	2
25	R2	2
R4	14	-	1
24	-	1
34	-	1
40	-	1
16	R1	2
23	R2	2
24	R2	2
25	R2	2
R5	25	-	1
56	-	1
23	R2	2
24	R2	2
25	R2	2

Таблица 7. R3R2, R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	23	-	1
24	-	1
25	-	1
23	R3	2
34	R3	2
36	R3	2
24	R3	3
25	R3	3
R4	14	-	1
24	-	1
34	-	1
40	-	1
16	R1	2
23	R2	2
25	R2	2
23	R3	2
34	R3	2
36	R3	2
24	R3	3
25	R3	3
R6	16	-	1
36	-	1
56	-	1
14	R1	2
23	R3	2
34	R3	2
36	R3	2
24	R3	3
25	R3	3

Таблица 8. R4R1, R2, R3

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	14	-	1
16	-	1
14	R4	2
24	R4	2
34	R4	2
40	R4	2
16	R4	3
23	R4	3
25	R4	3
36	R4	3
R2	23	-	1
24	-	1
25	-	1
34	R3	2
36	R3	2
14	R4	2
24	R4	2
34	R4	2
40	R4	2
16	R4	3
23	R4	3
25	R4	3
36	R4	3
R3	23	-	1
34	-	1
36	-	1
24	R2	2
25	R2	2
14	R4	2
24	R4	2
34	R4	2
40	R4	2
16	R4	3
23	R4	3
25	R4	3
36	R4	3

Таблица 9. R5R2, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	23	-	1
24	-	1
25	-	1
34	R3	2
36	R3	2
14	R4	2
40	R4	2
16	R4	3
34	R4	3
25	R5	2
56	R5	2
23	R5	3
24	R5	3
R6	16	-	1
36	-	1
56	-	1
14	R1	2
23	R3	2
34	R3	2
24	R3	3
25	R3	3
25	R5	2
56	R5	2
23	R5	3
24	R5	3

Таблица 10. R6R1, R3, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	14	-	1
16	-	1
24	R4	2
34	R4	2
40	R4	2
23	R4	3
25	R4	3
36	R4	3
16	R6	2
36	R6	2
56	R6	2
14	R6	3
23	R6	3
34	R6	3
24	R6	4
25	R6	3
R3	23	-	1
34	-	1
36	-	1
24	R2	2
25	R2	2
14	R4	2
40	R4	2
16	R4	3
16	R6	2
36	R6	2
56	R6	2
14	R6	3
23	R6	3
34	R6	3
24	R6	4
25	R6	3
R5	25	-	1
56	-	1
23	R2	2
24	R2	2
16	R6	2
36	R6	2
56	R6	2
14	R6	3
23	R6	3
34	R6	3
24	R6	4
25	R6	3

Таблица 11. R1R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R4	14	-	1
24	-	1
34	-	1
40	-	1
16	R1	2
23	R2	2
25	R2	2
36	R3	2
14	R1	2
16	R1	2
24	R1	3
34	R1	3
40	R1	3
23	R1	4
25	R1	4
36	R1	3
56	R1	3
R6	16	-	1
36	-	1
56	-	1
14	R1	2
23	R3	2
34	R3	2
24	R3	3
25	R5	2
14	R1	2
16	R1	2
24	R1	3
34	R1	3
40	R1	3
23	R1	4
25	R1	4
36	R1	3
56	R1	3

Таблица 12. R2R3, R4, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R3	23	-	1
34	-	1
36	-	1
24	R2	2
25	R2	2
14	R4	2
40	R4	2
16	R6	2
56	R6	2
23	R2	2
24	R2	2
25	R2	2
34	R2	3
36	R2	3
14	R2	3
40	R2	3
16	R2	4
56	R2	3
R4	14	-	1
24	-	1
34	-	1
40	-	1
16	R1	2
23	R2	2
25	R2	2
36	R3	2
56	R1	3
23	R2	2
24	R2	2
25	R2	2
34	R2	3
36	R2	3
14	R2	3
40	R2	3
16	R2	4
56	R2	3
R5	25	-	1
56	-	1
23	R2	2
24	R2	2
16	R6	2
36	R6	2
14	R6	3
34	R6	3
23	R2	2
24	R2	2
25	R2	2
34	R2	3
36	R2	3
14	R2	3
40	R2	3
16	R2	4
56	R2	3

Таблица 13. R3R2, R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	23	-	1
24	-	1
25	-	1
34	R3	2
36	R3	2
14	R4	2
40	R4	2
16	R4	3
56	R5	2
23	R3	2
34	R3	2
36	R3	2
24	R3	3
25	R3	3
14	R3	3
40	R3	3
16	R3	3
56	R3	3
R4	14	-	1
24	-	1
34	-	1
40	-	1
16	R1	2
23	R2	2
25	R2	2
36	R3	2
56	R1	3
23	R3	2
34	R3	2
36	R3	2
24	R3	3
25	R3	3
14	R3	3
40	R3	3
16	R3	3
56	R3	3
R6	16	-	1
36	-	1
56	-	1
14	R1	2
23	R3	2
34	R3	2
24	R3	3
25	R5	2
40	R1	3
23	R3	2
34	R3	2
36	R3	2
24	R3	3
25	R3	3
14	R3	3
40	R3	3
16	R3	3
56	R3	3

Таблица 14. R4R1, R2, R3

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	14	-	1
16	-	1
24	R4	2
34	R4	2
40	R4	2
23	R4	3
25	R4	3
36	R4	2
56	R6	2
14	R4	2
24	R4	2
34	R4	2
40	R4	2
16	R4	3
23	R4	3
25	R4	3
36	R4	3
56	R4	4
R2	23	-	1
24	-	1
25	-	1
34	R3	2
36	R3	2
14	R4	2
40	R4	2
16	R4	3
56	R5	2
14	R4	2
24	R4	2
34	R4	2
40	R4	2
16	R4	3
23	R4	3
25	R4	3
36	R4	3
56	R4	4
R3	23	-	1
34	-	1
36	-	1
24	R2	2
25	R2	2
14	R4	2
40	R4	2
16	R6	2
56	R6	2
14	R4	2
24	R4	2
34	R4	2
40	R4	2
16	R4	3
23	R4	3
25	R4	3
36	R4	3
56	R4	4

Таблица 15. R5R2, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	23	-	1
24	-	1
25	-	1
34	R3	2
36	R3	2
14	R4	2
40	R4	2
16	R4	3
56	R5	2
25	R5	2
56	R5	2
23	R5	3
24	R5	3
16	R5	3
36	R5	3
14	R5	4
34	R5	4
40	R5	4
R6	16	-	1
36	-	1
56	-	1
14	R1	2
23	R3	2
34	R3	2
24	R3	3
25	R5	2
40	R1	3
25	R5	2
56	R5	2
23	R5	3
24	R5	3
16	R5	3
36	R5	3
14	R5	4
34	R5	4
40	R5	4

Таблица 16. R6R1, R3, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	14	-	1
16	-	1
24	R4	2
34	R4	2
40	R4	2
23	R4	3
25	R4	3
36	R4	2
56	R6	2
16	R6	2
36	R6	2
56	R6	2
14	R6	3
23	R6	3
34	R6	3
24	R6	4
25	R6	3
40	R6	4
R3	23	-	1
34	-	1
36	-	1
24	R2	2
25	R2	2
14	R4	2
40	R4	2
16	R6	2
56	R6	2
16	R6	2
36	R6	2
56	R6	2
14	R6	3
23	R6	3
34	R6	3
24	R6	4
25	R6	3
40	R6	4
R5	25	-	1
56	-	1
23	R2	2
24	R2	2
16	R6	2
36	R6	2
14	R6	3
34	R6	3
40	R2	3
16	R6	2
36	R6	2
56	R6	2
14	R6	3
23	R6	3
34	R6	3
24	R6	4
25	R6	3
40	R6	4

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

2.5 Адаптация к изменениям состояния сети

2.5.1 Проблема адаптации RIP

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

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

Если какая-либо сеть становится недостижимой, все соседние маршрутизаторы установят метрику для этой сети равной 16. В следующем цикле посылки сообщений об обновлении маршрутизаторы будут передавать этот маршрут каждому из своих соседей с числом переходов, равным 16. Маршрутизаторы, расположенные на расстоянии одного перехода от маршрутизаторов, соседних с вышедшим из строя устройством, будут иметь количество переходов, равное 17. Любые записи в таблице маршрутизации, имеющие число переходов более 16, уменьшат это число до 16. В таблицах маршрутизации всех маршрутизаторов в сети количество переходов в недостижимую сеть будет сводиться к значению 16.

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

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

Существует несколько последствий воздействия медленной сходимости на производительность:

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

Другая проблема, которая встречается при осуществлении маршрутизации, это петля маршрутизации. Рассмотрим суть данной проблемы на примере. На рисунке 19 показана логическая петля, образованная между двумя маршрутизаторами.

Рисунок 19 – Пример образования петель маршрутизации

Маршрутизатор М2 может достигнуть целевой сети через маршрутизатор Ml с количеством переходов, равным 1. Маршрутизатор МЗ получает эту информацию из периодических сообщений об обновлении от маршрутизатора М2, который говорит, что МЗ может достигнуть целевую сеть, используя маршрутизатор М2 с количеством переходов, равным 2. В следующем цикле посылки сообщений об обновлении маршрутизатор МЗ известит маршрутизатор М2 о его достижимости целевой сети с количеством переходов, равным 3. В результате маршрутизатор М2 будет иметь два маршрута в целевую сеть: первый маршрут с использованием маршрутизатора Ml и количеством переходов, равным 1, и второй -- с использованием маршрутизатора МЗ с количеством переходов, равным 3. Маршрутизатор М2 выберет маршрут с использованием маршрутизатора Ml, так как он имеет наименьшую метрику.

В случае если канал связи между маршрутизаторами Ml и М2 выйдет из строя, М2 не получит сообщение об обновлении в требуемый интервал времени и удалит из своей таблицы запись с маршрутом в целевую сеть, использующим маршрутизатор Ml. Однако маршрутизатор М2 имеет альтернативный маршрут в целевую сеть с использованием маршрутизатора МЗ и с количеством переходов, равным 3. Следовательно, МЗ будет передавать весь трафик обратно маршрутизатору М2, что вызовет создание петли маршрутизации. Обмен пакетами между маршрутизаторами будет продолжаться до тех пор, пока поле TTL в заголовке IP-дейтаграммы не достигнет нуля и она не будет удалена одним из маршрутизаторов.

2.5.2 Отключение тупиковой сети

Рассмотрим распространение информации об отключении тупиковой сети 40. Будем отслеживать только маршрут для тупиковой сети, т.к. остальные маршруты меняться не будут. Рассылку начинает маршрутизатор R4, к которому подключена тупиковая сеть, затем R5, R6, R1 и т.д.

Таблица 17. Маршрутная таблица перед отключением тупиковой сети

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R4	2
R2	40	R4	2
R3	40	R4	2
R4	40	-	16
R5	40	R2	3
R6	40	R1	3

Таблица 18. Маршрутная таблица R4R1, R2, R3

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R4	2
40	R4	16
R2	40	R4	2
40	R4	16
R3	40	R4	2
40	R4	16

Таблица 19. Маршрутная таблица R5R2, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	40	R4	16
40	R5	4
R6	40	R1	3
40	R5	4

Таблица 20. Маршрутная таблица R6R1, R3, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R4	16
40	R6	4
R3	40	R4	16
40	R6	4
R5	40	R2	3
40	R6	4

Таблица 21. Маршрутная таблица R1R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R4	40	-	16
40	R1	5
R6	40	R1	3
40	R1	5

Таблица 22. Маршрутная таблица R2R3, R4, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R3	40	R6	4
40	R2	5
R4	40	-	16
40	R2	5
R5	40	R2	3
40	R2	5

Таблица 23. Маршрутная таблица R3R2, R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	40	R5	4
40	R3	5
R4	40	-	16
40	R3	5
R6	40	R1	5
40	R3	5

Таблица 24. Маршрутная таблица R4R1, R2, R3

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R6	4
40	R4	16
R2	40	R5	4
40	R4	16
R3	40	R6	4
40	R4	16

Таблица 25. Маршрутная таблица R5R2, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	40	R5	4
40	R5	6
R6	40	R1	5
40	R5	6

Таблица 26. Маршрутная таблица R6R1, R3, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R6	4
40	R6	6
R3	40	R6	4
40	R6	6
R5	40	R2	5
40	R6	6

Таблица 27. Маршрутная таблица R1R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R4	40	-	16
40	R1	7
R6	40	R1	5
40	R1	7

Таблица 28. Маршрутная таблица R2R3, R4, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R3	40	R6	6
40	R2	7
R4	40	-	16
40	R2	7
R5	40	R2	5
40	R2	7

Таблица 29. Маршрутная таблица R3R2, R4, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	40	R5	6
40	R3	7
R4	40	-	16
40	R3	7
R6	40	R1	7
40	R3	7

Таблица 30. Маршрутная таблица R4R1, R2, R3

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R6	6
40	R4	16
R2	40	R5	6
40	R4	16
R3	40	R6	6
40	R4	16

Таблица 31. Маршрутная таблица R5R2, R6

Маршрутизатор	Сеть назначения	Переход	Дистанция
R2	40	R5	6
40	R5	8
R6	40	R1	7
40	R5	8

Таблица 32. Маршрутная таблица R6R1, R3, R5

Маршрутизатор	Сеть назначения	Переход	Дистанция
R1	40	R6	6
40	R6	8
R3	40	R6	6
40	R6	8
R5	40	R2	7
40	R6	8

Таким образом, сходимость не достигнута, образовалась петля маршрутизации.

2.6 Технологии ускорения сходимости

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

Расщепление горизонта (Split — Horizon);
Обратное исправление (Poison Reverse);
Мгновенное изменение (Triggered Update);
Временный отказ от приема информации (Hold – Down и Garbage — Collection).

Предотвращению возникновения петель маршрутизации может помочь технология Split – Horizon. Описанная проблема «обоюдного обмана» может быть решена с помощью определения направления посылки маршрутной информации. С использованием технологии Split – Horizon маршрутизатор не будет распространять информацию об определенном маршруте через порт, который явился источником данной информации. Другими словами, маршрутизатор не будет информировать о достижимости получателя своего соседа, от которого информация о маршруте к получателю была получена.

На рисунке 2.3 показано, каким образом технология Split — Horizon будет устранять образовавшуюся ранее петлю.

Рисунок 20 – Пример использования технологии расщепления горизонта

Процедура обмена сообщениями об обновлении маршрутной информации между маршрутизаторами остается такой же, как и на рисунке2.2, за исключением того, что маршрутизатор МЗ не будет посылать информацию о маршруте в целевую сеть маршрутизатору М2. В результате маршрутизатор М2 имеет только один маршрут в целевую сеть, и если произойдет обрыв канала связи между маршрутизаторами Ml и М2, то он удалит из своей таблицы маршрутизации маршрут в Целевую сеть, избегая таким образом образования петли.

Технология Poison Reverse решает те же задачи, что и технология Split — Horizon, однако немного другими способами. Маршрутизаторы будут распространять маршруты через порты, которые явились их источниками. Но эти маршруты будут идентифицироваться как недостижимые, что достигается установкой количества переходов равным 16 (рисунок 2.4).

Рисунок 21- Пример работы технологии Poison Reverse

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

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

Совместное использование технологий Split – Horizont и Poison Reverse необходимо для предотвращения образования петель маршрутизации, которые включают только два маршрутизатора. Однако могут существовать ситуации, когда три или более маршрутизатора включены в процесс «взаимного обмана». Например, какой-либо маршрутизатор Ml полагает, что он имеет маршрут через маршрутизатор М2, маршрутизатор М2 через МЗ, МЗ через М4, а М4 через M1. Для ускорения сходимости в подобных ситуациях служит технология Triggered Update.

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

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

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

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

Маршруты, получаемые с помощью протокола RIP, могут проходить серию стадий в таблице маршрутизации. Например, для маршрутизаторов фирмы 3Com маршруты проходят следующие стадии:

UP — маршрут может находиться в данной стадии, если он достижим с определенной (меньше 16) метрикой. Маршрут остается в данном состоянии в течение шестикратного интервала времени между периодичной посылкой сообщений об обновлении. Это значение известно как таймер маршрута. Данный тай мер сбрасывается каждый раз, когда поступает новое сообщение об обновлении для этого маршрута. По истечении этого таймера маршрут более не рассматривается как корректный и переводится в стадию Garbare — Collection;
Hold — Down — маршрут, находящийся в стадии UP, переходит в данную стадию, если маршрутизатор получил сообщение об обновлении маршрута с метрикой, равной бесконечности, от маршрутизатора, который явился источником информации об этом маршруте. Маршрут будет оставаться в данной стадии весь период времени, равный четырехкратному интервалу посылки сообщений об обновлении. Это значение известно как Hold - Down Timer. В этой стадии маршрутизатор будет игнорировать информацию о сети на промежутке времени, следующем за получением сообщения, информирующего о том, что и эта сеть недостижима. Когда таймер Hold -- Down обнулится, маршру-тизатор перейдет в стадию Garbage — Collection. Если сообщение, содержащее информацию об этом маршруте с метрикой меньше 16, получено от исходного маршрутизатора до обнуления таймера, этот маршрут перейдет в стадию UP. Цель этого состояния — в позволении всем другим маршрутизаторам в автономной системе получать информацию о том, что маршрут не функционирует. Это препятствует маршрутизатору в этом состоянии ошибочно принимать сообщение, содержимое которого устарело;
Garbare — Collection. Когда таймер маршрута, который был в стадии UP, обнулился, он переходит в стадию Garbage Collection. Маршрут может оставаться в этой стадии на время, равное четырехкратному интервалу обновлений. Это значение времени называется Garbage — Collection Timer. В этой стадии соседи могут извещать маршрутизатор, что сеть более недостижима. В течение этой стадии маршрут с метрикой, равной 16, включается во все сообщения об обновлении, посылаемые этим маршрутизатором. Это вызывает удаление маршрута из списка возможных. Если не получено сообщений об обновлении до обнуления таймера Garbage —Collection, маршрут удаляется из таблицы маршрутизации. Если соседний маршрутизатор информирует об этом маршруте с метрикой меньше 16 до обнуления таймера, новый маршрут будет заменять маршрут, подготовленный для удаления. В этом случае таймер обнуляется.

2.7 Выводы по главе 2

Таким образом, в данной главе были рассмотрены назначение и основные цели маршрутизации, типы алгоритмов, метрики маршрутизации, протокол маршрутизации RIP.

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

Были рассмотрены проблемы маршрутизации, возникающие при изменении состояния сети, такие как: медленная сходимость и возникновение петель маршрутизации.

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

В завершение были рассмотрены технологии ускорения сходимости в сетях RIP.

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

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

2) Кульгин М. В. Коммутация и маршрутизация IP/IPX – трафика

3) RFC 1058. Routing Information Protocol

1. 1991г. Перестро~йка общее название нового курса советского партийного руководства совокупности политичес
2. Учёт и реализация готовой продукции
3. Основы психологической коррекции
4. Судебная система РФ Источники права
5. Ответы на экзаменационные билеты по высшей математики
6. реферату- Глобальна екологічна криза
7. по теме Международная торговля Ставки налога на добавленную стоимость косвенный налог фор.html
8. ТЕМА. Половая система совокупность органов обеспечивающих репродуктивную функцию организма или функцию
9. Промресурс
10. ФЗ РОССИЙСКАЯ ФЕДЕРАЦИЯ ФЕДЕРАЛЬНЫЙ ЗАКОН О РАТИФИКАЦИИ СОГЛАШЕНИЯ МЕЖДУ РОССИЙСКОЙ ФЕДЕРАЦ
11. Реферат- Общая характеристика и классификация программного обеспечение и базовых технологий управления информационными ресурсами
12. Уральский комбайн главной задачей имеет сборку зерноуборочного комбайна Вестерн по лицензии канадской.html
13. тематике ученика 2 А класса МБОУ
14. ТЕМА 1 МІЖНАРОДНА ЕКОНОМІЧНА СИСТЕМА Предмет курсу ldquo;міжнародна економікаrdquo;
15. МЫСЛЬ 1991 в кратком изложении ББК 87
16. ТЕМА 7. КРЕДИТ У РИНКОВІЙ ЕКОНОМІЦІ НЕОБХІДНІСТЬ СУТНІСТЬ ТА ФУНКЦІЇ КРЕДИТУ.
17. Псковинфопресс 2001
18. тема- Стабилизация и управление государственным долгом России Выполнили студенты 2 курс
19. Лабораторная работа 13
20. Управление культуры спорта молодежной политики и работы с детьми администрации Петушинского района

Материалы собраны группой SamZan и находятся в свободном доступе