一种路由迭代方法及路由交换设备

摘要

本发明公开了一种路由迭代方法及路由交换设备。该方法包括：当路由迭代被触发时，路由交换设备的主控板对迭代路由进行路由迭代处理；其中，在进行路由迭代过程中记录迭代路由的迭代路径，并根据记录的该迭代路由的迭代路径，在判断当前迭代到的依赖路由为所述迭代路由本身或该依赖路由已经在迭代路由中出现过时，在路由表中除了当前迭代到的依赖路由以外的路由中查找依赖路由进行路由迭代；所述路由交换设备的主控板将迭代结果下发到线卡板的路由表中，用以指导报文转发。采用本发明可避免循环迭代。

说明书

技术领域

本发明涉及通信技术领域，尤其涉及一种路由迭代方法及路由交换设备。

背景技术

BGP(Border Gateway Protocol，边界网关协议)是一种用于AS(Autonomous  System，自治系统)之间的动态路由协议。一个自治系统的经典定义是在一个 管理机构控制之下的一组路由器，它使用IGP(Interior Gateway Protocol，内部 网关协议)和普通度量值向其他自治系统转发报文。

每条路由均要有其对应的下一跳地址，对于普通的路由来说，其下一跳地 址在路由器直连的网段内。在BGP中，由于协议本身的特殊性，它产生的路 由的下一跳地址可能不是当前路由器直接相连的邻居。一种常见的原因包括： IBGP(内部BGP协议)之间发布路由信息时不改变下一跳。另一种导致路由 项的下一跳地址不是路由器某个接口的同网段地址的情况是：静态配置路由。

这种情况下，为了能够将报文正确转发出去，路由器必须先找到一个直接 可达的地址(查找IGP建立的路由表项)，通过这个地址到达路由表中指示的 下一跳。在上述过程中，去往直接可达地址的路由被称为依赖路由，路由器依 赖于这些路由指导报文转发。根据下一跳地址找到依赖路由的过程就是路由迭 代(recursion)。需要进行迭代的路由可以是静态路由、BGP路由等，称为迭 代路由。路由迭代功能可以使路由表项比较灵活，不依赖于特定的接口。

由于路由学习、迭代是一个动态而又复杂的过程，在上述过程中可能会出 现一条路由经过多次迭代后迭代到自身的情况，这种现象叫做路由的循环迭 代。例如，在特定应用场景下，如手工配置两条路由，它们互为备份、同时又 能负载分担，如图1所示，该组网中包括路由器A、B、C和业务服务器Server1、 Server2，Server1的IP地址为1.1.1.1，Server2的IP地址为2.2.2.2。在路由器 A上配置访问服务器的路由表项如下(格式为：目的地址/掩码下一跳)：

RT1：1.1.1.1/32 serial0

RT2：2.2.2.2/32 serial1

RT3：1.1.1.1/32 2.2.2.2

RT4：2.2.2.2/32 1.1.1.1

其中，RT1和RT3为等价路由，它们互为备份，RT2和RT4为等价路由， 它们互为备份。RT3和RT4是手工配置的路由，其下一跳地址不是直接可达的 地址，为迭代路由。该场景下，可能出现循环迭代，例如：

在对RT3进行路由迭代时，以RT3的下一跳地址2.2.2.2作为目的地址查 找到RT2，RT2的下一跳地址为直接可达的地址；RT3迭代到RT2上后，与 RT1形成等价路由，而RT1是RT4的依赖路由，因此触发RT4重新迭代；

RT4重新迭代到等价路由(RT1、RT3)后，与RT2形成等价路由，而RT2 是RT3的依赖路由，因此再次触发RT3重新迭代，RT3又迭代到等价路由(RT2、 RT4)，从而再次触发RT4重新迭代，不断循环。

路由器需要能够检测并停止循环迭代。

发明内容

本发明提供一种路由迭代方法及路由交换设备，用于避免循环迭代。

本发明提供的路由迭代方法，包括：

当路由迭代被触发时，路由交换设备的主控板对迭代路由进行路由迭代处 理；其中，在进行路由迭代过程中记录迭代路由的迭代路径，并根据记录的该 迭代路由的迭代路径，在判断当前迭代到的依赖路由为所述迭代路由本身或该 依赖路由已经在迭代路由中出现过时，在路由表中除了当前迭代到的依赖路由 以外的路由中查找依赖路由进行路由迭代；

所述路由交换设备的主控板将迭代结果下发到线卡板的路由表中，用以指 导报文转发。

本发明提供的路由交换设备，包括主控板和线卡板，所述主控板包括：

路由迭代模块，用于当路由迭代被触发时，对迭代路由进行路由迭代处理； 其中，在进行路由迭代过程中记录迭代路由的迭代路径，并根据记录的该迭代 路由的迭代路径，在判断当前迭代到的依赖路由为所述迭代路由本身或该依赖 路由已经在迭代路由中出现过时，在路由表中除了当前迭代到的依赖路由以外 的路由中查找依赖路由进行路由迭代；

路由下发模块，用于将所述路由迭代模块的迭代结果下发到线卡板的路由 表中，用以指导报文转发。

与现有技术相比，本发明具有如下技术效果：

本发明在路由迭代过程中记录迭代路径，并在迭代路由发生重新迭代时根 据记录的该迭代路由的迭代路径，在判断当前迭代到的依赖路由为所述迭代路 由本身或该依赖路由已经在迭代路由中出现过时，在路由表中除了当前迭代到 的依赖路由以外的路由中查找依赖路由进行路由迭代，从而避免了循环迭代。

附图说明

图1为现有技术中的一种组网结构示意图；

图2为本发明实施例提供的路由迭代流程示意图；

图3为本发明实施例提供的路由器的结构示意图。

具体实施方式

在路由器上配置静态路由时，或者BGP路由器从邻居BGP路由器接收到 BGP路由时，通常由于该路由的下一跳不是本路由器直接可达的地址，因而触 发进行路由迭代。路由迭代完成后，路由器会将路由迭代结果下发本地路由表， 以便使用该路由迭代结果指导报文转发，对于BGP路由器来说，还会将迭代 结果继续向邻居BGP路由器扩散。

实际应用中，有些路由器的主控板上配置有RIB(Routing Information Base， 路由信息数据库)表，线卡板上配置有FIB(Forwarding Information Base，转 发信息数据库)表，针对这种路由器，通常在路由器主控板的RIB表中配置静 态路由，或者BGP路由器从邻居BGP路由器接收到BGP路由后将其配置到 主控板的RIB表中，此时会触发路由器主控板对该路由进行路由迭代。路由迭 代完成后，路由器主控板会将路由迭代结果下发到线卡板的FIB表中。

本发明实施例对上述流程中的路由迭代过程进行了改进。

本发明实施例中，路由器在路由迭代过程中记录迭代路由的迭代路径信 息，并根据记录的该迭代路由的迭代路径信息，在判断当前迭代到的依赖路由 为所述迭代路由本身或该依赖路由已经在迭代路由中出现过时，在路由表中除 了当前迭代到的依赖路由以外的路由中查找依赖路由进行路由迭代，如果在继 续迭代过程中迭代失败，则停止迭代过程，以避免出现循环迭代。

考虑到路由迭代过程中通常针对一条迭代路由，可迭代到多条路由，这些 路由各自对应的迭代路径称为子路径，所有子路径的集合称为该迭代路由的迭 代路径。如果迭代到多条等价路由，且这些等价路由具有相同转发信息(如出 接口或隧道)，此种情况下，路由器将这些等价路由所对应的子路径中长度最 短的子路径保留，而将其它子路径删除，以确保不会迭代出冗余的转发信息。 在进行上述冗余转发信息的处理之后，路由器判断本次路由迭代过程所得到的 迭代路径与该迭代路由前次路由迭代过程所得到的迭代路径是否相同，若相 同，则停止路由迭代过程。

图2示出了本发明实施例提供的路由迭代流程。通常，出现以下情况时， 将触发对迭代路由进行路由迭代：

情况1：在路由器上手工配置静态迭代路由；

情况2：从其它路由器接收到BGP路由；

情况3：迭代路由依赖的路由发生变化，即，迭代路由所依赖的路由前缀 发生了变化，就需要对迭代路由重新迭代。这里，依赖的路由前缀从单条变成 了等价。例如，该迭代路由RTA已经进行过路由迭代，但当RTB迭代出的路 由与RTC形成等价路由，而RTC是RTA的依赖路由，此时触发RTA重新进 行路由迭代。

如图2所示，该流程可包括：

步骤201，路由器的主控板以迭代路由的下一跳地址为目的地址，在主控 板的RIB表中查找下一跳地址直接可达的路由，进行路由迭代，得到迭代路径 并记录迭代路径。

该步骤中，在路由表中查找到的下一跳地址直接可达的路由，通常是IGP 路由。在匹配到迭代路由，且该迭代路由已经迭代出本路由器的出接口的情况 下，还包括该迭代路由。

在迭代过程中，根据记录的迭代路径进行判断，如出现迭代到迭代路由本 身，或相同依赖路由在同一迭代路径中出现超过一次，则判定为出现循环迭代， 需要在RIB表中(不包含当前找到的依赖路由)继续查找依赖路由，直至找到 不是循环迭代的依赖路由或迭代失败。

步骤202，迭代完成后，根据记录的迭代路径判断迭代到的路由中是否存 在转发信息相同的等价路由，如果有，则转入步骤203，否则转入步骤204。

该步骤中，如果针对一条路由迭代出多条等价路由，则检查是否存在转发 信息相同的情况，如果存在，则只保留这些等价路由的迭代路径中最短的一条， 以确保不会迭代出冗余的转发信息。其中，对于普通路由来说，所述转发信息 可以是接口或下一跳；对于MPLS(Multi-Protocol Label Switching，多协议标 签交换)路由来说，所述转发信息可以是隧道相关信息，如隧道标识。

步骤203，从转发信息相同的等价路由所对应的子路径中选择长度最短的 路径，将其保留在迭代路径中，将其它子路径从迭代路径中删除。然后转入步 骤204。

步骤204，判断本次迭代路径与该迭代路由前次的迭代路径是否相同，如 果相同，则结束路由迭代过程；否则，在该迭代路由下一次被触发重新迭代时 转入步骤201。

若上述流程中迭代到的路由与路由表中的IGP路由等价，且该IGP路由是 其它迭代路由的依赖路由时，则触发对该其它迭代路由进行重新迭代。所述其 它迭代路由的重新迭代过程与上述流程类似，在此不再赘述。

上述流程中，可将迭代路径记录在主控板的RIB表中，当然也可针对迭代 路由设置用于记录迭代路径信息的数据结构，并将迭代路由的迭代路径记录在 该数据结构中。

考虑到大量的迭代路由可能拥有相同的迭代路径，针对这种情况，本发明 实施例可以对迭代路径进行复用，以便节省内存，提高处理效率。具体的，可 以设置用于记录迭代路径信息的数据结构，将迭代路由的迭代路径记录在该数 据结构中，如果有多个迭代路由具有相同迭代路径，则针对这些迭代路由仅记 录一份迭代路径信息，即多个迭代路由若具有相同的迭代路径，则对应于些迭 代路由记录一份迭代路径。

通过上述流程，相同依赖路由在单条迭代路径上只能出现一次，一旦在单 条迭代路由上出现相同的依赖路由，则表明该迭代路径发生了循环迭代，此时 停止迭代过程，这样可以及时、准确检测并停止迭代，以避免出现循环路由。

下面仍以图1所示的场景为例，说明本发明实施提供的路由迭代流程。

如图1所示，该组网中包括路由器A、B、C和业务服务器Server1、Server2， Server1的IP地址为1.1.1.1，Server2的IP地址为2.2.2.2。在路由起A上配置 访问服务器的路由如下：

RT1：1.1.1.1/32 serial0

RT2：2.2.2.2/32 serial1

RT3：1.1.1.1/32 2.2.2.2

RT4：2.2.2.2/32 1.1.1.1

首先，RT3由于下一跳不是直接可达，迭代到RT2上，其迭代过程为：以 下一跳地址2.2.2.2为目的地址在RIB表中查找下一跳地址直接可达的路由， 找到RT2，将RT2的出接口作为RT3的出接口记录在RIB路由表中，迭代成 功，产生迭代路径：

2.2.2.2----＞2.2.2.2/32 serial1

RT3迭代成功后，与RT1形成等价路由。

RT4由于下一跳也不是直接可达，迭代到等价路由(RT1、RT3)上，其 迭代过程为：以下一跳地址1.1.1.1为目的地址在RIB表中查找下一跳地址直 接可达的路由，找到RT1和RT3(其中RT3经过上述路由迭代后已经确定出 本路由器上的出接口)。分别将RT1和RT3的出接口作为RT4的出接口记录在 RIB路由表中，产生迭代路径，其中包括2条子路径1和2：

1.1.1.1---＞[1]1.1.1.1/32 serial0

            [2]1.1.1.1/32 2.2.2.2----＞2.2.2.2/32 serial1

RT4迭代成功后，与RT2形成等价路由，触发RT3重新迭代，其迭代过 程为：以下一跳地址2.2.2.2为目的地址在RIB表中查找下一跳地址直接可达 的路由，找到RT2和RT4(其中RT3经过上述路由迭代后已经确定出本路由 器上的出接口)，产生迭代路径，其中包括3条子路径1、2、3：

2.2.2.2----＞[1]2.2.2.2/32 serial1

             [2]2.2.2.2/32 1.1.1.1----＞1.1.1.1/32 serial0

             [3]                        1.1.1.1/32 2.2.2.2----＞2.2.2.2/32 serial1

该迭代路径中，子路径1和3转发信息相同(即出接口相同)，因此只保 留迭代路径较短的子路径1，得到修正后的迭代路径：

2.2.2.2----＞[1]2.2.2.2/32 serial1

             [2]2.2.2.2/32 1.1.1.1----＞1.1.1.1/32 serial0

由于RT3是RT4的依赖路由，RT3重新迭代后，结果与上一次迭代不同， 因此触发RT4重新迭代，得到迭代路径：

1.1.1.1----＞[1]1.1.1.1/32 serial0

             [2]1.1.1.1/32 2.2.2.2----＞2.2.2.2/32 serial1

             [3]                        2.2.2.2/32 1.1.1.1----＞1.1.1.1/32 serial0

该迭代路径中，子路径1和3转发信息相同(即出接口相同)，因此只保 留迭代路径较短的子路径1，得到修正后的迭代路径：

1.1.1.1----＞[1]1.1.1.1/32 serial0

             [2]1.1.1.1/32 2.2.2.2----＞2.2.2.2/32 serial1

RT4重新迭代后，迭代结果与上一次相同，因此停止迭代。

至此，上述路由迭代过程结束。

应用本发明上述实施例，不仅可以解决循环迭代问题，还可以支持利用循 环迭代实现的互为备份的网络应用，例如上述图1所示的网络架构中，通过静 态配置的路由RT1、RT2、RT3、RT4，实际上配置了多条互为备份的转发路径， 在上述情形下能够准确迭代出有效转发信息且不会无休止地重复迭代。

需要说明的是，上述实施例是以路由器为例描述的，具有上述功能的设备 还可以是交换设备，如三层交换机。这里，将具有本发明实施例所提供的功能 的设备统称为路由交换设备。

基于相同的技术构思，本发明实施例还提供了一种路由交换设备，可应用 于上述流程。

参见图3，为本发明实施例提供的路由交换设备，该设备可包括主控板31 和线卡板32，主控板31可包括：

路由迭代模块311，用于当路由迭代被触发时，对迭代路由进行路由迭代 处理；其中，在进行路由迭代过程中记录迭代路由的迭代路径，并根据记录的 该迭代路由的迭代路径，在判断当前迭代到的依赖路由为所述迭代路由本身或 该依赖路由已经在迭代路由中出现过时，在路由表中除了当前迭代到的依赖路 由以外的路由中查找依赖路由进行路由迭代；

路由下发模块312，用于将路由迭代模块311的迭代结果下发到线卡板32 的路由表中，用以指导报文转发。

进一步的，路由迭代模块311还用于：如果在路由表中除了当前迭代到的 依赖路由以外的路由中，未查找到依赖路由，则停止路由迭代过程。

进一步的，路由迭代模块311还用于：如果针对一条迭代路由迭代得到多 条等价路由，且所述多条等价路由的转发信息相同，则根据所述多条等价路由 对应的迭代子路径，将其中长度最短的迭代子路径保留在该迭代路由的迭代路 径中，将其它迭代子路径从该迭代路由的迭代路径中删除；判断本次路由迭代 过程所得到的迭代路径与该迭代路由前次路由迭代过程所得到的迭代路径是 否相同，若相同，则停止路由迭代过程。其中，所述转发信息包括路由的出接 口或隧道标识。

具体的，路由迭代模块311在两条或两条以上迭代路由的迭代路径相同的 情况下，对应于具有相同迭代路径的迭代路由，仅记录一份迭代路径。

综上所述，本发明实施例通过在路由迭代过程中叠加记录完整的迭代路 径，并基于此检查相同依赖路由在单条迭代路径上只出现一次，对一条路由的 多条迭代路径，根据迭代路径长度优选相同转发信息的迭代路径，实现循环迭 代的准确检测、及时停止重复迭代，以及实现互为备份的网络应用。

本领域技术人员可以理解实施例中的装置中的模块可以按照实施例描述 进行分布于实施例的装置中，也可以进行相应变化位于不同于本实施例的一个 或多个装置中。上述实施例的模块可以合并为一个模块，也可以进一步拆分成 多个子模块。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明 可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很 多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上 或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机 软件产品存储在一个存储介质中，包括若干指令用以使得一台终端设备(可以 是手机，个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述 的方法。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通 技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰， 这些改进和润饰也应视本发明的保护范围。