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

UptoLike

ВУЗ: 

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

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

Рубрика: 

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

Страницы