![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Формально это означает, что если справедливы утверждения вида
и в графе G(A, R\Lsf, W) не существует маршрута из s в f, то минимальный разрез графа G равен | Lsf |. Пусть для каждого ребра графа ТКС G задана своя пропускная способность, т.е. вес, определяемый некоторой неотрицательной величиной. Определение 7.2. Максимальным потоком из узла s в узел f ТКС называется максимальная мощность потока, которая может передаваться из s в f по графу G с учётом заданных пропускных способностей (весов) рёбер (каналов связи). Обозначим значение такого максимального потока через Vsf. Приведём для удобства дальнейших рассуждений известную теорему Форда-Филкерсона о связи минимального разреза и максимального потока [19]. Теорема 7 .1. Для любой ТКС с одним узлом-источником (т.е. узлом s, не имеющим входящих рёбер) и узлом-приёмником (т.е. узлом f, не имеющим исходящих рёбер) величина максимального потока от узла-источника к узлу-получателю равна величине минимального разреза. Основываясь на этой теореме, можно сформулировать критерий К-потоковой маршрутизации в виде следующей теоремы. Теорема 7.2. Пусть задан граф ТКС G = (A, R, W) и на нём определены два узла: узел-источник s и узел-получатель d. Тогда следующие два утверждения равносильны: 1) Пара узлов (s, f) является l -связной и не является (l+1) -связной. 2) Минимальный разрез графа G для пары (s, f) равен l. Доказательство. Пусть для каждой дуги графа ТКС G определена пропускная способность, равная единице. Выделим из графа G(A, R, W) подграф G(A, Rsf, W), содержащий только несамопересекающиеся маршруты от s к d. Заметим, что в G(A, Rsf, W) узел s не будет содержать входящих рёбер, а узел f не будет содержать исходящих рёбер. Это значит, что в этом подграфе можно определить поток из s в f. Поскольку пропускные способности всех рёбер равны 1, то максимальный поток через каждый маршрут из s в f тоже равен 1. Заметим, что максимальный поток из s в d равен максимальному числу непересекающихся маршрутов из s в f, т.е. значению связности в графе G(A, R, W) для пары узлов (s, f). Таким образом, утверждение 1) равносильно тому, что Vsf =l. C другой стороны, это утверждение равносильно 2). Тем самым теорема 7.2 доказана. 7.5.6. Алгоритм 2-потоковой маршрутизации и его оптимизация Алгорим 2-потоковой маршрутизации является частным случаем алгоритмов К-потокового распределения пакетов данных. В его основе лежит прокладка двух альтернативных маршрутов из каждого узла-источника к каждому узлу-получателю ТКС. Рассмотрим этот алгоритм подробнее. Целью алгоритма 2-потоковой маршрутизации является прокладка двух альтернативных маршрутов на каждом узле-источнике к каждому узлу-получателю ТКС. Поскольку альтернативный путь может выбираться на каждом узле маршрута от узла-источника к узлу-получателю, то выбор альтернативного маршрута можно свести к задаче определения альтернативного канала связи для пересылки пакетов данных к узлу-получателю на каждом узле-источнике ТКС. Таким образом, алгоритм 2-потоковой маршрутизации можно описать следующим образом [69]. Для каждого узла-получателя ai нужно выполнить следующие операции: 1) Определить множество всех узлов S1(ai), которые имеют с ним прямую связь; 2) Определить множество маршрутов R(ai) из всех узлов ТКС к узлу ai; 3) Проверить, существуют ли среди узлов из S1(ai) двунаправленные каналы связи и выбрать один из таких каналов как альтернативную связь для адресата ai; 4) Сохранить ai и взаимосвязанные узлы, объединённые каналом альтернативной связи, в списке 5) Проверить, связаны ли оставшиеся узлы из S1(ai) с одним из узлов, уже содержащимся в 6) Повторять шаг 5, пока все узлы не будут удалены из S1(ai); 7) Проверить каждый из оставшихся узлов в графе G, которые еще не являются частью 8) Повторять шаг 6, пока все узлы сети (кроме узла-получателя) не будут содержаться в После выполнения указанных операций алгоритма 2-потоковой маршрутизации в множестве R(ai) будут содержаться все альтернативные маршруты для каждого узла-источника к узлу-получателю ai. ТКС. Для обеспечения работоспособности описанного алгоритма необходимо выполнение следующего «триангуляционного» условия: каждый узел ai должен «формировать треугольник» связей с каждым из своих соседних узлов. Это означает, что если для узла ai есть соседний узел ak (
Предложенный алгоритм 2-потоковой марiрутизации пакетов данных позволяет повысить отказоустойчивость и надёжность маршрутизации (снизить риск «отказа» ТКС) при отказе (выходе из строя) одного или нескольких узлов или каналов связи ТКС с переменной динамикой (топологией). При определении оптимального альтернативного маршрута необходимо внести в предложенный алгоритм следующие изменения: 1) На втором шаге алгоритма в качестве множества R(ai) выбрать дерево кратчайших маршрутов к узлу ai от всех остальных узлов ТКС; 2) На третьем шаге алгоритма в качестве двунаправленного канала связи выбрать двунаправленный канал связи как оптимальный «в среднем», т.е. канал, минимальный по сумме стоимостей в каждом направлении; 3) На пятом шаге алгоритма выбирать узлы, которые связаны с 4) На седьмом шаге алгоритма выбирать такие узлы и такие каналы связи ТКС, что суммарная стоимость выбираемой пары смежных каналов связи ТКС будет минимальной на каждой итерации. 7.5.7. Методы централизованной и децентрализованной К-потоковой маршрутизации Основными недостатками однопотоковой маршрутизации пакетов данных в динамических ТКС с переменной структурой являются следующие её особенности: – неисправность или отказ хотя бы одного узла или канала связи ТКС, через которые проходит оптимальный или допустимый маршрут передачи пакетов данных, требуют трудоёмкого перепланирования (пересчёта) оптимального маршрута (или его части) с учётом неисправных узлов или каналов связи ТКС; – спланированный маршрут между любыми заданными узлом–источником и узлом-получателем ТКС может породить сетевые перегрузки в то время, когда другие (например, соседние) узлы и каналы связи могут быть свободными или недогруженными. Первый недостаток приводит к большим задержкам при управляемой передаче потоков данных, связанных с обновлением информации о состоянии ТКС и перерасчётом нового маршрута. Такие задержки (запаздывания) недопустимы для высококачественного QoS–обслуживания запросов пользователей ТКС или передачи мультимедийного трафика реального времени. Второй недостаток также приводит к задержкам из-за перегрузки узлов или каналов связи ТКС, входящих в оптимальный или допустимый маршрут. При этом сетевой трафик распределяется неравномерно, так что многие промежуточные узлы и каналы связи ТКС оказываются незагруженными или вообще не используются (хотя они более или менее свободны). Для преодоления трудностей, связанных с указанными недостатками, целесообразно использовать многопотоковую маршрутизацию. При этом планируется и одновременно используется не один (например, оптимальный) маршрут передачи пакетов данных, а К³ 2 маршрутов. Чем больше число маршрутов К, тем больше вероятность доставки пакетов данных от узла-источника к узлу-получателю ТКС. Вследствие этого увеличивается надёжность и отказоустойчивость глобальной ТКС. При централизованной многопотоковой маршрутизации осуществляется априорное планирование К³ 2 оптимальных или субоптимальных маршрутов по имеющейся фиксированной или обновлённой информации о состоянии ТКС. Параллельное использование этих непересекающихся маршрутов передачи пакетов данных обеспечивает более надёжную доставку пакетов от узла-источника к узлу-получателю ТКС. При этом сетевой трафик распределяется по ТКС более равномерно (сбалансированно). В результате снижается влияние возможных перегрузок в отдельных узлах или каналах связи ТКС. При децентрализованной (распределённой) маршрутизации в каждом последующем узле маршрута, начиная с узла-источника, планируется К³ 2 оптимальных или субоптимальных маршрутов передачи пакетов данных к узлу-получателю. Такой метод апостериорного планирования К-маршрутов “от достигнутого узла” требует специального механизма предотвращения циклов при передаче пакетов данных в глобальной ТКС. Главное достоинство метода апостериорной К-маршрутизации заключается в том, что она обеспечивает автоматический “обход” отказавших узлов или каналов связи ТКС как непреодолимых препятствий. Другое достоинство метода связано с локальным обнаружением отказавших узлов или каналов связи в результате мониторинга глобальной ТКС. Это позволяет быстро обновить информацию о текущем состоянии ТКС с переменной структурой (топологией) и внести необходимые коррекции в таблицы и карты маршрутизации.
|