Full
.docМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Новосибирский государственный технический университет»
Лабораторная работа №1: «Исследование алгоритмов маршрутизации в вычислительных системах сетевой архитектуры с регулярной структурой»
Группа: АВТ-115
Вариант: 2
Выполнили: Собянин М.Ю.
Шалакин М.А.
Новосибирск, 2015
-
Цель работы
Целью работы являются исследование отказоустойчивых алгоритмов маршрутизации для регулярной вычислительной системы, заданной регулярным графом.
-
Задание
-
Построить для соответствующего варианта граф ВС, заданный в таблице 3. Запустить на выполнение программу построения графа и сверить результаты. Оформить в отчете алгоритм построения графа для варианта.
-
Сформировать в отчете таблицу минимальных маршрутов для узла, соответствующего номеру варианта задания.
-
Сформировать по таблице маршрутов пути от узла, соответствующего номеру варианта, ко всем остальным узлам. Пути оформить в отчете с помощью маркировки i1->i2-> ...->ik, где i - номер вершины на пути следования пакета. С помощью программы сформировать посылки пакета по тем же маршрутам. Сверить результаты.
-
На произвольном маршруте задать обрыв. Оформить в отчете новый маршрут пакета.Описать алгоритм выбора обходного маршрута. С помощью программы провести соответствующий эксперимент и сверить результаты.
-
Сформировать с помощью программы непрерывный трафик по маршруту; убирая ребра на кратчайшем пути, исследовать - сколько обрывов выдержит алгоритм. Фиксировать новые маршруты обхода в отчете с помощью маркировки i1->i2->i3-> ... ->ik, где i - номер вершины на пути следования пакета.
-
Породить несколько сообщений из разных узлов-источников с разными узлами-назначения. Проанализировать поведение алгоритма. Анализ в виде трафиков на графе ВС оформить в отчете.
-
Исследовать поведение алгоритма при увеличении и уменьшении числа узлов на единицу.
Вариант: 6.
Кол-во узлов: 16
R1: 3
R2: 5
Длина пакета: 350
-
Ход работы
Согласно варианту был построен граф ВС. Он изображен на рисунке Рисунок 1.
Рисунок 1 – Граф ВС
Структура задается графом G(16,3,5)5.
Дополнительные связи (хорды) вводятся по следующему правилу. Каждый i-й узел связан с (i+r) Mod N - ((i+5) Mod 16) для нечетных узлов и с (i-r) Mod N - ((i-5) Mod 16) для четных i. Приведем несколько шагов расчета хорд:
Вершина 0 – четная. Поэтому (0-5) mod 16 = 3.
Вершина 1 – нечетная. Поэтому (1+5) mod 16 = 6.
Маршрутная таблица представлена ниже (Таблица Таблица 1). Каждая строка этой таблицы соответствует определенному узлу и содержит информацию о кратчайшем пути до этого узла от узла 6.
Таблица 1 – Таблица маршрутизации для вершины 2 графа
|
|
H |
S |
K |
NK |
|
0 |
2 |
2 |
1 |
1 |
|
1 |
1 |
1 |
2 |
0 |
|
2 |
1 |
1 |
1 |
0 |
|
3 |
1 |
1 |
0 |
0 |
|
4 |
1 |
0 |
2 |
0 |
|
5 |
1 |
0 |
1 |
0 |
|
6 |
0 |
0 |
0 |
0 |
|
7 |
0 |
0 |
1 |
0 |
|
8 |
0 |
0 |
2 |
0 |
|
9 |
0 |
0 |
3 |
0 |
|
10 |
0 |
1 |
1 |
0 |
|
11 |
0 |
1 |
2 |
0 |
|
12 |
0 |
1 |
3 |
0 |
|
13 |
0 |
1 |
4 |
0 |
|
14 |
0 |
2 |
2 |
0 |
|
15 |
1 |
2 |
1 |
0 |
|
Пункт назначения |
Путь |
|
0 |
6->3->4->1->0 |
|
1 |
6->3->2->1 |
|
2 |
6->3->2 |
|
3 |
6->3 |
|
4 |
6->5->4 |
|
5 |
6->5 |
|
7 |
6->7 |
|
8 |
6->7->8 |
|
9 |
6->7->8->9 |
|
10 |
6->7->10 |
|
11 |
6->7->10->11 |
|
12 |
6->7->10->11->12 |
|
13 |
6->7->10->11->12->13 |
|
14 |
6->7->10->11->14 |
|
15 |
6->3->2->15 |
4) Создадим обрыв между узлами 12 и 9, а также между узлами 7 и 6. Отправим пакет из узла 12 в узел 6. Рассчитанный путь из 12 в 6 путь будет таков: 12->11->10->7->8->5->6.
Путь полученный в ходе симуляции: 12->11->10->7->8->9->10->7->8->5->6.
5) Для исследования количества обрывов которые выдержит алгоритм будем отправлять пакеты из 14 в 6 пункты.
Уберем ребро 15-2 получим маршрут: 14->15->0->1->4->5->6
Уберем ребро 1-4 получим маршрут: 14->15->0->1->2->3->6
Уберем ребро 3-6 получим маршрут: 14->15->0->1->2->3->4->5->6
Уберем ребро 0-1 получим маршрут: 14->15->0->13->12->9->10->7->6
Убурем ребро 0-13 получим маршрут: 14->15->0->15->14->13->12->9->10->7->6
Уберем ребро 12-9 получим маршрут: 14->15->0->15->14->13->12->11->10->7->6
Уберем ребро 11-12 получим маршрут: 14->15->0->15->14->11->10->7->6
Уберем ребро 10-7 получим маршрут: 14->15->0->15->14->11->10->9->8->7->6
Уберем ребро 7-6, пакет следует по маршруту 14->15->0->15->14->11->10->9->8->7->8->9->10->11->14->15->0 и так на протяжении очень большого времени, но в результате пакет достиг точку назначения. Таким образом алгоритм сломался после 9 убранного ребра.
Алгоритм устойчив к разрывам. Он способен найти путь при его физическом наличии. При увеличении количества разрывов на кратчайшем пути, возрастает длина маршрута. Алгоритм имеет защиту от зацикливания, которая лежит в основе выбора следующей вершины. Если разрывы будут непосредственно связаны с вершиной-источником или вершиной-получателем, то алгоритм выдержит всего 3 разрыва. Т. е. максимальное количество разрывов, зависит от того, где будет рваться сеть.
При отправке пакет из одной вершины в другую было выяснено, что наибольший маршрут будет между вершинами, находящимися друг против друга на графе, и равен 5.
Граф с числом вершин больше или меньше на 1, так как для обеспечения регулярности и трехсвязности графа число вершин должно быть четно, а путь введения дополнительной связи – нечетным.
Вывод
В ходе лабораторной работы был исследован алгоритм маршрутизации пакетов для регулярных структур.
Алгоритм ищет кратчайший путь из одной вершины в другую.
Он обладает возможностями поиска обходного пути при возникновении разрыва. Если путь от одной вершины до другой существует, то пакет дойдет до получателя. Для того, чтобы пакет не попал в цикл, есть способы определения следующей вершины для выхода из него.
Также алгоритм может изменить направление движения пакета, если узел, в который он должен был быть направлен загружен. Это было замечено при посылке пакетов от одного узла другому большого числа пакетов.