WSC 2003

WSC 2003 Final Abstracts

Modeling Methodology A Track

Monday 10:30:00 AM 12:00:00 PM
Foundations of Multi-Paradigm Modeling and Simulation

Chair: Adelinde Uhrmacher (University of Rostock)

Computer Automated Multi-Paradigm Modelling: Meta-Modelling and Graph Transformation
Hans Vangheluwe (McGill University) and Juan de Lara (Universidad Autónoma de Madrid)

Computer Automated Multi-Paradigm Modelling based on Meta-Modelling and Graph Transformation is presented. The syntax of a class of models of interest is graphically meta-modelled in an appropriate formalism. From this abstract syntax, an interactive, visual modelling environment is generated. As the abstract syntax of all models is graph-like, graph rewriting is used to perform model transformation. Graph Grammar models thus allow for model transformation specification. Graph rewriting provides a rigourous basis for specifying and analyzing model transformations such as simplification, simulation, and code generation. AToM3, A Tool for Multi-formalism and Meta-Modelling, is introduced. Meta-modelling and graph transformation concepts are introduced through a simple reactive system example: a Timed Automata model of a traffic light. Meta-modelling, generating the visual modelling environment, and modelling transformations as graph grammars, as well as executing them, are performed in AToM3. The model transformations include simulation, transformation into Timed Transition Petri Nets, and code generation.

A Meta-Theoretic Approach to Modeling and Simulation
Mamadou K. Traoré (Université Blaise Pascal)

We aim at building a methodological framework that integrates various methods and key concepts in a more coherent Modeling and Simulation architecture. The required flexibility for such a framework can be achieved by modeling the modeling process itself. The essence of this process lies in refining successive abstraction levels, each level into a lower one. The traversal of these abstraction levels, from the highest level (the more abstract) to the lowest one (the more detailed) involves two aspects: (1) System knowledge reside at different levels of a specification hierarchy; (2) many formalisms are often required for knowledge specification. As multi-formalism modeling provides a powerful means to deal with many formalisms, we show that modeling in addition the specification hierarchy provide the means to support many modeling processes. Both means are combined in a common meta-theoretic approach to enhance flexibility of the integrative framework.

A Port Ontology for Automated Model Composition
Vei-Chung Liang (Carnegie Mellon University) and Christiaan J.J. Paredis (Georgia Institute of Technology)

We study the concept of ports and we define an ontology for representing them. Ports define the locations of interaction at the boundaries of components or sub-systems; they can be used across different disciplines for both product modeling and simulation. They are therefore a convenient abstraction that allows simulation modelers to modularize and encapsulate their system descriptions such that configurations of port-based product models can be used to generate multiple simulation models at different levels of abstraction. However, to combine system models effectively across different disciplines, the representation of the ports needs to be unambiguous yet flexible, so that it can accommodate the differences in vocabulary and approach of all the disciplines. We provide an overview of how a port ontology, defined in the web ontology language, OWL, can capture both syntactic and semantic information such that automated modelers can reason about the system configuration and corresponding simulation models.

Monday 1:30:00 PM 3:00:00 PM
Hybrid Dynamic Systems

Chair: Hans Vangheluwe (McGill University)

Mode Transition Behavior in Hybrid Dynamic Systems
Pieter J. Mosterman (The MathWorks, Inc.)

Physical system modeling benefits from the use of implicit equations because it is often an intuitive way to describe physics. Model abstraction may lead to efficient models with idealized component behavior that switches between modes (e.g., a diode may be on or off) based on inequalities (e.g., voltage > 0). In an explicit representation, the combination of these local mode switches leads to a combinatorial explosion of the number of global modes. It is shown how an implicit formulation of these mode switches circumvents the combinatorial problem. This leads to the use of differential and algebraic equations (DAE) for each of the modes. In case these DAEs are of high index, jumps in generalized state variables may occur. In combination with the inequalities that define mode switching, this leads to rich and complex mode transition behavior. An overview of this mode switching behavior and an ontology is presented.

Relating Chi to Hybrid Automata
Bert van Beek, Nick G. Jansen, Koos E. Rooda, Ramon R.H. Schiffelers, Ka L. Man, and Michel A. Reniers (Eindhoven University of Technology)

A hybrid automaton is one of the most popular formal models for hybrid system specification. The Chi language is a hybrid formalism for modeling, simulation and verification. It consists of a number of operators that operate on all process terms, including differential algebraic equations. This paper relates the two formalisms by means of a formal translation from a hybrid automaton model to a Chi model, and a comparison of the semantics of the two models in terms of their respective transition systems. The comparison is illustrated by means of three examples: a thermostat, a railroad gate controller, and dry friction.

Models for Continuous and Hybrid System Simulation
Mariana C. D'Abreu (Universidad de Buenos Aires) and Gabriel A. Wainer (Carleton University)

The DEVS formalism was defined as a method for modeling and discrete event systems. DEVS theory evolved and it was recently upgraded in order to permit modeling of continuous and hybrid systems. Here, we present a first experience on the use of two of the existing methods for defining continuous variable DEVS models (namely, the QDEVS and the GDEVS formalisms), to develop continuous and hybrid systems simulations. We show how to model these dynamic systems under the discrete event abstraction. Examples of model simulations with their execution results are included. An experimental analysis on quantization methods within models is also presented.

Monday 3:30:00 PM 5:00:00 PM
Simulation of Large Scale Networks I

Chair: Richard Fujimoto (Georgia Institute of Technology)

Simulation of Large Scale Networks Using SSF
David M. Nicol, Jason Liu, and Michael Liljenstam (University of Illinois, Urbana-Champaign) and Guanhua Yan (Dartmouth College)

Some applications of simulation require that the model state be advanced in simulation time faster than the wall-clock time advances as the simulation executes. This "faster than real-time" requirement is crucial, for instance, when a simulation is used as part of a real-time control system, working through the consequences of contemplated control actions, in order to identify feasible (or even optimal) decisions. This paper considers the issue of faster than real-time simulation of very large communication networks, and how this is accomplished using our implementation (in C++) of the Scalable Simulation Framework (SSF). Our tool (called iSSF) uses hierarchical levels of abstraction, and parallelism, to achieve speedups of nearly four orders of magnitude, enabling real-time execution rates on large network models. We quantify the effects that choice of hierarchical abstraction has on the simulation time advance rate, and show analytically and empirically how changing the abstraction mix affects performance.

Modelling Differentiated Services in Conservative PDES
Roger Curry, Rob Simmonds, and Brian Unger (University of Calgary)

This paper explains how DiffServ has been implemented in an IP network simulator using an asynchronous conservative parallel discrete event simulation (PDES) kernel. DiffServ provides Quality of Service (QoS) functionality for IP networks and is designed to provide greater scalability and lower overhead than previous IP based QoS schemes. The paper explains the DiffServ components that have been implemented, focusing on the implementation of the preemptive network buffers required to provide DiffServ functionality. Certain optimisations possible for non-preemptive network buffers are not possible here; the paper explores which will work in the preemptive case. In particular, exploiting lookahead is more difficult leading to reduced performance in some cases. Optimisation schemes are described for two different preemptive buffering strategies and performance results demonstrating the costs of using these buffers are presented.

Staged Simulation for Improving Scale and Performance of Wireless Network Simulations
Kevin Walsh and Emin Gün Sirer (Cornell University)

This paper describes staged simulation, a technique for improving the run time performance and scale of discrete event simulators. Typical wireless network simulations are limited in speed and scale due to redundant computations, both within a single simulation run and between successive runs. Staged simulation proposes to reduce the amount of redundant computation within a simulation by restructuring discrete event simulators to operate in stages that precompute, cache, and reuse partial results. This paper presents a general and flexible framework for staging, and identifies the advantages and trade-offs of its application to wireless network simulations. Experience with applying staged simulation to the ns2 simulator shows that it can improve execution time by an order of magnitude in typical scenarios and make feasible the simulation of large scale wireless networks.

Tuesday 8:30:00 AM 10:00:00 AM
Simulation of Large Scale Networks II

Chair: Bolesaw Szymanski (Rensselaer Polytechnic Institute)

Large-Scale Network Simulations with GTNetS
George F. Riley (Georgia Institute of Technology)

When designing a network simulation environment intended specifically for modeling large-scale topologies, a number of issues must be addressed by the simulator designer. Memory requirements for network simulation engines can grow quadratically with the size of the simulated topology and can easily exceed available memory on modern workstations. The number of outstanding simulation events grows linearly with the number of packets in flight being modeled, and can lead to performance bottlenecks when managing a sorted event list of millions of events. Tracking the results of the simulation using a packet-level log file can result in excessive usage of disk space. We discuss the design of the Georgia Tech Network Simulator (GTNetS) with emphasis on how GTNetS addresses these issues. We give results from performance experiments showing the reduction in memory and event list size as a result of our design decisions.

Modeling and Simulation Best Practices for Wireless Ad Hoc Networks
Luiz Felipe Perrone (Bucknell University), Yougu Yuan (Dartmouth College) and David M. Nicol (University of Illinois, Urbana-Champaign)

This paper calls attention to important practices in the modeling and the simulation of wireless ad hoc networks. We present three case studies to highlight the importance of following well-established simulation techniques, of carefully describing experimental study scenarios, and, finally, of understanding assumptions sometimes unstated in the framework of a simulator. The first case addresses the initial transient problem inherent to mobility and traffic generation sub-models. We quantitatively demonstrate how these transients can affect the simulation. Our second case illustrates the fact that strong scientific contributions can only be made via simulation studies when the models used are unambiguously specified. The example we use are simulations with and without a model for the ARP protocol. Finally, our third case discusses the importance of understanding the simulation tool and any default values used for model parameters. The example used relates to the use of the limited interference model.

Development of an Internet Backbone Topology for Large-Scale Network Simulations
Michael Liljenstam and Jason Liu (Dartmouth College) and David M. Nicol (University of Illinois, Urbana-Champaign)

A number of network simulators are now capable of simulating systems with millions of devices, at the IP packet level. With this ability comes a need for realistic network descriptions of commensurate size. This paper describes our effort to build a detailed model of the U.S. Internet backbone based on measurements taken from a variety of mapping sources and tools. We identify key attributes of a network design that are needed to use the model in a simulation, describe which components are available and which must be modeled, and discuss the pros and cons of this approach as compared to synthetic generation. As for attributes that we have to model, we also briefly discuss some measurement efforts that can potentially provide the missing pieces, and thus improve the fidelity of the model. Finally, we describe the resulting network model of the U.S. Internet backbone, which is being made publicly available.

Tuesday 10:30:00 AM 12:00:00 PM
Simulation of Large Scale Networks III

Chair: George Riley (Georgia Institute of Technology)

ROSS.Net: Optimistic Parallel Simulation Framework for Large-Scale Internet Models
David Bauer, Garrett Yaun, Christopher D. Carothers, Murat Yuksel, and Shivkumar Kalyanaraman (Rensselaer Polytechnic Institute)

ROSS.Net brings together the four major areas of networking research: network modeling, simulation, measurement and protocol design. ROSS.Net is a tool for computing large scale design of experiments through components such as a discrete-event simulation engine, default and extensible model designs, and a state of the art XML interface. ROSS.Net reads in predefined descriptions of network topologies and traffic scenarios which allows for in-depth analysis and insight into emerging feature interactions, cascading failures and protocol stability in a variety of situations. Developers will be able to design and implement their own protocol designs, network topologies and modeling scenarios, as well as implement existing platforms within the ROSS.Net platform. Also using ROSS.Net, designers are able to create experiments with varying levels of granularity, allowing for the highest-degree of scalability.

Loosely-Coordinated, Distributed, Packet-Level Simulation of Large-Scale Networks
Boleslaw K. Szymanski and Yu Liu (Rensselaer Polytechnic Institute)

The complexity and dynamics of the Internet is driving the demand for scalable and efficient network simulation. In this paper, we describe a novel approach that partitions the networks into domains and simulation time into intervals. Each domain is simulated independently of and concurrently with the others with only local domain information over the same simulated time interval. At the end of each interval, global routing information, packet delays and drop rates for each inter-domain flow are exchanged between domain simulators. When the exchanged information converges to the value within a prescribed precision all simulators progress to the next simulated time interval. This approach allows the parallelization with infrequent synchronization, and achieves significant simulation speedups. Such a solution supports simulations of large-scale networks on distributed machines with modest memory size.

An Improved Computational Algorithm for Round-Robin Service
Jorge R. Ramos and Vernon Rego (Purdue University) and Janche Sang (Cleveland State University)

We present an efficient algorithm for effecting round-robin service in discrete-event simulation systems. The approach generalizes and improves upon a previous approach in which a single arrival and a single departure event is considered and handled at a time; further, the previous approach is already an improvement over naive round-robin scheduling currently in use in simulation libraries. The prior proposal offered a run-time complexity of O(n^2), because the processing of each event required an entire traversal of the job pool. We propose a generalized algorithm which includes the previous case and also accommodates burst arrivals and batch departures, further reducing run-time complexity to O(n log n). This is achieved through a detailed but efficient computation of multiple departure times, while simultaneously obviating the need for a job pool update with each departure. Empirical results are presented to compare performance with previously proposed algorithms.

Tuesday 1:30:00 PM 3:00:00 PM
Visualization for Modeling and Simulation

Chair: Paul Fishwick (University of Florida)

A Taxonomy of Visualization Techniques for Simulation in Production and Logistics
Sigrid Wenzel, Jochen Bernhard, and Ulrich Jessen (Fraunhofer Institute for Material Flow & Logistics)

Simulation has become one of the most important techniques with regard to manufacturing and logistics systems. During modeling and experimenting simulation input and output data have to be presented to different target groups which range from simulation experts and factory planners to representatives of company management, and for different tasks and specific purposes. Different kinds of visualization techniques are used to present the simulation data, from static techniques as charts and layout plans to dynamic techniques as 2-D or 3-D animation as well as Virtual or Augmented Reality. But often, non-expressive and non-effective visualizations prevent the understanding of simulation output. This paper presents a taxonomy of visualization techniques for simulation in production and logistics and outlines how to use this taxonomy as a base for decision support to select the right visualization technique for specific target groups.

Visualization Methods for Time-Dependent Data – An Overview
Wolfgang Müller (PH Ludwigsburg) and Heidrun Schumann (University of Rostock)

Visualization has been successfully applied to analyse time-dependent data for a long time now. Lately, a number of new approaches have been introduced, promising more effective graphs especially for large datasets and multi-parameter data. In this paper, we give an overview on the visualization of time-series data and the available techniques. We provide a taxonomy and discuss general aspects of time-dependent data. After an overview on conventional techniques we discuss techniques for analysing time-dependent multivariate data sets in more detail. After this, we give an overview on dynamic presentation techniques and event-based visualization.

Problems of Visualization of Technological Processes
Pavel Slavik, Marek Gayer, Frantisek Hrdlicka, and Ondrej Kubelka (Czech Technical University in Prague)

This paper deals with problems of visualization of dynamic phenomena. An effort to develop new visualization schemes has been described. The main idea is to extend approaches used in the case of visualization of phenomena of static nature into an environment where dynamic phenomena are investigated and visualized. We introduced the “level of detail” approach in time scaling in the environment of dynamic processes where time plays a primary role. In the case of visualization of dynamic phenomena the users are looking for specific dynamic patterns that should help them to understand in a better way the nature of dynamic processes under investigation. A new approach that should meet these requirements has been developed. This approach has been verified by means of two systems used for simulation and visualization of technological processes that are of a dynamic nature.

Tuesday 3:30:00 PM 5:00:00 PM
Next Generation Modeling I

Chair: Wolfgang Müller (PH Ludwigsburg)

RUBE: A Customized 2D and 3D Modeling Framework for Simulation
Paul Fishwick, Jinho Lee, Minho Park, and Hyunju Shim (University of Florida)

We present a system called RUBE, which allows a modeler to customize model components and model structure in 2D and 3D. RUBE employs open source tools to assist in model authoring, allowing the user to visualize models with different metaphors. For example, it is possible to visualize an event graph as a city block, or a Petri network as an organically-oriented 3D machine. We suggest that such flexibility in visualization will allow existing model types to take on forms that may be more recognizable to modeling sub-communities, while employing notation as afforded by inexpensive graphical hardware. There is also a possibility to create model types using entirely new notations.

Information Visualization Supporting Modelling and Evaluation Tasks for Climate Models
Thomas Nocke and Heidrun Schumann (University of Rostock), Uwe Böhm (University of Potsdam) and Michael Flechsig (Potsdam Institute for Climate Impact Research)

Information visualization exploits the phenomenal abilities of human perception to identify structures by presenting abstract data visually, allowing an intuitive exploration of data to get insight, to draw conclusions and to interact directly with the data. The specification, analysis and evaluation of complex models and simulated model data can benefit from information visualization techniques by obtaining visual support for different tasks. This paper presents an approach that combines modelling and visualization functionality to support the modelling process. Based on this general approach, we have developed and implemented a framework that allows us to combine a variety of models with statistical and analytical operators as well as with visualization methods. We present several examples in the context of climate modelling.

Issues Using COTS Simulation Software Packages for the Interoperation of Models
Michael D. Ryde and Simon J.E. Taylor (Brunel University)

This paper intends to examine the interoperation of simulation models from the viewpoint of a simulation engineer who uses standard tools and methods to create these models. The paper will look at the models in the context of COTS (Commercially available Off-The Shelf) simulation packages with a view to applying Distributed Simulation (DS) theory to the subject. By studying current methods employed which enable COTS simulation packages to interoperate, this paper will discuss the tools currently used and examine their appropriateness. The paper will also suggest how an example COTS simulation package could be modified to provide the necessary functions and interoperability required to allow full distributed simulation.

Wednesday 8:30:00 AM 10:00:00 AM
Next Generation Modeling II – Applications

Chair: Helena Szczerbicka (University of Hannover)

Experiencing Natural Phenomena with Virtual, Constructed and Mathematical Models
Stephan Diehl and Carsten Görg (Saarland University)

In this paper we discuss how different kinds of models can be combined in an educational setting to enable students to experience natural phenomena, here earthquakes. Different tools enable students to manipulate virtual models, construct physical models and formulate mathematical models. Ideally, the modelling processes and the resulting models complement each other to some degree. Virtual and physical models can then be driven by real data as well as mathematical models of the phenomena.

Improving the Development Process for Eukaryotic Cell Cycle Models with a Modeling Support Environment
Nicholas A. Allen, Clifford A. Shaffer, Marc T. Vass, Naren Ramakrishnan, and Layne T. Watson (Virginia Polytechnic Institute & State University)

Biological pathway modelers attempt to describe cellular processes and regulatory networks with continuous and discrete models of the cell cycle. Previous practice has been to develop these models largely by hand, and then to validate models primarily by comparing time series plots versus the observed experimental results. This paper reports our experiences in designing and building a modeling support environment (MSE) for cell cycle models. We describe improvements to the development process for cell cycle models by (a) identifying the key elements of the existing modeling process, (b) applying simulation methodology to construct a revised modeling process, and (c) building and testing software that supports the revised modeling process.

Modeling Control in Manufacturing Simulation
Durk-Jouke van der Zee (University of Groningen)

A significant shortcoming of traditional simulation languages is the lack of attention paid to the modeling of control structures, i.e., the humans or systems responsible for manufacturing planning and control, their activities and the mutual tuning of their activities. Mostly they are hard coded and dispersed throughout the model. Consequently, not only realism but also modeling flexibility and modularity is harmed. In recognition of this fact we consider a framework for simulation modeling that explicitly represents control structures. The framework is meant to serve as a conceptual basis for extending capabilities of simulation models, tools and libraries in analyzing manufacturing systems. It does so by capturing key-abstractions of the manufacturing field in terms of classes and their relationships. To study the practical relevance of the framework its concepts were implemented in an object-oriented simulation language and applied to a case example.

Wednesday 10:30:00 AM 12:00:00 PM
Next Generation Modeling III – Agents

Chair: James Arthur (Virginia Polytechnic Institute and State Univ.)

Simulation for Testing Software Agents – An Exploration based on JAMES
Jan Himmelspach, Mathias Röhl, and Adelinde M. Uhrmacher (University of Rostock)

Agents are software systems aimed at working in dynamic environments. Simulation systems can be used to provide virtual environments for testing agents. The software to be tested, the objective of the simulation study, and the stage of the agent software development influences both: the environmental models used for testing and the mechanisms that synchronize the execution of agents and simulation. A clear distinction between model and simulation layer, and a modular design of the simulation system support the required flexibility. Based on the simulation system James (a Java based Agent Modeling Environment for Simulation) and two agent applications we will explore, how interfaces between virtual environments and software agents can be explicitly specified at the modeling level and suitable mechanisms for synchronization might be chosen on demand.

A Multi-Paradigm Simulator for Simulating Complex Adaptive Supply Chain Networks
Surya Dev Pathak, David M. Dilts, and Gautam Biswas (Vanderbilt University)

This paper introduces a multi-paradigm dynamic system simulator based on discrete time and discrete event formalism for simulating a supply chain as a complex adaptive system. Little is known about why such a diversity of supply chain structures exist. Simulating dynamic supply chain networks over extended periods using the multi-paradigm dynamic system simulator allows us to observe the emergence of different structures. The simulator is implemented using a software agent technology, where individual agents represent firms in a supply chain network. In this paper, we present an example scenario run on the simulator and the preliminary results that have been observed. This multi-paradigm tool provides a valuable investigation instrument for real life supply chain problems.

SPADES – A Distributed Agent Simulation Environment with Software-in-the-Loop Execution
Patrick F. Riley (Carnegie Mellon University) and George F. Riley (Georgia Institute of Technology)

Simulations are used extensively for studying artificial intelligence. However, the simulation technology in use by and designed for the artificial intelligence community often fails to take advantage of much of the work by the larger simulation community to produce distributed, repeatable, and efficient simulations. We present the System for Parallel Agent Discrete Event Simulation, (SPADES), which is a simulation environment for the artificial intelligence community. SPADES focuses on the agent as a fundamental simulation component. The thinking time of an agent is tracked and reflected in the results of the agents' actions by using a software-in-the-loop mechanism. SPADES supports distributed execution of the agents across multiple systems, while at the same time producing repeatable results regardless of network or system load. We discuss the design of SPADES and give experimental results. SPADES is flexible enough for a variety of application domains in the artificial intelligence research community.

[ Return to Top | Return to Program ]