<<

. 76
( 87 .)



>>

enforces the causal order among events as follows. Events are greedily simulated in time-
stamp order until no event messages remain or until a message arrives in the “past” (a
398 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


straggler). Upon receiving a straggler, the process execution is interrupted, and a rollback
action takes place using anti-messages. Each message is given a sign; positive messages
indicate ordinary events, whereas negative messages indicate the need to retract any cor-
responding event that was previously processed. Similar messages that have different
signs are called anti-messages. If a negative message is received, the message and the cor-
responding anti-message are both annihilated. A rollback consists of the following three
phases:

1. Restoration. The latest state (with respect to simulation time) valid before the strag-
gler™s timestamp replaces the current state, and successive states are discarded from
the state queue.
2. Cancellation. The negative copies of messages that were produced at simulation
times successive to the straggler™s timestamp are sent to the proper processes, to
possibly activate rollbacks there.
3. Coasting-forward. The effective state that is valid at the straggler™s timestamp is
computed by starting from the restored state and by elaborating those messages
with a timestamp up to the stragglers; during this phase no message is produced.

Rollbacks are made possible by means of state checkpointing. The whole state of the
process is checkpointed into the state queue according to some discipline [49].
To minimize the storage overhead required to perform rollbacks, and to detect the ter-
mination of LPs, optimistic synchronization mechanism uses a local virtual time (LVT)
and a global virtual time (GVT). LVT represents the timestamp of the latest processed
event at an LP, whereas GVT is defined as the minimum of all the local virtual times of all
LPs, and of all the timestamps of messages in transit within the simulation model. GVT
indicates the minimum simulation time at which a causal violation may occur. GVT com-
putation is used to commit the safe portion of the simulation.
The optimistic scheme is preferred when a system to be simulated contains high pre-
dictability of events so that rollbacks are kept to a minimum. Thus, to improve the PCS
network simulation, we use a hybrid approach with both conservative and optimistic
schemes.


14.3.3 Wireless Network Simulators Based upon PDES
Several simulation techniques have been proposed in the literature [14, 38, 39, 43, 48, 65]
to speed up the execution of simulation of large-scale wireless networks. In this section,
we shall describe them, and discuss their main features.
ns-2 has long been considered to be a de facto standard simulator for wireless and
wired networking protocols research. The networking community has long been resistive
to rewrite the network simulator or use different platforms. Therefore, some researchers
have tried to parallelize the ns-2 using established parallel and distributed simulation tech-
niques, thereby providing a transparent parallel execution of ns-2. Riley and Fujimoto
have proposed a distributed version of the popular network simulator, ns-2, which they re-
fer to as parallel and distributed ns, or simply PDNS [50]. Their goal is to use the existing
network simulator and minimize the changes to it while allowing their parallel simulator
to take advantage of their proposed new version of ns-2. They revised the ns-2 syntax by
adding a set of directives that are directly related to the parallelization of the simulation.
399
14.3 SIMULATION TECHNIQUES


Their idea is based upon the federated simulation approach, in which separate subnet-
works of the simulated model are executed on different processors connected either via a
Myrinet network, or a standard Ethernet network using the TCP/IP protocol stack. A li-
brary, which they refer to as Georgia Tech RTI Kit [25], is used for synchronization pur-
poses. Conservative methods for synchronizing ns-2 processes have been implemented.
The RTI Kit is a software implementation of the Run-Time Infrastructure of the Depart-
ment of Defense™s High-Level Architecture (HLA) for large-scale distributed simulations
[19]. Much of the improvement obtained in their design was obtained from parallelization
of the setup of the simulation and not the actual execution of the simulation.
Another project at the University of Cincinnati [17, 33] involved running ns-2 in paral-
lel. The main objectives of this work is to build a space“time parallel simulator to study
how effectively ad hoc network simulations can be performed in parallel. At the present
time, their testbed supports parallel execution of ns-2 programs consisting of point-to-
point links with static routing and UDP traffic. A conservative null-messages approach
has been used for synchronization purposes. Although initial results are encouraging, this
work is still at an early stage.
The PDES community has also tried to design efficient simulators for wireless and
mobile systems using PDES synchronization schemes without relying on preexisting net-
work simulators. Wireless Propagation and Protocol Testbed (Wippet) [48] is a versatile
simulator for wireless networks. It consists of basic set of modules implemented using the
TeD, an object-oriented and telecommunication-descriptive language for parallel simula-
tion of telecommunications developed at Georgia Tech. [51]. Its propagation and interfer-
ence modeling at the receiver MH made simulation suitable for studying dynamic chan-
nel-allocation schemes. The partitioning of the model into multiple zones is either
geographically based or channel based. Channel-based partitioning gives rise to better
speedup due to the rare synchronization of zones in which a mobile device changes the
channel. However, how that is achieved in the implementation of Wippet is unclear. Selec-
tion of other channels requires interference measurement on the destination channel,
which should induce overall synchronization on all zones.
The GloMoSim (Global Mobile Information System Simulator) is a library-based se-
quential and parallel simulator for wireless networks, including multihop wireless ad hoc
networking and traditional wired Internet connectivity [58, 65]. The GloMoSim is de-
signed as a set of library modules, each of which simulates a specific wireless communi-
cation protocol within the protocol stack. Modules of the protocol can be developed at dif-
ferent levels of granularity. It has been developed using PARSEC (Parallel Simulation
Environment for Complex Systems), a C-based parallel simulation language [1]. PARSEC
basically adopts a message-based approach to discrete event simulation in which physical
processes are modeled by simulation objects referred to as entities, and events that repre-
sent the transmission of timestamped messages among corresponding entities. Glomosim
has been designed so that it can be easily extended and new protocols and modules can be
added to this library using this PARSEC language. It has been implemented on both
shared- and distributed-memory machines, and it supports conservative layered simula-
tion in the context of wireless network simulation. The synchronization protocol makes
use of Chandy“Misra null-messages scheme [16, 57]. Although the results reported in
[65] show a significant reduction of the null-messages overhead, a speedup of only up to
3.5 was obtained using eight processors [65]. Low speedups hinder the improvement due
to unresolved causal dependencies. More recently, the authors have reported improvement
on conservative simulation due to better lookahead computation [43].
400 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


Both GloMoSim/Parsec and TeD/GTW systems require the simulation modelers to
learn new language extensions to describe their network models, although GloMoSim, as
opposed to TeD/GTW, was designed to make the mechanics of parallel simulation trans-
parent to protocol modelers by embedding them into the lowest (channel) layer. Further
knowledge of PDES synchronizations is needed to understand how they work, in order to
develop new models, unless users are interested in running or modifying preexisting mod-
els.
QualNet is basically a commercial product derived from GloMoSim, developed at
UCLA. It is designed by the Scalable Network Technologies Inc., headed by R. Bagrodia
from UCLA. Several extensions have been added to GloMoSim to facilitate the develop-
ment of new protocols for wired, wireless, and ad hoc networks.
The following summarizes other related work on parallel simulation of wireless net-
works. An optimistic model based on Time Warp is proposed in [14]. It uses logical process-
es (LPs) and uniform rectangular-shaped cells to simulate large-scale PCS networks. The
mobility of a MH is limited to four neighbors only, and low blocking probability is achieved
with a fixed ratio of 50 MHs per cell. Better results were obtained with a low number of mo-
bile hosts per cell. In [39], another optimistic parallel simulation is presented in which the
PCS coverage area is modeled by fixed hexagonal shaped cells identifying the LP. The MHs
are given constant speed and angle of movement. Although the obtained results are encour-
aging, the model is useful only for low call traffic and reduced mobility.
As opposed to the preceding two-cell-based partitioning, a channel-based partitioning
is proposed in [40]. In this method, when a MH makes a hand-off, a set of messages is
sent out to all channels available on the new BS. This scheme may generate an inordinate
number of messages, nullifying any performance gain. Mobility of MHs is limited to con-
stant speed and four directions”north, east, west, and south. The MH is disposed after the
call is terminated. A good analysis of break-even points between cell-based and channel-
based partitioning were reported.
Despite the fact that promising results were obtained in these approaches, most of them
ignored real-life patterns for mobility and PCS network deployment by restricting cell
shapes to uniform geometric objects such as hexagons, rectangles, or squares. These limi-
tations and weak spatial modeling of cell characteristics often simplify the simulation
model, and do not capture the accuracy and realism in PCS networks performance evalua-
tion. Linear movements have been used in some of the existing works [14, 39, 40, 43]. In
real transportation traffic flow, segmented movement patterns, occasional pauses, and,
most importantly, rush hour traffic and/or congested roads, trigger spikes in the call ar-
rival rate. The results reported in [14, 39] assumed a (fixed) ratio of MHs to channels per
cell, which is unrealistic. Furthermore, channel-based partitioning [40] creates an MH at
runtime and discards it after the call is terminated, thus losing mobility within calls and
requiring unrealistic call-arrival processes that may be unrelated to mobility patterns.
In [6], Bononi et al. have recently defined a prototype General Adaptive Interaction
Architecture (GAIA) middleware to be implemented over a conservative, HLA-based, dis-
tributed simulation of mobile systems. The aim of the proposed middleware is to provide
adaptive runtime allocation of model components over the set of federates executed on the
available set of execution units. The adaptive allocation is performed in order to balance the
need for parallel execution and the message-passing overhead of distributed simulation.
The leading assumption of this work is that mobility inside the simulation model maps on
dynamic changes in the area of influence of every simulated host. If a certain amount of
time-locality is present in the communication with the neighbor hosts, then adaptive allo-
401
14.3 SIMULATION TECHNIQUES


cation can reduce the amount of inter-federate synchronization-message overheads.
Preliminary results show that speedup can be obtained in HLA-based, conservative simula-
tion of mobile ad hoc networks, executed over networked clusters of personal computers.
Recently, Boukerche et al. [7] developed SWiMNET, a high-performance simulator for
wireless and mobile networks. Their scheme uses a hybrid approach to simulating wire-
less and mobile networks, based on a combination of optimistic and conservative tech-
niques. It exploits event precomputation due to a simple assumption: mobility and call ar-
rival events of MHs are independent from the state of the wireless PCS simulation. Thus,
all events for each MH can be precomputed assuming all channel requests are satisfied,
and the actual channel allocation simulation cancels events for blocked calls. An excep-
tion to this fact may be a hotspot, that is, congestion due to rush-hour traffic or at a traffic
junction. In this situation, the MHs in that region have very low, if any, mobility and tend
to make more calls. This is tackled in the mobility design by introducing hotspot areas
where speeds are reduced and call arrival rates are increased.
With this mechanism, all movement and call-related events for each MH are precom-
puted, assuming all channel requests are satisfied. The small portion of events to be re-
tracted due to blocked calls is later computed in the actual simulation. The low percentage
of blocked calls desirable for wireless networks is exploited by the optimistic portion.
Event cancellations are done only if a call is blocked or dropped. The precomputation can
be pipelined to the channel-allocation simulation, thus minimizing the overhead of gener-
ating events.
In Table 14.1, we summarize a comparison of model-related and simulation-related is-
sues for SWiMNet, Wippet, and GloMoSim.


Table 14.1. Comparison of Model and Simulation Issues
Model-Related Issues
Parameters SWiMNet Wippet GloMoSim
Mobility Segmented paths Manhattan-style Unspecified
Call arrivals Poisson process Model-wise Node-wise
per MH poisson process poisson process
Coverage map Irregular cells over Manhattan-style Uniform geometry
Voronoi diagrams urban environment (hexagons or squares)
Signal propagation Not employed Stochastic fading Free-space model
Call admission FCA RSSI-based DCA Unspecified
Handoff mechanism Cell crossing induced RSSI based Cell crossing induced
Model size 54 BSs, 10000 MHs 48 BSs 2000 nodes
(short range)
Simulation-Related Issues
Precomputation Mobility, calls NA NA
Synchronization Hybrid Optimistic Conservative
Partitioning Cell based Zone based Static node based
(channel/cell)
Call traffic 4 calls/MH/hr 6 calls/sec 1 pkt/sec
to system to each node
Speedup 11.8 on 16 4 on 8 6 on 16
processors processors processors
402 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


In what follows, we shall describe the main features of SWiMNet, a recently developed
scalable simulation testbed for wireless and mobile networks.

14.3.3.1 Description of SWiMNet Model Components. In SWiMNet, the entire
simulation model is the result of the composition of four model components: (1) mobility
models, (2) call process, (3) BS deployment, and (4) channel management scheme. Al-
though the first three model components are independent of each other, the channel man-
agement component is dependent on the compound result of the first three components.
Mobilities and calls are represented by independent and stochastic processes3: locations
of MHs are chosen pseudorandomly, MHs trajectories across the map are sequences of
pseudorandomly generated segmented movements, and call interarrivals and durations are
pseudorandomly distributed.
As part of the mobility model, the population of mobile hosts (MHs) are classified into
groups of workers, wanderers, travelers, or static users, so as to represent behavior of dif-
ferent users across the wireless coverage area. The number of MHs per class is arbitrary.
Movements are modeled such that a complete path is composed of any number of straight
segments. This allows almost any kind of movement, by approximating a curve line with
as many segments as required by the resolution considerations. Every segment is then log-
ically partitioned into unitary tracts of a given unitary resolution, which defines how fine-
ly the MH position is checked.
The call model is specified by means of a maximum call rate per hour per MH, and an
average call duration. The entire simulation time interval can be partitioned into any num-
ber of subintervals, each with a different call rate. Thus, it is possible to represent call rate
changes during the simulation; night hours may be represented with very low call rates,
office hours with high call rates.
By composing mobility, calls, and BS deployment, the precomputation stage (Stage
1) is able to generate one stream of possible events per MH. The destination of such
events within Stage 2 is precomputed as well. The actual set of possible events, their
correlations, and how they are simulated, depends on the channel management policy to
be simulated.
The general structure of the simulator consists of three logical levels and two physical
stages. Entities comprising logical Level 1 are organized into Stage 1 of n1 (container)
processes, where each process maintains a set of mobile host incarnations (all sets are dis-
joint). Stage 2 consists of n2 cell container processes, and implements Level 2 (event
sorters) and Level 3 (cell incarnations) of the logical structure. The event sorter and the
cell incarnation related to the same cell are managed by the same cell container process in
Stage 2. Therefore, communications between Level 2 and Level 3 are easier and faster by
means of direct memory access instead of message passing. Communications between
Stage 1 and Stage 2 are implemented by means of a Message Passing Interface (MPI) us-
ing the LAM 6.1 environment [44]. Since no feedback is necessary from Stage 2 to Stage
1, in principle the execution of the two stages may be performed at different times. How-
ever, that would require Stage 1 to store precomputed events on file and Stage 2 to read
them from file afterwards, thus adding overhead.
The structure of SWiMNet simulator is depicted in Figure 14.6. For simplicity, every
process is represented as composed of only one entity (i.e., MH/Cell objects) per level.
Communications between Stage 1 and Stage 2 are based on a conservative scheme using

3
Note that a discrete distribution with one element only corresponds to a deterministic behavior.
STAGE 1 MH incarnations


precomputed event

null message

rollback message

Event sorters


<<

. 76
( 87 .)



>>