Lagrange relaxation based algorithm for DiffServ/MPLS network dimensioning with QoS guarantees

An approach to dimensioning DiffServ/MPLS networks taking into account the per-class bandwidth reservation and fault tolerance cushion weights is proposed. Our dimensioning algorithm is based on Lagrange relaxation and it uses a bandwidth constraint model in order to provide per-class bandwidth reservation, and link costs which translate to backup LSP cushion weights. We propose an optimization formulation for our policy and also a polynomial time heuristic capable of approximating the optimal results. Besides a-priori dimensioning, a modified version of our dimensioning policy can also be run weekly/monthly in order to redimension LSPs according to the stored traffic history. Both the proposed heuristics have polynomial complexity and provides bounds on the value of the optimal objective function, which can be used to evaluate the accuracy of the results.