基于 GMPLS的新型流量工程算法研究#
郝靖鹏，刘博，忻向军**
（北京邮电大学电子工程学院，北京 100876）
5 摘要：传统流量工程的核心思想是 SPF 算法，即在网络中找到最短的一条路径，将数据沿
此最短路径传输。由于一条路径的带宽有限，当需要传输的流量较大时，容易造成拥塞，常
出现流量集中在代价较小的路径上，而很多路径上资源闲置的情况，使得网络资源不能充分
得到利用，传输效率较低。本文提出了一种基于带宽分布的新型流量分配算法——TDBB
（Traffic Distribution Based on Bandwidth）。与传统流量工程算法不同的是，TDBB算法没10
有把源端流量只沿一条路径传输，而是把流量按相应比例分成多分，并分别发送给多路径进
行传输，其中，每条路径所对应的流量比例由各路径带宽在总带宽中所占比例决定，每条路
径的带宽由此路径最小带宽所决定。相比于传统流量工程算法，TDBB算法可以最大限度利
用网络资源，提高传输效率，并且可实现最佳流量均衡，即在所传流量不超过网络可承担的
最大流量值的情形下，不会发生传统算法经常出现的链路拥塞情况。 15
关键词：流量工程；多路径；流量均衡；传输效率
中图分类号：TN92
The Research of New Traffic Engineering Algorithm Based
on GMPLS 20
Hao Jingpeng, Liu Bo, Xin Xiangjun
(School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing
100876)
Abstract: The key algorithm of the traditional traffic engineering is Shortest Path First, transferring
data on the shortest path in a network. It stands a good chance to cause traffic jam when lots of data are 25
needed to be transferred, due to the limit of the bandwidth of the single path, which explains why data
often concentrated on paths with lower costs rather than those with higher costs. TDBB（Traffic
Distribution Based on Bandwidth）, a totally new traffic engineering algorithm, is proposed in this
paper. In TDBB algorithm, traffic is not transferred only on one single path, but is divided into several
parts in a proportion and transferred on multipath, which is different from the traditional traffic 30
engineering algorithm. The traffic proportion related to each path is decided by the weight of each
path’s bandwidth, while the bandwidth of each path is decided by the minimum bandwidth on this path.
Compared with the traditional traffic engineering algorithm, TDBB could not only use the network
resources to the best and improve the transmission efficiency, but also facilitate the traffic flow balance,
which means that traffic jam would not happen, unless the whole resources of the network fail to afford 35
the demand.
Key words: traffic engineering; multipath; traffic flow balance; transmission efficiency
0 引言
互联网的迅速发展要求网络可以提供更快的传输速率。基于 SPF的传统流量工程算法40
有很多诸如无法充分利用网络资源以及容易造成链路拥塞的弊端，所以一种新型的流量工程
的算法的提出很有必要。文献[1]从优化路由的角度对流量工程进行研究，采用了分类法，
进行了多方面的广度分析。文献[2]提出一种流量分享路由选择机制，并提出了一种权重可
变方案。文献[3]进行了 CSPF算法的仿真实验，提出了一个实现 CSPF的简化模型，但对链
- 2 -
路权重的定义不清晰。 45
本文提出的 TDBB算法在很大程度上解决了传统流量工程算法的弊端。光网络中常用
的协议是通用多协议标签交换协议（GMPLS）。GMPLS 以必要的结构扩展MPLS 协议[4]。
借助 GMPLS 协议，很容易实现 TDBB算法在实际网络中的应用。
本文首先会对新型流量工程算法 TDBB进行介绍，然后分别在单源单宿与多源多宿的
动态链路情形下，对 TDBB 算法与 SPF算法在传输效率、阻塞率以及流量均衡性方面的优50
劣进行仿真比较。
1 新型流量工程算法说明
本章先对 TDBB 算法进行介绍，对其多路径分发机制进行详细说明，并分析其相对于
传统流量工程算法（SPF算法）的优势所在。
TDBB算法介绍 55
本文提出的 TDBB 算法利用各链路带宽在网络总带宽中所占的比重而简化原本复杂的
网络，在简化后的网络中进行流量分配，再映射到原有的网络中，其核心思想是将传统流量
工程算法中的单一路径改为多条路径进行流量传输。算法介绍如下：
1）对于网络 ),(1 EVG ，其源端是 sv ，宿端是 tv ；
2）网络 1G 的每一条链路 ),(1 jie 有以下两个属性： 60
a.代价 ),(1 jiw ;
b.带宽 ),(1 jif ;
3）根据每条链路的代价 ),(1 jiw ，找出 sv 到 tv 的最短路径 1P ；
4）在最短路径 1P 中，找出带宽最小的链路，将此带宽作为这整条最短路径 1P 的带宽。
从而可将 1P 简化为一条链路 ),(1 tse ，这条链路的两端是源端 sv 和宿端 tv ，且： 65
链路 ),(1 tse 的代价如式（1）所示
),(),( 11 jiwtsw 1),(1 PEjie (1)
链路 ),(1 tse 的带宽如式（2）所示
),(min),( 11 jiftsf 1),(1 PEjie (2)
其中
1P
E 是 1P 所有链路的集合。 70
5）在网络 1G 中，
若链路
1
),(1 PEjie ，则其更新后的带宽值如式（3）所示：
),(),(),( 112 tsfjifjif (3)
从而得到一个新的网络 ),(2 EVG 。在 2G 中：
),(),( 12 jiwjiw 75
),(),(),( 112 tsfjifjif ， 1),(1 PEjie
),(),( 12 jifjif ， 1),(1 PEjie
6）在 2G 中，删除所有带宽为 0的链路。在 2G 中，找出由源端 sv 到宿端 tv 的最短路径
- 3 -
中国科技论文在线
2P 。
7）找出路径 2P 中带宽最小的链路，并将将此链路的带宽作为最短路径 2P 的带宽。从80
而路径 2P 可简化为一条链路 ),(2 tse ，且：
链路 ),(2 tse 的代价如式（4）所示：
),(),( 22 jiwtsw 2),(2 PEjie (4)
链路 ),(2 tse 的带宽如式（5）所示：
),(min),( 22 jiftsf 2),(2 PEjie (5) 85
其中
2P
E 是 2P 所有链路的集合。
8）重复上述步骤会得到新的网络，知道在新网络 1nG 中，找不到可以使 sv 到达 tv 的路
径，此时算法终止。从而可以得到 n条从 sv 到 tv 的路径。
9）网络 1G 最终可简化为网络 ),( EVG ， ),( EVG 有以下特点：
只有 sv 和 tv 两个端点，且 sv 和 tv 间有 n条链路相连： ),(1 tse ， ),(2 tse ，…… ),( tsen 。 90
10）每条路径 iP上应分配到的流量的大小，如式（6）所示
),(
),(
*
1
tsf
tsf
FF
n
i
i
i
i
(6)
其中，F 是 sv 到 tv 需要传输的流量值， ),( tsf i 是 iP的带宽
11）新型算法可以得出以下数据
A．从 sv 到 tv 的速率如式(7)所示 95
),( tsfv i (7)
B．将大小为F 的流量从 sv 传到 tv ，新型算法可用最少的时间，所耗费的时间如式(8)
所示
n
i
i tsf
F
v
F
t
1
),(
(8)
C．网络带宽利用率如式(9)所示 100
),(
),(),(
1
11
jif
jifjif n
(9)
在式(9)中， ),(1 jif 的含义是原网络中所有链路的带宽和， ),(1 jifn 的含义是残
存的网络 1nG 中所有链路的带宽和。易知若 1nG 中链路集合为空集，表明此时网络每条链
路的带宽全部被利用了，即网络带宽利用率为 100%，当然，在实际的网络中通常不会可能
出现如此特殊的情况，但是，由此可以看出，新型算法使网络资源得到了最大程度的利用。 105
TDBB算法对 SPF算法的改进
SPF算法有三个缺点：
- 4 -
中国科技论文在线
A.流量常常集中在代价较小的路径上，不能充分利用网络资源；
B.闲置链路得不到利用，导致传输速率不高；
C.经常造成链路拥塞，且必须设计出相应的较复杂的算法来判断某条链路是否阻塞，对110
拥塞的处理会耗费很多不必要的时间，降低传输效率。
不同于传统流量工程算法，TDBB 算法通过多路径分发机制进行流量传递，有以下三个
方面的优点：
A.不单单以最短路径为传输路径，使闲置链路也得到利用，大幅度提高网络带宽利用率。
B.多条路径传输的速率大大高于单条路径传输的速率，使流量转发更快速。 115
C.可以解决 SPF 算法中经常出现的链路拥塞问题，实现流量均衡。在 SPF 算法中，当
流量超过最短路径的负载使，就会出现阻塞；而在 TDBB 算法中，当需要传输的流量大于
整个网络资源的总负载时才发生阻塞。
经过以上分析可知，TDBB 算法很大程度上解决了基于 SPF 算法经常出现的问题，对
网络的发展，有着潜在的重要意义。 120
2 仿真实验设计
本章设计了单源单宿以及多源多宿情形下的仿真实验，比较了 TDBB 算法与 SPF 算法
在传输效率、阻塞率以及流量均衡性方面的优劣。
单源单宿网络仿真设计
在图 1-a所示的网络中，每条链路有两个属性，分别是这条链路的代价和带宽。用 TDBB125
算法可将图 1-a的网络简化成图 1-b所示的结构。图 1-b中的各路径映射到原网络中分别是，
1P表示 ADBCF， 2P 表示 ADEF， 3P 表示 ABEF， 4P 表示 ABDECF。由式（6）可知，各条
路径分配的流量应为 %，%，%，%。
实验设定，流量到达服从参数为的泊松过程，每个请求的流量大小服从参数为 的
负指数分布。进行仿真实验时，由函数 exprnd（）生成流量请求到达的时间间隔与大小。一130
个随机过程是参数的泊松过程的充分必要条件为到达间隔 ),2,1( iX i 相互独立，且服
从相同参数的负指数分布。所以到达时间间隔由 exprnd（）函数产生的流量请求是泊松过
程。流量请求到达时间间隔服从参数为的负指数分布，流量传输时间服从参数为 的负
指数分布。array(1,:) = exprnd(arr_mean,1,arr_num)可以生成流量请求到达间隔，array(2,:) =
exprnd(tra_mean,1,arr_num)可生成流量传输时间的数据。其中，arr_mean 为 的倒数，135
tra_mean 为的倒数，arr_num 为总仿真的流量请求数。array 矩阵是 3*n 的矩阵，其中 n
是总的流量请求个数，array矩阵共有 3行，每一行含义如表 1所示。
表 1 array矩阵
Tab. 1 Matrix array
array矩阵的行 各行含义
array(1,:) 流量请求到达时刻
array(2,:) 流量传输时间
array(3,:) 流量传输完毕时刻
array(1,:) = exprnd(arr_mean,1,arr_num)生成流量请求到达时间间隔，而表1中的array(1,:)140
的含义是流量请求到达时刻，即对 array(1,:)进行了处理：通过程序 array(1,:) =
- 5 -
中国科技论文在线
cumsum(array(1,:))将原先流量到达间隔进行相加，进而可得到每个流量请求到达的时刻。
D
B
C
F
E
3,70M/s
6,70M/s
3,90M/s
5,50M/s
2,50M/s
1,60M/s
A 4,30M/s
1,110M/s
4,40M/s
A FP3
P2
P1
P4
50M/s
60M/s
30M/s
10M/s
图 1-a 示例网络 图 1-b 简化网络
-a A network as an example Fig. 1-b The simplified network 145
多源多宿网络仿真设计
若一个网络是多源多宿，可将此网络简化为一个单源单宿的网络[5]。假设图 1-a 所示的
网络拓扑中，不再只有 A—F 一对源宿端，若 A，B，C 是源端集，D，E，F 是宿端集，则
可定义端点 S与端点 T，使 S与源端集相连，T 与宿端集相连。规定新生成的链路代价是 0，
带宽无穷大。那么图 1-a所示的网络可以等效为图 2-a。 150
在图 2-a中，相比于图 1-a多出来的虚拟链路的代价是 0，带宽无穷大。用 TDBB算法，
可以将图 2-a简化为图 2-b 的简易网络。通常在实际的网络中，流量到达时间间隔以及流量
大小所服从的分布并不是一成不变的，也就是说流量到达率以及流量大小所服从的负指数
分布的参数 是会改变的。考虑到这种情况，仿真时以与 为自变量，生成三维图，可
较全面进行比较。 155
D
B
C
F
E
3,70M/s
6,70M/s
3,90M/s
5,50M/s
2,50M/s
1,60M/s
A 4,30M/s
1,110M/s
4,40M/s
S
T
P3
P2
P1
P4
1,6 0M/s
3,70M/s
4,30M/s
P5
1,110M/s
6,40M/s
S T
图 2-a 示例网络 图 2-b 简化网络
Fig. 2-a A network as an example Fig. 2-b The simplified network
3 仿真结果
图 3具体反映了单次仿真中 TDBB算法与 SPF算法的传输耗时情形。图 4，图 5与图 6160
分别对 TDBB算法与 SPF算法进行了 20次仿真，每次仿真有 100个流量请求通过，参数
与 是定值。组图 7 与组图 8 是参数与 为自变量的情形下进行的三维仿真图，综合比
较了 TDBB 与 SPF算法的优劣。
与 是定值
图 3 反映了每个流量请求传输总耗时的情况，具体地体现了两种算法在单个流量请求165
总耗时方面的差异。从图 3 中可以看出，在单源单宿情形下，SPF 算法比 TDBB 算法的流
量传输总耗时要大，其原因有两个方面：1）SPF算法比 TDBB 算法的传输速率要低，由此
SPF算法的传输时间较 TDBB算法要大；2）SPF算法比 TDBB 算法较易受到阻塞。所以需
要比较两个算法的传输效率与阻塞率，进行深入分析。
- 6 -
中国科技论文在线
170
图 3 TDBB算法与 SPF算法传输耗时比较
The compare of transmission time between TDBB and SPF
由图 4可知，TDBB 算法的传输效率要优于 SPF算法，这是因为采用多路径分发机制，
TDBB 算法可以更有效地利用网络资源，网络带宽利用率较高。
与图 5 可知，TDBB 算法的阻塞率低于 SPF 算法。阻塞率是一个网络是否良好运营的175
重要参数。SPF 算法使流量都倾向集中于最短路径，很容易造成流量阻塞，而 TDBB 算法
使流量均衡分配到各路径，阻塞率大大降低。
图 4与图 5的结果可以相互验证，传输效率越高，流量在下一个流量请求到达时传输完
成的概率就越高，那么阻塞率便越低；同样，阻塞率越低，说明 TDBB 算法下的网络链路
状况良好，传输效率自然越高。 180
图 4 TDBB与 SPF传输效率比较
compare of transmission efficiency between TDBB and SPF
- 7 -
中国科技论文在线
图 5 TDBB与 SPF阻塞率比较 185
The compare of blocking rate between TDBB and SPF
由图 6可知，在流量均衡性方面，TDBB 算法远远强于 SPF算法，因为 SPF算法通常
采用单一路径传输流量，由于 SPF算法的缺陷，即使有闲置的路径，流量也不会或极小可
能沿闲置链路传输，所以 SPF算法常会造成流量阻塞，均衡性能较差。相反，TDBB算法
可以将流量按个路径所能承担的流量多少，较为均匀地分摊到各链路上。 190
图 6 TDBB与 SPF均衡性比较
The compare of traffic flow balance between TDBB and SPF
与 是变量
由组图 7可知，图 7-b所表现的综合传输效率高于图 7-a。当接近 0且 接近 1时，195
即流量请求到达间隔无穷大且单个流量的大小无穷小时，网络基本无任何传输压力，即便如
此，SPF 算法的传输效率也未到 ，而 TDBB 算法的传输效率却接近 2。当为 1 时，即
流量请求几乎无间隔到达，参数 大约为 时，SPF算法传输效率就降为 0，而 TDBB算
法的传输效率在 约为 是才降为 0，说明对于同一个网络，TDBB算法可以比 SPF算法
承担更多流量传输。 200
- 8 -
中国科技论文在线
图 7-a SPF传输效率 图 7-b TDBB传输效率
-a Transmission efficiency of SPF -b Transmission efficiency of TDBB
通过比较组图 8可发现，图 8-b的“坡势”比图 8-a更平缓。当值为 1时，SPF阻塞
率为 1的范围大于 TDBB算法。可知，TDBB 算法的阻塞率普遍低于 SPF算法。 205
图 8-a SPF 阻塞率 图 8-b TDBB阻塞率
Fig. 8-a The blocking rate of SPF Fig. 8-b The blocking rate of TDBB
4 结论
本文给出了一种基于 GMPLS 的全新的流量工程算法，即 TDBB算法。对于传统流量工210
程算法所存在的传输效率低，易发生阻塞且流量均衡性差等弊端，本文提出的 TDBB算法
改传统单一路径传输的方式，按照各路径所能承受流量大小，将流量均衡分摊，其多路分发
机制有效解决了 SPF算法的问题。在仿真设计时，分别考虑了流量参数为定值及变量的情
况，在微观及宏观上对 TDBB算法与 SPF进行了比较。从仿真结果可以看出，在传输效率，
阻塞率，尤其是流量均衡性方面，TDBB 算法要优于 SPF算法。 215
[参考文献] (References)
[1] Ning Wang,Kin Hon Ho,George Pavlou, overview of routing optimization for internet traffic
engineering[J].IEEE Communications Surveys,2008,10(1):36-56.
[2] Hua Yiqiang,Liu Aibo,Lu yueming,etc. Load balance in hierarchical routing network[J]. The Journal of China
Universities of Posts and Telecommunications,2009,16(6):72-77. 220
[3] 王勇.光网络中 GMPLS 流量工程实现的研究[D]，西安，西安科技大学，2009.
[4] 朱玮 GMPLS 流量工程的实现和约束路由的研究{D}. 杭州：杭州电子科技大学，2010.
[5] 苏驷希. 通信网性能分析基础[M]. 北京：北京邮电大学出版社，2006
