Проектирование реляционных баз данных. Ковалев А.В - 22 стр.

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

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

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

                                               24