文档介绍：摘 要
DS-TE 环境下 LSP 抢占算法研究
传统的 IP 网络提供的是“尽力而为”的服务，本身不提供服务质量(QoS, Quality
of Service)保证。随着互联网的高速发展，实时业务和多媒体业务的应用种类不断增
加，用户对网络服务质量的要求也逐渐提高。原有的 IP QoS 机制已经不能满足当前
用户对于 QoS 的需求，因此，需要对 QoS 的实现机制进行深入研究。本论文对具有
区分服务感知的流量工程(DS-TE, DiffServ-Aware Traffic Engineering)网络中的 QoS 保
证问题进行了深入研究，主要对 DS-TE 环境下的抢占算法进行了改进与分析，主要
工作如下：
首先，论文介绍了 MPLS 技术的网络构成、工作原理以及核心技术。对 QoS 的
体系结构进行了介绍，对尽力而为服务模型、综合服务(IntServ)模型和区分服务
(DiffServ)模型各自的优缺点进行了分析比较。重点讨论了 DS-TE 环境下的 IP QoS 问
题：DS-TE 技术将 MPLS TE 技术和 DiffServ 模型相结合，既具有 DiffServ 模型良好
的扩展性，同时兼备 MPLS 流量工程有效的路由策略，是骨干网络中解决 QoS 问题
的有效方案。
然后，本论文对 DS-TE 环境下的抢占机制进行了重点研究，着重讨论了现行的
抢占算法。针对 V-PREPT 算法存在的不足，本论文给出了两种基于 V-PREPT(Versatile
Preemption)算法的改进算法：N-PREPT 算法和 BH-PREPT 算法。
N-PREPT 算法对于原算法的改进如下：根据网管人员对权值的具体配置，灵活
地更改优化标准的执行顺序，并依照此顺序对 LSP(LSP, Label Switching Paths)进行分
情况抢占；在最小化抢占总代价的前提下，首要考虑减小被抢占的 LSP 的规模；设
置多层约束条件，使得算法的输出结果更为理想，即尽量减少被抢占的 LSP 的总数
目；对优化模型及数学表达式进行了改进，能够更加准确地计算在减少抢占 LSP 数
目方面的代价和因抢占而造成的带宽浪费。仿真结果表明，N-PREPT 算法在减小由
重路由情况给网络带来的额外开销方面，较原算法拥有更好的性能。
BH-PREPT 算法对于原算法的改进如下：优先考虑最小化由抢占所带来的带宽浪
I
费；将可被抢占的 LSP 集合按照预留带宽大小分为两组，分别列举出所有可能被抢
占的 LSP 的组合，在其中寻找抢占总代价最小的组合作为算法输出；优先选择 LSP
数目最少的组合进行抢占；采用与 N-PREPT 算法相同的优化模型和数学表达式。通
过仿真结果可知，与 V-PREPT 算法相比较，BH-PREPT 算法在不同的权值配置下拥
有更好的算法输出结果，整体提高了原算法的性能。
关键字：
服务质量，MPLS 流量工程，区分服务，DS-TE，抢占算法
II
ABSTRACT
Research on LSP preemption Algorithm for DS-TE Networks