Fast network re-optimization schemes for MPLS and optical networks

This paper presents algorithms for re-optimizing network routing in connection-oriented networks such as Multi-Protocol Label Switched (MPLS) networks. The objective in re-optimization is to allow the network to carry more traffic without adding capacity. The need for re-optimization arises because of dynamic connection routing where connections, such as bandwidth guaranteed Label Switched Paths (LSPs) in MPLS networks, are routed as they arrive one-by-one to the network. Continual dynamic routing leads to network inefficiencies due to the limited information available for routing and due to simple path selection algorithms often used to satisfy connection set-up time constraints. We present a re-optimization scheme, where the re-optimizer constantly monitors the network to determine if re-optimization will lead to sufficient network efficiency benefits. When sufficient benefits can be obtained, the re-optimizer computes the least cost set of connections which must be re-routed to attain the necessary network efficiency and then computes the routes for the connections to be re-routed. We develop efficient re-optimization algorithms and demonstrate by simulations that several network performance metrics are significantly improved by re-optimization. (c) 2005 Elsevier B.V. All rights reserved.