Иерархическая декомпозиция

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

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

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

Рис. 8.4. Дерево иерархической декомпозиции глобальной ТКС

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

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

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

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

По мере повышения статуса (уровня) управления в общей иерархии сетевого управления увеличивается число “степеней свободы”, т.е. количество управляемых переменных, определяющих управляемую динамику сетевых потоков данных.

Декомпозиция глобальной ТКС на подсети разного уровня иерархии и сложности требует иерархической декомпозиции целей сетевого управления. При этом прежде всего необходимо определить глобальную цель g₀ и локальные цели g_{l, i}, i=1, 2, …, r, достижение которых означает, что глобальная ТКС гарантирует достижение общей (глобальной) цели, т.е., например предоставление всем пользователям требуемых услуг.

В простейшем случае глобальную цель можно представить как “линейную свёртку” локальных целей, т.е.

(8.1)

где w_i – весовые параметры (веса), такие что

0 £ wi £ 1, .

(8.2)

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

8.5.2. Иерархическая модель мульти-агентной маршрутизации

Рассмотрим задачу оптимальной маршрутизации потоков данных от узла-источника s к узлу-получателю f глобальной ТКС.

Сначала, зная адрес (например, IP-адрес) узла-источника s, идентифицируем локальную подсеть, которой он принадлежит. Обозначим её через L₁ = L (s).

Затем по адресу узла-получателя f найдём локальную подсеть, которой принадлежит этот узел. Обозначим её через L_i = L (f), i =1, 2, …, n_L, где n_L – общее число локальных (локализованных на нижнем уровне иерархии) подсетей. Такая локальная подсеть L_i в свою очередь принадлежит одной из автономных подсетей A _k, k=1, 2, …, n _A, n _A< n_L., более высокого уровня иерархии.

Каждая локальная подсеть L_i имеет собственный локальный маршрутизатор R_i. Предположим, что локальные маршрутизаторы связаны между собой по принципу “каждый с каждым” согласно типовой топологии “полносвязный”, а узел-получатель f принадлежит локальной подсети L_i, . Тогда маршрутизатор R_i способен решить задачу оптимальной внутренней маршрутизации между ними.

Однако в общем случае узел-получатель f может принадлежать любой из локальных подсетей L_i, где i ¹ j. Тогда её маршрутизатор R_j способен решить задачу оптимальной внутренней и внешней маршрутизации между узлами s Î L₁ и f Î L_j, используя локальный оптимальный маршрут в подсети L_i между s и Ri, вычисленный маршрутизатором Ri, и “достроив” его собственным оптимальным маршрутом от Ri до f Î L_j. Этот внешний оптимальный маршрут не обязательно непосредственно соединяет маршрутизаторы Ri и R_j, а может проходить в своей средней части через другие маршрутизаторы локальных подсетей глобальной ТКС.

В тех интересных для практики случаях, когда топология связей между локальными маршрутизаторами не является “полносвязной”, один из маршрутизаторов Ri или R_j должен “достроить” среднюю часть внешнего оптимального маршрутизатора, соединяющего узлы s Î L₁ и f Î L_j. Это требует знания топологии ТКС и параметров (весов) каналов связи между локальными маршрутизаторами или знания (предварительного расчёта) оптимальных маршрутов между ними.

Предположим, что локальные маршрутизаторы R_i, i =1, 2, …, n _L, связаны между собой топологией типа “кольцо” с односторонними каналами связи, определяющей соседство локальных маршрутизаторов. Тогда вычисление приемлемого маршрута, совпадающего или близкого к оптимальному, сводится к следующему.

Сначала по адресу узла-источника s определяется локальная подсеть, которой он принадлежит, и она обозначается через L₁ = L (s). Затем по адресу узла-получателя f определяется его локальная подсеть L_j = L (f) в глобальной ТКС.

Выбор средней части глобального маршрута определяется двоичным деревом внешней маршрутизации, изображённым на Рис. 8 5.

Рис. 8 5. Двоичное дерево внешней (глобальной) маршрутизации

Этот выбор зависит от того, какой именно локальной подсети L_j принадлежит узел-получатель f. В результате определяется средняя часть глобального маршрута вида

R₁ ® R₂ ®…..® R_j. (8.3)

Если при топологии “кольцо” каналы связи между локальными маршрутизаторами являются двусторонними, то в зависимости от направления обхода “кольца” строится два двоичных дерева, аналогичных дереву, изображённому на Рис. 8.5. По ним определяется наилучший маршрут передачи потоков данных типа (8.3) в ту или иную сторону движения по “кольцу” от локального маршрутизатора R₁ Î L₁ к локальному маршрутизатору L_nL = L (f).

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

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

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

Описанная схема иерархической маршрутизации даёт особенно большую экономию в случае, если локальные маршрутизаторы первоначально имели топологию связей типа “полносвязная”.

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

8.6. Принципы мультифрактального моделирования глобальных телекоммуникационных сетей нового поколения

8.6.1. Фрактальная декомпозиция глобальных сетей на автономные подсети

Глобальные ТКС, описываемые изменяющейся с течением времени графовой моделью вида

G(t) = G (A (t), R (t), W (t)), t Î [ t₀, t_T ], (8.4)

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

Общее количество узлов N = |A| и каналов связей M = |R| глобальной ТКС может быть очень большим, причём оно может изменяться в широких пределах с течением времени на рассматриваемом интервале [ t₀, t_T ]. Это порождает, согласно Р.Беллману, “проклятие размерности”, которое давлеет при анализе динамики глобальных ТКС и синтезе сетевого управления потоками данных.

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

Эффективным принципом разделения глобальной ТКС на автономные подсети является концепция фрактального или мультифрактального моделирования (МФМ) [93–95]. Использование этого принципа наиболее целесообразно на этапе концептуального проектирования глобальной ТКС и особенно её РТС и САУ.

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

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

В этом проявляется фрактальность (самоподобие топологии узлов и каналов связи) локальных подсетей и глобальной ТКС. Принцип самоподобия (self-similarity) тесно связан с быстро развивающейся в последние годы теорией фракталов [13].

Термин “фрактальный” происходит от латинского слова “fractus” и означает “дробный” или “ломанный”. В современной математике фракталами называются геометрические или графические объекты (кривая Пеано, снежинка Коха, ковёр Серпинского, множество Мандельброта и т.п.), обладающие свойствами определённого самоподобия.

Самоподобие, как основная характеристика фрактала, означает, что он устроен более или менее единообразно в широком диапазоне изменения масштабов или размера.

Теоретическая значимость и всеобъемлющий характер свойства самоподобия была отмечена М.Шредером [13]: “Самоподобие представляет собой понятие, объединяющее фракталы, хаос и степенные законы. Самоподобие или инвариантность относительно изменений масштаба или размера является отличительной чертой многих законов природы и бесчисленных явлений в окружающем нас мире. Самоподобие в действительности представляет собой одну из решающих симметрий, формирующих нашу Вселенную и влияющих на наши попытки понять её.”

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

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

Интерпретация глобальной ТКС как фрактала основана на том, что ей присуща определённая топологическая симметрия, т.е. некоторая неизменность топологии подсетей при изменении масштаба в процессе декомпозиции. При этом максимальный масштаб (количество узлов N) глобальной ТКС ограничен сверху некоторой величиной N^*. С другой стороны, минимальный масштаб локальных подсетей не может быть меньше некоторого числа N_*, при котором свойство самоподобия теряется. Аналогичные ограничения, задаваемые числами М_*и М^*, имеют место для числа каналов связи М.

Таким образом, для глобальной ТКС справедливы естественные фрактальные ограничения

N_*£ N £ N^*, М_*£ М £ М^* . (8.5)

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

На Рис. 8.6 представлена топология однородной (регулярной) глобальной ТКС типа “звезда” при её фрактальной декомпозиции на одну магистральную, три автономные и шесть локальных подсетей с числом узлов 4 и диаметром, кратным 2. Общее число узлов этой ТКС N = 31, а общее число каналов связи М = 28.

Рис. 8.6. Фрактальное представление однородной глобальной ТКС с топологией “звезда”.

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

Каждая такая подсеть имеет собственный маршрутизатор. Эти маршрутизаторы подсетей связаны между собой и с центральным маршрутизатором ТКС хотя бы одним каналом связи (на

Рис. 8..7. Фрактальная декомпозиция однородной ТКС с иерархической топологией типа “кольцо”

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

Задачи сетевого управления такими регулярными или квазирегулярными ТКС легко декомпозируются и вследствие этого значительно упрощаются.