Ускоренная имитация при моделировании сетей

Т. М. Татарникова, О. И. Кутузов (Санкт-Петербург)
 Концепция алгоритмического анализа стохастических сетевых моделей. Для количественной оценки вероятностно-временных характеристик (ВВХ) сложных систем типа информационные вычислительные сети (ИВС) нередко единственным методом решения остается статистическое моделирование на ЭВМ – метод Монте-Карло. Однако этот универсальный метод обладает существенным недостатком – медленной сходимостью. Использование расслоенной выборки и равновзвешенного метода позволяют ускорить процесс статистического моделирования сети.

При построении полной (топологически подобной) имитационной модели сети с целью оценки ее ВВХ возникает задача снижения размерности модели.

Формально уменьшение размерности может быть сведено к выделению на структуре сети некоторого множества классов объектов, с последующей их заменой соответствующими моделями. В качестве таких представителей различных кластеров целесообразно выбрать путь транспортировки транзактов между узлом-источником и узлом-отправителем (ПТТ) и декомпозировать сеть на подмножества ПТТ. В каждое подмножество включить пути, близкие по условиям транспортировки транзактов. Моделью ПТТ и объектом имитации может служить виртуальный канал (ВК), представляющий собой некоторый маршрут в сети от узла-источника до узла-адресата, состоящий из последовательности узлов коммутации-обработки транзактов и каналов связи-передачи транзактов между соседними узлами. Одна и та же модель ВК для представления разных кластеров будет отличаться только параметрами.

Для учета влияния потоков, циркулирующих по сети и являющихся фоновыми в выделенном ВК, строится вероятностный эквивалент нерассматриваемой части сети в виде генератора фоновых потоков.

При таком подходе имитируемый объект оказывается существенно меньшей размерности. Как теоретическую основу данного подхода можно рассматривать метод расслоенной выборки, предлагая в качестве совокупности факторных признаков все множество ПТТ сети.

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

Эффективность равновзвешенного расслоенного моделирования. Во многих приложениях представление показателя качества моделируемой системы используется в виде среднего риска: где  – случайный вектор, описывающий случайные процессы в моделируемой системе;  – вектор, задающий параметры модели; f(.) – функция, значение которой при различных реализациях  (i=1,2,...,N) вектора определяется в ходе вероятностного моделирования.

В частности, если f(.)= =1 при выполнении моделируемой системой заданных требований и f(.)= =0 в противном случае, то Q( ) есть вероятность выполнения заданных требований. Таким образом, решение задач, связанных с оценкой редких событий, может быть сведено к оцениванию математического ожидания М двоичной случайной величины (СВ) , заданной в виде функции = ( ), причем
СВ
=( ) имеет закон распределения p ( p), который известен.

Задача расчета оценки для М может решаться с помощью различных аналитико-статистических алгоритмов. Их эффективность будем характеризовать дисперсией оценки при фиксированном числе N опытов. Чем меньше дисперсия оценки, тем точнее алгоритм и тем он эффективнее, если, конечно, сложность расчетов в сравниваемых алгоритмах различается незначительно.

Наряду с непосредственным моделированием и с методом расслоения нас интересует также следующий конкретный вариант метода взвешенного моделирования. Вместо СВ разыгрывается равномерно распределенная СВ ,
x X, =1/n, j=1,...,n и показатель М оценивается как математическое ожидание СВ =nf( )p( ) на том основании, что М =М :

Этот конкретный прием в [4] назван равномерным взвешенным моделированием (РВМ). Для N реализаций  СВ дисперсия оценки = , получаемой РВМ, составляет D = . Если

                                                                             (1)

то РВМ не проигрывает в числе испытаний  числу испытаний  при непосредственном моделировании методом Монте-Карло. В [4] показано, что для практических приложений при разыгрывании редких событий:

t=                                                                 (2)

где  – коэффициент вариации по , т. е. по множеству вероятностей для единичных значений функции f( ).

Применение расслоения уменьшает значение t.

В общем случае при непосредственном моделировании полное количество испытаний , необходимых для получения оценки с заданной точностью, условно представим в виде двух подмножеств  и  таких, что

                                                          (3)

где  – число испытаний, реализации которых могут содержать положительный исход, т. е. в каждой из этих реализаций возникает состояние, для которого с вероятностью  возможно значение , i . Назовем такие реализации содержательными;  – число испытаний, реализации которых не могут содержать положительного исхода, т. е. в каждой из этих реализаций возникает состояние, для которого с вероятностью 1 значение =f( )=0, i . Назовем такие реализации пустыми. Тогда, чтобы при непосредственном моделировании получить  содержательных реализаций, необходимо провести в среднем

                                                                      (4)

испытаний. При этом получаем оценку, точность которой характеризуется дисперсией .

При совместном применении расслоения и РВМ проводим только содержательные испытания, число которых пусть будет равно

,                                                         (5)

получаем оценку с дисперсией D =D . Соответственно, соотношение числа испытаний при условии D =D равно

                                                  (6)

Таким образом, выигрыш в числе испытаний при переходе от непосредственного моделирования к совместному применению расслоения и РВМ имеет место при условии, что

                                                                   (7)

Оценим этот возможный выигрыш при моделировании маловероятных событий на примере расчета надежности системы, структурная схема которой изображена в виде случайного графа на рис. 1.

 

Рис. 1. Структурная схема рассматриваемой системы

Вершины (элементы системы) 1,...,15 имеются в графе с вероятностями  соответственно, дуги абсолютно надежны. Система работоспособна, если из полюса Г есть пути во все полюса п1, п2, п3 (движение против ориентированных дуг запрещено). Требуется найти вероятность отказа системы при , , , .

Система, изображенная на рис.1, имеет связность =2. Анализ [3] показывает, что при расслоенном моделировании для данных значений отказов элементов достаточно рассмотреть слои с кратностью отказов i при 2 i 3.

Для рассматриваемого примера r(+)=2.7·10-4 и =0.303. Согласно (6) выигрыш в числе испытаний при расслоении и РВМ по сравнению с непосредственным моделированием по методу Монте-Карло составит  раз.

Выигрыш в числе испытаний за счет только РВМ не столь значителен. Эффективность РВМ, оцениваемая сравнением числа обращений к ДСЧ при моделировании слоя с признаком ôaô=i, для данного примера дает следующий результат: при i=2 (i=2)=8.66; (i=2)=0.374; (1+ ) i=2.748, что дает = 3.15;
при
i=3 (i=3)=7.11; (i=3)=0.706; (1+ ) i=3.819, что дает = 1.39.

Однако применение метода РВМ позволяет не только упрощать процедуру розыгрыша состояний вектора , но сокращать и число испытаний при сохранении требуемой точности оценки.

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

Литература

1.      Башарин Г. П. Модели информационно-вычислительных систем. М.: Наука, 1993.

2.      Гриншпан Л. А. Методы анализа стохастических сетевых моделей вычислительных систем/Под ред. В. С. Танаева. Минск: Наука и техника, 1988.

3.      Яшков С. Ф. Анализ очередей в ЭВМ. -М.: Радио и связь, 1989.

4.      Кутузов О.И., Задорожный В.Н. Аналитико-статистический метод для расчета высоконадежных систем связи//Техника средств связи. Техника проводной связи. – 1990. – Вып. 1: С. 121–130.