Поскольку в дискретно-событийной модели все изменения происходят только во время возникновения событий, периоды бездействия системы пропускаются, и часы переводятся со времени возникновения одного события на время возникновения другого. Отметим, что при продвижении времени с постоянным шагом такие периоды бездействия не пропускаются, что приводит к большим затратам компьютерного времени, поэтому такой подход используется гораздо реже (29, стр.66).

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

состояние системы - совокупность переменных состояния, необходимых для описания системы в определенный момент времени;

часы модельного времени-переменная, указывающая текущее значение модельного времени;

список событий-список, содержащий время возникновения каждого последующего типа событий;

статистические счетчики-переменные, предназначенные для хранения статистической информации о характеристике системы;

алгоритм инициализации - алгоритм, устанавливающий модель в исходное состояние модель в момент времени, равный 0;

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

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

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

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

Для моделирования процесса функционирования логической схемы, её описание, полученное во время разработки, вместе с начальными значениями входных сигналов схемы подаётся на вход системе моделирования. Начальные значения входных сигналов могут генерироваться случайно или определяться исходя из спецификаций моделируемой схемы. В процессе моделирования определяются значения сигналов на выходах схемы. Это позволяет определить, соответствуют ли результаты функционирования схемы и скорость её работы спецификациям и ожидаемым результатам.

Основные действия, производимые при логическом моделировании идентичны для всех уровней абстракции моделируемых схем и моделей дискретного времени. Каждый элемент схемы имеет, по крайней мере, один вход и, по крайней мере, один выход, а также своё внутреннее состояние, зависящее от времени. Входы и выходы различных элементов схемы соединены между собой проводниками, по которым распространяются значения сигналов на входах и выходах элементов. Значения сигналов могут изменяться в дискретные моменты времени. Проводники в системе моделирования реализуются как узлы, в которых хранится текущее значение сигнала проводника и, возможно, будущее изменение этого сигнала. На значение сигнала в проводнике могут оказывать влияние выходы сразу нескольких элементов схемы, соединённые с этим проводником. По этой причине, узел должен отделять значения сигналов подаваемых на выходы связанных с ним элементов от входов связанных с ним элементов.

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

Для простоты, внешние входы элементов (контакты микросхемы) рассматриваются как узлы, которые управляют соединёнными с ними элементами схемы, подавая на них значения сигналов с внешних выводов.

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

Каждый цикл моделирования состоит из трёх шагов. На первом шаге происходит моделирование запланированных элементов схемы, и определение их нового состояния. Изменения состояний элементов могут привести к изменениям на выходах элементов, которые соединены с входами других элементов через промежуточные узлы. В этом случае на втором шаге, когда входов всех элементов схемы известны, согласно функции разрешения определяются новые значения сигналов узлов. На третьем шаге происходит планирование элементов схемы для повторного моделирования. В частности, планируются для последующего моделирования те элементы схемы, которые управляются узлами, на которых изменилось значение сигнала на предыдущем шаге.

Размещено на http://www.allbest.ru/

8

Рисунок 3.2 - Основная процедура моделирования.

Моделирование схемы заканчивается только тогда, когда на очередном цикле моделирования не произошло никаких изменений, или когда выполняется предопределённое условие завершения (например, время моделирования достигнет некоторого предельного значения).

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

Основным критерием, по которому отличают различные стратегии моделирования, является способ, которым осуществляется продвижение по модельному времени. В соответствии с этим все методы моделирования можно разделить на два класса (18, стр.103):

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

Этот метод является наиболее простым способом моделирования. Продвижение по модельному времени при таком способе моделирования, как правило, осуществляется на одинаковые интервалы. Для каждого такого интервала модельного времени происходит моделирование всех элементов схемы. Новые состояния элементов и значения сигналов сохраняются в переменных, и которые будут использоваться на следующем шаге модельного времени в качестве старых состояний элементов и значений сигналов. Третий этап цикла моделирования основной схемы вырождается в планирование на моделирование всех элементов схемы. Однако, эта стратегия может быть оптимизирована, путём моделирования только тех элементов схемы, для которых значения сигналов на входах были изменены на предыдущем шаге модельного времени. Эта оптимизированная стратегия также известна как синхронное моделирование, управляемое событиями.

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

Моделирование, управляемое событиями: Основным недостатком моделирования, управляемого временем является существование множества холостых шагов модельного времени (в течение которых не происходило никаких изменений в состояниях элементов или значений сигналов). Поэтому много времен расходуется на моделирование элементов, которые не изменяют своё состояние и значения сигналов, и на проверку того, произошли ли в схеме изменения, по сравнению с предыдущим шагом, или нет. Этот недостаток устраняется при моделировании, управляемом событиями, при котором изменения сигналов моделируются как события, связанные с определёнными шагами модельного времени. Шаги модельного времени указывают, на то, когда должны произойти эти события. Для сохранения последовательности событий во времени при моделировании, управляемом событиями, события всегда моделируются в порядке увеличения модельного времени. Таким образом, интервалы модельного времени, в течение которых не происходит никаких изменений в схеме, не моделируются, что обычно приводит к более быстрому моделированию.

Все методы распараллеливания логического моделирования могут быть разделены на два класса: методы синхронного и асинхронного параллельного логического моделирования.

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

Таким образом, после каждого цикла синхронного моделирования происходит синхронизация всех моделирующих процессоров. Следовательно, получаемое при синхронном параллельном моделировании ускорение зависит от скорости моделирования отдельных элементов схемы. Скорость увеличения модельного времени относительно реального времени определяется элементами схемы моделируемыми медленнее всех.

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

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

Для поддержания требуемого порядка обработки событий все события помещаются в очередь событий в порядке увеличения времени их наступления. ЛП всегда выбирает из очереди событий событие с самым маленьким временем наступления и обрабатывает его. При обработке очередного события локальное модельное время увеличивается до времени наступления этого события. Обработка очередного события также может привести к созданию нескольких новых событий, которые наступят в следующие моменты модельного времени. Если новое событие оказывает влияние на элементы локальной части схемы, то оно просто помещается в локальную очередь событий.

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

В случае параллельного логического моделирования, события отражают изменения сигналов, которые управляют или управляются элементами схемы. Так как обычно сигналы реализуются как узлы, то изменения сигналов, которые оказывают влияние на другие части схемы, должны также распространяться через узлы. Это означает, что узлы сами могут быть распределенными, если их входы и выходы соединяют части схемы, обрабатываемые различными ЛП (11, стр.312). Таким образом, в качестве таких распределённых узлов выступают создаваемые и пересылаемые сообщения для передачи изменений сигналов на удалённые части схемы.

Обычно подразумевается, что узел и все элементы схемы, связанные с этим узлом, находятся в одном и том же ЛП. Если узлы и связанные с ними элементы схемы были помещены в различные логические процессы, то должна быть проделана дополнительная работа для сохранения состояний узлов. Это выполняется с помощью сообщений. Следовательно, узлы, связывающие элементы схемы разных ЛП могут рассматриваться как специальные типы элементов схемы, пропускающие сигнал от одного ЛП к другому.

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

При последовательном моделировании событие с временем наступления t1 не может обрабатываться раньше события с временем наступления t2 если t2 < t1. Т.е. при последовательном моделировании порядок обработки событий соответствует времени их наступления. Это означает, что все события ei, которые могут оказать влияние на событие ej, обрабатываются перед обработкой события ej. Таким образом, при моделировании соблюдаются последовательность событий и зависимости между ними имеющие место в реальной системе. Для событий имеющих одинаковое время наступления должны использоваться подходы, гарантирующие определённость и повторяемость. Для простоты далее будет подразумеваться, что при моделировании не может возникнуть двух событий с одинаковыми временами наступления.

В параллельной среде, где каждый ЛП имеет своё собственное локальное модельное время и локальное состояние, глобальное состояние не доступно. В связи с этим, логическому процессу сложно предсказать, произойдёт ли в другом логическом процессе удалённое событие для данного логического процесса, которое имеет время наступление меньше чем времена наступления всех событий в его локальной очереди событий. Если произойдёт такое удалённое событие, то оно должно быть обработано перед обработкой всех локальных событий данного ЛП для поддержания требуемого порядка обработки событий. Решение о том, обрабатывать ли локальные события или ждать наступления удалённого события должно приниматься только на основе доступной информации о локальном состоянии данного ЛП.

В связи с отсутствием информации о глобальном состоянии, каждый ЛП должен принимать соответствующие меры, чтобы быть уверенным в том, что все события моделируются в правильном порядке. Для достижения этого существуют два основных принципа (См.54), описанные далее.

При консервативном подходе, локальные события обрабатываются только в том случае, когда ЛП точно уверен в том, что для него не поступят прошедшие удалённые события с других ЛП (т.е. удалённые события, имеющие время наступления меньше чем локальное модельное время). Это может быть достигнуто с помощью установления логических каналов между логическими процессами, которые могут планировать удалённые события друг для друга. Каждый раз, когда логический процесс планирует удалённое событие для другого логического процесса, часы канала устанавливаются на наименьшее значение локального модельного времени для обоих логических процессов. Так как логические процессы обрабатывают события только в порядке увеличения времени их наступления, и запланированные удалённые сообщения всегда имеют время наступления большее времени установленного в логическом канале, то значение часов логического канала не может уменьшаться. В случае, если логические каналы не получают сообщения в порядке FIFO, должны быть предусмотрены дополнительные действия для предотвращения уменьшения значения часов логического канала, так как это может нарушить консервативный подход. Перед обработкой очередного события логический процесс сверяет время наступления этого события с показаниями часов связанных с ним логических каналов. Если время наступления события является наименьшим, то данному логическому процессу не может быть запланировано более раннее удалённое событие, и ЛП обрабатывает очередное событие. В противном случае, логическому процессу может быть запланировано более раннее удалённое событие, и логический процесс должен быть заблокирован до тех пор, пока значения часов всех его каналов не станут больше времени наступления очередного события.

Блокировки, свойственные консервативному подходу, почти всегда к появлению тупиков во время моделирования схем, содержащих обратные связи. Для решения этой проблемы, логические процессы должны собирать дополнительную информацию для выявления и разрешения тупиков, или должны использовать методы позволяющие избежать тупики (например используя так называемые пустые сообщения) Проблема тупиков иногда приводит к серьёзным дополнительным затратам при параллельном распределённом моделировании.

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

Наиболее известным примером оптимистического метода является метод Деформации Времени (Time Warp). Этот метод был разработан для случая, когда несколько ЛП взаимодействуют между собой при помощи сообщений. Во время отката изменения, сделанные в удалённых логических процессах, отменяются с помощью посылки им антисообщений для неверных удалённых событий, Локальные процессы сохраняют список своих входных сообщений до тех пор, пока не обработаются события, связанные с этими сообщениями. Если антисообщение находит соответствующее ему необработанное сообщение, то оба сообщения удаляются. Если сообщение, соответствующее полученному антисообщению, уже обработано, то необходимо также выполнить откат ЛП, получившего это антисообщение. Это может привести к последовательности откатов. Существует несколько методов оптимизации для избегания слишком длинных цепочек откатов, которые могут сделать оптимистический подход неэффективным. Необходимо отметить, что время, затраченное на обработку предполагаемых событий при оптимистическом подходе, может быть бесполезно потрачено при консервативном подходе из-за блокировки, вызванной ожиданием новых событий или тупиками и их разрешением.

3.2 Имитационное моделирование информационных атак на ЛВС