A case study in simulating PCS networks using Time Warp.
There has been rapid growth in the demand for mobile communications over the past few years. This has led to intensive research and development efforts for complex PCS (personal communication service) networks. Capacity planning and performance modeling is necessary to maintain a high quality of service to the mobile subscriber while minimizing cost to the PCS provider. The need for flexible analysis tools and the high computational requirements of large PCS network simulations make it an excellent candidate for parallel simulation.Here, we describe our experiences in developing two PCS simulation models on a general purpose distributed simulation platform based on the Time Warp mechanism. These models utilize two widely used approaches to simulating PCS networks: (i) the  call-initiated and (ii) the portable-initiated models. We discuss design decisions that were made in mapping these models to the Time Warp executive, and characterize the workloads resulting from these models in terms of factors such as communication locality and computation granularity. We then present performance measurements for their execution on a network of workstations. These measurements indicate that the call-initiated model generally outperforms the portable initiated model, but is not able to capture phenomenon such as the busy line effect. Moreover, these studies indicate that the high locality in large-scale PCS network simulations make them well-suited for execution on general purpose parallel and distributed simulation platforms.
Introduction
A personal communication service (PCS) network [3] provides
wireless communication services for nomadic users. The
service area of a PCS network is populated with a set of geographically
distributed transmitters/receivers called radio ports.
A set of radio channels are assigned to each radio port, and the
users in the coverage area (or cell for the radio port) can send
and receive phone calls by using these radio channels. When
a user moves from one cell to another during a phone call a
hand-off is said to occur. In this case the PCS network attempts
to allocate a radio channel in the new cell to allow the phone call
connection to continue. If all channels in the new cell are busy,
then the phone call is forced to terminate. It is important to
engineer the system so that the likelihood of force termination
is very low (e.g., less than 1%).
Traditionally, analytic models have been used to understand
the performance characteristics of these types of networks.
However, analytic models are often not sufficiently general or
flexible because they must make simplifying assumptions about
the system parameters to make the analysis tractable. For ex-
ample, the blocking probability of a fixed channel assignment
PCS network can be modeled analytically using the Erlang-B
system [11, 20]. However, the Erlang-B system is only appropriate
for predicting the blocking probability p b when the

Figure

1: Estimating the problem size3.63.84.0
e r
500 1000 1500 2000
(a) The impact of network size
e r c e
(b) The impact of network size
r c
simulated sec
(c) The impact of the termination time
number of portables is much larger than the number of available
channels, resulting in a p b that is much greater than 1%. Further,
an analytic model for a fixed channel assignment PCS network
(a network where the radio channels used in each cell are static
and the number of channels per cell is constant) cannot be easily
modified to study other aspects of a PCS network such as the
effect of call hand-off [17] and dynamic channel assignment 1
[11, 20] on call blocking statistics. Now because discrete event
simulation provides a general, flexible framework for evaluating
system models, large high-capacity personal communication
services (PCS) networks models are an excellent candidate for
simulation.
In a PCS simulation, the network is usually represented by
hexagonal or square cells. Ideally, PCS simulation experiments
should model large networks containing thousands of
cells. However, due to limited computing resources, most studies
only examine small-scale networks containing fewer than 50
cells [11, 20], and output statistics of the boundary cells are usually
discarded to avoid the boundary effect. Lin and Mak [12]
showed that this approach may lead to biased output statistics,
and suggest using a large network with a wrap-around topology
to achieve reliable simulation results.
To illustrate the impact of network size, consider the following
portable initiated simulation model using a fixed channel
assignment scheme. A portable (or mobile phone) resides at a
cell for a period of time, then moves to another cell. When a
phone call arrives, a radio channel is used to connect the cor-
assignment strategies increase channel availability by "intelligently"
reallocating channels to cells based on the traffic load within the cell, traffic mobility, and
co-channel interference.
responding portable. If all channels are busy, then the call is
blocked (dropped). The output measure is the blocking probability
b , the probability that a phone call is dropped.

Figures

1 (a) and (b) illustrate the impact of network size.
The experiments assume that the expected number of portables
in a cell is N . A portable resides in a cell for a period of time t
(in this paper, t has an exponential distribution with mean 1
, as
proposed in [19]), then moves to one of the four neighboring
cells with equal probability. The call arrivals to a portable form
a Poisson process with the arrival rate -. The call holding times
have an exponential distribution with mean 1
. The simulation
covers seconds of simulated time, the mean call
holding time is 1
Wrapping effect occurs when the statistical results produced
from the simulation are in error because the cell boundaries
"wrap" back on themselves. This wrapping of the cells boundaries
allows a portable at an edge to suddenly move and reappear
on the other side of the grid of cells. Because of this unnatural
portable movement, error is introduced in the call statistics.
This error can be reduced by using a larger network work of
cells. The figures suggest that the network size S ? 256 cells
are required to avoid the wrapping effect.
Moreover, Figure 1 (c) suggests that T ?
lated) seconds are required to obtain the steady state blocking
probability. For S ? 256 and T ? 5 \Theta 10 4 seconds, the number
of events executed is on the order of 10 7 for a simple cell level
simulation. For larger, more complex PCS simulations, such
as Bellcore's Network Operations Plan (NOP) Architecture for
PCS which includes integration with switching elements from
the Plain Old Telephone Service (POTS) network, we estimate
the number of events executed for a single run to be between
depending on the detail of the simulation model.
We have observed between 10 4 and 10 5 events per second in
efficient discrete event simulation packages (commercial packages
are often much slower). Accordingly, a simulation of this
magnitude will require many hours of CPU time. Further, such
large simulation programs may require more memory than is
available on a single machine.
Because of the large computational requirements and the
need for flexibility, PCS network models are a good candidate
for a parallel simulation [8]. The impact of varying PCS simulation
parameters on the Time Warp mechanism is investigated
in [2]. This paper extends that work and examines our experiences
in executing PCS simulation models on a distributed
Time Warp system. In particular, we will discuss our approach
to mapping the PCS models to the distributed simulator, characteristics
of the workload model that impact the efficiency of the
distributed simulator, and the performance of the system that
was developed.
Most PCS models fall into two types of models: call-initiated
[9, 17] or portable-initiate [19, 12]. In this study, we will
consider both types of models. These models are described in
section 2. Section 3 describes design decisions that were made
to map the models to a Time Warp based distributed simulation
environment. Section 4 characterizes the workload for bothPCS
models and discusses aspects of the workload that impact the
distributed simulator. Section 5 describes the implementation
details of our distributed Time Warp environment and presents
performance data collected from executing the simulations on a
collection of workstations. Section 6 concludes by reflecting on
what was learned from this study about (i) the suitability of PCS
simulations for parallel simulation, and (ii) what is important
in the design and implementation of these models to enable
efficient execution on a Time Warp system.
2 Description of the PCS Models
In this section we describe the call-initiated and portable-
initiated models. The primary difference between these two
models is that the call-initiated model only simulates the behavior
of a portable during phone conversations. The portable-
initiated model tracks the movement of portables even if they

Figure

2: Call-Initiated Model: flowchart for call processing
within a single cell. A "Call Arrival" denotes a new call arriving
at this cell or a call hand-off to this cell.
Assign Channel
Call Complete?
On Going Call
Release Channel
Move
Move To
Neighboring Cell
Release Channel
Call Arrival
Channel
Available?
Call Blocked
are not in conversations. The implication of these differences
will be discussed in detail below.
The call-initiated model is organized around two object
types: Cell and Call. The Cell represents the area covered by a
cellular receiver/transmitter that has a fixed number of channels
allocated to it. The Call represents an active phone conversation.
As depicted in figure 2, when a Call arrives at a Cell, channel
availability is determined. If no channel is available then that
Call is counted as being blocked. If a channel is available, it is
assigned to that Call. When the Call completes, the occupied
channel is released. If the portable to whom the Call is connected
is leaving the Cell's area 2 , then the allocated channel is
released and the Call is handed-off to the destination Cell. The
hand-off to the destination Cell is realized as a call arrival event
at that neighboring Cell. If a channel at the neighboring Cell is
not available, the Call is counted as a hand-off block, which is
also known as a forced termination. If a channel is available,
the Call reconnects and continues without interruption.
The portable-initiated model is also organized around two
object types: Cell and Portable. As in the previous model,
the Cell represents a cellular receiver/transmitter that has some
fixed number of channels allocated to it. The Portable represents
a mobile phone unit that resides within the Cell for a period
of time and then moves to one of the four neighboring Cells.
As shown in figure 3, when a new call arrives at a Cell, the
Cell first determines the status of the destination Portable. If
the destination Portable is busy with another call, this call is
counted as a busy line. A busy line occurs when a Portable
is currently connected in a phone call and another phone call
arrives for that portable. The call-initiated model has no notion
of a busy line, which is one of the fundamental differences
between the two models and has an important effect on the call
statistics. If the Portable is not busy, the Cell determines channel
availability. If all channels are busy, the call is counted as a call
block. If a channel is available, it is allocated for the destination
use and the call is allowed to connect. While a call is
in progress, the Portable tracks its location. When the Portable
determines it is moving out of the current Cell's signal range, it
drops the currently used channel, and requests a channel from
the neighbor Cell into which it is moving. If all channels from
the neighboring destination Cell are busy, this call counts as a
We assume Portable movement is exponentially distributed.

Figure

3: Portable-Initiated Model: flowchart for call processing
within a single cell. A' ``Portable Arrival'' denotes a portable
entering a cell's area.
Assign Channel
Call Arrived?
Call Complete?
On Going Call
Release Channel
Channel
Available?
Busy?
Call Blocked
Busy Line
Move
Move
Move To
Neighboring Cell
Release Channel
Portable Arrival
Handoff?
hand-off block. If a channel is available, the call reconnects and
continues without interruption.
b is computed by the total number of blocked calls that are
not busy-lines divided by the total number of call attempts. Because
should reflect the call blocking probability due to net-work
congestion, busy-lines are subtracted from the total number
of blocked calls prior to computing p b . Table 1 shows that
the blocking probability p b , is significantly lower in this model
than the blocking probability in the call-initiated model. The
reason for this difference is busy lines are explicitly simulated
in the portable-initiated model, which reduce the number of
blocked calls in the simulation. By simulating busy-lines, calls
that may have blocked due to insufficient network resources
are being counted as busy-lines, which reduces the number of
call blocks in computing p b . This reduction in the number of
blocked calls is called the busy-line effect. Accordingly, the
portable-initiated model will have fewer blocked calls than the
call-initiated model, because of busy-lines, for the same number
of call attempts.
The difference in p b for the two models will decrease as the
number of portables per cell grows for some fixed number of
channels per cell. As the number of portables per cell becomes
larger, the number of call attempts grows, resulting in larger demands
placed on network resources. As network demand rises,
the p b will rise and the impact of busy-lines on p b will decrease.
Accordingly, the portable-initiated model should be used when
the number of portables per cell is not large because the busy line
effect has a significant impact on p b . For a large number portables
per cell, the call-initiated model is more appropriate. It will
be seen later that the call-initiated model is more efficient and
can be simulated in less time than the portable-initiated model.
The computational requirements for both models are discussed
below.
Implementation
This section focuses on howwe mapped the simulation model
to the distributed simulator, emphasizing design and implementation
decisions and rationales for these decisions that were
made along the way.
3.1 Distributed Simulators
The distributed simulator consists of a collection of logical
processes or LPs, each modeling a distinct component of the
system being modeled. LPs communicate by exchanging timestamped
event messages. Like most existing distributed simulation
protocols, we assume different LPs may not share state
variables that are modified during the simulation. The synchronization
mechanism must ensure that each LP processes events
in timestamp order in order to prevent events in the simulated
future from affecting those in the past. The synchronization
issue has been widely studied (e.g., see [4, 6, 13, 16]).
The Time Warp mechanism uses a detection-and-recovery
protocol to synchronize the computation. For a more detailed
discussion of the Time Warp mechanism we refer the reader to
[4, 10].
3.2 Implementing the PCS Models
A natural way to map both PCS models to a general purpose,
sequential simulator would be to realize each Call/Portable as
a simulation process and Cells as state variables. In the call-
initiated model, a call arrival at a cell could be simulated by
creating a Call LP, which would persist until the call completes
or is forced to terminate during a hand-off to another cell. In
the portable-initiated model, a call arrival at a cell could be
simulated by scheduling a "call arrival" event for a particular
Portable LP. In this model, each Portable LP would persist for
the duration of the simulation.
However, this approach poses a problem in Time Warp exe-
cution. In the call-initiated model, when a call is handed-off to
another Cell, a channel at the destination Cell must be available.
This implies that the Call LP must have access to a Cell's state
information, in particular that Cell's channel availability. The
Cell state information must therefore be shared among several
Call LPs. But, such sharing state information is not allowed in
Time Warp. A widely used solution to this problem is to implement
each Cell as an LP. Accesses to the Cell LP's state information
can be realized by exchanging timestamped messages
between LPs, that carry the value(s) of requested state vari-
able(s). However, in these PCS models, whenever a call arrives,
the Portable/Call LP would need to exchange timestamped messages
with the Cell LP to determine channel availability. The
overhead associated with these messages becomes large, particularly
when a Call or Portable has migrated to a Cell that is
on a different processor. The cost is prohibitive in a distributed
environment where communications are very expensive.
In order to avoid sharing state between LPs, we realized Cells
as LPs but Calls/Portables as timestamped messages that travel
among the Cell LPs. Mapping Cells to LPs is a standard technique
used in other applications [18]. Mapping Call and Portables
to timestamped messages is a reasonable approach from a
modeling perspective when viewed from the model flowcharts

Figures

2 and 3). In both models when a call (portable) arrives,
channel availability must be determined. Since the message denoting
the call arrival is sent to the Cell LP in which the call
will be processed, the channel availability information is accessible
by the Call/Portable contained within the call arrival
message. Moreover, in the portable-initiated model, Portable
availability (is the Portable engaged in a phone call?) must
also be determined by the Cell. Since the call arrival message
carries the Portable's state information, Portable availability is
known to the Cell. Using this mapping, a hand-off in both PCS
models is realized as a message sent between two Cell LPs.
The destination Cell LP views the hand-off as a call/portable
arrival. Accordingly, during all phases of call processing for
both PCS models, this mapping guarantees that the necessary
state information is available without the additional overhead of
exchanging timestamped messages.
A drawback with this approach is there are fewer LPs, and
thus less parallelism in the simulator. In the present context, this
is not a serious handicap because, as noted earlier, the required
simulations will contain hundreds to thousands of Cells. Thus,
there are a sufficient number of LPs for the computing platforms
that were available for this study. Further, the amount of parallelism
within a cell is limited, to a large extent, by dependencies
arising from their accesses to the Cell LP's state information.

Table

1: Compare P b for call-initiated and portable-initiated models across varied PCS parameters.
PCS Parameters call-initiated p b portable-initiated p b
mins 33.08% 17.52%
In both PCS models, the behavior of a Call/Portable is realized
by 4 different types of events: (i) NextCall, which denotes a
call arrival, (ii) CompletionCall,which denotes a completed call
at a Cell (i.e. the call was not blocked), (iii) MoveOut, which
denotes a call moving out of the current Cell, (iv) MoveIn, which
denotes the arrival of a hand-off call at a Cell.
To initialize the call-initiated simulation, each Cell sends
itself an initial event that invokes the StartUp method (event
procedure). Upon processing the StartUp method, each Cell
will initialize and schedule the arrival of the first Call to that
Cell by scheduling an event into the future that will invoke the
NextCall method. Each Call contains two independent timestamp
fields: call completion, and move timestamps. The call
completion timestamp represents the time at which the phone
call will complete. The move timestamp represents the time at
which the Call will leave the current Cell and reside at one of the
neighboring Cells. The minimum of these two timestamp fields
determines the event type and Cell destination of the Call. Call
arrivals are generated by scheduling the next Call arrival at the
end of processing the NextCall method. Accordingly, because
each Cell LP determines its own Call arrivals and sends messages
to itself, this simulation is self-initiating. This impacts the
performance of the distributed simulation, as will be discussed
later. For a detailed analysis of the performance bounds for
self-initiating simulations, we refer the reader to [15].
The portable-initiated simulation is similar to the call-
initiated Model. During initialization, each Cell sends itself
an initial event that invokes the StartUp method. Upon processing
the StartUp method, each Cell will initialize and schedule
some fixed number of messages, each containing a Portable.
Each Portable contains three independent timestamp fields: call
completion, next call and move timestamps. In the call-initiated
model, Calls only contained two independent timestamps: call
completion and move timestamps. The call completion and
move timestamps have the same meaning in both models.
However, the additional next call timestamp contained in the
portable-initiated simulation represents the time when the next
call will arrive. The primary purpose of the next call timestamp
is to determine when busy lines occur. The minimum of these
three timestamp fields determines the type of event that will be
scheduled by a Cell. Portable arrivals are generated by determining
when a Portable will receive its next call arrival based
on the NextCall timestamp. Accordingly, like the call-initiated
model, the portable-initiated model is also self-initiating.
In both models, Call/Portable interarrival times,
Call/Portable completion times and Call/Portable move times
are exponentially distributed, though one could trivially substitute
other distributions into the simulation program.
4 Workload Characterization
In this section we characterize the workload for each PCS
model. First we quantify the workload in terms of the PCS
model application parameters, and then discuss characteristics
that are relevant to the performance of the distributed simulator.
4.1 Model Parameters
Both PCS models have the following application parame-
ters: (i) Call/Portable mobility, (ii) call interarrival time, (iii)
number of Cells, (iv) number of Calls/Portables. Each of these
parameters is discussed below.
Mobility of Calls/Portables determines how frequently
Calls/Portables move to a different Cell. This, in turn, determines
how frequently LPs communicate. Recall from the
previous discussion that the only time Cell LPs communicate
is in the handoff of a Portable/Call. As LP's communicate
more frequently, the number of messages sent between processors
increases, which increases distributed simulator overheads,
leading to slower execution times. Section 5 will present performance
data that supports this hypothesis.
The call interarrival time determines the amount of work
available to the simulator over a given period of simulated time.
For modest size PCS networks, the call interarrival time has
a significant impact on the "rate" the simulation progresses
through simulated time, which will determine how likely a simulation
will roll back for a fixed amount of lookahead. The
faster the rate of progress, the more likely the simulation will
roll back. Lookahead is defined as the amount of simulated time
an LP can "see" into the future and will be discussed in more
detail later. For large PCS networks, the workload is sufficient
that a change in call interarrival times will not impact the sim-
ulation's rate of progress to effect the likelihood that rollbacks
occur. Section 5 will present performance data that supports
this hypothesis.
The number of Cells determines the number of LP's in the
Time Warp simulation. 1024 LPs were used for all experiments
presented in this study. Because of the large number of LPs
and self-initiating nature of the simulation implementation, the
amount of available parallelism should be very high. Also, the
number of Cell's determines the amount of memory needed for
state saving.
Next, the number of Portables in the portable-initiatedmodel
determines the number of pending events. For experiments
presented in this study, N , the number of Portables per Cell, is
varied among Accordingly, the total number of
pending events in the simulation ranges from 25; 000 to 75; 000.
By contrast, the number of Calls in the call-initiated model
does not determine the number of pending event. To model N
Portables per Cell in the call-initiated model, the call interarrival
time is the call interarrival time of the portable-initiated model
divided by the number of Portables per Cell. Also, in the call-
initiated model, a call only persists as long as the conversation
lasts or until it is forced to terminate. Accordingly, the number
of pending events is bounded by the number of channels in
the simulation. For all experiments presented in this study, the
number of channels per Cell was fixed at 10, making the number
of pending events in the simulation on the order of 10; 000 for
any number of Portables.
Additionally, the number of Calls/Portables per Cell for both
PCS models impacts the rate at which simulated time advances.
Increasing the number of Portables in the portable-initiated
simulation results in increasing the amount of work an LP must
perform. Similarly, increasing the number of Calls in the call-
initiated simulation increases the rate at which calls arrive with
respect to simulated time which increases the amount of work
an LP must perform.
4.2 Workload Properties
In general, the following properties can significantly impact
the performance of Time Warp based, distributed simulators: (i)
lookahead of LPs, (ii) event granularity, (iii) state saving over-
heads, (iv) message data size, (v) locality of communications,
and (vi) homogeneity of the model being simulated.
As previously stated, lookahead determines how "far" into
the simulated future an LP can predict future events. In [5] it was
shown that lookahead can significantly affect the performance of
Time Warp simulators with small message densities. However,
since both PCS models contain very large message densities, the
impact of lookahead on system performance may not be as large.
Because timestamps for determining call interarrivals, call completions
and mobility are exponentially distributed, both model
implementations will have a lookahead of 0 in the worst case.
Lookahead can be improved by pre-computing portions of the
computation for future events [14]. For the PCS models discussed
in this study, it is possible to pre-compute call completion
times, which should result in an increase in the average lookahead
of the simulation. However, this improvement reduces the
extensibility of the simulation implementation to incorporate
new features added to the simulation model. For example, the
Bellcore's Generic Criteria for 0.1 Wireless Access Communications
System (WACS) allows an active call to be interrupted
for emergency purposes, such as the processing of a 911 call
when no channel is available. This feature could not be easily
added to the "improved" simulation implementation without
advanced knowledge of when a call would be interrupted. For
this reason, techniques for improving lookahead were not exploited
in this implementation. Thus, the performance that was
obtained is conservative in this regard.
Event granularity is the average amount of real time to compute
an event. If the event granularity is small then incorrect
computation tends to propagate more rapidly relative to the
speed of the correction computation (anti-messages). Table 2
shows the event granularity, excluding message send times, for
each event type for the different PCS models. These timings
where obtained by runningthe simulation on a single Sun Sparc-
workstation. The timing information was captured by the Unix
gettimeofdaysystem call, which has a resolutionof
on this computing platform. A significant portion of this
granularity is overhead introduced by C++. We are currently
examing ways to reduce this overhead.
Because the Cell LPs of both PCS models contain less than
256 bytes of state, the state saving overhead is modest.
Scheduling an event requires the message data to be copied
into a new message buffer. Accordingly, the amount of data
contained in a message affects the overhead of scheduling events
as well as the amount of memory need to efficiently execute the
simulation. Portables and Calls contain less than 256 bytes of
data, so the overhead in scheduling events is low. However,
the number of pending events in the system may be as large as
necessitating a minimum of almost 20 MB memory for
LP state and event data.
The locality of each PCS simulation is shown in Table 3. We
see that most event types in the call-initiated model schedule
events to self while the portable-initiated model can schedule
an event to either self or a neighbor LP (north, south, east, and
west). This difference is due to a Portable persisting for the
life of the simulation in the portable-initiate model, even during
periods of inactivity (i.e. not connected to an ongoing call),
while a Call in the call-initiated model is terminated if the Call
completes or is blocked.
The homogeneity of a model determines how easily the simulation
objects (LP's, number of pending events) are mapped
onto the processors and how evenly distributed the workload is
across the processors. For both PCS models, since all the Cells
are identical (same mean and distribution for call interarrivals
call completions, mobility times and same number of Portables
per Cell), the workload will be well balanced across all proces-
Figure

4: Call-Initiated: parallel execution time (in seconds)
versus number of portables per cell (N), mobility and call inter-arrival
times. Call holding times are exponentially distributed
with a 3 minute mean. Experiments performed using 8 proces-
e
Call interarrival
time (minutes)
(a)
e
Call interarrival
time (minutes)
e
Call interarrival
time (minutes)
(c)
sors, thus eliminating the need for dynamic load management
mechanisms.
Performance Results
In this section we discuss our distributed implementation of
the Time Warp mechanism and then present performance data
for the two PCS simulation models.
5.1 Implementation of Distributed Simulator
A version of Time Warp has been developed that executes on
a collection of DEC 5000 workstations, Sun Sparc workstations,
or a mixture of these machines. All performance results presented
here were performed on DEC machines interconnected
by an Ethernet. The Time Warp system is written in C++. A
principal objective of this implementation is to enable efficient
simulation of thousands of "light weight" LPs (i.e., processes
that contain a small amount of state and perform little computation
in each event) in an object-oriented environment on
networked, heterogeneous workstations. Here we will describe
some of the user and kernel level features of the Time Warp
system.
LPs are implemented as C++ objects, and are referred to
as "entities." Each LP (entity) consists of a state vector that
stores the LP's private data, and a set of methods that define
the allowable operations that can be performed on that data.
Each method corresponds to a type of event. For instance, in
the PCS simulations, an entity for a cell will include the methods
described earlier in section 3.2 (NextCall, CompletionCall,
MoveOut, MoveIn).
It is anticipated that most simulations will contain far more
entities than processors, so each processor will typically contain
hundreds or thousands of entities (LPs). A priority queue data
structure called the calendar queue [1] is used in each processor
to select the next entity to execute. The processor's scheduler
always selects the entity containing the smallest timestamped
event as the next one for execution. Each entity includes a
linear list to hold the unprocessed events (method invocations)
scheduled for that entity.
To avoid unnecessary system overheads from malloc system
calls and memory fragmentation, the Time Warp kernel allocates
a single contiguous block of memory from which events
and other internal data structures are allocated.
Communications between processors is implemented using
PVM 3.2 (Parallel Virtual Machine), a message passing system
for heterogeneous collections of networked computers [7].
In addition to PVM's default routing of messages, PVM will
route messages directly between application processes by setting
up a TCP/IP connection between each enrolled application,
thus bypassing the PVM daemons at both the sending and receiving
host. In this mode, the sending process is not blocking,
making PVM's direct routing mode an asynchronous communications
protocol. When routing messages in direct mode, the
total time to deliver a message is in the range of 1.4 to 2.0 mil-
liseconds. When executing our distributed Time Warp kernel,
PVM is configured to directly route messages.

Table

2: Comparison of event types for call-initiated model and portable-initiated model based on event granularity
Event Type call-initiated event grain portable-initiated event grain
NextCall 258 usec 125 usec
CompletionCall 38 usec 93 usec
MoveCallIn 196 usec 107 usec
MoveCallOut 195 usec 324 usec

Table

3: Comparison of event types for call-initiated model and portable-initiated model based on number of messages sent and
locality of destination.
Event Type call-init # msgs portable-init # msgs call-init dest portable-init dest
near neighbor
CompletionCall near neighbor
MoveCallIn 1 1 self self or near neighbor
neighbor near neighbor

Figure

5: parallel execution time (in sec-
versus number of portables per cell (N), mobility and
call interarrival times. Call holding times are exponentially distributed
with a 3 minute mean. Experiments performed using 8
processors.
e
Call interarrival
time (minutes)
(a)
e
Call interarrival
time (minutes)
e
Call interarrival
time (minutes)
(c)
5.2 Performance Data
To determine the effect of the PCS workload characteristics
on Time Warp performance, we measured the execution times,
efficiency of the simulation 3 , average rollback distance and
percentage of remote communications for both PCS models. For
each metric, the number of portables per cell, mobility, and call
interarrival times were varied. The completion time for a phone
call was exponentially distributed with mean 3.0. The number
of channels per cell was fixed at 10. All experiments were
conducted on 8 DEC 5000 workstations, with each workstation
containing 128 cells, for a total of 1024 cells. All experiments
ran for 2:5 \Theta 10 4 simulated seconds. Each data point represents
the average of 6 runs.
In

Figures

4 and 5, the execution time is shown for each
of the PCS parameter values (number of portables, mobility,
and call interarrival times). In every case the call-initiated
simulation outperformed the corresponding portable-initiated
simulation. This can be attributed to the call-initiated model's
sending fewer remote messages, which is due to not simulating
the inactive periods of portables. Remote communications is
discussed later in this section.
Combined with fewer remote messages, there were fewer
events processed in the call-initiated simulation for all cases
except where the mean call interarrival time was low (6 minutes).
The reason more events are being processed in this case by the
call-initiated simulation is because calls that would be counted
as busy lines in the portable-initiated simulation, due to the
3 Efficiency is defined as the percentage of the simulation computationthat is committed.

Figure

Call-Initiated: efficiency of simulationversus number
of portables per cell (N), mobility and call interarrival times.
Call holding times are exponentially distributed with a 3 minute
mean. Experiments performed using 8 processors. ffl : Mobility
Mobility
c
e
Call interarrival
time (minutes)
(a)
c
e
Call interarrival
time (minutes)
c
e
Call interarrival
time (minutes)
(c)
high arrival rate of calls, are allowed to connect in call-initiated
simulation. However, when the call interarrival time is longer,
the movement of call-less portables in the portable-initiated
simulation causes the processing of more events than in the
call-initiated simulation.
The large size of the simulation models precluded reliable
measurement of sequential execution times. Memory management
overheads artificially inflated the execution time, causing
super-linear speedups to be obtained. However, based on execution
of smaller sized models, we estimate speedups range
between 4 and 8 for the distributed simulator.
Despite significant differences in execution times, the efficiencies
for both PCS simulations, as shown by Figures 6 and 7,
are over 95% for all PCS parameters (number of portables per
cell, call interarrival times, and mobility). These high efficiencies
are attributed to the size of the simulation workload relative
to the number of processors in both PCS implementations. Because
interprocessor communications are relatively infrequent,
the frequency of rollbacks is diminished.

Figures

8 and 9 show the average rollback distances for the
call-initiated and portable-initiated simulations. We see that
both simulations experienced long rollbacks. The call-initiated
simulationhad the shortest of the two simulations with rollbacks
distances ranging from 2:6 to 6:5. In the portable-initiated sim-
ulation, rollback distances ranged from 3:5 to 7:8. These results
are attributed to the self-initiating nature of both simulations.
Because, LPs schedule many events to themselves, neighboring
LPs become "unsynchronized" with respect to simulated time,

Figure

7: Portable-Initiated: efficiency of simulation versus
number of portables per cell (N), mobility and call interarrival
times. Call holding times are exponentially distributed with a 3
minute mean. Experiments performed using 8 processors. ffl :
Mobility
c
e
Call interarrival
time (minutes)
(a)
c
e
Call interarrival
time (minutes)
c
e
Call interarrival
time (minutes)
(c)

Figure

8: Call-Initiated: average rollback distance measured
in events per rollback versus number of portables per cell (N),
mobility and call interarrival times. Call holding times are
exponentially distributed with a 3 minute mean. Experiments
performed using 8 processors.
l
l
b a c
Call interarrival
time (minutes)
(a)
. ffl
l
l
b a c
Call interarrival
time (minutes)
l
l
b a c
Call interarrival
time (minutes)
(c)
leading to longer rollbacks when LPs exchange messages. How-
ever, because the efficiency of both simulations is very high, the
number of rollbacks is extremely low.
The "spikes" in Figures 8(a),(b),(c) and 9(a) are attributed
to a shift in rollback behavior. When increasing the mean call
interarrival time from 6 minutes to 10 minutes, the number
of secondary rollbacks increases because the workload has de-
creased, allowing the LPs to become more "unsynchronized".
We believe these rollbacks tend to be very long and perturb the
average. However, when increasing the call interarrival time
mean from 10 minutes to 30 minutes, we believe the frequency
of secondary rollbacks increase again, but become shorter as a
result of being more frequent, which reduces the average roll-back
distance.
In

Figures

and 11, the percentage of committed events that
were sent to LPs on different processors is shown. We see that
the call-initiated simulation has less than 1% remote commu-
nications, while the portable-initiated model ranges from 0:6%
to 5:0% remote communications, depending on the mobility.
The cause of these differences in remote communications lies
with the "life time" of Calls in the call-initiated simulation and
Portables in the portable-initiated simulation. Recall, in the
call-initiated implementation, that when a Call completes or is
blocked that Call ceases to exist. However, in the portable-
initiated simulation, Portables persist for the duration of the
simulation and move between Cells even when not processing
a phone call, resulting in more remote messages sent between
LPs. Because a higher percentage of messages are sent between
LPs residing on different workstations combined with
the high cost of remote communications, the communications
overhead in the portable-initiated simulation are much larger

Figure

9: average rollback distance measured
in events per rollback versus number of portables per cell
(N), mobility and call interarrival times. Call holding times are
exponentially distributed with a 3 minute mean. Experiments
performed using 8 processors.
l
l
b a c
Call interarrival
time (minutes)
(a)
l
l
b a c
Call interarrival
time (minutes)
l
l
b a c
Call interarrival
time (minutes)
(c)

Figure

10: Call-Initiated: % remote communications versus
number of portables per cell (N), mobility and call interarrival
times. Call holding times are exponentially distributed with a 3
minute mean. Experiments performed using 8 processors. ffl :
Mobility
R e
Call interarrival
time (minutes)
(a)
R e
Call interarrival
time (minutes)
R e
e
Call interarrival
time (minutes)
(c)
than call-initiated simulation, which underscores the execution
time results presented in Figures 4 and 5.
6 Conclusions
In this paper we characterize workloads for call-initiated and
portable-initiated PCS models in terms of suitability for Time
Warp execution. Experiments were completed to determine how
the workload characteristics affect Time Warp execution on a
collection of networked workstations. From these experiments,
we conclude:
ffl An important aspect of designing and implementing these
models (and any simulation model in general) is developing
a suitable mapping to Time Warp's execution
paradigm, such as eliminating the need for sharing state
among LPs and placing model objects to maximize the locality
of communications (i.e., implementing simulations
to be self-initiating) as was done in the implementation
of the PCS models.
ffl It was shown that, despite a poor lookahead, both PCS
simulations exhibited over 95% efficiencies for all PCS
parameters. Accordingly, lookahead does not seem to
play as significant a role in determining performance for
these large workload simulations as it does for smaller
models.
Efficient execution of small granularity, Time Warp simulations
is possible on distributed environments. This
suggests that the aggregate workload of the simulation
model and not the event granularity should be used when
determining suitability for Time Warp execution.

Figure

communications versus
number of portables per cell (N), mobility and call inter-arrival
times. Call holding times are exponentially distributed
with a 3 minute mean. Experiments performed using 8 proces-
R e
Call interarrival
time (minutes)
(a)
R e
Call interarrival
time (minutes)
R e
e
Call interarrival
time (minutes)
(c)
ffl Under modest remote communications loads, large message
delivery times for asynchronous communications
protocols do not appear to have a significant impact on
Time Warp efficiencies for large workloads.



--R

Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem.
Distributed Simulation of Large-Scale PCS Networks
Personal Communications - A Viewpoint
Parallel discrete event simulation.
Performance of Time Warp under synthetic workloads.
State of the art in parallel simulation.
Pvm 3 user's guide and reference man- ual
Efficient Massively Parallel Simulation of Dynamic Channel Assignment Schemes for Wireless Communications.
Performance issues and algorithms for dynamic channel assignment.
Virtual time.
Ordered Dynamic Channel Assignment Scheme with Reassignment in Highway Microcells.
On Simulating a Large-Scale Personal Communications Services Network

Parallel discrete-event simulation of FCFS stochastic queueing networks
Performance bounds on parallel self- initiating discrete-event simulations
Distributed simulation of discrete event systems.
A Measurement Based Prioritization Scheme for Handovers in Cellular and Micro-cellular Networks

Packet Reservation Multiple Access in a Metropolitan Microcellular Radio Environment.

--TR
Virtual time
Distributed discrete-event simulation
Parallel discrete-event simulation of FCFS stochastic queueing networks
Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem
Parallel discrete event simulation
Performance bounds on parallel self-initiating discrete-event simulations
State of the art in parallel simulation
Efficient massively parallel simulation of dynamic channel assignment schemes for wireless cellular communications
Distributed Simulation of Large-Scale PCS Networks

--CTR
L. Felipe Perrone , David M. Nicol, Rapid simulation of wireless systems, ACM SIGSIM Simulation Digest, v.28 n.1, p.170-177, July 1998
Christopher D. Carothers , Yi-Bing Lin , Richard M. Fujimoto, Simulating population dependent PCS network models using time warp, Proceedings of the 27th conference on Winter simulation, p.555-562, December 03-06, 1995, Arlington, Virginia, United States
Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, The effect of state-saving in optimistic simulation on a cache-coherent non-uniform memory access architecture, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.1624-1633, December 05-08, 1999, Phoenix, Arizona, United States
Jari Porras , Jouni Ikonen , Jarmo Harju, Applying a modified Chandy-Misra algorithm to the distributed simulation of a cellular network, ACM SIGSIM Simulation Digest, v.28 n.1, p.188-195, July 1998
David Nicol , Philip Heidelberger, On extending more parallelism to serial simulators, ACM SIGSIM Simulation Digest, v.26 n.1, p.202-205, July 1996
Michael Liljenstam , Rassul Ayani, Interference radius in PCS radio resource management simulations, Proceedings of the 30th conference on Winter simulation, p.1629-1640, December 13-16, 1998, Washington, D.C., United States
Francesco Quaglia , Vittorio Cortellessa, On the processor scheduling problem in time warp synchronization, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.3, p.143-175, July 2002
Voon-Yee Vee , Wen-Jing Hsu, Pal: a new fossil collector for time warp, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.
Francesco Quaglia , Andrea Santoro, Modeling and optimization of non-blocking checkpointing for optimistic simulation on myrinet clusters, Journal of Parallel and Distributed Computing, v.65 n.6, p.667-677, June 2005
Christopher D. Carothers , Brad Topol , Richard M. Fujimoto , John T. Stasko , Vaidy Sunderam, Visualizing parallel simulations in network computing environments: a case study, Proceedings of the 29th conference on Winter simulation, p.110-117, December 07-10, 1997, Atlanta, Georgia, United States
Peter Alleyne , Carl Tropper, On the parallel simulation of fixed channel allocation algorithms, Mobile Networks and Applications, v.5 n.3, p.209-218, Sept. 2000
Francesco Quaglia , Andrea Santoro, CCL v3.0: Multiprogrammed Semi-Asynchronous Checkpoints, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.21, June 10-13,
Andrea Santoro , Francesco Quaglia, Multiprogrammed non-blocking checkpoints in support of optimistic simulation on myrinet clusters, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.9, p.659-676, September, 2007
Christopher D. Carothers , Richard M. Fujimoto, Background execution of time warp programs, ACM SIGSIM Simulation Digest, v.26 n.1, p.12-19, July 1996
Christopher D. Carothers , Kaylan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.126-135, May 01-04, 1999, Atlanta, Georgia, United States
Francesco Quaglia , Roberto Beraldi, Space uncertain simulation events: some concepts and an application to optimistic synchronization, Proceedings of the eighteenth workshop on Parallel and distributed simulation, May 16-19, 2004, Kufstein, Austria
David Nicol , Philip Heidelberger, Parallel execution for serial simulators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.3, p.210-242, July 1996
Andrea Santoro , Francesco Quaglia, Communications and network: benefits from semi-asynchronous checkpointing for time warp simulations of a large state PCS model, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
Andrea Santoro , Francesco Quaglia, Transparent Optimistic Synchronization in HLA via a Time-Management Converter, Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.193-200, May 24-26, 2006
Robert Rnngren , Michael Liljenstam , Rassul Ayani , Johan Montagnat, Transparent incremental state saving in time warp parallel discrete event simulation, ACM SIGSIM Simulation Digest, v.26 n.1, p.70-77, July 1996
Diego Cucuzzo , Stefano D'Alessio , Francesco Quaglia , Paolo Romano, A Lightweight Heuristic-based Mechanism for Collecting Committed Consistent Global States in Optimistic Simulation, Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.227-234, October 22-26, 2007
Gilbert Chen , Boleslaw K. Szymanski, DSIM: scaling time warp to 1,033 processors, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Francesco Quaglia , Andrea Santoro, Modeling and optimization of non-blocking checkpointing for optimistic simulation on myrinet clusters, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999
Mineo Takai , Rajive Bagrodia , Addison Lee , Mario Gerla, Impact of channel models on simulation of large scale wireless networks, Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.7-14, August 20-20, 1999, Seattle, Washington, United States
Michael Liljenstam , Robert Rnngren , Rassul Ayani, Partitioning WCN models for parallel simulation of radio resource management, Wireless Networks, v.7 n.3, p.307-324, 05/01/2001
Ewa Deelman , Boleslaw K. Szymanski, Simulating spatially explicit problems on high performance architectures, Journal of Parallel and Distributed Computing, v.62 n.3, p.446-467, March 2002
Christopher D. Carothers , David Bauer , Shawn Pearce, ROSS: a high-performance, low memory, modular time warp system, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.53-60, May 28-31, 2000, Bologna, Italy
Mineo Takai , Rajive Bagrodia , Ken Tang , Mario Gerla, Efficient wireless network simulations with detailed propagation models, Wireless Networks, v.7 n.3, p.297-305, 05/01/2001
Roberto Beraldi , Libero Nigro, Distributed Simulation of Timed Petri Nets: A Modular Approach Using Actors and Time Warp, IEEE Concurrency, v.7 n.4, p.52-62, October 1999
Francesco Quaglia , Andrea Santoro, Nonblocking Checkpointing for Optimistic Parallel Simulation: Description and an Implementation, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.593-610, June
Brian Unger , Zhonge Xiao , John Cleary , Jya-Jang Tsai , Carey Williamson, Parallel shared-memory simulator performance for large ATM networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.4, p.358-391, Oct. 2000
Christopher D. Carothers , Richard M. Fujimoto, Efficient Execution of Time Warp Programs on Heterogeneous, NOW Platforms, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.299-317, March 2000
Jignesh Panchal , Owen Kelly , Jie Lai , Narayan Mandayam , Andrew T. Ogielski , Roy Yates, WiPPET, a virtual testbed for parallel simulations of wireless networks, ACM SIGSIM Simulation Digest, v.28 n.1, p.162-169, July 1998
Andrea Santoro , Francesco Quaglia, Transparent State Management for Optimistic Synchronization in the High Level Architecture, Simulation, v.82 n.1, p.5-20, January   2006
performance measurements;mobile communications;PCS networks;time warp;personal communication service;discrete event simulation;telecommunication computing;time warp simulation;distributed;parallel;flexible analysis tools;simulation platforms;mobile communication