WSC 2004 Final Abstracts

Sunday 1:00:00 PM 2:30:00 PM
Interfaces with Simulation Modeling
Chair: Gabriel Wainer (Carleton University)

The Potential Coupling Interface: Metadata for Model Coupling
Tom Bulatewicz, Janice Cuny, and Maureen Warman (University of Oregon)

Abstract:
Model coupling is a nontrivial task that is not adequately supported in existing frameworks. Our long term goal is to support the fast-prototyping of model couplings, enabling scientists to quickly experiment with a variety of linkings without having to make an upfront investment in repro-gramming. This paper introduces the centerpiece of our framework, the Potential Coupling Interface (PCI), a visual representation of a model code based on simplified control flow graphs. The PCI serves three roles: it is a new form of metadata describing the coupling potential of a model; it is the vehicle for the specification of couplings; and it is the basis for automatic code generation. It is easy to specify and once specified, it is available for all future coupling activities. The PCI allows scientists to focus on the impor-tant domain and model issues of coupling without having to revisit legacy code for each new effort.

Automated Database and Schema-Based Data Interchange for Modeling and Simulation
Gregory A. Harrison, David S. Maynard, and Eytan Pollak (Lockheed Martin Simulation, Training and Support)

Abstract:
Creating a simulation of a large enterprise system by manually coding all the details into a simulator tool is not just time consuming, but yields a system that is difficult to maintain. By separating the model-configuration data from the models, a higher level of automation can be achieved, and enhance the usefulness of the simulation. The underly-ing data can be manipulated by the subject matter experts, and then transformed into the appropriate structure for simulator use. This paper describes a method that auto-matically configures a simulation using external data that interfaces to generic processing flow. The models and the simulation were co-designed along with the interchange data representation to enable generic models to be config-ured under software sequenced by a workflow system. This allowed model re-use, and automatic configuration changes, in support of optimization. We also describe the application of this technique to the simulation of an enter-prise, student-training system.

Modeling and Simulation of Hardware/Software Systems with CD++
Ezequiel Glinsky and Gabriel A. Wainer (Carleton University)

Abstract:
Modeling and simulation (M&S) methodologies can be useful in the development of hardware-in-the-loop applications. CD++ is a toolkit with support for real-time model execution that implements DEVS, a sound, formal M&S framework allowing hierarchical, modular model composition and component reuse. We present a methodology that uses CD++ to develop hybrid hardware/software systems. The technique enables incremental transition from the simulated models to the actual hardware counterparts, supports experimental frameworks to facilitate testing in a risk-free environment, encourages component reuse, and allows developing models with different levels of abstraction. CD++ can reduce cost and time-to-market of hardware- in-the-loop applications, and preserves the benefits of a formal M&S methodology like DEVS.

Abstract:
Simulation and emulation techniques are fundamental to aid the process of large-scale protocol design and network operations. However, the results from these techniques are often view with a great deal of skepticism from the networking community. Criticisms come in two flavors: (i) the study presents isolated and potentially random feature interactions, and (ii) the parameters used in the study may not be representative of real-world conditions. In this paper, we explore both issues by applying large-scale experiment design and black-box optimization techniques to analyze convergence of network routes in the Open Shortest Path First protocol over a realistic network topology. By using these techniques, we show that: (i) the needed number of simulation experiments can be reduced by an order of magnitude compared to traditional full-factorial experiment design (FFED) approach, (ii) unnecessary parameters can easily be eliminated, and (iii) rapid understanding of key parameter interactions can be achieved.

On-Demand Computation of Policy Based Routes for Large-Scale Network Simulation
Michael Liljenstam and David M. Nicol (University of Illinois at Urbana-Champaign)

Abstract:
Routing table storage demands pose a significant obstacle for large-scale network simulation. On-demand computation of routes can alleviate those problems for models that do not require representation of routing dynamics. However, policy based routes, as used at the interdomain level of the Internet through the BGP protocol, are significantly more difficult to compute on-demand than shortest path intradomain routes due to the semantics of policy based routing and the possibility of routing divergence. We exploit recent theoretical results on BGP routing convergence and measurement results on typical use of BGP routing policies to formulate a model of typical use and an algorithm for on-demand computation of routes that is guaranteed to terminate and produces the same routes as BGP. We show empirically that this scheme can reduce memory usage by orders of magnitude and simultaneously reduce the route computation time compared to a detailed model of the BGP protocol.

New Event-driven Sampling Techniques for Network Reliability Estimation
Abdullah Konak (Penn State Berks - Lehigh Valley), Alice E. Smith (Auburn University) and Sadan Kulturel-Konak (Penn State Berks - Lehigh Valley)

Abstract:
Exactly computing network reliability measures is an NP-hard problem. Therefore, Monte Carlo simulation has been frequently used by network designers to obtain accurate estimates. This paper focuses on simulation estimation of network reliability. Using a heap data structure, efficient implementation of a previous approach, dagger sampling, is proposed. Two new techniques, geometric sampling and block sampling, are developed to efficiently sample states of a network. These techniques are event-driven rather than time-driven, and are thus efficient for highly reliable networks. To test relative performance, computational experiments are carried out on various types of networks using the new procedures.

A Case Study in Meta-Simulation Design and Performance Analysis for Large-Scale Networks
David Bauer, Garrett Yaun, Christopher D. Carothers, Murat Yuksel, and Shivkumar Kalyanaraman (Rensselaer Polytechnic Institute)

Multi-Formalism Modeling Approach for Semiconductor Supply/Demand Networks
Gary W. Godding (Intel Corporation), Hessam S. Sarjoughian (Arizona State University) and Karl Kempf (Intel Corporation)

Abstract:
Building computational models of real world systems usu-ally requires the interaction of decision modules and simu-lation modules. Given different models and algorithms, the major hurdles in building a principled and robust system are model composibility and algorithm interoperability. We describe an approach to the composibility problem in-cluding initial results. This exposition is given in the con-text of Linear Programming as the decision technique and Discrete Event Simulation as the simulation technique, both applied to the design and operation of semiconductor supply/demand networks.

Modeling Real-World Control Systems: Beyond Hybrid Systems
Stephen Neuendorffer (University of California, Berkeley)

Abstract:
Hybrid system modeling refers to the construction of system models combining both continuous and discrete dynamics. These models can greatly reduce the complexity of a physical system model by abstracting some of the continuous dynamics of the system into discrete dynamics. Hybrid system models are also useful for describing the interaction between physical processes and computational processes, such as in a digital feedback control system. Unfortunately, hybrid system models poorly capture common software architecture design patterns, such as threads, mobile code, safety, and hardware interfaces. Dealing effectively with these practical software issues is crucial when designing real-world systems. This paper presents a model of a complex control system that combines continuous-state physical system models with rich discrete-state software models in a disciplined fashion. We show how expressive modeling using multiple semantics can be used to address the design difficulties in such a system.

Computer Automated Multi-Paradigm Modelling for Analysis and Design of Traffic Networks
Hans Vangheluwe (McGill University) and Juan de Lara (Universidad Autónoma de Madrid)

Abstract:
Computer Automated Multi-Paradigm Modelling (CAMPaM) is an enabler for domain-specific analysis and design. Traffic, a new untimed visual formalism for vehicle traffic network modelling, is introduced. The syntax of Traffic models is meta-modelled in the Entity-Relationship Diagram formalism. From this, augmented with concrete syntax information, a visual modelling environment is synthesized using our CAMPaM tool AToM³, A Tool for Multi-formalism and Meta-Modelling. The semantics of the Traffic formalism is subsequently modelled by mapping Traffic models onto Petri Net models. As model abstract syntax is graph-like, graph rewriting can be used to transform models. The advantages of a domain-specific formalism such as Traffic as opposed to a generic formalism such as Petri Nets are presented. We demonstrate how the Traffic to Petri Net mapping allows one to employ Petri Net analysis techniques. A Coverability Graph is generated and conservation analysis is automated by transforming this graph into an Integer Linear Programming specification.

Abstract:
Ontologies represent the next important phase of the World Wide Web, creating a semantic web which links together disparate pieces of information and knowledge. Creating ontologies within computer simulation can be seen as a logical next phase of the web-based modeling and simulation thrust, where the emphasis is on knowl-edge and its representation rather than on run-time net-work characteristics. We introduce the concept of an on-tology and then survey two groups performing research in this area at the Universities of Florida and Georgia, re-spectively.

Potential Modeling and Simulation Applications of the Web Ontology Language - OWL
Lee Lacy and William Gerber (Dynamics Research Corporation)

Abstract:
The Semantic Web is an evolution of the current world-wide web that provides explicit semantics that enable software applications to better process information representations. The Web Ontology Language – OWL – is a new language for representing information on the Semantic Web. Modeling and simulation (M&S) applications have many information representation challenges. Examples of M&S data include data tables from authoritative data sources, behaviors for computer generated forces, and descriptions of units and entities to be simulated. OWL provides a consistent syntax using the Resource Description Framework (RDF) and predefined constructs with standard semantics. These features enable better information sharing and support reasoning by inferencing systems. OWL is best used for representing object-oriented descriptions of items in a well-defined domain. It could be used in the M&S community to support distributed representations of data, behaviors, descriptions of units and objects to be simulated, and scenarios with initial conditions.

Data and Metadata Requirements for Composable Mission Space Environments
Katherine L. Morse (SAIC)

Abstract:
Composability is the capability to select and assemble re-usable simulation components in various combinations into simulation systems to meet user requirements. The Defense Modeling and Simulation Office’s Composable Mission Space Environments program, seeks to develop concepts, technologies, and processes to enable the rapid, efficient, and flexible assembly of simulation systems from components. A workshop was held to examine the current state of composability, refine its definitions and intentions, identify capabilities and technologies needed to support practical composability, and propose research objectives and programmatic initiatives to move towards the goals of the Composable Mission Space Environments (CMSE) program. Approximately 35 experts from gov-ernment, industry, and academia participated in four working groups (WGs). This paper reports the findings and recommendations of the Data and Metadata WG.

Ontologies for Modeling and Simulation: Issues and Approaches
Paul A. Fishwick (University of Florida) and John A. Miller (University of Georgia)

Characterizations and Relationships of World Views
C. Michael Overstreet (Old Dominion University) and Richard E. Nance (Orca Computer, Inc)

Abstract:
We describe a characterization the three classical world views of event scheduling, activity scanning, and process interaction and discuss transformations among them. We believe that one advantage of each is to allow more concise model descriptions by allowing a model specifier to take advantage of contextual information. Automated transformation among world views is difficult due to a modeler’s use of contextual information. We illustrate this by transforming and then simplifying a model representation creating a version, similar to what a programmer or modeler might generate.

Simulation Worldviews - So What?
Michael Pidd (Lancaster University)

Abstract:
The simulation pioneers had no choice but to write code if they wished to conduct a computer simulation. Hence the early interest in simulation worldviews, which allowed an application model to be separated from a simulation en-gine. Nowadays, few simulations are developed this way and few students are taught the various simulation world-views, though they figure in many textbooks. Does this matter, or is an interest in simulation worldviews just a his-torical curiosity?

Some Recent Advances in the Process World View
Robert G. Sargent (Syracuse University)

Abstract:
We discuss a modification of the process world view, a graphical modeling representation language for the modified process world view called Control Flow Graphs (CFGs), an extension to CFGs called Hierarchical Control Flow Graph (HCFG) Models, and a simulation system that uses HCFG Models called HiMASS.

Tuesday 8:30:00 AM 10:00:00 AM
Modeling and Security
Chair: David Nicol (University of Illinois at Urbana-Champaign)

Abstract:
Supervisory Control And Data Acquisition (SCADA) systems gather and analyze data for real-time control. SCADA systems are used extensively, in applications such as electrical power distribution, telecommunications, and energy refining. SCADA systems are obvious targets for cyber-attacks that would seek to disrupt the physical complexities governed by a SCADA system. This paper uses a discrete-event simulation to begin to investigate the characteristics of one potential means of hardening SCADA systems against a cyber-attack. When it appears that real-time message delivery constraints are not being met (due, for example, to a denial of service attack), a peer-to-peer overlay network is used to route message floods in an effort to ensure delivery. The SCADA system, and peer-to-peer nodes all use strong hardware-based authentication techniques to prevent injection of false data or commands, and to harden the routing overlay. Our simulations help to quantify the anticipated tradeoffs of message survivability and latency minimization.

Fast Model-Based Penetration Testing
Sankalp Singh, James Lyons, and David M. Nicol (University of Illinois at Urbana-Champaign)

Abstract:
Traditional approaches to security evaluation have been based on penetration testing of real systems, or analysis of formal models of such systems. The former suffer from the problem that the security metrics are based on only a few of the possible paths through the system. The latter suffer from the inability to analyze detailed system descriptions due to the rapid explosion of state space sizes, which render the models intractable for tools such as model checkers. We propose an approach to obtain statistically valid estimates of security metrics by performing repeated penetration testing of detailed system models. We make use of importance sampling techniques to help reduce the variance of our estimates, and achieve relative error bounds quickly. We validate our approach by estimating security metrics of a large model with more than 2¹⁷⁰⁰ possible states.

A BGP Attack Against Traffic Engineering
Jintae Kim, Steven Y Ko, and David M. Nicol (University of Illinois at Urbana-Champaign) and Xenofontas A. Dimitropoulos and George F. Riley (Georgia Institute of Technology)

Abstract:
As the Internet grows, traffic engineering has become a widely-used technique to control the flow of packets. For the inter-domain routing, traffic engineering relies on configurations of the Border Gateway Protocol (BGP). While it is recognized that the misconfiguration of BGP can cause negative effects on the Internet, we consider attack methods that disable traffic engineering regardless of the correctness of configurations. We focus on the redirection of traffic as our attack objective, and present attack scenarios on some dominant sample network topologies to achieve this objective. We also evaluate and validate these attacks using two different discrete-event simulators, one that models BGP behavior on a network, and another that emulates it using direct-execution of working BGP code.

Evaluation of Secure Peer-to-Peer Overlay Routing for Survivable SCADA Systems
Jeffrey J. Farris and David M. Nicol (University of Illinois at Urbana-Champaign)

Panel on Future Challenges in Modeling Methodology
Simon J.E. Taylor (Convener) (Brunel University), Peter Lendermann (Singapore Institute of Manufacturing Technology), Ray J. Paul (Brunel University), Steven W. Reichenthal (Boeing), Steffen Straßburger (Fraunhofer Institute for Factory Operation and Automation (Fraunhofer IFF)) and Stephen John Turner (Nanyang Technological University)

Abstract:
This panel paper presents the views of six researchers and practitioners of simulation modeling. Collectively we attempt to address a range of key future challenges to modeling methodology. It is hoped that the views of this paper, and the presentations made by the panelists at the 2004 Winter Simulation Conference will raise awareness and stimulate further discussion on the future of modeling methodology in areas such as modeling problems in business applications, human factors and geographically dispersed networks; rapid model development and maintenance; legacy modeling approaches; markup languages; virtual interactive process design and simulation; standards; and Grid computing.

Abstract:
We investigate factors affecting the performance of caching to speed up discrete event simulation. Walsh and Sirer have shown that a variant of function caching (staged simulation) can improve the performance of simulation in a networking application. However, the effectiveness of caching depends significantly on cache size, the cost of consulting the cache, the hit rate, and the cost of completing the computation in case of a cache miss. We hypothesize that adaptive techniques can be used to optimize caching parameters and demonstrate an adaptive scheme that decides whether to utilize caching depending on observed cache performance and event processing times. We focus on evaluating quantitative relationships, using our own caching implementation with the P-Hold synthetic workload application running on the GTW simulation kernel. Experiments show that as the cache size is increased, performance improves to a point, then degrades, and also that the adaptive technique can substantially improve speedup.

Approximate Time-Parallel Cache Simulation
Tobias Kiesling (Universität der Bundeswehr München)

Abstract:
In time-parallel simulation, the simulation time axis is decomposed into a number of slices which are assigned to parallel processes for concurrent simulation. Although a promising parallelization technique, it is difficult to be applied. Recently, using approximation with time-parallel simulation has been proposed to extend the class of suitable models and to improve the performance of existing models. In trace-driven cache simulation, sequences of memory requests are processed to determine the performance of variously sized caches. Time-parallel simulation has been applied to trace-driven cache simulation, but only with limited scalability of the parallel algorithm. In order to solve the scaling problem, this work uses approximation with time-parallel cache simulation. Although introducing an uncertainty in the results, the approximate algorithms work in a way that result accuracy increases monotonically with time, allowing a direct control of the quality of results. Experiments with a prototypical implementation indicate the viability of this approach.

Parallel Simulation of UAV Swarm Scenarios
Joshua J. Corner (Air Force Research Lab) and Gary B. Lamont (Air Force Institute of Technology)

Abstract:
The concept of operations for a micro-UAV system is adopted from nature from the appearance of ocking birds, movement of a school of fish, and swarming bees among others. This "emergent behavior" is the aggregate result of many simple interactions occurring within the ock, school, or swarm. Exploration of this emergent behavior in a swarm is accomplished through a high performance computing parallel discrete event simulation. After design of the system, several experiments are designed, tested, and analyzed for effciency and effectiveness.

Towards Adaptive Caching for Parallel and Discrete Event Simulation
Abhishek Chugh and Maria Hybinette (The University of Georgia)

Abstract:
Group behaviors, e.g. birds flocking, are widely used in virtual reality, computer games, robotics and artificial life. While many methods to simulate group behaviors have been proposed, these methods are usually applied to sequential computing. Since most of these methods have a polynomial complexity, it is difficult to simulate a large group in real-time using these methods. In this paper, we propose a parallel algorithm to simulate the flocking behavior of a large group. The new partitioning and communication mechanisms in the parallel algorithm make the flocking simulation more efficient. Experimental results show that the proposed parallel algorithm provides good speedup in generating flocking behaviors compared with the sequential simulation.

A Framework for Adaptive Synchronization of Distributed Simulations
Bertan Altuntas and Richard Allen Wysk (The Pennsylvania State University)

Abstract:
Increased complexity of simulation models and the related modeling needs for global supply chains have necessitated the execution of simulations on multiple processors. While distributed simulation promises reduced complexity (as the result of decomposition), increased parallelism and con-venient analysis of geographically distributed systems, it poses a challenging problem: synchronizing the distributed simulation federates. This paper discusses a new discrete event distributed simulation framework, which is designed with two goals in mind: (1) easy and fast development of distributed simulations and (2) efficient adaptive synchro-nization of simulation processes. This research uses state machine models for the automated synthesis of so called ‘local synchronization agents’ and an adaptive synchroni-zation algorithm has been developed based on pacing of simulation processes using real-time. Upon completion, this scalable framework is expected to shorten the lead-time to develop distributed simulation systems with rea-sonable performance characteristics.

An Automatic Distributed Simulation Environment
Sarita Mazzini Bruschi, Regina Helena Carlucci Santana, Marcos José Santana, and Thais Souza Aiza (Universidade de São Paulo)

Abstract:
Developing a sequential simulation program is not an easy task. Developing a distributed simulation program is harder than a sequential one because it is necessary to deal with mapping physical processes into logical processes, communication and synchronization problems and learn another simulation language/library. In literature, several simulation environments can be found but the great number are for sequential simulation, not using all the advantages of a distributed/parallel platform. This paper presents ASDA, an automatic distributed simulation environment that aims at providing several possibilities to users developing a distributed simulation. The automatic word can be understood in three diferent ways: the environment automatically generates a distributed simulation program code; the environment can automatically choose one distributed simulation approach; and the environment can automatically convert a sequential simulation program into a distributed simulation program using the MRIP (Multiple Replication in Parallel) approach.

Parallel Simulation of Group Behaviors
Bo Zhou and Suiping Zhou (Nanyang Technological University)

Abstract:
Distributed simulation cloning technology is designed to analyze alternative scenarios of a distributed simulation concurrently within the same execution session. The goal is to optimize the execution time for evaluating different scenarios by avoiding repeated computation. In terms of High Level Architecture (HLA) based simulations, a federate may make clones to explore different scenarios at decision points. It is desirable to use an incremental cloning mechanism to replicate only those federates whose states will be affected. This paper discusses the theory and issues involved in incremental distributed simulation cloning, which employs an event checking algorithm to ensure accurate sharing and initiates cloning only when absolutely necessary. Experiments have been performed to compare the performance of entire cloning and incremental cloning mechanisms. The experimental results indicate that cloning technologies can effectively reduce the time of executing multiple scenarios, and the incremental cloning mechanism significantly surpasses entire cloning in execution efficiency.

Exploiting Temporal Uncertainty in Process-Oriented Distributed Simulations
Margaret L. Loper and Richard M. Fujimoto (Georgia Institute of Technology)

Abstract:
Existing research has defined a new type of simulation time called Approximate Time, where the simulation’s knowledge about the values that represent time is uncertain. The approach is based on temporal uncertainty and uses time intervals rather than precise time values to represent time. Simulation language constructs are necessary to provide a convenient means of exploiting the temporal uncertainty to simulation modelers. To address this problem, a new time advance primitive for process-oriented simulations was developed, termed the Interval Hold construct. Interval Hold is an extension of the well-known hold primitive used in conventional simulation languages. This paper defines the interval time advance primitive and describes an algorithm for implementing it.

Controlling Over-Optimism in Time-Warp Via CPU-Based Flow Control
Vinay Sachdev, Maria Hybinette, and Eileen Kraemer (University of Georgia)

Abstract:
In standard optimistic parallel event simulation, no restriction exists on the maximum lag in simulation time between the fastest and slowest logical processes (LPs). Over-optimistic applications exhibit a large lag, which encour-ages rollback and may degrade performance. We investi-gate an approach for controlling over-optimism that classi-fies LPs as FAST, MEDIUM, or SLOW and migrates FAST and/or SLOW processes. FAST LPs are aggregated, forcing them to compete for CPU cycles. SLOW LPs are dispersed, to limit their competition for CPU cycles. The approach was implemented on distributed Georgia Tech Time Warp(GTW)(Das et al. 1994) and experiments per-formed using the synthetic application P-Hold(Fujimoto 1990). For over-optimistic test cases, our approach was found to perform 1.25 to 2.75 times better than the stan-dard approach in terms of useful work and to exhibit exe-cution times shorter than or equal to the standard computa-tion.

Incremental HLA-Based Distributed Simulation Cloning
Dan Chen, Stephen John Turner, and Wentong Cai (Nanyang Technological University) and Boon Ping Gan and Malcolm Yoke Hean Low (Singapore Institute of Manufacturing Technology)

Abstract:
The labor intensive aspects of simulation development and maintenance make exploration of reuse essential. However, reuse is generally difficult to achieve in practice due to inflexible assumptions and changing requirements. This paper discusses a technology for simulation reuse called COERCE and the visualization tools that this technology requires. COERCE addresses techniques to make simulations more flexible (coercibility) and the process of transforming a simulation to meet new objectives (coercion). We address the following question: Given that COERCE is a semi-automated technology, what visualization capabilities are necessary to support it? We address this question empirically by studying the role of visualization in the construction of a new coercible simulation and in the coercion of an existing example simulation. Based on this study, we propose a set of requirements for any visualization toolkit meant to support COERCE.

Abstract:
We present a conceptual framework for validating reusable behavioral models. The setting for this work is a modern product development environment in which design is per-formed by teams of specialists that collaborate through model reuse. The various modes of model reuse separate validation-relevant knowledge from the tasks for which it is needed. To enable efficient and effective transfer of this knowledge to the tasks for which it is needed, we propose a framework for validating reusable behavioral models based on formal representations of validation-relevant knowledge. The framework defines the abstract knowledge representation as well as an abstract process for applying this knowledge to validate reusable behavioral models. Although this framework is not a complete solution to the validation problem in design, it forms a foundation for understanding and solving the problem and represents a starting point for future investigation.

Approximating Component Selection
Michael Roy Fox, David C. Brogan, and Paul F. Reynolds Jr. (University of Virginia)

Abstract:
Simulation composability is a difficult capability to achieve due to the challenges of creating components, selecting combinations of components, and integrating the selected components. We address the second of these challenges through analysis of Component Selection (CS), the NP-complete process of selecting a minimal set of components to satisfy a set of objectives. Due to the high order of computational complexity of CS, we examine approximating solutions that make the CS process practicable. We define two variations of CS and prove that good approximations to optimal solutions result from applying a standard Greedy selection algorithm to each. Despite our creation of approximable variations of CS, we conjecture that any proof of the inapproximability of CS will reveal theoretical limitations of its practicality. We conclude that reasonably constrained variations of CS can be solved satisfactorily, and efficiently, but more general cases appear to never be solvable in a similar manner.

Visualizing Coercible Simulations
Joseph C. Carnahan, Paul F. Reynolds Jr., and David C. Brogan (University of Virginia)

Foundations of Validating Reusable Behavioral Models in Engineering Design Problems
Richard J. Malak, Jr. and Christiaan J. J. Paredis (Georgia Institute of Technology)