(57)【要約】【課題】従来のルーティングテーブル管理方式は、必要メモリ量が大きく実装が困難かつコストの増大を招くばかりでなく、スループットのボトルネックとなる。【解決手段】ルーティングテーブルメモリの構造として、ＮＵＭＡ型，もしくはＣＣ−ＮＵＭＡ型、さらに進んでＣＯＭＡ型を提案した。これらは、共有ルーティングテーブルを備えず各インタフェースに分散して配置した分散ルーティングテーブルにより経路情報を管理し、位置ローカリティを活かす。特にＣＯＭＡ型では経路情報エントリのホームの位置が参照により自由に遷移するため、より位置ローカリティを活用できる。  ＣＣ−ＮＵＭＡ型、ＣＯＭＡ型はキャッシュを備え、時間ローカリティに対応する。また、キャッシュのハッシュ関数に攪拌作業を入れることでアドレスローカリティに対応する。さらにた、ゾーンごとにハッシュ関数を変えてキャッシュメモリに登録することにより空間ローカリティに対応し、キャッシュのヒット率を向上する。【選択図】  図１
2004221807.tif 000002
【特許請求の範囲】
【請求項１】
複数のインタフェースを有するルータであって、
上記複数の各インタフェースは、
入力されたパケットを処理するパケット処理部と、
上記パケットに依存する情報とパケットの宛先の組を情報として格納し、パケットに依存する情報をキーとして参照され、パケットの宛先を検索するルーティングテーブルと、を有し、
第１のインタフェースのルーティングテーブルにおいて検索がヒットしなかった場合、第２のインタフェースのルーティングテーブルを参照して、宛先を検索するルータ。
【請求項２】
上記各ルーティングテーブルは、該ルーティングテーブルの持つ情報の一部の複製を格納するルーティングテーブルキャッシュを有し、
あるルーティングテーブルキャッシュにおいて検索がヒットしなかった場合、そのルーティングテーブルキャッシュに対応するルーティングテーブルを参照して、宛先を検索する請求項１記載のルータ。
【請求項３】
上記各ルーティングテーブルは、ルーティングテーブルキャッシュとして構成されており、
パケットが到着したインタフェースにあるルーティングテーブルキャッシュにおいて検索がヒットしなかった場合、それ以外のインタフェースにあるルーティングテーブルキャッシュを参照して宛先を検索し、ヒットした場合には当該ヒットしたデータを上記第１のルーティングテーブルキャッシュにコピーする請求項１記載のルータ。
【請求項４】
上記第２のルーティングテーブルが参照結果を返した場合は、当該参照結果を上記第１のルーティングテーブルに格納する請求項１記載のルータ。
【請求項５】
上記インタフェース間で入力されたパケットを転送する第１のパスと、上記インタフェース間で上記ルーティングテーブルの格納情報を転送する第２のパスを独立に有する請求項１記載のルータ。
【請求項６】
上記ルーティングテーブルキャッシュのハッシュ関数に撹拌手段を用いる請求項２また３記載のルータ。
【請求項７】
上記ルーティングテーブルの内容変更時に変更されたルーティングテーブルと同じエントリをもつ他のルーティングテーブルのエントリを無効化するか、もしくは更新メッセージにより他のインタフェースにあるルーティングテーブルに変更を通知する請求項１記載のルータ。
【請求項８】
上記ルーティングテーブルのエントリに、当該エントリの内容と同じ内容を他のルーティングテーブルが保持することを示すためのビットマップ、もしくはフラグを備請求項１記載のルータ。
【請求項９】
上記パケットに依存する情報とは、ＩＰアドレスまたはＭＡＣアドレスである請求項１記載のルータ。
【請求項１０】
複数のパケット処理部と、各パケット処理部に対応して存在する複数のルーティングテーブルを有し、
第１のルーティングテーブルはそれに対応する第１のパケット処理部で処理されたパケットの宛先を検索するために先に用いられ、上記第１のルーティングテーブルで検索がヒットしなかった場合には、上記第２のルーティングテーブルで検索が行われ、
第２のルーティングテーブルはそれに対応する第２のパケット処理部で処理されたパケットの宛先を検索するために先に用いられ、上記第２のルーティングテーブルで検索がヒットしなかった場合には、上記第１のルーティングテーブルで検索が行われるルータ。
【請求項１１】
それぞれがパケットを入力される複数のインタフェースを備えるルータのルーティング方法であって、
上記各インタフェースは、入力されたパケットを処理するパケット処理部、入力されたパケットのアドレスに基づいて宛先を検索するためのルーティングテーブル、該ルーティングテーブルが格納するテーブルの少なくとも一部を格納するルーティングテーブルキャッシュを有することとし、
あるインタフェースに入力されたパケットのアドレスに基づいて、そのインタフェースの上記ルーティングテーブルキャッシュで宛先を検索する第１のステップ、
上記第１のステップで宛先が検索できなかったとき、当該インタフェースのルーティングテーブルで宛先を検索する第２のステップ、
上記第２のステップで宛先が検索できなかったとき、他のインタフェースのルーティングテーブルで宛先を検索する第３のステップ、
を有するルーティング方法。
【請求項１２】
上記第２または第３のステップで宛先が検索できたときには、当該宛先のデータを上記第１のステップで検索したルーティングテーブルキャッシュに登録する請求項１１記載のルーティング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信に於ける大容量パケットの低遅延交換システムに関わり、特に大容量パケットの低遅延交換システムにおけるパケットの経路決定作業に必要なルーティングテーブルと該ルーティングテーブルの管理運営方式に関わる。パケットとしては、特にＩＰパケット、イーサネット（登録商標）・フレームを受入れる。
【０００２】
【従来の技術】
【非特許文献１】
”Ｍｕｌｔｉ−ｚｏｎｅ  Ｃａｃｈｅｓ  ｆｏｒ  Ａｃｃｅｌｅｒａｔｉｎｇ  ＩＰ  Ｒｏｕｔｉｎｇ  Ｔａｂｌｅ  Ｌｏｏｋｕｐｓ，  Ｉ．Ｌ．Ｃｈｖｅｔｓａｎｄ  Ｍ．Ｈ．ＭａｃＧｒｅｇｏｒ，  ｐｐ．１２１−１２６，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＨＰＳＲ２００２，  Ｍａｙ．  ２００２”
通信分野においては、広帯域化、高品質化、低遅延化の要求を満たす様々なルータやスイッチの構成技術が提案されている。特に、ルーティングテーブルは今後のネットワークの高機能化、広帯域化、高品質化、低遅延化に係わる部位であり、ルーティングテーブルの動作性能がルータやネットワークの性能を左右する。
【０００３】
図１２は従来の基本的なルータの構成図である。この図を用いて基本的なパケット処理の手順を説明する。ルータの複数あるインタフェース１０１に投入されたパケットは、ルータのパケット処理部１０２において宛先情報が調べられる。この宛先情報を元にルーティングテーブル１２０１を参照し、出力先インタフェースおよびＱｏＳに必要な情報を得る。これらの情報をスイッチングファブリクス１０５に伝えることで、目的地である出力先インタフェースに該パケットを転送する。スイッチングファブリクス１０５としては、クロスバがよく用いられる。このクロスバに付随するアービタが要求を受け付け、ＱｏＳの情報や優先順位等を加味して調停を行う。この調停結果によりクロスバを設定し、入力インタフェースと出力インタフェースとの対応をとる。
【０００４】
ルーティングテーブルはルータで一つの共有ルーティングテーブル１２０２（プライマリルーティングテーブル、デフォルトルーティングテーブル等の名称で呼ばれる場合がある）のみを備える場合と、さらにそれに付随して各インタフェースに分散した分散ルーティングテーブル１２０１（セカンダリルーティングテーブル、シンプルルーティングテーブル等の名称で呼ばれる場合がある）を備える場合がある。
【０００５】
分散ルーティングテーブル１２０１の内容は共有ルーティングテーブル１２０２と同一内容であり、共有ルーティングテーブルへのアクセスを分散させるものである。特にキャッシュの場合はルーティングテーブルキャッシュと呼ばれる。ルーティングテーブルのキャッシュに関する従来技術としては  ”Ｍｕｌｔｉ−ｚｏｎｅ  Ｃａｃｈｅｓ  ｆｏｒ  Ａｃｃｅｌｅｒａｔｉｎｇ  ＩＰ  Ｒｏｕｔｉｎｇ  Ｔａｂｌｅ  Ｌｏｏｋｕｐｓ，  Ｉ．Ｌ．Ｃｈｖｅｔｓ  ａｎｄ  Ｍ．Ｈ．ＭａｃＧｒｅｇｏｒ，  ｐｐ．１２１−１２６，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＨＰＳＲ２００２，  Ｍａｙ．  ２００２”  を参照されたい。この論文において始めてＩＰに特化したキャッシュについての考察が行われた。この論文では、ＩＰトラフィックに存在する時間ローカリティと空間ローカリティを生かしたＭｕｌｔｉ−ｚｏｎｅ  Ｃａｃｈｅが提案されている。時間ローカリティは、ルータにあるＩＰアドレスから一度アクセスがあると、同じＩＰアドレスのアクセスがその後短時間に何度も発生する可能性が高いことを表す。空間ローカリティは、ルータがあるＩＰアドレスのパケットをある宛先（例えばインタフェース番号）に出力すると、その近辺のＩＰアドレス（下位数ｂｉｔのみ異なる様なＩＰアドレス）を持つパケットも同じ宛先に出力する可能性が高いことを表す。
【０００６】
図１２の技術では、共有ルーティングテーブルや他のルーティングテーブルは同じ内容を持っており、共有ルーティングテーブルの内容が適宜他のルーティングテーブルにコピーされる。また、図１２の従来例では他のインタフェースのルーティングテーブル相互では通信は行われない。
【０００７】
ルータ全体に一つのみ備わる共有ルーティングテーブル（図１２の１２０２）で経路情報を集中管理すると、ルータの処理速度の増大に伴うテーブル参照要求の集中に対応することが出来ないため、インタフェース毎にキャッシュを設けて（ルーティングテーブルキャッシュ）対応する構成が提案されている。
ルーティングテーブルキャッシュと同等の分散したルーティングテーブルを備えるものとして、特開２００２−１６４８９９、特開２０００−８３０５５、特開平１１−２８９４３５、特開平１１−１２２２８９などが提案されている。これらは、全体で一つの共有ルーティングテーブルとインタフェース毎に設けられたルーティングテーブルキャッシュの両方を備える。共有メモリへは共通のバスもしくはスイッチを介した結合となっており、この様なメモリ管理アーキテクチャをＵＭＡ（Ｕｎｉｆｏｒｍ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  ｍｏｄｅｌ）と呼ぶ。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、ルータにおけるルーティングテーブルおよびその参照機構を改善し、ルータの大容量化、低遅延化、低コスト化を図ることである。これにはルーティングテーブル用に用いられるメモリの単純化と小型化が必要である。メモリの小型化の結果、チップ点数や基板面積を削減することで低コスト化を図ることができ、動作速度が向上するためスループットが改善する。
【０００９】
従来のＵＭＡ型ルーティングテーブル管理構造において、ルーティングテーブル（図１２の１２０１）と共有ルーティングテーブル（１２０２）は実装されている場所は異なるが内容は同一である。この構造は、共有ルーティングテーブルに負荷が集中しないように、インタフェース毎に同一内容を持たせて共有ルーティングテーブルのアクセス集中を分散させるために考案された。
【００１０】
本願発明では従来手法における次のような課題に着目した。
１．共有ルーティングテーブルは各インタフェースにあるルーティングテーブルの和集合となる。従って、共有ルーティングテーブルのサイズは大きなものとなり、内容を参照する際の検索コスト、実装コストが必要となり、実効スループットの向上や低価格化に貢献できない。この共有ルーティングテーブルと同一の内容を各インタフェースで備えると、さらにコストがかかるだけでなく、ネットワークの発展に伴うルーティングテーブルの巨大化への対応が困難となる。
【００１１】
共有ルーティングテーブルとルーティングテーブルキャッシュを両方備える場合、各インタフェースにおけるルーティング情報の差異が大きいと、共有ルーティングテーブルで覚えるべき情報量が膨大となる。一般に、ルーティングテーブルの情報量が増えるとアクセスコストも増大するため、大規模かつ高速なルータでは共有ルーティングテーブルのアクセスコストが問題となり、実行スループットの向上が困難となる。
２．ルーティングテーブルの参照に強いインタフェース依存ローカリティ（位置ローカリティ）がある場合は共有ルーティングテーブルへの参照が少なく、巨大な共有ルーティングテーブルを備えるために必要なハードウエアコストに見合う性能向上を得ることが難しくなる。
３．ルーティングテーブルのキャッシュには時間ローカリティおよび空間ローカリティだけではなく、前述の位置ローカリティ、さらにアドレスローカリティについても考慮が必要である。アドレスローカリティは、有効もしくは頻繁に利用されるＩＰアドレスおよびＭＡＣアドレスが、アドレス空間全体に均一に分布しているのではなく偏在していることを表す。従ってルーティングテーブルのキャッシュにおけるハッシュ関数としては、与えられたＩＰアドレスの部分ビット情報を集めた単純なものではなく、アドレスローカリティに対応したキャッシュのハッシュ関数が必要である。Ｍｕｌｔｉ−Ｚｏｎｅキャッシュは空間ローカリティを有効に活かすが、位置ローカリティ、アドレスローカリティに対する考慮がなされていない。
４．ハッシュの実現に実装コストや処理コストが必要である場合、Ｚｏｎｅ毎に異なるハッシュを持たせることが困難となる。特開２００１−３２０４２０はハッシュにより検索した結果はトラフィックの調整に用い、ＩＰアドレス全体のＣＲＣを求めるというハッシュでＺｏｎｅに対応していない。
５．特開２００１−３２６６７９はルーティングテーブル検索手法に対する発明で、ＵＮＩＸ（登録商標）等のファイルシステムに標準で用いられる複数回間接参照方式のｉノード方式を、ルーティングテーブル参照に適用した発明である。記憶階層下位であるファイルシステムに用いられる様に、対象が大容量（ハードディスクではギガやテラといった容量を対象としている）である場合に有効であるが反面、複数回の参照が必要であるため速度が遅いという問題がある。
【００１２】
【課題を解決するための手段】
上述した課題を解決するために、発明では次のような手段を用いる。
１．共有ルーティングテーブルを備えず、各ポートにルーティングテーブルを分散配置した構造とする。すなわち、図１２の例とは異なり、それぞれのルーティングテーブルが異なる情報の組み合わせを持つこととする。ルーティングテーブルが独自の内容を持つことができるということはローカリティを利用して各テーブルが自分の思うように最適化できるということになる。この構造をＮＵＭＡ（Ｎｏｎ−Ｕｎｉｆｏｒｍ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  ｍｏｄｅｌ）と呼ぶ。さらに、ＮＵＭＡにキャッシュを備えたＣＣ−ＮＵＭＡ（Ｃａｃｈｅ  Ｃｏｈｅｒｅｎｔ−ＮＵＭＡ）の構造とする。もしくは、各ポートにルーティングテーブルキャッシュを分散配置した構造とする。この構造をＣＯＭＡ（Ｃａｃｈｅ  Ｏｎｌｙ  Ｍｅｍｏｒｙ  Ａｒｃｈｉｔｅｃｔｕｒｅ）と呼ぶ。  具体的なルータ構成としては、複数のインタフェースを有するルータであって、複数の各インタフェースは、入力されたパケットを処理するパケット処理部と、パケットに依存する情報とパケットの宛先の組を情報として格納し、パケットに依存する情報をキーとして参照され、パケットの宛先を検索するルーティングテーブルと、を有し、第１のインタフェースのルーティングテーブルにおいて検索がヒットしなかった場合、第２のインタフェースのルーティングテーブルを参照して、宛先を検索する。この構成により、ネットワークの発展に伴うルーティングテーブルの巨大化の問題が回避できる。パケットに依存する情報とは、たとえば、ＩＰアドレスや、ＭＡＣアドレスである。
【００１３】
各ルーティングテーブルは、ルーティングテーブルの持つ情報の一部の複製を格納するルーティングテーブルキャッシュを有し、あるルーティングテーブルキャッシュにおいて検索がヒットしなかった場合、そのルーティングテーブルキャッシュに対応するルーティングテーブルを参照して、宛先を検索するＣＣ−ＮＵＭＡとしてもよい。
【００１４】
また、各ルーティングテーブルは、ルーティングテーブルキャッシュとして構成されており、パケットが到着したインタフェースにあるルーティングテーブルキャッシュにおいて検索がヒットしなかった場合、それ以外のインタフェースにあるルーティングテーブルキャッシュを参照して宛先を検索し、ヒットした場合には当該ヒットしたデータを第１のルーティングテーブルキャッシュにコピーするＣＯＭＡとしてもよい。
【００１５】
第２のルーティングテーブルが参照結果を返した場合は、参照結果を上記第１のルーティングテーブルに格納することにして、キャッシュの効果を得ることもできる。
【００１６】
また、インタフェース間で入力されたパケットを転送する第１のパスと、インタフェース間でルーティングテーブルの格納情報を転送する第２のパスを独立に有することにすれば、双方の転送速度を向上することができる。
【００１７】
さらに、ルーティングテーブルキャッシュのハッシュ関数に撹拌手段を付加し、メモリ利用効率を向上させることができる。
【００１８】
上記ルーティングテーブルの内容変更時に変更されたルーティングテーブルと同じエントリをもつ他のルーティングテーブルのエントリを無効化するか、もしくは更新メッセージにより他のインタフェースにあるルーティングテーブルに変更を通知することにしてもよい。
【００１９】
本発明の他の観点では、複数のパケット処理部と、各パケット処理部に対応して存在する複数のルーティングテーブルを有し、第１のルーティングテーブルはそれに対応する第１のパケット処理部で処理されたパケットの宛先を検索するために先に用いられ、第１のルーティングテーブルで検索がヒットしなかった場合には、第２のルーティングテーブルで検索が行われ、第２のルーティングテーブルはそれに対応する第２のパケット処理部で処理されたパケットの宛先を検索するために先に用いられ、第２のルーティングテーブルで検索がヒットしなかった場合には、第１のルーティングテーブルで検索が行われるルータを提供する。
【００２０】
また他の観点の方法では、それぞれがパケットを入力される複数のインタフェースを備えるルータのルーティング方法であって、各インタフェースは、入力されたパケットを処理するパケット処理部、入力されたパケットのアドレスに基づいて宛先を検索するためのルーティングテーブル、該ルーティングテーブルが格納するテーブルの少なくとも一部を格納するルーティングテーブルキャッシュを有することとし、あるインタフェースに入力されたパケットのアドレスに基づいて、そのインタフェースの上記ルーティングテーブルキャッシュで宛先を検索する第１のステップ、第１のステップで宛先が検索できなかったとき、当該インタフェースのルーティングテーブルで宛先を検索する第２のステップ、第２のステップで宛先が検索できなかったとき、他のインタフェースのルーティングテーブルで宛先を検索する第３のステップ、を有する。
２．ルーティングテーブルの構造をＮＵＭＡとし、各インタフェースが独自に管理する分散ルーティングテーブルを備えると、位置ローカリティを活かすことができる。結果、共有ルーティングテーブルで必要となるメモリ量よりも少ないメモリ量で済む。また、ＣＣ−ＮＵＭＡとすれば、インタフェースの自他を問わず各インタフェースが管理する内容を参照した際にもその内容をキャッシュするため、同様に位置ローカリティを有効に活かすことができ、参照速度の向上が期待できる。ルーティングテーブルの管理構造をＣＯＭＡとすると、各ルーティング情報は決まった場所に留まるのではなく、よりアクセスが頻繁に発生するところに移動するため、理想的なルーティング情報の配置が行われる。従って、管理が複雑になるが、位置ローカリティを有効に活かすことができる。
３．アドレスローカリティを有効に活かすためには、通常用いられるあるビットを単純に抽出するハッシュ関数ではなく、ビット抽出ではなく攪拌を行うハッシュ関数が必要である。例えば、ＩＰアドレスで１０．１１３．５３．１５２というアドレスについて、２進数で表記すると００００１０１０．０１１１０００１．００１１０１０１．１００１１０００となる。これを全て用いてメモリを引くと３２ビットのアドレス空間が必要となるため実装が困難である。そこで、あるビットとして４の倍数である場所にあるビットを抽出するハッシュ関数を用いると、ハッシュ値は０１０１００１１となりこの値を元にメモリを引くというハッシュが考えられる。しかしながら、アドレスのローカリティを考えるとこの様にして得られたハッシュ値は同じような値が得られる確率が高くメモリを効率利用できない。そこで攪拌手段が必要となる。複雑な攪拌はハードウエアおよび処理コストが必要となるため、単純なＣＲＣ（Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋ）の除余項を用いたハッシュ関数を用いる。また、同じキャッシュ構造を複数備えることなく、単一のキャッシュで空間ローカリティを有効に活かすために、Ｚｏｎｅ毎に異なるハッシュ構造を備えＤｕａｌ−Ｐｏｒｔメモリを利用するなどで対応する。
４．ＣＲＣは生成多項式により良い攪拌結果が得られ、変換元および変換先のｂｉｔ数を自由に取ることができ（変換後のｂｉｔ数の方が変換前のｂｉｔ数より少ない必要がある）、実装コストと処理コストが共に小さい。また、ＣＲＣは並列化が容易で高速に行うことができる。また、ＣＲＣはＩＰアドレスの攪拌ハッシュ関数として用い、ルーティングテーブルキャッシュに利用する。
５．ルーティングテーブルキャッシュを検索する際の参照は間接参照ではなく、通常のキャッシュ同様ハッシュの一回参照により求めることで高速化を図る。キャッシュの参照方式はＳｅｔ  Ａｓｓｏｃｉａｔｉｖｅとする。
本発明の一形態によれば、通信を行うルータは帯域および実時間性を保障する前記アービタとそれに付随もしくは融合された交換器を備える。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。尚、以下の実施の形態ではルータを例に用いるが、本発明は特にルータに限らず同等のローカリティが存在する場合に適用することで大容量化、低遅延化、低コスト化の効果が期待できる。
【００２２】
【実施例１】
本発明によるＣＣ−ＮＵＭＡ型ルーティングテーブル構造および動作の例を述べる。
【００２３】
図１にＣＣ−ＮＵＭＡ型ルーティングテーブルの構成例を示す。ＣＣ−ＮＵＭＡ型では、各インタフェース１０１にパケットに関する様々な処理を行うパケット処理部１０２、およびルーティングテーブルキャッシュ１０３、分散ルーティングテーブル１０４を備える。また、各インタフェースの外にパケットの交換を行うスイッチングファブリクス１０５を備える。ルーティングテーブルキャッシュ１０３を備えない場合は、ＮＵＭＡ型ルーティングテーブル構造と呼ぶ。
【００２４】
あるインタフェースが他のインタフェースにある分散ルーティングテーブル１０４（リモート分散ルーティングテーブル）を参照する場合、パケットを授受するために利用する信号線を共用する方法と、独自の信号線を別途備える方法が存在する。共用する場合はルーティングテーブル情報を交換する別のファブリクス１０６が必要とならず、新たなハードウエアコストや基板上の配線コストが削減できる。しかしながらパケットの通信とルーティング情報の通信の衝突によるバンド幅の低下が発生する可能性がある。共用しない場合は、図１に示すように別途ルーティングテーブル情報を交換するファブリクス１０６を備える。ファブリクスの例としてはクロスバやリング（双方向リング、単方向リング）などがある。
【００２５】
各インタフェースは、独自に分散ルーティングテーブルとルーティングテーブルキャッシュを備えており、キャッシュを備えることで時間ローカリティに対応する。キャッシュにより短時間に起こる複数回の同一アドレスへのアクセスはほぼ全てキャッシュにヒットし、アドレス参照の高速化が予想できるためである。また、同時に位置ローカリティに対応する。インタフェース毎に特徴あるアクセスパターンが存在する場合も、それぞれのインタフェースが独自に備える分散ルーティングテーブルやルーティングテーブルキャッシュが、該当するインタフェースのアクセスパターンに従ってエントリを最適化できると予想できるためである。
【００２６】
ルーティングテーブルキャッシュの動作は、扱うアドレスがレイヤ３のＩＰアドレスか、レイヤ２のＭＡＣアドレスかにより若干異なる。
１．レイヤ３スイッチング（レイヤ３フォワーディング）を行う場合
レイヤ３スイッチングではＩＰアドレスを用いてルーティングを行う。ＩＰアドレスは、時間ローカリティ、位置ローカリティ、空間ローカリティ、アドレスローカリティの全てが有効である。時間ローカリティ、位置ローカリティについては分散ルーティングテーブルとルーティングテーブルキャッシュにより対応する。空間ローカリティを活かすために、Ｚｏｎｅ毎に異なるＣＲＣ攪拌ハッシュを用いる。  Ｚｏｎｅ毎とは、あるｐｒｅｆｉｘ長で区切ったときその区切りよりも長いか短いかで区別して、それぞれを別のＺｏｎｅとし、異なるＣＲＣを用いた攪拌を行うというものである。ＣＲＣは実装コストが小さく高速に動作する。ＣＲＣで攪拌を行うとアドレスがランダムに分布するようになり、ＩＰアドレス空間の粗密が攪拌の結果まばらになる。従ってキャッシュの特定アドレスに登録が集中することでキャッシュ能力が低下することを防ぎ、キャッシュのアドレスに均一にアクセスするようになるので、キャッシュのメモリを有効に利用できる。
【００２７】
図２に、ルーティングテーブルキャッシュ１０３および分散ルーティングテーブル１０４のアクセスにおけるフローチャートを示す。ここではＩＰｖ４を例に示すが、ＩＰｖ６においても同様である。また、ＩＰｖ４アドレスのマスク長について、２２を境界にＺｏｎｅを区別し、２２よりも少ない場合はハッシュＡを用いてＺｏｎｅ−Ａキャッシュに，多い場合はハッシュＢを用いてＺｏｎｅ−Ｂキャッシュに登録される場合について説明する。これらの処理は、制御部１０７によりソフトウエアまたはハードウエアで制御される。
【００２８】
ＩＰアドレス１９２．１６８．３４．５６に対するアクセスがあるとすると、まずＳ２０１でＺｏｎｅ別のハッシュ値を求める。キャッシュがＤｕａｌ−Ｐｏｒｔ構成となっている場合は、２つのＺｏｎｅ別ハッシュ値を同時に検索できる。  すなわち、Ｐｒｅｆｉｘの区切りにより２つのＺｏｎｅに分ける事が出来るので、それぞれに別のハッシュ生成と検索構造を持たせる。Ｓ２０２においてルーティングテーブルキャッシュを参照する。ヒットした場合はＳ２０６において、パケットのフォワーディングを行う。ミスヒットした場合は、Ｓ２０３において同じインタフェースに存在する分散ルーティングテーブル（ローカル分散ルーティングテーブル）を参照する。ミスヒットした場合はＳ２０４において他のインタフェースの分散ルーティングテーブル（リモート分散ルーティングテーブル）を参照する。それでもミスヒットした場合は、Ｓ２０５において宛先不明時の処理を行う。具体的にはデフォルトルートにパケットをフォワーディングするか破棄する等の処理が行われる。
【００２９】
ローカル分散ルーティングテーブル、もしくはリモート分散ルーティングテーブルにヒットした場合は、Ｓ２０７においてパケットのフォワーディングが行われる。同時に、キャッシュへの登録も行われる。登録の際、宛先だけでなくマスク値も参照する。
【００３０】
インターネットではある同じＩＰアドレスのプレフィックスを持ったものを集まりとして扱う。この同じｐｒｅｆｉｘがどこまでかを指定するのがマスク値である。例えば、ＷＩＮＤＯＷＳ  ＸＰ（登録商標）やＮＴ系だと、コマンドラインからｉｐｃｏｎｆｉｇ命令を実行するとＩＰアドレスと一緒にサブネットマスクというマスク値が出てくる。また、以下でＺＯＮＥとは、このマスク値がどれだけの長さであるか、すなわちｐｒｅｆｉｘをどこまでと見るのかにより分類した概念である。
【００３１】
ヒットしたエントリが１９２．１６８．０．０／１６であった場合は、マスク長が１６で２２よりも少ないことからハッシュＡを用いてＺｏｎｅ−Ａキャッシュに１９２．１６８．３４．５６のアドレスと宛先情報が登録される。ヒットしたエントリが１９２．１６８．３４．０／２４であった場合は、マスク長が２４で２２よりも多いことからハッシュＢを用いてＺｏｎｅ−Ｂキャッシュに登録される。
２．レイヤ２スイッチングを行う場合
レイヤ２スイッチングではＭＡＣアドレスを用いてルーティングを行う。ＭＡＣアドレスは、時間ローカリティ、空間ローカリティ、アドレスローカリティが有効である。この場合の動作も図２のフローチャートを用いて説明が可能である。
【００３２】
ＭＡＣアドレスにはマスク値が存在しないためＺｏｎｅを区別しない。従って、単純にＣＲＣにより攪拌を行う。ＭＡＣアドレス００：１１：ＡＡ：２２：ＢＢ：３３に対するアクセスがある場合、まずＳ２０１においてハッシュ値を求める。Ｓ２０２においてルーティングテーブルキャッシュを参照する。ヒットした場合はＳ２０６において、パケットのフォワーディングを行う。ミスヒットすると、Ｓ２０３において同じインタフェースに存在する分散ルーティングテーブル（ローカル分散ルーティングテーブル）を参照する。ミスヒットした場合はＳ２０４において他のインタフェースの分散ルーティングテーブル（リモート分散ルーティングテーブル）を参照する。それでもミスヒットした場合は、Ｓ２０５において宛先不明時の処理を行う。具体的にはデフォルトルートにパケットをフォワーディングするか、破棄するか等の処理が行われる。
【００３３】
ローカル分散ルーティングテーブル、もしくはリモート分散ルーティングテーブルにヒットした場合は、Ｓ２０７においてパケットのフォワーディングと同時にハッシュ値に従い、ルーティングテーブルキャッシュへの登録を行う。
【００３４】
【実施例２】
本発明によるＣＣ−ＮＵＭＡ型ルーティングテーブル上で経路情報処理を行う際の手順について述べる。ＢＧＰ（Ｂｏｒｄｅｒ  Ｇａｔｅｗａｙ  Ｐｒｏｔｏｃｏｌ）やＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）等の経路情報処理を行う際、相手に自分が持っている経路情報を伝える必要があるためにルーティングテーブルを読み出す必要がある。共有ルーティングテーブル方式では該当する共有ルーティングテーブルの内容を読み出すのみでよいが、分散ルーティングテーブル方式では情報が分散しているためこれをまとめる手順が別途必要となる。そこで、次の方針を採る。経路制御処理自体は各分散ルーティングテーブルにアクセス可能な専用ハードウエアやプロセッサで処理する。
１．あるインタフェースが経路制御処理で受け取った情報は、ローカル分散ルーティングテーブルのみで管理する。従ってリモート分散ルーティングテーブルにはなんら通知を行わない。
２．あるインタフェースが経路制御処理に伴う情報を送る場合でリモート分散ルーティングテーブルの内容を必要とする際は、該当するリモート分散ルーティングテーブルの内容を取得し通知する。
【００３５】
この手順に従えば、全分散ルーティングテーブルの内容を包括した情報を入手できる。ＣＯＭＡ型ルーティングテーブルにおいても同様で、基本的にはローカルに存在するホームのみで経路情報を扱い、リモート分散ルーティングテーブルのホームを参照する必要があるときのみ、この内容を取得し通知する。
【００３６】
これらの授受の手順に合わせてキャッシュインジェクション（キャッシュの投機的登録）も可能である。キャッシュに登録される情報は完全一致であるため通常経路制御処理で交換されるマスクが付加されたアドレスを直接登録することができない。そこで、マスクされている部位に適当な値を埋め込んだもの、もしくはＩＰｖ４やＩＰｖ６においてマスクなしで指定されているアドレスをキャッシュする。
【００３７】
【実施例３】
実施例２による経路制御処理により分散ルーティングテーブルに新たなデータが加わるなどして既存データのアップデートが行われた場合には、その情報をシェアしている他のインタフェースに存在するルーティングテーブルキャッシュの内容を更新する必要がある。この手順について、各共有ルーティングテーブルのエントリにビットマップ情報を加えて管理する場合を述べる。ビットマップ情報を加えて管理する場合は管理情報が増大するが、きめ細かい管理を行うため更新時の通信量が削減できる。
【００３８】
図３は本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、ビットマップで共有状況を管理する場合の共有ルーティングテーブルおよび分散ルーティングテーブルのエントリ構造を示した構造図である。
【００３９】
図３に該当する分散ルーティングテーブルのエントリの構造例を示す。エントリにはＩＰアドレス、宛先インタフェース番号、ＱｏＳ情報、Ｓｈａｒｅｄビットマップ情報、その他パトリシア木構造等で管理するため、その管理情報やマスク値の情報といった付加情報が含まれている。ＩＰアドレスは宛先および送り先を融合した形で管理している。ＱｏＳ情報は例えば占有可能な帯域幅や、ＱｏＳのクラス（どの様な帯域保証を行うか）の情報を記載する。Ｓｈａｒｅｄビットマップ情報は、当該エントリの情報が他のインタフェースと共有されているかどうかを示しており、例えば８個のインタフェースが有り、２番目と７番目のインタフェースが同じエントリを持つ場合はＳｈａｒｅｄビットマップは０１００００１０となる。
【００４０】
図４にこの手法におけるプロトコルを示す。ルーティングテーブルキャッシュにミスヒットすると（図４の４０１）、同じインタフェースにある分散ルーティングテーブルに参照要求を出す（図４の４０２）。ヒットした場合はそのエントリのＳｈａｒｅｄビットマップについて、該当部分（同じインタフェース番号に相当する部分）をマークする。ここで、Ｓｈａｒｄとは、複数のインタフェースで同じエントリをシェアしているということを表す。
【００４１】
ミスヒットした場合は別のインタフェースに存在する分散ルーティングテーブルに対し、参照要求を出す（図４の４０３）。ある共有ルーティングテーブルにエントリが存在した場合は、そのエントリのＳｈａｒｅｄビットマップについて、該当部分（その参照要求の発行元インタフェース番号に相当する部分）をマークする（図４の４０４）。ビットマップとなっているため、どのインタフェースがキャッシュしているかを把握できる。例えば、図４においては、インタフェース１の参照要求であるため、ビットマップの１ｂｉｔ目をマークする。エントリを更新した場合は（図４の４０５）、Ｓｈａｒｅｄビットマップに従い、該当するインタフェースのルーティングテーブルキャッシュに対してＩｎｖａｌｉｄａｔｅメッセージを発行しキャッシュを無効化する（図４の４０６）。同時に、Ｓｈａｒｅｄビットマップのマークを消去する。
【００４２】
図５は本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、ホームの位置を示す情報を有するルーティングテーブルキャッシュのエントリ構造を示した構造図である。
【００４３】
図５に示すようにどのインタフェースに存在するデータをキャッシュしているのかを表すホームＩＤを管理する。キャッシュエントリを消去する場合（キャッシュエントリの追い出し等）はホームＩＤに従い、該当するインタフェースの分散ルーティングテーブルのＳｈａｒｅｄビットマップを変更し、エントリを更新しても無駄なＩｎｖａｌｉｄａｔｅメッセージを生成しないようにする。
【００４４】
ここではＩｎｖａｌｉｄａｔｅメッセージによるキャッシュの無効化について述べたが、Ｕｐｄａｔｅメッセージによるキャッシュの更新を行ってもよい。
【００４５】
【実施例４】
実施例３とは異なり、各共有ルーティングテーブルのエントリに識別子を加えて管理する場合について述べる。この手法は更新時の通信量が増大するが管理情報が少なくなる。
【００４６】
図６は本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、単一ビットで共有状況を管理する場合の分散ルーティングテーブルのエントリ構造を示した構造図である。
【００４７】
この場合の共有ルーティングテーブルのエントリの構造例を図６に示す。Ｓｈａｒｅｄビットマップではなく、Ｓｈａｒｅｄフラグを持つ。
【００４８】
図７にこの手法におけるプロトコルを示す。ルーティングテーブルキャッシュにミスヒットすると（図７の７０１）、同じインタフェースにある分散ルーティングテーブルに参照要求を出す（図７の７０２）。ヒットした場合はそのエントリのＳｈａｒｅｄフラグをマークする。ミスヒットした場合は別のインタフェースに存在する分散ルーティングテーブルに対し、参照要求を出す（図７の７０３）。ある共有ルーティングテーブルにエントリが存在した場合は、そのエントリのＳｈａｒｅｄフラグをマークする（図７の７０４）。フラグであるため、どのインタフェースがキャッシュしているかは把握できない。エントリを更新した場合は（図７の７０５）、Ｓｈａｒｅｄフラグがマークされている場合はＩｎｖａｌｉｄａｔｅメッセージをブロードキャストしてキャッシュを無効化する（図７の７０６）。Ｉｎｖａｌｉｄａｔｅメッセージを受け取ったインタフェースで該当するエントリを持つ場合はキャッシュのエントリをＩｎｖａｌｉｄａｔｅする。持たない場合は無視する。同時に、Ｓｈａｒｅｄフラグのマークを消去する。Ｓｈａｒｅｄフラグをローカルインタフェース用とリモートインタフェース用の２つ備えることで、ローカルで解決するエントリの更新についてはブロードキャストを避けることができる。
【００４９】
またルーティングテーブルキャッシュ側については、実施例３同様にどのインタフェースに存在するデータをキャッシュしているのかを表すホームＩＤを管理する。キャッシュエントリを消去する場合（キャッシュエントリの追い出し等）はホームＩＤに従い、該当するインタフェースの分散ルーティングテーブルのＳｈａｒｅｄビットマップを変更し、エントリを更新しても無駄なＩｎｖａｌｉｄａｔｅメッセージのブロードキャストを生成しないようにする。
【００５０】
ここではＩｎｖａｌｉｄａｔｅメッセージによるキャッシュの無効化について述べたが、Ｕｐｄａｔｅメッセージによるキャッシュの更新を行ってもよい。
【００５１】
【実施例５】
図８は本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、特に管理情報を持たないルーティングテーブルキャッシュのエントリ構造を示した構造図である。
【００５２】
実施例３および実施例４において、ルーティングテーブルキャッシュ側についても、図８に示すように管理情報を付加しない手法について述べる。
【００５３】
キャッシュエントリを消去する場合で実施例３と共に用いる場合は（キャッシュエントリの追い出し等）は共有ルーティングテーブルのＳｈａｒｅｄ情報の削除要求がブロードキャストされる。実施例４と共に用いる場合は、キャッシュエントリの追い出し時、特に何もしない。
【００５４】
その他、各共有ルーティングテーブル、ルーティングテーブルキャッシュに管理情報を付加しない手法も考えられる。この手法は管理情報が必要ないが、エントリを更新する場合は必ず他のインタフェースに更新内容をブロードキャストする。
【００５５】
図９に、ＣＣ−ＮＵＭＡのキャッシュレス構造としてＮＵＭＡ型ルーティングテーブルの構成例を示す。ＮＵＭＡ型のルーティングテーブルメモリは各メモリの要領削減に貢献する一方で、キャッシュを持たないため低遅延化は難しい。
【００５６】
【実施例６】
本発明によるＣＯＭＡ型ルーティングテーブル構造の例を述べる。
【００５７】
図１０にＣＯＭＡ型ルーティングテーブルの構成例を示す。ＣＯＭＡ型では、各インタフェース１０１にパケットに関する様々な処理を行うパケット処理部１０２、およびルーティングテーブルキャッシュ１０３を備える。また、各インタフェースの外にパケットの交換を行うスイッチングファブリクス１０５を備える。このスイッチングファブリクスをルーティング情報の交換に共用する場合は、ルーティングテーブル情報を交換する別のファブリクス１０６が必要とならない。共用しない場合は別途ルーティングテーブル情報を交換するファブリクス１０６を備える。
【００５８】
各インタフェースは、独自にルーティングテーブルキャッシュを備えており、このため時間ローカリティおよび位置ローカリティに対応可能である。特に、ＣＯＭＡ型の場合はＣＣ−ＭＵＭＡ型と異なり各データのホーム（あるアドレスが格納されている場所）の移動を許す。ここでデータとは即ちエントリであり、図３でいう横一列の情報の組である。ＣＣ−ＮＵＭＡ型では、各インタフェースにおける経路制御プロトコルにより分散ルーティングテーブルのエントリが設定され、このエントリ（キャッシュではなくオリジナルのエントリを特にホームと呼ぶ）が他のインタフェースの分散ルーティングテーブルに移動しない。ＣＯＭＡ型では、ホームの参照を頻繁に行うリモートルーティングテーブルキャッシュはホームをキャッシュし（これをコピーと呼ぶ）さらに同じエントリ（ホームのコピー）のアクセスを続け、逆にローカルルーティングテーブルキャッシュ（ホーム）のアクセスが滞ると、これまでホームであったエントリが追い出され、コピーがホームとなる。この様に、各エントリがより頻繁に参照されるインタフェースの近くに配置されるようになるため、エントリの配置が利用と共に最適化され結果としてアクセスコストが少なくなる。
【００５９】
この特徴を活かすため、ＣＯＭＡ型でインタフェースの数が多い場合はファブリクス１０６を階層構造とする。
【００６０】
図１１は階層構造をもつファブリクスの例であり２進木構造となっている。各枝にはディレクトリ１１０１が存在する。この２進木構造は、より大きな整数ｎを用いたｎ進木構造でも構わない。以下に、ＣＯＭＡを用いたルーティングテーブルの管理プロトコルを示す。各ディレクトリは、エントリの次の状態を保持する。
【００６１】
ａ）Ｉｎｖａｌｉｄ：該当するエントリにはデータが存在しないことを示す。略称Ｓ状態
ｂ）Ｅｘｃｌｕｓｉｖｅ：他にコピーが存在しない。略称Ｅ状態
ｃ）Ｓｈａｒｅｄ：他にコピーが存在する可能性がある。略称Ｓ状態
ｄ）Ｒｅａｄｉｎｇ：上位階層に読み出し要求を出して待ち状態である。略称Ｒ状態
ｅ）Ａｎｓｗｅｒｉｎｇ：下位階層に読み出しもしくは書き込み要求を出して待ち状態である。略称Ａ状態
ｆ）Ｗｒｉｔｉｎｇ：上位階層に書き込み要求を出して待ち状態である。略称Ｗ状態。
【００６２】
まず、読み出し時の動作について述べる。ＥおよびＳ状態のエントリは、自由に読み出しできる。読み出しにミスした場合は、該当するエントリを加えてＲ状態とし、上位ディレクトリに問い合わせる。読み出しにヒットした場合はＡ状態とし下位階層に問い合わせる。存在しない場合はＲ状態とし、さらに上位階層に問い合わせる。この動作を再帰的に繰り返すことで、やがてホームもしくはコピーにたどり着く。このエントリの情報をＲおよびＡのエントリを元に階層を戻り、各エントリをＳｈａｒｅｄ状態に変えながらアクセスがあったインタフェースまで送る。
【００６３】
次に、書き込み時、すなわち更新時の動作について述べる。Ｅ状態のエントリは自由に書き込み可能である。Ｓ状態もしくは書き込みミスの場合はホームもしくはコピーを検索しデータを更新する必要がある。Ｓ状態の場合はエントリを更新した後Ｗ状態とし、上位ディレクトリに問い合わせる。書き込みミスの場合は直接上位ディレクトリへの問い合わせを行う。その階層にエントリが存在した場合はＡ状態とし下位階層に問い合わせる。存在しない場合はＷ状態とし、さらに上位階層に問い合わせる。この動作を再帰的に繰り返すことで、ホーム、もしくはコピーにたどり着く。このエントリの情報をＷおよびＡのエントリを元に階層を戻り、Ａ状態のエントリのみＳｈａｒｅｄ状態に変えながらアクセスがあったインタフェースまで送る。ホームもしくはコピーにたどり着かず、最上位階層に達したときは自分がＥｘｃｌｕｓｉｖｅとして保持すべき情報であるため、Ｗ状態をＳ状態に変えながら階層を下り、Ｅ状態として新たにエントリを加える。
【００６４】
【実施例７】
あるインタフェースのルーティングテーブルキャッシュのエントリが一杯になり、それ以上登録できなくなった場合、次の破棄を回避する手法がある。
１．他のあいているエントリをブロードキャストで探す
ブロードキャストメッセージを用いて、他のルーティングテーブルキャッシュの空きエントリを探し移管する。空きのあるルーティングテーブルキャッシュはエントリを予約確保し、応答メッセージを返す。追加して登録できるエントリがないインタフェースは、最も早く帰ってきた応答メッセージに従ってエントリを渡す。このメッセージもブロードキャストされ、移管対象となったルーティングテーブルキャッシュはエントリを予約領域に登録し、移管対象とならなかったルーティングテーブルキャッシュは予約を解除する。
２．各インタフェースに順に移管要求を出す
ブロードキャストメッセージを用いる手法は移管作業が迅速に行える半面、ブロードキャストを用いるため通信が混雑する可能性がある。そこで、各インタフェースに順に移管要求を出し逐次確認をとる手法がある。移管作業に時間が掛かる可能性があるが、ブロードキャストメッセージを用いる必要がない。
３．メモリを別途用意し、そこに保存する。
【００６５】
ＵＭＡやＮＵＭＡ，ＣＣ−ＮＵＭＡと構造上の差異が小さいが、このメモリはあくまでもＣＯＭＡのエントリ不足を補うためのもので、スワップスペースとして利用される。
【００６６】
【発明の効果】
本発明によるＮＵＭＡ，ＣＣ−ＮＵＭＡ，ＣＯＭＡ型ルーティングメモリ管理方式を用いることにより、ルーティングテーブルメモリ量の削減が可能となる。また、ＣＣ−ＮＵＭＡ、ＣＯＭＡ型といったキャッシュを用いる方式では、各種ローカリティに対応した高速なルーティングテーブル参照を可能とする。
【００６７】
本発明によるルーティングメモリ管理方式はスケーラブルであり、特に大規模かつスループットの高いルータを構築する際に重要なものである。
【００６８】
高度情報化社会においては、通信速度においてもルーティングテーブル容量においてもより大容量のルータが必要である。この様なルータの実効スループットを制限する要因の１つである、ルーティングテーブル参照時間の増大を緩和することで性能向上を図ることが可能となる。
【図面の簡単な説明】
【図１】本発明におけるルーティングテーブルメモリの管理構造の例として、ＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造を表したブロック図である。
【図２】本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造上でアドレス検索を行う手順を示した状態遷移図である。
【図３】本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、ビットマップで共有状況を管理する場合の分散ルーティングテーブルのエントリ構造を示した構造図である。
【図４】本発明におけるビットマップを用いたＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造上で更新作業が行われた場合の処理の流れをしめしたフロー図である。
【図５】本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、ホームの位置を示す情報を有するルーティングテーブルキャッシュのエントリ構造を示した構造図である。
【図６】本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、単一ビットで共有状況を管理する場合の分散ルーティングテーブルのエントリ構造を示した構造図である。
【図７】本発明における単一ビットを用いたＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造上で更新作業が行われた場合の処理の流れをしめしたフロー図である。
【図８】本発明におけるＣＣ−ＮＵＭＡ型ルーティングテーブル管理構造について、特に管理情報を持たないルーティングテーブルキャッシュのエントリ構造を示した構造図である。
【図９】本発明におけるルーティングテーブルメモリの管理構造の例として、ＮＵＭＡ型ルーティングテーブル管理構造を表したブロック図である。
【図１０】本発明におけるルーティングテーブルメモリの管理構造の例として、ＣＯＭＡ型ルーティングテーブル管理構造を表したブロック図である。
【図１１】本発明におけるＣＯＭＡ型ルーティングテーブル管理機構における階層構造を持つファブリクスの例として、２進木構造の例を示した構造図である。
【図１２】従来のＵＭＡ型ルーティングテーブル管理機構を表したブロック図である。
【符号の説明】
１０１      インタフェース
１０２      パケット処理部
１０３      ルーティングテーブルキャッシュ
１０４      分散ルーティングテーブル
１０５      パケット交換用スイッチングファブリクス
１０６      管理情報交換用スイッチングファブリクス
Ｓ２０１    ハッシュの演算状態
Ｓ２０２    ルーティングテーブルキャッシュの参照状態
Ｓ２０３    ローカル分散ルーティングテーブルの参照状態
Ｓ２０４    リモート分散ルーティングテーブルの参照状態
Ｓ２０５    宛先不明時の処理状態
Ｓ２０６    パケットのフォワーディング状態
Ｓ２０７    パケットのフォワーディングとキャッシュ登録を行う状態
４０１      ルーティングテーブルキャッシュにミスヒットしたアクション
４０２      ローカル分散ルーティングテーブルに参照要求を出すアクション
４０３      リモート分散ルーティングテーブルに参照要求を出すアクション
４０４      Ｓｈａｒｅｄビットマップにマーキングするアクション
４０５      エントリの更新アクション
７０６      Ｉｎｖａｌｉｄａｔｅメッセージの発行アクション
７０１      ルーティングテーブルキャッシュにミスヒットしたアクション
７０２      ローカル分散ルーティングテーブルに参照要求を出すアクション
７０３      リモート分散ルーティングテーブルに参照要求を出すアクション
７０４      Ｓｈａｒｅｄフラグにマーキングするアクション
７０５      エントリの更新アクション
７０６      Ｉｎｖａｌｉｄａｔｅメッセージの発行アクション
１１０１    ディレクトリ
１２０１    ルーティングテーブル
１２０２    共有ルーティングテーブル。
【図１】
2004221807.tif 000003
【図２】
2004221807.tif 000004
【図３】
2004221807.tif 000005
【図４】
2004221807.tif 000006
【図５】
2004221807.tif 000007
【図６】
2004221807.tif 000008
【図７】
2004221807.tif 000009
【図８】
2004221807.tif 000010
【図９】
2004221807.tif 000011
【図１０】
2004221807.tif 000012
【図１１】
2004221807.tif 000013
【図１２】
2004221807.tif 000014