(57)【特許請求の範囲】
【請求項１】
ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭ(Ternary-Content-Addressable-Memory)の登録情報とを比較して当該ＩＰパケットの行き先方路を検索する手段を備えたテーブル検索装置において、
前記検索する手段は、
パトリシアツリー全体を保持するテーブル更新処理手段と、
パトリシアツリーの一部を保持する第一のテーブル検索処理手段と、
ＴＣＡＭを備えた第二のテーブル検索処理手段と
を備え、
前記テーブル更新処理手段は、
前記パトリシアツリー全体を更新情報に基づき更新する手段と、
この更新する手段により更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出する手段と、
この抽出する手段により抽出された前記ノードの集合に書込まれた登録情報を前記第一のテーブル検索処理手段に前記パトリシアツリーの一部として登録する手段と、
前記抽出する手段により抽出された前記ノードの集合以外のノードに書込まれた登録情報を前記第二のテーブル検索処理手段の前記ＴＣＡＭに登録する手段と
を備え、
前記ヘッダ情報と前記第一のテーブル検索手段に保持された前記パトリシアツリーの一部および前記第二のテーブル検索手段の前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索する手段を備えた
ことを特徴とするテーブル検索装置。
【請求項２】
ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索するテーブル検索方法において、
パトリシアツリー全体を更新情報に基づき更新し、更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出し、抽出された前記ノードの集合に書込まれた登録情報をパトリシアツリーの一部として登録し、抽出された前記ノードの集合以外のノードに書込まれた登録情報をＴＣＡＭに登録し、
前記ヘッダ情報と前記パトリシアツリーの一部および前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索する
ことを特徴とするテーブル検索方法。
【請求項３】
情報処理装置にインストールすることにより、その情報処理装置に、
ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索する機能を備えたテーブル検索装置に相応する機能を実現させるプログラムにおいて、
前記検索する機能として、
パトリシアツリー全体を保持するテーブル更新処理機能と、
パトリシアツリーの一部を保持する第一のテーブル検索処理機能と、
ＴＣＡＭを備えた第二のテーブル検索処理機能と
を実現させ、
前記テーブル更新処理機能として、
前記パトリシアツリー全体を更新情報に基づき更新する機能と、
この更新する機能により更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出する機能と、
この抽出する機能により抽出された前記ノードの集合に書込まれた登録情報を前記第一のテーブル検索処理機能に前記パトリシアツリーの一部として登録する機能と、
前記抽出する機能により抽出された前記ノードの集合以外のノードに書込まれた登録情報を前記第二のテーブル検索処理機能の前記ＴＣＡＭに登録する機能と
を実現させ、
前記ヘッダ情報と前記第一のテーブル検索機能に保持された前記パトリシアツリーの一部および前記第二のテーブル検索機能の前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索する機能を実現させる
ことを特徴とするプログラム。
【請求項４】
請求項３記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＩＰルータなどのパケット転送装置に利用するに適する。本発明はパケット転送処理を行うときに、パケットヘッダ情報を元にパケットの転送経路を決定する際に検索する経路表であるルーティング・テーブル（以下では、単にテーブルという）の検索方法に関する。
【０００２】
【従来の技術】
ＩＰルータなどのパケット転送装置では、パケットヘッダに搭載された宛先アドレスを元にテーブルを検索し、次の経路を決定する。テーブルには経路と次の方路との関係を保持している。インターネットではＣＩＤＲ(Classless Inter Domain Routing)の機構が導入されており、テーブルの経路は３２ビットのＩＰアドレスとそれに対するプレフィクス長の組み合わせで表現される。すなわち、テーブルの経路は“ＩＰアドレス／プレフィクス長”の形式で表わされる。
【０００３】
経路のうち、プレフィクス長で指定された長さ以降のビットに関してはＤｏｎ’ｔ  Ｃａｒｅである。例えば、１２９．１３１．１７５．１２９／３２は３２ビット全てのビットがＤｏｎ’ｔ  Ｃａｒｅでない経路であり、１２９．６０．８３／２４は先頭の２４ビットが有効な経路である。パケットヘッダの宛先アドレスが１２９．６０．８３．１も１２９．６０．８３．１１１も同じ経路１２９．６０．８３／２４に一致する。図６は北米バックボーンルータにおけるルーティングテーブルのプレフィクス長の分布を示す図であり、横軸にプレフィクス長をとり、縦軸にプレフィクス数をとる。これによれば、２４ビットのプレフィクス長が最も多いことがわかる。
【０００４】
テーブルはパケットヘッダの宛先アドレスをキーとして用いて検索する。テーブルを検索する際に、ＣＩＤＲでは最長一致と呼ばれるテーブル検索規則に基づく。最長一致とはキーに用いる宛先アドレスが最も長く一致するものを正解とするものである。例えば、テーブルに経路１２９．３８．１１１／２４と経路１２９．３８／１６の二つの経路がある場合に、１２９．３８．１１１．２という宛先アドレスを持つパケットが到着した場合は、経路１２９．３８．１１１／２４の方がより長い範囲で一致するので、それを正解とする。
【０００５】
このような最長一致検索を行う方法としてＰａｔｒｉｃｉａと呼ばれるデータ構造でテーブルを表現する手法が採られてきた。Ｐａｔｒｉｃｉａとはテーブルをツリー構造で表現するものである。ツリーの各ノードにはアドレスの参照ビット位置と経路とが記載されており、宛先アドレスの参照ビット位置と経路の参照ビット位置とが一致しているかどうかで経路の判定を行うものである。図７にＰａｔｒｉｃｉａの例を示す。
【０００６】
最長一致によるテーブル検索を行う別の手段として連想メモリＣＡＭ(Content-Addressable-Memory)と呼ばれる素子を使う方法がある。ＣＡＭとはアドレスをキーとしてアクセスするのではなく、各番地に記録された値をキーとしてアクセスすることができる記憶素子である。各番地には“０”と“１”のバイナリ(Binary)の値だけでなく、“Ｄｏｎ’ｔ  Ｃａｒｅ”も使えるターナリー(Ternary)のものもあり、このようなターナリーの連想メモリ(ＴＣＡＭ)を用いることで高速なテーブルの検索が可能となる。ＴＣＡＭでは複数のものが同時にキーとして入力されたものに一致する場合は、最も若い番地にいるものが選ばれる。ＴＣＡＭの構成例を図８に示す。
【０００７】
ＴＣＡＭを用いて最長一致検索を行う場合はプレフィクス長が長い順番にＴＣＡＭの若番地に格納する必要がある。最低条件としては、同じプレフィクス部分を共有する経路同士はプレフィクス長が長いものがより若い番地に格納される必要がある。
【０００８】
【発明が解決しようとする課題】
本発明が解決しようとする課題は二つからなる。パトリシアツリーの検索をハードウェアで実現する場合は、ツリーの各ノードはメモリ上に配置される。ツリーの各ノードの探索はメモリアクセスにより実現される。したがって、Ｐａｔｒｉｃｉａの検索時間はツリーの深さに依存する。テーブルの登録情報数がＮのとき、平均でｌｏｇＮ回のメモリアクセスが必要となる。したがって、テーブルの登録情報数が多くなると、メモリアクセスがボトルネックとなって高速のテーブル検索が困難となる。これが本発明が解決しようとする一番目の課題である。
【０００９】
一方で、ＴＣＡＭを用いる方法では登録情報はプレフィクス長に関してソートされていなければならない。インターネットでは経路表の更新が頻繁に行われる。このためＴＣＡＭを用いて経路表を実現する際には、経路が追加あるいは削除されるたびにＴＣＡＭの中に格納された経路を並べ替えなければならない。
【００１０】
テーブルの登録情報数がＮのとき、平均Ｏ（Ｎ）回の登録情報の移動が必要となる。図９にＴＣＡＭにおけるソートの問題の様子を示す。テーブルの登録情報数が多くなると、テーブル更新が困難となる。これが本発明が解決しようとする二番目の課題である。
【００１１】
本発明は、このような背景に行われたものであって、高速なテーブル検索および高速なテーブル更新とを実現することができるテーブル検索装置および方法およびプログラムおよび記録媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
本発明の第一の観点は、ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索する手段を備えたテーブル検索装置である。
【００１３】
ここで、本発明の特徴とするところは、前記検索する手段は、パトリシアツリー全体を保持するテーブル更新処理手段と、パトリシアツリーの一部を保持する第一のテーブル検索処理手段と、ＴＣＡＭを備えた第二のテーブル検索処理手段とを備え、前記テーブル更新処理手段は、前記パトリシアツリー全体を更新情報に基づき更新する手段と、この更新する手段により更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出する手段と、この抽出する手段により抽出された前記ノードの集合に書込まれた登録情報を前記第一のテーブル検索処理手段に前記パトリシアツリーの一部として登録する手段と、前記抽出する手段により抽出された前記ノードの集合以外のノードに書込まれた登録情報を前記第二のテーブル検索処理手段の前記ＴＣＡＭに登録する手段とを備え、前記ヘッダ情報と前記第一のテーブル検索手段に保持された前記パトリシアツリーの一部および前記第二のテーブル検索手段の前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索する手段を備えたところにある。
【００１４】
本発明の構成を図１に示す。本発明はテーブル検索処理部Ｓとテーブル更新処理部Ｒとから構成され、テーブル更新処理部Ｒは全体の登録情報を保持するソフトウェアによるパトリシアツリー全体からなる。テーブル検索処理部Ｓはハードウェアからなるパトリシアツリーの一部とＴＣＡＭから構成される。
【００１５】
本発明の要点は重複するプレフィクスを持つ登録情報はハードウェアによるパトリシアツリーの一部に、そうでない登録情報はＴＣＡＭに入れることで、ハードウェアによるパトリシアツリーのサイズを小さくする一方で、ＴＣＡＭ内のソートを不要にすることである。
【００１６】
図５は重複した登録情報を有するパトリシアツリーの例である。図５の例では、７つの登録情報からなるテーブルがある。これをパトリシアツリーで表すと１２９．６０／１６と１２９．６０．８３／２４と１２９．６０．２２５／２４のプレフィクスを持つ３つの登録情報が重複するプレフィクスを持つものであることがわかる。これらの登録情報についてはハードウェアによるパトリシアツリーに格納する。パトリシアツリーは最長一致検索を行うことができるので、このような構成をとる。また、これら３つの登録情報以外は互いに重複するプレフィクスを持たないので、ＴＣＡＭに格納する。ＴＣＡＭでは最長一致検索を行う場合はプレフィクス長でソートしなければならないが、この場合は重複するプレフィクスを互いに持たず、完全一致であればよいので、ソートをしなくてもよい。
【００１７】
以下では、本発明の作用を説明する。まず本発明でのテーブル検索処理について説明する。ＩＰパケットがルータに到着するとヘッダから宛先アドレス（ＤＡ：Ｄｅｓｔｉｎａｔｉｏｎ  ａｄｄｒｅｓｓ）が抽出され、これがテーブル検索処理部Ｓに送られる。前述のとおり、テーブル検索処理部Ｓはハードウェアによるパトリシアツリーの一部とＴＣＡＭから構成され、ハードウェアによるパトリシアツリーの一部は重複するプレフィクスが存在する登録情報から構成される。ＴＣＡＭは重複するプリフィクスが存在しない登録情報から構成される。宛先アドレスはハードウェアによるパトリシアツリーの一部およびＴＣＡＭの双方に入力され、いずれか一方がマッチする登録情報を返す。両方ともマッチしない場合は登録情報は返さない。両方ともマッチすることはない。これは排他的な登録情報がそれぞれ入っており、ハードウェアによるパトリシアツリーの一部の方では最長一致したものが返されるからである。このようにしてテーブル検索処理部Ｓはマッチした登録情報を返す（マッチしない場合はマッチしないことを返す）。
【００１８】
本発明の第二の観点は、ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索するテーブル検索方法である。
【００１９】
ここで、本発明の特徴とするところは、パトリシアツリー全体を更新情報に基づき更新し、更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出し、抽出された前記ノードの集合に書込まれた登録情報をパトリシアツリーの一部として登録し、抽出された前記ノードの集合以外のノードに書込まれた登録情報をＴＣＡＭに登録し、前記ヘッダ情報と前記パトリシアリーの一部および前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索するところにある。
【００２０】
本発明の第三の観点は、情報処理装置にインストールすることにより、その情報処理装置に、ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索する機能を備えたテーブル検索装置に相応する機能を実現させるプログラムである。
【００２１】
ここで、本発明の特徴とするところは、前記検索する機能として、パトリシアツリー全体を保持するテーブル更新処理機能と、パトリシアツリーの一部を保持する第一のテーブル検索処理機能と、ＴＣＡＭを備えた第二のテーブル検索処理機能とを実現させ、前記テーブル更新処理機能として、前記パトリシアツリー全体を更新情報に基づき更新する機能と、この更新する機能により更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出する機能と、この抽出する機能により抽出された前記ノードの集合に書込まれた登録情報を前記第一のテーブル検索処理機能に前記パトリシアツリーの一部として登録する機能と、前記抽出する機能により抽出された前記ノードの集合以外のノードに書込まれた登録情報を前記第二のテーブル検索処理機能の前記ＴＣＡＭに登録する機能とを実現させ、前記ヘッダ情報と前記第一のテーブル検索機能に保持された前記パトリシアツリーの一部および前記第二のテーブル検索機能の前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索する機能を実現させるところにある。
【００２２】
本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体である。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２３】
これにより、コンピュータ装置等の情報処理装置により、高速なテーブル検索および高速なテーブル更新を実現することができる。
【００２４】
【発明の実施の形態】
本発明実施例のテーブル検索装置を図１ないし図５を参照して説明する。図１は本実施例のテーブル検索装置の構成図である。図２はパトリシアツリーの縮小効果を説明するための図である。図３はＴＣＡＭのソート不要効果を説明するための図である。図４は本実施例のテーブル更新処理を説明するための図である。図５は本実施例のテーブル検索処理を説明するための図である。
【００２５】
本実施例は、ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索するテーブル検索処理部Ｓを備えたテーブル検索装置である。
【００２６】
ここで、本発明の特徴とするところは、図１に示すように、パトリシアツリー全体を保持するテーブル更新処理部Ｒと、パトリシアツリーの一部を保持するテーブル検索処理部Ｓ１と、ＴＣＡＭを備えたテーブル検索処理部Ｓ２とを備え、テーブル更新処理部Ｒは、前記パトリシアツリーの全体を更新情報に基づき更新し、この更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出し、この抽出された前記ノードの集合に書込まれた登録情報をテーブル検索処理部Ｓ１に前記パトリシアツリーの一部として登録し、抽出された前記ノードの集合以外のノードに書込まれた登録情報をテーブル検索処理部Ｓ２の前記ＴＣＡＭに登録し、テーブル検索処理部Ｓは、前記ヘッダ情報とテーブル検索処理部Ｓ１に保持された前記パトリシアツリーの一部およびテーブル検索処理部Ｓ２の前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索するところにある。
【００２７】
本発明実施例のテーブル検索装置は、情報処理装置としてのコンピュータ装置により実現することができる。すなわち、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、ＩＰパケットのヘッダ情報とパトリシアツリーまたはＴＣＡＭの登録情報とを比較して当該ＩＰパケットの行き先方路を検索する機能を備えたテーブル検索装置に相応する機能を実現させるプログラムであって、パトリシアツリー全体を保持するテーブル更新処理部Ｒに相応する機能と、パトリシアツリーの一部を保持するテーブル検索処理部Ｓ１に相応する機能と、ＴＣＡＭを備えたテーブル検索処理部Ｓ２に相応する機能とを実現させ、テーブル更新処理部Ｒに相応する機能として、前記パトリシアツリー全体を更新情報に基づき更新する機能と、この更新する機能により更新されたパトリシアツリー全体について重複するプレフィクスを有するノードの集合を抽出する機能と、この抽出する機能により抽出された前記ノードの集合に書込まれた登録情報をテーブル検索処理部Ｓ１に前記パトリシアツリーの一部として登録する機能と、前記抽出する機能により抽出された前記ノードの集合以外のノードに書込まれた登録情報をテーブル検索処理部Ｓ２の前記ＴＣＡＭに登録する機能とを実現させ、前記ヘッダ情報とテーブル検索処理部Ｓ１に保持された前記パトリシアツリーの一部およびテーブル検索処理部Ｓ２の前記ＴＣＡＭに登録された登録情報とをそれぞれ比較して当該ＩＰパケットの行き先方路を検索するテーブル検索処理部Ｓに相応する機能を実現させるプログラムをコンピュータ装置にインストールすることにより、そのコンピュータ装置を本実施例のテーブル検索装置に相応する装置とすることができる。
【００２８】
本実施例のプログラムは本実施例の記録媒体に記録されることにより、コンピュータ装置は、この記録媒体を用いて本実施例のプログラムをインストールすることができる。あるいは、本実施例のプログラムを保持するサーバからネットワークを介して直接コンピュータ装置に本実施例のプログラムをインストールすることもできる。
【００２９】
これにより、コンピュータ装置により、高速なテーブル検索および高速なテーブル更新を実現することができる。
【００３０】
図４を参照して本実施例のテーブル検索処理を示す。図４では宛先アドレスが１２９．６０．８３．１のパケットが到着したときに、そのアドレスがハードウェアによるパトリシアツリーの一部およびＴＣＡＭの両方に入力されている。この場合はハードウェアによるパトリシアツリーの一部でマッチする登録情報が見つかる。
【００３１】
次に本実施例での登録情報の更新処理について説明する。ある登録情報に対して重複するプレフィクスを持つ登録情報があるかないかはテーブル更新処理部Ｒのソフトウェアによるパトリシアツリー全体を検索することにより求まる。つまり、ある登録情報に対して、ツリーの先頭からその登録情報に辿り着くまでに有効ノード（テーブルに該当の登録情報があるノード）が存在すれば、それはその登録情報よりも短いプレフィクス長の登録情報が存在することを意味する。また、その登録情報から下にツリーが伸びていればそれより長いプレフィクス長の登録情報が存在することを意味する。以上のような場合は、その登録情報は他の登録情報と重複するプレフィクスを持つことがわかる。
【００３２】
テーブルにある登録情報を追加する場合は、テーブル更新処理部Ｒのソフトウェアによるパトリシアツリー全体を検索して、その登録情報と重複するプレフィクスを持つ登録情報が存在するかどうか判定する。存在しない場合はその登録情報をＴＣＡＭに追加する。存在する場合は、ハードウェアによるパトリシアツリーの一部にその登録情報を追加する。さらに、既にテーブルに存在した登録情報の中で、その登録情報の追加によって重複するプレフィクスを持つ登録情報になったものはＴＣＡＭからハードウェアによるパトリシアツリーの一部に移す。そのような登録情報はソフトウェアによるパトリシアツリールートから新たに追加した登録情報に該当するノードを通るパス上に唯一存在する有効登録情報である。
【００３３】
テーブルから登録情報を削除する場合は、テーブル更新処理部Ｒのソフトウェアによるパトリシアツリー全体を検索して、その登録情報と重複するプレフィクスを持つ登録情報が存在するかどうか判定する。存在しない場合はその登録情報をＴＣＡＭから削除する。存在する場合は、その登録情報を削除することにより、重複するプレフィクスを持つ登録情報が存在しなくなるような登録情報はハードウェアによるパトリシアツリーの一部からＴＣＡＭに移す。
【００３４】
（実施例まとめ）
ネットワークのアドレス割当てはある程度地理的条件を考慮しており、また、階層的なアドレスの払い出しを行っているので、実際のところはテーブルには重複するプレフィクスを持つ登録情報は少ない。本実施例では重複するプレフィクスを持つ登録情報のみからなるパトリシアツリーの一部でテーブル検索処理を行うので、パトリシアツリーをコンパクトにすることができ検索時間が短縮化できる。この様子を図２に示す。また、それ以外の多数の登録情報についてはＴＣＡＭで高速に検索することが可能であり、登録情報のソートも不要である。このように、本実施例により、高速なテーブル検索および高速なテーブル更新が同時に実現できる。
【００３５】
【発明の効果】
以上説明したように、本発明によれば、高速なテーブル検索および高速なテーブル更新を実現することができる。
【図面の簡単な説明】
【図１】本実施例のテーブル検索装置の構成図。
【図２】パトリシアツリーの縮小効果を説明するための図。
【図３】ＴＣＡＭのソート不要効果を説明するための図。
【図４】本実施例のテーブル更新処理を説明するための図。
【図５】本実施例のテーブル検索処理を説明するための図。
【図６】プレフィクス分布の例を示す図。
【図７】パトリシアツリーの例を示す図。
【図８】ＴＣＡＭの構成例を示す図。
【図９】ＴＣＡＭのソートの問題を示す図。
【符号の説明】
Ｒ  テーブル更新処理部
Ｓ  テーブル検索処理部
Ｓ１、Ｓ２  テーブル検索処理部
【図１】
0003660311.tif 000002
【図２】
0003660311.tif 000003
【図３】
0003660311.tif 000004
【図４】
0003660311.tif 000005
【図５】
0003660311.tif 000006
【図６】
0003660311.tif 000007
【図７】
0003660311.tif 000008
【図８】
0003660311.tif 000009
【図９】
0003660311.tif 000010