(57)【要約】【課題】プリフィックス集合に含まれるプリフィックス長の分布のバラツキを制限する。【解決手段】本発明のプリフィックスの前処理方法は、プリフィックス長をより短いプリフィックス長に縮退する処理、プリフィックス長をより長いプリフィックス長に展開する処理、縮退及び展開を行った後に得られる修正プリフィックス集合をデータベースに格納する処理を含む。ここで、縮退を行う先のプリフィックス長が、１つのプリフィックス長に格納可能なプリフィックスの最大数Ｐｌｉｍに基づいて動的に決定されること、展開を行う先のプリフィックス長が、前処理を行う前のプリフィックスが有する最大のプリフィックス長、及び１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定されること、修正プリフィックス集合に含まれるプリフィックス長の数が、元のプリフィックス集合に含まれるプリフィクス長の数より小さいことを特徴とする。【選択図】図５
2006246489.tif 000002
【特許請求の範囲】
【請求項１】
複数のオリジナル・プリフィックスを含むプリフィックス集合をデータベースに格納する方法であって、
前記プリフィックス集合に含まれる複数のオリジナル・プリフィックスのプリフィックス長をより短いプリフィックス長に縮退し、
前記プリフィックス集合に含まれる少なくとも１つのオリジナル・プリフィックスのプリフィックス長をより長いプリフィックス長に展開し、
前記縮退及び前記展開を行った後に得られる修正プリフィックス集合をデータベースに格納するものであり、
前記縮退を行う先のプリフィックス長が、予め定められた１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定され、
前記展開を行う先のプリフィックス長が、前記複数のオリジナル・プリフィックスが有する最大のプリフィックス長、及び予め定められた１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定され、
前記修正プリフィックス集合に含まれるプリフィックス長の数が、前記プリフィックス集合に含まれる前記オリジナル・プリフィックスのプリフィクス長の数より小さいことを特徴とする、データベースへのプリフィックス集合の格納方法。
【請求項２】
前記縮退は、
プリフィックス長が同じであり、かつ、共通のサブ・プリフィックスを有するプリフィックスの完全集合を生成し、
共通の転送先を有するプリフィックスの最大部分集合を、前記完全集合に含まれるプリフィックスから抽出し、
前記最大部分集合に含まれるプリフィックスを、１つの前記共通のサブ・プリフィックスに集約することにより行う、請求項１に記載の方法。
【請求項３】
前記共通のサブ・プリフィックスへの集約を、
（１）前記共通のサブ・プリフィックスと同じプリフィックス長のオリジナル・プリフィックスが前記プリフィックス集合の中に存在すること、
及び
（２）前記共通のサブ・プリフィックスと同じプリフィックスが、前記修正プリフィックス集合に含まれるプリフィックス中に既に存在しないこと、
を満足する場合に実行する、請求項２に記載の方法。
【請求項４】
前記展開は、
（ａ）前記複数のオリジナル・プリフィックスの中から最長のプリフィックス長を判定し、
（ｂ）前記最長のプリフィックス長を有するオリジナル・プリフィックスを、予め定められた記憶容量を有する１又は複数の記憶領域に格納し、
（ｃ）前記記憶容量が部分的に満たされた状態にある前記記憶領域を選択し、
（ｄ）前記最長のプリフィックス長より短いプリフィックス長のオリジナル・プリフィックスを拡張し、前記選択した記憶領域の記憶容量が満たされるように、拡張後のプリフィックスを前記選択した記憶領域に配置する、請求項１に記載の方法。
【請求項５】
前記（ａ）乃至（ｄ）の処理を、前記プリフィックス集合に含まれる全てのプリフィックス長について繰り返し行う、請求項４に記載の方法。
【請求項６】
前記選択した記憶領域に配置するオリジナル・プリフィックスは、前記最長のプリフィックス長の次に長いプリフィックス長を有するプリフィックスから選択する、請求項４に記載の方法。
【請求項７】
前記共通のサブ・プリフィックスへの集約は、特定ビットがゼロ及び１である２つのプリフィックスを、前記特定ビットは可変ビットである１つのプリフィックスに置き換えることにより行う、請求項２に記載の方法。
【請求項８】
前記オリジナル・プリフィックスの拡張は、特定ビットが可変である１つのプリフィックスを、前記特定ビットがゼロ及び１である２つのプリフィックスに置き換えることにより行う、請求項４に記載の方法。
【請求項９】
前記オリジナル・プリフィックスは、ＩＰアドレス又はその一部である、請求項１に記載の方法。
【請求項１０】
コンピュータに、複数のオリジナル・プリフィックスを含むプリフィックス集合をデータベースに格納する処理を実行させるためのコンピュータ・プログラムであって、
前記処理は、
前記プリフィックス集合に含まれる複数のオリジナル・プリフィックスのプリフィックス長をより短いプリフィックス長に縮退する処理、
前記プリフィックス集合に含まれる少なくとも１つのオリジナル・プリフィックスのプリフィックス長をより長いプリフィックス長に展開する処理、
及び、
前記縮退及び前記展開を行った後に得られる修正プリフィックス集合をデータベースに格納する処理を含むものであり、
前記縮退を行う先のプリフィックス長が、予め定められた１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定され、
前記展開を行う先のプリフィックス長が、前記複数のオリジナル・プリフィックスが有する最大のプリフィックス長、及び予め定められた１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定され、
前記修正プリフィックス集合に含まれるプリフィックス長の数が、前記プリフィックス集合に含まれる前記オリジナル・プリフィックスのプリフィクス長の数より小さいことを特徴とする、コンピュータ・プログラム。
【請求項１１】
前記縮退は、
プリフィックス長が同じであり、かつ、共通のサブ・プリフィックスを有するプリフィックスの完全集合を生成し、
共通の転送先を有するプリフィックスの最大部分集合を、前記完全集合に含まれるプリフィックスから抽出し、
前記最大部分集合に含まれるプリフィックスを、１つの前記共通のサブ・プリフィックスに集約することにより行われる、請求項１０に記載のコンピュータ・プログラム。
【請求項１２】
前記展開は、
（ａ）前記複数のオリジナル・プリフィックスの中から最長のプリフィックス長を判定し、
（ｂ）前記最長のプリフィックス長を有するオリジナル・プリフィックスを、予め定められた記憶容量を有する１又は複数の記憶領域に格納し、
（ｃ）前記記憶容量が部分的に満たされた状態にある前記記憶領域を選択し、
（ｄ）前記最長のプリフィックス長より短いプリフィックス長のオリジナル・プリフィックスを拡張し、前記選択した記憶領域の記憶容量が満たされるように、拡張後のプリフィックスを前記選択した記憶領域に配置することにより行われる、請求項１０に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰルーティングやその他のデータベースに格納されるプリフィックス長の数を削減するためにプリフィックスの事前処理を行う技術に関する。
【背景技術】
【０００２】
以下に示す文献には、有益な背景技術情報が記載されている。これらの文献は、本明細書内で参照されることによって、本開示に組み込まれる。以下では、これらの文献を角括弧つきの参照符号によって引用することとする。例えば［３］は、Srinivasan等の文献を示す。）
１．Technologies,S.、SiberCAM Ultra-18M SCT1842. 2002.
２．N.McKeown and P.Gupt、「Algorithms for Packet Classification」、IEEE Network, 2001年、15(2)、p. 24-32.
３.V. Srinivasan, G.Varghese, S.Suri, M.Waldvogel、「Fast and scalable layer four switching」、ACM SIGCOMM Computer Communication Review, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, 1998年、28(4)
４．S.Dharmapurikar, K.Prabhakar, D.Taylor、「Longest prefix matching using bloom filters」、Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications、2003年8月
５．B.Chazelle , J.Kilian, R. Rubinfeld and A. Tal、「The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables」、Proceedings, Symposium on Discrete Algorithms (SODA)、2004年
６．V.Srinivasan, G.Varghese、「Fast Address Lookups Using Controlled Prefix Expansion」、ACM Transactions on Computer Systems (TOCS)、1999年、17(1)、p.1-40.
７．V. Srinivasan, G.Varghese、「Method and Apparatus for Fast Hierarchical Address Lookup using Controlled Expansion of Prefixes」、米国特許第6,011,795号
【０００３】
ビデオ会議やリアルタイム映画配信等の広帯域を要求するアプリケーションの普及によって、インターネットに接続されるホスト（端末）数の増加とともに、インターネットを流れるトラフィックが急速に増加している。これらの広帯域アプリケーションの十分な品質を確保するために、通信回線の広帯域化が進められている。しかしながら、端末相互間におけるエンド・ツー・エンドでのパフォーマンスを向上するためには、通信回線速度の向上だけでなく、ＩＰ（Internet Protocol）パケットのフィルタリング及びルーティングを行うネットワーク・ルータの性能向上が不可欠である。
【０００４】
ネットワーク・ルータにおいて重大なボトルネックとなる処理は、ＩＰアドレス・ルックアップである。ここで、ＩＰアドレス・ルックアップとは、ＩＰパケットを宛先に向けて転送する処理を意味しており、一般にＩＰフォワーディングと呼ばれている。アドレス・ルックアップが高速化されれば、パケット・クラシフィケーション等のネットワーク・ルータで実行される他の処理の高速化も可能となる。
【０００５】
ネットワーク・ルータが行うアドレス・ルックアップとは、アドレス・プリフィックスの集合の中から、入力されたＩＰパケットのヘッダに含まれる宛先アドレスに最長一致するアドレス・プリフィックス（以下、最長プリフィックスと呼ぶ）を決定する処理である。なお、１つのアドレス・プリフィックスは、１つのインターネット・アドレス又はその前半部分であるネットワーク・アドレスに対応する。以下では、アドレス・プリフィックスを単にプリフィックスと呼ぶ。
【０００６】
上述した最長プリフィックスの決定処理は、最長プリフィックス一致判定（ＬＰＭ：Longest Prefix Matching）と呼ばれている。ＬＰＭを行うための主要な解決策は、コンテント・アドレサブル・メモリ（ＣＡＭ：Content-Addressable Memories）、ツリーベースのアルゴリズム、及びハッシュベースのアルゴリズムである。
【０００７】
なお、本明細書に開示される発明は、ツリーベースのアルゴリズム及びハッシュベースのアルゴリズムによる解決策に対して有効なものであり、これらのプリフィックス探索アルゴリズムの使用に先立ってプリフィックス集合に対して行われるプリフィックスの事前処理技術に関するものである。
【０００８】
以下では、プリフィックス事前処理技術の背景技術を説明する。通常、プリフィックスは長さによって表現される。プリフィックスの長さがＬであることは、アドレス全体のうちの上位のＬビットがプリフィックスとして有効であることを意味する。有効でない他のビットは無視される、言い換えると、"don't-care"とみなされる。本明細書では、プリフィックスを整数（例えば、インターネット・アドレス）で表現する。また、プリフィックスに含まれる有効なビットの数をプリフィックス長と呼ぶこととする。
【０００９】
プリフィックスは、インターネット・アドレス（ＩＰアドレス）又はその前半部分であるネットワーク・アドレスに対応する。例えば、"１００．１０"は、ＩＰアドレス"１００．１０．１．２"のプリフィックスである。プリフィックスのデータベースには、プリフィックス"１００．１０"についてのフォワーディング情報を含まれている。しかしながら、当該データベースは、さらに長いプリフィックス"１００．１０．１．２"に対する詳細なフォワーディング情報を有している可能性がある。したがって、ネットワーク検索エンジンに入力されたＩＰアドレスに対するネクスト・ホップを決定するためには、データベース内の全てのプリフィックスとの比較を行い、入力されたＩＰアドレスと最長一致するプリフィックスに対応するフォワーディング情報を発見しなければならない。このような、最長一致するプリフィックスの判定を、最長プリフィックス一致判定（ＬＰＭ：Longest Prefix Matching）と呼ぶ。
【００１０】
一例として、"．ｃｏｍ"を宛先に指定するパケットをポートＡに転送するルータを考える。このルータが、"ｎｅｃ．ｃｏｍ"ドメインにはポートＢを介してより容易にアクセスできるロケーションに配置されていると仮定すると、当該ルータは、"ｎｅｃ．ｃｏｍ"を宛先に指定するパケットをポートＢにルーティングする必要がある。したがって、"ｎｅｃ．ｃｏｍ"を宛先アドレスとする入力パケットはポートＢに転送され、その他の"．ｃｏｍ"ドメインを宛先アドレスとする入力パケットはポートＡに転送される。
【００１１】
単純なプリフィックス・テーブルの例を図１に示す。なお、本明細書において、プリフィックス・テーブルとは、プリフィックスが格納されるデータベースを意味する。図１のプリフィックス・テーブル１は、本明細書において実行例として参照される。プリフィックス・テーブル１において、名前列はプリフィックスの名称を示し、プリフィックス列は、名称によって識別されるプリフィックスを示し、転送情報列は、プリフィックスに含まれる宛先アドレスを有する入力パケットの転送先を示している。例えば、名前"Ｐ０"で指定されるプリフィックス"０＊"は、プリフィックス長が１ビットのプリフィックスであり、宛先アドレスの最上位ビットがゼロであるパケットは転送先Ａに転送すべきことを示している。なお、アスタリスク＊は、アドレスのプリフィックスを除く部分を示している。また、転送情報に示されている転送先Ａ乃至Ｅは、具体的にはネクスト・ホップ・アドレス又はネットワーク・ルータの出力ポートに相当する。
【００１２】
続いて以下では、ツリーベースの解決策及びハッシュベースの解決策の概要を説明する。
【００１３】
［ツリーベースの解決策］
図２は、図１に示したプリフィックス・テーブル１に対する基本的なツリー・データ構造を示している。ツリー２は、与えられたプリフィックスによって構築される。ツリー２のノード２１乃至２７は、それぞれレベルＬに対応する。レベルＬのノードでは、入力されたヘッダに含まれるアドレスのＬ番目のビットが検査され、検査対象ビットが１であるかゼロであるかによって処理が分かれる。例えば、ルート・ノード２１では、アドレスの先頭ビットが検査される。この先頭ビットがゼロであれば、入力されたアドレスはプリフィックスＰ０と一致し、他のプリフィックスとは一致しないことが判定できる。他方、先頭ビットが１であれば、最長一致するプリフィックスを判定するため、さらに検査が行われる。つまり、このことは、ＬＰＭを行うためにツリー２の走査が必要であることを意味する。このため、最長一致するプリフィックスの決定に要する遅延時間は、ツリー２の深さに依存することになる。
【００１４】
上述したツリーベースのアルゴリズムに対するいくつかの改良が提案されている［２，３］。代表的な強化策は、ツリーの各ノードにおいて、ビット単位での比較を避けて、複数ビット単位での比較を行って次のプリフィックス長にジャンプすることである。このような改良技術は、ツリーに含まれるプリフィックス長の数の削減によって、その効果をいっそう高めることができる。
【００１５】
［ハッシュベースの解決策］
ハッシュベースの解決策では、異なるプリフィックス長ごとにハッシュ・テーブルを構築する。図３は、図１のプリフィックス・テーブル１に対してハッシュベースの解決策によるＬＰＭを実行するＬＰＭ処理装置３の構成を示している。個々のプリフィックス長に対するハッシュ・テーブル３２乃至３６は、ＬＰＭの迅速な探索が可能となるよう最適化されている。図３のＬＰＭ処理装置３が備える全てのハッシュ・テーブル３２乃至３６は、同時並行的にアクセスされる。ハッシュ・テーブル３２乃至３６の出力に設けられた優先度判定部３７は、入力アドレスと最長一致するプリフィックスをハッシュ・テーブル３２乃至３７の出力から選択する。なお、マスク部３１は、入力されたヘッダからプリフィックス部分を抽出するマスク処理を行うものである。
【００１６】
上述したハッシュベースのアルゴリズムに対するいくつかの改良が提案されている［４，５］。ハッシュベースのアルゴリズムでは最悪ケースにおけるＬＰＭの探索遅延が大きくなることから、これらの参照文献は、ハッシュ・テーブルの検索性能を向上するための高度な技術を開示している。しかしながら、構成上の基本的な形式は、上述したＬＰＭ処理装置３と同様である。
【００１７】
なお、Varghese等は、上述したツリーベースの解決策及びハッシュベースの解決策に適したプリフィックス展開技術を提案している［６，７］。当該展開技術は、与えられたプリフィックスを、予め定められたプリフィックス長の集合に属するように展開するものである。例えば、３２ビットのＩＰｖ４アドレスであれば、８ビットの倍数の４種類のプリフィクス長（８、１６、２４、３２ビット）に展開する。このようなプリフィックス展開によって、与えられたプリフィックス集合は、上記のＩＰｖ４アドレスの例であれば、４つのプリフィックス・テーブルによって構成することができる。このとき、各テーブルは、８ビットのアクセスワードによってアドレス可能であって、８ビットで表される網羅的な２８個のビット・パターンをテーブル要素に有する。一般的には、アクセスワードがｎビットであれば、２ｎ個のプリフィックスをテーブル要素とするＬｍａｘ／ｎ個のプリフィックス・テーブルによって構成することができる。ここでＬｍａｘは入力アドレス長である。このような、プリフィックスの前処理を行って、プリフィックス・テーブルを構成することにより、ＬＰＭ探索時のプリフィックス・テーブルへのアクセス回数、つまりメモリアクセス回数を抑制するものである。
【特許文献１】米国特許第６０１１７９５号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１８】
一般に、ネットワーク・ルータが有するルーティング・テーブル等のプリフィックス・テーブルに格納されるプリフィックス集合には、様々なプリフィックス長を有する多数のプリフィックスが含まれる。このように、プリフィックス数が多く、かつ、プリフィックス長の数が多くプリフィックス長の分布が不均一なプリフィックス集合に対して、上述したツリーベースの解決策及びハッシュベースの解決策を適用した場合、最長一致するプリフィックスを決定するまでの遅延時間が大きくなるといったＬＰＭの処理効率が悪化を招くという課題がある。
【課題を解決するための手段】
【００１９】
本発明の第１の態様は、複数のオリジナル・プリフィックスを含むプリフィックス集合をデータベースに格納する方法である。具体的には、前記プリフィックス集合に含まれる複数のオリジナル・プリフィックスのプリフィックス長をより短いプリフィックス長に縮退する処理、前記プリフィックス集合に含まれる少なくとも１つのオリジナル・プリフィックスのプリフィックス長をより長いプリフィックス長に展開する処理、前記縮退及び前記展開を行った後に得られる修正プリフィックス集合をデータベースに格納する処理を含む。さらに、前記縮退を行う先のプリフィックス長が、予め定められた１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定されること、前記展開を行う先のプリフィックス長が、前記複数のオリジナル・プリフィックスが有する最大のプリフィックス長、及び予め定められた１つのプリフィックス長に格納可能なプリフィックスの最大数に基づいて動的に決定されること、並びに、前記修正プリフィックス集合に含まれるプリフィックス長の数が、前記プリフィックス集合に含まれる前記オリジナル・プリフィックスのプリフィクス長の数より小さいことを特徴とする。
【００２０】
本発明の第２の態様は、上述した本発明の第１の態様の方法に含まれる処理をコンピュータに実行させるためのコンピュータ・プログラムである。
【発明の効果】
【００２１】
本発明によって、１つのプリフィックス長に属するプリフィックス数を制限した状態で、プリフィックス・テーブル等のプリフィックス・データベースに格納されるプリフィックス集合に含まれるプリフィックス長の数を最小化することができる。これにより、処理後に得られる修正プリフィックス集合に含まれるプリフィックス長の分布のバラツキを制限することができるため、ツリーベースの解決策又はハッシュベースの解決策によってＬＰＭを行う際の処理効率を向上することができる。
【発明を実施するための最良の形態】
【００２２】
本発明は、与えられたプリフィックスを予め定められたプリフィックス長の集合に展開するのではなく、以下に詳述するプリフィックス処理アルゴリズムを用いてプリフィックス長を動的に決定するものである。また、本発明では、与えられたプリフィックスのプリフィックス長は展開されるだけでなく、より短いプリフィックス長に縮退される場合もある。さらに、本発明は、プリフィックス長の数が最小になるように、最適なプリフィックス長を決定するものである。
【００２３】
以下の説明では、プリフィックス集合ＳＰと整数Ｃが与えられるものとし、プリフィックス集合ＳＰに含まれる複数のプリフィックスを新たなプリフィックス集合ＳＰ´に展開又は縮退する場合を考える。本発明にかかるプリフィックス事前処理方法では、新たなプリフィックス集合ＳＰ´に含まれるプリフィックス長の数が最小化され、かつ、各プリフィックス長に属するプリフィックスの数が所定数Ｃ以下になるように、展開又は縮退が行われる。
【００２４】
本実施の形態にかかるプリフィックス事前処理方法では、欲張り法アルゴリズムと呼ばれるアルゴリズムを使用する。展開または縮退されたプリフィックスが属することになるプリフィックス長は、所定の容量を持った容器（ビン）とみなすことができる。ここで、容器とは、具体的にはメモリである。
【００２５】
本実施の形態にかかるプリフィックス事前処理方法は、２つの主要な部分を含んでいる。１つは、プリフィックスの縮退処理であり、もう１つはプリフィックスの展開処理である。
【００２６】
本実施の形態にかかるプリフィックスの縮退処理について図４のフローチャートを用いて説明する。まず始めに、プリフィックス集合ＳＰに含まれるプリフィックスが有する最大プリフィックス長Ｐｆｒｏｍを判定する処理を行う。図４のステップＳ４０１では、Ｐｆｒｏｍをプリフィックス集合ＳＰに含まれ得る最大プリフィックス長に設定して処理を開始する。次に、プリフィックス長Ｐｆｒｏｍが空、つまり、プリフィックス長Ｐｆｒｏｍを有するプリフィックスがプリフィックス集合ＳＰ中に１つも存在しない場合には、プリフィックスを有する最初のプリフィックス長に到達するまで、プリフィックス長Ｐｆｒｏｍを順次減少させていく（ステップＳ４０２乃至Ｓ４０４）。これらの処理によって決定されたプリフィックス長Ｐｆｒｏｍが、縮退処理を行なう開始元のプリフィクス長（ソース・プリフィックス長）となる。
【００２７】
続いて、プリフィックス長Ｐｆｒｏｍに属するプリフィックスが縮退されることによって属することになる縮退処理後のプリッフィクス長（ディスティネーション・プリフィックス長）Ｐｔｏを決定する処理を行う。図４のステップＳ４０５からＳ４０８までが、この処理に対応する。つまり、プリフィックス長Ｐｔｏは、Ｐｆｒｏｍより短いプリフィックス長の中で、プリフィックスを有する最長のプリフィックスに相当する。
【００２８】
次に、共通のサブ・プリフィックス長Ｐｔｏを有する２Ｐｆｒｏｍ−Ｐｔｏ個のプリフィックスからなる完全集合Ｓを、プリフィックス長Ｐｆｒｏｍを有するプリフィックスの中から選択する（ステップＳ４０９）。ここで、サブ・プリフィックスとは、あるプリフィックスの上位ビットで示されるプリフィックス長の短いプリフィックスを意味している。例えば、００００＊→Ａ、０００１＊→Ａ、００１０＊→Ａ、及び００１１＊→Ｂは、プリフィックス長が４ビットであって、長さ２ビットの共通するサブ・プリフィックス"００"を有する、４個のプリフィックスからなる完全集合である。なお、アスタリスク＊は、アドレスのプリフィックスを除く部分を示している。また、Ａ及びＢは、各プリフィックスに含まれる宛先アドレスを有するパケットの転送先を示しており、具体的にはネクスト・ホップ・アドレス又はネットワーク・ルータの出力ポートに相当する。
【００２９】
次に、完全集合Ｓから、同じ転送先（ネクスト・ホップ・アドレス又はネットワーク・ルータの出力ポート）を有するプリフィックスの最大部分集合ＳＳを抽出する（ステップＳ４１０）。このプリフィックスの部分集合ＳＳに含まれるプリフィックスは、プリフィックス長Ｐｔｏの１つのプリフィックスに縮退される。
【００３０】
ただし、上述したプリフィックスの縮退は、以下に示す２つの条件を満足する場合にのみ可能となる。第１の条件は、プリフィックス長Ｐｔｏのプリフィックスがプリフィックス集合ＳＰの中に存在すること、である。つまり、上記の縮退処理によって、新たなプリフィックス長の生成は行わないものとする。第２の条件は、共通のサブ・プリフィックスが、プリフィックス長Ｐｔｏのプリフィックス集合の中に既に存在していないこと、である。図４のステップＳ４１２の縮退ルーチンによって、これらの条件が保証される。なお、ステップＳ４１２のＰｌｉｍは、プリフィックス長Ｐｔｏに格納可能なプリフィックスの最大数（２Ｐｔｏ）を表しており、ｎｕｍ＿ｐｒｅｆｉｘ（Ｐｔｏ）は、実際にＰｔｏに含まれているプリフィックス数を表している。
【００３１】
上記の００００＊→Ａ、０００１＊→Ａ、００１０＊→Ａ、及び００１１＊→Ｂの場合は、４つのうちの３つのプリフィックスが同じ転送先"Ａ"を有している。このため、これら３つのプリフィックスは、プリフィックス長２ビットの１つのプリフィックス００＊→Ａに縮退可能である。他方、４番目のプリフィックス００１１＊→Ｂは、プリフィックス長４ビットのまま維持される。このような変換によっても、正しいＬＰＭ動作を行うことが可能である。
【００３２】
続いて、プリフィックス展開プロセスの概要について説明する。展開プロセスでは、最大プリフィックス長Ｌ１のプリフィックス長を有する全てのプリフィックスが、必要数だけ用意された複数のビンのいずれかに割り当てられる。このとき、最終的なプリフィックス配置において、プリフィックス長の異なるｎ通りのビンを設ける場合には、ｎ−１通りのビンは全て埋まっている状態となる。なお、後述する展開プロセスの実行によって、１つのビンだけは部分的に埋まった状態となることがある。
【００３３】
部分的に埋まった状態のビンが存在する場合、このビンのプリフィックス長の次に長いプリフィックス長Ｌ２のビンから、部分的に埋まった状態のビンにさらに格納可能な数に相当するプリフィックスを移動する。この処理が展開となる。展開の対象となるプリフィックスを使い果たして、プリフィックス長Ｌ２のビンが空になった場合には、Ｌ２の次に長いプリフィックス長のビンから、プリフィックスの展開を行う。この動作を繰り返すことにより、部分的に埋まった状態のビンを一杯にすることができる。
【００３４】
図５は、上述したプリフィックス展開プロセスの詳細を示すフローチャートである。ステップＳ５０１では、Ｐｔｏがプリフィックス集合ＳＰに含まれ得る最大プリフィックス長に割り当てられる。その後のステップＳ５０２乃至Ｓ５０４において、Ｐｔｏが、実際にプリフィックスが属している最大プリフィックス長になるように調整される。このように調整されたプリフィックス長Ｐｔｏが、プリフィックス展開によって他のプリフィックスが属することになる目標のプリフィックス長に相当する。
【００３５】
次に、プリフィックス展開の元となるプリフィックス長Ｐｆｒｏｍが決定される（ステップＳ５０５乃至Ｓ５０８）。これに続くステップＳ５０９では、展開元プリフィクス長Ｐｆｏｒｍから目標プリフィックス長Ｐｔｏに展開可能なプリフィックスの最大数を算出する。なお、ステップＳ５０９のＰｌｉｍは、プリフィックス長Ｐｔｏに格納可能なプリフィックスの最大数（２Ｐｔｏ）を表しており、ｎｕｍ＿ｐｒｅｆｉｘ（Ｐｔｏ）は、実際にＰｔｏに含まれているプリフィックス数を表している。
【００３６】
ステップＳ５０９で算出した最大数がゼロであれば、次の展開元プリフィックス長Ｐｆｒｏｍが決定される（ステップＳ５１０）。一方、最大数が整数、つまり展開可能なプリフィックスが存在する場合は、目標プリフィックス長Ｐｔｏに新たにプリフィックスを収容することができなくなるまで、プリフィックス長Ｐｆｒｏｍのプリフィックスをプリフィックス長Ｐｔｏに展開する（ステップＳ５１１）。
【００３７】
上述したプリフィックス縮退及びプリフィックス展開の２つのアルゴリズムは、ともに本実施の形態にかかるプリフィックス事前処理方法を構成するものである。本発明にかかるプリフィックス事前処理方法の全体の処理手続きを図６に示す。プリフィックス縮退及びプリフィックス展開のループ処理（ステップＳ６０２及びＳ６０３）は、更なる変更が不可能となるまで繰り返し行われる（ステップＳ６０４）。
【００３８】
上述したように、本発明は、前処理後のプリフィックス長ごとのプリフィックス数に制限を加えて、プリフィックスを縮退・展開している。具体的には、上述したステップＳ４１２及びステップＳ５０９において、各プリフィックス長のプリフィックスの最大数をＰｌｉｍによって規定している。つまり、本発明のプリフィックスの展開処理を行うことにより、展開処理後のプリフィックス集合に含まれるプリフィックス長の分布は、最長のプリフィックス長の近辺に集約され、かつ、各プリフィックス長に属するプリフィックス数も均一化された状態となる。つまり、本発明の展開処理によって、展開処理後のプリフィックス集合に含まれるプリフィックス長の分布のバラツキを、当初のオリジナル・プリフィックスによって構成されるプリフィックス集合におけるプリフィックス長の分布より制限することができる。このようなプリフィックス長の分布のバラツキの抑制により、ハッシュベース及びツリーベースの解決策による最長一致探索の処理速度の高速化が可能となる。
【００３９】
また、上述した文献［６、７］に開示されているプリフィックス長の前処理方法では、プリフィックス長の前処理後の各プリフィックス長に属するプリフィックス数が制御されていないため、予め用意しておくプリフィックス・テーブルのサイズは最大サイズに相当するものを用意しておく必要がある。具体的には、一括して最長一致探索を行うプリフィックス長の範囲（アクセスワード）がｎビットであれば、２ｎ個の網羅的なエントリを格納可能なテーブルサイズを必要とする。これに対して本発明は、各プリフィックス長に属するプリフィックスの最大数を規定している。このため、プリフィックス・テーブルのサイズは、最大数に相当するプリフィックスを格納可能なサイズとすればよく、プリフィックス・テーブルを保持するためのメモリを効率的に使用することができる。
【００４０】
さらに、本発明では、上述した手順に従ってプリフィックスの縮退を行うことにより、縮退処理後のプリフィックス集合に含まれるプリフィックス数を削減することができる。
【００４１】
続いて以下では、プリフィックス・テーブルの更新について説明する。通常、ネットワーク・ルータでは、プリフィックス・テーブルの更新が行われる。プリフィックス・テーブルの更新には、新たなプリフィックスの追加、既存のプリフィックスの削除、及び既存のプリフィックスの転送情報（ネクスト・ホップ・アドレス、出力ポート等）の変更がある。上述した本実施の形態にかかるプリフィックスの事前処理を実行することにより、プリフィックス・テーブルの更新が多少複雑となる。プリフィックスの事前処理によって、処理前のプリフィックス長とは異なるプリフィックス長に展開又は縮退が行われているためである。
【００４２】
いま、プリフィックスの事前処理を実行した後のプリフィックス長の集合をＳ＝｛ｐｌ１、ｐｌ２、・・・、ｐｌＬ｝とする。また、プリフィックスの事前処理を行う前に存在するプリフィックスのことを、オリジナル・プリフィックスと呼んで区別することとする。
【００４３】
プリフィックス・テーブルの更新を容易にするため、本実施の形態では、オリジナル・プリフィックスのプリフィックス長を識別可能なタグを、プリフィックスの事前処理を行った後のプリフィックスに付加する。このタグは、プリフィックス・テーブルがハードウェア実装の場合にはハードウェアに付加されても良いし、ソフトウェア実装の場合は、ソフトウェアのデータ構造に付加されても良い。
【００４４】
プリフィックスの追加、削除及び変更のそれぞれの場合について、プリフィックス・テーブルの更新方法の概要を示す。
【００４５】
［プリフィックス追加］
プリフィックス長Ｌの新たなプリフィックスを追加する場合、当該プリフィックスに対して図４及び図５に示したアルゴリズムを実行し、プリフィックスの縮退又は展開を行う。なお、追加するプリフィックスが既存のプリフィックスＰ´と衝突する場合には、上述したオリジナル・プリフィックスのプリフィックス長を示すタグを参照し、Ｐ´のオリジナル・プリフィックス長がＬ以下である場合にのみ、Ｐ´を上書きする。
【００４６】
［プリフィックス削除］
プリフィックス長Ｌのオリジナル・プリフィックスＰをプリフィックス・テーブルから削除する場合、集合Ｓに含まれる全てのプリフィックス長を調査する。オリジナル・プリフィックスＰは、元のプリフィクス長と異なるプリフィックス長に縮退又は展開されている可能性があるためである。上記の調査によって削除対象のプリフィックスＰと一致し、かつ、オリジナル・プリフィックス長を示すタグが長さＬと一致するプリフィックスが発見された場合に、発見されたプリフィックスを削除する。
【００４７】
［プリフィックス変更］
プリフィックス長Ｌのオリジナル・プリフィックスＰの転送情報を変更する場合、集合Ｓに含まれる全てのプリフィックス長を調査する。プリフィックス削除の場合と同様に、オリジナル・プリフィックスＰは、元のプリフィクス長と異なるプリフィックス長に縮退又は展開されている可能性があるためである。上記の調査によって変更対象のプリフィックスＰと一致し、かつ、オリジナル・プリフィックス長を示すタグが長さＬと一致するプリフィックスが発見された場合に、発見されたプリフィックスの転送情報を変更する。
【００４８】
なお、上述した本実施の形態にかかるプリフィックスの事前処理方法は、コンピュータ・システムを用いて実現することが可能である。したがって、本発明にかかるプリフィックスの事前処理方法をコンピュータに実行させるコンピュータ・プログラムも本発明の範囲に含まれるものである。
【００４９】
さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【００５０】
【図１】プリフィックス・テーブルの一例を示す図である。
【図２】ツリーベースのＬＰＭを説明するための図である。
【図３】ハッシュベースのＬＰＭを説明するための図である。
【図４】本発明にかかるプリフィックス縮退処理を示すフローチャートである。
【図５】本発明にかかるプリフィックス展開処理を示すフローチャートである。
【図６】本発明にかかるプリフィックス事前処理を示すフローチャートである。
【符号の説明】
【００５１】
１  プリフィックス・テーブル
２  ツリー
３  ＬＰＭ処理装置
３２乃至３６  ハッシュ・テーブル
【図１】
2006246489.tif 000003
【図２】
2006246489.tif 000004
【図３】
2006246489.tif 000005
【図４】
2006246489.tif 000006
【図５】
2006246489.tif 000007
【図６】
2006246489.tif 000008