автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка методов и средств анализа однородных стохастических мега-сетей и исследование их вероятностных характеристик

гг. Ой 2 г "ОЯ 1998

ВСЕРОССИЙСКИЙ НАУЧНО — ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ПРОБЛЕМ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНФОРМАТИЗАЦИИ

На правах рукописи

УДК 519.718

ГАДАСИН ДЕНИС ВАДИМОВИЧ

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ АНАЛИЗА ОДНОРОДНЫХ СТОХАСТИЧЕСКИХ МЕГА-СЕТЕЙ И ИССЛЕДОВАНИЕ ИХ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК

Специальность 05.13.13 — Вычислительные машины,

комплексы, системы и сети

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москиа - 191)8

Работа выполнена и ВНИИПВТИ, г. Москва

Научный руководитель

доктор технических наук, с.н.с. Гадасни В.А.

Официальные оппоненты

доктор техпичеких наук проф. Умрихин Ю.Д.

кандидат технических наук Аакаев А.С.

Ведущая организация

Ипетиту г проблем передачи информации Российской академии наук

Защита состоится "09" декабря 1998 г. в 14 — 00 на заседании диссертационного совета Д. 163.01.01 Всероссийского научно-исследовательского института проблем вычислительной техники и информатизации (ВНИИПВТИ) по адресу: 113114, Москва, 2-й Кожевнический пер., 4/6.

С диссертацией можно ознакомиться в библиотеке

ВНИИПВТИ

Автореферат разослан " ноября 1998 года

Ученый секретарь

диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Рост размерности технических и программных средств ВТ характеризуется в настоящее время переходом к мега — сетям, включающих от тысяч до миллионов элементов — узлов и каналов взаимодействия. Структура сетей сравнительно однородна, трудно или даже невозможно выделить более —менее изолированные участки для декомпозиции. Отметим наиболее характерные примеры таких структур.

Глобальные информационно — вычислительные сети, рост масштабности очевиден, достаточно упомянуть INTERNET.

Микросхемотехника: процессоры, схемы памяти.

Супер—ЭВМ с параллельной обработкой данных.

Нейрокомпьютеры и нейросети.

Алгоритмы и программы параллельных, конвейерных, и т.п. вычислений.

Храпение и выборка информации в больших базах данных при естественных упрощениях могут интерпретироваться вероятностной моделью пространственной сети.

С ростом размерности сетей происходит радикальное перераспределение важности решения различных классов задач разработки и эксплуатации подобных объектов. Резко возрастает значимость анализа вероятностных характеристик избыточных сетей, частным случаем которого являются задачи надежности. (Для примера — надежность 0.999 для 100 элементов переходит в 0.0001, когда их миллион).

Диссертация посвящена разработке методов и средств исследования вероятностных характеристик связности однородных стохастических сетей с аддитивной структурой, включающих от тысяч до миллионов узлов и каналов связи — мега—сетей.

Однородность подразумевает отсутствие "сгустков" в сети: число каналов, примыкающих к любому узлу сети относительно невелико. Стохастичность допускает неправильное функционирование любого элемента сети — "отказ", причем отказы элементов считаются взаимно

независимы. Связность узлов означает возможность взаимодействия между ними — наличие хотя бы одного пути из исправных (нормально функционирующих) элементов сети.

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

Одномерная аддитивность предполагает, что степень структуры невелика ш = 0(1), тогда сеть высокого ранга п >> 1 можно изобразить в виде узкой ленты "шириной" ш. Многомерная аддитивность означает, что степень велика ш >> 1, и для наглядного изображения сети необходима плоскость или пространство еще большей размерности. Простейший пример — двухмерная сеть в виде решетки шхп: т квадратных ячеек "по горизонтали" и п — "по вертикали".

Цель исследования. Разработка конструктивных методов и реализуемых на стандартных ПЭВМ средств анализа стохастических сетей с многомерной (планарной, трехмерной) аддитивной структурой, формирование и обоснование зависимостей изменения вероятностных характеристик мега—сетей при варьировании их структуры и параметров отказа элементов.

Для достижения поставленной цели были решены следующие

задачи.

Дано компактное математическое описание класса сетей с однородной структурой.

Разработаны точные методы анализа узкого подкласса таких сетей, сохраняющих все основные особенности исходного класса.

Проведен численный эксперимент большого объема для формирования гипотез по приближенным методам и средствам анализа всего класса сетей.

На основе точных построены приближенные методы расчета характеристик мега —сетей с аддитивной структурой.

Оценена погрешность и область применения приближенных

методов.

Проведены экспериментальные исследования зависимости характеристик аддитивных сетей от их размерности, конфигурации, параметров отказа элементов.

Методы исследования. Системный анализ, теория надежности, исследование операций, комбинаторный анализ, теория матриц.

Научная новизна. Основным научным результатом работы является совокупность методов и средств для конструктивного анализ широкого класса стохастических сетей, включающих миллионы элементов, с однородной, многомерной (.пленарной; трехмерной) аддитивной структурой.

Получены следующие новые результаты:

— определена и обоснована самостоятельная предметная область — аддитивные структуры, получаемые итерационным присоединением к текущей границе сети подсетей дополнения. Число комплектующих подсетей опроделяет ранг п сети, количество узлов текущей границы — степень ш сети;

— на основе обобщения получены точные методы расчета характеристик связности произвольных аддитивных сетей, конструктивные при анализе одномерных сетей, когда m = O(l);

— разработаны методы оценки вероятности связи всех узлов многомерных (степень ш >> 1) аддитивных сетей и определены их погрешности;

— разработаны методы оценки вероятности связи между полюсами многомерных (степень гп >> 1) аддитивных сетей, в том числе — асимптотических свойств, и определены их погрешности;

— выявлена асимптотическая независимость вероятности связи между полюсами однородной аддитивной многомерной сети от положения полюсов, если ранг, степень сети и расстояние между полюсами стремятся к бесконечности.

На защиту выносятся основные положения диссертации:

— совокупность методов и средств точного вычисления характеристик связности фиксированного подмножества узлов произвольных аддитивных сетей;

— алгоритмизация процесса анализа при расчете характеристик аддитивных сетей — решеток;

— совокупность методов и средств нахождения оценок вероятности связности всего множества узлов и вероятности связи между полюсами многомерных амитивных сетей;

— метод оценки асимптотического значения вероятности связи произвольных полюсов в многомерной аддитивной сети.

Практическая ценность исследования определяется результатами:

— применение методов не требует специальной подготовки и высокой квалификации исполнителя:

— соотношения для вычислений просты, программная реализация возможна на стандартных ПЭВМ с использованием широкодоступного програмного обеспечения;

— получен спектр достоверных оценок характеристик связности сетей —решеток в широком диапазоне изменения параметров отказа каналов, от 0,02 до 0,9, и числа узлов, от 400 до 10 000. Информация позволяет конкретизировать априорные представления разработчиков, так как большинство планарных сетей "похожи" на двухмерную аддитивную сеть в виде решетки ш х п;

— обоснован количественный критерий сравнения собственно стохастических структур, инвариантный к размеру сети и конфигурации ее границ — асимптотическое значение вероятности связи между удаленными полюсами сети. Асимптотика не зависит от положения полюсов и определяется только их окрестностями, одинаковыми в случае однородной структуры;

— разработан инструментарий для оценки эффективности и точности известных и разрабатываемых приближенных методов анализа стохастических сетей на основе сравнения с результатами анализа тестовых многомерных аддитивных мега — структур.

Обоснованность результатов и выводов. Аналитические результаты получены корректным использованием математического аппарата и хороню согласуются с физической интерпретацией механизма связности узлов мега —сетей. Конструктивность методов проверена реальным счетом характеристик тестовых сетей —решеток, включающих десятки тысяч элементов, в широком диапазоне параметров отказа каналов. Высокая точность оценок подтверждена большим объемом численных экспериментов: для одномерных сетей — прямым сравнением с точными результатами; для многомерных структур — сопоставлением оценок для теоретически равных различных характеристик сетей.

Публикации и апробация работы. Результаты диссертации опубликованы в 3 статьях в центральных научных журналах страны общим объемом порядка 4 п.л. и докладывались на 3 конференциях всероссийского и международного уровня.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 37 позиций. Объем: 156 страниц, из них основного текста — 127 е., 17 таблиц, 5 рисунков.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Постановки задач, сводящиеся к подобным моделям, появились в 50 —х годах при разработке сетей связи военного и гражданского назначения. Известные методы решения, в основном — приближенные, в целом "закрывают" проблему анализа сетей небольшого размера (десятки узлов) или декомпозируемых на такие подсети. Для произвольной структуры решение возможно только численными методами. Трудоемкость точного вычисления характеристик связности экспоненциально зависит от числа элементов и уже при сотне узлов находится на пределе ресурсов крупных ЭВМ.

Конструктивные результаты для мега—сетей можно получить только при наложении ограничений: количественных (параметры отказа элементов) или качественных (структурных). Первые обусловлены прогрессом технологий — ростом надежности компонентов сети и, в конечном итоге, приводят к анализу почти детерминированной сети — вероятности отказа близки к нулю или единице. Чтобы сохранить трудоемкость счета постоянной при увеличении размера сети, близость к детерминированности должна возрастать, для мега —сетей приходится выходить за технологические пределы. Применение известных методов для анализа мега—сетей сопровождается аккумуляцией погрешности, что ведет либо к недопустимой ошибке, либо превосходит допустимое время получения результатов.

Структурные ограничения обусловлены возможностью активного использования человека на первом этапе расчетов — структурной аппроксимации исследуемой сети, включающей идентификацию класса структуры исходной сети и выбор "похожей" тестовой сети. Технические мега —сети, как правило, сравнительно однородны, либо очевидным образом декомпозируются на такие подсети, поэтому структурная аппроксимация достаточно быстро делается человеком. Фактически человек решает задачу распознавания образов, имеющую на ЭВМ, по меньшей мере, экспоненциальную зависимость трудоемкости от числа элементов сети. Из неформального закона сохранения суммарной трудоемкости отсюда объективно вытекает предпосылка упрощения анализа на последующих этапах —

вычислении характеристик и адаптации результатов с учетом особенностей аппроксимации. _ - ----- -

Основное препятствие для применения — узкий исходный набор классов тестовых сетей. При сколь —нибудь нетривиальной структуре и произвольных надежностях элементов вероятностный анализ крайне сложен, известные результаты ограничиваются фактически единичными структурами. Разработка конструктивных методов анализа аддитивных, особенно многомерных (ш >> 1), структур л ох оля ит кардинально расширить возможности структурной аппроксимации.

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

Неформально аддитивная структура означает, что сеть может быть построена итерационно: каждый последующий фрагмент сети присоединяется к границе фрагмента, введенного на предыдущем этапе. Типичным представителем рассматриваемого класса является сеть — решетка с ш квадратными ячейками по оси ОХ и п ячейками — по оси ОУ. Учитывая наглядность, приведем упрощенную интерпретацию используемых далее понятий и определений.

Сеть С,п называется аддитивной п—го ранга т—й степени, если ее можно сформировать на основе следующего итеративного процесса.

Задано множество {дк} подсетей к —го дополнения, к = 2,п, (рис. 1 —в, дп). Топология подсетей дополнения произвольна, в каждой подсети дк выделены подмножества: — входных узлов, {ик} —

выходных узлов, причем |{Uk}| = |{Vk}| = га, и любые два входных узла не являются смежными, т.е. между ними канал связи отсутствует. Входные и выходные узлы нумеруются числами от 1 до ш. Задана начальная сеть первого ранга Gj с подмножеством пронумерованных выходных узлов {Uj}, |{U]}| = гп, (рис 1—а, д1).

Аддитивная Для построения сети п —го ранга Gn каждый из входных узлов {Vn_ ]} подсети д„ совмещаются с таким же по номеру выходным узлом {Un_(} сети (n—1) —го ранга Gn_!. Выходные узлы {Un} присоединенной подсети становятся выходными узлами сети G„ (рис 1—6 — 1 — г).сеть Сп называется рекуррентной, если структура всех подсетей дополнения gk, к = 2д1, постоянна.

Аддитивная сеть называется одномерной, если ее степень m невелика, m = O(l); одномерную сеть высокого ранга можно изобразить в виде "длинной и узкой ленты". Аддитивная сеть называется многомерной, если ее степень m велика, ш >> 1; для изображения сети высокого ранга нужна, как минимум, плоскость.

Граница между ними нечеткая и определяется 'Величиной степени: m = O(l) или m » 1. Понятия выбраны по аналогии с визуальным отображением сети и содержательно эквивалентны возможности точного (для одномерной сети) или только приближенного (для многомерной сети) нахождения характеристик связности на основе предлагаемых методов.

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

Подсеть дополнения gk, k = Vn , называется стохастической, если для любого канала подсети задана вероятность отказа и все отказы взаимно независимы. Аддитивная сеть называется стохастической, если

вероятность отказа любого канала сети такая же, как ив соответствующей подсети"дополнения.

в •>("„}

в) » ..... в в Л м

Ч 14 -

б)

в о •«• (к в

(и„,)

а) ^ в в ... о > ^ (

1 2 д, т

Рис. 1. Схема построения аллитштой сети ш — й степени п — т ранга (не и оказаны капали н узлы, кроме фаничних)

а) Начальная ссть первою ранга

б) Сан, (|I — ! ^ — го ^ . () — множество выходных узлов

в) Подсеть и —ю дшюллшиы у. (V .}, — множество входных и выходные узлов подсети

г) Сеть п—го ранга (и.) множегтвп Ецходтах узлов

Аддитивная сеть называется рекуррентной, если структура всех комплектующих подсетей одинакова. Рекуррентная сеть называется изотропной, если к тому же одинаковы и параметры отказа аналогичных элементов всех подсетей.

Вероятностью связности двух узлов сечи называется вероятность события — между этими узлами существует хотя бы один путь из исправных каналов связи. Вероятностью связности заданного подмножества узлов сети называется вероятность события — любая пара узлов из подмножества связна.

В главе 2 разрабатываются общие методы точного нахождения вероятностных характеристик связности произвольных стохастических сетей п —го ранга т — й степени с аддитивной структурой. Методы основаны на обобщении известных результатов для рекуррентных сетей низкой (ш < 3) степени и сводятся к формированию и последующему перемножению п так называемых матриц перехода.

Пусть задано некоторое разбиение "У множества из т различных номеров на подмножества. Выходные узлы сети находятся в состоянии ")", если одновременно выполняется: между узлами с номерами, входящими в одно и то же. подмножество, существует путь из исправных элементов сети; между узлами с номерами, входящими в различные подмножества — отсутствует путь из исправных элементов сети. Зафиксируем состояние ']" выходных узлов сети (п—1)—го ранга С„_1 и присоединим подсеть д„, тогда в зависимости от отказов элементов подсети выходные узлы подсети (следовательно — выходные узлы сети п —го ранга Сп) будут описываться некоторым состоянием "Г. Вероятность такого перехода состояний есть элемент матрицы перехода Ап.

Доказывается, что ау можно найти на основе анализа только подсети дополнения дп. Если ввести вектор — столбец Рп, координатами которого являются вероятности различных состояний выходных узлов сети Сп, то приходим к основному типу соотношений для вычисления точных характеристик связности произвольной аддитивной сети Сп

Рп = Апрп-1 =•••= АпАп_,Ап_2...А3А2Р1 (1)

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

Общая идея сведения анализа сети к изучению комплектующих ее отдельных подсетей и начальной сети первого" ранга остается неизменной. Отсюда трудоемкость анализа линейно зависит от ранга п сети и растет примерно как (S(m)]2 при увеличении степени т, где S(tn) — порядок матрицы перехода. Найдены итерационные формулы для точного вычисления S(m), значения лежат в районе ml. Таким образом, собственно для расчетов метод может быть использован только если m = 0(1), т.е. для одномерных аддитивных сетей.

Однако даже при небольших m практическая трудоемкость велика, уже S(7) = 877, т.е. для каждой матрицы в (1) надо найти примерно 106 членов a¡j. Рассмотрены три направления упрощений практической реализации метода. Во —первых, разработан простой алгоритм итерационного нахождения всех различных разбиений множества из m элементов на подмножества, так как формирование множества состояний "вручную" при m > 5 — 6 практически невозможно.

Во вторых, предложен метод декомпозиции подсетей дополнения. Трудоемкость формирования матрицы перехода зависит от "сложности" подсетей. Для аддитивности одинаковость подсетей не требуется, ничто не препятствует саму подсеть рассматривать как аддитивно построенную из более простых структур. Например, для сети —решетки подсеть g(s,q) в виде ш последовательно соединенных узлов эквивалентна присоединению двух подсетей: g(s) = g(s,q=l) в виде m изолированных нар узлов и g(q) = g(s = 0,q).

В третьих, для изотропных сетей Gn трудоемкость можно снизить в п раз. Все матрицы перехода одинаковы, и тогда (1) есть одна из форм записи системы линейных конечно —разностных уравнений. Известными методами получены эквивалентные (1) соотношения для любой линейной комбинации Р„ координат вектора Рп

S{m) п_!

Pn=ZcljXj (2)

]=1

S(m) ]

Pn=LH)] DjPu_j (3)

j=i

Здесь: X¡ — характеристические числа (х.ч.) матрицы перехода A, dj, Dj некоторые коэффициенты, причем Dj есть симметрический многочлен j —го порядка от х.ч. матрицы А.

В последующих главах в качестве объекта исследования выбрана тестовая структура: изотропная сеть—решетка с квадратными ячейками размером mxn, m —й степени, п—го ранга. Вероятность отказа любого "горизонтального" канала равны q, "вертикального" — равна s.

Для мега— сетей ограничение изотропности обычно несущественно, однородность присуща большим масштабам, но позволяет кардинально повысить компактность изложения и наглядность обоснований. Кроме того, для большинства результатов возможные обобщения на произвольную аддитивную сеть достаточно прозрачны.

В главе 3 на примере сети—решетки конкретизируется алгоритмизация методов для вычисления точных характеристик одномерных сетей, ш = 0(1), для многомерных сетей определяется ряд важных теоретических свойств матрицы перехода.

Использование декомпозиции подсети дополнения g(s,q) на подсети g(s) = g(s,q=l) и g(q) = g(s=0,q) означает, что вместо А = A(s,q) в (1) надо подставлять произведение матрицы A(s)*A(q), элементы которых определяются на основе анализа более простых подсетей g(s) и g(q).

Установлено, что, в отличие от A(s,q), почти все члены матриц — сомножителей равны нулю (98% — для ш = 7, 99.93% - для m = 10).

Доказаны решающие правила, позволяющие априорно (не вычисляя) идентифицировать возможно ненулевые члены ay(s), a,j(q) матриц A(s) и A(q), исходя только из номеров состояний i и j в множестве, сформированном на основе алгоритма главы 2. К тому же кардинально упрощается и сам процесс нахождения ненулевых членов матриц—сомножителей. Это делает процедуру анализа доступной для лиц с неспециальной подготовкой и уменьшает реальное время подготовки счета в тысячи раз.

Само время счета (теоретическая трудоемкость) уменьшается примерно в S(m) раз до величины 0[nS(m)]. Качественный характер

скачка переводит анализ одномерных сетей умеренной степени в категорию конструктивно решаемых задач.

Доказано, что при нумерации состояний в соответствии с алгоритмом главы 2 матрицы Л(я) и А(я) будут треугольными, и характеристическими числами (х.ч.) матриц —сомножителей являются их диагональные элементы. Для сети —решетки любой степени ш найдены "диагонали" матриц Л(я) и А(д), что привело к важным при ш » 1 заключениям относительно спектра х.ч. матрицы —произведения А(.ч^). При малых вероятностях отказа я "горизонтальных" каналов значения ^ группируются в окрестностях точек к = 0,1,ш-1. Но тогда "хвостом" сумм в выражениях (2), (3) можно пренебречь и ограничиться небольшим числом максимальных х.ч. Следовательно, возможна экстраполяция характеристик сетей высокой степени, но малого ранга, п = 0(1), на случай п » 1.

В главе приведены результаты точного расчета характеристик одномерных сетей (т < 6). Можно отметить для сетей высокого ранга п неожиданно высокое значение вероятностных характеристик связности даже при "плохих" каналах, а также сравнительно быстрое "насыщение" насыщение характеристик с увеличением степени сети ш.

Глава 4 посвящена разработке методов нахождения оценок вероятности связности П„ всех узлов изотропной аддитивной сети фиксированной степени ш и произвольного ранга п (на примере двухмерной сети —решетки тхп). В основе лежит неявная экстраполяция характеристик одномерных сетей — "отбрасывание хвоста" суммы в (2), (3) приводит к соотношениям (4), (5), где к — уровень оценки.

ь п-1

Дп = И)

и

= (5)

Подставляя в (4), (5) вместо Яп исходные значения Пп для п = 1, 2к, придем к системе уравнений относительно неизвестных Ц, ц^, К В работе найдена компактная, учитывая, что к « ш, форма решения

в виде равенства нулю определителя (к+1) —го порядка, элементами определителя являются значения вероятностей связности исходных сетей, ранг которых не выше 2к. Значение к называется уровнем оценки. При увеличении уровня оценка сходится к истинной величине Пш достигая ее при k = S(m).

Предварительный анализ решения показал, что для низкой погрешности оценки необходима очень высокая точность задания исходных значений Пш 1 < n < 2k, даже при втором — третьем уровнях оценки. Обеспечение такой точности исходных значений становится крайне сложной проблемой, ведь исходные сети Gn — высокой степени (хотя и малого ранга п). Однако для подкласса аддитивных сетей, называемых конвертируемыми, проблема решается.

Аддитивная сеть Сп п—го ранга m—й степени называется конвертируемой, если ее можно интерпретировать как аддитивную сеть Гт т —го ранга п —й степени. При этом тип подсетей дополнения может меняться. Сеть —решетка имеет конвертируемую аддитивность, поэтому вероятность связности Пп всех узлов исходной сети Gn равна такой же для сети Гт. Если ранг Gn невелик, n = O(l), то степень п сети Гт мала, и методами главы 3 возможно точное нахождение Пп для сети Гт при любом значении т.

В численном эксперименте максимальный ранг исходных сетей G (степень сети Г) равнялся пяти, порядок матриц перехода для нахождения исходных значений П5 S(5) = 52. Оценки имеют достаточную точность при надежных каналах (s,q <0.1) и низкой (ш < 10) степени сети Gn. Однако при высокой степени сети результаты удручающие, в ряде случаев оценка была много больше единицы. Необходимо повышение уровня оценки, следовательно, ранга исходных сетей G, что ведет к потере конструктивности счета.

Разработан метод снижения трудоемкости, основанный на теоретической независимости х.ч. Aj матрицы перехода А от параметров отказа начальной сети G, (вероятностей отказа х каналов "первой строки" решетки, ведь матрица перехода А формируется на основе анализа только подсетей дополнения д. Логично требовать, чтобы

оценки были бы одинаковыми, по крайней мере, в некоторых произвольно выбранных значениях х = X;, в дальнейшем — опорных точках х^

Развитие идеи позволило получить конечно — разностное уравнение (6) для нахождения оценок к—го уровня 11ц(ц) на основе значений вероятностей связности ПДх,) исходных сетей не выше (к+1) —го ранга, тогда как ранее требовался анализ сетей 2к — го ранга. Правда, для каждой исходной сети надо найти характеристики в к опорных точках х5, 1 = 1, к, ранее — только в одной, х = ц. Достигнутое снижение трудоемкости оценивается как [5(2к)/5(к+1)]2 раз: для к = 4 ранг падает с 8 до 5, порядок матриц перехода — с 4140 до 52, реальные затраты уменьшатся более чем в Ю1 раз.

Если в определитель (6) вместо Кп_к+11 подставить то определитель будет некоторым многочленом Нк(р) к—й степени от р., корни Р) многочлена Як(ц) = 0 ость оценки х.ч. Х^. Аналогично получены оценки I) коэффициентов с!^, ] = 1, к.

П,(х,) П2(х,) ••• Пк(х,)Пк+1(х,) П,(х2) П2(х2) •" Пк(х2) Пк+1(х2)

К,(ч)| =

П1(хк) П2(х2) ■

:0

(6)

Пк(хк)Пк+1(хк)

Кп-1(чЖи(я)

За начальную сеть в (6) можно принимать сеть 1-го ранга, 1 > 1, в дальнейшем значение 1 называется порядком оценки. Для сохранения трудоемкости (максимального ранга исходных сетей) приходится соответственно снижать уровень оценки к, но результаты упрощаются и становятся более наглядными: для первого уровня в работе получены двухсторонние оценки — сверху и снизу; при к = 2 легко найти аналитические соотношения в конечном виде. С другой стороны, порядок 1 означает, что коэффициенты ^ в (2) уменьшаются в М^1-1 раз, и так как "хвост" суммы убывает быстрее начальных слагаемых, то погрешность, несмотря на снижение уровня, не должна заметно измениться.

Большой объем счета (основные результаты приведены) позволил сформировать подходы к определению погрешности оценки V получить порядковое соотношение (7) для относительной погрешности 1-го порядка, к —го уровня (р^ >^+1)

1-1 / К+1-1

Кп = Ппехр[±пО(ц1Ц2---йкЦк+1/Н1 )1 (?)

Область практического приложения фактически ограничиваете* случаями, когда вероятность связности всех узлов сети конечш Пп > 0.3 — 0.4), необходимость оценки "нулевой" связности возникает крайне редко. Численный эксперимент показал, что точность убывает при убывании Пп: для высоконадежных сетей (Пп > 0.9) ошибка оценок лежит в 5 — 6 значащей цифре, возрастает до процента на нижнек пределе (Пп - 0.3) и "в разы", когда Пп - 0.05. Отметим также неожиданно высокие значения вероятности связности всех узлов сети например, для сети 100 х 100 с 10 000 узлов: Я]0о = 0.885 прь параметрах отказа каналов 0.05, Я100 = 0.239 если я = б = 0.1.

Глава 5 посвящена методам нахождения оценки Яп вероятности связи Рп между произвольными узлами — полюсами изотропной аддитивной сети высокой степени. Для конкретности рассматривают« узлы (1,п) и (ш,п)) в тестовой сети —решетке Сп п —го ранга ш — Р. степени. Точное решение определяется таким же соотношением тиш (1), как и для связности всех узлов сети, во многом подобны (глава 3) г спектры матриц перехода. Однако напрашивающееся "прямое' использование метода предыдущей главы дало неудовлетворительные результаты.

Метод хорош, когда вероятность связности всех узлов сеть сравнительно велика, что эквивалентно неявным ограничениям сверху на ранг сети п, на параметры отказа элементов (каналов связи), нг степень сети ш. В данном случае ограничения на ранг и степеш отсутствуют вообще, а на параметры элементов много слабее. Более того, при аппроксимациях типа (4), (5) ни одно из оценочных х.ч. ^ не будет равно единице, и, следовательно, оценка финальной (ранг п-»<х>; вероятности связи между полюсами будет стремиться: либо к нулю либо к " плюс—минус бесконечности", тогда как истинное значение

конечно. Эксперимент подтверждает заключение — при малых т и п точность хорошая, при высоких т и п может быть "любое число" как положительное, так и отрицательное.

Потребовалась существенная модификация метода. Для рассматриваемой задачи теоретически максимальное х.ч. точных матриц перехода Х0 = 1, поэтому в оценочных соотношениях типа (4), (5) х.ч. |!0 априорно принималось равной единице, что "снимает" проблему ограничений на ранг сети. Как и выше, конвертируемая аддитивность обеспечивает нахождение точных значений Р^ вероятности связности между полюсами (1,]) и (т,_|) исходных сетей ] —го ранга С^, ] = 1, к—1, и для оценки вероятности связи между полюсами найдены соотношения типа (6).

Однако из —за слабых ограничений на параметры отказа каналов намного критичнее становится выбор опорных точек — вероятностей отказа каналов "первой строки" исходных сетей. В главе показано, что для низкой погрешности оценки конечной (больше 0.1—0.2) финальной вероятности связи полюсов все опорные точки должны лежать в очень малой окрестности х = 0. Физически это попятно: "активность" использования "вертикальных" (в направлении ранга) каналов сети для создания трассы связи между полюсами (1,п) и (т,п) увеличивается при х~>0, растет объем информации о поведении сети с ростом ранга п, повышается точность экстраполяции.

В соотношениях появляются дифференциалы, Р/'ЦО) — производная 1-го порядка по х в точке х = 0 вероятности связи Р,(0) между полюсами (1,Л (ш,]') сети С} т —й степени. В работе получено конечно —разностное уравнение (8) для оценки к —го уровня Я„(с:|) вероятности Рп(ц) снязи между полюсами сети в точке х = д.

1 Р,(0) р#) Рк(0)

0 РГ<0) (!) р2 (0) (1) Рк (0)

0 Л) Л) • • Л) =0

0 рГ(0, РГ'(О) : ■ РГ(0)

Лп-к+|(Ч) КП'к+2(Ч)

йп(Ч)

Финальная вероятность связи с10 между полюсами (1,п) и (т, сети н— го ранга Сп есть предел Рп при п->оо, равный коэффициенту п| Х0 = 1 в спектральном разложении характеристики типа (2). Тог, соотношение для нахождения оценки ^ финальной вероятное получается заменой в последней строке определителя (8) ^(я) на Го- А оценки Ц) х.ч. X)- достаточно найти корни многочлена (9), Фк(и) — 0.

ки=

о

1=ц

р{чср>

(2)

р; '(о)

1

(а (1)

Р2 (0)

Р?«>)

(к-1) (к-1) Р, Ю)Р2 (0)

к

^ (Ч

Рк(0) (2) Рк (0)

(к-1)

(0)

В работе исследована погрешность оценки ^ и показана I пороговая зависимость от выбора опорной точки х. Для это рассмотрено поведение миноров истинной матрицы перехода п[ изменении х при т >> 1. При сравнительно надежных каналах, когда : заметно меньше (1 — эц2), надо выбирать х = 0; когда замет! больше — лучше х = я. В подавляющем большинстве приложен! наблюдается первый случай, сеть достаточно надежна и финальн. надежность с!0 конечна, тогда как во втором случае — близка к нул] Для погрешности оценки получено порядковое соотношение

•••^к-1

а-^т-изЬ-и-Ик-!) (1'

Предел 30 финальной вероятности с!0, когда не только ра: сети п, но и степень т и "расстояние" между полюсами (1,п) и (т, стремятся к бесконечности называется асимптотическим значение (асимптотикой) вероятности. Полученные результаты позволили пай' оценку 1о асимптотики 30. Показано, что при ш >> 1 и ] = 0( характеристики исходных сетей Р^ в окрестности х = аппроксимируются выражением

Р{(х) = Р^0)ехр(-тЬ^х)+С> (т^-х)^

(1

к

Если шаг дискретности х мал, то аппроксимация позволяет произвести предельные переходы в (8), (9).

Обозначим Т} = Р)(0), Н)= Р^О) — Р^х), тогда уравнение для вычисления с погрешностью 0(т-1) оценки к —го уровня |)(к) = ^ асимптотики 30 будет

К 1/ А Ут • / >2 . 1/ Ли

1 1 1

0 Н, н2 • • нк

0 2 Н, 2 н2 • 1 ■ нк

0 k-l Н, к-1 н2 • к-1 - нк

Для погрешности оце! соотношение.

=0

(12)

ки асимптотики получено порядковое

|Ъ-а0|=о

ТкН2Нз-Нк.,

+0(т

(13)

_T(Ht(H, - Н2) (И, - Н3)- • -(Н, - Нк_,)_ Большой объем численного эксперимента (характерные результаты приведены) подтвердил теоретические заключения.

Принципиальным оказалось требование чрезвычайно высокой точности (до Ю-30- Ю-40) задания характеристик исходных сетей Pj, j = 1, k+1, при шаге дискретности 0.001 —0.0001. Находились оценки до 3-го уровня сетей, включающих до 10 000 узлов, дальнейший рост размерности лимитировался инструментальными ошибками разрядности счета. Фактическая погрешность оценок даже 3 —го уровня оказалась весьма низкой: — (5 —6)—я значащая цифра при d0 ~ 0.9; доли процента при d0 ~ 0.7, 1 —2 процента при d0 ~ 0.3 — 0.5.

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

положения и размеров сети. Это важный результат, свидетельствуют! о наличии чисто структурного фактора "прочности" однородных сете характеризующего сеть в целом. Таким образом, асимптотика являет тонким количественным критерием сравнения несопоставимых ран однородных мега —сетей, отличающихся размерами, конфигурацие параметрами элементов.

Для примера ограничимся сравнением асимптотики для сетей решеток 100 х 100 с антисимметричными параметрами отказа каналов.

Математически различие сетей иллюстрируется отличи« точных характеристик таких сетей 1 — го ранга в 1085 раз, 4 —го ранга 1016 раз: P4(s=0.1, q = 0.7) = 5.10-15, P4(s = 0.7, q = 0.1) = 0.3332. Одна] физически объекты одинаковы — это одна и та же сеть, "повернутая" i 90°, поэтому оценки 3 —го уровня почти равн R100(s = 0.1, q = 0.7) = 0.5373, R100(s = 0.7, q = 0.1) = 0.5579.

В Заключении дается сравнение трудоемкости предлагаем! методов с известными и рассматриваются некоторые перспектш развития работ в данном направлении. Проведенные исследовали разработки позволяют сделать следующие выводы.

1. Разработаны и реализованы на стандартных ПЭВМ мето/ анализа стохастических сетей включающих от тысяч до миллионов узл< и каналов связи — мега—сетей.

2. Математически определена предметная область стохастические аддитивные структуры, получаемые итерационнь

присоединением к текущей границе сети подсетей дополненг Количество узлов текущей границы определяет степень ш сети. 1 основе обобщения предложены точные методы анализа, конструктивш при m = O(l).

3. Разработаны методы и реализуемые на ПЭВМ средст приближенной оценки характеристик связности многомерных (ш » аддитивных сетей. Установлена погрешность оценки и определе! условия ее минимазации.

4. Исследованы асимптотические свойства вероятности свя: между полюсами многомерной сети, когда ранг, степень сети

расстояние между полюсами стремятся к бесконечности. Установлена нороговость асимптотики и ее инвариантность в однородной изотропной сети к положению полюсов, что дает возможность использовать асимптотику в качестве количественного критерия сравнения собственно стохастических структур.

5. Определены достоверные оценки характеристик связности сетей — решеток и широком диапазоне изменения параметров отказа каналов и числа узлов, позволяющие формировать априорные представления разработчиков — большинство пленарных сетей "похожи" на двухмерную аддитивную сеть » виде решетки m х п;

6. Разработан и обоснован инструментарий для оценки эффективности и точности известных и разрабатываемых методов анализа стохастических структур на основе сравнения с точными и/или корректно оцениваемыми характеристиками аддитивных сетей.

Публикации по теме диссертации

1. Гада спи В.А., Гадасии Д.В. Надежность крупномасштабных сечен связи с аддитивной структурой / Автоматика и телемеханика. 1997. No 1. С. 160- 173.

2. Гадасип В.А., Гадаенп Д.В. Надежность двухполюсных сетей с аддитивной структурой. 1 — Точные методы / Автоматика и телемеханика. 1997. No 10. С. 78-90.

3. Гадасип В.А., Гадасип Д.В. Надежность двухполюсных сетей с аддитивной структурой. 11 — Финальная вероятность связи в сетях — решетках / Автоматика и телемеханика. 1999 (в печати).

4. Гадасип Д.В. Оценка надежности крупномасштабных сетей связи с аддитивной структурой / Международный форум инфоматпзации (МФИ — 97). Программа и тезисы докладов конференции "Телекоммуникационные и вычислительные системы". М. 1997 г. С. 46.

5. Гадасип Д.В. Надежность двухполюсных сетей связи с аддитивной структурой / Тезисы докладов LI11 научной сессии, посвященной Дню радио. Российское научно—техническое общество радиотехники, электроники и связи им. А.С.Попова. М. 1998 г., С. 35.

6. Гадасип Д.В. Методы точного нахождения вероятностных характеристик связности произвольных стохастических сетей с аддитивной структурой/ Международный форум инфоматпзации (МФИ —98). Программа и тезисы докладов конференции "Телекоммуникационные и вычислительные системы". М. 1998 г.

0!

а о~

Г) ч«/

/

ВСЕРОССИЙСКИЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ПРОБЛЕМ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНФОРМАТИЗАЦИИ

на правах рукописи УДК 519.718

ГАДАСИН Денис Вадимович

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ АНАЛИЗА ОДНОРОДНЫХ СТОХАСТИЧЕСКИХ МЕГА-СЕТЕЙ И ИССЛЕДОВАНИЕ ИХ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК

Специальность 05.13.13 — Вычислительные машины, комплексы, системы

и сети

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель — докт. техн. наук, ст. научн. сотр. ГАДАСИН В.А.

Москва - 1998

СОДЕ РЖАНИЕ

Стр.

Введение..........................................................................................................................................................................................................................................4

Глава 1. Основные определения и обозначения, постановка задачи... 15

1.1 Основные определения и обозначения, постановка задачи..................................15

1.2. Обозор литературы и обоснование направлений исследования................18

Глава 2. Методы точного вычисления характеристик связности

аддитивных сетей............................................................................. 28

2.1. Идея подхода..................................................................................................... 29

2.2. Метод точного нахождения вероятности связности всех узлов аддитивной сети................................................................................................ 30

2.3. Метод точного нахождения вероятности связности произвольного подмножества узлов — полюсов аддитивной сети.................................... 38

2.4. Трудоемкость точного вычисления характеристик связности аддитивных сетей.............................................................................................. 42

2.5. Упрощения метода для практической реализации................................. 44

2.5.1 Алгоритмизация формирования множества деформаций.................. 45

2.5.2. Декомпозиция подсети дополнения на несколько, аддитивное объединение которых дает исходную..............................................................................................................47

2.5.3. Упрощения метода при анализе изотропных аддитивных сетей..........50

Выводы............................................................................................................................................................53

Глава 3. Нахождение точных характеристик связности одномерных аддитивных сетей (на примере тестовой сети —решетки с квадратными ячейками).................................................................. 54

3.1. Исходные положения...................................................................................... 55

3.2. Алгоритмизация процесса формирования матриц перехода для

сети решетки с квадратными ячейками................................................... 57

3.3. Свойства спектра характеристических чисел (корней,

собственных значений) матриц перехода....................................................................................................64

3.4. Численный эксперимент по нахождению точных характеристик

связнгости одномерных сетей — решеток......................................................................................................76

Выводы................................................................................................................. 80

Глава 4. Оценка вероятности связности всех узлов многомерных

аддитивных сетей............................................................................. 82

4.1. Основные положения оценки характеристик связности многомерных сетей.......................................................................................... 82

4.2. Метод оценки вероятности связности всех узлов многомерных аддитивных сетей.............................................................................................. 89

4.3. Численный эксперимент и погрешность оценки вероятности

связности всех узлов многомерных аддитивных сетей......................... 98

Выводы................................................................................................................ 105

Глава 5. Оценка вероятности связи между полюсами многомерных

аддитивных сетей и ее асимптотического поведения............... 111

5.1. Метод нахождения оценки вероятности связи между полюсами

двухмерных сетей............................................................................................. 112

5.2. Выбор параметров нахождения оценки финальной надежности

связи между полюсами сети....................................................................................................................................................118

5.3. Асимптотическое значение финальной надежности связи между полюсами надежной сети..............................................................................................................................................................126

5.4. Численный эксперимент по оценке финальной надежности связи

между полюсами надежной сети....................................................................................................................................128

Выводы................................................................................................................................................................................................................................135

Заключение..............................................................................................................................................................................................................................143

Список литературы..................................................................................................................................................................................................149

Приложение. Акты и справки о внедрении..........................................................................................................152

ВВЕДЕНИЕ

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

Глобальные информационно — вычислительные сети, рост масштабности очевиден, достаточно упомянуть INTERNET.

Микросхемотехника: процессоры, схемы памяти.

Супер —ЭВМ с параллельной обработкой данных, например, построенные на транспьютерах.

Нейрокомпьютеры и нейросети.

Алгоритмы и программы параллельных, конвейерных, и т.п. вычислений.

Хранение и выборка информации в больших базах данных при естественных упрощениях могут интерпретироваться вероятностной моделью пространственной сети.

С ростом размерности сетей происходит перераспределение важности решения различных классов задач в процессе разработки и эксплуатации подобных объектов. Резко возрастает значимость анализа вероятностных характеристик избыточных сетей, частным случаем которого является проблема надежности. (Для примера — надежность 0.999 для 100 элементов переходит в 0.0001, когда их миллион).

Диссертация посвящена разработке методов и исследованию вероятностных характеристик связности однородных стохастических сетей с аддитивной структурой, включающих от тысяч до миллионов узлов и каналов связи — мега — сетей.

Однородность подразумевает отсутствие "сгустков" в сети: число каналов, примыкающих к любому узлу сети невелико. Стохастичность допускает неправильное функционирование любого элемента сети — "отказ", причем отказы элементов взаимно независимы. Связность узлов означает возможность взаимодействия между ними — наличие хотя бы одного пути из исправных (нормально функционирующих) элементов сети.

Аддитивность структуры предполагает, что сеть может быть построена итерационно — последовательным присоединением к ее текущей границе подсетей дополнения с ограниченным числом элементов. Граница подсети становится новой текущей границей сети. Максимальное число узлов текущей границы ш задает степень аддитивной сети, количество п комплектующих подсетей — ее ранг.

Одномерная аддитивность предполагает, что степень структуры невелика, т = 0(1), тогда сеть высокого ранга, п » 1, можно изобразить в виде узкой ленты "шириной" т. Многомерная аддитивность означает, что степень велика, т » 1, и для наглядного изображения сети необходима плоскость или пространство еще большей размерности. Простейший пример — двухмерная сеть в виде решетки т х п: т квадратных ячеек "по горизонтали" и п — "по вертикали".

Постановки задач, сводящиеся к подобным моделям, появились в 50 —х годах при разработке сетей связи военного и гражданского назначения. Известные методы решения, в основном — приближенные, в целом

"закрывают" проблему анализа сетей небольшого размера (десятки узлов) или декомпозируемых на такие подсети. Для произвольной структуры решение возможно только численными методами. Трудоемкость точного вычисления характеристик связности экспоненциально зависит от числа элементов и уже при сотне узлов превосходит ресурсы современных ЭВМ.

Конструктивные результаты для мега —сетей можно получить только при наложении ограничений: количественных (параметры отказа элементов) или качественных (структурных). Первые обусловлены прогрессом технологий — ростом надежности компонентов сети и, в конечном итоге, приводят к анализу почти детерминированной сети — вероятности отказа близки к нулю или единице. Чтобы сохранить трудоемкость счета постоянной при увеличении размера сети, близость к детерминированности должна возрастать, для мега —сетей приходится выходить за технологические пределы. Применение известных методов для анализа мега —сетей сопровождается аккумуляцией погрешности, что ведет либо к недопустимой ошибке, либо к огромному времени счета.

Структурные ограничения обусловлены возможностью активного использования человека на первом этапе расчетов — структурной аппроксимации исследуемой сети, включающей идентификацию класса структуры исходной сети и выбор "похожей" тестовой сети. Технические мега —сети, как правило, сравнительно однородны, либо очевидным образом декомпозируются на такие подсети, визуализация в процессе разработки принципиально необходима. Поэтому структурная аппроксимация должна быстро делаться человеком. Фактически человек решает задачу распознавания образов, имеющую на ЭВМ, по меньшей мере, экспоненциальную зависимость трудоемкости от числа элементов сети. Из

неформального закона сохранения суммарной трудоемкости отсюда объективно вытекает предпосылка упрощения анализа на последующих этапах — вычислении характеристик и адаптации результатов с учетом особенностей аппроксимации. Основное препятствие для применения — узкий исходный набор классов тестовых сетей. При сколь —нибудь нетривиальной структуре и произвольных надежностях элементов вероятностный анализ крайне сложен, известные результаты ограничиваются фактически единичными структурами. Разработка конструктивных методов анализа аддитивных, особенно многомерных (т » 1) структур, позволяет кардинально расширить возможности структурной аппроксимации.

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

Указанные факторы определяют актуальность темы диссертации.

ЦЕЛЬ ИССЛЕДОВАНИЯ.

Разработка конструктивных методов и реализуемых на стандартных ПЭВМ средств анализа стохастических сетей с многомерной (планарной, трехмерной) аддитивной структурой, формирование и обоснование

зависимостей изменения вероятностных характеристик мега —сетей при варьировании их структуры и параметров отказа элементов.

Для достижения поставленной цели были решены следующие задачи.

Дано компактное математическое описание класса сетей с однородной структурой.

Разработаны точные методы анализа узкого подкласса таких сетей, сохраняющих все основные особенности исходного класса.

Проведен численный эксперимент большого объема для формирования нипотез по приближенным методам и средствам анализа всего класса сетей.

На основе точных построены приближенные методы расчета характеристик мега —сетей с аддитивной структурой.

Оценена погрешность и область применения приближенных методов.

Проведены экспериментальные исследования зависимости характеристик аддитивных сетей от их размерности, конфигурации, параметров отказа элементов.

МЕТОДЫ ИССЛЕДОВАНИЯ.

Системный анализ, теория надежности, исследование операций, комбинаторный анализ, теория матриц.

НАУЧНАЯ НОВИЗНА. Основным научным результатом работы является совокупность методов и средств для конструктивного анализа широкого класса стохастических сетей, включающих миллионы элементов, с однородной, многомерной (планарной, трехмерной) аддитивной структурой.

Получены следующие новые результаты:

— определена и обоснована самостоятельная предметная область — аддитивные структуры, получаемые итерационным присоединением к текущей границе сети подсетей дополнения. Число комплектующих подсетей

определяет ранг п сети, количество узлов текущей границы — степень ш сети;

— на основе обобщения разработаны точные методы расчета характеристик связности произвольных аддитивных сетей, конструктивные при анализе одномерных сетей, когда т = 0(1);

— разработаны методы оценки вероятности связи всех узлов многомерных (степень т » 1) аддитивных сетей и определена их погрешность;

— разработаны методы оценки вероятности связи между полюсами многомерных (степень т » 1) аддитивных сетей, в том числе — асимптотических свойств, и определены их погрешности;

— выявлена асимптотическая независимость вероятности связи между полюсами однородной аддитивной многомерной сети от положения полюсов, если ранг, степень сети и расстояние между полюсами стремятся к бесконечности.

НА ЗАЩИТУ ВЫНОСЯТСЯ основные положения диссертации:

— совокупность методов и средств точного вычисления характеристик связности фиксированного подмножества узлов произвольных аддитивных сетей;

— алгоритмизация процесса анализа при расчете характеристик аддитивных сетей — решеток;

— совокупность методов и средств нахождения оценок вероятности связности всего множества узлов и вероятности связи между полюсами многомерных аддитивных сетей;

— метод оценки асимптотического значения вероятности связи произвольных полюсов в многомерной аддитивной сети.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ ИССЛЕДОВАНИЯ определяется результатами:

— применение методов не требует специальной подготовки и высокой квалификации исполнителя;

— соотношения для вычислений просты, программная реализация возможна на ПЭВМ с использованием широкодоступного програмного обеспечения;

— получен спектр достоверных оценок характеристик связности сетей —решеток в широком диапазоне изменения параметров отказа каналов, от 0,02 до 0,9, и числа узлов, от 400 до 10 000. Информация позволяет конкретизировать априорные представления разработчиков, так как большинство планарных сетей "похожи" на двухмерную аддитивную сеть в виде решетки т х п;

— обоснован количественный критерий сравнения собственно стохастических структур, инвариантный к размеру сети и конфигурации ее границ — асимптотическое значение вероятности связи между удаленными полюсами сети. Асимптотика не зависит от положения полюсов и определяется только их окрестностями, одинаковыми в случае однородной структуры;

— разработан инструментарий для оценки эффективности и точности известных и разрабатываемых приближенных методов анализа стохастических сетей на основе сравнения с результатами анализа тестовых многомерных аддитивных мега — структур.

ОБОСНОВАННОСТЬ РЕЗУЛЬТАТОВ И ВЫВОЛОВ.

Аналитические результаты получены корректным использованием математического аппарата и хорошо согласуются с физической

и

интерпретацией механизма связности узлов мега —сетей. Конструктивность методов проверена реальным счетом характеристик тестовых сетей — решеток, включающих десятки тысяч элементов, в широком диапазоне параметров отказа каналов. Высокая точность оценок подтверждена большим объемом численных экспериментов: для одномерных сетей — прямым сравнением с точными результатами; для многомерных структур и асимптотик — сопоставлением оценок для теоретически равных характеристик различных сетей.

СТРУКТУРА ДИССЕРТАЦИИ.

Глава 1 содержит описание объекта исследований и общую постановку задачи, формализована предметная область — аддитивные структуры п —го ранга т —й степени. Дается краткий обзор известных методов анализа стохастических сетей, на основе которого конкретизируются направления исследований.

Глава 2 посвящена методам точного анализа произвольных стохастических сетей п —го ранга т —й степени с аддитивной структурой. Методы основаны на обобщении известных результатов для рекуррентных сетей низкой (т < 3) степени и сводятся к формированию и последующему перемножению п так называемых матриц перехода. Элементы матриц определяются на основе анализа соответствующих подсетей дополнения, порядок матриц равен некоторой функции 8(т), значение которой лежит в районе т!. Отсюда теоретическая трудоемкость анализа линейно зависит от ранга п сети и