(57)【特許請求の範囲】
【請求項１】
全エントリに対して最長一致検索を行うためのフォワーディングテーブルと、
全エントリの一部のエントリに対して最長一致検索を行うためのキャッシュテーブルとを備え、
前記フォワーディングテーブルにおいてエントリを前記キャッシュテーブルに入れるときには、そのエントリを親とする全エントリを、また前記キャッシュテーブルからエントリを出すときには、そのエントリの親となる全エントリを、当該エントリの使用状況の評価値に対する閾値および削除あるいは移動されるエントリの領域対応の優先度に応じて選択することを特徴とするルータにおけるキャッシュテーブル管理装置。
【請求項２】
全エントリに対して最長一致検索を行うためのフォワーディングテーブルあるいは全エントリの一部のエントリに対して最長一致検索を行うためのキャッシュテーブル内に仮想的な複数の領域を設定する手段と、
該領域内では、それぞれ固有に、削除あるいは移動対象を決めるためのエントリ群の使用状況の評価値と、少なくとも削除対象に選択される可否を決める閾値と選択された場合に実際に削除あるいは移動されるエントリの該領域に応じて決まる優先度の一つを持つ手段と、
該閾値および優先度に応じて入れ替え対象のエントリ群を選択する手段とを持つことを特徴とするルータにおけるキャッシュテーブル管理装置。
【請求項３】
各エントリあるいは各エントリ群と各仮想的な領域を関連付ける手段、または各エントリあるいは各エントリ群にそれぞれ優先度を関連付ける手段、または各エントリあるいは各エントリ群にそれぞれ閾値を関連付ける手段の内の少なくとも一つの手段を備えたことを特徴とする請求項２に記載のルータにおけるキャッシュテーブル管理装置。
【請求項４】
特定の時間区間において、エントリ群を構成する各エントリが持つ使用状況の評価値に対して、該使用状況を全てのエントリに対してあるいは一部のエントリに対して組み合わせた値あるいは統計値を各エントリ群の使用状況の評価値として用いる手段を備えたことを特徴とする請求項２に記載のルータにおけるキャッシュテーブル管理装置。
【請求項５】
プレフィクスビット列およびプレフィックス長から成るアドレスの集合を示す情報と、このアドレスの集合に対するパケットの出方路を示す情報と、優先度情報との組が登録されたエントリを複数有し最長一致検索されるフォワーディングテーブルと、
入れ替えるべきエントリを親とする前記フォワーディングテーブルの全エントリが書き込まれ、またエントリが削除・移動されるときには、その親も削除・移動されるキャッシュテーブルと、
前記フォワーディングテーブルの全エントリについて、その内容に加えてヒット情報が登録され、前記フォワーディングテーブルまたは前記キャッシュテーブルがヒットしたときにそのエントリの内容が更新されるヒット状況データベースと、
パケットが入力されるとそのパケットヘッダから宛先ネットワークアドレスを取り出し、このアドレスをキーにして前記キャッシュテーブルまたは前記フォワーディングテーブルを検索し、得られた出方路にパケットを転送するパケット処理回路と、
前記キャッシュテーブルに登録されている全エントリの前記優先度情報を含み、前記エントリ群入れ替えを行うときには、該優先度情報と前記ヒット状況データベースからの情報とを考慮して入れ替えるべきエントリ群を選択するエントリ選択装置と備えたことを特徴とするルータにおけるキャッシュテーブル管理装置。
【請求項６】
前記エントリ選択装置は、
前記ヒット状況データベースからエントリ群全ての情報を受け取り、この全エントリから、エントリ固有の優先度である領域，エントリ使用状況の評価値および閾値の代表値を決めるエントリ群代表値回路と、
前記キャッシュテーブルに既に存在するエントリ群に関して、そのエントリ群とその代表値を組にして表に持っており、その表の各エントリ群の代表値と、前記エントリ群代表値回路から送られてくる代表値とを比較して、キャッシュテーブルに既に存在するエントリ群がどのような優先順位にあるかを送出する前記領域，エントリ使用状況の評価値および閾値対応の比較回路と、
該比較回路から送られてきた優先順位データを基にエントリの最終的な入替え順位を決定する調停回路と、
前記キャッシュテーブルの空き状況を管理しており、当該エントリ群を追加することのできる空きがあるかどうかを調べ、空きが無い場合には、前記調停回路が決定した順位の最も低いエントリが所属するエントリ群から前記キャッシュテーブルのエントリを消去して十分な空きを作り、また削除したエントリ群を前記表からの削除のために前記比較回路に送るエントリ決定送付回路とから成ることを特徴とする請求項５に記載のルータにおけるキャッシュテーブル管理装置。
【請求項７】
前記エントリ使用状況の評価値として、ヒット回数またはヒット時刻またはその両者を採用することを特徴とする請求項２，請求項４または請求項６に記載のルータにおけるキャッシュテーブル管理装置。
【請求項８】
前記各代表値は、閾値と領域についてはエントリ中の最も高い値、ヒット回数は平均値、ヒット時刻は最近のものとすることを特徴とする請求項７に記載のルータにおけるキャッシュテーブル管理装置。
【請求項９】
前記調停回路は、０〜１の乱数を発生し、その乱数を２等分して、１／２づつをヒット回数とヒット時刻に割り当て、割り当てられた属性の順位を最終的な順位とすることを特徴とする請求項７または請求項８に記載のルータにおけるキャッシュテーブル管理装置。
【請求項１０】
前記エントリの優先度を受信パケットから得られる情報に応じて設定する手段を設けたことを特徴とする請求項２ないし請求項９のいずれかに記載のルータにおけるキャッシュテーブル管理装置。
【請求項１１】
前記フォワーディングテーブル内の優先度は、ポリシーサーバにより変更可能としたことを特徴とする請求項５ないし請求項１０に記載のルータにおけるキャッシュテーブル管理装置。
【請求項１２】
プレフィクスビット列およびプレフィックス長から成るアドレスの集合を示す情報と、このアドレスの集合に対するパケットの出方路を示す情報と、優先度情報との組が登録されたエントリを複数有し最長一致検索されるフォワーディングテーブルと、
入れ替えるべきエントリを親とする前記フォワーディングテーブルの全エントリが書き込まれ、またエントリが削除・移動されるときには、その親も削除・移動されるキャッシュテーブルと、
前記フォワーディングテーブルの全エントリについて、そ内容に加えてヒット情報が登録され、前記フォワーディングテーブルまたは前記キャッシュテーブルがヒットしたときにそのエントリの内容が更新されるヒット状況データベースとを備えたルータを、
パケットが入力されるとそのパケットヘッダから宛先ネットワークアドレスを取り出し、このアドレスをキーにして前記キャッシュテーブルまたは前記フォワーディングテーブルを検索し、得られた出方路にパケットを転送するパケット処理回路と、
前記キャッシュテーブルに登録されている全エントリの前記優先度情報を含み、前記エントリ群入れ替えを行うときには、該優先度情報と前記ヒット状況データベースからの優先度情報とを比較して入れ替えるべきエントリ群を選択するエントリ選択装置として機能させるためのプログラムを記録したコンピュータ読み込み可能なプログラム記録媒体。
【請求項１３】
前記エントリ選択装置は、
前記ヒット状況データベースからエントリ群全ての情報を受け取り、この全エントリから、エントリ固有の優先度である領域，エントリ使用状況の評価値およびこれらの各々についての閾値の代表値を決めるエントリ群代表値手段と、
前記キャッシュテーブルに既に存在するエントリ群に関して、そのエントリ群とその代表値を組にして表に持っており、その表の各エントリ群の代表値と、前記エントリ群代表値回路から送られてくる代表値とを比較して、キャッシュテーブルに既に存在するエントリ群がどのような優先順位にあるかを送出する前記領域，エントリ使用状況の評価値および閾値対応の比較手段と、
該比較回路から送られてきた優先順位データを基にエントリの最終的な入替え順位を決定する調停手段と、
前記キャッシュテーブルの空き状況を管理しており、当該エントリ群を追加することのできる空きがあるかどうかを調べ、空きが無い場合には、前記調停回路が決定した順位の最も低いエントリが所属するエントリ群から前記キャッシュテーブルのエントリを消去して十分な空きを作り、また削除したエントリ群を前記表からの削除のために前記比較回路に送るエントリ決定送付手段とから成ることを特徴とする請求項１２に記載のプログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ルータにおけるキャッシュテーブル管理、特にフォワーディングテーブルとキャッシュテーブルとの間でエントリを群単位で出し入れするときのキャッシュテーブルの管理に関する。
【０００２】
【従来の技術】
複数のネットワークを接続するルータは、異なるネットワークを越えて行われる通信を媒介するため、通信情報の固まり（パケット）の転送（フォワーディング）を行わなければならない。ルータは、接続されたネットワークから入力されたパケットをネットワークインタフェース（以下、「インタフェース」と記す）で受信し、そのパケットのヘッダ部分に含まれる送信先アドレスを基に、各ルータの持つフォワーディングテーブルを検索して、パケットを送信すべきインタフェースの番号を決定して、パケットのフォワーディングを行う。
【０００３】
この場合、ネットワークの数やネットワークに接続される端末の数が多いと、フォワーディングテーブルの規模も大きくなり、フォワーディングが低速化する。そこで、従来から、キャッシュテーブルを使用して、フォワーディング、ひいてはパケット処理を高速化した技術が知られている。
【０００４】
例えば、特開平６−２６１０７８号公報に記載された「テーブル検索方法及びルータ装置」では、各インタフェースはルーティングテーブル及びルーティングテーブル検索用のキャッシュメモリを備える。ルーティングテーブルには、特定のネットワークがそのルータのインタフェースを介して到達可能であるか、また、そのインタフェースを介してパケットを送出したとき、送出ネットワーク内での宛先をどこにすればよいかの情報が書かれている。すなわち、ルーティングテーブルの各エントリは宛先ネットワークアドレス，宛先ネットワークアドレスに対するマスク，送出ネットワーク内での宛先ネットワークアドレス及び送出インタフェース番号を格納する。
【０００５】
キャッシュメモリはＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）と対応テーブルとから成る。ＣＡＭには、ルーティングテーブル上の該当エントリへのポインタが得られた宛先ネットワークアドレスが登録され、対応テーブルは、ＣＡＭのエントリにリンクしているエントリを持ち、そこにルーティングテーブルの該当エントリへのポインタが登録される。そして、同じネットワークアドレスに対して再度ルーティングテーブルを検索する場合には、先ず、ＣＡＭに対して宛先ネットワークアドレスの照合を行い、該当アドレスが登録されている場合は、ＣＡＭの該当ネットワークアドレスが登録されているエントリにリンクしている対応テーブルのエントリからルーティングテーブルへのポインタを得る。この結果、検索回数の多い宛先ネットワークアドレスがキャッシュメモリに登録されることになるのでテーブル検索時の高速化が図れ、また、対応テーブルを設けるのでＣＡＭのエントリサイズを小さくすることができる。
【０００６】
しかし、この従来技術ではキャッシュメモリにおけるテーブル検索は、検索キーとしてホストアドレスを用いた完全一致検索方式を採用しているため、検索に時間がかかりすぎたり、ヒット率を上げようとすると大容量のキャッシュメモリを必要とするという問題点がある。
【０００７】
そこで、小林ほかにより特願平１１−０３３２８７において、最長一致検索のできるフォワーディングテーブル（以下、「フルテーブル」と記す）と、最長一致検索のできるキャッシュテーブルを設けた「キャッシュを有するルータの方路決定装置及びプログラムを記録した機械読み取り可能な記録媒体」が提案されている。
【０００８】
この技術について、先ず、それぞれのテーブルの構成と検索方法について説明する。第１の構成例においては、フルテーブルには、ルーティングに必要な全ての経路を含むエントリを入れ、キャッシュテーブルにはフルテーブルの一部のエントリを入れておく。また、第２の構成例においては、キャッシュテーブルにはフルテーブルの一部のエントリを入れておき、フルテーブルにはキャッシュテーブルにあるエントリを除いた全ての必要なエントリを入れておく。
【０００９】
キャッシュヒット率を高めるためには、キャッシュテーブルとフルテーブルでエントリを入れたり出したりの操作を行う必要があるが、第１の構成例においては、フルテーブルからキャッシュテーブルへはエントリをコピーし、キャッシュテーブルからフルテーブルへは、データを廃棄（削除）することになる。一方、構成例２においては、  フルテーブルからキャッシュテーブルへはエントリを移動し、キャッシュテーブルからフルテーブルへも、やはりデータを移動することになる。以下の説明では、第１の構成例について、コピーと削除という動作で説明するが、第２の構成例の場合には、第１の構成例におけるコピーが移動に、第１の構成例における削除が移動という操作に相当する。なお、コピーすることを単に「入れる」と呼ぶ。
【００１０】
フルテーブルは大量のデータを検索するので検索時間は長い。キャッシュテーブルは容量は小さいが高速に検索できる。先ず、検索要求があれば、まずキャッシュを最長一致検索で検索する。キャッシュでエントリが見つかれば（ヒットするという）、検索はここで終了する。しかし、見つからない場合（ミスヒット）には、引き続きフルテーブルを最長一致検索する。フルテーブルには全てのエントリが入っているので、必ずヒットし検索は終了する。最長一致検索とは、特願平１１−０３３２８７にも記載されているように、プレフィクス（Ｐｒｅｆｉｘ）が一致するものを候補とし、その候補のエントリから最も長いプレフィクス長をもつエントリをヒットエントリとする検索をいう。
【００１１】
例えば、（Ａ）１００．１２０．０．０／１６と（Ｂ）１００．０．０．０／８と（Ｃ）１００．１２０．１４０．０／２４と（Ｄ）１００．１２０．１８０．０／２４というプレフィクスで表わされるネットワークアドレスを有する４つのエントリがあるときに、検索キーとして、ネットワークアドレス「１００．１２０．１４０．５」が与えられたとする。なお、１００．１２０．０．０等はプレフィクスビットと呼ばれ、ドットで区切られた数字はそれぞれ８ビットで１０進数を表現する。この８ビットで構成される１０進数が０のときは任意数（ｄｏｎ’ｔ  ｃａｒｅ）を意味する。また、／の後の数はプレフィクス長を意味する。与えられたネットワークアドレス「１００．１２０．１４０．５」は、（Ａ），  （Ｂ），  （Ｃ）のいづれにもプレフィクスが一致するため、（Ａ），  （Ｂ），  （Ｃ）の３つとも検索結果の候補になる。しかし、最長一致検索では、候補の中から最も長いプレフィクス長のエントリを選択することになるため、この場合、プレフィクス長＝２４が最も長いので、検索の結果、（Ｃ）１００．１２０．１４０．０／２４のエントリがヒットする。
【００１２】
次に、キャッシュテーブルに入れるエントリについて述べる。この特願平１１−０３３２８７に提案の発明では、キャッシュテーブルに出し入れするエントリは、注目している単独のエントリのコピーや削除ではなく、所定の規則を持って複数あるいは場合によっては単独のエントリで移動することになる。すなわち、同じプレフィクスを持つエントリのプレフィクス長の短いものを親、長いものを子と呼ぶときに、キャッシュインのときは自分の全ての子を必ずいっしょにキャッシュに入れ、キャッシュアウトのときは自分の全ての親を必ずいっしょにキャッシュから取り出すのである。以下の説明では、この規則に従って移動すべき複数のエントリをエントリ群と呼ぶ。
【００１３】
このエントリ群の作り方は、具体例で示せば次のようである。例えば、前記（Ａ），  （Ｂ），  （Ｃ）および（Ｄ）の４つのエントリにおいて、（Ａ）１００．１２０．０．０／１６というエントリをフルテーブルからキャッシュに移動させるときは、（Ａ），（Ｃ）および（Ｄ）がエントリ群になる。また、（Ａ）をキャッシュテーブルからフルテーブルに移動させるときには、（Ａ）のみがエントリ群になる。
【００１４】
また、キャッシュからフルテーブルへの方向にエントリを移動する場合のエントリ選択方法としてＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）という方法が記述されている。ＬＲＵとは、エントリが参照された順序において最も古いものを対象とする方法である。これは次のような理由による。上述の（Ａ）１００．１２０．０．０／１６と（Ｃ）１００．１２０．１４０．０／２４と（Ｄ）１００．１２０．１８０．０／２４とでは出方路としてのインタフェース番号が異なっているときに、もし、（Ａ）１００．１２０．０．０／１６だけをキャッシュインしておくと、「１００．１２０．１４０．５」が検索キーとして与えられると、最長一致検索の結果として（Ｃ）対応のインタフェース番号が得られるべきところ、それとは異なる（Ａ）対応のインタフェース番号がキャッシュにおいて得られることになるからである。また、（Ｃ）をキャッシュアウトするときに（Ａ）をキャッシュに残しておくと、「１００．１２０．１４０．５」が検索キーとして与えられると、（Ｃ）対応のインタフェース番号と異なる（Ａ）対応のインタフェース番号がキャッシュヒットするからである。
【００１５】
【発明が解決しようとする課題】
ところで、キャッシュシステムでは、キャッシュに入れるべきデータはフルテーブル全体の一部分であるため、フルテーブルからエントリを選択してキャッシュに入れる必要がある。このとき、高速検索を行うためにはキャッシュでヒットする確率を上げなければならないので、キャッシュに入れるべきエントリの選択が重要である。また、キャッシュのエントリ内容を動的に変更する場合には、キャッシュから出すべきエントリの選択も重要である。
【００１６】
このような選択方法としては、上述の２つの先例におけるフォワーディング技術ではＬＲＵ方式が採用されている。しかしながら、このようなＬＲＵは、単独のエントリを出し入れする場合にあっては効果的であっても、特願平１１−０３３２８７におけるようにエントリ単独ではなく、エントリ群、すなわち関連の複数のエントリを束にしてキャッシュに出し入れするような制約の下では効果的とはいえないという第１の問題点がある。例えば、図１２に例示するように、使用時系列「３：００」「２：００」のプレフィクス（Ａ）１００．１２０．０．０／１６と、使用時系列「１：００」，「０：３０」のプレフィクス（Ｃ）１００．１２０．１４０．０／２４を含むキャッシュから（Ｃ）を出すときには、その親である（Ａ）も出すことになるが、そうすると（Ａ）よりも長い間使用されていない（Ｄ）がキャッシュに残ることになるのである。
【００１７】
また、ＬＲＵのようなアルゴリズムを採用すると、データの選択が参照度に従って機械的になされてしまい、意図的にデータの重要度、具体的には、ポリシー上または料金体系上から回線接続の容易性の度合をつけることができないという第２の問題点もある。例えば、エントリ別に重要度が異なるときにおいても、従来のＬＲＵでは、キャッシュへのエントリの出し入れを全てを平等に扱ってしまい、データの重要度に応じた扱いができない。
【００１８】
本発明は、このような問題を解決すために成されたものであって、その目的は、キャッシュを有するルータにおいて、キャッシュのヒット確率を上げることによって、キャッシュ検索より時間のかかるフルテーブル検索を行う確率を下げ、ルータのパケット処理時間を減らし、ルータのパケット処理能力を向上させることのできるキャッシュに入出力するエントリ群の管理装置およびプログラム記録媒体を提供することにある。
【００１９】
本発明の他の目的は、エントリの重要度に応じて、  検索処理に重み付けをするためのエントリ群選択、つまりキャッシュに入出力するエントリ群の選択方法を提供することにある。
【００２０】
【課題を解決するための手段】
第１の本発明のルータにおけるキャッシュ管理装置は、全エントリに対して最長一致検索を行うためのフルテーブルと、全エントリの一部のエントリに対して最長一致検索を行うためのキャッシュとを備え、前記フォワーディングテーブルにおいてエントリを前記キャッシュテーブルに入れるときには、そのエントリを親とする全エントリを、また前記キャッシュテーブルからエントリを出すときには、そのエントリの親となる全エントリを、当該エントリの使用状況の評価値に対する閾値および削除あるいは移動されるエントリの領域対応の優先度に応じて選択することを特徴とする。
【００２１】
第２の本発明のルータにおけるキャッシュ管理装置は、全エントリに対して最長一致検索を行うためのフルテーブルあるいは全エントリの一部のエントリに対して最長一致検索を行うためのキャッシュ内に仮想的な複数の領域を設定する手段と、該領域内では、それぞれ固有に、削除あるいは移動対象を決めるためのエントリ群の使用状況の評価値と、少なくとも削除対象に選択される可否を決める閾値と選択された場合に実際に削除あるいは移動されるエントリの該領域に応じて決まる優先度の一つを持つ手段と、該閾値および優先度に応じて入れ替え対象のエントリ群を選択する手段とを持つことを特徴とする。
【００２２】
この場合、各エントリあるいは各エントリ群と各仮想的な領域を関連付ける手段、または各エントリあるいは各エントリ群にそれぞれ優先度を関連付ける手段、または各エントリあるいは各エントリ群にそれぞれ閾値を関連付ける手段の内の少なくとも一つの手段を備えるようにしてもよい。
【００２３】
また、特定の時間区間において、エントリ群を構成する各エントリが持つ使用状況の評価値に対して、該使用状況を全てのエントリに対してあるいは一部のエントリに対して組み合わせた値あるいは統計値を各エントリ群の使用状況の評価値として用いる手段を備えるようにしてもよい。
【００２４】
第３の本発明のルータにおけるキャッシュ管理装置は、プレフィクスビット列およびプレフィックス長から成るアドレスの集合を示す情報と、このアドレスの集合に対するパケットの出方路を示す情報と、優先度情報との組が登録されたエントリを複数有し最長一致検索されるフルテーブルと、入れ替えるべきエントリを親とする前記フルテーブルの全エントリが書き込まれ、またエントリが削除・移動されるときには、その親も削除・移動されるキャッシュと、前記フルテーブルの全エントリについて、その内容に加えてヒット情報が登録され、前記フルテーブルまたは前記キャッシュがヒットしたときにそのエントリの内容が更新されるヒット状況データベースと、パケットが入力されるとそのパケットヘッダから宛先ネットワークアドレスを取り出し、このアドレスをキーにして前記キャッシュテーブルまたは前記フォワーディングテーブルを検索し、得られた出方路にパケットを転送するパケット処理回路と、前記キャッシュに登録されている全エントリの前記優先度情報を含み、前記エントリ群入れ替えを行うときには、該優先度情報と前記ヒット状況データベースからの優先度情報とを比較して入れ替えるべきエントリ群を選択するエントリ選択装置と備えたことを特徴とする。
【００２５】
エントリ選択装置は、前記ヒット状況データベースからエントリ群全ての情報を受け取り、この全エントリから、エントリ固有の優先度である領域，エントリ使用状況の評価値および閾値の代表値を決めるエントリ群代表値回路と、前記キャッシュに既に存在するエントリ群に関して、そのエントリ群とその代表値を組にして表に持っており、その表の各エントリ群の代表値と、前記エントリ群代表値回路から送られてくる代表値とを比較して、キャッシュに既に存在するエントリ群がどのような優先順位にあるかを送出する前記領域，エントリ使用状況の評価値および閾値対応の比較回路と、該比較回路から送られてきた優先順位データを基にエントリの最終的な入替え順位を決定する調停回路と、前記キャッシュの空き状況を管理しており、当該エントリ群を追加することのできる空きがあるかどうかを調べ、空きが無い場合には、前記調停回路が決定した順位の最も低いエントリが所属するエントリ群から前記キャッシュのエントリを消去して十分な空きを作り、また削除したエントリ群を前記表からの削除のために前記比較回路に送るエントリ決定送付回路とで構成してもよい。
【００２６】
より詳しくは、前記エントリ使用状況の評価値として、ヒット回数またはヒット時刻またはその両者を採用してもよく、前記各代表値は、閾値と領域についてはエントリ中の最も高い値、ヒット回数は平均値、ヒット時刻は最近のものとすることもできる。
【００２７】
また、前記調停回路は、０〜１の乱数を発生し、その乱数を２等分して、１／２づつをヒット回数とヒット時刻に割り当て、割り当てられた属性の順位を最終的な順位とするように構成してもよい。
【００２８】
また、前記エントリの優先度を受信パケットから得られる情報に応じて設定する手段を設けてもよいし、ポリシーサーバにより変更可能としてもよい。
【００２９】
本発明によれば、ヒットする可能性の高いエントリをキャッシュにおくことができるため、キャッシュミスヒット率の低い検索が可能であり、それゆえ全体の検索処理速度を向上させることが可能となる。すなわち、ヒット数の高いエントリが知られているときに、該エントリを優先的にキャッシュに入れておくことで、ヒットする可能性の高いキャッシュ内容となる。逆に、ヒット数の低いエントリはできるだけキャッシュに存在しないように、その優先度を下げることで、キャッシュを有効に使用できる。
【００３０】
また、エントリ群の平均，最大値、最小値といった統計数値を用いてエントリ群の代表値を得、その代表値をヒットする可能性を示す値として用いることにより、ヒット率を上げることができる。エントリ群は非常に多数のエントリから成るものもあり、まためったに使われないことがわかっている場合など様々な状況が考えられるため、そのエントリ群の一部のエントリだけを用いて前記代表値を決めることは、そのエントリ群の真の代表値により近くなるのである。
【００３１】
また、ポリシー上または料金体系上から重要度に応じて、エントリあるいはキャッシュの領域に優先度を設けておくことにより、重要度に応じて検索速度を調整することが可能となる。
【００３２】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００３３】
図１は本発明のルータの第１実施形態の全体構成図であり、パケット処理回路１０１，キャッシュテーブル１０２，フルテーブル１０３，ヒット状況データベース１０４およびエントリ選択装置１０５から構成される。先ず、各構成要素の概要を説明する。ここでは、前述の第１の構成例を想定している。すなわち、フルテーブル１０３には、ルーティングに必要な全ての経路を含むエントリを入れておき、キャッシュテーブル１０２には、フルテーブル１０３の一部のエントリを入れておく。
【００３４】
図１において、パケット処理回路１０１はキャッシュテーブル１０２とフルテーブル１０３に接続されており、キャッシュテーブル１０２はフルテーブル１０３とヒット状況データベース１０４とエントリ選択装置１０５とに接続されている。ヒット状況データベース１０４は、さらにフルテーブル１０３とエントリ選択装置１０５と接続されている。エントリ選択装置１０５は、さらにキャッシュテーブル１０２とフルテーブル１０３と接続されている。以下、断りがない限り、最長一致検索のことを単に検索と記す。
【００３５】
フルテーブル１０３は、プレフィクスビット列とプレフィックス長とから成るアドレスの集合を示す情報と、このアドレスの集合に対するパケットの出方路を示す情報と、フルテーブル１０３とキャッシュテーブル１０２のエントリを入れ替えるときにエントリを選択するための優先度情報との組が登録されたエントリを複数有する。また、キャッシュテーブル１０２は、受信したパケットの送信先アドレスをキーにしてフルテーブル１０３を検索したときにヒットしたエントリを「親」とするフルテーブル１０３の全エントリ（エントリ群）の内容が登録される。なお、ここで、フルテーブル，キャッシュテーブルといった場合、テーブル自体の他、それらの検索機構をも含んでいるものとする。
【００３６】
パケット処理回路１０１は、パケットが入力されるとそのパケットヘッダから宛先ネットワークアドレス（以下、「アドレス」と記す）を取り出し、このアドレスをキーにしてキャッシュテーブル１０２を検索する。キャッシュテーブル１０２はこのキーで検索され、ヒットするエントリがあれば、そのヒットした旨をヒットしたエントリのあるキャッシュテーブル１０２のアドレスと共にパケット処理回路１０１に通知する。一方、キャッシュテーブル１０２にヒットしなかった場合には、ミスヒットした旨をパケット処理回路１０１に通知する。パケット処理回路１０１はヒットアドレスを通知されたときには検索処理を完了し、ミスヒットを通知されたときにはフルテーブル１０３の検索を行う。
【００３７】
フルテーブル１０３の検索は、キーをフルテーブル１０３に入力して行う。フルテーブル１０３は、入力されたキーを基に検索され、ヒットしたアドレスをパケット処理回路１０１に通知する。
【００３８】
このとき、キャッシュテーブル１０２とフルテーブル１０３のうちのいづれかヒットした方のテーブルは、ヒット状況データベース１０４を更新する。ヒット状況データベース１０４には、フルテーブルの全エントリについて、エントリ番号，キャッシュテーブル１０２でのヒットアドレス，フルテーブル１０３でのヒットアドレス，各エントリの優先度，ヒットがあった時刻およびどのエントリがどのエントリと同じエントリ群に属するかの情報が書かれている。ここで、エントリの優先度とは、フルテーブル１０３のエントリのうちのどのエントリをキャッシュテーブル１０２に入れるべきか、またどのエントリを出すべきかの優先度合をいい、後述のように、フルテーブルにも登録されているエントリ固有の閾値，エントリ固有の領域，ヒット回数と、ヒット状況データベースにのみ登録されるヒット時刻等の優先度情報で定められる。
【００３９】
フルテーブル１０３は、エントリ選択装置１０５の指示に従って、フルテーブル１０３のエントリ内容をキャッシュテーブル１０２にコピーする。キャッシュテーブル１０２には、エントリ選択装置１０５の指示に従ってフルテーブル１０３から入力されたエントリが登録され（書き込まれ）、エントリ選択装置１０５の指示に従って、エントリ内容が消去（削除）される。
【００４０】
エントリ選択装置１０５は、ヒット状況データベース１０４を参照して、各エントリの優先度に基づいて、キャッシュテーブル１０２に存在させるエントリを決定し、キャッシュテーブル１０２とフルテーブル１０３にデータの移動を指示する。
【００４１】
次に、図２，図３，図４および図５を参照して、上述の各構成要素１０１〜１０５を詳細に説明する。
【００４２】
図２はパケット処理回路１０１の詳細を示す。図２を参照すると、このパケット処理回路１０１は、ヘッダコピー回路１０１１がパケットを受け取り、このパケットからＩＰアドレスを含むヘッダをコピーしてアドレス抽出回路１０１２に送る。また、パケット自体は出方路情報付加回路１０１４に送る。アドレス抽出回路１０１２は、コピーされたヘッダからＩＰアドレスを抽出して、キャッシュテーブル１０２とフルテーブル１０３に送る。ヒットアドレス・出方路情報変換回路１０１３は、キャッシュテーブル１０２とフルテーブル１０３のいずれかからヒットアドレス情報を受け取り、このヒットアドレス情報を出方路情報に変換して出方路情報付加回路１０１４に送る。出方路情報付加回路１０１４は、ヘッダコピー回路１０１１からのパケットと出方路情報付加回路１０１４からの出方路情報を受け取り、それらを結合する。ヒットアドレス・出方路情報変換回路１０１３における変換は、一覧表を検索して行う。一覧表はヒットアドレスと出方路インタフェース番号の組が表になったものである。
【００４３】
図３はキャッシュテーブル１０２の詳細を示す。図３を参照すると、キャッシュテーブル１０２では、検索キーレジスタ１０２１がパケット処理回路１０１におけるアドレス抽出回路１０１２からのＩＰアドレスを受け取る。最長一致検索回路１０２２は、このＩＰアドレスとビットマスク付メモリ１０２５の各エントリの内容とを比較して、最長一致となるエントリを決定する。最長一致検索回路１０２２は、決定したエントリのアドレス（メモリのアドレス）、つまりヒットアドレスあるいは一致しなかったという情報をパケット処理回路１０１および結果情報回路１０２３に送る。結果情報回路１０２３は、ヒットアドレスにヒットした時刻、つまり現時刻の情報を付加してヒット状況データベース１０４に送る。エントリ操作回路１０２４は、エントリ選択装置１０５およびフルテーブル１０３から送られてくる情報を受け取り、ビットマスク付メモリ１０２５の各エントリの削除，更新，読出しまたは書込みを行う。
【００４４】
フルテーブル１０３は、当然にキャッシュテーブル１０２より大規模であるが、その構成は、図３に示したキャッシュテーブル１０２のブロック図と同様である。
【００４５】
図４は、ヒット状況データベース１０４の詳細を示す。図４を参照すると、書込み読出し制御回路１０４１が、キャッシュテーブル１０２またはフルテーブル１０３からヒットアドレスとその時刻情報を受け取り、状況テーブル１０４２のうちのヒットアドレスと一致するエントリヒット時刻情報を書き込む。また、フルテーブル１０３からヒット情報を受け取った場合には、書込み読出し制御回路１０４１は、そのエントリ群の全エントリ情報をエントリ選択装置１０５に送る。
【００４６】
状況テーブル１０４２は、エントリ毎に、そのエントリの番号，キャッシュテーブル１０２でのヒットアドレス，フルテーブル１０３でのヒットアドレス，キャッシュテーブル１０２におけるそのエントリの領域，キャッシュテーブル１０２における閾値，フルテーブル１０３における閾値，キャッシュヒット回数，ヒット時刻，キャッシュテーブル１０２にエントリ群を入れる時のそのエントリ番号およびフルテーブル１０３にエントリ群を入れる時のそのエントリ番号を格納する。
【００４７】
図５は、エントリ選択装置１０５の詳細を示す。図５を参照すると、エントリ群代表値回路１０５７はヒット状況データベース１０４から上述のエントリ群全ての情報（Ｎ個）を受け取る。エントリ群代表値回路１０５７は、図６にその処理フローチャートを示すように、この全エントリから、閾値，領域，ヒット回数およびヒット時刻の各々について、最大値を持つエントリと最小値を持つエントリとを除外し、（Ｎ−２）個のエントリを抽出する。そして、抽出したエントリから閾値，領域，ヒット回数，ヒット時刻の４つの代表値を決める。各代表値は、図６に示すように、閾値と領域についてはエントリ中の最も高い値、ヒット回数は平均値、ヒット時刻は最近のものとする。各代表値は、閾値保持回路１０５３，領域保持回路１０５４，ヒット回数比較回路１０５５およびヒット時系列比較回路１０５６に送る。
【００４８】
ここで、閾値とは、エントリ群選択の優先度を定める他の属性、すなわち、領域，ヒット回数およびヒット時刻に対して比較の対象となる基準値であり、。また、領域とは、そのエントリ固有の優先度をいい、ポリシーあるいは料金体系から決められ得る。
【００４９】
比較回路１０５５〜１０５６は、キャッシュテーブル１０２に既に存在するエントリ群に関して、そのエントリ群とその代表値を組にして表に持っており、その表の各エントリ群の代表値と、エントリ群代表値回路１０５７から送られた値とを比較する。また、その際に、領域と閾値を考慮して比較を行う。本実施例では、ヒット回数，ヒット時刻を閾値と比較し、閾値を超えたエントリ群のみをまず選択し、さらに、比較回路１０５５〜１０５６に保持されている全エントリ群のヒット回数，ヒット時刻に、優先度を掛け算して算出した値の大きい順に優先度をつける。比較の結果、送られた代表値と、キャッシュテーブル１０２に既に存在するエントリ群とが、どのような順位にあるかを調停回路１０５２に送る。調停回路１０５２では、それぞれの回路から送られてきた順位データを元に、それらに差異がある場合には、それらを参考にして、図７にその処理フローチャートを示すように、最終的な順位を決定する。図７を参照すると、０〜１の乱数を発生し、その乱数を２等分して、１／２づつをヒット回数，ヒット時刻に割り当て、割り当てられた属性の順位を最終的な順位としてエントリ決定送付回路１０５１に送る。
【００５０】
エントリ決定送付回路１０５１は、キャッシュテーブル１０２の空き状況を管理しており、Ｎ個のエントリを追加することのできる空きがあるかどうかを調べ、空きが有るときには、そのままＮ個のエントリを書き込み、また空きが無いには、順位の最も低いエントリが所属するエントリ群からキャッシュテーブル１０２のエントリを消去し、空きが十分になるまでこの手順を繰り返す。最後に、削除したエントリ群を各回路１０５３〜１０５６に送る。各回路１０５３〜１０５６は、削除したエントリ群情報を受け取り、表からそのエントリ群を削除する。
【００５１】
なお、優先度は、上の説明では、閾値，領域，ヒット回数およびヒット時刻の４つの属性から定めるとしているが、本発明ではこれにとらわれることなく、優先度を定めるのにこれらの属性のうちの少なくとも一つを使用することも可能である。
【００５２】
次に、本発明の第２の実施例として、キャッシュテーブル１０２の内部を２つの領域に分け、それぞれＡ、Ｂとした例について説明する。この例ではヒット状況データベース１０４には、ヒット回数をエントリ毎に記録する。また、エントリ選択装置１０５は、領域Ａにおいては、エントリ群のヒット回数の代表値が閾値Ｍ以下のものをキャッシュテーブル１０２からの消去対象とし、領域Ｂにおいては、エントリ群のヒット回数の代表値が閾値Ｍの０．５倍以下のものを消去対象とし、さらに消去対象となったエントリ群に対して領域Ａと領域Ｂに２対１の重みをつけて、キャッシュテーブル１０２から削除するエントリ群を選択する。例えば、閾値を領域Ａは１０、領域Ｂは５とし、領域Ａと領域Ｂそれぞれからこれらの閾値を下回るエントリ群を選び出す。さらに、この選択されたエントリ群に対して、ある確率変数Ｎに基づいて削除するエントリ群を選択する。重み付けをして領域Ａのエントリ群はＮ、領域Ｂのエントリ群は２Ｎとする。この結果、最も確率の高いエントリ群を消去対象として選択する。さらに削除が必要であれば、この操作を繰り返す。
【００５３】
また、Ａの重み付けを０（ゼロ）として、Ａを確率によらずに削除対象から外すことも可能である。逆に閾値を無限大として、全てのエントリのヒット回数の代表値が閾値以下とする、つまり閾値を事実上使用しないことも可能である。
【００５４】
また、ヒット回数を用いない方法も可能である。上記例では、閾値とヒット回数を代表値として用いることを領域Ａ，Ｂで行ったが、これ以外の任意の組合せを領域Ａ，Ｂについて行うことも可能である。例えば、閾値はＡ，Ｂという領域に異なる値を割り付、このＡ，Ｂとは全く独立なａ，ｂという領域ではそれぞれヒット回数の平均値とヒット回数の最大値といった別の代表値を用いることも可能である。
【００５５】
また、エントリ選択装置１０５は、上述のキャッシュテーブル１０２に対する操作と同様の操作をフルテーブル１０３に対しても行い、フルテーブル１０３からキャッシュテーブル１０２に入れるエントリを選択する。
【００５６】
次に、第３の実施例について説明する。本例では、各エントリは、その優先度を定めるための属性として、フルテーブルのどの領域に入れることができるか（どの領域に属することができるか）という領域情報と閾値とを持つ。このような属性は、本実施例では固定とするが、動的に変更することが可能である。動的に変更する場合、例えば、属性の変更はポリシーサーバの指示に応じて行われる。ポリシーサーバは網の運用のためのルールが網の管理者によって記述されているものである。例えば、あるエントリは昼間は優先度が高いが夜は優先度が低いといったルールがポリシーサーバに記述されていると、ポリシーサーバーはそれに応じて昼と夜で優先度を切り替える必要があることを知り、各エントリの優先度の切り替えを行う。
【００５７】
図８は、そのようなポリシーサーバ３０１が設けられた本発明の第２の実施形態のルータの全体構成図を示す。ポリシーサーバー３０１は、ヒット状況データベース１０４とエントリ選択装置１０５に対して、各エントリの領域，閾値の値を定義し、これをマッピング回路１０４３とマッピング回路１０５８を通じて優先制御に反映させる。
【００５８】
すなわち、ポリシーサーバ３０１は、ユーザがフルテーブルの各エントリに対して定義した領域，閾値の値を端末３０２を通じて受け取り、ポリシーサーバ３０１内に保持する。さらに、ポリシーサーバ３０１は、保持している情報に変更があったときに、その情報をパケット処理回路１０１内のヘッダコピー回路１０１１とアドレス抽出回路１０１２を経由してヒット状況データベース１０４とエントリ選択装置１０５に送る（図９参照）。
【００５９】
ヒット状況データベース１０４では、マッピング回路１０４３が書込み読出し制御回路１０４１を通じて、状況テーブル１０４２に書き込み（図１０参照）、また、エントリ選択装置１０５では、マッピング回路１０５８が閾値保持回路１０５３および領域保持回路１０５４に存在する各エントリの閾値，領域を変更する（図１１参照）。
【００６０】
次に、本発明の第４の実施例について説明する。この例では、各エントリが持つ属性は、入力されたパケットにより変更され得る。パケットは、そのヘッダに属性を決める値を持っており、この値に従って、ヒットしたエントリの属性を変更する。
【００６１】
アドレス抽出回路１０１２は、コピーされたパケットヘッダからアドレスを抽出して、そのアドレスをキャッシュテーブル１０２とフルテーブル１０３に送るとともに、パケットヘッダのアドレス、あるいはそれ以外のヘッダ部分、ここでは、ＩＰバージョン４パケットのヘッダのＴｉｍｅ  Ｔｏ  Ｌｉｖｅ（ＴＴＬ）の値によって領域の値，閾値を決定し、マッピング回路１０４３とマッピング回路１０５８に送る。領域の値，閾値は、例えば、ＴＴＬが３２以上のときには領域＝低優先、閾値＝５０とし、ＴＴＬが３２未満のときには領域＝高優先、閾値＝１００とする。マッピング回路１０４３とマッピング回路１０５８の動作は第３実施例における動作と同様である。
【００６２】
次に、本発明の第５の実施例について説明する。この例では、エントリ選択装置１０５は、エントリ群の代表値を評価する際に、エントリ群を構成する全てのエントリのなかから所定の規則に従ってエントリを選んで，その選ばれたエントリ（計算対象エントリ）の値に基づいて求める。例えば，エントリ群を構成するエントリの最大値と最小値を除いた全ての値の平均値を代表値とする。あるいは、エントリ群を構成するエントリのヒット時刻の最近（最も近い過去）の時刻を持つエントリを除いたエントリの時刻の平均値を代表値とする。
【００６３】
次に、本発明の第６の実施例では、エントリ選択装置１０５はエントリ群の代表値を評価する際に、計算対象となるエントリの全ての値のなかから所定の規則に従って選ばれた値を用いる。例えば、  エントリのヒット時刻の系列において、最近（最も近い過去）の時刻を代表値とする。
【００６４】
次に、以上に説明したキャッシュの管理方法を実行するプログラムを半導体メモリ，ＣＤ−ＲＯＭ，フロッピーディスク等の記録媒体に記録し、それをルータに読み込ませて実行するようにしてもよい。そのルータは、上述のフルテーブル，キャッシュおよびヒット状況データベースを備えており、また、読み込んだプログラムは、ルータに上述のパケット処理回路およびエントリ選択装置と同様な機能を発揮させる。
【００６５】
【発明の効果】
本発明の第１の効果は、キャッシュを有するルータにおいて、エントリを群単位でキャッシュから出し入れする場合にも、キャッシュのヒット確率を上げることができることである。その理由は、よく使用されるエントリをキャッシュに置くようにするからである。よく使われるエントリは、使用頻度や、総使用回数などで定める優先度を用いて選ぶ。例えば、ランダムに選んだ場合に比べて使用頻度の高いものを選んだ場合に明らかにキャッシュヒット率が向上する。
【００６６】
また、第２の効果は、あるポリシーに基づいて、処理性能を向上させるべきエントリに属性を指定できるため、優先度合いをつけることが可能になることである。例えば、顧客毎に異なる料金体系を採用している場合、高い料金を得ている顧客の持つアドレスを包含するようなエントリの優先度を上げることで、その顧客と通信するパケットの処理を高速化でき、低い料金の顧客との差別化が可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態のブロック図
【図２】図１におけるパケット処理回路１０１の詳細ブロック図
【図３】図１におけるキャッシュテーブル１０２の詳細ブロック図
【図４】図１におけるヒット状況データベース１０４の詳細ブロック図
【図５】図１におけるエントリ選択装置１０５の詳細ブロック図
【図６】図５におけるエントリ群代表値回路１０５７の処理フローチャート
【図７】図５における調停回路１０５２の詳細ブロック図
【図８】本発明の第２の実施形態のブロック図
【図９】図８におけるパケット処理回路１０１の詳細ブロック図
【図１０】図８におけるヒット状況データベース１０４の詳細ブロック図
【図１１】図８におけるエントリ選択装置１０５の詳細ブロック図
【図１２】本発明を具体的に説明するための図
【符号の説明】
１０１      パケット処理回路
１０２      キャッシュテーブル
１０３      フルテーブル
１０４      ヒット状況データベース
１０５      エントリ選択装置
３０１      ポリシーサーバ
３０２      端末
１０１１    ヘッダコピー回路
１０１２    アドレス抽出回路
１０１３    ヒットアドレス・出方路情報変換回路
１０１４    出方路情報付加回路
１０２１    検索キーレジスタ
１０２２    最長一致検索回路
１０２３    結果情報回路
１０２４    エントリ操作回路
１０２５    ビットマスク付メモリ
１０４１    書込み読出し制御回路
１０４２    状況テーブル
１０４３    マッピング回路
１０５１    エントリ決定回路
１０５２    調停回路
１０５３    閾値保持回路
１０５４    領域保持回路
１０５５    ヒット数比較回路
１０５６    ヒット時系列比較回路
１０５７    エントリ群代表値回路
１０５８    マッピング回路
【図１】
0003591420.tif 000002
【図２】
0003591420.tif 000003
【図３】
0003591420.tif 000004
【図４】
0003591420.tif 000005
【図５】
0003591420.tif 000006
【図６】
0003591420.tif 000007
【図７】
0003591420.tif 000008
【図８】
0003591420.tif 000009
【図１０】
0003591420.tif 000010
【図１１】
0003591420.tif 000011
【図９】
0003591420.tif 000012
【図１２】
0003591420.tif 000013