|
Архив публикацийТезисыXV-ая конференцияФазовый переход отказоустойчивости в растущих сетях произвольной начальной конфигурации.koganow@niisi.msk.ru, 117218,Москва, Нахимовский п-т, 36, корп.1, НИИСИ РАН 1 стр.В нескольких предыдущих работах (1-2) и др. авторы исследовали отказоустойчивость вычислительных сетей на графе для случаев стационарного или растущего графа сети. Отказы элементов и на каждом такте работы сети формируются бернуллиевским испытанием на исправных элементах, а восстановления формируются бернуллиевским испытанием на разрушенных элементах. Вероятности этих испытаний фиксированы. Сеть считается работоспособной, пока ее исходный граф можно изоморфно вложить в ее исправный подграф, с учетом типов элементов, которые сопоставлены вершинам графа сети. Отказом сети считается первый такт работы, когда теряется работоспособность. Дополнительно требуется при наращивании сети не порождать связей между элементами тех типов, которые не связаны в исходной сети. Оценивалась средняя наработка (матожидание отказа) и асимптотика наработки для растущего графа сети (работоспособность определяется для вложения начального графа сети). Было обнаружено свойство появления положительной вероятности неограниченно долгой безотказной работы сети при достаточно быстром наращивании (критическая скорость роста). Этот результат был аналитически доказан (1) в частном случае корпоративных сетей (полный граф связей элементов) и подтвержден вычислительно (2) для случая планетарного графа (несколько звездообразных графов с центрами, связанными полным графом). Сходный эффект описан в (3). Для произвольной исходной сети рассмотрены два алгоритма наращивания сети: простое дублирование (изолированные экземпляры исходной сети) и связное дублирование (соответственные элементы каждого экземпляра связаны в полный граф и дуги исходного графа порождают соответсвенные дуги между любой парой экземпляров). Доказано, что при равной кратности дублирования наработка на отказ выше у связного дублирования. Доказывается, что для обоих алгоритмов имеется критическая скорость роста и ее параметрическая оценка имеет логарифмический порядок по числу тактов. Доказательство опирается на результат из (1). Литература. 1). Коганов А. В., Сазонов А. Н. Корпоративные вычислительные сети с разрушением и восстановлением. Фазовый переход в растущих сетях. // Математика. Компьютер. Оборазование: Сб. научных трудов. Том 2/ Под ред. Г.Ю.Ризниченко. - М.-Ижевск: НИЦ "Регулярная и хаотическая динамика". 2007. С. 48-59. 2) Коганов А.В., Сазонов А.Н. Анализ критических точек отказоустойчивости вычислительной среды планетарного типа. Программные продукты и системы, приложение к международному журналу «Проблемы теории и практики управления», №3, 2007, с. 27-31 3). Цициашвили Г.Ц., Маркова Н. В. Переходные явления в объединённой системе резервирования с восстановлением. Дальневосточный математический журнал, 2001, Том 2, №2, стр. 106-114. |
