Fixed point approximation for multirate multihop loss networks with state-dependent routing

• Published in: IEEE/ACM transactions on networking 2004-04, Vol.12 (2), p.361-374
• Main Authors: Mingyan Liu, Baras, J.S.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Approximation algorithms; Approximation error; Bandwidth; Bandwidths; Computational complexity; Computational modeling; Computer networks; Fixed points (mathematics); Mathematical analysis; Mathematical models; Measurement; Network topologies; Network topology; Networks; Routing; Routing (telecommunications); Simulation; Spread spectrum communication; Studies; Telecommunication traffic; Traffic flow
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2004.826248

In this paper we consider a class of loss networks that have arbitrary topologies and routes of arbitrary length. Multiple traffic classes are present, each with different bandwidth requirement, and each routed according to a state-dependent routing scheme. In particular, we consider the least loaded routing method generalized to routes of arbitrary number of hops. The connection level performance metric of interest is the end-to-end blocking probability. We are interested in developing fast evaluation methods to provide reasonably accurate estimates of the blocking probability, especially under heavy traffic load. Our algorithms are based on the fixed-point method framework, also known as the reduced load approximation. In addition to what commonly examined by previous work, two more factors contribute to the complexity of the computation in the scenario under consideration in this paper. One is the state-dependent nature of the routing mechanism, the other is the possible overlapping between routes due to the general multihop topology of the network. We present two fast approximation algorithms to evaluate the blocking probability with state-dependent routing by simplifying the route overlapping computation. We discuss the computational complexity of our algorithms as well as sources of approximation error. We then compare the numerical results with that of simulation and show that our algorithms provide fairly accurate blocking probability estimates especially under heavy traffic load.