Date Added: Aug 2009
Most network operators have considered reducing Label Switched Routers (LSR) label spaces (i.e. the number of labels that can be used) as a means of simplifying management of underlaying Virtual Private Networks (VPNs) and, hence, reducing Operational Expenditure (OPEX). This letter discusses the problem of reducing the label spaces in MultiProtocol Label Switched (MPLS) networks using label merging - better known as MultiPoint-to-Point (MP2P) connections. Because of its origins in IP, MP2P connections have been considered to have treeshapes with Label Switched Paths (LSP) as branches. Due to this fact, previous works by many authors affirm that the problem of minimizing the label space using MP2P in MPLS the MERGING PROBLEM cannot be solved optimally with a polynomial algorithm (NP-complete), since it involves a Harddecision Problem.