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

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

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

Пути с разделенными связями – это такие маршруты, которые не имеют общих связей.

Рис. 7 Сети с разделенными связями и узлами

 

Пути ABCDE и AFGHE первой сети (а) имеют разделенные связи, а маршруты ABCDE и ABC – нет. Во второй сети (б) разделенными связями обладают пути STUWX и SUX. Пути с разделенными узлами – это такие пути, у которых нет общих узлов. Пути ABCDE и AFGHE сети (а) имеют разделенные узлы, а маршруты STUWX и SUX сети (б) – нет. Концепция разделенных путей важна при рассмотрении надежности сети. Два пути между узлами M и N в сети (в) разделены как по связям, так и по узлам, и если связь или узел в одном из соединяющих их маршрутов отказывают, то все еще существует доступный путь для передачи данных между этими двумя источниками. С другой стороны, между узлами M и P существует два возможных пути, но они не разделены по связям и узлам, так что если узел N или O или связь Q откажут, то никакого альтернативного пути существовать не будет и соединение прервется.

Надежность сети, т.е. ее способность противостоять отказу узла или связи, зависит от количества разделенных узлов или связей между узлами источника и адресата. Связность по звеньям между двумя узлами определяется как минимальное число звеньев, которые должны быть удалены, чтобы отсоединить источник от адресата.

Рис 8. Различные отсечения на образце сети

 

Например, минимальное число связей, которые должны быть удалены для отсоединения узла C от узла J, показанной, на рисунке равно 3. Это значение можно определить, проводя на графе отсекающие линии (cs1, cs2,...). Минимальным является то отсечение, которое пересекает самое малое число связей. Размер минимального отсечения – это число разделенных путей между узлами C и J, что и определяет их связность по звеньям.

Степень связности определяет относительную устойчивость сети. Существует несколько алгоритмов, которые отвечают на вопрос, имеет ли данная сеть связность, равную m. Пригодность используемого алгоритма зависит от скорости достижения им соответствующего заключения, которая зависит от размеров сети. Рассмотрим два таких алгоритма – Клейтмана и Ивена.

Алгоритм Клейтмана

1. Выберите любой узел N₁.

2. Убедитесь, что узловая связность узла N₁ со всеми другими узлами равна по крайней мере m.

3. Удалите узел N₁ и все его связи.

4. Выберите второй узел N₂.

5. Убедитесь, что узел N₂ имеет m-1 соединений со всеми другими узлами.

6. Удалите узел N₂ и все его связи.

7. Выберите третий узел N₃.

8. Убедитесь, что он имеет по крайней мере m-2 соединений со всеми другими узлами.

9. Повторяйте процедуру, пока не доберетесь до узла m, т.е. выберите узел N_m и убедитесь, что он соединен по крайней мере еще с одним узлом.

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

В качестве примера рассмотрим следующую сеть (рис. 9).

 

BA: BA, BCA, BEFA

BC: BC, BAC, BEDC

BD: BCD, BAFD, BED

BE: BE, BAFE,BCDE

BF: BAF, BCDF, BEF

 

Рис. 9 Пример алгоритма Клейтмана – первый шаг

 

Выберите любой узел, например, узел B и убедитесь, что между узлом B и всеми другими узлами этой сети существует m=3 путей с разделенными узлами. Так как это условие удовлетворяется, то удалите из сети узел B вместе с его связями. Выберите другой узел, например, D, и убедитесь, что между узлом D и всеми другими узлами имеется m=3-1=2 пути с разделенными узлами (рис. 10).

 

DA: DCA, DEFA

DC: DC, DFAC

DE: DE, DFE

DF: DF, DEF

 

Рис. 10 Пример алгоритма Клейтмана – второй шаг

 

Так как это условие удовлетворяется, то удалите из сети узел D вместе с его связями. Выберите другой узел, например, F, и убедитесь, что между узлом F и всеми другими узлами существует m=3-2=1 путь (рис. 11).

 

FA: FA

FC: FAC

FE: FE

 

Рис. 11 Пример алгоритма Клейтмана – третий шаг

 

Таким образом, связность равна по крайней мере 3.

Алгоритм Ивена

1. Пронумеруйте узлы от 1 до N.

2. Сформируйте подмножество из узлов с номерами от 1 до m, где m – искомая связность.

3. Проверьте, что каждый узел в этом подмножестве имеет по крайней мере m маршрутов с разделенными узлами к каждому из других узлов в этом подмножестве.

4. Если предыдущий шаг неуспешен, то связность – меньше m. Если успешен, то перейдите к следующему этапу.

5. Для каждого из оставшихся j узлов (m<=j<=N) сформируйте подмножество узлов (L), содержащее набор, заданный в шаге 1 (размер m), увеличенный на число узлов из множества J.

6. Добавьте к сети новый узел X и соедините его с каждым узлом множества L. Проверьте, что между узлом X и каждым узлом j существует по крайней мере m маршрутов с разделенными узлами. Затем добавьте к множеству L узел j, удаленный из множества J, и продолжите процедуру со следующим узлом j.

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

В качестве примера выберите m=3 узлам (B, E и F) и подтвердите, что в этом множестве между каждой парой узлов имеется m=3 путей (рис. 12).

 

BE: BE, BAFE, BCDE

BF: BAF, BCDF, BEF

EF: EF, EDF, EBAF

 

 

Рис. 12 Пример алгоритма Ивена – первый шаг

 

Добавьте к сети новый фиктивный узел X и соедините его с узлами B, E и F. Выберите другой узел – C, и подтвердите, что между C и новым узлом X имеется m=3 путей (рис. 13).

 

CX: CBX, CAFX, CDEX

 

 

Рис 13. Пример алгоритма Ивена – второй шаг

 

Присоедините C к фиктивному узлу X. Выберите другой узел, A, и подтвердите, что между A и новым узлом X имеется m=3 путей (рис. 14).

 

AX: ABX, ACX, AFX

 

 

Рис. 14 Пример алгоритма Ивена – третий шаг

 

Присоедините A к фиктивному узлу X. Выберите другой узел – D и подтвердите, что между D и новым узлом X имеется m=3 путей (рис. 15).

 

DX: DCX, DFX, DEX

 

Рис 15. Пример алгоритма Ивена – четвертый шаг

 

Таким образом, связность равна по крайней мере 3.

 

Задания

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

Рис. 16 Сетевая диаграмма для расчета связности сетей

 

	A	B	C	D	E	F	G	H	I	J
A
B
C
D
E
F
G
H
I
J

Рис. 17 Табличная диаграмма для расчета связности сетей

Контрольные вопросы

1. В чем заключается связность сети?

2. Какие алгоритмы для проверки связности вы знаете? Рассмотрите один из алгоритмов.

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

Маршрутизация

 

Цель работы

Научиться определять оптимальные маршруты в сети и строить таблицы маршрутизации.