![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Оптимальная маршрутизация для всех пар узла сети
Для статических ТКС, в которых планирование оптимальных маршрутов производится одновременно для разных пар узлов, особую роль играет алгоритм Флойда [3]. Этот алгоритм вычисляет маршруты минимальных стоимостей между всеми парами узлов ТКС. Пусть узлы графа G(A, R, W) проиндексированы, т.е.. Лемма 6.2. Пусть dk (ai, aj) – минимальная стоимость маршрутов из ai в aj, причем индексы промежуточных узлов ТКС не превосходят k. Тогда . (6.5) Доказательство леммы 6.2. Рассмотрим все маршруты из ai в aj, где индексы промежуточных узлов не превосходят k+1. Кратчайший среди них маршрут либо содержит вершину ak+1, либо нет. Во втором случае, так как вершина ak+1 роли не играет, то кратчайший маршрут остается тем же, что и при k, и поэтому dk+1 (ai, aj)= dk (ai, aj). В первом случае маршрут можно будет разбить на два подмаршрута: из ai в ak+1 и из ak+1 в aj. Поскольку индексы промежуточных узлов в этих маршрутах не превосходят k, то dk+1 (ai, aj)= dk (ai, ak+1)+ dk (ak+1 , aj). (6.6) Лемма 6.2 доказана. Таким образом, рекуррентный алгоритм Флойда представляет собой последовательное вычисление по формуле (6.5) стоимостей и определение группы оптимальных маршрутов между всеми парами узлов ТКС. Таким образом, верно следующее равенство: . (6.7) Замечание. При настройке таблиц маршрутизации в ТКС удобно пользоваться следующим представлением маршрутов: P=PN× N={ tij }, где значение tij является индексом следующего (второго) узла кратчайшего маршрута из ai в аj. Тогда программная реализация алгоритма Флойда может выглядеть следующим образом:
Begin for i: =1 to N do for j: =1 to N do Begin d(ai, aj): =W(ai, aj); tij = j; End for k: =1 to N do for i: =1 to N do for j: =1 to N do if d(ai, aj) > d(ai, aj)+ d(ai, aj) then Begin d(ai, aj): = d(ai, ak)+ d(ak, aj); tij = tik; End End. Сложность алгоритма Флойда характеризуется величиной O(N3). 6.3. Методы оптимальной много-адресной маршрутизации потоков данных 6.3.1. Много-адресный алгоритм Беллмана-Форда Алгоритм Беллмана-Форда является распределённым алгоритмом оптимальной много-адресной маршрутизации [4]. Его идею можно сформулировать следующим образом: найти оптимальные маршруты передачи данных от данного узла-источника к остальным узлам. Алгоритм выполняется итеративно на каждом узле сети. На каждой итерации алгоритма вычисляются оптимальные маршруты от узла-источника до остальных узлов, причём число составляющих их рёбер не превосходит номер итерации. Это означает, что на первом шаге будут определяться кратчайшие однозвенные маршруты, на втором – кратчайшие маршруты, содержащие не более двух звеньев, на третьем – не более трёх и т.д. Рассмотрим описание алгоритма для конкретного узла. Пусть даны: G(s, f, w) – ориентированный граф;
h – номер итерации (то есть, рассматриваются маршруты, содержащие не более h каналов связи); Lh(j, v) – стоимость кратчайшего маршрута от узла j до узла v, содержащего не более h каналов связи. Требуется построить оптимальные маршруты от узла-источника s0 до остальных узлов и вычислить их стоимости. Работа алгоритма: 1. Инициализация.
Lh (s0, s0)=0 для всех h; 2. Итерация. Для каждого узла
Новый маршрут до узла v получается из кратчайшего маршрута от узла j до узла v, на котором достигается минимум 6.3.2. Много-адресный алгоритм Дейкстры Алгоритм Дейкстры используется для построения деревьев кратчайших маршрутов от узла-источника ко всем остальным узлам и выполняется итеративно. На каждой итерации алгоритм определяет кратчайший маршрут до ближайшего из необработанных узлов (то есть, до узла, стоимость кратчайшего маршрута до которого не больше стоимостей кратчайших маршрутов от узла-источника до других узлов), после чего данный узел считается обработанным алгоритмом. Изначально все узлы, кроме узла-источника, считаются необработанными. Алгоритм состоит в следующем. Пусть даны: G(s, f, w) – ориентированный граф,;
L(j) –если Требуется построить дерево кратчайших маршрутов от узла-источника s0 до остальных узлов и вычислить их стоимости. Работа алгоритма: 1. Инициализация. T1 - пусто, T1 ={ s0 }, т.е. вначале множество обработанных узлов состоит только из узла-источника. Узлу-источнику сопоставляется пустой маршрут. L (n)= w(s0, n) для 2. Шаг алгоритма. Берём из T1 узел с минимальной оценкой стоимости маршрута и помещаем его в T0 ( а также обозначаем соответствующий ему маршрут как кратчайший ). Иными словами, находим
При этом рассматриваем все рёбра с начальным узлом x. Для каждого ребра (x, j) выполняется одно из трёх действий: А) если Б) если
а также маршрут, состоящий из кратчайшего маршрута до x и ребра (x, j). В) если
и узлу j сопоставляется соответствующий оценке маршрут (либо прежний, либо как в Б)). Итерации повторяются до тех пор, пока T0 не станет равно s. По окончании работы алгоритма для каждого узла x будет определен кратчайший маршрут к нему от узла-источника, а значение L(x) будет соответствовать стоимости этого маршрута. Алгоритм Дейкстры имеет сложность O(N2), где N – число узлов в ТКС. 6.4. Особенности маршрутизации в динамических компьютерных сетях Необходимость в адаптивной маршрутизации (АМ) возникает при непредсказуемых изменениях структуры (узлов и каналов связи) и параметров (весов) ТКС или при перегрузке буферов узлов или каналов связи ТКС. По существу речь идёт о маршрутизации в динамических (нестационарных) глобальных ТКС с переменной структурой. Причинами изменения структуры ТКС могут быть как добавление или отказ (выход из строя) отдельных узлов и каналов связи, так и сетевые перегрузки, препятствующие передаче потоков данных по запрещённым (перегруженным) узлам и каналам. Поэтому маршрутизаторы должны планировать и корректировать оптимальные маршруты передачи пакетов данных, адаптируя их к возможным изменениям ТКС, происходящим в реальном времени. Для этого необходима обратная связь о текущем состоянии узлов и каналов связи ТКС, которая может быть организована путём обмена информацией между узлами ТКС. Отличительными чертами адаптивной маршрутизации по сравнению со статической или динамической маршрутизацией являются следующие особенности: - алгоритмы адаптивной маршрутизации требуют учёта и обработки текущей информации о реальном состоянии ТКС, что делает их более сложными и увеличивает время определения оптимального маршрута; - передача информации о состоянии или структурных изменениях в ТКС к адаптивным маршрутизаторам дополнительно загружает сеть и приводит к задержкам (запаздыванию); - увеличение сетевой нагрузки и времени запаздывания может приводить к колебаниям или автоколебаниям и увеличению числа шагов при определении оптимального маршрута. Адаптивная маршрутизация потоков данных в глобальных ТКС имеет ряд преимуществ по отношению к неадаптивной (статической или динамической) маршрутизации, а именно: - обеспечивает работоспособность и надёжность ТКС при непредсказуемых изменениях их структуры или параметров; - приводит к более равномерной загрузке узлов и каналов связи ТКС за счёт «выравнивания» нагрузки; - упрощает управление передачей потоков данных и облегчает адаптацию к сетевым перегрузкам; - увеличивает время безотказной работы и производительность ТКС при высоком уровне предоставляемых услуг в непредсказуемых условиях изменения сетевых параметров и структуры, что особенно важно для агентов-пользователей ТКС. Достижение этих преимуществ в значительной степени зависит от используемых принципов и алгоритмов адаптивной маршрутизации потоков данных в ТКС с непредсказуемо изменяющейся структурой и заранее неизвестным трафиком. Как отмечается в 6-ом издании монографии [1], «адаптивная маршрутизация – это задача, которую весьма трудно решить должным образом. Доказательством этого может служить тот факт, что наиболее крупные сети с пакетной коммутацией (такие, как ARPANET и её «наследники», TYMNET и сетевые архитектуры IBM и DEC) неоднократно претерпели значительные изменения принципов маршрутизации». Принципы алаптивной маршрутизации можно разбить на три класса в зависимости от используемой информации о реальной (текущем) состоянии ТКС, т.е. от характера сигналов обратной связи: - локальная информация (обратная связь) от одного узла ТКС; - локальная информация (обратная связь) от узла и его «соседей» в ТКС; - глобальная информация (обратная связь) от всех узлов ТКС; Простейший принцип адаптивной маршрутизации с локальной обратной связью от одного узла заключается в том, что пакет данных передается в канал связи с самой короткой очередью или с наибольшей вероятностью предпочтительности канала. При этом может происходить локальное выравнивание нагрузки в выходных каналах ТКС. Однако в этом случае возможно отклонение от оптимального маршрута. Более эффективные принципы адаптивной маршрутизации основываются на передаче в начальный узел локальной информации (обратной связи) от соседних узлов или глобальной информации от узлов ТКС. В качестве такой информации могут использовываться, например, данные об отказах или задержках в узлах или каналах связи в ТКС. В зависимости от используемых способов обработки локальной или глобальной информации (обратной связи) принципы адаптивной маршрутизации можно разбить на три класса: - централизованная (иерархическая одноуровневая) маршрутизация; - децентрализованная (распределённая) маршрутизация; - мульти-агентная (много-адресная) маршрутизация. Принцип централизованной маршрутизации (ЦМ) заключается в том, что каждый узел ТКС сначала передает информацию о своем состоянии (задержки или пропускные способности выходных каналов и т.п.) центральному узлу-маршрутизатору. Затем этот маршрутизатор вычисляет оптимальный маршрут на основе полученной глобальной информации о текущем состоянии м передает его обратно всем узлам ТКС. После этого начинается управляемая передача пакетов от узла-источника к узлу-получателю ТКС по спланированному оптимальному маршруту. Принцип децентрализованной маршрутизации (ДМ) основывается на распределённом обмене локальной информацией между узлами ТКС и использовании этой информации о текущем состоянии узлов и каналов связи ТКС для вычисления оптимального маршрута. По мере вычисления последовательных участков этого маршрута осуществляется распределённо-управляемая передача пакетов от узла-источника к узлу-получателю ТКС. Принцип мульти-агентной маршрутизации (МАМ) является своеобразным компромиссом между принципами централизованной и децентрализованной маршрутизации [29, 69]. Он основывается на многоадресной маршрутизации и анализе возможных сетевых конфликтов с целью их предотвращения или разрешения в процессе управляемой передачи пакетов по множеству оптимальных маршрутов от узлов-источников к узлам-получателям. Более подробно принцип и конкретные методы мульти-агентной маршрутизации будут рассмотрены в следующем разделе.
|