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

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

关键词 ：多路径路由;不相交多路径;域间;备用路径

 

1 引言

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

   在本文中,我们提出了一种多域间路由协议，目的是让更多的AS找到两条不相交的路径。 我们设定这个目标，因为不相交的路径具有很好的性质。 不相交路径具有更好的容错性，因为没有单个故障可以在同一时间让两条路径无效。同时，不相交的路径可以提供更高效的流量并行发送，因为当流量沿不相交路径传送时，总带宽为每个路径的带宽的总和。反之，如果该路径具有一些共同的链路或工作AS，那么总带宽决定与这些共享链接或自治域的能力，这是低效的。

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

    我们意识到,寻找不相交路径的低效率可能是因为路径选择的方法。我们观察到，为了让更多的AS发现不相交的路径，有时基于主路径来选择备用路径是不明智的选择。考虑图1所示的网络中的AS0为目的AS。从理论上讲，每一个AS到AS0都有两条不相交的路径。但是，对于AS7来说,如果选择7 → 5 → 2 → 0作为主路径，它就不可能发现从AS7到AS0并与主路径不相交的另一条路径。 而且，如果AS7选择7 → 6 → 3 → 2 → 0作为其备用路径，那么AS6将没有机会发现路径5 → 4 → 1 → 0，从而不能构建两个不相交的路 径。相反，如果AS7有选择突破这种首先选择主路径的约束，它可以选择两条不相交路径7 → 5 → 4 → 1 → 0和7 → 6 → 3 → 2 → 0。同时，AS6也能够发现两条不相交的路径。 此外，这些协议还可能产生较长的路径。而且由于备用路径要等到主路径收敛才能收敛，那样网络可能在某些情况下收敛缓慢。

    因此,在本文中,我们会尝试同时选择两个不相交路径, 而不是先选择一个主路径，然后再选择备用路径。我们把两条不相交路径作为一个路径组合,并选择最佳的组合。在基于路径组合的协议中，网络收敛是基于路径组合的，这样这两条路径将在同一时间收敛。在我们的模拟中，我们的协议能够更有效地产生不相交路径，而且收敛更快。

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

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

 

2 相关工作

    有两类涉及到我们工作的作品：一个是域间多路径路由,另一种是不相交多路径路由。

2.1 域间多路径路由

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

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

    PDAR [4]在某种程度上类似DIMR。 PDAR先选择一条主路径，然后选择与主路径最不相交的路径作为备用路径。在此之后，无论是主路径还是备用路径都被宣告给它的所有邻居。我们的协议和PDAR之间的区别是，我们把两个路径作为一个组合，并选择最佳的组合。PDAR的备用路径可能是很长的，从而只能用作保护路径，而我们的协议选择的不相交路径可以潜在地用于并发数据传输。

    YAMR [6]通过一种特殊的方式来选择备用路径。在选择主路径之后，针对主路径的每条链路，选择一条不包含该链路的路径作为备用路径。在被选择的这组备用路径中，没有单一的故障可以在同一时间内让所有的备用路径失效。同时，YAMR提出了故障信息隐藏机制，减少了路径更新数量。 然而，故障信息隐藏机制使数据平面和控制平面之间产生了不一致, 这可能导致潜在的转发环路。

2.2 不相交多路径路由

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

    此外，Ramasubramanian等[14]改善了上述的算法，设计了一个分布式路由协议来实现算法。其中，每一个节点在做决定时，仅仅依靠从相邻节点获得的信息。然而，由于路径增广必须要维持节点间的偏序关系，该协议是串行执行的: 当节点与接连的一个邻居进行通信时，必须等待这个邻居完成计算返回结果，才能与下一个邻居进行通信。因此，在任何时候，都只有一个节点在进行计算。

 

3 主要思想

    在这一节中,我们简单介绍DIMR的主要思想。 首先，我们在3.1节中描述环和不相交路径的关系。 其次，在3.2节中，描述两种形成环的情况。 再次,我们在3.3节中描述单个AS的策略，这种策略可以来促进环的形成。 最后，3.4节中用了例子来描述了DIMR如何运行。

3.1 环和不相交路径的关系

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

    首先，两个不相交的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路径。

    此外一个有趣的特点是，同一个AS环可能形成不同的相交路径。例如，在上述的网络中，AS6还具有2条AS路径[6 4 2 0]和[6 7 5 3 1 0]，它们也形成了0→1→3→5→7→6→4→2→0这个AS大环。虽然AS6和AS7发现的不相交路径是不同的，当时它们却共享了同一个AS环的信息。同时，这个AS环的信息是本地的，在上面的例子中，只有AS6和7知道的这个AS环的存在，而其他的AS并不会注意到它。

    然后，我们开始研究这种AS环是如何形成的。

3.2 环的形成

    在知道了AS不相交路径和环的关系后，我们研究一个环是如何产生的，以及如何利用此信息来帮助其他的AS找到自己的AS不相交路径。我们观察到，一个新的AS环的形成有两种情况：

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

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

    因为不相交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环的信息。

    2）从旧环开始形成一个新的环：只在同一个AS环的AS之间共享这个AS环的信息是不够的，如果能够将这个AS环的信息分享给其它的AS，那就很可能帮助到其它其他自治系统，他们也能找到自己的环。

 

    比如在图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就不能找出两个不相交的路径。

    再一次，我们修改了上述协议，允许一个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路径。

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

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

3.3 状态和策略

    DIMR使用了以上的机制来促进环的形成。我们观察到，在环的形成的过程中，一个AS可能会处于三种状态。因此，每个AS在从邻居收到路由信息之后，需要根据它的状态来做出适当的选择，从而促进环的形成。这三种状态是：

 

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

    2）正在形成派生环：如果一个AS不能找到两条不相交的路径，但从某个邻居收到两条路径，那么这代表有一个派生环正在形成。因此，这个AS会增加自己的AS号码并宣告两条路径。例如， 当AS 9仅从AS6接收两个路径[ 6 4 1 0 ]和[6 2 0 ]时就是在这种情况。它会意识到，有某个AS（AS6）知道了一个环（左边的虚线环）的信息并告诉它，它应该与别的AS分享信息，以便形成一个大环。因此， AS9增加自己的AS号并发布两条路径[9 6 4 1 0 ]和[9 6 2 0] 。这两条路径被称为后缀不相交的路径。

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

3.4 例子

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

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

    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现在发现了红色环的存在。

    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],他们构成了蓝色环。

    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都可以找到两条不相 交的路径。

 

4 详细设计

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

4.1 基本定义

    定义4.1（简单路径）：，其中是一个AS号，如果存在，，那么是一个简单的路径。

    定义4.2（完全不相交）：和是简单路径，， 。如果满足以下条件，那么路径和则是完全不相交的：

    定义4.3（后缀不相交）：和是简单路径，，，。那么如果使以下成立，那么路径和则是后缀不相交的：

    直观地讲，完全不相交的两条路径除了第一个和最后一个AS相同以外，其它AS都不相同，而后缀不相交的两条路径具有相同的前缀部分，但其后缀部分是完全不相交的。后缀不相交的两条路径可以通过在完全不相交路径前面增加简单路径而产生。

    定义4.4（路径组合） ：路径组合是两条完全不相交或者后缀不相交的简单路径的组合。两条完全不相交的路径被称为完全不相交组合，两条后缀不相交的路径被称为后缀不相交组合。

    定义4.5 （圆形表示法） ：设表示完全不相交组合。由路径和组成，其中设。 的圆形表示法为。设表示后缀的不相交的路径和组成的组合，其中。 的圆形表示法为。其中是的前缀，而 是的后缀。

    圆形表示法被用来表示和比较不同的路径组合。对于完全不相交的路径组合，圆形表示法是两条路径通过相反的顺序连接而成。例如，一个完全不相交的路径组合包含7:5:3:1:0和7:6:4:2:0则圆圈表示法为1:3:5:7:6:4:2。对于一个后缀不相交的路径组合，圆形表示法是由前缀部分和后缀部分的圆形表示法组成。例如，含有8:7:5:3:1:0和8:7:6:4:2:0的后缀不相交组合的圆形表示法为8:7_1:3:5:7:6:4:2。

4.2 路由选择规则

    我们使用了路径选择算法来决定什么哪些路径应该被安装到本地路由表并宣告到其它邻居。

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

 

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

    2 ）完全不相交组合的选择规则：当至少存在一个有效的完全不相交组合时应用这些规则，并选择最佳的完全不相交组合。这两个规则的含义是：

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

    ?优先选择圆圈符号的字典序更小的完全不相交组合

    例如，如果当前的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，因为它的圆圈符号有一个较低的字典序。

    3）后缀不相交组合的选择规则：如果没有有效的存在不相交的组合，但存在至少一个有效的后缀不相交组合，则应该应用这些规则。四个规则的含义是：

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

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

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

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

    例如，如果当前的AS号是5而且存在两个路径组合5:4_1:3:4:6:7:2和5:6:4:_1:3:4:2存在，选择前者，因为它具有较短的前缀。如果组合5:4_1:3:4:2和5:4_1:3:4:6:2存在，将选择前者，因为前缀等长的情况下后缀较短。如果存在组合5:6:4_1:3:4:2 和5:7:4_1:3:4:2存在，前者是优先选择的。

    4）简单路径的选择规则： 如果没有有效的完全不相交组合，也没有有效的后缀不相交组合存在则应用这些规则。这两个规则的含义是：

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

    ?选择拥有最低的字典序的路径

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

4.3 实现细节

    1）转发表和数据包头部：

    类似其他多路径路由协议，需要一个索引来区分这两个具有相同目的前缀的AS路径。因此，路由更新应该使用索引号来区分这两条AS路径，路由器也必须使用索引号来标识到同一个前缀的两个下一跳，同时数据包里面也需要指明沿着哪个下一跳发送该报文。因此，在转发表中包含两个附加字段（索引和下一索引） ，数据包的报头中也包含一个额外的索引字段。图7显示了网络收敛后的AS 2的转发表。

    当AS2收到一个目的地址为AS0索引为1的数据包时，它会搜索其转发表匹配目标是AS0，索引为1的表项，从而选择了转发表项的第二条表项。根据第二项，下一跳是AS3，下一索引是0。因此，AS2改变数据包的索引字段为0，并且将该报文发送给AS3。

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

 

5 方案性能评价

5.1 仿真环境

    我们通过扩展实现一个事件驱动的模拟器simBGP [10] ，其中包括重要功能像MRAI定时器，处理延迟，传输延迟， EPIC [15] ，进口和出口过滤器。 EPIC是限制路径探索的机制，我们将其扩展到支持多路径。Internet拓扑生成从CAIDA的AS关系数据[16]生成，简单起见， 使用一个路由来代表一个AS 而使用链接来代表商业关系，如客户供应商关系（C2P ） ，对等关系（ P2P ）和兄弟关系（ S2S） 。每台路由器上的出口过滤器上通过编程，来防止无谷路径[17 ] ，这意味着，从供应商/对等实体得到的AS路径不允许被宣告给其他供应商/对等实体。

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

    我们的单次实验流程如下：我们随机选择一个多宿主的边缘AS，它应该至少有三名提供商。首先，我们宣告前缀，被命名为“宣告”事件，并等待网络收敛。然后，对于这个AS的每一条提供商链路，我们关闭该链路，这被命名为“失效”事件，之后再打开该链路，这被命名为“恢复”事件。在我们的模拟中，我们进行80次实验，模拟了80次“宣告”事件，329次“失效”事件和“恢复”事件。对于每次实验中，我们计算了具有两条完全不相交路径的AS数量，以及两条路径的平均路径长度。对于每个事件，我们在事件发生后计算收敛时间。

5.2 模拟结果

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

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

    2）收敛延迟：收敛延迟测量了路由算法的稳定性，它是通过最后更新消息的时间减去收到事件的时间来得到。

    图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。

 

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

 

图10 路径的平均长度

    3）平均路径长度：平均路径长度表示一个AS的两条路径的平均长度。图10表示了路径的平均长度的CDF。我们使用两种口径来选择针对那些AS来计算路径： 一种是找到两条不相交路径的AS，结果用虚线表示，另一种是所有找到两天路径的AS，这是由实线表示。如图所示，通过使用DIMR，不仅那些找到的不相交路径更短，而且所有多连接的AS都找到了更短的两条路径。

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

 

6 结论

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

 

 

 

参考文献

.[1] W. Xu and J. Rexford, “Miro: multi-path interdomain rout- ing,” in Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer com- munications, ser. SIGCOMM ’06. New York, NY, USA: ACM, 2006, pp. 171–182. ?

.[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. ?

.[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] F. Wang and L. Gao, “Path diversity aware interdomain routing,” in INFOCOM 2009, IEEE, april 2009, pp. 307 – 315. ?

.[5] N. Kushman, S. Kandula, D. Katabi, and B. M. Maggs, “R- bgp: Staying connected in a connected world,” in Proceedings of the 4th USENIX conference on Networked systems design & implementation (NSDI’07), 2007. ?

.[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. ?

.[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. ?

[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.

[9] J. Su, B. Dai, Y. Liu, and W. Peng, “Inter-domain multipath routing protocols,” Journal of Software, vol. 23, no. 1, pp. 65–81, 2012.

[10] “Simplebgpsimulator,”http://www.bgpvista.com/simbgp.shtml/.

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

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

[13] M. Me ?dard, S. G. Finn, and R. A. Barry, “Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge- redundant graphs,” IEEE/ACM Trans. Netw., vol. 7, no. 5, pp. 641–652, Oct. 1999.

[14] S. Ramasubramanian, M. Harkara, and M. Krunz, “Linear time distributed construction of colored trees for disjoint multipath routing,” Computer Networks, vol. 51, no. 10, pp. 2854 – 2866, 2007.

[15] J. Chandrashekar, Z. Duan, Z.-L. Zhang, and J. Krasky, “Limiting path exploration in bgp,” in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, vol. 4, march 2005, pp. 2337 – 2348 vol. 4.

[16] “The caida as relationships dataset,” http://www.caida.org/data/active/as-relationships/.

[17] L. Gao, “On inferring autonomous system relationships in the internet,” IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 733–745, Dec. 2001.

[18] A. Elmokashfi, A. Kvalbein, and C. Dovrolis, “Bgp churn evolution: a perspective from the core,” in INFOCOM, 2010 Proceedings IEEE, ser. INFOCOM, 2010 Proceedings IEEE, 2010, pp. 1–9.