A new approach for scaling QoS routing algorithms

The paper studies the issue of scaling quality of service (QoS) routing algorithms to large-scale networks using partitioning. In particular, the paper focuses on a new approach which we call stochastic partitioning. We investigate the performance of this technique and develop an intelligent partitioning strategy that reduces the computational effort in routing, usually by orders of magnitude. The trade-off is an increase in QoS blocking probability (probability of failure to find a path that satisfies the QoS constraints). Finally, simulation results are produced which demonstrate the benefits and some practical limitations of stochastic partitioning.