Параллельный метод для расчета надежности сетей с ограничением на диаметр
Автор: Нестеров Сергей Николаевич, Мигов Денис Александрович
Журнал: Проблемы информатики @problem-info
Рубрика: Моделирование в системах информатики
Статья в выпуске: 4 (29), 2015 года.
Бесплатный доступ
В статье рассматривается задача точного расчета структурной надежности сети с ненадежными ребрами и абсолютно надежными вершинами. В качестве показателя надежности используется вероятность связности соответствующего случайного графа с ограничением на диаметр. Точный расчет данного показателя - NP-трудная задача, что делает его затруднительным для сетей реальной размерности. Предлагается параллельная реализация для известного метода факторизации и для его модификации, основанной на формировании всех путей между каждой парой полюсов. Разработаны два параллельных алгоритма для расчета на суперЭВМ с распределенной памятью. Результаты численных экспериментов позволили настроить параметры параллельных алгоритмов оптимальным образом и значительно повысить масштабируемость.
Надежность сети, случайный граф, диаметр графа, параллельные алгоритмы
Короткий адрес: https://sciup.org/14320291
IDR: 14320291
Список литературы Параллельный метод для расчета надежности сетей с ограничением на диаметр
- COLBOURX Сh. J. The combinatorics of network reliability. N.Y.: Oxford University Press, 1987.
- Цициашвили Г. Ш., ОСИПОВА M. А., ЛОСЕВ А. С. Асимптотика вероятности связности графа с низконадежными ребрами//Прикладная дискретная математика. 2013. № 1(19). С. 93-98.
- Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности//Проблемы информатики. 2010. № 2(6). С. 10-17.
- MLGOV D., RODIOXOV A. Parallel Implementation of the Factoring Method for Network Reliability Calculation//Springer Lecture Notes in Computer Science (in 2014, Part 6). 2014. V. 8584. P. 654-664.
- PAXDURAXGAX G., RAGHAVAX P., UPFAL E. Building Low-Diameter Peer-to-Peer Networks//IEEE Journal on Selected Areas in Communications (JSAC). 2003. V. 21(6). P. 995-1002.
- МЕЛЕНТЬЕВ В. А. Функция структурной отказоустойчивости и D-ограниченная компонента связности графа вычислительной системы//Прикладная дискретная математика. 2008. № 2(2). С.102-106.
- CANCE LA Н., Р ETINGI L. Reliability of communication networks with delay constraints: computational complexity and comlete topologies//Int. J. of Mathematics and Mathematical Sciences. 2004. V. 29. P. 1551-1562.
- CANALE E., CANCELA H., ROBLEDO F., RUBINO G., SARTOR P. On Computing the 2-Diameter-Constrained K-Reliabilitv of Networks//International Transactions in Operational Research. 2013. V. 20(1). P. 49-58.
- Мигов Д. А. Расчет надежности сети с ограничением на диаметр с применением точек сочленения//Автоматика и телемеханика. 2011. № 7. С. 69-74.
- Мигов Д. А. Расчет надежности двухполюсной сети с ограничением на диаметр с применением сечений//Проблемы информатики. 2011. № 11. С. 4-9.
- Мигов Д. А., НЕСТЕРОВ С. Н., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр//Вестник СибГУТИ. 2014. № 1. С. 49-56.
