Constrained Routing And Dynamic Traffic Grooming Algorithm Research And Implementation

The delivery of large scale digitized visual information over wide area networks is now becoming realistic. For traditional IP network, the currently deployed routing scheme is focused on constructing end-to-end connectivity which usually supports only one type of datagram service. The emerging high speed multimedia applications have different performance requirements such as bandwidth, delay, delay jitter, loss rate, nodes/links inclusion and nodes/links exclusion etc. The notion of Quality-of-Service (QoS) has been proposed to describe the quality defined performance contract between the service provider and the user applications. The QoS requirement of a connection is given as a set of constraints, which can be link constraints or end to end additive constraints. QoS routing is one such mechanism with two goals: selecting feasible paths that meet QoS constraints and making efficient utilization of the network resources. So the QoS routing problem can be attributed to the construction of path which satisfies the end-to-end QoS constraints at the same time optimizes some special cost function. This kind of problem can be solved by ILP (Integer Linear Programming) using CPLEX/AMPL. However, the running time of CPLEX will be unacceptable when the network scale become very large. So, in this paper, we will focus on solving the problem by heuristic algorithms.In chapter two, we first research and formulate several k shortest path algorithms, Then we give our attention on nodes/links inclusion routing problem, which is a very important strategy constraint. We propose an effective algorithm (NIR) to solve the nodes/links inclusion algorithm, the simulation results show that our algorithm can achieve a considerable performance when the time complexity is very low. Base on the research above, we give an algorithm to solving the disjoint paths computing problem. The algorithm can support node disjoint, link disjoint and SRLG disjoint.In chapter three, we focus on the inter-domain multi-constrain routing problem. An framework for distributed PCE inter-domain environment multi-constrain routing problem was proposed. The traditional BRPC algorithm aims to get the optimal results, and do not consider how to avoid to falling into the routing trap, which is very common in BRPC. Our method can solve the routing trap effective by introducing an extra backward iteration process.Routing for dynamic demands in two layer network is very critical for two layer network design. The most existing algorithms focus on the behavior under uniform traffic model. When the traffic model is non uniform, the performance of these algorithms became worse, and the blocking probability becomes high. To solve the problem, we propose a holding time aware algorithms, which can improve the performance under non uniform traffic model.