Ход работы

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Новосибирский государственный технический университет»

Лабораторная работа №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

Пункт назначения	Путь
	6->3->4->1->0
	6->3->2->1
	6->3->2
	6->3
	6->5->4
	6->5
	6->7
	6->7->8
	6->7->8->9
	6->7->10
	6->7->10->11
	6->7->10->11->12
	6->7->10->11->12->13
	6->7->10->11->14
	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, так как для обеспечения регулярности и трехсвязности графа число вершин должно быть четно, а путь введения дополнительной связи – нечетным.

Вывод

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

Алгоритм ищет кратчайший путь из одной вершины в другую.

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

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