Combined link dimensioning and weight assignment of minimum weight routing networks

MPLS (multi-protocol label switching) technology provides the flexibility required for managing the way the traffic is routed through the network. However, label switched path (LSP) configuring is a hard task in a growing network, as more and more routes need configuring and monitoring. A viable alternative may be to rely on an IGP (interior gateway protocol) routing protocol to determine the paths to be used by the LSPs, thus freeing the operator from the manual configuring of all LSP paths. Here, we address the procedure of dimensioning a MPLS network where a minimum weight routing protocol (as OSPF or IS-IS) is used to determine the paths of the LSPs. We start by presenting the complete minimum weight routing network design problem (MWRNDP) with explicit minimum weight routing constraints. Then, we propose a two-step approach based on two ILP models which are a decomposition of the complete model in two separate optimization problems: first, we determine the physical network configuration and the traffic flow routing with the network design problem (NDP); then, we determine the link weights required to achieve the determined traffic routing with the link weight assignment problem (LWA). Because in the first problem the traffic routing is destination based, there may be instances where a minimum weight routing solution is not found. In these cases, an additional constraint is added to the first problem and the two-step approach is repeated. An important observation is that this methodology obtains the optimal solutions and the computational results show that it requires much lower computational times than the original global MWRNDP model. Using the two-step approach, a set of computational tests is presented to determine the cost penalty in MPLS network design when using minimum weight routing as opposed to source based routing.