Flow-equivalent server method

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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.