(An) explicit routing procedure for traffic engineering

Abstract

This thesis deals with an offline routing problem, which can be used as an explicit routing procedure in MPLS(Multiprotocol Label Switching) network, for traffic engineering. This problem is foiiliulated as an MIP(Mixed Integer Programming) with the objective function which is to minimize the sum of the maximum link utilization for load balancing (link utilization) and the routing cost. Constraints are composed of link capacity restriction and demand requirement that has origin-destination pair, bandwidth requirement and hop restriction. The problem is proved to be NP-hard so that the Lagrangean relaxation method is applied to propose a Lagrangean heuristic. To test the effectiveness & efficiency of the proposed algorithm, computational experiments are performed with numerical instances. The experiment results show that the proposed algorithm solves the problem within a reasonable time.