一种域间出口路径动态选择方法及系统

摘要

本发明提供一种域间出口路径动态选择方法及系统，包含：各个域出口路由器周期性采集自身信息的步骤；计算所述域出口路由器传输性能评价值的步骤；域内路由器获取传输性能评价值的步骤；生成优先级的步骤，所述域内路由器按评价值大小对域出口路由器进行优先级排序；所述域内路由器选择所述传输性能评价值最大者路由器作为其出口路由的下一跳地址；其中，所述域出口路由器指连接域内和域外网络且具备直接通信能力的路由器；所述域内路由器指和域出口路由器进行直接连接且不具备和域外网络进行直接通信能力的路由器。本发明无需对现有的路由协议进行任何更改；静态路由表的配置由系统实时自动完成；有效解决传统方法存在的缺乏QoS参数考虑的弊端。

说明书

技术领域

本发明涉及计算机网络领域，具体涉及一种域间出口路径动态选择方法及系统。

背景技术

随着Internet网络规模的扩大和承载业务种类的增多，特别是具有实时服务质量要 求的新兴业务(如视频会议、VoIP、视频直播等)的不断涌现，要求通信网络提供 高效端到端QoS(Quality of Service)支持的呼声也在逐渐增高。为了满足业务发展 需求，解决带宽不足带来的网络访问问题以及规避网络出口故障引入的网络可用性 风险等，不同网络域之间往往会部署多条出口链路进行相连。因此，如何动态选择 出口路径，既能满足业务流QoS优化传输需求，又能对网络资源进行合理分配和使用， 将是极具研究价值的问题。

域间出口路径选择问题一般是指，在到达流量目的地的过程中，网络具有多个可 达出口的情况下，如何选择最适合的出口路径进行数据转发。目前，域间出口路径 的选择方法主要包含两种：手工配置静态路由方法，动态路由生成方法。

手工配置静态路由方法一般是依靠网络管理员，通过命令行界面CLI(Command  Line Interface)或者网络管理软件，修改路由器的静态路由表项，将出口路径选择设 定为路由器某个具体的接口地址。这样，在路由器接收到需要向外访问的数据包时， 通过查找静态路由表，并依据路由表的指示往路由器的对应端口投递，从而将数据 包转发到特定的出口路径上。

动态路由生成方法主要是通过运行路由协议，并依据路由学习结果生成路由表， 从而进行域间出口路径的选择。通常的，域间网络运行的路由协议为边界网关协议 BGP(Border Gateway Protocol)，如图1所示。BGP是一种外部网关协议，即它在 多个自治域系统AS(Autonomous System)或域间执行路由、与其他BGP系统交换 路由和可达信息。BGP执行的路由分为三种：AS间路由、AS内部路由和贯穿AS 路由。BGP协议负责维护路由表、发送路由更新信息且基于路由metric决定路由。

传统的BGP协议在路由公告、路由学习和路由生成时，并没有考虑网络服务质 量QoS(Quality of Service)等因素。因此，通过BGP协议生成的域间出口路径一般 仅含网络可达信息。目前，有许多的研究学者开始考虑如何为BGP协议添加QoS参 数信息，使得通过BGP协议生成的路由表，在域间出口路径的选择时能够包含QoS 信息的考虑。相关研究的公开文件和出版物包括：

Kin-Hon Ho，Ning Wang，Panos Trimintzios，George Pavlou，Michael Howarth.On  egress router selection for inter-domain traffic with bandwidth guarantees[C].2004 Workshop on High Performance Switching and Routing，2004，pp.337-342.(2004年高性 能交换和路由会议上，由郝何健，王宁，潘诺斯·特米特兹奥斯，乔治·裴弗洛，和迈克 尔·豪沃思等在文献【带宽保证下域间流量传输的出口路由选择[C].2004：337-342.】) 中提出使用BGP路由策略来控制每条流域间出口路径选择，并为其提供端到端带宽 保证。作者将所有流按带宽需求从大到小的顺序排列，并以此确定其代价。每条流 的出口链路选择问题转换为通用作业分配问题，并利用启发算法来解决这一问题， 而启发的条件是消费带宽越小越好。X.Li，Wong Lui KS，J.Wang，K.Nahrstedt.QoS  extension to BGP[C].The 10th International Conference on Network Protocols  Proceedings，Paris，France，12-15November 2002，pp.100-109(2002年10th国际网络协 议会议上，由李肖，景单河，王军，克拉拉·那赫斯特等在文献【BGP的QoS扩展[C]. 2002：100-109】)中提出将BGP协议进行QoS扩展，并执行带宽公告和路由。T.C. Bressoud，R.Rastogi.Optimal configuration for BGP route selection[C].In：Proc.of the  IEEE INFOCOM2003.San Francisco：IEEE，2003.916-926(2003年IEEE计算机通信 国际会议上，由托马斯·布鲁索，拉吉夫·罗斯托吉，马克史·密斯等在文献【BGP路由 选择的优化配置[C].2003：916-926】)中提出最优出口链路及边界路由器的选择方法， 同时优化ISP网络资源。Michael P.Howarth，Mohamed Boucadair，Paris Flegkas，Ning  Wang，George Pavlou，Pierrick Morand，Thibaut Coadic，David Griffin，Abolghasem  Asgari，Panos Georgatsos.End-to-end quality of service provisioning through  inter-provider traffic engineering[J]Computer Communications，Vol.29，No.6，31 March 2006，pp.683-702(由迈克尔·豪沃思，穆罕默德·博卡德，帕里斯·福格卡斯，王 宁，乔治·帕弗洛，皮尔里克·莫兰德，蒂博·卡迪克，大卫·格里芬，阿伯拉格哈斯木·阿斯 卡里，帕诺斯·耶伽斯索斯等在文献【端到端服务质量提供的域间流量工程方法[J].计 算机通信，2006，29(6)：683-702】)中提出q-BGP(QoS-inferred border gateway protocol) 的概念，用于BGP协议进行扩展来携带QoS相关信息，并实现域间信息交换。Tat  Wing Chim，Kwan L.Yeung.Time-Efficient Algorithms for BGP Route Configuration[C]. 2004 IEEE International Conference on Communications，June 2004，Vol.2，pp. 1197-1201(2004IEEE国际通信会议上，由达荣詹，杨群属等在文献【一种时间高效 的BGP路由配置算法[C].2004(2)：1197-1201】)中提出了BGP路由配置的两种算法 用于进行出口路径选择，算法的目标是减少传输穿透流量时产生的资源消耗，同时 降低对出口链路容量的需求。Lotfi Benmohamed，Bharat Doshi，Tony DeSimone，Robert  Cole.Inter-Domain Routing with Multi-Dimensional QoS Requirements[C].IEEE  Military Communications Conference，MILCOM 2005，Atlantic，NJ，Oct.2005(2005年在 IEEE军事通信会议上，由卢特菲·本·穆罕默德，巴拉特·多希，托尼·德西蒙，罗伯特·科 尔等在文献【多尺度QoS需求的域间路由[C].】)中提出了支持多拓扑(multi-topology) 和QoS感知(QoS-aware)的BGP路由扩展协议来支持QoS路由。由刘亚萍，龚正 虎，何俊峰等在文献【一种基于链路状态的域间出口优化选择框架及关键算法[J].计 算机学报，2007，30(11)：1963-1971】中提出了一种灵活的出口路由选择优化框架 BGP-ROS(BGP Route Optimization Service)，该方案能够随网络实时变化和AS要 求变化来调整出口路径。

现有技术的手工配置静态路由方法往往需要大量的人工进行输入，当网络规模 增大时，这种方法费时耗力，维护起来极其困难，有时甚至无法实现人工进行管理。 同时，当网络结构发生变化时，手工配置静态路由的方法需要重新进行配置，过程 繁杂，给网络管理带来了极大的负担。

现有技术在动态路由生成方法中，传统的BGP协议缺乏对域间网络QoS状态的考 虑，因此在生成的域间出口路由方面具有一定的缺陷。而目前基于BGP协议基础上 进行修改和扩充的方法(主要是增加QoS参数的考虑)，直接作用于路由器的控制平 面，实现起来比较复杂；同时，由于协议的兼容性问题，使得支持这些方案的路由 协议非常少；此外，新路由策略的引入会给网络带来信令开销和处理负担，甚至减 慢链路振荡时路由收敛速度，破坏路由协议的稳定性等等潜在的风险。

综上所述，手工配置静态路由方法需要人工参与和维护，缺乏对网络承载状态 的实时感知，以及对网络的动态变化进行自适应调整的能力；传统动态路由生成方 法基于路由协议扩展，会给网络带来额外开销，并对原有网络的稳定性和兼容性引 入潜在的危险。

发明内容

本发明的目的在于，为克服现有技术如果采用静态路由进行域间路由选择是会 缺乏对网络承载状态的实时感知，以及对网络的动态变化进行自适应调整的能力； 如果采用路由协议扩展，会给网络带来额外开销，并对原有网络的稳定性和兼容性 引入潜在的危险；从而提供一种域间出口路径动态选择方法及系统。

为实现上述目的，本发明提供的一种域间出口路径动态选择方法及系统，该方 法基于对静态路由表的动态管理进行域间出口路径选择，包含：

采集信息的步骤，各个域出口路由器周期性的采集自身的状态信息及所处网络 信息；计算所述域出口路由器传输性能评价值的步骤，所述各个域出口路由器依据 采集到的信息，计算自身的传输性能评价值；域内路由器获取传输性能评价值的步 骤，所述域出口路由器分别将自身的传输性能评价值发送给与其直连的域内路由器； 生成优先级的步骤，所述域内路由器依据接收到的所述各域出口路由器发送过来的 传输性能评价值，按评价值大小对域出口路由器进行优先级排序；选择出口路由器 的步骤，所述域内路由器选择所述传输性能评价值最大者路由器作为其出口路由的 下一跳地址；其中，所述域出口路由器指的是连接域内和域外网络且具备直接通信 能力的路由器；所述域内路由器指的是和域出口路由器进行直接连接且不具备和域 外网络进行直接通信能力的路由器。

上述技术方案中，所述采集信息的步骤通过路由器提供的接口进行查询，或通 过主动或被动测量的方式获取所处网络状态信息；所述传输性能评价值与所述域出 口路由器自身的性能状态和所述出口链路的QoS状态相关；

优化的，所述选择出口路由器的步骤之后还包含更新静态路由表的步骤，用于 避免由于静态路由表的失效造成数据包转发失败。

所述更新静态路由表的步骤进一步包含：

修改路由表步骤，所述域内路由器依据所述各域出口路由器发送的传输性能评 价值修改本地静态路由表信息；删除静态路由表的步骤，所述域内路由器设置定时 器的值，当在该值设定的时间段内没有收到某一所述域出口路由器发送过来的报文 时，将清除目的地为该所述与出口路由器的本地静态路由表设置。

优选的，所述各个域出口路由器采用模糊逻辑算法依据若干输入参数计算所述 各个域出口路由器的传输性能评价值。

所述若干输入参数包括：出口链路可用带宽、出口链路时延和路由器丢包率。

采用上述优选所述域出口路由器进行传输性能评价的步骤为：

域出口路由器获取信息步骤，所述域出口路由器采用SNMP协议查询路由器提 供的接口采集自身丢包率信息，采用主动测量的方法获取出口链路的可用带宽、时 延信息；对采集信息进行模糊化处理步骤，所述域出口路由器依据模糊逻辑算法对 信息进行模糊化处理，即采用隶属度函数得到所述输入丢包率信息、可用带宽和时 延信息对应的模糊语言变量及其隶属度值；获得传输性能评价值，所述域出口路由 器依据若干模糊推理规则和隶属度函数获取其传输性能评价值，即采用模糊推理准 则和隶属度函数进行模糊推理获取若干推理准则结果，并利用重心法对推理准则结 果进行解模糊获取传输性能评价值；最后，所述各个域出口路由器将得到的传输性 能评价值发送给所述域内路由器。

上述方案中，所述出口链路可用带宽设置其具有三种隶属度函数，对应的模糊 语言变量记为{Low，Medium，High}；所述出口链路时延设置其具有三种隶属度函数，模 糊语言变量记为{Low，Medium，High}；所述路由器丢包率设置其具有两种隶属度函数， 模糊语言变量记为{Low，High}。所述路由器传输性能评价值设置其具有三种隶属度函 数，模糊语言变量记为{Bad，Medium，Good}。

所述隶属度函数的确认遵循简单化原则，即输入所述丢包率信息、可用带宽和 时延信息对系统性能的影响具有的均匀度和线性特征。

基于以上方法，本发明基于现有网络的网元提出一种域间出口路径动态选择系 统，该系统基于对静态路由表的动态管理进行域间出口路径选择，包含：域内路由 器和属于所述域内路由器所在域的各个域出口路由器；其中，所述域内路由器，用 于接收各域出口路由器发送过来的传输性能评价值；对各域出口路由器按传输性能 评价值进行优先级排序；生成本地静态策略路由配置指令，将评价值最大者域出口 路由器作为下一跳地址；和所述各个域出口路由器，所述各个域出口路由器用于周 期性的采集自身的状态信息及所处网络信息；依据采集到的信息，计算自身的传输 性能评价值；分别将自身的传输性能评价值发送给与其直连的域内路由器；

此外，上述方案所述的系统中包所述域出口路由器指的是连接域内和域外网络 且具备直接通信能力的路由器；所述域内路由器指的是和域出口路由器进行直接连 接且不具备和域外网络进行直接通信能力的路由器。

所述域内路由器进一步包含：

优先级排序单元，用于依据接收到的所述各域出口路由器发送过来的传输性能 评价值，按评价值大小对域出口路由器进行优先级排序；选择下一跳路由器的单元， 用于根据优先级排序单元选择传输性能评价值最大者路由器作为其出口路由的下一 跳地址。

优选的，所述域内路由器还包含：一定时器，用于设置执行删除某条静态路由 的时间段的值；路由表修改单元，用于依据所述各域出口路由器发送的传输性能评 价值修改本地静态路由表信息。

上述技术方案中，所述各个域出口路由器进一步包含：

信息采集单元，用于周期性的采集所述域出口路由器自身的状态信息及所处网 络信息；计算传输性能评价值单元，用于依据采集到的信息，计算自身的传输性能 评价值；发送单元，用于将自身的传输性能评价值发送给与其直连的所述域内路由 器。

所述计算传输性能评价值单元采用模糊逻辑算法依据若干输入参数计算所述各 个域出口路由器的传输性能评价值；所述若干输入参数包括：出口链路可用带宽、 出口链路时延和路由器丢包率。

所述路由器的传输性能评价值具体采用：对采集信息进行模糊化处理步骤，所 述域出口路由器依据模糊逻辑算法对信息进行模糊化处理，即采用隶属度函数得到 所述输入丢包率信息、可用带宽和时延信息对应的模糊语言变量及其隶属度值；所 述域出口路由器依据若干模糊推理规则和隶属度函数和隶属度函数获取其传输性能 评价值，即采用模糊推理准则和隶属度函数进行模糊推理获取若干推理准则结果， 并利用重心法对推理准则结果进行解模糊获取传输性能评价值。

所述出口链路可用带宽设置其具有三种隶属度函数，对应的模糊语言变量记为 {Low，Medium，High}；所述出口链路时延设置其具有三种隶属度函数，模糊语言变量记 为{Low，Medium，High}；所述路由器丢包率设置其具有两种隶属度函数，模糊语言变量 记为{Low，High}。所述路由器传输性能评价值设置其具有三种隶属度函数，模糊语言 变量记为{Bad，Medium，Good}。

本发明的优点在于，基于对静态路由表的动态管理进行出口路径选择，无需对 现有的路由协议进行任何更改，不会给现有网络引入任何不稳定性；静态路由表的 配置由系统实时自动完成，无需人工进行参与，极大降低管理维护成本，同时系统 具有较短的响应时间；充分考虑网络的多种QoS状态，有效解决传统方法存在的缺 乏QoS参数考虑的弊端，使得出口路径的选择更贴近业务传输的需求；方法不引入 任何附加网元，且各参与网元之间采用松耦合机制，出口路径的评估和出口路径的 选择分开，使得系统具有较好的灵活性。

附图说明

图1是现有技术的边界网关协议BGP；

图2是本发明的域间出口路径选择示意图；

图3是本发明的域间出口路径选择的组成框图；

图4是本发明的示意的域内路由器和域间路由器信令交互流程的示意图；

图5是本发明的域出口路由器和域内路由器组成的域间出口路径选择工作的流 程图；

图6是本发明的域出口路由器在执行本发明的域间路由选择时的流程图；

图7是本发明的域内路由器在执行本发明的域间路由选择时的流程图；

图8是本发明的提供的一个具体实施例的实验拓扑图；

图9-a是本发明实施例的输入变量为出口链路可用带宽时对应的隶属度函数图；

图9-b是本发明实施例的输入变量为出口链路时延时对应的隶属度函数图；

图9-c是本发明实施例的输入变量为路由器丢包率时对应的隶属度函数图；

图9-d是本发明实施例的路由器传输性能评价值对应的隶属度函数图；

图10是采用本发明提供的动态选择路径的方法与现有技术静态配置下客户端下 载完成时间对比图。

具体实施方式

下面结合附图和具体实施方式对本发明作进一步详细描述。

参考图2和图3，本方案采用了动态路由生成的方法实现域间出口路径选择。系统 的工作模型如图3所示。

系统中包含若干域出口路由器101和域内路由器102。域出口路由器101指的是 连接域内和域外网络且具备直接通信能力的路由器，域内路由器102指的是和域出 口路由器进行直接连接且不具备和域外网络进行直接通信能力的路由器(处于域内， 而不与域出口路由器进行直连的路由器，不在本专利考虑的范围)。出口路径动态选 择问题，即可以解释为，域内路由器102在对来自于域内且目的地址为域外的包进 行转发时，如何选择出口路由器作为下一跳路由，从而为数据包指定域间出口路径。

如图2所示，为描述方便起见，域出口路由器记为R₁和R₂，域内路由器记为R₃。 域间出口路径选择的问题，即可解释为当来自域内的数据包达到域内路由器R₃时，R₃如何选择R₁或R₂作为数据包转发的下一跳地址。

如图4所示，该图为具体执行本发明提供的域间出口路径的选择的域内路由器 和域出口路由器的信令交互流程的示意图。所述各个域出口路由器通过自评估获得 自身传输性能值，并发送给域内路由器；域内路由器对接收的各个域出口路由器的 传输性能值进行优先级排序并生成控制策略，依据该策略修改本地的静态路由表信 息，选在下一跳地址。

所述域内路由器依据各域出口路由器发送过来的传输性能评价值维护本地静态 路由表信息，实现静态路由表的更新。同时，域内路由器设置定时器，当长时间没 有收到域出口路由器发送过来的报文时，将清除本地静态路由表设置。这样，可以 避免由于静态路由表的失效造成数据包转发失败。

如图5所示，该图为本发明提供的域间出口路径的选择，依靠域出口路由器和域 内路由器协作完成。系统工作步骤如下：

步骤501，域出口路由器周期性的采集自身的状态信息及所处网络信息，采集的 方法可以通过路由器提供的接口进行查询(如SNMP协议)，也可以通过主动或被动 测量的方式获取所处网络状态信息；

步骤502，域出口路由器依据采集到的信息，计算自身的传输性能评价值，传输 性能评价值的计算和域出口路由器自身的性能状态以及出口链路的QoS状态相关；

步骤503，域出口路由器分别将自身的传输性能评价值发送给与其直连的域内路 由器；

步骤504，域内路由器依据接收到的各域出口路由器发送过来的传输性能评价 值，按评价值大小对域出口路由器进行优先级排序；

步骤505，域内路由器选择传输性能评价值最大者路由器作为其出口路由的下一 跳地址，并生成策略维护本地静态路由表。

如图6所示，该图为本发明包含的域出口路由器的工作流程图，具体描述为：

步骤601，域出口路由器采集自身丢包率信息，以及出口链路的可用带宽、时延 信息；

步骤602，域出口路由器依据模糊逻辑算法对信息进行模糊化处理；

步骤603，域出口路由器依据模糊推理规则获取其传输性能评价值；

步骤604，域出口路由器将传输性能评价值发送给域内路由器。

如图7所示，该图为本发明包含的域内路由器的工作流程图，具体描述为：

步骤701，域内路由器接收各域出口路由器发送过来的传输性能评价值；

步骤702，对各域出口路由器按传输性能评价值进行优先级排序；

步骤703，生成本地静态策略路由配置指令，将评价值最大者域出口路由器作 为下一跳地址。

实施例

为了验证方案的可行性，我们在开源路由器Quagga上进行了实现。实验的拓扑图 如图8所示。

在实验拓扑图中，路由器Router₁作为域内路由器，路由器Router₂和路由器Router₃为 域出口路由器，Client₁与Router₁进行连接，并与域外的服务器Server进行通信。Client₂和 Client₃分别与Router₂和Router₃进行连接，并随机产生数据包向网络发送，形成背景流 量，从而占用一定的网络资源，造成网络的扰动。

域出口路由器Router₂和Router₃采用模糊逻辑算法对自身的传输性能进行评价，考 虑的参数包括：出口链路可用带宽、出口链路时延、路由器丢包率，模糊输出的值 为路由器的传输性能评价值。各个参数的隶属度函数如图9-a、9-b、9-c和9-d所示。

对于每一个输入变量，我们做如下考虑：

1)出口链路可用带宽Bandwidth：设置其具有三种隶属度函数，模糊语言变量 记为{Low，Medium，High}；

2)出口链路时延Delay：设置其具有三种隶属度函数，模糊语言变量记为 {Low，Medium，High}；

3)路由器丢包率Lossrate：设置其具有两种隶属度函数，模糊语言变量记为 {Low，High}；

对于输出变量，即路由器传输性能评价值，我们做如下考虑：

路由器传输性能评价值F-QoS：设置其具有三种隶属度函数，模糊语言变量记 为{Bad，Medium，Good}。

对于每个考虑的输入和输出变量，其隶属度函数的确认遵循简单化原则，即主 要是表现出变量具有的均匀度(homogeneity degree)和线性特征(linear behavior)。 例如，对于有效带宽而言，有效带宽的变化对于系统性能的影响是线性的。各个参 数的隶属函数设置可以用如下所示的简化图形表示。

模糊推理规则的定义如下表所示(输入变量的排序为Bandwidth、Delay、Lossrate， 输入为F-QoS)。

在解模糊阶段，采用重心法实现对路由器传输性能评价参数F-QoS进行解模糊， 可以通过以下公式进行表示：

$z^{*}=\int {\mu }_{\underset{~}{C}}\left(z\right)·\mathrm{zdz}/{\int \mu }_{\underset{~}{C}}\left(z\right)·\mathrm{dz}$

总结以上内容，域出口路由器进行传输性能评价的操作步骤为：

(1)域出口路由器采集自身丢包率信息(采用SNMP协议查询路由器提供的接

口)，以及出口链路的可用带宽、时延信息(采用主动测量的方法获取)；

(2)域出口路由器依据模糊逻辑算法对信息进行模糊化处理；

(3)域出口路由器依据模糊推理规则获取其传输性能评价值；

(4)域出口路由器将传输性能评价值发送给域内路由器。

域内路由器进行路由配置的操作指令如下(假定Client₁至Server的默认路由为 Router₂，则出口路径动态选择需要设置时，仅考虑设置Router₃即可)：

路由配置指令：

ip rule add from 192.168.1.1/32table policy prio 300

ip route add default via 192.168.3.1 table policy

路由删除指令：

ip rule del from 192.168.1.1/32 table 100

总结以上内容，域内路由器的操作步骤为：

(1)接收各域出口路由器发送过来的传输性能评价值；

(2)对各域出口路由器按传输性能评价值进行优先级排序；

(3)生成本地静态策略路由配置指令，将评价值最大者域出口路由器作为下 一跳地址

实验时，设置Client₁通过FTP协议向Server下载数据，在使用静态路由和本方法 后，完成时间对比如图10所示(实验中设置下载任务文件大小为2.02G)，可见，本 方法的域间出口路径动态选择能够缩短用户的下载完成时间。

需要说明的是，以上介绍的本发明的实施方案提供的域间出口路径动态选择可以运行的一种 方法，该实施例的说明只是用于帮助理解本发明的方法及其核心思想而并非限制。本领域的一般 技术人员应当理解，任何对本发明技术方案的修改或者等同替代都不脱离本发明技术方案的精神 和范围，其均应涵盖在本发明的权利要求范围内。