一种保存位图的方法和装置

摘要

本发明提出一种保存位图的方法和设备，其中方法包括：设置字典树(Trie树)节点对应的关键码长度；将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，创建Trie树并进行哈希(Hash)计算，将Hash值与位图的存储地址之间建立对应关系。本发明能够降低保存位图过程中的设备开销。

权利要求

1.一种保存位图的方法，其特征在于，所述方法用于当关键字为IP地址时，对位图对应规则中的IP地址与业务类型的组合所对应的位图进行保存；所述方法包括：设置各级字典树Trie树节点对应的关键码长度；

将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；

按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，为该IP地址配置对应的关键标识，创建相应的Trie树节点并保存该关键标识；为该IP地址所属的业务类型配置对应的组标识，对所述关键标识和组标识的组合进行哈希Hash计算，将计算得到的Hash值与所述IP地址与业务类型的组合所对应位图的存储地址之间建立对应关系；当所述Trie树节点有父节点时，对所述关键标识和父节点对应的业务类型组标识的组合进行Hash计算，将计算得到的Hash值与所述父节点位图的存储地址之间建立对应关系。

2.根据权利要求1所述的方法，其特征在于，所述Trie树包括N级节点，所述N为大于

2的自然数；

所述将位图对应规则中IP地址的掩码长度与关键码长度进行比较并根据比较结果将IP地址放入各级Trie树节点对应的队列为：当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

当IP地址的掩码长度大于n级Trie树节点的关键码长度、并且不大于n+1级Trie树节点的关键码长度时，将该IP地址放入n+1级Trie树节点对应的队列；其中，所述n为大于0且小于N的自然数。

3.根据权利要求2所述的方法，其特征在于，所述Trie树包括四级节点；

所述将位图对应规则中IP地址的掩码长度与关键码长度进行比较并根据比较结果将IP地址放入各级Trie树节点对应的队列为：当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

当IP地址的掩码长度大于一级Trie树节点的关键码长度、并且不大于二级Trie树节点的关键码长度时，将该IP地址放入二级Trie树节点对应的队列；

当IP地址的掩码长度大于二级Trie树节点的关键码长度、并且不大于三级Trie树节点的关键码长度时，将该IP地址放入三级Trie树节点对应的队列；

当IP地址的掩码长度大于三级Trie树节点的关键码长度、并且不大于四级Trie树节点的关键码长度时，将该IP地址放入四级Trie树节点对应的队列。

4.一种保存位图的装置，其特征在于，所述装置包括：

设置模块，用于设置各级Trie树节点对应的关键码长度；

分类模块，用于将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；

保存模块，用于按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，为该IP地址配置对应的关键标识，创建相应的Trie树节点并保存该关键标识；为该IP地址所属的业务类型配置对应的组标识，对所述关键标识和组标识的组合进行Hash计算，将计算得到的Hash值与所述IP地址与业务类型的组合所对应位图的存储地址之间建立对应关系；当所述Trie树节点有父节点时，对所述关键标识和父节点对应的业务类型组标识的组合进行Hash计算，将计算得到的Hash值与所述父节点位图的存储地址之间建立对应关系。

5.根据权利要求4所述的装置，其特征在于，当所述Trie树包括N级节点，N为大于2的自然数时，所述分类模块用于：当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

当IP地址的掩码长度大于n级Trie树节点的关键码长度、并且不大于n+1级Trie树节点的关键码长度时，将该IP地址放入n+1级Trie树节点对应的队列；其中，所述n为大于0且小于N的自然数。

6.根据权利要求5所述的装置，其特征在于，当所述Trie树包括四级节点时，所述分类模块用于：当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

当IP地址的掩码长度大于一级Trie树节点的关键码长度、并且不大于二级Trie树节点的关键码长度时，将该IP地址放入二级Trie树节点对应的队列；

当IP地址的掩码长度大于二级Trie树节点的关键码长度、并且不大于三级Trie树节点的关键码长度时，将该IP地址放入三级Trie树节点对应的队列；

当IP地址的掩码长度大于三级Trie树节点的关键码长度、并且不大于四级Trie树节点的关键码长度时，将该IP地址放入四级Trie树节点对应的队列。

7.一种路由器，其特征在于，所述路由器包括权利要求4所述的装置。

8.一种交换机，其特征在于，所述交换机包括权利要求4所述的装置。

说明书

一种保存位图的方法和装置

技术领域

[0001] 本发明涉及ACL位图算法技术领域，特别涉及一种保存位图的方法和装置。

背景技术

[0002] 访问控制列表(ACL，Access Control List)是一种流识别技术。网络设备为了过滤报文，需要配置一系列的ACL对报文进行分类。ACL包括一系列的匹配规则，其中匹配规则包括多个关键字。当收到报文后，网络设备按照ACL匹配规则优先级由高到低的顺序，依次对报文进行匹配，当匹配成功后，根据预先设定的策略对报文进行处理。

[0003] 为了实现报文的快速匹配，出现了一种ACL位图算法。其主要思想是，预先在网络设备中保存位图对应规则中所有关键字分别与业务类型所对应的ACL进行匹配的匹配结果，将该匹配结果称为位图；后续收到报文时，根据该报文关键字的实际取值及业务类型，查找对应的位图，最终得到与该报文匹配成功的ACL规则。

[0004] 例如，在网络设备中配置针对策略路由(PBR)业务的ACL，如表1所示：

[0005]规则标 源IP(sip) 目的IP 源端口 目的端口 协议 服务条 结果
识(rule (dip) (sport) (dport) 款(TOS) (Result)
id)
0 1.1.0.0/16 any any 2000-3000 6 any outif serial
2/0
1 1.1.0.0/24 any any any any 10 set pri
outif s 2/1
2 1.1.16.0/20 any 5000 any any any nexthop

[0006]2.1.1.1
3 any any any any any any deny

[0007] 表1

[0008] 在网络设备中配置针对网络地址翻译(NAT)业务的ACL，如表2所示：

[0009]规则标 源IP(sip) 目的IP 源端口 目的端口 协议 服务条 结果
识(rule (dip) (sport) (dport) 款(TOS) (Result)
id)
0 2.1.0.0/16 any any 80 6 any pool id 1
1 1.1.0.0/16 any any 80 17 any pool id 1
2 any any any any any any deny

[0010] 表2

[0011] 那么，以源IP为例，对于PBR业务，取值为1.1.0.0/16的源IP对应的位图为1001；而对于NAT业务，取值为1.1.0.0/16的源IP对应的位图为011。

[0012] 目前，保存位图的方法为：首先，为位图对应规则中关键字的可能取值配置关键标识(KID，Key Identifier)，为业务类型配置组标识(GID，GroupIdentifier)；之后，将该关键字可能取值对应的KID与所属业务类型对应的GID进行组合，并对该组合进行Hash计算，将计算的到的Hash值与所述关键字与业务类型的组合所对应位图的存储地址之间建立对应关系。如图1为现有技术中保存位图的方法逻辑示意图。假设关键字为源IP地址，为取值1.1.0.0/16分配对应的KID＝00；业务类型有PBR和NAT，为PBR分配对应的GID＝10，为NAT分配对应的GID＝11；当关键字取值为1.1.0.0/16、并且业务类型为PBR时，依据前面表一可知，其对应的位图为1001(满足规则为1，不满足规则为0)；当关键字取值为1.1.0.0/16、并且业务类型为NAT时，依据前面表二可知，其对应的位图为011。那么，保存位图的方式为：第一步，计算Hash(00+10)，将计算得到的Hash值与对应位图1001的存储地址之间建立对应关系；计算Hash(00+11)，将计算得到的Hash值与对应位图011的存储地址之间建立对应关系。第二步，将位图保存在对应存储地址指示的位置。

[0013] 当关键字为IP地址时，上述保存位图的方法有两种具体方式。

[0014] 第一种：分为两个阶段：第一阶段，为各个IP地址分配对应的KID，将KID采用字典树(Trie树)中的Trie树节点进行保存。第二阶段，遍历Trie树，对Trie树节点保存的KID及所属业务的GID的组合进行Hash计算，从而得到Hash表，Hash表的各个Hash值对应相应位图的存储地址；在第二阶段中，为了避免由于最长匹配原则引起的匹配错误，Trie树中的子节点还需要继承各级父节点所属业务的GID，并对本节点保存的KID及父节点所属业务的GID的组合进行Hash计算，将计算得到的Hash值对应父节点位图的存储地址。可见，对于子节点，需要依据所有父节点计算出Hash值，用于对应本节点位图的存储地址及父节点位图的存储地址。

[0015] 这种方式的缺点是：由于第二阶段需要遍历Trie树，而遍历Trie树的开销较大，时间复杂度较高，这就导致整个保存位图的过程开销较大。

[0016] 第二种：将上述方式的两个阶段穿插进行，即，在创建Trie树的同时进行Hash计算。具体来说，当为一个IP地址分配相应的Trie树节点后，采用该Trie树节点保存对应的KID；之后，将该KID及所属业务的GID的组合进行Hash计算，从而得到Hash表，Hash表的各个Hash值对应相应位图的存储地址。针对每个IP地址均进行上述相同的处理。

[0017] 这种方式仍然不能完全避免对Trie树的遍历，其原因是：由于IP地址的随机性，导致Trie树创建过程随机，这就使得创建一个新的Trie树节点时，该Trie树节点的子节点个数、位置均无法确定；然而，由于Trie树中的子节点需要继承各级父节点所属业务的GID，这就要求创建一个新的Trie树节点之后，遍历该Trie树节点的子Trie树，找到所有不为空的Trie树节点，使这些不为空的Trie树节点继承新创建的Trie树节点所属业务的GID。

[0018] 可见，现有的保存位图的方法均需要对Trie树进行遍历，导致保存位图的过程开销较大。

发明内容

[0019] 本发明提出一种保存位图的方法，能够降低保存位图过程中的设备开销。

[0020] 本发明还提出一种保存位图的装置，能够减低保存位图过程中的设备开销。

[0021] 本发明还提出一种路由器和交换机，能够减低保存位图过程中的设备开销。

[0022] 本发明的技术方案是这样实现的：

[0023] 一种保存位图的方法，所述方法用于当关键字为IP地址时，对IP地址与业务类型的组合所对应的位图进行保存；所述方法包括：

[0024] 设置各级字典树Trie树节点对应的关键码长度；

[0025] 将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；

[0026] 按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，为该IP地址配置对应的关键标识，创建相应的Trie树节点并保存该关键标识；为该IP地址所属的业务类型配置对应的组标识，对所述关键标识和组标识的组合进行哈希Hash计算，将计算得到的Hash值与所述IP地址与业务类型的组合所对应位图的存储地址之间建立对应关系；当所述Trie树节点有父节点时，对所述关键标识和父节点对应的业务类型组标识的组合进行Hash计算，将计算得到的Hash值与所述父节点位图的存储地址之间建立对应关系。

[0027] 一种保存位图的装置，包括：

[0028] 设置模块，用于设置各级Trie树节点对应的关键码长度；

[0029] 分类模块，用于将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；

[0030] 保存模块，用于按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，为该IP地址配置对应的关键标识，创建相应的Trie树节点并保存该关键标识；为该IP地址所属的业务类型配置对应的组标识，对所述关键标识和组标识的组合进行Hash计算，将计算得到的Hash值与所述IP地址与业务类型的组合所对应位图的存储地址之间建立对应关系；当所述Trie树节点有父节点时，对所述关键标识和父节点对应的业务类型组标识的组合进行Hash计算，将计算得到的Hash值与所述父节点位图的存储地址之间建立对应关系。

[0031] 一种路由器，该路由器包括上述保存位图的装置。

[0032] 一种交换机，该路由器包括上述保存位图的装置。

[0033] 综上可见，本发明提出的保存位图的方法和设备，在创建Trie树之前，首先按照IP地址的掩码长度对IP地址进行分类，将分类后的IP地址分别放入各级Trie树节点对应的队列中；之后逐级创建Trie树节点，用于保存为对应IP地址配置的关键标识，同时，对IP地址关键标识和所属业务组标识的组合进行Hash计算，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；并对IP地址关键标识父节点所属业务组标识的组合进行Hash计算，将计算得到的Hash值与父节点位图的存储地址之间建立对应关系。可见，本发明提出的方法和设备不需要在保存位图的过程中对Trie树进行遍历，因而能够降低设备开销。

附图说明

[0034] 图1为现有技术中保存位图的方法逻辑示意图；

[0035] 图2为本发明提出的保存位图的方法流程图；

[0036] 图3为本发明实施例第一步对IP地址进行分类保存的示意图；

[0037] 图4为本发明实施例第二步至第五步创建的Trie树结构示意图；

[0038] 图5为本发明实施例保存位图的装置结构示意图。

具体实施方式

[0039] 为使本发明的目的、技术手段和优点更为清楚明白，以下结合附图对本发明进一步详细描述。

[0040] 本发明提出一种保存位图的方法，用于当位图对应规则中的关键字为IP地址时，对IP地址的可能取值与业务类型的组合所对应的位图进行保存；参见图2，图2为本发明提出的保存位图的方法流程图，该方法包括：

[0041] 步骤201：设置各级Trie树节点对应的关键码长度；

[0042] 步骤202：将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；

[0043] 步骤203：按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，为该IP地址配置对应的关键标识，创建相应的Trie树节点并保存该关键标识；为该IP地址所属的业务类型配置对应的组标识，对所述关键标识和组标识的组合进行Hash计算，将计算得到的Hash值与所述IP地址与业务类型的组合所对应位图的存储地址之间建立对应关系；当所述Trie树节点有父节点时，对所述关键标识和父节点对应的业务类型组标识的组合进行Hash计算，将计算得到的Hash值与所述父节点位图的存储地址之间建立对应关系。

[0044] 上述步骤201中，各级关键码长度逐级增大，并且最高级别的关键码长度等于IP地址长度(即32位)。

[0045] 上述步骤201中，Trie树包括N级节点，其中N为大于2的自然数；

[0046] 上述步骤202具体包括：

[0047] 当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

[0048] 当IP地址的掩码长度大于n级Trie树节点的关键码长度、并且不大于n+1级Trie树节点的关键码长度时，将该IP地址放入n+1级Trie树节点对应的队列；其中，n为大于0且小于N的自然数。

[0049] 以下以Trie树包括4级节点，且各级节点对应的关键码长度分别为16、24、28、32为例，举具体的实施例进行详细介绍。具体过程包括：

[0050] 第一步：

[0051] 按照IP地址的掩码长度，对IP地址进行分类，分别放入各级Trie树节点对应的队列。

[0052] 具体分类方式为：

[0053] 当掩码长度≤16时，将IP地址放入一级Trie树节点对应的队列(以下简称一级队列)；

[0054] 当16＜掩码长度≤24时，将IP地址放入二级Trie树节点对应的队列(以下简称二级队列)；

[0055] 当24＜掩码长度≤28时，将IP地址放入三级Trie树节点对应的队列(以下简称三级队列)；

[0056] 当28＜掩码长度≤32时，将IP地址放入四级Trie树节点对应的队列(以下简称四级队列)；

[0057] 如图3为本发明实施例第一步对IP地址进行分类保存的示意图。

[0058] 第二步：

[0059] 依次提取一级队列中的各个IP地址，为该IP地址配置对应的KID，创建相应的Trie树节点并保存该KID。由于一级队列中IP地址的掩码均小于一级Trie树节点对应的关键码长度，因此，本步骤中创建的Trie树节点均为一级Trie树节点。

[0060] 如图4为本发明实施例创建的Trie树结构示意图。其中，第一行示出了本步骤创建的3个一级Trie树节点，分别用于保存一级队列中的IP00、IP01、IP02所对应的KID，即kid00、kid01、kid02。

[0061] 创建保存kid00的Trie树节点后，将IP00所属业务的GID配置为gid00，计算Hash(kid00+gid00)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系。

[0062] 创建保存kid01的Trie树节点后，将IP01所属业务的GID配置为gid01，计算Hash(kid01+gid01)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系。

[0063] 创建保存kid02的Trie树节点后，将IP02所属业务的GID配置为gid02，计算Hash(kid02+gid02)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系。

[0064] 第三步：

[0065] 依次提取二级队列中的各个IP地址，为该IP地址配置对应的KID，创建相应的Trie树节点并保存该KID。由于二级队列中IP地址的掩码均小于二级Trie树节点对应的关键码长度，因此，本步骤中创建的Trie树节点均为二级Trie树节点，并且在创建二级Trie树节点时，该Trie树中尚不存在低于二级的节点(例如，三级Trie树节点、四级Trie树节点等)。

[0066] 图4的第二行示出了本步骤创建的2个二级Trie树节点，分别用于保存二级队列中的IP10、IP11所对应的KID，即kid10、kid11。在本步骤中，创建的2个Trie树节点为上述kid00对应节点的子节点。

[0067] 创建保存kid10的Trie树节点后，将IP10所属业务的GID配置为gid10，计算Hash(kid10+gid10)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；

[0068] 另外，该Trie树节点继承其父节点的GID，即gid00，计算Hash(kid10+gid00)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系。

[0069] 创建保存kid11的Trie树节点后，将IP11所属业务的GID配置为gid11，计算Hash(kid11+gid11)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；

[0070] 另外，该Trie树节点继承其父节点的GID，即gid00，计算Hash(kid11+gid00)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系。

[0071] 第四步：

[0072] 依次提取三级队列中的各个IP地址，为该IP地址配置对应的KID，创建相应的Trie树节点并保存该KID。由于三级队列中IP地址的掩码均小于三级Trie树节点对应的关键码长度，因此，本步骤中创建的Trie树节点均为三级Trie树节点，并且在创建三级Trie树节点时，该Trie树中尚不存在低于三级的节点。

[0073] 图4的第三行示出了本步骤创建的2个三级Trie树节点，分别用于保存三级队列中的IP20、IP21所对应的KID，即kid20、kid21。在本步骤中，创建的2个Trie树节点为上述kid10对应节点的子节点。

[0074] 创建保存kid20的Trie树节点后，将IP20所属业务的GID配置为gid20，计算Hash(kid20+gid20)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；

[0075] 另 外，该 Trie树 节 点 继 承 其 一 级 父 节 点 的 GID，即gid00，计 算Hash(kid20+gid00)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系；

[0076] 并 且，该 Trie树 节 点 继 承 其 二 级 父 节 点 的 GID，即gid10，计 算Hash(kid20+gid10)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系。

[0077] 创建保存kid21的Trie树节点后，将IP21所属业务的GID配置为gid21，计算Hash(kid21+gid21)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；

[0078] 另 外，该 Trie树 节 点 继 承 其 一 级 父 节 点 的 GID，即gid00，计 算Hash(kid21+gid00)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系；

[0079] 并 且，该 Trie树 节 点 继 承 其 二 级 父 节 点 的 GID，即gid10，计 算Hash(kid21+gid10)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系。

[0080] 第五步：

[0081] 依次提取四级队列中的各个IP地址，为该IP地址配置对应的KID，创建相应的Trie树节点并保存该KID。由于四级队列中IP地址的掩码均小于四级Trie树节点对应的关键码长度，因此，本步骤中创建的Trie树节点均为四级Trie树节点。

[0082] 图4的第四行示出了本步骤创建的2个四级Trie树节点，分别用于保存四级队列中的IP30、IP31所对应的KID，即kid30、kid31。在本步骤中，创建的2个Trie树节点为上述kid20对应节点的子节点。

[0083] 创建保存kid30的Trie树节点后，将IP30所属业务的GID配置为gid30，计算Hash(kid30+gid30)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；

[0084] 另 外，该 Trie树 节 点 继 承 其 一 级 父 节 点 的 GID，即gid00，计 算Hash(kid30+gid00)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系；

[0085] 并 且，该 Trie树 节 点 继 承 其 二 级 父 节 点 的 GID，即gid10，计 算Hash(kid30+gid10)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系；

[0086] 并 且，该 Trie树 节 点 继 承 其 三 级 父 节 点 的 GID，即gid20，计 算Hash(kid30+gid20)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系。

[0087] 创建保存kid31的Trie树节点后，将IP31所属业务的GID配置为gid31，计算Hash(kid31+gid31)，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；

[0088] 另 外，该 Trie树 节 点 继 承 其 一 级 父 节 点 的 GID，即gid00，计 算Hash(kid31+gid00)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系；

[0089] 并 且，该 Trie树 节 点 继 承 其 二 级 父 节 点 的 GID，即gid10，计 算Hash(kid31+gid10)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系；

[0090] 并 且，该 Trie树 节 点 继 承 其 三 级 父 节 点 的 GID，即gid20，计 算Hash(kid31+gid20)，将计算得到的Hash值与该父节点相应位图的存储地址之间建立对应关系。

[0091] 上述实施例中，是以IP10、IP11、IP20、IP21、IP30和IP31对应的Trie树节点均为IP00对应Trie树节点的子节点为例进行说明的，容易想到的是，对于其他Trie树节点的子节点，也可以采用同样的方式创建Trie树节点并进行Hash计算，将计算得到的Hash值与位图的存储地址之间建立对应关系，将位图存入对应存储地址所指示的位置。

[0092] 本发明还提出一种保存位图的装置，如图5为本发明实施例保存位图的装置结构示意图。该装置包括：

[0093] 设置模块501，用于设置各级Trie树节点对应的关键码长度；

[0094] 分类模块502，用于将位图对应规则中IP地址的掩码长度与所述关键码长度进行比较，根据比较结果将IP地址放入各级Trie树节点对应的队列；

[0095] 保存模块503，用于按照关键码长度由小到大的顺序，依次提取所述Trie树节点对应的各个队列中的IP地址，为该IP地址配置对应的关键标识，创建相应的Trie树节点并保存该关键标识；为该IP地址所属的业务类型配置对应的组标识，对所述关键标识和组标识的组合进行Hash计算，将计算得到的Hash值与所述IP地址与业务类型的组合所对应位图的存储地址之间建立对应关系；当所述Trie树节点有父节点时，对所述关键标识和父节点对应的业务类型组标识的组合进行Hash计算，将计算得到的Hash值与所述父节点位图的存储地址之间建立对应关系。

[0096] 在上述设备中，当Trie树包括N级节点，并且N为大于2的自然数时，[0097] 分类模块502可以用于，当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

[0098] 当IP地址的掩码长度大于n级Trie树节点的关键码长度、并且不大于n+1级Trie树节点的关键码长度时，将该IP地址放入n+1级Trie树节点对应的队列；其中，所述n为大于0且小于N的自然数。

[0099] 在上述装置中，当Trie树包括四级节点时，

[0100] 分类模块502可以用于，当IP地址的掩码长度不大于一级Trie树节点的关键码长度时，将该IP地址放入一级Trie树节点对应的队列；

[0101] 当IP地址的掩码长度大于一级Trie树节点的关键码长度、并且不大于二级Trie树节点的关键码长度时，将该IP地址放入二级Trie树节点对应的队列；

[0102] 当IP地址的掩码长度大于二级Trie树节点的关键码长度、并且不大于三级Trie树节点的关键码长度时，将该IP地址放入三级Trie树节点对应的队列；

[0103] 当IP地址的掩码长度大于三级Trie树节点的关键码长度、并且不大于四级Trie树节点的关键码长度时，将该IP地址放入四级Trie树节点对应的队列。

[0104] 本发明还提出一种路由器，该路由器可以包括上述保存位图的装置。

[0105] 本发明还提出一种交换机，该交换机可以包括上述保存位图的装置。

[0106] 综上可见，本发明提出的保存位图的方法和装置适用于对IP地址与业务类型的组合所对应的位图进行保存，在创建Trie树之前，首先按照IP地址的掩码长度对IP地址进行分类，将分类后的IP地址分别放入各级Trie树节点对应的队列中；之后逐级创建Trie树节点，保存IP地址的关键标识，同时对IP地址关键标识和所属业务组标识的组合进行Hash计算，将计算得到的Hash值与相应位图的存储地址之间建立对应关系；并对IP地址关键标识父节点所属业务组标识的组合进行Hash计算，将计算得到的Hash值与相应父节点位图的存储地址之间建立对应关系。之后，就可以将相应位图存入存储地址所指示的位置。可见，本发明提出的方法和设备避免了保存位图过程中对Trie树的遍历，因而能够降低设备开销。

[0107] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明保护的范围之内。