Параллельный метод для расчета надежности сетей с ограничением на диаметр

Автор: Нестеров Сергей Николаевич, Мигов Денис Александрович

Журнал: Проблемы информатики @problem-info

Рубрика: Моделирование в системах информатики

Статья в выпуске: 4 (29), 2015 года.

Бесплатный доступ

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

Еще

Надежность сети, случайный граф, диаметр графа, параллельные алгоритмы

Короткий адрес: https://readera.ru/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.
Еще
Статья научная