Conference publications

Abstracts

XIV conference

Анализ критических точек отказоутойчивости вычислительной среды планетарного типа

Коганов А. В., Сазонов А. Н.

НИИ Системных Исследований РАН, Россия, 117218, г. Москва, Нахимовский пр-т, 36, корп. 1. Тел/факс.: (095) 719-76-81,E-mail: koganow@niisi.msk.ru

Рассматриваются модели вычислительных сред (ВС), построенные в форме направленных графов с мечеными вершинами [1]. Стрелы графа рассматриваются как односторонние каналы передачи информации, а метки (цвета) вершин – как типы вычислительных и серверных устройств. Под разрушением ВС понимается выделение некоторого собственного подграфа модели (РВС). Под починкой РВС понимается добавление некоторых вершин и дуг из множества ВС \ РВС. Моделью задачи для ВС называется некоторый подграф этой среды. Для целей эксперимента используются полные модели задач, граф которых совпадает с графом ВС. Образом задачи называется отображение вершин графа задачи в вершины графа РВС, при котором цвет образа совпадает с цветом прообраза, и ребру в прообразе соответствует ребро в образе. Заметим, что разные вершины одного цвета могут отображаться в одну вершину. Отказом называется невозможность нахождения образа полной задачи на графе РВС. Используется бернуллиевская модель «разрушения» (исключения из РВС) исправных вершин с однородной вероятностью p, и восстановления исключенных вершин с однородной вероятностью q. Критической вероятностью разрушения для данной ВС при заданных значениях q и числе итераций Ni называется наибольшее значение p=P, при котором вероятность отказа сети менее чем за Ni итераций не превосходит заданного e.

Задача решалась методом оценки эмпирических вероятностей в многократном эксперименте на имитационной модели. В связи со сложностью поиска образа задачи на РВС для произвольных графов [2] анализ критических точек отказоустойчивости ВС проводился для специального класса ВС — планетарных вычислительных систем (ПВС). Граф ПВС двунаправленный и состоит из центральных элементов (звезд), с каждой из которых связаны серверные элементы разных типов (планеты). Звезды между собой связаны полным графом. Получены непараметрические графики и регрессионные уравнения критической вероятности отказа в зависимости от параметров сети. Значение P возрастает как с увеличением количества звезд, так и с увеличением параметров q и e. Проведено экспериментальное сравнение режимов с построением образа задачи до или после этапа восстановления. Во втором случае критическая вероятность отказа P оказалась значительно выше, а коэффициенты уравнения линейной регрессии увеличились более чем в два раза. Это подтверждает эвристические соображения о целесообразности починки сразу же после обнаружения неисправности для повышения надежности системы.

Литература.

1. Коганов А. В. Индукторные пространства как средство моделирования // Вопросы кибернетики (Алгебра, Гипергеометрия, Вероятность, Моделирование). 1999, Стр. 119-181

2. Коганов А.В., Сазонов А.Н. Анализ отказоустойчивости вычислительной среды планетарного типа. 13-я международная конференция “Математика. Компьютер. Образование”, Тезисы докладов , Дубна, 2006, с. 152.