(57)【特許請求の範囲】
【請求項１】
アドレスのプレフィックスの２つの組により指定され、かつ優先度付けがなされた情報の中から、あるアドレスの組にマッチする情報を優先度を考慮して探索する、プレフィックスを含む複数アドレスによる連想情報探索方法であって、
１番目のプレフィックスにより１段目の２分木を構成し、１段目の２分木の各葉に１番目のプレフィックスが該当するもののみによる２番目のプレフィックスによる２段目の２分木を構成し、２段目の２分木の各葉には優先度付けされた情報を特定するものを線形リストにより保持することにより情報を管理し、これを用いてアドレスの組から情報の探索を行うことを特徴とする探索方法。
【請求項２】
２分木の各葉において、葉に属する情報の優先度の最小値を保持させることにより、探索範囲を狭めることを特徴とすることを特徴とする請求項１に記載の方法。
【請求項３】
アドレスプレフィックスの２つの組とプレフィックスでは表現されないプロトコル又はポート番号とにより指定され、かつ優先度付けがなされた情報の中から、あるアドレスの組にマッチする情報を優先度を考慮して探索する方法であって、
プロトコル又はポート番号によりハッシュテーブルを作成し、その先に前記２段階の２分木を作成することにより情報を管理し、これを用いてアドレスの組及びプロトコル又はポート番号から情報の探索を行うことを特徴とする請求項１に記載の方法。
【請求項４】
アドレスのプレフィックスの２つの組により指定され、かつ優先度付けがなされた情報の中から、あるアドレスの組にマッチする情報を優先度を考慮して探索する、プレフィックスを含む複数アドレスによる連想情報探索装置であって、
１番目のプレフィックスにより１段目の２分木を構成し、１段目の２分木の各葉に１番目のプレフィックスが該当するもののみによる２番目のプレフィックスによる２段目の２分木を構成し、２段目の２分木の各葉には優先度付けされた情報を特定するものを線形リストにより保持することにより情報を管理し、これを用いてアドレスの組から情報の探索を行うことを特徴とする探索装置。
【請求項５】
２分木の各葉において、葉に属する情報の優先度の最小値を保持させることにより、探索範囲を狭めることを特徴とする請求項４に記載の装置。
【請求項６】
アドレスプレフィックスの２つの組とプレフィックスでは表現されないプロトコル又はポート番号により指定され、かつ優先度付けがなされた情報の中から、あるアドレスの組にマッチする情報を優先度を考慮して探索する装置であって、
プロトコル又はポート番号によりハッシュテーブルを作成し、その先に前記２段階の２分木を作成することにより情報を管理し、これを用いてアドレスの組及びプロトコル又はポート番号から情報の探索を行うことを特徴とする請求項４に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネットのようなパケット交換型ネットワークにおいて、ファイヤーウォールにおけるパケットのフィルタリングやルータにおける差別化サービスのためのパケットのクラス分けやＩＰｓｅｃサービスにおける暗号アルゴリズムや鍵の選択などのように、パケットのソースアドレスとデスティネーションアドレスとからそのパケットに適用するサービスを決定するような場合における、プレフィックスを含む複数アドレスによる連想情報の探索方法及び装置に関する。
【０００２】
【従来の技術】
アドレスのプレフィックスの２つの組により指定され、かつ優先度付けがなされた情報の中から、あるアドレスの組にマッチする情報を優先度を考慮して探索する方法として、以下のような方法が挙げられる。
【０００３】
第１の方法は、線形リストによる方法である。これは、線形リスト中に優先度順に情報を並べておき、探索の際は先頭からマッチする情報を探索する方法である。
【０００４】
第２の方法は、Ｖ．Ｓｒｉｎｉｖａｓａｎらにより提案されたＧｒｉｄ−ｏｆ−Ｔｒｉｅｓと呼ばれる方法である（“Ｆａｓｔ  ａｎｄ  Ｓｃａｌａｂｌｅ  Ｌａｙｅｒ  Ｆｏｒ  Ｓｗｉｔｃｈｉｎｇ”，  ＡＣＭ  Ｓｉｇｃｏｍｍ  ’９８，  Ｓｅｐｔ．  １９９８）。この第２の方法は、２段の２分木を使用し、１段目の２分木をｌｏｎｇｅｓｔ  ｍａｔｃｈｉｎｇ（最長一致）により構成し、１段目の各葉にはその葉に該当するすべての設定が探索できる２段目の２分木を作成するものである。探索においては、１段目の２分木をｌｏｎｇｅｓｔ  ｍａｔｃｈｉｎｇにより探索し、該当する葉にある２段目の２分木を優先度を考慮して探索する。
【０００５】
【発明が解決しようとする課題】
しかしながら上述したごとき従来の探索方法によると、アドレスのプレフィックスの２つの組により特定され、かつ優先度付けがなされた大量の情報の中から、高速に探索すること及び追加削除を効率的に行うことを両立させるのは困難であった。
【０００６】
即ち、線形リストによる第１の方法は、追加や削除は容易にできるが、大量の情報を探索する際には遅くなるという問題がある。
他方、２分木を用いた方法としてＧｒｉｄ−ｏｆ−Ｔｒｉｅｓによる第２の方法があるが、この方法は、探索は高速にできるが、情報の追加削除には２分木を作成し直さなくてはならないため、追加削除に関して効率が非常に悪いという問題がある。
【０００７】
従って、本発明の目的は上記の問題を解決するため、高速な探索及び追加削除を効率的に行えることが可能なプレフィックスを含む複数アドレスによる連想探索方法及び装置を提供することにある。
【０００８】
【課題を解決するための手段】
本発明によれば、１番目のプレフィックスにより１段目の２分木を構成し、１段目の２分木の各葉に１番目のプレフィックスが該当するもののみによる２番目のプレフィックスによる２段目の２分木を構成し、２段目の２分木の各葉には優先度付けされた情報を特定するもの（ポインタなど）を線形リストにより保持することにより情報を管理し、これを用いてアドレスの組から情報の探索が行われる。
【０００９】
また、さらに２分木の各葉において、葉に属する情報の優先度の最小又は最大値を保持させることにより、探索範囲を狭めている。
【００１０】
【発明の実施の形態】
以下、本発明について実施形態を用いて説明する。
まず、表１のような情報を探索する場合を想定する。この実施形態では、３２ビットのアドレスを想定している。
【００１１】
【表１】
0003591426.tif 000002
【００１２】
この情報を本発明で用いる２段階の２分木に構成すると、図１に示すようになる。ソースアドレスにより１段目の２分木を構成し、デスティネーションアドレスにより２段目の２分木を構成している。
【００１３】
即ち、同図において、
▲１▼葉における“ｂｉｔ：ｘ”はｘ  ｂｉｔまでマッチしていることを表している。
▲２▼葉における“ｐｒｉ：ｙ”はその葉に属する情報の優先度の最小値はｙであることを表している。
▲３▼葉からの分岐は、“ｂｉｔ：”の値＋１ビット目が１である場合には右、０である場合には左へ分岐する。
【００１４】
（１）探索処理
以下、探索処理について説明する。ここでは、ソースアドレスが１０．２４０．２４０．１であり、デスティネーションアドレスが１９２．１６８．０．１の場合の探索を行う。
【００１５】
（１−１）まず始めにソースアドレスから１ｓｔ−Ｔｒｅｅを探索する。この例ではソースアドレスが１０．２４０．２４０．１なので、（Ａ）から始まり、（Ｂ）、（Ｃ）の葉を順にたどる。それぞれの葉に関して、２ｎｄ−Ｔｒｅｅがある場合にはそれを順に記憶しておく。この場合では（Ｂ）及び（Ｃ）である。
【００１６】
（１−２）次に（１−１）で記憶したものの２ｎｄ−Ｔｒｅｅを探索する。この例ではデスティネーションアドレスは１９２．１６８．０．１である。まず、２ｎｄ−Ｔｒｅｅ−１を探索する。各葉を評価する際に葉の線形リストも探索し、優先度の最小値を持ったものを記憶する。この場合では、（ａ）、（ｂ）、（ｃ）の順にたどることになる。（ａ）には線形リストがないため通過する。（ｂ）には線形リストがあるため探索を行い線形リストの中から最小の情報（ｂ−１）を保持する。この場合は、優先度２の情報が見つかる。次に（ｃ）の線形リストを探索し、優先度１の情報（ｃ−１）が見つかるので、前の情報と置き換える。これで２ｎｄ−Ｔｒｅｅ−１の探索が終了し、ここでは、優先度１（ｃ−１）の情報が見つかったことになる。
【００１７】
（１−３）次に同様にして２ｎｄ−Ｔｒｅｅ−２を探索することになる。しかし、１ｓｔ−Ｔｒｅｅの（Ｃ）の葉に属する優先度の最小値は３であることから、（１−２）で見つけた優先度１より高い情報を見つけることができないため、この２ｎｄ−Ｔｒｅｅ−２は探索を行う必要はない。
【００１８】
（１−４）以上のようにして、優先度１の情報（ｃ−１）が探索される。
【００１９】
（２）追加処理
以下、追加処理について説明する。ここでは、表２の情報を追加する場合について説明する。
【００２０】
【表２】
0003591426.tif 000003
【００２１】
（２−０）まず、情報の線形リストｉｎｆｏ−１ｉｓｔに優先度に従って追加する。
【００２２】
（２−１）情報を追加する場所を探す。まず、ソースアドレスから１ｓｔ−Ｔｒｅｅを探索する。該当する葉がない場合は作成するが、ここでは（Ｃ）があるので作成する必要はない。
【００２３】
（２−２）次に該当する２ｎｄ−Ｔｒｅｅ−２に移動し、探索するが、１９２．１６８．＊／１６の葉がないので作成する。そして図２に示すように、２ｎｄ−Ｔｒｅｅ−２に葉を追加する。他の場合の挿入も葉の挿入に関しては通常の２分木と同様の方法で行う。そして、その葉の線形リストに今回追加する情報を追加する。
【００２４】
（２−３）最後に葉の優先度の付け直しを行う。この実現方法は、以下の通りである。
『ある葉以下に属する情報の最小値を求めて、その葉のｐｒｉにセットする』を１ｓｔ−Ｔｒｅｅの先頭（Ａ）から再帰的に適用する。
【００２５】
（３）削除処理
以下、削除処理について説明する。ここでは、表３の情報を削除する場合について説明する。
【００２６】
【表３】
0003591426.tif 000004
【００２７】
（３−１）まず、該当する情報を探す。この場合では、１ｓｔ−Ｔｒｅｅを探索し（Ｂ）を発見する。次に２ｎｄ−Ｔｒｅｅを探索し、葉（ｃ）から（ｃ−１）を発見する。
【００２８】
（３−２）葉（ｃ）から（ｃ−１）を図３のように削除する。この際に葉が必要ない場合には葉も削除する。この場合には葉（ｃ）は探索に必要なくなるため削除する。同様にして、必要のない葉は削除する。場合によっては２ｎｄ−Ｔｒｅｅごと削除する場合もある。
【００２９】
（３−３）葉の優先度の付け直しを行う。この実現方法は、以下の通りである。
『ある葉以下に属する情報の最小値を求めて、その葉のｐｒｉにセットする』を１ｓｔ−Ｔｒｅｅの先頭（Ａ）から再帰的に適用する。
【００３０】
（３−４）最後に情報の線形リストｉｎｆｏ−１ｉｓｔから削除する。
【００３１】
以下ではアドレスプレフィックスの２つの組とその他にプロトコルによる指定が行われた場合について説明する。
【００３２】
この場合には、図４のようにプロトコルによるハッシュテーブルを作成し、その先に上記のような２段階の２分木を作成する。
【００３３】
検索処理に関しては、まずプロトコルによりハッシュテーブルを検索し、該当するテーブルの先にある２段階の２分木を上述と同様な方法により検索を行う。
【００３４】
追加処理に関しては、まずプロトコルによりハッシュテーブルを検索し、該当するテーブルの先に２段階の２分木があれば、その先に上述と同様な方法により追加を行い、なければ２段階の２分木を作成し、追加を行う。
【００３５】
削除処理に関しては、まずプロトコルによりハッシュテーブルを検索し、該当するテーブルの先に２段階の２分木があれば、その先から上述と同様な方法により削除を行う。
【００３６】
以上述べた実施形態は全て本発明を例示的に示すものであって限定的に示すものではなく、本発明は他の種々の変形態様及び変更態様で実施することができる。従って本発明の範囲は特許請求の範囲及びその均等範囲によってのみ規定されるものである。
【００３７】
【発明の効果】
以上詳細に説明したように本発明によれば、２段階の２分木と線形リストを併用し、２分木を再構成することなく追加削除を行えるようにすることにより、高速な探索と容易な追加削除を両立することができる。これは、大量の情報（設定）の中から２つのアドレスをキーとして探索し、かつその情報が変化するような場合に有効である。例えば、ＩＰｓｅｃを使用し、かつ一定時間ごとにＳＡ（鍵など）更新が行われる状況で、送出するパケットごとにこのＳＡの探索を行わなければならない状況などである。
【００３８】
また、ファイヤーウォールルータなどにおいて、パケットのフィルタリングをする際にポリシーを一定時間ごとに更新するような場合にも有効である。
【００３９】
このように、この発明はセキュリティなどを考慮したサーバやルータなどにおけるパケット処理の際のキーテクノロジとしての利用が見込める。
【図面の簡単な説明】
【図１】探索に用いる情報の管理方法を示した図である。
【図２】情報の追加方法を示した図である。
【図３】情報の削除方法を示した図である。
【図４】ハッシュテーブルを用いて情報管理方法を示した図である。
【図１】
0003591426.tif 000005
【図２】
0003591426.tif 000006
【図３】
0003591426.tif 000007
【図４】
0003591426.tif 000008