Ip Network Optimization Algorithm

With the explosive increase of traffic on IP backbone networks, traditional shortest path first routing algorithms may lead to network congestion in its nature. Network congestion will not only degrade the performance of the network,but also break ISP's QoS guarantees. In order to optimize the usage of the capacitated network resources and provide better service, a cost-effective split traffic method become more and more important. TE (Traffic Engineering) and Diff-Serv (differential services) architecture are proposed by IETF (Internet Engineering Task Force).Large IP networks use today's prevailing link-state routing protocols such as Open Shortest Path First (OSPF) or Intermediate System-Intermediate System (IS-IS) as their Interior Gateway Protocols (IGPs) for intra-domain routing. The routing and packet forwarding decisions for IGPs is primarily governed by link weights. So optimizing these link weights leads to less congestion in the network while utilizing link capacities efficiently, the studies of optimizing link weights have important significances. Recently many meat-heuristic search algorithms are engineered to solve this link weights setting problem, such as Genetic Algorithm and Tabu Search Algorithm and so on. The single logical link failures significantly affect network performance. Consequently, it is desirable to yield optimization link weights that are robust to all single link failures. Meanwhile the optimization algorithms must scale well, in terms of computational complexity and the size of the network.In this dissertation, the IP network link weights optimization problems, which must take many constraints such as bandwidth requirement, delay, cost and ECMP into account, mainly focus on two scenarios: without failures and single link failures.Firstly, the general weights setting problem for IP network is introduced in this dissertation. As to the problem's NP-hard character , it introduces intelligence optimization algorithms such as Genetic Algorithm, Tabu Search algorithm and HillHopping algorithm to solve the robust optimization of OSPF/IS-IS weights. This dissertation also presents simulations for the three algorithms and makes performance comparison.A Multi-Objective based Genetic Algorithm (MOGA) is proposed to find the solution to the multi-objective optimization problem without link failures in IP networks. The two main traffic engineering objectives are load balance and minimization of routing hop-sum.At last, this dissertation also discusses the network optimization problem in scenarios of single link failures. At first, we give a brief introduction about the characterization and classification of failures in IP backbone. According to the characteristics that network congestion is mainly caused by partial critical links, we also propose an optimization algorithm based on critical links and resource reserved to optimize the link weights setting. Simulation results indicate the proposed algorithm can improve the network survivability significantly.An IP network optimization simulation platform software is developed. It is easy to use and is universal. So it can be well applied to IP network link weights setting optimization.