A regular scalable fault tolerant interconnection network for distributed processing

Bounded degree networks like deBruijn graphs or wrapped butterfly networks are very important from VLSI implementation point of view as well as for applications where the computing nodes in the interconnection networks can have only a fixed number of I/O ports. One basic drawback of these networks is that they cannot provide a desired level of fault tolerance because of the bounded degree of the nodes. On the other hand, networks like hypercube (where degree of a node grows with the size of a network) can provide the desired fault tolerance but the design of a node becomes problematic for large networks. In their attempt to combine the best of the both worlds, authors in [IEEE Transactions on Parallel and Distributed Systems 4(9) (1993) 962] proposed hyper-deBruijn (HD) networks that have many additional features of logarithmic diameter, partitionability, embedding, etc. But, HD networks are not regular, are not optimally fault tolerant and the optimal routing is relatively complex. Our purpose in the present paper is to extend the concepts used in the above-mentioned reference to propose a new family of scalable network graphs that retain all the good features of HD networks and at the same time are regular and maximally fault tolerant; the optimal point to point routing algorithm is significantly simpler than that of the HD networks. We have developed some new interesting results on wrapped butterfly networks in the process.     

Modeling discrete event systems with state-dependent deterministic service times

In this paper extensions to the numerical solution method of deterministic and stochastic Petri nets (DSPNs) are introduced in order to cope with deterministic transitions with marking-dependent firing delays. The basic idea lies in scaling each row of the generator matrix of the Markov chain subordinated to a deterministic transition with marking-dependent firing delay by the delay value corresponding to this marking. Computational formulas of this solution method are implemented in the software package DSPNexpress which completely automates the solution process of DSPNs. The extended modeling power of DSPNs is illustrated by a single-server queuing system with Poisson arrivals, degradable deterministic service requirements, and finite capacity. Christoph Lindemann was supported by the Federal Ministry for Research and Technology of Germany (BMFT) and by the German Research Council (DFG) under grants ITR9003 and Ho 1257/2-1, respectively. Reinhard German was supported by Siemens Corporate Research and Development and by a doctoral fellowship from the German Research Council (DFG) under grant Ho 1257/1-2.     

Modeling physical systems using finite element Cell-DEVS

We propose a method to analyze complex physical systems using two-dimensional Cell-DEVS models. These problems are usually modeled with one or more Partial Differential Equations and solved using numerical methods. Our goal is to improve the definition of such problems by mapping them into the Cell-DEVS formalism, which permits easy integration with models defined with other formalisms, and its definition using advanced modeling and simulation tools. To show this, we used two methods for solving PDEs, and deduced the updating rules for their mapping to Cell-DEVS. As our simulation results show, the accuracy of the Cell-DEVS solution is the same of these previous methods, showing that we can use Cell-DEVS as a tool to obtain numerical solution for systems of PDEs. Simultaneously, this method provides us with a simpler mechanism for model definition, automated parallelism, and faster execution.     

CD++: a toolkit to develop DEVS models

The features of a toolkit for modeling and simulation based on the DEVS formalism are presented. The tool is built as a set of independent software pieces running on different platforms. Not only are the main characteristics of the environment presented, a focus on its use is also considered by inclusion of application examples for a variety of problems. Many models can be defined in an automated fashion, simplifying the construction of new models and easing their verification. The use of this formal approach has allowed the development of safe and cost‐effective simulations, significantly reducing development time. Copyright © 2002 John Wiley & Sons, Ltd.     

Throughput-coverage tradeoff in a scalable wireless mesh network

The wireless mesh network (WMN) is an economical and low-power solution to support ubiquitous broadband services. However, mesh networks face scalability and throughput bottleneck issues as the coverage and the number of users increase. Specifically, if the coverage is extended by multiple hops, the repeatedly relayed traffic will exhaust the radio resource and degrade user throughput. Meanwhile, as the traffic increases because of more users, the throughput bottleneck will occur at the users close to the gateway. The contention collisions among these busy users near the gateway will further reduce user throughput. In this paper, a newly proposed scalable multi-channel ring-based WMN is employed. Under the ring-based cell structure, multi-channel frequency planning is used to reduce the number of contending users at each hop and overcome the throughput bottleneck issue, thereby making the system more scalable to accommodate more users and facilitate coverage extension. This paper mainly focuses on investigating the overall tradeoffs between user throughput and cell coverage in the ring-based WMN. An analytical throughput model is developed for the ring-based WMN using the carrier sense multiple access (CSMA) medium access control (MAC) protocol. In the analysis, we also develop a bulk-arrival semi-Markov queueing model to describe user behavior in a non-saturation condition. On top of the developed analytical model, a mixed-integer nonlinear optimization problem is formulated, aiming to maximize cell coverage and capacity. Applying this optimization approach, we can obtain the optimal number of rings and the associated ring widths of the ring-based WMN.     

Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems

Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete graphical dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also address other problems that deal with the time evolution of such stochastic dynamical systems. Further, we point out the implications of our results to problems for other computational models such as Hopfield networks, communicating finite state machines and systolic arrays. In particular, our polynomial time algorithms for the predecessor existence problem for stochastic dynamical systems imply similar results for one-dimensional finite cellular automata.     

Generation of candidates' tree for the fault diagnosis of discrete event systems

This paper presents a discrete event model-based approach for Fault Detection and Isolation of manufacturing systems. This approach considers a system as a set of independent Plant Elements (PEs). Each PE is composed of a set of interrelated Parts of Plant (PoPs) modeled by a Moore automaton. Each PoP model is only aware of its local behavior. The degraded and faulty behaviors are added to each PoP model in order to obtain extended PoP ones. An extrapolation of Gaussian learning is realized to obtain acceptable temporal intervals between the time occurrences of correlated events. Finally based on the PoP extended models and the links between them, a fault candidates' tree is established for each plant element. This candidates' tree corresponds to a local on-line fault event occurrence observer, called diagnoser. Thus, the diagnosis decision is distributed on each plant element. An application example is used to illustrate the approach.     

An optimal effective controller for discrete event systems

An approach to the online synthesis of an optimal effective controller for discrete event systems is presented. The optimal effective controller can achieve the prescribed (cumulative) effectiveness measure while minimizing the total cost incurred for the execution of events. This approach is constructed over a generalized control framework for automata‐based discrete event systems, which allows event enforcement in addition to the (original) event disablement/enablement as the control mechanism. The optimal effective control policy generated by this approach is proved to be the least restrictive among all the possible optimal effective control policies for the given online expansion tree of the system behavior. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

非线性DEDS的标准结构

非线性DEDS是指由极大极小函数描述的系统, 常见于计算机科学、控制论、运筹学等领域, 考虑非自治非线性DEDS的结构问题, 通过引入白色图和凝白色图, 得到了系统能达和能观的两个充要条件以及系统的标准结构, 同时还给出了它们的矩阵表示.     

离散混沌网络系统中共同噪声诱导同步的条件

噪声普遍存在于各种真实系统和人造系统中,它对系统的同步动力学具有多重影响.本文探索外部噪声对高维离散复杂网络系统同步行为的积极作用.首先构建外部共同噪声驱动下两个参数相同、未耦合的离散混沌网络模型,然后利用Birkhoff遍历定理与矩阵论等相关理论,严格证明了噪声诱导两个离散混沌网络系统取得同步的充分条件,进一步借助于具体的混沌网络模型,利用数值仿真验证了理论分析的有效性.数值模拟的结果表明当网络模型参数满足理论分析的充分条件时,共同噪声可以诱导两个参数相同、未耦合的离散混沌网络在随机意义下取得同步,而且同步效果不依赖于复杂网络拓扑结构的选取.     

卫星网络建模与分布式仿真

卫星网络仿真是对卫星网络进行优化设计、性能分析、效能评估的有效途径.针对卫星网络的组成结构和运行特点,建立了卫星网络的节点模型、结构模型、链路模型和通信模型.在此基础上,基于HLA/RTI体系设计并实现了分布式卫星网络仿真系统,详细给出了各联邦成员的设计.该仿真系统通过编辑想定方案可灵活部署网络结构并能仿真星间、星地链路的通信过程,为仿真验证面向应用的卫星网络理论研究成果提供了一个通用的支撑平台.最后给出了一个3GEO 15MEO想定场景下的仿真结果,验证了模型的正确性和有效性.     

异步电动机的建模仿真方法研究

随着我国经济的不断发展,我国的各种工业都在不断发展,工厂数量也在不断的增加,这样电动机就成为了工厂发展的重要影响因素之一,众所周知,电动机是工厂内最普遍和最重要的电气设备,电动机运行的是否稳定也影响着工厂工作是否顺利,但是在异步电动机的运行过程中也存在着一些不足问题,例如异步电动机“存在的”的问题,异步电动机“存在的”是指系统的电量过低或者是电压过低,导致电量无法与机器顺利联通,导致电动机工作运行出现问题,这样就会给电动机设备带来很大程度的损坏,电动机一旦发生“存在的”问题,就会给工厂的运行带来很大的不便,包括很大的经济损失。因此,本人就电动机的建模仿真方法为基础,进行一些分析,并最终提出一些可行性的建议。     

A new approach to the analysis of discrete event dynamic systems

We present a new, time domain approach to the study of discrete event dynamical systems (DEDS), typified by queueing networks and production systems. A general state-space representation is developed and perturbation analysis is carried out. Observation of a single sample realization of such a system can be used to predict behavior over other sample realizations, when some parameter is perturbed, without having to make additional observations. Conditions under which this is always possible are investigated and explicit results for some special cases are included.     

Parallel discrete event simulation with SIMULA

The area of Discrete Event Simulation (DES) is the least impacted by parallel processing even though most of its applications require tremendous amounts of processing time. The common approach of parallelizing individually special purpose programs leads to very limited improvements in performance. We propose here the parallelization of general DES applications written in SIMULA, as a part of an ongoing project that aims towards developing methodologies and architectures for parallel DES. SIMULA is a general purpose process oriented language whose structure allows the creation of processes which can participate in a quasi-parallel execution according to an interleaved fashion. Problems related to the process interference representation, parallel scheduling and process synchronization are defined and solved. To test and verify the theoretical results the parallel execution of experimental and real DES applications has been simulated. The results show that significant improvement in performance can be expected.     

Modeling and control of drug assignment for pharmaceutical cabinets using discrete event systems approaches

The public health sector, considered to be vital, especially in this pandemic crisis of COVID-19, requires automation and control of drug distribution in pharmacies commonly called: “Dispensing.” In this paper, we address the medication assignment problem for automated dispensing cabinets (ADCs). First, we use a network of conflicting timed event graphs (CTEGs), a class of timed Petri nets with shared resources, to model pharmaceutical cabinets. Second, we develop a new method for controlling CTEGs under mutual exclusion constraints (MECs) to solve the problem of drug assignment, using a control approach based on Min-Plus algebra. Finally, a case study of assigning drugs is given to illustrate the proposed methodology and show the efficiency of the developed control laws.     

Queueing network software for systems modelling

Several requirements are placed on queueing models of computer systems. These include credibility, accuracy, timeliness and cost. Modelling software can have critical impact on all of these requirements. We survey the characteristics of major pieces of queueing software. Based on this survey we synthesize a set of design objectives for queueing software. Finally, we discuss our own queueing network software, the Research Queueing Package (RESQ), in light of these objectives.     

可扩展建模与仿真框架的候选标准和运作模式

军用建模与仿真领域存在许多问题,而Web技术已经在信息技术领域取得了前所未有的成功,如何将Web技术应用于建模与仿真领域,正是可扩展建模与仿真框架要解决的问题.文章介绍了可扩展建模与仿真框架的背景,描述了这个框架的定义,分析了用于构建这个框架的若干候选标准,包括元建模和模型驱动架构、可扩展的三维图形、Web服务、语义Web、覆盖组播、仿真参考标记语言、基本对象模型和概要文件标准等,重点研究了如何基于这些标准构建可扩展建模与仿真框架,接着讨论了用于描述如何使用这个框架的运作模式,最后进行了简要的总结并对这一领域当前存在的问题给出了自己的看法.     

A discrete event systems approach to network fault management: detection and diagnosis of faults

An important aspect of network management is fault management, which involves, detecting, locating, isolating, correcting and adapting to faults in the network. We study modeling of communication network protocol and fault detection, identification and localization in the discrete event system diagnosis framework. As an illustration of the approach, normal and faulty behavior of the X.25 network protocol is modeled as a finite state machine. This modeling formalism allows the utilization of discrete event system analysis for the detection and diagnosis of faults. Our approach provides a systematic way of performing fault diagnosis for network fault management. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

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...     

IEEE 802.11无线局域网OPNET建模与性能测试

讨论了IEEE802．11无线局域网的建模和性能问题。基于对IEEE802．11协议和目前功能最强大的网络仿真工具OPNET软件的研究。首先分析了无线局域网的各种行为,分别对这些行为单独建模后,通过有线状态机将它们集成而形成IEEE802．11协议支持模块。给出了模型输入输出接口的详细说明。并对网络的性能进行了分析比较。