図面 (/)

技術 検索装置、検索方法、プログラム、及び記録媒体

出願人 エヌ・ティ・ティ・コミュニケーションズ株式会社
発明者 浅井大史小原泰弘
出願日 2016年6月23日 (3年4ヶ月経過) 出願番号 2016-124838
公開日 2016年9月23日 (3年1ヶ月経過) 公開番号 2016-170818
状態 特許登録済
技術分野 検索装置 広域データ交換
主要キーワード マスクベクトル データ規模 ラディックス マルチウェイ 可搬メモリ マスク無し ルート経路 経路数
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年9月23日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (17)

課題

汎用ハードウェアを用いる場合でも、木構造表現される検索対象データ高速検索する。

解決手段

検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置において、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトルを含み、前記演算手段は、キーデータから所定ビット長チャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、遷移先のノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する。

概要

背景

ルータ等の装置においては、受信したパケット宛先アドレスに基づいて経路表検索して、パケットの転送先を決定する処理が行われる。当該処理では、最長一致探索が行われるが、そのために、従来、パトリシアトライ(Trie)、ラディックス木(基数木)等が用いられていた。従来は2分木のものが主流であり、性能は高くても数Mlps(Mega Lookup per second)であった。多進木(N−ary/Multiway)のものも考案されていたが、実用面では主流ではなかった。これらの性能が望ましいものではないため、数百Mlpsを実現するTCAMというハードウェアが事実上の標準となっている。TCAMでは経済性集積度規模性、消費電力発熱に難点がある。

TCAMの問題点を打破するため、市販品のデバイスソフトウェアを組み合わせて経路検索する技術が近年現れてきている。PacketShader、GPU Click、GAMT等はGPUを利用して高い経路検索性能を実現するが、GPUを利用するためTCAMと同様に熱問題などを抱える。なお、先行技術文献として特許文献1がある。

概要

汎用のハードウェアを用いる場合でも、木構造表現される検索対象データ高速に検索する。検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置において、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトルを含み、前記演算手段は、キーデータから所定ビット長チャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、遷移先のノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する。

目的

本発明は上記の点に鑑みてなされたものであり、汎用のハードウェアを用いる場合でも、木構造で表現される検索対象データを高速に検索することを可能とする技術を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置であって、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、前記演算手段は、キーデータから所定ビット長チャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する、検索装置であり、前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納され、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記ビットベクトルにおける内部ノードを示すビットの値である0又は1の個数を数え、当該個数と前記第1のベース情報とを用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記ビットベクトルにおけるリーフノードを示すビットの値である1又は0の個数を数え、当該個数と前記第2のベース情報とを用いて当該遷移先のリーフノードにアクセスすることを特徴とする検索装置。

請求項2

検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置であって、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、前記演算手段は、キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する、検索装置であり、前記検索対象データにおける各内部ノードについて、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、同じ値を持つリーフノードは圧縮され、前記検索対象データにおける各内部ノードは、圧縮前の所定のリーフノードの格納位置を示すビットを有するリーフベクトルを含み、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記第2のベース情報と、前記リーフベクトルにおける前記格納位置を示すビットの数とを用いて当該遷移先のリーフノードにアクセスすることを特徴とする検索装置。

請求項3

前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記ビットベクトルにおける内部ノードを示すビットの値である0又は1の個数を数え、当該個数と前記第1のベース情報とを用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記リーフベクトルにおける前記格納位置を示すビットの値である1又は0の個数を数え、当該個数と前記第2のベース情報とを用いて当該遷移先のリーフノードにアクセスすることを特徴とする請求項2に記載の検索装置。

請求項4

前記演算手段は、前記ビットベクトルと前記リーフベクトルのうちの前記ビットベクトルを先に調べ、当該ビットベクトルのビットの値に基づき前記リーフベクトルを使用することを特徴とする請求項2に記載の検索装置。

請求項5

前記演算手段は、当該演算手段により構成されるCPUのpopcnt命令を用いて前記ビットの数を算出することを特徴とする請求項1ないし4のうちいずれか1項に記載の検索装置。

請求項6

前記演算手段と前記記憶手段は、64ビットCPU上で構成することを特徴とする請求項1ないし5のうちいずれか1項に記載の検索装置。

請求項7

前記チャンクは、6ビット長であり、前記ビットベクトルは、64ビット長であることを特徴とする請求項1ないし6のうちいずれか1項に記載の検索装置。

請求項8

前記演算手段と前記記憶手段は、64ビットCPU上で構成し、前記チャンクは、6ビット長であり、前記ビットベクトルは、64ビット長であり、前記演算手段は、前記64ビットCPUのpopcnt命令を用いて前記ビットの数を算出し、前記遷移先のノードへのアクセスを、ベース情報からの、当該ビットの数に基づくオフセットを用いて行うことを特徴とする請求項1ないし4のうちいずれか1項に記載の検索装置。

請求項9

前記演算手段は、前記キーデータから前記所定ビット長よりも長いビット長のチャンクを取得し、当該チャンクを用いて探索を行うことにより、ダイレクトにリーフノードに到達することを特徴とする請求項1ないし8のうちいずれか1項に記載の検索装置。

請求項10

コンピュータを、請求項1ないし9のうちいずれか1項に記載の前記検索装置における各手段として機能させるためのプログラム

請求項11

請求項1ないし9のうちいずれか1項に記載の前記検索対象データを格納したコンピュータ読み取り可能な記録媒体

請求項12

検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段とを備える検索装置が実行する検索方法であって、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、前記検索方法は、キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する演算ステップを有し、前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納され、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、前記演算ステップにおいて、前記検索装置は、前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記ビットベクトルにおける内部ノードを示すビットの値である0又は1の個数を数え、当該個数と前記第1のベース情報とを用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記ビットベクトルにおけるリーフノードを示すビットの値である1又は0の個数を数え、当該個数と前記第2のベース情報とを用いて当該遷移先のリーフノードにアクセスすることを特徴とする検索方法。

請求項13

検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段とを備える検索装置が実行する検索方法であって、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、前記検索方法は、キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する演算ステップを有し、前記検索対象データにおける各内部ノードについて、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、同じ値を持つリーフノードは圧縮され、前記検索対象データにおける各内部ノードは、圧縮前の所定のリーフノードの格納位置を示すビットを有するリーフベクトルを含み、前記演算ステップにおいて、前記検索装置は、前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記第2のベース情報と、前記リーフベクトルにおける前記格納位置を示すビットの数とを用いて当該遷移先のリーフノードにアクセスすることを特徴とする検索方法。

技術分野

0001

本発明は、木構造表現される検索対象データを探索することにより、所望のデータを取得する検索技術に関連するものである。

背景技術

0002

ルータ等の装置においては、受信したパケット宛先アドレスに基づいて経路表検索して、パケットの転送先を決定する処理が行われる。当該処理では、最長一致探索が行われるが、そのために、従来、パトリシアトライ(Trie)、ラディックス木(基数木)等が用いられていた。従来は2分木のものが主流であり、性能は高くても数Mlps(Mega Lookup per second)であった。多進木(N−ary/Multiway)のものも考案されていたが、実用面では主流ではなかった。これらの性能が望ましいものではないため、数百Mlpsを実現するTCAMというハードウェアが事実上の標準となっている。TCAMでは経済性集積度規模性、消費電力発熱に難点がある。

0003

TCAMの問題点を打破するため、市販品のデバイスソフトウェアを組み合わせて経路検索する技術が近年現れてきている。PacketShader、GPU Click、GAMT等はGPUを利用して高い経路検索性能を実現するが、GPUを利用するためTCAMと同様に熱問題などを抱える。なお、先行技術文献として特許文献1がある。

先行技術

0004

特開2000−083054号公報

発明が解決しようとする課題

0005

上記のようにTCAMやGPU等の特定のデバイスを利用すると発熱等の問題があるため、特定のデバイスを利用して経路検索を高速化することは好ましくない。

0006

特定のハードウェアの利用を前提とすることなく、汎用のハードウェア(例:市販のCPU等)でソフトウェアにより経路検索を高速化する技術(例:DXR、SAIL)も提案されているが、当該技術には、経路表内の経路数が大規模になった際や、アドレス長が長くなった際に性能が低下してしまうという問題点がある。

0007

汎用のハードウェアを用いる検索処理において、検索対象データのデータ規模が大規模になったり、キーデータ長が長くなった場合に検索性能が低下する問題は経路検索に限らず生じる問題である。

0008

本発明は上記の点に鑑みてなされたものであり、汎用のハードウェアを用いる場合でも、木構造で表現される検索対象データを高速に検索することを可能とする技術を提供することを目的とする。

課題を解決するための手段

0009

本発明の実施の形態によれば、検索対象データを格納した記憶手段と、
キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置であって、
前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、
前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、
前記演算手段は、
キーデータから所定ビット長チャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する、検索装置であり、
前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納され、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、
前記演算手段は、
前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記ビットベクトルにおける内部ノードを示すビットの値である0又は1の個数を数え、当該個数と前記第1のベース情報とを用いて当該遷移先の内部ノードにアクセスし、
遷移先がリーフノードである場合に、前記ビットベクトルにおけるリーフノードを示すビットの値である1又は0の個数を数え、当該個数と前記第2のベース情報とを用いて当該遷移先のリーフノードにアクセスする
ことを特徴とする検索装置が提供される。

0010

また、本発明の実施の形態によれば、検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段とを備える検索装置が実行する検索方法であって、
前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、
前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、
前記検索方法は、
キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する演算ステップを有し、
前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納され、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、
前記演算ステップにおいて、前記検索装置は、
前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記ビットベクトルにおける内部ノードを示すビットの値である0又は1の個数を数え、当該個数と前記第1のベース情報とを用いて当該遷移先の内部ノードにアクセスし、
遷移先がリーフノードである場合に、前記ビットベクトルにおけるリーフノードを示すビットの値である1又は0の個数を数え、当該個数と前記第2のベース情報とを用いて当該遷移先のリーフノードにアクセスする
ことを特徴とする検索方法が提供される。

発明の効果

0011

本発明の実施の形態によれば、汎用のハードウェアを用いる場合でも、木構造で表現される検索対象データを高速に検索することが可能となる。

図面の簡単な説明

0012

マルチウェイ基数探索方法を説明するための図である。
本発明の実施の形態に係る検索装置10の構成図である。
本発明の実施の形態に係る検索装置20を示す図である。
記憶部12に格納される検索対象データの例を示す図である。
本実施の形態における検索対象データの構造及び検索処理の概要を説明するための図である。
内部ノードとリーフノードのより具体的な例を示す図である。
検索処理の手順を説明するためのフローチャートである。
ダイレクトポインティングを説明するための図である。
リーフノードのデータの圧縮例を説明するための図である。
圧縮例におけるデータ構造の例を説明するための図である。
リーフノードのデータの圧縮例を説明するための図である。
圧縮例におけるデータ構造の例を説明するための図である。
内部ノードのデータの圧縮例を説明するための図である。
leaf maskを適用する場合における内部ノードのデータ構造を示す図である。
leaf maskを使用する場合において、リーフの値を取得する処理のフローチャートである。
leaf maskに関するデータ作成方法を説明するための図である。

実施例

0013

以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。

0014

(探索方法について)
本実施の形態では、本発明の検索技術の適用先の例として、ルータにおいて、受信したパケットの宛先アドレスをキーとして、ルーティングテーブル(より具体的にはフォワーディングテーブル)を最長一致で検索することにより、当該パケットの転送先とするネクストホップの情報を取得する処理を想定している。ただし、本発明の適用先はこれに限らず、本発明は最長一致に限らず、完全一致等の様々な種類の検索に適用できる。以下では、検索(探索)の対象とするデータを検索対象データと呼ぶ。また、宛先アドレス等の検索のキーとなるデータをキーデータと呼ぶ。

0015

本実施の形態では、検索対象データを検索する手法として、多進木で表現されるマルチウェイ基数探索法を用いているので、まず、マルチウェイ基数探索法の概要を図1を参照して説明する。

0016

マルチウェイ基数探索法では、キーデータを先頭から所定数複数ビット(以下、チャンクと呼ぶ)ずつに分け、当該複数ビット毎に木の遷移を行う。図1は、2ビットずつチャンクとする例である。各チャンクは4種類の値(図1では、a、b、c、dと表す)を取り得るから、木における各ノードは4方向に分岐する。分岐先は内部ノード(図1で丸で示すノード)もしくはリーフノード(図1四角で示すノード)である。

0017

キーデータにおける最初のチャンクから一段目のノードで探索を開始し、該当する値の子ノードに分岐し、キーを次のチャンクに進めることで、順次探索を行い、リーフノードに到達したら探索終了となる。

0018

図1の例で、例えば、キーデータがdxxxx(xは任意の値)である場合、5で示すリーフノードに到達する。また、キーデータがbbxxである場合、6で示すリーフノードに到達する。リーフノードには、例えば、ネクストホップを示す情報(例:アドレス、IF情報等)が格納され、リーフノードに到達した場合、キーデータに対応するネクストホップの情報を取得できる。

0019

上記の例は、チャンク長を2ビットとする例であるが、例えば、64ビットCPUアーキテクチャを用いる場合、ビット幅を同一にして演算を効率的にするために、チャンク長を6ビットとして、各ノードで64分岐する木のデータ構造を使用することができる。

0020

上記のようなマルチウェイ基数探索法においては、一般に、各ノードは、子ノードをポイントするためのポインタ(子ノードを格納するアドレス等)を分岐数分持つが、各ポインタは、例えば64ビットで子ノードを指定するため、全体の木のデータ量が非常に大きくなるという問題がある。そのため、このようにポインタを用いる構成では、木のデータを汎用CPUのキャッシュに格納し切れず、CPUの外にあるメモリに格納せざるを得ないため、検索速度が低下するという問題がある。

0021

一方、本実施の形態に係る技術では、上記の技術に比べて、各内部ノードのデータ量を大幅に削減できるとともに、同じデータを持つノードを圧縮することもできるため、全体の木のデータ量を小さくすることができ、汎用CPUのキャッシュに木のデータを格納して処理を行うことが可能となる。従って、汎用CPU等の汎用のハードウェアを用いる場合でも、高速な検索処理が可能となる。以下、本実施の形態に係る技術をより詳細に説明する。

0022

装置構成例)
まず、本実施の形態に係る検索処理を実行する検索装置の構成例を説明する。図2は、本実施の形態に係る検索装置10の構成例を示す図である。

0023

図2に示すように、検索装置10は、演算部11、記憶部12、入力部13、出力部14を備える。演算部11は、後述する方法でキーデータを用いた検索対象データに対する検索処理を実行する機能部である。記憶部12は、検索対象データを格納する機能部である。入力部13は、キーデータを入力する機能部である。出力部14は検索結果を出力する機能部である。

0024

例えば、検索装置10は、汎用コンピュータであり、演算部11と記憶部12がCPUを構成する。この場合、記憶部12は、CPU内のキャッシュに相当する。また、記憶部12の一部がCPU外のメモリであってもよい。当該CPUは、本実施の形態に係る処理のロジックを持つプログラムに従って動作する。当該プログラムは記憶部12に格納される。また、当該プログラムは記憶部12以外のメモリ等の記憶部に格納されてもよい。

0025

当該プログラムは、可搬メモリ等の記録媒体に格納して、当該可搬メモリから汎用コンピュータにロードすることで、当該コンピュータを検索装置10として使用することができる。

0026

また、演算部11と記憶部12を、本実施の形態に係る処理のロジックをハードウェア回路として組み込んだ装置として構成することもできる。

0027

図3に、本実施の形態に係る検索装置の他の例である検索装置20を示す。検索装置20は、例えばルータとして機能する装置である。図3に示すように、検索装置20は、パケット処理部21、宛先決定部22、及び複数のインターフェース(IF)を有する。パケット処理部21は、IFを介してパケットを受信し、宛先決定部22により決定された宛先(ネクストホップ)に対応するIFからパケットを出力する。図3には、パケットをIF−Aから受信し、IF−Bから出力する例が示されている。

0028

宛先決定部22は、ルーティングテーブル(フォワーディングテーブル)を格納する記憶部を備え、パケット処理部21からパケットの宛先アドレスをキーデータとして受け取り、当該キーデータに基づきフォワーディングテーブルを検索することにより当該パケットのネクストホップを決定し、当該ネクストホップの情報をパケット処理部21に出力する。宛先決定部22として、例えば、図2に示した検索装置10を用いることができる。

0029

以下、検索装置10により実行される検索処理を詳細に説明する。以下、基本的な処理を行う方式を実施例1として説明し、実施例1に対してノードの圧縮を可能とした機能を加えた例を実施例2〜4として説明する。

0030

(実施例1)
図4に、検索装置10の記憶部12に格納される検索対象データの例を示す。図4は、実施例1〜4に共通である。前述したように、本実施の形態では、マルチウェイ基数探索法をベースとした検索処理を行うことから、検索対象データは、木における各内部ノードのデータを保持するnode array(ノード配列)と、木における各リーフノードのデータであるleaf array(リーフ配列)を有する。配列として格納される各ノードのデータには、各配列のIndexを指定することでアクセスできる。

0031

leaf arrayとnode arrayからなる検索対象データは、例えば可搬メモリ等の記録媒体に格納して、当該可搬メモリから検索装置10にロードすることで、検索装置10を検索対象データに対する検索装置10として使用することができる。また、検索対象データを、あるコンピュータからネットワークを経由して検索装置10にロードすることもできる。

0032

図5を参照して、実施例1における内部ノードのデータ構造について説明する。図5は、チャンクのビット長が2の場合、つまり、木の各ノードから4方向に分岐する場合の例であるが、チャンクのビット長が何ビットであっても同様の構造である。

0033

図5に示すように、内部ノードは、vector、base0、base1を有する。vectorは、当該内部ノードからの分岐数のビットからなるビットベクトルである。キーデータのチャンクが2ビットの場合、00、01、10、11の4種類の値を取り得る。vectorの各ビットは、右端から順に、上記4種類の各値に対応している。なお、「右端から」とするのは一例であり、「左端から」であってもよい。例えば、little endianのCPUを用いる場合に右端から数え、big endianのCPUを用いる場合に左端から数える。

0034

図5の例では、例えば、vectorの右端(0番目)のビットがチャンク00に対応し、1番目のビットがチャンク01に対応し、2番目のビットがチャンク10に対応し、3番目のビットがチャンク11に対応する。vectorの各ビットは、当該内部ノードからの遷移先(子ノード)が、内部ノードであるか、リーフノードであるかを示す。本実施の形態では、1が内部ノードを示し、0がリーフノードを示すが、これは例であり、1がリーフノードを示し、0が内部ノードを示すように構成してもよい。

0035

例えば、図5に示す内部データに対応するチャンクが00、01、10、11のうちの01であった場合、演算部11は、vectorの0番目から数えて1番目のビット(1)を参照することで、次のノードは内部ノードであることを把握する。また、例えば、チャンクが00、01、10、11のうちの00であった場合、演算部11は、vectorの0番目のビット(0)を参照することで、次のノードはリーフノードであることを把握する。

0036

上記のように演算部11は、vectorにより遷移先のノードが内部ノードであるかリーフノードであるかを把握できるが、このままでは、内部ノード/リーフノードのデータを取得するために、node array/leaf arrayにおけるどのIndexの要素にアクセスすればよいかわからない。そこで、本実施の形態では、内部ノードはbase0、base1を保持する。

0037

base1は、node arrayにおける、当該内部ノードのvectorのビット1に対応する子の内部ノードの格納開始Indexを保持する。base0は、leaf arrayにおける、当該内部ノードのvectorのビット0に対応する子のリーフノードの格納開始Indexを保持する。

0038

本実施の形態では、node arrayにおいては、各内部ノードについて、当該内部ノードの子となる内部ノードのデータがIndexの順番で格納されている。例えば、ある内部ノードについて、子の内部ノードが3つある場合、当該子の内部ノードの3つのデータは、node arrayにおいて、Indexが連続する3つのデータとして格納される。この3つのデータのうちIndexが先頭(最小)となるデータのIndexがbase1である。

0039

また、leaf arrayにおいて、各内部ノードについて、当該内部ノードの子となるリーフノードのデータがIndexの順番で格納されている。例えば、ある内部ノードについて、子のリーフノードが3つある場合、当該子のリーフノードの3つのデータは、leaf arrayにおいて、Indexが連続する3つのデータとして格納される。この3つのデータのうちIndexが先頭(最小)となるデータのIndexがbase0である。なお、本実施の形態で使用するIndexは、格納場所を指す指標であり、これを「アドレス」と言い換えてもよい。

0040

上記のようにしてnode array/leaf arrayにデータが格納されていることから、演算部11は、次のようにして、base0/base1を用いて子の内部ノード/リーフノードのデータにアクセスする。

0041

vectorのあるビット位置(0番目から数えてv番目とする)の子の内部ノードへのアクセスに関し、演算部11は、vectorの0番目からv番目までのビット位置の1の個数を算出(カウント)する。つまり、vectorの右端から(v+1)ビットの中の1の個数を算出する。この個数をbc(bit count)とすると、演算部11は、node arrayにおいて、bcにbase1を加えた値から1を引いた値(bc+base1−1)のIndexにアクセスすることで該当内部ノードのデータを取得できる。

0042

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にアクセスすることで該当リーフノードのデータを取得できる。

0043

図5には、上記の方法で、子の内部ノード(Index:2498)、及びリーフノード(Index:3127〜3129)にアクセスすることが示されている。

0044

一般にCPUにはビットの数を高速に算出するpopcntという機能が備えられており、本実施の形態では、この機能を有効に活用でき、高速に探索を行うことができる。なお、popcntを使用することは例であり、popcntを使用しないこととしてもよい。

0045

図5は、チャンク長が2ビット、つまり、vectorが4ビットである例を示しているが、これは例であり、チャンク長/vectorは他の長さであってもよい。図6に、チャンク長が6ビット、つまり、vectorが64(26)ビットである場合の例を示す。図6には、既に説明したとおりに、内部ノードがvector、base0/base1を有し、ビットカウント及びbase0/base1により、子の内部ノード/リーフノードにアクセスできることが示されている。

0046

本実施の形態では、内部ノードは、ビットベクトルと2つのbaseを持てばよく、分岐毎にポインタを有する方式に比べて、各ノードのデータ量を大幅に削減でき、結果として、検索対象データのデータ量を削減できる。

0047

図7を参照して、演算部11が実行する検索処理の処理手順を説明する。この処理の前提として、演算部11にはキーデータが入力され、また、記憶部12には、上述した構造を持つ検索対象データ(node array/leaf array)が格納されているものとする。また、図7は、リーフノードに到達することで検索処理が終了する例を示している。

0048

演算部11は、node arrayにおける最初の内部ノードからvectorを取得し(ステップ101)、また、キーデータから最初のチャンクを取得する(ステップ102)。

0049

演算部11は、チャンクに該当するvectorの位置のビットを読み、当該ビットが1であるかどうか判定する(ステップ103)。当該ビットが1である場合、前述したように、ビットカウントbcを算出し、(bc+base1−1)のIndexに格納されている内部ノードにアクセスして、当該内部ノードのvectorを取得する(ステップ104)。

0050

演算部11は、キーデータから次のチャンクを取得し(ステップ105)、再びステップ103の判定を実行する。

0051

ステップ103の判定の結果、チャンクに該当するvectorの位置のビットが0である場合(ステップ103のNo)、ステップ106に進む。ステップ106において、演算部11は、前述したように、ビットカウントbcを算出し、(bc+base0−1)のIndexに格納されているリーフノードにアクセスして、当該リーフノードの値を取得する。

0052

なお、例えば、フォワーディングテーブルにおいては、リーフとなるプレフィックス長が特定の範囲(例:/11〜/24)に集中する傾向があるため、最初のほうのノードの探索を省略して、ダイレクトに目的のエントリに到達させることが可能である。これをダイレクトポインティングと呼ぶ。図8を参照して例を説明する。

0053

図8の左側は、ダイレクトポインティングを行わない例であり、この例では、6ビットずつのチャンクで探索を行っている。図8の右側は、最初に12ビットのチャンクで探索を行うダイレクトポインティングの例を示している。図8の右側の場合でも、当該チャンクでリーフノードに到達できない場合、以降、実施例1での上記の方法と同様にして、例えば6ビットずつのチャンクで探索を行う。ダイレクトポインティングは、他の実施例にも適用可能である。

0054

(実施例2)
次に、実施例2として、実施例1で説明した方式に対して、リーフデータを圧縮できる方式を説明する。例えば、実施例1の方式をフォワーディングテーブルの検索に適用する際に、重複する値(ネクストホップ)を持つリーフノードが多く発生することが考えられる。実施例2は、実施例1の方式をベースとし、リーフノードを圧縮して保持できるようにしている。以下では、主に実施例1と異なる部分について説明する。

0055

図9は、実施例2における内部ノードを示す図である。図9に示すように、実施例2においては、実施例1で説明したvector、base0、base1に加えて、leafvecが追加される。leafvecはvectorのビット長と同じビット長である。

0056

また、leaf arrayにおける各内部ノードの子になるリーフノード(つまり、各段のリーフノード)に関して、同じ値を持つ連続するリーフノードは、連続が開始する最初のリーフノードのみが保持される。図9の例では、Indexが3127、3128、3129のリーフノードに関して、値は全部同じで7であり、この場合、Indexが3127のリーフノードのみが保持される。このような圧縮の結果、複数のリーフノードがある場合でも、同じ値を持つ複数のリーフノードを含まず、それぞれ異なる値となる。

0057

leafvecの要素は0又は1のビットであり、右端から、圧縮前のリーフノードの連続が開始する位置に対応するビットに1が立てられている。例えば、図9の例では、最初のリーフノードから連続が始まるので、当該最初のリーフノードに対応する最初(0番目)のビットに1が立てられている。また、連続が終わり別の値のリーフノードが始まる場合(リーフノードが変化する場合)、その位置に1が立てられる。リーフノードが変化する場合とは、最初のリーフノードを含む。ここでの「連続」とは1個の場合を含む。つまり、リーフノードのデータが全て異なる場合、リーフノードに対応するleafvecのビット位置には全て1が立てられる。leafvecの使用方法は以下のとおりである。

0058

演算部11が、チャンクに対応するvectorのビット(0番目から数えてv番目のビットとする)が0であることを検出すると、子がリーフノードであることを把握する。演算部11は、leafvecにおける右端の0番目から数えてv番目までのビット(v+1個のビット)における1のビットの個数を算出する。当該個数をbcとすると、vectorの場合と同様に、演算部11は、(bc+base0−1)のIndexのリーフノードにアクセスする。

0059

図10に、実施例2における内部ノードとリーフノードのデータ例を示す。図10の例において、演算部11は、チャンクに基づき、(a)で示す内部ノードにおけるvectorの0番目から数えた1番目のビットが1であることを検知し、それに対応する(c)の内部ノードにアクセスすることが示されている。また、例えば、(a)の内部ノードにおいて、チャンクが0番目から数えた2番目(0)に対応する場合に、演算部11は、leafvecにおける2番目までの3ビットにおける1の個数を算出し、base0を用いて、当該個数に対応するリーフノード(L(0))にアクセスする。

0060

リーフノードの圧縮は、上記のようにleafvecを用いる以外の方法で実現してもよい。以下、リーフノードの圧縮に係る他の方法を実施例3として説明する。ただし、実施例3の方法は、leafvecを用いる方法と実質的に同じである。

0061

(実施例3)
図11は、実施例3における内部ノードを示す図である。図11に示すように、実施例3においては、実施例1で説明したvector、base0、base1に加えて、maskが追加される。maskはvectorのビット長と同じビット長である。

0062

また、leaf arrayにおける各内部ノードの子になるリーフノード(つまり、各段のリーフノード)に関して、同じ値を持つ連続するリーフノードは、連続が開始する最初のリーフノードのみが保持される。図11の例では、Indexが3127、3128、3129のリーフノードに関して、値は全部同じで7であり、この場合、Indexが3127のリーフノードのみが保持される。このような圧縮の結果、複数のリーフノードがある場合でも、同じ値を持つ連続する複数のリーフノードを含まない。

0063

maskの要素は0又は1のビットであり、右端から、圧縮前のリーフノードの連続が開始する位置に対応するビットに0が立てられ、当該開始位置から同じ値の連続するリーフノードの位置に1(マスク)が立てられる。また、連続が終わり別の値のリーフノードが始まる場合(リーフノードが変化する場合)、その位置に0が立てられる。リーフノードが変化する場合とは、最初のリーフノードを含む。

0064

なお、内部ノードに該当する位置は、1を立ててもよいし、0でもよいが、本例では0としている。図11の例では、3つのリーフノードが連続するから、最初のリーフノードに該当するビット位置に0が立てられ、以降のリーフノードに該当するビット位置にはマスクである1が立てられる。maskの使用方法は以下のとおりである。

0065

演算部11が、チャンクに対応するvectorのビット(0番目から数えてv番目のビットとする)が0であることを検出すると、子がリーフノードであることを把握する。実施例3では、演算部11は、vectorとmaskのOR演算を行って、OR演算を行った後のvectorにおける右端の0番目から数えてv番目までのビット(v+1個のビット)における0のビットの個数を算出する。当該個数をbcとすると、演算部11は、(bc+base0−1)のIndexのリーフノードにアクセスする。

0066

図12に、実施例3における内部ノードとリーフノードのデータ例を示す。図11の例において、演算部11は、チャンクに基づき、(a)で示す内部ノードにおけるvectorの0番目から数えた1番目のビットが1であることを検知し、それに対応する(c)の内部ノードにアクセスすることが示されている。また、例えば、(a)の内部ノードにおいて、チャンクが0番目から数えた2番目(0)に対応する場合に、演算部11は、mask後のvectorにおける2番目までの3ビットにおける0の個数を算出し、base0を用いて、当該個数に対応するリーフノード(L(0))にアクセスする。

0067

maskは内部ノードの圧縮にも適用できる。maskを内部ノードの圧縮に適用する例を図13を参照して説明する。図13は、図6と同様に、チャンク長が6ビット、つまり、vectorが64(26)ビットである場合の例を示している。この例でも、実施例1で説明したvector、base0、base1に加えて、maskが追加される。maskはvectorのビット長と同じビット長である。

0068

また、各段の内部ノードに関して、同じ値を持つ連続する内部ノードは、連続が開始する最初の内部ノードのみが保持される。図13の例では、(a)に示すように、同一のサブツリーを持つ内部ノードが3つある。この場合、(b)に示すように、3つのうちの最初の内部ノードのみが保持される。このような圧縮の結果、複数の内部ノードがある場合でも、同じ値を持つ連続する複数の内部ノードを含まない。

0069

maskの要素は0又は1のビットであり、右端から、圧縮前の内部ノードの連続が開始する位置に対応するビットに1が立てられ、当該開始位置から同じ値の連続する内部ノードの位置に0(マスク)が立てられる。また、連続が終わり別の値の内部ノードが始まる場合(内部ノードが変化する場合)、その位置に1が立てられる。

0070

図13の例では、3つの内部ノードが連続するから、最初の内部ノードに該当するビット位置に1が立てられ、以降の内部ノードに該当するビット位置にはマスクである0が立てられる。つまり、図13(b)に示すように、vectorの最初の1に対応するmaskのビットは1であり、次の1とその次の1に対応するmaskのビットは0である。maskの使用方法は以下のとおりである。

0071

演算部11が、チャンクに対応するvectorのビット(0番目から数えてv番目のビットとする)が1であることを検出すると、子が内部ノードであることを把握する。演算部11は、vectorとmaskのAND演算を行って、AND演算を行った後のvectorにおける右端の0番目から数えてv番目までのビット(v+1個のビット)における1のビットの個数を算出する。当該個数をbcとすると、演算部11は、(bc+base1−1)のIndexの内部ノードにアクセスする。

0072

(実施例4)
次に、実施例4について説明する。実施例4は、実施例2、3よりも更にリーフノードを圧縮できる方式である。実施例4における内部データの構造を図14に示す。図14に示すように、実施例4の内部データは、既に説明したvector、leafvec、base0、base1に加えて、「A」で示すように、leaf maskとmasked leafが追加されたものである。記憶部12にはnode arrayとleaf arrayが格納されている。

0073

leaf maskはvectorと同じビット長の0/1のビットからなるデータである。masked leafは、あるリーフノードのデータである。以下、leaf maskとmasked leafを用いる場合の演算部11の動作を説明する。

0074

図15のフローチャートを参照して、実施例4における検索装置10の演算部11の動作例を説明する。図15は、実施例1、2とは異なる処理の部分を特に説明するためのものである。

0075

ステップ201において、演算部11は、現在のチャンクのvectorにおける該当ビット(0番目から数えてv番目のビットとする)が0であることを検出することで、リーフノードに遷移することを検出する。

0076

ステップ202では、演算部11は、leaf maskにおいて0番目から数えてv番目のビットが1であるかどうかを判定する。これが1である場合(ステップ202のYes)、masked leafの値をリーフデータの値として取得する(ステップ203)。

0077

ステップ202において、v番目のビットが1でない場合(ステップ202のNo)、演算部11は、実施例2と同様にして、leafvecの0番目からv番目までの1の個数(bc)を算出し、(bc+base0−1)のIndexのリーフノードにアクセスして値を取得する(ステップ204)。

0078

次に、図16を参照して、実施例4におけるleaf maskに関連するデータの作成方法を説明する。以下で説明するデータの作成は、検索装置10が行ってもよいし、他の装置(コンピュータ)が行ってもよい。以下では、データの作成を行う装置を作成装置と呼ぶ。作成装置は、検索装置10又は他の装置である。作成装置が他の装置である場合、データ作成後に、作成データを検索装置10の記憶部12に格納する。

0079

まず、作成装置は、圧縮なしでleaf arrayを計算する。これにより、例えば4分木であれば、親の内部ノード毎に、例えば図5のLで示すように、Indexが連続するリーフノードのデータが作成される。

0080

また、64分木であれば、親の内部ノード毎に、leaf arrayの項目数は最大で64になる。また、例えば16分木の例において、リーフ情報が3種類のA、B、Cであるとすると、リーフ情報が、図16(a)に示すとおり、例えばABAA BBBA BCBB CCCCのようにleaf array内に並ぶ。

0081

次に、作成装置は、マスクされるリーフ情報を選ぶ。本例では、Bをマスクして省略することにする。一般には、連続する断片が現れる回数が最も多いものをマスクするのが有効であることから、作成装置は、連続する断片が現れる回数が最も多いBをマスクすると決定する。なお、「連続する断片」は、ABAにおけるBのように1つの場合を含む。マスクされたリーフの情報Bは、masked leafに格納する。

0082

次に、作成装置は、マスクされるリーフ情報が現れるスロットを、leaf mask に保存する。マスクされるリーフ情報が現れるスロットとは、vectorにおける当該リーフに対応するビット位置に相当する。例えば、vectorが0010である場合に、左端を1番目として数えて2番目のビット0に対応するリーフをマスクする場合、leaf maskに、0100が保存される。

0083

また、作成装置は、leaf arrayにおいて、マスクされるリーフ情報のスロットを、直前の値と同じにする。これにより、図16(a)に示すリーフ情報から、図16(b)に示すように、「leaf mask:0100 1110 1011 0000」が得られ、「leaf array: AAAA AAAAACCC CCCC」が得られる。なお、本例は、big endianであるため、左端から数える。図16(b)において、下線部分がマスクされた部分であり、数える方向での直前の値(左の値)と同じ値になっている。

0084

次に、リーフマスク無しの場合と同じように、連続する部分を圧縮する。これにより、図16(c)に示すように、「leafvec:1000 0000 0100 0000」となり、「leaf array:AC」となる。

0085

上記の処理の結果、図16(d)に示すように、「leaf mask: 0100 1110 1011 0000」、「masked leaf:B」、「leaf vector:1000 0000 0100 0000」、「leaf array:AC」が得られる。

0086

なお、参考までに、リーフマスク無しで圧縮した場合のleaf arrayは「ABABABCBC」となり、実施例4により高い圧縮効果が得られることがわかる。

0087

実施例4では、マスク1つ(例:64bit)とリーフ1つが追加されるが、不連続であったいくつかのリーフを省略することができ、leaf arrayのさらなる圧縮が実現できる。これは、leaf arrayがあるネクストホップ値によって多く分断されている(状態になっている)場合や、リーフ1つの大きさ(leaf arrayの1エントリのサイズ)が16バイトなど大きかった場合に特に有効となる。

0088

なお、実施例2、3、4は、リーフノードを圧縮する例を示しているが、同じデータを持つ内部ノードに関しても、リーフノードの場合と同じようにして、圧縮することが可能である。また、リーフノードの圧縮と内部ノードの圧縮の両方を行うこととしてもよい。

0089

(実施の形態の効果)
以上、説明したように、本実施の形態では、木のデータ量を大幅に削減できることから、例えば汎用CPUのキャッシュ(例:L1、L2、L3キャッシュ)に検索対象データを格納して検索処理を実施でき、高速な検索処理を実現できる。特に、例として検索対象データが経路表である場合には、経路表内の経路数が大規模になった際に性能が低下してしまう問題点が解決される。また、処理が高速化されるため、アドレス長が長くなった際に性能が低下してしまう問題点も解決することが可能となる。

0090

また、木の各レベルで、ビット単位部分木の有無を表現するため、メモリ効率が良い。特に、例として64分木を用いる場合、64ビットずつ部分木の有無(子配列)を表現するため、64−bit CPUでの処理効率が良いという特徴を持つ。

0091

また、vector等において、1であるビットを数え、配列の中の該当する子に1ステップで飛べるため、高速処理を実現でき、メモリ効率も良い。また、1であるビットを数えるために、popcnt CPU instruction を使用でき、高速処理を実現できる。また、汎用的な多進木(Multiway trie)をベースにしているため、拡張性・柔軟性が高く、経路表検索に限らず、様々な検索に適用できる。

0092

更に、実施例2〜4で説明したリーフ情報の圧縮を行うことで検索対象データの量を小さくでき、更なる高速化を実現できる。

0093

一例として、本実施の形態に係る技術を用いることで、popcnt CPU instructionを持つ汎用CPUを利用して、50万のIPv4フルルート経路を保持する経路表について、シングルコアで240Mlps程度、4コアで910Mlps程度を実現することができる。TCAMを利用せず、汎用CPUでTCAMと同等から数倍の性能を発揮することができる。

0094

(実施の形態のまとめ)
以上、説明したように、本実施の形態により、検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置であって、前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトルを含み、前記演算手段は、キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、遷移先のノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行することを特徴とする検索装置が提供される。

0095

前記検索対象データにおける各内部ノードは、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスするように構成してもよい。

0096

前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納され、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記第1のベース情報と、前記ビットベクトルにおける内部ノードを示すビットの数とを用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報と、前記ビットベクトルにおけるリーフノードを示すビットの数とを用いて当該遷移先のリーフノードにアクセスすることとしてもよい。

0097

前記検索対象データにおける各内部ノードについて、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、同じ値を持つリーフノードは圧縮され、複数のリーフノードは、同じ値を持つ複数のリーフノードを含まず、前記検索対象データにおける各内部ノードは、圧縮前のリーフノードの値が変化した格納位置を示すビットを有するリーフベクトルを含み、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記第2のベース情報と、前記リーフベクトルにおける前記格納位置を示すビットの数とを用いて当該遷移先のリーフノードにアクセスすることとしてもよい。

0098

前記演算手段は、前記ビットベクトルと前記リーフベクトルのうちの前記ビットベクトルを先に調べ、当該ビットベクトルのビットの値に基づき前記リーフベクトルを使用することとしてもよい。

0099

前記検索対象データにおける各内部ノードについて、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、同じ値を持つリーフノードは圧縮され、複数のリーフノードは、同じ値を持つ複数のリーフノードを含まず、前記検索対象データにおける各内部ノードは、圧縮前のリーフノードの値が変化した格納位置を示すビットを有するマスクベクトルを含み、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記第2のベース情報と、前記マスクベクトルでマスクした前記ビットベクトルにおけるリーフノードを示すビットの数とを用いて当該遷移先のリーフノードにアクセスするようにしてもよい。

0100

前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納されており、同じ値を持つ内部ノードは圧縮され、複数の内部ノードは、同じ値を持つ複数の内部ノードを含まず、前記検索対象データにおける各内部ノードは、圧縮前の内部ノードの値が変化した格納位置を示すビットを有するマスクベクトルを含み、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記第1のベース情報と、前記マスクベクトルでマスクした前記ビットベクトルにおける内部ノードを示すビットの数とを用いて当該遷移先の内部ノードにアクセスすることとしてもよい。

0101

前記検索対象データの各内部ノードについて、遷移先となるリーフノードにおける所定の値がマスクされ、当該マスクされた値が別の値に変更された後に、同じ値を持つリーフノードが圧縮されたことにより、複数のリーフノードは、同じ値を持つ複数のリーフノードを含まず、前記リーフノード配列において、格納位置が連続して格納されており、前記検索対象データにおける各内部ノードは、前記マスクされた所定の値と、当該所定の値を持つリーフベクトルの圧縮前の位置を示すビットを有するリーフマスクと、圧縮前のリーフノードの値が変化した格納位置を示すビットからなるリーフベクトルとを含み、前記演算手段は、前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記ビットベクトルにおける当該ビットの位置と同じ位置に、前記リーフマスクにビットが立っているか否かを判定し、立っている場合に、前記所定の値を当該遷移先のリーフノードの値として取得し、立っていない場合に、前記第2のベース情報と、前記リーフベクトルにおける前記格納位置を示すビットの数とを用いて当該遷移先のリーフノードにアクセスすることとしてもよい。

0102

前記演算手段は、当該演算手段により構成されるCPUのpopcnt命令を用いて前記ビットの数を算出することとしてもよい。

0103

また、前記演算手段と前記記憶手段は、64ビットCPU上で構成することとしてもよい。また、前記チャンクは、6ビット長であり、前記ビットベクトルは、64ビット長であることとしてもよい。

0104

また、前記演算手段と前記記憶手段は、64ビットCPU上で構成し、前記チャンクは、6ビット長であり、前記ビットベクトルは、64ビット長であり、前記演算手段は、前記64ビットCPUのpopcnt命令を用いて前記ビットの数を算出し、前記遷移先のノードへのアクセスを、ベース情報からの、当該ビットの数に基づくオフセットを用いて行うこととしてもよい。

0105

また、前記演算手段は、前記キーデータから前記所定ビット長よりも長いビット長のチャンクを取得し、当該チャンクを用いて探索を行うことにより、ダイレクトにリーフノードに到達するようにしてもよい。

0106

また、本実施の形態により、コンピュータを、前記検索装置における各手段として機能させるためのプログラムを提供することもできる。また、本実施の形態により、前記検索対象データを格納したコンピュータ読み取り可能な記録媒体を提供することもできる。

0107

また、本実施の形態に係る検索方法を、キーデータに基づき検索対象データに対する検索処理を行う検索方法であって、前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトルを含み、前記検索方法は、キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、遷移先のノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行するステップを有する検索方法として構成してもよい。

0108

以下、本明細書に開示される構成を例示的に列挙する。
(第1項)
検索対象データを格納した記憶手段と、
キーデータに基づき前記検索対象データに対する検索処理を行う演算手段と、を備える検索装置であって、
前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、
前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、
前記演算手段は、
キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行する
ことを特徴とする検索装置。
(第2項)
前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納され、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、
前記演算手段は、
前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記第1のベース情報と、前記ビットベクトルにおける内部ノードを示すビットの数とを用いて当該遷移先の内部ノードにアクセスし、
遷移先がリーフノードである場合に、前記第2のベース情報と、前記ビットベクトルにおけるリーフノードを示すビットの数とを用いて当該遷移先のリーフノードにアクセスする
ことを特徴とする第1項に記載の検索装置。
(第3項)
前記検索対象データにおける各内部ノードについて、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、同じ値を持つリーフノードは圧縮され、複数のリーフノードは、同じ値を持つ複数のリーフノードを含まず、
前記検索対象データにおける各内部ノードは、圧縮前のリーフノードの値が変化した格納位置を示すビットを有するリーフベクトルを含み、
前記演算手段は、
前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記第2のベース情報と、前記リーフベクトルにおける前記格納位置を示すビットの数とを用いて当該遷移先のリーフノードにアクセスする
ことを特徴とする第1項に記載の検索装置。
(第4項)
前記演算手段は、前記ビットベクトルと前記リーフベクトルのうちの前記ビットベクトルを先に調べ、当該ビットベクトルのビットの値に基づき前記リーフベクトルを使用する
ことを特徴とする第3項に記載の検索装置。
(第5項)
前記検索対象データにおける各内部ノードについて、遷移先となるリーフノードは、前記リーフノード配列において、格納位置が連続して格納されており、同じ値を持つリーフノードは圧縮され、複数のリーフノードは、同じ値を持つ複数のリーフノードを含まず、
前記検索対象データにおける各内部ノードは、圧縮前のリーフノードの値が変化した格納位置を示すビットを有するマスクベクトルを含み、
前記演算手段は、
前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記第2のベース情報と、前記マスクベクトルでマスクした前記ビットベクトルにおけるリーフノードを示すビットの数とを用いて当該遷移先のリーフノードにアクセスする
ことを特徴とする第1項に記載の検索装置。
(第6項)
前記検索対象データにおける各内部ノードについて、遷移先となる内部ノードは、前記内部ノード配列において、格納位置が連続して格納されており、同じ値を持つ内部ノードは圧縮され、複数の内部ノードは、同じ値を持つ複数の内部ノードを含まず、
前記検索対象データにおける各内部ノードは、圧縮前の内部ノードの値が変化した格納位置を示すビットを有するマスクベクトルを含み、
前記演算手段は、
前記ビットベクトルのビットの値に基づき判定された遷移先が内部ノードである場合に、前記第1のベース情報と、前記マスクベクトルでマスクした前記ビットベクトルにおける内部ノードを示すビットの数とを用いて当該遷移先の内部ノードにアクセスする
ことを特徴とする第1項に記載の検索装置。
(第7項)
前記検索対象データの各内部ノードについて、遷移先となるリーフノードにおける所定の値がマスクされ、当該マスクされた値が別の値に変更された後に、同じ値を持つリーフノードが圧縮されたことにより、複数のリーフノードは、同じ値を持つ複数のリーフノードを含まず、前記リーフノード配列において、格納位置が連続して格納されており、
前記検索対象データにおける各内部ノードは、前記マスクされた所定の値と、当該所定の値を持つリーフベクトルの圧縮前の位置を示すビットを有するリーフマスクと、圧縮前のリーフノードの値が変化した格納位置を示すビットからなるリーフベクトルとを含み、
前記演算手段は、
前記ビットベクトルのビットの値に基づき判定された遷移先がリーフノードである場合に、前記ビットベクトルにおける当該ビットの位置と同じ位置に、前記リーフマスクにビットが立っているか否かを判定し、立っている場合に、前記所定の値を当該遷移先のリーフノードの値として取得し、立っていない場合に、前記第2のベース情報と、前記リーフベクトルにおける前記格納位置を示すビットの数とを用いて当該遷移先のリーフノードにアクセスする
ことを特徴とする第1項に記載の検索装置。
(第8項)
前記演算手段は、当該演算手段により構成されるCPUのpopcnt命令を用いて前記ビットの数を算出する
ことを特徴とする第2項ないし第7項のうちいずれか1項に記載の検索装置。
(第9項)
前記演算手段と前記記憶手段は、64ビットCPU上で構成する
ことを特徴とする第1項ないし第8項のうちいずれか1項に記載の検索装置。
(第10項)
前記チャンクは、6ビット長であり、前記ビットベクトルは、64ビット長である
ことを特徴とする第1項ないし第9項のうちいずれか1項に記載の検索装置。
(第11項)
前記演算手段と前記記憶手段は、64ビットCPU上で構成し、前記チャンクは、6ビット長であり、前記ビットベクトルは、64ビット長であり、
前記演算手段は、前記64ビットCPUのpopcnt命令を用いて前記ビットの数を算出し、前記遷移先のノードへのアクセスを、ベース情報からの、当該ビットの数に基づくオフセットを用いて行う
ことを特徴とする第2項ないし第7項のうちいずれか1項に記載の検索装置。
(第12項)
前記演算手段は、前記キーデータから前記所定ビット長よりも長いビット長のチャンクを取得し、当該チャンクを用いて探索を行うことにより、ダイレクトにリーフノードに到達する
ことを特徴とする第1項ないし第11項のうちいずれか1項に記載の検索装置。
(第13項)
コンピュータを、第1項ないし第12項のうちいずれか1項に記載の前記検索装置における各手段として機能させるためのプログラム。
(第14項)
第1項ないし第12項のうちいずれか1項に記載の前記検索対象データを格納したコンピュータ読み取り可能な記録媒体。
(第15項)
検索対象データを格納した記憶手段と、キーデータに基づき前記検索対象データに対する検索処理を行う演算手段とを備える検索装置が実行する検索方法であって、
前記記憶手段に格納される前記検索対象データは、内部ノード配列とリーフノード配列を有する多進木構造のデータであり、
前記検索対象データにおける各内部ノードは、遷移先が内部ノードであるかリーフノードであるかをビットで表したビットベクトル、遷移先の1つの内部ノードの格納位置を示す第1のベース情報、及び、遷移先の1つのリーフノードの格納位置を示す第2のベース情報を含み、
前記検索方法は、
キーデータから所定ビット長のチャンクを取得し、アクセスしている内部ノードの前記ビットベクトルにおける当該チャンクの値に対応するビットに基づき、当該内部ノードからの遷移先が内部ノードであるか、リーフノードであるかを判定し、判定された遷移先が内部ノードである場合に、前記第1のベース情報を用いて当該遷移先の内部ノードにアクセスし、遷移先がリーフノードである場合に、前記第2のベース情報を用いて当該遷移先のリーフノードにアクセスする処理を、遷移先がリーフノードになるまで繰り返し実行するステップを有する
ことを特徴とする検索方法。

0109

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

0110

10、20検索装置
11演算部
12 記憶部
13 入力部
14 出力部
21パケット処理部
22 宛先決定部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ