BGP收敛性及其对网络性能影响的定量分析.doc

第8期赵金晶等：BGP收敛性及其对网络性能影响的定量分析33BGP收敛性及其对网络性能影响的定量分析赵金晶，朱培栋，卢锡城（国防科学技术大学 计算机学院, 湖南 长沙 410073）摘 要：从Internet的结构特征入手，分析了BGP的收敛特性与域间路由系统的幂律特性与层次性之间的关系。根据域间路由系统的幂律特性以及AS间商业关系的层次性特点建立了三层幂律层次模型，剖析了不同层次上的不同收敛事件的收敛参数与网络结构本质的联系。在此基础上，提出了“Best Up”的收敛模式，取得了显著效果。关键词：域间路由；BGP；幂律；层次性中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)08-0024-10Quantitative analysis of BGP convergence and its influence on network performanceZHAO Jin-jing, ZHU Pei-dong, LU Xi-cheng (School of Computer, National University of Defense Technology, Changsha 410073, China)Abstract: The relation of BGP convergence and the characteristics of the inter-domain system was analyzed. The inter-domain routing system is classified into three hierarchiescore layer, transmit layer and stub layer based on the power law and commercial relations of autonomous systems. The relation of network topology and convergence parameters were presented of all sorts of convergence events in different layers. And a new proposal has been presented to improve BGP convergence based on the above analysis, called Best Up, which behaved better than normal convergence mode in the experiments.Key words: inter-domain routing; BGP; power-law; hierarchy 1 引言RFC38691中列出了IAB所关注的今后Internet研究和发展过程中需要特别关注的热点问题，其中指出当前运行的域间路由系统中，路由前缀在150 000 到200 000之间时，域间路由系统可能会因为算法的约束使得端到端的收敛时间变得不可接受，所以对BGP协议的收敛性问题的研究迫在眉睫。收稿日期：2006-04-18；修回日期：2007-07-04基金项目：国家重点基础研究发展计划(“973”计划)基金资助项目(2005CB321801)；国家高技术研究发展计划(“863”计划)基金资助项目(2006AA01Z213)；国家自然科学基金资助项目(60673169)Foundation Items: The National Basic Research Program of China(973 Program)(2005CB321801); The National High Technology Research and Development Program of China (863 Program)(2006AA01Z213); The National Natural Science Foundation of China(60673169)本文试图从Internet的本质特征入手来分析BGP的收敛问题。Internet是一个复杂系统，它是由大量自治系统（AS）组成的一个自组织网络，同时具有幂律特性、小世界特性、无尺度特性等基本特征。这些规律使得Internet能够在各种情况下保持稳定高效的运行，所以利用这些本质特征来指导Internet的运营与发展是非常有意义的工作。本文根据域间路由系统的幂律特性以及AS间商业关系的层次性特点建立了三层幂律层次模型，在此基础上对BGP的收敛过程进行建模，将收敛事件对网络的影响参数分为三类：收敛时间T，影响的AS范围Nc，对路径的影响因子，并从理论和实验两方面比较了它们在各个层次之间的取值范围。通过对BGP幂律-层次收敛模型的研究，认为Internet的幂律特性会对BGP的收敛性有很大的影响，尤其是其中的“hub”节点，在此基础上提出了加速BGP收敛时间的“Best Up”机制。本文剩余部分组织如下：第2节对域间路由系统的幂律性和层次特性进行了分析，通过有效的算法得到了域间路由系统的幂律层次模型；第3节在第2节的基础上建立了BGP的幂律层次收敛模型，并对发生在不同层次不同类型的10种收敛事件的各个收敛参数进行了分析，从中得到收敛时间、影响AS范围以及路径影响因子的最大最小值；第4节用SSFNet在真实的网络拓扑下对结论进行模拟验证；第5节在分析和实验的基础上研究了如何利用Internet的幂律特性来改进BGP的收敛性问题，提出了“Best Up”机制，取得了很好的效果；第6节是本文的结束语。2 Internet的幂律特性及其层次结构2.1 域间路由系统的幂律及层次性分析一些研究组通过对的Internet上的数据进行分析，生成了Internet的拓扑图。这些拓扑图可以用来分析网络的一些统计特性。Internet拓扑存在着幂律特征。目前，平均AS的互连度为56之间，但是有些AS的度达到数百乃至几千。图12为AS的连接关系图，可以清楚地看到，在Internet的中心有一个核，核的周围有很多由节点组成的长短不一的枝节连接在其上，平均节点度数随着节点到核的距离的增大而减小。这些核节点就是幂律网络中的Hub节点，它们彼此连接在一起，成为网络的核心。为了了解幂律特性对域间路由系统的影响，需要根据节点的转发能力对Internet上的节点进行分类。在此，借鉴了传统的网络层次模型Transit- Stub模型的思想，并考虑了Internet的幂律特性。Transit-Stub模型将AS域划分为Transit类和Stub两类，Transit节点彼此互连构成一个节点群，一个或多个Transit节点群构成拓扑图的核心，而Stub节点分布在Transit节点群四周与Transit节点相连，Transit节点具有路由转发功能，而Stub节点只能够接收和发送数据。为了突出Hub节点在网络中的重要作用，将Transit节点又分为两类：Hub节点和Middle节点。这样整个域间路由系统可以分为三层：核心层、转发层和边缘层，称为幂律层次模型。图1 域间路由系统结构2.2 幂律层次模型幂律层次模型的核心思想是利用域间路由系统的层次性与幂律特性之间的一致性来突出不同层次的节点在BGP收敛过程中的异同。模型的建立首先考虑域间路由系统的层次性，然后验证生成的层次模型是否具有幂律特性。如果两者是一致的，就说明层次模型本身也就是幂律层次模型。文献3中给出了Internet分层的一种形式化方法，文献4根据AS的商业关系中给出了Internet的五层结构，但这些模型都过于复杂，不利于根据层次性进行分析。为此，建立了一个Internet三层结构模型（核心层转发层边缘层），并给出各层次的有效推断算法。该Internet层次模型定义如下：1) 对于某节点集，若其中的所有节点都无Provider且它们之间形成一个全互连结构，则为核心层；2) 若某自治系统不为其他任何自治系统转发网络流量，则属于边缘层；3) 既不属于核心层又不属于边缘层的自治系统归为转发层。转发层又可以细分为很多子层，其基本思想是Customer位于其Provider所属的子层的下面，而自治系统之间的Peer关系不影响所属的层次；特别的，如果存在Sibling关系，则它们属于同一层次。3 BGP的幂律层次收敛模型基于域间路由的幂律特性和层次结构，本节提出了BGP幂律层次收敛模型PH_SPVP(power law - hierarchical simple path vector protocol ) ，它是建立在简单路径协议的基础上的，也就是说，源AS只会选择一条到目的AS的路径，并将它通告给自己的邻居，路径中不含环路，并且是无谷底（valley-free）的。路径是无谷底的，是指BGP路由的输出策略符合以下的规则：1) 输出到Provider：在与一个Provider交换路由信息时，一个AS可以输出自己的，其Customer的以及同胞的路由，但是不能输出从其他Provider或Peer学到的路由。2) 输出到Customer：在与一个Customer交换路由信息时，一个AS可以输出自己的，其Customer的以及同胞的路由，还可以输出从其Provider和Peer学到的路由。3) 输出到Peer：在与一个Peer交换路由信息时，一个AS可以输出自己的，其Customer的以及同胞的路由，但是不能输出从其他Provider或Peer学到的路由。总结起来，也就是说一条无谷底的AS路径是由零个或者多个Customer-Provider序列跟上一个或者零个对等对等边，再跟上多个或者零个Provider-Customer序列组成的。将网络定义为一个有向图G=（V，E），其中V=v1,vn，E=e1,em，e=(u,v), iff u会向v发送update报文。根据上一节中的分层规则，将G分为相应的三层：核心层C，边缘层S和转发层T。定义1 如果vj是vi的Provider，那么 vjPROVIDER(vi)，同理定义CUSTOMER(vi)，PEER(vi)。定义2 函数h(vi)表示节点vi所属的层次，1h(vi)3(1in) ，n为图2中的节点数。vi属于核心层C，iff vi属于边缘层S，iffvi属于转发层T，iff定义3 函数l(ej)表示边ej所属的层次，1 l (ej)6(1jm)，m为图中的边数。l(ej)=1, ej =(uk,um), iff ukC, 且umC。l(ej)=2, ej =(uk, um), iff ukC, 且umT。l(ej)=3, ej =(uk, um), iff ukC, 且umS。l(ej)=4, ej =(uk, um), iff ukT, 且umT。l(ej)=5, ej =(uk, um), iff ukT, 且umS。l(ej)=6, ej =(uk, um), iff ukS, 且umS。定义4 r= v1,vk是V中一条无谷底的简单路径，使得对于 ij，则vi vj，且有e=( vi, vj) E，路径r的长度为|r|=k。图2 点与边所属的层次定义5 影响的AS范围Nc：当网络中发生收敛事件X后，引起的从不收敛状态到收敛状态的节点的集合。定义6 影响路径因子：当网络中发生收敛事件X后，发生变化的路径占所有路径的百分比。通过可以对某一时间点上网络流量的变化进行预测。根据分析需要，将收敛事件X分为两大类，一类为边的变化Te，包括边的down和up；第二类为节点的变化Tn，包括节点的down和up。在这里假设各类延迟和处理时间的总和的上界为D，采用最短路径优先策略。下面对发生在各个层次上的不同收敛事件进行分析：1) 当收敛事件发生在e=1的情况下，即核心层C的内部。 收敛事件为Tn类型。分析：假设节点a失效，核心层C中除a外的所有节点以及a的Customer都会发现a的失效，它们会将路由表内所有需要经过a来转发的或者到达a的路由表项删除，并将发送withdrawal报文给自己的Customer。当Customer收到更新报文之后也会更新自己的路由表，并向自己的customer发送withdrawal报文，直到达到最底层需要通过a来转发报文的节点为止。收敛参数：受影响的节点集合Nc=(vi Customer(vi) Customer(Customer (vi) Customer(a)Customer(Customer (a)| viPeer(a) 且h(vi)=1)，即Nc为以所有除a外的核心层节点为根的树以及以a的Customer为根的树。Nc=(Ti Tj| Root(Ti)Peer(a)且Root(Tj)=Customer(a)。集合元素的最大数目为max|Nc|=N，即整个网络。设其中的最长路径为Rmax =(v1,vk | v1 Peer(a) 且h(v1)=1)，则 | Rmax |H ，H为网络的深度。则收敛时间T的上界为HD，下界为2D，出现在vi只有边缘层节点为Customer的情况下。影响路径因子可以用图论中的一个重要参数点的BC（betweenness centrality）值来表示。定义7 网络中点的BC定义为其中，为所有从s到t的最短路径数，(v)为所有从s经过点v到达t的最短路径数，节点的BC值可以用来衡量节点在网络中进行流量转发的重要性，是一个重要的网络属性参数。在幂律网络中，定义平均节点度k的BC值，其随度数k呈幂律变化，即，随着网络的不同而不同。所以这里影响路径因子为 ，因为节点a处于核心层，节点度数Degree(a)很大，核心层的平均度数约为800，所以10.1。对于节点的up事件，分析的过程同上，只是收敛的延迟时间D会有不同。以下的各种情况的up事件也是如此，为了节约篇幅不再赘述。 收敛事件为Te类型分析：假设节点a和节点b之间的链路发生断裂。首先a和b会将自己路由表中到达彼此的路径删除，重新选择一条可达的路径，例如acb和bca。随后a和b会将这条选出的最优路径向自己的Peer和Customer通告，如果它们的路径不会受到影响，那它就不需再向自己的Customer通告。由于核心层是全互连结构，所以a、b所有的Peer都不需要发送更新报文。而a、b则需要将自己路径的变化沿着无谷底的路径传播到所有的Customer节点。收敛参数：Nc=(abCustomer(a) Customer (Customer (a) Customer(b) Customer (Customer (b)，即Nc为以a和b为根的两棵树。Nc=(TaTb|Root(Ta)=a且Root(Tb)=b)。假设其中的最长路径为Rmax =( v1,vk | v1=a或者v1=b)，则 | Rmax |H ，H为网络的深度。则收敛时间T的上界为HD，下界为2D，出现在a或者b只有边缘层节点为Customer的情况下。收敛事件影响的路径为所有需要通过边ab到达目的节点的路径的集合，影响因子就是边ab的BC属性值：定义8 网络中边的BC值定义为其中，为所有从s到t的最短路径数，(e)为所有从s经过边e到达t的最短路径数。在层次性的幂律网络中，边的BC值与所属的层次有关。可以很直观的解释这种现象，假设节点i，j是边l的个顶点，如果l所属的层次比较低，那么经过l的最短路径只能是那些在i和j之下的节点，由于i和j的节点度比较小，所以它们下层的节点数会比较少，则通过l的最短路径数目会小。在网络总路径数一定的情况下，边l的BC值就会很小。所以这里影响路径因子为。其中边ab在网络的核心层，所以它们的影响因子会比较大，20.001 5。对于边的up事件，分析的过程与结果同上，下面也不再赘述。2) 当收敛事件发生在e=2的情况下，即核心层C与转发层T之间。分析：收敛事件只能为Te，假设节点节点a与b之间的链路发生断裂，a和b首先撤销自己的相应路由，重新计算最优路由。如果有最优路由，则通过update报文向外通告，如果没有新的最优路由，则发送withdrawal报文宣告a和b之间不可达。其中b会向自己的Customer发送，而a会向自己的Peer以及Customer发送通告消息，Peer(a)中的节点处理完自己的路由更新后会继续通告给下面的Customer。 收敛参数：Nc为所有以第一层节点为根的树以及以b为根的树的集合，Nc=( Ta |Root(Ta)=a)( Ti |Root(Ti)Peer(a)且h(Root(Ti)=1)( Tb |Root (Tb)=b)。最长路径Rmax =max(H(Ti)+1,H(Tb)H+1 ，H为网络的深度。则收敛时间T的上界为(H+1) D，下界为2D，出现在节点a的Peer节点以及节点b都只有边缘层节点为Customer的情况下。影响路径因子为。3) 当事件发生在e=3的情况下，即核心层C与边缘层S之间。分析：收敛事件只能为Te，假设节点a与b之间的链路发生断裂，a和b首先撤销自己的相应路由，重新计算最优路由。对于节点b不需要再向其他AS发送更新报文，而节点a会向其Peer节点以及其他的Customer节点发送更新消息，Peer(a)以及Customer(a)中的节点处理完自己的路由更新后也会向下面的Customer发送更新消息。 收敛参数：Nc=以a为根的树以Peer(a)为根的树，即以所有核心层节点为根的树，max|Nc|=N。核心层中的“hub”节点间是全互连的peer关系，所以|Rmax|=H，则收敛时间T的上界为HD，下界为2D，出现在节点a的Peer节点以及Customer节点都只有边缘层节点为Customer的情况下。影响路径因子4的范围为324) 当收敛事件发生在e=4的情况下，即发生在转发层T内部。 收敛事件为Tn类型。分析：假设节点a失效，那么它的Peer节点、Provider节点以及Customer节点都感知到这个变化，它们会将路由表内所有需要经过a来转发的或者到达a的路由表项删除，并将发送withdrawal报文给自己的Customer。Provider节点还会继续发送更新报文到自己的Peer和Provider，直到最顶层。当Customer收到更新报文之后也会更新自己的路由表，并向自己的Customer发送withdrawal报文，直到最底层需要通过a来转发报文的节点为止。收敛参数：Nc为由所有Customer(a)、Peer(a)、Provider(a)、Provider(Provider(a)以及Peer (Provider(a)、Peer(Provider(Provider(a)组成的树的集合，即最长路径Rmax=max(H(Ti)，H(Tj)，H(Tm)，H(Tn)2H-1，H为网络的深度。则收敛时间T的上界为(2H-1)D，下界为2D，只能出现在下面这种情况下：Provider(a)C，Customer(a)S并且Customer(Provider(a)S，Customer(Peer(a)S。影响路径因子5的范围为 收敛事件为Te类型。分两种情况讨论：Peer-Peer间的节点间不可达分析：假设节点a与b之间的链路发生断裂，a和b首先撤销自己的相应路由，重新计算最优路由。节点a以及节点b会向其Customer节点发送更新消息，Customer(a)和Customer(b)中的节点处理完自己的路由更新后也会向下发送更新消息。收敛参数：Nc=(TaTb|Root(Ta)=a, Root (Tb)=b)。最长路径| Rmax |=max(H(Ta),H(Tb)H1，即收敛时间T的上界为(H1) D，下界为2D，出现在Customer(a)和Customer(b)都属于S的情况下。影响路径因子6的范围为Provider-Customer间的节点不可达分析：假设节点a与b之间的链路发生断裂，a和b首先撤销自己的相应路由，重新计算最优路由。对于节点b再向它的Customer发送更新报文，而节点a会向其Peer节点、Provider节点以及其他的Customer节点发送更新消息，Peer(a)、Provider(a)中的节点以及Customer(a)中的节点处理完自己的路由更新后也会向下发送更新消息。而Provider(a)还会向自己的Provider和Peer继续发送更新消息，直到网络的最上层。 收敛参数：Nc为以b为根的树以及所有Customer(a)、Peer(a)、Provider(a)、Provider (Provider(a)以及Peer(Provider(a)、Peer(Provider (Provider(a)组成的树的集合。| Rmax|=max(H(Ti), H(Tj), H(Tm), H(Tn)2H2，即收敛时间T的上界为(2H2)D，下界为3D，只能出现在Provider(a)C，Customer(a)S，Customer(b)S并且Customer(Provider(a)S，Customer(Peer(a)S的情况下。影响路径因子。5) 当收敛事件发生在e=5的情况下，即发生在转发层T与边缘层S之间分析：收敛事件只能为Te，假设节点a与b之间的链路发生断裂，a和b首先撤销自己的相应路由，重新计算最优路由。对于节点b不需要再向其他AS发送更新报文，而节点a会向其Peer节点、Provider节点以及其他的Customer节点发送更新消息，Peer(a)、Provider(a)中的节点以及Customer(a)中的节点处理完自己的路由更新后也会向下发散更新消息，直到最底层。而Provider(a)还会向自己的Provider和Peer继续发散更新消息，直到网络的最上层。 收敛参数：受影响的节点集合Nc为以Customer(a)、Peer(a)、Provider(Provider(a)为根的树的集合。即| Rmax |=max(H(Ti),H(Tj), H(Tm), H(Tn)2H 1。即收敛时间T的上界为(2H1)D，下界为3D，只能出现在Provider(a)C，Customer(a)S并且Customer(Provider(a)S，Customer(Peer(a)S的情况下。影响路径因子8的范围为6) 当收敛事件发生在e=6的情况下，即发生在边缘层内部。 收敛事件为Tn类型。分析：假设节点a失效，那么它的对等节点会感知这种变化，但由于边缘层S中节点的连接信息是不向外部通告的，所以对等节点之需要更新自己的路由表项。收敛参数：Nc=peer(a)。收敛延迟T=D。影响路径因子。 收敛事件为Te类型。分析：假设节点a、b之间的链路发生断裂或者重新连接，a和b会首先更新自己的路由表，因为在边缘层S中边的连接信息是不向外部通告的，所以a和b不需要再向外发送更新报文。收敛参数：Nc=(Peer(a)。收敛延迟T=D。影响路径因子。通过上面对各种情况下收敛事件的分析，可以看出，收敛时间T与事件所发生的层次并无特别的关系，也就是说并不是层次越低，收敛时间越长。一般来讲，转发层的收敛时间比核心层更长。而事件影响的AS范围Nc是随着层次的增加而减少的，即在核心层，影响的范围会很大，而在边缘层，影响就微乎其微。然而这种关系可能并不太严格，特别是在层次结构复杂的转发层内部，Nc和节点与核心层的距离并没有严格的线性关系。事件对路径的影响因子，也可以理解为对网络流量的影响力，与层次有着比较严格的关系，因为节点的BC值与节点度成幂律关系，而AS的层次性也满足节点的幂律分布。而边的BC值从整体上看也与层次相关，越靠近核心，通过它的最短路径会越多，影响的流量也会越大。表1比较了Nc、T、这3个参数在哪种情况下会出现最大最小值。表1收敛参数最大最小值参数值层次事件类型Max(Nc)全网范围核心层CTnMin(Nc)连接边的2个节点边缘层STeMax(T)(2H1)D转发层T转发层T与边缘层S之间TnTeMin(T)D边缘层STn或TeMax()核心层CTnMin()边缘层STe4 模拟验证本节将通过实验对第3节分析得到的分层拓扑下各种收敛参数的结果进行模拟验证。4.1 实验设计实验采用SSFNet5模拟器对BGP的会话过程进行模拟。某一时刻指定特定层次中的任意BGP路由器停止一段时间后重新开始会话建立，由此观察在此过程中影响的路由器数目、路径数目以及收敛时间。为了模拟的真实性，对真实的BGP路由表数据进行提取抽样，从中根据资料6中的过滤规则筛选了110个节点AS组成网络，并保留它们的Customer-Provider或者Peering关系。根据第3.2节中的分层算法将这些节点分为核心层、转发层和边缘层，图3为最终生成的拓扑图。图4为节点的度分布，模型满足幂律特性。图3 模拟拓扑图图4 节点度分布模拟时间总共200s，在100s时将选定的路由器或者连接边停止1s再重启，这将导致网络收敛过程的发生。根据第3节的分析，将收敛事件发生的情况分为10类，选取相应的点和边。4.2 结果分析对模拟结果分析发现，在70s时所有AS的路由器会话都已完全建立，网络进入稳定状态。在100s时，使选定的节点或者边失效，这里边的失效可以通过将对应的AS连接端口停止转发来实现。因为撤销事件没有MRAI定时器的限制，所以对于10种不同的情况都可以在0.01s之内达到收敛状态，但是收敛时间还是会有差别。边缘层内部的收敛事件不需要通告全网，所以收敛时间非常快，达到e5s。在其余的几种情况下，转发层的收敛事件比核心层长10%左右。分析收敛事件影响的AS数的分布可以发现，一般来讲AS失效的影响比它们连接边的失效的影响要大很多，这是因为点的BC值一般比边的BC值要大。在模拟拓扑中，测量的网络深度H为5，而实验得到的影响的最长路径长度为7，这说明收敛信息的扩散存在着先上后下的过程，即先由Customer向Provider通告，再由Provider向自己其余的Customer通告，所以这种情况只能存在于转发层内部或转发层与边缘层之间的连接边上。这也就可以解释发生最长的收敛时间的情况为e=5，收敛事件为Te类型。撤销和通告的报文数反映了收敛事件所影响的路径数。图5 d）的左半部是announcement报文的数目，右半部是withdrawal报文的数目。在e=1，收敛事件为Tn的情况下撤销的报文最多，达到264个。这说明，因为AS3257为核心层节点，因此包含AS3257 的路径很多。而通告的报文在e=4，收敛事件为Tn的情况下达到892个，因为其他路由器在重新选路的过程中可以到达AS7018的备选路径比较多，收敛的过程也比较复杂，所以备选路径的数目也是影响收敛的关键因素之一。在101s时，将指定失效的点或者边重新恢复，那么就会产生up事件。up事件的收敛时间比down事件长很多，最多要90多秒才能够收敛，这是因为MRAI的影响。对数据进行分析发现，与down事件不同，路由重新选择的过程，每个AS平均需要向相同目的地通告两次路径，这两次通告之间必须要保证MRAI的时间间隔，所以在两三个时间段内网络上没有报文的发送和接收，而其他时间网络比较繁忙，所以更新报文的发送整体呈现出阶越式的趋势。在up事件的收敛过程中平均发生3 306次事件，包括接收、发送报文，以及路由器本身对转发表的操作，这与down事件的3 218次相差不多，而收敛时间却成为up事件的数百万次，可见MRAI对收敛时间的影响非常大。图5和图6分别为down事件和up事件在10种情况下各种收敛参数的比较。可以看出，收敛时间最长的情况存在于转发层，而核心层影响的AS数目比较多，产生的撤销和通告的报文数也比较多。这与第3节中模型分析得到的结果是吻合的。图5 down事件在各种层次情况下的收敛参数值比较图6 up事件在各种层次情况下的收敛参数值比较5 “Best Up”机制根据对BGP幂律层次收敛模型的分析以及模拟实验的结果，可以看出，网络核心层的Hub节点具有强连通性，以及很高的BC值，所以在BGP的收敛过程中起着非常重要的作用，通过它们可以加快收敛进程，缩短收敛时间，使更新消息得到尽快地传播。如何利用“Hub”节点的这个特点来加快BGP的收敛过程是本节的研究内容。在这里由于BGP协议的特性以及Internet的商业关系约束，要求更新报文的处理和扩散要满足一定的顺序，而不是完全随机的。假设在收敛过程中，影响的节点集合Nc包含的核心层节点为vi ,vj ，1ijk。由于vi ,vj都为Hub节点，由Internet的商业关系可知它们彼此为Peer关系。vi为收敛过程中更新报文通过的第一个Hub节点，其连接向量为Ci。根据第3节对BGP幂律层次收敛模型中讨论的各种收敛情况的分析，得知在大多数情况下，节点v收到更新报文后需要向Provider(v)、Peer(v)以及Customer(v)发送，这时要求v尽量先向Provider(v)发送消息。即每一个Nc中的节点将更新报文后“尽力向上”传播，直到网络核心层Hub节点vi ,vj ，然后以vi ,vj为根，树形扩散到整个Nc。在影响BGP收敛的各种因素中,MRAI定时器在其中起着极其重要的作用。通告报文在每一个路由器节点上都必须要等待到MRAI定时器到时才能够发送。所有在部署MRAI机制的情况下，收敛事件的持续时间会比正常情况下增加很多倍。而MRAI机制对于抑制路由抖动，提高域间路由系统的稳定性是非常有效的方法，在没有更好的方法取代它之前，MRAI定时器仍然会继续在域间路由系统中发挥作用和影响。从图7描述的“Best Up”机制的实现来看，“Best Up”机制中，AS向其Provider AS发送通告报文时，没有等待MRAI定时器的到时。这样加快了通告报文传播的速度，但是否会影响MRAI机制的作用呢？ 图7 “Best Up”机制的伪代码实现断言1 “Best Up”机制不会影响MRAI机制的作用。证明 在不考虑多宿主的情况下，每个AS只有一个Provider AS。而在大多数的多宿主情况下，AS只有2个到3个Provider AS。根据域间路由系统的层次特性和幂律特性，AS的祖先节点集合数量是非常有限的。而一个通告报文在没有MRAI定时器约束的情况下传输过一个路由器的时间一般在0.01s，0.1s的范围内，在一个AS内部传输的时间正常情况下不超过2s到3s。所以在“Best Up”机制中，一个通告报文从任何一个AS节点传输到Hub AS的时间可以控制在10s左右。当Hub AS接收到通告报文之后，它会等待MRAI定时器的到时在将报文发送到它的Peer节点和Customer节点。在这个过程中，如果被通告的路由发生变化，也可以有时间将最新的通告发送到Hub AS，使其在向全网扩散之前更新通告报文中的通告路径。换句话说，“Best Up”机制在短时间内，将通告报文传播到少数可以加快通告速度的关键节点上。如果通告报文是稳定的、正确的，那么通过这些关键节点，可以很快的将其在全网传播；反之，它也能够有时间将其撤回。所以，“Best Up”机制不会影响MRAI机制在域间路由稳定性方面所发挥的作用。下面我们通过模拟实验来验证按照这种方式是否能够达到减少收敛时间的目的。比较了节点数N=100、200、300、400、500的5种情况下，当收敛事件发生在转发层的Provider-Customer边上时，以下两种情况下的收敛时间。一种为无约束情况，即对单个节点的更新报文发送顺序没有约束；第二种情况为“Best Up”方法，即v尽量先向Provider(v)发送消息。图8和图9分别为在up事件和down事件中这2种方式的收敛时间T随着节点度数N的增大的变化情况，可以明显地看出采用“Best Up”方法可以明显地缩短收敛时间，并且随着N的增大，效果更明显。以N=500的实验为例，当收敛事件是图8 up事件中2种方式收敛时间比较图图9 down事件中2种方式收敛时间