The Research On Algorithm Of Multiple Constraints Single Path Routing Problem

As IP network application expands increasingly,all kinds of services emerge in endlessly.Network application needs the sustainment of the multiple QoS constraints routing model sustaining distinguishable services.The research of Multiple Constraints Single Path Routing(MCSPR)is very important. Through the research we can achieve that: 1.Connecting the request with each admitting QoS operation, finding the feasible path to satisfy the need of QoS; Optimizing the usage rate of full-scale usage, balancing the load of network and maximizing the capacity of the network for accepting the need of QoS.The reason of resolving completely the problem of MCSPR is hard:seeking the optimizing objective,satisfying the feasible and constraint path more than one,having the NP-Complete complexity of algorithm.The research content of this article involves:1.Describing formally the model of MCSPR problem,giving the commixing layout of the problem,proving that MCSPR problem is NP-Complete basing on the NP-Complete of the knapsack problem.2.Designing a central and distributed approximation algorithm for the problem;proving the quality of the answer by this algorithm,giving a distributed realization basing on this algorithm;the result of the experiment indicates the approximation of this algorithm is high,the circulation time is little.3.Resolving MCSPR problem basing on many objective,inherited and evolutional thought.In the first,enlarging the problem.Because the preference information of many optimized objective is difficult to obtain in routing problem.We acquires the approximate answer firstly,then analyzes and decides the Pareto approximate answer basing on actual demand,chooses the final project of the routing. The algorithm processes optimized choice basing on Strength Pareto Evolutionary Algorithm 2(SPEA2)and finds the multi-objective approximate path effectually.4. Finally,this article enlarges the solution of restraint routing,describes the problem with distributed restraint to satisfy optimized model,analyzes the research method of the resolution.