kryl_vych_seti

Группа административных блоков (AUG) содержит группу AU с чередованием байтов полезной нагрузки. AUG занимает фиксированное положение в кадре STM-1.

Синхронные транспортные модули STM-N (N = 4,16) содержат N групп AUG и образуются путем мультиплексирования транспортных модулей более низкого порядка (STM-1 или STM-4 соответственно).

Эти модули снабжаются заголовками секции (Section on Overhead), в котором описывается способ кодирования и т. д. N групп AUG чередуются через 1 байт и находятся в фиксированном положении относительно начала цикла STM-N.

4.5. Доступ пользователей в сетях SDH

Доступ пользователей к сети SDH производится с помощью специально разработанного сетевого элемента, называемого мультиплексором ''вставить-выделить" – МВВ (Add/Drop Multiplexor – ADM). Это устройство выполняет функции кроссового коммутатора и является программно управляемым электронным устройством. Основное назначение данного узла – это вставка и выделение контейнеров.

Различают линейные (рис. 4.2, а) и кольцевые сети (рис. 4.2, б).

а)

TM

МВВ

МВВ

TM

б)

МВВ	МВВ	МВВ	МВВ

Рис. 4.2 Структурная организация сети SDH

В сети линейной структуры трафик пропускается по цепи, образованной соединенными между собой узлами. При этом вставка и выделение контейнеров может производиться на любом узле. Два концевых узла называются терминальными и используют терминальные мультиплексоры (ТМ). Промежуточные узлы образуются с помощью МВВ.

91

В сетях кольцевой структуры нет терминальных мультиплексоров. Кольцевые SDH-сети могут обладать повышенной надежностью. Для этого применяют два кольца (рис. 4.3). При этом передача информации осуществляется в противоположных направлениях. При повреждении кабеля один или оба сигнала будут иметь пониженный уровень. В каждом МВВ осуществляется сравнение уровней сигналов, и этот эффект будет заметен. В двух МВВ, находящихся по обе стороны от места повреждения, производится соединение оптических волокон путем преобразования оптических сигналов в электрические с дальнейшим соединением электрических цепей. Таким образом образуется однокольцевая структура. Такое самовосстановление имеет широкое распространение.

Повреждение колец

МВВ		МВВ

МВВ		МВВ

Перемычка в мультиплексорах

МВВ	МВВ

МВВ		МВВ

Рис. 4 .3. Принцип восстановления в кольцевых структурах SDH-сетей

Пример сети SDH на основе кольцевых структур с тремя уровнями иерархии приведен на рис. 4.4.

92

ЦКС		ЦКС

Третий

уровень

ЦКС

ЦКС

Второй

ЦКС

ЦКС

ЦКС

уровень

Первый

уровень

МВВ	34 Мбит/с	2 Мбит/с

Рис. 4.4. Сеть SDH на основе кольцевых структур

На третьем (старшем) уровне иерархии находятся центры коммутации сообщений (ЦКС) и магистральные каналы связи, обеспечивающие передачу информации на скоростях 622 Мбит/с – 2,4 Гбит/с.

На втором уровне иерархии находятся ЦКС и кольцевые структуры с МВВ, обеспечивающие скорость передачи 622 Мбит/с.

На самом нижнем (первом) уровне располагаются кольцевые структуры с МВВ, обеспечивающие скорость передачи 155/622 Мбит/с, к которым подключаются первичные (низкоскоростные) каналы связи.

При переполнении трафика в каком-либо из колец возможно его перераспределение и направление в другие менее загруженные кольца. Тем самым легко осуществляется гашение взрывного трафика, и сеть обеспечивает гарантированное время доставки информации.

93

5.МЕТОДЫ МАРШРУТИЗАЦИИ

ВВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ

5.1.Определение кратчайших путей по матричному методу и методу Флойда

Ознакомимся с методами определения кратчайших путей в интегрированных вычислительных сетях [6].

Распределение каналов и потоков информации на линии связи производится с учетом длины пути. Для оценки длины пути используются различные критерии:

число транзитных участков между взаимодействующими узлами коммутации (УК);

протяженность пути; качество тракта передачи; надежность передачи и т. д.

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

сего значением для других возможных путей.

Втеории потоков все методы выбора кратчайших путей основаны на утверждении о том, что если кратчайший путь μij от произвольного

УКi к УКj проходит через промежуточные УКi1 ,…, УКik (рис. 5.1), то кратчайшие пути μi1,j,…, μik,j от УКi1,…, УКik к УКj соответственно являются частями кратчайшего пути μi,j от УКi к УКj.

УКi

УКi,1

УКik

УКj

likj

li,j

Рис. 5.1. Пути между узлами коммутации

94

Если длина пути μi1, j равна Li1, j, то

Li,j = Li,i1 + Li1, j.

Так как μi,j является кратчайшим, то
Lε,i = min (lε,v + Lv,i ),	5.1)
v=i1,iN

где N – число узлов сети.

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

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

методы нумерации узлов; матричные методы.

Матричный метод определения кратчайших путей позволяет найти длины кратчайших путей между всеми узлами сети одновременно и основывается на применении операций над матрицами расстояний.

Структуру сети связи с указанием длин ветвей можно описать в виде матрицы расстояний (длин) непосредственных связей

L = lij1 .

Элемент lij1 определяет длину ветви βi,j.

Рассмотрим пример. Пусть сеть связи имеет вид, изображенный на рис. 5.2.

	30	B			15
A	20	15	15
			20		C
	20	D
15					20
	25			10	25

F	40
	E

Рис. 5.2. Пример коммуникационной сети связи

95

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

								A						B	C	D	E	F
A													0	30	∞	20	∞	∞
B												∞		0	15	15	∞	∞
L1 = C											∞ 15 0 20 25 ∞														.	(5.2)
D						20								15	20	0	∞	25
E												∞		∞	25	10	0	40
F								15						∞	∞	25	40	0

Элементы главной диагонали равны 0, так как принимается, что расстояние внутри узла равно нулю. Если между парой узлов отсутствует ребро, то соответствующий элемент матрицы равен бесконечности (∞).

Если между узлами i и j имеется дуга β1i, j , то элемент l1j,i также прини-

мается равным бесконечности, например, l1A,F = ∞ , тогда же l1F , A =15 .

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

Матрица расстояний непосредственных связей неориентированной сети всегда симметрична относительно своей главной диагонали. Для ориентированной сети (как в примере) она может быть нессиметричной.

Возведем матрицу L1 в квадрат L2 = L1 × L1. Тогда

N
li2, j = ∑li1,k ×lk1, j =li1,1 ×l1,1 j +li1,2 ×l2,1	j + +li1,N ×l1N , j .	(5.3)

k =1

Можно интерпретировать умножение как последовательное соединение ветвей, а сложение – как параллельное соединение ветвей.

Произведение li1,k ×lk1, j соответствует двухтранзитному пути (т. е.

пути, проходящему через две транзитных ветви сети) от узла ik к узлу j через узел k (рис. 5.3, а), а сумма, например, трех произведений

l1	×l1	+l1	×l1	+l1	×l1	– трем двухтранзитным путям (рис. 5.3, б).
i,i	i, j	i, j	j, j	i,k	k, j

96

а)	б)
	l1
	i,i
i	jj	li1, j
li1,j	lk1,j
	i		j
	k	li1, j	l1
			j, j
	l1		l1
	i,k		k, j

k

Рис. 5.3. Двухтранзитные пути

Произведения l1	×l1	и l1	×l1	, j	фактически соответствуют одно-
i,i	i, j	i, j	j

транзитным путям, так как длина пути (задержка) внутри УК (т. е.

li1,i и l1j, j ) не принимается во внимание.

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

li1,k ×lk1, j	будем иметь l1	+l1	.
	i,k	k, j

При наличии нескольких параллельных одно-двухтранзитных путей (см. рис. 5.3, б) для определения длины кратчайшего пути между узлами следует операцию сложения заменить операцией выбора из всех длин минимальной длины однодвухтранзитного пути, т. е. вместо (5.3) будем иметь

li2, j = min (li1,k +lk1, j )= min		(li1,1 +l1,1 j );(li1,2 +l2,1	j );...(li1,N +l1N , j )		.
k =1,...,N
Таким образом, элемент l2		матрицы L2 равен длине кратчайшего
i, j

пути от УКi к УКj среди всех однодвухтранзитных путей.

При возведении матрицы L1 в r-ю степень при использовании этих операций получим матрицу

Lr = Lr–1 × L1,

элемент которой

97

lir, j = min (lir,k–1 + lr1, j )= min (lir,1–1 + l1,1 j );(lir,2–1 + l1j,2 );...(lir,N–1 + l1N , j ) k =1,...,N

будет равен длине кратчайшего пути от УКi к УКj среди всех однодвух- и т. д. r-транзитных путей.

При наличии на сети N узлов коммутации число транзитных ветвей в пути без петель не может быть больше (N–1). Следовательно, может потребоваться вычисление матрицы Lr, у которой r ≤ N–1.

Для конкретной сети может оказаться, что при r < N–1

Lr = Lr−1.

(5.4)

Так как при равенстве (5.4) всегда выполняется равенство Lr+1 = Lr, вычисление матрицы более высокой степени прекращается, если в процессе вычисления матриц встретится равенство (5.4).

Матрица Lr–1 при выполнении условия (5.4) называется дистанционной матрицей и обозначается

D=Lr –1 = Lr =

di,j

.

(5.5)

Таким образом, элементы дистанционной матрицы равны длинам кратчайших путей между соответствующими узлами сети связи. Матрица D часто называется матрицей расстояний (длин, задержек).

Для рассматриваемого примера вычислим l2A,B

l	2	= min	(l1	+ l1	);(l1	+ l1	);(l1	+ l1	);(l1	+ l1	);
	A,B		A, A	A,B	A,B	B,B	A,C	C,B	A,D	D,B

(l1A,E + l1BE );(l1A,F + l1FB ) = min (0 + 30);(30 + 0);(∞ +15);(20 +15);(∞+ ∞);

(∞ + ∞ ) = min 30;30;∞;35;∞;∞ = 30.

Аналогично вычислим остальные элементы матрицы L2, получим

																A			B	C	D	E	F
A																			30	40	20	∞	45
B															35				0	15	15	40	40
L2 = 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	0

98

Аналогично

																	A			B	C	D	E	F
A																				30	40	20	65	45
B															35					0	15	15	40	40
L3 = 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	0

Затем

																A				B	C	D	E	F
A																				30	40	20	65	45
B															35					0	15	15	40	40
L4 = 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	0

Здесь L4 = L3, следовательно D = L3.

Рассмотренные методы позволяют определить длину кратчайшего пути, но не указывают те ветви, которые входят в этот путь.

Определение самого кратчайшего пути связано с некоторой дополнительной процедурой.

Если для определения длины кратчайшего пути применяется способ нумерации узлов, то при выполнении дополнительной процедуры учитывается свойство веса УКi. Это свойство заключается в том, что существует УКj, для которого выполняется равенство

Wi = li,j + Wj.	(5.6)
Отсюда следует, что
Wi – Wj = li,j .	(5.7)

99

Поэтому если выполняется условие (5.7), то кратчайший путь от УКi проходит по ветви βi,j. Переходя к УКj , находим следующую ветвь, для которой выполняется последнее условие и которая также входит в этот кратчайший путь. Так, шаг за шагом можно определить все ветви, образующие кратчайший путь.

Исключив затем кратчайший путь из рассмотрения, подобным образом определяются и другие пути от исходящего УКi к входящему УКj Данный метод выбора кратчайших путей от одного узла до всех остальных узлов называется методом Флойда.

При матричном методе определения кратчайшего пути дополнительно к дистанционной матрице на основе матрицы длин непосредственных связей составляется так называемая модернизированная матрица длин непосредственных связей Г, элементы главной диагонали которой в от-

личие от элементов li,j = 0 имеют значения li,j = ∞, где значком ∞ обозначена бесконечность. Таким образом, матрица Г легко может быть

получена по матрице L1.

Для рассматриваемого случая

A

B

C

D

E

F

A

∞

30

∞

20

∞

∞

B

∞

∞

15

15

∞

∞

Г = C

∞

15

∞

20

25

∞

.

D

20 15

20

∞

∞

25

E

∞

∞

25

10

∞

40

F

15 ∞ ∞ 25 40

∞

Замена элементаl1

на l1

= ∞ в матрице Г означает, что длина пути

i,i

i,i

в УКi принимается бесконечно большой. Это дает возможность не рассматривать все пути проходящие через исходный узел, т. е. позволяет исключить путь (βi,i, βi,j), изображенный на рис. 5.3, б. Полученная таким способом модернизированная матрица длин Г = ||γi.j|| умножается на дистанционную матрицу D с использованием тех же операций, что и ранее. При умножении матрицы Г на матрицу D образуется матрица

= ГD, элементы которой используются для получения дисперсионных

100