Shirt a Phobia

Sample Page

In queueing theory, a discipline within applied probability, the flow-equivalent server method (also known as flow-equivalent aggregation,[1] Norton’s theorem for queueing networks, or the Chandy–Herzog–Woo method[2]) is a divide-and-conquer technique for analyzing product-form queueing networks. In plain terms, it simplifies a complicated network of queues by replacing one part of the network with a single artificial server that behaves the same from the outside: for each possible number of customers inside that part of the system, the artificial server is given the same throughput as the part it replaces.

More formally, the method replaces a sub-network with a single load-dependent service center whose service-rate function reproduces the throughput of the original sub-network as a function of the population it contains; the remaining network is then solved with the aggregated server in place of the sub-network.[2][3][4]

The technique is named for the analogy with Norton’s theorem in electrical-circuit analysis, in which a portion of a circuit is replaced by an equivalent source whose terminal behavior matches the original.[3] For closed product-form networks, including networks in the BCMP class, the construction is exact for the product-form quantities represented by the aggregation; for non-product-form networks, it is an approximation whose accuracy depends on how closely a single load-dependent server can summarize the throughput behavior of the aggregated sub-network.[2][4][1]

The method was introduced by K. Mani Chandy, Ulrich Herzog, and Lin S. Woo in 1975 and has been applied to performance modeling of computer systems and communication networks.[2][4][3] A related technique, Marie’s algorithm, extends the aggregation idea to networks outside the product-form class.[5]

History

The method was introduced by K. Mani Chandy, Ulrich Herzog, and Lin S. Woo in a 1975 article in the IBM Journal of Research and Development titled “Parametric Analysis of Queuing Networks”.[2] The paper showed that a closed product-form queueing network can be analyzed by repeatedly aggregating sub-networks, and that the aggregation step is exact when the network satisfies BCMP-class assumptions.[2] The connection with Norton’s theorem in electrical-circuit analysis was made explicit in subsequent textbook treatments, and the term Norton’s theorem for queueing networks became established in performance-modeling textbooks.[3][4]

The construction was extended to other classes of networks and to approximate methods in subsequent decades. Casale gave conditions for the stability of flow-equivalent aggregation in closed networks in 2008.[1]

Method

In its basic form the method partitions a closed product-form queueing network into two complementary sub-networks. The aggregate sub-network is studied in isolation under a short-circuit modification in which customers leaving the sub-network return to it immediately; this construction lets the throughput of the sub-network be expressed as a function of the number of customers it currently holds.[2][3] The other sub-network is then analyzed with the aggregate replaced by a single load-dependent service center whose service rate at population n equals the previously computed throughput function evaluated at n.[3][4]

The procedure can be applied recursively, decomposing a large network into smaller sub-networks and rebuilding the global solution from local analyses. The computational benefit is that the recursion replaces the analysis of one large state space with several smaller analyses; for product-form networks this can reduce the computational cost of mean value analysis and convolution algorithms without sacrificing exactness.[4]

For product-form networks, the Chandy–Herzog–Woo construction preserves the product-form solution for the portion of the network represented after aggregation. For networks that violate BCMP assumptions, the aggregation introduces an error because a single load-dependent server cannot in general capture the joint dependence of throughput on multiple state variables of the original sub-network; the resulting solution is therefore an approximation.[4][1]

Mathematical formulation

For the basic single-class case, consider a closed product-form queueing network with a fixed customer population N. Let A be the sub-network to be aggregated, and let n denote the number of customers currently inside A, where 0 ≤ n ≤ N. In the flow-equivalent construction, A is analyzed in isolation after its external outputs are short-circuited back to its inputs. Let

XA(n)

be the steady-state throughput of this isolated sub-network when it contains n customers.

The sub-network A is then replaced in the original network by a single load-dependent service center whose service rate at population n is

μA(n) = XA(n).

From the point of view of the rest of the network, the aggregated server completes work at the same rate as the original sub-network would have released customers when it contained n customers. For product-form networks satisfying the assumptions of the Chandy–Herzog–Woo construction, replacing A by this load-dependent center preserves the product-form solution for the aggregated model.[2][3][4] In approximate applications, the same definition is used as a modelling assumption even when the original sub-network is not product-form; in that case, the equivalent server matches the chosen throughput function but need not preserve the full behavior of the hidden sub-network.

A related approach is Marie’s algorithm, in which sub-networks are analyzed under state-dependent Poisson process arrivals rather than the closed short-circuit construction. Marie’s method extends flow-equivalent ideas to networks that do not satisfy product-form assumptions and is used in approximate analysis of general queueing networks.[5][6]

Other techniques in the same family include hierarchical decomposition combined with mean value analysis, fixed-point approximations for non-product-form networks, and aggregation–disaggregation methods for large Markov chains.[4][1]

Applications

Flow-equivalent aggregation is used in performance modeling of computer systems and communication networks, particularly for hierarchical models that combine many components.[4][3] Examples include models of multiprogrammed computer systems in which input–output and processing subsystems are aggregated separately, and models of telecommunications networks that combine many switching elements into a single equivalent component for tractable analysis.[3]

See also

References

  1. ^ a b c d e Casale, Giuliano (2008). “A note on stable flow-equivalent aggregation in closed networks”. Queueing Systems. 60 (3–4): 193–202. doi:10.1007/s11134-008-9093-6. hdl:10044/1/18300.
  2. ^ a b c d e f g h Chandy, K. Mani; Herzog, Ulrich; Woo, Lin S. (1975). “Parametric Analysis of Queuing Networks”. IBM Journal of Research and Development. 19 (1): 36–42. doi:10.1147/rd.191.0036.
  3. ^ a b c d e f g h i Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. pp. 249–254. ISBN 978-0-201-54419-0.
  4. ^ a b c d e f g h i j Lazowska, Edward D.; Zahorjan, John; Graham, G. Scott; Sevcik, Kenneth C. (1984). Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice-Hall. ISBN 978-0-13-746975-8. Archived from the original on February 19, 2026. Retrieved May 15, 2026.
  5. ^ a b Marie, Raymond A. (1979). “An Approximate Analytical Method for General Queueing Networks”. IEEE Transactions on Software Engineering. SE-5 (5): 530–538. doi:10.1109/TSE.1979.234214.
  6. ^ Marie, Raymond A. (1980). “Calculating equilibrium probabilities for λ(n)/Ck/1/N queues”. ACM SIGMETRICS Performance Evaluation Review. 9 (2): 117. doi:10.1145/1009375.806155.