CN101420415B - 形成路由表的方法及装置 - Google Patents

Abstract

本发明公开了一种形成路由表的方法，包括：为节点的匹配项分配匹配项存储空间以存储所述节点匹配项，使用匹配项位置标识指示所述节点匹配项所在的位置。本发明还公开了一种形成路由表的装置，包括：匹配项存储单元，用于为节点的匹配项分配匹配项存储空间以存储所述节点匹配项；匹配项位置标识单元，用于使用匹配项位置标识指示所述节点匹配项所在的位置。通过应用本发明可以有效减少路由表占用的内存资源。

Description

形成路由表的方法及装置

技术领域

本发明涉及通信技术领域，尤其涉及一种形成路由表的方法及装置。

背景技术

为了在用户众多的互联网络中完成由一地址到另一个地址的路由，通常将各种传输路径的相关数据存储在一起形成路由表，供进行路由时查询。

无类型域间路由(CIDR，Classless Inter-Domain Routing)是一种比较常用的路由表结构。在使用CIDR结构形成路由表时，一个网际协议(IP，InternetProtocol)网络使用一个前缀代表，这个前缀通常由IP网络的IP地址和和标识其有效位的掩码复合表示，例如“111^*”表示IP地址为“111”，有效位为三位，在存储时通常使用多比特树(Multi-Bit Tire)的方式进行存储，将在地址空间中相互邻近、路由相同的2的整数次幂个子网的路由表条目合并成一条路径，作为一个表项存储于路由表中，在进行查找时可以依照路径进行查找。

现以实例对存储的方法进行描述，假设有9个前缀“P1”“P2”“P3”“P4”“P5”“P6”“P7”“P8”“P9”，前缀标号与前缀值之间的关系如表1所示：

前缀标号	前缀值
		P1	*
P2	1*
		P3	00*
P4	101*
		P5	111*
P6	1000*
		P7	11101*

P8	111001*
		P9	1000011*

表1、前缀标号与前缀值之间的关系表

基本的二叉树搜索一步检查1个比特，若相应的地址前缀最长为M，则树的深度为M。如果一次检查K个比特则树的深度可减少到M/K，这样树的内部结点包含的匹配项增加为2的K次幂。这样的树被称为2的K次幂分支树，树的最大层数为M/K。查表算法在每个结点处检查的比特数为K，也就被称为树的步长。

假设该Multi-Bit Tire的步长为3，则树中每个节点将包含2的3次幂项，即8项，其结构如表2所示：

	匹配项	下一个节点的指针
			000	-	-
001	-	-
			010	-	-
011	-	-
			100	-	-
101	-	-
			110	-	-
111	-	-

表2、步长为3的节点结构

其中匹配项是指能与该项匹配的前缀，例如，“P1”的值为“*”，说明“P1”可以与任何一项匹配，假若该节点为根节点，初始记录为空时，从“000”到“111”都是“P1”的匹配项；“P2”的值为“1^*”，说明“P2”的IP地址为“1”，有效位为1位，任何以“1”开头的项都可以与“P2”匹配，假若该节点为根节点，从“100”到“111”都是“P2”的匹配项，此时若已存入“P1”，则在存入“P2”时，从“100”到“111”都将被“P2”覆盖；其它有效位在3位以内的前缀“P3”“P4”“P5”存储方式可以依此类推，“000”“001”为“P3”的匹配项，“101”为“P4”的匹配项，“111”为“P5”的匹配项，存入“P1”“P2”“P3”“P4”“P5”的节点结构如表3所示：

	匹配项	下一个节点的指针
			000	P3	-
001	P3	-
			010	P1	-
011	P1	-
			100	P2	-
101	P4	-
			110	P2	-
111	P5	-

表3、存入“P1”“P2”“P3”“P4”“P5”的节点结构

表2、表3中“下一个节点的指针”一栏存储的是指向下一级节点的指针，这是由于在前缀的有效位超过节点步长时，需要建立下一级节点，查找时根据这个指针就可以寻找到下一级节点，

以“P6”“P7”“P8”“P9”为例，“P6”的值为“1000^*”，说明“P6”的有效值为4位，在步长为3的根节点中寻找不到匹配项，因此在存入“P6”时需要建立下一级节点，根节点中“100”与“P6”的前三位匹配，因此要在“100”的“下一个节点的指针”一栏存入新建立的下一级节点指针，该新建立的下一级节点中，以“0”开头的表项都可以与“P6”匹配，存入“P6”的节点结构如表4所示：

	匹配项	下一个节点的指针
			000	P6	-
001	P6	-
			010	P6	-

011	P6	-
			100	-	-
101	-	-
			110	-	-
111	-	-

表4、存入“P6”的节点结构

“P7”的值为“11101^*”，“P8”的值为“111001^*”，其前3位值相同，都是“111”，因此可以为“P7”“P8”建立一个下一级节点，在根节点“111”的“下一个节点的指针”一栏存入新建立的下一级节点指针，该新建立的下一级节点中，以“01”开头的“010”“011”可与“P7”匹配，“001”可与“P8”匹配，存入“P7”“P8”的节点结构如表5所示：

	匹配项	下一个节点的指针
			000	-	-
001	P8	-
			010	P7	-
011	P7	-
			100	-	-
101	-	-
			110	-	-
111	-	-

表5、存入“P7”“P8”的节点结构

“P9”的值为“1000011^*”，有效值为7位，是节点步长“3”的2倍多，因此在根节点下一级节点的基础上还需要再建立一级新的节点，建立时，看现有的节点有没有可以与其前6位相匹配的项，若有则将新建立的节点指针填入该项“下一个节点的指针”一栏，若无则在根节点与其前3位相匹配项的“下一个节点的指针”一栏填入新建立的节点指针，本例中，表4所示存入  “P6”的节点“001”可与“P9”前6位匹配，因此在该项的“下一个节点的指针”一栏填入新建立的节点指针，新建立的项以“1”开头的表项都可以与“P9”匹配，存入“P9”的节点结构如表6所示：

	匹配项	下一个节点的指针
			000	-	-
001	-	-
			010	-	-
011	-	-
			100	P9	-
101	P9	-
			110	P9	-
111	P9	-

表6、存入“P9”的节点结构

至此，“P1”“P2”“P3”“P4”“P5”“P6”“P7”“P8”“P9”均已存入步长为3的Multi-Bit Tire，该Multi-Bit Tire完整结构如图1所示，包括：

相当于表3所示节点的根节点、相当于表4所示节点的节点1、相当于表5所示节点的节点2、相当于表6所示节点的节点3。

在对现有技术的研究和实践过程中，发明人发现现有技术存在以下问题：

每一个节点都需要申请固定大小的存储空间，而这些节点的表项大部分时候都没有填满，以图1为例，根节点有6栏为空白，节点1有11栏为空白，节点2有13栏为空白，节点3有12栏为空白，非常浪费内存资源，而在很多时候内存资源都是非常紧缺的资源。

发明内容

本发明实施例要解决的技术问题是提供一种形成路由表的方法及装置，可以减少路由表占用的内存资源。

为解决上述技术问题，本发明实施例一方面，提供了一种形成路由表的方法，包括：

为节点的匹配项分配匹配项存储空间以存储所述节点匹配项，使用匹配项位置标识指示所述节点匹配项所在的位置。

另一方面，提供了一种形成路由表的装置，包括：

匹配项存储单元，用于为节点的匹配项分配匹配项存储空间以存储所述节点匹配项；

匹配项位置标识单元，用于使用匹配项位置标识指示所述节点匹配项所在的位置。

由以上技术方案可以看出，由于本发明实施方式提供的技术方案根据节点实际存储匹配项的状况分配存储空间，而在实际使用中路由表中每个节点都有很大机会有大量空白表项，因此使用本发明实施方式提供的技术方案可以减少为空白表项分配的存储空间，有效减少路由表占用的内存资源。

附图说明

图1为现有技术示意图；

图2为本发明提供的形成路由表的方法实施例一中根节点匹配项部分结构图；

图3为本发明提供的形成路由表的方法实施例一中根节点指针部分结构图；

图4为本发明提供的形成路由表的方法实施例一中节点1结构图；

图5为本发明提供的形成路由表的方法实施例二中根节点匹配项部分结构图；

图6为本发明提供的形成路由表的方法实施例二中节点1匹配项部分结构图；

图7为本发明提供的形成路由表的装置实施例结构图。

具体实施方式

本发明提供了一种形成路由表的方法及装置，可以有效地节省路由表占用的内存资源。

在本发明提供的形成路由表的方法实施例中，为节点的匹配项分配匹配项存储空间以存储该节点的匹配项，使用匹配项位置标识指示所述节点匹配项所在的位置。

在该节点包含有指向下一个节点的指针时，根据所述节点的指向下一个节点的指针数量为该节点分配指针存储空间以存储指针，使用指针位置标识指示所述节点中指向下一个节点的指针所在的位置。

由于只为有内容的匹配项或下一个节点的指针分配存储空间，因此，使用本发明提供的形成路由表的方法实施例的路由表可以有效地节省其占用的内存资源。

本发明提供的形成路由表的方法的实施例一中，通常会根据一个节点的匹配项数量，为该节点分配一个匹配项存储空间以存储匹配项，使用匹配项位置标识指示所述节点匹配项所在的位置；在该节点包含有指向下一个节点的指针时，为该节点分配一个指针存储空间存储该指向下一个节点的指针，使用指针位置标识指示所述节点的指向下一个节点的指针所在的位置。

匹配项存储空间与匹配项位置标识可以被称为匹配项部分，指针存储空间与指针位置标识可以被称为指针部分。

以图1所示的根节点为例，该根节点中8个匹配项均有内容，其匹配项部分结构如图2所示：

根据该节点匹配项的数目“8”，为该节点分配一个可以容纳八个存储匹配项的匹配项存储空间，分别顺序存储“P3”“P3”“P1”“P1”“P2”“P4”“P2”“P5”；

由于该节点步长为“3”，因此该节点最多可存储八个匹配项，但很多时候并没有存到8个匹配项，而在匹配项存储空间中只存储匹配项的内容，并没有说明各匹配项对应的位置，因此在匹配项位置标识中需要进行相应的指示或标识。

在图2的例子中，由于节点最多可存储八个匹配项，因此为该节点建立的匹配项位置标识包括：八个标志位和指针201，这八个标志位顺序代表“000”“001”“010”“011”“100”“101”“110”“111”，每个标志位为1个比特，可以通过置“0”或置“1”来指示相应位置是否存储有匹配项，本实施例将以置“0”表示该项为空，置“1”表示该项存储有匹配项为例进行描述；指针201存储的是匹配项存储空间的指针，指向该节点的匹配项存储空间。

在图2中，由于每一项都存储有匹配项，因此八位标志位每一位都置“1”。

查找路由表时，通过图2，可以知道该节点的八个表项存储有匹配项，分别为：位于“000”的“P3”、位于“001”的“P3”、位于“010”的“P1”、位于“011”的“P1”、位于“100”的“P2”、位于“101”的“P4”、位于“110”的“P2”、位于“111”的“P5”。

由于图1所示根节点还包括2个指向下一个节点的指针，指向节点1的指针和指向节点2的指针，因此还需要为该节点分配指针部分，其指针部分如图3所示：

根据该节点的指向下一个节点的指针的数目“2”，为该节点分配一个可以存储两个存储指针的指针存储空间，分别顺序存储“指针1”“指针2”；

由于该节点步长为“3”，因此该节点最多可存储八个下一个节点的指针，但很多时候并没有存储8个指向下一个节点的指针，而在指针存储空间中只存储指向下一个节点的指针的内容，并没有说明各指向下一个节点的指针对应的位置，因此在指针位置标识中需要进行相应的指示。

在图3的例子中，由于节点最多可存储八个指针，因此为该节点建立的指针位置标识包括：八个标志位和指针301，这八个标志位顺序代表“000”“001”“010”“011”“100”“101”“110”“111”，每个标志位为1个比特，可以通过置“0”或置“1”来指示相应位置是否存储有下一个节点的指针，本实施例将以置“0”表示该项为空，置“1”表示该项存储有匹配项为例进行描述；指针301存储的是指针存储空间的指针，指向该节点的指针存储空间。

在图3中的指针1存储于“100”，指针2存储于“111”，因此将“100”对应的标志位置“1”，将“111”对应的标志位置“1”，将其余标志位置“0”，表示“指针1”“指针2”分别存储在这两个位置中，按照事先约定好的关系，例如本例中，以在前的存储于数值较小的表项，则可以知道指针1存储于“100”，指针2存储于“111”。定义方法有很多种，也可以使用从大到小的顺序排列。

此时本发明提供的形成路由表的方法实施例一，通过图2所示的匹配项部分和图3所示的指针部分保存了图1所示根节点的内容，通过比较可以发现，使用本发明提供的形成路由表的方法实施例一，不用为下一个节点指针表项为空的“000”“001”“010”“011”“101”“110”分配存储空间，大大节省了该根节点占用的内存资源。

空白表项越多的节点，使用本发明提供的形成路由表的方法实施例一占用的内存资源越少，以图1所示的节点1、节点2、节点3为例：

节点1中，存储有4项匹配项，一个指向下一个节点的指针，其节点结构如图4所示，节点包括：匹配项部分和指针部分。

匹配项部分为节点1分配了一个有四个存储匹配项位置的匹配项存储空间，分别顺序存储“P6”“P6”“P6”“P6”，匹配项位置标识包括：八个标志位和指针401，在与“000”“001”“010”“011”对应的标志位中置“1”，其他标志位置“0”，表示“P6”“P6”“P6”“P6”分别保存于“000”“001”“010”“011”，指针401存储的是匹配项存储空间的指针，指向节点1的匹配项存储空间。

指针部分为节点1分配了一个有一个存储指针位置的匹配项存储空间，存储“指针3”，位置指示包括：八个标志位和指针402，在与“001”对应的标志位中置“1”，其他标志位置“0”，表示“指针3”保存于“001”，指针402存储的是指针存储空间的指针，指向节点1的指针存储空间。

节点2和节点3的下一个节点的指针项全部为空，因此节点2和节点3都只有匹配项部分，其匹配项部分的结构可参考根节点和节点1的匹配项部分建立，在此不再详细描述。

以上是以步长为3的节点进行的描述，在步长为其他数值时，与使用本发明提供的形成路由表的方法实施例一的方法基本一致，在此不再详细描述。

在存储新的前缀，需要在一个节点中增加新的匹配项或指向下一个节点的指针时，重新为该节点分配存储空间，并删除旧的节点存储空间，具体做法如下：

节点在有新的匹配项加入时，为所述节点分配新的匹配项存储空间存储所述节点匹配项，建立新的匹配项位置标识指示所述节点匹配项所在的位置；并删除旧的匹配项存储空间与旧的匹配项位置标识。

节点在有新的指向下一个节点指针加入时，为所述节点分配新的指针存储空间存储所述节点的指针，建立新的指针位置标识指示所述节点的指向下一个节点的指针所在的位置，并删除旧的指针存储空间与旧的指针位置标识。

由于本发明提供的形成路由表的方法实施例一只为有内容的匹配项、或下一个节点的指针分配存储空间，而现有技术即使表项为空也要分配存储空间，并且在实际使用中，表项为空的现象非常常见，因此使用本发明提供的形成路由表的方法实施例一占用的内存资源大大小于现有技术占用的内存资源。

进一步，我们可以看到，由于有些前缀值的有效位不是步长倍数的前缀，会有多个匹配项，仍以图1为例，所示根节点中“P1”、“P2”和“P3”都分别有2个匹配项，节点1中“P6”有4个匹配项，节点2中“P7”有2个匹配项，节点3中“P9”有4个匹配项，这些重复的匹配项都要占去一位表项存储空间，为了减少重复匹配项占用的存储空间，节约内存资源，本发明提供的形成路由表的方法实施例二，为所述匹配项分段，判断位于同一段内的匹配项是否相同，相同则分配一位匹配项存储空间以存储所述相同的匹配项，并在分段指示位进行标记；不相同则为同一段内的匹配项各分配一位匹配项存储空间存储以所述不相同匹配项，并在分段指示位进行标记的方法。

下面仍以图1为例对本发明提供的形成路由表的方法实施例二进行描述：

以图1所示根节点为例，将该根节点匹配项分为4段，每段两项，其中有两段内的匹配项是相同的，因此其匹配项部分结构如图5所示：

因为本实施例中将匹配项分为4段，因此需要设立4个分段指示位分别对应4段，每个分段指示位为1个比特，可以通过置“0”或置“1”来指示相应分段内的匹配项是否相同，本实施例将以置“0”表示不同，置“1”表示相同为例进行描述。

由于第一段为两个“P3”，因此在匹配项存储空间相应为该段分配同一个表项存储位置，存储“P3”，在相应分段指示位置“1”，表示该段内的两个匹配项相同；第二段与第一段情况相同，为两个“P1”，同样在匹配项存储空间相应为该段分配同一个表项存储位置，存储“P1”，在相应分段指示位置“1”，表示该段内的两个匹配项相同；第三段和第四段中匹配项均不相同分别为“P2”、“P4”和“P2”、“P5”，因此仍然按照匹配项数目分别为其在匹配项存储空间分配两个表项存储位置，存储“P2”、“P4”和“P2”、“P5”，并在相应分段指示位置“0”，表示这两段内的两个匹配项不相同。

此时该根节点的匹配项存储空间共占用了6个表项存储位置，分别顺序存储“P3”“P1”“P2”“P4”“P2”“P5”，该根节点的匹配项位置标识包括：八个标志位和指针501，八个指示位均置“1”，指针501存储的是匹配项存储空间的指针，指向该节点的匹配项存储空间。

查找路由表时，通过匹配项位置标识可以知道该节点所有位置均存储有匹配项，通过第一段的分段指示位可以知道第一段中两个匹配项相同，且只保存了一次，再参照匹配项存储空间的内容，可以知道“000”和“001”都存储的是“P2”；通过第二段的分段指示位可以知道第二段中两个匹配项相同，且只保存了一次，再参照匹配项存储空间的内容，可以知道“010”和“011”都存储的是“P1”；通过第三段和第四段的分段指示位可以知道这两段内的两个匹配项不相同，再参照匹配项存储空间的内容，可以知道“100”“101”“110”“111”分别存储的是“P2”“P4”“P2”“P5”。

对一个节点匹配项的分段数目，根据实际情况可以是任何小于表项数目且可整除表项数目的整数，例如有8个匹配项的节点，则可以分为4段也可以分为2段或1段，以上是以分为4段为例进行的描述，现以图1所示节点1的匹配项分2段为例进行描述。

因为本实施例中将匹配项分为了2段，因此需要设立2个分段指示位分别对应2段，每个分段指示位为1个比特，可以通过置“0”或置“1”来指示相应分段内的匹配项是否相同，本实施例将以置“0”表示不同，置“1”表示相同为例进行描述。

该节点的匹配项位置标识包括：八个标志位和指针601，由于该节点“000”“001”“010”“011”存储有匹配项，而其他位为空，因此与“000”“001”“010”“011”指示位置“1”，其他标志位置“0”，指针601存储的是匹配项存储空间的指针，指向该节点的匹配项存储空间。

由于第一段为四个“P6”，因此在匹配项存储空间相应为该段分配一个表项存储位置，存储“P6”，在相应分段指示位置“1”，表示该段内的两个匹配项相同；第二段通过匹配项位置标识的标志位可以知道，第二段没有存储数据，因此置“0”或置“1”均可。

此时该根节点的匹配项存储空间共占用了1个表项存储位置，存储“P6”。

查找路由表时，因为有两个分段指示位，可以知道该节点匹配项被分为2段，通过第一段的分段指示位可以知道第一段中四个匹配项相同，且只保存了一次，再参照匹配项存储空间的内容，可以知道“000”“001”“010”“011”都存储的是“P6”；通过匹配项位置标识中“100”“101”“110”“111”对应的标志位，可以知道这些表项为空，未存储数据。

本发明提供的形成路由表的方法实施例二中的指针部分与本发明提供的形成路由表的方法实施例一基本相同，在此不再重复描述。

以上是以步长为3的节点进行的描述，在步长为其他数值时，使用本发明提供的形成路由表的方法实施例一的方法基本一致，在此不再详细描述。

在存储新的前缀，需要在一个节点中增加新的匹配项或指向下一个节点的指针时，重新为该节点分配存储空间，并删除旧的节点存储空间，具体做法如下：

节点在有新的匹配项加入时，为所述节点分配新的匹配项存储空间存储所述节点匹配项，建立新的匹配项位置标识指示所述节点匹配项所在的位置；并删除旧的匹配项存储空间与旧的匹配项位置标识。

节点在有新的指向下一个节点指针加入时，为所述节点分配新的指针存储空间存储所述节点的指针，建立新的指针位置标识指示所述节点的指向下一个节点的指针所在的位置，并删除旧的指针存储空间与旧的指针位置标识。

由于本发明提供的形成路由表的方法实施例二，将节点的匹配项进行分段，在分段中匹配项相同时，只分配一位匹配项存储空间存储所述相同的匹配项，并在分段指示位进行标记，因此使用本发明提供的形成路由表的方法实施例二占用的内存资源得到了有效的减少。

本发明提供的形成路由表的装置实施例结构如图7所示，形成路由表的装置700包括：

匹配项存储单元710，用于为节点的匹配项分配匹配项存储空间以存储所述节点匹配项；

匹配项位置标识单元720，用于使用匹配项位置标识指示所述节点匹配项所在的位置。

匹配项增加单元730，用于在所述节点有新的匹配项加入时，控制所述匹配项存储单710元与所述匹配项位置标识单元720为所述节点分配新的匹配项存储空间以存储所述节点匹配项，建立新的匹配项位置标识指示所述节点匹配项所在的位置；并删除旧的匹配项存储空间与旧的匹配项位置标识。

指针单元740，用于根据所述节点的指向下一个节点的指针数量，为所述节点分配指针存储空间以存储指针，使用指针位置标识指示所述节点的指向下一个节点的指针所在的位置。

指针增加单元750，用于在所述节点有新的指向下一个节点指针加入时，控制所述指针单元740为所述节点分配新的指针存储空间存储所述节点的指针，建立新的指针位置标识指示所述节点的指向下一个节点的指针所在的位置，并删除旧的指针存储空间与旧的指针位置标识。

其中，匹配项存储单元710进一步包括：

第一匹配项存储单元711，用于根据所述节点的匹配项数量为所述节点的匹配项分配匹配项存储空间以存储匹配项；

或第二匹配项存储单元712，用于将所述匹配项分段，在位于同一段内的匹配项相同时，分配同一匹配项存储空间以存储所述相同的匹配项，并在分段指示位进行标记；不相同时，为同一段内的匹配项各分配匹配项存储空间以存储所述不相同匹配项，并在分段指示位进行标记。

本发明提供的形成路由表的装置实施例的具体运作方式，可参考上文描述的本发明提供的形成路由表的方法实施例，在此不再详细描述。

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

以上对本发明所提供的一种本发明提供的形成路由表的方法及装置进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。

Claims (9)

1.一种形成路由表的方法，其特征在于，包括：

为节点的匹配项分配匹配项存储空间以存储所述节点匹配项，使用匹配项位置标识指示所述节点匹配项所在的位置；

所述为节点的匹配项分配匹配项存储空间存储匹配项包括：

将所述匹配项分段，在位于同一段内的匹配项相同时，分配同一匹配项存储空间以存储所述相同的匹配项，并在分段指示位进行标记；不相同时，为同一段内的匹配项各分配匹配项存储空间以存储所述不相同匹配项，并在分段指示位进行标记。

2.如权利要求1所述的形成路由表的方法，其特征在于，所述方法还包括：

根据所述节点的指向下一个节点的指针数量，为所述节点分配指针存储空间以存储指针，使用指针位置标识指示所述节点的指向下一个节点的指针所在的位置。

3.如权利要求1或2所述的形成路由表的方法，其特征在于，所述为节点的匹配项分配匹配项存储空间以存储所述匹配项包括：

根据所述节点的匹配项数量为所述节点的匹配项分配匹配项存储空间以存储匹配项。

4.如权利要求1或2所述的形成路由表的方法，其特征在于，所述方法还包括：

在所述节点有新的匹配项加入时，为所述节点分配新的匹配项存储空间以存储所述节点匹配项，建立新的匹配项位置标识以指示所述节点匹配项所在的位置；并删除旧的匹配项存储空间与旧的匹配项位置标识。

5.如权利要求2所述的形成路由表的方法，其特征在于，所述方法还包括：

在所述节点有新的指向下一个节点指针加入时，为所述节点分配新的指针存储空间存储所述节点的指针，建立新的指针位置标识指示所述节点的指向下一个节点的指针所在的位置，并删除旧的指针存储空间与旧的指针位置标识。

6.一种形成路由表的装置，其特征在于，包括：

匹配项存储单元，用于为节点的匹配项分配匹配项存储空间以存储所述节点匹配项；

匹配项位置标识单元，用于使用匹配项位置标识指示所述节点匹配项所在的位置；

所述匹配项存储单元包括：

第一匹配项存储单元，用于根据所述节点的匹配项数量为所述节点的匹配项分配匹配项存储空间以存储匹配项；

或第二匹配项存储单元，用于将所述匹配项分段，在位于同一段内的匹配项相同时，分配同一匹配项存储空间以存储所述相同的匹配项，并在分段指示位进行标记；不相同时，为同一段内的匹配项各分配匹配项存储空间以存储所述不相同匹配项，并在分段指示位进行标记。

7.如权利要求6所述的形成路由表的装置，其特征在于，所述装置还包括：

指针单元，用于根据所述节点的指向下一个节点的指针数量，为所述节点分配指针存储空间以存储指针，使用指针位置标识指示所述节点的指向下一个节点的指针所在的位置。

8.如权利要求6或7所述的形成路由表的装置，其特征在于，所述装置还包括：

匹配项增加单元，用于在所述节点有新的匹配项加入时，控制所述匹配项存储单元与所述匹配项位置标识单元为所述节点分配新的匹配项存储空间以存储所述节点匹配项，建立新的匹配项位置标识以指示所述节点匹配项所在的位置；并删除旧的匹配项存储空间与旧的匹配项位置标识。

9.如权利要求7所述的形成路由表的装置，其特征在于，所述装置还包括：

指针增加单元，用于在所述节点有新的指向下一个节点指针加入时，控制所述指针单元为所述节点分配新的指针存储空间存储所述节点的指针，建立新的指针位置标识指示所述节点的指向下一个节点的指针所在的位置，并删除旧的指针存储空间与旧的指针位置标识。

Images