2.2. Структурный синтез и оптимизация топологии

2.2.1. Регулярные графы

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

Граф Петерсона, изображенный на рис. 2.1, состоит из 10 узлов и 15 линий со связностью 3. Степень каждого узла также равна трем, и, следовательно, связность этого графа максимальна. Говорят, что такой граф имеет максимальную связность. Другое свойство оптималь­ности графа Петерсона связано с диаметром графа, т.е. максимальным расстоянием между парами узлов сети, измеряемым числом "шагов" от узла к узлу. На втором уровне будет три узла, так как степень ис­ходного узла была равна трем. По той же причине каждый из трех уз­лов второго уровня будет соединен не более чем с двумя узлами третьего уровня. На расстоянии двух шагов от исходного будет не более 10 узлов, включая и его самого. Таким образом, граф степени 3 и диаметра 2 не может содержать более десяти узлов. Этот макси­мум достигается на графе Петерсона.

Рис. 2.1. Граф Петерсона

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

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

2.2.2. Общая эвристическая схема

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

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

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

Рис. 2.2. Эвристический метод оптимизации топологии

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