Analysis of delay distributions in CDMA mobile switching system

In this paper, we propose a seemingly efficient method computing delay distributions in CDMA mobile switching system. The proposed method is based on queueing network modeling and GPH(generalized phase-type) semi-Markov chain analysis. The class of GPH distributions has several properties which can be applied conveniently for computational purposes. The basic methodology adopted in delay analysis for switching system is explained step by step. Application results are given to demonstrate the accuracy of the method and to verify that the system meets the requirements for delay. The proposed method seems to be very useful to analyze delay distributions in communication systems including switching system.     

Modelling knowledge and action in distributed systems

We present a formal model that captures the subtle interaction between knowledge and action in distributed systems. We view a distributed system as a set ofruns, where a run is a function from time toglobal states and a global state is a tuple consisting of anenvironment state and alocal state for earch process in the system. This model is a generalization of those used in many previous papers.Actions in this model are associated with functions from global states to global states. Aprotocol is a function from local states to actions. We extend the standard notion of a protocol by definingknowledge-based protocols, ones in which a process' actions may depend explicitly on its knowledge. Knowledge-based protocols provide a natural way of describing how actions should take place in a distributed system. Finally, we show how the notion of one protocolimplementing another can be captured in our model. Joseph Y. Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School, in Ghana. After a year as a visiting scientist at MIT, he joined IBM in 1982. He is currently the manager of the Mathematics and Related Computer Science Department at the IBM Almaden Research Center, and a consulting professor in the Computer Science Department at Stanford. His major research interests are reasoning about knowledge, distributed computation, and logics of programs. He was program chairman and organizer of the first conference of Theoretical Aspects of Reasoning About Knowledge, program chairman of the Fifth ACM Symposium on Principles of Distributed Computing, and was the co-recipient (with Ronald Fagin) of the MIT Publisher's Prize for the Best Paper Paper at the 1985 International Joint Conference on Artificial Intelligence. Ronald Fagin is manager of the Foundations of Computer Science group at the IBM Almaden Research Center. He received his B.A. degree in mathematics from Dartmouth College in 1967 and his Ph.D. in mathematics, specializing in mathematical logic, from the University of California at Berkeley in 1973. He joined IBM in 1973 at the Thomas J. Watson Research Center. In 1975, he transferred to the San Jose Research Laboratory (now the IBM Almaden Research Center) where most of his research has centered on applications of logic to computer science. In particular, he has done research on the theory of relational databases and, more recently, on theories of knowledge and belief. He has received three IBM Outstanding Innovation Awards for his contributions to relational database theory, extendible hashing, and reasoning about knowledge. He was co-recipient (with Joe Halpern) of the MIT Press Publisher's Prize for the Best Paper at the 1985 International Joint Conference on Artificial Interlligence.Some material in this paper appeared in preliminary form in Halpern and Fagin (1985). An abridged version of the paper appeared in Vogt F (ed) Proceeding of Concurrency 88 (Lecture Notes in Computer Science Vol. 335) Springer-Verlag, 1988, pp 18–32     

Mean-delay approximation for cyclic-service queueing systems

This paper investigates mean delays in a single-server queueing model with cyclic service. An approximate analysis is performed for an arbitrary number of queues, constant switch-over time, exhaustive service discipline, Poisson arrival processes, and general service-time distributions. Neither inter-arrival nor service-time distributions have to be identical for the different queues. A major value of our approximation lies in the simplicity of its numerical evaluation for an arbitrary number of queues and any traffic pattern. Extensive comparisons with simulation results show the high accuracy of the approximation over a wide range of parameters.     

Mission reliability of an automatic control system integrated with distributed intelligent built-in-test systems

This paper introduces distributed-centralized Built-in-Test (BIT) systems interfaced with an automatic control system with the purpose of improving mission reliability. By Using a block diagramming method, a complicated system is decomposed into mutually exclusive subsystems so that a distributed BIT is connected to each subsystem for multiple parallel processing of fault direction. The data produced by the distributed BITs is sent to a central control processor. We present a Markov process approach to analytically derive the mission reliability of an automatic control fault-tolerant system with distributed BITs. As diagnostic mistakes of the BIT, the false alarm and fault missing of BIT are considered with the malfunction of the BIT itself. Numerical examples are also prepared to evaluate the performance of distributed intelligent BITs, by comparing mission reliabilities corresponding to the variation of design parameters in a time domain.     

Performance analysis of an integrated hybrid-switched multiplex structure

The performance of an integrated voice/data hybrid-switched multiplex structure is analyzed. The approach is based on an imbedded two-dimensional Markov chain associated with the voice and data queueing processes, which accounts for their interaction. Using generating functions, a method for determining exactly the average data delay is given. As an application, an analytical expression for the average data delay is derived for the so-called single channel case. These results should be considered primarily as a theoretical contribution since the numerical difficulties involved in the solution procedure for the general case are formidable.     

Analysis of a replicated data base

In this paper we study the performance characteristics of a replicated data base under two different updating policies. In the synchronous case requests for any replications of the data base can be processed only if no copies of data base are being updated due to a previous write request, whereas in the non-synchronous case read requests are allowed to be processed at any time if there is a free data base copy. We formulate a queueing theoretic model of the system assuming a Poisson arrival process for both read and write requests. This model is then solved using the matrix geometric solution method and the relevant performance metrics are derived and analyzed.     

Stability analysis of systems with stochastically varying delays

A stability analysis of linear systems with stochastically varying delay is performed. It is assumed that the delay function has the form of a sawtooth with switches occurring at the arrival times of a homogeneous Poisson process. Several notions of stochastic stability are considered and corresponding stability criteria are derived. For two examples the different criteria are compared and the effect on stability of various deterministic approximations is examined.     

Approximate techniques for modeling the performance of complex systems

This survey paper discusses a variety of approximate technique for analyzing and predicting the performance of complex systems, such as computer networks. Such techniques tend to the more readily usable by the persons in charge of design, development, selection, or tuning of such systems than the great majority of the techniques available in the current literature. The discussion is motivated by the author's experience in industry for nine years, during which time he saw numerous instances where performance models gave good results when they were applied in situations where a large number of the assumptions made in developing the models were demonstrably false. These results have motivated him to study the current literature on performance modeling to find out why such models work as well as they do. This has led to the results discussed here.A large portion of the paper is a survey of some of the most interesting techniques for approximately modeling system performance that have been developed recently, along with some theoretical developments which indicate why highly simplified models often work surprisingly well. Since it is rare to find situations where the assumptions made in developing models are really valid, simplified models are normally as accurate as more elaborate models. A few examples of successful use of approximate models are discussed next. The paper concludes with a summary of the most important principles developed and an indication of some of the approaches to approximate modeling which the author feels merit further research.     

Patient flow modelling and performance analysis of healthcare delivery processes in hospitals: A review and reflections

Analysis of hospital processes is essential for development of improved methods, policies and decision tools for overall performance improvement of the hospital system. Amidst the current scenario of continuously increasing healthcare costs and scarcity of resources, optimal utilization of resources without hampering the quality of care has gained importance in any country. Modelling, analysis and management of patient flows, in this context, plays a key role in performance analysis and improvement of hospital processes as appropriate modelling of patient flows may help healthcare managers make decisions related to capacity planning, resource allocation and scheduling, appointment scheduling and for making necessary changes in the process of care. The concept of patient flow and its modelling has gained much attention in healthcare management literature over past few decades. In this paper, the existing approaches pertaining to modelling of patient flows in hospital systems have been classified and critically appraised focussing on the recent advancements in order to identify future research avenues. A generic framework for patient flow modelling and performance analysis of hospital systems that may serve as a guide for the practitioners dealing with similar kinds of problems to improve healthcare delivery has also been provided.     

Error detection and diagnosis for fault tolerance in distributed systems

The early error detection and the understanding of the nature and conditions of an error occurrence can be useful to make an effective and efficient recovery in distributed systems. Various distributed system extensions were introduced for the implementation of fault tolerance in distributed software systems. These extensions rely mainly on the exchange of contextual information appended to every transmitted application specific message. Ideally, this information should be used for checkpointing, error detection, diagnosis and recovery should a transient failure occur later during the distributed program execution. In this paper, we present a generalized extension suitable for fault-tolerant distributed systems such as communication software systems and its detection capabilities are shown. Our extension is based on the execution of message validity test prior to the transmission of messages and the piggybacking of contextual information to facilitate the detection and diagnosis of transient faults in the distributed system.     

Stability analysis of neutral systems with distributed delays

The stability of neutral systems with distributed delays is investigated in this paper. A modified Lyapunov-Krasovskii functional is constructed to study this class of systems. The proposed stability criterion is discrete-, distributed- and neutral-delay-dependent. In addition, by this method one can study the case when the coefficient matrix of the neutral delay term is time-varying uncertain. The reduced conservatism is illustrated in a numerical example.     

多Agent的供应链分布式仿真系统设计与实现

供应链是由供应商、制造商、仓库、配送中心和渠道商等构成的物流网络。并且供应链已经为社会带来了巨大的经济效益,本文就多Agent的供应链分布式仿真系统设计做了详细的研究,以便其能够很快的得到实现。     

On some queueing models of time division multiple access communication system

In this paper we consider a general queueing model for a time division multiple access communication channel and establish the relationship between the steady-state probability distribution of the number of packets in the buffer at various observation epochs. These results are derived using the theory of embedded Markov chain and discrete state level crossing analysis. We also provide a table describing the relationship between the results given here and the results available in the literature.     

A note on the use of the Lambert W function in the stability analysis of time-delay systems

The Lambert W function is defined to be the multivalued inverse of the function w→we^w=z. This function has been used in an extremely wide variety of applications, including the stability analysis of fractional-order as well as integer-order time-delay systems. The latter application is based on taking the mth power and/or nth root of the transcendental characteristic equation (TCE) and representing the roots of the derived TCE(s) in terms of W functions. In this note, we re-examine such an application of using the Lambert W function through actually computing the root distributions of the derived TCEs of some chosen orders. It is found that the rightmost root of the original TCE is not necessarily a principal branch Lambert W function solution, and that a derived TCE obtained by taking the mth power of the original TCE introduces superfluous roots to the system. With these observations, some deficiencies displayed in the literature (Chen, Y. Q., & Moore, K. L. (2002a). Analytical stability bound for delayed second-order systems with repeating poles using Lambert W function. Automatica, 38(5), 891-895, Chen, Y. Q., & Moore, K. L. (2002b). Analytical stability bound for a class of delayed fractional-order dynamic systems. Nonlinear Dynamics, 29(1-4), 191-200) are pointed out. Moreover, we clarify the correct use of Lambert W function to stability analysis of a class of time-delay systems. This will actually enlarge the application scope of the Lambert W function, which is becoming a standard library function for various commercial symbolic software packages, to time-delay systems.     

Mean-value analysis and convolution method for queue-dependent servers in closed queueing networks

In this paper, we formulate a recursive relation for the marginal probabilities of a closed network with K customers in terms of the same network with K ? 1 customers. Mean-value analysis (MVA) is an application of this relation, together with Little's formula. It is shown that the convolution method, too, can be based on the same recursive result. This leads to a new convolution algorithm called normalized convolution algorithm (NCA), which like MVA works entirely with probabilities and throughputs rather than with quantities such as normalization contacts. NCA avoids a difficult problem, the occurrence of floating-point over-flows in the original convolution algorithm.We shall also solve a numerical stability problem found in MVA. Finally, we show how MVA and the convolution algorithm can be combined in the same problem to yield a hybrid method retaining the best properties of both methods.     

Performance analysis of an M/G/1 queueing system under Bernoulli vacation schedules with server setup and close down periods

This paper is concerned with the analysis of a single server queueing system subject to Bernoulli vacation schedules with server setup and close down periods. An explicit expression for the probability generating function of the number of customers present in the system is obtained by using imbedded Markov chain technique. The steady state probabilities of no customer in the system at the end of vacation termination epoch and a service completion epoch are derived. The mean number of customers served during a service period and the mean number of customers in the system at an arbitrary epoch are investigated under steady state. Further, the Laplace-Stieltjes transform of the waiting time distribution and its corresponding mean are studied. Numerical results are provided to illustrate the effect of system parameters on the performance measures.     

On the propagation of updates in distributed replicated systems

We analyse the performance and dependability of protocols which implement ‘sequence consistency’ in distributed replicated systems. Sites send messages to each other from time to time, passing information about the update requests that have been received. The recipient of a message is chosen according to some probability distribution which may depend on the sender. The random variables of main interest are (a) the interval between receiving an update request and being able to execute it on the original site, subject to the consistency requirement, and (b) the time it takes to bring all sites to a consistent state after the arrival of an update.     

Modelling for flexible manufacturing systems and structural properties of optimal work routing policy

We consider flexible manufacturing systems (FMSs) which are composed of a set of workstations linked together with a material handling system (MHS). Each workstation consists of an input buffer, a single machine and an output buffer. The MHS consisting of a single cart routes work among the workstations according to the process paths required by the work. We deal with an optimal control problem in this FMS. We model the FMS as a closed queueing network. In the model, the cart routes the work to the workstations in accordance with a Markov routing with exponentially distributed routing time, and the machines process work with exponentially distributed processing time. An objective is to find a work routing policy that maximizes the total expected reward earned by operating machines. This optimal control problem is formulated as an undiscounted semi-Markov decision process. Structural properties of an optimal policy are analysed. Moreover, a sufficient condition is derived for the optimal policy to be of control limit type. An example is given to illustrate the result.     

Delay and resource analysis in MANETs in presence of throwboxes

This paper addresses the delay analysis and resource consumption in mobile ad hoc networks (MANETs) equipped with throwboxes. Throwboxes are stationary, wireless devices that act as relays, and that are deployed to increase the connectivity between mobile nodes. Our objective is to quantify the impact of adding throwboxes on the performance of two routing protocols, namely the Multicopy Two-hop Routing protocol and the Epidemic Routing protocol, in the cases where the throwboxes are fully disconnected or mesh connected. To this end, we use a Markovian model where the successive meeting times between any pair of mobile nodes (resp. any mobile node and any throwbox) are represented by a Poisson process with intensity λ (resp. μ). We derive closed-form expressions for the distribution of the delivery delay of a packet and for the distribution of the total number of copies of a packet that are generated, the latter metric reflecting the overhead induced by the routing protocol. These results are then compared to simulation results. Through a mean-field approach we also provide asymptotic results when the number of nodes (mobile nodes and/or throwboxes) is large.