автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Построение распределенных сетевых структур и анализ показателей их надежности

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

Аль-Хадша Фарес Али Хуссейн

ПОСТРОЕНИЕ РАСПРЕДЕЛЕННЫХ СЕТЕВЫХ СТРУКТУР И АНАЛИЗ ПОКАЗАТЕЛЕЙ ИХ НАДЕЖНОСТИ

05.13.01 - Системный анализ, управление и обработка информации (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

15 ПАЯ 2014

005549133

Волгоград -2014

005549133

Работа выполнена на кафедре «Электронно-вычислительные машины и системы» в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Волгоградский государственный технический университет»

Научный руководитель доктор технических наук, профессор

Фоменков Сергей Алексеевич.

Научный консультант доктор технических наук, профессор

Лукьянов Виктор Сергеевич.

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

Финогеев Алексей Германович

доктор технических наук, профессор, ФГБОУ ВПО «Пензенский государственный университет» г. Пенза, кафедра «Системы автоматизации проектирования», профессор;

Македонский Сергей Александрович

кандидат технических наук, Волгоградский филиал Акционерного банка «РОССИЯ», главный специалист по информационной безопасности.

Ведущая организация ФГБОУ ВПО «Астраханский

государственный технический университет» («АГТУ»), г. Астрахань.

Защита состоится «11» июня 2014 года в 15:00 часов на заседании диссертационного совета Д 212.028.04, созданного на базе Волгоградского государственного технического университета по адресу: 400005, г. Волгоград, пр. Ленина 28, ВолгГТУ, ауд. 209.

С диссертацией можно ознакомиться в библиотеке Волгоградского государственного технического университета.

Автореферат разослан «21» апреля 2014 г.

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

диссертационного совета Водопьянов Валентин Иванович

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

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

Работы, связанные с методами проектирования сетей, моделированием и/или оценкой показателей надежности, проводились, в частности, В. С. Лукьяновым, А. В. Старовойтовым, И. В. Черковским, В. М. Трухановым, Ю. В. Головановым, Б. П. Филиным, JI. И. Рожковым, К. Райншке (К. Reinschke), В. И. Мясниковым, Ю. Н. Мельниковым, JI. И. Абросимовым, Р. Примом (R. Prim), Д. А. Козловым, Н. Ф. Бахаревой, Т. D. Neame, М. Zukerman, R. G. Addie, N. D. Georganas, S. Bodamer, J. Charzinski и др.

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

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

1) отсутствует систематизированный подход к анализу методов построения;

2) при анализе показателей надежности существует большое количество фрагментарных подходов;

3) часто используемые приемы резервирования носят эмпирический характер без формализации в виде критерия по вводу резервных элементов в сети;

4) не описаны конкретные инженерные методики построения сетей, анализа их показателей надежности и введения резервных элементов.

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

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

задачи:

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

2) предложить новые и модифицированные алгоритмы построения сетей;

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

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

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

6) произвести валидацию созданных программных средств.

Объектом исследования являются сети связи.

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

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

Научная новизна работы заключается в следующем:

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

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

3) Сформулированы полуэмпирические инженерные методики для построения сетей, оценки показателей надежности и резервирования элементов сети.

Практическая значимость и внедрение. Разработанные средства рассчитаны на пользователей, занимающихся проектированием сетей, оценкой и/или повышением их показателей надежности. Сюда относятся провайдеры Интернет, администраторы сетей, проектировщики телефонных сетей.

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

Предложенные модели и методы были реализованы в виде комплекса программных средств: 'Т^Бип" (построение топологий сети различными методами), "КеЙуз" (анализ показателей надежности связи в динамическом и стационарном режиме, покрытия сети методом дискретно-событийного имитационного моделирования, введение резервных элементов по критерию), "Ые1Апа1Шс" (анализ показателей надежности связи в вышеназванных режимах, методом марковских цепей), "11е8егуеМа51ег" (расчет надежности покрытия сети аналитическим способом и введение резервных элементов двумя предложенными способами), "11езегуеМаз1егЕх" (расчет показателей надежности покрытия сети методом Монте-Карло), 'ТЧеИгг^" (построение топологии сети в консольном режиме).

Программные средства 'Т^Був" и "№1Апа1Шс" внедрены в учебный процесс на кафедре «ЭВМ и С» в рамках дисциплин «Отказоустойчивые системы» и «Надежность и эксплуатация средств ВТ».

Получено свидетельство о регистрации программных средств "МеЙпп" и "№13уз" в Федеральной службе по интеллектуальной собственности.

Программные средства "МйЗпп" и "ЫйЗув" внедрены в процесс проектирования и оценки показателей надежности сетевых структур в ООО "ВолгаБлоб", г. Волгоград, что отражено в соответствующих актах.

На защиту выносятся:

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

2) новая вариация метода Ежи-Вильямса для построения сети и метод введения резервных элементов для иерархических сетей;

4) предложенные инженерные методики для построения сетей, оценки показателей надежности и резервирования элементов сети;

5) программные продукты ^Бип, КйБув, №1АпаШк, 11езегуеМаз1ег, 11езегуеМаз1егЕх, Ыейпщ.

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

Апробация работы. Результаты работы обсуждались на внутривузовских научных конференциях и кафедральных семинарах кафедр «ЭВМиС» и

«САПРиПК», а также докладывались на следующих конференциях: Международная научно-практическая конференция «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2013» (г. Одесса, SWorld), Международная научно-практическая конференция «Инновационные информационные технологии» (г. Прага, 2013), XI Международная научно-практическая конференция «Перспективы развития информационных технологий» (г.Новосибирск, 2013), XXV Международная научная конференция «Математические методы в технике и технологиях» (г. Саратов, 2012). По теме диссертации опубликованы 23 печатные работы, в том числе 4 в изданиях, рекомендованных ВАК, 3 работы в зарубежных журналах (из них 1 работа в зарубежном журнале, входящем в международную базу цитирования «SCOPUS»). По результатам работы созданы два программных продукта, которые получили свидетельства о государственной регистрации.

Структура и содержание диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения, а также библиографического списка из 91 наименований и двух приложений. Общий объем работы 162 страницы, в том числе 73 рисунка и 31 таблица.

СОДЕРЖАНИЕ РАБОТЫ

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

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

По результатам анализа делается вывод о необходимости систематизации вариаций метода Ежи-Вильямса, о детальном изучении вариаций метода Прима, метода иерархий, метода концентраторов.

При использовании метода Ежи-Вильямса проводится выбор пар узлов для соединения. Этот выбор можно сделать двумя способами. Также двумя способами можно обрабатывать уже созданные пары. Поэтому потенциально возможны четыре варианта, но в литературе описаны только три из них. Четыре различных варианта алгоритма рассмотрены подробнее во второй главе.

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

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

Также отмечается отсутствие доступных программных пакетов для реализации вышеуказанных алгоритмов.

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

В данной главе приводится систематизация методов построения сетей, а также обобщенная схема алгоритма Ежи-Вильямса (рис. 1), где присутствуют два правила, каждое из которых имеет два варианта (е или f, s или m). В первой главе было выявлено, что существуют три варианта алгоритма Ежи-Вильямса (fs, fin, es). В данной работе предлагается четвертый (ет), который дает самые хорошие результаты при самых больших временных затратах. Наличие вариаций позволяет выбирать метод с позиции соотношения «стоимость сети — время получения результата».

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

Обозначим как get_time_for_work(i) процедуру получения случайного времени безотказной работы i -го экземпляра, а за get_time_for_break(i) — случайного времени пребывания его в состоянии отказа, m — число элементов системы, п — суммарное число экземпляров.

Введем матрицу состояния системы в начальный момент времени: 1 get_time_for_work(l)

А = 1 get_time_for_work(2)

1 get_time_for_work(n)

Особые моменты будут происходить во времена . Единица в

первом столбце означает исправность экземпляра, а О — пребывание в состоянии отказа. Алгоритм моделирования динамического режима представлен на рисунке 2, стационарного — на рисунке 3.

Для динамического режима строится график вероятности работоспособности системы как функции времени. Среднее время рабочего состояния определяется как оценка математического ожидания времени работы. Для стационарного режима определяются среднее время рабочего состояния, среднее время отказного состояния, коэффициент готовности.

Рис. 1 — Обобщенный алгоритм Ежи-Вильмса

Коррекция головы кучи

Регистрируем время отказа

как А[1][2]

Рис. 2 — Блок-схема алгоритма одного испытания имитационного моделирования связи

9

Рис. 3 — Блок-схема алгоритма одного испытания имитационного моделирования связи

Расчет надежности покрытия может быть осуществлен как путем аналитического, так и путем имитационного моделирования. При аналитическом решении область применимости ограничена иерархическими сетями, но время расчета ниже на порядки по сравнению с имитационными способом.

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

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

Математическое ожидание этой случайной величины дается формулой *-(1-ЛГ(ж)) , (1)

где К(м) - зависимость собственного коэффициента готовности от размера резерва.

Резервируются узлы с максимальным значением этого параметра.

Если сеть не является иерархической, то для расчета надежности покрытия необходимо использовать имитационные методы. Одним из них является метод Монте-Карло. Дискретно-событийная имитационная модель используется в качестве альтернативы. Преимуществами является то, что эта модель позволяет найти некоторые дополнительные характеристики надежности сети и использовать законы распределения случайных величин без приближений и допущений. Недостатком является то, что время расчета является самым большим. Алгоритм на рис. 3 был модифицирован так, чтобы анализировать покрытие (рис. 4).

В третьей главе производится описание программных разработок ^Бнп, ШБув, КезегуеМаз1ег, КевегуеМа^егЕх, ШАпаНйс, ЫеЯгсщ. Приводятся также архитектуры созданных систем, их функционал, режимы работы, взаимодействия программных продуктов, обосновывается выбор средств разработки и используемой операционной системы. Указаны методы, использованные для высокопроизводительных вычислений:

специализированные структуры данных, в частности бинарные кучи; технология распараллеливания ОрепМР; оптимизация, профилирование.

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

Рис. 4 — Блок-схема алгоритма одного испытания имитационного моделирования покрытия сети

В таблице 1 представлено сравнение вариаций метода Ежи-Вильямса. Очевидной становится проблема соотношения цены и качества. Видно, что при различии в стоимости сети в 5-10% время расчета может различаться в десятки и сотни раз. Стоит отметить, что классический метод Прима не учитывает ограничения, поэтому его решение не является верным в общем случае — оно лишь показывает нижнюю границу стоимости.

Табл. 1 — Сравнение методов на сети из 1600 абонентов

Метод

Прима

Прима с ограничениями

Ёжи-Вильямса (em)

Ёжи-Вильямса (fm)

Стоимость сети, у.е.

1221

2224

1710

1798

Время расчёта, сек

4,6

312

165

1,0

Ёжи-Вильямса (fs)

1826

0,7

Ёжи-Вильямса (es)

1752

71

Также для сети, изображенной на рисунке 5, проводится анализ показателей надежности сети при различных законах восстановления и экспоненциальном законе отказов. Пуассоновские потоки отказов даны такими: для элементов сети «Пр» и «Ус» - 0,1 отк/час, для линий связи «Св» - 0,01 отк/час, а д.чя источника и приемника «А» и «В» - 0,02 отк/час. Среднее время восстановления для всех элементов равно 2 часам. Источник и приемник имеют однократное нагруженное резервирование. Под резервированием подразумевается нагруженное резервирование, т. е. существуют два источника и два приемника, работающих параллельно, и при отказе одного может продолжать работать другой.

Для сравнения представлены аналитические (Anal) и имитационные (Sim) данные для случаев без восстановления (I) и с марковским (Е) восстановлением динамического режима (рис. 6). Также представлено среднее время до отказа в динамическом режиме и параметры стационарного режима (табл. 2). Очевидно, что решения двумя этими способами практически совпадают, что позволяет с большой долей вероятности говорить о правильности подхода.

Для примера №2 (рис. 7, табл. 3), состоящего из 100 клиентов, проводится анализ области покрытия. Сервер предполагается расположенным в начале координат. Покрытие детально анализируется в трех случаях: 1) для текущего состояния (до выполнения резервирования); 2) после выполнения обычного резервирования (32 итерации резервирования); 3) после усиленного резервирования (45 итераций).

Рис. 5 — Пример №1

Табл. 2 — Сравнение результатов аналитического и имитационного

моделирования

Модель Динамический режим Стационарный режим

Среднее время работы, ч Среднее время работы, ч Среднее время отказа, ч Коэффициент готовности

Siml 8,14088 — — —

Anall 8,14287 — — —

SimE 21,9415 17,8138 0,921644 0,950804

AnalE 21,8987 17,8359 0,922993 0,950797

Время, ч

Рис. 6 — Сравнение результатов аналитического и имитационного моделирования для динамического режима примера №1

-Siml

ша еез Anal!

-SlmE

вш ma AnalE

Табл.3 — Параметры надежности элементов сети из примера №2

Элемент Интенсивность отказов, 10"5час"1 Среднее время восстановления, час Нагруженное резервирование

Абонентское оборудование 100 2 0

Линия связи 10 1 0

Центр коммутации 50 3 2

Табл. 4 — Средняя вероятность необслуживания из примера №2

Резервирование ЛезегуеМа81ег КезегуеМа51егЕх №18уз (в режиме покрытия)

Нет 0,021585 0,021603 0,0215665

Обычное 0,005542 0,005540 0,0055354

Усиленное 0,003644 0,003651 0,00364732

Введено резервов

Рис. 8 — Последовательность увеличения коэффициента готовности при резервировании для примера №2

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

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

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

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

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

В частности проводится расчет примера из таблицы 1 сторонними средствами (вариант &). Построенная сеть имеет топологию, идентичную нашему примеру, но программа выдает результат 1825 у.е. из-за другого принципа округления. Процедура построения сторонними средствами занимает 2,6 сек, что примерно в 3,5-4 раза больше, чем время выполнения разработанной нами программы.

Также приводится валидация методов расчета показателей надежности на примере №3 (рис. 9). Предполагается, что слева от схемы расположен источник, а справа — приемник. При анализе покрытия источник принимался сервером, а приемник — единственным клиентом.

Рис. 9 — Пример №3 для валидации средств оценки надежности

Восстановление всех блоков считается независимым. Блоки 1 и 2 образуют первое устройство (оно функционирует, если исправен хотя бы один из них), а блок 3 — второе (функционирует, если исправен этот блок). Отказы и восстановления в примере принимаются марковскими. Интенсивность отказов — Х- 0,01/час, а восстановлений — р. = 1/час.

Табл. 5 — Проверка программных средств для оценки надежности

Параметр №1АпаШю (связь) ЯезегуеМ^егЕх Ыейув ¡Эталон (покрытие)

Стационарный режим

К 0,990002 0,990003 0,990002 10,990003 0,9900019509

Ттк,час ¡98,0769 98,073 ! ~ . _ 1 98,0769230769

Динамический режим без восстановления

Тшк.час 66,6667 66,6661 -- — ¡66,6666666667

Динамический режим с марковским восстановлением

Тшк,час 98,1132 ¡98,1132 — — 198,1132075472

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

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

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

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

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

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

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

1. На основе литературных источников произведен анализ и сравнение методов построения сетей, предложена их систематизация, оценена область применимости методов. На основе систематизации представлена новая вариация метода Ежи-Вильямса, дающая самые высокие качественные показатели, но требующая больших временных затрат.

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

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

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

5. Разработаны программные средства ШБт, Ы^Буз, №1Апа1Шс, Ке5егуеМаБ1ег, Кезег/еМаз1егЕх, реализующие предложенные модели и алгоритмы.

6. Произведен анализ работоспособности и эффективности созданных средств на тестовых примерах. Валидность средств подтверждена совпадением

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

ОСНОВНЫЕ ПУБЛИКАЦИИ Статьи в журналах, рекомендуемых ВАК

1. Аль-Хадша, Ф.А.Х. Выбор в сети k-кратчайших путей / Аль-Хадша Ф.А.Х. // Изв. ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 12 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2011. - № 11. - С. 136-137.

2. Лукьянов, B.C. Оценка показателей надёжности сетей / Лукьянов

B.C., Гаевой C.B., Аль-Хадша Ф.А.Х. // Вестник компьютерных и информационных технологий. - 2013. - № 8. - С. 47-52.

3. Лукьянов, B.C. Оценка показателей надёжности сетей в стационарном режиме / Лукьянов B.C., Гаевой C.B., Аль-Хадша Ф.А.Х. // Известия ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 16 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2013. - № 8 (111). - С. 165-169.

4. Лукьянов, B.C. Проектирование топологических сетей с ограничением по пропускной способности канала / Лукьянов B.C., Аль-Хадша Ф.А.Х. // Известия ВолгГТУ. Серия «Актуальные проблемы управления, вычислительной техники и информатики в технических системах». Вып. 14 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2012. - № 10 (97). - С. 193-199.

Статьи в журналах SCOPUS

5. Аль-Хадша, Ф.А.Х. The coverage analysis of hierarchical networks with specified reliability indices / Аль-Хадша Ф.А.Х., Гаевой C.B., Лукьянов B.C. // International Review on Computers and Software (IRECOS). - 2013. - Vol. 8, No. 5 -

C. 1199-1202.

Свидетельства о регистрации программных систем

6. Свид. о гос. регистрации программы для ЭВМ № 2013614144 от 24 апреля 2013 г. РФ, МПК (нет). Имитационная модель для оценки влияния параметров надёжности и иных характеристик на передачу сообщений в сетевых системах (NetSys) / Гаевой C.B., Аль-Хадша Ф.А.Х., Лукьянов B.C.; ВолгГТУ. -2013.

7. Свид. о гос. регистрации программы для ЭВМ № 2013616401 от 8 июля 2013 г. РФ, МПК (нет). Автоматизированная система проектирования топологий сетей (NetSim) / Аль-Хадша Ф.А.Х., Лукьянов B.C.; ВолгГТУ. - 2013.

Статьи в журналах и сборниках

8. Аль-Хадша, Ф.А.Х. Исследование сертификационного центра на базе веб-сервера / Аль-Хадша Ф.А.Х. // Бизнес. Образование. Право. Вестник Волгоградского института бизнеса. Серия "Бизнес". - 2008. - № 5. - С. 98-101.

9. Аль-Хадша, Ф.А.Х. Assessment of the Network Reliability / Аль-Хадша Ф.А.Х., Гаевой C.B., Лукьянов B.C. // Communications in Control Science

and Engineering (CCSE). - 2013. - Vol. 1, Issue 4, October. - C. 58-62.

10. Лукьянов, B.C. Design Methods of Network Cabling With Concentrators / Лукьянов B.C., Аль-Хадша Ф.А.Х. // International Journal of Psycho-Educational Sciences / AREES University. - 2012. - Issue 1, No. 1, December. - C. 95-102. - Eng.

11. Аль-Хадша, Ф.А.Х. Оценка влияния параметров надёжности на производительность участков сети / Аль-Хадша Ф.А.Х. // Перспективы развития информационных технологий : сб. матер. XI междунар. науч.-практ. конф. (Новосибирск, 28 февр. 2013 г.) / Центр развития научного сотрудничества (ЦРНС). - Новосибирск, 2013. - С. 122-126.

12. Аль-Хадша, Ф.А.Х. Показатели надёжности отдельных участков иерархических сетей / Аль-Хадша Ф.А.Х., Гаевой С.В. // Инновационные информационные технологии : матер, междунар. науч.-практ. конф., г. Прага, Чехия, 22-26 апр. 2013 г. В 4 т. Т. 2 / МИЭМ НИУ ВШЭ [и др.]. - М., 2013. - С. 109-111.

13. Аль-Хадша, Ф.А.Х. Проектирование топологии сети с ограниченной шириной канала методами Прима и Ёжи-Вильямса / Аль-Хадша Ф.А.Х. // Математические методы в технике и технологиях - ММТТ-25 : сб. тр. XXV междунар. науч. конф. В 10 т. Т. 5. Секции 8, 9 (г. Волгоград, 29-31 мая 2012 г.) / ВолгГТУ [и др.]. - Саратов, 2012. - С. 115-116.

' 14. Лукьянов, B.C. Анализ области покрытия иерархических сетей с определёнными показателями надёжности / Лукьянов B.C., Аль-Хадша Ф.А.Х., Гаевой С.В. // Сборник научных трудов SWorld по матер, междунар. науч.-практ. конф. «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2013» (18-29 июня). - 2013. - Вып. 2, т. 8. - С. 5-10.

Подписано в печать 10.04.2014 г. Формат 60x84 1/16. Бумага офсетная. Печать трафаретная. Печ. л. 1,0. Тираж 100 экз. Заказ № 197.

Типография ИУНЛ Волгоградского государственного технического университета. 400005, г. Волгоград, просп. им. В.И. Ленина, 28, корп. №7.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» (ВолгГТУ)

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

04201459845

АЛЬ-ХАДША ФАРЕС АЛИ ХУССЕЙН

ПОСТРОЕНИЕ РАСПРЕДЕЛЕННЫХ СЕТЕВЫХ СТРУКТУР И АНАЛИЗ ПОКАЗАТЕЛЕЙ ИХ НАДЕЖНОСТИ

05.13.01 - "Системный анализ, управление и обработка информации (промышленность)"

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор

Фоменков Сергей Алексеевич

Научный консультант: доктор технических наук,

профессор_

Лукьянов Виктор Сергеевич

Волгоград-2014

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..............................................................................................................6

ГЛАВА 1. МЕТОДЫ ПОСТРОЕНИЯ СЕТЕЙ И АНАЛИЗА ПОКАЗАТЕЛЕЙ ИХ НАДЕЖНОСТИ..............................................................................................13

1.1 Общее описание процесса построения топологии сетей........................13

1.2 Метод Прима................................................................................................15

1.3 Метод Прима с ограничениями..................................................................16

1.4 Метод Ежи-Вильямса..................................................................................16

1.5 Использование пассивных и активных концентраторов..........................18

1.5.1 Метод иерархий....................................................................................18

1.5.2 Метод концентраторов.........................................................................20

1.6 Постановка задачи оценки параметров надежности связи между источником и приемником................................................................................21

1.7 Проблема резервирования иерархических сетей.....................................23

1.8 Постановка задач диссертации...................................................................24

ГЛАВА 2. РАСЧЕТ ТОПОЛОГИИ СЕТИ И ПОКАЗАТЕЛЕЙ ЕЕ НАДЕЖНОСТИ.....................................................................................................26

2.1 Систематизация методов построения сетей и особенности реализации алгоритма Ежи-Вильямса.................................................................................26

2.2 Расчет показателей надежности связи между источником и приемником в динамическом и стационарном режимах.....................................................31

2.2.1 Расчет аналитическим способом.........................................................31

2.2.2 Расчет способом дискретно-событийного имитационного моделирования...............................................................................................34

2.3 Аналитические выражения для коэффициента готовности при резервировании..................................................................................................38

2.4 Введение резервных элементов в иерархические сети............................41

2.5 Введение резервных линий связи между элементами.............................44

2.6 Определение показателей надежности области покрытия сетей путем

дискретно-событийного имитационного моделирования.............................45

2.7 Обработка статистических данных, полученных в результате дискретно-событийного имитационного моделирования.............................49

2.8 Выводы по главе 2.......................................................................................50

ГЛАВА 3. РАЗРАБОТКА АВТОМАТИЗИРОВАННЫХ СИСТЕМ ПРОЕКТИРОВАНИЯ И ОЦЕНКИ ПОКАЗАТЕЛЕЙ НАДЕЖНОСТИ СЕТЕЙ .................................................................................................................................53

3.1 Описание программы №18нп.....................................................................53

3.1.1 Общие требования к системе..............................................................53

3.1.2 Выбор средства реализации................................................................55

3.1.3 Архитектура системы...........................................................................56

3.1.4 Функционал инструментария..............................................................58

3.1.4.1 Задание набора абонентов............................................................58

3.1.4.2 Построение топологии..................................................................60

3.1.4.3 Анализ построенных топологий..................................................61

3.2 Описание программы Ке18у8.....................................................................61

3.2.1 Общие требования к системе..............................................................61

3.2.2 Выбор средства реализации................................................................62

3.2.3 Архитектура системы...........................................................................62

3.2.4 Функционал инструментария..............................................................63

3.3 Взаимодействие Ке18кп и Ке18уБ.............................................................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.4.1 Пример расчета динамического режима путем дискретно-событийного имитационного моделирования............................................84

4.4.2 Пример расчета стационарного режима путем дискретно-событийного имитационного моделирования............................................86

4.4.3 Аналитический расчет динамического и стационарного режимов. 87

4.5 Анализ показателей надежности участков сети.......................................88

4.6 Примеры вычисления коэффициента готовности в общем случае.........92

4.7 Расчет области покрытия и мест для установки резервных элементов для иерархической сети аналитическим методом.........................................95

4.8 Расчет области покрытия и введение резервных линий для произвольной сети методом Монте-Карло......................................................99

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

4.10 Использование обобщенного критерия введения резерва...................106

4.11 Методики построения сетей, анализа и улучшения их показателей надежности.......................................................................................................107

4.11.1 Построение иерархической сети....................................................107

4.11.2 Построение сети с активными концентраторами..........................109

4.11.3 Анализ показателей надежности связи между источником и приемником..................................................................................................110

4.11.4 Анализ показателей надежности покрытия сети...........................112

4.11.5 Введение резервных элементов в иерархическую сеть................113

4.12 Выводы по главе 4...................................................................................115

ГЛАВА 5. АНАЛИЗ РАБОТОСПОСОБНОСТИ И ЭФФЕКТИВНОСТИ

РАЗРАБОТАННЫХ СРЕДСТВ...........................................................................117

5.1 Валидация инструментария на практических задачах...........................117

5.1.1 Расчет методов Прима и Ежи-Вильямса на тестовом примере №1 .......................................................................................................................117

5.1.2 Расчет методом Ежи-Вильямса на тестовом примере №2..............121

5.1.3 Валидация методов расчета надежности на примере №1..............128

5.1.3.1 Тестовый пример №1..................................................................128

5.1.3.2 Расчет стационарного режима примера №1.............................129

5.1.3.3 Расчет динамического режима без восстановления для примера №1.............................................................................................................131

5.1.3.4 Расчет динамического режима с восстановлением для примера №1.............................................................................................................133

5.1.3.5 Временные показатели расчета..................................................136

5.1.4 Валидация методов расчета надежности связи в динамическом режиме на примере №2...............................................................................137

5.2 Внутренняя непротиворечивость инструментария................................140

5.3 Внедрение в учебный процесс.................................................................141

5.4 Возможные области применения............................................................144

5.5 Выводы по главе 5.....................................................................................145

ЗАКЛЮЧЕНИЕ....................................................................................................146

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ...........................................148

ПРИЛОЖЕНИЕ А. СВИДЕТЕЛЬСТВА О ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРОГРАММ............................................................................159

1

ПРИЛОЖЕНИЕ Б. АКТЫ ВНЕДРЕНИЯ ПРОГРАММНЫХ РАЗРАБОТОК 161

ВВЕДЕНИЕ

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

Работы, связанные с методами проектирования сетей, моделированием и/или оценкой показателей надежности, проводились, в частности, В. С. Лукьяновым, А. В. Старовойтовым, И. В. Черковским,

В. М. Трухановым, Ю. В. Головановым, Б. П. Филиным, Л. И. Рожковым, К. Райншке (К. Reinschke), В. И. Мясниковым, Ю. Н. Мельниковым, Л. И. Абросимовым, Р. Примом (R. Prim), Д. А. Козловым, Н. Ф. Бахаревой, Т. D. Neame, М. Zukerman, R. G. Addie, N. D. Georganas, S. Bodamer, J. Charzinski и др.

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

В вышерассмотренных работах были предложены отдельные

алгоритмы построения сетей и некоторые подходы к анализу их показателей надежности, а также некоторые конкретные примеры введения резервных элементов. Однако эти работы имеют ряд недостатков:

1) отсутствует систематизированный подход к анализу методов построения;

2) при анализе показателей надежности существует большое количество фрагментарных подходов;

3) часто используемые приемы резервирования носят эмпирический характер без формализации в виде критерия по вводу резервных элементов в сети;

4) не описаны конкретные инженерные методики построения сетей, анализа их показателей надежности и введения резервных элементов.

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

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

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

2) предложить новые и модифицированные алгоритмы построения

сетей;

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

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

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

6) произвести валидацию созданных программных средств.

Объектом исследования являются сети связи.

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

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

Научная новизна работы заключается в следующем:

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

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

3) Сформулированы полуэмпирические инженерные методики для построения сетей, оценки показателей надежности и резервирования элементов сети.

Практическая значимость и внедрение. Разработанные средства рассчитаны на пользователей, занимающихся проектированием сетей, оценкой и/или повышением их показателей надежности. Сюда относятся провайдеры Интернет, администраторы сетей, проектировщики телефонных сетей.

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

Предложенные модели и методы были реализованы в виде комплекса программных средств: "№18ип" (построение топологий сети различными методами), 'ЧЧе18у8" (анализ показателей надежности связи в динамическом и стационарном режиме, покрытия сети методом дискретно-событийного имитационного моделирования, введение резервных элементов по критерию), 'ТЧе1АпаШ1с" (анализ показателей надежности связи в обоих режимах методом марковских цепей), "11е8ер/еМа81ег" (расчет надежности покрытия сети аналитическим способом и введение резервных элементов двумя предложенными способами), "Ке5еп/еМа81егЕх" (расчет показателей надежности покрытия сети методом Монте-Карло), 'ЧЧеАп^" (построение топологии сети в консольном режиме).

Программные средства "NetSys" и "Ке1Апа1Шс" внедрены в учебный процесс на кафедре «ЭВМ и С» в рамках дисциплин «Отказоустойчивые системы» и «Надежность и эксплуатация средств ВТ».

Получено свидетельство о регистрации программных средств 'Т^Зпп" и "Не13уз" в Федеральной службе по интеллектуальной собственности.

Программные средства "№13нп" и 'Ч^Зуэ" внедрены в процесс проектирования и оценки показателей надежности сетевых структур в ООО

"ВолгаБлоб", г. Волгоград, что отражено в соответствующих актах.

На защиту выносятся:

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

2) новая вариация метода Ежи-Вильямса для построения сети и метод введения резервных элементов для иерархических сетей;

4) предложенные инженерные методики для построения сетей, оценки показателей надежности и резервирования элементов сети;

5) программные продукты NetSim, NetSys, NetAnalitic, ReserveMaster, ReserveMasterEx, Netlmg.

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

Апробация работы. Результаты работы обсуждались на внутривузовских научных конференциях и кафедральных семинарах кафедр «ЭВМиС» и «САПРиПК», а также докладывались на следующих конференциях: Международная научно-практическая конференция

«Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2013» (г. Одесса, SWorld), Международная научно-практическая конференция «Инновационные информационные технологии» (г. Прага, 2013), XI Международная научно-практическая конференция «Перспективы развития информационных технологий» (г. Новосибирск, 2013), XXV Международная научная конференция

«Математические методы в технике и технологиях» (г. Саратов, 2012). По теме диссертации опубликованы 23 печатные работы, в том числе 4 в изд�