Abstract

National audience; Multiprotocol Label Switching (MPLS) is experiencing a growing interest mainly due to the flexible support of traffic engineering and Quality of Service (QoS). The efficient routing of Label Switched Paths (LSP) is an active research field where Constraint-Based Routing (CBR) appears to be a major building block. CBR can be seen as the decision entity that calculates the explicit paths for LSPs. The path calculation process can be constrained by different criteria, such as QoS requirements and particularly bandwidth guarantees considered in this paper. Special attention has been given to on-line solutions for CBR that process LSP establishment demands on the fly without any information on future demands. Currently, many proposals are formulated for CBR algorithms for bandwidth guaranteed tunnels, often compared to prove the effectiveness of one method over another. Nevertheless, no coherent evaluation has been clearly established for the general CBR problem, pointing out the different trade-offs involved in many solutions. In this article, we investigate the different objectives of CBR algorithms. We establish clear and general criteria for these algorithms, namely: reducing blocking probability, minimizing network costs, and load balancing. An effort of classification is made in order to map existing proposals to the proposed criteria. The study, performed to evaluate the influence of these parameters with simulations, shows the drawbacks of partial considerations, and the need for a global solution. Finally, we propose an integrating solution that encompasses the different criteria presented in the paper.