Локальные каталоги узлов ТКС

Рис.6.2. Пример каталогов маршрутов и узлов ТКС при фиксированной оптимальной маршрутизации

6.2.2. Метод лавинной маршрутизации

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

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

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

Недостатком алгоритма является чрезвычайно высокая нагрузка на сеть, что приводит к снижению эффективности её работы и к высокой вероятности её перегрузки. К достоинствам алгоритма можно отнести его вычислительную «дешевизну» и высокую надёжность (доставка пакета даже в том случае, если некоторые узлы сети вышли из строя), что делает его применимым в нестабильных сетях, либо при широковещательных запросах (или сообщениях), поскольку пакет получают практически все узлы прямо или косвенно связанные с узлом-источником. Кроме того, алгоритм может применяться в качестве эталона для тестирования других алгоритмов маршрутизации (поскольку при лавинной маршрутизации будут задействованы все допустимые маршруты от узла-источника к узлу-получателю, то, по крайней мере, один из них окажется кратчайшим). Этот метод можно использовать для построения графа допустимых маршрутов G(s, f, w) для любых s и f, а затем к этому графу применить алгоритм Дейкстры.

6.2.3. Случайная маршрутизация

Случайная маршрутизация является модификацией лавинной маршрутизации и позволяет существенно сократить накладные расходы сетевых ресурсов. При случайной маршрутизации на каждом узле, осуществляющем ретрансляцию, для всех пар «узел, приславший пакет»-«узел-получатель» определяется вектор распределения вероятностей P. Значения элементов вектора P соответствуют вероятностям пересылки пакета по тому или иному исходящему каналу связи ретранслирующего узла.

Таким образом, длина вектораP равна числу этих каналов. Вектор Р обладает двумя свойствами:

1) , где P_i – значение i-го элемента вектора;

2) если j-й элемент вектора P соответствует узлу, приславшему пакет, то P_j =0;

Остальные значения можно рассчитывать разными способами. Например,

, (6.1)

где P_i – вероятность выбора канала i; R_i – скорость передачи данных по каналу i.

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

6.2.4. Остовная оптимальная маршрутизация в симметричных сетях

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

Постановка задачи оптимальной маршрутизации пакетов данных в статических (фиксированных) ТКС для остовного алгоритма следующая. Пусть статическая модель ТКС представлена графом G(A, R, W) и задана пара узлов, первый из которых является узлом-источником, а второй – узлом-получателем. Требуется найти маршрут передачи пакетов данных из s в f минимальной стоимости.

Так как любой подмаршрут оптимального маршрута является оптимальным, то для решения задачи оптимальной маршрутизации достаточно построить дерево кратчайших маршрутов для каждого узла-источника. В случае симметричных статических ТКС, у которых веса каналов связи (рёбер графа) одинаковы в обоих направлениях и не изменяются с течением времени, любое дерево кратчайших маршрутов для одного узла будет деревом кратчайших маршрутов для всех остальных узлов. Это означает, что в симметричных ТКС задача оптимальной маршрутизации сводится к задаче построения остова минимальной стоимости, т.е. максимального связного подграфа T графа G, не содержащего циклов, сумма стоимостей рёбер которого минимальна.

Рассмотрим алгоритм построения такого остова.

Работа алгоритма:

Алгоритм выполняется итеративно за конечное число шагов. Сначала выбираем произвольный узел и полагаем, что

T =({ s }, Ø, W). (6.2)

Шаг алгоритма: выбираем ребро с минимальным весом такое, что его начальный узел, принадлежит графу T, а конечный узел – не принадлежит T, и добавляем его вместе с конечным узлом в T, т.е.

. (6.3)

Алгоритм выполняется до тех пор, пока в T не войдут все вершины графа G.

Теорема 6.1. Граф T, построенный по остовному алгоритму, будет остовом минимальной стоимости графовой модели G симметричной статической ТКС.

Для доказательства этой теоремы потребуется следующая лемма [69].

Лемма 6.1. Для любого узла a_i Î A графа G(A, R, W) симметричной ТКС инцидентные ему рёбра (a_i, a_j)Î R минимальной стоимости содержатся в графе T вида (6.2), (6.3).

Доказательство леммы 6.1. При построении графа T возникает два случая, когда на очередном шаге алгоритма существует возможность включения ребра (a_i, a_j) в T:

1);

2).

Рассмотрим первый случай. Так как a_i принадлежит T, то либо a_i = s (тогда согласно (6.3) ребро (a_i, a_j) будет включено в T на первом шаге), либо на каком-то шаге узел a_i включен в T вместе с ребром, чья стоимость, с одной стороны, меньше стоимостей всех остальных рёбер, которые не принадлежат T и инцидентны узлам, входящим в T, а, с другой стороны, – больше, чем стоимость ребра (a_i, a_j). Тогда из (6.3) следует, что ребро (a_i, a_j) будет включено в T на следующем шаге.

Во втором случае будем рассматривать шаг алгоритма, на котором в T будет включен узел a_i. Согласно (6.3) этот узел войдет в T вместе с ребром (a_i, a_j), так как его стоимость среди всех инцидентных a_i рёбер – минимальна.

Таким образом, лемма 6.1 доказана.

Доказательство теоремы 6.1. Так как граф G симметричной ТКС – связный, то на каждом шаге алгоритма множество рёбер, начало которых принадлежит T, а конец – нет, будет непустым. Таким образом, процесс построения не закончится, пока в T не войдут все вершины графа G.

Так как на каждом шаге алгоритма к графу T добавляется по одному узлу и одному ребру, а в начале он содержит только один узел и одно ребро, то в конце он будет состоять из N узлов и N-1 ребра (где N – число узлов в графе G). Это означает, что T будет остовом графовой модели G ТКС. Докажем, что его стоимость будет минимальной.

Рассуждая от противного, предположим, что существует остов T¹ такой, что сумма весов его рёбер меньше суммы весов рёбер остова T. Тогда справедливо соотношение

. (6.4)

Однако это соотношение противоречит утверждению леммы 6.1. Следовательно, соотношение (6.4) неверно и стоимость T действительно минимальна.

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

Пример работы алгоритма приведен на рис.6.3., где остов с минимальной стоимостью выделен жирными линиями.

Рис. 6.3. Пример симметричного графа с построенным в нем остовом минимальной стоимости.