Multiobjective Traffic Engineering optimization over the Internet

Abstract

In the current information age, Traffic Engineering (TE) over the Internet is a critical issue. The aim of TE is to map the required traffic request over the network topology in an efficient way so as to satisfy Quality of Service (QoS) and topology constraints. In this work, we will consider a multiobjective Multi Protocol Label Switching (MPLS) TE problem. This problem can be formulated as multiobjective mixed integer mathematical problem. We considered minimal routing cost, optimal load on links and minimal number of label switched paths as our objectives. The constraints of our problem address hop count, bandwidth, number of splits and QoS. Since the above multiobjective problem is NP-hard, exact solution methods fail to give a good solution under reasonable time constraint. In this work, a survey of available mathematical models for MPLS TE is conducted. We have adopted a path based mixed integer programming formulation of this problem and solved a 10-node problem using lexicographic weighted Chebyshev method. We also developed eight heuristic algorithms based on the genetic algorithm. Two of these algorithms produce a single solution. The remaining six algorithms produce a Pareto curve in a single run. These six algorithms differ in initialization and crossover operators. We solved the 10-node problem using each of these heuristics and compared the results with the lexicographic weighted Chebyshev method. Various performance metrics were used to compare among the proposed algorithms. Using Kruskal Wallis nonparametric test with five replications for each set of parameters, we found that there is no significant variation among the metrics generated by various algorithms. We also conducted experiments to study the sensitivity of the heuristic algorithms with respect to the weights used in the fitness function. It was found that assigning a higher weight to the routing costs gives better metrics. The last experiment was repeated for a 20-node problem. We arrived at the same conclusion as above. Finally, we propose some possible future research directions.