CN101848133B - 一种前缀匹配的方法、装置和系统 - Google Patents

Abstract

本发明实施例提供了一种实现前缀匹配的方法，包括：按照前缀长度是否超过设定的前缀长度阈值将前缀分别存放到不同的存储区域内；在所述不同的存储区域内同时查询匹配的前缀，并将各自的查询结果发送给外部比较电路；所述外部比较电路对所述查询结果进行比较。本发明实施方式还提供一种实现前缀匹配的装置和系统。本发明实施例基于IPv6前缀长短不一的特点，通过设定前缀长度阈值，按照前缀长度的不同将前缀存放在不同的存储区域内，较长的前缀分配较大的存储空间，较短的前缀分配较小的存储空间，从而节约了存储器的空间。

Description

一种前缀匹配的方法、装置和系统

技术领域

本发明涉及通信技术领域，尤其涉及一种前缀匹配的方法、装置和系统。

背景技术

路由器在转发IP报文时，需要根据IP报文的目的地址去查询存储于TCAM(ternary content addressable memory，三重内容可寻址存储器)中的路由表，在TCAM中存储的路由表中，存储的是IP地址的前若干位，即前缀；路由器在查询路由表时采用最长前缀匹配规则，即选择与IP报文目的地址匹配位数最多的前缀所对应的端口进行转发。

随着网络规模的扩大和IPv6(Internet Protocol version 6，下一代互联网协议)的广泛使用，路由器需要支持的IPv6前缀的数目越来越多。但发明人发现，在现有技术中，对于IPv6前缀存储存在浪费存储空间，路由器成本较高的问题。

发明内容

一方面，本发明实施例提供了一种前缀匹配的方法，在一定程度上节约了存储器的空间，降低了路由器的成本。

为达到上述目的，本发明实施例采用如下技术方案：

一种前缀匹配的方法，包括：

按照前缀长度是否超过设定的前缀长度阈值将前缀分别存放到不同的存储区域内；

在所述不同的存储区域内同时查询匹配的前缀，并将各自的查询结果发送给外部比较电路；

所述外部比较电路对所述查询结果进行比较，得到最终匹配结果。

一方面，本发明实施例提供了一种前缀匹配的装置，在一定程度上节约了存储器的空间，降低了路由器的成本。

为达到上述目的，本发明实施例采用如下技术方案：

一种前缀匹配的装置，包括：

存储模块，用于存储前缀，包含多个存储区域；

分配模块，用于将前缀按照前缀长度是否超过前缀长度阈值分别存放到所述存储模块的不同的存储区域内；

查询模块，用于在所述存储模块的不同的存储区域内查询匹配的前缀，并将查询结果发送给外部比较电路；

外部比较电路，用于对所述查询模块的查询结果进行比较，得到最终匹配结果。

另一方面，本发明实施例提供了一种前缀匹配的系统，在一定程度上节约了存储器的空间，降低了路由器的成本。

为达到上述目的，本发明实施例采用如下技术方案：

一种前缀匹配的系统，包括：

所述第一存储区域，用于存放长度超过前缀长度阈值的前缀；

所述第二存储区域，用于存放长度小于或等于前缀长度阈值的前缀；

外部比较电路，用于接收在所述不同的存储区域查询的查询结果，并进行比较，得到最终匹配结果。

本发明实施例基于IPv6前缀长短不一的特点，通过设定前缀长度阈值，按照前缀长度的不同将前缀存放在不同的存储区域内，较长的前缀分配较大的存储空间，较短的前缀分配较小的存储空间，从而与现有技术相比，在一定程度上节约了存储器的空间，降低了路由器的成本。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作以简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的实现前缀匹配方法的流程图；

图2为本发明实施例提供的实现前缀匹配的装置的结构图；

图3为本发明实施例提供的查询模块的结构图；

图4为本发明实施例提供的实现前缀匹配的系统示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

为了解决现有前缀匹配技术浪费存储器资源、路由器成本过高的问题。本发明实施例提供了一种前缀匹配的方法。

如图1所示，本发明实施例提供的前缀匹配的方法，包括：

101、设定前缀长度阈值；

IPv6前缀长短不一，为了将IPv6的前缀按长度进行分类，需要设定一个前缀长度阈值，本发明实施例中，前缀长度阈值可以为64bit；

102、按照前缀长度是否超过设定的前缀长度阈值将前缀分别存放不同的存储区域内。

对要存储的前缀进行判断，若其长度大于64bit，则将其存储进第一存储区域，每个前缀分配128bit的存储空间；

若其长度小于64bit，则将其存储进第二存储区域，每个前缀分配64bit的存储空间；

由于大多数IPv6的前缀长度都不大于64bit，因此只有较少的IPv6前缀被存储进第一存储区域内；大多数的IPv6前缀则被存储进第二存储区域，每个前缀占用64bit的空间，与现有技术相比，节省了存储空间，降低了路由器成本；

103、在所述不同的存储区域内同时查询匹配的前缀，并将各自的查询结果发送给外部比较电路；

本发明实施例提供的查询前缀的方法具体为：

同时向第一存储区域和第二存储区域发送查询请求；

各存储区域在收到所述查询请求后，分别对自身存储的前缀进行查询；

查询后，各存储区域分别将各自的查询结果发送给外部比较电路。

104、所述外部比较电路接收到所述查询结果后，对其进行比较，得到最终匹配结果；

所述外部比较电路对查询结果比较，得到最终匹配结果的方法具体为：

若在所述第一存储区域能找到匹配的前缀，则将所述前缀确定为最终匹配的结果；若所述第一存储区域未能找到匹配的前缀，则将所述第二存储区域匹配的前缀确定为最终匹配结果；若在上述两存储区域均未找到匹配的前缀，则查询失败。

上述本发明实施例所提供的技术方案，通过设定前缀长度阈值，按照前缀长度的不同将前缀存放在不同的存储区域内，较长的前缀分配较大的存储空间，较短的前缀分配较小的存储空间，按照本发明实施例提供的查询方法，能够实现前缀的匹配，与现有技术相比，本发明节约了存储器的空间，降低了路由器的成本。

在本发明实施例中，只设定了一个前缀长度阈值，在实际应用中，可将本发明技术方案进行推广以进一步节省存储空间，根据需要设定多个前缀长度阈值，即将IPv6的前缀按照其长度不同，分别存放于多个不同的存储区域内；在查询时，可按照上述查询方法在多个存储区域内查询，并由外部比较电路对所述多个存储区域内的查询结果进行比较。

上述推广过程与本发明实施例及其类似，在此不再过多赘述。

如图2所示，本发明实施例提供的实现前缀匹配的装置，包括：

存储模块201，用于存储前缀，包含多个存储区域；

分配模块202，用于将前缀按照前缀长度是否超过前缀长度阈值分别存放到所述存储模块201的不同的存储区域内；

查询模块203，用于在所述存储模块201的不同的存储区域内查询匹配的前缀；并将查询的结果发送给外部比较电路；

外部比较电路204，用于对查询模块203的查询结果进行比较，得到最终匹配结果。

如图3所示，在本发明实施例中，所述查询模块203包括：

请求发送单元301，用于向存储模块201的各存储区域发送查询请求；

查询单元302，用于在存储模块201中各存储区域的前缀中查询匹配的前缀；

发送单元303，用于将查询单元302的查询结果发送给外部比较电路204。

本发明实施例提供的实现前缀匹配的装置，分配模块202按照前缀长度的不同将其分别存储于存储模块201中的不同存储区域中去，通过查询模块203对存储模块201中的不同存储区域分别进行查询，并将查询结果发送给外部比较电路204，由所述外部比较电路204对查询结果进行比较，实现了对存储在各存储区域内前缀的匹配，与现有技术相比，在一定程度上节约了存储器的空间，降低了路由器的成本。

如图4所示，本发明实施例提供一种实现前缀匹配的系统，包括：

两个并行连接的存储区域41a和41b和外部比较电路204，其中第一存储区域41a中存放长度超过前缀长度阈值的前缀，第二存储区域41b中存放长度小于或等于前缀长度阈值的前缀；

外部比较电路204，用于接收在所述不同的存储区域查询的查询结果，并进行比较，得到最终匹配结果。

所述实现前缀匹配的系统，还包括：

分配模块202，用于将前缀按照前缀长度是否超过前缀长度阈值分别存放到所述不同的存储区域内；

查询模块203，用于在所述不同的存储区域内查询匹配的前缀，并将查询结果发送给外部比较电路204。

如图3所示：所述查询模块203包括：

请求发送单元301，用于向所述不同的存储区域同时发送查询请求；

查询单元302，用于在所述不同的存储区域存储的前缀中查询匹配的前缀；

发送单元303，用于将查询单元的查询结果发送给所述外部比较电路204。

所述外部比较电路204，用于接收各存储区域的查询结果，并进行比较，得到最终匹配结果；具体为：若在第一存储区域41a能找到匹配的前缀，则将所述前缀确定为最终匹配的结果；若在第一存储区域41a未能找到匹配的前缀，则将第二存储区域41b匹配的前缀确定为最终匹配结果；若均未找到匹配的前缀，则查询失败。

在上述本发明实施例提供的实现前缀匹配的系统，将前缀按照长度的不同存放在不同的存储区域41内，并按照一定的连接方式和查询模块203，实现了前缀的匹配，与现有技术相比，节约了存储器的空间，降低了成本。

本发明实施例提供的实现前缀匹配的系统可以应用到路由器当中，在路由器中，将IP地址的前缀按照前缀长度是否超过前缀长度阈值进行分类，并将其分别存放到所述实现前缀匹配的系统中的不同存储区域内；

当路由器转发IP报文时，先获取IP报文的目的地址，然后将所述目的地址与所述不同存储区域内的前缀进行匹配，并对匹配的结果进行比较，最终找出相匹配的前缀，将所述IP报文从所述前缀所对应的端口转发出去。

在本发明实施例提供的路由器中，由于将前缀按照前缀长度是否超过前缀长度阈值分别存放到不同的存储区域内，较长的前缀分配较大的存储空间，较短的前缀分配较小的存储空间，从而与现有的路由器相比，节约了存储器的空间，降低了路由器的成本。

另外，本发明实施例还可以进一步推广，不限于IPv6前缀查询，在需要执行前缀匹配操作的系统中，均可以将前缀按长度分为两个或者多个部分，并分别存放在不同的存储区域内，在查询时查询两个部分或者多个部分，根据两个部分或者多个部分的查询结果判决得到最终的匹配结果，从而节约了存储器的存储空间，降低了成本，并且查询接口的带宽保持不变。

本领域普通技术人员可以理解：实现上述实施例方法中的全部或部分步骤可以通过程序来指令相关的硬件完成，所述的程序可以存储于计算机可读存储介质中，如ROM/RAM、磁碟或光盘等。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求所述的保护范围为准。

Claims (9)

1.一种前缀匹配的方法，其特征在于，包括：

按照前缀长度是否超过设定的前缀长度阈值将前缀分别存放到不同的存储区域内；

在所述不同的存储区域内同时查询匹配的前缀，并将各自的查询结果发送给外部比较电路；

所述外部比较电路对所述查询结果进行比较，得到最终匹配结果。

2.根据权利要求1所述的前缀匹配的方法，其特征在于，所述按照前缀长度是否超过设定的前缀长度阈值将前缀分别存放到不同的存储区域内包括：

将长度超过前缀长度阈值的前缀存放于第一存储区域，将长度小于或等于前缀长度阈值的前缀存放于第二存储区域。

3.根据权利要求1所述的前缀匹配的方法，其特征在于，所述在所述不同的存储区域内同时查询匹配的前缀，并将各自的查询结果发送给外部比较电路包括：

向所述不同的存储区域同时发送查询请求；

所述不同的存储区域接收到查询请求后，在所述不同的存储区域存储的前缀中查询匹配的前缀；

将各自的查询结果发送给外部比较电路。

4.根据权利要求1或2所述的前缀匹配的方法，其特征在于，所述外部比较电路对所述查询结果进行比较，得到最终匹配结果的步骤包括：

若在第一存储区域能找到匹配的前缀，则将所述前缀确定为最终匹配的结果；若在第一存储区域未能找到匹配的前缀，则将第二存储区域匹配的前缀确定为最终匹配结果；若均未找到匹配的前缀，则查询失败。

5.一种前缀匹配的装置，其特征在于，包括：

存储模块，用于存储前缀，包含多个存储区域；

分配模块，用于将前缀按照前缀长度是否超过前缀长度阈值分别存放到所述存储模块的不同的存储区域内；

查询模块，用于在所述存储模块的不同的存储区域内同时查询匹配的前缀，并将查询结果发送给外部比较电路；

外部比较电路，用于对所述查询模块的查询结果进行比较，得到最终匹配结果。

6.根据权利要求5所述的前缀匹配的装置，其特征在于，所述查询模块包括：

请求发送单元，用于向所述不同的存储区域同时发送查询请求；

查询单元，用于在所述不同的存储区域存储的前缀中查询匹配的前缀；

发送单元，用于将查询单元的查询结果发送给外部比较电路。

7.一种前缀匹配的系统，其特征在于，包括：两个并行连接的存储区域和外部比较电路；

所述第一存储区域，用于存放长度超过前缀长度阈值的前缀；

所述第二存储区域，用于存放长度小于或等于前缀长度阈值的前缀；

查询模块，用于在所述不同的存储区域内同时查询匹配的前缀，并将查询结果发送给外部比较电路；

外部比较电路，用于接收在所述不同的存储区域查询的查询结果，并进行比较，得到最终匹配结果。

8.根据权利要求7所述的系统，其特征在于，还包括：

分配模块，用于将前缀按照前缀长度是否超过前缀长度阈值分别存放到所述不同的存储区域内。

9.根据权利要求8所述的系统，其特征在于，所述查询模块包括：

请求发送单元，用于向所述不同的存储区域同时发送查询请求；

查询单元，用于在所述不同的存储区域存储的前缀中查询匹配的前缀；

发送单元，用于将查询单元的查询结果发送给所述外部比较电路。

Images