Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?

Научные направления

Поделиться:
Статья опубликована в №3 (ноябрь) 2013
Разделы: Информационные технологии, Математика
Размещена 30.11.2013. Последняя правка: 29.11.2013.
Просмотров - 3002

АНАЛИЗ ОБЛАСТИ ПОКРЫТИЯ СЕТЕЙ ПРОИЗВОЛЬНОЙ СТРУКТУРЫ С ОПРЕДЕЛЁННЫМИ ПОКАЗАТЕЛЯМИ НАДЁЖНОСТИ

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

ВолгГТУ

Аспирант

Гаевой Сергей Владимирович, аспирант, ВолгГТУ, кафедра


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


Abstract:
Due to wide spread of the distributed computing systems a problem of its effective usage became actual. Therefore the analysis of algorithms used in similar systems is necessary. In this paper an attempt to investigate a coverage area of a network with some reliability indices has been made. One has proposed an algorithm how to determine the size of reserve. The method of simulation modeling was used to solve this problem.


Ключевые слова:
сети, имитационное моделирование, область покрытия, показатели надежности.

Keywords:
net, network, simulation modeling, simulation, coverage area, reliability indices.


УДК 004.94

ВВЕДЕНИЕ

Ранее проблема надежности сетей рассматривалась нами с позиция существования связи между отдельным абонентом и ЦК [1][2]. Теперь ее необходимо рассмотреть с позиции множества абонентов, то есть с позиции покрытия зоны обслуживания. В системе существует набор серверов, которые осуществляют обслуживание, и набор клиентов, которые пользуются обслуживание. Из-за отказов определенных часть абонентов может оказываться вне зоны доступа, то есть отрезанной от серверов. Необходимо определить количественные показатели данной системный. К ним относится вероятность того, что в системе вне зоны доступа находятся не более некоторого числа узлов, а также среднее число абонентов вне зоны доступа. Можно определить еще среднюю вероятность пребывания абонента вне зоны доступа (вероятность пребывания вне зона доступа может быть различна для различных абонентов).

ОПРЕДЕЛЕНИЕ ОБЛАСТИ ПОКРЫТИЯ

1 Рассматриваемая система

Сказанное проще всего пояснить примером. Рассмотрим сеть, построенную методом Ежи-Вильямса (рис. 1) [3][4] с использованием [5]. Красные точки — это абоненты, , розовая — ЦК, синие линии — линии связи.

Одной из современных технологий построения городских Интернет-сетей является использование VPN-сервера как шлюза для доступа к глобальной сети. Это позволяет, провести аутентификацию пользователя. Используемыми протоколами являются PPTP и L2TP. По такой схеме построен Интернет таких провайдеров, как «Коламбия» и «Билайн». Альтернативной технологией является PPPoE («Дом.Ру»), но ее мы рассматривать не будем.

В данном контексте в ЦК будет находится L2TP-сервер. Целью является рассмотреть покрытие сети абонентов. То есть назвать предполагаемое количество обслуживаемых абонентов в зависимости от показателей надежности. Определим следующие характеристики для элементов системы (табл. 1).

 

Рисунок 1 — Сеть, построенная метод Ежи-Вильямса

Таблица 1 — Параметры надежности элементов сети

Элемент

Интенсивность отказов,

Среднее время восстановления, час

Нагруженное резервирование

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

100

2

0

Линия связи

10

1

0

ЦК

50

3

2

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

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

2 Метод решения

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

На этот раз в качестве метода решения возьмем метод имитационного моделирования. Этот метод, в частности метод дискретных событий, мы уже использовали ранее в [9][10]. Использование метода имитационного моделирования преследует три цели. Во-первых, проверить, аналитическое решение; во-вторых, создать средство, которое в перспективе будет использовано для анализа сетей произвольной структуры; в-третьих, использовать законы распределения случайных величин, отличные от экспоненциальных. Несмотря на произвольность закона распределения, мы будем использовать экспоненциальные законы, что иметь возможность сравнить аналитическое и имитационное решения.

Событиями модели являются отказы и восстановления. Из-за наличия резервирования не всякий отказ или восстановление приводят к имению области покрытия. Только отказы последнего элемента в резерве и восстановление первого элемента приводят к изменению топологии.

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

Чтобы определить область покрытия (то есть число абонентов, имеющих доступ к ЦК), достаточно воспользоваться алгоритмом Дейкстры [11]. Сначала серверы получат оценку 0, а все остальные узлы — бесконечность. Стоимости дуг принимают нулевыми. Затем запускается алгоритм Дейкстры. Клиенты, сохранившие оценку в бесконечность, — вне зоны покрытия.

Путем имитационного моделирования можно снять определенные характеристики. Будем выбирать число испытаний равным 30, а длину интервала моделирования достаточной, чтобы относительная погрешность результата не превосходила 2%.

3 Система «как есть»

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

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

В качестве средства мы воспользуемся модификацией [12]. Рассмотрим вышеуказанные параметры для сетей разной размерности (табл. 2).

Очевидно, что КГ убывает с увеличением размерности сети, а среднее число абонентов вне обслуживания и вероятность необслуживания растут. Налицо сверхлиненый рост среднего число абонентов вне обслуживания.

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

 

Таблица 2 — Параметры надежности сетей

Размер

сети

КГ, 0%

КГ, 5%

КГ, 10%

Среднее число абонентов вне обслуживания

Средняя вероятность необслуживания

100

0,81075

0,908042

0,933935

2,15665

0,0215665

200

0,657418

0,870347

0,923604

6,23743

0,0311872

500

0,350238

0,734173

0,842575

24,6016

0,0492032

1000

0,122764

0,666957

0,791553

67,2183

0,0672183

 

4 Резервирование элементов сети

Необходимо ввести критерий уровня резервирования. Мы уже делали это для иерархических сетей в [6][7], поэтому рассмотрим вопрос обобщения.

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

p = λt / (λt + 1) , (1)

где λ- интенсивность отказов, t - среднее время восстановления.

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

В случае наличия R резервных элементов вероятность пребывания элемента в состоянии отказа равняется p^(R+1). Для случая наличия зависимости в восстановлении резервных элементов эту величину может потребоваться рассчитывать имитационно как дискретную функцию от R.

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

Важностью элемента назовем сумму его необходимостей для всех клиентов. Очевидно, что важностью ЦК будет количество клиентов. Обозначим важность k. Очевидно, что элементы с k = 0 можно сразу исключить из рассмотрения.

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

k * p ^(R + 1) (2)

Введем предельный уровень отказов , то есть максимально возможное значение величины, указанной выше. Иными словами,

k * p ^(R + 1) ≤ d (3)

Из (3) можно выразить размер резерва. Округление надо вести вверх.

Запретим элементам получать резерв меньше, чем указано в табл. 1. Осуществим резервирование вышеуказанным способом (табл. 3, 4).

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

Теперь среднее число абонентов вне обслуживания растет почти линейно. Вероятность необслуживания слабо меняется с ростом объема сети. Предложенная схема резервирования компенсирует это. Коэффициент готовности при ненулевом допуске (табл. 3 и 4) также мало зависит от размера сети.

Изменим сеть из 100 абонентов, изображенную на рисунке 1. Отобразим на ней места, где программа установила резервы в случаях d = 0.02 (рис. 3) и d = 0.01 (рис. 3). Число резервов отметим ниже и правее самого узла.

Обратите внимание, что линии связи в этом примере не получили резерва, так как их коэффициент простоя ниже на порядок: для абонента это — 0,2%, а для линии связи — 0,01%. Для полноты картины скажем, что коэффициент простоя ЦК — 0,15%.

 

Таблица 3 — Параметры надежности системы с резервом (d = 0.02)

Размер

сети

КГ, 0%

КГ, 5%

КГ, 10%

Среднее число абонентов вне обслуживания

Средняя вероятность необслуживания

100

0,864264

0,967946

0,995414

0,55354

0,0055354

200

0,745309

0,98679

0,996044

1,26005

0,00630025

500

0,530305

0,985538

0,992963

3,03031

0,00606062

1000

0,277661

0,985206

0,99396

5,96584

0,00596584

 

Таблица 4 — Параметры надежности системы с резервом (d = 0.01)

Размер

сети

КГ, 0%

КГ, 5%

КГ, 10%

Среднее число абонентов вне обслуживания

Средняя вероятность необслуживания

100

0,886718

0,99329

0,996617

0,364732

0,00364732

200

0,794811

0,993631

0,996752

0,698709

0,003493545

500

0,602071

0,987999

0,995161

1,81432

0,00362864

1000

0,354584

0,990277

0,999114

3,50115

0,00350115

 

Очевидно, что на рис. 3, по сравнению с рис. 2, появляются дополнительные резервы: резервируются более удаленные (менее важные элементы).

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

 

Рисунок 2 — Вариант расстановки резервов (d = 0.02)

 

Таблица 4 — Средняя вероятность необслуживания

Размер сети

Без резервирования

С резервированием 
(d = 0.02)

С резервированием 
(d = 0.01)

100

0,021585

0,005542

0,003644

200

0,031198

0,006408

0,003495

500

0,049203

0,006056

0,003630

1000

0,067231

0,005962

0,003502


Рисунок 3 — Вариант расстановки резервов (d = 0.01)

 

ЗАКЛЮЧЕНИЕ

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

Библиографический список:

1 Лукьянов, В.С. Оценка показателей надёжности сетей / Лукьянов В.С., Гаевой С.В., Аль-Хадша Ф.А.Х. // Вестник компьютерных и информационных технологий. - 2013. - № 8. - C. 47-52.
2 Лукьянов, В.С. Оценка показателей надёжности сетей в стационарном режиме / Лукьянов В.С., Гаевой С.В., Аль-Хадша Ф.А.Х. // Известия ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 16 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2013. - № 8 (111). - C. 165-169.
3 Аль-Хадша, Ф.А.Х. Проектирование топологии сети с ограниченной шириной канала методами Прима и Ёжи-Вильямса / Аль-Хадша Ф.А.Х. // Математические методы в технике и технологиях – ММТТ-25 : сб. тр. XXV междунар. науч. конф. В 10 т. Т. 5. Секции 8, 9 (г. Волгоград, 29-31 мая 2012 г.) / ВолгГТУ [и др.]. - Саратов, 2012. - C. 115-116.
4 Лукьянов, В.С. Проектирование топологических сетей с ограничением по пропускной способности канала / Лукьянов В.С., Аль-Хадша Ф.А.Х. // Известия ВолгГТУ. Серия «Актуальные проблемы управления, вычислительной техники и информатики в технических системах». Вып. 14 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2012. - № 10 (97). - C. 193-199.
5 Свид. о гос. регистрации программы для ЭВМ № 2013616401 от 8 июля 2013 г. РФ, МПК (нет). Автоматизированная система проектирования топологий сетей (NetSim) / Аль-Хадша Ф.А.Х., Лукьянов В.С.; ВолгГТУ. - 2013.
6 Лукьянов, В.С. Анализ области покрытия иерархических сетей с определёнными показателями надёжности / Лукьянов В.С., Аль-Хадша Ф.А.Х., Гаевой С.В. // Сборник научных трудов SWorld по матер. междунар. науч.-практ. конф. «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2013» (18-29 июня). - 2013. - Вып. 2, т. 8. - C. 5-10.
7 Лукьянов, В.С. Анализ области покрытия иерархических сетей с определёнными показателями надёжности [Электронный ресурс] : доклад / Лукьянов В.С., Аль-Хадша Ф.А.Х., Гаевой С.В. // Современные проблемы и пути их решения в науке, транспорте, производстве и образовании ’2013 : докл. на междунар. науч.-практ. Интернет-конф. (18-29 июня 2013 г.) / Проект SWorld. – Режим доступа : http://www.sworld.com.ua/index.php/ru/technical-sciences-213/electrical-engineering-radio-engineering-213/17944-213-039 (дата обращ. 27.06.2013).
8 Аль-Хадша, Ф.А.Х. Анализ области покрытия сетей произвольной структуры, обладающих показателями надёжности / Аль-Хадша Ф.А.Х., Гаевой С.В., Лукьянов В.С. // России – творческую молодёжь : матер. I всерос. науч.-практ. студ. конф., г. Камышин, 22-23 мая 2013 г. В 4 т. Т. 2 / ВолгГТУ, КТИ (филиал) ВолгГТУ. - Волгоград, 2013. - C. 11-12.
9 Имитационное моделирование грид-систем : монография / Лукьянов В.С., Андреев А.Е., Жариков Д.Н., Островский А.А., Гаевой С.В.; ВолгГТУ. - Волгоград, 2012. - 215 с.
10 Имитационная модель гетерогенной вычислительной системы / Лукьянов В.С., Жариков Д.Н., Гаевой С.В., Попов Д.С. // Изв. ВолгГТУ. Серия "Актуальные проблемы управления, вычислительной техники и информатики в технических системах". Вып. 11 : межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2011. - № 9. - C. 85-88.
11 Филлипс, Д. Методы анализа сетей / Д. Филлипс, А. Гарсиа-Диас : Пер. с англ. — М. : Мир, 1984. — 496 с., ил.
12 Свид. о гос. регистрации программы для ЭВМ № 2013614144 от 24 апреля 2013 г. РФ, МПК (нет). Имитационная модель для оценки влияния параметров надёжности и иных характеристик на передачу сообщений в сетевых системах (NetSys) / Гаевой С.В., Аль-Хадша Ф.А.Х., Лукьянов В.С.; ВолгГТУ. - 2013.




Рецензии:

1.12.2013, 22:39 Назарова Ольга Петровна
Рецензия: Логично изложен материал. В каком пакете выполнялись расчеты, уточните.Рекомендуется к печати

02.12.2013 13:13 Ответ на рецензию автора Аль-Хадша Фарес Али:
Проектирование и моделирование велось пакетах собственной разработки. Ссылки на них даны в тексте в соответствии с ГОСТом: "Сказанное проще всего пояснить примером. Рассмотрим сеть, построенную методом Ежи-Вильямса (рис. 1) [3][4] с использованием [5]." "В качестве средства мы воспользуемся модификацией [12]. " А в списке использованных источников указано: "5 Свид. о гос. регистрации программы для ЭВМ № 2013616401 от 8 июля 2013 г. РФ, МПК (нет). Автоматизированная система проектирования топологий сетей (NetSim) / Аль-Хадша Ф.А.Х., Лукьянов В.С.; ВолгГТУ. - 2013." "12 Свид. о гос. регистрации программы для ЭВМ № 2013614144 от 24 апреля 2013 г. РФ, МПК (нет). Имитационная модель для оценки влияния параметров надёжности и иных характеристик на передачу сообщений в сетевых системах (NetSys) / Гаевой С.В., Аль-Хадша Ф.А.Х., Лукьянов В.С.; ВолгГТУ. - 2013. "



Комментарии пользователей:

2.12.2013, 16:17 Назарова Ольга Петровна
Отзыв: Спасибо!


2.12.2013, 23:07 Аль-Хадша Фарес Али
Отзыв: И Вам спасибо!


Оставить комментарий


 
 

Вверх