Синтез топологии каналов передачи данных в вычислительных сетях

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

Рассматривается следующая задача. Дано:

· множество узлов (вершин) сети, — число узлов;

· трафик, для его задания используется некоторая метрика; трафик задается в виде матрицы , ее элемент есть трафик между узлами и ;

· матрица стоимостей прокладки и аренды (за прогнозируемое время эксплуатации) связи между парами узлов, — стоимость связи между узлами и ;

· стоимость обслуживающего оборудования, стоимость определяется типом оборудования, а тип выбирается в зависимости от трафика в соответствующем канале.

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

Решение задачи включает две процедуры:

1. выбор системы связей — каркаса сети;

2. перенос трафика связей, не вошедших в каркас и называемых хордами, в те или и иные связи каркаса.

В первой процедуре рассматривается полный граф , — множество ребер (связей) полного графа. Каркас выбирается в виде остовного дерева, в дальнейшем к нему могут добавляться некоторые другие связи.

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

где

Начало исполнения алгоритма — включение в двух вершин и , которым соответствует минимальный элемент матрицы .

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

Алгоритм второй процедуры основан на классификации связей. Связи первого ранга — это связи каркаса. Связь второго ранга — это хорда такая, что имеется вершина и связи и включены в каркас. Хорда -го ранга — это хорда такая, что имеется вершина и связи и являются связями ранга меньше , причем одна из них имеет ранг .

Результаты классификации хорд составляют матрицу , ее элемент , где — ранг связи .

Заполнение матрицы происходит по следующему алгоритму. Сначала всем связям первого уровня присваивается ранг , т.е. принимаем . Далее если и имеется такое, что , то . Алгоритм выполняется при последовательном увеличении до полного заполнения .

Перенос трафика из хорд в связи каркаса происходит по эвристикам, выбираемым генетическим методом.

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

1. Если ( , то трафик из связи переносится в связи и ;

2. Выбирается , соответствующее минимальной сумме при условии ; трафик из связи переносится в связи и ;

3. То же, что и правило 2, но с измененным условием ;

4. То же, что и 3, но перенос трафика осуществляется только, если , иначе связь присоединяется к каркасу.