Разработка топологического графа академической региональной информационной сети

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

V={vi} - множества точек - узлов сети;

E={ei} - множества простых (непрерывных самонепересекающихся) кривых - линий связи;

и удовлетворяющего следующим условиям:

• каждая кривая из Е содержит ровно две точки множества V, которые и являются ее граничными;
• единственными общими точками кривых из множества Е являются точки из множества V.

Сознательно отпустим одно из определяющих условий геометрического графа, а именно определения замкнутой кривой, как кривой, содержащей только одну точку из множества V. Случаи наличия

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

• Граф не является вырожденным, т.е. имеет ребра.
• Множества V и Е являются конечными. Таким образом, сам граф является конечным - все узлы сети известны и их количество конечно.
• Граф не имеет параллельных ребер. С точки зрения вычислительных сетей это условие означает, что ни одна из линий связи не дублируется.
• Минимальная валентность узла равна 1, т.е. граф связен.
• Максимальная валентность узла равна |V|-1.
• Граф не является ориентированным. В контексте сетей связи это условие означает, что линия связи является дуплексной, т.е. возможна передача по ней в любом направлении.

В качестве базовой топологии будем рассматривать полный граф - граф, в котором любые две вершины смежные (топология "каждый с каждым"). С точки зрения надежности такая топология является предпочтительной и ее целесообразно использовать при проектировании высоконадежной сети с небольшим количеством узлов. При увеличении числа узлов n = |V| количество ребер k = |Е| полного графа будет

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

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

180 удаление из графа одного ребра без нарушения его связности приведет к изменению схемы маршрутизации информационных потоков и, как следствие, к перераспределению трафика и изменению загрузки каналов связи и коммутационных узлов.

Для формализации задачи синтеза топологической структуры введем следующие обозначения:

Р - множество принципов π∈P построения системы или элементов. В большинстве случаев эти принципы заданы или известны.

F - множество взаимосвязанных функций, выполняемых системой. Каждому набору принципов построения π соответствует некоторое множество функций F(π), из которого рассматривается множество f∈ F(π), соответствующее задачам системы.

А - множество взаимосвязанных элементов системы. А' - рассматриваемое множество элементов, ¾ - операция отображения элементов множества F на элементы множества А. Тогда оптимальное отображение должно обеспечить экстремум целевой функции (или нескольких функций) при выполнении заданных ограничений.

Получим систему соотношений:

Соотношения (4)-(6) определяют задачу синтеза топологии при известных принципах построения; соотношения (5)-(6) - при известных принципах построения и выполняемых функциях. Если же заданы принципы построения системы, выполняемые функции и элементы системы, то задача построения системы сводится к определению соотношения (6).

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

Необходимо отметить, что топология сети тесно связана с пропускной способностью каналов связи, быстродействием маршрутизаторов и предполагаемым трафиком [2].

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

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

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

Данный анализ связан со значительными временными затратами. Рассмотрим граф, изображенный на рис. 1. Это полный граф с числом вершин, равным 4. Согласно формуле (2), возможно построение 4^4-2 =16 покрывающих деревьев. Количество возможных подграфов данного графа, ³ 6!

содержащих три ветви, будет определяться как с ð = (у —ɜĴ7 ⁼ 2〇 ·

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

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

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

183

Для составления этой матрицы необходимо решить две задачи:

1. Составить карту распределения информационных ресурсов по узлам сети.
2. Определить прогнозируемую интенсивность запросов к распределенным информационным запросам.

Решение первой задачи заключается в распределении по узлам информационных ресурсов - WWW- , news- и ftp-серверов и обычно определяется административно. Ориентировочно можно оценить трафик сети как совокупность соотношений, взяв за единицу http-трафик - интенсивность запросов к WWW-серверам. Трафик в первый месяц после ввода сети в эксплуатацию и подключения основной массы абонентов представляется следующим образом:

• ftp - 10 единиц;
• news - 5 единиц;
• прочее - 0.5 единицы.

Начиная со второго месяца работы, происходит перераспределение трафика, объясняемое "утолением информационного голода" и приводящее к следующим оценкам:

• ftp - 1/3 единицы;
• news - 2 единица;
• прочее - 1/6 единицы.

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

Вероятностные значения интенсивности запросов к информационным ресурсам также могут быть получены только эмпирически.

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

При удалении каких-либо ребер и появлении транзитного графика через некоторые узлы эта матрица будет изменена следующим образом. Создадим таблицу маршрутизации для топологического дерева. Очевидно, что она будет статической для данной сети. Обозначим ребро e∈E как еij, если оно соединяет вершины i и j. Таблица содержит k = N(N-1) столбцов и (N-1) строк, где N -количество узлов сети. Ячейка (m, еij ) содержит Śij, если путь из узла i в узел j проходит через ребро (линию связи) m и 0 в противном случае.

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

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

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

1. Определить расстояние между объектами по прямой и по коммуникационным колодцам.
2. Зафиксировать наличие прямой видимости между объектами или возможное количество установки ретрансляторов.
3. Произвести расчет стоимости по всем пригодным по пропускной способности каналам связи. При этом необходимо учесть, что возможно распараллеливание каналов связи.
4. Выбрать линию связи с минимальной стоимостью. Стоимость линии связи складывается из двух составляющих - разовой (стоимость оборудования, подключения и т.п.) и эксплуатационной (стоимость аренды линии, технической поддержки, оплаты энергетических ресурсов и т.п.).

Литература

1. Ларионов А.М., Майоров С. А., Новиков Г.И. Вычислительные комплексы, системы, сети. Л.: Энергоиздат., 1987. – С. 391.
2. Хетагуров Я. А., Древс Ю. Г. Проектирование информационновычислительных комплексов. – М.: Высшая школа, 1987. – 400 с.