Achieving maximum throughput with a minimum number of label switched paths in MPLS networks

MPLS (multi-protocol label switching) networks allow multiple LSPs (label-switched paths) be established from a source to a destination to satisfy throughput required by an application. Given a MPLS network, where each link is associated with a maximum available bandwidth, a fundamental traffic engineering problem is how we can find minimum number of paths to achieve the maximum throughput. Optimally solving this problem can save huge amount of valuable network resources including available label space and reduce management complexity. This paper proves that finding a minimal number of LSPs is an NP-hard problem. To deal with this problem, we have studied four approximation algorithms. We found from simulations that the average number of paths produced by all these algorithms grows quite slowly when the network grows large. Moreover, the two algorithms, topological-sort-based maximum-path algorithm and greedy-based maximum-edge algorithm perform better than other algorithms. Between these two algorithms, the greedy-based maximum-edge algorithm is more time-efficient while keeps comparable performance.