Simulation Basics

Overview

Modeling and Simulation, or sometimes being referred to as M&S, was

becoming one of the academic programs of choice not only for
students but also for many professionals in all disciplines. Modeling
and simulation is a discipline with its own body of knowledge, theory,
and research methodology.

On the primary side of the said discipline is the fundamental notion

that models are approximations for the real world. To engage in
Modeling and Simulation, students or professionals must first create a
model approximating an event. The model is then followed by
simulation, which allows for the repeated observation of the model.
After one or many simulations of the model, a third step takes place
and that is analysis. Analysis aids in the ability to draw conclusions,
verify and validate the research, and make recommendations based on
various iterations or simulations of the model.

These basic concepts coupled with visualization, the ability to

represent data as a way to interface with the model, make Modeling
and Simulation a problem-based discipline that allows for repeated
testing of a hypothesis. Teaching these concepts and providing
research and development opportunities are core to Modeling and
Simulation education. Modeling and Simulation also serves as a tool or
application that expands the ability to analyze and communicate new
research or findings.

Handling Stepped and Event-based Time in Simulation

In a continuous system, the state variables change continuously with
respect to time, whereas in discrete systems, the state variables change
instantaneously at separate points in time. Unfortunately for the
computational experimentation there are but a few systems that are
either completely discrete or completely continuous state, although
often, one type dominates the other in such hybrid systems. The idea
here is to find a computational model that mimics the behavior of the
system closely, specifically the simulation time-advance approach is
critical.

Taking a closer look into the dynamic nature of simulation models,

keeping track of the simulation time as the simulation proceeds, we
can distinguish between two time-advance approaches: time-driven
and event-driven.

Modeling And Simulation 1

I Modeling And Simulation

Time-Driven Simulation

This is the most widely known approach in simulation of natural

systems.

For continuous systems, time-driven simulations advance time with a

fixed increment. With this approach, the simulation clock is advanced
in increments of exactly Δt time units. Then after each update of the
clock, the state variables are updated for the time interval [t, t+Δt].
Less widely used is the time-driven paradigm applied to discrete
systems. In this case, we have to specifically consider whether:

• The time step Δt is small enough to capture every event in the

discrete system. This might imply that we need to make Δt arbitrarily
small, which is certainly not acceptable with respect to the
computational times involved.
• The precision required can be obtained more efficiently through the
event-driven execution mechanism. This primarily means that we have
to trade efficiency for precision.

Event-Driven Simulation

In event-driven simulation, the next-event time advance approach is

used. For the case of discrete systems, this method consists of the
following phases:
Step 1: The simulation is initialized to zero and the times of
occurrence of future events are determined.
Step 2: The simulation is advanced to the time of the occurrence of the
most imminent (i.e. first) of the future events.
Step 3: The state of the system is updated to account for the fact
that an event has occurred.
Step 4: Knowledge of the times of occurrence of future events is
updated and the first step is repeated.
The advantage of this approach is that periods of inactivity can be
skipped over by jumping the clock from event time to the next event
time. This is perfectly safe since by definition, all state changes only
occur at event times. Therefore, causality is guaranteed.

2
Simulation Basics

The event-driven approach to discrete systems is usually exploited in

queuing and optimization problems. However, as we will see next, it is
often also a very interesting paradigm for the simulation of continuous
systems.
Consider a continuous system where every now and then, (possibly at
irregular or probabilistic time steps) discontinuities occur, for instance,
in the temperature of a room where the heating is regulated in some
feed-back loop:

Figure 1: Typical discontinuities in Time versus State trajectories of continuous

systems or its (higher order) derivative with respect to time.

The difficulty of an efficient time-driven simulation of such a system

is in the integration method applied. Specifically, multi-
step integration methods to solve the underlying differential equations
might prove not to work in this case. The reason is that these methods
use extrapolation to estimate the next time step. This would mean that
they will try to adapt to the sudden change in state of the system thus
reducing the time step to infinite small sizes.

Discrete versus Continuous Modeling

Continuous

In an analog computer, a computer that represents data by measurable

quantities, as voltages or, formerly, the rotation of gears, in order to
solve a problem, rather than by expressing the data as numbers.

Discrete

Digital computers, which is a computer that operates with numbers

expressed directly as digits.

Modeling And Simulation 3

I Modeling And Simulation

Uniformly spaced time steps.

Fixed time step intervals (may be scaled)

Adjustable time steps

• Bigger steps while functions are well-behaved

• Smaller steps while function values are rapidly

changing
Arbitrarily spaced times (next-event times)

• May delay taking a step until a real-time (or scaled)

clock catches up.

• May perform the next event step as soon as possible

(ASAP)

Hybrid

Combined Analog and Digital.

Includes digital interfaces to the real world
Sample the analog values at discrete times (A/D conversion)
Increment the digital value, updating the analog values, at discrete
times (D/A conversion)

Deterministic Model
Repeatable results:

Linear and bilinear forms:

Linear: x' = xA + b
Bilinear: x' = xBxT + xA + b

Where:

A and B are matrices

x`, x and b are vectors.
xT is the transpose of x

4
Simulation Basics

More complex (nonlinear) mathematical forms such as:

m' = m * v / (1 - (c2 / v2))
Finite State Machines (FSM)

• A set of states

• Transition table of entries of the form

<state, input, next state, output>
Hybrid Dynamical System (HDS)

• A controlling FSM

• A collection of dynamical models, and which one to use is

selected by the state of the FSM.
Component-based models (Agent-based Models)
Many components, each with a behavior model.

• Homogeneous Agent Models (Same model, separate

state variables)
• Heterogeneous Agent Models (Distinct models and
state variables)
May be represented in many detail forms

• Mesh models (space-filling)

• Network models (graph-like interconnects and

dependencies)

• Finite Elements (predefined component types -- may be

meshes or network elements)

• Agent-based -- may range from simple, as in finite

elements, to complex agents with contained
"intelligence" models.

Stochastic Forms

Characterizing randomness in behaviors of otherwise deterministic

models

Modeling And Simulation 5

I Modeling And Simulation

Using random variates (random variable values from some given

probability distribution) variables
Randomness in a run of the model (common for games)

• Select a random distribution for one or more given

variables

• Each time a new value is needed for one of the selected

variables generate a new random variate from the
appropriate distribution.
Use multiple runs to generate aggregated behavior characterizations
(called Monte Carlo simulations)

• Perform a "significant" number of individual random

runs (> 70)

• The random values selected in the runs must be

"independent" from run to run.

• Generate histograms and other useful statistical

representations of the outputs to show how the behavior
ranges due to the randomness of the internal values in
the model.
Deterministically represent and propagate variability for the model
variables
Conventional stochastic models (Kalman filter variants,
etc.)

• Rely on central limit theorem to justify propagating

normal distributions

• Requires linear and bilinear form models.

Markov Models -- state models with transition probabilities
Bounded error models

• All sources of randomness must have bounded

errors

• Must be able to propagate error intervals

through all calculations in the model time steps.

6
Simulation Basics

Sources and Propagation of Errors

Errors in Models

• Sources of Errors
• The point or place from which the condition of
deviating from accuracy or correctness came.
• Characterizing Errors
• The process of describing errors
• Using Error Bounds
• The term “error bound,” refers to an upper bound on the
size of the error. It is important to realize that although
the absolute value of the error may be considerably
smaller than the error bound, it can never be larger. In
general, the smaller the error bound the better the
approximation.
• Interpreting Error Implications
• The interpretation of error implied or resulting
outcomes.

Sources of Errors

• Input Values (measurements)

• Machine Inaccuracies
• Algorithm Inaccuracies
• Bad models

Measurement Errors

• Measurement granularity
• Granularity accuracy ==> Error intervals
• Types of measurements

Modeling And Simulation 7

I Modeling And Simulation

Machine Errors: Representation

• Float: 7 decimal places, E+/-38, or subnormal E-45 (fewer
digits of precision)
• Double – 16 decimal places, E +/-308, or subnormal E-324
(fewer digits of precision)
• Equality comparisons (does 0.0F == 0.0D?)
• Overflow (too big an exponent)
• Underflow (too small an exponent)
• Mismatch (1.000E19D + 47.3D = ?)
Machine Errors
• Divide by zero (+/- Inf), or divide zero by zero (NaN)
• Propagate “bad” values
• Worst-case scenarios, not seen as errors:
– Near zero results of add or subtract
– Near zero denominator
Algorithm Sources of Errors
• Inaccurate representation of real world
• Inaccurate representation of ideal world
• Computational errors

Real World to Ideal World Model

• Math Models are idealistic
• Real world has many perturbations
• Statistical estimates are only “best fit” to observe
measurements

• Results in an inaccurate ideal model

8
Simulation Basics

Ideal Model to Implementation

• Machine errors in number representations
• Machine errors in arithmetic calculations
• Results in even worse implementation model values
Computational Errors
• Numerical calculation to approximate math functions
• Numerical Integration
• Numerical differentiation
• Techniques used determine the error behaviours
Controllable Errors
• Understanding sources and behaviour of errors empowers you
to control them and predict their effects on the results.
• Identifying sources and effects of errors allows you to better
judge the quality of models.

What Gives Bad Models?

• Wrong equations
• Wrong numerical methods
• Details gone awry
• All irrationally affect results.
Characterizing Errors
• Error Forms (Probability Distributions)
• Error propagation effects on error forms
• Limitations versus needs
Error Characterizations
• Error probability distributions
• The normal distribution
• Zoo of common other distributions

Modeling And Simulation 9

I Modeling And Simulation

• Arbitrary distributions
• Error bounds
• Generalized error estimation functions
• Enumerated values and “false negatives”
Error Probability Distributions
• Measurement error characteristics
• Calculation error characteristics
• Introduced algorithmic error terms
Measurement Error Characteristics
• Discrete sample on a number line
• Spacing determines “range” for each measurement point
• Actual value may be anywhere in that range
Calculation Error Characteristics
• Round-off
• Divide by near-zero
• Divide by zero
• Algorithm inaccuracies
Algorithmic Error Characteristic
• Depends on the algorithms/solvers used
• Depends on the problem size
• Depends on inter-sub model data sharing patterns and volume
Errors: Normal Distributions
• Easy to characterize
• Propagates nicely through linear stages
• Useless for nonlinearities, special conditions
• Not always a good fit

10
Simulation Basics

Errors: Generalized Distributions

• Not commonly used
• Easy to represent (histograms into PDFs)
• Propagate through nonlinear calculations
• Awkward: histograms, PDFs, CDFs for each variable
Errors: Bounded
• Not commonly used
• Easy to represent (+/-error magnitude)
• Can be propagated through nonlinear calculations
• Still awkward for some calculations
Errors: Propagating a Distribution
• Highly dependent on the distribution and the calculations being
performed.
• Generally only linear operations give easily predictable
algebraic results.

• Others require piecewise approximations

Errors: Bounds
• Expected value, +/-error magnitude, or min/max
• Propagates through calculations
• More complex forms may be needed after propagation –
bounded piecewise linear distributions
Errors: Unhandled Implication
• Misinterpretation of results
• Misplaced confidences

Modeling And Simulation 11

I Modeling And Simulation

References
Include list of books, journals and other online references that you used in
writing the module. Titles of sources should be written out in full.

a. Textbook
Principles of Modeling and Simulation: A Multidisciplinary
Approach, John A. Sokolowski, Catherine M. Banks. Latest
edition.
b. References
1. A Guide to Simulation, (reprint of 1983 edition),
Springer. P. Bratley, B.L. Fox and L.E. Schrage, 2012
C. Other Supplemental Materials
1. [Link]
2. [Link]
7-RandomVariateGenerationSlides_131022.pdf
3. [Link]
[Link]
[Link]/Research/Publications/_Documents/todo/converte
d/[Link]

12
Lecture 1 - Introduction
Scilab is a scientific software package for numerical computations providing a
powerful
open computing environment for engineering and scientific applications. Developed
since 1990 by researchers from INRIA (French National Institute for Research in
Computer Science and Control, [Link] and ENPC (National
School of Bridges and Roads, [Link] it is now
maintained and developed by Scilab Consortium
[Link] since its creation in May 2003.
Distributed freely and open source through the Internet since 1994, Scilab is
currently being used in educational and industrial environments around the world.
Scilab includes hundreds of mathematical functions with the possibility to add
interactively functions from various languages (C, Fortran...). It has sophisticated data
structures (including lists, polynomials, rational functions, linear systems...), an
interpreter and a high level programming language.
Scilab has been designed to be an open system where the user can define new
data types and operations on these data types by using overloading.
A number of toolboxes are available with the system:
• 2-D and 3-D graphics, animation
• Linear algebra, sparse matrices
• Polynomials and rational functions
• Simulation: ODE solver and DAE solver
• Scicos : a hybrid dynamic systems modeler and simulator
• Classic and robust control, LMI optimization
• Differentiable and non-differentiable optimization
• Signal processing
• Metanet: graphs and networks
• Parallel Scilab using PVM
• Statistics
• Interface with Computer Algebra (Maple, MuPAD)
• Interface with Tcl/Tk
• And a large number of contributions for various domains.
Scilab works on most Unix systems including GNU/Linux and on Windows
9X/NT/2000/XP. It comes with source code, on-line help and English user manuals.
Binary versions are available.
Some of its features are listed below:
• Basic data type is a matrix, and all matrix operations are available as
built-in operations.
• Has a built-in interpreted high-level programming language.
• Graphics such as 2D and 3D graphs can be generated and exported to
various formats so that they can be included into documents.
The image below is a 3D graph generated in Scilab and exported to GIF format
and included in the document for presentation. Scilab can export to Postscript and GIF
formats as well as to Xfig (popular free software for drawing figures) and LaTeX (free
scientific document preparation system) file formats.
 When you start up Scilab, you see a window like the one shown in Fig. 1 below.
The user enters Scilab commands at the prompt (-->). But many of the commands are
also available through the menu at the top. The most important menu for a beginner is
the “Help” menu. Clicking on the “Help” menu opens up the Help Browser, showing a
list of topics on which help is available. Clicking on the relevant topic takes you to
hyperlinked documents similar to web pages. The Help Browser has two tabs – Table
of Contents and Search. Table of Contents contains an alphabetically arranged list of
topics. To see the list of functions available in Scilab, search for Elementary Functions
in the contents page of Help Browser. Other useful functions may be available under
different headings, such as, Linear Algebra, Signal Processing, Genetic Algorithms,
Interpolation, Metanet, Optimization and Simulation, Statistics, Strings, Time and
Date etc. Use the Search tab to search the help for string patterns.
Help on specific commands can also be accessed directly from the command
line instead of having to navigate through a series of links. Thus, to get help on the
Scilab command “inv”, simply type the following command at the prompt. This is useful
when you already know the name of the function and want to know its input and output
arguments and learn how to use it.
-->help inv
Scilab can be used as a simple calculator to perform numerical calculations. It
also has the ability to define variables and store values in them so that they can be used
later. This is demonstrated in the following examples:
 Usually the answer of a calculation is stored in a variable so that it could be used
later. If you do not explicitly supply the name of the variable to store the answer, Scilab
uses a variable named “ans” to store such results. You could enter more than one
command on the same line by separating the commands by semicolons (;). The
semicolon suppresses echoing of intermediate results. Try the command
-->a=5;
-->_
and you will notice that the prompt reappears immediately without echoing a=5.
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

Introduction

Dynamical simulation, in computing science, is the simulation of

systems of objects that are free to move, usually in three
dimensions according to Newton's laws of dynamics, or
approximations thereof.
Dynamical simulation is used in computer animation to assist
animators to produce realistic motion, in industrial design (for
example to simulate crashes as an early step in crash testing), and
in video games. Body movement is calculated using time
integration methods.

Graph or Network Transition-Based Simulation

Graph = {S, L}
Where:
S is a set of nodes.
L is a set of links -- an association of one node to another as a pair
(aka a tuple) of references. We will assume the order of the node
references indicates the direction of the link, giving directed links
as opposed to undirected links.
One or more directed links implies it is a directed graph.
Undirected links only imply that it is an undirected graph.
Repeated tuples in the set of links implies redundant links. Except
in special cases, these will be assumed to be repeated reference to
the same link in drawings.
If a tuple has the same node as the first and second reference it is a
"self-loop" link. Except in special cases, these will be assumed to
NOT be included.
The degree of a node is the number of links into and out of the
node.
a. The number of links into a node gives its
in-degree

MODELING AND SIMULATION 1

I MODELING AND SIMULATION

b. The number of links out of a node gives

its out-degree

Trail -- any sequence of links and their shared nodes which can be
traced from one node to another visiting each included link only
once. Note that all paths are trails.

• A trail segment is any consecutive sequence of

nodes and links contained in a trail.

• A trail segment that is a path except that it starts

and ends on the same node is a loop. Note that
by the definition, above this trail segment is not
a path.

• When alternate (redundant) links between nodes

are not included a trail may be represented by
the ordered sequence of nodes it passes through.
Walk -- Any sequence of links and their shared nodes which can
be traced from one node to another.

• When alternate (redundant) links between nodes

are not included, a walk may be represented by
the ordered sequence of nodes it passes through.
A Subgraph is a subset of the nodes in a parent graph, and
includes only links from the parent graph that are between nodes in
the subgraph.

• Any connected subgraph which has no

undirected path to other nodes in the graph is a
component of the graph.

• Any graph which consists of two or more

components is unconnected.

• A hypernode is a node that represents a

subgraph and all the links between the nodes in
the subgraph.

• A hyperlink is any link that is between a

hypernode and any node external to the
subgraph it includes.

• A hypergraph is any graph that includes one or

more hypernodes.

2
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

A semantic graph is a graph whose links indicate various

association types between the nodes.
A bipartite graph is a graph whose nodes form two distinct sets
and whose links start in one of those sets and end in the other.
Graph element properties are homogeneous value fields over the
members of the set of nodes or over the members of the set of
links. Property fields may be defined as restricted to the links or
nodes of a subgraph.
Any field associated with each link in a graph forms a field of link
properties, such as names, weights, or associated agent models and
state variables for the links.

Path

Any sequence of links and their shared nodes which can be traced
from one node to another visiting, each included node only once.

• The length of a path is the number of links it contains.

• The distance between two nodes is the length of the shortest

path between the nodes.

• A directed path is a path in which all contained links are

directed from the start node, in succession, to the end node, and
is also known as a route between the two nodes.

• An undirected path ignores the direction of the links it

contains.

• A path segment is any consecutive sequence of nodes and links

contained in a path.

• The diameter of a graph is the largest distance between any

two nodes in the graph.

• A connected graph has an undirected path between any two

nodes in the graph.

• An unconnected graph (or disconnected graph) has at least

one pair of nodes with no undirected path between them. When
a subset of nodes cannot be connected to any another subset of
nodes then the nodes are in separate components of the graph.

MODELING AND SIMULATION 3

I MODELING AND SIMULATION

• When alternate (redundant) links between nodes are not

included a path may be represented by the ordered sequence of
nodes it passes through.

Trail
Any sequence of links and their shared nodes which can be traced
from one node to another visiting each included link only once. Note
that all paths are trails.

• A trail segment is any consecutive sequence of nodes and links

contained in a trail.

• A trail segment that is a path except that it starts and ends on

the same node is a loop. Note that by the definition, above this
trail segment is not a path.

• When alternate (redundant) links between nodes are not

included a trail may be represented by the ordered sequence of
nodes it passes through.

Walk
Any sequence of links and their shared nodes which can be traced
from one node to another.

• When alternate (redundant) links between nodes are not

included a walk may be represented by the ordered sequence of
nodes it passes through.

Finite State Machine

Or finite-state automaton (plural: automata), or simply a state

machine, is a mathematical model of computation used to design both
computer programs and sequential logic circuits. It is conceived as an
abstract machine that can be in one of a finite number of states. The
machine is in only one state at a time; the state it is in at any given
time is called the current state. It can change from one state to another
when initiated by a triggering event or condition; this is called a
transition. A particular FSM is defined by a list of its states, and the
triggering condition for each transition.

4
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

The behavior of state machines can be observed in many devices in

modern society that perform a predetermined sequence of actions
depending on a sequence of events with which they are presented.
Simple examples are vending machines, which dispense products
when the proper combination of coins is deposited, elevators, which
drop riders off at upper floors before going down, traffic lights, which
change sequence when cars are waiting, and combination locks, which
require the input of combination numbers in the proper order.

Network Model
A network model is any real-world network application model.

Common network models include:

• Electric power grid

• Communication networks

• Highways

• Petroleum distribution pipelines

• Water distribution pipes and channels

• Virtual networks of actual traffic

These are commonly called the Critical Infrastructure (CI) networks.

Hybrid Dynamical Systems

Defined as a finite state machine (FSM) and a collection of dynamics
models. The FSM state determines which dynamics model is "in
control" at any given time.

MODELING AND SIMULATION 5

I MODELING AND SIMULATION

Figure 1: A Basic General HDS Device Model

This approach can make an HDS model very attractive for general
modeling use due to its intuitive simplicity for describing multi-state
behaviors. These behaviors can be nonlinear over the state transitions
and may be used for generating piecewise (patchwise) linear models of
device behaviors.

Simple Model Problems

The general HDS model presented above, as with most simple models,
has many hidden complexities that usually must be taken into
consideration for its practical use. To illustrate some of these hidden
complexities and how to handle them the electronic circuit model in
Figure 2 is used.

Figure 2: A Simple Electronic Circuit Model

6
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

For each of the FSM states the dynamics of the circuit, they can be
defined as follows:
Init state
The model constants (base values) and initial conditions are not yet
set up or are being set up. Generally, the setup is at the start of this
state, or this state is treated as a transition state where the model is
set up and then automatically transitions to a "Down" state. The
"Init" state sets the state variables as follows:
Zsource = z the modeled internal impedance.

Vsource = 0 the voltage for "Down".

Vout = 0 there is no output voltage.

Iout = 0 there is no output current.

Zload = ∞ the unknown external load

Figure 3: The Simple Electronic Circuit Model in the

"Init" state.
The "Init" state sets the model up for the transition into the
"Down" state, automatically transitions to that state after the setup.
Down state
The system is turned off. This may be because it hasn't been turned
on yet, because it has failed, or because it has been shut down. It
sets the state variables as follows:
Zsource = z the modeled internal impedance.

MODELING AND SIMULATION 7

I MODELING AND SIMULATION

Vsource = 0 the voltage for "Down".

Vout = 0 there is no output voltage.

Iout = 0 there is no output current.

Zload = Zextern the external load (from model propagation)

Figure 4: The Simple Electronic Circuit Model in the

"Down" state.

As the model runs, each timestep should include calculating

and propagating the load impedance value contributions from
loads external to this component. This is the DPI seen by the
neighboring components along each link.

Up state
The system is up and running normally. It sets the state
variables as needed each time step as follows:
Zsource = zsupp the modeled internal impedance.

Vsource = vsupp the voltage for "On".

Zload = Zextern the external load (from model propagation)

Iout = Vsupply / (Zsupply + Zload)

8
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

Vout = Iout * Zload

Figure 5: The Simple Electronic Circuit Model in the "Up"

state.

The Zload must be determined each time step before the outputs
can be calculated for the supply. Once the Zload is calculated,
the Iout and then the Vout may be generated.
Degraded state
Something has caused the system to act in a manner that
degrades its performance. Often, there can be multiple versions
of this state, which should each be modeled as separate states.
It may set the state variables as follows:
Zsource = zdegraded the modeled internal impedance.

Vsource = vdegraded the voltage for "On".

Zload = Zextern the external load (from model

propagation)

Iout = Vsupply / (Zsupply + Zload)

Vout = Iout * Zload

MODELING AND SIMULATION 9

I MODELING AND SIMULATION

Figure 6: The Simple Electronic Circuit Model in the

"Degraded" state.

The Zload must be determined each time step before the outputs
can be calculated for the supply. Once the Zload is calculated,
the Iout and then the Vout may be generated.
Of course, there can be different types of degradation, and two
that are of interest here are changes in Zsource and changes in
Vsource. These could be two different types of degraded
performance, and therefore, become candidates for two
separate "Degraded" FSM states.
If the model is made up of many "patches" resulting from different
dynamics behavior functions and behavior parameters for each
FSM state, then the modeler should be aware of each of the
following:
1. What are the "state variables" defined for each of the dynamics
and for the overall model, and how are they related, especially
for the separate dynamic models for each of the different FSM
states?
A single consistent set of "state variables" across all of the
dynamics definitions allows the total HDS model to be
considered as defining a single state space of the behaviors of
the overall HDS model via these state variables. This approach
may force state variables from one dynamics model to be
included in the overall collection even though they are not used
by the other dynamics models. A reasonable way to select and
maintain useful values into "unused" state variables is needed.
The difficulty with this preponderance of possibly "unused"
state variables is deciding which ones to set and to what values.
Is there a need to maintain a "reasonable and valid" value in a

10
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

variable that is not being used in each dynamics model? This is

often made more obvious if the specific transitions are
considered, and the variables are selected and values set based
on the dynamic models to which the HDS model can transition
from any given FSM state. Which state variables contribute
directly to the externally observable and output variables must
be considered here as well.
2. Are there discontinuities in the values of the state variables as
FSM transitions cause the state variables to cross the patch
boundaries?
There may be many discontinuities, whether in the base values
("Up" Vsource or Zsource versus their "Degraded" counterparts
versus their "Down" values) or any various derivatives in the
state variables vector. However, only those patch boundaries
which are traversed by defined FSM state transitions must be
considered when trying to guarantee model continuity during
those transitions.
A physical system, even simply modeled, has a "mode of
behavior" for each of the defined FSM states. These modes of
behavior are the focus for selecting the states of the FSM, but
once identified, the transitions between the modes of behavior
must be considered individually.
The transitions for this power supply model include:
o from "Down" to "Up"
o from "Up" to "Down".
o from "Up" to "Degraded".
o from "Degraded" to "Up".
o from "Degraded" to "Down".
o from "Init" to "Down".
The transitions can all be modeled as abrupt and severe
discontinuities, but that would give uncharacteristically ideal
well-behaved but sudden discontinuous changes in both
voltage and current. This is impractical for real physical
systems and is moderated by the complex variable
contributions of system impedances and the actual physical
makeup of generators. An alternative way in which they can
each be modeled is by adding intermediate "transition" states to
the FSM, much like the "Init" state described above. Without
modeling individual device criticalities, it would be very

MODELING AND SIMULATION 11

I MODELING AND SIMULATION

difficult to reasonably predict the behavior variations that can

cause failures internal to the device or unexpected behaviors
that may dominate its influence on other externally connected
components.

State Space Trajectories

Use these for major headings within each module. Avoid using more
than one or two on each page. Discuss the content for this topic.

As discussed above, the HDS model's state space is defined by the

number of state variables that must be included in the overall HDS
model. However, there are wide regions of that space that are not
realistically accessible for traversal. These restrictions are caused
by the following:
1. The FSM states and transitions that control the use of the
dynamics actually restrict the trajectories the behavior can
follow,
2. The actual physical limits of the system being modeled limit
the ranges of some of the state variables' values, and
3. The behavior properties of the dynamics models themselves
which, if nonlinear, may contain singularities and other
computationally impaired state space regions.
These complicate the model development, but they also greatly
reduce the total state space extent that must be considered for the
HDS model's behavior. Generator shafts do not spin infinitely fast,
and voltage sources are usually limited in the maximum voltage
and current they can produce. Oddities in design and failure modes
can, however, allow wider value swings than are commonly
expected, such as voltage and current spikes and undershoots.
There is no immediately obvious way to generate a perfect
representation of the many trajectories the behavior of a device
may take, but some limitations on specific state variables can
usually be guaranteed. This enables defining behavior limit regions
and, therefore, the eligible model behavior regions to include and
exclude in the model state space.
State Space Behavior Regions
There are ways to generate many variations on state space behavior
regions. A good starting place is to define the behavior limits on

12
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

the ideal elements of the component model. If the voltage source is

either on or off then it is either running in its expected range of
output or it is at zero. Investigating the extremes of values possible
for the load impedance, which is expected to vary over time, the
limits on the other state variables can be estimated. These
estimates allow the behavior state space region boundaries to be
identified and characterized.
A. Basic and Transient Behavior Regions
Some preliminary estimates show that if the load approaches z = 0,
then the maximum current is given by:
Iout(max) = Vsupply / Zsupply
and the minimum voltage from Vsupply is given as:
Vout(min) = 0
If z = ∞, then the minimum current is:
Iout(min) = 0
and the maximum voltage is:
Vout(max) = Vsupply
When these limits are entered into the equations for the dynamics
model for "Up," the steady-state behavior is well-defined and has
immediately calculable implications on the other state variable
values, thus defining a behavior region for the dynamics model.
Other manageable implications come from reactive power aspects
of the complex impedances.
Due to the capacitive and inductive components of the impedance
the above picture becomes somewhat naive, as the sudden changes
in voltage or current can induce strong "back-EMF" inducing high
voltages or currents as transient behavior caused by the power
supply transitioning from one state to another. In power systems,
an attempt is made to perform the real-world state transitions only
at zero crossings of the AC power, voltage, or current, but the
timing of failures and spurious incidents is generally not so
accomodating. The resulting voltage or current surges can be
considered critical in identifying which events may become
triggers of failures, especially when they exceed the capacity of a
transmission line or the power limits of components attached to the
power supply.
Each tolerance limit, whether it is the voltage at which a capacitor
fails or the current at which a resistor or wire overheats, becomes a
critical limit that should be considered in the behavior region
boundaries for the component's state space. Without these details,

MODELING AND SIMULATION 13

I MODELING AND SIMULATION

the model cannot anticipate an overheated wire or resistor, thus the

effects it has on power delivery.
The critical limits may be considered in several categories:
1. "Impossible" behavior limits -- These are limits that cannot
physically be exceeded by the elements of the components, or
the limits on derived state variables that depend on other such
limited variables.
2. "Prescribed" limits -- These are the design limits of
components or component elements which the manufacturer
recommends, not exceeding. A designer of elements will
generally observe these and even leave a safety margin, but
that does not guarantee the component assembly will fail if that
threshold is exceeded, only that the probability of failure will
increase dramatically when it has exceeded. For some items
such as fuses and dircuit breakers, these limits are very close to
the failure limits, but for most other types of component
elements, the safety margin is more significant. Exceeding
prescribed limits may involve degraded performance of
components, which often should become new HDS model
behavior states.
3. Probabilistic thresholds -- When a mean value and a
probability distribution are specified for a variable, such as a
resistor which has 20% accuracy, or a voltage reading that has
+/- 5% accuracy, then the limits on either side of the mean
(expected) value can be chosen. These limits are usually
selected to have some predefined probability of containing the
actual value given the observations and the estimated mean.
The actual probability range limits used may be chosen for any
of a number of reasons, and is often dependent on the model
and the situation where the model is to be used. This interval
defines a range which, if one of the above limits ("Impossible"
or "Prescribed") lies within the range, there is some reasonable
probability that the value, for which the mean is only an
estimate, has actually crossed the threshold. This "distance to
mean" for the particular value's probability distribution and
selected value range probability interval provides a boundary
"safety margin", or a region of heightened probability of
crossing a limit boundary, and therefore, of the type of failure
indicated by that boundary. These can be used to gauge the
severity of possibility of failure.
Working from these three definitions, five categories of behavior
"risk of failure" can be defined:

14
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

1. The "Impossible" limit was exceeded -- No component should

be able to get to this point and still be working unless the limit
was unrealistic. The limit needs to be readjusted for the
elements of the component modeled.
2. The current value is within the probabilistic boundary region of
"Impossible" behavior. Any component that gets this close is
very likely going to fail very soon, unless the "Impossible"
behavior limit was unrealistic.
3. The "Prescribed" failure threshold exceeded -- As the state
value progresses from the "Prescribed" threshold value toward
the "Impossible" limit, the likelihood of failure dramatically
increases. The system component has been pushed beyond its
designed limits.
4. The current value is within the probabilistic boundary region of
the "Prescribed" failure threshold. This should be a warning to
illustrate that the system is pushing its design limits.
5. The current value is not within the probabilistic boundary
region of any failure threshold. This should illustrate that the
system is operating in its "normal" design range.
One step to being able to better predict an estimated mean is to use
existing stochastic model techniques, such as Kalman filter
variations, to maintain estimates of the variations of the values,
while periodically updating them to reflect real-world observations
when they are available.
B. Normal Variations and Model Covariances
To be able to estimate the extents of the probabilistic boundary
region about the current mean for a value, the model must be
aware of the probability distribution function for the variable.
When using a model to which Kalman filter variants are applied, it
is assumed that the variable estimate is from a variable with
Gaussian noise added to it. This makes the distribution symmetric
and the range of "Probable" values easy to calculate. Another
approach to use when the distribution is obviously not Gaussian is
to propagate a piecewise linear PDF and calculate the extents on
either side of the mean that give the desired probability of
inclusion. This result may not be symmetric about the mean.
Using the Gaussian additive noise assumption, and assuming the
state values vector time step propagation function is differentiable
a Kalman filter variant (the "extended" or the "unscented" version)
can be applied to the state variable propagation steps so a
covariance matrix is maintained. Using the covariance matrix, the

MODELING AND SIMULATION 15

I MODELING AND SIMULATION

interdependence of state variables and the variance of the

individual variables can be used for estimating the PDF, thus, the
probabilistic boundary interval around the estimated state variable
at each step. The result is that any state vector transition between
the "critical regions" can be detected and modeled.
There is another advantage in using the Gaussian assumption and
the Kalman filter approach. The methods for updating some or all
of the state variable values and the covariance matrix from actual
observations, also assuming some Gaussian distribution of additive
noise, are well defined. The result is that the HDS component
model's state variables vector can be propagated through predicted
model behavior steps with error estimates, then updated to be
brought closer to reality when real-world value observations
become available.
By using the HDS model and the model forms outlined above, the
component models can be easily combined into large models of
many components networked together and still retain the needed
details of the contributions of the components.
Network Flow Models Using Multiple HDS Components
For continuous network flow models of large, sparsely
interconnected systems, modeled as a single dynamical model or as
a single HDS model, they must be represented by very large
vectors and matrices. When matrices get extremely large, the
operations on them, such as calculating a matrix inverse, get very
time consuming and begin to accumulate dramatic computation
errors. The calculations can be parallelized to speed them up, but
to parallelize the problems to take advantage of parallel processing
speedups requires customized algorithms for each computation.
To get away from the programming complexities and from
grappling with the problem sizes, it is recommended that the
network be represented by a graph of the network topology, and
that each network node and link have an HDS model associated
with it. Each node and link represents a component in the network
and can be modeled more reasonably as a single, relatively simple
HDS model of that component device. This approach introduces
some overall model computation complexities, but allows
extremely large network flow models to be easily combined from a
relatively small number of component HDS models. The approach
also allows the models to be easily spread among parallel
processors by subdividing the overall network on the identified
links, while minimizing the interprocessor communications
needed.

16
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

Each HDS model need only communicate with those other

network components with which it shares a link. This provides a
simple segmentation of the problem using the links and nodes, and
allows easy partitioning of the problem to superimpose it onto any
parallel architecture.
As stated, this reorganization does not come without some
complexities. Network flow models often include large systems of
partial differential equations, and the "feedback" aspects influence
the model's behavior. For electrical systems, these often include
large numbers of "loop-node" equations. Dr. Ruben Kelly of
UNM, using ideas from mechanical engineering that date back into
the 1920's, devised a method called Driving Point Impedance
(DPI) Techniques for Circuit Analysis. The technique is already
used for fluid flows, and by extending his DC and low frequency
techniques to AC, fixed frequency with phasing, and complex
representations voltage, current, and impedances this system
approach can be applied to modern electric power systems.
Using DPI, a network, from the view of each component, consists
of modeling the internals of each component and the driving point
impedances from the point of view of each of its connections to the
rest of the network. To employ this technique in electric power
network flows, the overall model must be updated each time step
in two phases:
1. Phase I: Propagate the impedances as needed.
2. Phase II: Propagate the voltage and current contributions from
each power source as needed.
Feedback loops must be handled as a separate phase if they are
included in the network.
One consolation is that if impedances, voltages, and currents do
not change they do not need repropagated. This makes it useful to
maintain the DPI value for each portal for each component, as well
as a list of voltages and currents from the various contributing
sources.
Considering a large network of HDS models, some questions need
to be discussed:
1. When an HDS model is used to model a single device in a
large network of devices, how many of the state variables need
to be propagated to other components of the network?
Only a few of the state variables, or even variables derived
from them need to be passed to the neighboring network

MODELING AND SIMULATION 17

I MODELING AND SIMULATION

components. The components themselves will determine which

of those needed integration with their own state variables and
passing on. A transmission line model may generate a driving
point impedance (DPI) value for each of its ends, based on
what is on its other end and its own contributions of
impedance. A load must present its DPI to each attached
transmission line. A transformer must calculate the
contribution from the DPI on its other side as well as include
its own contributions to the impedance.
2. How does each component determine what the DPI of the loads
it is connected to (driving)?
The impedances must be passed out every link from a node,
and may be unique for each link. Only after the impedances
have been propagated across the network can the voltage and
current contributions be calculated for each source at each
component. In Phase I, sources have only their internal
impedance to propagate, loads likewise, and only transformers,
transmission lines and other "inputs to outputs" devices must
be able to pass impedances from one side to their other side.
3. How does the model get the voltages and currents at the
various locations in the network?
The DPI allows easy calculation of the voltage at each node
due to a voltage source, and the voltages allow the calculations
of the currents through each link and load. The current
contributions from the multiple voltage sources are added
together to get the total currents through the specific
components.
4. How do we avoid needing the loop-node differential equations
in these calculations?
The loop-node equations are to compensate for the dynamics of
the voltage and current variations of the frequencies involved.
For steady-state AC at a fixed frequency, these can all be
converted to a higher level of abstraction and viewed as RMS
voltages and currents with real and complex aspects influenced
by the resistive, capacitive, and inductive loads throughout the
network. The model can focus on real and reactive power
delivery on longer time steps rather than the numerical
methods for solving differential equations which must be run
using short time steps.
If higher resolution is desired for parts of the network, the
lower level of abstraction, numerical solutions to the

18
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

differential equations, are available, but they are not essential

for all of the models all of the time.
5. What other advantages are there of having all these small
models rather than a single large aggregate model?
By dividing the network into individually modeled components
and combining their interactions via the representative network
it becomes easy to:
1. Partition the model to run on many processors,
2. Replace a large subnetwork with a representative, yet
smaller, aggregate model; and
3. Generate aggregate models of subnetworks that include
the criticalities contributed by each of the included
component device models.
The result is that when the small models are aggregated, the
criticalities they include can be incorporated into a simpler
aggregate model more easily. To generate large aggregate
models that are purely linear differential equations, many
aspects of the criticalities are discarded before the model is
built. This prevents the user of the model from even being
made aware when a criticality begins to influence the behavior
of the model.
Of course, for criticalities to influence the model behavior, the
model must be able to detect and respond appropriately to the state
vector incursions into the critical regions of the model state space.
Internally Triggered FSM Transitions
Earlier discussions mentioned that some FSM states' dynamics
models should be able to run to completion and then trigger an
FSM state transition to another state. These states are generally the
initialization ("Init") and transition states that should be created to
make the HDS dynamics patches "fit together" to form a
continuous manifold for the state space trajectories.
In addition to the above dynamics model-triggered FSM transition,
there are certain internal state variable vector trajectory excursions
that should trigger FSM transitions.
At times, the internal behavior trajectory of an HDS will cross a
boundary into a critical region, whether from normal model
responses to changing inputs, or from updates generated from
sensor inputs from the real world. These boundary crossings
should cause an FSM state transition. If too much current is drawn

MODELING AND SIMULATION 19

I MODELING AND SIMULATION

from the generator and it overheats, it can create an open circuit

when a wire melts or rise in terms of the internal resistance,
causing the generator to operate in a degraded mode. The
internally modeled behaviors, as these cases, can cause the actual
FSM state transition.
For an internal state variable trajectory to initiate an FSM state
transition, the condition must be detected while the state transition
must be initiated. This requires state variable location pattern
detection and state transition initiator to be included in the design
of the HDS model as in Figure 7.

Figure 7: An HDS Model Variant with Pattern Recognition

As indicated in Figure 7, the State Control and Pattern Recognizer
is relegated the duty of merging external state control requests with
state transitions dictated by internal state variable values'
trajectories and critical region boundary traversals.
Even with the pattern recognition, the model is not complete until
the modeler realizes that the inputs must go into the proper
dynamics model, and the outputs must be generated by the
currently active dynamics model. The complete network
component HDS model overview is presented in Figure 8 below.

20
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

Figure 8: The Network Component HDS Model

Actor/ Agent Based Simulation

An agent-based model (ABM) is one of a class of computational
models for simulating the actions and interactions of autonomous
agents (both individual or collective entities such as organizations or
groups) with a view to assessing their effects on the system as a whole.
It combines elements of game theory, complex systems, emergence,
computational sociology, multi-agent systems, and evolutionary
programming. Monte Carlo Methods are used to introduce
randomness. Particularly within ecology, ABMs are also called
individual-based models (IBMs), and individuals within IBMs may
be simpler than fully autonomous agents within ABMs. A review of
recent literature on individual-based models, agent-based models, and
multiagent systems shows that ABMs are used on non-computing
related scientific domains including biology, ecology and social
science. Agent-based modeling is related to, but distinct from, the
concept of multi-agent systems or multi-agent simulation in that the
goal of ABM is to search for explanatory insight into the collective
behavior of agents obeying simple rules, typically in natural systems,
rather than in designing agents or solving specific practical or
engineering problems.

MODELING AND SIMULATION 21

I MODELING AND SIMULATION

Agent-based models are a kind of microscale model that simulate the

simultaneous operations and interactions of multiple agents in an
attempt to re-create and predict the appearance of complex
phenomena. The process is one of emergence from the lower (micro)
level of systems to a higher (macro) level. As such, a key notion is that
simple behavioral rules generate complex behavior. This principle,
known as K.I.S.S. ("Keep it simple, stupid") is extensively adopted in
the modeling community. Another central tenet is that the whole is
greater than the sum of the parts. Individual agents are typically
characterized as boundedly rational, presumed to be acting in what
they perceive as their own interests, such as reproduction, economic
benefit, or social status, using heuristics or simple decision-making
rules. ABM agents may experience "learning", adaptation, and
reproduction.
Most agent-based models are composed of: (1) numerous agents
specified at various scales (typically referred to as agent-granularity);
(2) decision-making heuristics; (3) learning rules or adaptive
processes; (4) an interaction topology; and (5) a non-agent
environment. ABMs are typically implemented as computer
simulations, either as custom software, or via ABM toolkits, and this
software can be then used to test how changes in individual behaviors
will affect the system's emerging overall behavior.

Mesh Models
Background
➢ How do we represent a continuum? A continuous sequence in
which adjacent elements are not perceptibly different from
each other, although the extremes are quite distinct
➢ How do we represent a deformable object? Or a replaceable
object?
➢ How do we represent disjoint or disconnected parts?

Representing a Continuum
− Field equations (analytical)
− Mesh points (discrete locations)
− Mesh “cells” (discrete objects)
− Combinations

22
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

Continuum Field Equations

− Gravitation
− Electric charges
− Magnetic fields
− Evenly propagated point source radiated energy

Continuum Mesh Points

− Attributed values at each point
− Fixed grid points
− Mobile grid points
− Arbitrary (strategically placed) points
− Multi-mesh points

Continuum Mesh Combinations

− Objects, particles, and fields
⚫ Radiation transport and collisions
⚫ Protein models
⚫ Satellite orbits
− Integrated systems
− Boundary transports

Continuum Mesh Cells

− Point locations and attributes
− Attribute values over line, surface, or volume regions (1-D, 2-
D, or 3-D)
− May form a hierarchy of cell types
⚫ Node (Point)
⚫ Edge (Line between points)
⚫ Face (Surface bounded by lines)
⚫ Zone (Volume bounded by surfaces)

MODELING AND SIMULATION 23

I MODELING AND SIMULATION

Mesh Cell Behaviour Types

− Fixed positions (Eulerian Mesh)
− Adaptive positions (Lagrangian Mesh)
⚫ Crushing collision surface
⚫ Wavefront deformation
− Adaptive refinement for finer localized representation
− Assemblies of parts
⚫ Separate “independent objects”
⚫ Boundaries

Implementing a Mesh Model

➢ Choose a model object representation
➢ Represent the state variables (properties of the represented
objects)
➢ Organize the model calculations (state variable calculations for
each time step)
➢ Decide how to view the time step values

State Variables
➢ State variables are EVERY variable that changes over time and
must be carried from time step to time step.
➢ State variables are mostly “attributes” (properties) of the
elements.
➢ State variables generally are in vectors whose value entries
correspond to the cells in a single cell set.

State Variable Representations

➢ Each has its own data type, depending on what it represents.
➢ Commonly float or double, may also be integer, enumerated
value, vector, string, or ...
➢ Generally loosely interpreted as meaning ANY attribute of an
element or of the model itself.

State Variable Calculations

➢ Inputs to calculations:

24
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

State variable values (one or many)

Constants and coefficients
Element associations
➢ Outputs

New state variable values

State Variable Calculations
➢ Temporary variables may or may not be considered state
variables.
➢ Calculations may be iterated many times over for each of many
inputs (A differential equation solver or integrator) or be
simple expression evaluation as in (a = b).
➢ A state variable could be the state of a lesser (limited scope)
Finite State Machine.
➢ Generally best to organize the calculations to iterate through
the output values, calculating each before going on.
➢ Each mesh cell has its own state variables, and it often is best
to compute all for one cell at a time, but some algorithms
require one attribute for all cells before the next attribute can
be calculated.
➢ Selecting the order to do calculations among attributes can be a
precedence-based scheduling problem.
➢ Work to keep it as simple as possible!!
➢ Use comments to inform source code readers why you have
used a specific ordering or technique!

Choose a Model Object Representation

➢ Finite Elements? (Pick from a zoo of predefined cell element
types)
➢ Regular Polyhedral Mesh? (Homogeneous mesh cells)
➢ General Polyhedral Mesh? (Hierarchy of generalized cells)
➢ Any combination of the above?

Model Cell Criteria

➢ Cell shapes?

MODELING AND SIMULATION 25

I MODELING AND SIMULATION

➢ Cell properties (attributes)?

➢ Cell associations with neighbor cells?
➢ Cell associations with other cell set members?
➢ Complexities of developing supporting code?

Finite Element Cell Types

➢ 1-D: Line, interpolated line, spline
➢ 2-D: Triangle, rectangle, trapezoid, circle, ellipse, interpolated
shape variations
➢ 3-D: Tetrahedral, hexahedral, spherical, ellipsoidal
➢ Special types: Springs, shock absorbers, circuit components,
other custom variations

Regular Polyhedral Cell Types

➢ Limited to “regular” shapes that will cover a “region”.
➢ 1-D: No problem.
➢ 2-D: Triangles, quadrangles, and hexagons only.
➢ 3-D: Hexahedrals only.
➢ Does not cover irregularly shaped model objects/parts.

General Polyhedral Cell Types

➢ A hierarchy of cells (nodes, edges, faces, and zones).
➢ 0-D: node (point) has a location (usually)
➢ 1-D: edge (line) connects two end points (nodes).
➢ 2-D: face is surrounded by edges.
➢ 3-D: zone is surrounded by faces.
➢ Fully generalized polyhedral shapes, allowing extreme shape
representation.

Matrix Representations
of Mesh Models
➢ Vectors of cell set member attributes (property values)
− One value for each cell in the cell set

26
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

− May be scalars, vectors, matrices, tensors, strings,

enumerated values (hot/warm/cold, on/off, ...), or ?
➢ Examples
− Volume temperature, material makeup, mass, density,
pressure, ...
− Point coordinates (1-D, 2-D, or 3-D usually)
− Each entry a vector of flow through a surface
➢ Represent relations which indicate
− cell adjacency within a set of cells
− cell associations between cell sets
➢ May contain values representing
− Cell interaction properties (weights, coefficients)
− Linear state value propagator coefficients
− Stochastic covariance values for property values
between cell pairs

Matrix Mesh Model

Characteristics
➢ Most model matrices are sparse
➢ Matrix math does NOT handle nonlinearities well, so
nonlinearities must be handled as separate expressions for each
transformation.
➢ Matrix representations do NOT clearly indicate organization at
higher levels of abstraction.
➢ It is easy to get lost in the code and data relationships at all
levels.
➢ Parallel partitioning can be awkward.

Viewing Time Step Values

➢ Generally state variable combinations are valid only between

(not during) time steps. That is when to view them (except for
debugging purposes).

MODELING AND SIMULATION 27

I MODELING AND SIMULATION

➢ Sometimes auxiliary state variables are created JUST so they

can be viewed!!
➢ Print the values.
➢ Plot the values.
➢ Use the values to adjust visual “meters” or other indicators.
➢ Use the values to adjust images on virtual displays.
➢ Save the values for a later animation.
➢ Post process the values for a custom view.

Hybrid Simulation
Agent-Based Modeling and Simulation (ABMS) and System
Dynamics (SD) are two popular simulation paradigms. Despite
their common goal, these simulation methods are rarely combined
and there has been a very low amount of joint research in these
fields. However, it seems to be advantageous to combine them to
create more accurate hybrid models.
Hybrid simulation for modelling large systems
Developing models for large systems is not a trivial task. Using
only Discrete Event Simulation (DES) as a modelling technique
may mean that the complexity of the underlying model will
increase exponentially with the size of the model. An alternative to
this is the use of System Dynamics (SD) for modeling large
systems using the positive and negative feedback loops. However,
for modelling a human-centric system like healthcare, DES is
important as it provides individuality analysis; similarly, SD is
important as it facilitates the whole systems approach. The
combined application of OR/Simulation methods enable the
symbiotic realization of the strengths of individual techniques,
while reducing their limitations; in this paper it is suggested that a
combined SD-DES approach (also referred to as hybrid technique)
can be effectively used for modelling large systems. The example
being used in this context is the modelling of an Integrated Care
(IC) system in healthcare.

28
DYNAMICAL, FINITE STATE, and COMPLEX MODEL SIMULATION

References
a. Textbook
Principles of Modeling and Simulation: A Multidisciplinary
Approach, John A. Sokolowski, Catherine M. Banks. Latest
edition.
b. References
1. A Guide to Simulation, (reprint of 1983 edition),
Springer. P. Bratley, B.L. Fox and L.E. Schrage, 2012
C. Other Supplemental Materials
1. [Link]
2. [Link]
7-RandomVariateGenerationSlides_131022.pdf
3. [Link]
[Link]
[Link]/Research/Publications/_Documents/todo/converted/handboo
[Link]

MODELING AND SIMULATION 29

Lecture 2 - The Workspace and Working Directory

While the Scilab environment is the visible face of Scilab, there is another that is not
visible. It is the memory space where all variables and functions are stored, and is called the
Workspace. Many a times it is necessary to inspect the workspace to check whether or not a
variable or a function has been defined. The following commands help the user in inspecting the
memory space: who, whos and who_user(). Use the online help to learn more about these
commands.
The who command lists the names of variables in the Scilab workspace. Note the
variable names preceded by the “%” symbol. These are special variables that are used often and
therefore predefined by Scilab. It includes %pi ( π ), %e ( e ), %i ( √−1 ), %inf ( ∞ ), %nan
(NaN) and others.
The whos command lists the variables along with the amount of memory they take up in
the workspace. The variables to be listed can be selected based on either their type or name.
Some examples are:
-->whos() Lists entire contents of the workspace, including functions,
libraries, constants
-->whos –type constants Lists only variables that can store real or complex constants. Other
types are Boolean, string, function, library, polynomial etc. For a
complete list use the command -->help typeof.
-->whos –name nam Lists all variables whose name begins with letters nam

To understand how Scilab deals with numbers, try out the following commands and use the
whos command as follows:
-->a1=5; Defines a real number variable with name 'a1'
-->a2=sqrt(-4); Defines a complex number variable with name 'a2'
-->a3=[1, 2; 3, 4]; Defines a 2x2 matrix with name 'a3'
-->whos -name a Lists all variables with name starting with the letter 'a'

Name Type Size Bytes

a3 constant 2 by 2 48
a2 constant 1 by 1 32
a1 constant 1 by 1 24

Now try the following commands:

-->a1=sqrt(-9) Converts 'a1' to a complex number
-->whos -name a Note that 'a' is now a complex number
-->a1=a3 Converts 'a1' to a matrix
-->whos -name a Note that 'a1' is now a matrix
-->save('[Link]') Saves all variables in the workspace to a disk file [Link]
-->load('[Link]') Loads all variables from a disk file [Link] to workspace

Note the following points:

● Scilab treats a scalar number as a matrix of size 1x1 (and not as a simple number)
because the basic data type in Scilab is a matrix.
● Scilab automatically converts the type of the variable as the situation demands. There is
no need to specifically define the type for the variable.
Converting To Parallel And Distributed Simulation

Parallel/ Distributed Simulation

Simply stated, this is a technology that enables a simulation

program to be executed on parallel/distributed computer
systems, namely systems composed of multiple interconnected
computers.

As this definition suggests, the two key components to this

technology are:

1. Simulation on parallel or distributed computers technology

2. Execution on parallel or distributed computers technology

MODELING AND SIMULATION 1

I MODELING AND SIMULATION

Computer Simulation
A computer simulation is a computation that models the
behavior of some real or imagined system over time.
Simulations are widely used today to analyze the behavior of
systems such as air traffic control and future generation
telecommunication networks without actually constructing the
systems and situations of interest.
Parallel simulation and distributed simulation refer to
technologies that enable a simulation program to execute on a
computing system containing multiple processors, such as
personal computers, interconnected by a communication
network.
4 principal benefits to executing a simulation program
across multiple computers:
1. Reduced execution time. By subdividing a large simulation
computation into many sub-computations, and executing the
sub-computations concurrently across, say, ten different
processors, one can reduce the execution time up to a
factor of ten.
e.g. This is not unlike subdividing your lawn into ten
equally sized strips, and hiring ten people each with
their own lawn mower to work on a different strip.

2. Geographical distribution. Executing the simulation

program on a set of geographically distributed
computers enables one to create virtual worlds with
multiple participants that are physically located at
different sites.
e.g. Consider a simulated air battle composed of flight
simulators executing on computers at distinct
geographical locations, such as London, New York, and
Japan.

3. Integrating simulators that execute on machines from

different manufacturers.
e.g. Supposed that flight simulators for different types
of aircraft have been developed by different
manufacturers. Rather than porting these programs to a
single computer, it may be more efficient to hook
together the existing simulators, each executing on a
different computer, to create a new virtual environment.
Again, this requires the simulation computation to be
distributed across multiple computers.
4. Fault tolerance. Another potential benefit of utilizing multiple
processors is increased tolerance to failures. If one processor

2
Converting To Parallel And Distributed Simulation

goes down, it may be possible for other processor to proceed

despite the failure.

Classes of Simulation Application

1. Analytic Simulation
Usually attempt to capture detailed quantitative data concerning the
system being simulated. For example, in the air traffic simulation, one
might be interested in the average "circling time" for each aircraft when it
arrives at a busy airport. In a telecommunication network simulation, one
might be interested in statistics such as the average delay to perform a
file transfer or the amount of data per second transmitted through a
typical connection.

2. Virtual Environment
Virtual environment simulations with human participants are sometimes
referred to as human-in-the-loop (or man-in-the-loop) simulations, and
simulations including embedded physical devices are also called
hardware-in-the-loop simulations
Virtual environment simulations differ from traditional analytic simulations
in several important ways. First, they almost always include human
participants or actual physical devices as entities within the simulation
itself, as opposed to external users viewing or artificially manipulating the
simulation as described earlier for analytic simulations. Thus, it is
important that the simulated world advance in time at approximately the
same rate that time advances are perceived by the human participants.

Applications
While some of the applications where parallel and distributed,
simulation technologies have been applied. And that, far from
being complete, this list gives a flavor of some of the current and
potential uses of the technology.
Military Applications – Military establishments has had a
major role in developing distributed simulation technology for

MODELING AND SIMULATION 3

I MODELING AND SIMULATION

virtual environments, and to a lesser, though still significant

extent, parallel simulation technology for analytic simulation
applications.
Some of the most prominent military applications utilizing this technology
are as follows:
1. War gaming simulations – also referred to as aggregated simulations
These simulations are often used to evaluate different strategies for
attacking or defending against an opposing force, or for acquisition
decisions to determine the number and type of weapon systems that
should be purchased to be prepared for future engagement.
2. Training environment – these simulations embed pilots, tank operators,
commanding officers and their staffs, and the like, into an environment to
train personnel for actual combat.
3. Test and Evaluation (T&E) – Training simulations embed humans into
a synthetic battlefield, T&E simulations embed physical components into
a virtual environment, often to evaluate the effectiveness of proposed
new device or to verify that manufactured devices operate at reported
specifications.

Entertainment Application – Distributed simulation technology can be

applied in amusement park and arcade centers where players are co-
located but interact with each other and computer- generated entities
over a local area network. These systems sometimes use costly custom-
designed hardware that can only be justified economically by repeated
use by many users. Another emerging market is the multi-user home
entertainment industry where video game machines or personal
computers are interconnected through the Internet.
Entertainment and training systems employing distributed simulation
technologies have much in common, but they also differ in many
important respects. Obviously, entertainment systems must be engaging.

Social Interactions and Business Collaborations – Another potentially far-

reaching impact of distributed virtual environments is creating new means
for people to interact socially on the Internet. The Internet has already
made fundamental changes in the way people interact both in the office
and at home.
Virtual environments can also provide a new means for interactions in the
business world between colleagues and clients. Entire "virtual
corporations" could be created, composed of employees who are based
physically at different locations or different companies but who are
working together on a joint venture.

Education and Training – Nonmilitary applications for DVEs in education

and training abound. Much work has been accomplished in the medical
community using virtual environments for training as well as treatment of
patients. Computer-generated environments can provide a more cost-
effective (and safe!) means for doctors to practice surgical techniques.

4
Converting To Parallel And Distributed Simulation

Experimental studies have been performed/conducted using virtual

environments to treat patients with various phobias such as a fear of
heights.

Telecommunication Networks – Analytic simulations have long been

used in the telecommunications industry to evaluate networking
hardware, software, protocols, and services. The widespread deployment
of fiber optics technology has had important impacts on the use of
simulation in modeling networks.
First, this technology has brought about increased use of
telecommunication networks for applications other than voice
communications, namely transmission of still images, data, and video.
So-called Broadband Integrated Services Digital Networks (B-ISDN)
provide a single networking infrastructure to carry these diverse types of
traffic. Network designers have had to totally rethink their designs, and
tum toward simulation tools to aid them. Networking technologies such as
Asynchronous Transfer Mode or ATM 2 have emerged to meet the
challenge of supporting these diverse types of traffic on a single network
infrastructure.

Digital Logic Circuits and Computer Systems – Simulations of digital

electronic circuits and computer systems is a second area where parallel
simulation can play a significant role. Fast simulation of logic circuits is of
considerable interest to the electronic computer-aided-design community
because simulation is a major bottleneck in the design cycle. Final
verification of a computer system may require weeks using conventional
sequential simulation techniques. Much of the work in applying parallel
simulation techniques to logic circuits has been focused on the VHDL
hardware description language that has become widely used in industry.
Several prototype parallel simulation systems have been developed that
execute VHDL programs on multiple processor computers, with varying
degrees of success reported in the literature. Successful demonstrations
typically report up to an order of magnitude reduction in execution time.

Transportation – Simulation can play an important role in designing and

managing road and air transportation systems. It can be used as an
analysis tool to evaluate the effectiveness of adding a new runway to an
airport, or rerouting vehicular traffic after the completion of a major
sporting event. As alluded to earlier, it may be used "on-line" in
developing strategies to respond to an unexpected event, for example,
congestion resulting from adverse weather conditions.

Hardware Platforms
Parallel versus Distributed Computers
Multiple-CPU hardware platforms can be broadly classified into two
categories: parallel and distributed computers. Differences between

MODELING AND SIMULATION 5

I MODELING AND SIMULATION

these platforms are summarized in Table 1.2. Parallel and distributed

computing platforms are distinguished by the physical area occupied by
the computer.
The processors in parallel computers are in close physical proximity,
usually within a single cabinet, or a small number of adjacent cabinets in
a machine room. These are usually homogeneous machines, using
processors from a single manufacturer. These machines normally provide
switching hardware tailored to the parallel computer, so the delay in
transmitting a message from one computer to another (referred to as the
communication latency) is relatively low. This latency is typically a few
microseconds to tens of microseconds for a message containing a few
bytes in contemporary machines.
Latency is important because it has a large impact on
performance; if latencies are large, the computers may spend
much of their time waiting for messages to be delivered. Here,
communication latency is perhaps the single most important
technical aspect differentiating parallel and distributed
computers. There are three principal classes of parallel
computers that are in use today: shared-memory
multiprocessors, distributed memory multicomputers, and
SIMD machines (see Fig. 1.1), as will be elaborated upon
momentarily.

Simulations executing on distributed computers are referred to as

distributed simulations. Distributed simulations may be used for analytic
purposes, or more commonly for constructing distributed virtual
environments. The latter is perhaps the more common application for
distributed simulation technology, and the term distributed simulation in
the literature sometimes refers exclusively to distributed virtual
environments.

6
Converting To Parallel And Distributed Simulation

Shared-Memory Multiprocessor
Shared-memory multiprocessors, distributed memory multicomputers,
and SIMD machines provide different programming models to the
application. The distinguishing property of the programming model for
shared-memory multiprocessors is one may define variables that are
accessible by different processors.
One type of shared-memory machine, the symmetric multiprocessor
(SMP), has become increasingly popular. A typical shared-memory
machine is depicted in Figure 1.2. These systems consist of off-the-shelf
microprocessors connected to memory through a high-speed switch,
such as a bus. Frequently accessed instructions and data are stored in a
high-speed cache memory that is attached to each processor. Typically,
the multiprocessor hardware automatically moves data and instructions
between the cache and "main" memories, so the programmer need not
be concerned with its operation, except perhaps to tune the program to
maximize performance.

A second class of shared-memory multiprocessor is the so-called non-

uniform memory access (NUMA) machine. These machines are typically
constructed by providing memory with each processor (as opposed to
separate memory modules as shown in Fig. 1.2) but allow each
processor to directly read or write the memory attached to another
processor (as well as its own memory). Unlike symmetric
multiprocessors, the programmer's interface to these machines
distinguishes between "local" and "remote" memory, and provides faster
access to local memory. This makes these machines more difficult to
program than so-called uniform memory access (UMA) machines where
the average access time to any memory location is the same.

Distributed-Memory Multi-computers
Multi-computers do not support shared variables. Rather, all
communications between processors must occur via message
passing. Message-passing libraries are provided to send and
receive messages between processors.

MODELING AND SIMULATION 7

I MODELING AND SIMULATION

Examples include the Cray T3D, NCube/Ten, and Intel

Paragon. Large multi-computers may contain hundreds of
processors.

A block diagram for a typical distributed memory multicomputer is

shown in Figure 1.3. Each "node" of the network is not unlike that
found in personal computers; it includes a CPU, cache memory,
and a communications controller that handles interprocessor
communication.

The communications controller is responsible for sending and receiving

messages between nodes and typically transfers messages directly
between that node's memory and the inter- connection network. Such
transfers that usually do not require the intervention of the CPU, except
to initiate the transfer or to be notified when the transfer is completed, are
referred to as direct memory access (DMA) operations.

SIMD Machines
SIMD stands for single-instruction-stream, multiple-data-stream. The
central characteristic of these machines is that all processors must
execute the same instruction (but using different data) at any instant in
the program's execution. Typically, these machines execute in "lock-
step," synchronous to a global clock. This means all processors must
complete execution of the current instruction (some may choose not to
execute that instruction) before any is allowed to proceed to the next
instruction. Actually, lock-step execution need not be strictly adhered to
so long as the machines appears to the application that it operates in this
fashion. Lock-step execution and the constraint that all processors must
execute the same instruction distinguish these machines from the others,
so-called MIMD (multiple-instruction-stream, multiple-data-stream)
computers that are described.

8
Converting To Parallel And Distributed Simulation

Distributed Computers
Two characteristics that distinguish distributed computers from parallel
machines are heterogeneity and the network used to interconnect the
machines. Unlike parallel computers, distributed systems are often
composed of stand-alone computer work- stations from different
manufacturers. Unix-based workstations (for example, Sun, Silicon
Graphics, DEC, or IBM workstations), and personal computers are most
commonly used for distributed simulations today. Heterogeneity is
important because many distributed simulators are constructed by
interconnecting existing sequential simulators (for example, tank
simulators in DIS) operating on specific workstations. Heterogeneity
eliminates the need to port existing simulators to new platforms, and it
enables participation of users with different computing equipment in
distributed simulation exercises.
Different distributed computers are distinguished by the geographical
extent covered by the system, which in turn dictates the type of network
used to interconnect the machines. Local area network (LAN) based
systems consist of a collection of machines in a limited geographic area,
such as within a single building or a university campus, interconnected
through a high-speed network or switch. MAN (metropolitan area
network) based systems have the physical extent of a city, and a WAN
(wide area network) based systems may be distributed across a nation or
the world.

Conservative Synchronization Algorithms

At first glance, this paradigm would seem ideally suited for
parallel/distributed execution; one can simply map different logical
processes to different processors and let each LP execute forward, event

MODELING AND SIMULATION 9

I MODELING AND SIMULATION

by event, and exchange messages (that schedule events for other LPs)
as needed. Unfortunately, there is a catch.
Each logical process must process all of its events, both those generated
locally and those generated by other LPs, in time stamp order. Failure to
process the events in time stamp order could cause the computation for
one event to affect another event in its past, clearly an unacceptable
situation.
Errors resulting from out-of-order event processing are referred to as
causality errors, and the general problem of ensuring that events are
processed in a time stamp order is referred to as the synchronization
problem.

Synchronization Problem
When the simulation is distributed over multiple processors, a mechanism
is required for the concurrent execution to produce exactly the same
results as the sequential execution. The goal of the synchronization
algorithm is to ensure that this is the case. It is important to realize that
the synchronization algorithm does not need to actually guarantee that
events in different processors are processed in time stamp order but only
that the end result is the same as if this had been the case.

Local Causality Constraint - A discrete-event simulation, consisting of

logical processes (LPs) that interact exclusively by exchanging time
stamped messages obeys the local causality constraint if and only if each
LP processes events in a time stamp order.

By looking at the figure as an example, event E10 affects E20 by

scheduling a third event E15 which modifies a state variable used by
E20. This necessitates sequential execution of all three events.
Observation. If each LP adheres to the local causality constraint, then the
parallel distributed execution will yield exactly the same results as a
sequential execution of the same simulation program provided that
events containing the same time stamp are processed in the same order
in both the sequential and parallel execution. Events containing the same
time stamp are referred to as simultaneous events.

10
Converting To Parallel And Distributed Simulation

Historically, the first synchronization algorithms were based on so-called

conservative approaches. The fundamental problem that conservative
mechanisms must solve is to determine when it is "safe" to process an
event. More precisely, If a process contains an unprocessed event, EIO
with time stamp TIO (and no other with smaller time stamp), and that
process can determine that it is impossible for it to later receive another
event with time stamp smaller than TIO , then EIO is said to be safe
because one can guarantee that processing the event now will not later
result in a violation of the local causality constraint. Processes containing
no "safe" events must block. As will be seen momentarily, this can lead to
deadlock situations if appropriate precautions are not taken.

Deadlock
A deadlock occurs when two or more tasks permanently block each other
by each task having a lock on a resource which the other tasks are trying
to lock. For example:
o Transaction A acquires a share lock on row 1.
o Transaction B acquires a share lock on row 2.
o Transaction A now requests an exclusive lock on row 2,
and is blocked until transaction B finishes and releases
the share lock it has on row 2.
o Transaction B now requests an exclusive lock on row 1,
and is blocked until transaction A finishes and releases
the share lock it has on row 1.
Transaction A cannot complete until transaction B completes, but
transaction B is blocked by transaction A. This condition is also called a
cyclic dependency: Transaction A has a dependency on transaction B,
and transaction B closes the circle by having a dependency on
transaction A.
Both transactions in a deadlock will wait forever unless the deadlock is
broken by an external process. The Microsoft SQL Server Database
Engine deadlock monitor periodically checks for tasks that are in a
deadlock. If the monitor detects a cyclic dependency, it chooses one of
the tasks as a victim and terminates its transaction with an error. This
allows the other task to complete its transaction. The application with the
transaction that terminated with an error can retry the transaction, which
usually completes after the other deadlocked transaction has finished.
Using certain coding conventions in applications reduces the chance that
applications will cause deadlocks.
Deadlocking is often confused with normal blocking. When a transaction
requests a lock on a resource locked by another transaction, the
requesting transaction waits until the lock is released. By default,
transactions do not time out, unless LOCK_TIMEOUT is set. The
requesting transaction is blocked, not deadlocked, because the
requesting transaction has not done anything to block the transaction

MODELING AND SIMULATION 11

I MODELING AND SIMULATION

owning the lock. Eventually, the owning transaction will complete and
release the lock, and then the requesting transaction will be granted the
lock and proceed.
Deadlocks are sometimes called a deadly embrace.
Deadlock is a condition that can occur on any system with multiple
threads, not just on a relational database management system, and can
occur for resources other than locks on database objects. For example, a
thread in a multithreaded operating system might acquire one or more
resources, such as blocks of memory. If the resource being acquired is
currently owned by another thread, the first thread may have to wait for
the owning thread to release the target resource. The waiting thread is
said to have a dependency on the owning thread for that particular
resource. In an instance of the Database Engine, sessions can deadlock
when acquiring non-database resources, such as memory or threads.

In the illustration, transaction T1 has a dependency on transaction T2 for

the Part table lock resource. Similarly, transaction T2 has a dependency
on transaction T1 for the Supplier table lock resource. Because these
dependencies form a cycle, there is a deadlock between transactions T1
and T2.

Deadlock Detection and Recovery

The principal disadvantage of the Chandy/Misra/Bryant algorithm is that a
large number of null messages can be generated, particularly if the look-
ahead is small. Recall that the approach used in this algorithm is to avoid
deadlock situations.

Deadlock Detection
The simulation computation depicted is one example of a diffusing
computation. This means the distributed computation consists of a set of
processes, and processes only perform computations upon receiving one
or more messages.
A single controller process is introduced to the distributed simulation. The
distributed simulation computation cycles through the following steps:
1. The computation is initially deadlocked.
2. The controller sends message(s) to one or more LPs
informing them that certain events are safe to process, thereby
breaking the deadlock. More will be said about this later.

12
Converting To Parallel And Distributed Simulation

3. The LP(s) process the event(s) that have been declared safe.
This typically generates new messages that are sent to other
LPs that (hopefully) cause them to process still more events, and
generate additional messages to still other LPs. The spreading
of the computation to previously blocked processes is viewed as
constructing a tree. Every process that is not blocked is in the
tree.
Whenever a message is sent to a process that is not in the tree,
that process is added to the tree, and (logically) a link is
established from the process sending the message to the process
receiving the message. LPs that are in the tree are referred to as
being engaged. Processes that are not in the tree are referred to
as being disengaged.
4. Just as the tree expands when the diffusing computation
spreads to new LPs, it also contracts when engaged LPs become
blocked. Specifically, if an LP becomes blocked, and that LP is a
leafnode in the tree, the LP removes itself from the tree and
signals its parent (the LP that originally sent it the message that
caused it to become engaged) that it is no longer in the tree. An
LP becomes a leaf node in the tree when all of the LPs it added
to the tree signal that they have removed themselves from the
tree.
5. If the controller becomes a leaf node in the tree, then the
computation is again deadlocked, completing the cycle.

Deadlock Recovery
The deadlock can be broken by observing that the message(s) containing
the smallest time stamp in the entire simulation is (are) always safe to
process. This is the event that would be processed next in a sequential
execution of the simulation program. Thus, to break the deadlock, the
simulation executive need only identify the event containing the smallest
time stamp and send a message to the LP(s) holding the event to
indicate that the event can now be safely processed.
Locating the smallest time-stamped event is relatively straightforward
because the computation is deadlocked, so no new events are being
created while the smallest time stamped event is being located.

Synchronous Execution

In the deadlock detection and recovery algorithm the processors

repeatedly cycle through "phases" of (1) one or more processors
processing simulation events and (2) deadlock resolution.
Barrier Synchronization – the mechanisms which
handles conservative synchronization algorithms which
utilizes the approach of cycling between phases, but
they explicitly control when the entire computation

MODELING AND SIMULATION 13

I MODELING AND SIMULATION

stops rather than relying on the system becoming

deadlocked.
A barrier is a general parallel programming construct that
defines a point in (wall clock) time when all of the processors
participating in the computation have stopped. When a
processor executes the barrier primitive, it blocks, and remains
blocked until all of the processors have executed the barrier
primitive. The barrier operation is completed when all of the
processors have executed the barrier primitive; each processor
is then allowed to resume execution, starting at the statement
immediately following the barrier.

Tree Barrier

The bottleneck problem is easily solved by organizing the

processors as a balanced tree with each node of the tree
representing a different processor (see Fig. 3.10 for the case of
fourteen processors). When a leaf processor reaches the barrier
point, it sends a message to its parent processor. Each interior
node of the tree waits until it receives a synchronization
message from each of its children. When it has received
such a message from each child, and has itself reached
the barrier point, it sends a message to its parent.

Butterfly Barrier

Another approach that eliminates the broadcast to notify

the processors that a global synchronization has been
achieved is the butterfly barrier.
Assume that an N processor barrier is performed, and the
processors are numbered 0, 1, 2, ..., N - 1. To simplify
the discussion, assume that N is a power of 2; it is
straightforward to extend the approach to arbitrary N. The
communication pattern among processors for this barrier
mechanism for the case of eight processors is shown in
Figure 3.11 (a).
Each processor executes a sequence of log N pairwise
barriers with a different processor at each step. A

14
Converting To Parallel And Distributed Simulation

pairwise barrier between processors i and} is

accomplished by simply having i (or}) send a message to}
(i) when it has reached the barrier point, and then wait for
a message from} (i) indicating that processor has also
reached the barrier point. In the first step, processors
whose binary addresses differ only in the least significant
bit perform a pairwise barrier; for example, processors 3
(011) and 2 (OIQ) perform a pairwise barrier. In the
second step, processors whose addresses differ only in
the second least significant bit; for example, processor 3
(011) and 1 (O!!I) synchronize. In general, in step k
processor i synchronizes with the processor whose
address differs in only the kth bit (where bits are
numbered 1,2, ... , 10gN from least significant to most
significant). These pairwise synchronizations continue for
log N steps until all of the address bits have been
scanned. This communication pattern is referred to as a
butterfly. Each processor is released from the barrier
once it has completed the log N pairwise barriers.

Transient Messages
A transient message is a message that has been sent but has not
yet been received by the destination processor. They are, in
effect, "in the network." Transient messages are an issue if
asynchronous message sends are allowed; that is, the sender is
allowed to execute after performing a message send without
waiting for the receiver to acknowledge receipt of the message.
Asynchronous sends are particularly useful in distributed
computing systems (for example, networks of workstations)
because the delay in waiting for the receiver to send an
acknowledgment for a message may be large.

MODELING AND SIMULATION 15

I MODELING AND SIMULATION

A Simple Synchronous Protocol

A simple approach using look ahead to determine safe events
can be derived by parallelizing the sequential event processing
loop. Consider a sequential simulation that has advanced to
simulation time T, which is the time of the next unprocessed
event in the event list. If the constraint is made that an event
must be scheduled at least L units of simulation time into the
future, then it can be guaranteed that all new events that are
later scheduled in the simulation will have a time stamp
greater than or equal to T +L, so any event with time
stamp less than T +L can be safely processed.

References
a. Textbook
Principles of Modeling and Simulation: A Multidisciplinary
Approach, John A. Sokolowski, Catherine M. Banks. Latest edition.
b. References
1. A Guide to Simulation, (reprint of 1983 edition), Springer. P. Bratley,
B.L. Fox and L.E. Schrage, 2012
C. Other Supplemental Materials
1. [Link]
2. [Link]
RandomVariateGenerationSlides_131022.pdf
3. [Link]
4. [Link]
[Link]/Research/Publications/_Documents/todo/conver
ted/h [Link]

16
Lesson 3 – Matrix Operations

Matrix operations built-in into Scilab include addition, subtraction, multiplication,

transpose, inversion, determinant, trigonometric, logarithmic, exponential functions and many
others. Study the following examples:
-->a=[1 2 3; 4 5 6; 7 8 9]; Define a 3x3 matrix. Semicolons indicate end of a row
-->b=a'; Transpose a and store it in b. Apostrophe (') is the transpose
operator.
-->c=a+b Add a to b and store the result in c. a and b must be of the
same size. Otherwise, Scilab will report an error.
-->d=a-b Subtract b from a and store the result in d.
-->e=a*b Multiply a with b and store the result in e. a and b must be
compatible for matrix multiplication.
-->f=[3 1 2; 1 5 3; 2 3 6]; Define a 3x3 matrix with name f.
-->g=inv(f) Invert matrix f and store the result in g. f must be square
and positive definite. Scilab will display a warning if it is ill
conditioned.
-->f*g The answer must be an identity matrix
-->det(f) Determinant of f.
-->log(a) Matrix of log of each element of a.
-->a .* b Element by element multiplication.
-->a^2 Same as a*a.
-->a .^2 Element by element square.

There are some handy utility functions to generate commonly used matrices, such as zero
matrices, identity matrices, diagonal matrices, matrix containing randomly generated numbers
etc.

-->a=zeros(5,8) Creates a 5x8 matrix with all elements zero.

-->b=ones(4,6) Creates a 4x6 matrix with all elements 1
-->c=eye(3,3) Creates a 3x3 identity matrix
-->d=eye(3,3)*10 Creates a 3x3 diagonal matrix, with diagonal elements equal to 10.

It is possible to generate a range of numbers to form a vector. Study the following

commands:

-->a=[1:5] Creates a vector with 5 elements as follows [1, 2, 3, 4, 5]

-->b=[0:0.5:5] Creates a vector with 11 elements as follows [0, 0.5, 1.0,
1.5, ... 4.5, 5.0]

A range requires a start value, an increment and an end value, separated by colons (:). If
only two values are given (separated by only one colon), they are taken to be the start and end
values and the increment is assumed to be 1 (a:b is the short form for a:1:b, where a and b
are numbers). The increment must be negative when the start value is greater than the end value.
You can create an empty matrix with the command:
-->a=[ ]
Distributed Virtual Environments

Introduction

A principal goal in most virtual environments is concerned with

achieving a "sufficiently realistic" representation of an actual imagined
system, as perceived by the participants embedded into the
environment. What "sufficiently realistic" means depends on what one
is trying to accomplish. In the context of training, this means that
humans embedded into the environment are able to develop skills that
would be applicable in actual situations they might later encounter.

Thus, the environment must be sufficiently realistic that the system

with which the operator is working, such as an aircraft in the case of a
flight simulator, behaves the way a real aircraft would behave in terms
of its response to controls and other effects such as smoke or wind.

Contrasting DVE and PDES Systems

Driven primarily by differing requirements, key features that
distinguish DVE from PDES systems are summarized below:

• Paced versus unpaced execution. Unlike PDES systems which are

typically designed to achieve as-fast-as-possible execution of the
simulation, advances of simulation time in DVEs are almost always
paced with wallclock time.

• Geographical distribution. PDES systems are seldom executed in a

geographically distributed fashion because of the difficulty in
achieving speedup when communication latencies are high.

• Repeatability. Many analytic simulation applications must produce

exactly the same results if the simulation program is re-executed with
the same inputs. This is often not so essential in DVEs.

• Synchronization requirements. Because the goal of a DVE is to

provide a sufficiently realistic environment as perceived by its users,
synchronization requirements can often be relaxed. For example, if
two or more events occur so close together in time that the humans
viewing the environment cannot perceive which occurred first, it may
be permissible for the distributed simulation to process those events in
any order without compromising the goals of the training exercise (or
entertainment session).

Modeling And Simulation 1

I Modeling and Simulation

Server versus Serverless Architectures

An important decision in the design of a DVE that includes
geographically distributed participants and/or resources concerns the
physical distribution of the simulation computations. Possible
approaches include the following:

• Centralized server architecture. As shown in Figure 7.l(a),

interactive users (clients) may "log into" a central computer (a server)
that maintains the shared state of the virtual world. Machines at the
user's site may perform local simulation computations pertaining to
entities "owned" by the client, and generate one or more graphical
displays for the user.

• Distributed server architecture. This is similar to the centralized

server architecture, except that a multiprocessor or a collection of
processors interconnected on a LAN is used to implement the server.
The shared state of the virtual world is now distributed among the
processors within the compute server and must be maintained by
exchanging messages among these processors.

2
Distributed Virtual Environments

• Distributed, serverless architecture. Rather than utilize a server, the

simulation computations are distributed among geographically
distributed processors; see Figure 7.1 (c). Computation-only entities
may now be distributed among geographically distributed processors.

Distributed Interactive Simulation

Distributed Interactive Simulation (DIS) has been used extensively in
building DVEs for training in the defense community. A principal
objective of DIS (and subsequently the High Level Architecture effort)
is to enable interoperability among separately developed simulators.

The primary mission of DIS is to define an infrastructure for linking

simulations of various types at multiple locations to create realistic,
complex, virtual "worlds" for the simulation of highly interactive
activities (DIS Steering Committee 1994). A DIS exercise may include
(1) human-in-the-loop systems such as tank or flight simulators
(sometimes referred to as virtual simulators), (2) computation only
elements such as wargame simulations (sometimes referred to as
constructive simulations), and (3) live elements such as instrumented
tanks or aircraft.

DIS Design Principles

DIS utilizes the following design principles (DIS Steering Committee

1994):

• Autonomous simulation nodes. Autonomy is important because it

simplifies development (developers of one simulator need not be
overly concerned with details of other simulators in the DVE), it
simplifies integration of existing (legacy) simulators into a DVE, and
it simplifies allowing simulators to join or leave the exercise while it is
in progress.
• Transmission of "ground truth" information. Each node sends
absolute truth concerning the state of the entities it represents. This
state information will usually be a subset of the state variables
maintained by the node.
• Transmission of state change information only. To economize on
communications, simulation nodes only transmit changes in behavior.
Information concerning objects that do not change (for example, static
terrain) does not need to be transmitted over the network.
• Use of "dead reckoning" algorithms to extrapolate entity state
information. Each node maintains information concerning other

Modeling And Simulation 3

I Modeling and Simulation

entities, such as those that are visible to it on the battlefield. This

information is updated whenever the entities send new status
information via PDUs.

DIS PDUs

A key ingredient in DIS to support interoperability among simulators

is the definition of standard PDU types that are communicated among
simulators. Several DIS PDUs are defined to transmit events of
interest to entities in different DIS nodes, among which are the
following examples:

• Entity state PDUs contain ground truth information indicating the

appearance and location of an entity.
• Fire PDUs indicate a munition has been fired from an entity. This
might cause a muzzle flash to be produced on the displays of entities
that can view the entity firing the munition.
• Detonation PDUs indicate the trajectory of a munition has
completed. Entities receiving this PDU must assess their damages and
produce appropriate audio and visual effects from the detonation.

Time Constraints

It is clear that the latency to transmit a message over the network will
play an important role in determining the "realism" of the virtual
environment. For example, if the Fire PDU is delayed in the network,
it could be. Received by the second simulator after the detonation
PDU is received so it could appear that the effect (the shell detonating)
precedes the cause (the shell being fired) in the second simulator.

Dead Reckoning
Consider a DVE consisting of a collection of vehicles moving over
some space. Assume that each simulator executes on a separate
processor and models a single vehicle. Each simulator must generate a
display for its driver indicating the position and orientation of the other
vehicles within visual range. Assume that the display is updated at a
rate of 60 times per second. Each simulator maintains locally the
position of other vehicles, and every 17 milliseconds (1/60th of a
second) generates a suitable graphical image. In order to keep other
vehicles up to date, each simulator also broadcasts its current location
to the other simulators every 17 milliseconds.

4
Distributed Virtual Environments

A technique called dead reckoning can be used to reduce

interprocessor communication. The basic idea is that rather than send
frequent state updates, each simulator estimates the location of remote
entities from its last reported position, direction, velocity, and the like.
For example, if it is shown that the vehicle is traveling east at 50 feet
per second, and its coordinate position at time 200 seconds into the
simulation is (1000, 1000) where each unit corresponds to one foot,
then it can be predicted that one second later it will be at position
(1050, 1000) without transmitting a position update message.

High Level Architecture

In the HLA a distributed simulation is called a federation, and each
individual simulator is referred to as a federate. A federate need not be
a computer simulation; it could be an instrumented physical device
(for example, the guidance system for a missile) or a passive data
viewer.

Next, we give an historical perspective on the HLA, followed by

discussion of technical aspects of HLA federations. We are
specifically concerned with the interface to the distributed simulation
executive, called the Run-Time Infrastructure (RTI) in the HLA, in
order to identify the types of services that are provided to support
DVEs.

Historical Perspective

The roots for the HLA stem from DIS aimed primarily at training
simulations and the Aggregate Level Simulation protocol (ALSP)
which applied the concept of simulation interoperability to war gaming
simulations. The HLA development began in October 1993, when the
Defense Advanced Research Projects Agency (DARPA) awarded
three industrial contracts to develop a common architecture that could
encompass the DoD modeling and simulation community. The designs
were received in January 1995 and, with inputs from the DoD
community, were combined to form an initial architecture proposal. In
early 1995, the Defense Modeling and Simulation Office (DMSO)
formed a group called the Architecture Management Group (AMG)
which included representatives from several sizable efforts in the DoD
in modeling and simulation. The AMG was given the task of
overseeing the development of the HLA. An initial architecture

Modeling And Simulation 5

I Modeling and Simulation

proposal was given to the AMG in March 1995, and the HLA began to
take form. The AMG formed several technical working groups to
develop specific aspects of the HLA. These included definition of the
Interface Specification and the Object Model Template.

Specifically, four so-called proto-federations (prototype federations)

were formed:

• The platform protofederation including DIS-style training

simulations; that is, real-time human-in-the-loop training simulations.

• The Joint Training protofederation including as-fast-as-possible time-

driven and event-driven wargaming simulation models to be used for
command-level training.

• The analysis protofederation including as-fast-as-possible event-

driven wargaming simulations such as those that might be used in
acquisition decisions.

• The engineering protofederation including hardware-in-the-loop

simulations with hard real-time constraints.

Protofederation development was largely focused on adapting existing

simulations for use in the HLA to verify the claims that such an
infrastruture could successfully support model reuse.

Overview of the HLA

Any real-world. entity that is visible to more than one federate is

represented in the HLA by an object. The HLA does not assume the
use of object-oriented programming language, however. Each object
instance contains:

(1) an identity that distinguishes it from other objects,

(2) attributes that indicate those state variables and parameters of an
object that are accessible to other objects, and
(3) associations between objects (for example, one object is part of
another object).

The HLA includes a non-runtime and a runtime component. The non-

runtime components specify the object model used by the federation.
This includes the set of object types chosen to represent the real world,
the attributes and associations (class definitions) of these objects, the
level of detail at which the objects represent the world (for example,

6
Distributed Virtual Environments

spatial and temporal resolution), and the key models and algorithms
(for example, for dead reckoning) that are to be used.

The runtime component is the RTI that provides facilities for allowing
federates to interact with each other, as well as a means to control and
manage the execution.

Individual federates may be software simulations (combat models,

flight simulator, etc.), live components (for example, an instrumented
tank), or passive data viewers. The RTI can be viewed as a distributed
operating system that provide the software environment necessary to
interconnect cooperating federates.

It provides several categories of services, as described below.

More precisely, HLA consist of three components:

1. The HLA rules that define the underlying design principles

used in the HLA.

2. An object model template (OMT) that specifies a common

format for describing the information of common interest to the
simulations in the federation.

3. An interface specification that defines the services provided by

the Run-Time Infrastructure (RTI) for linking together
individual federates.

HLA Rules

The HLA rules summarize the key principles behind the HLA. These
principles were discussed in the previous lesson, so we do not
elaborate upon them further. The OMT specifies the class hierarchy
for objects and interactions, and details concerning the type and
semantics of object attributes. It is used to specify both SOMs and
FOMs. Class definitions are similar to those used in object oriented
design methodologies.

The OMT (version 1.3) consists of the following tables:

• The object model identification table provides general information
concerning the FOM or SOM such as its name, purpose, version, and
point-of-contact information.
• The object class structure table specifies the class hierarchy of
objects in the SOM/FOM.

Modeling And Simulation 7

I Modeling and Simulation

• The attribute table enumerates the type and characteristics of object

attributes.
• The interaction class structure table defines the class hierarchy
defining the types of interactions in the SOM/FOM.
• The parameter table defines types and characteristics of interaction
parameters.
• The routing space table specifies the nature and meaning of
constructs called routing spaces that are used to efficiently distribute
data throughout large federations;
• The FOM/SOM lexicon is used to describe the meaning of all terms
used in the other tables, such as the meanings of object classes,
attributes, interaction classes, and parameters.

Attribute Table

Each object class includes a fixed set of attribute types. Attributes

specify portions of the object state shared among federates during the
execution. The object model template represents the following
characteristics of attributes (corresponding to columns in the attribute
table):

• Object class. This indicates the class in the object class structure
table, such as Vehicle, and can be chosen from any level in the class
hierarchy.
• Attribute name. This specifies the name of the attribute, such as
position.
• Data type. This field specifies the type of the attribute and is not
unlike type specifications in conventional programming languages. For
basic data types, this field specifies one of a standard set of base data
types, such as integer or floating point.

Interaction Class Structure Table

Interactions are actions taken by one federate that have an affect on

another federate(s). A class hierarchy similar to that used for objects is
used to document interaction types. For example, in Table 7.3

8
Distributed Virtual Environments

Observers in the battlefield (called Stealth viewers) can similarly

receive interactions and display them but cannot generate suitable
actions from the interaction. The rules concerning inheritance of
classes in interaction class structure tables are essentially the same as
those of the object class structure table.

Parameter Table

Just as attributes provide state information for objects, parameters

provide state information for interactions. Parameter types are
specified in the parameter table. The parameter table includes many
fields that are similar to attribute tables. Specifically, it includes
columns to specify the interaction class, parameter name, and the data
type, cardinality, units, resolution, accuracy, and accuracy condition
for parameters. Their meaning is similar to that specified in the
attribute table. The other entries in the attribute table that are not
included in the parameter table concern state updates and ownership
transfer, which do not apply to interactions.

Interface Specification

In the HLA, there is a clear separation between the functionality of

individual federates and the RTI. For example, all knowledge
concerning the semantics and behavior of the physical system being
modeled is within the federate.

The interface specification defines a set of services provided by

simulations or by the Run-Time Infrastructure (RTI) during a
federation execution. HLA runtime services fall into the following
categories:

• Federation management. This includes services to create and delete

federation executions, to allow simulations to join or resign from
existing federations, and to pause, checkpoint, and resume a federation
execution.

• Declaration management. These services provide the means for

simulations to establish their intent to publish object attributes and
interactions, and to subscribe to updates and interactions produced by
other simulations.

• Object management. These services allow simulations to create and

delete object instances, and to produce and receive individual attribute
updates and interactions.

Modeling And Simulation 9

I Modeling and Simulation

• Ownership management. These services enable the transfer of

ownership of object attributes during the federation execution; recall
that only one federate is allowed to modify the attributes of an object
instance at any time.

• Time management. These services coordinate the advancement of

logical time, and its relationship to wallclock time during the
federation execution.

• Data distribution management. These services control the

distribution of state updates and interactions among federates, in order
to control the distribution of information so that federates receive all of
the information relevant to it and (ideally) no other information.

Typical Federation Execution

A typical federation execution begins with the invocation of federation

management services to initialize the execution. Specifically, the
Create Federation Execution service is used to start the execution, and
each federate joins the federation via the Join Federation Execution
service.

Each federate will then use the declaration management services to

specify what information it can provide to the federation, and what
information it is interested in receiving. The Publish Object Class
service is invoked by the federate to indicate it is able to provide new
values for the state of objects of a specific class, such as the position of
vehicles modeled by the federate. Conversely, the Subscribe Object
Class Attribute service indicates the federate is to receive all updates
for objects of a certain class, such as the altitude attribute of all aircraft
objects.

Federates may use the data distribution management services to further

qualify these subscriptions, such as to say that the federate is only
interested in aircraft flying at an altitude greater than 1000 feet. The
federate may then inform the RTI of specific instances of objects
stored within it via the Register Object Instance (object management)
service.

10
Lecture 4 – Sub-matrices

A sub-matrix can be identified by the row and column numbers at which it starts and ends. Let us
first create a matrix of size 5x8.

-->a=rand(5,8)*100 Generates a 5x8 matrix whose elements are generated as random

numbers.

Since the elements are random numbers, each person will get a different matrix. Let us
assume we wish to identify a 2x4 sub-matrix of a demarcated by rows 3 to 4 and columns 2 to
5. This is done with a(3:4, 2:5). The range of rows and columns is represented by the range
commands 3:4 and 2:5 respectively. Thus 3:4 defines the range 3, 4 while 2:5 defines the
range 2, 3, 4, 5. However, matrix 'a' remains unaffected.

-->b=a(3:4, 2:5) This command copies the contiguous sub-matrix of size 2x4 starting from
element at (3,2) up to element (4,5) of a into b.

A sub-matrix can be overwritten just as easily as it can be copied. To make all elements
of the sub-matrix between the above range equal to zero, use the following command:
-->a(3:4, 2:5)=zeros(2,4) This command creates a 2x4 matrix of zeros and puts it into
the sub-matrix of a between rows 3:4 and columns 2:5.

Note that the sub-matrix on the left hand side and the matrix on the right side (a zero
matrix in the above example) must be of the same size.

While using range to demarcate rows and/or columns, it is permitted to leave out both the
start and end value in the range, in which case they are assumed to be 1 and the number of the
last row (or column), respectively. To indicate all rows (or columns) it is enough to use only the
colon (:). Thus, the sub-matrix consisting of all the rows and columns 2 and 3 of a, the
command is a(:, 2:3). Naturally a(:, :) represents the whole matrix, which of course
could be represented simply as a.

However, it is not possible to specify only the start value of the range and leave out the
end value or vice versa. Either both must be specified or both must be left out. Scilab uses a
special symbol to refer to the number of the last row (or column) by the symbol “$”. This can be
used within range specifications to represent the number of the last row (or column).

It must also be noted that the sub-matrix need not necessarily consist of contiguous rows
and/or columns. For example, to extract the odd rows and column from matrix a, you could use
the following command:

-->c=a(1:2:$, 1:2:$) This command copies the sub-matrix of a with rows 1, 3, 5 and
columns 1, 3, 5, 7 into b. The rows are represented by the
range 1:2:$ which implies start from 1, increment by 2 each
time and up to $, which in this case is 5.
Networking and Data Distribution

Introduction

The network plays a critical role in distributed simulation systems.

Simulator-to-simulator message latency can have a large impact on the
realism of the virtual environment. One hundred to 300 milliseconds are
considered adequate for most applications, though for some, latencies as low
as a few tens of milliseconds may be required.

Aggregate network bandwidth, the amount of data transmitted through the

network per unit time, is also important because large-scale distributed
simulations can easily generate enormous amounts of data. Thus it is
important to both achieve maximal bandwidth and minimal latency in the
network itself, as well as to control the amount of data that must be
transmitted and still provide each participant a consistent view of the virtual
world.

Message-Passing Services
All networks provide the ability to transmit messages between simulators.
Having said that, there are a number of different characteristics that
differentiate different types of network services. Some of the more important
characteristics for DVEs are enumerated below. Simple DVEs may utilize
only one type of communication service.

Reliable Delivery

A reliable message delivery system is one where the service guarantees that
each message will be received at the specified destination(s), or an exception
will be raised for any message that cannot be delivered. Typically, this means
the networking software will retransmit messages if it cannot determine (for
example, via an acknowledgment message) that the message has been
successfully received.

An unreliable or best-effort delivery service does not provide such a

guarantee.

Message Ordering

An ordered delivery service guarantees that successive messages sent from

one simulator to another will be received in the same order in which they
were sent. This property may or may not be provided with the network
delivery service.
For example, if successive messages are routed along different paths through
the network, they may not arrive in the same order that they were sent.

Modeling And Simulation 1

I Modeling and Simulation

Connection-Oriented versus Connectionless

Communication

In a connectionless (also called a datagram) service, the sender places the

data it wishes to transmit into a message, and passes the message to the
networking software for transmission to the destination(s). This is analogous
to mailing a letter through the postal system. In a connection-oriented
service, the sender must first establish a connection with the destination
before data can be sent. After the data have all been sent, the connection
must be terminated. Connection-oriented services are analogous to telephone
services.

Unicast versus Group Communication

A unicast service sends each message to a single destination. A broadcast

service sends a copy of the message to all possible destinations, while a
multicast mechanism sends it to more than one, but not necessarily all,
destinations. Multicast communication is important when realizing large-
scale simulations.

For example, a typical operation is a player needs to send a state update

message to the other players that can see it.

Examples: DIS and NPSNet

The communication requirements in the DIS standard 1278.2 specify three

classes of communication services, based in part on existing networking
products:

1. Best-effort multicast
2. Best-effort unicast
3. Reliable unicast

These communication services are available in the Internet Protocol suite,

discussed later in this chapter. There, best-effort communication is achieved
using the connectionless User Datagram Protocol (UDP) and reliable
communication is achieved using the Transmission Control Protocol (TCP)
which provides a connection-oriented service.

An example illustrating the communication services typically used in large

DVEs is NPSNet. NPSNet is a project at the Naval Post Graduate School
aimed at developing large-scale virtual environments containing thousands of
users. The NPSNet communications architecture is described in Macedonia,
Zyda et al. (1995).

It provides four classes of communications:

1. Light weight interaction. This service provides a best-effort,
connectionless group communication facility. State updates, interactions, and

2
Networking and Data Distribution

control messages will typically use this service. Each message must be
completely contained in a maximum transfer unit (MTU), sized at 1500 bytes
for Ethernet and 296 bytes for 9600 bits/second point-to-point links. It is
implemented with a multicast communication mechanism.

2. Network pointers. These provide references to resources, analogous to

links in the World Wide Web. They are somewhat similar to lightweight
interactions (for example, both use multicast) but contain references to
objects, while lightweight interactions contain the objects themselves.

3. Heavy weight objects. These provide a reliable, connection-oriented

communication service.

4. Real-time streams. These provide real-time delivery of continuous streams

of data, as well as sequencing and synchronization of streams. They are
intended for transmission of video or audio streams.

Networking Requirements
The success of a DVE, especially large-scale DVEs containing many
participants often depends critically on the performance of the underlying
network infrastructure.

For example, networking requirements for DIS are described in IEEE Std
1278.21995 (1995). Specific requirements include the following:
• Low latency. The DIS standard calls for simulator-to-simulator latencies of
under 300 milliseconds for most (termed loosely coupled) interactions, and
100 millisecond latency for tightly coupled interactions, such as where a user
is closely scrutinizing the actions of another participant in the DVE.

• Low-latency variance. The variance of delay between successive messages

sent from one processor to another is referred to as jitter. Low jitter may be
required in a DVE to maintain a realistic depiction of the behavior of remote
entities. Jitter requirements can be alleviated somewhat by buffering
messages at the receiver to smooth fluctuations in latency. Dead reckoning
also provides some resilience to delay variance. The DIS standard specifies a
maximum dispersion of arrival times for a sequence of PDUs carrying voice
information to be 50 milliseconds.

• Reliable delivery. As discussed previously, best-effort communication is

sufficient for much of the traffic generated in a DVE, but reliable delivery is
important for certain, nonperiodic events. The DIS standard calls for 98% of
the PDUs for tightly coupled interactions and 95% for loosely coupled
interactions to be delivered within the specified latency requirement.

• Group communication. Group communication services are important for

moderate to large DVEs, especially in geographically distributed systems
where broadcast communication facilities are not readily available. A

Modeling And Simulation 3

I Modeling and Simulation

multicast group is the set of destinations that is to receive messages sent to

the group, analogous to the set of subscribers to an Internet newsgroup.

Large DVEs present a particularly challenging application for multicast

protocols because they may require group communication services that
support the following:

1. Large numbers of groups (for example, thousands).

2. A single simulator to belong to many different groups at one time.
3. Frequent changes to group composition that must be realized quickly (for
example, within a few milliseconds) so that simulators do not miss important
information.

• Security. Certain applications such as defense simulations have security

requirements (for example, to prevent eavesdropping on classified
information). Sensitive data must be encrypted at the source and decrypted at
the destination. This, of course, affects the latency requirements, which must
include the time to perform such operations.

Networking Technologies
Networks may be broadly categorized as local area networks (LANs)
covering a limited physical extent (for example, a building or a campus),
metropolitan area networks (MANs) covering a city, and wide area networks
(WANs) that can extend across continents. Unlike parallel computing
platforms which typically use proprietary interconnection networks, the
distributed computers typically used to implement DVEs have standard
networking technologies for interconnecting machines.

In general, LANs provide a much "friendlier" environment for distributed

simulation systems than WANs (MANs are intermediate between these two).
LANs often operate at link bandwidths, ranging from many megabits per
second (for example, Ethernet operates at 10 MBits per second) up to a
gigabit per second or more, and can achieve application-to-application
latencies of a few milliseconds or less.

LAN Technologies

Historically LAN interconnects have typically been based on either a shared

bus or a ring interconnection scheme (see Fig. 5.1). A recent phenomenon is
the appearance of switched LANs, such as those based on Ethernet or
asynchronous transfer mode (ATM) switching technology. These are
increasing in popularity, especially for applications requiring high
bandwidth. Bus and ring topologies date back to the 1970s and have been in
widespread use since then. Each is discussed next.

4
Networking and Data Distribution

Fig.5.1 Typical LAN topologies. (a) Bus-based network; (b) ring network

Bus-Based Networks. In a bus-based system, each computer connects

directly to the bus via a tap. Actually, as shown in Figure 5.1(a), the bus may
consist of many bus segments that are interconnected by a circuit, called a
repeater, that copies the signal from one segment of the bus to another,
amplifying the signal to compensate for attenuation. Each message is
broadcast over the bus. Processors connected to the bus must check the
address of the message against their local address and read the message into
their local memory if there is a match.

Rings. Here, the processors are organized as a ring using point-to-point

communication links (rather than a shared bus) between pairs of processors,
as shown in Figure 5.1(b). Data circulate in one direction on the ring. When a
message passes through a processor, the message's destination address is
compared with that of the processor. If there is a match, the processor retains
a copy of the message. In some rings the destination processor removes the
message from the ring. In others, the message is allowed to circulate around
the ring, in which case the source is responsible for removing the message.

Switched LANs. Switched LANs are networks based on N-input, N-output

switches. Recently these have seen greater use, especially with the advent of
asynchronous transfer mode (ATM) technology which has resulted in several
commercial products. A small switched LAN network topology is shown in
Figure 5.2(a). Each link in this figure is bidirectional; it can carry traffic in
both directions.

Modeling And Simulation 5

I Modeling and Simulation

(a) (b)
Fig. 5.2 Switched LAN. (a) Typical topology; (b) four-input, four-output switch.

A four-input, four-output switch is depicted in Figure 5.2(b). The switch

contains tables that indicate for each input port and channel which output
port and channel are used in the next hop of the connection. When a cell
arrives, its incoming port number, VPI, and CPI are used to look up the
outgoing port and channel number. The cell is routed through the internal
switch fabric to the output link, and is sent on that link with the new VPI and
VCI to identify the channel that is being used. The switch fabric contains a
switching circuit, such as a crossbar switch, that allows simultaneous
transmission of cells from different input links to different output links.

Switched LANs are more expensive than bus or ring networks because of the
need for switching hardware, compared to the cables and taps required in
Ethernet. Switched LANs can provide higher bandwidth in applications
where the bus/ring becomes a bottleneck, so they are becoming more widely
used where high bandwidth communications are required.

WAN Technologies

Historically, communications in wide area networks have evolved

from two distinct camps, the telephone industry and the computer data
communications industry. In voice communication using telephones,
the sound produced by the speaker is converted to an electrical signal
that is then sampled at regular intervals. Each sample is transmitted
through the network and converted back to sound at the receiver.
Telephone voice traffic requires the network to provide a steady
stream of voice samples flowing from the speaker to the listener with a
minimal amount of latency.

Quality of Service

Much current work in the networking community has been focused on

trying to achieve both the predictable, low-latency properties in circuit

6
Networking and Data Distribution

switching and the efficient utilization of bursty traffic in packet

switching. This is accomplished by segregating different types of
traffic according to their bandwidth and delay requirements. The basic
idea is to provide traffic requiring low latency and jitter certain
amounts of guaranteed bandwidth, similar to the guarantees made in
circuit switching.

A network architecture designed to provide QoS guarantees to

applications includes several important components (Zhang 1993):
• Flow specification. This is a language used to specify characteristics
of the message flows produced by traffic sources and the QoS
requirements of the application with respect to the flows.
• Routing. The routing algorithms specify the paths used to transmit
messages through the network. This includes paths for point-to-point
traffic as well as routing trees for multicast traffic. The routing
algorithm can have a large effect on the QoS provided to the
application; a poor routing algorithm will result in congestion in the
network that might otherwise have been avoided.
• Resource reservation. These protocols provide a means to reserve
resources in the network such as bandwidth and message buffers for
traffic produced by the application. RSVP is one example of such a
protocol that propagates resource reservation requests among nodes in
the Internet to reserve resources for unicast and multicast traffic
(Zhang 1993).
• Admission control. Since the network only has a finite amount of
resources, some reservation requests must be rejected in order to
ensure QoS guarantees for other traffic flows that have already been
accepted can be maintained. Admission control algorithms determine
which resource reservation requests are accepted and which are
denied.
• Packet scheduling. These algorithms determine which packet is
transmitted over each communication link next. As discussed in the
previous section, this can significantly impact the QoS provided to
each traffic flow.

Communication Protocols
When dignitaries from two foreign countries come together, a protocol
is necessary for the two to interact and communicate, but without each
offending the other according to their own local customs and
procedures. Similarly interconnecting two or more computers,
particularly computers from different manufacturers, requires
agreement along many different levels before communication can take
place. For example, what cable and connectors should be used? What
is the unit of data transmitted: a byte, a packet, a variable length

Modeling And Simulation 7

I Modeling and Simulation

message, or...? Where is the destination address stored in the message?

What should happen if data transmitted over a link are lost or damaged
by a transmission error? The set of rules and conventions that are used
to precisely answer questions such as these are referred to as a
communication protocol.

OSI Protocol Stack

The International Standards Organization (ISO) defined the Open

System International (abbreviated OSI) reference model as a guide for
protocol specification. It is intended as a framework into which
specific protocol standards can be defined. Seven layers are defined, as
depicted in Figure 5.4. Each of these layers is described briefly to
convey the functionality provided by each layer.

Layer 1: Physical Layer The physical layer is concerned with defining

the electrical signals (optical signals in the case of fiber optic links, or
electromagnetic signals in the case of microwave or radio links) and
mechanical interface to enable the transmission of a bit stream across a
communication link. Detailed information such as the voltage levels
for ones and zeros, timing information, the dimension of connectors,
and the signal assigned to each wire of the link are specified here.
RS-232-C is an example of a physical layer protocol that is often used
to connect terminals to computers.

Layer 2: Data Link Layer The data link layer divides the stream of
bits provided by the physical layer into frames and performs error
checking on individual frames. Error checking is performed by
combining all of the bits in the frame (for example, adding all of the
bytes together, although more sophisticated techniques are often used)
to produce a compact checksum which is appended to the end of the
frame. The receiver performs the same operation on the bytes of the
frame and compares the result with the checksum at the end. If they do
not match, the frame is discarded, and a protocol to retransmit the
corrupted frame comes into play. For example, the receiver might send
a signal to the sender asking it to retransmit the frame.

Layer 3: Network Layer The network layer is responsible for creating

a path through the network from the sender to the receiver. This
requires a routing function to specifY which outgoing link should be
used at each hop as the data move through the network. Routing is not
as straightforward as it might seem at first because it may be desirable
to take into account loading on the network in order to route messages
to bypass congested links.

8
Networking and Data Distribution

Layer 4: Transport Layer The transport layer provides an end-to-end

communication service between hosts, hiding details of the underlying
network. Large messages are broken into packets in this layer, and are
transmitted through the network and reassembled at the destination.
The two most well-known transport layer protocols are the
Transmission Control Protocol (TCP) and the User Datagram
Protocol (UDP). Both are implemented in the DoD protocol stack.
TCP provides a reliable, connection-oriented, ordered communication
service.

Layer 5: Session Layer The session layer is applicable when

connection-oriented communications are used. It enhances the
transport layer by providing dialogue control to manage who's talking,
and synchronization.

Layer 6: Presentation Layer The presentation layer provides a means

for parties to communicate without concern for low level details of the
representation of data. For instance, data types, such as floating point
numbers, may be represented differently on different machines, so
some conversion is necessary if these numbers are transmitted across
the network.

Layer 7: Application Layer This layer defines a collection of protocols

for various commonly used functions required by end users. Examples
include protocols for file transfers, electronic mail, remote login, and
access to directory servers.

ATM Protocol Stack

Circuit switching is well suited for voice traffic but is inefficient for
bursty data communications. Conversely, packet switching is more
efficient for bursty traffic but suffers from unpredictable latencies and
increased jitter, making it less attractive for voice communication.
Asynchronous transfer mode (ATM) technology was developed as a
means to efficiently handle both types of traffic, as well as anothers
such as video for teleconferencing and multimedia applications. ATM
uses a hybrid approach that features virtual circuits and cell switching.
The protocol stack for ATM defines three layers, the ATM physical
layer, the ATM layer, and the ATM Adaptation layer (AAL). Standard
transport layer (level 4) protocols such as TCP can then be built on top
of the ATM services.

Modeling And Simulation 9

I Modeling and Simulation

Level 1: ATM Physical Layer The ATM physical layer protocols

provide similar functionality to the physical layer in the OSI model.
Data may be transferred between two locations by one of two means:
1. An ATM adapter board in a computer can put a stream of
cells directly onto the wire or fiber. A continuous stream of
cells is sent. If there are no data, empty cells are transmitted.
This approach is usually used in switched LANs using ATM.
2. ATM cells may be embedded into another framing protocol.
In particular, cells may be transmitted via the Synchronous
Optical NETwork (SONET) protocol which is widely used in
the telephone industry.

Level 2: ATM Layer The ATM layer deals with cell transport through
the network and routing. Each cell is 53 bytes including a 5 byte
header and 48 byte payload (data). The 48 byte payload size was a
compromise between 32 (promoted by Europe) and 64 (promoted by
the United States).

Level 3: ATM Adaptation Layer The adaptation layer is responsible for

"adapting" specific types of data (for example, video frames, voice
samples, data packets) for transmission through the network.

Several different adaptation layer protocols are defined, optimized for

different types of traffic
1. AALl supports constant bit rate (CBR) traffic such as that occurring
in uncompressed voice and video. This traffic is usually connection
oriented and sensitive to delays.

2. AAL2 supports variable bit rate (VBR) traffic that is connection

oriented, and sensitive to delays. Some video and audio traffic belong
to this category, such as video where the number of bits used to
represent each video image is reduced using a compression algorithm,
resulting in a varying number of bits from one video frame to the next.

3. AAL3/4 supports VBR traffic that is not delay sensitive, and mayor
may not be connection oriented. Computer-generated data (for
example, file transfers or electronic mail) is often of this type. This is
called AAL3/4 (rather than just AAL3) for historical reasons.
Originally two different protocols were defined, one to support
connection-oriented services, and the second for connectionless
services. It was later discovered that the resulting mechanisms were
very similar, so these were combined.

4. AAL5 also supports delay insensitive VBR traffic but is simpler

than AAL3/4. This protocol is also called SEAL (Simple and Efficient

10
Networking and Data Distribution

Adaptation Layer); it was proposed after it was found that AAL3/4

was more complex than necessary to support computer-generated
traffic.

Internetworking and Internet Protocols

A wide variety of different networking technologies and protocols

have been developed, each with different advantages and
disadvantages. Many are in use today. The idea in internetworking is
to be able to link together different types of networks to form a
"network of networks" that appears to users as a single network.
In this way, users connected to an Ethernet LAN can communicate
with users connected to a token ring as if they were together on a
single network. By convention, internetworking (with a lower case "i")
refers to the practice of hooking together different networking
technologies to create a new network, and the Internet (upper case "I")
refers to the global network of networks in widespread use today.

The suite of Internet protocols is the most popular in use today. It is an

open standard governed by the Internet Engineering Task Force
(IETF). The protocol stack consists of five layers, with several
protocols defined within each layer, affording one the ability to pick
and choose the protocol that best fits one's application. These protocols
cover the physical, data link, network, transport, and application layers
of the OSI reference model, or levels 1 through 4, and level 7.

Level 1: Internet Physical Layer The internetworking concept suggests

many different physical layer protocols, and indeed, many different
physical layer protocols defined today use the Internet protocol stack.
Ethernet is perhaps the most popular among users connected to a LAN.
SLIP (Serial Line Internet Protocol) is used for serial lines, such as
home access to the Internet via personal computers. Token ring
protocols are also used, as well as many others.

Level 2: Data Link Layer As mentioned earlier, standard protocols are

needed for mapping IP addresses to physical addresses for different
types of subnetworks. For example, Address Resolution Protocol
(ARP) maps IP addresses to Ethernet addresses and Reverse ARP
(RARP) is used to map Ethernet addresses to IP addresses. These are
defined in the data link layer.

Level 3: Network Layer Three network layer protocols are defined. In

addition to IP, two other protocols called ICMP (Internet Control
Message Protocol) and IGMP (Internet Group Multicast Protocol) are

Modeling And Simulation 11

I Modeling and Simulation

defined. ICMP is used to send control messages between routers and

hosts, such as to implement flow control and to indicate errors. IGMP
is used for multicasting.

Level 4: Transport Layer Two transport layer protocols are defined,

UDP (User Datagram Protocol) and TCP (Transport Control Protocol).
These are sometimes denoted TCPlIP and UDPlIP to designate that
the protocols operate using IP at the network layer.

Level 5: Application Layer Several application protocols are defined at

the top of the protocol stack. Some well-known protocols include File
Transfer Protocol (FTP) and Trivial File Transfer Protocol (TFTP) for
transferring files between remote hosts, TELNET for creating a login
session on a remote host, Simple Mail Transfer Protocol (SMTP) for
exchanging electronic mail, and Domain Name Service (DNS) which
provides services for mapping easier to remember symbolic host
names such as [Link] to IP addresses.

Group Communication
Here, we describe the communication facilities that are often provided
to support group communications.

Group and Group Communication Primitives

A group is a set of processes, or here, simulators, such that each

receives a copy of every message sent to the group. Open groups are
groups where the sender need not be a member of the group to send a
message to the group. Closed groups only allow simulators that are
part of the group to send a message to the group. Groups may
dynamically expand and contract during the execution of the
distributed simulation. For example, if a vehicle moves to a position
that makes it visible to another player, the latter should be added to the
group to which the vehicle simulator is publishing position updates so
that it can receive updates concerning the vehicle's position. Ajoin
operation is used to add a simulator to a group. Conversely, a leave
operation is used to delete someone from a group. Minimally the group
communications facilities will provide primitives to create, destroy,
join, leave, and send a message to the group.

Transport Mechanisms

12
Networking and Data Distribution

The actual mechanism used to transport messages to the simulators in

the group depends on the mechanisms provided by the underlying
network. In particular, group communication can be implemented by
the following mechanisms:

• Unicast. Separate point-to-point communications are used to send

messages to destinations in the group.

• Broadcast. If the underlying network provides an efficient broadcast

medium, the message can be broadcast to all simulators, and
destinations not in the group discard the message.

• Multicast. The network provides a mechanism to only deliver

messages to members of the multicast group. This is often
accomplished by constructing a spanning tree that controls the
generation and distribution of copies of the message among the
members of the group.

Data Distribution
Whatever communication facility is provided by the underlying
network, some strategy must be developed to efficiently distribute
state information among the simulators. The software in the distributed
simulation executive to control this distribution of information is
referred to as the data distribution (DD) system. The task of the DD
software is to provide efficient, convenient to use services to ensure
that each simulator receives all of the messages relevant to it, and
ideally, no others.

Interface to the Data Distribution System

Whenever a simulator performs some action that may be of interest to

other simulators, such as moving an entity to a new location, a
message is generated. Some means is required to specify which other
simulators should receive a copy of this message. Specifically, the
distributed simulation executive must provide mechanisms for the
simulators to describe both the information it is producing, and the
information it is interested in receiving. The set of newsgroup names
defines a name space, which is a common vocabulary used to describe
data and to express interests. Each user provides an interest expression
that specifies a subset of the name space, which is a list of

Modeling And Simulation 13

I Modeling and Simulation

newsgroups, that indicates what information the user is interested in

receiving. A description expression, again a subset of the name space,
is associated with each message that describes the contents of the
message.

The newsgroup analogy is useful to specify how information should be

disseminated in a DVE. There are three basic concepts:

• Name space. The name space is a set of values used to express

interests and to describe information. The name space is a set of tuples
(VI' V2 , ... , VN) where each Vi is a value of some basic type, or
another tuple. For example, a simulator modeling a radar might
indicate it is interested in receiving a message whenever the location
of any aircraft within one mile of the radar changes. The name space
could be defined as a tuple (VI' V2), where VI is an enumerated type
specifying the different types of vehicles in the DVE (for example,
truck, aircraft, and ship), and V2 is a tuple specifying the X and Y
coordinate positions of a vehicle.

• Interest expressions. An interest expression provides the language by

which the simulator specifies what information it is interested in
receiving. An interest expression defines some subset of the name
space. For example, the interest expression for all aircraft within 1
mile of location (Xo, Yo) is all tuples (aircraft, (X, Y)) such that (Xo -
X)2 +(Yo - Y)2 < 1.

• Description expressions. A description expression is associated with

each message. It specifies a subset of the name space that characterizes
the contents of the message.

Example: Data Distribution in the High Level Architecture

The HLA provides two mechanisms for controlling the distribution of

data:

1. Class-based data distribution.

2. Value-based data distribution via routing spaces.

Class-Based Data Distribution Recall that in the HLA the federation

must define a FOM that specifies the classes of objects of common
interest to the federation. The FOM specifies a hierarchy indicating
object classes and their interrelationships, and object attributes. For
example, a class may be defined called vehicle, with separate
subclasses called aircraft, tank, and truck. These class definitions are

14
Networking and Data Distribution

used for data distribution. Specifically, each federate invokes the

Subscribe Object Class Attributes service to indicate it is to receive
notification of updates to attributes of a specific class in the class
hierarchy tree.

Routing Spaces Routing spaces are an abstraction defined separately

from objects and attributes, solely for the purpose of data distribution.
A routing space is a multidimensional coordinate system. The name
space for a single N-dimensional routing space is a tuple (XI' X2 , .•.
,XN ) with Xmin :: Xi :: Xmax' where Xmin and Xmax are federation-
defined values.

Modeling And Simulation 15

Lecture 5 – Scilab Programming Language
Scilab has a built-in interpreted programming language so that a series of commands can
be automated. The programming language offers many features of a high level language, such as
looping (for, while), conditional execution (if-then-else, select) and functions. The
greatest advantage is that the statements can be any valid Scilab commands.

To loop over an index variable i from 1 to 10 and display its value each time, you can
try the following commands at the prompt:
-->for i=1:10
-->disp(i)
-->end

The for loop is closed by the corresponding end statement. Once the loop is closed,
the block of statements enclosed within the loop will be executed. The disp(i) command
displays the value of i.

Conditional execution is performed using the if-then-elseif-else construct. Try

the
following statements on the command line:
-->x=10;
-->if x<0 then disp('Negative')
-->elseif x==0 then disp('Zero')
-->else disp('Positive')
Positive
-->end

This will display the word Positive. You may also notice that the statement
disp('Positive') is executed even before the keyword end is typed.

A list of all the Scilab programming language primitives and commands can be displayed
by the command what(). The command produces the following list:
if else for while end select case quit
exit return help what who pause clear resume
then do apropos abort break elseif

You can learn about each command using the help command. Thus help while will
give complete information about while along with examples and a list of other commands that
are related to it. The greatest advantage is that you can test out every language feature
interactively within the Scilab environment before putting them into a separate file as a function.

Following operators are available in Scilab:

Symbol Operation Symbol Operation
[ ] Matrix definition ; Statement separator
( ) Extraction eg. m = a(k) ( ) Insertion eg. a(k) = m
' Transpose + Addition
– Subtraction * Multiplication
\ Left division / Right division
^ Exponent .* Element wise mult.
.\ Element wise left division ./ Element wise right division
.^ Element wise exponent

Following are the boolean operators available in Scilab:

Symbol Operation Symbol Operation
== Equal to ~= Not equal to
< Less than <= Less than or equal to
> Greater than >= Greater than or equal to
~ Negation
& Element wise AND | Element wise OR

The boolean constants %t and %T represent TRUE and %f and %F represent FALSE.
The following are examples for typical boolean operations:
-->a=rand(3,4)*10 Generate matrix a with 3 rows and 4 columns and containing
random numbers between 0 and 10.
-->a == 0 Creates matrix a with same size as matrix a, with elements either T (if the
element is equal to zero) or F (if the element is not zero).
-->a < 20 Creates matrix a with same size as matrix a, with elements either T (if
the element is less than 20) or F (if the element is greater than or equal to
20).
-->bool2s(a < 20) First creates a matrix of boolean values T or F depending on whether the
element in matrix a is less than 20 or greater than or equal to 20. Then
creates a matrix with numerical vales 1 or 0 corresponding to T or F,
respectively
-->find(a < 20) Creates a vector containing the indices of elements of matrix a which are
less than 20