CN101039265A

CN101039265A - 一种路由器及路由转发方法

Info

Publication number: CN101039265A
Application number: CNA2007100277118A
Authority: CN
Inventors: 吴海博; 施勇; 涂伯颜
Original assignee: Tsinghua University; Huawei Technologies Co Ltd
Current assignee: Tsinghua University; Huawei Technologies Co Ltd
Priority date: 2007-04-25
Filing date: 2007-04-25
Publication date: 2007-09-19
Anticipated expiration: 2027-04-25
Also published as: CN100531144C

Abstract

本发明公开了一种路由转发方法，包括以下步骤：获得分组数据转发的全局路由转发信息，根据所述全局路由转发信息确定对所述分组数据转发的对外接口；查询所述对外接口与标签的映射关系，获得该分组数据的标签；用所述标签封装分组数据，并依照路由转发信息将分组数据转发至所述分组数据转发的对外接口。本发明还公开了一种路由器。采用本发明，路由器内部路由的问题得以解决，避免发生错误的路由和路由黑洞造成的丢包，从而提高了系统的鲁棒性，减少了路由恢复时间。

Description

一种路由器及路由转发方法

技术领域

本发明涉及通信技术领域，尤其涉及一种路由器及路由转发方法。

背景技术

随着互联网技术的发展，路由器的体系结构也发生着巨大的变化，新一代核心路由器硬件体系结构已经从集中控制方式发展到集群结构下分布式的处理方式。控制单元和转发单元路由转发方式(ForCES，Forwarding and ControlElement Separation)旨在将路由器内控制单元(CE，Control Element)和转发单元(FE，Forwarding Element)分离，通过定义标准接口施行统一的设计规范，是当前分布式路由器研究的重要方向。

参见图1，是现有技术的ForCES系统的结构示意图。

如图1所示，CE和多个FE通过网络互联构造了一个完整的ForCES路由器，CE负责路由的计算，执行控制和信令协议，并配置和管理FE，与CE之间通过ForCES协议进行通信的FE，根据来自CE的控制命令对分组数据进行相应的处理，通常用于转发分组数据。

ForCES系统必须可以支持上百个FE正常工作，FE数目众多，如何实现分组数据在FE间的路由转发是需要研究的内容。ForCES工作组目前已经提出了FE间的拓扑发现草案，但对于分组数据如何在路由器内部进行路由转发还没有具体的研究。

发明内容

本发明的实施例提供一种路由器及路由转发方法实现分组数据在路由器内部的路由及转发。

为了解决上述技术问题，本发明的实施例提出了一种路由器内部的路由转发方法，包括：

获得分组数据转发的全局路由转发信息，根据所述全局路由转发信息确定对所述分组数据转发的对外接口；

查询所述对外接口与标签的映射关系，获得该分组数据的标签；

用所述标签封装分组数据，并依照路由转发信息将分组数据转发至所述分组数据转发的对外接口。

相应地，本发明的实施例还提供了一种路由器，包括控制单元，其中，所述控制单元包括：

第一通信模块，用于向路由转发的对外接口发送地址信息并收集对外接口信息；

标签分配模块，用于根据所述对外接口信息对路由转发的对外接口分配标签；

转发信息计算模块，用于计算并相应更新转发信息，该转发信息指导分组数据发送至对外接口。

本发明的实施例还提供了一种路由器，包括至少一个转发单元，其中所述转发单元包括：

转发信息存储模块，用于存储该转发单元与其他转发单元间路径上的每个结点信息及其对应的转发信息；

标签封装模块，用于查询路由器下一跳地址获得到相应的标签并对分组数据进行封装；

转发模块，用于依照所述标签，查询所述转发信息，对分组数据进行转发。

本发明的实施例还提供了一种路由器，包括控制单元和至少一个转发单元，所述控制单元包括：

转发信息计算模块，用于计算并相应更新转发信息，该转发信息指导分组数据发送至对外接口；

所述转发单元包括：

实施本发明的实施例，具有如下有益效果：

本发明的实施例在拓扑发现草案的基础上提出了一种新的FE间路由方法，包括转发表更新算法和基于标签的转发策略，从而解决了路由器内部的路由问题。

附图说明

图1是现有技术的ForCES系统的结构示意图；

图2是本发明实施例的路由器的结构示意图；

图3是本发明实施例中路由器的控制单元与各个转发单元之间的拓扑关系示意图；

图4是本发明实施例中图3所述的控制单元中标签分配模块所分配的标签与接口的映射关系表示意图；

图5是本发明实施例中图3所述的转发单元中转发信息存储模块所存储的转发表示意图；

图6是本发明实施例中图3所述的转发单元中标签封装模块封装IP分组数据的组成示意图；

图7是本发明实施例中图3所述的转发单元中转发模块的结构示意图；

图8是本发明实施例提供的路由转发的方法流程图；

图9是本发明实施例提供的路由转发方法中计算最短路径的方法流程图；

图10是本发明实施例提供的路由转发方法中控制单元为转发单元计算和保存转发表内容并作相应更新的方法流程图；

图11是本发明实施例提供的路由转发方法中转发单元进行路由转发的方法流程图；

图12是本发明实施例提供的路由转发方法中的路由计算方法的运算时间随结点数目变化的示意图；

图13是本发明实施例提供的路由转发方法在理想情况下使用备份路径和不使用备份路径时路由恢复时间流程图。

具体实施方式

参见图2，是本发明实施例的路由器的结构示意图。

如图2所示，一个路由器内部可以包含一个控制单元1和多个转发单元，图示中用转发单元2至到转发单元N表示，控制单元1和多个转发单元之间通过ForCES协议进行通信，在此，以路由器包含一个转发单元1和五个转发单元为例，构造其拓扑关系如图3所示，转发单元可以认为是网络中的一个结点，其中，结点0、结点2、和结点4为边缘结点，分别有2个、2个、3个对外接口，其余的结点为内部结点。

结合图2和图3，详细说明发明实施例所提供的路由器的结构以及功能作用。

其中，控制单元1包括：

第一通信模块10，用于向所有的FE告知其自身的IP地址信息，以便FE向汇报信息。

相应的，转发单元2包括：

第二通信模块20，用于向控制单元1报告其自身的所有接口信息，包括数量各相应的IP地址，转发单元N中的通信模块N0具有与第二通信模块20相同的功能作用；

需要说明的是，相邻的转发单元之间通过定期发送Hello包来监测邻居信息，每个转发单元只记录自身的邻居信息，邻居失效可通过Hello超时来检测。所有转发单元将其邻居信息通过第二通信模块20告知控制单元1，控制单元1搜集这些信息后构造出图3所示的拓扑关系图。

所述控制单元1还包括有：

标签分配模块11，用于在所述第一通信模块10收到来自结点0、结点2和结点4所有出口的IP地址后，分配编号作为相应的接口标签，分配情况如图4所示，并将所述对应关系表保存在所有边缘结点，即结点0、结点2、结点4的映射表中；

转发信息计算模块12，用于为转发单元计算转发信息并作相应更新；

具体地，转发信息计算模块12包括：

最短路径计算模块120，利用拓扑信息进行最短路径的计算，计算出某一边缘结点，如结点0出发到所有其他边缘结点，如结点2和结点4的最短路径，同时保存各个结点相应转发表更新信息；

备份路径计算模块121，用于对于每条最短路径上的结点，假设下一跳失效，删除下一跳结点以及与之相应的边后，重新依次计算所有结点间的备份路径，所述备份路径上每个结点及其对应的备份转发表更新信息保存至所述转发表。例如，对于结点0，假设下一跳结点1失效，在图中删除下一跳结点1以及与之相关的边，重新计算0到出口结点4的最短路径，得路径结点0结点3结点2结点4，此处仅为举例，将0依次换为其他边缘结点例如：结点2和结点4作为最短路径计算的入口，重复以上操作，便可以完成备份路径的计算。

所述转发单元2还包括有：

转发信息存储模块21，用于存储所述控制单元1中的最短路径计算模块12以及备份路径上计算模块13计算所得的最短路径以及备份路径上每个结点及其对应的转发信息；所述转发信息存储模块21种存储的转发表的组成示意图如图5所示，其中标志位指明表项是主路径还是备份路径；

标签封装模块22，用于根据路由器下一跳IP地址获得得到相应的标签，并用所述标签封装分组数据，如图6所示：

转发模块23，用于依照所述标签，查询所述转发信息存储模块21中的转发信息将分组数据进行逐跳转发。

参见图7，是所述转发模块23的结构示意图，具体地，转发模块23包括：

链路检测子模块230，用于对路由转发的下一跳链路进行检测；

第一判断子模块231，用于判断所述链路检测子模块230所检测到的路由转发的下一跳链路是否失效；

转发子模块232，用于在所述链路检测子模块230检测到路由转发的下一跳链路有效时，查询所述转发表21，进行正常的路由转发，或在所述链路检测子模块230检测到路由转发的下一跳链路失效时，查找所述转发表21中的备份路径信息进行路由转发；

表项更新子模块233，用于删除所述失效链路对应的转发表21中的转发表项；

需要说明的是，在此，由所述第二通信子模块20告知所述控制单元1重新计算新的备份路径并更新相应的转发表项。

作为优选的实施方式，所述控制单元1还包括：

标签回收模块14，当转所述链路检测子模块230检测到下一跳链路失效，第二通信子模块20通知标签回收模块14，将相应的失效结点标签进行回收。

所述转发模块23还包括：

第二判断子模块234，用于判断路由转发的结点是否为出口结点；

标签解封装子模块235，用于在第二判断模块234判断到所述结点为出口结点时，路由转发的出口处，将分组数据的标签去掉，将分组数据转发出路由器。

作为一种优选的实施方式，控制单元1和转发单元2以及转发单元N等，部署在同一个硬件设备上，完成对路由的控制和转发。

需要说明的是，同样地，图2中所示的控制单元1和转发单元2以及转发单元N还可以分别独立，部署在不同的硬件设备上，即控制单元1部署在一个硬件设备上，构成一种用于控制路由转发的路由器，转发单元2至转发单元N部署在另一个硬件设上，构成专门转发路由信息的路由器，它们之间通过信息交互，同样可以完成对路由的控制和转发，其功能和作用与它们同时部署在一个硬件设备上的功能和作用相同，在此不再赘述。

参见图8，为本发明实施例提供的路由转发的方法流程图。

结合本发明实施例所构建的ForCES路由器说明本方法的具体流程，，本发明的实施例所构建的ForCES路由器包含一个CE和五个FE，此处仅为举例，本发明的实施例可以将控制单元和转发单元部署在不同的硬件设备上或者分别为单独的路由设备，将控制单元和转发单元通过网络互联构造一个完整的路由器。同样控制单元和转发单元可以在同一个路由设备上。

FE拓扑关系如图3所示，结点0，结点2和结点4为边缘结点，分别有2个，2个，3个对外接口，结点1、结点3为内部结点。

需要说明的是，相邻FE间通过定期发送Hello包来监测邻居信息，每个结点只记录自身的邻居信息，邻居失效可通过Hello超时来检测。所有FE将其邻居信息告知CE，CE搜集这些信息后构造出图3所示的拓扑关系图。

初始时CE告知FE自身的IP地址，以便FE向CE汇报信息，所有FE向CE报告自身所有接口信息，包括数量和相应IP地址。

首先，在步骤S100，CE收集到来自结点0、结点2和结点4的所有出口IP地址后根据所有转发单元的对外接口按序分配标签，分配情况如图4所示，建立标签与接口之间的映射关系，并保存在所有边缘结点的映射表中，即结点0，结点2，和结点4中。

在步骤S101，控制单元利用拓扑信息，进行路由计算，计算出从某一边缘结点出发到所有其他边缘结点的最短路径信息；

具体地，所述步骤S101中，CE利用拓扑信息进行最短路径计算，便可计算从某一边缘结点(如结点0)出发到所有其他边缘结点(如结点2和4)的最短路径信息。

在步骤S102，控制单元计算最短路径获得FE转发表更新信息；

在步骤S103，FE保存每个结点及其对应的转发表更新信息，更新FE的转发表；

在步骤S104，边缘结点接收到外界分组数据后，转发单元查找全局转发表，该全局转发表存有全局转发信息，获得到全局转发的下一跳链路，根据该下一跳链路确定出口FE；

在步骤S105，FE通过查询所述映射关系获得分组数据的标签；

在步骤S106，FE用所述标签封装分组数据，并查询所述转发表将分组数据转发至出后FE。。

参见图9，为本发明实施例提供的路由转发方法中计算最短路径的方法流程图。

结合图3所示的拓扑关系图，计算最短路径的具体的方法流程如下：

在步骤S200，设置集合S为已求得最短路径上的结点集合，数组D[i]用于存放0到结点i的距离，数组C[i，j]用于存放结点i到j的距离，P[i]存放结点0到结点i间最短路径的上结点i的前一个结点；

在步骤S201，初始时集合S中放置编号为0的结点，D[0]＝0，D[1]＝2，D[2]＝∞，D[3]＝6，D[4]＝∞，P[1]＝0，P[3]＝0；

在步骤S202，图3所示的拓扑关系图中有五个结点，所以共有四次循环：

第一次：在V-S中结点1的D[1]值最小，将1加入S，S＝{0，1}，并使D[2]＝5，P[2]＝1；

第二次：在V-S中结点2的D[2]值最小，将2加入S，S＝{0，1，2}，并使D[4]＝7，P[4]＝2；

第三次：在V-S中结点3的D[3]值最小，将3加入S，S＝{0，1，2，3}，D[4]无变化；

第四次：在V-S中结点4的D[4]值最小，将4加入S，S＝{0，1，2，3，4}，D[4]无变化。

参见图10，为本发明实施例提供的路由转发方法中控制单元为转发单元计算和保存转发表内容并作相应更新的方法流程图。

结合图3所示的拓扑关系图，控制单元为转发单元计算和保存转发表内容并作相应更新的方法流程如下：

在步骤S300，根据最短路径的计算方法，CE计算以结点0为起点的最短路径，并保存与其他边缘结点间最短路径上的所有结点(如0，4之间：0，1，2，4)同时保存各个结点相应转发表更新信息(如0，4之间)：

具体方法为：收集边缘结点4的所有出口IP地址(IP4，IP5，IP6)，查映射表得对应的标签集合(tag4，tag5，tag6)；

为结点0保存：(tag4，port0)，(tag5，port0)，(tag6，port0)

为结点1保存：(tag4，port1)，(tag5，port1)，(tag6，port1)

为结点2保存：(tag4，port2)，(tag5，port2)，(tag6，port2)

为结点4保存：(tag4，port2)，(tag5，port3)，(tag6，port4)

在步骤S301，控制单元计算并保存备份路径的转发表更新信息，对于上述结点0开始的每条最短路径，假设下一跳失效，删除图中下一跳结点以及与之相关的边后，利用最短路径计算方法重新计算最短路径，并保存路径上每个结点对应的转发表更新信息。

例如，对于结点0，假设下一跳1失效，在图中删除下一跳结点1以及与之相关的边，重新计算0到出口结点4的最短路径，得路径0-3-2-4，置0表项中标志位为备份并保存如下转发表更新信息：

为结点0保存：(tag4*，port1)(tag5*，port1)(tag6*，port1)(标志位用*表示)

为结点3保存：(tag4，port1)(tag5，port1)(tag6，port1)

为结点2保存：(tag4，port2)(tag5，port2)(tag6，port2)

为结点4保存：(tag4，port2)(tag5，port3)(tag6，port4)

当然极少数结点可能不再有符合条件的备份路径。

在步骤S302，将结点0依次换为其他边缘结点(结点2和结点4)作为最短路径计算的入口，重复步骤S300和步骤S301，完成对FE的所有转发表更新的保存。

在步骤S303，在此过程中可能会出现重复表项，如步骤S1020和S1021中为结点2都保存：(tag4，port2)，(tag5，port2)，(tag6，port2)，为此最后CE需先进行重复表项合并，再将所有更新信息下发到各个FE中。

参见图11，为本发明实施例提供的路由转发方法中转发单元进行路由转发的方法流程图。

结合图3所示的拓扑关系图，以结点0为入口结点4为出口为例，转发单元进行路由转发的方法流程如下：

在步骤S400，转发单元的边缘结点0接收路由器的外界分组数据；

在步骤S401，转发单元查全局转发表得整个路由器的下一跳IP地址；

在步骤S402，假设为下一跳的IP地址为IP4，转发单元查映射表得标签tag4；

在步骤S403，转发单元将结点0用标签tag4封装IP分组数据；

在步骤S404，结点通过发送Hello超时检测下一跳是否失效；若检测到链路失效，则转入步骤S405，若链路正常，则转入步骤S406；

在步骤S405，启用备份路径：(tag4，port1)，(tag5，port1)，(tag6，port1)改走0-3-2-4，置转发表中标志位为主，由于下游结点已有相应的转发表内容，所以可以正常转发；

需要说明的是，在启动备份路径后，转发单元将删除原表项(tag4，port0)，(tag5，port0)，(tag6，port0)，并且告知CE使其重新计算新的备份路径并更新相应FE中的转发表表项，此外CE要进行标签和标号的回收。

在步骤S406，查转发表将分组数据从接口IP0_0转发出去，逐跳转发直至分组数据到达出口结点4；

在步骤S407，判断结点4是否为路由转发的出口结点，若判断结果为是，则转入步骤S408，若判断结果为否，则转入步骤S404，继续进行链路是否失效的检测；

在步骤S408，通过查映射表确定标签tag4对应接口IP4，此时去掉标签后将分组数据从IP1转发出路由器。

实施本发明所提供的路由器及路由转发方法，具有以下优点：

第一，本发明所提供的路由转发方法，是基于标签的路由转发方法，分组数据之所以根据标签而没有直接使用出口IP地址来路由，是因为标签具有以下优点：

首先，引入标签可以容易区分分组数据的来源，根据有无标签可以方便地区分分组数据是外部分组数据还是内部分组数据，从而进行不同的处理；

其次，标签数目与外部接口数目一致，比起IP地址位数要小得多，所以查标签的效率高，同时可节约转发表空间。

第二，本发明实施例中所用及的路由计算的方法，具有良好的性能和扩展性。

图12给出了所述路由计算的方法运算时间随结点数目变化的情况，运算时间总体随结点数目的增加而增大，但由于实际FE数目的限制，所述路由计算方法的运行时间会停留在毫秒级，从而表明路由计算的方法具有良好的性能和一定的扩展性。由于所述路由计算的方法增加了转发表更新操作，分析可知所述路由计算方法的时间复杂度为：O(m*n²)。

第三，本发明实施例引入了备份路径对路由机制进行改进，提高了系统鲁棒性，与不采用备份路径相比减少了路由恢复时间。

图13从定性的角度给出了理想情况下使用备份路径和不使用备份路径时路由恢复时间。其中：a表示无备份路径，b表示有备份路径，c表示通信时间，d表示Hello检测时间，所谓理想情况是指所有的备份路径都存在的情况，因为有时备份路径可能并不存在，例如拓扑图中到某结点的路径上某处只有唯一通路，该路径上的结点失效后便不再存在备份路径，虽然这属于少数情况。从图中可以看到采用备份路径的恢复时间几乎与平均Hello超时时间一致，而不使用备份路径则增加了FE汇报，CE重新计算以及CE对FE路由更新的时间开销。

以上所揭露的仅为本发明一种较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。

Claims

1、一种路由转发方法，其特征在于，包括以下步骤：

2、如权利要求1所述的路由转发方法，其特征在于，所述查询对外接口与标签的映射关系之前还包括：

对路由转发的对外接口分配标签，并建立标签与对外接口之间的映射关系。

3、如权利要求1所述的路由转发方法，其特征在于，所述依照路由转发信息将分组数据转发至该分组数据转发的对外接口具体为：

计算并保存路由转发信息，更新各节点的路由转发信息；

依照所述路由转发信息将分组数据转发至该分组数据转发的对外接口。

4、如权利要求3所述的路由转发方法，其特征在于，所述计算并保存路由转发信息具体包括：

依次以任一结点作为入口结点计算到所有边缘结点的最短路径，确定所述最短路径上的所有结点，并保存各个结点相应的路由转发表更新信息。

5、如权利要求4所述的路由转发方法，其特征在于，所述计算并保存路由转发信息还包括：

对于所述每条最短路径上的结点，假设下一跳结点链路失效，删除所述下一跳结点以及与之相关的边后，重新计算最短路径，并保存路径上每个结点对应的路由转发表更新信息。

6、如权利要求5所述的路由转发方法，其特征在于，所述路由转发方法包括：

若下一跳结点链路失效，则删除所述结点链路对应的路由转发表项，启用备份路径路由，查找与所述备份路径相应的转发信息进行分组数据路由转发；

若下一跳结点链路有效，则查询原路由转发表信息进行分组数据路由转发。

7、如权利要求6所述的路由转发方法，其特征在于，所述路由转发方法还包括：

判断转发结点是否为出口结点，若判断结果为是，则转发单元在路由转发的出口处去掉标签，将分组数据转发出去，若判断结果为否，则继续检测下一跳结点。

8、如权利要求6或7中任一项所述的路由转发方法，其特征在于，所述方法还包括：检测到下一跳链路失效的消息后，将相应的失效结点标签进行回收。

9、一种路由器，包括控制单元，其特征在于，所述控制单元包括：

10、如权利要求9所述的一种路由器，其特征在于，所述转发信息计算模块具体包括：

最短路径计算模块，计算所有结点之间的最短路径，确定所述最短路径上所有结点，并保存各个结点相应的转发信息并作相应更新；

备份路径计算模块，用于对于每条最短路径上的结点，假设下一跳失效，删除下一跳结点以及相应的边后，重新依次计算所有结点间的备份路径，确定所述备份路径上所有结点，并保存各个结点相应的转发信息并作相应更新。

11、如权利要求9或10所述的一种路由器，其特征在于，所述控制单元还包括：

标签回收模块，用于得到下一跳链路失效的消息后，将相应的失效结点标签进行回收。

12、一种路由器，包括至少一个转发单元，其特征在于，所述转发单元包括：

13、如权利要求12所述的一种路由器，其特征在于，所述转发模块包括：

链路检测子模块，用于对路由转发的下一跳链路进行检测；

第一判断子模块，用于判断所述链路检测子模块所检测到的路由转发的下一跳链路是否失效；

转发子模块，用于在所述链路检测子模块检测到路由转发的下一跳链路有效时，查询所述转发信息中的最短路径信息，进行正常的路由转发，或在所述链路检测子模块检测到路由转发的下一跳链路失效时，查找所述转发信息中的备份路径信息进行路由转发；

表项更新子模块，用于删除所述失效链路对应的转发表项，并告知所述控制单元重新计算新的备份路径并更新相应的转发表项。

14、如权利要求12或13所述的一种路由器，其特征在于，所述转发信息计算模块还包括：

第二判断子模块，用于判断路由转发的结点是否为出口结点；

标签解封装子模块，用于在第二判断模块判断到所述结点为出口结点时，路由转发的出口处，将分组数据的标签去掉后转发出去。

15、一种路由器，包括控制单元和至少一个转发单元，其特征在于，所述控制单元包括：

所述转发单元包括：

16、如权利要求15所述的一种路由器，其特征在于，所述转发信息计算模块具体包括：

最短路径计算模块，根据结点间的拓扑关系利用路由表更新算法，计算所有结点之间的最短路径，保存所述最短路径上所有结点以及各个结点相应的转发信息并作相应更新；

备份路径计算模块，用于对于每条最短路径上的结点，假设下一跳失效，删除下一跳结点以及相应的边后，重新依次计算所有结点间的备份路径，保存所述备份路径上所有结点以及各个结点相应的转发信息并作相应更新。

17、如权利要求16所述的一种路由器，其特征在于，所述控制单元还包括：第一通信模块，用于与转发单元交互获取彼此的信息，包括向其发送其自身的IP地址。

18、如权利要求15至17中任一项所述的一种路由器，其特征在于，所述转发单元还包括：第二通信模块，用于向控制单元发送其自身的接口信息，包括数量和相应的IP地址，以及与其他转发单元交互获取彼此的信息。

19、如权利要求15至18中任一项所述的一种路由器，其特征在于，所述转发模块包括：

链路检测子模块，用于对路由转发的下一跳链路进行检测；

20、如权利要求15至18中任一项所述的一种路由器，其特征在于，所述转发模块还包括：

21、如权利要求15至18中任一项所述的一种路由器，其特征在于，所述控制单元还包括：

标签回收模块，用于得到转发单元检测到下一跳链路失效的消息后，将相应的失效结点标签进行回收。