Higher-order distributional properties in closed queueing networks

In many real-life computer and networking applications, the distributions of service times, or times between arrivals of requests, or both, can deviate significantly from the memoryless negative exponential distribution that underpins the product-form solution for queueing networks. Frequently, the coefficient of variation of the distributions encountered is well in excess of one, which would be its value for the exponential. For closed queueing networks with non-exponential servers there is no known general exact solution, and most, if not all, approximation methods attempt to account for the general service time distributions through their first two moments.We consider two simple closed queueing networks which we solve exactly using semi-numerical methods. These networks depart from the structure leading to a product-form solution only to the extent that the service time at a single node is non-exponential. We show that not only the coefficients of variation but also higher-order distributional properties can have an important effect on such customary steady-state performance measures as the mean number of customers at a resource or the resource utilization level in a closed network.Additionally, we examine the state that a request finds upon its arrival at a server, which is directly tied to the resulting quality of service. Although the well-known Arrival Theorem holds exactly only for product-form networks of queues, some approximation methods assume that it can be applied to a reasonable degree also in other closed queueing networks. We investigate the validity of this assumption in the two closed queueing models considered. Our results show that, even in the case when there is a single non-exponential server in the network, the state found upon arrival may be highly sensitive to higher-order properties of the service time distribution, beyond its mean and coefficient of variation.This dependence of mean numbers of customers at a server on higher-order distributional properties is in stark contrast with the situation in the familiar open M/G/1 queue. Thus, our results put into question virtually all traditional approximate solutions, which concentrate on the first two moments of service time distributions.     

Machine allocation algorithms for job shop manufacturing

In this paper we present algorithms for the solution of two server (machine) allocation problems that occur in manufacturing networks. The manufacturing network is modelled as an open network of queues with general interarrival time and service time distributions. The queueing network is analyzed by using the parametric decomposition method: a two-moment approximation scheme. The server allocation problems are solved by means of a marginal analysis scheme. Numerical results on two manufacturing networks are presented.     

Some Equivalence Results for Load-Independent Exponential Queueing Networks

In this paper we derive a number of results concerning the behavior of closed load-independent exponential queueing networks. It is shown that if the service rate of any station is increased (decreased), then the throughput of the network itself also increases (decreases). This is not true for product form networks in general. In addition, if the service rate at server i is increased then both the mean queue length and mean waiting time at server i decrease while both these quantities increase at all stations j ? i. The opposite effect is observed if the senrvice rate at station i is decreased. The main result of the paper is a proof of the conjective that corresponding to any general closed queueing network consisting of M stations and in which N customers circulate according to the elements of an irreducible stochastic routing matrix Q, there exists a closed load-independent exponential queueing network with the same M, N, and Q such that the mean number of customers at each station in the exponential network is equal to that in the general network. If the network throughput is specified, it is shown that this exponential network iS unique.     

MRE hierarchical decomposition of general queueing network models

Summary The principle of Minimum Relative Entropy (MRE), given fully decomposable subset and aggregate mean queue length, utilisation and flow-balance constraints, is used in conjunction with asymptotic connections to infinite capacity queues, to derive new analytic approximations for the conditional and marginal state probabilities of single class general closed queueing network models (QNMs) in the context of a multilevel variable aggregation scheme. The concept of subparallelism is applied to preserve the flow conservation and a universal MRE hierarchical decomposition algorithm is proposed for the approximate analysis of arbitrary closed queueing networks with single server queues and general service-times. Heuristic criteria towards an optimal coupling of network's units at each level of aggregation are suggested. As an illustration, the MRE algorithm is implemented iteratively by using the Generalised Exponential (GE) distributional model to approximate the service and asymptotic flow processes in the network. This algorithm captures the exact solution of separable queueing networks, while for general queueing networks it compares favourably against exact solutions and known approximations.This work is sponsored by the Science and Engineering Research Council (SERC), UK, under grant GR/F29271     

An approximate MVA algorithm for exponential, class-dependent multiple servers

Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms.     

Server allocation and routing in homogeneous queues with switchingpenalties

This paper considers a multiclass routing and server allocation problem in a queueing system of multiple stations in parallel with penalties for switching the server between stations. We proceed by dynamically ranking the queues so that if all arrivals ceased, switches of the server between queues would be maximally delayed by serving queues in order of rank. The main result of this paper shows that we may improve any policy by constructing a greedy version that routes arriving customers to the queue of highest acceptable rank and allocates the server to the queue of highest rank whenever it switches. We also establish analogous results for a variant of the problem that encourages fairness in server allocation by restricting attention to pseudocyclic policies which visit each queue periodically     

A parametric programming solution to the F-policy queue with fuzzy parameters

This paper investigates the F-policy queue using fuzzy parameters, in which the arrival rate, service rate, and start-up rate are all fuzzy numbers. The F-policy deals with the control of arrivals in a queueing system, in which the server requires a start-up time before allowing customers to enter. A crisp F-policy queueing system generalised to a fuzzy environment would be widely applicable; therefore, we apply the α-cuts approach and Zadeh's extension principle to transform fuzzy F-policy queues into a family of crisp F-policy queues. This study presents a mathematical programming approach applicable to the construction of membership functions for the expected number of customers in the system. Furthermore, we propose an efficient solution procedure to compute the membership function of the expected number of customers in the system under different levels of α. Finally, we give an example of the proposed system as applied to a case in the automotive industry to demonstrate its practicality.     

Throughput bounds for closed queueing networks

Analytical lower and upper bounds for the throughput of closed queueing networks with single and delay (infinite) servers are studied in this paper. The numerical evaluation of these bounds requires a small number of significant operations which is independent of the population N. This is in contrast to the exact computation of the throughput which requires at least O(N) operations as N tends to infinity. The bounds are given by simple closed-form analytical expressions and may be more suitable for various performance studies than the algorithmical form of the exact solution.In this paper, the previously known balanced-job bounds are generalized to networks containing delay servers (terminals) and a hierarchy of bounds is obtained for single and multiple class networks. For the single class network, further new bounds are derived: lower and upper bounds that require the evaluation of one square root and an upper bound that requires a constant number of exponentiations. This upper bound does not employ the balancing of server loadings and is especially useful for asymptotic analysis in the case of a large number of customers N.     

多层服务器集群容量规划启发方法研究

本文研究了多层服务器集群系统的容量规划问题,提出以吞吐优化为目标的增量式服务器资源配置算法SHISA.该方法基于闭环排队网络模型求解系统的稳态性能指标,利用请求队列长度、资源利用率及有效响应时间等启发信息指导服务器的增量配置过程.对不同启发信息下算法的求解能力进行了敏感性分析.     

Information theoretic analysis for a general queueing system at equilibrium with application to queues in tandem

Summary In this paper, information theoretic inference methology for system modeling is applied to estimate the probability distribution for the number of customers in a general, single server queueing system with infinite capacity utilized by an infinite customer population. Limited to knowledge of only the mean number of customers and system equilibrium, entropy maximization is used to obtain an approximation for the number of customers in the G¦ G¦1 queue. This maximum entropy approximation is exact for the case of G=M, i.e., the M¦M¦1 queue. Subject to both independent and dependent information, an estimate for the joint customer distribution for queueing systems in tandem is presented. Based on the simulation of two queues in tandem, numerical comparisons of the joint maximum entropy distribution is given. These results serve to establish the validity of the inference technique and as an introduction to information theoretic approximation to queueing networks.This work was supported under a Naval Research Laboratory Fellowship under Grant N00014-83G-0203 and under an ONR Grant N00014-84K-0614 Former address:Westinghouse Defense and Electronics Center, Baltimore, MD, USA     

Characteristics of optimal workload allocation for closed queueing networks

We consider the problem of allocating a given workload among the stations in a multi-server product-form closed queueing network to maximize the throughput. We first investigate properties of the throughput function and prove that it is pseudoconcave for some special cases. Some other characteristics of the optimal workload and its physical interpretation are also provided. We then develop two computational procedures to find the optimum workload allocation under the assumption that the throughput function is pseudoconcave in general. The primary advantage of assuming pseudoconcavity is that, under this assumption, satisfaction of first order necessary conditions is sufficient for optimality. Computational experience with these algorithms provides additional support for the validity of this assumption. Finally, we generalize the solution procedure to accommodate bounds on the workloads at each station.     

Asymptotic bounds of throughput in series-parallel queueing networks

We propose a piece-wise linear upper bound on the throughput rate from a network of series-parallel queues where arrivals occur through a single infinite queue. This bound is tight and is observed to be extremely accurate in forecasting the actual throughput rate. We also describe the monotonicity of throughput as a function of the arrival rate and specify a condition under which the upper bound may be computed. We approximate analytically the throughput measured as a function of the arrival rate for two tandem exponential queues, where the first queue has an infinite buffer while the second queue has a finite buffer. We extend this analysis to elementary split and merge queueing networks. We demonstrate the generality and robustness of this asymptotic property, for larger series-parallel networks with general service times and specify the set up of a single simulation experiment which can be used to retrieve the throughput for any arrival rate, as well as other networks performance measures.     

Optimal anticipative scheduling with asynchronous transmissionopportunities

Service is provided to a set of parallel queues by a single server. The service of queue i may be initiated only at certain time instances {t_nⁱ}_n=1^∞ that constitute the connectivity instances for queue i. The service of different customers cannot overlap. Scheduling is required to resolve potential contention of services initiated at closely spaced, closer than the service time, connectivity instances. At any time t, the future connectivity instances are available for scheduling. An anticipative policy is given, which at time t schedules the transmissions until a certain future time t+h. The length of the scheduling horizon h is selected based on the backlog at t. The allocation of the server in the interval [t, t+h], is done in accordance to the backlogs of the individual queues at t. The throughput region of the system is characterized, and it is shown that the policy we propose achieves maximum throughput. The policy has a low implementation complexity which is bounded for all the achievable throughput vectors. The average delay and the scheduling complexity are studied by simulation, and the trade-off between the two is demonstrated. The above scheduling problem arises in the access layer of the cross-links of a satellite network     

Approximate analysis of product-form type queueing networks with blocking and deadlock

A numerical procedure for analyzing exactly closed exponential queueing networks with finite queues is presented first. Due to the finiteness of these queues, blocking and deadlock may occur. Deadlocks are assumed to be detected and resolved instantaneously. The numerical procedure is then incorporated in an approximation algorithm for analyzing closed exponential queueing networks of the product-form type, in which some of the queues are finite. These finite queues are assumed to be linked together to form a single subnetwork. The approximation algorithm is based on a variant of Norton's theorem. Comparisons between the approximate results and exact numerical results were carried out and the relative error was observed to be small.     

Buffer allocation in general single-server queueing networks

The optimal buffer allocation in queueing network systems is a difficult stochastic, non-linear, integer mathematical programming problem. Moreover, the objective function, the constraints or both are usually not available in closed form, making the problem even harder. A good approximation for the performance measures is thus essential for a successful buffer allocation algorithm. A recently published two-moment approximation formula to obtain the optimal buffer allocation in general service time single queues is examined in detail, based on which a new algorithm is proposed for the buffer allocation in single-server general service time queueing networks. Computational results and simulation results are shown to evaluate the efficacy of the approach in generating optimal buffer allocation patterns.     

A delay model of queueing network system based on fuzzy sets theory

The goal of our research is the delay analysis of queueing model for data networks using fuzzy sets theory. We propose an fuzzification of M/M/1 queueing system. We also apply fuzzy sets theory to the open central server network model with the fuzzy queues. Thus, we represent the delay analysis and performance of open central server network model based on fuzzy sets theory.     

The stationary distribution invariance of states in a closed queueing network with temporarily non-active customers

A stationary functioning of a closed queueing network with temporarily non-active customers is analyzed. Non-active customers are located at network nodes in queues, being not serviced. For a customer, the feasibility of passing from its ordinary state to the temporarily non-active state (and backwards) is provided. Service times of customers at different nodes possess arbitrary distributions. Finally, the stationary distribution invariance of network states is established with respect to the functional form of customer service time distributions under fixed first-order moments.     

Approximate throughput analysis of cyclic queueing networks withfinite buffers

An approximation method for obtaining the throughput of cyclic queueing networks with blocking as a function of the number of customers in it is presented. The approximation method was developed for two different blocking mechanisms. It was also extended to the case of the central server model with blocking. Validation tests show that the algorithm is fairly accurate     

A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks

This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are block-structured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures can be calculated.Scope and purposeThe exact analysis of queueing networks with multiple servers at each workstation and finite capacities of the intermediate queues is extremely difficult as for even the case of exponential operation (service or processing) times the Markovian chain that models the system consists of a huge number of states which grows exponentially with the number of stations, the number of servers at each station and the queue capacity of each intermediate queue of the resulting system. The scope and purpose of the present paper is to analyze and provide a recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks. By applying the proposed algorithm one may create the transition matrix of a K-station queueing network for any K. This process allows one to obtain the exact solution of the resulting large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures of the system can be obtained.     

Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems

We consider a class of queueing networks referred to as "generalized constrained queueing networks" which form the basis of several different communication networks and information systems. These networks consist of a collection of queues such that only certain sets of queues can be concurrently served. Whenever a queue is served, the system receives a certain reward. Different rewards are obtained for serving different queues, and furthermore, the reward obtained for serving a queue depends on the set of concurrently served queues. We demonstrate that the dependence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specifically, maximizing the throughput is no longer equivalent to maximizing the stability region; we therefore need to maximize one subject to certain constraints on the other. Since stability is critical for bounding packet delays and buffer overflow, we focus on maximizing the throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random rewards and random scheduling constraints.