(57)【要約】【課題】  シンプルな並列処理によって実装が容易でかつ高速なネットワークアドレス参照を実現する。【解決手段】  本発明は、それぞれに異なるプレフィックス長L（ビット）が割り当てられた複数のプレフィックス参照手段が、各プレフィックス参照手段毎に、該プレフィックス長Lに従って、アドレスにサブネットマスクをかけ、先頭のLビットのみを残し、残りを削除し、その値をYとし、該Yに対してハッシュ関数を適用し、プレフィックスメモリのハッシュテーブルのインデックスを取得し、該インデックスに対応したバケットの値を参照し、値が存在すればマッチしたとし、プレフィックスの値Lとマッチしたパケットの値Xの組み{L, X}を出力する。【選択図】  図２
2012216959.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークアドレスを参照するネットワークアドレス参照装置であって、
参照対象のアドレスを入力するアドレス入力手段と、
プレフィックスとデータの対応付けを入力するプレフィックスDB入力手段と、
アドレスとプレフィックスの対応付けを記録保持するデータベースを管理するアドレスープレフィックスDB管理手段と、
アドレスの参照を並列処理する並列処理手段と、
前記並列処理手段より得られたアドレスに対応するデータを出力する参照結果出力手段と、を有し、
前記並列処理手段は、
前記アドレス入力手段により入力されたアドレスを格納するキャッシュと、
前記プレフィックスDB入力手段から取得したアドレスとプレフィックスの対応表をハッシュテーブルとして保持する複数のプレフィックスメモリと、
前記入力されたアドレスに基づいて、前記プレフィックスメモリを参照し、処理結果を出力する処理を並列で行う複数のプレフィックス参照手段と、
前記複数のプレフィックス参照手段から出力されたプレフィックスのうち、最も大きなプレフィックスを出力する統合手段と、
を含むことを特徴とするネットワークアドレス参照装置。
【請求項２】
前記複数のプレフィックス参照手段は、
それぞれ異なるプレフィックス長L（ビット）が割り当てられ、該プレフィックス長L
に従って、前記アドレスにサブネットマスクをかけ、先頭のLビットのみを残し、残りを削除し、その値をYとし、該Yに対してハッシュ関数を適用し、前記プレフィックスメモリの前記ハッシュテーブルのインデックスを取得し、該インデックスに対応したバケットの値を参照し、値が存在すればマッチしたとし、プレフィックスの値Lとマッチしたバケットの値Xの組み{L, X}を前記統合手段に出力する手段を含む
請求項１記載のネットワークアドレス参照装置。
【請求項３】
前記アドレス入力手段により前記アドレスを受信すると、各々の前記プレフィックス参照手段に同時に該アドレスを送信する処理分配手段を含む
請求項１または２記載のネットワークアドレス参照装置。
【請求項４】
前記アドレス−プレフィックスＤＢ管理手段は、
新たなプレフィックスの情報を取得すると、プレフィックスとデータの組みをハッシュキーとハッシュ値に変換し、該当するプレフィックス長のプレフィックスメモリのハッシュテーブルに格納する手段を含む
請求項１記載のネットワークアドレス参照装置。
【請求項５】
ネットワークアドレスを参照するネットワークアドレス参照方法であって、
アドレスの参照を並列処理する複数の並列処理手段が、
入力されたアドレスをキャッシュに格納し、
前記入力されたアドレスに基づいて、アドレスとプレフィックスの対応表をハッシュテーブルとして保持する複数のプレフィックスメモリを参照し、プレフィックスを出力する並列処理ステップと、
統合手段が、
前記並列処理ステップの複数の処理結果である複数のプレフィックスのうち、最も大きなプレフィックスを出力する統合ステップ、
を行うことを特徴とするネットワークアドレス参照方法。
【請求項６】
前記並列処理ステップにおいて、
それぞれに異なるプレフィックス長L（ビット）が割り当てられた前記並列処理手段の複数のプレフィックス参照手段が、各プレフィックス参照手段毎に、
該プレフィックス長Lに従って、前記アドレスにサブネットマスクをかけ、先頭のLビットのみを残し、残りを削除し、その値をYとし、該Yに対してハッシュ関数を適用し、前記プレフィックスメモリの前記ハッシュテーブルのインデックスを取得し、該インデックスに対応したバケットの値を参照し、値が存在すればマッチしたとし、プレフィックスの値Lとマッチしたバケットの値Xの組み{L, X}を出力する請求項５記載のネットワークアドレス参照方法。
【請求項７】
参照対象のアドレスが入力されると、前記複数のプレフィックス参照手段に同時に該アドレスを送信する
請求項６記載のネットワークアドレス参照方法。
【請求項８】
前記アドレス−プレフィックスＤＢ管理手段が、
新たなプレフィックスの情報を取得すると、プレフィックスとデータの組みをハッシュキーとハッシュ値に変換し、該当するプレフィックス長のプレフィックスメモリのハッシュテーブルに格納する
請求項６記載のネットワークアドレス参照方法。
【請求項９】
請求項１乃至４のいずれか１項に記載のネットワークアドレス参照装置を構成する各手段としてコンピュータを機能させるためのネットワークアドレス参照プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークアドレス参照方法及び装置及びプログラムに係り、特に、ルータにおけるルーティングテーブル参照など、高速にネットワークアドレスを参照するためのネットワークアドレス参照方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
通信ネットワークにおいて、ネットワークアドレス参照は様々な場面で利用される重要な技術である。ここで「ネットワークアドレス」とは、例えばIPネットワークにおけるIPv4アドレスやIPv6アドレスなどである。以下にネットワークアドレス参照の例を述べる。
【０００３】
ルータで構成されるパケットネットワークにおいて経路制御を実現するためには、受信したパケットに記載された宛先アドレスとルータ内部で保持する経路表を参照し、該パケットを転送するべき適切なネットワークインタフェースを参照し、当該インタフェースにパケットを転送することによって次ホップのルータへの転送が実現される。
【０００４】
すなわち、参照の対象となるネットワークアドレスに対応するインタフェース名を経路制御アルゴリズムによって管理された経路表を参照することで高速に取得する。
【０００５】
その他のネットワークアドレス参照の例として，ネットワークアドレスに対する評判システムや位置サービスシステムがある。いずれもネットワークアドレスに対して予め用意された対応表をもとにアドレスに紐づくデータを出力するシステムである。前者はネットワークアドレスの評判（過去の振る舞いが良いか悪いかなど）をデータとし、後者はネットワークアドレスが物理的に存在する地理情報、例えば緯度経度や国名、さらに詳細な地名などである。
【０００６】
上記のようなネットワークアドレス参照において用いられる対応表は、ネットワークアドレスの一部、すなわちプレフィックス表記を用いて管理されることが一般的である。プレフィックスは、例えばIPv4アドレスの場合、"129.60.0.0/16"などのように表記し、これはアドレス129.60.0.0〜129.60.255.255 の65536個のアドレスを表現する。"/16 "における"16"はプレフィックス長であり、32ビットのIPv4アドレスの内、先頭の16ビットがプレフィックスとなる。IPv4アドレスの場合プレフィックス長は0から32までの値を取る。
【０００７】
ネットワークアドレス参照を実現する従来技術として、Radix Trie と呼ばれるデータ構造が提案されている（例えば、非特許文献１参照）。しかしながら非特許文献２で指摘されているように、Radix Trie は参照対象のアドレス長が大きい場合、例えば128ビットのアドレス長を持つIPv6アドレスの場合に性能が悪くなることが知られている。
【０００８】
非特許文献２では、プレフィックス長の大小によって構成された複数のハッシュ表に対して二分探索を適用することにより、アドレス長Wに対して計算コストが log2(W)のオーダーとなるアルゴリズムを提案している。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Donald R. Morrison, "PATRICIA--Practical Algorithm To Retrieve Information Coded in Alphanumeric,"Journal of the ACM (JACM), Volume 15, Issue 4, Pages: 514 - 534,October 1968.  portal.acm.org/citation.cfm?id=321479.321481
【非特許文献２】Marcel Waldvogel, George Varghese, Jon Turner, Bernhard Plattner"Scalable High Speed IP Routing Lookups,"ACM SIGCOMM Computer Communication Review  archive Volume 27, Issue 4, Pages: 25 - 36, October 1997.http://www.sigcomm.org/sigcomm97/papers/p182.pdf
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記の非特許文献２の手法は効率的であるものの、動作が複雑であるため実装が難しいという問題があった。
【００１１】
本発明は、上記の点に鑑みなされたもので、きわめてシンプルな並列処理によって実装が容易でかつ高速なネットワークアドレス参照を実現すること可能なネットワークアドレス参照方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するため、本発明は、ネットワークアドレスを参照するネットワークアドレス参照装置であって、
参照対象のアドレスを入力するアドレス入力手段と、
プレフィックスとデータの対応付けを入力するプレフィックスDB入力手段と、
アドレスとプレフィックスの対応付けを記録保持するデータベースを管理するアドレスープレフィックスDB管理手段と、
アドレスの参照を並列処理する並列処理手段と、
前記並列処理手段より得られたアドレスに対応するデータを出力する参照結果出力手段と、を有し、
前記並列処理手段は、
前記アドレス入力手段により入力されたアドレスを格納するキャッシュと、
前記プレフィックスDB入力手段から取得したアドレスとプレフィックスの対応表をハッシュテーブルとして保持する複数のプレフィックスメモリと、
前記入力されたアドレスに基づいて、前記プレフィックスメモリを参照して得られた処理結果を出力する処理を並列で行う複数のプレフィックス参照手段と、
前記複数のプレフィックス参照手段から出力されたプレフィックスのうち、最も大きなプレフィックスを出力する統合手段と、を含む。
【発明の効果】
【００１３】
上述のように本発明によれば、実装が容易でかつ高速なネットワークアドレス参照が実現されるようになる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態におけるネットワークアドレス参照装置の構成図である。
【図２】本発明の一実施の形態における並列処理部の構成図である。
【図３】本発明の一実施の形態における並列演算部の具体的な処理の例である。
【図４】本発明の一実施の形態における並列処理部の動作のフローチャートである。
【図５】本発明の一実施の形態におけるプレフィックス参照部の動作のフローチャートである。
【発明を実施するための形態】
【００１５】
以下図面と共に、本発明の実施の形態を説明する。
【００１６】
図１は、本発明の一実施の形態におけるネットワークアドレス参照装置の構成図である。
【００１７】
同図に示す、ネットワークアドレス参照装置は、参照対象のアドレスを入力するアドレス入力部１０、プレフィックスとデータの対応付けを入力するプレフィックスDB入力部２０、アドレスとプレフィックスの対応付けを記録保持するデータベースを管理するアドレスープレフィックスDB管理部３０、アドレスの参照を並列処理する並列処理部１００、前記並列処理部１００より得られたアドレスに対応するデータ出力する参照結果出力部４０からなる。
【００１８】
本発明のネットワークアドレス参照装置は、アドレスが入力されると並列処理部１００にてアドレス参照を実施し、その結果を参照結果出力部４０に出力する。参照するアドレスとプレフィックスに関する情報はアドレス−プレフィックスDB管理部３０によって管理される。アドレス−プレフィックＤＢ管理部３０は、プレフィックスとデータの組みの挿入と削除を実現する機能を備えている。挿入と削除の命令はプレフィックスDB入力部２０を通じて行われる。
【００１９】
図２は、本発明の一実施の形態における並列処理部の構成を示す。
【００２０】
並列処理部１００は、処理分配部１１０、キャッシュ１２０、並列演算部１３０、処理統合部１４０を有する。
【００２１】
並列処理部１００は、アドレス入力部１０から入力されたアドレスを処理分配部１１０で取得する。
【００２２】
処理分配部１１０は、入力アドレスを並列演算部１３０およびキャッシュ１２０の両方に同時に出力する。
【００２３】
処理統合部１４０は、キャッシュ１２０からデータが得られた場合はそのデータを出力し、キャッシュから得られない場合は並列演算部１３０から出力された1つ以上の出力を参照し、最もプレフィックス長が大きかったものを出力する。
【００２４】
並列演算部１３０は、アドレスとプレフィックスの参照を並列に行うプレフィックス参照部１３１を複数有する。前記各々のプレフィックス参照部１３１が用いるアドレスとプレフィックスの対応表は各々のプレフィックス参照部１３１がアクセス及び管理可能なプレフィックスメモリ１３２上にハッシュテーブルの形式で記録される。
【００２５】
ここで各々のプレフィックス参照部１３１は、それぞれ異なるプレフィックス長L（ビット）が割り当てられる。但し、プレフィックス長に対応するデータ量が多い場合は該当するプレフィックス長は複数のプレフィックス参照部１３１によって管理することにより、各々のプレフィックス参照部１３１が担当するプレフィックス数の上限を抑える。
【００２６】
並列処理部１００は参照対象のアドレスが入力されると、各々のプレフィックス参照部１３１に同時にそのアドレスを送信する。各々のプレフィックス参照部１３１は並列にアドレス参照を実行し、その結果を処理統合部１４０に出力する。
【００２７】
各々のプレフィックス参照部１３１は、自身に割り当てられたプレフィックス長Lにしたがって、受信アドレスにサブネットマスクをかけ、W−Lビット右にシフトする。ここでWはアドレスのビット長である。すなわち、先頭のLビットのみを残し、残りを削除する演算を行う。その値をYとする。
【００２８】
次に、プレフィックス参照部１３１は、上記のYに対してハッシュ関数を適用し、プレフィックスメモリ１３２上のハッシュテーブルのインデックスを得る。インデックスに対応したバケットの値を参照し、値が存在すればマッチしたとし、プレフィックスの値Lとマッチしたバケットの値Xの組み{L, X}を出力する。 
アドレスープレフィックスDB管理部３０は、プレフィックスＤＢ入力部２０から新たなプレフィックスの情報を得た後、該当するプレフィックス長のプレフィックス参照部１３１が管理するハッシュテーブルにプレフィックスとデータの組みをハッシュキーとハッシュ値に変換し、ハッシュテーブルに格納する。このとき該当するプレフィックス長が複数のプレフィックス参照部１３１に割り当てられている場合は、ランダムにプレフィックス参照部１３１を選択するか、あるいは個々のプレフィックスメモリ１３２上のハッシュテーブルに登録されているプレフィックスのエントリ数に応じて、少ないプレフィックス参照部１３１を選択する。その他、任意の方法によって割り当てを行うことが可能である。
【００２９】
いずれの割り当て方法においても同一のプレフィックスは異なるプレフィックス参照部１３１で重複しないように割り当てが行われる。同様に、あるプレフィックスを削除する場合には該当するプレフィックスメモリ１３２上のハッシュテーブルから該プレフィックスのエントリを削除する。
【００３０】
キャッシュ１２０は、任意のサイズのエントリをもち、エントリ数がサイズを超えたら古いものから順に、あるいはランダムな方法でエントリを削除する。
【００３１】
以下に、並列処理部１００の処理について説明する。
【００３２】
並列演算部１３０のプレフィックス参照部１３１は、並列に動作する構成になっており、図３に示すように、各々に異なるプレフィックス長が割り当てられる。但し、沢山のプレフィックスが存在するプレフィックス長については複数のプレフィックス参照部１３１が割り当てられる。
【００３３】
図４は、本発明の一実施の形態における並列処理部の動作のフローチャートである。
【００３４】
ステップ１０１）  並列処理部１００は、アドレス入力部１０からあるアドレスXに対する参照要求を受信する。
【００３５】
ステップ１０２）  並列処理部１００は、キャッシュ１２０に該当するアドレスXが存在するかをチェックする。このキャッシュ１２０は比較的小さいメモリで構成されており、ハッシュテーブルなどを用いることによって高速な参照が可能である。あるいはTCAM(Ternary content Addressable Memory)のようなハードウェアを使っても構わない。
アドレスがキャッシュ１２０に存在した場合はステップ１０８に移行する。そうでない場合はステップ１０３の並列処理に移行する。
【００３６】
ステップ１０３）  並列演算部１３０では各々のプレフィックス参照部１３１が同時並列にアドレスの参照を行い、結果を処理統合部１４０へ出力する。
【００３７】
ステップ１０４）  処理統合部１４０は出力を監視し、少なくとも１つのプレフィックス参照部１３１より出力が存在した場合には、ステップ１０６に移行し、１つも出力がない場合にはステップ１０５に移行する。
【００３８】
ステップ１０５）  ステップ１０４において出力がない場合にはNull（該当なし）を出力して処理を終了する。
【００３９】
ステップ１０６）  処理統合部１４０は、プレフィックス参照部１３１から出力されたプレフィックスのうち、最も大きなプレフィックスを採用して参照結果出力部４０に出力する。
【００４０】
ステップ１０７）  さらに、処理統合部１４０は、出力データをキャッシュ１２０に登録して処理を終了する。但し、キャッシュ１２０が実際に更新されるか否かはキャッシュ１２０が別途判断する。
【００４１】
ステップ１０８）  ステップ１０２においてアドレスXがキャッシュ１２０になかった場合には、そのアドレスに対応するデータを出力して終了する。
【００４２】
図５は、本発明の一実施の形態におけるプレフィックス参照部の動作のフローチャートである。並列演算部１３０での具体的な処理の様子を図３に図示する。図３の例ではIPv4アドレス"192.168.42.33" に対する参照が４つのプレフィックス参照部１３１によって処理される場合を示している。個々のプレフィックス参照部１３１は上から順に24, 24, 16, 8 ビットのプレフィックス長を有する。すなわち、24ビットのプレフィックスは2つのプレフィックス参照部１３１１，１３１２に重複なく割り当てられている。なお、上記のプレフィックス長は固定ではなく、32ビットのアドレス体系であれば、32（1〜32）通りのプレフィックス長をとり得る。
【００４３】
ステップ２０１）  並列演算部１３０は、アドレスXに関する参照要求を受信する。ここでは、アドレス"192.168.42.33" に対する参照要求を取得する。"192.168.42.33 "は2進数表記で"11000000101010000010101000100001"である。
【００４４】
ステップ２０２）  受信したアドレスXにＬビットのマスクをかけ、残りの部分をＹとする。図３の例では、24ビットを担当する一番上のプレフィックス参照部１３１１が、まずネットマスク"11111111111111111111111100000000"を前記アドレスに対して掛け（すなわち両者の論理積をとる）、さらに32-24ビット=8ビット右にシフトすることによって"110000001010100000101010 "を得る。
【００４５】
ステップ２０３）  Ｙにハッシュ関数H()を適用する。
【００４６】
図３の例では、プレフィックス参照部１３１１は、この値に対して"00 "〜"03 "の４つの値を返すハッシュ関数を適用する。
【００４７】
ステップ２０４）H(Y)とプレフィックスメモリインデックス（ハッシュテーブル）１３２を比較してマッチするか判定し、マッチする場合はステップ２０５に移行し、マッチしない場合は処理を終了する。ここでは、ハッシュ関数を適用した結果"02 "を得たものとする。プレフィックスメモリ１３２（ハッシュテーブル）のインデックス"02 " に対応するバケットを参照し、"567 "という値が存在することがわかったので、マッチしたものとし、プレフィックス長 24 と値 567 の組み{24, 567} を処理統合部１４０に出力する。
【００４８】
他のプレフィックス参照部１３１1〜１３１４の動作も同様である。
【００４９】
この例の場合、1番目の24ビットのプレフィックス長を端とするプレフィックス参照部１３１１と8ビットのプレフィクス長を担当するプレフィックス参照部１３１４の二つから出力が行われるが、最終的によりプレフィックス長の大きい24の方が採用され、アドレス"192.168.42.33 "に対してはデータ"567"が返される。
【００５０】
なお、上記のネットワークアドレス参照装置の構成要素の各動作をプログラムとして構築し、ネットワークアドレス参照装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５２】
１０  アドレス入力部
２０  プレフィックスＤＢ入力部
３０  アドレス−プレフィックスＤＢ管理部
４０  参照結果出力部
１００  並列処理部
１１０  処理分配部
１２０  キャッシュ
１３０  並列演算部
１３１  プレフィックス参照部
１３２  プレフィックスメモリ
１４０  処理統合部
【図１】
2012216959.tif 000003
【図２】
2012216959.tif 000004
【図３】
2012216959.tif 000005
【図４】
2012216959.tif 000006
【図５】
2012216959.tif 000007