hql-基于多转发树的无中断域间路由协议

书书书 第３５卷　第１０期２０１２年１０月 计　　算　　机　　学　　报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｖｏｌ．３５Ｎｏ．１０Ｏｃｔ．２０１２　 收稿日期：２０１２０６３０；最终修改稿收到日期：２０１２０８０９．本课题得到国家自然科学基金（６１０７０１９９）、国家“九七三”重点基础研究发展规 划项目基金（２００９ＣＢ３２０５０３）资助．胡乔林，男，１９７９年生，博士，讲师，主要研究方向为容迟容断网络、网络生存性和虚拟网络．Ｅｍａｉｌ： ｈｕｑｉａｏｌｉｎ＠ｎｕｄｔ．ｅｄｕ．ｃｎ．彭　伟，男，１９７４年生，博士，副研究员，主要研究方向为路由协动、移动网络．陈　新，男，１９８１年生，博士，主要 研究方向为网络安全．苏金树，男，１９６２年生，博士，教授，博士生导师，主要研究领域为计算机网络、信息安全． 犕犉犜２犅犌犘：基于多转发树的无中断域间路由 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 胡乔林１）　彭　伟２）　陈　新１）　苏金树２） １）（空军预警学院五系　武汉　４３００１９） ２）（国防科技大学计算机学院　长沙　４１００７３） 摘　要　ＢＧＰ通过触发全局、反应式收敛应对链路或节点失效引起的拓扑变化，然而ＢＧＰ协议收敛时间长、收敛 过程中的瞬时失效严重降低了数据平面转发性能，难以支持关键业务流量．该文提出了容忍失效的ＭＦＴ２ＢＧＰ，通 过利用路径标识符以较低的消息开销构造符合ＢＧＰ策略的多转发树，使得每个ＡＳ获得多样性路径，当出现瞬时 失效时，在不改变协议动态性的情况下，允许节点动态切换报文转发路径以实现无中断报文转发，通过嵌入“失效 根源信息”以降低收敛时间，抑制瞬时失效以降低路由系统的扰动．通过在Ｉｎｔｅｒｎｅｔｌｉｋｅ拓扑上的大量实验表明，在 链路失效场景中与其它协议相比，ＭＦＴ２ＢＧＰ能有效改善收敛时间，降低转发中断时间，改善路由系统稳定性． 关键词　域间路由；瞬时失效；多转发树；多路径；快速恢复 中图法分类号ＴＰ３９３　　　犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１２．０２０２３ 犕犉犜２犅犌犘：犃犮犺犻犲狏犻狀犵犇犻狊狉狌狆狋犻狅狀犉狉犲犲犐狀狋犲狉犇狅犿犪犻狀犚狅狌狋犻狀犵犘狉狅狋狅犮狅犾犝狊犻狀犵犕狌犾狋犻狆犾犲犉狅狉狑犪狉犱犻狀犵犜狉犲犲狊 ＨＵＱｉａｏＬｉｎ１）　ＰＥＮＧＷｅｉ２）　ＣＨＥＮＸｉｎ１）　ＳＵＪｉｎＳｈｕ２） １）（犇犲狆犪狉狋犿犲狀狋犉犻狏犲，犃犻狉犉狅狉犮犲犚犪犱犪狉犃犮犪犱犲犿狔，犠狌犺犪狀　４３００１９） ２）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉，犖犪狋犻狅狀犪犾犝狀犻狏犲狉狊犻狋狔狅犳犇犲犳犲狀狊犲犜犲犮犺狀狅犾狅犵狔，犆犺犪狀犵狊犺犪　４１００７３） 犃犫狊狋狉犪犮狋　ＢＧＰｔｒｉｇｇｅｒｓｇｌｏｂａｌａｎｄｒｅａｃｔｉｖｅｒｏｕｔｉｎｇｃｏｎｖｅｒｇｅｎｃｅｔｏｄｙｎａｍｉｃａｌｌｙａｄａｐｔｔｏｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙａｎｄｐｏｌｉｃｙｃｈａｎｇｅｓｓｕｃｈａｓｌｉｎｋｏｒｎｏｄｅｆａｉｌｕｒｅｓ．Ｎｅｖｅｒｔｈｅｌｅｓｓ，ＢＧＰｆａｃｅｓｔｈｅｃｈａｌｌｅｎｇｅ ｏｆｌｏｎｇｃｏｎｖｅｒｇｅｎｃｅｔｉｍｅ，ｔｒａｎｓｉｅｎｔｆａｉｌｕｒｅｄｕｒｉｎｇｔｈｅｒｏｕｔｉｎｇｃｏｎｖｅｒｇｅｎｃｅ，ｗｈｉｃｈａｆｆｅｃｔｓｔｈｅｆｏｒ ｗａｒｄｉｎｇｐｅｒｆｏｒｍａｎｃｅｓｏａｓｔｏｈａｒｄｔｏｓｕｐｐｏｒｔｍｉｓｓｉｏｎｃｒｉｔｉｃａｌｔｒａｆｆｉｃ．Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓｔｈｅｐｒｏ ｔｏｃｏｌｆｏｒａｃｈｉｅｖｉｎｇｆａｉｌｕｒｅｔｏｌｅｒａｎｔｉｎｔｅｒｄｏｍａｉｎｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｎａｍｅｄＭＦＴ２ＢＧＰ，ｉｔｃｏｎｓｔｒｕｃｔｓ ｐｏｌｉｃｙｃｏｍｐｌｉａｎｔｍｕｌｔｉｐｌｅｆｏｒｗａｒｄｉｎｇｔｒｅｅｓｕｓｉｎｇｐａｔｈｉｄｅｎｔｉｆｉｅｒｗｉｔｈｌｏｗｍｅｓｓａｇｅａｎｄｐｒｏｃｅｓｓ ｏｖｅｒｈｅａｄ，ｗｈｉｃｈｍａｋｅｅｖｅｒｙＡＳｄｉｓｃｏｖｅｒｙｄｉｖｅｒｓｉｔｙｐａｔｈ，ＥｖｅｒｙＡＳｃａｎｓｗｉｔｃｈｔｒａｆｆｉｃｔｏｂａｃｋｕｐ ｐａｔｈｄｙｎａｍｉｃａｌｌｙｔｏａｃｈｉｅｖｅｄｉｓｒｕｐｔｉｏｎｆｒｅｅｆｏｒｗａｒｄｉｎｇｗｉｔｈｏｕｔｃｏｍｐｒｉｓｉｎｇｔｈｅｒｏｕｔｉｎｇｂｅｈａｖｉｏｒｉｎ ｔｈｅｐｒｅｓｅｎｃｅｏｆｔｒａｎｓｉｅｎｔｆａｉｌｕｒｅｓｃｅｎａｒｉｏ．ＭＦＴ２ＢＧＰｒｅｄｕｃｅｓｔｈｅｃｏｎｖｅｒｇｅｎｃｅｔｉｍｅｂｙｃａｒｒｙｉｎｇ “ｒｏｏｔｃａｕｓｅｎｏｔｉｆｉｃａｔｉｏｎ”ｉｎｕｐｄａｔｅｍｅｓｓａｇｅｓａｎｄｒｅｄｕｃｅｓｔｈｅｃｈｕｒｎｏｆｒｏｕｔｉｎｇｓｙｓｔｅｍｂｙｓｕｐｐｒｅｓｓ ｉｎｇｎｏｎｎｅｃｅｓｓａｒｙｒｏｕｔｉｎｇｕｐｄａｔｅｓ．Ｄｅｔａｉｌｅｄｅｘｐｅｒｉｍｅｎｔｓｏｎｉｎｔｅｒｎｅｔｌｉｋｅｔｏｐｏｌｏｇｙｓｕｇｇｅｓｔｔｈａｔ ＭＦＴ２ＢＧＰｒｅｄｕｃｅｓｃｏｎｖｅｒｇｅｎｃｅｔｉｍｅａｎｄｆｏｒｗａｒｄｉｎｇｄｉｓｒｕｐｔｉｏｎｔｉｍｅｉｎｌｉｎｋｆａｉｌｕｒｅｓｃｅｎａｒｉｏｓ， ｅｎｈａｎｃｅｓｔｈｅｒｏｕｔｉｎｇｓｔａｂｉｌｉｔｙｔｈａｎｏｔｈｅｒｐｒｏｔｏｃｏｌｓ． 犓犲狔狑狅狉犱狊　ｉｎｔｅｒｄｏｍａｉｎｒｏｕｔｉｎｇ；ｔｒａｎｓｉｅｎｔｆａｉｌｕｒｅ；ｍｕｌｔｉｐｌｅｆｏｒｗａｒｄｉｎｇｔｒｅｅｓ；ｍｕｌｔｉｐｌｅｐａｔｈ； ｆａｓｔｒｅｃｏｖｅｒｙ １　引　言 Ｉｎｔｅｒｎｅｔ已经发展成为重要的通信基础设施， 承载了许多如ＶｏＩＰ、在线游戏、远程医疗等对延迟 及中断敏感的关键业务，然而Ｉｎｔｅｒｎｅｔ却容易遭到 破坏，例如软硬件故障、误配置、攻击等因素都会造 成网络失效．通过对Ｓｐｒｉｎｔ骨干网链路故障进行分析［１］，人们发现失效几乎每天都会发生，且９０％属 于瞬时性故障．理想的路由协议应保证只要底层拓 扑连接就能提供持续通信．然而ＢＧＰ协议［２］缺乏生 存性保证，在失效时仅触发全局、反应式收敛应对拓 扑变化，相对于ＩＧＰ秒级的收敛，ＢＧＰ由于大量“路 径探索”［３］以及ＭＲＡＩ和ＷＲＡＴＥ定时器的限制， 导致收敛时间甚至达到３０分钟［４］，这进一步恶化了 转发中断．ＫａｔｚＢａｓｓｅｔｔ等人［５］发现即使多宿主ＡＳ 并不总能实现容错，ＢＧＰ导致大量多宿主ＡＳ经历 不可达事件，持续时间甚至长达数小时或天，其数量 与持续时间都远超预期，严重降低数据平面的转发 性能．Ｗａｎｇ［６］通过对顶级ＩＳＰ进行测量，发现ＢＧＰ收敛期间的动态性造成大量路由器经历瞬时路由失 效、环路，即使在失效切换和链路恢复时路由黑洞也 会造成数十秒的报文丢失． 可达性是路由协议的顶级目标，研究者通过加 速收敛以降低失效对转发中断的影响，包括Ｇｈｏｓｔ Ｆｌｕｓｈｉｎｇ［７］、ＥＰＩＣ［８］等通过抑制或嵌入“失效根源”信息以快速作废非法路径，但ＧｈｏｓｔＦｌｕｓｈｉｎｇ、 ＥＰＩＣ在Ｉｎｔｅｒｎｅｔｌｉｋｅ拓扑下，其加速收敛效果并不 明显．而且由于多数是瞬时失效，过快收敛反而给路 由器增加负担，带来路由的不稳定性．加速收敛并不 能满足关键应用需求，也不能消除收敛过程对转发 中断的影响．一些研究工作集中于扩展ＢＧＰ，比如 ＭＩＲＯ［９］、ＲＢＧＰ［１０］、Ｓｐｌｉｃｉｎｇ［１１］、Ｃｏｎｓｅｎｓｕｓ［１２］、 ＹＡＭＲ［１３］等采用预计算备份路径的方法，不同程度 上暴露底层拓扑冗余路径，但这些协议ＡＳ之间的 备份路径缺乏协调可能形成环路，也并不能保证每 个ＡＳ获得多样性路径，且部分协议难以实现完全 无中断转发． 针对抑制瞬时失效、无中断报文转发、低开销的 需求，本文提出了通过构造多转发树容忍失效的域 间路由协议（ＭｕｌｔｉｐｌｅＦｏｒｗａｒｄｉｎｇＴｒｅｅａｎｄＦａｉｌｕｒｅ ＴｏｌｅｒａｎｔＢＧＰ，ＭＦＴ２ＢＧＰ）以实现快速路由恢复， 其主要面临如下挑战：（１）在 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ＢＧＰ中，ＡＳ节点 无全局拓扑，使得每个ＡＳ难以获得、区分多样性路 径；（２）在构造多转发树时要求降低收敛时间，并保 证处理开销在合理范围内；（３）保证报文在多转发 树之间切换时不会形成环路．为此，ＭＦＴ２ＢＧＰ设 计主要包括３个关键部分，即控制平面的多转发树 构造、加速收敛与瞬时失效抑制、数据平面无中断报 文转发算法．该协议的特点在于：（１）充分利用底层 冗余拓扑，提供可保证的结构化多样性路径，避免了 备份路径之间可能的环路；（２）抑制瞬时失效，避免 失效全局可视化，增强了ＢＧＰ系统的稳定性；（３）从 数据平面保护流量，采取本地先验式的方法处理瞬 时失效引起的报文丢失，支持关键业务的应用； （４）具有可扩展性、兼容性，便于增量部署． 本文第２节介绍相关工作；第３节描述问题模 型；第４节设计ＭＦＴ２ＢＧＰ协议框架以及控制平面 的多转发树构造、加速收敛、失效抑制以及报文转发 算法；第５节对协议的正确性进行分析；第６节通过 模拟验证ＭＦＴ２ＢＧＰ的收敛性以及无中断转发性 能；最后对本文工作进行 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ． ２　相关工作 当前大部分研究工作主要利用冗余路径以应对 出现的失效，ＩＥＴＦＲＴＧＷＧ工作组致力于ＩＧＰ协 议的ＩＰＦＲＲ（ＩＰ快速重路由），比如Ｄｅｆｌｅｃｔｉｏｎｓ［１４］ 等，其主要思想是为可能出现的链路、节点失效预计 算备份路径．Ｍｅｄａｒｄ等人［１５］最早提出了冗余树的 方法以容忍单链路失效，Ｋｉｎｉ等人［１６］通过构造多冗 余树以容忍两条链路失效，然而在图论中计算冗余 路径的经典算法都需要获得全局一致性拓扑信息， 而域间路由系统中每个ＡＳ仅能获得局部拓扑信 息，无法进行有效集中式计算；其次由于Ｉｎｔｅｒｎｅｔ的 ＡＳ数量大，集中式计算复杂度非常高，即使是分布 式方法也由于协议复杂度过高而难以实现；最后由于 ＢＧＰ协议需要保证策略实现，进一步限制了可达性， 因此许多ＩＧＰ中的方法难以直接应用于ＢＧＰ中． 现有ＢＧＰ协议缺乏对多路径的考虑，缺乏发 现、使用多路径的能力，大量研究表明多路径可增强 网络容量、可靠性．ＭＩＲＯ［９］通过复杂的协商机制获 得多路径，依赖于配置通告备份路径的策略，是一种 无结构路径的方法，ＭＩＲＯ采用隧道机制区分那些 需要在备用路径上传输的报文，并且没有考虑快速 路由恢复．ＲＢＧＰ［１０］为ＡＳ通告一条与最佳路径不 相交的ＡＳ级备份路径以提高可靠性，这依赖于大 量手工配置通告备份路径的策略，是一种无结构路 径的方法，信令机制较复杂，且并不能完全保证获得 多样性路径，且需要特殊报文封装机制进行转发． ４２０２ 计　　算　　机　　学　　报 ２０１２年 Ｃｏｎｓｅｎｓｕｓ［１２］路由协议借鉴了分布式系统中快照实 现一致性的算法，将路由计算集中于顶级ＡＳ，这却 违反了ＡＳ自治性，当链路失效造成报文不能正常 转发时进入瞬时模式，采用偏转（Ｄｅｆｌｅｃｔｉｏｎ）、回退 （Ｂａｃｋｔｒａｃｋｉｎｇ）、备份（Ｂａｃｋｕｐ）机制发起本地重路 由．Ｓｐｌｉｃｉｎｇ［１１］利用ＢＧＰ路由器中已有的多条路径 构造多路径转发．ＹＡＭＲ［１３］为每个ＡＳ最佳路径的 每一跳都获得冗余标签路径，其平均ＲＩＢ／ＦＩＢ存储 平均至少增加４．６倍，且部分冗余路径对于快速恢 复难以发挥作用．ＡＣＦ［１７］在路由不一致的情况下采 用检测并恢复的方法，通过在报文头中添加路径踪 迹域、黑名单域等辅助路由决策和转发，较大程度增 加了报文头开销，可能形成违反ＡＳ策略的转发路 径．ＡｄｄＰａｔｈ［１８］通告多路径，需要全网路由器更新， 且增加了路由震荡的风险． 上述针对ＢＧＰ的多路径协议主要通过修改策 略使其在控制平面通告多路径，这需要复杂的信令、 决策机制等，是一种无结构的方法，并没有对ＢＧＰ 协议进行系统化的设计，对于多链路失效的转发缺 乏考虑；且这些协议对于路径多样性暴露程度并没 有确定性的保证，且基本上没有考虑抑制瞬时失效 的方法，对于多路径协议的收敛期间的动态行为缺 乏考虑．对于降低协议开销、保证无中断转发、抑制 瞬时失效这３个相互影响的问题，已有工作并不能 完全解决．ＭＦＴ２ＢＧＰ通过为目标前缀构造冗余 树，每个ＡＳ自动获得结构化的多样性路径，而无需 大量人工配置复杂策略，可以实现负载均衡、降低 ＢＧＰ扰动，面临失效时动态切换路径以实现快速路 由恢复，在不影响报文转发的情况下抑制瞬时失效， 增强ＢＧＰ路由系统的稳定性． ３　网络模型和问题分析 ３１　网络模型 ＭＦＴ２ＢＧＰ做出如下设定（其中设定（１）是为了 简化表述，这是当前研究普遍采用的设置，不影响协 议的正确性，而（２）、（３）是研究ＢＧＰ［２］的基本设置）： （１）每个ＡＳ狏仅由单边界网关路由器节点组成 （不考虑ｉＢＧＰ），狏对每个狌∈犘犲犲狉狊（狏）（犘犲犲狉狊（狏）为狏 的邻居节点）的导入、导出路径分别保存在ｒｉｂ＿ｉｎ（狏← 狌）、ｒｉｂ＿ｏｕｔ（狏→狌）中，ｌｏｃ＿ｒｉｂ（狏）保存本地最佳路径； （２）ＡＳ的导入导出策略服从“ＧａｏＲｅｘｆｏｒｄ”原 则［１９］，即仅出现“ｖａｌｌｅｙｆｒｅｅ”的路径； （３）ＡＳ间建立ｅＢＧＰ会话，路由更新消息服从 ＳＰＶＰ［２０］模型． ３２　问题的提出与分析在给定拓扑下网络容忍失效的性能主要取决于 拓扑暴露程度、协议响应性两个因素．ＢＧＰ协议在 这两个方面却存在不足．虽然ＢＧＰ将快速响应性置 于一致性之上，但是却带来了大量环路以及路由黑 洞，直接影响转发性能；同时，尽管Ｉｎｔｅｒｎｅｔ底层路 径具有充分冗余［２１］，ＡＳ无可替代路径的不到 ５％［９］，ＢＧＰ协议对于底层路径暴露程度不足，缺乏 发现、区分和使用多路径的能力，多宿主ＡＳ也仅能 控制报文出口，而仍然缺乏容错性［５］，这主要是由于 ＢＧＰ缺乏故障隔离能力、仅通告并使用单路径、协 议的动态性造成的瞬时性不可达、环路（将其统称为 瞬时路由失效）［２２］，从而造成了网络可用性相对较 低，而一些多路径ＢＧＰ协议却增加了环路发生的可 能性［１８］，比如ＲＢＧＰ为当前下一跳通告备份路径 时，如图１中ＡＳ２为下一跳ＡＳ１通告备份路径 （２０），当ＡＳ１ＡＳ０和ＡＳ２ＡＳ０多链路同时失效 时，由于ＡＳ１和ＡＳ２独立决策，将会在造成备份路 径之间形成环路，甚至某些单链路特殊场景下也可 能造成环路．Ｓｐｌｉｃｉｎｇ［１１］仅利用已有路径，却没有考虑如何获得多样性路径，比如ＡＳ０ＡＳ３断开时 Ｓｐｌｉｃｉｎｇ仍将产生失效．合理发现、利用多样性路径是解决这些问题的关键．基于以上观察，在设计 ＭＦＴ２ＢＧＰ时对ＳＰＶＰ［２０］定义进行扩展以发现、区 分多路径；在多路径开销和性能之间折衷，确保协议 的收敛性和正确性． 图１　链路故障导致ＢＧＰ瞬时失效 定义１．　合法路径．ＢＧＰ中合法路径必须服从策略、能够到达犱（即不含失效链路／节点）；其次路 径犘＝π（狌，犱）是合法的必须满足：犻，狀犻１， π（狌，犱）＝π（狌，狏犻）＋π狌（狌∈狏犻，犱）＝π（狌，狏犻）＋π（狏犻， 犱），即π狌（狌∈狏犻，犱）＝π（狏犻，犱），即合法路径不会造成报文偏转．其中路径犘＝π（狌，犱）＝（狌，狏１，狏２，…， 狏狀，犱），表示狌分配的到达犱的节点序列，π狌（狌∈狏犻， 犱）表示在狌的路由 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 中所看到的狏犻到达犱的路 ５２０２１０期 胡乔林等：ＭＦＴ２ＢＧＰ：基于多转发树的无中断域间路由协议 径，而π（狏犻，犱）表示狏犻实际采用转发路径，犘·犙表示为路径犘、犙拼接． 设非空合法路径犘、犙完全不相交；或者在某点 交叉，即犻，犼，使得狏犻＝狑犼≠犱，或者犘与犙仅在犱汇合，如果π狌（狌∈狏犻，犱）＝π狕（狕∈狑犼，犱），那么犘、犙之间是一致的，一致性路径不会造成转发环路． 定义２．　隐藏路径与备份路径．指底层拓扑存 在到达犱的合法路径，但ＡＳ却没有获取该路径，其 具有相对性，比如图１中，ＡＳ３可以通过（３５６２０） 或（３４６２０）合法路径封装报文到达目标，却 被ＡＳ４、ＡＳ５隐藏．备份路径是指可到达犱且没有被 选作最佳路径的合法路径，备份路径也可能被隐藏． 定义３．　路径不相交度．对于给定路径犘、犙， 如果犘和犙具有不同下一跳，犇犻狊犼狅犻狀狋（犘，犙）＝１－ ｜犘∩犙｜／｜犘｜（计算｜犘∩犙｜时不包含源、目的节 点）；否则犇犻狊犼狅犻狀狋（犘，犙）＝０，这是由于具有相同下 一跳的路径无法用于快速恢复．对于节点狌的合法 路径犘、犙，如果满足犇犻狊犼狅犻狀狋（犘，犙）＞０，则称狌具 有多样性路径． 定义４．　转发树．对于给定目标前缀犱，存在稳 定的路径分配使ＢＧＰ收敛后，所有节点最佳路径最 终形成以犱为根节点的转发树［２０］，转发树中所有节 点转发路径具有一致性，即如果π（狌，犱）＝（狌，狏， 犘），那么π（狏，犱）＝（狏，犘）．由于ＢＧＰ的策略限制， 其转发树并不一定是最短路径树． 定义５．　路径标识（ＰａｔｈＩｄｅｎｔｉｆｉｅｒ，ＰＩＤ）．当 存在多条到达目标前缀的路径时，为了区分、处理每 条合法路径，节点需要同时根据前缀狆狉犲犳犻狓和特定 标识符ψ区分路径，即利用（狆狉犲犳犻狓，ψ）路径标识符唯一标识一条路径犘． 定义６．　秩函数λ狏：犘狏→犖，对于犘∈犘狏，犘狏＝ ｛犘｜犘＝狏·π（狏，犱），狏∈犘犲犲狉狊（狌）｝，犘狏表示从狏到 达犱的合法路径集合，如果犘１、犘２∈犘狏，λ狏（犘１）＞ λ狏（犘２），那么犘１具有更高优先级． 定义７．　瞬时失效节点．指出现失效后，节点狏 的狉犻犫＿犻狀（狏）中无可到达犱的合法路径，此时节点可 行路径集为空或包含非法路径，此时会造成报文丢 失或者环路［２２］．如图１所示，目标前缀犱位于ＡＳ０， ＡＳ旁矩形框为根据ＶａｌｌｅｙＦｒｅｅ得到的路由表， 比如ＡＳ５具有３条到达ＡＳ０的路径，ＡＳ５根据 “ＰｒｅｆｅｒＣｕｓｔｏｍｅｒ”优选（５３０）作为最佳路径．假设 链路ＡＳ０ＡＳ３断开，ＡＳ３发送撤销消息到ＡＳ４和 ＡＳ５，ＡＳ５将根据其偏好策略优先选择（５４３０）， 而ＡＳ４将选择（４５３０）路径作为最佳路由， ＷＲＡＴＥ（撤销速率限制定时器）使得ＡＳ２和ＡＳ３ 延迟通告新的可用路径，此时ＡＳ５、ＡＳ４之间形成 环路，ＡＳ３无到达ＡＳ０的路径．即ＡＳ３、ＡＳ４、ＡＳ５ 经历瞬时失效． 定义８．　转发中断．转发路径是指在时刻狋，报 文从狌发送到犱所实际经过的节点序列，表示为 犳狅狉狑犪狉犱（狌，犱），如果狏∈犳狅狉狑犪狉犱（狌，犱），狏的转发 平面中的下一跳为空或陷入环路，则称之为转发中 断（本文忽略失效检测时间，ＢＦＤ机制可将失效检 测时间降至１５ｍｓ以内，Ｃｉｓｃｏ路由器已经普遍实现 ＢＦＤ）．需要注意的是，节点瞬时失效仅是转发中断 的必要条件，比如在图１中，如果ＡＳ２ＡＳ０链路失 效，虽然ＡＳ６采用（６２０）不是合法路径，但是由于 ＡＳ２具有冗余路径，在检测到失效以后能够迅速切 换（２１０），此时并无节点经历转发中断．而在一些 加速收敛协议中，如ＧｈｏｓｔＦｌｕｓｈｉｎｇ将使ＡＳ２快速 撤销路径（２０），如果ＡＳ６无备份路径，将导致ＡＳ６ 也经历转发中断，数据平面的转发中断相对于ＢＧＰ 收敛时间更准确度量协议性能［２３］，文献［５］也指出 控制平面的可达与数据平面的可达并不完全相关， 本文也将用瞬时失效率、转发中断作为衡量协议性 能的重要指标． ４　犕犉犜２犅犌犘协议设计 ４１　犕犉犜２犅犌犘基本框架 ＢＧＰ路由系统表示为犛＝〈犌，犘狅犾犻犮狔（犌），狊〉，其中ＡＳ图表示为犌＝（犞，犈），犞＝｛０，１，…，狀｝， 犘狅犾犻犮狔为所有节点的策略集合．ＢＧＰ系统状态表示为元组〈狉０，狉１，…，狉狀〉，其中狉犻表示ＡＳ犻的路由表中 所包含的到达犱的路径集合，狆∈狉犻，狊０表示犱发起 通告时的初始状态，狊０＝〈狉００，狉０１，…，狉０狀〉．当处于收敛 状态狊犳犻狀犪犾时，所有节点的转发路径将形成以犱为根 的最佳转发树犅犲狊狋＿犜狉犲犲（犱，〈狉犳犻狀犪犾０，狉犳犻狀犪犾１，…， 狉犳犻狀犪犾狀〉）＝犌（犞′，犈′），且有犞′＝｛狀犼∈犞｜狆∈狉犼｝， 犈′＝∪狀犼∈犞′｛（狌，狏）∈犈狘狆∈狉犼∧狆 ＝狏１，狏２，…，狏（ ）犿∧（（狌＝狀犼∧狏＝狏１）∨ （狌＝狏犽∧狏＝狏犽＋１））｝ （１） 　　当链路失效后ＢＧＰ重新收敛形成新的以犱为 根的转发树．如图１中，ＡＳ０ＡＳ３断开后收敛最终 得到失效后转发树．基于以上观察，如果各个节点在 失效前能够发现、预计算出备份转发树，就可以保证 每个ＡＳ在面临链路／节点失效的时候，仍然存在合 法备份路径，从而将流量切换到备份转发树中，且备 ６２０２ 计　　算　　机　　学　　报 ２０１２年 份转发树路径上具有完全一致性，其结构化性质阻 止了环路形成．然而，由于ＢＧＰ并不能获得全局 拓扑进行有效集中式计算链路或者节点不相交 树［１５１６］，而注入失效链路并强制其收敛获得失效后 转发树，其收敛时间过长且会中断报文转发．为此， ＭＦＴ２ＢＧＰ对协议通告过程进行修改，添加路径标 识符以区分、获得结构化的多样性路径．节点为了能 够利用多条路径进行无环转发，也需要为多路径分 配路径标识符，任意节点狏必须实现如下映射： 犘犪狋犺犐犇狏狆犪狋犺，（ ）犱：犘犪狋犺→犘犐犇 犉狅狉狑犪狉犱狏犘犐犇，（ ）犱：犘犐犇→烅 烄 烆 犘犪狋犺 （２） 　　路径标识函数犘犪狋犺犐犇狏，即节点狏需要为每条 合法路径从路径标识集合犘犐犇中选择合适标识符 ψ犻狏，其中ψ犻狏表示节点狏的第犻条路径标识符，而转发函数犉狅狉狑犪狉犱狏则根据ψ（ψ∈犘犐犇）进行报文转发，将ψ映射到对应的路径犘＝（狏１，狏２，…，狏狀），节点狏犽和狏犽－１需正确解释ψ，且狏犽能够将报文转发到狏犽－１，即犉狅狉狑犪狉犱狏犽（ψ，犱）＝狏犽－１，１犻狀．其中路径标识符可以是全局一致标识或本地分配的标识符， 而本地分配标识符更加灵活，但狏犽、狏犽－１之间需对本 地标识符ψ犼狏犽以及ψ犻狏犽－１按照式（２）的条件协商后进行映射转换，即对于标识符ψ路径犘上相邻节点，如图２（ａ）所示，犿犪狆（ψ犼狏犽）＝犿犪狆（ψ犻狏犽－１）＝ψ以保证转发一致性，标识符映射可采用与Ｄｅｆｌｅｃｔｉｏｎ［１４］类 似的方法，为表述方便本文采用全局一致性标识． 在不影响理解的情况下，本文中将网络节点等 同于ＡＳ节点．对于标识符ψ和其对应转发树ψ也不进行区分，对于转发树ψ（非最佳转发树）中节点对应ψ的路径，也称为该节点的备份路径． 图　２ ４２　控制平面多转发树构造与更新 ＭＦＴ２ＢＧＰ对路由通告、路由决策进行了相应 的修改，如图１中，ＡＳ０根据本地策略向３个邻居节 点ＡＳ１、ＡＳ２、ＡＳ３通告前缀时分别分配标识符ψ１０、 ψ２０、ψ３０（简记为ψ１、ψ２、ψ３）．各节点（不含ＡＳ７、ＡＳ８）最终获得多路径如图３所示，其中对更新消息处理 顺序可能导致中间状态不同，但最终收敛结果一致， 形成３个不同转发树，简记为ψ１＿犜狉犲犲、ψ２＿犜狉犲犲、 ψ３＿犜狉犲犲．其中对于ＡＳ７仅能通过上行路径（ｕｐｈｉｌｌ）［１９］到达目标前缀，ＡＳ６和ＡＳ２会导出所有本地合法路 径到ＡＳ７，ＡＳ７可根据本地策略决定各个路径标识 上的最佳路径．图３表现了协议运行过程，暂时并没 有考虑将具有相同下一跳的路径合并以降低开销以 及加速收敛等优化操作．其中，图３中“”表示发送更新消息，下划线“—”表示该节点ｒｉｂ＿ｉｎ发生变 化，路由表中斜体部分表示可以合并的路径，设置最 佳路径标识符“犅犲狊狋”是为了与当前协议兼容，并且 避免由于标识符数量过少而导致部分节点使用次优 路径（如果不考虑“犅犲狊狋”，更容易实现，但是却违反 了标准ＢＧＰ语义）． 图３　ＭＦＴ２ＢＧＰ更新消息处理过程示例 当节点检测到最佳路径的下一跳失效后，如果 该节点具有不相交度大于０的备份路径，通过修改 报文头以动态切换到具有不同标识符上的转发树， 实现无中断转发． ４．２．１　前缀通告 在ＭＦＴ２ＢＧＰ协议中，ＡＳ狏发起前缀通告时， 针对不同的节点对〈狏，狌〉为每条路径分配标识符，狏 的ｌｏｃ＿ｒｉｂ发生改变并在通过导出策略后，需将对应 标识符（犪狀狀＿狆犻犱）的路径信息发送到邻居节点狌．当 狏的邻居节点数大于可用路径标识符数量，将其余 的邻居ＡＳ路径标识符设置为隐藏标识符（犎犻犱犲＿ 犘犐犇），表示该路径仅可能被部分ＡＳ选作最佳路 ７２０２１０期 胡乔林等：ＭＦＴ２ＢＧＰ：基于多转发树的无中断域间路由协议 径，但是并不会传播到全网，从而在暴露的路径数量 以及开销之间进行折衷．如果发起前缀通过的ＡＳ 仅有单条路径，如图２（ｂ）所示，此时ＡＳ０可以将路 径标识符池［ψ１，ψ２，ψ３］通告给ＡＳ１，然后ＡＳ１从标识符池中取出标识符并通告给不同邻居，或者ＡＳ１ 自主对不同邻居分配路径标识符． 通过分配路径标识符使得路由器能够区分、利 用多路径，狏存储的ｒｉｂ＿ｉｎ（狏←狌）、ｒｉｂ＿ｏｕｔ（狏→狌）、 ｌｏｃ＿ｒｉｂ（狏）以及更新报文狌狆犱犪狋犲数据结构修改为映射类型，比如某个完整的更新报文将包括（狆犲犳犻狓， 犘犐犇，犃犛＿犘犪狋犺）三个域，分别表示前缀、标识符以及 ＡＳ路径．其通告过程如过程１所示，其中省略了 ＭＲＡＩ设置等语句．过程１中第１～３步表示构造原 始的通告路径．第４～１０步表示依据路由策略从路 径标识符池中选取路径标识符，并构造对应标识符 的更新消息．第１１～１３步则表示将包含标识符的更 新消息发送到邻居节点中． 过程１．　路由器狏目标前缀通告过程． ／狏表示发起通告的路由器，狆狉犲犳犻狓为目标前缀，犘犲犲狉狊（狏）表示其邻居列表，犘犐犇＿犛犲狋表示可用路径标识符集合， 狌狆犱犪狋犲为路由更新消息／ １．犘狅狉犻犵犻狀··＝狆犪狋犺＿犻狀犻狋（狆狉犲犳犻狓）／／构造通告路径 ２．狏．狅狉犻犵犻狀＿狉犻犫（狆狉犲犳犻狓）··＝犘狅狉犻犵犻狀 ３．ＩＦ狏．犘犪狋犺＿犛犲犾犲犮狋犻狅狀（狆狉犲犳犻狓）＝＝Ｔｒｕｅ／／检测ｌｏｃ＿ｒｉｂ是否改变 ４．ＦＯＲＥＡＣＨ狑∈狆犲犲狉狊（狏）ＤＯ ５．ＩＦ狏．犲狓狆狅狉狋＿狆狅犾犻犮狔（狑，狆狉犲犳犻狓，狅狉犻犵犻狀＿狆犪狋犺）＝＝Ｔｒｕｅ ＆＆狏．犵犲狋＿犾犻狀犽（狑）≠ｄｏｗｎ／／检测到达对应邻居节点的路径无失效且能通过导出策略 ６．ＩＦ犘犐犇＿犛犲狋＝＝ ７． 犪狀狀＿狆犻犱··＝犎犻犱犲＿犘犐犇 ８．ＥＬＳＥ ９． 犪狀狀＿狆犻犱··＝犘犐犇＿犛犲狋．狆狅狆（）／／获得路径标识符 １０．ＥＮＤＩＦ １１．狌狆犱犪狋犲＝狏．犾狅犮＿狉犻犫［犪狀狀＿狆犻犱］／／根据标识符构造更新消息 １２．狏．犲狓狆狅狉狋＿犪犮狋犻狅狀（犪狀狀＿狆犲犲狉，狆狉犲犳犻狓，狌狆犱犪狋犲） １３．狏．狊犲狀犱＿狌狆犱犪狋犲（狑，犪狀狀＿狆犻犱，狌狆犱犪狋犲）／／发送更新报文到狑 １４．ＥＮＤＩＦ １５．ＥＮＤＦＯＲ １６．ＥＮＤＩＦ ４．２．２　路由更新 节点接收到路由更新消息后，将启动路由更新 发送的过程，其服从ＳＰＶＰ模型［２０］．如过程２所示， 其中第１～４步表示狏接收到狌更新报文以后，狏根 据导入策略对更新报文进行过滤．第５～９步中，狏 从更新报文中提取所有路径标识符对应的路径信 息，狏更新所保存的ｒｉｂ＿ｉｎ（狏←狌）．第１０～１３步中狏 调用本地路径选择过程，使用秩函数λ狏犫犲狊狋从所有可 行路径中选择最佳路径，然后为每个路径标识符计 算新的最佳路径，并最终下载到ＦＩＢ中．其中在过 程２中，狏中具有标识符ψ犻的路径集合表示为犘狏ψ犻， βψ犻表示对应标识符的最佳路径，令λ狏ψ犻表示对应路径标识符的秩函数，要求选择最大不相交多样性路径． 过程２．　路由器狏路径选择过程． １．ＩＦ犾狅狅狆＿犱犲狋犲犮狋犻狅狀（狌狆犱犪狋犲）＝＝Ｔｒｕｅ　　／／环路检测 ２．　　ＲＥＴＵＲＮ ３．狏．犻犿狆狅狉狋＿狆狅犾犻犮狔（狌，狌狆犱犪狋犲） ／／根据导入策略对狌狆犱犪狋犲报文进行过滤并修改路径属性 ４．狏．犻犿狆狅狉狋＿犪犮狋犻狅狀（狌，狌狆犱犪狋犲） ５．ＦＯＲＥＡＣＨ（犘犐犇，犘犪狋犺）∈狌狆犱犪狋犲［狆狉犲犳犻狓］ＤＯ 　／／遍历狌狆犱犪狋犲中所有标识符对应的路径信息 ６．　ＩＦ犘犪狋犺＝＝ ７．　　Ｄｅｌ狏．狆犲犲狉狊［狌］．ｒｉｂ＿ｉｎ［狆狉犲犳犻狓］［犘犐犇］ ８．　ＥＬＳＥ ９．　　狏．狆犲犲狉狊［狌］．ｒｉｂ＿ｉｎ［狆狉犲犳犻狓］［犘犐犇］··＝犘犪狋犺 　　　　　／／狏更新对应的ｒｉｂ＿ｉｎ（狏←狌） １０．狅犾犱＿狉犻犫＝犆狅狆狔（狏．ｌｏｃ＿ｒｉｂ［狆狉犲犳犻狓］）／／复制原有ｌｏｃ＿ｒｉｂ １１．β犫犲狊狋··＝ｍａｘ（λ狏犫犲狊狋（∪犘狏ψ犻））／／从所有路径标识符中选择最佳路径 １２．　　狏．ｌｏｃ＿ｒｉｂ［狆狉犲犳犻狓］［犫犲狊狋］··＝β犫犲狊狋１３．犻狀狊狋犪犾犾＿犉犐犅（β犫犲狊狋）１４．ＦＯＲＥＡＣＨψ犻∈犘犐犇＿犛犲狋ＤＯ １５．　βψ犻＝··＝ｍａｘ（λ狏ψ犻（犘犪狋犺狏ψ犻））／／为每个路径标识符选择对应的最佳路径，且满足路径多样性要求 １６．　狏．ｌｏｃ＿ｒｉｂ［狆狉犲犳犻狓］［ψ犻］··＝βψ犻１７．　犻狀狊狋犪犾犾＿犉犐犅（βψ犻）１８．ＩＦ狅犾犱＿狉犻犫≠狏．ｌｏｃ＿ｒｉｂ［狆狉犲犳犻狓］／／如果ｌｏｃ＿ｒｉｂ改变，则将向每个狆犲犲狉发送更新消息 １９．　ＲＥＴＵＲＮＴｒｕｅ，ＴＨＥＮ狊犲狀犱＿狌狆犱犪狋犲（狆犲犲狉狊（狏）） ２０．ＥＬＳＥ ２１．　ＲＥＴＵＲＮＦａｌｓｅ ４３　多转发树下的加速收敛 与标准ＢＧＰ协议构造单个以犱为根的转发树 相比，ＭＦＴ２ＢＧＰ在构造多转发树时，为了传播隐 藏路径也相应增加了一定的开销．ＭＦＴ２ＢＧＰ则将 ＥＰＩＣ［８］的思想扩展到多路径场景以加速协议收敛 （简称ＭＦＴ２ＥＰＩＣ）．ＭＦＴ２ＥＰＩＣ主要针对各标识 符上的路径之间存在的依赖性，在每条标识符路径 上添加不同的序列号（犳犲狊狀）进行区别，即犳犲狊狀＝ （〈狓，狔〉：犖）表示链路两边节点有序对与序列号的 组合．即完整的更新消息包含［狆犲犳犻狓，犘犐犇］＋ ［犃犛＿犘犪狋犺］＋｛犳犲狊狀犔犻狊狋｝，犳犲狊狀犔犻狊狋包含对应犃犛＿犘犪狋犺 中的犳犲狊狀列表．当出现链路失效（或更改策略）撤销 ［狆犲犳犻狓，ψ］相关路径时，狌发送的撤销消息中包含 犳犲狊狀犔犻狊狋１信息，令犳犲狊狀犔犻狊狋１＝［（〈犪１，犫１〉，狀１），（〈犪２， 犫２〉，狀２），…，（〈犪犽，犫犽〉，狀犽）］，狏接收撤销消息后，狏可 ８２０２ 计　　算　　机　　学　　报 ２０１２年 利用撤销消息中的犳犲狊狀犔犻狊狋信息作废其它邻居节点通告的所有标识符上的非法路径，设狏存储的某 条路径犘对应的犳犲狊狀犔犻狊狋２＝［〈犪′１，犫′１〉，狀１），〈犪′２， 犫′２〉，狀２），…，〈犪′犾，犫′犾〉，狀′犾）］，且犽犾．如果存在（犪犻＝＝ 犪′犻）∧（犫犻＝＝犫′犻）∧（狀犻＝＝狀′犻）），犻＝１，２，…，犽，即 犳犲狊狀犔犻狊狋２与撤销路径犳犲狊狀犔犻狊狋１相关，此时可以快速作废非法路径犘，从而加速收敛并消除收敛过程中 可能的环路． ４４　瞬时失效抑制在不影响转发连续的情况下，可以利用多路径 压制瞬时失效以实现故障隔离能力，避免频繁收敛 带来的路由震荡，从而降低控制平面的扰动．基本思 想是当最佳路径失效后，如果备份路径具有不同的 下一跳，则并不发送更新消息，并且设置合理定时器 （绝大多数ＢＧＰ故障将会在１０ｍｉｎ内恢复［２４］，可据 此设置默认定时器）．如果定时器超时则需要发送路 由更新消息，触发路由重新收敛．比如狌检测到路径 标识符ψ对应的路径失效，如果狌仍然具有其它可行转发树对应的路径，在不影响持续转发的情况下， 狌可对与ψ相关的失效消息进行抑制，将该策略称为ＳＵＰ（ＳｕｐｐｒｅｓｓａｌｌＵＰｄａｔｅｍｅｓｓａｇｅ）． ＳＵＰ策略将会使得部分节点在压制失效后可 能使用非最佳路径，比如图１中链路ＡＳ０ＡＳ３失效 后，将导致ＡＳ３、ＡＳ４、ＡＳ５的最佳路径发生变化，如 果ＡＳ３压制失效信息，在消息压制期间，将会使得 受到失效影响的节点ＡＳ３、ＡＳ４、ＡＳ５到达目标的跳 数增加．为此，设置新的路由策略ＳＮＵＭ（Ｓｕｐｐｒｅｓｓ ＮｏｎＢｅｓｔＵｐｄａｔｅＭｅｓｓａｇｅ），即狌在检测到失效后，如果其狌的最佳路径改变，狌在利用备份路径转发 的同时也发送更新消息，如图１中ＡＳ０ＡＳ３失效 后，ＡＳ３将发送与ψ３相关的路由更新消息，但是由于ψ３并不改变图１中ＡＳ１、ＡＳ２、ＡＳ６的最佳路径，因此，ＡＳ５可以安全压制更新路由消息，不再进一 步向ＡＳ６发送消息，并避免持续使用次优路径． ４５　报文转发过程为了保证转发一致性，需要修改报文头格式并 增加路径标识符ψ，通常可以在ＩＰ报文头中添加额外的ｓｈｉｍ报文头［１４］，或者利用现有ＩＰ报文头中 ＴＯＳ或ＤＳＣＰ域，通过报文头中标识符ψ指示报文当前所采用的转发树． 在链路失效时，失效检测节点具有特殊的角色， 失效节点在查找备份可用转发树的同时，还需要将 报文头中的路径标识符修改为所切换的转发树标识 符．在单链路失效时，由于转发树中对应的所有节点 转发视图具有一致性，在节点间无需协调的情况下， 检测失效的节点仅需要发起本地重路由即可保证无 环转发． 当出现节点失效、多链路失效时，以及采用瞬时 失效抑制，将会造成各个ＡＳ节点之间转发视图不 一致，单失效下的转发机制并不能充分利用已经获 得的冗余路径，而且还可能出现转发环路，因此还需 要信令机制以避免环路．如图１中，如果ＡＳ２ＡＳ０ 和ＡＳ１ＡＳ０同时断开，如果ＡＳ２检测到失效后采 用图３中标识符为ψ１的路径，修改报文头标识符为 ψ１，并将报文转发到ＡＳ２；同时，由于ＡＳ２发现ＡＳ２ＡＳ０断开，由于ＡＳ１与ＡＳ２之间无协调，如果 ＡＳ１选择ψ２路径，将导致ＡＳ１和ＡＳ２之间形成环路，在这种多失效场景下必须利用辅助信息才能无 环转发． 为了充分利用已获得的多转发树，ＭＦＴ２ＢＧＰ 在报文中添加“报文经历信息”犝狊犲犱＿犘犐犇，表示报 文已经使用过的转发树．如图２（ｂ）中所示，节点在 接收到报文后，提取报文头中犝狊犲犱＿犘犐犇信息以避 免重复选择同一转发树，该信息存储实际不超过 ２ｂｉｔｓ． 具体报文转发如过程３所示，其中犅犲狊狋＿犜狉犲犲 表示最佳转发树对应的路径，其下一跳表示为 犫犲狊狋＿狀犺狅狆（犱，犅犲狊狋＿犜狉犲犲），而根据路径标识符ψ形成的转发树为ψ＿犜狉犲犲，其下一跳表示为犫犲狊狋＿狀犺狅狆（犱， ψ＿犜狉犲犲），犳狅狉狑犪狉犱＿狆犪犮犽犲狋（狀犺狅狆，狋狉犲犲）表示根据对应转发树转发报文，犆犺犪狀犵犲＿犺犲犪犱犲狉（狋狉犲犲，狋狉犪狀狊犻犲狀狋）表示修改报文头中的路径标识符为特定的转发树， 并且设置报文进入失效转发模式． 过程３．　报文转发过程． １．狀犺狅狆··＝犅犲狊狋＿狀犺狅狆（犱，狆犪犮犽犲狋．犮狌狉狉犲狀狋＿犘犐犇）／／按指定标 识符转发 ２．ＩＦ犱≠狀犺狅狆 ３．ＩＦ狏．ｇｅｔ＿ｌｉｎｋ（狀犺狅狆）＝＝犝犘 ４．犳狅狉狑犪狉犱＿狆犪犮犽犲狋（狀犺狅狆，狆犪犮犽犲狋．犮狌狉狉犲狀狋＿犘犐犇） ５．ＥＬＳＥ ６．ＦＯＲＥＡＣＨ（犘犐犇，犃犛＿犘犪狋犺）∈狏．ｌｏｃ＿ｒｉｂ［狆狉犲犳犻狓］ＤＯ ７． ＩＦ犘犐犇ｎｏｔｉｎ狆犪犮犽犲狋．犝狊犲犱＿犘犐犇ａｎｄ犘犐犇≠犅犲狊狋＿犜狉犲犲 ８．ＩＦ犃犛＿犘犪狋犺．狏犪犾犻犱＝＝Ｆａｌｓｅ／／如果犘犐犇对应的犃犛＿犘犪狋犺 是非法路径，需要将其加入报文犝狊犲犱＿犘犐犇中 ９． 狆犪犮犽犲狋．犃犱犱＿犝狊犲犱＿犘犐犇（犘犐犇） １０． ＣＯＮＴＩＮＵＥ １１．ＥＮＤＩＦ １２．（狀犲狑犺狅狆，狀犲狑＿狋狉犲犲）··＝犳犻狀犱＿犅犲狊狋＿犘犐犇＿狀犺狅狆（犱，犘犐犇） ／／根据策略从所有可行标识符中选择路径 １３．ＥＮＤＩＦ １４．ＩＦ狀犲狑犺狅狆≠ａｎｄ狏．ｇｅｔ＿ｌｉｎｋ（狀犲狑犺狅狆）≠Ｄｏｗｎ １５． 犆犺犪狀犵犲＿犺犲犪犱犲狉（狀犲狑＿狋狉犲犲，狋狉犪狀狊犻犲狀狋） ９２０２１０期 胡乔林等：ＭＦＴ２ＢＧＰ：基于多转发树的无中断域间路由协议 １６． 狆犪犮犽犲狋．犃犱犱＿犝狊犲犱＿犘犐犇（狀犲狑＿狋狉犲犲） １７． 犳狅狉狑犪狉犱＿狆犪犮犽犲狋（狀犲狑犺狅狆，狀犲狑＿狋狉犲犲） １８．ＥＬＳＥ １９． ＩＦ狏．ｌｏｃ＿ｒｉｂ［狆狉犲犳犻狓］［犅犲狊狋＿犜狉犲犲］．狏犪犾犻犱＝＝Ｔｒｕｅ 　　　　　　　／／在无对应路径标识符时，如果犅犲狊狋＿犜狉犲犲 可行则通过犅犲狊狋＿犜狉犲犲转发 ２０． 狀犺狅狆··＝犅犲狊狋＿狀犺狅狆（犱，狆犪犮犽犲狋．犮狌狉狉犲狀狋＿犘犐犇） ２１． 犳狅狉狑犪狉犱＿狆犪犮犽犲狋（狀犺狅狆，狆犪犮犽犲狋．犮狌狉狉犲狀狋＿犘犐犇） ２２． ＥＬＳＥ ２３． 犇狉狅狆狆犪犮犽犲狋 ２４． ＥＮＤＩＦ ２５．ＥＬＳＥ ２６．犳狅狉狑犪狉犱＿狊狌犮犮犲狊狊（） ２７．ＥＮＤＩＦ 过程３中的第１～４步，报文依据对应标识符转发．第６～１２步在未使用过的转发树中选择备份路径（瞬时失效中优先选择非犅犲狊狋＿犜狉犲犲以降低协议 动态性的影响），需要说明的是，当节点具有多个备 份转发树时，节点可以根据策略选择最短路径树 犛犜犉（或者固定优先选择某个特定标识的转发树 犛犘犜［１６］，并且将已失效转发树标识加入报文中的 犝狊犲犱＿犘犐犇域中）．第１４～１７步中，节点将根据修改后的转发树标识进行转发．第１９～２１步中，当节点在无可用转发树时，则尝试使用犅犲狊狋＿犜狉犲犲转发． 该转发过程可以有效解决多链路失效下的转发 环路，比如在图１中，当节点失效引起ＡＳ２ＡＳ０以 及ＡＳ１ＡＳ０断开后，报文到达ＡＳ２后，其犅犲狊狋、ψ２皆失效，如果ＡＳ２选择了ψ１将报文转发到ＡＳ１，ＡＳ１将通过报文中犝狊犲犱＿犘犐犇以及当前链路状况， 仅能选择标识符ψ３，最后通过ψ３成功转发报文．当路径标识符数量为犽时，为了表示报文头的状态，其 报文头开销的最大长度约为１＋２ｌｇ（犽）ｂｉｔｓ． ５　协议属性分析 ５１　协议收敛属性 定理１．　对于给定的ＳＰＶＰ实例犣，如果它不含ＤｉｓｐｕｔｅＷｈｅｅ［２０］，那么ＭＦＴ２ＢＧＰ最终收敛；且在路由收敛期间不会出现瞬时环路． 证明．　ＤｉｓｐｕｔｅＷｈｅｅｌ［２０］的定义略，本文将 ＳＰＶＰ扩展到多路径路由．与标准ＢＧＰ不同，狏具有 多条到达目标ＡＳ０的路径，狏采用路径标识符ψ进行区分，路由更新消息中包含ψ以及ＡＳ＿Ｐａｔｈ路径信息．狏的最佳路径标识符β犫犲狊狋将从狏的可行路径集合犘狏，即从ｒｉｂ＿ｉｎ（狏←狆犲犲狉狊（狏））中选择，因此在同样的拓扑、策略下，如果ＳＰＶＰ在无ＤｉｓｐｕｔｅＷｈｅｅｌ的情况下收敛，那么ＭＦＴ２ＢＧＰ中最佳路径β犫犲狊狋上 也一定收敛． 其次，对于路径标识符ψ犻，狏在路由决策过程中计算ψ犻（除最佳路径β犫犲狊狋）路径时与ψ犼（犻≠犼）的路径隔离，即在ψ犻上其可行路径集合即仅在犌ψ犻犌中选择路径，显然，如果ＳＰＶＰ在拓扑犌中无Ｄｉｓｐｕｔｅ Ｗｈｅｅｌ，犌ψ犻对犌删除了部分边，犌ψ犻也不会含有ＤｉｓｐｕｔｅＷｈｅｅｌ，那么ＭＦＴ２ＢＧＰ中标识符为ψ犻的路径βψ犻在犌ψ犻上也一定收敛． 证毕．５２　报文转发属性 引理１．　对于任意节点狌，如果在链路犲失效前，其最佳路径上包含犲，在ＢＧＰ协议中最终收敛 能够得到不含犲的路径，那么ＭＦＴ２ＢＧＰ保证狌存 在某条标识符ψ的路径不通过犲．证明．　首先，显然当ＭＦＴ２ＢＧＰ使用充分数量的路径标识符时，总能获得底层拓扑中服从策略 多样性路径，并形成多转发树．设最佳转发树（犅犲狊狋＿ 犜狉犲犲）中失效链路犲的失效根节点为狇，设犲失效之前，π犅犲狊狋（狌，犱）＝犘犫犲狊狋＝（狌，狏１，狏２，…，狏狀）·π（狇，犱），且π（狇，犱）＝（狇，狑１，狑２，…，狑犿，犱）；在犲失效之后如果ＢＧＰ协议收敛能够使狌获得到达犱的路径为 犘犫犪犮犽狌狆＝（狌，狕１，狕２，…，狕狋，犱），即狌在失效前、后的最后一跳分别为狑犿和狕狋．下面证明ＭＦＴ２ＢＧＰ能够获得多样性路径． （１）如果狑犿≠狕狋，根据前缀通告过程，ＡＳ０发起前缀通告时将会针对每个邻居节点狑犿、狕狋分配不同的路径标识符ψ犻、ψ犼（犻≠犼）进行区分；节点狕狋到达犱的路径必不包含失效链路犲．因此，狕狋需要将ψ犼的路径通告给狕狋－１，依次类推，可知狌将会存在ψ犻、ψ犼上的多样性路径．同样，通过归纳法证明，狌将ψ犼路径通告给狏１，任意狏犻（狀＞犻１）中存在某条标识符ψ犼的路径不通过犲，且最终狑也将会获得不包含犲的 路径． （２）如果狑犿＝狕狋，说明犘犫犲狊狋与犘犫犪犮犽狌狆路径重叠， ＡＳ０仅有一个邻居节点．如果狑犿为每个邻居节点分配标识符，设失效前犘犫犲狊狋路径的标识符为ψ犻，狕狋－１到达犱的路径不包含犲，其标识符为ψ犼．依次类推，可得狌将会存在不经过犲的标识符为ψ犼的路径．对于狏犻（狀＞犻１），其证明与上面相同． 证毕． 引理２．　在无失效场景下，报文总在最佳路径上转发；当出现单或多链路失效后引起路由收敛期 间，如果协议获得的多样性路径中存在可行的转发 路径，那么报文不会被丢弃，且不会陷入环路． 证明．　分３种情况证明，即无失效、单链路失效、多链路失效场景．显然，在无失效场景下ＭＦＴ２ ＢＧＰ处于收敛状态，狏的最佳路径是对所有可行路 ０３０２ 计　　算　　机　　学　　报 ２０１２年 径集合犘狏计算得到一致性路径，报文在最佳路径上 安全转发． 其次，当出现单链路犲＝（狌，狏１）失效以后，设失效检测节点狌的最佳路径为π犅犲狊狋（狌，犱）＝（狌，狏１， 狏２，…，狏狀，犱），当犲失效后，狌切换到路径πψ犻（狌，犱）＝（狌，狑１，狑２，…，狑犽，犱），如果犇犻狊犼狅犻狀狋（π犅犲狊狋（狌，犱）， πψ犻（狌，犱））＝１，报文将在转发树ψ犻＿犜狉犲犲中无环转发．如果０＜犇犻狊犼狅犻狀狋（π犅犲狊狋（狌，犱），πψ犻（狌，犱））＜１，即π犅犲狊狋（狌，犱）与πψ犻（狌，犱）部分重叠，由ＭＦＴ２ＢＧＰ报文转发算法可知必有狏１≠狑１，设π犅犲狊狋（狌，犱）与πψ犻（狌，犱）在某点狏犻＝狑犼相交，其中狏犻∈π犅犲狊狋（狌，犱），狑犼∈ πψ犻（狌，犱），１＜犻狀，１＜犼犽．如果π犅犲狊狋（狏犻，犱）＝πψ犻（狑犼，犱），即狏犻中标识符为犅犲狊狋和ψ犻具有同样的路径，由于其任意转发树ψ上转发路径具有一致性，即报文不会回退或环路；而当π犅犲狊狋（狏犻，犱）≠πψ犻（狑犼，犱），即狏犻中标识符为犅犲狊狋和ψ犻具有不同的路径，报文狆在ψ犻可无环转发．出现多链路失效时，根据报文转发过程，具有如 下属性：（１）报文狆不会２次遇到同一个失效链路，该属性主要是由于检测失效的节点会将其失效转发 树的标识符ψ犻加入到报文头中，下行节点选择转发树时将避免ψ犻，这使得狆不会两次遇到同一个失效链路；（２）当出现第犽（犽２）个链路失效后，当前节点狌将根据ψ犽（ψ犽≠ψ犻）转发报文狆，如果在ψ犽不能成功转发，说明出现了新的失效链路，狌将避免使用 狆．犝狊犲犱＿犘犐犇，并选择新路径，此时狆要么被成功转发，或由于无可行路径而丢弃． 证毕． ＭＦＴ２ＢＧＰ获得多转发树的同时也一定程度 上增加了计算、存储开销，在不采用路径合并的时 候，其最大存储开销线性增加．根据文献［２５］的结 论，硬件的发展仍然满足Ｍｏｏｒｅ’ｓ定律，其多路径 计算、存储带来的开销是在可承受范围之内，且如果 将同一前缀的多标识符路径进行合并到单个转发 表，其存储开销将会进一步减低． 由于互联网ＡＳ拓扑具有幂率特性，其平均ＡＳ 跳数为４，可证ＭＦＴ２ＢＧＰ增加转发路径的长度非 常小，在本文后实验中也证明了这一点． ６　性能评价 为验证ＭＦＴ２ＢＧＰ性能，本文对轻量级Ｓｉｍ ＢＧＰ①进行扩展，实现了所有ＢＧＰ相关的重要特 征．根据ＣＡＩＤＡ②的数据分析可知当前ＡＳ数量为 ３１２１２，链路数量为６００５２，多宿主ＡＳ占总数的 ５３．４％，由于其规模过大，采用Ｄｉｍｉｔｒｏｐｏｕｌｏｓ［２６］根 据ＣＡＩＤＡ数据标注推断的ＡＳ级Ｉｎｔｅｒｎｅｔｌｉｋｅ拓 扑图，该拓扑具有ＡＳ之间的商业关系以及Ｉｎｔｅｒｎｅｔ 的复杂结构特征，Ｓｐｌｉｃｉｎｇ［１１］也使用了该拓扑．本文 采用的８００节点的拓扑如图４所示，链路数量为 １５８２，协议模拟参数如表１所示．实验对ＭＦＴ２ ＢＧＰ在各种场景下的收敛时间、消息数进行比较； 为验证ＭＦＴ２ＢＧＰ的无中断转发的性能，还从平均 ＡＳ瞬时失效率、平均转发中断时间、路径伸展度等 方面进行比较． 图４　８００ＡＳ节点拓扑 表１　实验参数设置 参数 默认值 ＭＲＡＩ ３０ｓ（Ｐｅｅｒｂａｓｅｄ） ＳＳＬＤ，ＷＲＡＴＥ Ｔｒｕｅ，Ｆａｌｓｅ导入导出策略 ＧａｏＲｅｘｆｏｒｄ其它设置 基于标准ＢＧＰ ＭＲＡＩ抖动 ［０．７５，１］ＭＲＡＩ链路队列延迟 ［０．０１，０．１］ｍｓ ＦＩＢ处理更新延迟［０．００１，０．０１］ｍｓ默认ＰＩＤ数量 ２ ６１　多转发树构造开销 该场景中主要针对多宿主ＳｔｕｂＡＳ发起前缀 通告，测试其收敛时间以及消息数量．在ＢＧＰ实现 中ＭＲＡＩ通常设置为ＰｅｅｒＢａｓｅｄ．由于源节点在发 起通告时，所有节点并没有对其邻居设置ＭＲＡＩ，为 保证模拟的真实性，降低ＰｅｅｒＢａｓｅｄ的影响，因此 设置发送消息等待时间为［０，ＭＲＡＩ］随机分布，以 此作为背景ＭＲＡＩ． （１）当使用路径标识符数量为２时，随机选择 １５０个多宿主（犘狉狅狏犻犱犲狉２）的ＡＳ共测试６４８次． 收敛时间、消息数量累积分布概率如图５（ａ）、图５ （ｂ）所示，与ＢＧＰ相比，收敛时间增加仅约４％，总 体消息数量增加约２０％，以合理的开销获得了多样 性路径．ＭＦＴ２ＢＧＰ在前缀通告时消息数量有所增 加，这是由于为了将隐藏合法路径暴露给其它ＡＳ， 而收敛时间与ＢＧＰ相比几乎无增加，这是由于不同 标识符上的收敛具有相对隔离性质，而ＢＧＰ收敛时 间主要与网络直径、ＭＲＡＩ设置等因素相关［２７］，理 论上收敛时间为ｍａｘ｛ψ１＿犪狀狀，ψ２＿犪狀狀，犅犲狊狋｝，其中 ψ犻＿犪狀狀为对应标识符上的收敛时间．此外ＭＦＴ２ ＢＧＰ中ＭＲＡＩ采用ＰｅｅｒＢａｓｅｄ设置，由于ψ１、ψ２会相互影响，也一定程度上会限制更新消息传播速度， 稍微增加收敛时间． １３０２１０期 胡乔林等：ＭＦＴ２ＢＧＰ：基于多转发树的无中断域间路由协议 ① ② ｓｉｍＢＧＰ：ＡｌｉｇｈｔｗｅｉｇｈｔｅｖｅｎｔｄｒｉｖｅｎＢＧＰｓｉｍｕｌａｔｏｒ．ｈｔｔｐ：／／ｗｗｗ．ｂｇｐｖｉｓｔａ．ｃｏｍ／ｓｉｍｂｇｐ．ｐｈｐＣＡＩＤＡＡＳｒｅｌａｔｉｏｎｓｈｉｐｓ（２００９０４２９）．ｈｔｔｐ：／／ｗｗｗ．ｃａｉｄａ．ｏｒｇ／ｄａｔａ／ｒｅｑｕｅｓｔ＿ｕｓｅｒ＿ｉｎｆｏ＿ｆｏｒｍｓ／ａｓ＿ｒｅｌａｔｉｏｎｓｈｉｐｓ．ｘｍｌ 图５　标识符数量为２时的构造开销 （２）当使用路径标识符数量为３时，随机选择 ７１个多宿主（犘狉狅狏犻犱犲狉３）测试２１４次．收敛时间、消息数量累积分布概率如图６（ａ）、图６（ｂ）所示，其 收敛时间仅增加１０％，总体消息数量增加４０％，但 考虑到每个节点获得的路径数量将会达到３，此开 销仍然在合理范围内． 图６　标识符数量为３时的构造开销 ＭＦＴ２ＢＧＰ在初始化时，带来了一定的消息开 销，但这种开销也仅出现在多转发树的初始构造中． ６２　单失效下协议性能 针对单链路失效，测试了边缘链路、核心链路失 效两种场景． （１）在边缘链路失效中，随机选择３００个多宿 主ＡＳ（犘狉狅狏犻犱犲狉２），断开多宿主ＡＳ与其中的一 个犘狉狅狏犻犱犲狉的链路（这是最极端情况），共进行了 ６５０次实验，分别测试了ＢＧＰ、ＧｈｏｓｔＦｌｕｓｈｉｎｇ［７］、 ＥＰＩＣ［８］、ＭＦＴ２ＢＧＰ以及加速收敛的ＭＦＴ２ＥＰＩＣ． 图７　单失效下控制平面开销 从图７