МЕТОД ПРОСТРАНСТВЕННОЙ ДЕКОМПОЗИЦИИ МОНТАЖНО-КОММУНИКАЦИОННОГО ПРОСТРАНСТВА ДЛЯ ПОСТРОЕНИЯ СЕТЕВЫХ ПОТОКОВ

Развитие научно-технического прогресса приводит к стремительному увеличению размерности различных сетей, инфотелекоммуникационных, электрических, сети маршрутов и т.д., что приводит к накоплению очень большого объема как структурированных, так и неструктурированных данных (Big data), которые требуют анализа и обработки. В работе рассмотрен метод моделировании оптимальной декомпозиции монтажно-коммутационного пространства инструментами теории предфрактальных графов. В отличии от всех известных методов в данном подходе совместного решения задач размещения и трассировки магистраль (канал) представляет собой часть плоскости (пластины). Предложен способ рекурсивного деления монтажно-коммутационного пространства с созданием активно-пассивной графовой модели. Важную роль в монтажно-коммутационной декомпозиции играют «стенки» между пространственными фрагментами, а также расположение на стенках транзитных точек, разрешающих проведение через них связей (проводников). Появляется возможность более гибкого распределения ресурса «стенок», определяются потоки связей через пропускные способности «стенок», при этом проводники не фиксируются на «стенках», зато используют понятие «пучков», «связок», «потоков» связей и математический аппарат потоков в сетях, графовых или предфрактально графовых. Полученный дуальный граф такой декомпозиции назван «конверт-графом», имеет много интересных аналитических свойств. Для решения задачи синтеза такого графа (сети), в котором поток существует и удовлетворяет всем введённым извне ограничениям, предложен алгоритм «вертушечного» деления МКП на зоны, оценка времени решения для которого меняется от O(Q2.33) до O(Q3).

1. Кочкаров А.М. Распознавание фрактальных графов: Алгоритмический подход. Нижний Архыз: Специальная астрофизическая обсерватория РАН. Компьютерно-издательский центр В. Лебедева, 1998.

2. Мелроуз Дж. Иерархические фрактальные графы и блуждания на них // Сборник «Фракталы в физике» / Под редакцией Л. Пьетронеро, Э. Тозатти. М.: Мир, 1988. С. 507-512.

3. Малашенко Ю.Е., Новикова Н.М. Потоковые задачи анализа уязвимости многопродуктовых сетей. М.: ВЦ АН СССР, 1989.