一种按需域间路径构建方法＊

柳立言

（宁夏师范学院教育技术中心，宁夏 固原75600）

1 引言

在域间路由中，边界网关协议BGP（Border Gateway Protocol）作为当前Internet域间路由的事实标准，节点可以决定选择和转发哪些路径，但是节点的可用路径取决于下游节点的决策，节点无法对此过程进行控制，故往往不能获得其真正所需的路径。在BGP中，尽管每个节点可能拥有多条备选路径，但是协议要求每个路由器仅仅选取一条最优路径通告至邻居节点，导致了某些自治域不能获得自己需要的路径。这种情况通过图1的例子可以看出，在图1中，如果源端S希望能够拥有到达目的端D 的两条不相交的路径，一条作为传输路径，一条作为备份路径，在S的路由表中无法找到这样的两条路径。事实上，这样的路径是存在的，比如，SBCEFD与SAD，SBCEFD与SAD 不与网络中任何一个节点的本地策略相冲突，由于BGP中节点仅仅转发一条最优路径，在节点C路径CEFD被屏蔽了。

Figure 1 BGP routing to a destination node D图1 BGP路由至目标节点D

为了解决BGP可控性不高的问题，最近的研究出现了几种替代BGP的备选方案，包括源路由［1～6］、overlay网络［7］以及多路径 路由［8～11］。在源路由中，端用户拥有全网的拓扑视图，可以自主选择报文传输的路径，通过在报文的头部加入报文路径的方式指示中间节点将其转发至合适的下一跳。在overlay网络中，报文可以穿越中间节点提高性能或者可靠性。多路径路由的研究刚刚起步，其主要思想为增加通告的路径信息量，直接在底层网络上构建多条路径。但是，当前替代BGP的这几种方法都存在明显的问题：源路由的实现代价较大，可行性没有得到验证；overlay网络的可扩展性制约了其实际的应用；多路径路由用途较为单一，比如只是提高可靠性或者提高传输效率等，无法满足用户差异化的路径需求。

针对域间路径选择过程不可控的问题，本文提出了一种按需的域间路径构建方法，以增强域间路由的可控性。为了简便起见，在以下的讨论中，用源端表示报文的发送方，也是路径的发起者；用目的端表示报文的接收方，也是路径的终点。靠近报文源端的节点称为上游节点，靠近报文接收方的节点称为下游节点。比如在图1中，S是上游节点，D是下游节点。本文解决方案基于当前域间路由的如下特性［8］：

（1）BGP协议提供的基本路径满足大多数节点的需求；

（2）少数的节点有着特殊的路径需求，需要BGP提供个性化的路径服务，例如：Avoiding、Preferring以及Disjoint，其中，Avoiding常见于避开网络中某个恶意自治系统AS（Autonomous System）［12，13］，或者避开某条拥塞连接等。Preferring常见于希望优先通过［14］可信节点提供的路径。Disjoint常常用来提高网络可靠性，选择一条与已有路径最不相交的路径［6，7，11］，当前的 BGP 协议无法满足节点的个性化需求的主要原因为：BGP中每个节点的可用路径由下游节点决定，而其无法对下游节点的选路过程进行控制从而获取自身所需的路径。既然BGP协议能够满足网络中大多数节点的需求，本文在避免对BGP协议的逻辑结构进行太大改变的基础上，对BGP协议进行扩展。如果上游节点希望下游节点根据其需要选路，则在路径选择前上游节点需要将路径需求提交至下游节点。主要思路如下：采用基本的BGP协议保证源端与目的端的可达性，在此基础上，需要构建特殊路径的源端将路径构建请求发送至目的端，由目的端发起一个与BGP相似的网络收敛过程协助源端构建满足需求的路径。

本文主要贡献如下：（1）对BGP［15］协议扩展提出了基于策略的路由协议 P－BGP（Policy－based BGP）。P－BGP与BGP最大的区别在于在其通告中嵌入了更多的策略信息，嵌入的策略用来指导中间节点选择满足源端期望的路径。

（2）通过多次的P－BGP收敛过程构建了按需的域间路径，并且通过实验验证了其具备良好的性能。相比于当前的其他BGP替代方案，本文方法能够构建满足用户需求的路径，并且理论上路径的构建数量可以任意多。除此之外，本文方法仅仅对BGP进行了简单修改，易于实现。

本文结构如下：第2节对当前域间路由的相关工作进行了总结；第3节提出了P－BGP；第4节阐述了按需路径构建方法的主要思想以及实现方式；第5节为实验以及性能分析；第6节总结全文并指出未来工作。

2 相关工作

2.1 当前的域间路由

BGP协议［15］是当前域间路由的事实标准，具有以下几个特征：

（1）基于目标：BGP通告地址块的可达信息，并且每个路由器根据报文目的地址最长前缀匹配发送报文。不同源端发送的报文通过同一个路由器后将会采用同样的下游路径。

（2）单路径路由：一个路由器从一个邻居至多学习到一条最优路径，并且只能选择向其他邻居通告一条最优路径。这个特征限制了BGP通告的路径的数量，限制了路由的适应性。

（3）路径向量协议：与连接状态协议泛洪拓扑信息不同的是，BGP是一个路径向量协议，路由器只能获得由其邻居通告的路径。BGP的这个特征通过牺牲某些路径的可达性提高了协议的可扩展性。

（4）基于本地策略：每个域采用某些策略来决定选取哪条BGP路径。可用的路径依赖于下游路由器的策略组合。这个特征限制了每个AS有过多的路径可以选择。

选择和输出BGP路由的本地策略主要依赖于邻居域间的商业关系。最著名的商业关系是文献［16］中阐述的服务提供商－顾客（Provider－Customer）、对等（Peer）以及兄弟（Sibling）关系。在服务提供商－顾客的关系中，顾客为传输服务向服务商支付报酬。一般来说，服务商将从顾客处获取的路径向所有的邻居通告，但是顾客仅仅将从服务商处获取的路径向自己的顾客通告。在端对端的关系中，两个AS发现为对方的顾客传送流量对自身都有益，一般不收取传输服务费。对等关系下，一般从一个对等端获取的路径仅仅被通告至本端的邻居。兄弟AS一般属于同一个组织，比如一个大的互联网服务提供商ISP（Internet Service Provider），他们互相提供传输服务而不涉及商业关系。一旦从多个邻居收到同一个地址前缀的通告，AS倾向使用的路径优先级为：顾客提供的通告、兄弟关系通告、对等关系通告、提供商提供通告。

2.2 源路由

为了构建真正满足用户需求的网络路径，在过去的几年中，部分研究者提出了源路由来提供更好的适应性［1～6］。在源路由中，源端确定到达目的端的端至端路径。源端发送的数据报文中包含了报文要经过的路径的每一跳，网络中的中间节点根据报文的下一跳指示将报文发送至正确的下一跳。尽管源路由扩大了选路的适应性，但要在网络中部署存在几个问题：

（1）中间节点缺乏对数据的控制：在源路由中，中间节点仅仅按照报文携带的路径下一跳将报文发送至下一跳，缺乏控制流量的措施，使中间节点很难基于自身的商业关系选择路径，这将导致网络服务商不愿在网络中部署源路由，极大地阻碍了源路由的应用。

（2）可扩展性：源路由需要获取全部的网络拓扑。拓扑数据的快速更新将是一个难点，由于网络的规模越来越大，必须将节点以及连接的变化情况快速地发送至网络的每个边界节点，这是一个极大的挑战。

2.3 Overlay网络

在overlay［7］网络中，几个节点在当前Internet上形成一个虚拟拓扑。当底层网络的直接路径存在问题时，发送节点可以将流量发送至中间节点，由中间节点转发至目标节点。尽管overlay有助于解决直接路径的若干问题，但还不能大规模应用在网络中，主要原因如下：

（1）数据层过载：通过中间节点转发数据增加了网络的延时，并且消耗了网络带宽以及节点的处理能力。数据包需要通过封装的方式进行传送，消耗了额外的带宽。

（2）探测过载：为了补偿对底层网络的不可见，overlay网络一般通过探测的方式推算底层路径的性质。当前没有适合大规模网络的探测方式，难以在网络中得到部署。

2.4 域间多路径路由

由于BGP路由的局限性以及源路由和overlay的无法大规模实施，近年来有研究者将目光投向了域间的多路径构建，期望通过在底层网络上直接构建多路径的方式提高路由的服务质量。当前域间多路径的构建方式主要有两种：不改变BGP通过其他进程构建多路径［8］和对BGP进行扩展使其一次通告多条路径［11］。域内多路径路由MIRO（Multi－path Interdomain Routing）［8］和 D－BGP［11］是这两种方案的典型代表。

MIRO允许节点在使用BGP默认路由的基础上通过协商的方式构建节点间的隧道，使节点可以对流过其中的报文流进行更多的控制。MIRO的最大优点是不用对BGP协议进行修改，但是不能保证满足用户期望的路径总能被发现，并且因为采用了隧道方式传送报文，消耗额外的网络资源。DBGP提出允许BGP通告除基本路径外的一条与基本最优路径最不相交的备份路径来提高路由应对错误的能力，但是其附带的备份路径只能够作为最优路径的备份，无法用来进行并发传输。

事实上，在当前的网络下，BGP提供的最优路径能够满足绝大多数用户的需求，只有少部分用户需要构建特定需求的路径［8］。在全网范围内统一采用多路径的方式是一种巨大的浪费，按需的路径构建是一种更加合理的方法，存在特定需求的节点按需构建特殊路径，其他节点采用基本的BGP路径。

3 P－BGP及其性质

作为按需路径构建方法的准备工作，本节对当前的BGP协议进行扩展提出了P－BGP。P－BGP的主要特征为在路径通告中增加了更多的策略项，这些添加的策略项称为S＿P策略项。目的端可以在路径通告时将选路的要求添加到路径通告中的S＿P项中，指导中间节点选择满足需求的路径进行通告。

3.1 BGP决策分析过程

由于P－BGP的具体实现涉及对BGP决策过程的修改，在提出具体的P－BGP方案前，首先对BGP的路径选择过程进行阐述。文献［17］对ISP中常用的BGP决策过程使用的策略进行了总结。一个ISP中的BGP路由器拥有多个到达目的地址的路径，BGP路由器需要根据策略选择一条最优的路径转发给邻居节点。如果没有策略的存在，路由器将选择一条最短的路径转发至邻居。但是，为了使得网络管理员能够控制路径选择过程，路由通告中加入了一些特殊的属性，允许一个路由器根据这些属性进行路径的选择。这个过程就是决策过程，包括对一系列属性的对比。路由器依照表1的次序对候选路径依次对比下去。如果候选路径拥有不同属性值，路由器选择最能满足本地利益的那条路径。如果候选路径拥有相同的属性值，则路由器继续进行下一属性的对比，直到找到最优路径。比如，LocalPref属性作为决策过程的第一步，通过更改LocalPref属性，管理员可以选择一条不是最短的路径作为最优路径。MED属性通常用在两个拥有多条连接的AS间，显示应当使用哪条端连接。BGP使用严格的排序过程使得网络策略的表达更加清晰明了。

Table 1 The BGP decision attribute表1 BGP决策属性

文献［17］总结了影响ISP策略的几种因素。（1）商业关系：常见的商业关系为服务提供商－顾客，对等以及兄弟关系。商业关系是ISP决策过程中最重要的一项因素。（2）流量工程：ISP为了调整其域内的流量走向以达到较好的网络利用率，其通过设定BGP选路参数的方式调整网路流量状况。（3）可扩展性：为了限制网络路由表的大小或者是避免路由振荡，网络管理员可能将某些路径过滤或者修改路由参数。（4）安全：为了保证路由的安全，网络管理员需要将无效的路径删除，阻断DDoS攻击等，一般都是通过调整路由参数来实现这些目标。

3.2 P－BGP

P－BGP与BGP最大的区别在于在路径通告中添加了更多策略项，在P－BGP中有两种策略可以添加到S＿P项中：路径选择策略和路径取消策略。路径选择策略用来指导中间节点选择何条路径进行通告；路径取消策略用来指导节点有选择地删除路径。表2前三项表示P－BGP中可以包含的三种路径选择策略，表2的最后一项为P－BGP中包含的路径删除策略。在当前的P－BGP版本中暂时确定了这四种策略，在后续的研究中可以添加更多的策略。

Table 2 Path notices contained in the policy表2 路径通告中包含的策略

由于在路径选择过程中涉及更多的策略，PBGP中间节点对路径通告的处理过程也与BGP不同。在BGP中，节点如果收到路径通告，则根据表1的决策过程选择一条最优的路径通告给邻居节点。在P－BGP中，最优路径不单纯由本地策略决定，而是由本地策略与S＿P策略共同决定。为了将S＿P策略添加至路径选择过程中，同时又保留中间节点对路径的控制能力，我们将S＿P策略在路径选择过程中的优先级设定为在表1中的第一个属性后、其他六个属性前，即在P－BGP路径选择过程中参考的属性顺序为：LocalPref、S＿P属性、AS path length、Origin type、MED、eBGP－learned over iBGP－learned、IGP cost、Router ID。

性质1 路由节点有部署P－BGP的动机。

说明 通过对表1以及影响ISP策略的几种因素的分析可以看到，ISP基于以下的利益关系确定通告路径：本地的利益、下游节点的利益以及上游节点的利益。LocalPref作为最常用的属性，较多地被ISP的管理者用来控制路由，代表域的本地的利益需求。我们认为，AS path length属性综合考虑了下游节点以及上游节点的利益：AS依据AS path length属性选择最短的路径，AS出于为下游节点的利益考虑，因为其采用最短路径作为路径性能的衡量标准，认为最短的路径具备最好的性能，最能满足下游节点的需求；然而，AS path length属性又是由下游节点设定的，下游节点在将路径通告给邻居时可以将AS path length值设定为一个对自身有利的值。MED属性是AS为上游节点的利益考虑，采用有利于上游节点的路径进行传送。从路径选择的决策过程可以看出，在决策过程中本地的利益需求被放在首位，上游节点的利益在不损害下游节点的利益基础上能够得到满足。我们将S＿P属性添加到BGP的决策过程中的第二项，使其位于 LocalPref属性后，AS path length属性前，仍然没有打破AS选路的利益顺序。LocalPref仍然处于决定过程的第一步，保证了中间AS对选路过程的绝对控制权，保证了本地的利益；如果S＿P属性代表了上游节点的利益需求，但是其值仍然由下游节点设定，没有打破AS选择路径的利益顺序，S＿P属性能够能到AS的支持，路由节点有部署P－BGP的动机。

性质2 P－BGP比BGP能够提供更加差异化的路径构建能力。

说明 如果P－BGP路径通告中的策略项都为空，则P－BGP退化为BGP。当策略项不为空时，能够构建满足不同需求的路径。因此，相比于BGP，P－BGP能够提供更加差异化的路径构建能力。

4 一种按需域间路径构建方法

本节基于多个P－BGP过程提出了按需的域间路径构建方法 OIPBM（On－demand Inter－domain Path Building Method）。

4.1 OIPBM主要流程

OIPBM的主要思想如下：采用现有网络的BGP协议保证网络的可达性，如果某个源端S需要构建通向目的端D的特殊路径，则S将路径的构建需求发送至D，由D发起一个全网的P－BGP收敛过程协助其完成特殊路径的构建。

Figure 2 OIPBM schematic diagram图2 OIPBM示意图

在OIPBM中BGP与P－BGP共存，但其相互独立，不相互影响，如图2所示。BGP保证网络的可达性，而P－BGP则负责网络中有特殊需求的节点间的特定路径构建。BGP过程通告网络的可达性信息，使得网络中需要构建特殊路径的节点间可以互相通信；在P－BGP中，构建符合源端需求的特殊路径，并且在路径构建成功后将网络中的冗余路径消除。在P－BGP中，需要构建特殊路径的源端将构建多路径的需求发送至目的端，请求目的端帮助其构建满足需求的路径；目的端为自身生成一个别名，将别名回复至源端，同时以别名作为目的地址发起全网收敛过程，将所需的路径构建策略添加到路由通告的S＿P选项中。等到该全网过程收敛，源端获得目的地址为目的端别名的满足要求的域间路径。由于采用了全网的收敛过程来协助源端构建满足要求的路径，在网络中产生了冗余路径，发起一个额外P－BGP收敛过程将网络中的冗余路由表项删除，源端将需要保留的路径发送至目的端，目的端发送带有S＿P策略的路径取消通告将网络中冗余路由表项删除。

按需域间路径构建方法处理流程如下：

（1）BGP全网信息通告，BGP的全网通告保证了网络的可达性。

（3）D收到源端S发送的路径构建请求后，为自己生成一个别名D′，将别名D′发送至S。

（4）D以D′为目的端生成新的网络可达性通告，并且将S所要求的路径构建策略嵌入到以D′为目的地址的路径通告的S＿P选项中，发起一个P－BGP收敛过程。

（5）中间转发节点选择和通告最优路径。在目的端为D′的P－BGP过程收敛后，如果S收到目的端为D′的路径，则S获得了满足其要求的路径。

（6）S将确定采用的路径通告至D，D以D′为目的端发起路径取消通告，并且将路径取消的策略嵌入到路径通告中，将网络中的冗余路径消除。

（7）S可以根据需要重复（2）～（6）的步骤构建任意数量的路径。

通过（1）～（7）的步骤，源端S可以收到目的端为D以及D′的路由表项。由于S已经知道D′为D的别名，因此其实际上拥有了到达D的满足要求的路径。S可以将构建的路径用作其希望的任何用途，不论是用作备份路径或者并发传输。

4.2 一个例子

现在通过图3的例子阐述按需路径的构建过程，S表示需要构建路径的源端，D表示路径的目的端。

曾任诺贝尔物理学奖评委主任的瑞典皇家学会爱克斯朋教授，在解密诺贝尔奖评选过程时坦言：这是一个“很令人不安的、没法再弥补的疏漏，赵忠尧在世界物理学家心中是实实在在的诺贝尔奖得主!”

Figure 3 BGP state diagram and OIPBM state diagram图3 BGP状态图以及OIPBM状态图

图3 a是BGP协议收敛后的网络状态，节点的路由表如图3所示，其中部分路由表项被省略了。节点C的本地策略为CEFD与CAD都不违背域的商业利益，但是从路径跳数考虑选择路径CAD。假设S需要向D发送大规模的实时数据，由于连接A－D的传输容量有限，路径SAD不能满足网络传输的要求，S希望另外通过一条不通过连接A－D的路径进行并发传输，但是S查询自身的路由表发现，路由表中的SAD以及SBAD两条路径都要通过连接A－D，不能满足实时数据传输的要求。下面以S构建不通过连接A－D 的路径为例阐述OIPBM的消息过程。

OIPBM中由D协助源端S选择一条不通过连接A－D的路径。由于BGP过程与P－BGP过程相互独立，且BGP过程已被大家所熟知，因此不对BGP收敛过程进行过多阐述，着重阐述P－BGP的消息过程。图3b给出了P－BGP中的网络消息顺序。（1）源端S与目的端D通信，S向D通报再次构建一条新路径p′的请求，并且标记构建策略为Avoiding（A－D）。（2）D 收到了源端S 的路径构建请求后，为自身重新生成一个别名D′，并且将D′回复至源端S。（3）以D′为目的地址发起新的PBGP收敛过程，并且在P－BGP通告的S＿P项中携带对新路径的策略Avoiding（A－D）。节点A收到目的端为D′的路径通告，发现新路径不愿意通过连接A－D，则A不转发任何路径。节点C收到目的端为D′的路径通告后，再根据按需域间路径构建处理流程的前五个步骤的选择最终决定了CEFD作为传输路径。（4）节点S在收到目的端为D′的路径P′＝SBCEFD′后，将P′向节点D 通报，请求删除网络中的冗余路径。（5）节点D发起冗余路由表项删除过程。生成目的端为D′的UPDATE通告，在通告的S＿P选项中添加路径删除的策略except（P′），将通告向全网分发。节点A收到路径取消通告后，将本地通向D′的路由表项完全删除，并向节点S发出路径取消通告，节点S将D′：SACFD′删除，保留路径D′：SBCEFD′。最终得到的网络状态如图3c所示。由于有了节点D的预先通知，节点S知道D′是节点D 的别名，因此，节点S实际上拥有了一条不通过连接A－D 到达目标节点D的路径SBCEFD′。

4.3 几个关键问题

4.3.1 别名的表示

从3.1节的描述中可以看到，别名在OIPBM中发挥了极其重要的作用。OIPBM采用别名寻找通向目标地址的满足要求的路径。我们可以对当前的IP地址进行扩充以表示别名，在IP地址后附上一个数表示该地址的第几个别名，比如，用152.172.33.44（3）表示地址152.172.33.44的第三个别名。在构建了满足要求的要求路径后，可以仿照MIRO的思路在源端与目的端间构建隧道。或者随着多路径要求的增多，可以对IP报文以及路由表的格式进行修改，为其增加更多的位数，使其能够支持别名。

4.3.2 冗余路由表项的消除

在目的地址为D′的路由过程收敛后，S实际上拥有了到达节点D 的特殊路径P′1，P′2，…，P′n。然而造成极大浪费的是，因为采用了一个全网的收敛过程来构建由S至D的路径，网络中产生了许多的额外路由表项，如果这些路由表项一直保留，随着网络多路径的增多必将导致路由表规模的无限扩大，影响路由表查找的性能。因此，在S至D′的路由过程收敛后，需要将网络中冗余的路由表项消除。OIPBM中采用了一个额外的全网收敛过程来消除网络中的冗余路由表项。S将确定使用的路径P′1，P′2，…，P′n告知节点D，节点D 发出带有S＿P策略的 UPDATE通告，将策略can＿exc（D′，P′1，P′2，…，P′n）添加到通告中的S＿P策略中，每个节点收到带有策略的路径取消通知后，将本地目标地址为D′但不属于P′1，P′2，…，P′n的路径删除。通过这种方式，仅仅保留源端选择的那些路径，将网络中的冗余路由表项全部删除。然而一个重要的问题是：如果在冗余路由表项消除的过程中发生了路径失效，OIPBM是否能保证其正确性。

路径的失效可能发生在三个时刻：（1）冗余消除通告从S发送至D的过程中；（2）D发出冗余消除通告后的已更新节点；（3）D发出冗余消除通告后的未更新节点。下面以图3b为例对这三种情况分别讨论：

（1）如果冗余消除消息在从S发送至D 的过程中发生了路径失效。节点D发出冗余路径删除信息，节点S失去了最优路径，重新向D发出一个路径构建请求，并且在通告中附上失去了到达D′的路径，则节点D重新发起目标地址为D′的收敛过程。

（2）如若失效发生在D已经发出冗余消除通告后的已更新节点。比如，在图3b中，当冗余更新消息处于节点A、B，且节点F、E、C已更新时连接C－E 失效，则C发出路径取消信息，节点A、B、C、S到达D′的路由表项全都删除，节点S失去到达D′的最优路径，S请求D重新构建。

（3）如若冗余消除消息处于节点A、C时发生了连接BC的失效，则节点B、S消去通向D′的路由表项，节点S失去了通向D 的最优路径，S请求节点D重新构建。

根据以上的讨论我们可以看到，如果在S发出了冗余消除消息后构建的路径发生了失效，则都要重新开始OIPBM的第二个以及第三个全网收敛过程。因此，OIPBM适合用于网络状况比较稳定、失效率不高的环境，Internet的主干网满足这个条件。

5 实验与分析

5.1 实验方案

评价OIPBM最理想的方法是在Internet上对其进行分析，但是这种方法的难度较大，因此我们在AS级别的拓扑上仿真OIPBM的性能，假设每个AS根据它和邻居间的商业关系选择和输出路径。每个AS作为一个节点对待。

实验采用三个年份（2005年、2007年和2009年）的AS级别拓扑分析网络规模增大对网络对多路径的影响，评价OIPBM的性能，实验拓扑来自于RouteViews［18］项目。为了推导AS间的关系，我们采用了Gao［16］的算法。AS拓扑和商业关系的关键特性在表3中给出。

Table 3 Experimental data set表3 实验数据集

5.2 选取不通过某些节点的路径

为了进行一个横向的对比，我们分别考察了BGP、源路由（采用source进行标记）、多路径路由（以MIRO为代表）以及OIPBM的表现，MIRO的设置如文献［8］中所示。图4给出了本实验的结果，其中后缀a1、a2以及a3分别表示避免网络中的一个、两个以及三个节点的情形。实验采用了文献［8］中所述的 Respect Export Policy作为 MIRO的选路方式，即节点认为符合其输出策略的每条路径都是等价的，节点在不违背其输出策略的前提下考虑路由通告中的策略进行路径选择，具体选择哪条路径由P－BGP通告中携带的期望信息决定。

Figure 4 Avoid node diagram图4 避免节点实验结果图

从图4中可以看到，在避免一个、两个以及三个节点的情况下，OIPBM的成功率都接近于源路由，远远超过多路径路由。特别是随着避免的节点数目的增多，多路径路由的成功率急剧下降，而OIPBM保持了平稳的下降趋势。我们认为，这是由网络中的节点连接度的分布情况决定的，在Internet中，少量的节点拥有最大的节点连接度［8］。BGP下的网络路径基本都通过这些大连接度的节点，一旦需要选择避免这些节点的备选路径，则MIRO通过协商的方式很难找到满足要求的备选路径。

5.3 选取最不相交的路径

网络中常用的另外一种选路策略为选取一条与最优路径不相交的路径作为备份路径，本文在MIRO、D－BGP以及OIPBM下实现了这个功能并将其结果进行了对比。MIRO中原有跳数为2～3跳，我们放宽对其的限制，将MIRO的跳数设定为10跳，以此结果下的成功率与OIPBM进行对比。

本文采用文献［11］中计算路径相交度的方法来度量两条路径的相似程度，计算方法如式（1）所示，结果越小表明两条路径越不相交，实验结果如图5所示。

Figure 5 Select a basic path and the disjoint path图5 选择一条与基本路径最不相交的路径

通过图5可以看到，即使在MIRO已经采用了很大的泛洪跳数的情况下，其选择一条最不相交路径的成功率仍然不如OIPBM。D－BGP性能介于MIRO与OIPBM之间，同样也没有OIPBM性能好。但是，随着网络规模的增大，MIRO、D－BGP以及OIPBM的性能都有较大的提高。

6 结束语

当前Internet路由的可控性不够，本文针对域间路由可控性不够的问题，提出了一种满足Internet要求的按需路径构建方式。首先在BGP路由通告报文中添加了策略信息对BGP协议进行扩展，扩展后的协议称为P－BGP。在P－BGP的基础上进一步提出了按需的域间路径构建方法OIPBM，OIPBM在空策略的P－BGP收敛的基础上，需要构建多路径的源端向目的端发出请求，由目的端协助其构建满足需求的多路径。OIPBM在不改变BGP逻辑正常路由过程的基础上实现了满足源端需求的BGP路径构建。

未来的工作包括扩大OIPBM的应用场景，与加强域内路由可控性的方案结合，构建一个可控的路由体系。

［1］ Zhu D，Gritter M，Cheriton D.Feedback based routing［J］.ACM SIGCOMM Computer Communication Review，2003，33（1）：71－76.

［2］ Kaur H T，Kalyanaraman S，Weiss A，et al.BANANAS：An evolutionary framework for explicit and multipath routing in the Internet［J］.ACM SIGCOMM Computer Communication Review，2003，33（4）：277－288.

［3］ Raghavan B，Snoeren A C.A system for authenticated policy－compliant routing［J］.ACM SIGCOMM Computer Communication Review，2004，34（4）：167－178.

［4］ Argyraki K，Cheriton D R.Loose source routing as a mechanism for traffic policies［C］∥Proc of the ACM SIGCOMM Workshop on Future Directions in Network Architecture，2004：57－64.

［5］ Yang X.NIRA：A new Internet routing architecture［C］∥Proc of the ACM SIGCOMM Workshop on Future Directions in Network Architecture，2003：301－312.

［6］ Godfrey P B，Ganichev I，Shenker S，et al.Pathlet routing［C］∥Proc of the ACM SIGCOMM 2009Conference on Data Communication，2009：111－122.

［7］ Andersen D，Balakrishnan H，Kaashoek F，et al.Resilient overlay networks［C］∥Proc of the ACM Symposium on Operating Systems Principles，2001：131－145.

［8］ Xu W，Rexford J.MIRO：Multi－path interdomain routing［C］∥Proc of the 2006Conference on Applications，Technology，Architectures，and Protocols for Computer Communications，2006：171－182.

［9］ Walton D，Retana A，Chen E，et al.Advertisement of mul－tiple paths in BGP［EB／OL］.［2012－12－17］.http：／／tools.ietf.org／html／draf－ietf－idr－add－paths－08.

［10］ Motiwala M，Elmore M，Feamster N，et al.Path splicing［C］∥Proc of SIGCOMM’08，2008：27－38.

［11］ Wang Feng，Gao Li－xin.Path diversity aware interdomain routing［C］∥Proc of the 28th IEEE International Conference on Computer Communications，2009：307－315.

［12］ Zlatokrilov H，Levy H.Area avoidance routing in distancevector networks［C］∥Proc of the 27th Conference on Computer Communications，2008：475－483.

［13］ Li Y，Gouda M G.The blocking option in routing protocols［C］∥Proc of the 28th IEEE International Symposium on Reliable Distributed Systems，2009：227－235.

［14］ Hu Nin，Zou Peng，Zhu Pei－dong.Based on the reputation mechanism of the inter－domain routing security coordination management approach［J］.Journal of Software，2010，21（3）：505－515.（in Chinese）

［15］ Rekhter Y，Li T，Hares S.RFC 4271，A border gateway

protocol 4（BGP－4）［S］.NY：The Internet Society，2006.

［16］ Gao L.On inferring autonomous system relationships in the Internet［J］.IEEE／ACM Transactions on Networking，2001，9（6）：733－745.

［17］ Caesar M，Rexford J.BGP routing policies in ISP networks［J］.IEEE Network，2005，19（6）：5－11.

［18］ Route Views［EB／OL］.［2005－01－27］.http：／／www.Route－Views.org.

［19］ Griffin T G，Wilfong G.An analysis of BGP convergence properties［C］∥Proc of the Conference on Applications，Technologies，Architetures，and Protocols for Computer COmmunication，1999：277－288.

附中文参考文献：

［14］ 胡宁，邹鹏，朱培栋.基于信誉机制的域间路由安全协同管理方法［J］.软件学报，2010，21（3）：505－515.