Monte Carlo Summation for Product-Form Loss Networks

We have repeatedly seen that performance measures for product-form loss networks take the form of simple functions of normalization constants. An effective method to calculate normalization constants therefore leads to an effective method to calculate performance measures. In Chapters 2 and 3 we presented efficient recursive and convolution algorithms to calculate normalization constants for stochastic knapsacks and generalized stochastic knapsacks. In Chapter 5 we presented efficient convolution algorithms for generalized tree and hierarchical tree networks. Nevertheless, calculating the normalization constant for arbitrary topologies is an NP-complete problem [102]. Many simple topologies — including the important star topology — appear to be particularly elusive for combinatorial approaches.