An efficient algorithm for global path optimization in multiprotocol label switching networks

This paper proposes an algorithm to solve the optimization of label switched paths (LSPs) in multiprotocol label switching (MPLS) networks. The underlying optimization problem in this task is the well-known unsplittable multicommodity flow problem equipped with practically relevant objective functions and specialized with hard technical requirements. The proposed heuristic algorithm is based on network flow theory. It incorporates iterative shortest path search and performs adaptive edge weight adjustments in order to successfully satisfy all the required traffic demands and to maximize user-defined objectives. The robust algorithm facilitates the incorporation of several strategic and optimization objectives and the fulfillment of certain hard technical requirements of the largest problem domain as well. Novel features of the approach include a new adaptive path allocation/deallocation strategy based on the identification of bottleneck links, demand ordering and preprocessing phases, and a systematic path allocation control method. The efficiency of the method is empirically shown on randomly generated networks with practical sizes and topologies, and on a real-world IP (Internet Protocol) backbone network. The algorithm is able to successfully solve difficult problem instances comprising very large instances with 1000 nodes, 3500 edges and 999000 traffic demands. The computational tests demonstrate that the proposed approach can be efficiently applied to solve problem instances that embed MPLS specific hard technical requirements. Furthermore, it is shown that our algorithm offers significantly better performance than the straightforward adaptations of existing methods that were developed for related network optimization problems. Namely, our algorithm produces acceptable results quicker, it can solve problems that were not previously solvable, and it yields better results than the alternative methods. The extensive empirical tests demonstrate the combinatorial properties of the target problem and the performance aspects of the algorithm and its components as well.