CN108259326A - 路由表更新方法、装置、分配节点以及叶报文转发设备 - Google Patents

Abstract

一种路由表更新方法、装置、分配节点以及叶报文转发设备，该方法包括：分配节点接收入口节点发送的报文；所述报文为在存储在入口节点上的前置热点路由表中未匹配成功的报文；根据报文的目的IP地址在分配表中进行匹配项字段的匹配；若目的IP地址与分配表中的第一匹配项字段匹配成功，获取第一匹配项字段对应的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；确定第一查找节点拥塞并获取第一前缀子树的路由信息；将第一前缀子树的路由信息发送给入口节点，以更新前置热点路由表；和/或将第一前缀子树的路由信息添加至分配节点上存储的后置热点路由表中；后置热点路由表的路由表项和前置热点路由表的路由表项包含的字段相同。

Description

路由表更新方法、装置、分配节点以及叶报文转发设备

技术领域

本发明涉及通信技术领域，尤其涉及一种路由表更新方法、装置、分配节点以及叶报文转发设备。

背景技术

路由器的主要任务是进行网络协议(英文：Internet Protocol，简称：IP)报文转发，即根据报文头中的目的IP地址将到达路由器输入端口的报文转发到正确的出端口。路由查找就是根据报文的目的IP地址，查找路由器中的路由表，得到报文的出端口信息的过程。

随着网络的发展，路由器的吞吐量的需求逐步提高。在现有技术中，一种提高路由器的吞吐量的方法为水平扩展(Scale Out)，即整个路由器由多个盒子堆叠搭建而成，主要通过增加盒子数量来提升性能，容易实现规模效应从而降低成本。

以下描述一个现有技术中的水平扩展的分布式路由器以及路由查找方法。分布式路由器包括入口计算节点、反弹计算节点以及出口计算节点，进一步，还可以包括其它计算节点。入口计算节点接收网络报文，并确定将接收到的网络报文路由到哪个反弹计算节点。具体的，入口计算节点基于接收到的目的IP地址生成散列秘钥，每个散列密码与分布式路由器的不同计算节点(例如反弹计算节点)相对应，这样，入口计算节点确定具体的反弹计算节点之后，将网络报文发送给所确定的反弹计算节点而不执行路由查找。反弹计算节点基于目的IP地址确定将网络报文路由到哪儿。具体的，每个反弹计算节点存储不同的路由条目集合(例如子集、部分等)。反弹计算节点确定负责网络报文从分布式路由器的离开的具体的出口计算节点。

在该路由查找方法中，采用目的IP地址生成的散列秘钥进行路由表的分布式存放，会造成大量路由条目的重复，而且因为基于散列秘钥作分布式路由查找，所以会存在哈希(Hash)冲突，需要额外的机制来解决哈希冲突，另外还会造成虚假命中。因此，导致整个路由效率较低。

发明内容

本发明实施例提供一种路由表更新方法、装置、分配节点及叶报文转发设备，用以解决现有技术中分布式路由器的路由机制效率较低的技术问题。

第一方面，本发明实施例提供了一种路由表更新方法，该方法从报文转发系统的分配节点的角度进行说明。分配节点接收所述报文转发系统的入口节点发送的报文；所述报文为所述入口节点在存储在所述入口节点上的前置热点路由表中未匹配成功的报文。前置热点路由表的路由表项包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口节点的物理盒子号以及出端口。分配节点上存储有分配表，所述分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号。分配节点根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在所述分配表中进行所述匹配项字段的匹配；若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，分配节点获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；所述第一查找节点为所述报文转发系统的查找节点；分配节点确定所述第一查找节点拥塞，并获取所述第一前缀子树的路由信息。分配节点将所述第一前缀子树的路由信息发送给所述入口节点，所述第一前缀子树的路由信息用于更新所述前置热点路由表；和/或分配节点将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中；其中，所述后置热点路由表的路由表项包括所述前缀字段以及所述出端口字段。本发明实施例中的路由表更新方法，对分布式路由查找带来的拥塞情况反应及时，定位精确，而且更新及时，拥塞可以控制在毫秒级，所以不容易丢包，报文转发设备的处理器的负担也小。

在一个可能的设计中，分配节点确定所述第一查找节点拥塞，包括：分配节点将所述报文存入所述第一所述匹配项字段对应的队列中；分配节点确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，分配节点确定所述第一查找节点拥塞。通过该方法，可以快速的确定查找节点是否拥塞，提高拥塞控制的反应时间。

在一个可能的设计中，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，所述方法还包括：在将所述报文出队时，所述分配节点根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，分配节点将所述报文在所述后置热点路由表中进行匹配，并将所述报文发送给匹配成功的前缀字段对应的出口节点。通过该方法，报文不需要再发送给第一查找节点，所以可以降低第一查找节点的拥塞，提高报文转发效率。

在一个可能的设计中，分配节点将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中，包括：分配节点将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。通过该方法可以快速的判断报文的流向，提高报文处理的速度。

在一个可能的设计中，分配节点获取匹配成功的匹配项对应的前缀子树的路由信息，包括：分配节点发送更新请求消息给第一查找节点、分配节点所在的物理盒子上的处理器或SDN控制器，更新请求消息用于请求匹配成功的匹配项对应的前缀子树的路由信息；分配节点接收第一查找节点、所述处理器或SDN控制器发送的匹配项对应的前缀子树的路由信息。

在一个可能的设计中，所述更新请求消息包括所述前缀子树的标识和所述叶分配节点所在的物理盒子号。

第二方面，本发明实施例提供一种路由查找方法。该方法从报文转发系统的叶报文转发设备的角度进行描述。在该方法中，叶报文转发设备接收报文。叶报文转发设备根据所述报文的目的IP地址按照LPM原则在所述叶报文转发设备上存储的前置热点路由表中进行匹配；所述前置热点路由表的路由表项包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口叶报文转发设备标识以及出端口。若叶报文转发设备在所述前置热点路由表中未匹配成功，则根据所述的目的IP地址按照所述LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及核心报文转发设备标识字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述核心报文转发设备标识字段为所述一个前缀子树的路由信息所在的核心报文转发设备的标识；所述核心报文转发设备为所述报文转发系统的核心报文转发设备。若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，叶报文转发设备获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一核心报文转发设备的标识；叶报文转发设备确定所述第一核心报文转发设备拥塞，并获取所述第一前缀子树的路由信息；叶报文转发设备将所述第一前缀子树的路由信息更新至所述前置热点路由表；和/或所述叶报文转发设备将所述第一前缀子树的路由信息添加至所述叶报文转发设备上存储的后置热点路由表中；其中，所述后置热点路由表的路由表项包括所述前缀字段以及所述出端口字段。本发明实施例中的路由表更新方法，对分布式路由查找带来的拥塞情况反应及时，定位精确，而且更新及时，拥塞可以控制在毫秒级，所以不容易丢包，报文转发设备的处理器的负担也小。

在一个可能的设计中，所述叶报文转发设备确定所述核心报文转发设备拥塞，包括：叶报文转发设备将所述报文存入所述第一所述匹配项字段对应的队列中；叶报文转发设备确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，叶报文转发设备确定所述第一核心报文转发设备拥塞。

在一个可能的设计中，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，所述方法还包括：在将所述报文出队时，叶报文转发设备根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，叶报文转发设备将所述报文在所述后置热点路由表中进行匹配，并将所述报文发送给匹配成功的前缀字段对应的出口节点。

在一个可能的设计中，叶报文转发设备将所述第一前缀子树的路由信息添加至所述叶报文转发设备上存储的后置热点路由表中，包括：叶报文转发设备将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

在一个可能的设计中，所述前置热点路由表和所述后置热点路由表为同一个热点路由表。

在一个可能的设计中，叶报文转发设备获取匹配成功的匹配项对应的前缀子树的路由信息，包括：叶报文转发设备发送更新请求消息给第一核心报文转发设备、叶报文转发设备上的处理器或SDN控制器，更新请求消息用于请求匹配成功的匹配项对应的前缀子树的路由信息；叶报文转发设备接收第一核心报文转发设备、所述处理器或SDN控制器发送的匹配项对应的前缀子树的路由信息。

在一个可能的设计中，所述更新请求消息包括所述前缀子树的标识和所述叶报文转发设备标识。

第三方面，本发明实施例提供一种分配节点。该分配节点包括：发送端口、接收端口和处理器。发送端口可以用于执行前述第一方面中的路由表更新方法中发送的步骤。接收端口可以执行前述第一方面中的路由表更新方法中接收或获取的步骤。处理器可以执行前述第一方面中的路由表更新方法中添加、匹配或确定的步骤。

第四方面，本发明实施例提供一种路由表更新装置，所述路由表更新装置包括用于实现第一方面所述的方法的功能模块。

第五方面，本发明实施例提供一种叶报文转发设备。该叶报文转发设备包括：至少两个端口、发送端口、接收端口和处理器。发送端口可以用于执行前述第二方面中的路由表更新方法中发送的步骤。接收端口可以执行前述第二方面中的路由表更新方法中接收或获取的步骤。处理器可以执行前述第二方面中的路由表更新方法中添加、匹配或确定的步骤。

第六方面，本发明实施例还提供一种计算机存储介质，所述计算机存储介质上存储有程序代码，所述程序代码包括用于实现所述第一方面和第二方面的方法的任意可能的实现方式的指令。

附图说明

图1为本发明实施例提供的一种报文转发系统的结构图；

图2a-图2b为本发明实施例提供的一种前缀以及前缀子树的示意图；

图3为本发明实施例提供的另一种报文转发系统的结构图；

图4为本发明实施例提供的一种报文转发设备的结构图；

图5为本发明实施例提供的一种路由表更新方法的流程图；

图6为本发明实施例提供的一种匹配项对应的队列的示意图；

图7为本发明实施例提供的再一种报文转发系统的结构图；

图8为本发明实施例提供的另一种前缀子树的示意图；

图9为本发明实施例提供的另一种路由表更新方法的流程图；

图10为本发明实施例提供的一种路由表更新装置的功能框图。

具体实施方式

本发明实施例提供一种路由表更新方法、装置、分配节点以及叶报文转发设备，用以解决现有技术中分布式路由器的路由机制效率较低的技术问题。

以下将详细描述本发明实施例中方案的实施过程、目的。

本文中术语“和/或”，仅仅是一种描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。另外，本文中字符“/”，一般表示前后关联对象是一种“或”的关系。

为便于说明本发明实施例中的路由表更新方法，下面先介绍本发明实施例中的路由查找方法，及该方法可以应用的报文转发系统。请参考图1所示，为本发明实施例提供的一种可能的报文转发系统的结构图。如图1所示，该报文转发系统包括控制器、至少一个入口节点、至少一个分配节点、至少一个查找节点以及至少一个出口节点。在实际运用中，一个物理盒子可以只包括一种节点，也可以是多种节点的集合。例如，一个物理盒子可以既包括入口节点，也可以包括分配节点。一个物理盒子可以既包括入口节点，也可以包括查找节点。一个物理盒子可以既包括入口节点，也可以包括出口节点。一个物理盒子可以既包括分配节点，也可以包括查找节点。一个物理盒子可以既包括查找节点，也可以包括出口节点。一个物理盒子可以既包括入口节点，也可以包括分配节点和查找节点。一个物理盒子可以既包括入口节点，也可以包括分配节点和出口节点。一个物理盒子可以既包括入口节点，也可以包括查找节点和出口节点。一个物理盒子可以既包括分配节点，也可以包括查找节点和出口节点。一个物理盒子可以既包括入口节点，也可以包括分配节点、查找节点以及出口节点。控制器可以与各个节点是分开设置的，也可以是和任一种节点设置在同一物理盒子中。这些物理盒子堆叠形成路由器整机。当然，在实际运用中，这些物理盒子也可以是分散在不同的区域，由不同的厂商制造。

在图1所示的结构中，每种节点之间传递的是报文，例如入口节点接收报文，然后将报文发送给任一个分配节点，该分配节点在进行查找之后，将报文再传递给查找出的查找节点，然后查找节点在确定该报文的出口节点之后，就将该报文传递给确定出的出口节点，然后出口节点再将该报文进行转发给其它网元。

应理解，图1所示的结构中仅示出了报文转发系统一种可能的情形，但本发明实施例并不限于此。该报文转发系统还可包括其它元器件，本发明实施例不做限定。

入口节点上可以存储有热点路由表，热点路由表的路由表项包括前缀字段以及出端口字段，出端口字段包括报文转发系统的出口节点的物理盒子号以及出端口。热点路由表可以包括使用比较频繁的前缀。

可选的，前缀可以用“0”、“1”和“*”组成的三值位串表示。

在一个可能的例子中，热点路由表的路由表项包括前缀字段、出端口字段，例如表一所示。

前缀	出端口字段
		0000*	31-02

表一

在表一的例子中，该路由表项表示与前缀0000*匹配的报文需要从物理盒子号为31号的出口节点的02号出端口号进行转发。

分配节点上存储有分配表，每个分配节点上存储的分配表相同。分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号。

具体的，前缀树可以是二叉树也可以是多叉树。前缀树为根据前缀中的位串建立起来的二叉树或多叉树。如果每次考虑一位，则建立一棵二叉树，也称为单位Trie树。图2a示出了一颗单位前缀树。其中，前缀树包含11个真实前缀，图2a中左侧p0～p10，在单位Trie树中对应的节点用黑色圆圈表示，连接点用白色圆圈表示。如果每次考虑多位，则建立一棵多位Trie树。每次考虑的位数一般是固定的，称为Trie树的步长(英文：stride)。

多位Trie树可以看作按stride把一个单位Trie树分成多个子树，并为每个子树创建一个Trie节点。每个Trie节点均有一个关联前缀，一个Trie节点的关联前缀是该Trie节点对应的子树的根节点上的前缀值。

图2b示出了基于图2a中的前缀建立的stride等于3的多位Trie树。该多位Trie树包括7个Trie节点，如图2b中所示的Trie Node T1～Trie Node T7，每个Trie节点即为一个前缀子树。每个前缀子树中均包含至少一个真实前缀。每个Trie节点配置有一个前缀节点，例如前缀子树T1的根节点对应的前缀为p0，前缀子树T2的根节点对应的前缀为000*，该前缀并非真实前缀。

举例来说，基于图2b所示的各个前缀子树建立的分配表如表二所示。

匹配项	查找节点号
		*	10
000*	11
		100*	12
111*	13
		000010*	14
000011*	15
		111010*	16

表二

在表二中，第一个表项的匹配项字段为前缀子树T1的根节点对应的前缀，查找节点号字段为10，表示前缀子树T1的所有真实前缀(前缀p1和前缀p2)对应的路由信息都存储在物理盒子号为10的查找节点上。类似的，第二个表项的匹配项字段为前缀子树T2的根节点对应的前缀。第三个表项的匹配项字段为前缀子树T3的根节点对应的前缀。第四个表项的匹配项字段为前缀子树T4的根节点对应的前缀。第五个表项的匹配项字段为前缀子树T5的根节点对应的前缀。第六个表项的匹配项字段为前缀子树T6的根节点对应的前缀。第七个表项的匹配项字段为前缀子树T7的根节点对应的前缀。

对应的，查找节点上可以存储有真实路由表，该真实路由表可以存储部分前缀子树的所有真实前缀的路由信息。如此一来，每个查找节点只要维护部分真实前缀的路由表项，所以维护路由表所花费的资源就较少，而且也便于查找节点进行快速查找。

可选的，可以为每个前缀子树分配一个查找节点，或者一组查找节点。如果是一组查找节点，那么一组查找节点中的其中一个查找节点作为主查找节点，而其它查找节点可以作为备份查找节点。

真实路由表的表项包括至少一个前缀子树的真实前缀和对应的出口节点的物理盒子号及出端口。举例来说，物理盒子号为10的查找节点上的真实路由表项例如如表三所示。

真实前缀	出端口
		P1，0*	20-01
P2，10*	21-02

表三

表三示出的是前缀子树T1的路由信息，前缀子树T1包括两个真实前缀，分别为p1，表示为0*，p2，表示为10*。真实前缀填充在真实前缀字段，出端口字段为报文转发系统的出口节点的物理盒子号以及出端口。

在表三的例子中，第一个路由表项表示与前缀0*匹配的报文需要从物理盒子号为21号的出口节点的01号出端口号进行转发。

下面将描述如何进行路由查找。当有报文进入入口节点时，入口节点可以根据报文的目的IP地址在如表一所示的热点路由表中进行匹配，若匹配成功，则将该报文发送给匹配成功的前缀对应的出口节点进行转发。若匹配不成功，则入口节点可以随机选择一个分配节点，将报文发送给分配节点。分配节点根据该报文的目的IP地址按照LPM原则在如表二所示的分配表中进行匹配，若匹配成功，则获取匹配成功的匹配项对应的查找节点的物理盒子号，并将该报文发送给获取的物理盒子号对应的查找节点。该查找节点接收到报文后，根据该报文的目的IP地址按照LPM原则在如表三所示的真实路由表中进行匹配，获取到匹配成功的真实前缀对应的出口节点的物理盒子号和出端口，并将该报文发送给获取到的出口节点。出口节点就按照该出端口转发该报文。至此，一个报文在报文转发系统中的转发过程就结束了。

由以上描述可以看出，在本发明实施例中，真实路由表分布式存放在不同的查找节点上，所以可以使得路由表分布更均匀，而且降低了单个节点的路由表规格的压力。进一步，分配节点和查找节点在匹配时均采用LPM匹配原则，所以分配查找节点时，无冲突，也不会有虚假命中的情况，所以整体上路由查找效率较高。

需要说明的是，如果分配到某个查找节点的流量大于该查找节点的处理能力，则该查找节点会发生拥塞，甚至会丢包，所以增大了报文处理时延，降低了报文转发系统的吞吐率。针对该技术问题，本发明实施例提供了一种解决查找节点拥塞的方法，具体的，在图1所示的报文转发系统的架构中，分配节点在确定出报文需要发往的查找节点时，判断该查找节点是否拥塞，如果该查找节点拥塞，那么就获取该报文在分配表中匹配成功的前缀子树的路由信息，并将该前缀子树的路由信息发送给入口节点，使得入口节点能够将该前缀子树的路由信息及时的更新到热点路由表(为便于描述，下文称存储在入口节点上的热点路由表为前置热点路由表)。如此一来，入口节点在下次匹配热点路由表时，命中率会提高，那么分配给该查找节点进行路由查找的报文就会减少，所以就解决了查找节点拥塞的问题，进而降低了报文处理时延，提高了报文转发系统的吞吐率。

本发明实施例提供的解决查找节点拥塞的方法的另一种可能的实施方式请参考图3所示的报文转发系统，与图1所示的报文转发系统不同的是，分配节点和出口节点可以有连接关系，并在分配节点上可以设置后置热点路由表，后置热点路由表的结构与前置热点路由表的结构相同，例如均包括前缀字段以及出端口字段。分配节点可以在判断出某个查找节点拥塞时，获取该报文在分配表中匹配成功的前缀子树的路由信息，并将该前缀子树的路由信息添加到后置热点路由表中。如此一来，已经到达分配节点上的需要分配到该查找节点上的报文就可以在后置热点路由表中进行匹配，并将该报文发送给匹配成功的出口节点。出口节点就按照该出端口转发该报文，而无需再发送给该查找节点，那么发送给该查找节点进行路由查找的报文就会减少，所以就解决了查找节点拥塞的问题，进而降低了报文处理时延，提高了报文转发系统的吞吐率。

进一步，分配节点也可以将该前缀子树的路由信息发送给入口节点，使得入口节点能够将该前缀子树的路由信息及时的更新到前置热点路由表，入口节点在下次匹配热点路由表时，命中率会提高，那么分配给该查找节点进行路由查找的报文就会减少，所以就解决了查找节点拥塞的问题，进而降低了报文处理时延，提高了报文转发系统的吞吐率。

图3所示的报文转发系统与图1所示的报文转发系统相同的部分将不再赘述，请参考前述对图1所示的报文转发系统各节点的描述。

接下来请参考图4，图4为本发明实施例提供的报文转发设备的可能的结构图。该报文转发设备例如为上述入口节点、分配节点、查找节点、出口节点、控制器的一种可能的结构图。如图4所示，该报文转发设备包括：处理器10、发送端口20、接收端口30、存储器40。存储器40、发送端口20和接收端口30和处理器10可以通过总线进行连接。当然，在实际运用中，存储器40、发送端口20和接收端口30和处理器10之间可以不是总线结构，而可以是其它结构，例如星型结构，本申请不作具体限定。

可选的，处理器10具体可以是通用的中央处理器或特定应用集成电路(英文：Application Specific Integrated Circuit，简称：ASIC)，可以是一个或多个用于控制程序执行的集成电路，可以是使用现场可编程门阵列(英文：Field Programmable GateArray，简称：FPGA)开发的硬件电路，可以是基带处理器。

可选的，处理器10可以包括至少一个处理核心。

可选的，存储器40可以包括只读存储器(英文：Read Only Memory，简称：ROM)、随机存取存储器(英文：Random Access Memory，简称：RAM)和磁盘存储器中的一种或多种。存储器40用于存储处理器10运行时所需的数据和/或指令。存储器40的数量可以为一个或多个。存储器40还可以用于存储前述热点路由表、分配表、真实路由表。

可选的，发送端口20和接收端口30在物理上可以相互独立也可以集成在一起。

可选的发送端口20和接收端口30总和的数量为至少两个，用于报文输出的发送端口20也可以称为出端口，用于报文输入的接收端口30也可以称为入端口。

接下来请参考如图5所示，为本发明实施例提供的一种路由表更新方法的流程图。如图5所示，该方法包括：

步骤101：入口节点接收报文。例如入口节点接收从其它报文转发系统发送的报文，或者是入口节点接收与入口节点连接的主机或服务器发送的报文。通常报文包括报文头、报文正文以及校验码等。报文头中可以包括源IP地址，目的IP地址。

步骤102：入口节点根据报文的目的IP地址在前置热点路由表中进行匹配，以确定该报文的出端口信息，即出口节点所在的物理盒子号以及出端口。可选的，匹配的结果包括匹配成功和匹配不成功。若匹配成功，则入口节点将该报文发送给匹配成功的前缀字段对应的出端口信息中的出口节点，出口节点则根据出端口转发该报文。若匹配不成功，则执行步骤103，即将该报文发送给任一分配节点。通过该方法可以快速的进行报文转发，而且可以减轻分配节点和查找节点的负担。

举例来说，报文的目的IP地址为111110010(二进制描述，为便于描述，简化为9bits，在实际运用中，目的IP地址可以是其它长度，例如32bits)，在前述如表一所述的前置热点路由表中进行匹配，匹配的结果为未匹配成功，即前置热点路由表中并未存储该目的IP地址对应的路由信息，所以入口节点可以执行步骤103，将该报文发送给任一分配节点，例如第一分配节点。

可选的，在步骤103中，入口节点可以考虑负载均衡，将报文发送给当前工作量较小的分配节点。当然，在实际运用中，也可以是完全随机分配，也可以是轮流分配。

接收到该报文的分配节点可以执行步骤104，即根据报文的目的IP地址在分配表中进行匹配，例如采用LPM原则在前述描述的分配表中进行匹配项字段的匹配。若目的IP地址与分配表中的第一匹配项字段匹配成功，分配节点在步骤104中还获取匹配成功的匹配项对应的第一查找节点的物理盒子号。具体的，例如第一匹配项字段对应的第一前缀子树的路由信息所在的第一查找节点的物理盒子号，第一查找节点为该报文转发系统的查找节点。

举例来说，报文的目的IP地址为111110010，分配节点在前述表二所示的分配表中进行匹配，按照LPM原则进行匹配，会匹配到匹配项字段的第四项111*，那么分配节点就获取第四项111*对应的前缀子树的路由信息所在的查找节点的物理盒子号13。

在确定第一查找节点号后，分配节点执行步骤105，即确定第一查找节点是否拥塞。可选的，步骤105可以有多种实施方式，以下将举例进行说明。

步骤105的一种可能的实现方式为：分配节点将该报文存入第一匹配项字段对应的队列中；分配节点确定所述队列中的报文总长度是否超过预设阈值；若报文总长度超过预设阈值，分配节点确定第一查找节点拥塞。

在一个实际的例子中，分配节点可以为分配表中的每个匹配项字段建立一个队列，为便于描述，下文称为分配队列(英文：Root Queue，简称：RQ)，请一同参考图6所示，图6为每个匹配项字段建立的队列的示意图。在图6中，假设分配表的匹配项字段共有n条表项，n为正整数。所以可以为这n条匹配项分别建立一个RQ，共n个RQ。因为一个匹配项对应的前缀子树的路由信息可以存放在一个或多个查找节点上，所以一个RQ对应的报文可以存入与该RQ对应的一个或多个出口队列(英文：Output Queue，简称：OQ)中；因为多个匹配项对应的前缀子树的路由信息可以存放在同一个查找节点上，所以每个OQ可以存放至少两个RQ对应的报文。每个OQ与一个查找节点对应。因此，OQ的数量k为大于或等于2的整数。

需要说明的是，如果一个匹配项对应的前缀子树的路由信息存储在两个或两个以上的查找节点上(每个查找节点上存储的均为该前缀子树的全部路由信息)，那么该匹配项对应的RQ中的报文可以通过调度机制调度到这两个或两个以上的查找节点对应的OQ上，例如随机调度，或者是轮流调度。

可选的，报文存入OQ中后，可以按照先进先出的原则出队，发往对应的查找节点。若某个查找节点的查找能力不足以应付时，会发生拥塞，该拥塞会传递到对应的RQ，表现在RQ中，即RQ对应的报文拥塞，所以RQ对应的报文的总长度(或称为RQ的深度)会增加，当RQ的深度大于队列容量时，就会发生丢包。

因此，可以设置RQ的深度大于预设阈值时，即RQ对应的报文的总长度大于预设阈值时，则确定该查找节点拥塞。

以上举例说明了一种可能的确定第一查找节点是否拥塞的实例，但在实际运用中，也可以通过其它实施方式确定第一查找节点是否拥塞，例如当第一查找节点判断自己拥塞时，向所有分配节点发送通知信息，通知自身目前处于拥塞状态。再例如，分配节点判断调度到第一查找节点上的端口发包速率是否超过阈值，若发包速率超过阈值，则表示该第一查找节点拥塞，反之，则表示第一查找节点不拥塞。

不管是通过上述哪种方式确定第一查找节点拥塞，若确定第一查找节点不拥塞，分配节点就可以正常按照流程发送报文给第一查找节点。

若确定第一查找节点拥塞，分配节点可以执行步骤106，即获取匹配成功的匹配项对应的前缀子树的路由信息。例如获取匹配成功的第一匹配项对应的第一前缀子树的路由信息。

可选的，步骤106可以包括：步骤1061，分配节点发送更新请求消息，更新请求消息用于请求匹配成功的匹配项对应的前缀子树的路由信息；步骤1062：分配节点接收该前缀子树的路由信息。

具体的，在步骤1061中，分配节点可以向第一查找节点、分配节点所在的物理盒子中的处理器或者软件定义网络(英文：Software Defined Network，简称：SDN)控制器发送更新请求信息。因为第一查找节点为匹配成功的匹配项对应的前缀子树的路由信息所存放的节点，所以可以向第一查找节点请求该前缀子树的路由信息。处理器或者SDN控制器通常存储有全部节点的路由信息，所以也可以向处理器和SDN请求该前缀子树的路由信息。

可选的，分配节点发送的更新请求消息的格式例如如表五所示。

查找节点的物理盒子号

分配节点的物理盒子号

前缀子树的标识(ID)

表五

在表五中，查找节点的物理盒子号和分配节点的物理盒子号还可以用其它能够唯一标识一个查找节点或分配节点的标签代替。前缀子树的ID用来表示请请求的是哪个前缀子树的路由信息，所以可以填充前缀子树的ID，也可以填充前缀子树的根节点对应的前缀，即匹配成功的匹配项。

可选的，在第一查找节点、处理器或SDN控制器接收到分配节点发送的更新请求信息时，可以根据该更新请求信息获取该前缀子树的路由信息，并发送给请求的分配节点。举例来说，在接收到如表五所示的格式的更新请求信息时，可以根据前缀子树的ID获取该前缀子树的路由信息。然后按照分配节点的物理盒子号将获取到的该前缀子树的路由信息发送给该分配节点。

可选的，第一查找节点、处理器或SDN控制器发送的更新响应消息的格式例如如表六所示。

表六

在表六中，路由数量字段用于表示该更新响应消息中包含多少条路由信息，该字段为可选的字段。第i条路由信息字段(i为取值为1至p)用于填充路由信息。完成标志字段用于表示此次更新结束，因为在实际运用中，一次更新可以通过多个更新响应消息完成，所以完成标志字段用于告知分配节点此次更新是否结束。完成标志字段为可选的字段。

分配节点在接收到更新响应消息之后，可以根据前缀子树的ID获知该更新响应消息中的路由信息是哪个前缀子树的路由信息。

分配节点的物理盒子号可以使分配节点获知该更新响应消息是发送给自己的。

分配节点在接收到第一查找节点、处理器或SDN控制器发送的更新响应消息时，可以从更新响应消息中提取出该前缀子树的路由信息。

以上仅举例说明了更新请求消息和更新响应消息的一种可能的实现方式，在实际运用中，还可以采用类型的传输格式发送更新请求消息和更新响应消息，本发明实施例不作具体限定。

以上描述了一种可能的获取匹配成功的匹配项对应的前缀子树的路由信息，但在实际运用中，分配节点还可以通过其它方式获取该前缀子树的路由信息，本发明实施例不作具体限定。

在分配节点获取到该前缀子树的路由信息，例如第一前缀子树的路由信息之后，接下来可以只执行步骤107，即分配节点将该前缀子树的路由信息发送给入口节点；也可以只执行步骤109，即将该前缀子树的路由信息添加至分配节点上存储的后置热点路由表中；也可以既执行步骤107也执行步骤109。

在步骤107中，既可以将该前缀子树的路由信息发送给所有的入口节点，也可以只发送给报文来源的入口节点。对于入口节点和分配节点位于同一个物理盒子的情况，步骤107中发送路由信息可以是通过物理盒子内部的总线进行发送。对于入口节点和分配节点未位于同一个物理盒子的情况，步骤107中发送路由信息可以是通过物理盒子之间的通信线路进行发送。

在入口节点接收到分配节点发送的前缀子树的路由信息之后，入口节点就执行步骤108，即将该前缀子树的路由信息更新至前置热点路由表中。如此一来，当再有目的IP地址的最高位为该匹配项的报文到达入口节点时，入口节点利用目的IP地址在更新后的前置热点路由表中进行匹配，就会匹配成功，然后直接将报文发送给匹配成功的出口节点所在的物理盒子，入口节点可以将报文按照前述匹配成功的出端口进行转发。因为匹配成功的报文不会再发送给匹配节点，也不会进入RQ，所以分配给第一查找节点的报文的数量就降低了，所以第一查找节点的拥塞情况就会得到改善，分配节点的处理量也会下降。

另外，该实施例中的方法，对拥塞情况反应及时，定位精确(例如能精确定位到是哪个查找节点拥塞)，而且更新响应时间大约为2ms，所以拥塞控制在ms级，不容易丢包，处理器的处理负担小。

接下来介绍步骤109的具体实施过程。具体的，在分配节点上创建一个后置热点路由表，该后置热点路由表的格式可以相同。然后为分配表中的每个匹配项维护一个标志位，例如为每个RQ队列维护一个标志位。标志位的初始值为0、false或其它表征后置热点路由表无效的值。

可选的，当分配节点在步骤106中获取到匹配成功的匹配项对应的前缀子树的路由信息时，执行步骤109，将该前缀子树的路由信息存入后置热点路由表中。如此一来，当该前缀子树对应的RQ中的报文出队时，可以在后置热点路由表中进行匹配，就会匹配成功，然后分配节点直接将报文发送给匹配成功的出口节点所在的物理盒子，入口节点可以将报文按照前述匹配成功的出端口进行转发。因为匹配成功的报文不会再发送给第一查找节点，所以第一查找节点处理的报文的数量就降低了，所以第一查找节点的拥塞情况就会得到改善。

可选的，在步骤109的同时或之后，分配节点还将该前缀子树对应的RQ对应的标志位的值置为表征后置热点路由表有效的值。如此一来，当该前缀子树对应的RQ中的报文出队时，可以先检查该标志位，若标志位的值表征后置热点路由表无效，则直接将报文发送给对应的查找节点进行路由查找；若标志位的值表征后置热点路由表有效，则直接通过后置热点路由表进行路由查找。通过设置标志位，可以快速的判断报文的流向，提高报文处理的速度。

步骤109的实施例除了具有前述步骤107所描述的技术效果之外，还因为更新后置热点路由表的更新响应时间大约为4微秒(us)，更新信令占带宽大约0.128％，所以对拥塞的反应更及时。

需要说明的是，若既存在前置热点路由表，又存在后置热点路由表，那么在前述表五所示的更新请求消息中还可以包括对象字段，该对象字段用于表征请求更新的对象是前置热点路由表还是后置热点路由表。相应的，在表六所示的更新响应消息中也可以包括该对象字段。可选的，该对象字段可以用两个bit组成，第一个bit标识更新前置热点路由表，第二个bit标识更新后置热点路由表，例如10表示更新前置热点路由表，01表示更新后置热点路由表，11表示更新前置热点路由表和后置热点路由表。

图1所示的报文转发系统为从逻辑上划分各个节点，但在实际部署中，入口节点和分配节点可能在一个物理盒子中，即热点路由表和分配表存储在同一个物理设备上。例如在如图7所示的实际部署的报文转发系统的网络结构中，该网络结构为叶-脊(leaf-spine)的拓扑结构。该报文转发系统包括2m个叶交换机(分别为叶交换机1至叶交换机2m)及m个核心交换机(分别为核心交换机1至核心交换机m)，其中，m为正整数。每个叶交换机分别与m个核心交换机连接，每个核心交换机分别与2m个叶交换机连接。每个叶交换机还可以连接不超过m个的主机或服务器。当然，在实际运用中，图7中的交换机还可以是其它报文转发设备，例如路由器，本发明实施例不作具体限定。

在如图7所述的报文转发系统中，叶交换机即可以实现入口节点的功能，也可以实现分配节点的功能，所以叶交换机中可以同时存储热点路由表和分配表，所以当叶交换机查询热点路由表没有匹配成功时，可以在本地继续查找分配表。进一步，叶交换机也可以实现出口节点的功能。核心交换机可以实现查找节点的功能。

当然，图7只是示出了实际部署时的一种网络结构，在实际运用中，图5所示的方法同样适用于其它网络结构，例如基于胖树(英文：fat-tree)拓扑结构的3级克洛斯(clos)架构，例如更多级的clos架构。这些网络结构在实际实施图5所示的方法时，原理与图7的结构是相同或相似的，所以以下将以图7所示的报文转发系统为例详细描述这类clos架构中热点路由表的更新的实施过程。

如图8所示，为本实施例中的前缀子树的示意图。在图8所示的前缀子树中，共有4个前缀子树，分别为前缀子树T10至前缀子树T13。前缀子树T10的根前缀，即根节点为前缀R0。前缀子树T11的根前缀为前缀R1。前缀子树T12的根前缀为前缀R2。前缀子树T13的根前缀为前缀R3。前缀R0至前缀R3为非真实前缀。前缀R0至前缀R3分别会填充在分配表的匹配项字段。

前缀子树T10包含真实前缀p11和真实前缀p12。前缀子树T11包含真实前缀p13和真实前缀p17。前缀子树T12包含真实前缀p14、真实前缀p15和真实前缀p16。前缀子树T13包含真实前缀p18。真实前缀p11至真实前缀p18可以填充澡热点路由表、真实路由表中的前缀字段。

假设前缀子树T10和前缀子树T12的路由信息存放在核心交换机1中，那么核心交换机1上的存放的真实路由表例如如表七所示。

真实前缀	出端口
		p11:1*	2-01
p12：01*	4-03
		p14：1110*	7-02
p15:1111*	6-03
		p16:11110*	2-02

表七

假设前缀子树T11和前缀子树T13的路由信息存放在核心交换机3中，那么核心交换机3上的存放的真实路由表例如如表八所示。

真实前缀	出端口
		p13:0101*	4-01
p17：01000*	5-03
		p18：11110010*	6-02

表八

假设前缀子树T11的路由信息还存放在核心交换机2中，那么核心交换机2上的存放的真实路由表例如如表九所示。

真实前缀	出端口
		p13:0101*	4-01
p17：01000*	5-03

表九

假设前缀子树T13的路由信息还存放在核心交换机4中，那么核心交换机4上的存放的真实路由表例如如表十所示。

真实前缀	出端口
		p18：11110010*	6-02

表十

叶交换机上保存的分配表例如如表十一所示。

表十一

其中，表十一中，核心交换机标识字段对应前述分配表中的查找节点的物理盒子号。另外，在本实施例中，在分配表中可以增加RQ ID字段，用于填充每个匹配项对应的RQID。当然，在实际运用中，还可以通过另外建立一个匹配项与RQ ID的对应关系表。

接下来请同时参考图9，图9为本发明实施例中路由表更新方法的流程图。如图9所示，该方法包括：

步骤201：叶交换机接收报文。例如叶交换机1接收到一个主机发送的报文。

步骤202：叶交换机根据报文的目的IP地址在前置热点路由表中进行匹配。该步骤102的实施方式相同，所以在此不再赘述。

步骤203：若步骤202未匹配成功，叶交换机根据报文的目的IP地址在分配表中进行匹配，并获取匹配成功的匹配项对应的核心交换机标识。举例来说，报文的目的IP地址为111110010(二进制描述，方便描述，简化为9bits)，报文长度为1.2K。叶交换机1按照LPM原则查询前置热点路由表，并未匹配成功，所以叶交换机1又按照LPM原则查询例如表十一所示的分配表，命中第三个匹配项，即R2：111*，对应的核心交换机标识为核心交换机1。

步骤204：叶交换机确定该核心交换机是否拥塞。继续以前述例子为例进行说明，在命中第三个匹配项后，叶交换机1继续读取第三个匹配项对应的RQ ID为2。然后将报文存入RQ ID为2的队列中。此时RQ ID为2的队列的报文总长度(已有字节数加存入报文长度)例如变为10.2K。假设预设阈值为10K，那么此时RQ ID为2的队列的报文总长度已超过阈值，所以可以确定核心交换机1处于拥塞状态。

可选的，叶交换机上可以为每个RQ维护如表十二所示的状态信息。

表十二

因此，叶交换机可以根据表十二查询获取到每个RQ的报文的已有字节数，加上新存入的报文的长度，即可得到当前每个RQ的报文的总长度。当然，在实际运用中，还可以通过其它形式记录每个RQ的报文的已有字节数，本发明实施例不作具体限定。

步骤205：若该核心交换机拥塞，则获取匹配成功的匹配项对应的前缀子树的路由信息。

可选的，步骤205包括：步骤2051：叶交换机发送更新请求消息给该核心交换机、叶交换机上的处理器或SDN控制器；步骤2052：叶交换机接收匹配成功的匹配项对应的前缀子树的路由信息。

继续以前述例子为例进行说明，匹配成功的匹配项为第三项R2，对应的核心交换机为核心交换机1。因此，叶交换机1可以向核心交换机1、叶交换机1上的处理器或SDN控制器发送更新请求消息。发送给核心交换机的更新请求消息例如表十三所示，发送给处理器或SDN处理器的消息格式可以再增加一个字段，用于填充处理器或SDN控制器的通信地址即可，或者将表十三中的“核心交换机标识”字段替换为用于填充处理器或SDN控制器的通信地址的字段即可。

核心交换机标识	叶交换机标识	前缀子树的ID
			核心交换机1	叶交换机1	T12

表十三

当核心交换机1接收到如表十三所示的消息请求消息后，就将保存的前缀子树T12中的所有路由信息封装成更新响应消息，发送给叶交换机1。可选的，消息响应消息例如表十四所示。

表十四

在实际运用中，消息的长度是有限制的，那么可以通过多个消息来发送前缀子树的路由信息，例如分为如表十五所示的两个消息来发送。

表十五

步骤206：叶交换机将该前缀子树的路由信息更新至前置热点路由表中。举例来说，叶交换机1将前缀子树T12的路由信息更新至前置热点路由表中，那么前置热点路由表新增的表项如表十六所示。

前缀	出端口字段
		…	…
p14:1110*	7-02
		p15:1111*	6-03
p16:11110*	2-02

表十六

假设此时叶交换机1又接收到一个报文，报文的目的IP地址同样为111110010，那么叶交换机就会匹配如表十六所示的前置热点路由表，命中p15，获取匹配成功的真实前缀对应的出端口信息，即叶交换机7上的端口02。然后叶交换机1通过图7所示的报文转发系统将该报文发送给叶交换机7。该报文不需要再到分配表中进行匹配，也不需要存入RQ中，更不需要再发送给核心交换机1进行路由查找，所以可以降低分布式查表的拥塞。

若叶交换机上还设置有后置热点路由表，那么叶交换机还可以执行步骤207，即将该前缀子树的路由信息更新至后置热点路由表中。

举例来说，叶交换机1上为每个RQ维护如表十七所示的状态信息。

表十七

在叶交换机将前缀子树的路由信息更新至后置热点路由表中后，可以更新RQ ID为2的RQ的标志位为1，表征后置热点路由表有效。

可选的，在实际运用中，前置热点路由表和后置热点路由表可以是同一个表，也可以是分开的两个表。

在有标志位的情况下，报文出队时，可以先查询一下标志位，若标志位的值表征后置热点路由表有效，那么就可以查询该后置热点路由表，然后将报文转发给匹配成功的叶交换机。若标志位的值表征后置热点路由表无效，那么就可以将该报文发送给在分配表中匹配成功的核心交换机，进一步进行路由查找。

举例来说，在如表十七所示的状态下，此时队列1中的一个报文出队，该报文的长度为0.5K，则将队列1的深度更新为4K(已有字节数减去出队报文长度)。此时队列1对应的标志位为0，表征后置热点路由表无效，所以将该报文发送给核心交换机2或核心交换机3(随机选择或轮询，或根据调度器的调度结果选择)进行查询真实路由表。

此时又有一个报文进行报文转发系统，该报文的目的IP地址为010100001，报文长度为1.2K。叶交换机按照LPM原则查询分配表，命中第二个表项，即R1:010*。读取RQ的ID为1，那么就将该报文存入队列1中，队列1的深度更新为5.2K。假设预设阈值为5K，叶交换机则发送更新请求消息给核心交换机2或核心交换机3(随机选择或轮询，或根据调度器的调度结果选择)，或者也可以发给叶交换机的处理器或者SDN控制器。发送给核心交换机2的更新请求消息例如表十八所示。

核心交换机标识	叶交换机标识	前缀子树的ID
			核心交换机2	叶交换机1	T11

表十八

核心交换机2接收到该更新请求消息之后，将保持的前缀子树T11的所有路由信息封装成更新响应消息，发送给叶交换机1。该更新响应消息例如表十九所示。

表十九

叶交换机1接收到该更新响应消息之后，可以将路由信息存入后置热点路由表中，那么后置热点路由表新增的表项如表二十所示。

前缀	出端口字段
		…	…
p13:0101*	4-01
		p17:01000*	5-03

表二十

然后，叶交换机1更改队列1的标志位为1，表征后置热点路由表有效。

假设此时队列1的一个报文出队，该报文的目的IP地址为010110101，叶交换机1可以检查队列1的标志位的值，因为在前述步骤已更改为1，所以表征后置热点路由表有效，那么叶交换机1就可以利用该报文的目的IP地址按照LPM的原则查表，命中表项p13:0101*，获取出端口信息，即叶交换机4的端口01，然后转发该报文。该报文就不会再发送给核心交换机2和核心交换机3，从而降低分布式查表的拥塞。

由以上描述可以看出，本发明实施例中的更新路由表的方法，对分布式路由查找带来的拥塞情况反应及时，定位精确，而且更新及时，拥塞可以控制在毫秒级，所以不容易丢包，报文转发设备的处理器的负担也小。

基于同一发明构思，本发明实施例还提供一种报文转发设备(如图4所示)，该报文转发设备用于实现前述方法中的任意一种方法。

可选的，当该报文转发设备为分配节点时，接收端口30，用于接收报文转发系统的入口节点发送的报文；所述报文为所述入口节点在前置热点路由表中未匹配成功的报文；所述前置热点路由表的路由表项包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口节点的物理盒子号以及出端口；

处理器10，用于根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号。

处理器10还用于若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；所述第一查找节点为所述报文转发系统的查找节点；确定所述第一查找节点拥塞，并获取所述第一前缀子树的路由信息；发送端口20，用于将所述第一前缀子树的路由信息发送给所述入口节点，所述第一前缀子树的路由信息用于更新所述前置热点路由表；和/或处理器10还用于将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中；其中，所述后置热点路由表的路由表项包括所述前缀字段以及所述出端口字段。

可选的，处理器10用于：将所述报文存入所述第一所述匹配项字段对应的队列中；确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，确定所述第一查找节点拥塞。

可选的，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，处理器10用于：在将所述报文出队时，根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，所述分配节点将所述报文在所述后置热点路由表中进行匹配；发送端口20还用于将所述报文发送给匹配成功的前缀字段对应的出口节点。

可选的，处理器10用于将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

可选的，当图4中的报文转发设备为叶报文转发设备，例如前述叶交换机时，接收端口30，用于接收报文；处理器10，用于根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在所述叶报文转发设备上存储的前置热点路由表中进行匹配；所述前置热点路由表的路由表项包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口叶报文转发设备标识以及出端口；处理器10还用于若在所述前置热点路由表中未匹配成功，则根据所述的目的IP地址按照所述LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及核心报文转发设备标识字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述核心报文转发设备标识字段为所述一个前缀子树的路由信息所在的核心报文转发设备的标识；所述核心报文转发设备为所述报文转发系统的核心报文转发设备；若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一核心报文转发设备的标识；确定所述第一核心报文转发设备拥塞，并获取所述第一前缀子树的路由信息。

处理器10还用于将所述第一前缀子树的路由信息更新至所述前置热点路由表；和/或还用于将所述第一前缀子树的路由信息添加至所述叶报文转发设备上存储的后置热点路由表中；其中，所述后置热点路由表的路由表项包括所述前缀字段以及所述出端口字段。

可选的，处理器10用于将所述报文存入所述第一所述匹配项字段对应的队列中；确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，确定所述第一核心报文转发设备拥塞。

可选的，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，

处理器10还用于在将所述报文出队时，根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，将所述报文在所述后置热点路由表中进行匹配；发送端口20还用于将所述报文发送给匹配成功的前缀字段对应的出口节点。

可选的，处理器10用于将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

可选的，所述前置热点路由表和所述后置热点路由表为同一个热点路由表。

基于同一发明构思，本发明实施例还提供一种路由表更新装置，该路由表更新装置包括用于执行前述方法步骤的功能模块。在一种可能的实现方式中，如图10所示，该路由查找装置包括接收单元301、处理单元302以及发送单元303。

当该路由表更新装置为分配节点时，接收单元301，用于接收报文转发系统的入口节点发送的报文；所述报文为所述入口节点在前置热点路由表中未匹配成功的报文；所述前置热点路由表的路由表项包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口节点的物理盒子号以及出端口；处理单元302，用于根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号。

处理单元302还用于若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；所述第一查找节点为所述报文转发系统的查找节点；确定所述第一查找节点拥塞，并获取所述第一前缀子树的路由信息。

发送单元303，用于将所述第一前缀子树的路由信息发送给所述入口节点，所述第一前缀子树的路由信息用于更新所述前置热点路由表；和/或处理单元302还用于将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中；其中，所述后置热点路由表的路由表项包括所述前缀字段以及所述出端口字段。

可选的，处理单元302用于：将所述报文存入所述第一所述匹配项字段对应的队列中；确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，确定所述第一查找节点拥塞。

可选的，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，处理单元302用于：在将所述报文出队时，根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，所述分配节点将所述报文在所述后置热点路由表中进行匹配；发送单元303还用于将所述报文发送给匹配成功的前缀字段对应的出口节点。

可选的，处理单元302用于将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

前述实施例中的路由查找方法中的各种变化方式和具体实例同样适用于本实施例的路由表更新装置以及图4中的报文转发设备，通过前述对路由更新方法的详细描述，本领域技术人员可以清楚的知道本实施例中路由表更新装置以及图4中的报文转发设备的实施方法，所以为了说明书的简洁，在此不再详述。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明实施例可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

显然，本领域的技术人员可以对本申请进行各种改动和变型而不脱离本申请的精神和范围。这样，倘若本申请的这些修改和变型属于本申请权利要求及其等同技术的范围之内，则本申请也意图包含这些改动和变型在内。

Claims (22)

1.一种路由表更新方法，其特征在于，包括：

报文转发系统的分配节点接收所述报文转发系统的入口节点发送的报文；所述报文为所述入口节点在存储在所述入口节点上的前置热点路由表中未匹配成功的报文；所述分配节点上存储有分配表，所述分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号；

所述分配节点根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在所述分配表中进行所述匹配项字段的匹配；

若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，所述分配节点获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；所述第一查找节点为所述报文转发系统的查找节点；

所述分配节点确定所述第一查找节点拥塞，获取所述第一前缀子树的路由信息；

所述分配节点将所述第一前缀子树的路由信息发送给所述入口节点，所述第一前缀子树的路由信息用于更新所述前置热点路由表；和/或所述分配节点将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中；

其中，所述前置热点路由表和后置热点路由表的路由表项均包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口节点的物理盒子号以及出端口。

2.如权利要求1所述的方法，其特征在于，所述分配节点确定所述第一查找节点拥塞，包括：

所述分配节点将所述报文存入所述第一所述匹配项字段对应的队列中；

所述分配节点确定所述队列中的报文总长度是否超过预设阈值；

若所述报文总长度超过所述预设阈值，所述分配节点确定所述第一查找节点拥塞。

3.如权利要求2所述的方法，其特征在于，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，所述方法还包括：

在将所述报文出队时，所述分配节点根据所述队列对应的标志位确定所述后置热点路由表是否有效；

在所述后置热点路由表有效时，所述分配节点将所述报文在所述后置热点路由表中进行匹配，并将所述报文发送给匹配成功的前缀字段对应的出口节点。

4.如权利要求3所述的方法，其特征在于，所述分配节点将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中，包括：

所述分配节点将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

5.一种路由查找方法，其特征在于，包括：

报文转发系统的叶报文转发设备接收报文；

所述叶报文转发设备根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在所述叶报文转发设备上存储的前置热点路由表中进行匹配；

若叶报文转发设备在所述前置热点路由表中未匹配成功，则根据所述的目的IP地址按照所述LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及核心报文转发设备标识字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述核心报文转发设备标识字段为所述一个前缀子树的路由信息所在的核心报文转发设备的标识；所述核心报文转发设备为所述报文转发系统的核心报文转发设备；

若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，所述叶报文转发设备获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一核心报文转发设备的标识；

所述叶报文转发设备确定所述第一核心报文转发设备拥塞，并获取所述第一前缀子树的路由信息；

所述叶报文转发设备将所述第一前缀子树的路由信息更新至所述前置热点路由表；和/或所述叶报文转发设备将所述第一前缀子树的路由信息添加至所述叶报文转发设备上存储的后置热点路由表中；

其中，所述前置热点路由表和后置热点路由表的路由表项包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口叶报文转发设备标识以及出端口。

6.如权利要求5所述的方法，其特征在于，所述叶报文转发设备确定所述核心报文转发设备拥塞，包括：

所述叶报文转发设备将所述报文存入所述第一所述匹配项字段对应的队列中；

所述叶报文转发设备确定所述队列中的报文总长度是否超过预设阈值；

若所述报文总长度超过所述预设阈值，所述叶报文转发设备确定所述第一核心报文转发设备拥塞。

7.如权利要求6所述的方法，其特征在于，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，所述方法还包括：

在将所述报文出队时，所述叶报文转发设备根据所述队列对应的标志位确定所述后置热点路由表是否有效；

在所述后置热点路由表有效时，所述叶报文转发设备将所述报文在所述后置热点路由表中进行匹配，并将所述报文发送给匹配成功的前缀字段对应的出口节点。

8.如权利要求6所述的方法，其特征在于，所述叶报文转发设备将所述第一前缀子树的路由信息添加至所述叶报文转发设备上存储的后置热点路由表中，包括：

所述叶报文转发设备将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

9.如权利要求5-8中任一项所述的方法，其特征在于，所述前置热点路由表和所述后置热点路由表为同一个热点路由表。

10.一种路由表更新装置，其特征在于，包括：

接收单元，用于接收报文转发系统的入口节点发送的报文；所述报文为所述入口节点在前置热点路由表中未匹配成功的报文；

处理单元，用于根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号；

所述处理单元还用于若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；所述第一查找节点为所述报文转发系统的查找节点；确定所述第一查找节点拥塞；并获取所述第一前缀子树的路由信息；

发送单元，用于将所述第一前缀子树的路由信息发送给所述入口节点，所述第一前缀子树的路由信息用于更新所述前置热点路由表；和/或所述处理单元还用于将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中；其中，所述前置热点路由表和所述后置热点路由表的路由表项均包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口节点的物理盒子号以及出端口。

11.如权利要求10所述的装置，其特征在于，所述处理单元用于：将所述报文存入所述第一所述匹配项字段对应的队列中；确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，确定所述第一查找节点拥塞。

12.如权利要求11所述的装置，其特征在于，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，所述处理单元用于：在将所述报文出队时，根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，所述分配节点将所述报文在所述后置热点路由表中进行匹配；

所述发送单元还用于将所述报文发送给匹配成功的前缀字段对应的出口节点。

13.如权利要求12所述的装置，其特征在于，所述处理单元用于将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

14.一种分配节点，其特征在于，包括：

接收端口，用于接收报文转发系统的入口节点发送的报文；所述报文为所述入口节点在前置热点路由表中未匹配成功的报文；

处理器，用于根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及查找节点号字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述查找节点号字段为所述一个前缀子树的路由信息所在的查找节点的物理盒子号；

所述处理器还用于若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一查找节点的物理盒子号；所述第一查找节点为所述报文转发系统的查找节点；确定所述第一查找节点拥塞；并获取所述第一前缀子树的路由信息；

发送端口，用于将所述第一前缀子树的路由信息发送给所述入口节点，所述第一前缀子树的路由信息用于更新所述前置热点路由表；和/或，所述处理器还用于将所述第一前缀子树的路由信息添加至所述分配节点上存储的后置热点路由表中；其中，所述前置热点路由表和所述后置热点路由表的路由表项均包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口节点的物理盒子号以及出端口。

15.如权利要求14所述的分配节点，其特征在于，所述处理器用于：将所述报文存入所述第一所述匹配项字段对应的队列中；确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，确定所述第一查找节点拥塞。

16.如权利要求15所述的分配节点，其特征在于，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，所述处理器用于：在将所述报文出队时，根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，所述分配节点将所述报文在所述后置热点路由表中进行匹配；

所述发送端口还用于将所述报文发送给匹配成功的前缀字段对应的出口节点。

17.如权利要求16所述的分配节点，其特征在于，所述处理器用于将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

18.一种叶报文转发设备，其特征在于，包括：

接收端口，用于接收报文；

处理器，用于根据所述报文的目的网络协议IP地址按照最长前缀匹配LPM原则在所述叶报文转发设备上存储的前置热点路由表中进行匹配；

所述处理器还用于若在所述前置热点路由表中未匹配成功，则根据所述的目的IP地址按照所述LPM原则在分配表中进行所述匹配项字段的匹配；所述分配表的分配表项包括匹配项字段以及核心报文转发设备标识字段，所述匹配项字段为一个前缀子树的根节点对应的前缀，所述核心报文转发设备标识字段为所述一个前缀子树的路由信息所在的核心报文转发设备的标识；所述核心报文转发设备为所述报文转发系统的核心报文转发设备；若所述目的IP地址与所述分配表中的第一所述匹配项字段匹配成功，获取将所述第一所述匹配项字段作为前缀的第一前缀子树的路由信息所在的第一核心报文转发设备的标识；确定所述第一核心报文转发设备拥塞；并获取所述第一前缀子树的路由信息；

所述处理器还用于将所述第一前缀子树的路由信息更新至所述前置热点路由表；和/或还用于将所述第一前缀子树的路由信息添加至所述叶报文转发设备上存储的后置热点路由表中；其中，所述前置热点路由表和所述后置热点路由表的路由表项均包括前缀字段以及出端口字段，所述出端口字段包括所述报文转发系统的出口叶报文转发设备标识以及出端口。

19.如权利要求18所述的叶报文转发设备，其特征在于，所述处理器用于将所述报文存入所述第一所述匹配项字段对应的队列中；确定所述队列中的报文总长度是否超过预设阈值；若所述报文总长度超过所述预设阈值，确定所述第一核心报文转发设备拥塞。

20.如权利要求19所述的叶报文转发设备，其特征在于，所述叶报文转发设备还包括发送端口，所述队列对应一个标志位，所述标志位用于表征所述后置热点路由表是否有效，

所述处理器还用于在将所述报文出队时，根据所述队列对应的标志位确定所述后置热点路由表是否有效；在所述后置热点路由表有效时，将所述报文在所述后置热点路由表中进行匹配；

所述发送端口还用于将所述报文发送给匹配成功的前缀字段对应的出口节点。

21.如权利要求20所述的叶报文转发设备，其特征在于，所述处理器用于将所述第一前缀子树的路由信息添加至所述后置热点路由表中，并将所述队列对应的标志位的值置为表征所述后置热点路由表有效的值。

22.如权利要求18-21中任一项所述的叶报文转发设备，其特征在于，所述前置热点路由表和所述后置热点路由表为同一个热点路由表。