孙尚 王万龙

（中国人民解放军66061 部队 北京市 100144）

1 引言

近几年，互联网(Internet)的迅速发展及使用人数的递增，带宽不足将是往后互联网所面临到的一个重要问题，带宽的竞争和冲突严重危害了整体网络的传输性能。由于标签交换技术的发展，许多优点因素证明其将发展为未来网络技术的主流，尤其多重协议标签交换技术(MultiprotocolLabel Switch, 简称MPLS)，它整合了目前各种交换式路由器技术的优点，其结合了非同步传送模式(Asynchronous Transfer Mode, 简称ATM)的快速化、简单传输的优点，以及传统IP 的普遍性(ubiquity)、延展性(scalability)及弹性度(flexibility)优点。本文重点研究MPLS 网络标签交换技术中的路由路径安排，并可以使得有足够的带宽分给不同类型服务，从而达到服务所需。

2 算法设计

2.1 LSP路由安排算法

本节将介绍如何安排有服务质量需求的数据的路由选择方式，下面列举两项：Best-fit shortest path algorithm (BSP)和Worstshortest path algorithm (WSP)。

2.1.1 Best-fit shortest path algorithm (BSP)

Best-fit shortest path algorithm 是 由Dijkstra’s shortest path algorithm 演变而来，将最短路径距离权重考虑成连接带宽权重，来计算安排某一来源端(source)到目的端(destination)之间标签交换路径，LSP(s, d)，而此LSP(s, d)路径所选择的路径，是为欲配置的LSP 路径所连接带宽剩余总和为最小者。

（1）相关符号定义与注解：

G(N, L, C)：图形G 具有N 个节点及L 个连接

N：网络节点数的集合

L：任两节点间连接(Link)的集合

C：网络所有连接带宽权重的集合

s：欲安排LSP 起点(来源端)

t：欲安排LSP 终点(目的端)

b：欲安排LSP 所需带宽权重

S：N 集合中的部分集合

Du：s 点到u 点的带宽权重

duv：u 点到v 点之间连接的带宽权重

duv*：u 点到v 点之间连接减去b 后的带宽权重

G’：G(N, L)所有连接减去b 所行成的网络图形

图1：网络带宽安排范例