路径路由协议

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
21,No.
7,July2010,pp.
15891604http://www.
jos.
org.
cndoi:10.
3724/SP.
J.
1001.
2010.
03816Tel/Fax:+86-10-62562563byInstituteofSoftware,theChineseAcademyofSciences.
Allrightsreserved.
互联网无中断转发的生存性路由协议苏金树,胡乔林+,赵宝康(国防科学技术大学计算机学院,湖南长沙410073)Disruption-FreeForwardingSurvivableRoutingProtocolsonInternetSUJin-Shu,HUQiao-Lin+,ZHAOBao-Kang(SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha410073,China)+Correspondingauthor:E-mail:huqiaolin@nudt.
edu.
cnSuJS,HuQL,ZhaoBK.
Disruption-FreeforwardingsurvivableroutingprotocolsonInternet.
JournalofSoftware,2010,21(7):15891604.
http://www.
jos.
org.
cn/1000-9825/3816.
htmAbstract:Internetisbecomingtheinfrastructureandstartstocarrymorecriticalmissiontrafficwhereevenashortdisruptioncancausesignificantlossesforcertainapplications.
Nevertheless,traditionalrouteprotocolshavetheproblemoflongconvergencedelay,transientunreachabilityandloopuponthenetworktopologychangesduetolinks/nodesfailureorvariousotherreasons.
Unfortunately,thetransientroutingfailuresareverycommonaccordingtotheexperimentalstudies.
Numerousroutingprotocolswhichcanprovidedisruption-freeforwardingandfastrecoveryhavebeenproposed.
Thispaperfirstlystudiestherootcauseoftransientfailures,andthenpresentsclassificationstandardsforsurvivableroutingprotocols.
Thereafter,itfocusesonanalyzingthefundamentalmechanismofexistingrepresentativesurvivableroutingprotocolsandcomparingtheircharacteristics,performanceandoverhead.
Finally,thecurrentresearchstatusandopenresearchissuesareconcluded.
Keywords:transientfailure;routerecovery;fastrerouting;multipathrouting;survivablerouting摘要:互联网逐渐成为通信基础设施并承载了更多的关键业务流量,即使瞬时中断也会对某些应用造成巨大损失.
然而,传统路由协议在出现链路/节点故障等拓扑变化时存在收敛时间长、瞬时不可达以及环路的问题.
实际测量发现,路由瞬时失效相当普遍.
因此,研究人员提出多种能够保证流量无中断转发和快速恢复的路由协议.
在分析瞬时失效现象以后,提出了生存性路由协议的分类方法,重点对一些重要的路由协议的核心路由机制进行深入分析,并比较其特点、性能、开销等.
最后,结合该领域研究现状以及存在的问题,指出未来生存性路由的研究重点.
关键词:瞬时失效;路由恢复;快速重路由;多路径路由;生存性路由中图法分类号:TP393文献标识码:AInternet已发展成为重要的通信基础设施,承载了更多的关键业务流量.
在重要的国防、经济场合,网络瞬时中断都会带来不可估量的损失.
ISP由于网络中断而引起的经济损失每小时以百万美元计算[1],致使网络生存性问题日益突出.
为避免巨大损失,需要可用率达99.
999%的网络.
然而遗憾的是,目前互联网连两个"9"的指标还SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.
2008AA01A325(国家高技术研究发展计划(863));theNationalBasicResearchProgramofChinaunderGrantNo.
2009CB320503(国家重点基础研究发展计划(973))Received2009-09-08;Revised2009-11-09;Accepted2009-12-291590JournalofSoftware软件学报Vol.
21,No.
7,July2010不能达到[2,3].
网络延迟和中断是两个重要的网络性能指标,直接影响着网络新兴数据业务的部署应用,如VoIP、在线游戏、远程医疗、电子银行等对于持续端到端连接的要求非常高,Cisco公司预测[4],到2012年,Internet中客户IP流量将近90%都是视频流量,这些流量对于延迟和中断都非常敏感,恢复时间低于50ms是寻常要求[5],而恢复时间在200ms~2s之间会使实时业务服务质量严重下降.
影响互联网生存性的因素众多,包括底层光网技术、拓扑、体系结构、路由协议等多方面因素,而在IP层进行故障处理具有低成本、灵活性等方面的优势[6].
在给定拓扑、体系结构的情况下,路由协议是影响互联网生存性的最主要因素,直接影响到互联网承载新兴业务的能力.
理想的路由协议应该保证只要底层拓扑连接就能够提供持续的端到端通信,然而,目前Internet中广泛采用的OSPF、BGP协议缺乏生存性保证,在面临失效时主要通过触发新的全局性、反应式收敛来应对拓扑变化,这种收敛过程对拓扑变化反应迟缓,难以满足IP实时业务的需求.
比如,按照RFC建议设置OSPF,需40s~120s检测失效,收敛时间达数十秒,而BGP收敛时间则以分钟计.
在路由收敛转换过程中,当前路由协议由于隐藏冗余拓扑、使用单路径、失效全局可视化等问题,当出现链路/节点失效时,路由器不能快速、正确地切换工作路径,造成大量的丢包和服务中断.
如何使互联网适应关键业务的无中断需求,成为工业界[7]、学术界共同关注的热点和难点问题,引起了Sigcomm,NSDI,Infocom等主流会议的关注.
新型网络体系结构中明确提出Internet在可用性、可靠性方面存在不足,应针对路由生存性提出解决方案[8],保证网络可靠性以及应对失效的健壮性.
"AlloverIP"的发展趋势更加凸显了生存性路由协议的重要性.
本文主要针对在失效条件下能够提供无中断流量转发、增强互联网生存性的路由协议进行研究,首先阐述了互联网的路由瞬时失效现象,并对现有生存性路由协议进行了分类,然后分别针对单失效、多失效场景深入分析、评价了这些典型路由协议的核心机制、特点、性能,最后讨论并指出未来的研究方向.
1互联网生存性路由协议研究背景与分类广泛使用的OSPF,BGP路由协议本质上都满足安全性、活性的需求,但是由于协议动态行为以及消息传播处理速度等物理限制,降低了路由更新速度,造成了收敛过程中各个路由器的拓扑视图、RIB、FIB信息不能及时、同步,从而在网络状态发生改变时就有可能造成瞬时性不可达、路由与转发环路(将其统称为瞬时失效),导致了底层拓扑的连接并不意味着路由系统的可达.
1.
1互联网中瞬时失效现象现有网络时常面临光缆割断、路由器崩溃、操作失误、攻击、iBGP/eBGP会话失效等众多威胁,文献[9]通过对Sprint骨干网链路故障进行分析发现,失效几乎每天都会发生,且大多数失效属于短时间故障,这些威胁将频繁触发路由失效事件,造成网络的不稳定.
大量的研究表明,现有的域内、域间路由协议在面临失效事件时,包括OSPF[10],BGP[11]在内的路由协议收敛时间相对较长,BGP收敛甚至达到30分钟以上,而收敛期间的动态性也严重影响数据平面的转发性能[12]:大量路由器将会经历瞬时性不可达、路由环路等问题[13].
近年来,通过对ISP,VoIP等应用的实际测量,发现Internet可用性相对较低,Wang等人[14]通过对顶级ISP测量发现,即使在失效切换和链路恢复时,路由黑洞也会造成数十秒的报文丢失.
Zhang等人[15]指出,超过39%的路由更新会导致可达性丢失,时间甚至长达300s.
Kushman等人[16]通过对VoIP的分析发现,50%的VoIP中断与BGP更新高度相关.
路由收敛时间长、收敛期间的瞬时性不可达以及路由环路等问题严重降低了网络性能,难以支持关键、交互式以及实时应用.
针对这些问题,学术界广泛开展了设计无环、降低收敛时间的路由协议的研究,文献[17]对IGP协议加速收敛的技术进行了总结,BGP加速收敛的协议包括BGP-RCN[18],EPIC[19]等.
但是,由于大多数失效属于瞬时失效,这类降低收敛时间的协议却可能频繁收敛,造成消息更新风暴,导致出现很高的CPU和内存开销的现象,从而造成网络的不稳定[20].
而对瞬时失效进行抑制却进一步恶化了路由的不稳定性[21],甚至可能恶化报文分发性能.
目前,对BGP快速收敛的研究陷入了困境[22].
此外,这些加速收敛的协议主要从控制平面上降低失效对于流量转发的影响,但是并不能彻底消除收敛期间对转发中断的影响,不能取得"无中断"的转发.
网络的迅速发展以及应用需求对路由协议提出了更高的要求,本文将生存性路由定义为,网络在遭受攻苏金树等:互联网无中断转发的生存性路由协议1591击、故障等各种路由失效事件的情况下,只要底层网络拓扑连接,忽略失效检测时间(双向转发检测BFD机制可将失效检测时间降至15ms以内),路由协议应该在网络状态改变的情况下快速、正确地恢复,保证流量无中断转发,以增强网络生存性.
生存性路由协议需要降低重收敛时间长带来的负面影响,同时需要应对收敛期间中瞬时失效的挑战.
如何在给定的环境下高效地利用资源并在性能和开销之间取得平衡,构成了生存性路由的研究核心.
1.
2生存性路由协议的分类现有路由协议主要采用单路径、最短路径的方法,没有充分利用底层冗余拓扑[23],而缺乏多路径发现、转发能力;路由机制上缺乏故障诊断、隔离能力[24],失效发生时,路由协议难以确定导致路由更新的根源,不能及时作废无效路由.
比如BGP难以识别非法路径,造成大量"路径探索"[25].
以上问题也都影响了协议的生存性,因而需要突破传统路由协议的缺陷,比如利用RCN[18]机制提供故障诊断能力等.
而大多数生存性路由协议主要解决当前协议中存在的某些方面的问题,因此带来了路径建立方式、维护方式、报文转发方式等多个方面的改变.
本文主要根据现有解决问题的场景、路径建立和维护时机、失效反应点等方面对生存性路由协议进行分类.
(1)根据协议覆盖的故障类型,可以分为处理单链路/节点失效以及多个独立失效场景下的路由协议.
现有的大多数协议主要集中于保证单链路/节点失效下流量的持续转发(单节点失效可能引起多链路失效,但这些失效是局部性且相关的);而对于独立多失效场景下的协议设计更为复杂,对网络体系结构、路由器实现都有更高的要求.
(2)根据协议所采用的路径计算方法,可以分为集中式和分布式方法.
集中式方法在计算效率、路径一致性等方面具有优势,但其可扩展性、路由收敛时间、通信开销却面临着挑战.
RCP[26],Consensus[27]体系结构采用了集中式方法计算、分发路由,强制使各个路由器达到路由的一致性,以应对网络失效情景.
(3)根据协议对备份路径的建立时间,可以分为先验式预计算和反应式按需计算路径方法,这两种使用备份路径的方法降低了转发对路由收敛的依赖程度.
先验式预计算路径通过对所有可能出现的失效,预计算备份路径存储于RIB,FIB,检测到失效后,立即切换到备份路径;而按需计算路径则主要根据即时的失效信息按需计算新的符合条件的恢复路径.
(4)根据协议应对失效时反应点的位置,可以分为源端路径级恢复和本地链路级快速重路由(简称本地快速重路由).
源端路径级恢复是指源节点在发现故障点以后,整体迅速切换到能够绕过失效点的备份路径;而本地链路级快速重路由是指当前节点发现故障后立即切换到可以绕过故障点的下一跳,而不用源节点切换路径.
此外,根据协议适用范围可以分为域内和域间生存性路由协议;根据报文转发实现方式可以分为基于报文封装和报文头标记修改、接口相关的转发等.
生存性路由协议所覆盖的故障类型很大程度上影响着协议复杂性以及协议所采用的具体技术、机制,虽然上述(2)~(4)分类法也能对协议进行较好的归纳,但是为了提取出这些生存性协议的核心思想,特别是为了区分各种协议具体采用的技术、机制所能够适用的场景,本文主要从单/多失效场景的角度出发,根据各种协议的核心思想进行分类和总结,并详细分析了其中典型路由协议的研究成果.
2单失效场景下生存性路由协议该类路由协议主要应对目前失效比例较高的单链路/节点失效,当前节点检测到失效后,在无全局协调的情况下,根据自身路由信息库做出本地决策,而不会导致多节点之间的备份路径互相冲突.
对失效位置可预知的情况,主要分析了顺序更新FIB相关的协议;对失效不可预知的情况,按照备份路径的结构化性质,分析了无结构化路径的域内/间本地快速重路由,以及基于结构化备份子图的本地重路由.
2.
1顺序更新FIB文献[9]的数据显示,约20%的故障是进行路由维护造成的,这种维护并非紧急的链路/节点事件,从而为解决瞬时失效问题创造了时间上的机会.
Francois等人针对链路状态协议提出了通过顺序更新FIB避免环路的机制OFIB[28,29].
OFIB的主要思想是:要求将被关闭的链路l在收敛期间继续保持连接,确保其他节点在收敛期间1592JournalofSoftware软件学报Vol.
21,No.
7,July2010仍能使用l而不会造成报文丢失;其次,强制要求所有路由器按照一定的次序更新FIB,以破坏环路形成的条件;当收敛完成以后,所有的流量将不会经过l,此时可以将需要维护的链路、路由器平稳关闭,而不会造成转发中断.
如图1(a)所示,假设链路ij将会被关闭,如果s到达目标节点d最短路径经过链路i→j,那么s可以将报文转发到其他节点n.
其中,节点n到达d的最短路径树SPT中不含有链路i→j.
很明显,此时不会形成环路,即s,d|Ps→d={s,…,i,j,…,d},且s,d|sdP→′={s,n,…,d}andi→jinitndP→,那么可以得到finalsdsdPP→→′=.
其中,Ps→d,,sdP→′finalsdP→分别表示在链路关闭事件发生之前、使用顺序更新FIB以及链路关闭之后得到的从节点s到d的路径.
从这个事实中可以得出如下结论:当链路i→j关闭引起路由收敛时,在收敛期间,如果所有路由器等待在rSPTi→j(j)中的子节点更新FIB之后再更新FIB,将不会引起环路.
其中,rSPTi→j(j)是断开ij后j的反向最短路径树.
类似地可以得到,如果链路i→j恢复,路由器应该等待在()finalijrSPTj→中的父节点路由器更新FIB以后再更新.
根据这两个结论,通过将相关的信息编码端入LSPs(链路状态报文),则很容易设计相应的协议避免环路[28].
(a)OFIB(b)LFA(c)U-turn(d)Tunnels(e)Not-viaFig.
1ExampleoffastlocalreroutinginIGP图1IGP中本地快速重路由示例Francois进一步针对OSPF提出使用步进设置链路权值的方法[29],这种方法不修改OSPF(openshortestpathfirst)协议,实际上是将预规划链路ij关闭导致的路由收敛分解为多个子序列,通过步进式地增加链路ij的权值Δ,每次权值的改变将会引起OSPF收敛并逐步更新所有路由器FIB,且不会导致路由瞬时失效.
可以证明,在运行OSPF协议的稳定网络中,通过逐步为ij的权值加1,必定会得到一个无环路收敛过程.
为了减少对链路ij调整的次数以提高效率,Francois提出优化重路由权重序列的ORMS(optimalreroutemetricsequence)方法,以使得每次对ij的调整步进足够大,减少调整次数,使得该方法实用可行.
OFIB主要针对有规划的路由维护,由于强制所有路由器按照顺序更新FIB,避免了转发环路,保证了无中断转发,但同时也会明显延长收敛时间.
2.
2域内本地快速重路由链路/节点失效更多地是由意外故障引起的,IETFRTGWG以及其他研究者致力于IGP协议的本地快速重injwd432897i'soriginalpathi'sLFApathdon'tpassi→ji'sLFApathdon'tpassjsijdn.
.
.
.
.
.
.
.
.
iujrd5551010i'soriginalpathi'sU-turnpathijxynd112113y'soriginalpathi→j'stunnelsSiijsudSuUsvIsIjJis'soriginalpaths'sNot-viapath苏金树等:互联网无中断转发的生存性路由协议1593路由[30],并提交了一些包括ECMP的草案,其应对失效场景主要包括单链路/节点、共享风险链路组SRLG等.
这些研究主要采用预计算备份下一跳以应对当前下一跳的故障,其区别主要表现在对备份下一跳的计算方式上,比如,LFA[31]仅利用一跳内的节点信息计算备份下一跳,而U-turn[32],Tunnels[33],Not-via[34],Deflections[35],FIR[36]等为了增加覆盖范围,考虑利用多跳外的节点信息预计算备份下一跳.
而SafeGuard[37]则采用报文显示携带信息的方法,根据不同携带信息,分别利用反应式或先验式预计算路径发起本地重路由.
(1)无环备份(LFA)[31].
LFA为节点计算一个无环的备份下一跳.
如图1(b)所示,假设节点i经过i→j到达目标d,当LFA对链路i→j进行保护时,将为默认下一跳j选择备份下一跳n,其条件满足Cost(n→…d)cost(ni,d),说明ni具有比ni1到达目标更低的开销,此时,ni不能继续按照默认下一跳进行转发,ni将按照备份路径数据库进行转发到1in+′,并且更新报文剩余路径开销为pkt.
cost=pkt.
costcost(ni,1in+′).
通过对这3种模式的处理,SafeGuard能够在出现单链路失效的时候快速发起重路由,并加速网络收敛.
2.
3域间本地快速重路由囿于Internet中AS的规模,由于顺序更新FIB的方法需要所有AS合作、计算量大、收敛时间延迟而使其在BGP中不可行.
当前,应对域间链路失效主要使用本地快速重路由方法.
本质上,域间快速重路由与域内快速重路由的原理相同且能够通用,主要区别在于备份路径的计算方法.
BGP协议中,链路无权值、无全局拓扑、单条最佳路径通告、典型的Valley-free策略[40]等阻碍了对更多冗余路径的发现,因此,IETFRTGWG针对IGP的快速重路由也就不能直接应用于BGP.
考虑到当前BGP路由表、更新消息过多,已经影响BGP的稳定性,域间快速重路由协议必须限制开销,也进一步加剧了设计难度.
(1)域间链路保护隧道[41].
Bonaventure等人[41]提出了为每条域间链路预先建立最佳IP保护隧道的方法,应对域间链路失效,该IP隧道的下一跳可以作为被保护链路的备份下一跳,主要使用主出口-次出口pe-se(primaryegress-secondaryegress)隧道保护两个AS之间的并行链路,使用主出口-次入口pe-se(primaryegress-secondaryingress)隧道保护末端(stub)AS与提供者(provider)AS之间的域间链路.
当域间链路失效时,路由器能够使用IP隧道发起本地快速重路由.
这种在邻居AS之间预建立隧道的方法可以应对AS间的单链路失效,但不能应对跨AS域的失效,不具有通用性,而且需要设置带外的域间隧道.
(2)R-BGP[42].
R-BGP在BGP收敛过程中使用预计算的备份路径保证无中断转发,然而,在BGP协议中,使用合适的备份路径却需面临3个挑战:备份路径的选择分发、避免环路以及收敛后停止使用备份路径.
对于第1个问题,R-BGP使每个AS尽量为其最佳路径的下一跳通告一条到达目标前缀的最大不相交路径来加以解决;R-BGP采用BGP-RCN[18]的思想在每个路由更新消息中嵌入失效根源信息RCN(rootcausenotification),以避免收敛过程中的环路并加速收敛;通过利用AS之间的层次关系,如果AS显式地接收到所有邻居的撤销消息,该AS可以判断自身将不会具有服从策略的路径,从而停止转发,这样就解决了第3个问题.
R-BGP降低了收敛延迟,但没有考虑iBGP相关的失效事件,且修改了BGP语义.
(3)BRAP[43].
BRAP保证当出现单条域间链路失效时,通过备份感知路由协议BRAP以执行非停止的路由,BRAP的主要思想是:每个域间路由器A除通告最佳路径以外,在服从策略限制下必须具有以下通告能力:①通告反向路径的能力,反向路径定义为不经过A的默认下一跳B到达目标的路径;②通告无环备份路径的能力,无环备份路径定义为A到上行邻居的临时路径.
假设路由器B具有最佳路径和反向路径,那么当B发现最佳路径中的下一跳域间链路失效时,通过使用反向路径即可进行快速重路由;而当出现iBGP链路失效以及恢复时,使用无环备份路径发起本地快速重路由.
BRAP放松了最大不相交路径的条件,对实际的部署进行了考虑,但其缺点是增加了一定数量的路由更新消息,修改了BGP路由协议.
(4)D-BGP[44].
D-BGP通过通告多路径的方法以增加域间路径多样性,在单链路失效后进行快速本地重路由.
D-BGP要求域间路由器除了最佳路径Pbest以外,还通告一条与最佳路径最大不相交的备份路径Qalt.
D-BGP使用两个限制条件以减少通告消息以及存储开销.
对于当前节点u,假设u的所有邻居节点已经向u通告了其最佳路径以及备份路径,用Pi表示从邻居i学习到的最佳路由,Qi表示从邻居i学习到的备份路径,在这些学习到的路径中,u选择最佳路径Pbest以及备份路径Qalt,使用|Pa∩Pb|表示路径Pa和Pb共享的边/节点数目.
如果满足以下任意条件之一,则节点u将不会给邻居节点通告备份路径Qalt:①如果u具有v的最佳路径Pv或者备份路径Qv;|Pbest∩Pv|=0或者|Pbest∩Qv|=0,则表示邻居节点v已经有了一条不相交路径;②如果|Pbest∩Qalt|路由协议借鉴了分布式系统中利用快照达到全局一致性状态的经验,从而使得路由行为更可预测、更安全.
Consensus路由将域间路由协议的安全性和活性分离:安全性意味着路由器严格按照上行路由器采用的路径进行转发报文,除非遇到链路失效;而活性将保证快速响应失效、策略的变化.
Consensus路由通过要求每个时间段内BGP路由器达到全局稳定状态.
与传统的BGP相比,Consensus路由有意延迟了BGP的更新.
Consensus路由在报文转发时采用了两种逻辑上分离的模式:稳定模式和瞬时模式.
处于稳定模式时,所有路由器具有全局一致性的路由视图;当由于链路失效等造成报文不能正常转发时,将转入瞬时转发模式,主要采用包括偏转(deflection)、绕道(detouring)、回退(backtracking)、备份(backup)路由机制发起本地重路由.
2.
4单失效下结构化备份子图在域内快速重路由中,各个节点独立依据自身策略从多条可行路径中选择某条备份恢复路径.
然而,该备份路径并不为其他节点所知,各节点的备份路径不具有全局一致性,在某些情况下甚至可能出现环路,本地重路由往往需要额外的信令机制.
而结构化拓扑是指在特定的某个备份子图上所有节点具有一致性视图,其核心思想是,对原始图G抽取出多个符合条件的子图Gi,独立在这些子图Gi上运行路由协议,其Gi中所有节点的路径、节点转发行为都是一致的.
目前的结构化备份子图方法需要具有全局拓扑知识,而在BGP中,这一假设并不成立,BGP中实现结构化备份子图较为困难,有待进一步的研究,目前,结构化备份子图方法主要适用于域内协议.
(1)弹性路由层RRL(resilientroutinglayer)[45].
RRL通过对需要保护的链路l、节点n在原始拓扑G上删除l、与n关联的链路后分别得到诱导拓扑子图,称为"层",即每"层"中包含原始拓扑所有节点,但是仅包含链路子集.
"节点n安全"表示该节点n在某"层"Li中仅有与该节点关联的一条链路包含在该"层"Li中,而Li称为"节点n的安全层".
"层"Li中所有的节点依然保持连接,且Li具有如下属性:在节点n的安全层中,n不会用于传输流量;如果n故障,那么任何对于n安全的层中的节点对之间的路径仍然连通;如果n故障,任何以n为目标节点的流量都将会丢失.
在RRL中,每个Li都独立计算RIB和FIB,当链路/节点故障时,当前路由器可以透明地将报文快速重路由到对应的"安全层"进行转发,且不会造成环路.
(2)多路由配置MRC(multipleroutingconfiguration)[46].
MRC对RRL进一步加以改进,是一种自定义的结构化RRL,与RRL的区别在于,MRC通过限制链路权重以获得备份拓扑,图3表现了MRC的相关概念.
MRC通过在原始拓扑G=(V,E)中对需要保护的节点n和链路l进行限制和隔离而得到对应的备份拓扑Cp.
链路l在备份拓扑Cp的被隔离是指其权值wp(l)=∞,l被限制是指wp(l)=|E|*wmax.
其中,wmax表示图G中的最大权值,通过对与节点u关联的链路进行隔离和限制,可以将节点u隔离,即如果节点u在Cp中满足条件:(u,v)∈E,wp(u,v)≥|E|*wmax,且(u,v)∈E,wp(u,v)路由协议1597DAG包含网络图中的所有的符合约束的边,从而为所有节点到达目标节点提供了大量的备份路径.
MARAs引入了新的多路径概念,即多对一最大连接度、多对一最大流、多对一最大化最短备份路径树.
MARAs采用了集中式的方法对所有的节点进行排序,所有节点获得了大量的一致备份路径,从而可以进行快速的失效恢复.
Fig.
3AnexampletopologywithonebackupconfigurationinMRC图3MRC中具有单个备份拓扑配置示例3面向多失效场景的生存性路由协议在独立多链路失效场景中,难以预测可能出现并发失效的链路,各失效检测节点也难以及时获取其他链路失效信息,这给协议设计带来了巨大挑战.
如果采用顺序FIB更新,节点在不能得知其他失效链路位置时无法计算或仅计算出非法的FIB更新顺序;当采用非结构化的快速本地重路由时,由于发起重路由的节点仅能够根据本地局部知识,而无法感知到其他故障点以及其他节点的决策,报文可能传输到其他失效节点/链路而被丢失或陷入环路,仅使用本地快速重路由是难以保证无环、无中断转发的,必须有其他信息辅助转发,这是由协议的分布式特性的本质造成的.
单失效场景下的生存性路由协议在多失效场景中不能完全保证协议的正确性和完整性.
目前,应对多独立失效场景的协议主要采用两种机制,即先验式计算多结构化子图覆盖各种可能的并发多链路失效,并在各逻辑子图上独立运行路径选择算法;或者在报文中嵌入"故障根源"等信息,通过报文隐式地传递控制平面失效信息,利用这些特殊信息进行反应式检测、纠正节点间的不一致决策,从而消除环路或黑洞.
3.
1多失效下的结构化备份子图根据Menger's定理,假定图G中n边/节点失效,网络保持连通的充要条件是G为k>n的边/节点不相交连接图,该类协议通过构造能够容忍多失效的多个逻辑拓扑,以保证流量在多独立失效的场景下无中断转发.
(1)2DMRC[51].
2DMRC对MRC扩展以应对两个独立并发失效,它必须满足以下3个条件:(1)在隔离节点u的拓扑中,节点u必须不能作为中转节点,但是流量可以从一个隔离的入口节点转发到另外一个隔离的出口节点;(2)在每个备份拓扑中,所有的节点必须都是连接的,但是不能使用隔离节点作为中转节点;(3)所有的节点对之间必定至少存在一个备份拓扑将其隔离.
条件(1)决定了限制链路的权重,而条件(2)和条件(3)决定了如何构造备份拓扑的哪些节点能够在同一个备份拓扑中同时隔离.
以这3个条件作为输入限制产生能够容忍两个独立并发失效的备份拓扑,即任意两个组件失效的时候至少存在一个备份拓扑不使用这两个组件.
当出现并发失效时,通过连续地对多个备份拓扑进行多次尝试以提供无中断转发.
该协议效率不足,最差情况下算法复杂性将达到O(|V|5).
(2)独立双链路失效恢复[52].
假定网络拓扑是3边连接图G=(V,E),该协议为每个节点u∈V分配4个地址:1个无失效下的常规地址u0,3个备份保护地址u1,u2和u3.
将与节点u连接的链路分成3个保护组,表示为12,uuLL和3uL.
节点u与3个保护图相关联,表示为(,\)iiuuGVEL,i=1,2,3.
其中,iuG是通过将iuL删除以后而所得到的,可以证明这种构造方法保证每个保护图iuG都是2边连接图,在每个保护图iuG中使用着色树(colortree)技术以路由报文.
令gguuSvuvL=∈表示通过guL的链路连接u的节点集合,当连接到节点u的链路失效以后,guS中的节点可以通过隧道将报文传输到保护地址ug.
该协议将保护图和着色树技术结合起来以容忍并发两条链路1234567812345678NormalCpRegularnode-linkRestrictedlinkIsolatednode-link1598JournalofSoftware软件学报Vol.
21,No.
7,July2010失效,其协议的复杂度为O(|V||E|).
(3)路径拼接(pathsplicing)[53].
路径拼接通过将多个到达同一目的节点的最短路径树(单个以目的节点为根的最短路径树称为"片段")组合形成路径,端系统通过报文头中的"拼接报文头(splicingheader)"而切换报文转发路径进行全局恢复;而路由器可以通过改变"拼接报文头"发起本地快速重路由.
路径拼接在给定的拓扑上随机扰动链路权重以获得多个拓扑,并运行多个路由协议实例为这些拓扑计算对应的最短路径树(即片段),随机扰动函数为L′(i,j)=L(i,j)+weight(a,b,i,j)*random(0,L(i,j)),L(i,j)表示原始链路的权重,Weight(a,b,i,j)表示节点i,j之间的属性函数.
比如,节点的度数Random(0,L(i,j))表示[0,L(i,j)]之间的随机数.
其中,i,j,Weight(a,b,i,j)=fab(degree(i)+degree(j)),fab是位于区间[a,b]与degree(i)+degree(j)相关的线性函数.
在预计算多个片段以后,完整的路径即可由多个片段组合而成,如图4所示,其中的01字串表示"拼接报文头".
当链路失效后,节点通过设置报文中"拼接报文头"使得报文重路由到不同的分片上,实现无中断转发.
Fig.
4Pathsplicing图4路径拼接与MRC不同,路径拼接允许多次改变"拼接报文头"以应对多个失效,但是并不能保证100%的覆盖,从而降低了实现复杂度.
此外,当路径拼接通过随机扰动链路权重获得多个拓扑计算分片时,并没有将特定节点隔离,因此可能造成转发环路.
路径拼接主要通过限制拼接位的数量来消除持久环路,通过偏转计数法消除瞬时环路.
将路径拼接扩展到域间路由时,报文转发时利用路由表中已经存在的多条路径,通过在报文头添加拼接位信息,从而可以选择BGP路由表中的备份路径.
采用这种方法报文头开销过大,而且难以使用最大不相交路径.
3.
2信息携带辅助路由一些研究工作采用了在报文中携带"故障根源"的方法,在不中断报文转发的同时,利用普通报文携带控制平面失效信息以辅助节点路由转发.
采用这种方法应对多个失效改变了协议语义,也给路由器带来了额外的计算开销.
(1)FCP路由[54].
与OSPF路由机制不同,FCP并不致力于减少收敛时间,而是试图完全消除收敛过程;FCP也不使用复杂的预计算备份路径,而是通过在报文中携带"故障根源"信息,使得报文自主发现可用路径,从而保证了流量的无中断转发.
FCP通过一个类似于RCP[26]的平台分发全局一致性拓扑视图,当路由器路由失效后,FCP在报文头中插入"故障根源"信息的黑名单,路由器接收到该报文后,只要底层网络拓扑连通,通过FCP算法就可以计算出避开故障链路/节点的新无环路径.
图5展示了FCP的转发过程.
当所有路由器无一致性拓扑视图时,采用基于源路由SABCFEDGF={}F={}F={B-D}F={B-D}F={B-D,F-E}Fig.
5AnexampleillustratingFCP图5FCP示例Slice0Slice1Slice2SliceDstNext-Hop0daIPheaderTransportheaderPayload1da2dbsacdbPathsplicingheader010100Forwardingtablesats苏金树等:互联网无中断转发的生存性路由协议1599的SR-FCP(source-routingFCP),第1跳路由器在报文中添加完整的到达目标的源路径,下行路由器按照报文头指定的路径转发直到检测到新失效链路.
此时,路由器将失效链路加入报文头的失效信息域,并用新计算的路径替换报文中的源路径,SR-FCP也可用于域间路由.
FCP在多失效情况下可以保证无中断转发.
但是,由于路由器几乎需要为每个失效报文都计算新的路径,即使通过路径缓存的方法也会造成路由器CPU的负担过重;其次,报文头开销大且长度不固定,在核心路由器中难以实现.
类似地,BISF[55]对FIR[36]进行了扩展,报文中携带了失效链路的黑名单,当节点检测到失效链路后,通过发起类似于本地快速重路由的方法实现无中断转发.
但是,该节点仍然必须利用黑名单信息以避免环路并辅助报文转发,使其容忍多失效,且BISF不能保证100%的覆盖.
(2)ACF路由[56].
ACF接受在路由收敛过程中全局路由视图不一致的现实,在路由不一致的情况下采用检测并恢复的方法,通过在报文头p中添加路径踪迹域(pathtrace)、黑名单域(blacklist)以及其他辅助功能域,进行动态按需路由计算.
其中,路径踪迹域表示为p.
pathTrace,用以记录报文所经历过的AS列表;黑名单域表示为p.
blackList,黑名单域中的AS可能由于无服从策略的路径或该AS可能引起环路,从而不能将报文正确传输.
ACF对报文处理过程如下:当在ASs产生报文p,且其目标域为ASd时,当前BGP路由器检测p.
pathTrace,如果本地AS号不包含在p.
pathTrace中,报文将按照正常模式转发;如果本地AS号码包含在p.
pathTrace中,说明产生了环路,当前BGP路由器将p.
pathTrace中所有的AS号移除并添加到p.
blackList中,同时调用转发平面搜索RIB中不经过p.
blackList的备份路径.
如果当前BGP路由器没有备份路径,可将报文传输到ASd时,当前BGP路由器将会发起本地恢复转发(recoveryforwarding),其核心思想类似于报文封装技术,将报文偏转到最有可能包含合法路径的ASr中.
比如Top-10AS,ASr同样可以继续发起本地恢复转发,以应对可能的多失效场景.
ACF在报文头中增加了大量的开销,且对应的域长度可变,不利于高速核心路由器的实现.
同时,由于采用恢复转发会造成路径长度较大,并有可能形成违反AS策略的转发路径.
4生存性路由协议的比较与评价基于不同应用场景、技术的生存性路由协议有着各自的特点,为了对当前的生存性路由协议有一个整体的了解,表1从多个方面对这些协议进行了比较,包括协议可应对失效类型、核心机制以及特点,着重比较了该协议通过何种方法解决收敛延迟大、瞬时失效的问题,另外,也列出该协议需要哪些假设条件、是否需要额外信令机制、报文转发方式、算法是否分布式、理论覆盖范围.
表中的None表示无特别的机制改善该指标.
为了进一步揭示,表2对生存性路由协议的性能和开销进行了比较,从协议收敛延迟、路径伸展度(即备份路径长度相对于最优路径增加幅度)、各种开销、实现复杂度、协议兼容性等角度进行了综合比较.
生存性协议所能应对的失效场景影响了协议的复杂度、性能及开销,而路径计算是否采用集中式与特定应用、假设条件相关.
通过表1和表2的比较,从生存性路由协议对路径建立和维护的时机、失效反应点两个角度分别对协议实现的复杂度、性能及开销进行了分析和总结.
(1)先验式预计算与反应式按需计算路径的比较.
对于先验式预计算路径的协议,由于其备份路径都是预先计算的,其算法的复杂度并不是影响性能的主要因素,当前节点检测到失效后立即切换到备份路径,先验式预计算路径与本地快速重路由结合几乎可以达到无缝持续转发.
域内/域间快速重路由、结构化备份子图等都采用了先验式和本地链路重路由的方法,相关实验结果也表明了该方法的良好性能.
这类方法的缺点是,需要在路由器中保存较多状态,且可能造成多次查找路由表,增加了开销.
反应式按需计算的协议主要包含信息携带辅助路由,这类协议算法复杂度、存储开销较低,但却需要利用每个报文头中的特殊信息进行即时的路径计算.
比如FCP[54],ACF[56]类的信息携带辅助协议其报文头开销长度可变,路由器转发平面实现困难.
相比而言,结构化备份子图的方法其报文头开销固定,更易于实现.
(2)源端路径级恢复与本地链路级快速重路由的比较.
绝大多数生存性路由协议采用了本地链路级快速重路由方法,其转发中断程度相对更低.
然而,本地链路级重路由需要复杂的路径切换机制,通常采用报文封装等1600JournalofSoftware软件学报Vol.
21,No.
7,July2010开销较大的操作.
首先,对于域内/域间快速重路由、结构化备份子图等协议,比如Deflections[35],FIR[36]等,为了避开失效点,经常需要报文回退,报文可能会多次经过同一节点,造成网络资源浪费;其次,本地链路级重路由仅依据本地知识选择备份路径,可能发生环路、选择次优路径的问题.
而源端路径级恢复可以避免类似问题,但却会增加中断时间.
生存性路由协议的选择涉及到网络拓扑、规模、协议性能、实现复杂度、兼容性、成本等多个关联因素,比如表2中的部分性能指标甚至会相互冲突.
举例来说,MRC[46]使用更少的备份拓扑降低了存储开销,但必然会造成网络稀疏,从而导致备份拓扑中路径伸展度更高.
如何达到效率和资源代价的合理折衷是需要着重研究的.
Table1Comparisonofcharacteristicsofsurvivableroutingprotocols表1生存性路由协议特点比较SolutionsProtocolFailuretypeProactive/ReactiveLocal/GlobalMulti-pathDomainLongconvergenceTransientunreachabilityLoopAssump-tionSignalDistri-butedPacketforwardingOFIB[28]SingleProactiveLocalNoIntraNoneOrderedupdateOrderedupdatePlannedfailureYesNoNormalORMS[29]SingleProactiveLocalNoIntraNoneNoneOrderedupdatePlannedfailureNoNoNormalLFA[31]SingleProactiveLocalYesIntraNoneReroute,backupnexthopSPTGTNoYesNormalU-turn[32]SingleProactiveLocalYesIntraNoneReroute,backupnexthopSPT,encap-sulationGTNoYesEncap-sulationTunnels[33]SingleProactiveLocalYesIntraNoneReroute,backupnexthopSPT,encap-sulationGTNoYesEncap-sulationNot-via[34]SingleProactiveBothYesBothNoneReroute,backupnexthopSPT,encap-sulationGTYesYesEncap-sulationDeflec-tions[35]SingleProactiveBothNoBothNoneDeflectionDeflectionrulesGTYesYesTagarchitectureFIR[36],FIFRN[39]SingleProactiveLocalNoIntraNoneRerouteFailureinferencingGTNoYesInterfacespecificSafe-Guard[54]SingleBothLocalNoIntraNoneTransient-modeRemainingpathcostCarrycost,GTYesYesDetectthenrescueProtec-tion[41]SingleProactiveLocalYesInterNoneReroute,protectiontunnelsEncap-sulationPolicy,coll-aborationNoYesEncap-sulationR-BGP[42]SingleProactiveLocalYesInterRCNReroute,backuppathRCNPolicy,coll-aborationYesYesEncap-sulationBRAP[43]SingleProactiveLocalYesInterReplacewithdrawReroute,backuppathEncap-sulationPolicy,coll-aborationYesYesEncap-sulationD-BGP[44]SingleProactiveLocalYesInterRCNReroute,backuppathRCNPolicy,coll-aborationYesYesEncap-sulationConsensusrouting[27]SingleProactiveLocalNoInterSnapshot,consensusTransientmodeSnapshot,consensusPolicy,coll-aborationYesYesEncap-sulationRRL[45]SingleProactiveBothYesIntraNoneBackuplayerLayeridentifierGTYesNoPacketmarkMRC[46]SingleProactiveBothYesIntraNoneBackuptopologyTopologyidentifierGTYesNoPacketmarkIPRT[49]SingleProactiveBothYesIntraNoneRedundanttreesTreeidentifierGTYesNoPacketmarkMARAs[50]SingleProactiveBothYesIntraNoneAlternativeroutingMAorderingGTNoNoNormal2DMRC[51]2ProactiveBothYesIntraNoneBackuptopologyTopologyidentifierGTYesNoPacketmarkDuallinkFailures[52]2ProactiveBothYesIntraNoneProtectionaddressProtectiongraphsGTYesNoEncap-sulationSplicing[53]Multi-pleProactiveBothYesBothNoneMultipleslicesSplicingheaderGTYesYesPacketmarkFCP[54]Multi-pleReactiveLocalNoBothNoneRecomputerouteFailurecarryingNetworkmapYesNoFailurecarryingBISF[55]Multi-pleProactiveLocalNoIntraNoneRerouteBlacklistGTYesYesInterfacespecificACF[56]Multi-pleReactiveLocalNoInterNoneDetectingandrecoveringPathtrace,blacklistAScoll-aborationYesYesRecoveryforwardingSPT:Shortestpathtree;Intra:Intradomain;InterInterdomain;GT:Globaltopology;RCN:Rootcausenotification苏金树等:互联网无中断转发的生存性路由协议1601Table2Comparisonofperformancesandoverheadsforsurvivableroutingprotocols表2生存性路由协议性能和开销比较OverheadProtocolConvergencedelayPathstretchCoverageImplementationcomplexitySignalPacketheaderComputationalcomplexityRIB/FIBentrystorageCompati-bilityOFIB[28]↑Low100%LowLowNoneHighLowYesORMS[29]↑Low100%LowNoneNoneHighLowYesLFA[31]-LowPartialLowNoneNoneHighLowYesU-turn[32]-LowPartialMediumNoneLowHighLowYesTunnels[33]-LowPartialMediumNoneLowHighLowYesNot-via[34]-LowPartialHighHighLowHighHigh,2*eNoDeflections[35]-Medium100%MediumLowMediumHighMediumYesFIR[36]FIFRN[39]-Medium100%MediumNoneNoneHighNoneYesSafeGuard[54]-Low100%HighLowMediumLowMediumNoProtection[41]-Low100%MediumNoneLowLowLow,2*normalYesR-BGP[42]↓Medium100%MediumLowLowLowLow,2*normalNoBRAP[43]↓Medium100%HighHighLowLowLow,2*normalNoD-BGP[44]↓Medium100%MediumLowLowLowLow,2*normalNoConsensus[27]↑Medium100%HighHighLowHighLow,2*normalNoRRL[45]-Medium100%MediumLowMediumHighMedium,N*normalNoMRC[46]-Medium100%MediumLowMediumHighMedium,n*normalNoIPRT[49]-Medium100%MediumLowLowMediumLow,2*normalNoMARAs[50]-Low100%MediumNoneNoneHighHighYes2DMRC[51]-Medium100%HighMediumMediumHighMedium,N*normalNoDuallinkfailures[52]-Medium100%HighMediumMediumMediumMedium,4*normalNoSplicing[53]-LowPartialLowLowMediumLowMedium,k*normalNoFCP[54]NoneHigh100%HighMediumHighLowLowNoBISF[55]-MediumPartialHighMediumHighHighMediumNoACF[56]-High100%HighMediumHighLowLowNoe:Numberofnodesinthenetwork;n:Numberofbackuplayers/topologies;k:Numberofslices;↑:Increase;-:Nochange;↓:Decrease5结论与未来展望生存性路由协议可以显著增强互联网的生存性,符合网络作为基础设施、新兴应用发展的需求,ISP也能够获得潜在利润.
近年来,生存性路由协议引起了学术界和工业界的广泛关注,这些协议的核心思想也相互影响,众多路由器厂商参与制定相关协议草案.
从目前研究的分布状况来看,针对域内协议的研究占多数,其原因在于,域内路由位于单管理域,可获得全局拓扑,开销在可承受范围内,出现了一些非常优秀的协议.
相比而言,域间生存性路由协议的研究更为迫切,应成为未来研究的重点.
我们认为,未来研究中需进一步解决的问题主要有:(1)可扩展性.
它直接影响协议的可行性,目前,生存性路由协议计算需求较高,开销普遍较大.
若能建立路由失效模型,或实施选择性保护,放松100%覆盖要求,将降低算法以及实现复杂性,在性能和开销之间达到平衡.
(2)生存性路由协议的实现与部署.
首先,设计新协议时需要考虑其兼容性,尽量避免对OSPF,BGP协议的语义、消息格式进行较大改动,否则,即使FCP[54]这样较好的技术也因为涉及到修改体系结构而导致目前难以实际使用.
其次,域间路由协议扩展性、稳定性问题更加突出[57],生存性路由协议不能引入过多开销,甚至要降低开销.
比如:降低更新消息数量以增强其稳定性、可扩展性;在路由器硬件体系结构中需要研究能够支持共享冗余的RIB,FIB,并且不会降低查询、更新时间.
目前,一些研究正在进行这方面的工作[58].
(3)流量工程.
由于生存性路由协议需要绕过失效组件快速重路由,必定导致大量流量转移,可能带来其他链路的拥塞,造成不必要的报文丢失.
目前,考虑流量负载均衡分布、路由优化的工作偏少[48,59].
1602JournalofSoftware软件学报Vol.
21,No.
7,July2010(4)BGP瞬时失效问题更加突出.
Internet中,AS规模、策略等阻碍了BGP学习更多的路径.
在不牺牲网络稳定性的前提下,进一步研究如何实现更灵活的BGP路由决策过程、如何通告或获取多样性路径[60]、如何改进转发过程等等.
(5)多失效场景下的生存性路由协议更具挑战性.
如何应对这种极端环境下的中断,需要进一步地从理论、机制上加以解决.
同时,协议设计需要探索如何综合考虑域内和域间路由相互影响的问题.
(6)生存性路由协议的模拟.
对于域内协议的模拟相对较为真实,然而当前对于域间生存性路由协议的模拟还只是将每个AS看作单个路由器节点,而AS之间的连接仅看作单条边.
这种模型缺乏合理性,与实际的AS拓扑并不相符.
即使CAIDA组织对Internet中AS拓扑进行了标注,也未考虑AS之间多条边的存在这一问题.
致谢衷心感谢对本文提出宝贵建议的匿名审稿专家以及对本文工作给予支持的老师和同学们.
References:[1]SchillingWW,AlamM.
MeasuringthereliabilityofexsitingWebservice.
In:Proc.
ofthe2007IEEEIntelector/InformationTechnologyConf.
LosAlamitos:IEEEComputerSociety,2007.
356361.
http://dx.
doi.
org/10.
1109/HICSS.
2007.
338[2]GummadiKP,MadhyasthaHV,GribbleSD,LevyHM,WetherallD.
Improvingthereliabilityofinternetpathswithone-hopsourcerouting.
In:Proc.
oftheOSDI2004.
SanFrancisco:USENIXAssociation,2004.
183198.
http://portal.
acm.
org/citation.
cfmid=1251267[3]PaxsonV.
End-to-Endroutingbehaviorintheinternet.
IEEE/ACMTrans.
onNetworking,1997,5(5):601615.
[doi:10.
1109/90.
649563][4]CiscoVisualNetworkingIndex.
Forecastandmethodology.
20082013.
2009.
http://www.
cisco.
com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_c11-481360_ns827_Networking_Solutions_White_Paper.
html[5]CholdaP,MykkeltveitA,HelvikBE,WittnerOJ,JajszczykA.
Asurveyofresiliencedifferentiationframeworksincommunicationnetworks.
IEEECommunicationsSurveys&Tutorials,2007,9(4):3255.
[doi:10.
1109/COMST.
2007.
4444749][6]IannacconeG,ChuahC,BhattacharyyaS,DiotC.
FeasibilityofIPrestorationinatier-1backbone.
IEEENetworkMagazine,2004,18(2):1319.
[doi:10.
1109/MNET.
2004.
1276606][7]WangH,YangYR,LiuPH.
ReliabilityasanInterdomainservice.
In:Proc.
oftheACMSIGCOMM2007.
Kyoto:ACMPress,2007.
229240.
http://doi.
acm.
org/10.
1145/1282380.
1282407[8]FeldmannA.
Internetclean-slatedesign:WhatandwhyACMComputerCommunicationReview,2007,37(3):5964.
[doi:10.
1145/1273445.
1273453][9]MarkopoulouA,IannacconeG,BhattacharyyaS,ChuahCN,GanjaliY,DiotC.
CharacterizationoffailuresinanoperationalIPbackbonenetwork.
IEEE/ACMTrans.
onNetworking,2008,16(4):749762.
[doi:10.
1109/TNET.
2007.
902727][10]BasuA,RieckeJG.
StabilityissuesinOSPFrouting.
In:Proc.
oftheACMSIGCOMM2001.
SanDiego:ACMPress,2001.
225236.
http://doi.
acm.
org/10.
1145/383059.
383077[11]LabovitzC,AhujaA,BoseA,JahanianF.
DelayedInternetroutingconvergence.
IEEE/ACMTrans.
onNetworking,2001,9(3):293306.
[doi:10.
1109/90.
929852][12]PeiD,WangL,MasseyD,WuSF,ZhangL.
Astudyofpacketdeliveryperformanceduringroutingconvergence.
In:Proc.
oftheDSN2003.
SanFrancisco:IEEEPress,2003.
183192.
http://ieeexplore.
ieee.
org/iel5/8589/27228/01209929.
pdf[13]WangF,QiuJ,GaoL,WangJ.
Onunderstandingtransientinterdomainroutingfailures.
IEEE/ACMTrans.
onNetworking,2009,17(3):740751.
[doi:10.
1109/TNET.
2008.
2001952][14]WangF,MaoZM,WangJ,GaoL,BushR.
Ameasurementstudyontheimpactofroutingeventsonend-to-endInternetpathperformance.
In:Proc.
oftheACMSIGCOMM2006.
Pisa:ACMPress,2006.
375386.
http://portal.
acm.
org/citation.
cfmid=1159956[15]ZhangY,MaoZM,WangJ.
Aframeworkformeasuringandpredictingtheimpactofroutingchanges.
In:Proc.
oftheINFOCOM2007.
Anchorage:IEEEComputerSociety,2007.
339347.
http://dx.
doi.
org/10.
1109/INFCOM.
2007.
47[16]KushmanN,KandulaS,KatabiD.
Canyouhearmenow!
ItmustbeBGP.
ACMSIGCOMMComputerCommunicationReview,2007,37(2):7584.
[doi:10.
1145/1232919.
1232927][17]RaiS,MukherjeeB,DeshpandeO.
IPresiliencewithinanautonomoussystem:Currentapproaches,challenges,andfuturedirections.
IEEECommunicationsMagazine,2005,43(10):142149.
[doi:10.
1109/MCOM.
2005.
1522138][18]PeiD,AzumaM,MasseyD,ZhangL.
BGP-RCN:ImprovingBGPconvergencethroughrootcausenotification.
ComputerNetworks,2005,48(2):175194.
[doi:10.
1016/j.
comnet.
2004.
09.
008]苏金树等:互联网无中断转发的生存性路由协议1603[19]ChandrashekarJ,DuanZH,ZhangZL,KraskyJ.
LimitingpathexplorationinBGP.
In:Proc.
oftheIEEEINFOCOM2005.
Miami:IEEEComputerSociety,2005.
23372348.
http://dx.
doi.
org/10.
1109/INFCOM.
2005.
1498520[20]ChoudhuryG.
PrioritizedtreatmentofspecificOSPFversion2packetsandcongestionavoidance.
RFC4222,2005.
[21]MaoZ,GovindanR,VargheseG,KatzRH.
RouteflapdampingexacerbatesInternetroutingconvergence.
In:Proc.
oftheACMSIGCOMM.
ACMPress,2002.
http://doi.
acm.
org/10.
1145/964725.
633047[22]YannuzziM,Masip-BruinX,BonaventureO.
Openissuesininterdomainrouting:Asurvey.
IEEENetwork,2005,19(6):4956.
[doi:10.
1109/MNET.
2005.
1541721][23]MühlbauerW,MaennelO,UhligS.
Buildinganas-topologymodelthatcapturesroutediversity.
In:Proc.
oftheACMSIGCOMM2006.
Pisa:ACMPress,2006.
195206.
http://portal.
acm.
org/citation.
cfmid=1159937[24]FeldmannA,MaennelO,MaoZM.
LocatingInternetroutinginstabilities.
In:Proc.
oftheSIGCOMM2004.
Portland:ACMPress,2004.
205218.
http://doi.
acm.
org/10.
1145/1030194.
1015491[25]OliveiraR,ZhangB,PeiD,ZhangL.
QuantifyingpathexplorationintheInternet.
IEEE/ACMTrans.
onNetworking,2009,17(2):445458.
[doi:10.
1109/TNET.
2009.
2016390][26]CaesarM,CaldwellD,FeamsterN,RexfordJ,ShaikhA,vanderMerweJ.
Designandimplementationofaroutingcontrolplatform.
In:Proc.
oftheNSDI2005.
Boston:USENIXAssociation,2005.
1528.
http://portal.
acm.
org/citation.
cfmid=1251203.
1251205[27]JohnJP,Katz-BassettE,KrishnamurthyA,AndersonT.
Consensusrouting:TheInternetasadistributedsystem.
In:Proc.
oftheNSDI2008.
Berkeley:USENIXAssociation,2008.
351364.
http://portal.
acm.
org/citation.
cfmid=1387614[28]FrancoisP,BonaventureO.
Avoidingtransientloopsduringtheconvergenceoflink-stateroutingprotocols.
IEEE/ACMTrans.
onNetworking,2007,15(6):12801292.
[doi:10.
1109/TNET.
2007.
902686][29]FrancoisP,ShandM,BonaventureO.
DisruptionfreetopologyreconfigurationinOSPFnetworks.
In:Proc.
oftheINFOCOM2007.
Anchorage:IEEEComputerSociety,2007.
8997.
http://dx.
doi.
org/10.
1109/INFCOM.
2007.
19[30]FrancoisPF,BonaventureO.
AnevaluationofIP-basedfastreroutetechniques.
In:Proc.
oftheACMCoNEXT2005.
Toulouse:ACMPress,2005.
244245.
http://doi.
acm.
org/10.
1145/1095921.
1095962[31]AtlasA,ZininA.
BasicspecificationforIPfastreroute:Loop-freealternates.
RFC5286,2008.
[32]AtlasA.
U-turnalternatesforIP/LDPlocalprotection.
IETFInternetDraft,Draft-Atlas-IP-Local-Protect-Uturn-03.
Txt,WorkinProgress,2006.
[33]BryantS,FilsfilsC,PrevidiS,ShandM.
IPFastrerouteusingtunnels.
IETFInternetDraft,Draft-Bryant-Ipfrr-Tunnels-03.
Txt,WorkinProgress,2007.
[34]ShandM,BryantS,PrevidiS.
IPfastrerouteusingnot-viaaddresses.
IETFInternetDraft,Draft-Ietf-Rtgwg-Ipfrr-Notvia-Addresses-03.
Txt,2008.
[35]XiaoweiY,DavidW.
Sourceselectablepathdiversityviaroutingdeflections.
In:Proc.
oftheACMSIGCOMM2006.
Pisa:ACMPress,2006.
159170.
http://doi.
acm.
org/10.
1145/1159913.
1159933[36]NelakuditiS,SanghwanL,YinzheY,ZhangZL,ChuahCN.
Fastlocalreroutingforhandlingtransientlinkfailures.
IEEE/ACMTrans.
onNetworking,2007,15(2):359372.
[doi:10.
1109/TNET.
2007.
892851][37]LiA,YangX,WetheralD.
SafeGuard:Responsiveroutingwithconsistentforwarding.
In:Proc.
oftheACMCoNext2009.
Rome:ACMPress,2009.
301312.
http://doi.
acm.
org/10.
1145/1658939.
1658974[38]LiA,FrancoisP,YangX.
OnimprovingtheefficiencyandmanageabilityofNotVia.
In:Proc.
oftheACMCoNext2007.
NewYork:ACMPress,2007.
112.
http://doi.
acm.
org/10.
1145/1364654.
1364688[39]ZifeiZ,NelakuditiS,YinzheY,LeeS,WangJ,ChuahCN.
Failureinferencingbasedfastreroutingforhandlingtransientlinkandnodefailures.
In:Proc.
oftheINFOCOM2006.
Barcelona:IEEEComputerSociety,2006.
15.
http://dx.
doi.
org/10.
1109/INFOCOM.
2006.
353[40]GaoL,RexfordJ.
StableInternetroutingwithoutglobalcoordination.
IEEE/ACMTrans.
onNetworking,2001,9(6):681692.
[doi:10.
1109/90.
974523][41]BonaventureO,FilsfilsC,FrancoisP.
Achievingsub-50millisecondsrecoveryuponBGPpeeringlinkfailures.
IEEE/ACMTrans.
onNetworking,2007,15(5):11231135.
[doi:10.
1109/TNET.
2007.
906045][42]KushmanN,KandulaS,KatabiD,MaggsBM.
R-BGP:Stayingconnectedinaconnectedworld.
In:Proc.
oftheNSDI2007.
Cambridge:USENIXAssociation,2007.
341354.
http://citeseerx.
ist.
psu.
edu/viewdoc/summarydoi=10.
1.
1.
86.
4001[43]WangF,GaoL.
Abackuprouteawareroutingprotocol-fastrecoveryfromtransientroutingfailures.
In:Proc.
oftheIEEEINFOCOM2008.
Phoenix:IEEEComputerSociety,2008.
23332341.
http://dx.
doi.
org/10.
1109/INFOCOM.
2008.
302[44]WangF,GaoL.
Pathdiversityawareinterdomainrouting.
In:Proc.
oftheIEEEInfocom2009.
RiodeJaneiro:IEEEComputerSociety,2009.
307315.
http://dx.
doi.
org/10.
1109/INFCOM.
2009.
50619341604JournalofSoftware软件学报Vol.
21,No.
7,July2010[45]FosselieHA,KvalbeinA,CicicT,GjessingS,LysneO.
Resilientroutinglayersforrecoveryinpacketnetworks.
In:Proc.
oftheDependableSystemsandNetworks(DSN).
Yokohama:IEEEcomputerSociety,2005.
238247.
http://dx.
doi.
org/10.
1109/DSN.
2005.
81[46]KvalbeinA,HansenAF,CicicT,GjessingS,LysneO.
FastIPnetworkrecoveryusingmultipleroutingconfigurations.
In:Proc.
oftheINFOCOM2006.
Barcelona:IEEEComputerSociety,2006.
111.
http://dx.
doi.
org/10.
1109/INFOCOM.
2006.
227[47]PsenakP,MirtorabiS,Pillay-EsnaultP.
Multi-Topology(MT)routinginOSPF.
IETFRFC4915,2007.
[48]ApostolopoulosG.
UsingmultipletopologiesforIP-onlyprotectionagainstnetworkfailures:Aroutingperformanceperspective.
TechnicalReport,ICS-FORTH377,Greece,2006.
[49]CicicT,HansenAF,ApelandOK.
RedundanttreesforfastIPrecovery.
In:Proc.
oftheBROADNETS.
Raleigh:IEEEComputerSociety,2007.
152159.
http://dx.
doi.
org/10.
1109/BROADNETS.
2007.
4550419[50]OharaY,ImahoriS,vanMeterR.
MARA:Maximumalternativeroutingalgorithm.
In:Proc.
oftheInfocom2009.
RiodeJaneiro:IEEEComputerSociety,2009.
298306.
http://dx.
doi.
org/10.
1109/INFCOM.
2009.
5061933[51]HansenAF,LysneO,CicicT,GjessingS.
Fastproactiverecoveryfromconcurrentfailures.
In:Proc.
oftheICC2007.
Glasgow:IEEEComputerSociety,2007.
115122.
http://dx.
doi.
org/10.
1109/ICC.
2007.
28[52]KiniS,RamasubramanianS,KvalbeinA,HansenAF.
FastrecoveryfromduallinkfailuresinIPnetworks.
In:Proc.
oftheInfocom2009.
RiodeJaneiro:IEEEComputerSociety,2009.
13681376.
http://dx.
doi.
org/10.
1109/INFCOM.
2009.
5062052[53]MotiwalaM,ElmoreM,FeamsterN,NempalaS.
Pathsplicing.
In:Proc.
oftheSIGCOMM2008.
Seattle:ACMPress,2008.
2738.
http://doi.
acm.
org/10.
1145/1402958.
1402963[54]LakshminarayananKK,CaesarMC,RanganM,AndersonT,ShenkerS,StoicaI.
Achievingconvergence-freeroutingusingfailure-carryingpackets.
In:Proc.
oftheACMSIGCOMM2007.
Kyoto:ACMPress,2007.
241252.
http://doi.
acm.
org/10.
1145/1282380.
1282408[55]WangJ,ZhongZ,NelakuditiS.
Handlingmultiplenetworkfailuresthroughinterfacespecificforwarding.
In:Proc.
oftheGLOBECOM2006.
SanFrancusco:IEEEComputerSociety,2006.
16.
http://dx.
doi.
org/10.
1109/GLOCOM.
2006.
33[56]ErmolinskiyA,ShenkerS.
Reducingtransientdisconnectivityusinganomaly-cognizantforwarding.
In:Proc.
oftheACMSIGCOMMHotnetVII.
Calgary:ACMPress,2008.
9196.
http://citeseerx.
ist.
psu.
edu/viewdoc/summarydoi=10.
1.
1.
141.
3080[57]ElmokashA,KvalbeinA,DovrolisC.
OnthescalabilityofBGP:Therolesoftopologygrowthandupdaterate-limiting.
In:Proc.
oftheCoNEXT2008.
Madrid:ACMPress,2008.
112.
http://doi.
acm.
org/10.
1145/1544012.
1544020[58]deCarliL,PanY,KumarA,EstanC,SankaralingamK.
PLUG:Flexiblelookupmodulesforrapiddeploymentofnewprotocolsinhigh-speedrouters.
In:Proc.
oftheACMSIGCOMM2009.
Barcelona:ACMPress,2009.
207218.
http://doi.
acm.
org/10.
1145/1592568.
1592593[59]KvalbeinA,CicicT,GjessingS.
Post-Failureroutingperformancewithmultipleroutingconfigurations.
In:Proc.
oftheIEEEINFOCOM2007.
Anchorage:IEEEComputerSociety,2007.
98106.
http://dx.
doi.
org/10.
1109/INFCOM.
2007.
20[60]GodfreyPB,GanichevI,ShenkerzS,StoicaI.
Pathletrouting.
In:Proc.
oftheACMSIGCOMM2009.
Barcelona:ACMPress,2009.
111122.
苏金树(1962-),男,福建莆田人,博士,教授,博士生导师,CCF高级会员,主要研究领域为计算机网络,信息安全.
赵宝康(1981-),男,博士,助理研究员,主要研究领域为无线网络安全,高性能路由器.
胡乔林(1979-),男,博士生,主要研究领域为网络生存性.