<kbd id='woaibaidu'></kbd><address id='woaibaidu'><style id='woaibaidu'></style></address><button id='woaibaidu'></button>

          当前位置:主页 > 路由器 > 路由器故障 >
            DIMR:不相交多路径域间路由
            2018-04-15 23:53 发布 次浏览

          首先,两个不相交的AS路径形成一个AS环。本文中定义的环是一个AS序列,它从同一个AS(目的AS)开始又在同一个AS结束,并且不包含相同的AS。例如,在图2中,BGP运行在网络上,AS0是目的AS,并发布一个前缀。为了简单起见,我们假设这些AS的策略允许它们可以将AS路径宣告给相邻的AS。网络收敛后,AS7有两条不相交的AS路径[7 5 3 1 0]和[7 6 4 2 0],这两条路径形成了一个大环0→1→3→5→7→6→4→2→0。与此相对,如果AS7知道了这个AS环的存在,它就能相应地发现两个不相交的AS路径。

          1)转发表和数据包头部:

          4.1 基本定义

          3.1 环和不相交路径的关系

          [16] “The caida as relationships dataset,”

          ?优先选择前缀部分具有更低的字典顺序的组合

          我们的贡献和工作可以概括如下: 我们提出 了DIMR(不相交多路径域间路由),以使更多的AS发现两条不相交的路径, 这个协议包含一个分布式算法,用来并行地构造节点不相交路径。其次,我们在DIMR的规则设计中引入了路径组合和圆形表示 法的新概念,选择两个不相交的路径。 第三,我们在BGP模拟器SimBGP [10]上实现了DIMR,并把它 和PDAR(路径多样性感知路由)进行比较。 实验结 果表明,DIMR能使90%以上的多连接AS发现两条不相 交的路径, 并而且这些路径还具有更短的平均路径长 度。

          因为不相交AS路径和环之间有关系,所以修改BGP的第一步就是允许一个AS将它的AS环的信息与这个环上的其它AS进行共享。例如,AS7要与AS5共享这个环的信息的,它将向AS5发送两个AS路径[5 3 1 0]和[7 6 4 2 0]。现在,AS5就知道了这个大环0→1→3→5→7→6→4→2→0,并能够发现两条不相交的路径[5 3 1 0]和[5 7 6 4 2 0]。在AS7发送两条路径的时候,因为其中一条([7 5 3 1 0])包含了AS5,所以AS5会将这个路径过滤掉。不过,因为这条路径是从AS5宣告给AS7,AS5具有这条路径的信息,所以过滤掉这条路径并不会破坏这个AS环的信息。

          因为这个大环的形成使用了这两个小环的信息,而这两个小环并不使用别的环的信息,所以我们定义这两个小环为基本环,而这个大环为派生环。

          ?优先选择具有更短的圆圈符号的完全不相交组合

          我们认为这个结果的差异源于选择两条路径的方法的不同。在PDAR中,主路径优先选择,根据主路径来选择替代路径。因此,主路径的收敛延迟是跟BGP相同的,但另一条路径沿着很长的路径传播从而收敛得非常缓慢。而在DIMR中,两条路被视为一个组合,从而同时被选择,他们也同时收敛。

          我们将DIMR的仿真结果与BGP和基本PDAR进行比较。我们只考虑基本PDAR ,因为它实现的主要思想是PDAR根据主要路径来选择一个替代路径,那就是DIMR和PDAR之间的关键区别。

          3.4 例子

          再一次,我们修改了上述协议,允许一个AS向所有相连的邻居共享它的的AS环信息。因此,AS6发送两条路径[6 2 0]和[6 4 1 0]到AS9,同时,AS9也将这个环的信息传递给AS8,从而发送两条路径[9 6 2 0]和[9 6 4 1 0]。基于同样的道理,AS10发送路径[10 7 2 0]和[10 7 5 3 0]到AS8。这样,AS8就能计算出两个不相交的路径[8 9 6 4 1 0]和[8 10 7 5 3 0]。然后,AS8就知道了这一个大环0→1→4→6→9→8→10→7→5→3→0。通过把这个大环的信息共享给AS9和10之后,他们就可以找到两个不相交的AS路径。

          3) 形成黑色环: AS5将蓝色环的信息传递 给AS2,4和6, 这使得AS4和6都能找到两条不相交的路 径。 在此期间,AS1发送不相交的路径给AS6,AS3发 送不相交的路径给AS4。 最后,AS4和6发送其不相交路 径到其邻居,网络收敛。

          最终,所有的AS都发现了两条不相交的路径,并了 解到了环的信息。 AS1,2和3都选择了红色环所代表的 路径。 AS4和5选择了蓝色环代表的路径。 AS6选择了 黑色环代表的路径。 同时,AS2和3还知道蓝色环的信 息, 而AS1和5知道了黑色环的信息。 对于图1中的例 子,如果采用DIMR的话,AS6和7都可以找到两条不相 交的路径。

          算法的输入是所有的合法路径,然后计算所有合法的路径组合,最后通过选择规则选择出最适合的路径或者路径组合。

          域间多路径路由是第一次在MIRO [1]中提出。它使一个AS可以对其他AS提供替代路径,这是通过在两个AS之间设置隧道来实现。 在MIRO中,可供选择的路径是通过协商来提供:当一个AS需要某一条前缀的替代路径时,它向其他的AS请求路径。这个被请求的AS根据其本地路由策略来向发起请求的AS回应。因为协商和安装路径需要时间,所以该方案不适合用于快速故障恢复。

          首先,我们假设该网络上运行BGP协议。网络收敛后,两个AS6和7将具有两个不相交的AS路径,而其他的AS将只有一个AS路径。现在的AS环已经形成,但只有AS6和7知道这个AS环的信息。这是由于BGP的功能只允许AS宣告自己的最佳路径,但是这样做阻止了其他自治系统找到两条不相交AS路径的机会。为了帮助所有的AS发现两个不相交的AS路径,我们需要对BGP做一些修改。

          2) 形成蓝色环: AS2发送两条不相交的路径 到AS1,3和5,然后AS1和3就知道了红色环的信息。 在 此期间,AS4和6发送它们的路径[4 3 0]和[6 1 0]到AS5。 根据第IV-B节中所描述的规则, AS 5从中选择两条不相 交的路径[5 1 2 0]和[5 4 3 0],他们构成了蓝色环。

          这里需要注意的是,AS8在选择环的时候有三种选择,我们选择了更大的那个环是为了更方便地画图和说明想法。

          比如在图4上的网络上,如果在同一个AS环上的各个自治域可以共享AS信息,那么AS1,6和7都可以发现一个环,但是AS8,9和10却无法找到AS环的信息。这是因为,AS的6和7只宣告自己的最佳路径[6 2 0]和[7 2 0]的给AS8和9,他们他们发现AS8和9并不在同一个环上。这样AS8,9和10就不能找出两个不相交的路径。

          DIMR:不相交多路径域间路由

          [10] “Simplebgpsimulator,”

          .[6] I. Ganichev, B. Dai, P. Godfrey, and S. Shenker, “Yamr: Yet another multipath routing protocol,” ACM SIGCOMM Computer Communication Review, vol. 40, no. 5, pp. 13–19, 2010. ?

          DIMR:不相交多路径域间路由

          [8] D. Qin, J. Yang, H. Wang, B. Zhang, L. Gao, and Z. Liu, “Multipath interdomain routing via deviation from primary path,” in Information Networking (ICOIN), 2012 International Conference on. IEEE, 2012, pp. 222–227.

          DIMR:不相交多路径域间路由

          DIMR:不相交多路径域间路由

          1)已经形成一个环:如果一个AS找到了两条不相交的路径,那么该AS已经形成了一个环。这个AS会通过宣告两条路径的方式,将这个环的信息宣告出来,这对于其它AS找到新的环是有帮助的。例如,在图3中,当AS6找到了两条不相交的路径[ 6 4 1 0 ]和[ 6 2 0 ] ,它就知道了左侧虚线环的存在。一方面,AS6与AS2和4共享环的消息。另一方面,它宣告信息给AS9 ,以便形成更大的环。

          定义4.2(完全不相交):和是简单路径,, 。如果满足以下条件,那么路径和则是完全不相交的:

          在我们的研究中,我们试图找出为什么现有的协议生成不相交路径的效率都比较低。我们观察现有的域间多路径路由协议发现,其中大部分都是基于BGP设计的。在这些设计中,主路径的选择与BGP路径选择是相同的标准,然后根据选择出的主路径来选择备用路径。例如,PDAR[4]选择与主路径最不相交的作为备用路径, YAMR[6]则根据主路径的每条链路来选择不包含该链路的备用路径。

          表I显示了上述网络协议的一次完整运行的细节信息。 在这个例子中,DIMR的过程可被视为形成了三个环。

          ?选择拥有最短的长度的路径

          .[3] I. van Beijnum, J. Crowcroft, F. Valera, and M. Bagnulo, “Loop-freeness in multipath bgp through propagating the longest path,” in Communications Workshops, 2009. ICC Workshops 2009. IEEE International Conference on, june 2009, pp. 1 –6. ?

          定义4.1(简单路径):,其中是一个AS号,如果存在,,那么是一个简单的路径。

          例如,如果当前的AS号是5而存在两个路径组合1:3:5:4:2和1:3:5:6:4:2,那么优先选择1:3:5:4:2,因为它包含较少的AS。而如果存在路径组合1:3:5:4:2和1:4:5:3:2,那么优先选择1:3:5:4:2,因为它的圆圈符号有一个较低的字典序。

          2.2 不相交多路径路由

          1)具有不相交路径AS数量:这表示在网络收敛之后,有多少个多连接AS(拥有一个以上邻居的AS)能够找到两条不相交路径。在我们的拓扑结构中,多连接AS的数量是26166 ,这是也是具有不相交路径的AS的数量的上限。

          定义4.5 (圆形表示法) :设表示完全不相交组合。由路径和组成,其中设。 的圆形表示法为。设表示后缀的不相交的路径和组成的组合,其中。 的圆形表示法为。其中是的前缀,而 是的后缀。

          4.3 实现细节

          在本节中,我们描述协议的细节。 首先,我们在4.1节中介绍一些基本定义。 此后,4.2节描述了选择算法选择规则。最后在4.3节中说明实现的细节。

          图8表示不相交的路径的AS数量的CDF (累积分布函数)。结果表明,DIMR的结果显著优于PDAR。我们观察到,在使用PDAR时,只有不到60%的试验中具有两条不相交路径的AS数量超过23000,而在使用DIMR是,在96%的试验中,这个数字都是大于24000的。而且,由于多连接AS的数量为26166 ,DIMR使的91%的多连接AS都能找到两条不相交路径。此外,由于在每次实验中,进行前缀宣告的AS的位置是随机选取的,我们认为PDAR算法对于宣告前缀的AS的位置较为敏感,因此可能在针对某些AS宣告的前缀计算不相交路径时表现不好。而与此相反,DIMR对位置相对较不敏感,在计算不相交路径时得到比较 良好的表现。

          定义4.4(路径组合) :路径组合是两条完全不相交或者后缀不相交的简单路径的组合。两条完全不相交的路径被称为完全不相交组合,两条后缀不相交的路径被称为后缀不相交组合。

          1)从目的AS开始形成一个新的环:为了简单起见,我们解释如图3的环如何形成。

          在本文中,我们提出不相交多路径域间路由算法DIMR在使尽可能多的AS发现不相交的路径。在协议中,我们引入路径组合的概念,它由两个完全不相交或两个后缀不相交的路径组成。我们用圆形符号来表示一个有效的路径组合,并设计了选择路径组合的规则。通过使用这种路径组合选择算法,DIMR的表现优于PDAR,使90%以上的多连接AS找到完全不相交路径。同时,DIMR产生的路径也更短,收敛时间比PDAR稍快。我们未来的研究将侧重于DIMR对于路由协议的稳定性的影响,同时也考虑如何增量部署DIMR。

          2.1 域间多路径路由

          5.2 模拟结果

          我们研究首先从环和不相交路径的关系开始,我们发现,一个环和不相交AS路径之间存在对应关系。

          2)路由策略兼容性:这个算法可以兼容一定程度的路由策略。它实现路由策略是通过出口过滤。在选择阶段通过算法规则选择最佳路径或路径组合。而在宣告阶段,路由器根据本地路由策略来决定是否要宣告某条路径给某个邻居。如果两条路都被允许宣告,路由器宣告路径组合。如果只有一条路径是允许宣告的,路由器则宣告一条简单路径。如果不允许宣告任何路径,那么路由器宣告一个路由撤销。

          ?优先选择圆圈符号的前缀更短的组合

          多路径路由已经很久就被应用域内流量工程上[11]。不相交多路径路由需要多条路径是节点不相交或链路不相交的[12]。 Medard等在[13]提出了一种利用两棵染色树来生成两条不相交的路径的集中式算法。这两棵染色树具有相同的根,即目的节点。 对于每一个非目的节点,该节点在一棵树上到的根的路径和从另一棵树上到根的路径是节点不相交的。他们推出了一个名为路径增广机制。 该成果的限制是,该算法是集中式的算法,必须知道整个网络的拓扑结构。

          ?优先选择圆圈符号的后缀更短的组合

          DIMR:不相交多路径域间路由

          参考文献

          图9显示了在“宣告”,“失效”和“恢复”事件过程中的收敛延迟的CDF 。在所有三个事件里,因为PDAR和DIMR都比BGP经历较长的收敛过程,这是因为消息需要传播更长的路径,以便找到不相交的路径。在“宣告”事件,DIMR明显优于PDAR 。通过使用DIMR, 52.5%的情况下收敛时间在120s内,97.5%的情况下收敛时间在140s内 。而使用PDAR,这些对应的数字是36.3%和81.3%。在“失效”和“恢复”事件中,DIMR的行为和PDAR在大多数情况下是类似的。但是,我们观察到三个事件中,DIMR的最长的收敛时间是161.33s, 139.59s和155.83s,而在PDAR中,这个对应的数字是207.78s,212.8s和219.86s。

          4)路由更新数量:路由更新是从一个AS到另一个AS的信息,它可能包含一条或两条路径,或没有路径。 路由更新的数量是所有路由事件触发的路由更新的数量。这是一个路由协议的成本,还可以衡量协议的可扩展性和不稳定性[18]。我们观察到PDAR和DIMR在路由更新数量的区别很小,表示DIMR的控制消息开销和PDAR类似。我们认为这是因为,为了要寻找两天路径,所需要传送的必要信息是相似的。

          4 详细设计

          1) 形成红色环: 第一,AS0宣告[0]给AS1和AS3,从 而他们各得到了一条路径,但不能发现两条不相交的 路径。因此,AS1发送路径[1 0]到AS2和AS6,AS3发送 路径[3 0]到AS2和4。然后,一旦AS2从AS1和3接收到 路径,它就可以找到两条不相交路径[2 1 0]和[2 3 0]。 AS2现在发现了红色环的存在。

          在描述完DIMR的主要内容之后, 我们描述在图5所示 的网络上如何运行DIMR。

          4.2 路由选择规则

          3 )正在形成基本环:如果一个AS既找不到两条不相交的路径,也找不到从同一个邻居收到的两条路径,那说明正在形成一个基本环。这时,这个AS将添加自己的AS号并宣告这个路径以形成一个基本环。例如, 当AS1从AS0收到一条路径[0]的时候是处于在这种情况,所以AS1添加了自己的的AS号并宣告路径[1 0]。

          2 相关工作

          本文的其余部分安排如下: 第2节概述了相关工作。第3节用一个例子来解释DIMR的主要思想。 DIMR设计的细节在第4节。 第5节介绍了DIMR的性能评价。第6节总结我们的工作。

          1)规则概述:图6表示了的路径选择规则。由于在我们的方案里,一个AS可能有三种状态,所以这些规则被分为三类。在进行路径选择的时候,这个AS根据自身的状态,选择对应类别的规则。因此,在每一次路径选择中,只会使用一类规则。在每个类别中,规则都是有顺序的,所以应该根据这个顺序来使用规则来进行路径选择。

          R-BGP[5]专门用于防止AS遇到传输路径断开。 每一个AS都通过宣告一条保护路径来保护自身和其下一跳邻居之间的链路。因此,在发生故障时,数据包可以沿着保护路径发回到上一跳,而不会被丢弃。R-BGP引入较小的开销,但只适合于链路保护的问题。

          [12] S. Ramasubramanian, H. Krishnamoorthy, and M. Krunz, “Disjoint multipath routing using colored trees,” Computer Networks, vol. 51, no. 8, pp. 2163 – 2180, 2007.

          .[7] D. Qin, J. Yang, Z. Liu, H. Wang, B. Zhang, and W. Zhang, “Amir: Another multipath interdomain routing,” in Advanced Information Networking and Applications (AINA), 2012 IEEE 26th International Conference on, march 2012, pp. 581 –588. ?

          5.1 仿真环境

          摘 要 :域间多路径路由, 它使源AS可以使用多条路 径发送流量到同一个目的AS, 是一种有前途的技术, 可以提高带宽,提高容错性和故障的快速恢复。 但是,以前的域间多路径路由协议,往往会产生一些相交的路径, 相交的地方形成了瓶颈, 这使得他们很容易在瓶颈处形成单点故障,因此效率不高, 降低了域间流量工程或并发多径传输的效率。 在本文中,我们提出了不相交多路径域间路由(DIMR), 试图让更多的AS找到两条不相交的路径。 在这个协议中,我们提出了路径组合的概念并设计了的路径组合选择的规则。 我们评估DIMR仿真。 实验结果表明,DIMR能使90%以上的多连接AS找到两条不相交的路径。

          5 方案性能评价

          DIMR:不相交多路径域间路由

          [11] G. Lee and J. Choi, “A survey of multipath routing for traffic engineering,” Information and Communications University, Korea, 2002.

          .[2] X. Yang and D. Wetherall, “Source selectable path diver- sity via routing deflections,” in Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, ser. SIGCOMM ’06. New York, NY, USA: ACM, 2006, pp. 159–170. ?

          我们设计的原则有两点:首先,我们总是偏向于较短的对象:更短的路径或者具有较短的圆圈符号的组合。这样的设计,使得每个路由器都努力让所选路径的长度减到最小,我们认为这是收敛的关键,而且还减小了AS路径的平均长度。其次,我们希望不同的自治域的做出选择应该是一致而不产生冲突的。因此,我们选择的路径或路径组合具有相同的长度时,选择其中字典序较小的对象。

          域间多路径路由,这使得源AS利用多条路径发送数据到同一目的AS,可以提供更好的用户控制,更快的故障反应和更多的带宽。它是一种很有前途的技术,用于利用附加的链路资源,提高互联网的性能和满足不同应用的各种需求。许多研究人员意识到域间多路径路由的潜力并开展了很多工作[1]–[9]。 这些工作都充分利用了多条路径来提高网络的性能(如容错性、用户控制和快速重路由)。