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

Лабораторная работа №1

Факультет:	АВТ
Группа:	АМ-109
Студенты:	_________________
	_________________
	_________________
Дата:

Цель работы

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

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

№ варианта: 8

Количество узлов: 28

r : 9

Длинна пакета: 500

Ход работы

1. Граф

Результирующий граф получается из кольцевой структуры путем введения дополнительной связи длиной r = 9. Дополнительные связи (хорды) вводятся по следующему правилу. Каждый i-й узел связан с (i+r) Mod N - ((i+5) Mod 16) для нечетных узлов и с (i-r) Mod N - ((i-5) Mod 16) для четных i. Из регулярности и трехсвязности графа G следует, что N - всегда четно, а r - всегда нечетно.

Рис. 1 Граф

2. Маршрутная таблица

Построим маршрутную таблицу для полученного графа.

Таблица 1.

№ узла	H	S	K	/K
0	1	1	1	0
1	1	1	2	0
2	1	1	3	0
3	0	0	5	0
4	0	0	4	0
5	0	0	3	0
6	0	0	2	0
7	0	0	1	0
9	1	0	1	0
10	1	0	2	0
11	1	0	3	0
12	1	0	4	0
13	1	0	5	0
14	0	1	1	2
15	0	1	1	1
16	0	1	1	0
17	1	1	2	0
18	1	1	1	0
19	1	1	2	0
20	1	1	3	0
21	1	1	4	0
22	1	1	5	0
23	0	1	4	0
24	0	1	3	0
25	0	1	2	0
26	0	1	1	0
27	0	1	0	0

3. Таблица кратчайшех путей

В соответствии с маршрутной таблицей заполним таблицу кратчайших путей

Таблица 2.

8->27->0

8->27->0->1

8->27->0->1->2

8->7->6->5->4->3

8->7->6->5->4

8->7->6->5

8->7->6

8->7

8->9

8->9->10

8->9->10->11

8->9->10->11->12

8->9->10->11->12->13

8->7->16->15->14

8->7->16->15

8->7->16

8->9->18->17

8->9->18

8->9->18->19

8->9->18->19->20

8->9->18->19->20->21

8->9->18->19->20->21->22

8->27->26->25->24->23

8->27->26->25->24

8->27->26->25

8->27->26

8->27

4. Обрыв связи

Создадим обрыв связи 24-23 и посмотрим на поведение алгоритма:

Нет обрыва:

8->27->26->25->24

Обрыв:

8->27->26->25->6->5->14->15->24

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

Принцип работы алгоритма с неисправностями простой: пакет "выбрасывается" по свободной линии в соседний узел, из которого он снова идет по минимальному маршруту, заложенному в таблице минимальных маршрутов данного узла, т.е. открывается и тот порт, проходя через который, пакет будет ближе всего к цели. Проблема зацикливания пакетов в ВС решена следующим образом: если свободных линий, в которые можно "выбросить" пакет две, то он "выбрасывается" в направлении, на которое указывает переменная Х, которая случайным образом принимает значения 1 и 0 и фиксируется в данном узле. Кроме того, пакет не должен двигаться в направлении, откуда он вошел в узел; исключение составляет ситуация, когда пакет попадает в тупик, т.е. когда в узле, в который вошел пакет, есть обрывы на двух других линиях.

5. Многочисленные обрывы при непрерывном трафике

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

Последовательные обрывы связей:

Обрыв 24-23:

8->27->26->25->6->5->14->15->24

Обрыв 24-15:

27->26->25->6->5->14->15->16->7->6->25->26->27->0->1->10->11->20->21->22->23->24

Обрыв 5-6:

8->17->26->25->6->7->8->27->26->25->6->7->16->15->14->5->4->23->24

Обрыв 4-23:

8->27->26->25->6->7->16->15->14->5->4->3->12->3->22->23

6. Столкновение пакетов при движении по разным маршрутам:

Пустим два пакета по маршрутам 8-25 и 25-0:

8->27->26->25

25->26->(линия занята)->17->16->8->27->0

7. Добавление и удаление вершин графа

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

Выводы

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