Матрично-графовые модели компьютерных сетей

В математической теории и информатике граф – это совокупность объектов со связями между ними. Объекты представляются как вершины или узлы графа, а связи – как дуги или ребра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или ребрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. В частности, модели графов широко используются для анализа и синтеза процессов маршрутизации в компьютерных сетях.

Существует большое разнообразие задач, связанных с путями и маршрутами в графе, начиная отстандартныхзадачнасуществованиемаршрута и заканчивая задачами поиска путей, отвечающих определенным требованиям. Такими требованиями могут быть максимальность или минимальность длины маршрута, пропускной способности или надежности пути, требования ко множеству вершин, принадлежащих или не принадлежащих пути, и т.д. Для достижения таких требований большое значений имеют «внутренние» свойства графов – ориентированность, цикличность, взвешенность, топология и т.п.

Задача о существовании путей между вершинами графа и определение длины этих путей является основной для процессов маршрутизации. Для решения этой задачи рассмотрим простой орграф G = (V, E), V - множество вершин, E - множество ребер (дуг). Пусть v, и V j являются вершинами G: (v i , V j ) е G. На рис.1 приведен пример такого графа с 4-мя вершинами.

Рис.1. Пример графа с 4 вершинами

Введем в рассмотрение матрицу смежности А орграфа G [1]. Для рис.1 имеет место

⎡0 1 0 1⎤ 1 0 0 0⎥ A= ⎢⎢1 1 0 ⎥ 1⎥ ⎣0 1 0 0⎥⎦ данная матрица определяет наличие единичных путей (путей в одно ребро, в один «хоп» [2]). Матрица A2 = A х A определяет путевую матрицу [1] с путями двойной длины (2 хопа), при этом если оба элемента aik и akj равны 1, т.е. в графе имеется путь длины 2 из вершины vi через vk в вершину vj. Таким образом, aij(2) определяет число различных путей длины 2 из vi в vj . Аналогично диагональный элемент aii(2) указывает число циклов длины 2 в вершине vi для i = 1, 2, .… n. С помощью подобной аргументации легко показать, что элемент в i-ой строке и j-ом столбце матрицы А3 задает число путей длины 3 из vi в vj.

В общем случае для n > 1, n – целое, путевая матрица A n будет определяться выражением An = 1A х A x... x 3, при этом если сложить мат- n рицы А, А2, …, Аn, то получим матрицу

Вn = A + A2 + … + An, по которой можно определить число путей из vi в vj длины, меньшей или равной n.

Для определения достижимости вершины v_j из v_i необходимо выяснить, существует ли хотя бы один путь из v_i в v_j , причем длина этого пути произвольна. Решение этого вопроса с помощью матрицы смежности и путевых матриц оказывается достаточно трудоемким [1], поэтому целесообразно ввести в рассмотрение матрицу достижимости, которая определяет только существование пути, а не число путей между любыми двумя вершинами.

Матрица достижимости Р _n размера n × n задается выражением

Pn = Ь ] = 5У , здесь pij = 1, если существует путь из vi в vj , иначе pij = 0.

Матрицу достижимости легко получить из матрицы В_n , положив p_ij = 1, если элемент на пересечении i -ой строки и j -го столбца B_n не нулевой, в противном случае p_ij = 0. Например

n

a(2) = Е a * • as • к=1

Аналогично определяются матрицы A ³ и

A ⁴ : A ³ = A х A x A = A x A ² ; A ⁴ = A x A ³ ,

	⎜⎛3 3	5 3	0 0	3⎞ 2	⎟	⎜⎜⎛11	1 1	0 0	1⎞ 1
B 4 =	⎜ 6	8	0	5	⎟⎟, P 4 =	⎜⎜1	1	0	1
	⎜⎝2	3	0	1⎠	⎟⎟	⎜⎝1	1	0	1⎠

	⎡1	1	0	1⎤		⎡1	2	0	1⎤
A 3 =	⎢ 1	1	0	0	⎥ ⎥, A 4 =	⎢⎢ 1	1	0	1 ⎥⎥
	⎢2	2	0	1	⎥ ,	⎢2	3	0	2⎥
	⎣ 0	1	0	1⎦	⎥	⎢⎣ 1	1	0	0⎥⎦

Для каждого фиксированного k условие a ik × a _kj = 1 выполняется в том и только в том случае,

Метод вычисления путевых матриц путем определения, то есть вычисления А , А² , …, Аⁿ , а затем Вⁿ – весьма громоздок. Существует и другой метод, основанный на аналогичных идеях, но более эффективный [1], основанный на использовании булевых матриц, элементами которых могут быть 0 или 1.

Булева сумма и произведение булевых матриц А и В размера n × n также являются булевыми матрицами:

с = a v b , ij ij ij ,

n dу = V k=1

(ak л by)

для всех i,

j, k = 1, 2 ... n .

Матрица смежности, так же как и матрица достижимости, является булевой.

(2)                    ( r ) _ X ^{r - 1)}

При этом A = A ^л A , A = A ^л A , для всех r = 2, 3, …, n Единственная разница между А² и А⁽²⁾ состоит в том, что А⁽²⁾ – булева матрица и элемент на пересечении i -й строки и j -го столбца А⁽²⁾ равен 1 в том случае, когда существует по крайней мере один путь длины 2 из v_i в v_j . Из этих рассуждений следует, что матрица Р_n задается выражением

n

P n = A v A ⁽²⁾ V A ⁽³⁾ V ... V A ^{( n} ) = _V A ^{( k} ) .

k = 1

Например,

⎛0 1

A =

⎝0 1

⎛1 1

A ⁽³⁾ =

⎝0

00   01 ⎟⎟⎞

0     1 ⎟⎟,

0  0 ⎟⎠

00   01 ⎟⎟⎞

00    11 ⎟⎟⎟⎠

A ⁽²⁾ =

⎛1 1

0 0⎞

⎝1 0

⎛1 1

A ⁽⁴⁾ =

P ₄ = A v A ⁽²⁾ v A ⁽³⁾ v A ⁽⁴⁾ =

⎝1

01⎟

00   11 ⎟⎟⎞

00   01 ⎟⎟⎟⎠

⎛1 1 0 1⎞

⎝1 1 0 1⎠

Данный метод получения матрицы достижимости простого орграфа реализуется на ЭВМ

путем использования алгоритма, предложенного Уоршаллом [1; 10].

Задана матрица смежности А . Матрица достижимости Р_n вычисляется в результате следующих шагов.

• 1.    Инициализация. Установить Р := А .

• 2.    Итерация. Повторять шаги 3 и 4 при k = 1, 2, …, n .

• 3.    Обработка строк. Повторить шаг 4 при i = 1, 2, …, n .

4. Обработка столбцов. Повторять при j = 1, 2, „., n : установить р_ц : = p_ti v ⁽р_й л p_k] )

Трудоемкость этого алгоритма O( n³ ) (так как происходит пересчет по трем переменным k , i , j ).

Целью маршрутизации является планирование, оптимизация и адаптация маршрута передачи пакетов от источника запроса к получателю, которые в общем случае могут находиться в различных автономных подсетях глобальной телекоммуникационной системы (ТКС). Для достижения этой цели маршрутизатор должен обладать информацией о топологии и стоимости каналов связей, адресах узлов-источников и узлов-получателей данных, критериях оптимальности маршрутов и т.д. Решение этих проблем связано с группой задач «о кратчайших путях».

Большинство задач этого вида можно рассматривать как расширение, обобщение или модификацию следующей задачи.

Задача 1. В ориентированном графе G с матрицей весов W = [ w ij ] требуется найти путь между заданной парой вершин s и t , у которого сумма весов составляющих его дуг (ребер) минимальна. Здесь s и t являются соответственно начальной и конечной вершинами. Заметим, что для орграфа кратчайшие пути ( s, t ) и ( t, s ) в общем случае различны.

Любой участок кратчайшего пути сам является кратчайшим путем между парой его концевых вершин. Значит, если найден кратчайший (s, t) - путь, промежуточные вершины которого образуют множество V’ , то фактически решена задача отыскания кратчайших путей из s во все вершины множества V’ . Поэтому естественно обобщение сформулированной задачи.

Задача 2. Найти кратчайшие пути между заданной начальной вершиной s и всеми остальными вершинами графа.

Наконец, в самой широкой постановке задача выглядит так.

Задача 3. Найти кратчайшие пути между всеми вершинами графа (орграфа).

Определяющим в приведенных формулировках является количество пар концевых вершин, для которых следует найти кратчайший связующий путь: в первой задаче это одна пара, во второй ( n – 1) пара, а в третьей – C _n ² для простого графа или 2C _n ² для ориентированного [3].

Еще одна разновидность задачи возникает, когда для некоторой пары вершин кроме кратчайшего требуется найти еще ( k – 1) путей, длины которых составляют неубывающую последова-

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

В общем случае в теории графов элементы матрицы весов могут иметь как положительные ( w_ij > 0), так и отрицательные ( w_ij < 0) значения [4]. Наличие отрицательных значений существенно усложняет решение задачи поиска кратчайших путей. Задача становится еще более сложной, если в графе присутствуют циклы с отрицательным суммарным весом. Для задач маршрутизации отрицательные значения весов обычно игнорируются (исходя из практических соображений). В этом смысле, если выполняется так называемое правило треугольника [3]: w _y <  w k + w _kj , то задача становится существенно проще и фактически может рассматриваться как разновидность задачи поиска кратчайшего пути в графе с ребрами единичной длины.

Пусть Г(s) – множество вершин, являющихся концами дуг, выходящих из вершины s . Рассмотрим случай, когда веса всех дуг графа одинаковы. Не нарушая общности, можно считать, что для любой дуги w_ij = 1. Эффективное решение задачи получается с помощью простой процедуры, в результате которой каждая обработанная вершина получает пометку, равную расстоянию от s .

Процесс начинается с того, что все v е F(s) получают пометку, равную единице. На второй итерации все v е r ₂ (s) помечаются двойкой, затем все v е F 3 (s) помечаются тройкой, и вообще на i -й итерации для всех v е F(s) имеем l(v) = i , где l(v) – расстояние от вершины s до вершины v как длина пути.

Процесс завершается, когда помеченной оказывается вершина t . Описанная процедура расстановки пометок называется поиском в ширину. После того, как вычислена длина кратчайшего пути, можно найти сам путь, т.е. множество составляющих его дуг, или, что то же самое, последовательность проходимых вершин.

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

Формальная реализация такова:

• 1.    Каждой вершине v_i приписывается целое число T(v_i) – волновая метка (начальное значение T(v_i) = –1);

• 2.    Заводятся два списка OldFront и NewFront (старый и новый «фpонт волны»), а также пе-pеменная T (текyщее вpемя);

• 3.    OldFront: = {s}; NewFront: = {}; T(s): = 0; T: = 0;

• 4.    Для каждой из веpшин, входящих в OldFront, пpосматpиваются инцидентные (смежные) ей веpшины u_j, и если T(u_j) = –1, то T(u_j): = T + 1, NewFront: = NewFront + {u_j};

• 5.    Если NewFront = {}, то ВЫХОД(«нет решения»);

• 6.    Если t ∈ NewF ront (то есть одна из веp-шин u_j совпадает t), то найден кpатчайший пyть между s и t с T(t) = T + 1 промежуточными ребрами; ВЫХОД(«решение найдено»);

• 7.    OldFront: = NewFront; NewFront: = {}; T: = T + 1; goto (4).

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

Этот эффективный алгоритм имеет линейную сложность как по числу вершин, так и по числу ребер. Другие названия волнового алгоритма – поиск в ширину, алгоритм степного пожара [5].

Кратчайшие пути и в этом случае можно находить с помощью волнового алгоритма. А именно, пусть r – наибольший общий делитель весов ребер графа G (задача решается в целых числах). Преобразуем граф, заменив каждое из wij ребер (vi, vj) простой цепью, состоящей из ребер единичной длины. В полученном при этом графе G’ полностью сохраняются метрические соотношения, характеризующие расстояния между вершинами графа G. Вместе с тем G’ – это граф с ребрами единичной длины, для которого задача решается по описанной выше схеме. Очевидный недостаток такого подхода – высокая трудоемкость из-за весьма большой размерности графа G’. Действительно, число вершин (и ребер) в G’ больше, чем в G, на вели чину, равную   ∑ wij – m, где m – количество r (v, ,vJ )eE ребер исходного графа G. Поэтому используют более эффективные алгоритмы решения задачи. Это, например, алгоритм Дейкстры и алгоритм Флойда.

Это алгоритм поиска кратчайшего пути в орграфе с неотрицательными весами. Если граф не ориентирован, то можно рассматривать граф, который получается из данного заменой каждого неориентированного ребра { v_i, v_j } парой дуг ( v_i , v_j ) и ( v_j , v_i ) с весом, равным весу исходного неориентированного ребра. Если граф не взвешен, можно считать, что все ребра имеют один и тот же вес. Требуется найти кратчайший путь между вершиной s графа G и всеми остальными вершинами.

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

Корректность алгоритма состоит в следующем. Существенна положительность весов дуг. Пусть на некотором этапе А и В – множествa вершин с постоянными и временными пометками. В конце шага 2 всякая временная пометка – это длина кратчайшего пути между вершиной s и помеченной вершиной, проходящего только через вершины множества А . Но тогда для вершины x , помечаемой на шаге 2, – это длина кратчайшего пути из s в x . Действительно, если бы это было не так, то в В существовала бы вершина x’ , через которую проходит кратчайший путь из s в x . При этом за x’ можно взять такую вершину на этом пути, что все предшествующие x’ вершины пути лежат во множестве А . Пусть α и β – длины частей этого пути от s к x’ и от x’ к x . Так как веса всех дуг положительны, то α , β > 0. Так как этот путь кратчайший, то α + β <  l ( x ), но отсюда следует, что α = l ( x’ ) <  l ( x ). А это соотношение противоречит минимальности пометки x среди всех временных пометок вершин.

На каждой итерации работы алгоритма ровно одна временная пометка становится постоянной, поэтому алгоритм завершает работу не более чем за n итераций. На каждой итерации просматривается n вершин. Таким образом, трудоемкость алгоритма Дейкстры O ( n² ).

Реализация алгоритма:

• 1.    T = {s} – множество вершин, расстояние до которых уже найдено.

• 2.    Пока V \ T – не пусто (есть необработанные вершины).

Найти вершину t g V \ T с наименьшей пометкой D ( t ) – кратчайшее расстояние от источника до вершины t .

Перенести найденную вершину в множество обработанных: T = T ^ { t }.

Модифицировать пометки необработанных вершин через t .

Цикл по всем вершинам u g V \ T, смежным с t .

D ( u ) = min { D ( u ); D ( t ) + w_tu }, где w_tu – вес ребра ( t, u ).

Выделим теперь свойство задачи, которое допускает ее правильное решение описанным алгоритмом. Любая часть решения также является решением, то есть если s , v₁ , …, vn , f – кратчайший путь из s в f , то для любого i = 1; 2 … n путь s , v₁ , …, v_i является кратчайшим из s в v_i . Подобное свойство является одним из важнейших свойств метода, известного под названием динамического программирования [6].

«Динамическое программирование, в сущности, вычисляет решение для всех подзадач. Вычисление идет от малых подзадач к большим, ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж эта задача решена, ее ответ где-то хранится и никогда не вычисляется заново» [7].

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W [ w_ij ]. В конечном итоге получается матрица, элементы которой представляют собой вес минимального пути, соединяющего i и j вершины. Тем самым алгоритм обеспечивает решение задачи отыскания кратчайших путей для всех n ( n – 1) упорядоченных пар вершин орграфа и всех n ( n – 1)/2 неупорядоченных пар вершин простого графа даже при наличии дуг (ребер) с отрицательным весом. Единственным условием является отсутствие в графе контуров (циклов) с суммарным отрицательным весом. Более того, алгоритм позволяет выявить такие контуры.

Учитывая, что для получения результата следует выполнить n итераций, трудоемкость алгоритма можно оценить как O ( n ³) [9].

Задачу поиска кратчайшего пути в графе с отрицательными весами дуг решает алгоритм Беллмана-Форда, представляющий собой модификацию алгоритма Дейкстры. Модификация алгоритма Дейкстры состоит в следующем:

• 1.    На шаге 2 пересчет величин l ( v_i ) с помощью выражения l (v i ) = min { l (v i ), l (v j ) + w(v i , v j ) } производится для всех вершин, а не только для

• 2.    Если для некоторой помеченной вершины v_i происходит уменьшение величины l ( v_i ), то с этой вершины и инцидентной ей помеченной дуги пометка снимается.

• 3.    Процедура заканчивается, когда все вершины помечены и когда после выполнения шага 2 ни одно из чисел l ( v_i ) не меняется.

непомеченных или временно помеченных. Следовательно, числа l ( v_i ) могут уменьшаться как для непомеченных, так и для помеченных вершин.

Трудоемкость алгоритма O ( n³ ) [8].

Алгоритм Беллмана-Форда не решает задачи поиска кратчайшего пути при наличии в исходном графе контура, имеющего отрицательный суммарный вес.

Для обнаружения контура отрицательной длины можно обычным способом применять алгоритм Беллмана-Форда, но в процессе его работы необходимо учитывать, сколько раз помечаются отдельные вершины. Как только число пометок какой-либо вершины достигает n , где n – число вершин графа, процедуру можно остановить: исходный граф содержит контур отрицательного суммарного веса.

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

Пусть в ациклическом орграфе с матрицей весов ( w_ij ) вершины пронумерованы так, что для любой дуги ( v_i , v_j ) выполняется отношение i <  j , то есть дуга всегда направлена от вершины с меньшим индексом (номером) к вершине с большим индексом (номером).

Подобная нумерация всегда может быть выполнена на основе порядковой функции графа. Требуется найти кратчайший путь из s в t . Как и в случае алгоритма Дейкстры, фактически отыскиваются кратчайшие пути до всех вершин графа.

Длина кратчайшего пути l ( v_j ) до вершины v_j легко находится, если известны длины кратчайших путей до всех вершин v , е Г - (v j ), т.е. вершин, являющихся началами дуг, входящих в вершину v_j .

При этом / (v j ) = min ^[ l (v , ) + w j ] , и |Г ( v j ) <  j , так как при' используемой системе нумерации вершин число входящих дуг для любой вершины всегда меньше, чем ее индекс (номер) [3].

Полагая l ( s ) = l ( v₁ ) = 0, на первой итерации получаем, что l ( v₂ ) = l ( v₁ ) + w₁₂ = w₁₂ , так как вторая вершина может иметь лишь одну входящую дугу. На второй итерации получаем l ^{( v} з ) = min [ l ^{( v} i ) ⁺ w i ₃ ] (не более двух вхо-

V i е Г ^- ( V 3 )

дящих дуг). Затем l ( v ₄ ) = min [ l ( v i ) + w i ₄ ] (не v j E Г — ( ^v 4 )

более трех входящих дуг) и т.д., пока не будет получена длина кратчайшего пути для s .

Трудоемкость первого этапа равна O ( m ), поскольку необходимо просмотреть все ребра, а трудоемкость второго – O ( n ), так как, в худшем случае, кратчайший путь может включать все вершины графа.

Классификация алгоритмов

Автор	Решаемая задача		Слож ность (трудоемкость)
	Определение матрицы достижимости	Поиск кратчайших путей
Уоршалл	+	-	O(n 3 )
Ли (волновой)	-	+	O(n)
Дейкстра	-	+	O(n 2 )
Флойд	-	+	O(n 3 )
Беллман- Форд	-	+	O(n 3 )

Таким образом, для того, чтобы выяснить, существуют ли в данном графе пути, то есть для поиска путевой матрицы, применяется алгоритм Уоршалла, имеющий сложность O ( n ³) и достаточно простую программную реализацию. Для того, чтобы найти путь между двумя заданными вершинами графа (орграфа), количество промежуточных вершин (и, соответственно, ребер) в котором минимально (то есть кратчайший путь), можно использовать волновой алгоритм поиска в ширину. Его недостаток – не учитываются веса ребер. Трудоемкость этого алгоритма линейная, программная реализация проста. Если требуется найти кратчайший путь между двумя заданными вершинами графа с учетом весов ребер, можно использовать либо алгоритм Дейкстры, имеющий трудоемкость O ( n ²) , но очень простую реализацию, либо алгоритм Форда. Кроме того, последний обладает возможностью выявить наличие отрицательных циклов и ребер с отрицательными весами и имеет трудоемкость O ( n ³) .

Внутренний протокол маршрутизации rIP предназначен для сравнительно небольших и относительно однородных сетей и использует алгоритм Беллмана-Форда [11].

Протокол OSPf (алгоритм предложен Дейкстрой) является альтернативой rIP в качестве внутреннего протокола маршрутизации [11].

Для того чтобы обеспечить работу с большими и сложными сетями, в IGr P введены усовершенствования алгоритма Беллмана-Форда [11]:

• -    для описания путей вместо простой введена векторная метрика.Применение векторной метрики позволяет адаптировать систему с учетом различных видов сервиса.

• -    вместо выбора одного пути с минимальной метрикой информационный поток может быть поделен между несколькими путями с метрикой, лежащей в заданном интервале. Распределение потоков определяется соотношением величин комбинированной метрики. Используются маршруты с комбинированной метрикой меньше некоторого предельного значения M, а также с метрикой меньше V*M, где V – значение вариации M (обычно задается оператором сети).

• -    существуют определенные проблемы с вариацией. Трудно определить стратегию использования вариации V > 1 и избежать зацикливания пакетов.В современных реализациях V = 1.

• -    разработан ряд мер, препятствующих осцилляциям маршрутов при изменении топологии сети.

• 1.    Трамбле Ж., Соренсон П. Введение в структуры данных. М.: Машиностроение, 1982. – 784 с.

• 2.    Олифер В. Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. Изд. 3. СПб.: Питер, 2006. – 672 с.

• 3.    Домнин Л.Н. Элементы теории графов. Пенза: Изд. ПГУ, 2004. – 139 с.

• 4.    Оре О. Теория графов. М.: Наука, 1980. – 208 с.

• 5.    Чернобаев А. Алгоритмы решения некоторых теоретико-графовых задач. 2004. http://www. de.uspu.ru/Informatics/Metodes/DPP/F/02/1/ ergeal/ www.ergeal.ru/archive/cs/discra/index.htm/

• 6.    Беллман Р. Динамическое программирование. Пер. с англ. М., 1960. – 400 с.

• 7.    Ахо А., Хопкрофт Дж, Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. – 536 с.

• 8.    Поздняков С.Н., Рыбин С.В. Компьютерная математика», СПб: Изд. СПбГЭТУ ЛЭТИ, 2005. – 65 с.

• 9.    Тимофеев А.В., Сырцев А.В. Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой // Новые технологии. Прил. к журналу «Информационные технологии», № 8/2005. – 32 с.

• 10.    Warshall S.A. A Theorem on Boolean Matrices // J. ACM, №9, 1962.– Р.11-12.

• 11.    Семенов Ю.А. Telecommunication technologies – телекоммуникационные технологии. V 3.0, 2007. http://book.itep.ru/