域间多路径路由的实现方法

摘要

本发明公开了一种面向用户定制的，能够兼容现有路由协议及基础设施的域间多路径路由的实现方法，所述方法包括以下步骤：根据用户定制的路由性能要求，向主控节点输入用户路由定制参数，所述用户路由定制参数包括用户定制的目的网络；主控节点从路由表中选择AS节点组成局部拓扑的AS节点集合；主控节点请求所述AS节点集合中的各AS节点构造路段项并将所述路段项返回至主控节点；主控节点基于构建的局部拓扑，计算出满足用户定制的可行路径；主控节点为用户安装这些满足用户要求的路径，用户利用所述安装成功的可行路径，实现域间多路径路由。本发明实现了用户灵活选路以及个性化的路由需求服务。

说明书

技术领域

本发明涉及互联网路由协议及算法技术领域，尤其涉及一种面向 用户定制的域间多路径路由的实现方法。

背景技术

随着互联网应用快速增长，异构环境、泛在联网、移动接入和海 量流媒体等新应用的不断涌现，人们对多样化和个性化的互联网高效 路由的服务需求越来越大。由于传统域间路由协议（BGP）存在可靠 性差、不支持多路径路由等诸多问题，以BGP协议（单径路由协议） 为核心技术的互联网面临着越来越严重的技术挑战。域间多路径路由 能有效地满足用户选路灵活性，提高网络的可靠性、稳定性与安全性， 是实现互联网高效路由的重要方法。近年来域间多路径路由受到学术 界广泛地关注和研究，产生了许多域间多路径路由技术。

目前研究域间多路径路由主要有两种思路：基于BGP的增强设 计和支持多路径路由的新型域间路由协议设计。第一类研究主要包括 域间多路径路由(MIRO),可靠BGP(RBGP),感知多样性多路径路由 (DBGP和BBGP)等工作，它们的主要目标是解决一些特定的应用问 题，例如确保网络可靠安全，支持流量工程等，但是现有的增强BGP 多路径设计仍具有BGP协议的一些本质缺陷与不足。第二类研究的代 表性工作有下一代域间路由协议(HLP)、新型互联网路由体系结构 (NIRA)，它们完全抛弃了现有路由协议及其基础设施，设计了支持多 路径路由的新型路由体系结构，其不足是部署比较困难。

同时，互联网路由社区存在两种不同激励模型：互联网服务和流 量交换定价模型(STEM)和联盟路由激励模型(CRIM)。STEM是目前 AS（自治系统）之间的服务和流量交换定价模型，该服务模型对相 邻AS的路由服务没有激励；而CRIM是一种新型的路由联盟激励模 型，它对提供路由服务的每个AS都有激励。对于使用不同的激励模 型，AS提供路由服务的积极性也会不同，在STEM服务模型下，AS 仅公开兼容其策略的路由信息，而在CRIM激励模型下，AS愿意公开 路径的路由信息，并保证路由质量。因此，本发明考虑这两种激励模 型下的域间多路径路由的设计方法，不仅可以适用于目前传统的AS 服务模型，提供一定程度的多样化路由服务；而且可用于AS路由联 盟激励模型，提供功能强大的多样化路由服务，同时可以保证用户的 路由质量。因此，能够兼容两种不同激励模型的多路径路由实现方法 也成为亟待解决的技术问题。

发明内容

（一）要解决的技术问题

本发明要解决的技术问题是：如何避免上述两种域间多路径路由 方法的不足，提供一种兼容现有路由协议及基础设施的域间多路径路 由的实现方法，

（二）技术方案

为解决上述问题，本发明提供了一种面向用户定制的，兼容现有 路由协议及基础设施的域间多路径路由的实现方法，所述方法包括以 下步骤：

S1：根据用户定制的路由性能要求，向主控节点输入用户路由定 制参数，所述用户路由定制参数包括用户定制的目的网络；

S2：主控节点从路由表中选择AS节点组成局部拓扑的AS节点 集合；

S3：主控节点请求所述AS节点集合中的各AS节点构造路段项 并将所述路段项返回至主控节点；

S4：主控节点基于构建的局部拓扑，计算出满足用户定制的可行 路径；

S5：主控节点为用户选择并安装所述满足用户定制的可行路径， 用户利用所述安装成功的可行路径，实现域间多路径路由。

优选地，所述用户路由定制参数还包括正常路径数、备份路径数、 路由开销代价信息、路由计算时间间隔、路由定制时间期限、激励模 型和路径性能约束参数，所述路径性能约束参数包括延迟、延迟抖动、 带宽和丢失率参数。

优选地，所述步骤S2进一步包括以下步骤：

S21：主控节点根据所述用户路由定制参数，从其BGP路由表中 获得到达目的网络的路径，并按照高质量优先的原则确定路径选择范 围，最后确定一个节点候选集合；

S22：在所述节点候选集合的基础上进一步选择AS节点组成局 部拓扑的AS节点集合。

优选地，所述步骤S22在进一步选择AS节点组成局部拓扑的 AS节点集合时，根据所述AS节点的度或AS节点路径可用度来选择。

优选地，所述步骤S3进一步包括以下步骤：

S31：主控节点向所述AS节点集合中的各AS节点发出构造路段 项请求报文；

S32：各AS节点根据其BGP路由表，对其到达目的网络的可行 路径进行编码形成路段项，并将所述路段项返回至主控节点。

优选地，所述步骤S32进一步包括以下步骤：

S321：各AS节点根据目的网络查询其BGP路由表，获得到达 目的网络的可行路径，然后根据路段可视度和自身路由策略确定可行 路径中能够作为路段项信息的PL路径；

S322：对于各AS节点的每一条PL路径，该AS节点根据PL路 径类型，生成不同类型的路段项。

优选地，所述步骤S32进一步包括以下步骤：

S323：各AS节点根据目的网络查询其BGP路由表，获得到达 目的网络的可行路径；

S324：各AS节点根据路段可视度和自身路由策略，确定能够作 为路段项信息的可行路径，生成相应的路段项。

优选地，所述步骤S5进一步包括以下步骤：

S51：主控节点直接在所选路径上各AS节点的多路径路由表安 装满足用户定制的可行路径；

S52：用户通过所述安装成功的可行路径，实现多路径路由。

优选地，所述步骤S5进一步包括以下步骤：

S53：判断所述满足用户定制的可行路径中的其中一个路径是否 兼容主控节点策略，如果是，执行步骤S54，如果否，执行步骤S55；

S54：对于兼容主控节点策略的路径，直接将所述路径装入到主 控节点的多路径路由表并打上特定路由标记，跳过步骤S55；

S55：对于不兼容主控节点策略的路径，通过协商在所述路径上 的AS节点安装路由表或隧道表；

S56：重复步骤S53-S55，直至安装完满足用户定制的可行路径， 主控节点安装路径成功后，用户通过所述可行路径，实现多路径路由。

优选地，所述步骤S55进一步包括以下步骤：

S551：主控节点建立隧道记录；

S552：逐一检查所述路径上各节点是否用其管理的路段作为主路 径，如果不是主路径，主控节点则与该节点进行协商并建立IP隧道， 直到所述路径上所有不兼容策略的节点都建立了IP隧道，整条路径 由级联IP隧道构成，形成一条可以使用的路径。

优选地，所述步骤S552进一步包括以下步骤：

S5521：检查路径上其中一个AS节点是否用其管理的路段作为 主路径；如果是，跳过步骤S5522及S5523，如果否，则继续执行步 骤S5522;

S5522：主控节点向所述AS节点发出建立隧道请求，请求内容 包括主控节点的隧道记录；

S5523：所述AS节点分配一个隧道ID，将自身控制的路径信息 加入隧道记录中，并在其自身隧道表中安装所述隧道记录，然后将隧 道记录返回给主控节点，主控节点用返回的隧道记录替换旧隧道记录 并保存；

S5524：重复步骤S5521-S5523，直到该路径上所有不兼容策略 的节点都建立了IP隧道，使得整条路径由级联IP隧道构成，形成一 条可以使用的路径。

（三）有益效果

本发明在现有BGP路由系统的基础上，为满足用户的多样化和 个性化的路由需求,通过构建局部拓扑进行路由计算的方法，提供了 一种高效可靠的多路径路由解决方案，不仅实现了用户灵活选路以及 个性化的路由需求服务，而且提高了互联网服务供应商（ISP）的核 心竞争力和经济收益。

同时，本发明考虑两种不同激励模型下的域间多路径路由的设计 方法，不仅可以适用于目前传统的AS服务模型，提供一定程度的多 样化路由服务；而且可用于AS路由联盟激励模型，提供功能强大的 多样化路由服务，同时可以保证用户的路由质量。

附图说明

图1为本发明的域间多路径路由实现方法的流程图；

图2为本发明的域间多路径路由实现方法的步骤S2的流程图；

图3为本发明的域间多路径路由实现方法的步骤S3的流程图；

图4为本发明的域间多路径路由实现方法当激励模型为STEM时 的步骤S32的流程图；

图5本发明的域间多路径路由实现方法当激励模型为CRIM时的 步骤S32的流程图；

图6为本发明的域间多路径路由实现方法当激励模型为CRIM时 的步骤S5的流程图；

图7为本发明的域间多路径路由实现方法当激励模型为STEM时 的步骤S5的流程图；

图8为本发明的域间多路径路由实现方法的步骤S55的流程图；

图9为本发明的域间多路径路由实现方法的步骤S552的流程图；

图10为本发明的域间多路径应用场景示意图；

图11为本发明的域间多路径路由计算抽象模型；

图12为本发明的域间多路径的路段项构造流程图；

图13为本发明的域间多路径节点构造路段项示意图；

图14为本发明的域间多路径IP隧道建立示意图；

图15为本发明的不同激励模型下UMIR的路径多样性示意图；

图16为本发明的路段可视度R对路径多样性的影响示意图；

图17为本发明的拓扑节点数N对路径多样性的影响示意图；

图18为本发明的不长于主路径的路径数目分布示意图；

图19为本发明的路段可视度R的通信开销比较示意图；

图20为本发明的拓扑节点数N对计算开销的影响示意图。

具体实施方式

下面结合附图及实施例对本发明进行详细说明如下：

本发明提出的面向用户定制的域间多路径路由的实现方法，采用 一种启发式算法构建局部拓扑的方法，具体实施方式结合附图详细说 明如下：

本发明使用了一种新型的路段项，所述路段项是指AS节点之间 的链路即路由信息，基于路段项这个基本路由构件设计了一种域间多 路径路由协议的实现方法。由于扩展性和选路灵活性是多路径路由协 议必须解决的两个重要问题，因此基于这两点，在设计本发明的域间 多路径路由实现方法（简称“UMIR路由协议”）时，从提高协议的 扩展性和选路灵活性出发，确定UMIR路由协议的设计思想是：根据 用户路由请求，主控节点收集一定规模的局部拓扑，然后进行路由计 算。局部拓扑形成包括节点选择和节点路段构造过程。通过选择节点 度值较大的节点，提高了路径多样性的潜力。节点构造路段时考虑路 段的物理属性M、策略属性T和代价信息C。通过控制节点的路段可 视度R（代表节点的可用路段数目）和拓扑节点数N（代表局部拓扑 的规模大小）可以调节UMIR路由协议的性能与开销。路由计算过程 可以使用多种路由算法（例如策略路由、最小代价路由等），以提高 路由计算的能力。

如图1所示，本发明的域间多路径路由的实现方法的具体流程如 下列步骤S1－S5所示：

S1：根据用户定制的路由性能要求，向主控节点输入用户路由定 制参数，所述用户路由定制参数包括用户定制的目的网络。所述主控 节点是指部署了UMIR路由协议、接收用户路由定制并负责发起路径 计算任务的ISP节点。

在步骤S1中，所述用户路由定制参数还可包括正常路径数、备 份路径数、路由开销代价信息、路由计算时间间隔、路由定制时间期 限、激励模型和路径性能约束参数，所述路径性能约束参数包括延迟、 延迟抖动、带宽和丢失率参数。具体操作如下：

a.输入用户定制的目的网络d，包括AS号，目的网络前缀，或 者目的服务器IP地址等参数；

b.输入用户定制的正常路由数以及备份路由数；

c.输入路由开销代价信息；

d.输入路由计算的时间间隔，以及路由定制的时间期限；

e.输入所用激励模型，例如STEM或者CRIM；

f.输入路由的各种约束参数，包括延迟D，延迟抖动J，带宽B 和丢失率LR等性能指标。

下面结合图10及图11描述用户路由定制的需求，如图10所示， 图10为一个用户定制的多路径路由服务的应用场景，例如ALICE和 BOB都需要访问名称为Ｄ的AS中某个网络D1。ALICE希望使用延 迟最短的路径，而BOB需要使用带宽最大的路径，因此他们需要其 ISP（即主控节点Z）定制这种特定性能的路径服务。为了便于后面 的描述，我们将图10中的每个AS抽象为一个网络节点，得到图11 所示的路由计算抽象模型，即AS图。

S2：主控节点从路由表中选择AS节点组成局部拓扑的AS节点 集合。

具体地，如图2所示，步骤S2可以包括以下两个步骤：

S21：主控节点根据所述用户路由定制参数，从其BGP路由表中 获得到达目的网络的路径，并按照高质量优先的原则，即按照主路径、 候选路径以及逻辑路径的顺序确定路径选择范围，最后确定一个节点 候选集合。

具体地，由于可用路径的类型包括三种基本类型：主路径、候选 路径以及其他逻辑路径，对于主路径，由于它兼容主控节点的路由策 略被优先确定为路径选择对象；对于候选路径，由于它不满足主控节 点的选路策略但是它们符合其他AS节点的路由策略而被次优确定为 路径选择对象；对于其他逻辑路径，如果前两种路径AS节点还不满 足协议构建局部拓扑的要求时，可以进一步考虑使用这种逻辑路径， 因此这种逻辑路径被选择的优先级为最低。最后从这三种路径上可以 获得节点候选集合。

S22：在所述节点候选集合的基础上，根据节点选择策略以及节 点度大小，从节点候选集合中选择AS节点组成局部拓扑的AS节点 集合。

步骤S22在选择AS节点组成局部拓扑的AS节点集合时，AS 节点的选择原则主要有两个：AS节点的度或AS节点路径可用度。 所述AS节点的度表示与该节点直接相邻的AS数目，它反映了节点 的总体服务质量；而AS节点路径可用度表示AS节点中目的网络的 可用路径数，它是衡量到达目的网络的服务质量。主控节点根据用户 的需求与自身的选择策略，可以使用两种不同的节点选择策略：第1 种策略-若协议需要最大化其路径多样性，则根据节点度来选择所需 节点；第2种策略-若协议需要最大化其策略兼容的路径数，则根据 节点的路径可用度来选择所需节点。

下面结合图13来解释节点选择的过程，如图13所示，根据主控 节点Z的路由表RIB，该节点首先确定主路径上的节点集{B,D}；候 选路径上的节点集{A,D}；直接邻居节点集{C},最后得到待选节点集 {A,B,C}。假设局部拓扑节点数目N要求为2，且节点选择策略使用 第1种策略即最大化其路径多样性。基于路由表RIB可以计算出各 AS节点度：Degree（A）=3,Degree（B）=3,Degree（C）=2；然后 选择节点度最大的两个节点构成局部拓扑节点集合{A,B}。

S3：主控节点请求所述AS节点集合中的各AS节点构造路段项 并将所述路段项返回至主控节点。

具体地，如图3所示，所述步骤S3包括以下步骤：

S31：根据步骤S2确定的AS节点集合，主控节点向所述AS节 点集合中的各AS节点发出构造路段项请求报文。

S32：各AS节点根据其BGP路由表，对其到达目的网络的可行 路径进行编码形成路段项，并将所述路段项返回至主控节点。

根据UMIR协议使用的激励模型的不同，各个AS节点构造路段 项的算法不同：

具体地，如图4所示，若使用STEM激励模型，所述步骤S32 包括以下步骤：

S321：各AS节点根据目的网络查询其BGP路由表，获得到达 目的网络的可行路径，然后根据路段可视度和自身路由策略确定可行 路径中能够作为路段项信息的PL路径，以提供给主控节点用于构造 局部拓扑；

S322：对于各AS节点的每一条PL路径，如图12和图13所示， 该AS节点根据PL路径类型，即主路径或候选路径，分别生成不同 类型的路段项，其中，主路径生成type=1的路段信息，整个路段项 格式为【路段标识，目的网络，度量矢量，路段类型（type=1）】；而 候选路径生成type=2的路段信息，整个路段项格式为【路段标识， 目的网络，度量矢量，路段类型（type=2）】。

若使用CRIM激励模型，如图5所示，则所述步骤S32包括以下 步骤：

S323：各AS节点根据目的网络查询其BGP路由表，获得到达 目的网络的可行路径，所述可行路径包括主路径和候选路径。

S324：如图12和图13所示，各AS节点根据路段可视度和自身 路由策略，确定能够作为路段项信息的可行路径，生成相应的路段项。 整个路段项格式为【路段标识，目的网络，度量矢量，路段类型 （type=0）】，值得注意的是，与STEM激励模型中不一样的是，它所 生成的路段项的路段类型全部都为type=0。

S4：主控节点基于构建的局部拓扑，计算出满足用户定制的可行 路径。

具体地，主控节点获得计算某个目的网络的局部拓扑后，可以调 用路由算法例如最短路径算法，最大带宽算法或策略路由算法等，并 根据用户路由性能的要求，计算出满足用户特性的可行路径。本发明 的路由算法可以采用现有技术的路由算法的任意一种，本发明在此不 做限定，但是，作为优选的技术方案，可以采用如下的路由算法：

算法1：Bfs-path-search（BPS）路径计算算法

Bfs-path-search（G，s,t,n）

#输入:局部拓扑图（G）采用邻接表存储，(s,t)为源、目的节点对

#输出:计算n边不相交路径

上述的算法1程序给出了以局部拓扑为输入并计算路由的基本 算法。该算法具有很强的扩展性，经适当扩展可以支持更强大的路径 计算功能，例如最短（延迟）路径算法，最大（带宽）路径算法，多 约束路径优化路由算法，或者策略路由算法等，以满足不同路由计算 需求。

S5：主控节点为用户选择并安装所述满足用户定制的可行路径， 用户利用所述安装成功的可行路径，实现域间多路径路由。

具体地，对于满足用户定制的可行路径，主控节点根据自己的路 由策略为用户选择并安装其多路径路由表。根据所用激励模型的不 同，采取的方法也不相同。

在CRIM激励模型下，由于所有AS节点都愿意提供路由服务， 故直接在各AS节点的多路径路由表中安装即可，此种情况下，如图 6所示，步骤S5包括以下步骤：

S51：主控节点直接在所选路径上各AS节点的多路径路由表安 装满足用户定制的可行路径；

S52：用户通过所述安装成功的可行路径，实现多路径路由。

在STEM激励模型下，对于兼容主控节点策略的路径，也可以直 接调度使用，但是对于不兼容AS节点的选路策略的路径，则需要通 过协商似的路径上AS节点愿意提供路径服务，在此情况下，如图7 所示，步骤S5包括以下步骤：

S53：判断所述满足用户定制的可行路径中的其中一个路径是否 兼容主控节点策略，如果是，执行步骤S54，如果否，执行步骤S55；

S54：对于兼容主控节点策略的路径，直接将所述路径装入到主 控节点的多路径路由表并打上特定路由标记，跳过步骤S55；

S55：对于不兼容主控节点策略的路径，通过协商在所述路径上 的AS节点安装路由表或隧道表；

S56：重复步骤S53-S55，直至安装完满足用户定制的可行路径， 主控节点安装路径成功后，用户通过所述可行路径，实现多路径路由。

对于步骤S55，如图14所示，图14给出了一个建立Z-B-E-D路 径为可行路径的具体实例。给定一条路径，按顺序标记路径上的AS 节点，所有AS节点记为AS={n1，…,nk},相应地其管理的路段记为 PL={p1，…,pk}，主控节点依次与节点k进行协商，如图8所示，执 行如下步骤：

S551：主控节点建立空隧道记录(d,tid=null,path_old=null)，其中 d表示目的网络；

S552：逐一检查所述路径上各节点是否用其管理的路段作为主路 径，如果不是主路径，主控节点则与该节点进行协商并建立IP隧道， 直到所述路径上所有不兼容策略的节点都建立了IP隧道，整条路径 由级联IP隧道构成，形成一条可以使用的路径。

如图9所示，S552的具体流程为如下：

S5521：检查路径上其中一个AS节点k是否用其管理的路段pk 作为主路径，如果是，跳过步骤S5522及S5523，继续检查下一个节 点k-1，如果否，则继续执行步骤S5522;

S5522：主控节点向所述AS节点发出建立隧道请求，请求内容 包括主控节点的隧道记录（d,tid,path_old）；

S5523：所述AS节点分配一个隧道ID，将自身控制的路径信息 加入隧道记录中，即将AS节点控制的路径拼接上旧路径标识path_old 构成新路径标识path_new，并在其自身隧道表中安装所述隧道记录 （tid,path_new）,然后将隧道记录返回给主控节点，主控节点用返回 的隧道记录替换旧隧道记录并保存；

S5524：重复步骤S5521-S5523，直到该路径上所有不兼容策略 的节点都建立了IP隧道，使得整条路径由级联IP隧道构成，形成一 条可以使用的路径。

本发明的上述域间多路径路由的实现方法具有如下主要特点： （1）用户直接驱动的路由计算与选择方法；（2）集中控制与路由计 算；（3）路由信息按需传播；（4）将策略和拓扑信息植入路由信息中 传播；（5）结合链路状态算法和路径矢量算法的特征。本发明根据用 户定制的路由及其性能要求，通过收集一定规模AS节点的路由信息 构建局部拓扑，然后以此为基础进行路由计算，实现域间多路径路由 的方法。本发明能满足用户多样化和个性化的路由需求，解决了以往 域间多路径路由方法中存在的问题。

下面介绍本发明提出的域间多路径路由实现方法的实验效果。

评估Internet路由协议的最理想方法是通过在Internet中真实部 署来测量协议的性能和开销。但是，由于各种客观因素的限制，在已 经商业化的Internet上进行部署测试几乎是不现实的，因此比较适合 的方法是以近似的互联网拓扑环境来模拟路由协议运行。为了评价本 发明的域间多路径路由的实现方法，我们开发了一个UMIR模拟器来 模拟UMIR路由协议。该模拟器模拟了UMIR路由协议的基本运行 机制和关键特性，例如协作节点选择策略、路段请求与构建方法、构 造局部拓扑，策略配置等。实验拓扑使用真实的互联网拓扑，该拓扑 是基于路由表协作分析与共享网站(www.routeviews.org)中的BGP路 由表，利用GAO推理算法推导出Internet拓扑（该拓扑标注了AS节 点的商业关系）。然后我们随机选取了10000个随机点对进行AS路 径特性及其多样性实验分析。由于实验中要使用到RIB路由表，故我 们首先获得一个RIB路由表实例，并选择路径公开的Origin AS作为 目的节点，而目的节点使用比例优先随机采样法RFRS来确定。目的 节点的采样分布如下表1所示，其中AF、AP、AR、RI和LA分别 代表5个分配自治系统号（即ASN号码）的地区互联网号码注册中 心RIR(Regional Internet Number Registries)机构。

表1目的AS节点的采样分布表

为了评价UMIR路由协议，我们考察了协议性能和开销两方面的 内容。UMIR路由协议性能主要包括路径多样性和路径长度。UMIR 路由协议开销包括通信和计算开销。模拟实验中参数设置包括：（1） 设定局部拓扑大小N；（2）确定节点选择策略S；（3）设定路段可视 度R；（4）配置AS激励模型。然后，根据不同实验参数，观察它们 对UMIR路由协议性能和开销的实际影响。我们做了大量的模拟实 验，其实验结果如附图中的图15至图20所示：图15给出了不同激 励模型配置下的路径多样性累积概率分布CDF(Cumulative  Distribution Function)曲线；图16给出了路段可视度R对路径多样性 的影响；图17给出了局部拓扑大小N对路径多样性的影响；图18 给出了不长于主路径的路径分布；图19给出了不同路段可视度R下 通信开销的观察；图20给出了拓扑节点数N对协议计算开销的影响。

实验结果分析与评价如下：

路径多样性是域间多路径路由协议的重要特征之一，它表明了协 议能实现路径多样性的丰富程度，也是用户选路灵活性的重要标志。 图15给出了不同激励模型下路径数目的统计结果。不同激励模型的 两条曲线上的路径数目呈指数增长，而且其变化趋势基本相同。STEM 的路径数偏低，而CRIM的路径数较高。这是由于在STEM模型中， 相邻AS之间的商业关系限制了可用路径的数目，会出现许多无效的 “谷底”路径；而在CRIM激励模型下，由于激励消除了这种限制， 从而使得可用路径大大增加，进一步提高了UMIR协议的路径多样 性。从图15可以看出，对于CRIM模型，80%节点对的路径数大于 7352条；对于STEM模型，80%节点对的路径数大于2433条路径， 显然UMIR路由协议在STEM模型下能发现大量的多样化路径，而 在CRIM激励模型下，UMIR路由协议的路径多样性将更加丰富。

图16给出了随着路段可视度R变化对UMIR路由协议的路径多 样性的影响。随路段可视度R的增加，路径多样性呈现指数递增的趋 势。从理论上来说，这是很容易理解的，因为假定路径长度为n,每 条路段有m个选择，则可能路径将是mⁿ量级的路径数目。当路段可 视度R=5时，CRIM路径数为2235条，STEM路径数为753条。随 着R继续增加，则路径数目呈现指数增长趋势。另一个问题是，路段 可视度R的增加将导致通信和计算开销的增加。因此路段可视度R 是必须仔细考虑并认真选取的协议参数，R=5是比较合适的参数。

图17给出了在路段可视度R=5时，拓扑节点数N对路径多样性 的变化影响。随着拓扑节点数N增加，路径数目出现快速递增的趋 势。但是，与路段可视度R对路径多样性的影响比较，从图中可以看 出拓扑节点数N没有路段可视度R对路径多样性的影响大。对BGP 路由表的统计结果显示，基于目的网络可用路径上AS节点构成的局 部拓扑节点数N平均为18。从图上可以看出，拓扑节点数N=17时 接近最大值，而拓扑节点数N继续增加时其路径数目增加不明显。

为了评价UMIR协议发现高质量路径的能力。图18给出了不长 于主路径的路径分布。图中可以看出：在传统STEM模型下，UMIR 协议能发现少量的优质路径，约11%的节点对有不长于主路径的路 径；而在CRIM激励模型下，超过64%以上的节点对有四条以上不长 于主路径的路径。另外，约有8%的节点对存在短于主路径的路径。 从路径长度（即AS节点数目）上看，尽管短于最佳路径的路径不是 很多，但是与最佳路径长度相同的节点对却很丰富，最多有近百条路 径。因此，利用这些潜在的高质量路径可以改善用户应用的路由性能。

为了评价UMIR路由协议的开销影响，我们统计了UMIR路由 协议进行路径计算的通信和计算开销。UMIR路由协议开销的影响因 素主要包括两个方面，其一是局部拓扑节点数N，其二是节点的路段 可视度R。拓扑节点数和路段可视度决定了路由协议的性能和开销。 拓扑规模和路段可视度越大，UMIR协议能发现更多路径数目，协议 性能更好，相应地通信和计算开销则越大。因此，拓扑规模和路段可 视度的取值必须在路由性能与开销之间进行综合权衡。图19给出了 不同路段可视度R下通信开销的实验结果。从图中可知，通信开销变 化不大，通信报文数目集中在40到130之间。路段可视度R对通信 开销的影响是线性关系，随着R值越大，通信开销也越大。对于路段 可视度R=3，5和7，20%节点对的通信报文数目分别小于43，68和 88，而80%的节点对大于43，68和88。图20给出了拓扑节点数N 对UMIR协议计算开销的影响。随着拓扑节点数N的递增，计算开 销也呈指数递增。在N小于10之前，计算开销的变化比较平缓，其 原因可能是由于节点度偏少导致边数增加缓慢。在N=10时，路段可 视度R为3，5，7时，其计算时间分别为0.7s，9.5s和52s。可以发 现路段可视度R和拓扑节点数N对计算开销的影响较大，尽管R和 N的取值越大，UMIR路由协议的路由性能会越好，但是其开销也是 巨大的。因此，这些协议参数的选取需要综合考虑UMIR路由协议性 能和开销之间的平衡。

通过模拟实验分析，我们得出如下结论：第一，UMIR路由协议 具有较大的路径发现能力，能满足用户选路灵活性的要求，实现用户 多样化、个性化的路由服务需求；第二，UMIR路由协议能发现高质 量的路径，利用这些路径可以改善用户应用的路由性能（例如，低延 迟）要求；第三，UMIR路由协议具有合理的计算和通信开销。综上 所述，本发明达到了预期目的。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关 技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下， 还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明 的范畴，本发明的专利保护范围应由权利要求限定。