基于单程建路的高效快速双向标签交换路径生成算法-金鑫.pdf
《基于单程建路的高效快速双向标签交换路径生成算法-金鑫.pdf》由会员分享,可在线阅读,更多相关《基于单程建路的高效快速双向标签交换路径生成算法-金鑫.pdf(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第 38 卷第 3 期 电 子 与 信 息 学 报 Vol . 38No.3 2016 年 3 月 Journal of Electronics & Information Technology Mar . 2016 基于单程建路的高效快速双向标签交换路径生成算法 金 鑫文 安黄维芳刘 年魏承志张剑波*任 智(中国南方电网电力调度控制中心 广州 510623) (重庆邮电大学移动通信技术重庆市重点实验室 重庆 400065) 摘 要:双向标签交换路径( LSP)是多协议标签传输应用( MPLS-TP)网络技术的重要组成部分,但现有的双向 LSP生成算法因双程建路而在控制开销和用时方面导致冗余。
2、为此,该文提出一种基于单程建路的高效双向 LSP 生成算法( EAEBL),在保障建路效果的前提下,通过控制消息的一次单程正向传递完成双向 LSP 的生成,从而减少建立双向 LSP 的控制开销和用时而且能够加快启动数据分组的传递。理论分析验证了 EAEBL 算法的有效性,仿真结果显示:与现有的 4 种双向 LSP 生成算法相比,EAEBL 算法的建路控制开销和用时分别减少了 14.7%和 50%以上,数据分组在源 LSR 的等待时间则被减至趋近于 0。 关键词:多协议标签交换传输应用;双向标签交换路径;单程;控制开销 中图分类号: TP393.4 文献标识码: A 文章编号:1009-5896
3、(2016)03-0707-06 DOI: 10.11999/JEIT150754 An Efficient Algorithm for Rapidly Establishing Bidirectional Label Switch Paths Based on Single Trips of Control Packets JIN XinWEN AnHUANG WeifangLIU NianWEI ChengzhiZHANG JianboREN Zhi(CSG Power Dispatching Control Center, Guangzhou 510623, China) (Chongq
4、ing Key Laboratory of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China) Abstract: Bidirectional Label Switch Paths (LSPs) are important parts of Multi-Protocol Label Switching- Transport Profile (MPLS-TP) networking technology. However, t
5、he existing algorithms of establishing bidirectional LSPs have redundancy in operation, control overhead, and waiting time of data packets. To address this problem, a novel algorithm based on single trips of control packets, Efficient Algorithm for Establishing Biderictional LSPs (EAEBL), is propose
6、d in this article. On the premise of completing the establishment of bidirectional LSPs, EAEBL only needs to transfer the control packet through a single trip, thus the redundancy in operation and control overhead is reduced and conveying data packets is accelerated. Theoretical analysis verifies th
7、e effectiveness of EAEBL. Simulation results show that EAEBL reduces the control overhead and delay for establishing bidirectional LSPs by at least 14.7% and 50%, respectively, as compared with three existing algorithms. Moreover, the waiting time of data packets in source LSPs is decreased to appro
8、ach zero. Key words: Multi-Protocol Label Switching-Transport Profile (MPLS-TP); Bidirectional LSPs; Single trips; Control overhead 1 引言通过扩展 MPLS(Multi-Protocol Label 收稿日期: 2015-06-24;改回日期: 2015-09-27;网络出版: 2015-11-19 *通信作者:张剑波 基金项目:国家自然科学基金(61379159) ,长江学者和创新团队发展计划基金(IRT1299) ,南方电网科技项目(K -ZD2013-0
9、22) Foundation Items: The National Natural Science Foundation of China (61379159), The Program for Changjiang Scholars and Innovative Research Team in University (IRT1299), The Science and Technology Project of China Southern Power Grid Company (K-ZD2013-022) Switching)1,2架构而得到的分组交换网络技术MPLS-TP (Tran
10、sport Profile)3,4近年来受到人们关注。作为传送和数据技术融合发展的产物,MPLS - TP 致力于在网络中实现面向连接的跨域分组传输,它简化了 MPLS技术的部分内容并在多个环节做了扩展,逐渐成为一种适应业务 IP 化、网络分组化的主流技术。 MPLS-TP 吸收了 GMPLS(Generalized Multi- Protocol Label Switching)5,6中的双向 LSP (Label- Switched Path)技术7,8,使采用它的网络能支持正708 电 子 与 信 息 学 报 第 38 卷 反两个方向的 LSP。对于如何建立双向 LSP,人们已做了一些研
11、究, 目前的双向 LSP 生成算法已从初期的控制消息传递两个来回独立地建正反向 LSP发展到控制消息传递一个来回同时建双向 LSP。但我们经过深入研究发现现有的双向 LSP生成算法在操作、控制开销和数据分组等待时间方面存在冗余,影响了控制开销和数据分组时延等性能,因此在本文中提出了一种仅需单程传递建路分组的双向 LSP生成新算法解决上述问题。 本文后续内容组织如下:第 2 节介绍现有双向LSP 生成算法; 第 3 节详述提出的双向 LSP 建立新算法并加以分析;第 4 节对新算法进行仿真验证;最后,第 5 节总结全文并简介未来研究方向。 2 双向LSP 目前已有一些关于在 GMPLS 和 MP
12、LS-TP 网络中如何建立双向 LSP 的研究。文献9提出一种在两个已有的方向相反的单向 LSP上通过控制层面的操作来建立双向 LSP 的算法(如图 1(a)所示),该算法能够在逻辑上关联正(从源 LSR (Label Switching Router)到目的 LSR)、反两个方向的 LSP,但因为需要分别建立正、反向 LSP,较为繁琐。为了降低双向 LSP 标签分配失败的概率,文献10 提出一种在 GMPLS 网络中建立双向标签路径的算法ULS(Upstream Label Set),如图 1(b)所示。在 ULS中,从源 LSR 开始,上游 LSR 向下游 LSR 发送一个可选标签集合,下
13、游 LSR 从该集合中选择一个标签发给上游 LSR,上游 LSR 发回 1 个 ResvConf 消息进行确认。ULS 比双向独立建路方式减少了一个消息回程,但传送标签集会导致冗余控制开销。 在 GMPLS 定义的双向 LSP 生成算法7,11中,用标签请求消息和 Resv 消息分别为下、上行 LSP分配不同的标签,如图 1(c)所示。与 ULS 相比虽然控制开销和建路耗时有所减少,但仍然需要 1 个来回且标签请求消息因携带标签而有冗余开销。 文献12为 MPLS-TP 网络提出的双向 LSP 生成算法NLDM(Novel Label Distribution Mechanism)采用反向建路
14、方式且正、反向 LSP 用同样的标签, 标签请求消息不再携带标签,但完成 LSP 生成仍需要 1个完整的消息来回。 从上述内容可看出,目前 MPLS-TP 网络的双向 LSP 生成算法已经从 2 个消息来回发展到 1 个消息来回且标签请求消息不再携带标签;但我们通过深入研究发现,当前算法的双程建路方式在操作、 图 1 双向 LSP 建立过程 控制开销和 路径启用时间方面仍然存在冗余,有必要加以解决以提高建路性能。 3 EAEBL算法 为解决现有 MPLS-TP双向 LSP生成算法存在的控制开销和时间冗余问题,本文提出一种基于单程建路的高效双向 LSP 生成算法EAEBL (Efficient
15、Algorithm for Establishing Bidirectional LSPs),采用单程建路的思想降低开销和用时。 3.1 EAEBL算法包含的新机制 为减少控制开销和建路用时,在 EAEBL 算法中设计了以下 4 种新机制: (1)单程建路: 在 EAEBL 算法中,上游节点为下游节点分配的标签供正、反两个方向的 LSP 使用,因此,只需要单程一次性的端到端标签请求 消息传送,便能够完成双向 LSP 的建立,如图 2 所示。为了建立反向 LSP 的表项, 标签请求消息需携带源节点地址 Src addr。 (2)正向建路: 现有的双向 LSP 生成算法通常采用“ 反向建路” 或
16、“正、反向建路” 的方式,而EAEBL 算法采用 “正向建路” 方式,从而为单程完成双向 LSP 建立打下基础。 第 3 期 金 鑫等: 基于单程建路的高效快速双向标签交换路径 生成算法 709 图 2 EAEBL 算法建立双向 LSP 的过程及数据分组传输 (3)且 建且用: 在现有的双向 LSP 生成算法中,源 LSR 上的数据分组要等到所有的 LSR 都被分配了标签后才能得到传送;而在 EAEBL 算法中,源 LSR 上的数据分组不必等到所有 LSR 都得到标签,只需在源 LSR 为下游的邻居节点 LSR2 分配了标签后,便可立即传送,如图 2 所示。这样,通过LSP 的且建且用,便能以
17、最快的速度启用新建的LSP,使数据分组在源 LSR 的等待时间缩短至趋近于 0。 (4)2 维避重 : 为避免标签冲突,EAEBL 算法让每个 LSR记录自己和其它节点已经使用的标签号,并在为其它节点分配标签时避免使用这些已用的标签号 (现有算法通常只排除自己使用的标签) ,从而从自己和其它节点两个维度避免标签重号,消除标签冲突的风险。LSR 获得其邻居节点使用的标签号的方法是:当有数据分组到达时,该 LSR 从数据分组头部取出标签号并进行保存,从而得以获知相邻 LSR 所使用的标签号。 3.2 算法操作 EAEBL 算法建立双向 LSP 的操作具体如下: (1)源 LSR 收到需要它转发的数
18、据分组后,获取通往目的节点的路由,然后选择一个未使用的标签,将其装入一个新建的 标签请求消息,同时装入源节点地址 Src addr,然后将该消息发给下一跳 LSR,并建立相应的正向标签表项。 (1) 位于路径中间的 LSR 收到上一跳 LSR 发来的标签后,建立反向标签表项;接着查找出通往目的节点的路由,选择一个未使用的标签,将其装入一个新建的标签请求消息,同时装入源节点地址 Src addr,然后将该消息发给下一跳 LSR;并且建立相应的正向标签表项。 (2) 目的 LSR 收到上一跳 LSR 发来的标签后,建立相应的反向标签表项。 综上所述,双向 LSP 通过控制标签请求消息的单程一次性传
19、递便得以建立。 3.3 性能分析 3.3.1开销分析 本小节对 EAEBL 算法的通信开销和存储开销进行详细分析。 (1) 通信开销分析: EAEBL 算法让标签请求消息携带源地址,会引入新的通信开销,即单程传送一个地址的开销;但现有算法皆采用双程及以上的控制消息传送方式,因此在建立双向 LSP 的总通信开销上至少比 EAEBL 多RLA( )( 1)l l ln ,其中 lR,lA分别为 Resv 消息和节点地址的长度,n 为LSP 包含的节点数。下面证明上述论断。 引理1 EAEBL 算法建立双向 LSP 的通信开销比现有算法至少减少RLA( )( 1)l l ln 。 证明 设标签和标签
20、请求消息的长度为分别为lP和 lL, hLS和 hRC分别为标签集(Label Set) 与ResvConf 消息的长度。定义建立 1 条双向 LSP 的通信开销 C 为所有节点发送的控制消息的比特数之和,计算如式(1): ,11imnijijCl(1) 其中,mi为第 i 个节点发送的控制消息总数,li,j为第 i 个节点发送的第 j 个控制消息的长度。于是,上文所述现有双向 LSP 生成算法的通信开销分别为 PR2( 1)( )C n ll 分建(2) ULS P LS R RC( 1)( )C n ll ll (3) GMPLS P L R( 1)( )C n lll (4) NLDM
21、P R( 1)( )C n ll (5) 不难看出, NLDM 算法的通信开销最小。而 EAEBL算法的通信开销为 EAEBL P L A( 1)( )C n lll (6) 由于 Resv 消息包含源节点地址(32 bit) 、标签(20 bit)和“ Message ID”(32 bit)等字段,因此有 RLAl ll (7) 结合式(5) 式(7),可得 EAEBL NLDMCC(8) 而且可进一步算得减少的通信开销 CS为 RLA( ) ( 1) (1962032)( 1) 144 144 (bit)SC lll nnn (9) 即 EAEBL 算法的通信开销低于现有相关算法,而且至少
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 单程 高效 快速 双向 标签 交换 路径 生成 算法 金鑫
限制150内