научная статья по теме ОПТИМИЗАЦИЯ ТОПОЛОГИИ СЕТЕЙ ПЕРЕДАЧИ ИНФОРМАЦИИ БОЛЬШОЙ РАЗМЕРНОСТИ Автоматика. Вычислительная техника
Текст научной статьи на тему «ОПТИМИЗАЦИЯ ТОПОЛОГИИ СЕТЕЙ ПЕРЕДАЧИ ИНФОРМАЦИИ БОЛЬШОЙ РАЗМЕРНОСТИ»
Автоматика и телемеханика, Л- 5, 2007
© 2007 г. В.М. ВИШНЕВСКИЙ, д-р техн. наук, А.О. ЛЕОНОВ
(Институт проблем передачи информации им. A.A. Харкевича РАН, Москва), H.H. ЛЕВЧЕНКО, канд. техн. наук, A.M. СТЕПАНОВ, канд. физ.-мат. наук (Институт проблем информатики РАН, Москва)
ОПТИМИЗАЦИЯ ТОПОЛОГИИ СЕТЕЙ ПЕРЕДАЧИ ИНФОРМАЦИИ БОЛЬШОЙ РАЗМЕРНОСТИ1
Рассматривается задача синтеза топологической структуры двусвязпых сетей большой размерности по критерию стоимости и ограничениями па диаметр. Предложены точный комбинаторный алгоритм решения задачи и параллельный алгоритм для проведения вычисления па многопроцессорной потоковой вычислительной системе. Показано, что распараллеливание обеспечивает значительный выигрыш во времени вычислений оптимальной топологической структуры сетей большой размерности.
Задача оптимизации топологической структуры одна из основных задач, которую необходимо решать на этапе проектирования распределенных корпоративных сетей передачи информации. Ошибки в топологическом проектировании сети приводят к значительным экономическим потерям в связи с высокой стоимостью прокладки или аренды междугородных каналов связи (десятки и сотни тысяч долларов в месяц).
С математической точки зрения задача синтеза топологии сети является сложной задачей нелинейного программирования большой размерности, для которой отсутствует единый эффективный метод решения.
Решению задач синтеза топологической структуры сетей передачи информации уделяется значительное внимание [1 5. 11 15]. Интерес к этим работам значительно вырос в последние годы в связи с быстрым развитием корпоративных сетей передачи информации. Обзор последних работ приведен в [16 19]. Однако из-за трудностей вычислительного характера результаты в основном получены для сетей небольшой и средней размерности [11 13].
В [1. 2] предложены точные комбинаторные алгоритмы синтеза топологической структуры для корпоративных сетей передачи информации малой размерности. В [2. 3] найдена форма экстремальных графов с заданными свойствами для сетей большой размерности. Однако во всех перечисленных работах отсутствует алгоритм синтеза топологии большой размерности, позволяющий строить оптимальные по
1 Работа выполнена ири поддержке Российского фонда фундаментальных исследований, грант 06-07-90929.
критерию стоимости сети передачи информации с ограничениями на структурную надежность.
В настоящей работе сделана попытка закрыть указанный пробел. В первой части работы предлагается комбинаторный алгоритм синтеза, разработанный для проведения вычислений на однопроцессорных системах: во второй параллельный вычислительный алгоритм, обеспечивающий резкое сокращение времени расчета топологической структуры корпоративной сети передачи информации.
2. Постановка задачи синтеза топологии сети
Пусть N — число центров коммутации (ЦК) корпоративной сети. Предполагается, что известны места размещения ЦК (географические координаты) и тарифы на аренду каналов связи между всеми парами ЦК \\C (i, j)\\, ij = l, 2. N.
Синтезируемая топология сети должна удовлетворять следующим ограничениям:
• между каждой парой центров должно быть не менее двух непересекающихся по узлам маршрутов:
превышать заданной величины d;
Необходимо построить топологию сети минимальной стоимости при соблюдении описанных выше ограничений.
Корпоративная сеть передачи информации может быть представлена графом G = (V, E), вершины которого соответствуют ЦК и ребра — каналам связи. Обозначим N = \V\ число вершин ЦК и M = \E\ число ребер графа G (число каналов связи). Всем ребрам графа G приписаны неотрицательные веса C(x,y) стоимости аренды каналов между центрами, соответствующими вершинам «у. Под стоимостью графа понимается сумма весов, входящих в G ребер (обозначается C(G)). Наконец, обозначим через В множество всех остовных подграфов графа G0.
Используя введенные обозначения и понятия, математическую постановку задачи можно записать в следующем виде.
Найти остовный подграф G граф а G0 такой, что (1) C (G) = min
2 Дополнительное ограничение на вероятность связности графа P(G) проверяется отдельными алгоритмами, которые не рассматриваются в данной статье.
Остановимся более подробно на условиях (2) (3). Ограничение (2) эквивалентно требованию наличия двух непересекающихся путей между любыми парами вершин в графе О. Условие (3) по определению диаметра графа эквивалентно ограничению на длину кратчайшего пути между каждой парой вершин.
В общем случае задача (1) (3) является ХР-полной, так как ХР-полная задача коммивояжера преобразуется в ее некоторый частный случай. Решение данной
задачи методом полного перебора требует просмотра 2 2 вариантов топологических структур, причем просмотр заключается в генерации каждого варианта и проверке условий (2) (4).
Проблема выбора топологии решается различными путями в зависимости от предполагаемого числа центров сети. Если число центров не превышает 10 14. то при наличии достаточных вычислительных ресурсов оптимизационная задача может решаться точно [4. 8]. При числе центров больше 14 16 задача в общем случае решалась только приближенно с помощью эвристических алгоритмов с обратной связью. Но для некоторых популярных частных случаев решение может быть основано на результатах теоретических исследований классов экстремальных графов. Найденные экстремальные графы могут быть рассмотрены в качестве конкретных топологических структур при создании сетей передачи данных. В частности, в [5] было показано, что существует единственный экстремальный граф (с минимальным числом ребер). который является двусвязным и диаметр которого не превышает трех. Такие экстремальные графы рассматриваются как первоочередные кандидаты на решение, что позволяет значительно ускорить процесс синтеза топологии сетей большой размерности.
Теорема. Пусть заданы, следующие ограничения для топологического графа:
1. Двусвязность; в графе существуют два непересекающихся пути между любыми двумя вершинами.
3. Диаметр графа после удаления из него любого ре бра или вершины d2 =3. Тогда минимальное число ребер для n вершин, при котором еще существуют графы с указанными характеристиками, будет
— m(n, 3) = 2n — 4, если число вер шин n лежит в интервале 4 < n < 7;
— m(n, 3) = 2n — 5, если число вер шин n лежит в интервале 8 < n < 23;
— m(n, 3) = 2n — 6, если число вер шин n > 24.
Экстремальный образующий граф при n > 24 имеет вид, представленный на рис. 1. Доказательство данной теоремы приведено в [5].
Интерес в основном представляет именно последний случай, а именно случай, когда число центров проектируемой сети не менее 24. В этом случае существует только одно семейство графов, которое имеет минимальное число ребер при числе вершин n > 24 и соблюдении ограничений (2) и (3).
Общий вид данного семейства приведен на рис. 1.
Данное семейство экстремальных графов характеризуется тем. что все центры (узлы сети) условно разделены на две группы. Первая включает в себя шесть центров. образующих два «ядра» сети по три центра в каждом. Каждый же из остальных центров, входящих во вторую группу, имеет по одной прямой связи с каждым из ядер, причем каждый из центров одного ядра имеет как минимум по две кратчайшие связи через центры второй группы с центрами второго ядра.
Рис. 1. Вид экстремального графа.
Назовем прямые соединения между элементами каждого из ядер «магистралями». Все остальные соединения будем называть «ординарными каналами» или просто »каналами».
Следствие 1. Для графа, изображенного на рис. 1, минимальная степень вершины, входящей в одно из ядер, равняется восьми.
Доказательство. Предположим обратное. Пусть существуют два ядра: ядро А н ядро В. И пусть степень вершины А1 меньше 8. Тогда учитывая то, что два ребра соединяют вершину А1 с вершинами того же ядра А2 и АЗ, имеется не более пяти ребер, соединяющих вершину А1 с вершинами графа, не принадлежащими ядрам, а, следовательно, через них и с ядром В. Так как в ядре В также три вершины, то по крайней мере одна из них имеет не более одной смежной с ней вершины, не принадлежащей ядрам, которая так же смежна вершине А1. Без ограничения общности можно принять, что это вершина В1. Возможны следующие два варианта:
а. В графе имеется одна вершина, смежная с вершинами А1 и В1 и не принадлежащая ядрам. Обозначим эту вершину С1. Удалим ребро А1-С1. Тогда минимальный путь из вершины А1 в С1 будет иметь длину четыре или более. В частности кратчайший путь может проходить через следующие ребра: А1-А2, А2-Сх, Сх-В1, В1-С1, т.е. диаметр получившегося графа оказывается не менее 4. А это противоречит предположению 3 теоремы о том, что диаметр графа после удаления из него одного ребра или одной вершины равен трем.
б. В графе не имеется ни одной вершины, не принадлежащей ядрам, смежной и с вершиной А1, н с вершиной В1 одновременно. Пусть вершина С2 смежна с А1 и не смежна с В1. Пусть С2 смежна с узлом В2 из ядра В. Удалим ребро С2-В2. Тогда диаметр получившегося графа будет не менее чем четыре. Действительно, минимальный путь из С2 в В1 будет проходить через С2-А1, А1-Сх, Сх-В2, В2-В1. Но это снова противоречит предположению 3 теоремы.
Задачу по генерации топологии сети на базе полученного семейства экстремальных графов без ограничения общности можно разбить на два этапа:
1. Выбор опорных центров сети двух ядер по три центра.
2. Оптимальное подключение остальных центров к каждому из ядер.
Занумеруем все центры от 1 до N. Тогда XI. Yl, Z1 центры первого ядра и Х2, Y2, Z2 центры второго ядра. Стоимость магистралей равна:
P ядер = [C(X1, Yl) + C(Y1, Zl) + C(X1, Zl) + C(X2, Y2) + C(Y2, Z2) + C(X2, Z2)]*k,
где коэффициент k является отношением пропускной способности магистрали ядра к пропускной способности ординарного канала.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.