MPLS网络中支持Diffserv流量工程的抢占算法

通过对MPLS网络中支持Diffserv流量工程的抢占策略的分析，基于抢占策略包括LSP的数目、LSP的优先级和抢占带宽三个主要抢占准则的思想，提出了一种优化的启发式算法。该算法基于回溯法的原理求解NP完全问题。仿真结果表明，与其它算法相比，该算法表现出更高的求解准确度，求解时间复杂度相当，适合实际的大规模网络的应用。此外，本文也考虑了在抢占策略下的路由方法。

An Algorithm with minimal preemption cost for MPLS Diffserv-Aware Traffic Engineering

Bandwidth, preemption priority and the number of LSPs to be preempted are three main preemption optimization metrics in preemption policy for MPLS networks. For the choice of LSPs to be preempted is to be cited as an NP-complete problem, it is hard to get optimal result in large scale networks. In this paper, a heuristic algorithm based on backtracking is proposed to solve the problem. Simulation results indicate that our algorithm has higher choice accuracy than the well-known heuristic algorithm cited by many other papers. Moreover, the computational complexity of our algorithm is acceptable for router’s online computing in large scale networks. Otherwise, a path selection schema for minimizing the preemption is studied.