Методы маршрутизации в вычислительных сетях: Методические указания к выполнению лабораторных работ 1-2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

МЕТОДЫ МАРШРУТИЗАЦИИ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ Методические указания к выполнению лабораторных работ № 1–2

Санкт-Петербург 2005

Составитель Ю. Д. Крылов Рецензент кандидат технических наук С. В. Горбачев

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

Редактор А. М. Картухина Компьютерная верстка А. Н. Колешко Сдано в набор 06.12.04. Подписано к печати 28.12.04. Формат 60´84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,27. Усл. кр.-отт. 0,95. Уч. -изд. л. 0,96. Тираж 100 экз. Заказ № Редакционно-издательский отдел Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии СПбГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67

©

ГОУ ВПО “Санкт-Петербургский государственный университет аэрокосмического приборостроения”, 2004

Введение Маршрутизация – это выбор наилучшего в некотором смысле пути между двумя любыми абонентскими машинами для передачи информации при их функционировании в составе территориально-распределенной вычислительной сети [1]. Критерии выбора маршрута могут быть различными. Например, оптимальным маршрутом может быть кратчайший по протяженности путь или путь, обеспечивающий определенный уровень надежности при передаче информации, или же путь, в котором наименьшее число промежуточных узлов коммутации, где информация может временно храниться в буферной памяти и где наблюдаются задержки при ее передаче. Матричный метод и метод Флойда [3] обеспечивают нахождение кратчайших путей по критерию минимального линейного расстояния между двумя абонентскими машинами. Метод рельефов обеспечивает нахождение кратчайшего пути по критерию минимизации числа так называемых хопов (прыжков) или числа коммуникационных машин между двумя взаимодействующими абонентскими машинами.

Учебноисследовательская лабораторная работа № 1 ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ ПУТЕЙ ПО МАТРИЧНОМУ МЕТОДУ И МЕТОДУ ФЛОЙДА

Описание работы Цель работы: ознакомление с методами определения кратчайших путей в территориально-распределенных вычислительных сетях. Распределение каналов и потоков информации на линии связи производится с учетом длины пути. Для оценки длины пути используются различные критерии [1,2,4]: – число транзитных участков между взаимодействующими узлами коммутации (УК); – протяженность пути; – качество тракта передачи; – надежность передачи и т. д. Кратчайшим путем передачи информации называется путь, для которого критерий длины пути имеет наименьшее значение по сравнению с его значением для других возможных путей. В теории потоков все методы выбора кратчайших путей основаны на утверждении о том, что если кратчайший путь mij от произвольного УКi к УКj проходит через промежуточные УКi1,…,УКik (рис. 1), то кратчайшие пути mi1,j,…,mik,j от УКi1,…, УКik к УКj , соответственно, являются частями кратчайшего пути mi,j от УКi к УКj . Если длина пути mi1,j равна Li1,j ,то Li,j = Li,i1 + Li1,j .

OE i

OE ik

OEi1

OE j

l ik,j l

i1,j

li,j Рис. 1

Так как m i,j является кратчайшим, то L1, j 1 min (l1,2 2 L2, j ), 23 i1,iN

4

(1)

где N – число узлов сети. Для нахождения кратчайшего пути от узла e к узлу j необходимо просмотреть все возможные пути и выбрать тот, у которого длина наименьшая. Имеется ряд методов определения длины кратчайшего пути. Их можно разделить на две группы: методы нумерации узлов и матричные методы. Матричный метод определения кратчайших путей позволяет найти длины кратчайших путей между всеми узлами сети одновременно и основывается на применении операций над матрицами расстояний. Структуру сети связи с указанием длин ветвей можно описать в виде матрицы расстояний (длин) непосредственных связей: L1 = || li1,j ||, где элемент li1, j определяет длину ветви bi,j . Пример. Пусть сеть связи имеет вид, представленный на рис. 2. B

30 A

15

20

15 15

20

C

20

D

20

15 25

25

10

F E

40 Рис. 2

Цифры на ребрах и дугах соответствуют длинам ветвей. Тогда матрица расстояний будет:

A A 0 B 1 L1 2

B

C

D

E

F

30 1 20 0 15 15

1 1

1 1

C 1 15 0 20 25 1 . D 20 15 20 0 1 25 E 1 1 25 10 0 40 F 15

1

1

25 40

(2)

0 5

Элементы главной диагонали равны 0, так как принимается, что расстояние внутри узла равно нулю. Если между парой узлов отсутствует ребро, то соответствующий элемент матрицы равен бесконечности (¥). Если между узлами i и j имеется дуга 11i,j , то элемент li1, j также принимается равным бесконечности, например, l1A,F = ¥, тогда же l1 F,A =15. При анализе сетей передачи данных длину ветви удобно трактовать как задержку, которую вносит ветвь при передаче информации. Матрица расстояний непосредственных связей неориентированной сети всегда симметрична относительно своей главной диагонали. Для ориентированной сети (как в примере) она может быть нессиметричной. Возведем матрицу L1 в квадрат L2 = L1· L1 . Тогда N

1 1 1 1 1 li2,j 1 4 li1,k 2 lk1, j 1 li1,1 2 l1, j 3 li,2 2 l2, j 3 ... 3 li,N 2 lN ,

(3)

k 11

Можно интерпретировать умножение как последовательное соединение ветвей, а сложение как параллельное соединение ветвей. Произведение li1,k 1 lk1,j соответствует двухтранзитному пути (т. е. пути проходящему через две транзитных ветви сети) от узла ik к узлу j через узел k (рис. 3,а), а сумма, например, трех произведений li1,i 1 li1,j 2 li1,j 1 l1j,j 2 li1,k 1 lk1,j

трем двухтранзитным путям (рис. 3,б). б) l1i,i

a) i

l1i,j

j

li1,k

j

l1k,j

i

l1j,j

l i1,j

k

l1k,j

li1,k k

Рис. 3

6

Произведения li1,i 1 li1, j и li1, j 1 l1j,j фактически соответствуют однотранзитным путям, так как длина пути (задержка) внутри УК (т. е. li1,i и l1j,j ) не принимается во внимание. Для подсчета длины каждого из таких n транзитных путей необходимо операцию умножения заменить операцией сложения, т. е. вместо li1,k 1 lk1,j будем иметь li1,k + lk1, j . При наличии нескольких параллельных одно- двухтранзитных путей (рису. 3,б) для определения длины кратчайшего пути между узлами следует операцию сложения заменить операцией выбора из всех длин минимальной длины одно- двухтранзитного пути, т. е. вместо (3) будем иметь:

1

2

1

21

2

1

2

1 1 1 1 1 li2,j 3 min li1,k 4 lk1, j 3 min li1,1 4 l1, j ; li,2 4 l2, j ; ... li,N 4 lN, j . k 11,...,N

Таким образом , элемент li2,j матрицы L2 равен длине кратчайшего пути от УКi к УКj среди всех одно- двухтранзитных путей. При возведении матрицы L1 в r-ю степень при использовании этих операций получим матрицу Lr = Lr–1*L1 , элемент которой

lir,j 3 min

k 21,...,N

1l 1

r 1 i,k

2

1

21

2

1

1 r 11 1 r 11 1 4 lk1, j 3 min lir,111 4 l1, j ; li,2 4 l2, j ; ... li,N 4 lN , j

2

будет равен длине кратчайшего пути от УКi к УКj среди всех однодвух- и т. д. r-транзитных путей. При наличии на сети N узлов коммутации число транзитных ветвей в пути без петель не может быть больше N–1 . Следовательно, может потребоваться вычисление матрицы Lr, у которой r £ N–1. Для конкретной сети может оказаться, что при r < N–1 Lr = Lr–1 .

(4)

Так как при равенстве (4) всегда выполняется равенство Lr+1 = Lr, вычисление матрицы более высокой степени прекращается, если в процессе вычисления матриц встретится равенство (4). Матрица Lr–1 при выполнении условия (4) называется дистанци онной матрицей и обозначается D = Lr–1 = Lr = || d i,j || .

(5)

7

Таким образом, элементы дистанционной матрицы равны длинам кратчайших путей между соответствующими узлами сети связи. Матрица D часто называется матрицей расстояний (длин, задержек). Для рассматриваемого примера вычислим l2A,B: L2A,B = min |(l 1A,A + l1A,B); (l1A,B + l1B B); (l1A,C + l1C,B ); (l1A,D + l1D,B); (l1A,E + l1E,B);( l1A,F + l1 F,B)| = = min |(0 + 30); (30 + 0); (¥ + 15); (20 + 15); (¥ + ¥);(¥ + ¥)|= = min | 30; 30; ¥; 35,¥,¥ |=30 . Аналогично вычислим остальные элементы матрицы L2 , получим:

A

B

C

D

E

F

A 0 30 40 20 1 45 B 35 0 15 15 40 40 L2 2

C 40 15 0 20 25 45 ; D 20 15 20 0 45 25 E 30 25 25 10 0 35 F 15 40 45 25 40 A

B

C

D

E

0 F

A 0 30 40 20 65 45 B 35 0 15 15 40 40 L3 1

C 40 15 0 20 25 45 ; D 20 15 20 0 45 25 E 30 25 25 10 0 35 F 15 40 45 25 40 A

B

C

D

E

0 F

A 0 30 40 20 65 45 B 35 0 15 15 40 40 L4 1

C 40 15 0 20 25 45 . D 20 15 20 0 45 25 E 30 25 25 10 0 35 F 15 40 45 25 40

8

0

Здесь L4 = L3, следовательно, D = L3 . Рассмотренные методы позволяют определить длину кратчайшего пути, но не указывают те ветви, которые входят в этот путь. Определение самого кратчайшего пути связано с некоторой дополнительной процедурой. Если для определения длины кратчайшего пути применяется способ нумерации узлов, то при выполнении дополнительной процедуры учитывается свойство веса УКi . Это свойство заключается в том, что существует УКj , для которого выполняется равенство: Wi = li,j+Wj .

(6)

Отсюда следует, что Wi – Wj = li,j . (7) Поэтому, если выполняется условие (7), то кратчайший путь от УКi проходит по ветви bi,j . Переходя к УКj , находим следующую ветвь, для которой выполняется последнее условие и которая также входит в этот кратчайший путь. Так, шаг за шагом можно определить все ветви, образующие кратчайший путь. Исключив затем кратчайший путь из рассмотрения, подобным образом определяются и другие пути от исходящего УКi к входящему УКj. Данный метод выбора кратчайших путей от одного узла до всех остальных узлов называется методом Флойда. При матричном методе определения кратчайшего пути дополнительно к дистанционной матрице на основе матрицы длин непосредственных связей составляется так называемая матрица длин непосредственных связей Г, элементы главной диагонали которой в отличие от элементов li,j = 0 имеют значения li,j = ¥, где значком ¥ обозначена бесконечность. Таким образом, матрица Г легко может быть получена по матрице L1 . Пример. Для рассматриваемого случая

A A B C Г2 D E

B

C

D

E

F

1 30 1 20 1 1 1 1 15 15 1 1 1 15 1 20 25 1 . 20 15 20 1 1 25 1 1 25 10 1 40

F 15

1

1

25 40

1 9

Замена элемента l1i,i = 0 на l1i,i = ¥ в матрице Г означает, что длина пути в УКi принимается бесконечно большой. Это дает возможность не рассматривать все пути, проходящие через исходный узел, т. е. позволяет исключить путь (bi,i , b i,j), изображенный на рис. 3,б. Полученная таким способом модернизированная матрица длин Г = ||gi.j || умножается на дистанционную матрицу D с использованием тех же операций, что и ранее. При умножении матрицы Г на матрицу D образуется матрица D = ГD, элементы которой используются для получения дисперсионных матриц (т. е. матриц величин второго и т. д. кратчайших путей). Каждый элемент матрицы D = || d i,j || имеет вид: 1i, j 2 min ( 3 i,1 4 d1, j );( 3 i,2 4 d2,j ); ... ( 3 i,i 4 di, j ); ... ( 3 i,N 4 dN, j ) . k

(8)

В выражении (8) min означает, что минимум может браться для кратчайшего пути (k = 1), второго по длине пути (k = 2) и т. д. Каждый из членов (gi,e + de,j) = ¥ в выражении (8) определяет длину пути от узла i к узлу j ,если первым транзитным узлом после узла i на пути к узлу j будет узел e, e Î (1,…, N). Если узел e не является соседним узлом i, то (gi,e + de,j) = ¥. Так как gi,i = ¥, член (g i,i + di,j) будет всегда ¥. При этом элемент (gi,j + dj,j) не обязательно равен ¥. Таким образом, число членов выражения (8), не равных бесконечности, равно числу n соседних УК, т. е. числу исходящих из УК направлений (ветвей). Член выражения (8), имеющий минимальное значение и определяющий длину кратчайшего пути от узла i к узлу j через узел e: 11i,j = min |(gi,1 + d1,j);…(gi,N + dN,j)|, 1

заносится в качестве элемента 11i,j в дисперсионную матрицу первого 1 выбора D = || 11i,j ||. Второй по значению член выражения (8), определяющий длину второго по протяженности пути после кратчайшего от узла i к узлу j: 12i, j = min |(gi,1 + d1,j );…(gi,N + dN,j)|, 2

заносится в качестве элемента 12i, j в дисперсионную матрицу второго 2 выбора D = || 12i, j || . При наличии n соседних узлов можно получить n дисперсионных матриц D1 ,…, Dn . Рассмотрим пример расчета элементов матриц D (D1,D2,…). Пусть сеть связи имеет вид, представленный на рис. 2. 10

Тогда матрицы L1 и Г будут

A A 0 B 1 L1 2

B

C

D

E

F

30 1 20 0 15 15

1 1

1 1

A A 1 B 1

B

C

D

30 1 20 1 15 15

E 1 1

F 1 1

C 1 15 0 20 25 1 C 1 15 1 20 25 1 , Г2 . D 20 15 20 0 1 40 D 20 15 20 1 1 40 E 1 1 25 15 0 40 E 1 1 25 15 1 40 1

F 15

1

25 40

0

F 15

1

1

25 40

1

Тогда, например, элемент 111,2 ,определяющий минимальный по протяженности путь от вершины A к вершине B матрицы D1, согласно (8) будет 111,2 = min [(g1,1 + d1,2);(g1,2 + d2,2);(g1,3 + d3,2); (g1,4 + d4,2); 1

(g1,5 + d5,2); (g1,6 + d

6,2

)] =

= min [(¥ + 30); (30 + 0); (¥ + 15); (20 +15); (¥ + 25); (¥ + 40) = 30. 1

Так как минимальное значение в выражении находится на втором месте, что соответствует вершине B, то в минимальном пути от вершины A к вершине B нет промежуточных вершин. 2 матрицы D2 , соответствующий второму по протяженЭлемент 11,2 ности пути от вершины A к вершине B, будет: 2 = min […. ] = 35. 11,2 2

Так как второе по минимуму выражение находится на четвертом месте, что соответствует вершине D, то второй по протяженности путь от вершины A к вершине B проходит через вершину D. Выбрав кратчайшие пути от какого-либо узла ко всем остальным, можно построить так называемое дерево кратB чайших путей, в котором из всего множества путей от узла указаны только кратчайшие от A него пути ко всем остальным узлам. Например, для графа, представленного на D C E рис. 2, которому сопоставлена матрица L1 непосредственных связей, дерево кратчайших путей от вершины А изображено на рис. 4. F Дерево кратчайших путей является поддеРис. 4 ревом дерева путей. 11

З а м е ч а н и е . Дерево кратчайших путей и дерево путей от узла ко всем остальным узлам для неориентированных графов (сетей) совпадает с деревом кратчайших путей и деревом путей соответственно от всех узлов к рассматриваемому узлу i. Для ориентированных графов (сетей связи) такого совпадения может и не быть. Порядок выполнения работы 1. Получить задание. 2. Построить граф-схему алгоритма определения расстояний между вершинами по матричному методу (используя дистанционные матрицы) или алгоритма определения кратчайших путей по методу Флойда (используя дисперсионные матрицы). 3. Составить программу для реализации алгоритма. 4. Начертить дерево путей от заданной вершины к остальным вершинам и дерево кратчайших путей от заданной вершины к остальным вершинам при использовании метода Флойда. Содержание отчета 1. Задание. 2. Сеть связи вычислительной сети по примеру (рис. 2). 3. Программа. 4. Результат выполнения программы Контрольные вопросы 1. Какие критерии используются при выборе оптимальных путей в вычислительных сетях? 2. Чем отличается матричный метод определения оптимального пути от метода Флойда? 3. Как формируется исходная дистанционная матрица? 4. Как формируется матрица непосредственных длин связей Г? 5. Что такое дисперсионная матрица? Задание к лабораторной работе № 1 1. Используемый в работе метод определяется по формуле: i (mod 2), где i – номер варианта задания; 0 – метод при использовании матрицы расстояний; 1 – метод при использовании дисперсионной матрицы. 2. Число узлов определяется по формуле: N=5+i (mod 3).

12

3. Соответствие узлов по номерам и их идентификаторов 1 – A; 2 – B; 3 – C; 4 – D; 5 – E; 6 – F; 7 – H. Число узлов

Подвариант

N=5

1

AB=30; BD=40; DB=40; AC=50; CA=50; CD=10; EA=35; ED=35+; BC=20; CE=40+

2

AB=30; BD=30; DB=30; CA=60; CD=15+; CB=10+; AE=30; EA=30; CE=25+;ED=40+

3

AB=30; BA=30; BD=20; AC=25; CB=15; CD=20+; EA=25; CE=15; DE=40+

4

AB=20+; BD=30+; CA=40; CB=10; BC=10; CD=15+; AE=35; EC=15; ED=40

1

AB=30; BC=15; CB=15; AD=20; DA=20; DC=20; CD=20; BD=15+; DF=25+; CE=25+; ED=10; EF=40+; DF=25+; FA=15

2

BA=35; BC=10; CB=10; AD=40; DB=10; CD=25+; AF=60; DF=10+; CE=70+; DE=15; EF=30+

3

AB=20; BC=30; AD=20; DA=20; DC=20+; CE=10; EC=10; DE=35; DF=10; EF=40+; FA=15

4

BA=40; BC=10; CB=10; AD=30+; DB=15; BD=15; DC=40+; DE=20; ED=20; CE=15+; AF=25; FE=20; EF=20;

1

AB=20; BA=20; BC=30; AD=30; BD=20; DB=20; DC=15; CE=35; DE=20+; DF=10; FD=10; FE=15; FH=15; FH=25; DH=15; HD=15;HA=35

2

AB=30; BC=40; CB=40; DA=35; DB=10+; DC=15; CE=35; ED=20; EF=40+; FD=15+; HF=30; HD=30;DH=30; AH=45; HA=45

3

AB=15; BA=15; BC=30+; BD=20; AD=15; DA=15; DC=20; CD=20; CE=35+; DE=40+; DF=10; FE=20+; HF=10+; HD=50+; AH=35+

4

BA=20; BC=15; BD=25; DB=25; DC=30+; DA=25+; CE=35+; ED=40; FE=30; EF=30; DF=15; FH=40+; HD=15; DH=15; HA=25

N=6

N=7

Расстояние между узлами

Примечания: 1. Запись, например, AB = означает, что направление передачи будет от узла A к узлу B. 2. + означает двустороннюю передачу (соответствующая дуга не имеет стрелок).

13

4. Номер узла, расположенного в центре рисунка, определяется по формуле: K=] N/2+1 [, где ] [– ближайшее меньшее целое. Остальные узлы располагаются симметрично по кругу. 5. Номер подварианта определяется по формуле: j=i [ mod 4 ], где 0 – подвариант 1; 1 – подвариант 2; 2 – подвариант 3; 3 – подвариант 4. 6. Расстояния между узлами приведены в таблице. Учебноисследовательская лабораторная работа № 2 МЕТОД РЕЛЬЕФОВ

Описание работы Цель работы: ознакомление с методами маршрутизации [1], где в качестве критерия при выборе наилучшего пути используется минимизация количества транзитных звеньев между любыми парами абонентов. Данный метод маршрутизации широко используется в интегрированных вычислительных сетях [2,4]. Этот метод относится к групповым распределенным методам динамического управления. Критерием выбора пути является минимизация длины пути, выраженная числом транзитных участков. На сети связи при применении этого метода должны выполняться операции формирования рельефа и его коррекция [3]. Формирование рельефа осуществляется в начальный момент времени (в момент пуска сети) и при развитии сети, то есть при вводе в действие новых узлов коммутации (УК). Коррекция выполняется периодически в процессе функционирования сети или в момент возникновения повреждений или перегрузок. Рассмотрим эти операции. В момент пуска сети формирование рельефа начинается с некоторого узла УКa , a = 1,2,…,N, где N – число УК на сети. Говорят, что начинается построение a-рельефа. В запоминающих устройствах каждого УКi сети отводится объем памяти 14

NMi, где Mi – число исходящих направлений из УКi . Туда заносится матрица рельефов Ri . При формировании рельефа из УК- инициализатора во всех исходящих из него направлений передается цифра 1, которая на соседних с УК-инициализатором узлах заносится в матрицу Ri по координатам ( n,m1), где n – номер УК-инициализатора; m1 – номер ветви по которой поступила единица. Пример. Пусть имеем сеть, изображенную на рис. 1,а. Далее процесс построения рельефа будет следующим. 1. Все УК, в которые поступила цифра 1, передают по всем исходящим направлениям, за исключением того направления, по которому поступила 1, цифру 2. Эта цифра во всех УК, в которые она поступила, заносится в матрицу Ri по координатам: (n,m2), где m2 – номер ветви, по которой поступила цифра 2. В примере цифра 2 будет занесена в матрицу RB, RC, RD, RE, RF. Теперь УК, на которые поступила цифра 2, передают по исходящим направлениям цифру 3 и т. д. Пусть в каждом УК отведена область памяти для формирования матрицы R (рис. 1,б). Пусть узлом-инициатором является УКА. В этом случае цифра 1 будет записана в матрицу RB и RC. 2. Если в УК поступает цифра с одного направления, на данном УК происходит инициализация для передачи цифры на единицу больше той, которая поступила по всем направлениям, за исключением того направления, по которому передана данная цифра. Передача цифры по этому направлению возможна лишь при поступлении в данный УК следующей цифры. Цифра, передаваемая по этому направлению, должна быть на единицу больше цифры, поступающей второй по порядку. Например, в УКD цифра 2 поступает по одному направлению – от УКВ. Тогда цифра 3 с УКD должна передаваться по всем направлениям, за исключением направления к УКВ . По этому направлению будет передана цифра 4, так как следующая по порядку цифра, поступившая в УКD , – это цифра 3 . 3. Инициализация передачи цифр по всем направлениям на каждом УК происходит один раз после поступления первой цифры по порядку. Например, при передаче цифры 3 на УКС от УКЕ она заносится 15

a) 1

1 OE

1

A

1

2

2 2

OE A 2 3 OE D 3

б)

R B – OE A

2

3

1

2

3

1 CA 1 CB 1 CE R C – OE A 1

2

3

1 DB 1 DE RD – OE A

R E – OE A

2

3

1 EB 1 EC 2

2

1 ED 3

1 FC R F – OE A

2

Рис. 1

16

3

1 BE

4

2 3

OE A

1 BA 1 BC 1 BD

OE N 2

3

3

4 3

2

2

OE F 3

в матрицу RC по соответствующим координатам, а инициализация передачи следующей по порядку цифры уже не происходит, так как ранее была осуществлена передача цифры 2. Так будет сформирован А-рельеф. Аналогично, строятся рельефы для всех остальных узлов сети. Считается, что рельеф сформирован, если построены все a-рельефы: (a = 1, 2,…, N). Поиск оптимального пути при установлении соединения от УКi к УКj состоит в отыскании в УКi и в каждом промежуточном УК ветви, которой соответствует минимальное число в строке матрицы рельефов для этих УК. Пример. Пусть требуется установить соединение от УКD к УКА (рис. 1,а). На УК D происходит обращение к строке матрицы рельефов R D , cоответствующей УКА (рис. 1,б). Соединение установлено по ветви, которой сооответствует минимальное число в этой строке. Для рассматриваемого примера – это ветвь bDB. На УКВ процесс поиска оптимального пути повторяетcя. В данном случае будет выбрана ветвь bВА . Если в этой ветви нет свободных каналов, то выбирается ветвь, которой соответствует следующее по порядку число, т. е. ветвь bВС и т. д. При выборе пути возможно возникновение “петель’’, т. е. когда соединение дважды проходит через один и тот же узел. Пример. Пусть требуется установить соединение от УКD к УКA . На УКD выбирается ветвь bDB. Пусть теперь в ветви bBA нет ни одного свободного канала. Тогда вызов согласно матрице RB перенаправляется по ветви bBC. Если в ветви bCA тоже нет свободных каналов, то согласно матрице RC вызов должен быть направлен обратно на УКВ. Это первый тип “петли’’. При соответствующей модификации данный вызов может блуждать по сети по такой петле: bDB, bBC, bCE ,bCB . Вызов дважды попадает в УКВ. Это второй тип “петли’’. Появление петель первого и второго типов недопустимо. Способ борьбы с возникновением петель заключается в том, что в процессе распространения по сети вызов “запоминает’’ номера УК, через которые он прошел, чтобы не проходить через них дважды. Коррекция Ситуация на сети непрерывно меняется: – одни направления перегружаются, а нагрузка других уменьшается; 17

a)

Rl

Rl Rl

OE l

Ri Ri OE i

Ri

Rm m

R

OE m Rm

б)

1 li11111111112

11111111112

OE 1 Rl –OE j OE N

1 i i1 OE 1 R i – OE j OE N

1111112

1il 1 im

111112

1 i in

r 11

r 1i

r 1m

r 1 1n

r j1

r jl

r jm

r j in

r N1

r Nl

rnm

r N in

Ri

Ri

2

1mi

2

OE 1 Rm–OE j OE N Рис. 2

– могут выйти из строя каналы связи; – могут быть повреждения в отдельных направлениях связи и УК. Поэтому необходима коррекция рельефа сети. Рассмотрим процесс обмена служебной информацией между управляющими устройствами (УУ) соседних узлов УКi, УКl, УКm (рис. 2,а) при коррекции рельефа сети. Пусть в УКi хранится матрица рельефов Ri (рис. 2,б). Пусть по18

ступил сигнал начала передачи служебной информации о рельефах на соседние УК. Тогда УУ считает из ЗУ, в котором хранится матрица Ri, элемент первой строки и найдет минимальный из них. Предположим, что минимальным элементом, т. е. элементом с минимальной высотой 1-го рельефа, будет r1,l . Это означает, что кратчайший путь из УКi до УК1 проходит через узел УКl , а число транзитных участков в нем равно r 1,l . Согласно определению формирования рельефа УУ, прибавив единицу к этому элементу, получим элемент R i1 = min (r1,i1,…,r 1,l , r1,m ,…r1,in) +1, i

который необходимо передать на соседние узлы. Значение ri1 равно высоте 1–рельефа тех ветвей, которые связывает узлы с УКi. Однако в рассматриваемой распределенной системе динамического управления элемент ri1 не передается на соседние узлы до тех пор, пока не будут определены другие элементы, соответствующие другим рельефам, т. е. r2i = min (r2,i1,…,r 2,l, r 2,m,…, r 2,in) + 1; i

… rNi = min (r N,i1,…,r N,l ,rN,m,…,r N,in) + 1. Эти элементы образуют вектор Ri = (r1i,…,rji,…,rNi) . После того как вектор Ri полностью вычислен управляющим устройством, УКi передает его в УУ всех соседних УК (рис. 2,б). При этом он записывается в ЗУ этих УК в качестве столбцов матрицы рельефов (рис. 2,б). Точно такие же операции выполняют управляющие устройства всех остальных УК. Если в ветви, например bi,m, отсутствуют каналы или она повреждена, то при вычислении элемента Rie , e = 1,…, N принимаем r e,m = ¥ . Порядок выполнения работы 1. Получить задание. 2. Нарисовать структуру вычислительной сети в соответствии с заданием. 3. Построить граф-схему алгоритма определения расстояний между исходной вершиной и любыми другими вершинами. 19

3. Составить программу для реализации алгоритма. Содержание отчета 1. Задание. 2. Граф-схема алгоритма. 3. Программа реализации алгоритма. Контрольные вопросы 1. Какой критерий используется для определения кратчайшего пути? 2. Что такое матрицы рельефов? 3. В каких случаях необходима коррекция рельефов? 4. Какого типа петли могут возникнуть при передаче информации? Задание к лабораторной работе № 2 1. Расположение вершин такое же, как и на рис. 1. 2. Соответствие номеров и обозначений вершин следующее: 1 – A; 2 – B; 3 – C; 4 – D; 5 – E; 6 – F. 3. Номер топологической схемы выбирается по формуле: N = 1+ i (mod 4), где i – номер варианта задания. Номер топологической схемы

Ребра, соединяющие вершины

1

AB; AC; BC; BD; BE; CF; DE; EC

2

AB; AC; BC; BD; BE; CF; DE; EF

3

AB; AC; BC; BD; BE; CE; CF; EF

4

AB; AC; BC; BD; CE; CF; DE; EF

4. Выбор исходной вершины определяется по формуле: N вершины = 1+ i (mod 6). 5. Написать программу определения оптимальных путей до исходной вершины от вершин, не являющихся соседними с исходной.

20

Библиографический список 1. Олифер В. Г. , Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы /СПб.: Питер, 2000. 672 c. 2. Лазарев В. Г. Интеллектуальные цифровые сети: Справочник / Под ред. Н. А. Кузнецова. М.: Финансы и статистика, 1996. 224 c. 3. Лазарев В. Г., Лазарев Ю. В. Динамическое управление потоками в сетях связи. M.: Радио и связь, 1989. 237 c. 4. Cоветов Б. Я., Яковлев С. А. Построение сетей интегрального обслуживания. Л.: Машиностроение, 1990. 332 c.

21

Оглавление Введение ........................................................................... 3 Учебно-исследовательская лабораторная работа № 1. Определение кратчайших путей по матричному методу и методу Флойда ............................................................ 4 Учебно-исследовательская лабораторная работа № 2. Метод рельефов ....................................................................... 14 Библиографический список .................................................. 21

22