Nothing Special   »   [go: up one dir, main page]

CN107431660B - 检索装置、检索方法及记录介质 - Google Patents

检索装置、检索方法及记录介质 Download PDF

Info

Publication number
CN107431660B
CN107431660B CN201680014265.4A CN201680014265A CN107431660B CN 107431660 B CN107431660 B CN 107431660B CN 201680014265 A CN201680014265 A CN 201680014265A CN 107431660 B CN107431660 B CN 107431660B
Authority
CN
China
Prior art keywords
leaf
node
bit
internal node
vector
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201680014265.4A
Other languages
English (en)
Other versions
CN107431660A (zh
Inventor
浅井大史
小原泰弘
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Communications Corp
Original Assignee
NTT Communications Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NTT Communications Corp filed Critical NTT Communications Corp
Publication of CN107431660A publication Critical patent/CN107431660A/zh
Application granted granted Critical
Publication of CN107431660B publication Critical patent/CN107431660B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/25—Routing or path finding in a switch fabric
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9027—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30036—Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30036—Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
    • G06F9/30038—Instructions to perform operations on packed data, e.g. vector, tile or matrix operations using a mask

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

一种检索装置，具有：存储单元，其存储检索对象数据；以及运算单元，其根据密钥数据进行对所述检索对象数据的检索处理，在所述存储单元中存储的所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量，所述运算单元反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据中取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点并访问转移目的地的节点。

Description

检索装置、检索方法及记录介质
技术领域
本发明涉及通过搜索用树结构表现的检索对象数据来取得期望的数据的检索技术。
背景技术
在路由器等装置中进行如下处理：根据所接收到的分组的目的地地址检索路径表而决定分组的转发目的地。在该处理中进行最长一致检索，为此以往使用Patricia前缀树(Trie)、基数树(Radix树)等。以往，二叉树的方式成为主流，性能即使高也就是数Mlps(Mega Lookup per second)。虽然也研究了多叉树(N-ary/Multiway)的方式，但是在实际应用中不是主流。这些树的性能未达到所期望的，因而实现数百 Mlps的TCAM这样的硬件成为事实上的标准。TCAM在经济性、集成度/规模性、功耗/发热方面存在难点。
为了打破TCAM的问题，近年来出现了将市售品的器件和软件组合起来进行路径检索的技术。PacketShader、GPU Click、GAMT等利用GPU实现较高的路径检索性能，但是由于利用GPU，因而与TCAM一样存在热问题等。另外，作为现有技术文献有专利文献1。
现有技术文献
专利文献
专利文献1：日本特开2000－083054号公报
发明内容
发明要解决的问题
如上所述，在利用TCAM或GPU等特定的器件时存在发热等问题，因而不期望利用特定的器件使路径检索高速化。
也提出了不以特定的硬件的利用为前提，而在通用的硬件(例如市售的CPU等) 中利用软件使路径检索高速化的技术(例如DXR、SAIL)，然而该技术在路径表内的路径数成为大规模时或地址长度变长时，存在性能下降的问题。
在使用通用的硬件的检索处理中，在检索对象数据的数据规模成为大规模、密钥数据长度变长的情况下，不仅路径检索，而且也产生检索性能下降的问题。
本发明正是鉴于上述情况而完成的，其目的在于，提供在使用通用的硬件的情况下，也能够高速地检索用树结构表现的检索对象数据的技术。
用于解决问题的手段
根据本发明的实施方式提供检索装置，具有：存储单元，其存储检索对象数据；以及运算单元，其根据密钥数据进行对所述检索对象数据的检索处理，其特征在于，
在所述存储单元中存储的所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，
所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量，
所述运算单元反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点并访问转移目的地的节点。
另外，根据本发明的实施方式提供由检索装置执行的检索方法，该检索装置具有：存储单元，其存储检索对象数据；运算单元，其根据密钥数据进行对所述检索对象数据的检索处理，其特征在于，
在所述存储单元中存储的所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，
所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量，
所述检索方法具有如下步骤：反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据中取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点并访问转移目的地的节点。
发明效果
根据本发明的实施方式，即使是在使用通用的硬件的情况下，也能够高速地检索用树结构表现的检索对象数据。
附图说明
图1是用于说明多路径基数搜索方法的图。
图2是本发明的实施方式的检索装置10的结构图。
图3是示出本发明的实施方式的检索装置20的图。
图4是示出存储部12中存储的检索对象数据的例子的图。
图5是用于说明本实施方式的检索对象数据的结构及检索处理的概要的图。
图6是示出内部节点和叶节点的更具体的例子的图。
图7是用于说明检索处理的步骤的流程图。
图8A是用于说明直接指向(direct pointing)的图。
图8B是用于说明直接指向的图。
图9是用于说明叶节点的数据的压缩例的图。
图10是用于说明压缩例中的数据结构的例子的图。
图11是用于说明叶节点的数据的压缩例的图。
图12是用于说明压缩例中的数据结构的例子的图。
图13是用于说明内部节点的数据的压缩例的图。
图14是示出应用leaf mask时的内部节点的数据结构的图。
图15是示出在使用leaf mask时取得叶的值的处理的流程图。
图16是用于说明有关leaf mask的数据生成方法的图。
具体实施方式
下面，参照附图说明本发明的实施方式。另外，下面说明的实施方式只不过是一个例子，本发明所应用的实施方式不限于以下的实施方式。
(关于搜索方法)
在本实施方式中，作为本发明的检索技术的应用对象的例子假定如下的处理：在路由器中，将所接收到的分组的目的地地址作为密钥，按照最长一致来检索路由表(更具体地讲是转发表(forwarding table))，取得作为该分组的转发目的地的下一跳(next hop)的信息。然而，本发明的应用对象不限于此，本发明不限于最长一致，可以应用于完全一致等各种类型的检索。下面，将作为检索(搜索)的对象的数据称为检索对象数据。另外，将目的地地址等成为检索的密钥的数据称为密钥数据。
在本实施方式中，使用利用多叉树表现的多路径基数搜索法作为对检索对象数据进行检索的方法，因而首先参照图1说明多路径基数搜索法的概要。
在多路径基数搜索法中，从开头起按照每规定数量的多个比特(以下称为块(chunk))划分密钥数据，按照该多个比特进行树的转移。图1是将每2比特作为块的例子。各块可以取4种类型的值(在图1中表示为a、b、c、d)，因而将树中的各节点分支成4个方向。分支点是内部节点(在图1中用圆圈示出的节点)或者叶节点 (在图1中用四方形示出的节点)。
在从密钥数据中的第一个块起第一段的节点中开始搜索，分支成相应的值的子节点，使密钥进入下一个块，由此依次进行搜索，在到达叶节点时搜索结束。
在图1的例子中，例如在密钥数据是d××××(×表示任意的值)的情况下，到达由5示出的叶节点。另外，在密钥数据是bb××的情况下，到达用由6示出的叶节点。在叶节点存储有例如表示下一跳的信息(例如地址、IF信息等)，在到达叶节点的情况下，取得与密钥数据对应的下一跳的信息。
上述的例子是将块长度设为2比特的例子，然而例如在使用64比特CPU结构的情况下，能够使用将块长度设为6比特、在各节点进行64分支的树的数据结构，以便将比特宽度设为相同宽度而有效地进行运算。
在如上所述的多路径基数搜索法中，通常各节点具有对应分支数量的、指向子节点用的指针(存储子节点的地址等)，然而各指针例如用64比特指定子节点，因而存在整体的树的数据量非常庞大的问题。因此，在这样使用指针的结构中，树的数据不能完全存储在通用CPU的高速闪存中，不得不存储在位于CPU之外的存储器中，因而存在检索速度下降的问题。
另一方面，在本实施方式的技术中，与上述的技术相比，能够大幅削减各内部节点的数据量，并且能够压缩具有相同数据的节点，因而能够减小整体的树的数据量，能够在通用CPU的高速闪存中存储树的数据而进行处理。因此，即使是使用通用CPU 等通用的硬件的情况下，也能够进行高速的检索处理。下面，更详细地说明本实施方式的技术。
(装置结构例)
首先，说明执行本实施方式的检索处理的检索装置的结构例。图2是示出本实施方式的检索装置10的结构例的图。
如图2所示，检索装置10具有运算部11、存储部12、输入部13、输出部14。运算部11是利用后述的方法对使用了密钥数据的检索对象数据执行检索处理的功能部。存储部12是存储检索对象数据的功能部。输入部13是输入密钥数据的功能部。输出部14是输出检索结果的功能部。
例如，检索装置10是通用计算机，由运算部11和存储部12构成CPU。在这种情况下，存储部12相当于CPU内的高速闪存。另外，存储部12的一部分也可以是 CPU以外的存储器。该CPU按照具有本实施方式的处理的逻辑的程序进行动作。该程序存储在存储部12中。另外，该程序也可以存储在存储部12以外的存储器等的存储部中。
通过将该程序存储在可移动存储器等记录介质中，并从该可移动存储器加载到通用计算机中，能够使用该计算机作为检索装置10。
另外，也可以将运算部11和存储部12构成为将本实施方式的处理的逻辑作为硬件电路装配而成的装置。
图3是示出本实施方式的检索装置另一例的检索装置20的图。检索装置20例如是作为路由器发挥作用的装置。如图3所示，检索装置20具有分组处理部21、目的地决定部22及多个接口(IF)。分组处理部21经由IF接收分组，从与通过目的地决定部22决定的目的地(下一跳)对应的IF输出分组。在图3中示出了从IF-A接收分组并从IF-B输出的例子。
目的地决定部22具有存储路由表(转发表)的存储部，从分组处理部21接收分组的目的地地址作为密钥数据，根据该密钥数据检索转发表，由此决定该分组的下一跳，将该下一跳的信息输出给分组处理部21。目的地决定部22例如能够使用图2所示的检索装置10。
下面，详细说明由检索装置10执行的检索处理。下面，将进行基础处理的方式作为实施例1进行说明，将对实施例1追加了能够进行节点的压缩的功能的方式的例子作为实施例2～4进行说明。
(实施例1)
图4是示出在检索装置10的存储部12中存储的检索对象数据的例子的图。图4 对于实施例1～4是相同的。如前面所述，在本实施方式中，进行以多路径基数搜索法为基础的检索处理，因而检索对象数据具有保存树中的各内部节点的数据的node array(节点排列)、和树中的各叶节点的数据即leaf array(叶排列)。通过指定各排列的Index，能够访问作为排列而存储的各节点的数据。
由leaf array和node array构成的检索对象数据存储在例如可移动存储器等记录介质中，并从该可移动存储器加载到检索装置10中，由此能够使用检索装置10作为针对检索对象数据的检索装置10。另外，也能够从某一计算机经由网络将检索对象数据加载到检索装置10中。
参照图5对实施例1的内部节点的数据结构进行说明。图5是在块的比特长度是 2、即从树的各节点向4个方向进行分支的例子，无论块的比特长度是几比特都是同样的结构。
如图5所示，内部节点具有vector、base0、base1。vector是由来自该内部节点的分支数量的比特构成的比特向量。在块的比特长度是2比特的情况下，可以取00、 01、10、11这4种值。vector的各比特从右端起顺序地对应于上述4种的各值。另外，“从右端起”是一个例子，也可以是“从左端起”。例如，在使用低位优先(little endian) 的CPU的情况下是从右端数起，在使用高位优先(big endian)的CPU的情况下是从左端数起。
在图5的例子中，例如vector的右端(第0个)比特对应于块00，第1个比特对应于块01，第2个比特对应于块10，第3个比特对应于块11。vector的各比特示出来自该内部节点的转移目的地(子节点)是内部节点还是叶节点。在本实施方式中， 1表示内部节点，0表示叶节点，但这是示例，也可以构成为1表示叶节点、0表示内部节点。
例如，在与图5所示的内部数据对应的块是00、01、10、11中的01的情况下，运算部11通过参照从vector的第0个数起的第1个比特(1)，能够掌握下一个节点是内部节点。另外，例如在块是00、01、10、11中的00的情况下，运算部11通过参照vector的第0个比特(0)，能够掌握下一个节点是叶节点。
如上所述，运算部11能够根据vector掌握转移目的地的节点是内部节点还是叶节点，但在这种状态下，为了取得内部节点/叶节点的数据，不知道访问node array/leafarray中的哪个Index的要素为好。因此，在本实施方式中，内部节点保存base0、base1。
base1保存node array中与该内部节点的vector的比特1对应的子的内部节点的存储开始Index。base0保存leaf array中与该内部节点的vector的比特0对应的子的叶节点的存储开始Index。
在本实施方式中，在node array中，对于各内部节点按照Index的顺序存储成为该内部节点的子的内部节点的数据。例如，对于某一内部节点，在子的内部节点有3 个的情况下，在node array中将该子的内部节点的3个数据存储为Index连续的3个数据。这3个数据中Index成为开头(最小)的数据的Index是base1。
另外，在leaf array中，对于各内部节点按照Index的顺序存储成为该内部节点的子的叶节点的数据。例如，对于某一内部节点，在子的叶节点有3个的情况下，在leaf array中将该子的叶节点的3个数据存储为Index连续的3个数据。这3个数据中Index 成为开头(最小)的数据的Index是base0。另外，在本实施方式中使用的Index是指示存储部位的指标，可以将其改称为“地址”。
按照以上所述在node array/leaf array中存储有数据，因而运算部11按照以下所述使用base0/base1访问子的内部节点/叶节点的数据。
关于对vector所在的比特位置(从第0个数起第v个)的子的内部节点的访问，运算部11计算(计数)从vector的第0个到第v个的比特位置的1的个数。即，从 vector的右端开始计算(v+1)比特中的1的个数。在设该个数为bc(bit count)时，运算部11通过在nodearray中访问将bc与base1相加后的值减1而得的值 (bc+base1-1)的Index，能够取得该内部节点的数据。
关于对vector所在的比特位置(从第0个数起第v个)的子的叶节点的访问，运算部11计算(计数)从vector的第0个到第v个的比特位置的0的个数。即，从vector 的右端开始计算(v+1)比特中的0的个数。在设该个数为bc(bit count)时，运算部11通过在leaf array中访问将bc与base0相加后的值减1而得的值(bc+base0-1) 的Index，能够取得该叶节点的数据。
图5示出了利用上述的方法访问子的内部节点(Index：2498)及叶节点(Index：3127～3129)。
通常CPU具备快速计算比特的个数的popcnt这种功能，在本实施方式中，能够有效运用该功能快速进行搜索。另外，使用popcnt是例子，也可以不使用popcnt。
图5示出了块长度是2比特即vector是4比特的例子，但这是例子，块长度/vector也可以是其它长度。图6示出块长度是6比特即vector是64(26)比特的例子。如已经说明的那样，在图6中示出内部节点具有vector、base0/base1，根据比特计数及 base0/base1，能够访问子的内部节点/叶节点。
在本实施方式中，内部节点可以具有比特向量和2个base，与在每个分支具有指针的方式相比，能够大幅削减各节点的数据量，其结果是，能够削减检索对象数据的数据量。
参照图7说明运算部11执行的检索处理的处理步骤。作为该处理的前提，向运算部11输入密钥数据，并且在存储部12存储具有上述构造的检索对象数据(node array/leafarray)。另外，图7示出了通过到达叶节点，检索处理结束的例子。
运算部11从node array中的第一个内部节点取得vector(步骤101)，从密钥数据取得第一个块(步骤102)。
运算部11读取与块相对应的vector的位置的比特，判定该比特是否是1(步骤103)。在该比特是1的情况下，如前面所述计算比特计数bc，访问在(bc+base1-1) 的Index中存储的内部节点，取得该内部节点的vector(步骤104)。
运算部11从密钥数据取得下一个块(步骤105)，再次执行步骤103的判定。
在步骤103的判定的结果是与块相对应的vector的位置的比特是0的情况下(步骤103：否)，进入步骤106。在步骤106，运算部11按照前面所述计算比特计数bc，访问在(bc+base0-1)的Index中存储的叶节点，取得该叶节点的值。
另外，例如在转发表中存在成为叶的前缀长度集中于特定的范围(例如：/11～/24) 的倾向，因而能够省略最初的节点的搜索，直接到达目标入口(entry)。将此称为直接指向(direct pointing)。参照图8A、B说明例子。
图8A是不进行直接指向的例子，在该例子中，在各6比特的块中进行搜索。图 8B示出了最先在12比特的块中进行搜索的直接指向的例子。在图8B的情况下，当在该块中不能到达叶节点的情况下，以后与实施例1的上述的方法一样，例如在各6 比特的块中进行搜索。直接指向也能够适用于其它实施例。
(实施例2)
下面，作为实施例2，说明对于实施例1所说明的方式能够压缩叶数据的方式。例如，在将实施例1的方式应用于转发表的检索时，考虑到将会多发具有重复的值(下一跳)的叶节点。实施例2是以实施例1的方式为基础，压缩叶节点并进行保存。下面，主要说明与实施例1不同的部分。
图9是实施例2的内部节点的图。如图9所示，在实施例2中，除在实施例1 中说明的vector、base0、base1以外，还追加了leafvec。leafvec是与vector的比特长度相同的比特长度。
另外，关于leaf array中成为各内部节点的子的叶节点(即，各段的叶节点)，具有相同值的连续的叶节点仅保存开始连续的第一个叶节点。在图9的例子中，关于 Index是3127、3128、3129的叶节点，值全部相同是7，在这种情况下，Index仅保存3127的叶节点。这样压缩的结果是，在具有多个叶节点的情况下，也不包括具有相同值的多个叶节点，而成为彼此不同的值。
leafvec的要素是0或1的比特，从右端起，对与压缩前的叶节点开始连续的位置对应的比特设定1。例如，在图9的例子中是从第一个叶节点开始连续的，因而对与该第一个叶节点对应的第一个(第0个)比特设定1。另外，在连续结束、另一个值的叶节点开始的情况下(叶节点变化的情况下)，在该位置设定1。叶节点变化的情况包括第一个叶节点。此处的“连续”包括1个的情况。即，在叶节点的数据全部不同的情况下，在与叶节点对应的leafvec的比特位置全部设定1。leafvec的使用方法如下所述。
运算部11在检测出与块对应的vector的比特(从第0个数起第v个比特)是0 时，可知子是叶节点。运算部11计算leafvec中从右端的第0个数起到第v个的比特 (v+1个比特)中的1的比特的个数。在设该个数为bc时，与vector的情况相同，运算部11访问(bc+base0-1)的Index的叶节点。
图10示出实施例2中的内部节点和叶节点的数据例。在图10的例子中示出，运算部11根据块检测从(a)所示的内部节点中的vector的第0个数起的第1个比特是 1，访问与其对应的(c)的内部节点。另外，例如在(a)的内部节点中，在块对应于从第0个数起的第2个(0)的情况下，运算部11计算截止到leafvec中第2个的3 比特中的1的个数，使用base0访问与该个数对应的叶节点(L(0))。
叶节点的压缩也可以利用如上所述使用leafvec以外的方法实现。下面，将有关叶节点的压缩的另一种方法作为实施例3进行说明。但是，实施例3的方法实质上与使用leafvec的方法相同。
(实施例3)
图11是示出实施例3中的内部节点的图。如图11所示，在实施例3中，除在实施例1中说明的vector、base0、base1以外，还追加了mask。mask是与vector的比特长度相同的比特长度。
另外，关于leaf array中成为各内部节点的子的叶节点(即，各段的叶节点)，具有相同值的连续的叶节点仅保存开始连续的第一个叶节点。在图11的例子中，关于 Index是3127、3128、3129的叶节点，值全部相同是7，在这种情况下，Index仅保存3127的叶节点。这样压缩的结果是，在具有多个叶节点的情况下，也不包括具有相同值的连续的多个叶节点。
mask的要素是0或1的比特，从右端起，对与压缩前的叶节点开始连续的位置对应的比特设定0，在从该开始位置起相同值连续的叶节点的位置设定1(掩码)。另外，在连续结束、另一个值的叶节点开始的情况下(叶节点变化的情况下)，在该位置设定0。叶节点变化的情况包括第一个叶节点。
另外，与内部节点相对应的位置既可以设定1，也可以设定0，在该例子中是设为0。在图11的例子中，3个叶节点连续，因而在与第一个叶节点相对应的比特位置设定0，在与以后的叶节点相对应的比特位置设定掩码即1。mask的使用方法如下所述。
运算部11在检测出与块对应的vector的比特(从第0个数起第v个比特)是0 时，可知子是叶节点。在实施例3中，运算部11进行vector与mask的OR运算，计算从进行OR运算后的vector中右端的第0个数起到第v个的比特(v+1个比特)中的0的比特的个数。在设该个数为bc时，运算部11访问(bc+base0-1)的Index的叶节点。
图12示出实施例3中的内部节点和叶节点的数据例。在图12的例子中示出，运算部11根据块检测从(a)所示的内部节点中的vector的第0个数起的第1个比特是 1，访问与其对应的(c)的内部节点。另外，例如在(a)的内部节点中，在块对应于从第0个数起的第2个(0)的情况下，运算部11计算截止到mask后面的vector 中第2个的3比特中的0的个数，使用base0访问对应该个数的叶节点(L(0))。
mask也能够适用于内部节点的压缩。参照图13说明将mask适用于内部节点的压缩的例子。图13与图6一样示出了块长度是6比特、即vector是64(26)比特时的例子。在该例子中，除在实施例1中说明的vector、base0、base1以外，还追加了 mask。mask是与vector的比特长度相同的比特长度。
另外，关于各段的内部节点，具有相同值的连续的内部节点仅保存开始连续的第一个内部节点。在图13的例子中，如(a)所示，具有相同的子树的内部节点有3个。在这种情况下，如(b)所示，仅保存3个中的第一个内部节点。这样压缩的结果是，在具有多个内部节点的情况下，也不包括具有相同值的连续的多个内部节点。
mask的要素是0或1的比特，从右端起，对与压缩前的内部节点开始连续的位置对应的比特设定1，在从该开始位置起相同值连续的内部节点的位置设定0(掩码)。另外，在连续结束、其它的值的内部节点开始的情况下(内部节点变化的情况下)，在该位置设定1。
在图13的例子中，3个内部节点连续，因而在与第一个内部节点相对应的比特位置设定1，在与以后的内部节点相对应的比特位置设定掩码即0。即，如图13(b) 所示，与vector的第一个的1对应的mask的比特是1，与下一个的1以及再下一个的1对应的mask的比特是0。mask的使用方法如下所述。
运算部11在检测出与块对应的vector的比特(从第0个数起第v个比特)是1 时，可知子是内部节点。运算部11进行vector与mask的AND运算，计算从进行 AND运算后的vector中右端的第0个数起到第v个的比特(v+1个比特)中的1的比特的个数。在设该个数为bc时，运算部11访问(bc+base1-1)的Index的内部节点。
(实施例4)
下面说明实施例4。实施例4是比实施例2、3进一步压缩叶节点的方式。图14 示出实施例4的内部数据的构造。如图14所示，实施例4的内部数据除已经说明的 vector、leafvec、base0、base1以外，如“A”所示还追加了leaf mask和masked leaf。在存储部12中存储有node array和leaf array。
leaf mask是由与vector相同比特长度的0/1的比特构成的数据。masked leaf是某一叶节点的数据。下面，说明在使用leaf mask和masked leaf时的运算部11的动作。
参照图15的流程图，说明实施例4的检索装置10的运算部11的动作例。图15 是用于特别说明与实施例1、2不同的处理的部分的图。
在步骤201，运算部11检测当前的块的vector中的相应比特(从第0个数起第v 个比特)是0，由此检测出转移到叶节点。
在步骤202，运算部11判定在leaf mask中从第0个数起第v个比特是否是1。在其是1的情况下(步骤202：是)，取得masked leaf的值作为叶数据的值(步骤203)。
在步骤202，在第v个比特不是1的情况下(步骤202：否)，运算部11与实施例2一样计算leafvec的从第0个到第v个的1的个数(bc)，访问(bc+base0-1)的 Index的叶节点并取得值(步骤204)。
下面，参照图16说明实施例4的有关leaf mask的数据的生成方法。以下说明的数据的生成既可以由检索装置10进行，也可以由其它装置(计算机)进行。下面将进行数据的生成的装置称为生成装置。生成装置是检索装置10或者其它装置。在生成装置是其它装置的情况下，在数据生成后，将生成数据存储在检索装置10的存储部12中。
首先，生成装置计算没有压缩的leaf array。由此，例如如果是四叉树，对于父的每个内部节点，生成例如在图5的L所示的Index连续的叶节点的数据。
另外，如果是六十四叉树，按照父的每个内部节点，leaf array的项目数最大达到64。另外，例如在十六叉树的例子中，在设叶信息是A、B、C这三种时，叶信息如图16的(a)所示，例如以ABAA BBBA BCBB CCCC的方式在leaf array内排列。
然后，生成装置选择被掩蔽的叶信息。在该例中，将B掩蔽并省略。通常，将连续的断片出现的次数最多的进行掩蔽比较有效，因而生成装置决定将连续的断片出现的次数最多的B进行掩蔽。另外，“连续的断片”包括如ABA中的B那样是1个的情况。将被掩蔽的叶的信息B存储在masked leaf中。
然后，生成装置将被掩蔽的叶信息出现的时隙保存在leaf mask中。被掩蔽的叶信息出现的时隙相当于与vector中的该叶对应的比特位置。例如，在vector是0010 的情况下，在将与设左端为第1个开始数起第2个的比特0对应的叶掩蔽的情况下，在leaf mask中保存0100。
另外，生成装置将在leaf array中被掩蔽的叶信息的时隙设为与紧前面的值相同的值。由此，根据图16的(a)所示的叶信息，如图16的(b)所示得到“leaf mask：010011101011 0000”，并得到“leaf array：AAAA AAAA ACCC CCCC”。另外，该例是高位优先(bigendian)，因而从左端数起。在图16的(b)中，下划线部分是被掩蔽的部分，成为与计数方向上的紧前面的值(左侧的值)相同的值。
然后，与没有叶掩蔽的情况相同，将连续的部分压缩。由此，如图16的(c)所示成为“leafvec：1000 0000 0100 0000”，成为“leaf array：AC”。
上述处理的结果是，如图16的(d)所示，能够得到“leaf mask：0100 1110 10110000”、“masked leaf：B”、“leaf vector：1000 0000 0100 0000”、“leaf array：AC”。
另外，作为参考，没有叶掩蔽而进行压缩时的leaf array成为“ABABABCBC”，可知根据实施例4得到较高的压缩效果。
在实施例4中，追加了1个掩码(例如64bit)和1个叶，但能够省略不连续的几个叶，实现leaf array的进一步压缩。这对于下面的情况特别有效：leaf array被某个下一跳值多次断开(成为条纹状态)的情况、或1个叶的尺寸(leaf array的1入口的尺寸)较大为16字节等情况。
另外，实施例2、3、4示出了将叶节点压缩的例子，但对于具有相同数据的内部节点，也能够进行与叶节点的情况一样的压缩。并且，也可以进行叶节点的压缩和内部节点的压缩双方。
(实施方式的效果)
如以上说明的那样，在本实施方式中能够大幅削减树的数据量，因而能够在例如通用CPU的高速闪存(例如L1、L2、L3高速闪存)中存储检索对象数据而实施检索处理，实现快速的检索处理。特别是在例如检索对象数据是路径表的情况下，能够解决在路径表内的路径数成为大规模时性能下降的问题。另外，由于处理高速化，因而也能够解决在地址长度变长时性能下降的问题。
另外，在树的各等级中，用比特单位表现部分树的有无，因而存储器效率良好。特别是在例如使用六十四叉树的情况下，表现每64比特部分树(子排列)的有无，因而具有在64-bit CPU中的处理效率良好的特点。
另外，在vector等中，对是1的比特进行计数，对排列中相应的子跳过1步骤，因而能够实现快速处理，存储器效率也良好。并且，由于计数是1的比特，因而能够使用popcntCPU Instruction，实现快速处理。另外，由于以通用的多叉树(Multiway trie)为基础，因而扩展性/灵活性提高，不限于路径表检索，能够适用于各种检索。
另外，通过进行在实施例2～4中说明的叶信息的压缩，能够减小检索对象数据的量，实现更进一步的快速化。
作为一例，通过使用本实施方式的技术，能够利用具有popcnt CPU Instruction的通用CPU，对保存50万的IPv4全根(full root)路径的路径表，实现单核约为 240Mlps、4核约为910Mlps。不利用TCAM，在通用CPU中即可发挥与TCAM相同乃至数倍的性能。
(实施方式的汇总)
如以上说明的那样，根据本实施方式提供检索装置，具有：存储单元，其存储检索对象数据；以及运算单元，其根据密钥数据进行对所述检索对象数据的检索处理，其特征在于，在所述存储单元中存储的所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量，所述运算单元反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点并访问转移目的地的节点。
也可以构成为，所述检索对象数据中的各内部节点包括表示转移目的地的1个内部节点的存储位置的第1基础信息、和表示转移目的地的1个叶节点的存储位置的第 2基础信息，所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是内部节点的情况下，使用所述第1基础信息访问该转移目的地的内部节点，在转移目的地是叶节点的情况下，使用所述第2基础信息访问该转移目的地的叶节点。
也可以是，对于所述检索对象数据中的各内部节点，成为转移目的地的内部节点在所述内部节点排列中按照存储位置连续的方式进行存储，成为转移目的地的叶节点在所述叶节点排列中按照存储位置连续的方式进行存储，所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是内部节点的情况下，使用所述第1基础信息和所述比特向量中表示内部节点的比特的数量来访问该转移目的地的内部节点，在转移目的地是叶节点的情况下，使用所述第2基础信息和所述比特向量中表示叶节点的比特的数量来访问该转移目的地的叶节点。
也可以是，对于所述检索对象数据中的各内部节点，成为转移目的地的叶节点在所述叶节点排列中按照存储位置连续的方式进行存储，具有相同值的叶节点被压缩，多个叶节点不包括具有相同值的多个叶节点，所述检索对象数据中的各内部节点包括具有表示压缩前的叶节点的值变化的存储位置的比特的叶向量，所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是叶节点的情况下，使用所述第2基础信息和所述叶向量中表示所述存储位置的比特的数量来访问该转移目的地的叶节点。
也可以是，所述运算单元先调查所述比特向量和所述叶向量中的所述比特向量，根据该比特向量的比特的值使用所述叶向量。
也可以是，对于所述检索对象数据中的各内部节点，成为转移目的地的叶节点在所述叶节点排列中按照存储位置连续的方式进行存储，具有相同值的叶节点被压缩，多个叶节点不包括具有相同值的多个叶节点，所述检索对象数据中的各内部节点包括具有表示压缩前的叶节点的值变化的存储位置的比特的掩码向量，所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是叶节点的情况下，使用所述第2 基础信息和用所述掩码向量掩蔽后的所述比特向量中的表示叶节点的比特的数量访问该转移目的地的叶节点。
也可以是，对于所述检索对象数据中的各内部节点，成为转移目的地的内部节点在所述内部节点排列中按照存储位置连续的方式进行存储，具有相同值的内部节点被压缩，多个内部节点不包括具有相同值的多个内部节点，所述检索对象数据中的各内部节点包括具有表示压缩前的内部节点的值变化的存储位置的比特的掩码向量，所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是内部节点的情况下，使用所述第1基础信息和用所述掩码向量掩蔽后的所述比特向量中的表示内部节点的比特的数量访问该转移目的地的内部节点。
也可以是，对于所述检索对象数据中的各内部节点，成为转移目的地的叶节点中的规定值被掩蔽，该被掩蔽的值被变更为另一个值，然后将具有相同值的叶节点压缩，由此多个叶节点不包括具有相同值的多个叶节点，并在所述叶节点排列中使存储位置连续进行存储，所述检索对象数据中的各内部节点包括所述被掩蔽的规定值、具有表示具有该规定值的叶向量的压缩前的位置的比特的叶掩码、以及由表示压缩前的叶节点的值变化的存储位置的比特构成的叶向量，所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是叶节点的情况下，判定是否在所述比特向量中与该比特的位置相同的位置对所述叶掩码设定了比特，在设定了比特的情况下，取得所述规定值作为该转移目的地的叶节点的值，在未设定比特的情况下，使用所述第2基础信息和所述叶向量中表示所述存储位置的比特的数量来访问该转移目的地的叶节点。
也可以是，所述运算单元使用由该运算单元构成的CPU的popcnt命令计算所述比特的个数。
另外，也可以是，所述运算单元和所述存储单元是在64比特CPU中构成的。并且，也可以是，所述块是6比特长度，所述比特向量是64比特长度。
另外，也可以是，所述运算单元和所述存储单元是在64比特CPU中构成的，所述块是6比特长度，所述比特向量是64比特长度，所述运算单元使用所述64比特 CPU的popcnt命令计算所述比特的个数，使用来自基础信息的基于该比特的数量的偏置进行对所述转移目的地的节点的访问。
另外，也可以是，所述运算单元从所述密钥数据中取得比所述规定比特长度长的比特长度的块，使用该块进行搜索，由此直接到达叶节点。
另外，根据本实施方式也能够提供使计算机作为所述检索装置中的各单元发挥作用的程序。并且，根据本实施方式也能够提供存储了所述检索对象数据的计算机可读的记录介质。
另外，上述的“存储单元”也可以置换为存储部、存储电路、存储器件中任意一方。并且，上述的“运算单元”也可以置换为运算部、运算电路、运算器件中任意一方。
另外，本实施方式的检索方法也可以构成为根据密钥数据进行对检索对象数据的检索处理的检索方法，所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量，所述检索方法具有如下步骤：反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点并访问转移目的地的节点。
本发明不限于上述的实施方式，能够在权利要求书的范围内进行各种变更及应用。
本专利申请以在2015年3月11日提出的日本专利申请第2015－048657号为基础并对其主张优先权，并且将第2015－048657号日本专利申请的全部内容引用于此。
标号说明
10、20检索装置；11运算部；12存储部；13输入部；14输出部；21分组处理部；22目的地决定部。

Claims (14)

1.一种检索装置，具有：存储单元，其存储检索对象数据；以及运算单元，其根据密钥数据进行对所述检索对象数据的检索处理，其特征在于，
在所述存储单元中存储的所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，
所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量、表示转移目的地的1个内部节点的存储位置的第1基础信息以及表示转移目的地的1个叶节点的存储位置的第2基础信息，
所述运算单元反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据中取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点，在判定出的转移目的地是内部节点的情况下，使用所述第1基础信息访问该转移目的地的内部节点，在判定出的转移目的地是叶节点的情况下，使用所述第2基础信息访问该转移目的地的叶节点。
2.根据权利要求1所述的检索装置，其特征在于，
对于所述检索对象数据中的各内部节点，成为转移目的地的内部节点在所述内部节点排列中按照存储位置连续的方式进行存储，成为转移目的地的叶节点在所述叶节点排列中按照存储位置连续的方式进行存储，
所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是内部节点的情况下，使用所述第1基础信息和所述比特向量中表示内部节点的比特的数量访问该转移目的地的内部节点，
所述运算单元在转移目的地是叶节点的情况下，使用所述第2基础信息和所述比特向量中表示叶节点的比特的数量访问该转移目的地的叶节点。
3.根据权利要求1所述的检索装置，其特征在于，
对于所述检索对象数据中的各内部节点，成为转移目的地的叶节点在所述叶节点排列中按照存储位置连续的方式进行存储，具有相同值的叶节点被压缩，多个叶节点不包括具有相同值的多个叶节点，
所述检索对象数据中的各内部节点包括具有表示压缩前的叶节点的值变化的存储位置的比特的叶向量，
所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是叶节点的情况下，使用所述第2基础信息和所述叶向量中表示所述存储位置的比特的数量访问该转移目的地的叶节点。
4.根据权利要求3所述的检索装置，其特征在于，
所述运算单元先调查所述比特向量和所述叶向量中的所述比特向量，根据该比特向量的比特的值使用所述叶向量。
5.根据权利要求1所述的检索装置，其特征在于，
对于所述检索对象数据中的各内部节点，成为转移目的地的叶节点在所述叶节点排列中按照存储位置连续的方式进行存储，具有相同值的叶节点被压缩，多个叶节点不包括具有相同值的多个叶节点，
所述检索对象数据中的各内部节点包括具有表示压缩前的叶节点的值变化的存储位置的比特的掩码向量，
所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是叶节点的情况下，使用所述第2基础信息和用所述掩码向量掩蔽后的所述比特向量中的表示叶节点的比特的数量来访问该转移目的地的叶节点。
6.根据权利要求1所述的检索装置，其特征在于，
对于所述检索对象数据中的各内部节点，成为转移目的地的内部节点在所述内部节点排列中按照存储位置连续的方式进行存储，具有相同值的内部节点被压缩，多个内部节点不包括具有相同值的多个内部节点，
所述检索对象数据中的各内部节点包括具有表示压缩前的内部节点的值变化的存储位置的比特的掩码向量，
所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是内部节点的情况下，使用所述第1基础信息和用所述掩码向量掩蔽后的所述比特向量中的表示内部节点的比特的数量来访问该转移目的地的内部节点。
7.根据权利要求1所述的检索装置，其特征在于，
对于所述检索对象数据中的各内部节点，成为转移目的地的叶节点中的规定值被掩蔽，该被掩蔽的值被变更为另一个值，然后将具有相同值的叶节点压缩，由此多个叶节点不包括具有相同值的多个叶节点，并在所述叶节点排列中使存储位置连续进行存储，
所述检索对象数据中的各内部节点包括所述被掩蔽的规定值、具有表示具有该规定值的叶向量的压缩前的位置的比特的叶掩码、以及由表示压缩前的叶节点的值变化的存储位置的比特构成的叶向量，
所述运算单元在根据所述比特向量的比特的值判定出的转移目的地是叶节点的情况下，判定是否在所述比特向量中与该比特的位置相同的位置对所述叶掩码设定了比特，在设定了比特的情况下，取得所述规定值作为该转移目的地的叶节点的值，在未设定比特的情况下，使用所述第2基础信息和所述叶向量中表示所述存储位置的比特的数量访问该转移目的地的叶节点。
8.根据权利要求2至7中任一项所述的检索装置，其特征在于，
所述运算单元使用由该运算单元构成的CPU的popcnt命令计算所述比特的数量。
9.根据权利要求1～7中任意一项所述的检索装置，其特征在于，
所述运算单元和所述存储单元是在64比特CPU中构成的。
10.根据权利要求1～7中任意一项所述的检索装置，其特征在于，
所述块是6比特长度，所述比特向量是64比特长度。
11.根据权利要求2至7中任一项所述的检索装置，其特征在于，
所述运算单元和所述存储单元是在64比特CPU中构成的，所述块是6比特长度，所述比特向量是64比特长度，
所述运算单元使用所述64比特CPU的popcnt命令计算所述比特的数量，使用来自基础信息的基于该比特的数量的偏置进行对所述转移目的地的节点的访问。
12.根据权利要求1～7中任意一项所述的检索装置，其特征在于，
所述运算单元从所述密钥数据中取得比所述规定比特长度长的比特长度的块，使用该块进行搜索，由此直接到达叶节点。
13.一种存储有程序的计算机可读取的存储介质，该程序使计算机作为权利要求1～7中任意一项所述的所述检索装置中的各单元发挥作用。
14.一种由检索装置执行的检索方法，所述检索装置，具有：存储单元，其存储检索对象数据；以及运算单元，其根据密钥数据进行对所述检索对象数据的检索处理，其特征在于，
所述存储单元中存储的所述检索对象数据是具有内部节点排列和叶节点排列的多叉树结构的数据，
所述检索对象数据中的各内部节点包括用比特表示转移目的地是内部节点还是叶节点的比特向量、表示转移目的地的1个内部节点的存储位置的第1基础信息以及表示转移目的地的1个叶节点的存储位置的第2基础信息，
所述检索方法具有如下步骤：
反复执行如下处理，一直到转移目的地成为叶节点为止，所述处理是：从密钥数据中取得规定比特长度的块，根据所访问的内部节点的所述比特向量中与该块的值对应的比特，判定从该内部节点起的转移目的地是内部节点还是叶节点，在判定出的转移目的地是内部节点的情况下，使用所述第1基础信息访问该转移目的地的内部节点，在判定出的转移目的地是叶节点的情况下，使用所述第2基础信息访问该转移目的地的叶节点。
CN201680014265.4A 2015-03-11 2016-01-29 检索装置、检索方法及记录介质 Active CN107431660B (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
JP2015048657A JP5960863B1 (ja) 2015-03-11 2015-03-11 検索装置、検索方法、プログラム、及び記録媒体
JP2015-048657 2015-03-11
PCT/JP2016/052664 WO2016143405A1 (ja) 2015-03-11 2016-01-29 検索装置、検索方法、プログラム、及び記録媒体

Publications (2)

Publication Number Publication Date
CN107431660A CN107431660A (zh) 2017-12-01
CN107431660B true CN107431660B (zh) 2020-08-18

Family

ID=56550536

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201680014265.4A Active CN107431660B (zh) 2015-03-11 2016-01-29 检索装置、检索方法及记录介质

Country Status (7)

Country Link
US (1) US11762826B2 (zh)
EP (1) EP3270551B1 (zh)
JP (1) JP5960863B1 (zh)
CN (1) CN107431660B (zh)
AU (1) AU2016230539B2 (zh)
ES (1) ES2830746T3 (zh)
WO (1) WO2016143405A1 (zh)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111373389B (zh) * 2017-11-20 2023-11-17 华为技术有限公司 数据存储系统以及用于提供数据存储系统的方法
CN108008728B (zh) * 2017-12-12 2020-01-17 深圳市银星智能科技股份有限公司 清洁机器人以及基于清洁机器人的最短路径规划方法
JP2020004132A (ja) * 2018-06-28 2020-01-09 エヌ・ティ・ティ・コミュニケーションズ株式会社 検索装置、検索方法、プログラム、及び記録媒体
JP7088868B2 (ja) * 2019-03-22 2022-06-21 エヌ・ティ・ティ・コミュニケーションズ株式会社 通信装置、通信方法及びプログラム
US11288244B2 (en) * 2019-06-10 2022-03-29 Akamai Technologies, Inc. Tree deduplication
US11652791B2 (en) * 2019-08-07 2023-05-16 Cisco Technology, Inc. Consolidated routing table for extranet virtual networks
US11899985B1 (en) 2021-03-31 2024-02-13 DreamBig Semiconductor Inc. Virtual modules in TCAM
CN115328366B (zh) * 2022-08-11 2023-09-19 北京智慧星光信息技术有限公司 基于全路径计算的千万级树形节点搜索展示方法和系统

Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6522632B1 (en) * 1998-05-06 2003-02-18 Avici Systems Apparatus and method for efficient prefix search
WO2004040400A2 (en) * 2002-09-16 2004-05-13 North Carolina State University Methods and systems for fast binary network address lookups using parent node information stored in routing tables entries
US7523218B1 (en) * 2002-04-30 2009-04-21 University Of Florida Research Foundation, Inc. O(log n) dynamic router tables for prefixes and ranges
US7539153B1 (en) * 2008-05-05 2009-05-26 Huawei Technologies Co., Ltd. Method and apparatus for longest prefix matching based on a trie
CN101484895A (zh) * 2006-07-07 2009-07-15 新叶股份有限公司 比特序列检索装置、检索方法以及程序
US7831626B1 (en) * 2006-11-27 2010-11-09 Netlogic Microsystems, Inc. Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node
CN101911068A (zh) * 2008-01-17 2010-12-08 新叶股份有限公司 比特序列检索装置、检索方法以及程序
CN102739551A (zh) * 2012-07-17 2012-10-17 中山大学 多存储器流水路由体系结构
CN102741841A (zh) * 2009-11-30 2012-10-17 新叶股份有限公司 比特序列检索装置、检索方法以及程序
CN104052669A (zh) * 2013-03-12 2014-09-17 西普联特公司 用于处理交替配置的最长前缀匹配表的装置和方法

Family Cites Families (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
IL100987A (en) * 1991-02-27 1995-10-31 Digital Equipment Corp Method and device for encoding
US5664172A (en) * 1994-07-19 1997-09-02 Oracle Corporation Range-based query optimizer
US6266706B1 (en) 1997-09-15 2001-07-24 Effnet Group Ab Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams
SK3692000A3 (en) * 1997-09-15 2000-09-12 Effnet Group Ab Method and system for fast routing lookups
JP3547625B2 (ja) 1998-09-03 2004-07-28 三菱電機株式会社 データ検索装置およびデータ検索方法
US6829695B1 (en) * 1999-09-03 2004-12-07 Nexql, L.L.C. Enhanced boolean processor with parallel input
US6675163B1 (en) * 2000-04-06 2004-01-06 International Business Machines Corporation Full match (FM) search algorithm implementation for a network processor
US20030208488A1 (en) * 2000-09-20 2003-11-06 North Dakota State University System and method for organizing, compressing and structuring data for data mining readiness
US6931418B1 (en) * 2001-03-26 2005-08-16 Steven M. Barnes Method and system for partial-order analysis of multi-dimensional data
US6985483B2 (en) * 2001-07-31 2006-01-10 North Carolina State University Methods and systems for fast packet forwarding
US7444318B2 (en) * 2002-07-03 2008-10-28 University Of Florida Research Foundation, Inc. Prefix partitioning methods for dynamic router tables
US8886677B1 (en) * 2004-07-23 2014-11-11 Netlogic Microsystems, Inc. Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix length
JP4973101B2 (ja) * 2006-09-29 2012-07-11 日本電気株式会社 自動合成装置
US8086641B1 (en) * 2006-11-27 2011-12-27 Netlogic Microsystems, Inc. Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating same
WO2008132016A1 (en) * 2007-05-01 2008-11-06 International Business Machines Corporation Method and system for approximate string matching
US9438413B2 (en) * 2010-01-08 2016-09-06 Novell, Inc. Generating and merging keys for grouping and differentiating volumes of files
US8522348B2 (en) * 2009-07-29 2013-08-27 Northwestern University Matching with a large vulnerability signature ruleset for high performance network defense
US8669977B2 (en) * 2009-10-01 2014-03-11 Intel Corporation Hierarchical mesh quantization that facilitates efficient ray tracing
US20140188885A1 (en) * 2012-12-27 2014-07-03 Broadcom Corporation Utilization and Power Efficient Hashing
EP2976740A4 (en) * 2013-03-15 2017-01-11 Factual Inc. Apparatus, systems, and methods for analyzing characteristics of entities of interest
US9842132B2 (en) * 2015-10-23 2017-12-12 International Business Machines Corporation Bloom filter index for device discovery

Patent Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6522632B1 (en) * 1998-05-06 2003-02-18 Avici Systems Apparatus and method for efficient prefix search
US7523218B1 (en) * 2002-04-30 2009-04-21 University Of Florida Research Foundation, Inc. O(log n) dynamic router tables for prefixes and ranges
WO2004040400A2 (en) * 2002-09-16 2004-05-13 North Carolina State University Methods and systems for fast binary network address lookups using parent node information stored in routing tables entries
CN101484895A (zh) * 2006-07-07 2009-07-15 新叶股份有限公司 比特序列检索装置、检索方法以及程序
US7831626B1 (en) * 2006-11-27 2010-11-09 Netlogic Microsystems, Inc. Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node
CN101911068A (zh) * 2008-01-17 2010-12-08 新叶股份有限公司 比特序列检索装置、检索方法以及程序
US7539153B1 (en) * 2008-05-05 2009-05-26 Huawei Technologies Co., Ltd. Method and apparatus for longest prefix matching based on a trie
CN102741841A (zh) * 2009-11-30 2012-10-17 新叶股份有限公司 比特序列检索装置、检索方法以及程序
CN102739551A (zh) * 2012-07-17 2012-10-17 中山大学 多存储器流水路由体系结构
CN104052669A (zh) * 2013-03-12 2014-09-17 西普联特公司 用于处理交替配置的最长前缀匹配表的装置和方法

Also Published As

Publication number Publication date
WO2016143405A1 (ja) 2016-09-15
AU2016230539A1 (en) 2017-10-05
EP3270551B1 (en) 2020-10-14
EP3270551A1 (en) 2018-01-17
AU2016230539B2 (en) 2018-08-16
JP2016170526A (ja) 2016-09-23
JP5960863B1 (ja) 2016-08-02
US20180039662A1 (en) 2018-02-08
US11762826B2 (en) 2023-09-19
CN107431660A (zh) 2017-12-01
EP3270551A4 (en) 2018-07-18
ES2830746T3 (es) 2021-06-04

Similar Documents

Publication Publication Date Title
CN107431660B (zh) 检索装置、检索方法及记录介质
KR100962653B1 (ko) 블룸 필터 및 복수 해싱 구조를 사용한 ｉｐ 주소 검색방법 및 장치
KR101028470B1 (ko) Ｉｐ주소 검색을 위한 장치 및 방법
US6985483B2 (en) Methods and systems for fast packet forwarding
CN104468357B (zh) 流表的多级化方法、多级流表处理方法及装置
CN111937360B (zh) 最长前缀匹配
US6691171B1 (en) Method and system for address lookup in data communication
JP3881663B2 (ja) フィールドレベルツリーを用いたパケット分類装置及び方法
US20050083937A1 (en) IP address lookup method using pipeline binary tree, hardware architecture, and recording medium
JP2009219012A (ja) 固定長データの検索方法
US11115333B2 (en) Single stage look up table based match action processor for data packets
US20070091899A1 (en) Data structure for storing and accessing multiple independent sets of forwarding information
US6925503B2 (en) Method and system for performing a longest prefix match search
US20220109626A1 (en) Forwarding Rules Among Lookup Tables in a Multi-Stage Packet Processor
Lim et al. Binary searches on multiple small trees for IP address lookup
CN113824814B (zh) 一种转发表的地址匹配方法、装置、网络设备及介质
Bahrambeigy et al. Bloom-Bird: A scalable open source router based on Bloom filter
CN107204926B (zh) 预处理cache的路由快速查找方法
JP6205463B2 (ja) 検索装置、検索方法、プログラム、及び記録媒体
JP4726310B2 (ja) 情報検索装置、情報検索用マルチプロセッサおよびルータ
CN106330721B (zh) Ip路由查找方法及装置
CN112565089B (zh) 一种路由信息的处理方法及装置
JP2018196075A (ja) 検索装置、検索プログラム、及び検索方法
JP3754043B2 (ja) データ検索装置
Bahrambeigy et al. Towards Accelerating IP Lookups on Commodity PC Routers using Bloom Filter: Proposal of Bloom-Bird

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant