A randomized rounding heuristic to reroute tunnels in MPLS networks

In multi-protocol label switching (MPLS) networks, traffic demands can be routed along tunnels called label switched paths (LSPs). One tunnel is characterized by a path in the network and a reserved bandwidth. These tunnels can be created and deleted dynamically, depending on traffic demand arrivals or departures. After several operations of this type, the network resources utilization can be unsatisfactory, with for instance congestion or too long routing paths. One way to improve it is to reroute tunnels. Different rerouting procedures may be applied, breaking tunnels or using make-before-break. This has to be adapted to the LSP quality of service (QoS) requirements. Moreover, for network management purposes, we would like to control the number of rerouting operations to perform. A global rerouting framework is proposed, which enables to consider independently each class of LSPs. Then, a mathematical model is introduced. As it appears very hard to solve to optimality, a heuristic based on randomized rounding is proposed. Finally, the designed tool has enabled a numerical study on the proportion of tunnels to reroute in order to reach near-optimal network states.