ГЛАВА 2
ФОРМИРОВАНИЕ ВИРТУАЛЬНОЙ СТРУКТУРЫ КОРПОРАТИВНОЙ СЕТИ
2.1. Формирование дерева доставки сообщений
Компьютерная сеть представлена в виде нагруженного графа G(V, E), где V= { vi
зi=1,2…m}- множество вершин графа, E={ei,j зi,j=1,2…m} – множество ребер графа.
Каждое ребро ei,j графа характеризуется весом wi,j. При рассмотрении вопросов
маршрутизации под весом wi,j ребра ei,j будем подразумевать задержку ti,j
единицы информации между узлами vi и vj сети. В данном случае в качестве
ограничения вводится значение допустимой задержка td доставки единицы
информации между произвольными узлами сети, а в качестве параметра оптимизации
рассматривается суммарная задержка Ts,r на пути Ls,r. В данном случае задача
маршрутизации состоит в нахождении пути L(vs,vr)= (es,i, …, ej,r) между
вершинами vs и vr для которого выполняется условие:
. (2.1)
где: Ts,r - суммарная задержка на пути L(vs,vr).
В качестве ограничения на включение ребра ei,j в состав пути Ls,r
рассматриваются условия:
* C(i,j)> cs, где: C(i,j) - значение пропускной способности канала; cs -
требуемое значение пропускной способности для доставки сообщений по пути Ls,r.
* td >tm , где: td – значение допустимой задержки передачи пакетов; tm –
максимальная задержка передачи пакетов между узлами дерева передачи данных.
При решении этой задачи используется алгоритм нахождения кратчайших путей. В
настоящее время при определении кратчайших путей на графе используется ряд
алгоритмов [57]. В работе [58] приведена сравнительная оценка временной
сложности алгоритмов маршрутизации. Показано, что наименьшей временной
сложностью при разряженных графах обладает алгоритм Дейкстры.
В соответствие с двухуровневой структурой корпоративной сети граф G=(V, E)
может быть представлен в виде графа G0=(V0, E0), определяющего структуру
магистральной подсети, и некоторого множества подграфов {Gi=(Vi,Ei)зi=1,…,n},
соответствующего локальным подсетям корпоративной сети. Под граничными вершины
подграфов Gi=(Vi, Ei) будем подразумевать вершины vk для которых справедливо
условие: vkОVi($ ek,m , v mОV0).
Так на рис. 2.1 представлена структура графа G=(V, E) состоящая из подграфа G0
=(V0, E0), образованного множеством вершин V0 = {v6, v7, v8, v9, v10, v11, v12,
v14, v15, v19 }, и множества подграфов {Gi=(Vi, Ei) зi=1,…,5}. Причем, в
подграфе G1=(V1, E1) граничной вершиной является вершина v4, в подграфе G2=(V2,
E2) – вершина v13, в подграфе G3=(V3, E3) – вершина v17, в подграфе G4=(V4, E4)
– вершина v18, а в подграфе G5=(V5, E5) – вершина v5.
В компьютерных сетях граничным вершинам соответствуют граничные маршрутизаторы
или мосты.
В общем случае, для вершины vsОV1 подграфа G1 = (V1,E1) и вершины vrОV2
подграфа G2 = (V2,E2), а также граничных вершин vkОV1 ($ ek,i , v iОV0) и vmОV2
($ em,j ,vjОV0 ), путь L(vs,vr) определяется выражением: L(vs,vr) = L1(vs,vk)+
L0(vk,vm) + L2(vm,vr) . Соответственно суммарная задержка Ts,r пути L(vs,vr)
равна:
. (2.2)
Рис.2.1
При нахождении вершины источника или приемника внутри магистральной сети
соответствующее слагаемое в выражении (2.2) отсутствует. Например, при vsОV0
путь L(vs,vr) = L0(vs,vm) + L2(vm,vr), соответственно:
. (2.3)
При нахождении источника и приемника в одной локальной сети, т.е. при vsОV1 и
vrОV1 путь L(vs,vr) = L1(vs,vr) , а величина Ts,r равна:
. (2.4)
С учетом того, что скорости передачи информации в локальных подсетях, как
правило, выше скоростей передачи информации в глобальных сетях при L0(vs,vm) =
L2(vm,vr), где: L0(vs,vm) - длина пути на участке глобальной сети; L2(vm,vr) -
длина пути на участке локальной сети выполняется условие:
. (2.5)
При расположении источника и адресата в различных локальных сетях на
значительном удалении друг от друга: . В этом случае Ts,r » Tk,m и,
соответственно:
. (2.6)
Отсюда следует, что в данном случае основное внимание необходимо уделять
вопросам построения оптимального пути между граничными вершинами на графе
G0=(V0, E0).
Рассмотрим случай при котором АС1 постоянно располагается относительно вершины
v4, а мобильная АС2 перемещается вдоль пути
В соответствие с весом ребер (табл. 2.1) формируются пути между граничной
вершиной v4 подграфа G1(V1, E1) и граничными вершинами v13, v17 и v18,
соответственно подграфов G2(V2, E2), G3(V3, E3) и G4(V4, E4).
Путь L1(v4,v13) =10. Путь L2(v4,v17) =12 и путь L3(v4,v18) =11. Путь
L1(v4,v13)
проходит через вершины v4 – v8 – v12 –v13. Путь L2(v4,v17) включает вершины v4
– v7 – v11 –v14 –v17. Путь L3(v4,v18) проходит через вершины v4 – v7 – v9
–v18.
v4
v5
v6
v7
v8
v9
v10
v11
v12
v13
v14
v15
v17
v18
v19
v4
-
v5
-
v6
12
-
v7
5
v8
9
v9
-
v10
12
-
v11
0
10
v12
8
v13
10
v14
2
v15
-
v17
-
v18
-
v19
-
Таблица 2.1
На рис. 2.2. эти пути выделены жирными линиями. Пути L1(v4,v13) и L2(v4,v17)
полностью различны, так как не имеют общих ребер. Пути
- Київ+380960830922