PADS 2008 Program
Tutorial: Distributed Simulation on the Grid
Stephen John Turner
The development of many complex simulation applications requires collaborative effort from researchers with different domain knowledge and expertise, possibly at different locations. These simulation systems often require huge computing resources and data sets which may be geographically distributed. In order to support collaborative model development and to cater for the increasing complexity of such systems, it is necessary to harness distributed resources over the Internet. The emergence of Grid technologies provides exciting new opportunities for large scale distributed simulation, enabling collaboration and the use of distributed computing resources, while also facilitating access to geographically distributed data sets. Part 1 of this tutorial describes the concepts and research challenges of large scale distributed simulation on the Grid. Part 2 presents a Service Oriented HLA RTI (High Level Architecture Runtime Infrastructure) developed at Nanyang Technological University. This is an open-source middleware that can be used for executing HLA-based distributed simulations in a Grid environment. The tutorial assumes a basic knowledge of parallel and distributed simulation.
1.Background and Motivation: Introduction to Web and Grid Services; Introduction to HLA; Motivation for Distributed Simulation on the Grid.
2.Taxonomy of Grid-based Simulation: Grid-Facilitated Approach; Grid-Enabled Approach; Grid-Oriented Approach; Non-HLA Approaches.
3.Research Challenges: Collaborative Model Development; Model Discovery and Matching; Resource and Simulation Management.
4.Decoupled Architecture: Advantages of a Decoupled Architecture; Migration and Load Balancing; Fault Tolerance.
5.SOHR Framework: Introduction to Globus Toolkit and WSRF (Web Services Resource Framework); Architecture of SOHR; Services and Modules; Experimental Results.
6.Using SOHR: Developing Clients; Using SOHR as a Service; Deploying SOHR; Extending SOHR.
7.Demonstration of SOHR: Demonstration of Distributed Simulation on the Grid using SOHR.
8.Conclusions: Further information; Future Work.
Keynote: Mobility Models for Wireless Networks: Challenges, Pitfalls, and Successes
Don Towsley
The performance of any mobile network is highly influenced by the mobility patterns of nodes in the network. In fact mobility behavior is the most important environmental factor that determines performance and influences network design. Thus it is important that we develop models that
1. accurately capture the mobility of nodes, while at the same time.
2. are amenable to mathematical analysis and/or efficient simulation.
In the past, the wireless networking community relied on simple models such as random walk [3] and random waypoint [2]. However, the first of these modelswas found to be too simplistic although very useful in analysis and simulation. The latter, on the other hand was widely accepted and used in simulations. However, recently it was disvcovered that practitioners had severely misued it in simulations [4]. That and the growing appreciation that random waypoint is unrealistic has led to significant activities recently focusing on the development of parsimonious and accurate models describing the movement of nodes in mobile wireless networks. These have included efforts to model connectivity within sparse mobile networks associated with people and vehicles, and with the movement of units in miliatary settings.
This talk will provide some of the early history in modeling mobility, including some of the failures described above. The talk will then describe the more recent application of a wide range of techniques to account for mobility. These range from Markov chains to ODE-based fluid models [6], from the use of exponetial, lognormal, and heavytailed distributions [1]to geometric weighted Gaussian distributions for intercontact times [5], and from the use of discrete state models to continuous state PDE-based models. The goal of the talk is to provide a better understanding of the issues underlying the accurate modeling of mobiltiy, recent progress in addressing these issues and the challenges that different approaches place on simulation.
Time Jails: A Hybrid Approach to Scalable Network Emulation
Andreas Grau, Steffen Maier, Klaus Herrmann, Kurt Rothermel
It is essential to evaluate the performance of newly developed distributed software and network protocols. Network emulation enables reproducible evaluation of unmodified real implementations. Software built for distributed systems, such as a large scale peer-to-peer system, requires evaluation scenarios with thousands of communicating nodes. Two approaches for scaling network emulation to such scenario sizes have been proposed in the literature: node virtualization and time virtualization. Node virtualization allows maximizing the utilization of standard hardware used for emulation experiments. Time virtualization enables trading experiment duration for virtually increased resources of the hardware. It stands to reason that a combination of those two approaches may increase scalability even further. However, in existing combinations, either node virtualization implies relatively high overhead or time virtualization requires modifications of the test subject implementation.
In this paper, we present a novel hybrid approach called Time Virtualized Emulation Environment (TVEE). It integrates node virtualization with low overhead and time virtualization, which is transparent to the execution of test subjects. We introduce virtual time based on epochs to enable better dynamic hardware utilization during long lasting experiments. Additionally, a mechanism similar to soft timers ensures an accurate reproduction of network properties in the time virtualized emulation. Our evaluations show the accuracy and scalability of time virtualized network emulation. Comparing TCP throughput, TVEE outperforms other approaches using an event based virtual time by an order of magnitude.
Adaptive Model Update Algorithms for Remote Network Emulation
Yan Gu, Richard Fujimoto
Remote network emulation is an approach that utilizes a remote parallel simulator to improve the scale and accuracy of network emulation for general users with no local access to high performance computing facilities. The remote network emulation approach involves using a large scale detailed packet level simulation at a remote site in conjunction with a local network emulation to quickly provide QoS predictions to real time applications. Model update algorithms are needed to keep the remote simulator and local emulator updated with each other¡¯s status, while keeping the amount of communication required to an acceptable level. In this paper two adaptive model update algorithms are explored for triggering network status updates. The first algorithm dynamically adjusts update frequency according to the real network status between the remote simulator and emulator. The second algorithm triggers updates whenever the prediction error of the network emulation exceeds a pre-set threshold. Preliminary experimental results show that the two algorithms can improve emulation accuracy compared with a fixed update algorithm for the scenarios that were tested.
Toward Scalable Routing Experiments with Real-Time Network Simulation
Yue Li, Jason Liu, Raju Rangaswami
The ability to conduct accurate and realistic experiments is critical in furthering the research and development of network routing protocols. Existing framework for routing experiments is found to be lacking in one or more of the three required features: realism, scalability, and flexibility. We develop a new software infrastructure that combines the scalability and flexibility benefits of real-time network simulation with the realism of open-source routing protocol implementations. The infrastructure seamlessly integrates the open-source XORP router software with a previously developed real-time network simulation engine. Our design of the infrastructure uses a novel forwarding plane offloading approach that decouples routing from forwarding and confines the more resource consuming forwarding operations inside the simulation engine to reduce I/O overhead. Experiments demonstrate superior performance of the experimental infrastructure without impairing accuracy.
Parallel Vehicular Traffic Simulation using Reverse Computation-based Optimistic Execution
Srikanth Yoginath, Kalyan Perumalla
Vehicular traffic simulations are useful in applications such as emergency management and homeland security planning tools. High speed of traffic simulations translates directly to speed of response and level of resilience in those applications. Here, a parallel traffic simulation approach is presented that is aimed at reducing the time for simulating emergency vehicular traffic scenarios. Three unique aspects of this effort are: (1) exploration of optimistic simulation applied to vehicular traffic simulation (2) addressing reverse computation challenges specific to optimistic vehicular traffic simulation (3) achieving absolute (as opposed to selfrelative) speedup with a sequential speed equal to that of a fast, de facto standard sequential simulator for emergency traffic. The design and development of the parallel simulation system is presented, along with a performance study that demonstrates excellent sequential performance as well as parallel performance.
Modelling and Simulation of Pedestrian Behaviours
Wee Lit Koh, Lin Lin, Suiping Zhou
The modelling and simulation of autonomous pedestrians has important applications in real-time crowd and crisis simulations. With the increase in processing powers and dedicated graphics cards, more processing powers can now be allocated for the generation of realistic behaviours for individuals within the crowd. We have proposed a representation for autonomous agents that is aimed to generate some human-like behaviours. In particular, to generate smooth and realistic navigational behaviour such as human-like collision avoidance, we have also proposed a two tier navigation model for autonomous agents. Using the proposed model, a scene in a typical shopping mall has been created. Behaviours such as crowd avoidance and lane following have been observed from the simulation.
Parallel and Distributed Spatial Simulation of Chemical Reactions
Matthias Jeschke, Roland Ewald, Alfred Park, Richard Fujimoto, Adelinde M.Uhrmacher
The application of parallel and distributed simulation techniques is often limited by the amount of parallelism available in the model. This holds true for large-scale cell-biological simulations, a field that has emerged as data and knowledge concerning these systems increases and biologists call for tools to guide wet-lab experimentation. A promising approach to exploit parallelism in this domain is the integration of spatial aspects, which are often crucial to a model¡¯s validity. We describe an optimistic, parallel and distributed variant of the Next-Subvolume Method (NSM), a method that augments the well-known Gillespie Stochastic Simulation Algorithm (SSA) with spatial features. We discuss requirements imposed by this application on a parallel discrete event simulation engine to achieve efficient execution. First results of combining NSM and the grid-inspired simulation system AURORA are shown.
Secure Referee Selection for Fair and Responsive Peer-to-Peer Gaming
Steven Webb, Sieteng Soh, Jerry Trahan
Peer-to-peer (P2P) architectures for Massively Multiplayer Online Games (MMOG) provide better scalability than Client/Server (C/S); however, they increase the possibility of cheating. Recently proposed P2P protocols use trusted referees that simulate/validate the game to provide security equivalent to C/S. When selecting referees from untrusted peers, selecting non-colluding referees becomes critical. Further, referees should be selected such that the range and length of delays to players is minimised (maximising game fairness and responsiveness). In this paper we formally define the referee selection problem and propose two secure referee selection algorithms, SRS-1 and SRS-2, to solve it. Both algorithms ensure the probability of corrupt referees controlling a zone/region is below a predefined limit, while attempting to maximise responsiveness and fairness. The trade-off between responsiveness and fairness is adjustable for both algorithms. Simulations show the effectiveness of our algorithms in two different scenarios.
Stochastic Process Models for Packet/Analytic-Based Network Simulations
Robert Cole, George Riley, Derya Cansever, William Yurcik
WE present our preliminary work that develops a new approach to hybrid packet/analytic network simulations for improved network simulation fidelity, scale, and simulation efficiency. Much work in the literature addresses this topic, including [10] [11] [8] [12] [13] and others. Current approaches rely upon models, which we refer to in this paper as Deterministic Fluid Models [9] [12], to address the analytic modeling aspects of these hybrid simulations. Instead we draw upon an extensive literature on stochastic models of queues and (eventually) networks of queues to implement a hybrid stochastic model/packet network simulation. We will refer to our approach as Stochastic Fluid Models throughout this paper. We outline our approach, present test cases, and present simulation results comparing the measured queue metrics from our approach for hybrid simulation to those of a deterministic fluid model hybrid simulation and a full packet¨Clevel simulation. We also discuss plans for future areas of research on this approach.
Performance Analysis of Real Traffic Carried with Encrypted Cover Flows
Nabil Schear, David Nicol
Encrypted protocols, such as SSL, are becoming more prevalent because of the growing use of e-commerce, anonymity services, and secure authentication. Likewise, traffic analysis is becoming more common because it is often the only way to analyze these protocols. Though there are many valid uses for traffic analysis (such as network policy enforcement and intrusion detection), it can also be used to maliciously compromise the secrecy or privacy of a user. While the payload can be strongly protected by encryption, analysis of traffic patterns can yield information about the type and nature of traffic. In this paper we use simulation and an analytic model to examine the impact on user experience of a scheme that masks the behavior of real traffic by embedding it in synthetic, encrypted, cover traffic. This point provides a novel context where we observe the synergy of simulation and analytic modeling. We show that a detailed simulation model of network traffic characteristics can be used to estimate the parameters of an analytic model of tunneling.
An Algorithm Selection Approach for Simulation Systems
Roland Ewald, Jan Himmelspach, Adelinde M. Uhrmacher
No simulation algorithm will deliver best performance under all circumstances, so simulation systems often offer execution alternatives to choose from. This leads to another problem: how is the user supposed to know which algorithm to select? The need for an automated selection mechanism is often neglected, as many simulation systems are focused on specific applications or modeling formalisms and therefore have a limited number of expert users. In generalpurpose simulation systems like JAMES II, an ¡¯intelligent¡¯ selection mechanism could help to increase the overall performance, especially when users have limited knowledge of the underlying algorithms and their implementation(s) (which is almost always the case). We describe an approach to integrate algorithm selection methods with such systems. Its effectiveness is illustrated in conjunction with the ¡¯plug¡¯n simulate¡¯ approach of JAMES II [12].
Interval Branching
Patrick Peschlow, Peter Martini, Jason Liu
We propose a new simulation method, called interval branching, which aims to facilitate efficient simulation studies of systems that involve temporal uncertainty. The method uses interval timestamps for events and explores different execution orders of overlapping events by branching the simulation. We first present a sequential version of interval branching, and then extend it to parallel simulation using the logical process paradigm. The parallel interval branching algorithm uses the logical-process cloning technique for efficient computation of branches. Our preliminary experiments show its potential as an efficient method for discrete-event simulation studies.
Symbiotic Simulation Systems: An Extended Definition Motivated by Symbiosis in Biology
Heiko Aydt, Stephen John Turner, Wentong Cai, Malcolm Yoke Hean Low
Although various forms of symbiosis are known in biology, only mutualism has been considered in the context of symbiotic simulation systems. In this paper, we explain why the original definition of symbiotic simulation systems is narrow and why it is important to consider other forms of symbiosis as well. As a consequence we propose an extended definition of symbiotic simulation systems motivated by symbiosis in biology. By using this extended definition, we identify five different types of symbiotic simulation systems which can be applied in various applications. We describe how single systems can be combined and propose a hybrid symbiotic simulation system in the context of semiconductor manufacturing.
Evaluating the performance of real time videoconferencing in ad hoc networks through emulation
Jorge Hortelano, Juan-Carlos Cano, Carlos T. Calafate, Pietro Manzoni
The validation of new video protocols and applications for mobile ad hoc networks in a real environment is an important task. In this work we present Castadiva, a test-bed architecture that allows validating software solutions for ad hoc networks using low cost, off-the-shelf devices and open source software. We use this tool to test a videocall using
the OLSR protocol in different scenarios, varying the number of hops between the caller and the receiver.
The results obtained in this paper show that, for an ad hoc network with a large number of hops, the quality of videocalls suffers a significant degradation even in the absence of mobility.
Scalability versus Accuracy in Physical Layer Modeling for Wireless Network Simulations
Elyes Ben Hamida, Guillaume Chelius, Jean Marie Gorce
In wireless networking, due to the high complexity of analytical and theoretical models, simulations are generally considered as the most convenient methodology for performance evaluation. Nonetheless, the physical complexity of the wireless medium induces a clear tradeoff between accuracy and scalability in a wireless network simulator design. In this paper, we focus on this tradeoff and study the impact of physical layer (PHY) modeling accuracy in the computational cost of simulations. We first discuss the main aspects of the wireless medium and briefly show how they have been handled in existing simulators. Then, we introduce a flexible and modular PHY simulation framework to analyze in more details their influence on the scalability of simulations.
Hybrid Testbed Enabling Run-time Operations for Wireless Applications
Kumiko Maeda, Keisuke Nakata, Takaaki Umedu, Hirozumi Yamaguchi, Keiichi Yasumoto, Teruo Higashino
In this paper, we propose a hybrid Testbed enabling Run-time Operations for Wireless network Applications (TROWA). TROWA is a wireless network emulator and its simulation core is based on the network simulator MobiREAL. TROWA can emulate packet transmissions in multi-hop wireless networks in real-time, with realistic mobility models of urban pedestrians. Also it provides APIs that allow real stations to connect with their simulated networks with a little modification of applications and protocols. One of the significant features of TROWA is the control interfaces to manipulate the movement of simulated nodes during the execution of applications. This enables performance analysis and algorithm validation in an efficient way. Additionally, TROWA can improve the accuracy of real-time simulation by prioritizing the simulation events. By several experiments for a VoIP application, we show the usefulness of TROWA.
A comparison of Interest Manager Mechanisms for Agent-Based Simulation using a Time Warp Executive
Maria Hybinette, Tianhao He
An important issue for agent-based simulation architectures concerns the means by which agents can be kept up to date regarding the position and state of other agents and objects in their local environment. We implement two distributed publish-subscribe approaches and assess their performance within our SASSY architecture. One implementation supports direct agent-to-agent communication, while in the other all messages pass through an intermediate LP. In both cases the system does not maintain global state, but facilitates communication between individual agents that may affect one another. The environment is decomposed into a set of regions, where an LP referred to as an Interest Manager (IM) manages each region. When agents enter a region they register their presence with the appropriate InterestManager. Agents also subscribe and unsubscribe to information from neighboring regions as they move through the environment. Publish-subscribe approaches have been utilized in other simulation environments (e.g., HLA), but we believe our approach is the first to use a peer-to-peer method in an optimistic environment. We assess the efficiency of these two methods by measuring the number of rollbacks, and total runtime for various configurations of the simulation.
DyMeLoR: Dynamic Memory Logger and Restorer Library for Optimistic Simulation Objects with Generic Memory Layout
Roberto Toccaceli, Francesco Quaglia
In this article we focus on checkpoint/restore facilities for optimistic simulation objects with generic memory layout. Specifically, we present the design and implementation of a C library, named DyMeLoR (Dynamic Memory Logger and Restorer), that, beyond offering traditional services for dynamic memory allocation/release, additionally supports transparent checkpoint/restore of scattered simulation objects' states. DyMeLoR is well suited for being integrated within optimistic simulation platforms relying on kernel processes, each managing one or more simulation objects, as typical in most implementations of general purpose optimistic simulation platforms. From the point of view of efficiency, DyMeLoR has been designed in order to minimize memory consumption for meta-data describing the current layout of the simulation object's state, and to provide good trade-offs between the cost of meta-data manipulation and the cost of memory-to-memory data copies associated with checkpoint/restore tasks. Also, the library exhibits Piece-Wise-Deterministic (PWD) behavior, thus allowing the employment of (optimized) sparse checkpointing strategies each time the overlying application software complies with the PWD assumption. We also report the results of an experimental study where DyMeLoR is integrated within the ROme OpTimistic Simulator (ROOT-Sim), and is used to support optimistic simulation of a cellular system.
An Agent-based Environment for Simulation Model Composition
Farshad Moradi, Rassul Ayani, Imran Mahmood
As Modelling and Simulation gains more popularity, the demand on reducing time and resource costs associated with development and validation of simulation models has also increased. Composing simulation models of reusable and validated simulation components is one approach for addressing the above demand. This approach requires a composition process that is able to support a modeller with discovery and identification of components as well as giving feedback on feasibility of a composition.
Software agents are programs that can with some degree of autonomy perform tasks on behalf of a user or another program. In a Multi Agent System (MAS) autonomous agents interact and collaborate with each other in order to solve complex problems that are
beyond the individual capabilities or knowledge of each agent, thus providing modularity and scalability. The objective of this work has been to develop a Multi Agent System for discovery and composition of BOM (Base Object Model) based simulation models, which provides the flexibility and adaptability to test and assess, amongst others different discovery and composition methods and techniques.
The MAS that we developed is based on the JACK? Intelligent Agents and executes a rule-based process for discovery and composition of BOMs. Our preliminary results indicate its feasibility, portability, adaptability and flexibility.
Advancing the Layered Approach to Agent-based Crowd Simulation
Bikramjit Banerjee, Ahmed Abukmail, Landon Kraemer
We adapt a scalable layered intelligence technique from the game industry, for agent-based crowd simulation. We extend this approach for planned movements, pursuance of assignable goals, and avoidance of dynamically introduced obstacles/threats, while keeping the system scalable with the number of agents. We exploit parallel processing for expediting the pre-processing step that generates the path-plans offline. We demonstrate the various behaviors in a hall-evacuation scenario, and experimentally establish the scalability of the frame-rates with increasing number of agents.
Micro-synchronization in Conservative Parallel Network Simulations
Siming Lin, Xueqi Cheng, Jianming Lv
Lookahead is a critical factor in conservative parallel simulation. Greater lookahead usually brings better performance. However, in the simulation of computer networks, lookahead is usually determined by the minimal delay of the border links between any two subnets that simulated by different sequential logical processes (LPs), which is too small to get good performance. Traditionally, the lookahead exploitation usually only reflects the parallelism among LPs, which possibly wastes the potential parallelism inside each LP, especially, in the case that each LP simulates thousands of entities. Here we present a simple method called micro-synchronization to exploit the parallelism inside each LP. Different from the previous work, such as lookahead accumulation and local time warp, we keep the traditional usage of lookahead among LPs unchanged, and however, we impose the relaxed sequential event scheduling inside each LP, which can indirectly improve the lookahead. We also present a state causality model to prove the correctness of our method, which means that there is no risk in the relaxed sequential execution. Finally, the experiment evaluates our method and shows that it can improve the performance of conservative parallel simulation of computer networks to some extent.
A Hybrid HLA Time Management Algorithm Based on Both Conditional and Unconditional Information
Ke Pan, Stephen John Turner, Wentong Cai, Zengxiang Li
The High Level Architecture (HLA), which is the IEEE standard for distributed simulation, defines six service groups. The Time Management (TM) service group ensures a Time-Stamp-Ordered (TSO) message delivery sequence and correct time advancement of each simulation component (federate) in an HLA-based distributed simulation application (federation). To control time advancement of a federation, a distributed TM algorithm requires each regulating federate to periodically propagate its local time information to all constrained federates for their respective calculation of Greatest Available Logical Time (GALT). The time information propagated is called conditional information or unconditional information depending on whether it can be guaranteed to be true conditionally or unconditionally. A traditional distributed TMalgorithm can be either synchronous or asynchronous. In general, a synchronous algorithm utilizes conditional information while an asynchronous algorithm utilizes unconditional information. However, both synchronous and asynchronous algorithms have their own drawbacks and thus cannot be used for all federation scenarios. To resolve the drawback of each algorithm, this paper proposes a hybrid TM algorithm by combining synchronous and asynchronous algorithms. The three algorithms have been incorporated into an RTI (Run Time Infrastructure) and experimental results show that the hybrid algorithm effectively combines the advantages of both synchronous and asynchronous algorithms.