1
УДК 681.32-192
Моделирование надежности компьютерной сети
© А.М. Андреев, Г.П. Можаров
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Исследована надежность компьютерных сетей, структура которых хорошо
отображается в виде случайного графа сетевого типа. Рассмотрена задача
оценки вероятности связности случайного граф, посредством моделирования
надежности компьютерных сетей, а также возможности управления надежно-
стью и качеством компьютерных сетей. Изучена вероятность связности двух
выбранных узлов сети между собой или одного из узлов сети со всеми остальны-
ми. Определены верхние и нижние границы для мер наиболее надежной коммуни-
кационной сети.
Ключевые слова:
компьютерная сеть, моделирование надежности, границы
надежности, связность, случайный граф, разделяющее множество.
Введение.
Компьютерная сеть (КС) представляется моделью в
виде линейного графа, в котором узлы или вершины соответствуют
КС, а ребра — линиям связи между ними. Критерии надежности для
такой модели могут определяться различными способами. Простей-
шим критерием [1, 2] является минимум ребер или узлов, которые
должны быть удалены, чтобы нарушить все пути между любой
оставшейся парой узлов. Эта мера, известная как связность графа,
равняется нижней границе максимального числа узлов, разъединяю-
щих пути между любой парой узлов. Более общим критерием [3–5]
является минимальное число ребер, которое должно быть удалено из
графа, чтобы изолировать любой подграф из
m
узлов от остального
графа. Эту величину обозначим
.
m
Аналогично можно сформу-
лировать критерий для случая отказа узлов [6, 7].
Отказы узлов или ребер в сети появляются случайно. Показате-
лем общей надежности сети является верхняя граница вероятности
прерывания обслуживания между любой парой действующих узлов,
определяемая заданным числом узлов и ребер в любом разделяющем
множестве сети и их надежностью. Вычисление этой вероятности ос-
новывается также на максимальном числе разделяющих множеств,
удаление которых приводит к нарушению связи между любой парой
действующих узлов в КС.
Математическая модель надежной компьютерной сети.
Веро-
ятностные характеристики надежных компьютерных сетей могут
быть определены для случая статистически независимых контактов.
Любая двухполюсная сеть из
m
контактов будет связана с вероятно-
стью
g p
и замкнута с вероятностью
:
h p
