Research On Constraint-Based Routing Algorithms Optimized For Traffic Engineering

The Internet's traditional best effort architecture and shortest path first routing algorithm take the risk of congestion in nature. With the fast growth of the Internet and the rapid increase of access bandwidth, the risk of congestion also increases dramatically. Congestions will not only downgrade the network's performance, but also break the ISP's QoS guarantees. This issue has therefore caused widespread concern.Traffic Engineering is a network optimizing technology of great value. It avoids congestion by optimizing the utilization of network resources. Constraint-based routing (CBR) is an important technology for traffic engineering provided by Multi-Protocol Label Switching. CBR can select a path according to QoS constraints and traffic engineering objectives. By combining traffic engineering objectives in the QoS route selection phase, we can balance the traffic, reduce the risk of congestion, and improve the utilization of network resources. Thus, it has great theoretic and application values.In this paper, we mainly studied single path online constraint-based routing algorithms, precomputing algorithms, and multipath algorithms towards primary traffic engineering objectives, such as minimum interference, load balancing, and minimum usage of network resources. Our work concentrates on:1. Single path online routing algorithmsIn light of the IMIRA algorithm's characteristic of only considering interference minimizing, we proposed an improved version named IMIRA-LB which has a better load balancing. In light of the problem wherein MIRA's judgment on a critical link may be too simple, we proposed a new link criticality function and a corresponding algorithm named MINCF. On these bases, we proposed an algorithm named HORA which can consider all the three objectives (minimum interference, load balancing, and minimum usage of network resources) and can be easily adjusted by the administrators. All these three algorithms have better request success rates than the NewMIRA and some other former algorithms. The IMIRA-LB algorithm performs better in topologies which have a certain number of ingress/egress pairs. However, if the number of ingress/egress pairs is very big, the interference will be very complex and the performance of IMIRA-LB and NewMIRA will be significantly downgraded. MINCF and HORA algorithms can be adjusted by the administrators so they can achieve better performance. They show better adaptive ability to different topologies and requests.2. Single path precomputing algorithms for traffic engineeringIn light of the fact that an online algorithm has strict limitations on complexity, we proposed two different precomputing algorithms. One is the PreMINCF algorithm, which precomputes the link criticality function, and the other is the PreKMIP algorithm, which precomputes K paths. The PreMINCF algorithm has better adaptive ability. It cuts down operation time without losing much of the optimization effect through precomputing. The PreKMIP algorithm obtains a better performance in request success rates and throughput with a certain increase in operation time.3. Multipath traffic engineering algorithmIn light of the fact that most of the current multipath algorithms focus on load balancing, few have done so in interference minimizing. We thus proposed two multipath routing algorithms, namely, MPN-MI algorithm and MKP-MITS algorithm. MPN-MI algorithm attempts to minimize path number and interference. It can select a minimum number of minimum interference paths while satisfying the request bandwidth, thereby reducing the interference and extra control overhead for the multipath. The MKP-MITS algorithm minimizes the interference at most K paths. This algorithm does better load balancing and also considers interference minimizing while splitting the traffic along multipaths.To sum up, we thoroughly conducted research on traffic engineering routing. The algorithms proposed in this dissertation can optimize route selection, such as interference minimizing, load balancing, and minimizing of resource usage. Therefore, our proposed algorithms can improve success rate and throughput while satisfying the request bandwidth. We believe that our contributions provide a solid groundwork for future research and engineering in next generation Internet both in theory and in practice.