A preemption-aware on-line routing algorithm for MPLS networks

In the context of Multiprotocol Label Switching (MPLS), we look at the problem of organizing the mapping of Label Switched Paths (LSPs) in an optimal way throughout the network on the basis of a given objective function. This problem is highly combinatorial and makes dynamic and real-time features a difficult issue for any LSP routing scheme. For this reason, we propose a computationally efficient, though approximate, on-line scheme adapted to an incremental optimization of the network state. We also propose an integration of a computationally efficient preemption mechanism into this approximation. The efficiency of this algorithm is obtained through a very rigid but seemingly appropriate policy concerning which LSPs are appropriate for preemption. A feedback from preemption on the routing process is proposed, in order to regulate the rate of the reroutings and to tune the balance between stability and continuous reorganization in a network.