Критерий корректности распределяющих карт маршрутизации

Рассмотрим обычные РТМ и РКМ. Расширим РТМ и РКМ согласно (5.18) в следующем виде:

, (5.23)

. (5.24)

Назовём расширением карты маршрутизации T. Заметим, что такое расширение РКМ не приведет к изменению в распределении информационных потоков в ТКС.

Рассмотрим узлы и зафиксируем узел-получатель. Будем говорить, что узел a_k доминирует над узлом a_i по отношению к узл у a_j (в контексте карты маршрутизации T), если при управлении потоками данных, задаваемом РКМ T, существует такая совокупность потоков данных, при которой поток данных, направленный к узлу-получателю a_j узлом a_k, будет протекать через узел a_i. Обозначим это отношение доминирования соотношением

. (5.25)

Заметим, что отношение доминирования нетранзитивно, т.е., из соотношений

(5.26)

не следует, что

. (5.27)

В качестве примера рассмотрим граф, соответствующий некоторой ТКС, приведенный на рисунке 5.1. Пусть для него задана РКМ T. Рассмотрим таблицы маршрутизации из её расширения для узла-получателя a₅ = f

(5.28)

Из (5.28) видно, что

и. (5.29)

Однако при этом

. (5.30)

Будем говорить, что узел a_k транзитивно доминирует над узлом a_i по отношению к узлу a_j (в контексте карты маршрутизации T), если существует последовательность узлов вида

, (5.31)

такая, что для любых справедливо соотношение

. (5.32)

Обозначим такой тип доминирования следующим образом:

. (5.33)

Рассмотрим несколько свойств, связанных с отношениями доминирования и транзитивного доминирования узлов ТКС [69].

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

если, то. (5.34)

Докажем утверждение Леммы 5.1. Пусть доминирование узла a_k над узлом a_i проявляется при интенсивности потока x_k в a_k и x_i в a_i (будем рассматривать только этот один поток, направленный от a_k к a_j и проходящий через a_i, для которого из определений (5.15) и (5.16) следует, что x_i ≤ x_k). Тогда такое доминирование будет проявляться при любой интенсивности x> x_i в узле a_i. Это происходит в силу того, что всегда можно создать поток данных, направленный от a_i к a_j. Заметим, что любой поток от узла a_i к узлу-получателю a_j с интенсивностью x≥ x_i не может проходить через узел a_k, поскольку в этом случае появился бы циклический маршрут, что соответствовало бы существованию бесконечного маршрута и противоречило бы условию корректности РКМ.

Теперь докажем, что любой поток от узла a_i к узлу a_j с интенсивностью x< x_i не будет проходить через узел a_k. Действительно, если это не так, то такой поток с интенсивностью меньшей, чем x_i, будет протекать через a_k с интенсивностью, не превосходящей x_i, и, следовательно, не превосходящей x_k. Тогда можно создать новый поток от a_k к a_j с такой интенсивностью, чтобы суммарная интенсивность потоков на узле a_k была равна x_k. Оба эти потока будут проходить через a_i, что приведет к появлению циклических, а, значит, бесконечных маршрутов, что противоречит условию корректности РКМ. Таким образом, поток любой интенсивности, направленный от узла a_i к узлу a_j через a_k протекать не может, и, следовательно,

. (5.35)

Лемма 5.1. доказана. Из неё вытекает следующее следствие.

Следствие 5.1. В условиях леммы 5.1 для любого узла, отличного от узла-получателя, справедливо следующее соотношение:

. (5.36)

Лемма 5.2. Пусть выполнены условия леммы 5.1, задан узел-получатель и существуют три узла такие, что

, а (т.е.,). (5.37)

Рассмотрим потоки, направленные к узлу-получателю от узлов a_i и a_k. Пусть максимальная интенсивность таких потоков от a_k, при которой они будут протекать через узел a_m, равна x_k (если верхнего ограничения нет, то полагаем, что x_k = ∞), а минимальная положительная интенсивность, с которой проходят через a_k потоки от a_i равна x_i (если минимума нет, то в качестве значения x_i принимаем инфимум положительных значений). Тогда, следующие утверждения равносильны:

1) x_i ≤ x_k., (5.38)

2). (5.39)

Докажем, что из первого утверждения следует второе. Из леммы 5.1 следует, что

и. (5.40)

Запустим от узла a_i поток к узлу-получателю a_j, который будет протекать через a_k с интенсивностью x_i или, если x_i =0, с любой интенсивностью меньшей, чем x_k (далее под x_i будем подразумевать эту интенсивность). Из узла a_k запустим поток к a_j с интенсивностью (x_k – x_i). Тогда интенсивность суммарного потока, протекающего через узел a_k, будет равна x_k, и этот поток будет проходить через a_m, минуя a_i и не возвращаясь в a_k, так как

и. (5.41)

Таким образом, справедливо второе утверждение леммы 5.2.

Следствие первого утверждения из второго очевидно (см., в частности, пример (5.28)). Лемма 5.2. доказана.

Лемма 5.3. В условиях леммы 5.1 справедливо следующее утверждение: любой узел, выбранный при фиксированном узле-получателе, не может транзитивно доминировать сам над собой, т.е.

. (5.42)

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

. (5.43)

В соответствии со следствием 5.1 из леммы 5.1 без потери общности можно считать, что элементы этой последовательности обладают следующим свойством:

. (5.44)

Рассмотрим три подряд идущих узла данной последовательности. Пусть максимальная интенсивность потоков от узла к узлу-получателю, при которой он будет протекать через узел, равна (если верхнего ограничения нет, то полагаем, что), а минимальная положительная интенсивность, с которой через узел проходят потоки от равна (если минимума нет, то в качестве значения принимаем инфимум положительных значений). Тогда из леммы 5.2 следует, что. В то же время, нетрудно убедиться, что.

Таким образом, справедлива следующая цепочка соотношений:

. (5.45)

откуда следует, что. Получили противоречие, из которого следует справедливость леммы 5.3.

Следствие 5.2. В условиях леммы 5.1 при фиксированном узле-получателе существует отличный от него узел такой, что для любого узла, отличного от a_j и a_i, справедливо сочетание

. (5.46)

Иными словами, согласно следствию 5.2 для любого узла-получателя существует отличный от него узел такой, что при любой интенсивности x> 0 справедливо уравнение

. (5.47)

Доказательство этого следствия поведём методом от противного. Предположим, что такого узла нет. Тогда существует узел-получатель такой, что для любого отличного от него узла существует узел такой, что

. (5.48)

Тогда можно построить последовательность вида (5.43) со свойством (5.44). Но из леммы 5.3 следует, что такой последовательности не существует. Поэтому сделанное предположение неверно, что доказывает справедливость следствия 5.2.

Следствие 5.3. В условиях леммы 5.1 при фиксированном узле-получателе справедливо следующее утверждение: если узел транзитивно доминирует над узлом, то a_i не может доминировать над a_k, т.е.,

. (5.49)

Утверждение следствия 5.3 очевидно, так как в противном случае узел a_k транзитивно доминировал бы над самим собой, что противоречит утверждению леммы 5.3.

Зафиксируем узел-получатель. Построим для него матрицу доминирования Q ^(j). Рассмотрим расширение РКМ T. Каждой расширенной РТМ сопоставим вектор с компонентами

(5.50)

Тогда матрица доминирования будет выглядеть следующим образом:

(5.51)

Рассмотрим связь матрицы доминирования с отношениями доминирования узлов ТКС в форме импликации вида:

. (5.52)

Из соотношения (5.52) следует эквивалентность следующих соотношений

. (5.53)

Критерий корректности для РКМ можно сформулировать в виде следующей теоремы [69].

Теорема 5.5. Распределяющая карта маршрутизации T корректна тогда и только тогда, когда для любого узла-получателя верно, что его матрица доминирования Q ^(j) удовлетворяет следующему требованию:

. (5.54)

Докажем сначала необходимость. Пусть РКМ корректна. Зафиксируем узел-получатель. Предположим, что существует число k такое, что

. (5.55)

Тогда из (5.53) следует, что

, (5.56)

а это противоречит утверждению леммы 5.3.

Теперь докажем достаточность. Рассмотрим РКМ. Так как все прокладываемые этой картой маршруты будут заканчиваться в узле-получателе a_j, то нам остаётся доказать, что все определяемые РКМ маршруты будут конечнозвенными.

Предположим, что РКМ некорректна. Тогда будут существовать бесконечные маршруты, т.е., маршруты, содержащие циклы. В этом случае будут существовать узлы, транзитивно доминирующие сами над собой. Но из (5.54) в силу (5.53) следует, что любой узел не может транзитивно доминировать сам над собой, т.е.

. (5.57)

Полученное противоречие доказывает корректность РКМ и справедливость теоремы 5.5.

5.7. Методы одно-агентной маршрутизации потоков данных

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

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

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

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

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

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

Каждой автономной подсети глобальной ТКС соответствует ориентированный граф (графовая модель) с весами, вершины a_i которого соответствуют узлам подсети, а рёбра c_j и их веса w_j – каналам связи между узлами и стоимостям этих каналов связи. Если каналы связи являются двусторонними, то их стоимости и соответственно веса на графе могут быть различными для разных направлений передачи данных. Точно также магистральная подсеть, связывающая между собой все маршрутизаторы автономных (локальных) подсетей глобальной ТКС, может быть представлена “магистральным” графом с соответствующими весами вида

, , , . (5.58)

Ориентированным маршрутом в орграфе G называется чередующаяся последовательность вершин и рёбер вида

, (5.59)

где s – начальная вершина, f – конечная вершина.

На взвешенном графе G может быть построен граф допустимых маршрутов G_p, связывающих узел-источник s с узлом-получателем f и не имеющий петель. Любой ориентированный путь на этом графе может служить маршрутом адресной передачи данных в ТКС. Однако стоимость передачи данных по разным маршрутам может быть различной.

В общем случае веса w_j на графе допустимых маршрутов могут быть функциями от числа его узлов, расстояний между ними, пропускной способности каналов связи, измеренной величины задержки передаваемых пакетов данных и т.п. В задачах стохастической маршрутизации веса w_i могут зависеть от средней загруженности каналов связи, средней длины очереди в ТКС и т.п.

Обозначим через s узел-источник данных, а через f узел-получатель данных в глобальной ТКС. Им соответствуют начальная вершина s и конечная вершина f на графе допустимых маршрутов, причём каждому ребру c_i этого графа соответствуют веса w_i = w_i(r_i), равные стоимости передачи данных по соответствующему каналу связи в заданном направлении.

Общая стоимость j -го допустимого маршрута передачи данных от узла s к узлу f определяется функционалом качества вида

(5.60)

где M_j - число звеньев (рёбер графа) j -го маршрута, соединяющего граничные вершины s и f.

Оптимальным маршрутом передачи данных между заданными начальным узлом (вершиной) s н конечным узлом (вершиной) f будем называть такой маршрут, на котором функционал (5.60) принимает минимальное значение среди всех допустимых маршрутов, т.е.

. (5.61)

В общем случае, минимум (5.61) функционала (5.60) может достигаться не на одном, а на нескольких допустимых маршрутах, каждый из которых является оптимальным. В этом проявляется многозначность (многовариантность) решения задачи оптимальной маршрутизации. Эта неоднозначность полезна для равномерного распределения трафика и адаптации к перегрузкам.

В частном случае, когда требуется минимизировать общее количество передач данных между узлами s и f получим, что w_i =l и К_j= N_j. Если же w_i, равно расстоянию между соответствующими узлами j -го маршрута, то минимизация функционала (5.60) приводит к определению кратчайшего маршрута (пути), соединяющего узел-источник и узел -получатель данных.

Стоимость w_i канала связи можно выбрать обратно пропорциональной скорости передачи данных по этому каналу или прямо пропорциональной задержке пакетов. В этих случаях минимизация критерия качества (5.60) приводит к оптимальным маршрутам с наибольшей скоростью передачи данных или минимальными задержками пакетов.

Разработчики сети ARPANET использовали для оптимальной маршрутизации критерий (5.60), где в качестве весов w_i использовались сначала длины очереди, а затем непосредственно измеряемое время задержки в i -том канале связи ТКС. При этом обнаружилось, что в процессе вычисления оптимальных маршрутов возникали нежелательные эффекты «пробуксовки» и «колебаний» [4], а при передаче по этим маршрутам наблюдались канальные и сетевые перегрузки. Чтобы устранить эти недостатки, было предложено в качестве весов w_i в критерии (5.60) использовать величины, характеризующие степень использования i-го канала связи. В этом случае оптимальные маршруты при низкой нагрузке оказывались близки маршрутам, получаемых в случае, когда w_i является временем задержки, а при высокой нагрузке они были близки маршрутам, получаемым в случае, когда w_i обратно пропорциональны пропускной способности i-го канала связи ТКС.

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

, (5.62)

характеризующий среднее время задержки по всей сети. Здесь λ _j – поток данных в j-ом канале, измеряемый числом пакетов в единицу времени (например, в секунду), μ _j – пропускная способность j-ого канала связи, M – число каналов связи в разомкнутой ТКС с N узлами и γ – полная внешняя нагрузка ТКС, т.е. сумма всех поступающих в ТКС пакетов вида

, (5.63)

где γ _ij – средняя нагрузка между i-ым и j-ым узлами ТКС, содержащей не более N (N -1) пар узлов «источник-получатель» пакетов данных.

Следует отметить, что во всех коммерческих ТКС стоимости каналов связи задаются независимо от реального трафика (сетевой нагрузки). Это позволяет гарантировать сходимость алгоритмов оптимальной маршрутизации и отделить этот процесс от адаптивного управления передачей пакетов по маршруту.

5.8. Деревья оптимальных маршрутов c корневым узлом-получателем и методы их использования для централизованной и децентрализованной маршрутизации

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

Будем называть его деревом оптимальных маршрутов (ДОМ), ведущих к заданному узлу-получателю. В общем случае число таких деревьев равно числу N(N-1).

В статических ТКС для построения оптимальных маршрутов от узла-источника к узлу- получателю можно использовать методы одно-агентной маршрутизации, основанные на методе Дейкстры (Dijkstra) [1], методе Беллмана-Форда (Bellman-Ford) [6], методе Форда-Фулкерсона (Ford-Fulkerson) [20], а также на нейросетевых методах (например, на базе нейронных сетей Хопфилда) [69]) и их модификациях. Многократное применение этих алгоритмов для разных пар “источник-получатель” позволяет построить все деревья оптимальных маршрутов, корни которых соответствуют возможным узлам-получателям ТКС.

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

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

Для получения дерева оптимальных маршрутов с корневым узлом-получателем a₀ = f можно использовать алгоритм Беллмана-Форда [6]. Этот алгоритм решает задачу поэтапно, начиная с узла-получателя a₀ = f и до тех пор, пока не будет охвачен самый «удалённый» (по стоимости каналов связи) от него узел-источник a_i = s, i = 1, …, N.

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

Применяя описанный алгоритм к каждому узлу как к потенциальному получателю, можно построить все N -1 деревьев и таблиц оптимальных маршрутов с корневым узлом-получателем. Этот подход используется в схеме централизованной маршрутизации, когда построение всех деревьев и таблиц оптимальных маршрутов возлагается на выделенный маршрутизатор-координатор. Полученные результаты вычислений этот центральный маршрутизатор передает всем узлам-получателям сообщений.

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

При децентрализованной маршрутизации все узлы ТКС равноправны и должны поддерживать две табличные БД:

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

- таблицу оптимальных маршрутов, ведущих к корневому узлу-получателю.

При этом все пакеты данных идентифицируются IP-адресом узла-получателя и передаются ему по оптимальным маршрутам.

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

Рис. 5.2. Граф ТКС с двусторонними связями между N=15 узлами и одним узлом-получателем a₀=f.

В качестве примера рассмотрим ТКС, граф которой с N=15 узлами a₀, a₁, …, a₁₄ изображён на рис.5.2. Предположим, что веса рёбер графа пропорциональны расстоянию между соответствующими узлами, а узлом-приёмником является узел a₀ = f. Тогда дерево оптимальных маршрутов с корнем в вершине f будет иметь вид, представленный на рис.5.3. Определенный путь от любой вершины этого дерева к его корню f определяет оптимальный маршрут передачи данных от соответствующего узла-источника ТКС к заданному узлу-приёмнику a₀ = f.

Рис. 5.3. Дерево оптимальных маршрутов передачи пакетов данных от вершин s ₁, …, s ₁₄ к корневой вершине s₀ = f.

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

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

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

В общем случае число деревьев оптимальных маршрутов с корневым узлом-источником равно N (N -1). Для их построения можно использовать алгоритм Дейкстры (Dijkstra)[4]. Алгоритм решает эту задачу поэтапно, строя дерево оптимальных (в смысле минимизации функционала (5.60)) маршрутов с корнем в узле-источнике s до тех пор, пока не будет охвачен самый «удаленный» узел-получатель.

С помощью этого дерева можно построить таблицу оптимальных маршрутов для корневого узла-источника a₀ = s, определяющую последовательность каналов связи и узлов ТКС, через которые нужно посылать пакеты данных к любому узлу-получателю a_i = f, i =1, …, N -1. Подобные деревья и таблицы оптимальных маршрутов могут быть заранее построены для каждого узла ТКС, являющегося потенциальным или реальным источником сообщений.

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

Схема централизованной маршрутизации основана на выделении специального маршрутизатора-координатора с глобальной БД о ТКС, который заранее строит деревья и таблицы оптимальных маршрутов для всех узлов-источников и посылает их в эти узлы. Эта схема обычно применяется в ТКС, ориентированной на виртуальные каналы.

В этом случае между каждой парой «источник-получатель» может существовать несколько виртуальных каналов. Поэтому управляющие пакеты передаваемых данных должны нести не только информацию об адресах узла-источника и узла-получателя, но и номера (идентификаторы) виртуальных каналов. Этот метод используется в ТКС с сетевой архитектурой SNA фирмы IBM, в глобальных ТКС TYMMEN и Telenet (США) и TRANSPAC (Франция) [1–6].

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

Распределенная версия оптимальной маршрутизации на базе модифицированных алгоритмов Беллмана-Форда и Дейкстры, генерирующих дерево оптимальных маршрутов от текущего узла ТКС, была реализована сначала в глобальной ТКС ARPA Министерства обороны США, а затем в сети Datapac (Канада) и в сетевых архитектурах DNA фирмы DEC и BNA фирмы Burroughs [1–6].