MPLS Traffic Engineering Using Enhanced Minimum Interference Routing: AN Approach Based on Lexicographic Max-Flow

The main contribution of this paper is a new algorithm for dynamic routing of bandwidth guaranteed tunnels. The algorithm is a generalization of the "minimum-interference" based algorithm presented in [6]. The routing objective is to satisfy as many potential future requests as possible in an environment where requests arrive one-by-one, and there is no knowledge of future arrivals other than their potential ingress-egress points. An application of these algorithms is for the routing of MPLS bandwidth-guaranteed label-switched paths (LSPs). The presented algorithm performs better than the scheme presented in [6], and other previously proposed algorithms, on several metrics like the number of rejected demands and successful re-routing of demands upon link failure. Also, the new algorithm is more robust in performance to implementations where most requests are routed with a shortest-path computation, and the computations required for determining "minimum-interference" are performed only infrequently.