Методы маршрутизации в вычислительных сетях. Крылов Ю.Д. - 10 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

10
Замена элемента l
1
i,i
= 0 на l
1
i,i
= ¥ в матрице Г означает, что
длина пути в УК
i
принимается бесконечно большой. Это дает воз-
можность не рассматривать все пути, проходящие через исходный
узел, т. е. позволяет исключить путь (b
i,i
, b
i,j
), изображенный на рис.
3,б. Полученная таким способом модернизированная матрица длин Г
= ||g
i.j
|| умножается на дистанционную матрицу D с использованием
тех же операций, что и ранее. При умножении матрицы Г на матри-
цу D образуется матрица D = ГD, элементы которой используются
для получения дисперсионных матриц (т. е. матриц величин второ-
го и т. д. кратчайших путей). Каждый элемент матрицы D = || d
i,j
||
имеет вид:
,,11,,22,,,,,
min ( );( ); ... ( ); ... ( ).
ij i j i j ii ij iN Nj
k
dd d d12 34 34 34 3 4
(8)
В выражении (8) min означает, что минимум может браться для
кратчайшего пути (k = 1), второго по длине пути (k = 2) и т. д. Каждый
из членов (g
i,e
+ d
e,j
) = ¥ в выражении (8) определяет длину пути от
узла i к узлу j ,если первым транзитным узлом после узла i на пути к
узлу j будет узел e, e Î (1,…, N). Если узел e не является соседним
узлом i, то
(g
i,e
+ d
e,j
) = ¥.
Так как g
i,i
= ¥, член (g
i,i
+ d
i,j
) будет всегда ¥. При этом элемент
(g
i,j
+ d
j,j
) не обязательно равен ¥. Таким образом, число членов выра-
жения (8), не равных бесконечности, равно числу n соседних УК, т. е.
числу исходящих из УК направлений (ветвей).
Член выражения (8), имеющий минимальное значение и определя-
ющий длину кратчайшего пути от узла i к узлу j через узел e:
1
,ij
1 =
1
min |(g
i,1
+ d
1,j
);…(g
i,N
+ d
N,j
)|,
заносится в качестве элемента
1
,ij
1 в дисперсионную матрицу первого
выбора D
1
= ||
1
,ij
1 ||. Второй по значению член выражения (8), определя-
ющий длину второго по протяженности пути после кратчайшего от
узла i к узлу j:
2
,ij
1 =
2
min
|(g
i,1
+ d
1,j
);…(g
i,N
+ d
N,j
)|,
заносится в качестве элемента
2
,ij
1 в дисперсионную матрицу второго
выбора D
2
= ||
2
,ij
1 || .
При наличии n соседних узлов можно получить n дисперсионных
матриц D
1
,…, D
n
.
Рассмотрим пример расчета элементов матриц D (D
1
,D
2
,…).
Пусть сеть связи имеет вид, представленный на рис. 2.

Страницы