DOI: 10.11817/j.issn.1672-7207.2015.08.

域间网络保护路由

袁静^{1, 2}，陈凯³，胡成臣⁴，陈曦¹

(1. 清华大学 自动化系，北京，100084；

2. 国家计算机网络应急技术处理协调中心，北京，100029；

3. 香港科技大学 计算机科学与工程系，香港；

4. 西安交通大学 计算机科学与技术系，陕西 西安，710049)

摘要：提出一种域间网络保护路由模型，利用边界网关协议(BGP)路由表中已经存在的后备路由资源，确保在路由收敛过程中自治系统(autonomous system，AS)节点之间端对端的连通性，从而避免数据传输发生中断，解决瞬态故障。并利用互联网AS-level网络拓扑图重构AS节点的路由表，评估互联网的可保护程度。研究结果表明：提出的保护路由模型在不增加BGP路由器额外开销的基础上能够较好地保证网络数据传输不中断，增强互联网的连通性。

关键词：域间网络；边界网关协议；瞬态故障；保护路由

中图分类号：TP393             文献标志码：A         文章编号：1672-7207(2015)08-2884-08

Protected routing for inter-domain network

YUAN Jing^{1, 2}, CHEN Kai³, HU Chengchen⁴, CHEN Xi¹

(1. Department of Automation, Tsinghua University, Beijing 100084;

2. National Computer Network Emergency Response Technical Team/Coordination Center of China,

Beijing 100029, China;

3. Department of Computer Science and Engineering,

Hong Kong University of Science and Technology, Hong Kong, China;

4. Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, China)

Abstract: A protected routing model for inter-domain network was proposed based on the existing backup paths in border gateway protocol (BGP) routing table to guarantee the end-to-end connectivity and the uninterrupted packet forwarding for autonomous system (AS) nodes, and to solve the transient failure. The protectability of the current internet was evaluated based on constructing the complete AS nodes’ routing tables by using the internet AS-level topology graph. The results show that the protected routing model can guarantee the uninterrupted packet forwarding and enhance the connectivity of Internet without increasing the overhead of BGP routers.

Key words: inter-domain network; border gateway protocol; transient failure; protected routing

可靠的互联网连通性是保证在线实时网络应用服务品质的主要因素，而边界网关协议(border gateway protocol，BGP)则是保证互联网连通性的关键协议。虽然在互联网拓扑结构中存在许多冗余链路资源，但BGP协议本身的路由不稳定问题往往会导致自治系统(autonomous system，AS)节点之间连接丢失，互联网持续的连通性不能得到保证。当网络拓扑结构发生变化或链路出现故障时，BGP协议会重新计算AS节点到达各个目的节点的最佳路由并更新路由表信息，该过程称为路由收敛过程。在路由收敛过程中，某些AS节点会暂时与目的节点中断连接(在路由收敛过程结束后恢复连接)引起路由不稳定，从而导致节点之间传输数据被丢失，互联网的连通性出现短暂的中断，该现象被称为瞬态故障(transient failure)。瞬态故障发生在BGP路由收敛过程中，一种最直观的解决方案是通过缩短BGP路由收敛时间从而尽量避免数据丢失^[1-4]。文献[2]通过降低最小路由通告时间间隔(minimum routing advertisement interval，MRAI)以加快BGP路由收敛的速度。文献[4]设计了一种新的BGP路由机制，即BGP-RCN(BGP-root cause notification)，将引发BGP重新计算路由的根源信息(root cause information)包含到更新消息中。当网络中单条链路出现故障时，若某个AS节点首次收到因为链路故障而引发的更新消息，则该节点会删除其路由表中所有跟故障链路相关的路由，以保证在BGP收敛过程中，这些失效路由不会被输出。因此，BGP-RCN减少了路由更新消息的数目，进而缩短了BGP收敛时间。虽然这类方法减少了BGP的路由收敛时间，但由于互联网的规模非常庞大，无论这类研究如何加快BGP路由的收敛速度，还是不能避免收敛过程中存在的数据丢失现象，即并没有从根本上消除瞬态故障。另一类解决瞬态故障的研究思路是利用互联网AS-level拓扑结构中潜在的冗余连接资源，使AS节点获取更多的路由信息。文献[5-6]通过设计新的BGP协议，允许每个AS节点向其邻居广播多条到达目的节点的路由，以确保在路由收敛过程中节点之间的数据传输不中断。文献[7]通过预先计算额外的关键故障转移路由来确保互联网的连通性。只要某个AS节点在BGP收敛过程结束后仍存在到达目的节点的路由，则文献[7]确保在BGP收敛过程中，该AS节点与目的节点之间的连通性保持不变，不会发生数据中断。虽然这类方法解决了BGP瞬态故障，但它们不仅需要AS节点提前计算额外的路由信息，而且还需要AS节点将这些额外路由广播给其邻居节点，从而使得BGP路由器和网络都存在额外开销(路由器存在路由的计算和存储开销；网络存在路由的传输开销)，可能还会延长BGP的路由收敛时间。此外，在域间网络连通性的现有研究中，为了分析在不同的网络故障下域间网络的可恢复性，文献[8]深入地分析了当发生不同网络故障时，域间路由系统所采取的相应措施并精确地指出影响互联网可靠性的瓶颈；文献[9-10]通过寻找互联网交换点IXP上的冗余资源以及修改对等AS节点的商业关系，以提高互联网的可恢复性。这类研究的关注点是当互联网遭遇重大灾害(如大地震、光缆切断等)时，如何快速有效地恢复AS节点之间的连通性。它们的研究重点是域间网络的可恢复性，并没有解决由于BGP路由不稳定而导致的瞬态故障。为了消除BGP收敛过程中的瞬态故障，本文作者提出了一种新的域间网络路由模型，即保护路由模型(protected routing)，利用AS节点路由表中已经存在的后备路由信息(而不是预先计算的额外路由信息)，在BGP路由收敛过程中确保AS节点之间端对端的连通性，从而避免数据传输发生中断。并利用互联网AS-level网络拓扑图重构BGP路由表，评估了当前互联网的可保护程度。需要指出的是，已有学者在研究域内网络(intra-domain network，即IP网络)的连通性问题时，利用“保护路由”命名其设计的域内网络路由机制^[11]。他们研究的重点是一个AS节点内部的连通性，而本文的研究对象是域间网络(inter-domain network)，其研究重点是不同AS节点之间的连通性，即从宏观的角度研究整个互联网的连通性。

1  保护路由模型

域间网络拓扑结构可定义为一个有向图G=(V，E)，其中V为AS节点的集合，E为AS节点之间关系链接的集合。在图G中采用“valley-free”路由输出策 略^[12]，即AS节点在输出路由时需要考虑其与邻居节点之间的商业关系。在域间网络中，AS节点之间主要有4种商业关系：提供商-客户关系(provider-customer)，客户-提供商关系(customer-provider)，对等关系(peer-peer)和同胞关系(sibling-sibling)。对于1个AS节点而言，在与其provider或peer交换路由信息时，会输出自己本地的或是从其customer和sibling学习到的路由，但不会输出从其provider或peer学习到的路由；而与其customer或sibling交换路由信息时，会输出任意类型的路由(本地的或是从其customer，provider，peer和sibling学习到的路由)。

1.1  问题描述

BGP路由收敛过程中的瞬态故障如图1所示，其中，节点5是目的节点。若链路(2 5)出现故障断开，则节点2会向它的其他邻居节点，即节点1与节点4发送路由撤销消息，撤销其已经失效的到达目的节点的最佳路由(2 5)。对于节点4而言，在收到来自节点2的路由撤销消息后其路由表为空，即它与目的节点之间失去连接，导致数据丢失。虽然在BGP路由收敛过程结束后，节点4的路由表中存在新的到达目的节点的最佳路由(4 2 1 3 5)，但在收敛过程中，其无法与目的节点5保持持续的连通性。

图1  BGP瞬态故障实例

Fig. 1  An example of BGP transient failure

为了解决上述瞬态故障，本文提出了一种域间网络保护路由模型。与现有研究域间网络可恢复性的工作(恢复路由模型指代这类研究工作)相比，保护路由模型能够确保在BGP路由收敛过程中AS节点之间的数据传输不中断。

1.2  模型定义

对于任意一个AS节点d∈V，是以节点d作为目的节点的路由信息图，其中，。是一个有向无环图。虽然对于任一源AS节点，其路由表中可能存在多条路由到达目的节点d，但根据BGP协议，该节点只能挑选1条路由作为最佳路由转发数据，其路由表中剩余的路由被称为后备路由。当网络出现链路故障时，本文将利用这些后备资源实现AS节点之间无中断的数据传输。

对于任意一对AS节点，为源节点s到目的节点d的路由信息图，其中，。是一个有向无环图。在中仅有1条最佳路由，若存在其他路由则被设为后备路由。

在源节点s到目的节点d的最佳路由上，某条链路出现的故障定义为f，f=(i，j)表示最佳路由上节点i与节点j之间的链路出现故障，其中节点i称为故障链路的直接上游节点。从节点i的路由表中删除因为链路故障而失效的路由，则得到。

定义1(恢复路由) 对于任一AS节点对，若源节点s到目的节点d的最佳路由上的任意一条链路发生故障f，在BGP路由收敛过程结束后，节点s与d之间仍然存在1条新的可达路由，则称是可恢复的(resilient)，即节点s是可恢复的。

定义2(保护路由) 对于任一AS节点对，若源节点s到目的节点d的最佳路由上的任意1条链路发生故障f，在BGP路由收敛过程中，总是在故障链路直接上游节点i的路由表中存在另一条后备路由，即在中存在另一条路由，使得节点s到d可达，则称是受保护的(protected)，即节点s是受保护的。

若故障链路的直接上游节点拥有后备路由，则保护路由模型能够保证在BGP收敛过程中，源节点s到d的数据传输不丢失，即保护路由避免了收敛过程中出现的瞬态故障。注意：当选取路由为节点s转发数据时，该路由对于节点s而言可能并不遵循“valley-free”约束。但由于这些后备路由仅在BGP收敛过程中被使用(使用时间比较短)，当收敛过程结束后，各个AS节点将使用其新的遵循策略约束的最佳路由转发数据，因此不会对某些AS节点的商业利益产生太大影响。

定义3 对于每一个AS节点，若是可恢复的或是受保护的，则称是可恢复的或是受保护的。

定义4 对于每一个AS节点，若是可恢复的或是受保护的，则称图G是可恢复的或是受保护的，即整个域间网络是可恢复或受保护的。

1.3  模型示例

恢复路由和保护路由实例如图2所示，图中共有4个AS节点，其中节点对<1 2>，<1 3>，<2 4>和<3 4>之间都是provider-customer的关系，<2 3>之间为peer-peer关系。

对于R¹而言，由于节点2和3仅有1条路由到目的节点1，若它们最佳路由上的链路出现故障，则2个节点都不能到达目的节点，所以，与既不是可恢复的也不是受保护的。节点4的最佳路由是(4 2 1)，若其中的链路(2 1)断开，则BGP收敛结束后(4 3 1)将作为节点4的最佳路由，确保其到目的节点1可达。根据定义1，是可恢复的。但在BGP收敛过程中，节点4最初并不知道(2 1)链路已经断开，它仍然向节点2发送数据包直到它收到来自节点2的撤销路由消息后才停止发送。由于(2 1)链路已经断开，节点2又没有后备路由到达目的节点1，则节点2将会丢弃来自4的数据包，导致节点4和1之间出现了数据丢失现象，因此是可恢复的但不是受保护的。结合1.2节中的定义3，可以得出R¹既不是可恢复的，也不是受保护的。R²和R³与R¹情况类似，既不可恢复也不受保护。

对于R⁴而言，由于节点1，2，3均有后备路由到达目的节点4，所以当节点最佳路由上的任意链路断开时，节点都可以选择后备路由转发数据，保证数据传输不中断。故R⁴是受保护的。

图2  恢复路由和保护路由实例

Fig. 2  An example of resilient routing and protected routing

1.4  模型分析

属性1 在BGP路由收敛过程中，若故障链路的直接上游节点拥有后备路由，则保护路由模型能够保证节点之间的数据传输不发生中断且不会因为选取后备路由转发数据而产生路由环路。

证明：在收敛过程中，若故障链路的直接上游节点拥有到达目的节点的后备路由，则该节点使用后备路由转发数据，其他源节点仍然使用其原有最佳路由转发数据，这保证了节点之间的数据传输不发生丢失。

保护路由模型不会产生的路由环路现象如图3所示，其中，目的节点为d。当链路(b d)出现故障时，链路的直接上游节点b将会选择来自其邻居节点c的后备路由转发数据。假设节点b在选取后备路由转发数据时会产生路由环路，则只可能出现如下2种情况：一种路由环路是由于选取来自节点c的后备路由所产生的(图3(a))；另一种路由环路出现在节点c到目的节点d的最佳路由上(图3(b))。

对于图3(a)所示的情况，当节点c将其到达目的节点的最佳路由输出给节点b时，保护路由模型要求节点b在更新路由表之前，首先检查自己是否是上的1个节点(是1个AS节点序列)。若节点b是路由上的1个节点，即节点c是通过b转发数据到目的节点(c是b的上游节点)，则节点b不更新自己的路由表并忽略来自c的路由信息；反之，节点b将根据节点c的最佳路由更新自己的路由表信息，c是b的下游节点。通过这个操作，保护路由模型确保了AS节点路由表中的所有路由不存在环路。因此，当AS节点选择后备路由转发数据时，不会产生如图3(a)所示的路由环路现象。

图3  保护路由模型不会产生的路由环路现象

Fig. 3  An example to illustrate that routing loops cannot be created by protected routing model

对于图3(b)所示的情况，最佳路由是节点c基于“valley-free”及“customer-preference”策略，从其路由表中挑选出来的最短路由。由于节点c在更新其路由表信息时，类似于节点b，也需重复上述路由检查操作以确保其路由表中的路由不存在环路，因此，节点c的最佳路由不可能存在环路，图3(b)所示的路由环路现象不会发生。

综上所述，在BGP路由收敛过程中，保护路由模型在利用AS节点路由表中的后备路由实现保护路由时，不会产生路由环路。

另一方面，由于链路故障，AS节点之间需更新路由信息，重新计算最佳路由。在路由收敛过程中，AS节点之间可能会因为更新路由而导致数据传输出现短暂的环路。保护路由模型能够避免的路由环路现象如图4所示，当链路(3 4)出现故障后，节点3向它的2个邻居节点1和2发送路由撤销消息，告诉邻居它要撤销路由(3 4)。节点2在收到撤销消息后，立刻选择(2 1 3 4)作为新的最佳路由转发数据，而节点1则选择(1 2 3 4)作为新的最佳路由，故而在节点1与2之间形成了短暂的路由环路并导致数据传输中断。为了解决这种BGP路由收敛过程中出现的环路问题，保护路由模型在AS节点的更新消息中引入根源信息(root cause information)^[4]。

属性2 在BGP路由收敛过程中，保护路由模型能够解决(因链路故障)AS节点之间更新路由信息而形成的数据转发环路。

证明： 保护路由模型在AS节点的路由更新消息中引入根源信息。在BGP路由收敛过程中，如果某个AS节点收到其邻居发送的包含根源消息的路由撤销消息，则该节点不仅知道其邻居节点的最佳路由失效，还能识别出其他与这条失效链路相关的路由并将它们从路由表中删除。例如在图4中，如果节点3在路由撤销消息中包含根源消息(即链路(3 4)出现故障失效)，那么当节点1和2收到来自3的撤销消息时，不仅知道路由(3 4)被撤销，而且还知道引起路由撤销的原因是链路(3 4)出现故障失效了，因此，节点1和2将会从各自的路由表中删除与链路(3 4)相关的所有路由，即除了删除它们原有到达目的节点4的最佳路由，还将分别删除路由(1 2 3 4)和(2 1 3 4)，这样就可以避免图4所示的路由环路现象。

图4  保护路由模型能够避免的路由环路现象

Fig. 4  An example to illustrate that routing loops can be avoided by protected routing model

2  域间网络路由重构

由于AS节点路由表中的后备路由信息是实现保护路由的关键，因此，利用当前互联网完备的AS-level网络拓扑结构，重构AS节点的路由表信息是评估现有域间网络可保护程度的基础。

2.1  域间网络拓扑

本文的互联网AS-level网络拓扑数据是通过对3700个不同自治系统AS节点里的992 000个P2P用户主机的路由数据进行测量而获取的^[13]。这是目前测量互联网AS-level网络拓扑结构最大的路由数据集，它有541 023 742条测量结果包含约62亿数据跳转。因此利用这个信息量丰富的拓扑结构数据集，能够构建出更加完备的域间网络AS节点路由表。

在商业关系的约束下，AS节点在网络拓扑中的层次一般都处在其所有的提供商(provider)的层次之下。本文根据每一个AS节点连接的客户(customer)数目对网络拓扑进行分层^[14]，每层AS节点的数目如表1所示。网络的第1层(Tier-1)由当前已知的9个AS节点组成，即AS174，AS209，AS701，AS1239，AS2914，AS3356，AS3549，AS3561和AS7018，这9个AS节点是顶层服务提供商，它们只为其他AS节点提供数据传输和转发服务，而不作为其他AS节点的客户；第2层(Tier-2)是由客户数目大于50的AS节点组成；第3层(Tier-3)AS节点的客户数目大于5但小于等于50；第4层(Tier-4)则是由客户数目小于等于5的AS节点组成。

表1  不同Tier上的AS节点的统计信息

Table 1  Statistics information of AS nodes at different Tiers

通过深入分析数据集可以发现：在Tier-4中存在很多stub AS节点和连接度为1的AS节点。Stub AS节点不为其他AS节点提供数据转发服务，它们一般只位于AS路由的最后一跳(即只作为目的AS节点)，不会对保护路由产生影响；而连接度为1的AS节点其路由表中不存在后备路由，不能实现保护路由，所以在本文的实验数据中会忽略这2类AS节点。删除这2类AS节点后，网络拓扑的分层统计结果如表2所示。

表2  不同Tier上的无stub AS节点和连接度为1的AS节点的统计信息

Table 2  Statistics information of AS nodes at different Tiers after pruning stub ASes and 1-degree ASes

2.2  域间网络路由重构

对于某个目的节点d而言，首先，根据文献[8]中提出的算法计算每个源节点到目的节点d的最佳路由，然后每个源节点根据BGP路由输出策略将自己的最佳路由输出给其邻居节点，完成整个域间网络路由信息R^d的重构。具体实现过程如下。

算法1 目的节点d的路由信息R^d重构算法

输入：目的节点d

输出：R^d

For 每一个源AS节点s

计算之间的最佳路由；

End

For 每一个源AS节点s

For 节点s的每一个邻居节点k

根据BGP路由输出策略，节点s将其到最佳路由输出给邻居节点k；

If 节点k不是上的一个AS节点

#节点k更新自己的路由信息

；

添加P到节点k的路由表中；

End

End

End

3  域间网络保护路由的评估

当网络拓扑结构出现变化时(链路故障或节点失效)，保护路由模型利用AS节点路由表中已经存在的后备路由资源，确保在BGP收敛过程中，AS节点之间的数据传输不发生中断。本节将在重构的AS-level域间网络路由信息的基础上，评估当前互联网的可保护程度，从整体上认知整个网络的可靠性。

3.1  评估参数

1) 后备资源比率。AS节点路由表的后备路由资源是实现保护路由的基础。因此对于某一个R^d，首先评估拥有后备路由的源AS节点在整个域间网络AS节点中所占的比例。

其中：N_B为拥有后备资源的源AS节点(∈V_d\d)的数目；N_AS为所有源AS节点(∈V_d\d)的数目。

2) 受保护比率。对于某一个R^d，根据保护路由的定义计算受保护的源AS节点在整个域间网络AS节点中所占的比例。该值可以评估当以某个AS节点作为目的节点时，整个域间网络(即互联网)的可保护程度。

其中：N_P为受保护的源AS节点(∈V_d\d)的数目。

3.2  评估结果

本文所采用的互联网AS-level拓扑结构图共包含6 979个AS节点(只关注non-stub AS节点)。对于每一个AS节点，首先计算路由信息R^d，然后根据3.1节中的评估参数对整个域间网络的可保护程度进行评估。

3.2.1  后备资源比率

对于每个R^d，首先评估拥有后备路由资源的源AS节点所占的比例，其结果如图5所示。从图5可以看出：对于任一R^d，超过90%的源AS节点都拥有到达目的节点的后备路由，这一结果充分说明本文提出的保护路由模型在现有互联网上具有可行性。在BGP路由收敛过程中，可以利用这些已经存在的后备路由资源实现保护路由(无需计算和传输额外路由)，确保AS节点之间无中断的数据传输。

图5  拥有后备路由的源AS节点所占的比率

Fig. 5  Ratio of source AS nodes with backup paths

虽然给定R^d时，大部分源节点都拥有到达目的节点的后备路由，但这并不能保证这些节点都是受保护的。因为对于某一源节点而言，其到达目的节点的最佳路由是由一系列AS节点组成的，即最佳路由是AS节点序列，根据定义2，当且仅当此序列上的每个AS节点都拥有到达目的节点的后备路由时，才可以判定该源节点是受保护的。因此，以后备路由为基础，首先判断源AS节点是否受保护，进而评估当前域间网络的可保护程度。

3.2.2  域间网络可保护程度

对于某个目的节点d，根据定义2，首先对每一个源AS节点s()，判断当s到d的最佳路由上的任意一条链路出现故障时，是否受保护(即源节点s是否受保护)；然后计算R^d的受保护比率；最后评估整个域间网络的可保护程度。其结果如图6所示。从图6可以看出：绝大部分的R^d (大于5 200个R^d)拥有较高的受保护比率(保护比率大于0.85)，即在不增加BGP路由器额外开销的基础上，仅利用当前AS节点路由表中已经存在的后备路由资源，就可以确保在BGP路由收敛过程中R^d中85%以上的源AS节点实现保护路由，即无中断的数据传输。

图6  域间网络AS节点受保护率统计柱状图

Fig. 6  Histogram of protected ratio for AS nodes in inter-domain network

由图6可以看出：某些R^d的受保护率比较低，这是因为其目的节点大都处于Tier-4且连接度都非常小(仅有1个provider或customer)，因此其他大部分源AS节点仅拥有1条路由到这些目的节点，这就导致R^d的受保护率比较低。然而，由于这些节点大都处于域间网络比较低的层次(Tier-4)，大多数节点在网络中扮演customer的身份，它们很少为其他AS节点转发数据，不是网络的关键传输节点，所以，不会对整个域间网络的可保护程度造成太大的影响。

3.2.3  不同Tier上AS节点的受保护程度

根据AS节点所拥有的customer数量将其划分到域间网络不同的Tier上。不同Tier上AS节点的受保护比率如图7所示。从图7可以看出：AS节点所处的层次越高，其受保护的比率越大，例如Tier-1和Tier-2上节点的受保护比率都在0.75~1.00之间。这是由于与Tier-4上的AS节点相比，Tier-1和Tier-2上的节点具有更大的连接度，即其他节点拥有多条后备路由到这些目的节点。因此，域间网络中层次高的AS节点具有更高的受保护比率。

在域间网络中，Tier-1和Tier-2上的AS节点大部分扮演服务提供商的角色，为了保证好的服务质量(数据传输不发生中断)，在线实时网络应用要求它们具有较高的受保护率。由图7可以看出：本文提出的保护路由模型，利用AS节点路由表中已经存在的后备路由资源就能够为Tier-1和Tier-2上绝大部分节点提供有效保护，即实现无中断的数据传输。

图7  不同Tier上AS节点受保护率统计柱状图

Fig. 7  Histogram of protected ratio for AS nodes at different Tiers

4  结论

1) 提出了一种域间网络保护路由模型，仅利用BGP路由表中已经存在的后备路由资源，在网络出现链路故障，BGP进入收敛过程后，能够很好地保证AS节点之间数据传输不发生中断，消除瞬态故障。

2) 评估了当前域间网络的可保护程度，域间网络中层次较高的AS节点具有更高的受保护比率。

3) BGP路由输出策略也会影响到域间网络的可保护程度，本文进一步的工作将研究如何松弛路由输出策略，以提高AS节点的受保护比率。

参考文献：

[1] PEI Dan, ZHAO Xiaoling, WANG Lan, et al. Improving BGP convergence through consistency assertions[C]//Proceedings of IEEE INFOCOM. New York: IEEE Press, 2002: 901-912.

[2] Subramanian L, Caesar M, Ee C T, et al. A next generation inter-domain routing protocol[J]. ACM SIGCOMM Computer Communication Review, 2005, 35(4): 13-24.

[3] Abuzneid A, Stark B J. Improving BGP convergence time via MRAI timer. novel algorithms and techniques in telecommunications and networking[M]. New York: Springer, 2010: 105-110.

[4] PEI Dan, Azuma M, CHEN Jiwei, et al. BGP-RCN: Improving BGP convergence through root cause notification[J]. Computer Networks, 2005, 48(2): 175-194.

[5] WANG Feng, GAO Lixin. A backup route aware routing protocol–fast recovery from transient routing failures[C]// Proceedings of IEEE INFOCOM Mini-Conference. Phoenix: IEEE Press, 2008: 2333-2334.

[6] WANG Feng, GAO Lixin. Path diversity aware inter domain routing[C]//Proceedings of IEEE INFOCOM. Rio de Janeiro: IEEE Press, 2009: 307-315.

[7] Kushman N, Kandula S, Katabi D, et al. R-BGP: Staying connected in a connected world[C]//Proceedings of the 4th USENIX Conference on Networked Systems Design and Implementation. Cambridge: USENIX Press, 2007: 1-14.

[8] WU Jian, ZHANG Ying, MAO Z M, et al. Internet routing resilience to failures: analysis and implications[C]//Proceedings of the 3rd ACM Conference on Emerging Network Experiment and Technology. New York: ACM Press, 2007: 1-12.

[9] HU Chengchen, CHEN Kai, CHEN Yan, et al. evaluation potential routing diversity for Internet failure recovery[C]// Proceedings of IEEE INFOCOM Mini-Conference. San Diego: IEEE Press, 2010: 1-5.

[10] HU Chengchen, CHEN Kai, CHEN Yan, et al. A measurement study on potential inter-domain routing diversity[J]. IEEE Transactions on Network and Service Management, 2012, 9(3): 268-278.

[11] Kong K, GAO Lixin, Guerin R, et al. On the feasibility and efficacy of protection routing in IP networks[J]. IEEE/ACM Transactions on Networking, 2011, 19(5): 1543-1546.

[12] GAO Lixin. On inferring autonomous system relationships in the Internet[J]. IEEE Transactions on Networking, 2001, 9(6): 733-745.

[13] CHEN Kai, Choffnes D, Potharaju R, et al. where the sidewalk ends: extending the Internet as graph using trace routes from P2P users[C]//Proceedings of the 5th ACM Conference on Emerging Network Experiment and Technology. Rome: ACM Press, 2009: 217-228.

[14] Oliveira R, PEI Dan, Willinger W, et al. In search of the elusive ground truth: The Internet’s as-level connectivity structure[C]// Proceeding of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. Annapolis: ACM Press, 2008: 217-228.

(编辑  赵俊)

收稿日期：2014-08-20；修回日期：2014-11-09

基金项目(Foundation item)：国家自然科学基金资助项目(61272459，61203039，61272459，61170245，61221063)；国际合作“111”引智计划项目(B06002)；国家高技术研究发展计划(863计划)项目(2013AA013501)(Projects (61272459, 61203039, 61272459, 61170245, 61221063)  supported by the National Natural Science Foundation of China; Project (B06002) supported by 111 International Collaboration Program of China; Project (2013AA013501) supported by the National High Technology Research and Development Program (863 Program) of China)

通信作者：陈曦，博士，副研究员，从事网络路由优化与无线传感器网络研究；E-mail：bjchenxi@mail.tsinghua.edu.cn