Computational Algorithms for Closed Queueing Networks with Exponential Servers

Computational Algorithms for Closed Queueing Networks with Exponential Servers

September 1973 | Jeffrey P. Buzen
This paper presents computational algorithms for computing the equilibrium distribution of customers in closed queueing networks with exponential servers. The algorithms are based on two-dimensional iterative techniques that are efficient and simple to implement. The paper derives expressions for various marginal distributions and discusses implementation considerations such as storage allocation and order of evaluation. A closed queueing network consists of M service facilities and N circulating customers. The state of the network is described by a vector (n₁, n₂, ..., nₘ), where nᵢ is the number of customers at the ith facility. The service time for a customer at the ith facility is exponentially distributed with mean 1/μᵢ. The probability that a customer will proceed to the jth facility after completing service at the ith facility is pᵢⱼ. The equilibrium distribution of customers in the network is given by P(n₁, n₂, ..., nₘ) = 1/G(N) * ∏(Xᵢⁿᵢ), where (X₁, X₂, ..., Xₘ) is a real positive solution to the eigenvector-like equations μⱼXⱼ = ∑μᵢXᵢpᵢⱼ and G(N) is a normalizing constant. Expressions for marginal distributions are derived, including the probability that there are exactly k customers at the ith facility. These expressions are used to compute expected values and other network characteristics. The paper also discusses the computation of G(N), which involves a simple iterative algorithm that computes G(1), G(2), ..., G(N) using N·M multiplications and additions. The paper also considers networks with load-dependent servers, where the service time for a customer depends on the number of customers present. In this case, the equilibrium distribution is given by P(n₁, n₂, ..., nₘ) = 1/G(N) * ∏[(Xᵢⁿᵢ)/Aᵢ(nᵢ)], where Aᵢ(k) is a function of the load-dependent service time. The computation of G(N) in this case is more complex and involves a different iterative algorithm. The paper also discusses the use of queueing network models for analyzing multiprogrammed computer systems. The central server model is used to study the behavior of fixed partition systems operating under a constant backlog. The model is analyzed using techniques from Jackson and Gordon and Newell. The paper also discusses the use of queueing network models for studying issues such as optimal load balancing for peripheral processors, the trade-off between fault rate and level of multiprogramming in virtual memory systems, and the trade-off between buffer size and level of multiprogramming for certain types of I/O devices.This paper presents computational algorithms for computing the equilibrium distribution of customers in closed queueing networks with exponential servers. The algorithms are based on two-dimensional iterative techniques that are efficient and simple to implement. The paper derives expressions for various marginal distributions and discusses implementation considerations such as storage allocation and order of evaluation. A closed queueing network consists of M service facilities and N circulating customers. The state of the network is described by a vector (n₁, n₂, ..., nₘ), where nᵢ is the number of customers at the ith facility. The service time for a customer at the ith facility is exponentially distributed with mean 1/μᵢ. The probability that a customer will proceed to the jth facility after completing service at the ith facility is pᵢⱼ. The equilibrium distribution of customers in the network is given by P(n₁, n₂, ..., nₘ) = 1/G(N) * ∏(Xᵢⁿᵢ), where (X₁, X₂, ..., Xₘ) is a real positive solution to the eigenvector-like equations μⱼXⱼ = ∑μᵢXᵢpᵢⱼ and G(N) is a normalizing constant. Expressions for marginal distributions are derived, including the probability that there are exactly k customers at the ith facility. These expressions are used to compute expected values and other network characteristics. The paper also discusses the computation of G(N), which involves a simple iterative algorithm that computes G(1), G(2), ..., G(N) using N·M multiplications and additions. The paper also considers networks with load-dependent servers, where the service time for a customer depends on the number of customers present. In this case, the equilibrium distribution is given by P(n₁, n₂, ..., nₘ) = 1/G(N) * ∏[(Xᵢⁿᵢ)/Aᵢ(nᵢ)], where Aᵢ(k) is a function of the load-dependent service time. The computation of G(N) in this case is more complex and involves a different iterative algorithm. The paper also discusses the use of queueing network models for analyzing multiprogrammed computer systems. The central server model is used to study the behavior of fixed partition systems operating under a constant backlog. The model is analyzed using techniques from Jackson and Gordon and Newell. The paper also discusses the use of queueing network models for studying issues such as optimal load balancing for peripheral processors, the trade-off between fault rate and level of multiprogramming in virtual memory systems, and the trade-off between buffer size and level of multiprogramming for certain types of I/O devices.
Reach us at info@study.space
Understanding Computational algorithms for closed queueing networks with exponential servers