8.3 Комбинаторный алгоритм топологической оптимизации сети передачи информации
Рассмотрим комбинаторный алгоритм решения задачи выбора оптимальной схемы соединения узлов коммутации пакетов выбора маршрутов и пропускной способности линий, который использовался на разных этапах проектирования и развития базовой сети системы «Сирена», а также других крупномасштабных сетей.
Комбинаторный подход опирается на представления сети передачи данных в виде конечного графа без петель и кратных ребер, вершиной которого соответствуют узлам сети, а ребра - линиям связи. Такое представление удобно для изучения характеристик сети, т.к. эти характеристики эквиваленты различным инвариантам графа, исследование которых ведется методами хорошо разработанной теории графов.
Применение теории перечисления графов для решения задачи топологической оптимизации долгое время считалось бесперспективным из-за необходимости исследования значительного числа возможных вариантов соединения линий связи. Например, в сети из 10 узлов существует 245 вариантов расположения линий связей, включая множество тривиальных случаев. Если предположить, что анализ каждого варианта составляет 1 с (на самом деле эта цифра значительно больше, т.к. анализ включает в себя проверку надежностных показателей, решение задачи выбора пропускных способностей и распределения потоков), то на исследование всех вариантов потребуется более чем 
лет.
Даже для малых сетей с числов узлов б и 7 потребуется соответственно 8,8 ч. и 24,2 сут.
Тем не менее в последнее время комбинаторный подход находит все более широкое применение при решении задачи топологической оптимизации. Это связано во-первых с повышением производительности ЭВМ, используемых для расчета комбинаторных задач; во-вторых с разработкой новых эффективных алгоритмов генерации графов с заданными свойствами и, наконец, большой опыт разработки и эксплуатации сетей передачи данных позволяет достаточно обоснованно формулировать требования к проектируемой сети, которые существенно сужают класс возможных решений задачи топологической оптимизации.
Ниже дается описание ряда комбинаторных алгоритмов топологической оптимизации, которые учитывают основные реальные требования, выдвигаемые при проектировании компьютерных сетей.
Необходимость разработки комбинаторных алгоритмов вызвана по крайней мере следующими причинами:
1. Крупномасштабные сети передачи данных обычно проектируются поэтапно, причем размерность сети на первых этапах невелика, что позволяет получать точное решение задачи топологической оптимизации с помощью комбинаторных алгоритмов. В тоже время известные приближенные алгоритмы [83,105] не позволяют находить точное решение даже для сетей небольшой размерности. При этом лучшие эвристические алгоритмы по данным разработчиков дают погрешность до 10%.
2. Наличие точного решения позволяет оценить качество известных и вновь разрабатываемых эвристических алгоритмов.
3. Комбинаторные алгоритмы предоставляют широкие возможности для изучения свойств оптимальных решений и оптимизируемой функции, что в свою очередь создает предпосылки для разработки новых эффективных алгоритмов.
Разработанные алгоритмы программно реализованы в пакете прикладных программ синтеза топологии сетей передачи данных, которые включают:
- точный и приближенный алгоритм конструктивного перечисления графов для решения задачи топологического синтеза сети минимальной стоимости при наличии ограничений на надежность. Указанные алгоритмы эффективно используются на этапе предпроектного исследования сети;
- комбинаторные алгоритма точного и приближенного решения задачи синтеза топологии, выбора пропускных способностей и маршрутов, применяемые на этапе технического проектирования и в процессе развития компьютерной сети;
- алгоритм «насыщения сечения»;
- алгоритмы решения задачи топологического синтеза сетей с повышенными требованиями к надежности (проектирование сетей с количеством независимых путей между каждой парой узлов большим Двух);
- эвристические алгоритмы задач синтеза топологии сетей большой размерности.
