Research on Tabu Search applied in off-line MPLS layout design problem

There are two kinds of layout designs in multi-protocol label switch network:on-line and off-line. To perform traffic engineering based on a given topological structure and Qos requirement of the network, the layout design must be carried out to search an optimal link set and to make the flow distribution. One advantage of off-line MPLS layout design is to allow a globally optimal network design. To obtain the optimal MPLS layout, namely, to minimize the link set of LSP and to allocate flow hereinafter is designated as MPSFAP (Minimum Path Set and Flow Allocation Problem). It is difficult to get an exact solution to MPSFAP because it is a mixed-integer nonlinear multi-depot problem. Here, we propose a heuristic algorithm based on tabu search to solve the problem. The simulation result shows that the approximate solutions of our algorithm are close to the exact ones.