Multi-service Matrix Under The Te Performance Of The Algorithm

The Internet has grown dramatically over the past 10 years. With the fast development of Internet as well as abundance of network traffic and high requirement of network performance, it challenged the network ISP very much. Traffic Engineering is coming. TE is one of the most important network optimization techniques which are mainly dealt with optimization for network resources to avoid network congestion. Theoretically, if the TM is known exactly, then an optimal routing for it can be obtained by solving the corresponding multi-commodity flow problem instance. Unfortunately, measuring and predicting traffic demands are illusive problems. Flow measurements are rarely available on all links. For a large-scale Internet with bursty demands, it is important for large ISP network operators to find a single robust or fixed set of routes to optimize the performance over multiple TMs. Multiple TMs can be used to characterize the change of traffic or traffic uncertainty in exogenous traffic.This paper concentrates on the topic of traffic engineering based on multiple traffic matrices. In chapter 2, we mainly discuss the problem of performance metric which include average case performance, worst case performance and their tradeoff in traffic engineering based on multiple traffic matrices. We propose a new metric-a weighted sum of the average case and the worst case performance-to control the tradeoff between these two considerations. We prove that optimizing routing using this metric has desirable properties, such as the average case performance being a decreasing, convex function to the worst case performance. Then we discuss the metric in our remaining chapters are all about the worst case performance. In chapter 3, the topic is about traffic engineering based on OSPF/IS-IS routing protocol for multiple TMs. We first prove that the traditional TE algorithms for single accurate TM are NP-hard problems not to mention TE algorithms dealing with multiple TMs. We then provide several heuristic algorithms for multiple TMs and we stress on one particular algorithm to discuss with elements of that algorithm have great impact on our performance. And we find the parameter k from k shortest path algorithm and iterative cycles have deep relation with the last performance. In chapter 4, we suppose several heuristic algorithms for traffic engineering for multiple traffic matrices, which are similar to the algorithms in chapter 3 but not the same. And then we discuss factors that influence the final network performance. In chapter 5, we mainly discuss the problem of finding a routing for ISP under certain network perforce. First we design a heuristic algorithm to find a single routing that meets the ISP demand. If we can not find the single routing, we use multiple routings. Then we discuss how effectively to monitor the least links to change routing under congestion. And finally we discuss the problem of merging a lot of traffic matrices into several critical, but with least number of traffic matrices.