BGP协议改进,Bgp 协议

('1.4BGP慢收敛问题................................................................................................................11.4.1慢收敛问题.............................................................................................................11.4.2两种讨论方案..........................................................................................................21.5论文工作............................................................................................................................3第二章RouteChangeOrigin机制对BGP系统的改进分析.........................................................32.1慢收敛的说明....................................................................................................................42.2慢收敛的一种解决方案.....................................................................................................52.3路径向量协议和RCO改进协议分析模型.......................................................................62.3.1OriginalSimplePathVectorProtocol-SPVP1.......................................................62.3.2改进简单路径向量协议-SPVP2.........................................................................112.4SPVP1和SPVP2收敛特性分析.....................................................................................122.4.1全连接AS图的收敛特性.....................................................................................132.4.2SPVP2的任意图的收敛特性...............................................................................182.5小结..................................................................................................................................19第三章RCO机制性能验证与比较..............................................................................................203.1模拟验证工具及参数.......................................................................................................203.1.1模拟工具...............................................................................................................203.1.2时间模型:..............................................................................................................203.1.3拓扑模型...............................................................................................................213.1.4度量参数...............................................................................................................213.2分类模拟及实验结果.......................................................................................................223.2.1源变化情况的模拟:...............................................................................................223.2.2会话变化情况:......................................................................................................24第四章RCO机制的讨论..............................................................................................................274.1RCO机制的讨论.............................................................................................................285.1结论..........................................................................................................................................295.1.1论文工作总结...............................................................................................................291.4BGP慢收敛问题Internet在商业上取得了很大的成功,但是它在可用性,可靠性和服务质量等发方面仍然滞后于传统的电信网.从1995年至今,BGP吸引了一些研究人员的目光,陆续进行了多方面的研究工作,代表的有RameshGovindan[8],GeoffHouston[9],LixinGao[10,11]等对AS级别的网络拓扑,增长规律和路由稳定性等方面作的多研究;Griffin等人在[12,13,14,15]从理论上对BGP不收敛问题的探讨等.1.4.1慢收敛问题人们曾经认为,Internet在出现故障情况下会很快的恢复或找到很好的路由.至少有一篇报导[16]采用定量的端用户经验的方法认为Internet域之间的路径恢复时间应该小于或者在30秒的量级,而这些延迟被认为主要是由于队列,路由器CPU处理时间造成的.但是,在CraigLabovitz的文章[3]显示,这些传统的关于Internet错误路径结束时间的认识都是不正确的,尽管BGP避免了RIP协议的路由环路问题,但是它仍图1-6测量拓扑示意图然存在着满收敛问题.Labovitz通过图1-6的测量拓扑,在ISP1中向网络周期的注入错误的路由,等到系统稳定后再恢复路由,通过工具在其它几个ISP处检测与该路由相关的UPDATE报文.在两年间,主动的注入路由来模拟路由错误,恢复等.他将路由事件分成四类:Tup:原来不可用的路径被通告为可用.代表一条路径的修复.Tdown:原来可用的路径被撤回,代表路由的错误,所有的路由都不可用.Tshort:一条长的正确路由被一条短的路由隐式的撤回替代,代表一条路径的修复及错误结束(Failover).Tlong:一条可用的短的路由被隐式的长的路径所替代,代表一条路径错误和错误结束.这四类路由事件表现出不同的延迟(见图1-7)图1-7四类路由事件的延迟及UpdateMessages统计图1-7(a)显示的是在所有ISP监测的四类路由事件得到的收敛时间积分分布,横轴代表从注入错误到所有ISP的路由表达到稳定的经历的时间(以秒为单位),纵轴是所有注入事件次数的比例积分.这四类事件都显示了很长的收敛时间分布,数据显示,至少20%的Tlong和40%的Tdown时间将至少持续3分钟,对于某些少数但仍有一定比例的事件其收敛时间可以达到15分钟之长.数据显示,约70%的Tup和Tshort将在90秒内收敛,而同一时间内,只有5%的Tdown和Tlong事件会收敛;至少20%的Tlong和40%的Tdown时间将至少持续3分钟,要比Tup和Tshort慢好多.图1-7(b)显示的是在注入四类路由事件之后,5个ISP产生的BGP消息数量,含通告和撤回报文.观察显示,每个ISP在Tdown和Tlong,消耗的报文平均接近于2倍的Tup和Tshort.Labovitz认为收敛延迟与ISP的地理分布和网络距离无关,只与拓扑等因素有关.他的后续分析[4]发现,在Tdown事件发生的时候,一些AS在收敛之前邹时有很大的概率选择器它错误的备份路由.Labovitz的理论分析表明,对于一个n个节点的BGP系统,在某一个网络前缀发生Tdown情况下,收敛时间的下界是(n-1),上界是O((n-1)!).1.4.2两种讨论方案慢收敛问题应该说是对BGP协议的一个新的认识.导致慢收敛主要有两个因素,一个是协议本身分布式的特点,使得路由器在选路的时候一直穷举错误的路径直到最终收敛,另一个因素是由于MARI的影响.MRAI是可以配置的,在路由器向它的邻居发送一条新路径的时候,它将启动MRAI计时器,在定时器结束之前,路由器都不可再向该邻居发送相同网络前缀的路由信息,这样可以减少系统报文的数量,因为在MRAI超时之前,路由器可能接收到许多报文,进行多次的选路进程,采用定时器就可以避免尽量少的让邻居路由器得到这些不必要的中间过渡信息,这减少了收敛过程的报文数.然而它的负面效果是增加了收敛的时间.如何解决慢收敛问题,Labovitz在文章中并没有给出一个确切的方法,只是推测改进定时器,或者增加路由环检测一项,应该可以缓解慢收敛.针对这种提议,Griffin等人[17]作了模拟工作,试图找到一个最优值来加快收敛.虽然他针对一个简单的拓扑的可以得到一个最优值,然而实际的网络无论在规模还是操作上都要复杂得多,很难为现实网络找到一个理论的最优值.并且,他的改进效果并不明显.另外,D.Pei在[32]中提出通过ConsistencyAssertion来判断解决慢收敛问题.基本想法是当一个路由器接收到来自不同邻居的报文时候,它根据这些报文的矛盾来判断可能的问题出在哪里,并过滤它认为是错误的路由.他的结果显示的相比之下由很大的改进,但是它的协议没有明确的指出慢收敛的原因是什么,同时很难保证它的判断是正确的,这样会影响它的效果.1.5论文工作论文的研究工作主要包括三个方面的内容:对慢收敛问题进行了深入的分析,提出了一个新的解决机制--路由变化源(RouteChangeOrigin,RCO)[20];通过建立两个简单路径向量协议模型(SimplePathVectorProtocol,SPVP),深入的分析了RCO机制的收敛特性,并同源协议做了理论对比;通过模拟数据验证了理论分析结果.同前面介绍的两种提议机制相比,RCO机制概念更清晰,效果更好,是本论文的创新点.本文的具体结构如下:在第二章中,首先对慢收敛问题进行分析和说明,并提出一个新的解决机制—路由变化源(RouteChangeOrigin,RCO).通过对路径向量协议的抽象,建立了两个简单路径向量协议模型(SimplePathVectorProtocol,SPVP)用来描述原有BGP协议和增加了RCO机制的改进协议.通过理论分析,对比两个协议在Tdown情况下的收敛特性.第三章中,着重讨论了模拟工作的方法和模拟结果.通过改进现有的模拟工具,实现RCO机制.在此基础之上,针对两类不同的拓扑和不同的RCO情况进行模拟,并对不同的现象做了解释,相关的实验数据验证了第二章中的理论分析,也支持了RCO机制的和理性.第四章针对在实际理论和模拟工作中出现的一些问题进行了简单的分析和讨论,并对论文的创新点做了总结,同时对RCO机制和BGP慢收敛问题的进一步研究进行了展望.第二章RouteChangeOrigin机制对BGP系统的改进分析本部分试图针对BGP慢收敛特性,提出了一个可行的解决方案,为了分析改进协议与原协议的性能,建立了两个简单路径向量协议模型,通过理论分析,给出两个协议在收敛过程中的性能比较.2.1慢收敛的说明为了更清楚的理解慢收敛问题,先用一个简单的拓扑来解释一下.在图2-1中,每个节点代表一个简化的AS,每个AS只有一个eBGP路由器,AS之间的连接如图所示.只考虑一个属于AS0的目的网络前缀X,其它每个AS的所有到达网络前缀X的路由(AS路径)都列在各自的旁边,其中,第一行是它的最佳路由.例如,对于AS2来说,它有两条可用路由,分别为(0),(410),表示AS2可以直接通过AS0到达网络前缀X,或者可以顺序的经过AS4,AS1,AS0到达网络前缀X,显然路由(0)的路径最短,AS2选择该选项最为最佳路由.这里,我们不考虑策略和其他复杂的关系,只考虑最短路径优先的原则,即选择AS路径最短作为最佳路由.AS0AS1AS2AS3AS4PrefixXFigure1.SimpleTopology04100104101020310图2-1慢收敛说明示意图下面,我们将会看到如果有拓扑变化时,系统中每个AS是如何选择路由的.假设网络前缀X与AS0的内部链路出现故障,AS0的BGP路由器将从IGP协议得到这一信息,BGP路由器会直接把网络前缀X从路由表项中剔除,同时向它的邻居AS1和AS2通告这一变化.我们看看根据目前的协议会出现哪些可能的情况.由于AS1只有一条可用路由(0),所以在接收到AS0的撤回报文的时候,直接把该条表项删除,并向AS3和AS4发送撤回报文.当AS3接收到AS1的撤回报文之后,将把路由表项(10)删除,尽管另一条路由(410)实际上已经不可用,AS3还是把它选为最佳路由,然后把这条新路由通告给AS1(我们假设这里没有采用路由环的检测).同样,对于AS2也有类似的问题,它有两条可用路由(0)和(410),在收到AS0的撤回报文之后,AS2将删除路由表项(0),并选择(410),作为最佳路由,并把这个新的路由通告给AS4.而AS4根据AS1,AS2,AS3的报文传播和处理时间的快慢,可以选择不同的路由作为最佳路由,尽管这些路由信息都是错误的.实际上,以上的描述仅仅是其中的可能一种,由于系统的异步性,它还有好多其它的可能.同样,如果AS0和AS1之间的BGP会话(对于AS1来说,该会话表示为[10],而对于AS0来说则表示为[01])因为某种原因而中断,表明通过会话[10]不可能到达网络前缀X,再收敛过程中也会也会产生类似的过程.从上述分析不难想象,对于现实的网络,无论在规模还是复杂程度上,都要远远的超过上面的拓扑,因而当出现一个故障点的时候,路由器在收敛过程中很容易选择非法的路由,经过很长的时间才能达到收敛,趋于稳定.可以看到,本来备份路由是为了提高冗余,但是在收敛过程中起到了负面的效果.2.2慢收敛的一种解决方案从上面的例子中,定义慢收敛如下:在BGP系统拓扑或策略发生变化导致涉及某个网络前缀的部分或全部路由不可用时,AS选择无效路径而导致的系统收敛的迟延现象.实际上,产生慢收敛的主要原因是,根据目前的BGP协议,路由器在撤回一条路由的时候,撤回报文只是撤回单一的路由表项,它所携带的信息并没有明确的指出撤回的最根本原因是什么,所以路由器在接收到报文的时候,只是删除或替换对应对等体Loc_RIB_In中的路由表项,却从不区别其他备份路由是否还是同样有效.并且,撤回报文在传播的过程中,所携带的拓扑变化信息会变得越来越少,容易导致远处的BGP路由器在选路的时候,分辨错误路由的能力变得更低,这样就更容易导致将错误的路由发布到BGP系统中.因而,解决慢收敛的一个途径就是如何填加一些信息,从而可以指导AS的路由器在路由发生变化时,能迅速的选择正确的路径.对比前面介绍的链路状态路由协议OSPF,可以看到OSPF可以迅速的向区域内部的域内路由器发送链路状态的变化信息,指出是哪一个链路不可用,从而使每个OSPF路由器可以在短时间内收敛.受其启发,可以对现有的BGP协议进行改进,对于由于拓扑或者策略造成的路由变化,在BGP的更新报文中增加拓扑变化信息的说明,指出拓扑变化的原始起点,从而有助于BGP路由器的选路过程,过滤掉一些由这些变化导致的非法路径来避免或加速慢收敛的问题.这里使用一个新的概念路由变化源(RouteChangeOrigin,RCO),用于描述拓扑或者策略变化,这些变化可能是发生在网络前缀X接入的AS0内部(但是不影响AS0的BGP路由器正常工作),称这种为"源变化"(SourceRouteChange),而AS0称为"源RCO"(SourceRCO,因为AS0是网络前缀X的发源地),表示为RCO=[0];或者变化发生在一个BGP会话,如上面的例子中,BGP会话[10]的中断,这种称为"会话变化"(SessionRouteChange),该会话称为"会话RCO"(SessionRCO),表示为RCO==)(Xorigins=)(Xoriginl[10].这样,RCO就可以明确的指出在路由变化的时候,具体是由于哪一段会话或AS内部问题导致的该网络前缀的路由不可用,也就是说,任何含有该RCO的路由表项都是不可用的.其它的沿用现有的机制传播相应的更新报文,当其他的BGP路由器接收到该消息的时候,就可以在选路过程中,可以过滤掉含有这些RCO的路由,不再考虑这些路由,这样在某些情况就可以完全消除慢收敛问题,或很大程度上加速收敛.例如,上述的例子中,AS1在检测到会话[10]中断情况下,它将向AS3和AS4发送撤回报文,并携带RCO=[10],用于指出该路由的变化是由于会话[10]的中断引起,这样当AS3接收到该消息后,在重新进行选路时,由于(310)和(3410)含有RCO=[10],因而就会直接将这两条路由标记为不可用,就不会再选择错误的路由;同样对于AS4,在标记(10),(310)为非法之后,会直接选择路径(420),这样AS4就直接选择了正确的路由,避免了可能的错误路由的影响.RCO除了上述两种之外,还有一类是由于策略变化引起的.这种策略实际是由于人为因素而改变路由的,例如,AS3在正常的情况下,应该选择路由(10)作为最佳路由,但是人为地原因,它可能突然变化,选择路由(420)做为最佳路由,这种情况实际上是会话变化情况的一个变化.所以在后面的讨论主要集中在对于源变化和会话变化两种情况.下面我们首先对原协议和RCO改进协议建立一个简单的模型.2.3路径向量协议和RCO改进协议分析模型第二章RouteChangeOrigin机制对BGP系统的改进分析上述是对慢收敛提出的解决方案的简单说明,为了更好地分析该方案的性能,比较原协议和RCO改进协议的收敛特性,我们首先建立了两个简单的路径向量协议模型(SimplePathVectorProtocol,SPVP),其中SPVP1是原BGP协议的抽象描述,SPVP2是改进协议的模型描述.这两个模型的基本特性与BGP的相关标准一致.但是为了便于分析的简单,集中考虑收敛问题,我们针对模型做了如下的假设和简化:1.不考虑AS的IBGP关系,假设每个AS只有一个运行路径向量协议的边界路由器,即把AS简化成一个边界路由器;用AS来代替它的路由器;2.任意两个AS之间值存在一个路由会话,不考虑策略的影响;3.每个AS最多只有一条最佳路由;4.假设每个路由器传播和处理更新报文的时间都是相同的;5.只考虑一个属于AS0的网络前缀X,避免考虑过多的网络前缀而导致分析的混乱;6.选路的原则基本是按照路径最短优先原则(ShortestPathFirst).实际上,SPVP1和SPVP2是尽可能简化的路径向量协议.这个模型同Griffin在[13,14]中建立的模型有一些类似,但是不同的是,我们的模型主要集中讨论收敛特性,同时在模型中定义的状态和状态的转移是完全不同的.2.3.1OriginalSimplePathVectorProtocol-SPVP1在这个模型SPVP1中,Internet模型化为一个无向图},{EVG=,其中V是节点的集合,任意一个节点Vv∈代表网络中的一个AS;E代表边的集合,任意一个边代表两个AS之间的一个会话连接.Ee∈对于任意一个节点,我们用代表该节点的邻居的集合,同时用i)(ineighbors)(ineighborsni=表示该节点i的邻居数目,对于一个连通的图,该节点的邻居数目应该不小于1.假设在初始状态,节点有i)0(inKK≤≤条到达AS0的内部网络前缀X的备选无环路由表项,这些路径分别为,其中下标.所以对于任意的AS(非AS0)来说,如果它在初始状态有路由到达网络前缀X,则它的这些路由一定是从它的邻居AS得到的.其中每个备选路由表示为从该节点出发,到达目的前缀X经过的所有节点(AS)的路径,具体形式为:Kiiiiiirrr,...,,21∈Kiii,,,21L)(ineighbors),,,(21XaairjiijL=这里i,)(ineighborsj∈Vaa∈K,,21(riij.(注:为了方便,我们用X来代表每一条路由中路径节点号AS0,这样),,,21XaaijL=等价于)0,,,(21Laairjiij=).这条路由表示该路由表项是由邻居节点发送过来的,节点可以按照如下的顺序到达目的前缀X:jii0,,,21Laaij.为了便于讨论,我们把节点的备份路由由K维扩展成维的形式:iininiiiiiirrr,...,,21,每条路由表项对应一个邻居AS.如果一个节点没有接收到邻居节点发送过来的到达目的前缀X的路由,则相应的备选路由表示为iji)(=jiir.这样就得到了一致的表示.每个节点在进行选路决策中,从所有备选路由中选择唯一一条最佳路径:iiriniiiiiirrr,...,,21})({jiiirBestr=Best表示选路进程:r是具有最高的评价的路由,其中,备选路由的评价函定义为:i)(jiirrank)(ineighborsij∈ikr()nodefirstrlengthrrrank_./1,./1)(=ikikik,该函数意为着的路径越短,它的评价就越高;如果两条备选路径的长度相同,那么路径向量的第一个节点AS数字越小,相应的评价越高.例如假设节点有两条备选路由=(246)和=(3456),显然根据评价函数,同路径长度为4的路径相比,r的路径长度为3,应该有更高的评价;而如果节点两条路径分别为=(246)和=(346),由于两条路径的长度相同,根据评价函数路径的第一节点是AS2,而路径的第一个节点是AS3,比AS2的数字要大,所以有更高的评价.ikrikrir2ir3ir3ir2iir2ir3ir2ir3ir2ir在节点没有任何备选路由的情况下,允许i)(=ir.如果,那么节点使用作为到达目的前缀X的分组转发路由.这里定义节点i的状态为其最佳路由,即=.当它的状态变化的时候,例如,节点一般情况下向它的所有邻居节点发送更新报文,根据报文的类型,可以分成两大类:通告(Announcement)和撤回(Withdrawal).具体的定义如下:)(≠ir\'is→iirisirisirisi如果并且,节点产生更新报文,发送给邻居节点,告诉邻居节点通过"我"的一条新路径可以到达目的前缀X.这里的更新报文表示为:)(\'≠→iiss\'iiss≠ij,)(:\'ijisijim→=注意,这里的箭头表示报文由节点发送给节点,m下标表示是由节点来处理来自节点的报文,而"→ijjiji"操作定义为,其中,也就是说节点在发送路由之前应该把自己的AS号附加到路径向量的最前面.在本文中这类的报文消息称作通告Announcement.)1XaiiikLjim(\'si=)),1\'ineighborsiXaiskki∈L((=i如果,这意味着节点这个时候无法到达目的前缀X,它先前告诉邻居节点的路由信息已经失效,这就要撤回失效的消息,该消息称为撤回报文(Withdrawal),表示为:)()(\'=→≠iissi,wjimji:→=其中的w表示Withdrawal.以上关于消息报文的定义为下面关于消息的产生和发送规则做了基础描述.定义全局状态是图中所有AS节点的状态的集合,同时包括每个节点的所有未处理的消息报文:SG),...,,,,......,,(2121VVMMMsssS=,其中,表示在一个特定时刻,邻居节点发送给节点的所有待处理消息.)(,ineighborsjmMjiji∈=Ui全局的状态转移定义如下:\'SS→σ,其中,==≠∈=φσφσσσσσiiiiikMifMifM,0,,...),,......,,(21这里假设一个转移过程中,每个节点都处理消息队列中的一个消息,如果他的消息队列不为空的话.在这个转移定义中,对于任意的一个非空的报文iσ,节点i将进行选路进程.选路进程),(\'iiisprocesssσ=),(iisprocessσ主要是通过一下三步实现,同BGP选路进程是一致的:ijwik:→ijneighborsk∈ikr\':21≠→=XakaikL(\'rik=)Xijr\'ikrji)(ineighbors,kj({\'Bestsi=i,0jomji∈=)XL\'=is≠om,neighborskj∈Step1.首先,节点应该按照下面的规则更新备份路由:1)如果0=iσ,则对于所有的有;ijrr=\'2)如果miki==σ,,节点应该替换相应的由邻居节点发送过来的备选路由为空:)(i\')(=ikr,并且对于任意的有;kj≠ijr=ij3)如果0=mikiσ,节点应该将邻居节点发送过来的备选路由替换为新的路由:,这里要求节点没有出现在路径向量中,以保证不会出现环路,否则;其它任意的,有i)Xki)21aLka21akaLijr((=k≠=\'.Step2.然后根据这些更新的备选路由,节点进行选路进程,同前面描述的相同:}),\'jrij∈Step3.最后,节点把得到的新的最佳路由通过更新报文om按照如下规则发送给邻居:1)如果,;iiss=\')(ineighbors2)如果且,那么对于(1kasi=)(而对于有,其中;,:wjiji→=,kj=0=jiom)(i3)如果且,对于)(\'≠isiisXkas≠=)(1\'L,kj≠)(:\'ijisijiom→=,对于,其中.,kj=0=jiom)(ineighbors∈,kj这样,我们得到更新之后的ViMi≤≤1},{\':M.)(,\'ineighborsjomMjiiii∈+=σ定义这样的转换σ为一轮(round).如果一个转换是一个有限序列,称之为一个h-轮转换序列.如果一个全局状态,对于所有的hσσσ......21SViMi≤≤1,都是空的,那么称它为最终稳态(finalstablestate).如果对于所有的Vi≤≤0S1,在全局状态到达最终稳态的过程中,每个节点的状态在转换过程中没有变化,称这种全局状态是稳定状态.在这种状态,尽管没个节点可能还有要处理的报文,但是这些报文不会引起它的状态的变化.在这里用从初始全局状态到一个稳态的转换序列的长作为衡量简单路径向量协议收敛时间的一个度量.SisS2.3.2改进简单路径向量协议-SPVP2现在在SPVP1的基础上,添加RCO来加速收敛过程,定义这个改进的协议为SPVP2.因为Tdown事件在网络中是经常发生的路由变化(参见Labovitz[3,18,19]),慢收敛现象明显,所以这里主要探讨SPVP2中Tdown事件的收敛延迟问题.Tdown事件主要可以分成两类:分别由源变化和会话变化引起.在下面将分别的进行讨论.如前面所述,RCO是对路由变化事件源头的描述.在由源变化引起的网络前缀X的Tdown事件情况下,RCO==)(Xorigins[0]只能由AS0发起产生;而对于会话变化引起的Tdown情况,只能由会话两端的AS发起首个RCO,例如会话[10]出现故障,只有AS1发起产生RCO==)X(originl[10],而对于AS0可以产生RCO==)(Xl\'imji=origin[01](注意,会话RCO中的AS号码是有顺序的,第一个AS号是自身的号码.对于本例,AS0产生的AS0没有实际意义).),(iisσ0\'=iσ\'iσ)(m∈≠ijrorigin∈)(ineighbors显然,在源变化情况下,网络前缀X是完全不可达的,这意味着此刻其他任意AS节点达到X的路由都变成无效的,所以产生关于前缀X撤回消息的AS可以利用RCO来通知其它的AS所有路径无效.这样,在SPVP2中,通告消息改为,撤回消息可以更改为,而对于源变化情况,是不会产生通告消息的.任何由RCO引起并产生的报文必须在它的报文中加入RCO,并传递给他的邻居,即RCO是可传递的.这里允许))(,(:\'Xoriginsijimiji→=)())(,(:Xoriginwj→=origin,表示没有RCO的变化事件,这可以是Tup事件(注意,RCO机制不用于Tup事件),相应的选路进程process要作如下更改为:)\'iσ,is(\'process1)如果,不发生状态变化,且不产生输出消息;2)如果(0\'≠=ikm)(ineighborsk∈),要作如下修改:如果,那么首先检查备份路由,如果RCO=,即备份路由中含有RCO,则,否则,其中;\'ikoriginj∈),(\'\'iisprocessσ)(\'=ijrijijrr=\'之后的选路过程和),(sprocessiiσ相同;对于输出报文,与SPVP1的类似,只是最后在报文中同样的增加了RCO.实际上,当源变化事件发生的时候,一旦一个节点第一次接收到撤回消息,这个节点将把所有前缀X的备选路由标记为非法,并向他曾经发送过路由信息的所有邻居发送同样含有RCO的撤回消息.这样,每个AS就不会选择错误的消息了.2.4SPVP1和SPVP2收敛特性分析根据上述模型,分别对SPVP1和SPVP2在源变化事件情况下的收敛特性进行讨论.在SPVP2的定义中,可以看到,在源变化情况下,当路由器接收到含有的报文时候,将标记所有到达网络前缀X的备选路由为非法,所以对于每一轮,SPVP2节点都不会选择任何错误的路由作为它的最佳路由.于是可以得到如下的一个结论:)(Xorigins定理1.对于源变化产生的Tdown事件,SPVP2系统的节点在收到撤回报文的时候就会收敛,除了向邻居节点发送撤回报文外不回发送其它任何错误的通告报文.2.4.1全连接AS图的收敛特性在这一部分将讨论全连接AS图的收敛特点.尽管全连接AS图是一个很特殊的情况,但是对它的分析可以很好的用来理解收敛特性.这里考虑一个大小为n+1的全连接图G,节点分别为AS0,AS1,…ASn.正像前面模型中定义的那样,AS0拥有网络前缀X(后文中用X来代表该节点),并在Tdown事件发生的时候发出含有=)(Xsorigin[0]的撤回报文.对于这种由源变化产生的Tdown事件,origin表示为[X],而初始的全局状态为((X),(X),(X),….,(X),{X->1:w},{X->2:w},…,{X->n:w}),最终稳态为((-),(-),…,(-),)(Xs0Sφ,…,φ).因为X的状态在整个过程中始终没有变化,为了简单起见,在下面的讨论中只列出全局状态中的节点1到节点n的状态.收敛时间是从初始状态到一个稳定状态经过的轮数,在稳定状态下,每个节点的状态为(-).0SsSis定理2:对于一个大小为n+1的全连接图,对于SPVP2来说,在源变化Tdown事件下收敛时间是1.证明:在源变化情况下,根据SPVP2的选路进程,当每个AS节点处理撤回报文(这里,i.e.,[X],为简单起见被省略掉),),(\'iimsprocessiwiX:→)(Xorigins它会把所有的路由标记为非法,即标记当前到达前缀X的最佳和所有备份路由为非法,这样就不会有任何错误的路由被选为最佳路由,然后向邻居发送撤回报文,wji:→)(ineighborsj∈.这样经过1轮之后,全连接图达到一个稳定的状态:,),(),......,11MM,:wiwii:1→+(),((=1,...,iw→,....,,),1(1211MMMX1n),...,21(:iXi),....,1(),XX),12(:Xi→1S2s1s1M2M),......,1121nMS:i→win:,...,→,其中有n-1个撤回报文消息:.很显然,在之后的1iM11n轮中,这些撤回消息会被处理,但是状态会一直保持(-)直到达到最终稳态.所以收敛时间是为常数1.#对于SPVP1,分析将会变得困难一些.在经过第一轮之后,下一个状态变成:1S)2((1n.而将由如下报文:1iM),1)1((:121Xii→→)1(:)...,1)1((:1XninXiii→+→+.表2-1ofSPVP1…is…ns(2X)(1X)(1X)(1X)…iM…nM2->1:(21X)3->1:(31X)4->1:(41X)……n->1:(n1X)1->2:(12X)3->2:(31X)4->2:(41X)……n->2:(n1X)…1->i:(12X)…i-1->i:((i-1)1X)i+1->i:((i+1)1X)…n->i:(n1X)…1->n:(12X)2->n:(21X)3->n:(31X)…n-1->n:((n-1)1X)这样状态具有如下的形式,见表2-1所示,前两行表示每个节点对应的状态,后两行表示每个节点的消息队列(这里的讨论没有采用路由环检测).1S在之后的转换序列中,状态的转化强烈的依赖每个节点在每轮中如何选择处理报文.根据不同的选择规则,我们可以得到针对SPVP1在源变化情况下收敛时间的上限和下限.定理3:对于一个大小为n+1的全连接图G,SPVP1在源撤回Tdown事件下的收敛时间下限是.)(2nO证明:在如下情况下发生最短的转换序列:在每一轮中,对于图中的每个节点,如果存在一个消息,它总是可以不改变该节点的状态,那么它总是比会改变该节点状态的消息要好,所以如果节点选择这样的消息将会保证在状态转移过程中产生的消息数目变少,同时减少到达稳态的轮数.根据这个规则,在状态,每个节点首先选择处理从邻居节点发送过来的消息,该邻居节点不是它"最佳"路由的路径中的第一个AS;而从它的\'最佳\'路由的路径中的第一个AS发送过来的消息则要最后处理.例如,在这样,S状态下,节点AS1的"最佳"路由为[2X],而它的备份路由为[3X],[4X],…,[NX],那么AS1优先处理不是从AS2发送过来的消息[21X],因为如果选择的话,会导致AS1重新选择新的路由;相反它会优先选择别的AS发送过来的消息,例如从AS3发送过来的消息3—〉1:[31X],由于这个备份路由彼此可AS1的"最佳"路由[2X]评价要低,所以AS1不会改变它的状态.对于其他节点类似,这样,从状态经过最初的n轮,只有备份路由一直在改变,而每个节点的状态保持不变,就不会有新的消息发送出去.在处理完最后一个消息后,每个节点将改变"最佳"路由,路径长度变成3,因为这个时候所有的路径长度都变成3.但是这个时候节点1的状态变成(-),它将发送撤回报文,因为它所有的备份路由在状态开始,经过轮之后都成为非法路径.在开始第轮的时候,全局状态将如表2-2中所示:1S211Sis0SnSnthn1+1s2s…is…ns(-)(31X)(12X)(12X)1M2M…iM…nM2->1:(231X)3->1:(312X)4->1:(412X)……n->1:(n12X)1->2:w3->2:(312X)4->2:(412X)……n->2:(n12X)…1->i:w…i-1->i:((i-1)12X)i+1->i:((i+1)12X)…n->i:(n12X)…1->n:w2->n:(231X)3->n:(312X)…n-1->n:((n-1)12X)表2-2ofSPVP1nS根据同样的规则和类似的过程,在从状态经历nS1n轮之后,每个节点将改变它的\'最佳\'路由长度为4,因为所有的备份路由长度变成4.但是节点1仍然保持(-)状态,并且不发送报文,因为它处理的所有报文都通告非法路由,同样节点2的状态变成(-),并且发送撤回报文.继续上述过程,在从初始状态起,经过∑+=+nnnin2)1()1(is=i1轮之后,所有的节点状态都会变成(-),之后的消息将或者是通告长度为n的路由消息或者是撤回消息,但是他们将不会改变任何节点的状态.因此,这样在轮之后,全局状态达到一个稳态,所以对于SPVP1的最短收敛时间是.#2/)1(+nn)(2nO定理4:对于大小为n+1的全连接图G,在源变化Tdown事件情况下,SPVP1的收敛时间上界是.))!1((nO证明:实际上,对于最长的转换序列应该发生在如下的情况:在每一轮中,对于图中的每个节点i,它总是优先选择那些消息,这些消息的特点是将总会改变它的\'最佳\'路由(状态)s,并总是最后选择不改变它的状态的消息.这样的规则刚好和前面的规则相反,显然这样会在转换序列中产生更多的消息,因此会增加到达稳定状态的转换轮数.i根据上述规则,在状态情况下,每个节点将优先处理它\'最佳\'路由路径中的第一个邻居节点发送过来的报文.这样每个节点总是把路由转向具有稍高一点的AS号的邻居路由,例如:1S==otherwiseXiXsi),2(2,1),3(.而且每个节点将会发送如下的报文:→=→=otherwiseXikiiXikiomki),2(:2,1),3(:.继续如上的过程,每个节点根据表4-2中从上到下的顺序处理等待消息队列里的消息,从初始状态经过轮状态转换后,它将经历如下的状态序列iSiM0n(1X)->(2X)->…->((i-1)X)->((i+1)X)->…->(nX).并且每个节点将会遍历从邻居节点发送过来的路由长度为3的路径.每个节点都有可能遍历所有长度为3的路由.iM类似的过程,每个节点将持续遍历所有长度为4的路径,一直到长度为n,直至所有备份路由为非法.整个过程将经历轮进入稳定状态.因此SPVP1最坏情况下的收敛时间是∑∏==111)(niijjn))!1((nO.这个结论与Labovitz在[4]得到的关于n个AS节点的全连接图分析的结论一致.#2.4.2SPVP2的任意图的收敛特性对于非全连接图,关于SPVP1的收敛特性很难分析,但是可以得到SPVP2的一些确切的特性结果.定理5:对于任意的运行SPVP2的AS图,在源变化Tdown事件情况下,节点的收敛时间是ip,其中p是从节点到源变化AS的最短路径,系统的收敛时间正比于lp,其中是最长的路径,实际上是以origin以为根的AS图的最短生成树深度.lp)(Xs证明:根据SPVP2的定义,从源变化AS发出的撤回消息将会经过p轮到达节点.这个可以通过对节点到达目的地的最短路径长度进行归纳得到.ii很显然,最接近源变化AS的节点,例如经过第一轮转换之后进入稳定状态.我们假设对于距离为p=m的节点结论成立.对于距离为p=m+1的任意节点,它一定与距离为ip=m的节点相邻.根据假设,节点在m轮之后达到稳定状态,并且发送撤回消息给节点.这样,在经过m+1轮之后,节点也将会处理撤回报文,并且进入稳定状态(-).这意味着对于任意具有距离jijip=m+1地节点结论成立.#上述分析和结论是基于SPVP模型中定义的\'轮\'得到的,而实际的BGP中,度量参数有明显不同,并且不同的AS会有不同的报文传播和处理时间,不在遵循论的概念.在定理6中将给出消耗的总报文数,这样的效果是更加直观,同时可以通过模拟工作来验证.首先来定义一个新的概念:KeyConnection,-以源RCO为根的AS图的最短生成树的每条边都是KeyConnection.定理6:对于任意的AS图,V和E分别代表图中的节点数和边数目,则对于源变化Tdown事件,SPVP2最终收敛需要消耗的所有消息数目是VE2-1,而系统收敛的时间位于V和VE2之间.注意,SPVP2最终收敛是指到达最终稳态,而系统收敛时刻是指到达的最早稳定状态,但是此刻系统中还可能有消息报文没有处理.证明:显然,除了,每个AS只有一个向上的KeyConnection,如果撤回消息沿着keyconnection传播,将能够达到最快的系统收敛,并且所用的消息数目只有)(Xorigins1V个.另外,根据命题1,每个AS在接收到撤回消息之后将马上收敛;与SPVP1一致,对于每个KeyConnection,撤回消息只是单方向传播,而对于非KeyConnection,报文将双向传播,因为BGP会话两端的AS都要向对方发送撤回消息.所以,很自然,系统最终稳定的时候,将总共消耗VEVE=2)1(2(O+1个撤回消息,这是系统收敛的上界时间.#plp2.5小结本章针对BGP慢收敛问题提出了一个新的解决机制RouteChangeOrigin,通过简单路径向量模型的分析,得到如下的结论:1.对于源变化产生的Tdown事件,SPVP2系统的节点在收到撤回报文的时候就会收敛,除了向邻居节点发送撤回报文外不回发送其它任何错误的通告报文;2.对于一个大小为n+1的全连接图,对于SPVP2来说,在源变化Tdown事件下收敛时间是13.对于一个大小为n+1的全连接图G,SPVP1在源撤回Tdown事件下的收敛时间下限是;)2n4.对于大小为n+1的全连接图G,在源变化Tdown事件情况下,SPVP1的收敛时间上界是;))!1((nO5.对于任意的运行SPVP2的AS图,在源变化Tdown事件情况下,节点的收敛时间是i,其中p是从节点到源变化AS的最短路径,系统的收敛时间正比于,其中是最长的路径,实际上是以以为根的AS图的最短生成树深度;lp)(Xorigins6.对于任意的AS图,V和E分别代表图中的节点数和边数目,则对于源变化Tdown事件,SPVP2最终收敛需要消耗的所有消息数目是VE2-1,而系统收敛的时间位于V和VE2之间.上述结果明显的显示出,在源变化情况下,RCO机制表现出了很好的性能.-34-第三章RCO机制性能验证与比较根据前一章的分析,我们分别对SPVP1和SPVP2进行模拟测试,以检验改进协议的性能.下面分别介绍一些相关的模拟方法和工具,之后在详细的说明模拟的结果,并给出相应的讨论.3.1模拟验证工具及参数下面主要就以下几个方面进行简单的叙述,包括模拟工具,模拟的时间模型,拓扑模型及性能度量参数等方面进行讨论.3.1.1模拟工具作为模拟工具,采用ScalableSimulationFramework(SSFNet)[21]来模拟.SSFNet是近年来实现的一个新的模拟工具,它是基于离散事件的模拟方法,采用面向对象的框架,核心部分包括事件,实体,输入输出通道以及进程五个部分,这些类面向进程,对于用户隐含了底层的内部模拟实现细节,诸如进程,线程,时间队列,及同步等机制,向模拟用户提供易于扩展的接口,很容易根据实际需要在此工具中增加新的协议或网络单元等模块,底层的机制相当于一个黑盒子.SSFnet的最大优点是提供可扩展性,可以支持多达100,000个节点网络规模,另外,它可以支持并行计算,加快模拟速度.在SSFnet中原本内置了BGP协议,该BGP依据RFC实现,其所附带的验证程序表明,运行结果与实际的BGP运行机制相同,通过对器相关模块的修改,实现了SPVP1和SPVP2以进行模拟仿真.SSFnet中,一般的方法是根据一个拓扑,生成相应的配置文件,该配置文件描述了系统的拓扑,同时指定系统拓扑中每个节点所代表的实体类型(如AS域,路由器,主机,等等),以及这相应的节点实现的协议,如代表BGP路由器的节点需要实现IP,TCP,BGP协议等等的相关协议.由于我们只对大规模的BGP系统进行模拟来验证收敛特性,因而只在节点上实现了IP,TCP和BGP协议及相关的工具中的其他组件,而不考虑域内的路由协议.3.1.2时间模型:协议由于网络自身的复杂性,很难对网络给出一个确切的时间模型描述或模拟.在对BGP进行模拟时,为更好的模拟实际的网络,工作中采用RFC1771中建议的定时器数值,并考虑抖动因素;另一方面,工作主要是在稳定网络拓扑的基础上讨论拓扑变化产生的影响,同时为减少模拟的负载,加快模拟,对KEEPALIVE(保活定时器)设置为0,这意味着所有的AS节点之间的会话不再需要周期的发送KEEPALIVE报文.除了协议自身的时间机制,还有其他的诸多时间因素,如链路延迟,队列时间,CPU处理时间等因素.为了考虑随机因素,同时简化模型,对于所有的链路,延迟均设置为一个常数值;而其他的所有随机因素都归一到CPU时间上,而这些因素可能有很多复杂的问题,目前还没有一个很确切的时间概念,因而将这些因素综合到一起,设置CPU处理时间均匀分布在0.1到1.0秒之间,另一方面,由于AS之间的规模存在差异,大的AS内部可能存在多个IBGP路由器,这样的AS相应的内部收敛时间可能要长一点,所以在对消息处理的时候,对更大规模的AS,适当的增加了它的CPU处理时间,但是幅度增长缓慢.以上的时间模型只是一种近似,还需要对实际的网络进行更多的研究.3.1.3拓扑模型这里主要采用两种拓扑,一个是全连接图,而另一个是BRITE[22]拓扑生成工具生成的拓扑.全连接图的直径是1,很容易说明源变化而产生的慢收敛问题,可以以一个节点作为网络前缀X的接入AS,察看其他AS节点的收敛行为.另一个是由BRITE拓扑生成工具产生的拓扑.目前主要的拓扑生成工具有GT-ITM[23],Inet[24],andBRITE等.这些工具在基本方法上有区别,GT-ITM主要关心Internet的层次特性,BRITE和Inet主要关心在连接特性方面更相似于现在的Internet.BRITE,采用powerlaw[25]生成拓扑,可以适用于更大规模的拓扑,并且适合于这种拓扑具有AS级别的连接性,如度相关的分布等.BRITE具有很强的扩展性,和灵活性,目前来说能够满足模拟的需要.为考虑生成拓扑的规模,采用BRITE生成70,100,150,200四个规模的AS级BGP系统,分析显示,每个拓扑的直径约在5到6左右.每个AS平均具有两个链路,因而节点数与链路数之比是1:2.每个节点最小出度为2(实际上由于只考虑AS之间的连接性问题,不需要考虑StubAS).最大的出度为30左右.可以粗略的认为这样生成的网络是实际网络的一个子图,能够大致的体现网络的连接性问题.3.1.4度量参数对于SPVP1和SPVP2,在模拟中,主要就以下几个参数对两个协议在源变化情况下的性能进行评价.由于源变化和会话变化的效果有差别,因而对两种情况采用略有不同的参数,对于会话情况的讨论嫌简单介绍,在后一节再详细说出评价参数的原因和使用的差别.对于源变化情况:采用系统收敛的时间和收敛的消息数目作为评价参数;对于链路变化源情况:系统收敛的消息数目;另外,由于系统的收敛是一个过程,无法简单的用单一的收敛时间来评价新协议的有效性,而系统的每个AS由于MRAI的原因,每个AS对会在30秒的整数倍附近收敛,因而,我们对多次测量,对每次测量得到的多数AS分布的时间分布参数;同时以某一轮测试为例,给出系统稳定过程中,每个AS收敛的时间分布;与原BGP协议不同的是,改进的BGP协议,每个路由器在收到新的一条路径后,它将确切的得到一条正确的路由,尽管该路由不一定是最有的路由,因而我们还要给出一个典型的测试中,系统的每个节点得到可用路由的时间分布.3.2分类模拟及实验结果3.2.1源变化情况的模拟:随机的选择拓扑中的一些节点,作为网络前缀X的接入AS,重复试验表明,各个节点都具有很强的相似性,因而对两种拓扑的测试,只是从中选出具有代表性的一个节点,来进行说明测试结果.3.2.1.110节点全连接图的模拟结果图中3-1显示的是以10个节点的全连接图为基础,进行的1000次循环试验,每次让AS0模拟一次源变化事件,记录收敛时间和报文数目.由于路由系统是一个异步系统,每个个体之间差异很大,所以报文在链路上的传播,在路由器的队列中等待以及处理的时间,都不尽相同,会有很大的差异,因而多次实验得到的是一个分布曲线.在图3-1(a),(b)中,横轴表示测验的次数,最大值是1000,纵轴分别是系统收敛消耗的报文数量和收敛时间(单位为秒).对于每一次循环,由于每次的数量都不同,为了直观的显示,根据他们的大小重新排序,所以下面的数据不是与每次实际测验的次序一致的.另外把两个协议的测试结果放在了同一张图中,为便于比较,分别在图中永不同的颜色和标尺来画出曲线.图3-1源变化的报文分布和收敛时间分布曲线(10节点全连接图,SPVP1和SPVP2)10节点的全连接图在拓扑上很简单,模拟结果显示在对于SPVP1的大多数测试中,系统一般要200多秒才收敛.对于全连接图,由于AS1和其他9个节点直接相连,在稳定情况下,每个AS(除了AS1)都有8条备份路由,对于SPVP1,在收到AS1的撤回消息之后,多数的测试显示,每个AS都将选择其他的备份路由,从图中以及表3-1中可以看出,这样的情况下,系统将总体发送200到500左右的消息才能够收敛;如图3-1(b)显示的,收敛时间多数分布在30秒,60秒,90秒或者更长时间,明显的是30秒的倍数关系,每个台阶上的测试次数都占很大的比例.这实际上与BGP协议中的30秒MRAI有关系.在观测的1000次测试中,系统在源变化事件已经发生之后,出现的最长的错误路径长度是8,而理论上可以出现的最长错误路径是9.这充分说明,对于SPVP1大部分时间中,系统各个成员选择和通告的路径都是非法的和无效的,而且这些需要很长时间才能够消除,与实际的观测相一致[3].对于SPVP2,在源变化事件发生后,系统总共确切需要81个报文就达到最终的稳定,这81个报文包括如下两部分:网络前缀X的接入AS0向它的9个邻居AS发送撤回报文,之后是9个AS分别向除了AS0之外的其他8个AS发送撤回报文(他们不向AS0发送撤回报文,因为他们的路由都是从AS0得到的),这样共计:9+89=81个报文.实际上,这81个消息只是遵从BGP协议的发送撤回机制,最少的情况下,该系统将只用9个消息即可以稳定.另一方面,SPVP2的收敛时间要小于1秒钟,实际上,这个时间主要是报文的链路传输和队列以及CPU处理时间.在收敛过程中,没有任何无效错误路径被选择.表3-1中很清楚的列出这些数字.所以从10个节点的拓扑测试中,可以看到SPVP2在性能上要优于SPVP1.表3-110节点源变化性能模拟结果总报文数收敛时间(秒)出现的最长路径SPVP1197~501~4.0/34.0/65.0/95.0/120.08SPVP281<1.0无3.2.1.2BRITE生成的拓扑模拟结果显然全连接图是最简单的拓扑,尽管它很容易说明效果,但是并不能很好的反应网络的真实状况,为了更好的模拟实际网络,采用了BRITE生成4个大小不同的拓扑,在这些拓扑的基础上,进行了测量.图3-2(a),(b)中分别给出了SPVP1系统收敛时间的分布状况,同样,横轴是循环的次数,纵轴是系统收敛时间(单位是秒)和报文数量.所有的数据由小到大的进行了排列,这样得到的是一个累积分布.图3-2(a)中显示的是SPVP1的四个大小不同的系统收敛时间,可以看到,对于70个点的系统,在路由撤回之后,大概要花100至200秒才能收敛,随着系统规模的增长,收敛时间也在迅速的增长,当达到200个点时候,系统大该要在800秒到1150秒之间收敛.图3-2SPVP1的源变化收敛特性(BRITE生成拓扑)图3-2(b)中显示的是SPVP1的系统收敛报文的分布曲线.可以看到,对于大小为70个节点的系统,大部分测试显示系统收敛消耗的报文数目在1300到4000报文之间;而对于节点是100的系统,则系统需要约3500—5000报文;当系统规模增长到200个时,系统消耗的报文数目已经达到2.0—2.6104个报文.很显然,系统越大,在收敛过程中可能出现的无效路由也越多,收敛时间和收敛报文的消耗就会迅速增加.而实际上,这远远超过了系统所需要的报文数目.现在来看看SPVP2的模拟结果.图3-3(a),(b)显示的是SPVP2系统收敛时间和报文数目分布情况.横轴和纵轴意义同前.可以看出,由于没有错误路由的干扰,SPVP2很快的收敛.尽管测试了1000次,这4个系统都在5秒至9秒之间收敛,分布都很类似(时间的差别可能跟系统的直径有关系).而系统收敛时消耗的报文数量,分别集中在小的范围内,是在收敛的上限和下限之间.在系统最终稳定的时候,最终消耗的报文数是一个确切的数目,4个规模的系统在系统最终稳定的时候,分别消耗报文205,295,445,595个,与前面第二章的定理6是一致的.表3-2中给出了收敛报文的分布范围以及最终需要的报文数目.与SPVP1比较,无论时间还是报文数量都提高了两个数量级.图3-3SPV2的源变化收敛特性(BRITE生成拓扑)表3-2:SPVP2理论和模拟报文上下限(BRITE生成拓扑)Labovitz在[3][4]中提到,在BGP协议Tup事件情况(故障恢复,路由可用)下,收敛性能要比Tdown好很多.这里也把SPVP2的Tup和Tdown做一个比较.在图3-4中显示的是Tup的收敛时间和报文数量分布,可以看到,Tup收敛时间主要分布在几个30秒倍数的台阶上,并且随着拓扑大小增加而变长,例如,对于70个节点的拓扑,45%的测试在30秒左右收敛,另外50%多的测试在60秒左SystemSize70100150200TotalEdges137197297397Theo.Updates205295445595Exp.Updates205295445595右收敛;而对于其他的3个拓扑,则主要集中在60秒收敛.同样,对于4个拓扑,大部分的测试需要300,600,900,1200左右的报文才能收敛.同前面的分析可以看到,对于改进的协议,即使是与Tup对比较,其性能也是要好很多.这里要注意的是,RCO机制不用在在路由恢复的时候,不采用RCO机制.3.2.2会话变化情况:对于会话变化情形,由于各个规模拓扑的相似性,模拟中以200个节点的拓扑为例来进行模拟,该拓扑中共计有397个链路,拓扑中不存在StubAS,即没有只有一个邻居的AS.图3-4SPVP2的源变化Tdown和Tup收敛特性比较(BRITE生成拓扑)时间参数的选择参照了前面源变化模拟设置.模拟中研究这样的情形,对于网络前缀X,它属于AS0,而AS0有两个邻居AS1和AS2,如图2-1中所示.显然如果AS0与AS1的会话或与AS2的会话中断,对整个系统的影响最大,因而模拟的焦点集中在这种链路上,即AS0与它的下一个AS邻居之间的会话变化情况.一般来说,在稳定情况下,整个系统大部分AS有两类可选的路径:分别经过AS2-AS0,AS1-AS0.但是很多AS管理者出于流量方面的考虑,人为的让一条链路做地址前缀的首选路径,与该前缀相关流量都通过这个链路出去或回来.这样为了抑制另一条备份链路,会人为地把备份链路通告的路径加长,这样其他AS不会选择加长的路径.例如,正常情况下,AS0向AS1和AS2发送正常的路由信息为(0);如果AS0希望所有的流量经过AS1到达AS0,而不愿意通过AS2达到,可以把发送给AS2的路由加长为(00)或者(000),甚至更长.这是普遍采用的技术,这里也对这种由策略产生的情况进行讨论,为简单起见分别称之为P1,P2,P3,对应发送给AS2的路由为(0),(00),(000).预期在采用策略情况下,更能够体现RCO的优点.在SPVP2中,有些节点接收到会话变化源origin,可能导致路由器没有备份路由选择,这种情况下,应该很快的向他的邻居发送撤回消息(并携带该会话变化源),这样在某些测试中显示的一个结果是:系统收敛时,虽然在很多时候比原协议要好,但是会出现总共发送的报文数量变多的现象.分析可能的原因是由于撤回消息发送太快,当路由器接收到撤回报文的时候,可能导致没有有效的备份路由,于是迅速的传播撤回报文,但是在发送万撤回报文之后,又可能很快的接到新的有效路由,尽管可能不是最佳路径,但是它会选择这个路由然后再向邻居通告,这样一直到得到一个最佳路由为止,节点可能要变化好多次.这样系统收敛要消耗的报文就有可能变多.由于会话变化情况比较复杂,这里只给出了一些模拟的结果.针对这种情况,考虑到系统中很可能有正确的路由,为了试图减慢撤回消息的发送,--在AS接收到撤回消息后,让他等待一个很短的时间,这样在单个会话中断的情况下可能有好一些的效果,因为,在等待的时间里,新的路径可能会传递过来,这样原来的撤回消息就可以不用发送.)(Xl)(Xoriginl基于这个思想,称这个新改进的协议为W-SPVP2,让撤回消息等待适当的时间,测试的结果是1.8秒可以得到一个比较好的结果.这里把SPVP1,SPVP2和W-SPVP2的模拟结果分别列出,为了便于参考,在某些图中也列出了相应的会话恢复的收敛情况.由于会话变化对收敛的影响要远小于源变化的影响,一般每次测试的结果不会有特别大的起伏,因而测试进行了100次,为了便于清楚的显示数据曲线,从中选出连续的40次测试得到的曲线.综合了以上的考虑,模拟工作是如下进行的:随机的选择一个节点作为网络前缀X的接入AS.在模拟的开始,系统正常的运行达到一个稳定状态,每个节点都有一个到达网络前缀X的最佳路由.这时让首选路径的会话中断,然后AS1将向它的其他邻居发送撤回报文,然后记录收敛过程中的相关测量参数.B.评估参数为了更好的综合评估SPVP1和SPVP2的性能,采用以下的参数:1)系统收敛的更新报文消耗(包括撤回和通告报文);2)节点收敛时间在主要时间段的分布:采用这个参数是由于MRAI的影响,大部分节点会在30秒的台阶上收敛,就同源变化模拟中显示的一样,多分布在30秒,60秒,等等,这里把时间表示成[030],[3060]等,分别表示在30秒内收敛,在30和60秒之间收敛.我们列出在每轮测试中有多少节点会在主要的时间片断中收敛.3)节点收敛时间的分布:以其中的一轮测试为例,详细的看一下在一轮典型的测试中,每个节点具体在什么时候收敛,4)第一个可用有效路由获得的时间分布:根据定理1,每个节点在它达到稳定之前,都可能得到一个有效的路由,尽管它不是最优的,所以画出了在一个典型的测试中,每个节点得到第一个可用路由的时间分布.这里要注意的是,第一个可用的有效路由是指这样的路由,节点在得到该路由之后,无论是否进行选路进程,不会在选择错误的路由作为最佳路由.之所以采用2,3,4中描述的评估参数,是因为对于会话变化情形,评价它的性能不像源变化那么简单,如果单纯采用系统最终收敛时间的分布来做评判,则显得不公平.所以用这些参数能够更客观和综合的评价性能.C.模拟结果:根据如上的参数,给出连续的40轮的模拟结果.A.报文的消耗图3-5(a),(b),(c)分别显示了SPVP1,SPVP2以及W-SPVP2的在P1,P2和P3情况下的报文消耗数量(含撤回和通告)分布.为了便于比较,同样列出了会话恢复的数据.从图中我们可以得到如下的观察.1):当备份路径的长度增加,相应的SPVP1,SPVP2和W-SPVP2消耗的报文数目增加.显然,如果备份路径的长度增加,导致各个节点在选择到正确的路径时间变长,因为选择错误路由的可能性增加了.而如果备份路径无限长,就同源变化相同了.2):一般来讲,SPVP2在P2和P3情况下,同SPVP1相比消耗的报文会减少约15%到20%.但是P1情况,就不尽相同,可能会好,也可能会不好.稍候会做讨论.3):W-SPVP2对于三幅图来说,相比SPVP1都会减少20%报文.这说明对于模拟的拓扑来说,让撤回报文等待一个合适的时间有可能减少一定数量的报文.另外,P2同P1相比,报文数量迅速递减,这是由于在P1中,200点中有76%(153个节点)采用首选路径做为它的最佳路由,而P2中有95%(190个)节点采用首选路径最为它的最佳路由.同样P3的情况更加明显.这有可能说明当系统中采用首选路径作为最佳路径的比例越大,SPVP2的效果越好.B.节点在主要时间片断的分布图3-6显示了在时间片断0-30秒,30-60秒等的分布情况.横轴是测试的轮次,纵轴是相应在该时间段中有多少百分比的节点收敛.例如,P1显示在图3-6(a-1)(a-2)中,对于SPVP2和W-SPVP2在40次循环中,大约70%的AS会在几秒内收敛,大约10%的节点会在30至60秒内收敛;然而对于SPVP1大约50%的节点会在30秒收敛,另外的接近50%的节点在30至60秒收敛.P2,P3分别对应图3-6(b),(c),显然具有同样的效果.所以可以得到下面的一个观察结果:4)同SPVP1相比,SPVP2和W-SPVP2中的AS会早一些收敛.C.AS在一轮测试中的收敛时间分布拿出一个典型的测试作为例子,看看在一轮测试中AS收敛时间的分布状况.图3-7(a),(b),(c)对应给出了P1,P2和P3分布情况,横轴是时间,纵轴是在相应时间收敛的AS数目百分比.同样可以看到,AS多分布在30秒的台阶上收敛,而且分布特征同观察4类似,这也从另一个侧面证实了观察4的结论.D.最早可用路由分布时间图3-8(a),(b),(c)中分别显示了P1,P2,P3在一轮测试中,AS得到一个可用路由的最早时间分布.可以看到,无论是P1,P2,P3,对于SPVP2和W-SPVP2,几乎所有的AS在几秒之内就可以得到一个可用且有效的的路由,尽管这条路由可能不是最佳路由,但是它保证了AS可以正确的转发IP报文.而对于SPVP1,大部分节点总是在接近该点收敛的时候才能得到一个最早的可用路由.注意这里的最早可用路由是指那些得到正确路由后,不会在之后的时间里选择错误的路由.图3-5SPVP1,SPVP2,W-SPVP2会话变化Tdown和Tup分布图3-6会话变化过程中主要时间片断的收敛AS分布图3-7一轮会话变化过程节点收敛时间分布图3-8一轮会话变化过程节点最早可用路由时间分布3.3小结通过以上的分析和模拟工作,对于改进的协议的性能有了一个初步的认识.不难看出,从上述模拟结果,可以大致得到一下几点结论:如果一个AS内部的网络前缀X完全不可达,或者一个StubAS完全不可达,则改进协议SPVP2将完全消除慢收敛问题,系统将在很快的时间内收敛,收敛时间只取决于链路延迟和CPU,队列等的延迟;系统消耗的Update报文数量将变成一个确切的数量,只和链路的数量有关.这种情况下,将大大的降低系统的无谓负载和不良影响.对于会话变化,在单点会话变化情况下(不是与StubAS相连的会话),通过改进协议一般情况下可以很好的指导路由器选路,不存在任何选择错误路径的可能,系统中的节点会在很短的时间内,得到一个可用的路由(尽管未必是最佳路由),多数情况下,收敛时间和报文数量会有改善,但是也有一些其他的例外,我们在下一章做简单的说明.以上的分析和模拟,可以看RCO机制在某种程度上可以加速BGP路由系统的收敛,是一种可能的解决的思路.第四章RCO机制的讨论前两章的工作只是对BGP协议慢收敛问题的一个初步的认识和改进的一些分析和模拟.第二章和第三章的讨论主要讨论了源变化和会话变话两种情况,实际的路由系统中可能还有其他很多种情况和问题,下面做一个简单的讨论.4.1RCO机制的讨论1.如果某一个AS的BGP路由器出现某种故障,导致其他AS无法与之通信,或者针对同一个网络前缀,在同一时间有多个会话中断,那么这相当于多个会话变化,系统应该允许多个不同的RCO同时存在.但是这种情况下,可能存在的一个问题是任一个AS都很难知道系统中准确的应该有几个RCO,所以在选路的时候仍有可能选择无效的路由,会降低RCO效果.一种方法是,每个AS在接收到一个RCO的时候,应该保存RCO一个合适的时间,以验证后来不会再选择错误的路径.但是,保存的时间不能过长,以防止影响路由恢复.另一种可能的方法是,可以建立一套机制让AS在接收到RCO的时候可以选择去相关的数据库查询相关还有哪些RCO,这样路由器可以把多个RCO合并到一个报文中.实际上,模拟显示,对于AS的路由器出现故障的情况下,它的效果和源变化情况类似,只是时间稍微延迟了一些,这是由于故障AS的其他邻居AS检测到故障的时间存在差别导致的,但这并不影响太多.其它复杂情况还需要深入的研究.2.RCO在具体的协议实现中,为了与原有协议兼容,可以作为一个路由信息中的一个TransitiveOptionalCommunity[26],这样,即使是原有的协议无法识别该特性,也可以同样的不处理,但是传递出去.3.策略的影响在BGP路由中很重要.如何处理策略,比较好的办法是将策略的变化转化成类似的拓扑变化的形式.例如如果AS3人为地用[2560]来替换原来的路由[460],则可以认为会话[32]不可用,这样就可以转化成策略类型的RCO.是不是所有的策略变化都可以转化成为拓扑类型的变化,还是一个值得探讨的问题.4.对于会话变化,在某些情况下,它表现得不是很好,在第三章的模拟中就可以看出来.在模拟工作中,曾经采用OregonInternetExchange[27]的路由表构建了一个500节点的拓扑,做了同样的模拟,结果显示,对于P1情况,好坏各半.但是P2,和P3的情况要好很多.具体的原因,除了前面推测的撤回报文传播过快外,它应该很强的依赖网络拓扑.同时如果采用等待的定时器,是不是必要,它会不会产生新的问题,如果可以作为一个可行的办法,那么如何选择最优的数值,这些问题目前还很难用理论来解释或回答,希望以后能够找到一个很好的分析,进一步的探讨它的原因,以完善RCO机制.5.RCO机制如果不采取措施的话,很可能存在安全问题,就是如何验证含有RCO的报文是正确的.目前AS之间的报文分发依靠AS之间信任协做来完成的,但是这种松散的协作不能保证一定是按全的.而且,一旦某个AS伪造了一个RCO,带来的后果会很麻烦,当某些AS错误或蓄意地通告含有非法的RCO报文时,如果没有相应的机制来检验RCO的合法性,BGP路由器有可能错误地过滤掉正确的路由表项,严重的情况下,会导致无法访问某些网络,为此需要针对RCO建立一个安全的机制.目前BGP为了协同认证一个网络前缀等信息,采用路由策略规范语言(RoutingPolicySpecificationLanguage,RPSL)[28]来定义了AS,route,prefix等路由信息的描述以及与之相关的认证等规定,这样就产生了InternetRoutingRegistry(IRR)分布式数据库系统[29],每个AS都应该向IRR提交它网络内部的网络前缀,路由信息等等的RPSL描述.IRR实际上是AS及其路由信息的一个数据库系统,只有相它注册的路由信息才是合法的.这样,AS就可以接收和处理在IRR中合法注册的地址块,而对于没有注册的地址前缀,则作丢弃处理.这样可以在很大程度上防止地址前缀的错误通告.对于RCO,为了增强它的可靠性,也可以采用相似的方法,采用RPSL语言建立一个RCO的验证系统:如果相应的产生RCO,无论是产生源变化或者会话变化的AS发送含有RCO的报文的同时,主动向该验证系统注册RCO;而其他AS在接收到含有RCO的报文时候,它可以根据自己的策略,选择相信该RCO有效性,或者到数据库验证的方式来确认该RCO的有效性,然后再进行路由的过滤.这种颁发的好处是可以利用现有的机制来增强RCO的安全.上面的分析是基于简单路径向量模型进行的,其中有很多的假设,而实际的系统要复杂得多,如果要真正的实现这些机制,就必须考虑内部BGP关系,两个AS之间多个BGP会话,考虑更多的策略问题,以及对会话变化情况,以及更接近实际的大规模网络的性能的的深入分析.5.1结论本章将对论文工作做个简单的总结.5.1.1论文工作总结论文的工作期间,主要针对BGP协议的慢收敛问题,进行了深入的分析,为加速协议收敛,提出了一个新的收敛机制--路由变化源(RouteChangeOrigin,RCO).同时,为了分析RCO机制的性能,通过建立两个简单路径向量协议模型(SimplePathVectorProtocol,SPVP),从理论上得到RCO在源变化情况下的收敛特性,同原协议对比有很大的提高;同时为了验证理论的分析,利用模拟工具,增加BGP的相关模块,实现了对原有协议和改进协议的收敛模拟,模拟数据验证了理论分析结果.5.1.2论文的创新点本文主要有如下的创新点:1.针对BGP协议的慢收敛问题进行了深入的分析,指出了慢收敛的原因;2.提出了RouteChangeOrigin的机制来改进慢收敛;3.建立了简单路径向量协议模型SPVP,用来抽象原有路径向量协议和改进协议;4.通过SPVP模型,对RCO机制进行了理论的分析,得到了在源变化情况下的收敛特性,给出了在源变化情况下,原BGP协议和改进协议的收敛时间上界和下界;5.针对会话变化中出现的情况,提出了减缓撤回消息的机制,同时提出了一个增强RCO安全的认证机制.5.2展望尽管本文的工作在一定程度上说明RCO的有效,但是它还是有一些问题既需要解决,如同前面的讨论,实际的网络要复杂许多,要真正解决慢收敛问题,还要做深入的研究和探讨,同时也要解决如下的问题:-47-第五章结论与展望1.在会话变化情况的深入分析,从理论上对他的行为给出更好地描述;2.从理论上认识策略对BGP协议的影响,理清策略和拓扑变化之间的关系;3.解决好RCO的安全问题;4.针对实际网络,构建更大规模的拓扑进行模拟,以期望更好的认识BGP收敛特性.总之,,RCO在一定程度上缓解了BGP的慢收敛问题,我们希望经过完善,能够成为一个合适的解决方案.',)