Содержание к диссертации
Введение
Глава 1. Методы построения сетей и анализа показателей их надежности 13
1.1 Общее описание процесса построения топологии сетей 13
1.2 Метод Прима 15
1.3 Метод Прима с ограничениями 16
1.4 Метод Ежи-Вильямса 16
Глава 2. Расчет топологии сети и показателей ее надежности 26
2.1 Систематизация методов построения сетей и особенности реализации алгоритма Ежи-Вильямса 26
2.2 Расчет показателей надежности связи между источником и приемником в динамическом и стационарном режимах 31
2.3 Аналитические выражения для коэффициента готовности при резервировании 38
2.4 Введение резервных элементов в иерархические сети 41
2.5 Введение резервных линий связи между элементами 44
2.6 Определение показателей надежности области покрытия сетей путем дискретно-событийного имитационного моделирования 45
2.7 Обработка статистических данных, полученных в результате дискретно-событийного имитационного моделирования 49
2.8 Выводы по главе 2 50
Глава 3. Разработка автоматизированных систем проектирования и оценки показателей надежности сетей 53
3.1 Описание программы NetSim 53
3.2 Описание программы NetSys 61
3.3 Взаимодействие NetSim и NetSys 64
3.4 Программные утилиты 65
3.5 Используемые технологии высокороизводительных вычислений 69
3.6 Архитектура программного комплекса и его функциональная структура 69
3.7 Выводы по главе 3 70
Глава 4. Примеры расчета топологии сети и ее показателей надежности 72
4.1 Сравнение методов Прима и Ежи-Вильямса 72
4.2 Вариации метода иерархий 77
4.3 Вариации метода концентраторов 81
4.4 Моделирование с целью получения показателей надежности связи между приемником и источником 83
4.5 Анализ показателей надежности участков сети 88
4.6 Примеры вычисления коэффициента готовности в общем случае 92
4.7 Расчет области покрытия и мест для установки резервных элементов для иерархической сети аналитическим методом 95
4.8 Расчет области покрытия и введение резервных линий для произвольной сети методом Монте-Карло 99
Глава 5. Анализ работоспособности и эффективности разработанных средств 117
5.1 Валидация инструментария на практических задачах 117
5.2 Внутренняя непротиворечивость инструментария 140
5.3 Внедрение в учебный процесс 141
5.4 Возможные области применения 144
5.5 Выводы по главе 5 145
Заключение 146
Список использованных источников
- Метод Прима
- Расчет показателей надежности связи между источником и приемником в динамическом и стационарном режимах
- Описание программы NetSys
- Вариации метода иерархий
Введение к работе
Актуальность темы исследования. В связи с массовым распространением распределенных систем (базы данных, сети связи, Grid-системы, распределенные вычислительные системы) необходим анализ методов построения таких структур и определения их показателей надежности. Для обеспечения связности нескольких абонентов достаточно объединить их в древовидную (иерархическую) структуру. Однако такая структура может не обладать высокими показателями надежности, так как выход из строя одного звена, кроме оконечных, приводит к разделению сети на две подсети, обмен данными между которыми невозможен. Поэтому процесс построения сети необходимо рассматривать совместно с процессом анализа показателей надежности.
Работы, связанные с методами проектирования сетей, моделированием и/или оценкой показателей надежности, проводились, в частности, В. С. Лукьяновым, А. В. Старовойтовым, И. В. Черковским, В. М. Трухановым, Ю. В. Головановым, Б. П. Филиным, Л. И. Рожковым, К. Райншке (K. Reinschke), В. И. Мясниковым, Ю. Н. Мельниковым, Л. И. Абросимовым, Р. Примом (R. Prim), Д. А. Козловым, Н. Ф. Бахаревой, T. D. Neame, M. Zukerman, R. G. Addie, N. D. Georganas, S. Bodamer, J. Charzinski и др.
Вопросы резервирования узлов для отдельных аппаратных комплектов рассматривались в ряде источников. Также рассматривались вопросы оценки надежности сетей с обходными трактами. Обычно они базируются на полуэмпирических неформализованных рекомендациях. Например, рекомендуется в первую очередь резервировать элементы, расположенные ближе к центру сети. При расчете показателей надежности иногда делается допущения об абсолютной надежности прорезервированной аппаратуры.
В вышерассмотренных работах были предложены отдельные алгоритмы построения сетей и некоторые подходы к анализу их показателей надежности, а также некоторые конкретные примеры введения резервных элементов. Однако эти работы имеют ряд недостатков:
1) отсутствует систематизированный подход к анализу методов
построения;
2) при анализе показателей надежности существует большое количество
фрагментарных подходов;
-
часто используемые приемы резервирования носят эмпирический характер без формализации в виде критерия по вводу резервных элементов в сети;
-
не описаны конкретные инженерные методики построения сетей, анализа их показателей надежности и введения резервных элементов.
Целью диссертации является повышение эффективности процесса построения сетей, где под эффективностью будем понимать оценку по отдельным критериям: время получения результата, стоимость построенной сети, значения показателей надежности.
Для достижения поставленной цели необходимо решить следующие
задачи:
1) проанализировать существующие методы и алгоритмы построения
сетевых структур, оценки показателей надежности; произвести их сравнение по
показателям качества результата, времени выполнения и т. д.;
-
предложить новые и модифицированные алгоритмы построения сетей;
-
создать модели и алгоритмы для анализа показателей надежности связи между источником и приемником, для анализа показателей надежности покрытия сети, для введения резервных элементов в построенные сети;
-
создать программную реализацию для осуществления построения топологий сетей, оценки показателей надежности, введения резервных элементов;
-
сформулировать методики для построения топологий сетей, оценки показателей надежности, введения резервных элементов;
6) произвести валидацию созданных программных средств.
Объектом исследования являются сети связи.
Предметом исследования являются процессы построения топологий и
анализ показателей надежности аппаратуры в сетях.
Методы исследования. В процессе выполнения работы были
использованы следующие методы: системного анализа, математического
моделирования, объектно-ориентированного и процедурного
программирования, теории надежности, численные методы, использования специализированных структур представления данных при программировании, проведения высокопроизводительных вычислений.
Научная новизна работы заключается в следующем:
-
Разработаны новые имитационные и аналитические модели, а также алгоритмы на их основе для определения показателей надежности связи между источником и приемником в сети (для двух ситуаций: переходного процесса из полностью исправного состояния в отказное (динамический режим) и стационарного состояния) и покрытия сети. Предложенные алгоритмы универсальны для различных сетей и характеризуются малым временем выполнения. В случае покрытия область применения аналитической модели ограничена иерархическими сетями, но эта модель имеет самое малое время расчета.
-
Предложены новая вариация метода Ежи-Вильямса для построения сети, дающая самые высокие качественные показатели, но требующая больших временных затрат, и метод введения резервных элементов для иерархических сетей.
3) Сформулированы полуэмпирические инженерные методики для
построения сетей, оценки показателей надежности и резервирования элементов
сети.
Практическая значимость и внедрение. Разработанные средства рассчитаны на пользователей, занимающихся проектированием сетей, оценкой и/или повышением их показателей надежности. Сюда относятся провайдеры Интернет, администраторы сетей, проектировщики телефонных сетей.
Предложенные средства могут быть внедрены не только в сферы деятельности, связанные с проектированием сетей, но и в сферы, связанные с подключением абонентов к водопроводам, канализации, электроснабжению ЛЭП. Также разработанные средства могут быть внедрены при анализе показателей надежности аналогичных сетей перед построением, модификацией.
Предложенные модели и методы были реализованы в виде комплекса программных средств: “NetSim” (построение топологий сети различными методами), “NetSys” (анализ показателей надежности связи в динамическом и стационарном режиме, покрытия сети методом дискретно-событийного имитационного моделирования, введение резервных элементов по критерию), “NetAnalitic” (анализ показателей надежности связи в вышеназванных режимах методом марковских цепей), “ReserveMaster” (расчет надежности покрытия сети аналитическим способом и введение резервных элементов двумя предложенными способами), “ReserveMasterEx” (расчет показателей надежности покрытия сети методом Монте-Карло), “NetImg” (построение топологии сети в консольном режиме).
Программные средства “NetSys” и “NetAnalitic” внедрены в учебный процесс на кафедре «ЭВМ и С» в рамках дисциплин «Отказоустойчивые системы» и «Надежность и эксплуатация средств ВТ».
Получено свидетельство о регистрации программных средств “NetSim” и “NetSys” в Федеральной службе по интеллектуальной собственности.
Программные средства “NetSim” и “NetSys” внедрены в процесс проектирования и оценки показателей надежности сетевых структур в ООО “ВолгаБлоб”, г. Волгоград, что отражено в соответствующих актах.
На защиту выносятся:
1) имитационные и аналитические модели, а также построенные на их базе
алгоритмы определения показателей надежности связи между источником и
приемником в сети для двух случаев (динамического режима и стационарного
состояния) и покрытия сети;
2) новая вариация метода Ежи-Вильямса для построения сети и метод
введения резервных элементов для иерархических сетей;
-
предложенные инженерные методики для построения сетей, оценки показателей надежности и резервирования элементов сети;
-
программные продукты NetSim, NetSys, NetAnalitic, ReserveMaster, ReserveMasterEx, NetImg.
Достоверность научных результатов обеспечивается использованием
апробированных методов (системного анализа, математического
моделирования, процедурного и объектно-ориентированного
программирования, параллельного программирования), совпадением результатов аналитического и имитационного моделирования в общей области применимости, внутренней непротиворечивостью предложенных моделей, проверкой на тестовых примерах.
Апробация работы. Результаты работы обсуждались на внутривузовских научных конференциях и кафедральных семинарах кафедр «ЭВМиС» и
«САПРиПК», а также докладывались на следующих конференциях: Международная научно-практическая конференция «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2013» (г. Одесса, SWorld), Международная научно-практическая конференция «Инновационные информационные технологии» (г. Прага, 2013), XI Международная научно-практическая конференция «Перспективы развития информационных технологий» (г. Новосибирск, 2013), XXV Международная научная конференция «Математические методы в технике и технологиях» (г. Саратов, 2012). По теме диссертации опубликованы 23 печатные работы, в том числе 4 в изданиях, рекомендованных ВАК, 3 работы в зарубежных журналах (из них 1 работа в зарубежном журнале, входящем в международную базу цитирования «SCOPUS»). По результатам работы созданы два программных продукта, которые получили свидетельства о государственной регистрации.
Метод Прима
Данный метод создан, чтобы построить минимальное остовное дерево по существующему графу. Полагается, что каждый узел может быть соединён с каждым, то есть в изначальном графе каждый узел связан с каждым. Это так называемая полносвязная топология.
Он является одним из жадных алгоритмов [1]. Существуют множества вершин и дуг, входящих в оптимальное решение. На каждой итерации добавляется одна вершина и одна дуга. Выбирается самая дешёвая дуга из дуг, соединяющих вершину, входящую в оптимальное решение, и вершину, не входящую в оптимальное решение. Если несколько дуг имеют одинаковую стоимость, то выбирается любая из них. Итерации продолжаются, пока все вершины не войдут в оптимальное решение.
Существует несколько способов выбора начального значения множеств оптимального решения. Во-первых, можно найти дугу минимальной стоимости, поместить её во множество дуг, а во множество вершин поместить вершины, которая она соединяет. Если существует несколько дуг минимальной стоимости, то можно выбирать любую. Во-вторых, можно включить во множество вершин произвольную вершину. Вне зависимости от того, с какой вершиной начинается выполнение алгоритма, решение будет оптимальным.
В данном случае предполагается, что центры коммутации уже соединены, поэтому стоимость их соединения равна нулю. Значит, стартовое множество вершин будет включать множество центров коммутации. Включать или не включать дуги, соединяющие центры коммутации, роли не играет.
С одной стороны, этот метод дает оптимальное решение (т. е. решение с меньшей суммарной длиной кабеля не существует). С другой стороны, этот метод никак не учитывает ограничения, налагаемые на уплотнение канала, что не соответствует реальным практическим задачам.
Метод Прима с ограничениями — это эмпирическая модификация метода Прима [31, 32], то есть оптимальность решения не гарантируется.
Отличие от канонического метода Прима в том, что перед тем, как добавить вершину и дугу во множества оптимального решения, надо проверить ограничения. Делается это следующем образом. Канал от добавляемого узла складывается с каналом от узла, к которому осуществляется присоединение вплоть до центра коммутации. Параллельно с этим проверяются ограничения для каждого из абонентов. Если ограничения выполняются, то узел и дуга добавляются во множества. Если хоть где-то ограничения не выполняются, все изменения отменяются и выбранная дуга больше не рассматривается (как вариант можно полагать её длину равной бесконечности).
Этот метод с самого начала учитывает ограничения, поэтому соответствующая модификация не требуется. Метод является эмпирическим и даёт решение лишь близкое к оптимальному. Этот метод также является жадным алгоритмом. Первым узлом соединения будем называть узел, который присоединяют, а вторым — тот, к которому присоединяют первый. Канал проходит от первого ко второму. Первым узлом может быть только абонент, а вторым — как абонент, так и центр коммутации. В [31, 32] приведен следующий алгоритм. Сначала выбираются два узла по определённому критерию. Первый из них вместо того, чтобы присоединяться к центру коммутации, присоединяется ко второму узлу. Но перед этим проверяются отсутствие циклов и ограничения. Если уплотнение канала не противоречит ограничениям, а циклы не образуются, то соединение узлов производится, каналы уплотняются. Если хотя бы одно из условий не выполняется, то соединение первого узла со вторым больше не рассматривается, но соединение второго узла с первым при определённых условиях может быть возможно. Итерации продолжаются до тех пор, пока все абоненты не будут присоединены или пока не закончатся возможные соединения.
В [31, 32] предлагают два способа выбора пары узлов для соединения: 1) e (most expensive, самый дорогой) — выбирается такая пара, чтобы разность между расстоянием от первого узла до второго и расстоянием от первого узла до ближайшего центра коммутации была минимальной. Эта величина не может быть положительной, потому что, если положить вторым узлом ближайший центр коммутации, то получится 0 и ограничения будут верны в силу сделанных допущений. 2) f (furthest, самый дальний) – первым выбирается узел наиболее удалённый от ближайшего центра коммутации, а вторым — узел ближайший к первому. В [31, 32] предлагают два способа рассмотрения узлов: 1) s (single, одинарный) — после присоединения первого узла ко второму первый узел выводится из рассмотрения, дальнейшие подключения к нему запрещены. В этом случае образование циклов невозможно, поэтому проверку можно не проводить. Также упрощается процесс уплотнения канала: при подключении к узлу гарантируется, что он ни к чему не подключён, поэтому достаточно уплотнить лишь его канал. 2) m (multiple, множественный) — после соединения двух узлов присоединения к любому из них возможны. Образование циклов возможно, поэтому необходимо проверить, не существует ли уже в системе путь от второго узла к первому. Параллельно с этим осуществляем попытку уплотнения каналов, ведь второй узел может быть соединён со своим «вторым» узлом и канал того узла тоже надо будет уплотнять.
Расчет показателей надежности связи между источником и приемником в динамическом и стационарном режимах
Каждый элемент может находиться в (R,+ 1) состоянии, где R, число экземпляров i-го элемента. Для расчета стационарного режима методом марковских цепей N потребуется решить систему из П(Яг+1) линейных уравнений, где N 1=1 число отказывающих элементов системы. Решение теоретически возможно, но требует больших объемов памяти и больших вычислительных мощностей. Предположим, что Vі: = 1,V: R,=1 и N=15 , тогда число уравнений равно 215=32768 . Если для чисел использовать 32-битные вещественные числа, то хранение системы уравнений уйдет 4 32768 (32768 + 1) 4G6 . Поэтому будет использован другой подход. Элементы сети отказывают независимо (это предположение делается практически всегда) [36], поэтому вероятность того, что сеть находится в некотором состоянии, есть произведение вероятностей того, что ее элементы находятся в некотором N состоянии. Выбрав из П(Д,-+1) состояний рабочие состояния, можно 1=1 рассчитать их вероятности как произведения вероятностей пребывания в некотором состоянии отдельных элементов сети (они предполагаются независимыми), а затем сложить (состояния взаимоисключающие). То есть = 5 . , (2.1) где Pi - вероятность i-го состояния, W - множество рабочих состояний, К - коэффициент готовности. (2.2) (2.3) множество всех и Очевидно, что WvB = U WAB = 0 где В - множество отказных состояний, состояний. Величина {Ттк+ТЪгУ есть среднее число отказов/восстановлений в единицу времени [25]. События, которые приводят к отказам, случаются с частотой i EW jeB интенсивность переходов из i-го состояния в j-е. :І ИГ ; г- D (2.4) где ij События, которые ведут к восстановлению, происходят с частотой (2.5) (2.5) Ты (2.6) (2.7) І р, І \ ІЄВ jew Очевидно, что в силу стационарности режима ieW j EB ІЄВ j W и Т wrk Отсюда можно получить конкретные значения Например, их можно получить так: К Twrk = -1 (Twrk+Tbrk) 1-К -1 ТЬгк= (Twrk+Tbrky В динамическом режиме нас интересует первый переход в отказное состояние, поэтому все отказные состояния надо объединить в одно поглощающее состояние и запретить все переходы из отказных состояний. Вероятность этого поглощающего состояния является вероятностью отказа. Чтобы найти зависимость вероятности отказа от времени, надо решить систему линейных дифференциальных уравнений Колмогорова.
Из-за объединения всех отказных состояний число дифференциальных уравнений динамического режима не может быть больше числа линейных уравнений в стационарном режиме. Количество уравнений будет одинаковым лишь в том случае, если у системы имеется лишь одно отказное состояние. Численное решение дифференциальных уравнений занимает больше времени, чем численное решение линейных уравнений.
Если каждый элемент имеет однократное резервирование, то число рабочих состояний не менее 2N , а значит, число дифференциальных уравнений — не менее 2%1 . Показательный рост числа состояний делает невозможным использование этого метода для больших сетей. Для малого числа элементов аналитический способ подходит, но с увеличением размера задачи его ресурсоемкость сильно растет. Кроме того, аналитический способ решения требует, чтобы законы распределения всех случайных величин были показательные.
Такую систему уравнений можно решить методом Гаусса, Крамера, Жордана-Гаусса и др., но проще всего реализовать алгоритм итераций [79, 80]. Полученный вектор решений представляет собой средние времена рабочего состояния в зависимости от того, в каком из рабочих состояний начинает функционировать система. Предполагается, что система в начальный момент времени полностью исправна, поэтому необходима лишь компонента вектора, отвечающая за это время, но найти придется все компоненты.
Существует еще несколько способов оценки параметров надежности сетей произвольной структуры [47, 59]. Например, метод особой точки. В динамическом режиме он позволяет найти вероятность рабочего состояния, но только для системы без восстановления. В стационарном режиме этот метод позволяет найти коэффициент готовности. Поэтому необходим более общий способ решения. Аналитический способ не дает результата в общем случае , но может быть использован для проверки основного решения (имитационного способа).
Описание программы NetSys
Для анализа построенных топологий (см. 3.1.4.2) в программе были реализованы следующие алгоритмы обработки сетевых структур [60]: 1) алгоритм Дейкстры; 2) алгоритм Флойда; 3) задача коммивояжера (поиск наикратчайшего гамильтонового цикла); 4) поиск 4 наикратчайших путей методом поиска в глубину. Для представления результатов этих расчетов используется отдельное окно. Результаты работы первых двух алгоритмов представляются в виде таблицы, а результаты двух последних — в виде списков узлов.
Разработанная имитационная модель [51] производит анализ последствий сбоев и отказов в отдельных узлах и каналах, а также их влияния на возможность передачи сообщения в сети. Рассматриваются ситуации, в которых находится обходной путь передачи сообщений или не находится. Рассматривается динамический процесс отказов-восстановлений узлов и каналов. На основе вышеизложенного можно сформулировать следующие требования к проектируемой системе: 1) Система должна представлять собой самостоятельное приложение, не требующее для выполнения своих функций стороннего программного обеспечения, за исключением среды выполнения. 2) Программа должна поддерживать возможность анализа надежности связи между источником и приемником в динамическом и стационарном режиме. 3) Программа должна поддерживать анализ области покрытия имитационным способом. 4) Программа должна поддерживать введение резервных элементов по предложенной формуле (2.21). 5) Система должна поддерживать сохранение исследуемой сети в файл и загрузку из него. 6) Системы должна представлять данные расчета в файле, совместимом с системой LibreOffice. 7) Программа должна быть кроссплатформенной. Основной средой для ее функционирования является Linux Mint 13 Maya. 8) Система должна использовать все ресурсы многопроцессорных систем, то есть использовать возможности распараллеливания. С учётом сформулированных требований была разработана следующая структура системы. Программа разбита на две компонентны: расчетный модуль и графический модуль. Расчетный модуль написан на С++ [49, 65, 66, 74, 82, 89] с использованием технологии OpenMP [23, 86]. Код использует исключительно кроссплатформенные возможности. Сторонние библиотеки не используются. Это дает преимущества, аналогичные указанным в 3.1.3. Далее было использовано объединение двух разработанных нами программных комплектов NetSim и NetSys. На рисунке 3.5 показан пример экспорта созданной топологии из NetSim в NetSys. Впоследствии на примерах (см. подразделы 4.5, 4.7-4.9) станет видно, во-первых, что взаимодействие NetSim и NetSys позволяет вести оценку параметров надежности сетей, а, во-вторых, будет показано, как можно определять необходимость в резервных элементах и их число. Аналогично можно провести анализ участков иных сетей, например, полученных иерархическим методом или методами, не использующими уплотнение канала: методами Прима, Ёжи-Вильямса.
Для осуществления взаимодействия двух программ были предприняты следующие меры. В программу NetSim был добавлен экспорт данных в формате NetSys, а также импорт данных о резервировании из файла, сохраненного NetSys.
Программа NetImg (рис. 3.6) представляет собой набор Java-классов из модуля NetGUI программы NetSim (рис. 3.1). Эти классы выполняют преобразование вывода (stdout) модуля NetCalc в файл .png. Выделение этих классов в отдельный исполняемый файл было необходимо для упрощения отладки/валидации работы программы NetSim. Также эта утилита будет необходима для получения графического представления результатов работы модуля NetCalc в консольном режиме. Рис. 3.6 — Архитектура NetImg
Архитектура NetAnalitic Программа NetAnalitic (рис. 3.7) была создана для аналитического расчета показателей надежности связи между источником и приемником в динамическом и стационарном режимах. За один раз она сразу рассчитывает стационарный и динамический режим. Для расчета коэффициента готовности используется формула (2.1), а для расчета среднего времени рабочего состояния и среднего времени отказного состояния в стационарном режиме — формулы (2.6) и (2.7), соответственно. Для расчета среднего времени рабочего состояния в динамическом режиме решается система уравнений (2.10) с использованием метода итераций [79, 80]. Для получения зависимости вероятности рабочего состояния от времени в динамическом режиме решается система дифференциальных уравнений Колмогорова с использованием метода Эйлера (см. подраздел 2.2.1). В силу того, что расчет динамического режима является долгим по сравнению с расчетом стационарного, расчет любого из параметров динамического режима может быть отменен.
Программа ReserveMaster (рис. 3.8) осуществляет расчет показателей надежности покрытия иерархических сетей аналитическим способом и вводит резервирование обоими методами, предложенными в подразделе 2.4. Для расчета вероятностей отказов ЦК, абонентов и линий связи могут использоваться марковские приближения из подраздела 2.3. Они задаются в качестве входных параметров. Все восстановления принимаются независимыми, а резервирование — нагруженным. Программа ReserveMasterEx (рис. 3.9) ведет расчет показателей надежности сетей произвольной структуры методом Монте-Карло. Вероятности отказов ЦК, абонентов и линий связи задаются в качестве входных параметров. Для их расчета тоже могут потребоваться марковские приближения из подраздела 2.3. Программы ReserveMaster и ReserveMasterEx обмениваются данными с программой NetSys через текстовые файлы (рис. 3.3, 3.8, 3.9). Используются марковские приближения для расчета коэффициентов готовности (см. подраздел 2.3). В подразделе 2.3 даются формулы для расчета коэффициента готовности аналитическим способом (с марковским приближением). Они использовались для построения графиков в этом подразделе. Для имитационного расчета использовались формулы из монографии [25] и программные разработки [50, 52], а также материалы [16-19]. 3.5 Используемые технологии высокороизводительных вычислений Для ускорения вычислений использовались следующие подходы к проведению высокопроизводительных вычислений. Использование специализированных структур данных [1], в частности бинарных куч [71, 72], позволяет организовать быструю выборку следующего события имитационной модели (см. рис. 2.4, 2.5, 2.6), а также следующего элемента для резервирования при резервировании по критерию (формулы (2.18) и (2.21)). Использование технологии распараллеливания вычислений OpenMP [23, 86] производится не только для распараллеливания испытаний имитационного моделирвоания (NetSys, ReserveMasterEx), но и для распараллеливания итераций алгоритмов построения сетей там, гда это возможно и целесообразно (NetSim), для распараллеливания итераций расчета методом марковских цепей (NetAnalitic), для распараллеливания переборного варианта введения резервных элементов в иерархические сети (ReserveMaster).
Использование различных режимов оптимизации, профилирование программных разработок с помощью утилиты gprof [78, 83, 91] позволило повысить работоспособность кода и сократить время наиболее «тяжелых» участков кода.
Вариации метода иерархий
Существуют две модификации метода иерархий: с улучшением и без [41]. Для их сравнения рассмотрим пример №2, полученный с использованием NetSim. Пример был сгенерирован автоматически. Рис. 4.8 — Пример №2 после применения метода иерархий без улучшения На рисунке 4.8 представлен результат работы метода иерархий без улучшения, стоимость которого составляет 10930.9.
Использование улучшения оценок снижает стоимость сети (рис. 4.9) до 9636.2. Очевидно, что процедура улучшения снижает стоимость сети почти на 12% и не требует значительного количества дополнительного времени, поэтому все следующие примеры будут рассмотрены только в варианте с улучшением. Рис. 4.9 — Пример №2 после применения метода иерархий с улучшением краевых точек Пример №3 получим следующим образом: сгенерируем 140 случайных абонентских точек внутри круга (рис. 4.10) радиуса 20 ед. и преобразуем их в иерархию, разрешив подключать к коммутатору до 20 абонентов. Ширину канала каждого абонента зададим случайным числом, равномерно распределенным от 0 до 1000. Максимальную ширину канала ограничим 10000. В результате использования метода иерархий с улучшением получим следующую топологию (рис. 4.11). Стоимость соединения составляет 947. Рис. 4.10 — Пример №3 без соединения Этот расчет занимает меньше 50 мсек. Составим зависимость времени расчета от числа случайных точек (табл. 4.3) внутри такого круга. Табл. 4.3 — Зависимость времени расчета и стоимости от числа абонентов Число точек Стоимость Время расчета, сек 500 1698.26 0.39 1000 2656.07 2.948 1500 3324.59 10.389 2000 3979.46 24.211 Рис. 4.11 — Построенная иерархия для примера №3 Анализ данных из таблицы 4.3 позволяет сделать вывод, что время выполнения метода иерархий пропорционально кубу числа абонентских пунктов, то есть O(n3) .
Пример №3 после применения метода добавления Рассмотрим пример №3, который был использован для построения топологии методом иерархии (рис. 4.10). Необходимо построить топологию как методом добавления, так и методом удаления, разрешив подключать к коммутатору до 20 абонентов. Будем полагать, что коммутатор эквивалентен 120 ед. кабеля. Рассмотрим результаты по методу добавления (рис. 4.12) и методу удаления (рис. 4.13). Первая сеть имеет стоимость 1258.82 (из них 898.823 за кабель), вторая — 1339.15 (из них 1099.15 за кабель). Алгоритм добавления использует три концентратора из четырех, алгоритм удаления — два.
Оценить производительность алгоритмов сложно, так как расчеты ведутся слишком быстро. Надо увеличить число точек до 10000. Ввиду невозможности визуального анализа таких схем, они здесь не приводятся. Сведем данные в таблицу 4.4. Отсюда видно, что метод удаления дает результат несколько хуже и требует значительно больше времени для его получения.
Можно сделать вывод, что метод удаления дает результат более низкого качества и требует гораздо больше времени для расчета, поэтому в дальнейшем будет использован метод добавления.
В качестве примера №4 возьмем систему, изображенную на рисунке 4.14. В отличие от всех остальных, этот пример не получен с использованием NetSim. Это система взята на основе экспертных оценок из [31, 32]. Пуассоновские потоки даны такими: для элементов сети «Пр» и «Ус» - 0,1 отк/час, для линий связи «Св» - 0,01 отк/час, а для источника и приемника «A» и «B» - 0,02 отк/час. Среднее время восстановления для всех элементов равно 2 часам. Стрелками указано направление прохождения сигнала [36]. Источник и приемник имеют однократное нагруженное резервирование.
Пример №4 Под резервированием подразумевается нагруженное резервирование, т. е. существуют два источника и два приемника, работающих параллельно, и при отказе одного может продолжать работать другой. Моделирование работы системы будем проводить: 1) без восстановления (I); 2) с экспоненциальным восстановлением (E); 3) с восстановлением по закону Вейбулла с параметром 3,31 (W); 4) с детерминированным временем восстановления2 (C). Для генерации случайного значения интервала времени, распределенного по экспоненциальному закону (в том числе для интервала между событиями простейшего потока) воспользуемся формулой [31]: t=-m-ln(l-R) . (4.1) А для получения значения, распределенного по закону Вейбулла [31] «V-ln(l-S) " () , (4.2) где і?є[0;і) - случайное равномерно распределенное число, т -математическое ожидание случайного значения времени, r(v) — гамма-функция Эйлера.
Для выполнения расчета с заданной погрешностью необходимо провести предварительные испытания [31, 32]. Для оценки погрешности используется правило трех сигм [56]. При числе испытаний в 1000 относительная погрешность среднего времени безотказной работы, в соответствии с ЦПТ, достигает 10%. Вычислительные ресурсы позволяют увеличить число испытаний в 100 раз, что сократит погрешность в V100=10 раз. Поэтому будем проводить именно 100000 испытаний. Известно [31, 32], что абсолютная погрешность измеряемой путем имитационного моделирования вероятности при числе испытаний не менее 1 Это делает закон распределения близким к нормальному [44, 45]. 2 Время восстановления всегда одно и то же. 20-40 не может превосходить 2 ZN , где - квантиль нормального распределения для требуемого уровня значимости, N - число испытаний. Для правила трех сигм квантиль равняется трем. Поэтому абсолютная погрешность измерения вероятности не превосходит 0,005. Рассмотрим систему при разных законах восстановления (рис. 4.15). Графики W и C совпали, ввиду того, что для закона распределения времени восстановления W мода близка к матожиданию, для закона восстановления C они совпадают, а для E мода равна нулю. Поэтому у системы с восстановлением E будет больше времен восстановления, которые короче среднего (примерно 63%). Сведем среднее время рабочего состояния системы в единую таблицу (табл. 4.5). Ее относительная погрешность, полученная при моделировании, — 0,91%.
