Diffusion approximation of a queueing network with a semi-Markov input

Diffusion approximation for queueing networks with a semi-Markov input is constructed. This approximation can be used in analysis and design of communication and computer networks.Translated from Kibernetika, No. 2, pp. 100–103, March–April, 1991.     

Diffusion approximation of open queueing networks with critical traffic levels

We consider an open Jackson network with a critical traffic level. The vector queueing process at the network nodes is shown to converge, with appropriate normalization, to a diffusion process with a reflecting boundary.Translated from Kibernetika, No. 4, pp. 90–96, July–August, 1989.     

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.     

An approximation method for a class of queueing systems

We consider a queueing system with an ordered hunt. Specifically, we consider a communication system in which messages arrive at a node that has n output links numbered 1,…,n, and an arriving message is processed by the lowest numbered idle link. Obtaining such steady-state parameters as the expected delay of an arbitrary message and the utilization factor of each link requires knowledge of the complete state space of the system and the solution of 2ⁿ linear equations. In this paper we develop a method of computing the approximate values of these parameters without the need for the knowledge of the complete state space and the solution of 2ⁿ linear equations.     

An approximation technique for central server queueing models with a priority dispatching rule

An approximation technique to solve central server queueing models with a priority dispatching rule is described in this paper. This technique reduces the problem size by aggregating I/O activities and combining different classes into a smaller number of classes, so that the reduced problem can be solved numerical examples considered, throughputs and mean CPU queue sizes calculated by the approximation differ from simulation results by less than 15 percent.     

A new MVA-based approximation for closed queueing networks with a preemptive priority server

We propose a new MVA-based noniterative algorithm for solving closed queueing network models of computer systems with a preemptive priority server. The algorithm attempts to capture synchronization error, delay error, and the effect of preemption on the interarrival time variability of lower priority jobs at FCFS servers. The principal feature of our approximation is that it attempts to capture the effects of preemption not only at the priority server, but also at other servers in the system. Numerical results indicate that the algorithm predicts the performance measures of low priority jobs more accurately than previously developed MVA-based algorithms.     

Diffusion approximation for a closed Jackson network

We investigate the asymptotic behavior of a vector queueing process in the Markov model of a closed queueing network. The number of jobs circulating in the network is assumed to increase without bound, while the processing rate at each node is directly proportional to the number of jobs at that node.Translated from Kibernetika, No. 1, pp. 30–33, January–February, 1989.     

Identification and approximation of queueing systems

A distance-measures approach to the problems of identification and approximation of queueing systems is presented. This approach combines ideas from statistical robustness, information-type measures, and parameter-continuity of stochastic processes.     

An analysis of an approximation algorithm for queueing networks

Queueing network models have proved to be useful aids in computer system performance prediction. Numerous approximation algorithms have been devised to allow queueing networks to be analyzed with a reduced computational expense. In particular, for separable queueing networks several popular iterative approximation algorithms are available.

One disadvantage of these algorithms has been the lack of results concerning their behavior, such as whether or not iteration convergence is guaranteed. This paper presents an analysis of an approximate MVA algorithm proposed by Schweitzer (1979). It is proved that the equations defining the algorithm have a unique solution when there is only a single customer class, and iteration initializations that yield monotonic convergence to this solution are exhibited. It is also proved that the solution is pessimistic relative to the exact queueing network solution.     

Filtering of a semi-Markov queueing system with retrials

A recursive differential equation for the conditional probability of the number of waiting customers is derived for the M_wrM|G|1 queue with continuous monitoring of the server state.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 169–173, July–August, 1991.     

Diffusion approximation for multiprogrammed computer systems

This paper presents results of diffusion approximations which may be used in the analysis of multiprogrammed computer systems. First of all we give a mathematical proof for the best CPU utilization under different priority rules in the case of one CPU and more DTU-s. With the help of the Brownian motion approximation we get an explicit result for a model considered by Gaver and Shedler in priority queues, without using the Wald identity. Some examples are given when the diffusion approximation is more complicated than the Brownian motion one.     

On a multiserver markovian queueing system with balking and reneging

In this paper a multi-server queueing model with balking and reneging is considered. Steady-state distribution of the number of customers in the system is obtained. An expression for the average loss of customers during a fixed duration of time is also advanced.     

Throughput bounding and simple approximation methods for exponential fork/join queueing networks with blocking

Exponential fork/join queueing networks (FJQNs) with finite buffers have been used as a major tool for evaluating the performances of manufacturing systems. In this study, we first suggest the throughput upper and lower bounds. Our upper-bounding method is elaborated on with general network configuration (acyclic configuration), while our lower bounds can be obtained only for networks with more specialized configuration. Next, developed is a simple approximation method for throughputs, which are based on decomposition/aggregation principles and structurally equivalent relations between different configurations.     

The queueing equivalence to a manufacturing system with failures

The authors consider optimal production rate control in a failure prone manufacturing system. It is well known that the hedging point policy is the optimum controller for such a system. They show that under the hedging point policy the system can be treated as an M/M/1 queue. Therefore, existing results in queuing theory can be readily applied to obtaining the steady-state probability density function of the production surplus, based on which the optimal hedging point policy can be computed. To a large extent, the approach is based on sample path analysis. It not only provides an alternative way to solve the problem but also reveals some interesting insights     

Application of optimal filtering methods for on-line of queueing network states

We show the solution to the optimal filtering problem for states of Markov jump processes by observations of multivariant point processes. A characteristic feature of observations is that their compensators are random linear functions of the system state, and the composite “state–observations” process does not possess the Markov property. The provided optimal filtering estimate is expressed via the solution of some recurrent system of linear differential equations and algebraic relations. We present examples of using theoretical results to construct typical models of real queueing networks. We establish the connections between our new optimal filtering algorithm and classical results of Kalman–Bucy and Wonham. We propose a solution for the problem of estimating the current state of a UDP connection given the observations of video stream.     

A tandem queueing system with priorities

A system ofN unlimited queues andN time-discrete servers in series, is investigated. The input consists ofN stochastic processes where requests which have been generated according to thei-th process leave the system after they have received serivice by servers 1, 2, ...,i. The holding-time distributions can be calculated by means of an equivalence theorem which holds under certain conditions for the service times.     

Single-server queueing system with time and information redundancy

A queueing system with an unreliable server characterized by three types of failures is considered.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 163–176, September–October, 1991.