8.7 Общая задача топологического синтеза компьютерной сети

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

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

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

при следующих ограничениях:

1) задержка сообщения (пакета) в любом виртуальном соединении не должна превышать заданную величину Т;

2) матрица F должна удовлетворять матрице ;

3) величина потока в каждом соединении не должна превышать пропускную способность данного соединения

4) в каждой вершине, в которую направлен некоторый поток, должно быть выбрано единственное направление, по которому он выйдет из вершины.

При выборе алгоритма решение задачи (8.8) необходимо учитывать следующие требования:

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

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

- алгоритм должен давать достаточно хорошие решения с точки зрения их близости к оптимальным.

Ниже дано описание приближенного алгоритма.

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

Шаг 2. Определить минимальное число каналов связи так, чтобы

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

Шаг 4- Взять очередную пару и выбрать кратчайший маршрут с наименьшей загрузкой.

Шаг 5. Направить весь поток по выбранному маршруту.

Шаг 6. Если все пары из О, рассмотрены, то перейти к шагу 7, иначе к шагу 4.

Шаг 7. На каждой паре выбрать число каналов так, чтобы

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

Здесь также в начале определяется нижняя граница числа ребер . Для заданного числа узлов коммутации и ребер исследуются все графы, удовлетворяющие ограничениям (8.5)-(8.8). Для каждого такого графа решается задача выбора пропускных способностей и распределения потоков. Граф для которого эта задача дает наименьшую стоимость, запоминается в качестве оптимального решения. Затем число ребер увеличивается на единицу, и процесс продолжается. Схема алгоритма совпадает со схемой рисунка 8.5, за исключением того, что после шага «генерация очередного графа» следует шаг «решения задачи выбора пропускных способностей и распределения потоков».

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

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