Creating multipoint-to-point LSPs for traffic engineering

MPLS has been proposed as an efficient mechanism for traffic engineering in networks to account for and utilize network resources properly. A fundamental problem in MPLS is to reduce the label space usage by label switched paths (LSPs), while meeting the requirements of the flows traversing the network. Use of multipoint-to-point LSP trees has been proposed as a technique to reduce label space usage. However, various aspects with respect to the creation and maintenance of multipoint-to-point LSPs have not gained sufficient attention. We address the problem of merging a given set of LSPs into a minimum number of multipoint-to-point trees. We show that the problem of optimal merging is NP-complete and propose a heuristic for merging. The effectiveness of the algorithm in both offline and online cases is shown by analysis and simulation on real world scenarios.