Введение к работе
Актуальность темы. Рост размерности технических и программных средств ВТ характеризуется в настоящее время переходом к мега — сетям, включающих от тысяч до миллионов элементов — узлов и каналов взаимодействия. Структура сетей сравнительно однородна, трудно или даже невозможно выделить более —менее изолированные участки для декомпозиции. Отметим наиболее характерные примеры таких структур.
Глобальные информационно — вычислительные сети, рост масштабности очевиден, достаточно упомянуть INTERNET.
Микросхемотехника: процессоры, схемы памяти.
Супер—ЭВМ с параллельной обработкой датптых.
Нейрокомпьютеры и нейросети.
Алгоритмы и программы параллелып>гх, конвейерных, и т.п. вычислений.
Храпение и выборка информации в больших базах данных при естественных упрощениях моїут интерпретироваться вероятностной моделью пространственной сети.
С ростом размерности сетей происходит радикальное перераспределение важности решения различных классов задач разработки и эксплуатации подобных объектов. Резко возрастает значимость анализа вероятностных характеристик избыточных сетей, частным случаем которого являются задачи надежности. (Для примера — надежность 0.999 для 100 элементов переходит в 0.0001, когда их миллион).
Диссертация посвящена разработке методов и средств исследования вероятностных характеристик связности однородных стохастических сетей с алдитивпой структурой, включающих от тысяч до миллионов узлов и каналов связи — мега—сетей.
Однородность подразумевает отсутствие "сгустков" в сети: число каналов, примыкающих к любому узлу сети относительно невелико. Стохастичность допускает неправильное функционирование любого элемента сети — "отказ", причем отказы элементов считаются взаимно
4 независимы. Связность узлов означает возможность взаимодействия между ними — наличие хотя бы одного пути из исправных (нормально функционирующих) элементов сети.
Аддитивность структуры предполагает, что сеть может быть построена итерационно — последовательным присоединением к ее текущей границе подсетей дополнения с ограниченным числом элементов. Граница подсети становится новой текущей границей сети. Максимальное число узлов текущей границы m задает степень аддитивной сети, количество п комплектующих подсетей — ее ранг.
Одномерная аддитивность предполагает, что степень структуры невелика m = O(l), тогда сеть высокого ранга п >> 1 можно изобразить в виде узкой ленты "шириной" ш. Многомерная аддитивность означает, что степень велика m >> 1, и для наглядного изображения сети необходима плоскость или пространство еще большей размерности. Простейший пример — двухмерная сеть в виде решетки m х n: m квадратных ячеек "по горизонтали" и п — "по вертикали".
Цель исследования. Разработка конструктивных методов и реализуемых на стандартных ПЭВМ средств анализа стохастических сетей с многомерной (планарной, трехмерной) аддитивной структурой, формирование и обоснование зависимостей изменения вероятностных характеристик мега—сетей при варьировании их структуры и параметров отказа элементов.
Для достижения поставленной цели были решены следующие задачи.
Дано компактное математическое описание класса сетей с однородной структурой.
Разработаны точные методы анализа узкого подкласса таких сетей, сохраняющих все основные особенности исходного класса.
Проведен численный эксперимент большого объема для формирования гипотез по приближенным методам и средствам анализа всего класса сетей.
На основе точных построены приближенные методы расчета характеристик мега —сетей с аддитивной структурой.
Оценена погрешность и область применения приближенных методо п.
Проведены экспериментальные исследования зависимости характеристик аддитивных сетей от их размерности, конфигурации, параметров отказа элементов.
Методы исследования. Системный анализ, теория надежности, исследование операций, комбинаторный анализ, теория матриц.
Научная новизна. Основным научным результатом работы является совокупность методов и средств для конструктивного анализ широкого класса стохастических сетей, включающих миллионы элементов, с однородной, многомерной {Планерной, трехмерной] аддитивной структурой.
Получены следующие новые результаты:
определена и обоснована самостоятельная предметная область — аддитивные структуры, получаемые итерационным присоединением к текущей границе сети подсетей дополнения. Число комплектующих подсетей определяет ранг п сети, количество узлов текущей границы — степень m сети;
на основе обобщения получены точные методы расчета характеристик связности произвольных аддитивных сетей, конструктивные при анализе одномерных сетей, когда m = O(l);
разработаны методы оценки вероятности связи всех узлов многомерных (степень m >> 1) аддитивных сетей и определены их погрешности;
разработаны методы оценки вероятности связи между полюсами многомерных (степень гп >> 1) аддитивных сетей, в том числе — асимптотических свойств, и определены их погрешности;
выявлена асимптотическая независимость вероятности связи между полюсами однородной аддитивной многомерной сети от положения полюсов, если ранг, степень сети и расстояние между полюсами стремятся к бесконечности.