A conceptual modeling framework for discrete event simulation using hierarchical control structures

Conceptual Modeling (CM) is a fundamental step in a simulation project. Nevertheless, it is only recently that structured approaches towards the definition and formulation of conceptual models have gained importance in the Discrete Event Simulation (DES) community. As a consequence, frameworks and guidelines for applying CM to DES have emerged and discussion of CM for DES is increasing. However, both the organization of model-components and the identification of behavior and system control from standard CM approaches have shortcomings that limit CM’s applicability to DES. Therefore, we discuss the different aspects of previous CM frameworks and identify their limitations. Further, we present the Hierarchical Control Conceptual Modeling framework that pays more attention to the identification of a models’ system behavior, control policies and dispatching routines and their structured representation within a conceptual model. The framework guides the user step-by-step through the modeling process and is illustrated by a worked example.     

Asynchronous parallel discrete event simulation

Complex models may have model components distributed over a network and generally require significant execution times. The field of parallel and distributed simulation has grown over the past fifteen years to accommodate the need of simulating the complex models using a distributed versus sequential method. In particular, asynchronous parallel discrete event simulation (PDES) has been widely studied, and yet we envision greater acceptance of this methodology as more readers are exposed to PDES introductions that carefully integrate real-world applications. With this in mind, we present two key methodologies (conservative and optimistic) which have been adopted as solutions to PDES systems. We discuss PDES terminology and methodology under the umbrella of the personal communications services application     

Modelling complex manufacturing systems using discrete event simulation

This paper presents an approach in simulating complex manufacturing systems. The approach is founded on developing several general purpose simulation generators for an assembly station, a manufacturing cell, and an inventory transfer function. These simulation generators can then be linked together to create a model of a complex manufacturing system. A typical manufacturing system is modelled using these simulation generators and the results summarized.     

A context-based object-oriented application framework for discrete event simulation

Applying object-oriented programming (OOP) to construct simulation programs has gained momentum in the research community. Major research efforts involved with object-oriented paradigm adopted in discrete-event simulation are reviewed in this paper, along with a simulation application framework proposed which provides special reusability mechanisms. This object-oriented simulation framework consists of three object elements, that is, model, service and scheduler. The relations and interactions among these elements are also demonstrated. In addition, the abstraction of a model under such a framework is reached by a special concept and implementation, referred to as the simulation context. Each simulation context is used to model a component sub-system, e.g. the control or physical flows of a manufacturing system. A practical system, CSIMT+ +, is also developed to validate the feasibility of such a simulation application framework. Furthermore, various forms of application models based on this framework are also illustrated.     

A fixed point approach to parallel discrete event simulation

Discrete event simulation is viewed as solving a fixed point problem whose unknowns are infinite histories or streams of event and time information. Stream domains provide two notions of convergence, which correspond to the usual categorization of simulation methods. Metric convergence leads to optimistic parallel simulation (the classic event list mechanism turns out to be a specialization), and convergence in the sense of partial orders leads to conservative parallel simulation.     

基于乐观策略的并行离散事件模拟研究

并行离散事件模拟（PDES）又称分布式模拟,通过将一个离散事件模拟程序在多个处理器上并行执行来提高模拟性能。乐观策略在解决并行模拟中各模拟部分之间的同步关系时具有较好的性能。介绍了基于乐观策略的并行离散事件模拟的原理,讨论了存在的问题,并给出相应的解决方法。     

A framework for adaptive collective communications for heterogeneous hierarchical computing systems

Collective communication operations are widely used in MPI applications and play an important role in their performance. However, the network heterogeneity inherent to grid environments represent a great challenge to develop efficient high performance computing applications. In this work we propose a generic framework based on communication models and adaptive techniques for dealing with collective communication patterns on grid platforms. Toward this goal, we address the hierarchical organization of the grid, selecting the most efficient communication algorithms at each network level. Our framework is also adaptive to grid load dynamics since it considers transient network characteristics for dividing the nodes into clusters. Our experiments with the broadcast operation on a real-grid setup indicate that an adaptive framework allows significant performance improvements on MPI collective communications.     

Control of discrete event systems modeled as hierarchical statemachines

Discrete-event systems (DESs) are systems in which state changes take place in response to events that occur discretely, asynchronously, and often nondeterministically. A class of DESs modeled as hierarchical state machines (HSMs), a special case of the statecharts formalism introduced recently, is considered. An efficient algorithm is provided for solving reachability problems in the HSM framework. It utilizes the hierarchical structure of HSMs. This efficient solution is used extensively in control applications, where controllers achieving a desired behavior are synthesized online     

A framework for real-time discrete event control

The TTM/RTTL (timed transition model with real-time temporal logic) framework is presented for modeling, specifying, and analyzing real-time discrete-event systems. TTMs are used to represent the process of the plant and its controller. RTTL is the assertion language for specifying plant behavior and verifying that a controller satisfies the specification. The framework adapts features from the program verification literature which are useful for posing problems of interest to the control engineer, such as modular synthesis and design. Examples are used to illustrate the ideas presented. The authors' published analytical results are summarized and referenced     

Event rates and aggregation in hierarchical discrete event systems

A discrete event system (DES) is a dynamical system whose evolution in time develops as the result of the occurrence of physical events at possibly irregular time intervals. Although many DES's operation is asynchronous, others have dynamics which depend on a clock or some other complex timing schedule. Here we provide a formal representation of the advancement of time for logical DES via interpretations of time. We show that the interpretations of time along with a timing structure provide a framework to study principles of the advancement of time for hierarchical DES (HDES). In particular, it is shown that for a wide class of HDES the event rate is higher for DES at the lower levels of the hierarchy than at the higher levels of the hierarchy. Relationships between event rate and event aggregation are shown. We define a measure for event aggregation and show that there exists an inverse relationship between the amount of event aggregation and the event rate at any two successive levels in a class of HDES. Next, we study how to design the timing structure to ensure that there will be a decrease in the event rate (by some constant factor) between any two levels of a wide class of HDES. It is shown that if the communications between the various DES in the HDES satisfy a certain admissibility condition then there will be a decrease in the event rate. These results for HDES constitute the main results of this paper, since they provide the first mathematical characterization of the relationship between event aggregation and event rates of the HDES and show how to design the interconnections in a HDES to achieve event rate reduction. Several examples are provided to illustrate the results.The authors gratefully acknowledge the partial support of the Jet Propulsion Laboratory. Please address all correspondence to K. Passino (email: passino@eagle.eng.ohio-state.edu).     

A survey of challenges in modelling and decision-making for discrete event logistics systems

In this paper, we consider discrete event logistics systems (DELS). DELS are networks of resources through which material flow. They have been the subject of a large body of analytic research. A huge variety of specific models exists that generally require application by model and/or solution experts to answer narrowly-defined logistics questions about inventory, sourcing, scheduling, routing, etc. It has, however, proven difficult to integrate these models in any comprehensive way into information systems for logistics because of the lack of conceptual alignment between the models produced by researchers and the information systems deployed in practice with which they should be integrated. In this paper, we systematically identify several challenges for DELS research. We analyse the root of the difficulties for applying academic research results in DELS, and indicate some potential future research directions.     

并行离散事件模拟的同步机制研究

逻辑模拟在设计新系统的过程中起着重要作用,通过计算机进行模拟可以实时反馈输出结果,及早发现潜在的问题,进而缩短设计周期,降低研发成本。并行离散事件模拟通过分散计算量到并行机或者网络的多个节点来减少模拟时间,被视为解决模拟速度问题的有效途径。在影响模拟性能的因素中,各并行子系统之间的同步问题是直接影响并行性能的关键因素之一。探讨了并行离散事件模拟的同步机制,介绍了其基本原理、特点及存在的问题,并阐述了可能的改进方法。     

Generating non-standard random distributions for discrete event simulation systems

This paper introduces a novel method for generating non-standard random distributions. These distributions are required when the system cannot be modelled accurately using conventional probabilistic distributions. In the proposed method, the desired random distribution is built by splitting the density function into smaller segments which are individually approximated with simple polynomial functions. Then, the inverse transformation method is used to form the final random distribution function. This paper presents also new criteria for expediting the selection of the correct segment. The complexity of the proposed process for segment selection is O(log M), where M is the number of segments. An example of the application of the proposed method to simulation of disk access patterns for performance evaluation of computer systems is provided.     

Domain-specific discrete event modelling and simulation using graph transformation

Graph transformation is being increasingly used to express the semantics of domain-specific visual languages since its graphical nature makes rules intuitive. However, many application domains require an explicit handling of time to accurately represent the behaviour of a real system and to obtain useful simulation metrics to measure throughputs, utilization times and average delays. Inspired by the vast knowledge and experience accumulated by the discrete event simulation community, we propose a novel way of adding explicit time to graph transformation rules. In particular, we take the event scheduling discrete simulation world view and provide rules with the ability to schedule the occurrence of other rules in the future. Hence, our work combines standard, efficient techniques for discrete event simulation (based on the handling of a future event set) and the intuitive, visual nature of graph transformation. Moreover, we show how our formalism can be used to give semantics to other timed approaches and provide an implementation on top of the rewriting logic system Maude.     

Predicting the behavior of large scale P2P systems by parallel discrete event simulation

P2P systems are becoming the dominator of Internet.Such systems are typically composed of thousands to millions of physical computers,which make it difficult to predict their behaviors without a large scale distributed system simulator.This paper is an attempt to predict the behavior of large scale P2P systems by building a novel parallel simulator:AegeanSim,which provides parallel discrete event simulation of such systems on high performance server clusters.We abstract the execution of P2P applications wit...     

A hierarchical hybrid framework for modelling anomalous behaviours

The presence of anomalies in collected information, i.e. data that deviates substantially from what is normally expected, is a valuable source of knowledge and its discovery has many practical applications. Anomaly-detection approaches rely on building models that suitably describe data patterns deemed as normal, however they may incur the generation of a considerable amount of false positives. Signature-based techniques, which exploit a prior knowledge base of anomalous patterns, are able to effectively detect them but fail in identifying anomalies which did not occur previously. Hybrid anomaly detection systems combine the two approaches in order to obtain better detection performances. This paper proposes a framework, called HALF, that allows to develop hybrid systems by combining available techniques, coming from both approaches. HALF is able to operate on any data type and provides native support to online learning, or concept drifting. This enables the incremental updating of the knowledge bases used by the techniques. HALF has been designed to accommodate multiple mining algorithms by organizing them in a hierarchical structure in order to offer an higher and flexible detection capability. The framework effectiveness is demonstrated through two case studies concerning a network intrusion detection system and a steganography hunting system.     

Robust and adaptive supervisory control of discrete event systems

Both robust and adaptive supervisory control in discrete-event systems are discussed. It is assumed that the system G to be controlled is not known exactly. It is only known either that it belongs to a set or that it has certain lower and upper bounds. The task of robust supervision is to synthesize a supervisor that realizes a given desired behavior for all possible G. A necessary and sufficient condition for the existence of such a robust supervisor is derived. Based on this condition, a robust supervisory control and observation problem of synthesizing a robust supervisor whose behavior is both legal and acceptable is solved. Adaptive supervision is discussed. As the system progresses, the information on occurrences of events may help to resolve or reduce uncertainties     

A hierarchical framework for evaluating simulation software

In simulation software selection problems, packages are evaluated either on their own merits or in comparison with other packages. In either method, a comprehensive list of criteria for evaluation of simulation software is essential for proper selection. Although various simulation software evaluation checklists do exist, there are differences in the lists provided and the terminologies used. This paper presents a hierarchical framework for simulation software evaluation consisting of seven main groups and several subgroups. An explanation for each criterion is provided and an analysis of the usability of the proposed framework is further discussed.     

On controllability of discrete event systems in a behavioral framework

The purpose of this paper is to investigate the controllability and the achievability of discrete event systems within a behavioral framework. Based on the notion of Willems’ behavioral controllability [1, 2], we introduce a new concept related to the controllability of discrete event systems. By using the controllability proposed here and the notion related to achievable behaviors [3, 4], we show that the behavioral controllability for a given specification with respect to language is equivalent to the existence of a controller, so that an interconnected system satisfies the specification exactly. A proposed controller here is represented by the intersection of the behavior of a given plant and that of a given (controllable) specification. We also clarify that our controllers for a given specification fit the properties of well-known supervisory controllers proposed and developed by Ramadge and Wonham [5]. The text was submitted by the authors in English.