[attachment=13261]
ABSTRACT
Some applications of simulation require that the model
state be advanced in simulation time faster than the
wall-clock time advances as the simulation executes.
This faster than real-time requirement is crucial, for
instance, when a simulation is used as part of a real-
time control system, working through the consequences
of contemplated control actions, in order to identify
feasible (or even optimal) decisions. This paper con-
siders the issue of faster than real-time simulation of
very large communication networks, and how this is ac-
complished using our implementation (in C++) of the
Scalable Simulation Framework (SSF). Our tool (called
iSSF) uses hierarchical levels of abstraction, and paral-
lelism, to achieve speedups of nearly four orders of
magnitude, enabling real-time execution rates on large
network models. We quantify the effects that choice
of hierarchical abstraction has on the simulation time
advance rate, and show empirically how changing the
abstraction mix affects the execution rate on a large
network example.
1 INTRODUCTION
Discrete-event simulation is a powerful computational
paradigm that allows a modeler to explore the potential
behavior of many kinds of discrete systems. Some ap-
plications of discrete-event simulation require that the
models be evaluated very quickly. For instance, when
simulation is used at the heart of an optimization so-
lution, the faster a model can be evaluated the richer
the solution space can be explored. Even more criti-
cal are applications where the discrete-event simulation
is used in a real-time control system. Not only must
the simulation advance the model state in simulation
time as fast as wallclock time (in the same units), more
often it must advance the model state at a rate signifi-
cantly faster than wallclock time, such as in cases where
the consequences of multiple different control decisions
must be computed and compared. An example of this is
given in (Ye, Kaur, Kalyanaraman, Kenneth, Vastola,
and Yadav 2002), where real-time simulation is used
to decide how select inputs for the OSPF (Moy 1998)
routing protocol.
Network defense is an area ripe for application of
faster than real-time simulation. It is easy to imagine a
control system that considers re-routing, partitioning,
and/or quarantining decisions as evidence of a cyber-
attack mounts. A simulation model can work through
cost/benefit/risks assessments of considered actions, us-
ing potentially sophisticated metrics to find an effective
response. However, faster than real-time simulation
of large network models requires aggressive techniques
both in modeling, and in execution strategy.
We will discuss simulator performance in terms of a
“baseline” packet-oriented simulation. Here the major-
ity of the workload involves ascribing delays to packets
as they move through a network, the delays being func-
tions of queuing at routers and processing through pro-
tocol stacks. Our unit of model activity then might be a
“packet-event”, which reflects either sending or receiv-
ing a packet (or both, if that occurs in the same com-
putation). A packet sent between two hosts, across 4
routers, would account for at least 6 packet events from
initial transmission to final receipt (one send-only event,
four receive-followed-by-send events, and one final re-
ceive event). In a strictly packet oriented simulation
a packet event is implemented within the simulation
kernel as one discrete event, involving a computational
action applied to the member of the event list with least
future time-stamp. We consequently use as a baseline
metric of simulator performance the rate at which the
simulation kernel executes “kernel-events”, on a large
network model. We recognize that this figure depends
on the problem size, insofar as the cost of a priority
heap access depends on the number of elements in the
heap; we likewise recognize that it depends on the com-
putational effort associated on average with each event
executed. Nevertheless the concept provides a useful
baseline that, within the context of a given simulation
Nicol, Liu, Liljenstam, and Yan
kernel, may be only slowly sensitive to problem size if
the priority list mechanism is optimized.
Traffic intensity is a good measure of model “size”—
the problem of simulating a 10K device network in
faster than real time under very light traffic load is
very different from that of simulating that same net-
work under heavy load. The aggregate packet-event
rate demanded of a workload mix, on a given topol-
ogy, describes the rate (in simulation time) at which
the network state is being modified. An implementa-
tion is faster than real time if those state modifications
are made at a wallclock rate that exceeds the aggre-
gate packet-event rate, using the same units of time.
For example, consider a model with 500 traffic flows,
where the offered load per flow is 10 packets/second,
and an average flow crosses three routers. This implies
an packet-event rate of 50 packets/sec/flow, for an ag-
gregate packet-event rate of 25,000 packet-events/sec.
This model can be run four times as fast as real-time
on a simulation kernel capable of executing 100K kernel-
events per second.
However, if we limit ourselves to pure packet-based
representation on a purely serial simulation kernel, our
ability to simulate networks faster than real-time is lim-
ited by the kernel-event rate of the serial simulation
kernel. In order to handle larger models it is neces-
sary to use more abstract model representations that
can affect the model state with less effort per inherent
packet-event than can a packet-oriented simulator, and
it may be necessary to also use parallel execution.
This paper describes how our implementation of the
SSF interface (called iSSF) can meet faster than real-
time challenges, using a combination of model abstrac-
tion and parallelism. We develop simple analytic mod-
els that help guide choices of abstraction to achieve
faster than real-time goals, and demonstrate its faster
than real-time capabilities on a large network model.