(57)【要約】【課題】キャッシュ検索とツリー検索とをおこなったとき、検索性能を改善する。【解決手段】制御部３は、転送制御識別情報５にもとづいてツリー検索とキャッシュ検索とを並行しておこなう。制御部３は、ツリー検索から得た検索結果６とキャッシュ検索から得た検索結果７のうち先に得た検索結果にしたがい受信データ４の転送先を決定する。制御部３は、キャッシュ検索の検索結果７がミスヒットである場合、かつキャッシュ検索がツリー検索より先に検索結果を得ることができる場合に転送制御識別情報５に対応するエントリをキャッシュデータに登録する。【選択図】図１
2018056739.tif 000002
【特許請求の範囲】
【請求項１】
受信データの転送先をツリー検索方式により検索するツリー検索に用いるツリーデータと、前記転送先をキャッシュ検索方式により検索するキャッシュ検索に用いるキャッシュデータとを記憶する記憶部と、
前記受信データに含まれる転送制御識別情報にもとづく前記ツリー検索と前記キャッシュ検索とを並行しておこない、前記ツリー検索と前記キャッシュ検索のうち先に得た検索結果にしたがい前記受信データの転送先を決定する制御部と、
を含むスイッチ。
【請求項２】
前記制御部は、前記キャッシュ検索の検索結果がミスヒットである場合、かつ前記転送制御識別情報にもとづく前記キャッシュ検索が前記転送制御識別情報にもとづく前記ツリー検索より先に検索結果を得ることができる場合に前記転送制御識別情報に対応するエントリを前記キャッシュデータに登録する、
請求項１に記載のスイッチ。
【請求項３】
前記記憶部は、あらかじめ設定する閾値を記憶し、
前記制御部は、前記転送制御識別情報にもとづく前記ツリー検索のノード数が前記閾値よりも大きいときに、前記転送制御識別情報にもとづく前記キャッシュ検索が前記転送制御識別情報にもとづく前記ツリー検索より先に検索結果を得ることができると評価する、
請求項２に記載のスイッチ。
【請求項４】
前記記憶部は、動的に更新される閾値を記憶し、
前記制御部は、前記転送制御識別情報にもとづく前記ツリー検索のノード数と前記キャッシュ検索に用いた前記転送制御識別情報に対応するノード数との比較結果にもとづいて前記閾値を更新し、
前記転送制御識別情報にもとづく前記ツリー検索のノード数が前記閾値よりも大きいときに、前記転送制御識別情報にもとづく前記キャッシュ検索が前記転送制御識別情報にもとづく前記ツリー検索より先に検索結果を得ることができると評価する、
請求項２に記載のスイッチ。
【請求項５】
前記制御部は、前記転送制御識別情報にもとづく前記ツリー検索のノード数が、前記キャッシュ検索でミスヒットした前記転送制御識別情報に対応するノード数よりも大きいときに、前記転送制御識別情報にもとづく前記キャッシュ検索が前記転送制御識別情報にもとづく前記ツリー検索より先に検索結果を得ることができると評価する、
請求項２に記載のスイッチ。
【請求項６】
前記キャッシュデータは、前記転送制御識別情報のハッシュ値と、前記転送制御識別情報に対応するノード数とを含み、
前記制御部は、前記転送制御識別情報に対応するエントリを前記キャッシュデータに登録するときに前記転送制御識別情報のハッシュ値が重複するエントリがある場合、重複するエントリのうち前記ノード数が大きなエントリを前記キャッシュデータに登録し、前記ノード数が小さなエントリを前記キャッシュデータに非登録とする、
請求項２乃至請求項５のいずれか１項に記載のスイッチ。
【請求項７】
前記キャッシュデータは、さらに前記転送制御識別情報ごとの通信帯域に関する帯域情報を含み、
前記制御部は、前記転送制御識別情報に対応するエントリを前記キャッシュデータに登録するときに前記転送制御識別情報のハッシュ値が重複するエントリがある場合、重複するエントリのうち前記帯域情報により特定される前記通信帯域が大きなエントリを前記キャッシュデータに登録し、前記通信帯域が小さなエントリを前記キャッシュデータに非登録とする、
請求項６に記載のスイッチ。
【請求項８】
受信データの転送先をツリー検索方式により検索するツリー検索に用いるツリーデータと、前記転送先をキャッシュ検索方式により検索するキャッシュ検索に用いるキャッシュデータとを記憶する記憶部と、制御部とを含むスイッチの通信方法であって、
前記制御部は、
前記受信データに含まれる転送制御識別情報にもとづく前記ツリー検索と前記キャッシュ検索とを並行しておこない、前記ツリー検索と前記キャッシュ検索のうち先に得た検索結果にしたがい前記受信データの転送先を決定する、
通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スイッチ、および通信方法に関する。
【背景技術】
【０００２】
インターネットやＶＰＮ（Virtual Private Network）に接続するネットワーク環境においては、Ｌ２ＳＷ（Layer 2 Switch）やＬ３ＳＷ、ルータ、ＯｐｅｎＦｌｏｗＳＷなどのパケットスイッチが広く利用されている。
【０００３】
パケットスイッチは、受信したパケットに含まれるＩＰ（Internet Protocol）アドレス等にもとづいてテーブルを検索してパケットごとの処理内容を決定する。パケットスイッチは、決定した処理内容にしたがい、ＶＬＡＮ（Virtual Local Area Network）タグの付与や転送先の決定等をおこない、パケットを送信する。
【０００４】
このようなパケットスイッチは、近年のＳＤＮ（Software Defined Network）／ＮＦＶ（Network Function Virtualization）のトレンドに伴い、仮想化／ソフト化が求められている。たとえば、パケットスイッチは、ソフトウェア処理によるツリー検索やキャッシュ検索等で、ＩＰアドレスをキーにしたテーブル検索をおこなう。
【０００５】
キャッシュ検索は、キャッシュデータとして登録してあるエントリの数によらずに検索時間をほぼ一定にすることができるが、ハッシュ関数の演算に所要の処理時間を有する。また、キャッシュ検索は、キャッシュデータとして未登録のエントリについて検索結果を得ることができない。また、キャッシュ検索は、古いエントリを新しいエントリに置き換えるため、一旦登録されたエントリでも運用過程で未登録のエントリとなり得る。
【０００６】
一方、ツリー検索は、検索結果を得るまでにたどったツリーの分岐ポイントの数が増大するにしたがい検索時間が増大する。そのため、ツリー検索は、キャッシュ検索と比較して、分岐ポイントの数が小さいときに検索時間が小さく、分岐ポイントの数が大きいときに検索時間が大きくなる。
【０００７】
したがって、ツリー検索における検索時間は、ツリー検索における分岐ポイントの数と、キャッシュ検索におけるキャッシュデータ次第で、キャッシュ検索における検索時間より長くもなるし短くもなる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１３−４２３２０号公報
【特許文献２】特開２００１−１６８９１０号公報
【特許文献３】特開平１１−２３２２８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、キャッシュ検索とツリー検索とを並行しておこなったとき、キャッシュ検索は、ツリー検索より速いと見込まれる場合であっても、キャッシュにおいてエントリが未登録のために検索結果を得られない場合がある。また、キャッシュ検索とツリー検索とを直列でおこなう検索方法は、先にキャッシュ検索をおこない、キャッシュ検索で検索結果を得られない場合にツリー検索をおこなうことから、キャッシュにおいてエントリが未登録の場合に検索時間が大きくなる。
【００１０】
１つの側面では、本発明は、キャッシュ検索とツリー検索とをおこなったとき、検索性能を改善できるスイッチ、および通信方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、以下に示すような、スイッチが提供される。スイッチは、記憶部と、制御部とを含む。記憶部は、受信データの転送先をツリー検索方式により検索するツリー検索に用いるツリーデータと、転送先をキャッシュ検索方式により検索するキャッシュ検索に用いるキャッシュデータとを記憶する。制御部は、受信データに含まれる転送制御識別情報にもとづくツリー検索とキャッシュ検索とを並行しておこない、ツリー検索とキャッシュ検索のうち先に得た検索結果にしたがい受信データの転送先を決定する。
【００１２】
また、上記目的を達成するために、以下に示すような、スイッチの通信方法が提供される。スイッチは、記憶部と、制御部とを含む。記憶部は、受信データの転送先をツリー検索方式により検索するツリー検索に用いるツリーデータと、転送先をキャッシュ検索方式により検索するキャッシュ検索に用いるキャッシュデータとを記憶する。制御部は、受信データに含まれる転送制御識別情報にもとづくツリー検索とキャッシュ検索とを並行しておこない、ツリー検索とキャッシュ検索のうち先に得た検索結果にしたがい受信データの転送先を決定する。
【発明の効果】
【００１３】
１態様によれば、スイッチ、および通信方法において、キャッシュ検索とツリー検索とをおこなったとき、検索性能を改善できる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施形態のスイッチの構成の一例を示す図である。
【図２】第２の実施形態のネットワークシステムの構成の一例を示す図である。
【図３】第２の実施形態のＬ２ＳＷのハードウェア構成の一例を示す図である。
【図４】第２の実施形態のＬ２ＳＷの機能構成の一例を示す図である。
【図５】第２の実施形態のパケット転送過程の一例を示す図である。
【図６】第２の実施形態のツリーテーブルの一例を示す図である。
【図７】第２の実施形態のキャッシュテーブルの一例を示す図である。
【図８】第２の実施形態のツリー検索の検索時間とキャッシュ検索の検索時間との比較例を示す図である。
【図９】第２の実施形態の検索処理のフローチャートを示す図である。
【図１０】第２の実施形態の受信済ノード数管理表の一例を示す図である。
【図１１】第３の実施形態の検索処理のフローチャートを示す図である。
【図１２】第３の実施形態のキャッシュ使用閾値判定表更新処理のフローチャートを示す図である。
【図１３】第３の実施形態のキャッシュ使用閾値判定表の一例（その１）を示す図である。
【図１４】第３の実施形態のキャッシュ使用閾値判定表の一例（その２）を示す図である。
【図１５】第３の実施形態のキャッシュ使用閾値判定表の一例（その３）を示す図である。
【図１６】第３の実施形態のキャッシュ使用閾値判定表の一例（その４）を示す図である。
【図１７】第４の実施形態の検索処理のフローチャートを示す図である。
【図１８】第４の実施形態のキャッシュ登録判定例を示す図である。
【図１９】第５の実施形態のキャッシュ登録処理のフローチャートを示す図である。
【図２０】第５の実施形態のキャッシュテーブルの一例（その１）を示す図である。
【図２１】第５の実施形態のキャッシュテーブルの一例（その２）を示す図である。
【図２２】第６の実施形態のＬ２ＳＷの機能構成の一例を示す図である。
【図２３】第６の実施形態のキャッシュ登録処理のフローチャートを示す図である。
【図２４】第６の実施形態のキャッシュテーブルの一例（その１）を示す図である。
【図２５】第６の実施形態のキャッシュテーブルの一例（その２）を示す図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して実施形態を詳細に説明する。
［第１の実施形態］
まず、第１の実施形態のスイッチについて図１を用いて説明する。図１は、第１の実施形態のスイッチの構成の一例を示す図である。
【００１６】
スイッチ１は、受信データ４を転送するデータ転送装置である。たとえば、スイッチ１は、ＩＰパケットを転送対象データとするパケットスイッチ（パケット転送装置）である。スイッチ１は、より具体的にはＬ２ＳＷやＬ３ＳＷ、ルータ、ＯｐｅｎＦｌｏｗＳＷなどであってもよい。
【００１７】
スイッチ１は、記憶部２と、制御部３とを含む。記憶部２は、ツリーデータ２ａと、キャッシュデータ２ｂとを記憶する。ツリーデータ２ａは、受信データ４の転送先をツリー検索方式により検索するツリー検索に用いられるデータである。なお、ツリーデータ２ａは、ツリー検索に先立ってあらかじめ用意されるデータである。
【００１８】
キャッシュデータ２ｂは、受信データ４の転送先をキャッシュ検索方式により検索するキャッシュ検索に用いられるデータである。なお、キャッシュデータ２ｂは、キャッシュ検索の結果にしたがい更新されるデータである。
【００１９】
制御部３は、転送制御識別情報５にもとづいてツリー検索とキャッシュ検索とを並行しておこなう。すなわち、制御部３は、転送制御識別情報５を検索キーとしてツリー検索をおこなうとともに、転送制御識別情報５を検索キーとしてキャッシュ検索をおこなう。
【００２０】
転送制御識別情報５は、受信データ４に含まれる。転送制御識別情報５は、受信データ４の転送制御に用いられる識別情報である。転送制御は、たとえば転送先の決定がある。転送制御識別情報５は、たとえば、ＩＰパケットに含まれる宛先ＩＰアドレスやＥｔｈｅｒｎｅｔ（登録商標）フレームに含まれるＭＡＣ（Media Access Control）アドレス等がある。
【００２１】
制御部３は、ツリー検索から得た検索結果６とキャッシュ検索から得た検索結果７のうち先に得た検索結果にしたがい受信データ４の転送先を決定する。たとえば、制御部３は、キャッシュ検索より先にツリー検索から検索結果６を得た場合、検索結果６にしたがい受信データ４の転送先を決定する。また、制御部３は、ツリー検索より先にキャッシュ検索から検索結果７を得た場合、検索結果７にしたがい受信データ４の転送先を決定する。
【００２２】
なお、制御部３は、ツリー検索から検索結果６を得て（検索ヒット）、キャッシュ検索から検索結果７を得られなかった（検索ミスヒット）場合、検索結果６にしたがい受信データ４の転送先を決定する。以下、検索ヒットを単にヒットと称し、検索ミスヒットを単にミスヒットと称する場合がある。また、制御部３は、ツリー検索から検索結果６を得られなかった場合、ミスヒット処理をおこなう。
【００２３】
制御部３は、キャッシュ検索がミスヒットした場合に検索結果６（ヒット）と検索結果７（ミスヒット）とからキャッシュデータの登録の是非を判定する。制御部３は、キャッシュ検索がミスヒットした場合に一律にキャッシュデータの登録をおこなうと、新たに追加したエントリに代わって古いエントリを削除する場合がある。これは、キャッシュ検索性能を改善する場合があるが、並行しておこなうツリー検索との関係でスイッチ１としてみた場合、検索性能を損なうおそれがある。
【００２４】
つまり、キャッシュ検索の検索時間がツリー検索の検索時間よりも長い検索キーについてキャッシュデータ２ｂの登録をおこなうと、キャッシュ検索は次回以降の検索でミスヒットしなくなるもののツリー検索よりも検索時間がかかるため検索結果が選択されない。すなわち、キャッシュ検索の検索時間がツリー検索の検索時間よりも長い検索キーのキャッシュデータ２ｂへの登録は、スイッチ１としての検索時間の短縮に寄与しない。さらに、キャッシュ検索の検索時間がツリー検索の検索時間よりも長い検索キーのキャッシュデータ２ｂへの登録は、キャッシュ検索の検索時間がツリー検索の検索時間よりも短い検索キーをキャッシュデータ２ｂから削除する場合がある。このようなキャッシュデータ２ｂの更新は、スイッチ１としての検索時間を大きくする。
【００２５】
そこで、制御部３は、キャッシュ検索の検索結果がミスヒットである場合、かつキャッシュ検索がツリー検索より先に検索結果を得ることができる場合に転送制御識別情報５に対応するエントリをキャッシュデータに登録する。言い換えれば、制御部３は、キャッシュ検索の検索結果がミスヒットである場合、キャッシュ検索がツリー検索より先に検索結果を得ることができる見込みのないエントリをキャッシュデータに登録しない。
【００２６】
これにより、キャッシュデータ２ｂは、キャッシュ検索がツリー検索より先に検索結果を得ることができないエントリに優先して、キャッシュ検索がツリー検索より先に検索結果を得ることができるエントリを登録することができる。
【００２７】
したがって、制御部３は、キャッシュ検索がツリー検索より先に検索結果を得ることができるときに、キャッシュ検索のヒット率を向上することができる。これにより、スイッチ１は、キャッシュ検索とツリー検索とをおこなったとき、キャッシュ検索性能を改善し、ひいては全体的な検索性能を改善できる。たとえば、スイッチ１は、キャッシュ検索とツリー検索とを並行しておこなったときに、キャッシュ検索性能を改善することができる。また、スイッチ１は、先にキャッシュ検索をおこない、キャッシュ検索で検索結果を得られない場合にツリー検索をおこなう検索方法と比較して、キャッシュ検索性能を改善することができる。
【００２８】
［第２の実施形態］
次に、第２の実施形態のネットワークシステムについて図２を用いて説明する。図２は、第２の実施形態のネットワークシステムの構成の一例を示す図である。
【００２９】
ネットワークシステム１０は、ＶＰＮコアＮＷ１１や、ＩＳＰ１２、コア・メトロＮＷ１４などの複数のネットワークと、端末装置１８，１９，２２，２３，２５，２６などの複数の端末装置を含む。ネットワークシステム１０は、さらにルータ１３，１５，１７，２１，２４や、Ｌ２ＳＷ１６，２０などのデータ転送装置（スイッチ）を含み、複数のネットワークと複数の端末装置を接続する。
【００３０】
これにより、ネットワークシステム１０は、インターネットやＶＰＮへの接続環境を提供する。このとき、データ転送装置は、受信したＩＰパケットの転送先を決定し、決定した転送先に受信したＩＰパケットを送信することをおこなう。データ転送装置は、ＩＰパケットを高速に転送することで、高速なネットワーク通信環境の構築に貢献する。
【００３１】
次に、データ転送装置のハードウェア構成と機能構成について、代表してＬ２ＳＷ２０を一例に挙げて説明する。まず、Ｌ２ＳＷ２０のハードウェア構成について図３を用いて説明する。図３は、第２の実施形態のＬ２ＳＷのハードウェア構成の一例を示す図である。
【００３２】
Ｌ２ＳＷ２０は、プロセッサ１００によって装置全体が制御されている。すなわち、プロセッサ１００は、Ｌ２ＳＷ２０の制御部として機能する。プロセッサ１００には、バス１０３を介してメモリ１０１と複数の周辺機器が接続されている。プロセッサ１００は、マルチプロセッサであってもよい。プロセッサ１００は、たとえばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、またはＰＬＤ（Programmable Logic Device）である。またプロセッサ１００は、ＣＰＵ、ＭＰＵ、ＤＳＰ、ＡＳＩＣ、ＰＬＤのうちの２以上の要素の組み合わせであってもよい。
【００３３】
メモリ１０１は、Ｌ２ＳＷ２０の主記憶装置として使用される。メモリ１０１には、プロセッサ１００に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０１には、プロセッサ１００による処理に必要な各種データが格納される。
【００３４】
また、メモリ１０１は、Ｌ２ＳＷ２０の補助記憶装置としても使用され、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。メモリ１０１は、補助記憶装置として、フラッシュメモリやＳＳＤ（Solid State Drive）などの半導体記憶装置やＨＤＤ（Hard Disk Drive）などの磁気記録媒体を含んでもよい。
【００３５】
バス１０３に接続されている周辺機器としては、入出力インタフェース１０２、およびネットワークインタフェース１０４，１０５，１０６，１０７がある。
入出力インタフェース１０２は、プロセッサ１００からの命令にしたがってＬ２ＳＷ２０の状態を表示する表示装置として機能するモニタ（たとえばＬＥＤ（Light Emitting Diode）やＬＣＤ（Liquid Crystal Display）など）が接続されている。また、入出力インタフェース１０２は、キーボードやマウスなどの情報入力装置を接続可能であって、情報入力装置から送られてくる信号をプロセッサ１００に送信する。
【００３６】
また、入出力インタフェース１０２は、周辺機器を接続するための通信インタフェースとして機能する。たとえば、入出力インタフェース１０２は、レーザ光などを利用して、光ディスクに記録されたデータの読み取りをおこなう光学ドライブ装置を接続することができる。光ディスクは、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００３７】
また、入出力インタフェース１０２は、メモリ装置やメモリリーダライタを接続することができる。メモリ装置は、入出力インタフェース１０２との通信機能を搭載した記録媒体である。メモリリーダライタは、メモリカードへのデータの書き込み、またはメモリカードからのデータの読み出しをおこなう装置である。メモリカードは、カード型の記録媒体である。
【００３８】
ネットワークインタフェース１０４，１０５，１０６，１０７は、データの転送元や転送先となる通信機器との間でデータの送受信をおこなう。たとえば、ネットワークインタフェース１０４，１０５，１０６，１０７は、それぞれ送信ポートに対応する。
【００３９】
以上のようなハードウェア構成によって、Ｌ２ＳＷ２０は、第２の実施形態の処理機能を実現することができる。たとえば、Ｌ２ＳＷ２０は、プロセッサ１００がそれぞれ所定のプログラムを実行することでデータ転送装置として機能し、データ転送をおこなうことができる。
【００４０】
Ｌ２ＳＷ２０は、たとえば、コンピュータで読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施形態の処理機能を実現する。Ｌ２ＳＷ２０に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。たとえば、Ｌ２ＳＷ２０に実行させるプログラムを補助記憶装置に格納しておくことができる。プロセッサ１００は、補助記憶装置内のプログラムの少なくとも一部を主記憶装置にロードし、プログラムを実行する。またＬ２ＳＷ２０に実行させるプログラムを、光ディスク、メモリ装置、メモリカードなどの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、たとえばプロセッサ１００からの制御により、補助記憶装置にインストールされた後、実行可能となる。またプロセッサ１００が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００４１】
次に、Ｌ２ＳＷ２０の機能構成について図４を用いて説明する。図４は、第２の実施形態のＬ２ＳＷの機能構成の一例を示す図である。
Ｌ２ＳＷ２０は、受信部３１と、検索キー抽出部３２と、検索部３３と、アクション処理部３４と、送信部３５とを含む。受信部３１は、パケット（ＩＰパケット）３０を受信する。検索キー抽出部３２は、パケット３０から検索キー（第１の実施形態の転送制御識別情報５に相当）を抽出する。検索キー抽出部３２は、抽出した検索キーを検索部３３に出力するとともに、パケット３０をアクション処理部３４に出力する。
【００４２】
検索部３３は、入力した検索キーにもとづく検索をおこない、検索結果をアクション処理部３４に出力する。検索部３３は、ツリー検索部３６と、キャッシュ検索部３７と、検索結果選択部３８と、キャッシュ管理部３９とを含む。ツリー検索部３６は、検索キーを用いてツリー検索方式によるツリーテーブルの検索をおこなう。キャッシュ検索部３７は、検索キーを用いてキャッシュ検索方式によるキャッシュテーブルの検索をおこなう。
【００４３】
検索結果選択部３８は、ツリー検索部３６から得られた検索結果とキャッシュ検索部３７から得られた検索結果のうち、より先に得られた検索結果を選択してアクション処理部３４に出力する。なお、検索結果選択部３８は、キャッシュ検索部３７がミスヒットした場合、ツリー検索部３６から得られた検索結果を選択してアクション処理部３４に出力する。また、検索結果選択部３８は、ツリー検索部３６とキャッシュ検索部３７のいずれもがミスヒットした場合、ミスヒット処理をおこなう。キャッシュ管理部３９は、ツリー検索部３６から得られた検索結果とキャッシュ検索部３７から得られた検索結果とにもとづいてキャッシュテーブルを更新する。
【００４４】
アクション処理部３４は、検索結果にしたがいパケット３０に対応するアクション処理をおこない、送信部３５にパケット３０を出力する。アクション処理部３４がおこなうアクション処理は、たとえば、転送やＶＬＡＮタグの付与などがある。また、アクション処理は、データ転送装置の種別（たとえばルータなど）に応じて、パケットフィルタリングや、アドレス変換などを含む。送信部３５は、アクション処理にしたがった転送先にパケット３０を送信する。
【００４５】
ここで、パケット転送過程について図５を用いて説明する。図５は、第２の実施形態のパケット転送過程の一例を示す図である。
Ｌ２ＳＷ２０は、パケット１１０を受信する。パケット１１０は、宛先ＭＡＣアドレス（Ｌ２ＳＷ２０のＭＡＣアドレス）と、宛先ＩＰアドレスと、ペイロードとを含む。Ｌ２ＳＷ２０は、宛先ＩＰアドレスを検索キーとして抽出する。Ｌ２ＳＷ２０は、宛先ＩＰアドレスを検索キーにしてテーブル検索をおこなう。ここでいうテーブル検索は、ツリー検索とキャッシュ検索の並行検索をいう。Ｌ２ＳＷ２０は、検索結果にもとづくアクション処理をおこなう。たとえば、Ｌ２ＳＷ２０は、ＶＬＡＮタグの付加や、宛先ＭＡＣアドレス（転送先のＭＡＣアドレス）の付け替えをおこないパケット１２０を生成する。Ｌ２ＳＷ２０は、パケット１２０を転送先に送信する。
【００４６】
次に、ツリーテーブルについて図６を用いて説明する。図６は、第２の実施形態のツリーテーブルの一例を示す図である。
ツリーテーブル２００は、ツリー検索においてあらかじめ用意されるデータであり、メモリ１０１に記憶される。ツリーテーブル２００は、フォワーディングテーブルの一態様であり、宛先ＩＰアドレス（検索キー）のビットパターンにしたがって分岐するツリー構造を有する。たとえば、ツリーテーブル２００は、ＩＰアドレスのＭＳＢ（Most Significant Bit）側から共通の値ごとにマージしたツリー構造を有する。なお、説明を簡単にするために、ＩＰｖ４で３２ビットのＩＰアドレスを８ビットとして説明する。
【００４７】
ツリーテーブル２００は、５つのエントリを有し、それぞれ検索キーを「００００００００」、「０００００００１」、「００００００１０」、「００００００１１」、「０００００１１１」とする。各検索キーには、処理（アクション処理）が対応付けられていて、対応する処理を検索結果とする。たとえば、検索キー「００００００００」は、処理Ａが対応付けられ、検索キー「０００００１１１」は、処理Ｅが対応付けられている。
【００４８】
検索キー「００００００００」，「０００００００１」，「００００００１０」，「００００００１１」は、起点と終点を含む５つの分岐点を有する。検索キー「０００００１１１」は、３つの分岐点を有する。以下、分岐点の数をノード数と称する。
【００４９】
ツリー検索部３６は、ＭＳＢ側からビットの値にしたがって分岐点ごとに分岐先を決定しながらツリーをたどることから、ノード数が多い検索キーほど検索時間を要する。たとえば、ツリー検索部３６は、検索キー「００００００００」がノード数「５」（検索ルートＡ）であり、検索キー「０００００１１１」がノード数「３」（検索ルートＢ）であることから、検索キー「０００００１１１」よりも検索キー「００００００００」に検索時間を要する。
【００５０】
これにより、Ｌ２ＳＷ２０は、ツリー検索におけるノード数と検索時間とに対応関係があることから、ノード数を比較することによって検索時間の比較をおこなうことができる。また、Ｌ２ＳＷ２０は、キャッシュ検索の検索時間がほぼ一定であることから、キャッシュ検索で用いた検索キーに対応するノード数と、ツリー検索におけるノード数とを比較してキャッシュ検索とツリー検索との検索時間の比較をおこなうことができる。
【００５１】
次に、キャッシュテーブルについて図７を用いて説明する。図７は、第２の実施形態のキャッシュテーブルの一例を示す図である。
キャッシュテーブル２１０は、キャッシュ検索において更新されるデータであり、メモリ１０１に記憶される。キャッシュテーブル２１０は、フォワーディングテーブルの一態様であり、宛先ＩＰアドレス（検索キー）のハッシュ値をインデックスとするテーブルデータ構造を有する。たとえば、キャッシュテーブル２１０は、項目「ハッシュ値」と、項目「宛先ＩＰアドレス」と、項目「処理」を含む。
【００５２】
項目「ハッシュ値」は、宛先ＩＰアドレス（検索キー）を入力値としたときのハッシュ演算の結果を示す。たとえば、検索キー「００００００００」は、ハッシュ値「３」であり、検索キー「０００００１１１」は、ハッシュ値「９」である。
【００５３】
キャッシュ検索部３７は、ハッシュ式全ビット一致検索（ＥＭ（Exact Match）−ＨＡＳＨ）をおこなう。キャッシュ検索部３７は、宛先ＩＰアドレスをハッシュ演算して得たハッシュ値をインデックスにしてキャッシュテーブル２１０を検索する。
【００５４】
キャッシュテーブル２１０は、キャッシュ検索部３７がミスヒットしたときに、新しいエントリが追加される。なお、キャッシュテーブル２１０は、所定数のエントリを有し、新しいエントリが追加登録されると古いエントリが削除される。
【００５５】
各ハッシュ値には、宛先ＩＰアドレスと処理（アクション処理）が対応付けられていて、対応する処理を検索結果とする。たとえば、ハッシュ値「３」は、宛先ＩＰアドレス「００００００００」と処理Ａが対応付けられ、ハッシュ値「９」は、宛先ＩＰアドレス「０００００１１１」と処理Ｅが対応付けられている。
【００５６】
次に、ツリー検索の検索時間とキャッシュ検索の検索時間について図８を用いて説明する。図８は、第２の実施形態のツリー検索の検索時間とキャッシュ検索の検索時間との比較例を示す図である。
【００５７】
キャッシュ検索部３７は、ハッシュ演算をおこなうためツリー検索部３６よりも検索時間を要する場合があるが、エントリ数に依存することなくほぼ一定の検索時間で検索結果を得ることができる。
【００５８】
一方、ツリー検索は、ノード数に応じて検索時間が増大するという特性がある。そのため、ツリー検索は、ノード数が閾値Ｔｎより小さいとき検索時間がキャッシュ検索より小さく、ノード数が閾値Ｔｎより大きいとき検索時間がキャッシュ検索より大きい。
【００５９】
そのため、Ｌ２ＳＷ２０は、キャッシュ検索とツリー検索を並行して実行するとき、ノード数が閾値Ｔｎより大きい検索キーでのキャッシュ検索におけるヒット率を向上させることで検索時間を改善する。
【００６０】
次に、キャッシュ検索においてヒット率を向上させる検索処理について図９を用いて説明する。図９は、第２の実施形態の検索処理のフローチャートを示す図である。
検索処理は、キャッシュ検索とツリー検索を並行して実行し、検索結果を得る処理である。検索処理は、検索部３３によって実行される処理である。
【００６１】
［ステップＳ１１］検索部３３は、受信パケットから検索キー（宛先ＩＰアドレス）を抽出する。
［ステップＳ１２］検索部３３は、検索キーを用いてツリー検索とキャッシュ検索を並行処理する。たとえば、検索部３３は、マルチコアＣＰＵを用いるなどして、ツリー検索とキャッシュ検索を同時に実行する。
【００６２】
［ステップＳ１３］検索部３３は、ツリー検索とキャッシュ検索のいずれかが検索ヒット（検索結果がヒット）したか否かを判定する。検索部３３は、ツリー検索とキャッシュ検索のいずれかが検索ヒットした場合にステップＳ１４にすすみ、いずれも検索ヒットしない（ミスヒットした）場合にステップＳ１７にすすむ。
【００６３】
［ステップＳ１４］検索部３３は、ツリー検索がヒットしたか否かを判定する。検索部３３は、ツリー検索がヒットした場合にステップＳ１５にすすみ、ツリー検索がヒットしていない場合、すなわちキャッシュ検索がヒットした場合にステップＳ１６にすすむ。
【００６４】
［ステップＳ１５］検索部３３は、ツリー検索結果でヒット処理をおこなう。すなわち、検索部３３は、ツリー検索による検索結果をアクション処理部３４に出力する。
［ステップＳ１６］検索部３３は、キャッシュ検索結果でヒット処理をおこなう。すなわち、検索部３３は、キャッシュ検索による検索結果をアクション処理部３４に出力する。
【００６５】
これにより、検索部３３は、ツリー検索とキャッシュ検索のうちからより先に得た検索結果を用いてヒット処理をおこなうことができる。
［ステップＳ１７］検索部３３は、キャッシュ検索がミスヒットしたか否かを判定する。検索部３３は、キャッシュ検索がミスヒットした場合にステップＳ１８にすすみ、キャッシュ検索がミスヒットしていない場合にステップＳ２１にすすむ。
【００６６】
［ステップＳ１８］検索部３３は、受信済ノード数管理表を用いて検索キーのノード数が受信済（検索済）か否かを判定する。検索部３３は、検索キーのノード数が受信済である場合にステップＳ１９にすすみ、検索キーのノード数が受信済でない場合にステップＳ２０にすすむ。
【００６７】
なお、受信済ノード数管理表は、ノード数ごとにデータを受信済であるか否かを管理する表である。また、検索部３３は、キャッシュ検索に用いた検索キーのノード数を、ツリー検索結果より取得することができる。受信済ノード数管理表については、後で図１０を用いて説明する。
【００６８】
［ステップＳ１９］検索部３３は、検索キーのノード数があらかじめ設定する閾値より大きいか否かを判定する。検索部３３は、検索キーのノード数が閾値より大きい場合にステップＳ２０にすすみ、検索キーのノード数が閾値より大きくない（小さい）場合にステップＳ２１にすすむ。なお、閾値は、経験値あるいは設計値などを用いて事前に設定される値であり、メモリ１０１に記憶される。
【００６９】
［ステップＳ２０］検索部３３は、キャッシュ登録処理を実行する。キャッシュ登録処理は、検索キーに対応するエントリをキャッシュテーブル２１０に登録する処理である。また、第２の実施形態において、検索部３３は、キャッシュ登録処理において受信済ノード数管理表を更新する。すなわち、検索部３３は、受信済ノード数管理表において検索キーのノード数が未受信であったときに受信済に更新する。
【００７０】
このようにして、検索部３３は、検索キーのノード数が未受信であった場合、検索キーに対応するエントリをキャッシュテーブル２１０に登録する。また、検索部３３は、検索キーのノード数が受信済であった場合、検索キーのノード数が閾値より大きいときに検索キーに対応するエントリをキャッシュテーブル２１０に登録する。
【００７１】
これにより、検索部３３は、キャッシュ検索において、ツリー検索より先に検索結果を得られるときの検索ヒット率を改善することができる。一方で、検索部３３は、キャッシュ検索において、ツリー検索より後に検索結果を得られるときの検索ヒット率を低下させる場合がある。しかしながら、検索部３３は、ツリー検索とキャッシュ検索のうちからより先に得た検索結果を用いてヒット処理をおこなうことから、ツリー検索より後に検索結果を得られるときの検索ヒット率の低下は問題にならない。結果として、検索部３３は、ツリー検索とキャッシュ検索を並行しておこなうときの検索性能を改善する。
【００７２】
［ステップＳ２１］検索部３３は、ツリー検索とキャッシュ検索のいずれもが検索ミスヒット（検索結果がミスヒット）したか否かを判定する。検索部３３は、ツリー検索とキャッシュ検索のいずれもが検索ミスヒットした場合にステップＳ２２にすすみ、いずれかが検索ヒットしている場合に検索処理を終了する。
【００７３】
［ステップＳ２２］検索部３３は、ミスヒット処理を実行し、検索処理を終了する。
次に、受信済ノード数管理表について図１０を用いて説明する。図１０は、第２の実施形態の受信済ノード数管理表の一例を示す図である。
【００７４】
受信済ノード数管理表２２０は、ノード数ごとにデータを受信済であるか否かを管理する表である。受信済ノード数管理表２２０は、項目「ノード数」と、項目「受信済フラグ」を含む。項目「ノード数」は、ツリー検索における検索キーに対応するノード数を示す。たとえば、項目「ノード数」は、ツリー検索が８ビットの検索をおこなうとき「１」から「８」までの８つのレコードを有する。項目「受信済フラグ」は、ノード数ごとのデータ受信の有無、言い換えればノード数ごとの検索キーの検索の有無を示す。項目「受信済フラグ」は、初期状態としてすべてのレコードで「０（＝未受信）」であり。データ受信ごとに「１（＝受信済）」に更新される。
【００７５】
たとえば、受信済ノード数管理表２２０は、ノード数「１」，「２」，「４」，「６」，「７」，「８」がデータ未受信であり、ノード数「３」，「５」がデータ受信済であることを示す。
【００７６】
検索部３３は、受信済ノード数管理表２２０を用いることで、データ未受信のノード数の検索キーに対応するエントリをキャッシュテーブル２１０に登録することができる。また、検索部３３は、受信済ノード数管理表２２０を用いることで、データ受信済のノード数の検索キーに対応するエントリを、閾値と比較してからキャッシュテーブル２１０に登録することができる。
【００７７】
［第３の実施形態］
次に、第３の実施形態のＬ２ＳＷについて説明する。第３の実施形態のＬ２ＳＷは、第２の実施形態の検索処理において静的に決定されていた閾値を、検索処理において動的に決定する点で相違する。
【００７８】
まず、第３の実施形態の検索処理について図１１を用いて説明する。図１１は、第３の実施形態の検索処理のフローチャートを示す図である。
検索処理は、キャッシュ検索とツリー検索を並行して実行し、検索結果を得る処理である。検索処理は、検索部３３によって実行される処理である。なお、第２の実施形態の検索処理と同様の処理については、ステップ番号を同じにして説明を簡潔にする。
【００７９】
［ステップＳ１１］検索部３３は、受信パケットから検索キー（宛先ＩＰアドレス）を抽出する。
［ステップＳ１２］検索部３３は、検索キーを用いてツリー検索とキャッシュ検索を並行処理する。
【００８０】
［ステップＳ１３ａ］検索部３３は、ツリー検索とキャッシュ検索のいずれかが検索ヒットしたか否かを判定する。検索部３３は、ツリー検索とキャッシュ検索のいずれかが検索ヒットした場合にステップＳ１４にすすみ、いずれも検索ヒットしない場合にステップＳ１６１にすすむ。
【００８１】
［ステップＳ１４］検索部３３は、ツリー検索がヒットしたか否かを判定する。検索部３３は、ツリー検索がヒットした場合にステップＳ１５にすすみ、ツリー検索がヒットしていない場合にステップＳ１６にすすむ。
【００８２】
［ステップＳ１５］検索部３３は、ツリー検索結果でヒット処理をおこなう。
［ステップＳ１６］検索部３３は、キャッシュ検索結果でヒット処理をおこなう。
［ステップＳ１６１］検索部３３は、キャッシュ使用閾値判定表更新処理を実行する。キャッシュ使用閾値判定表更新処理は、キャッシュ使用閾値判定表を用いて、キャッシュ登録の判定に用いる閾値を動的に更新する処理である。キャッシュ使用閾値判定表更新処理については、後で図１２を用いて説明する。
【００８３】
［ステップＳ１７］検索部３３は、キャッシュ検索がミスヒットしたか否かを判定する。検索部３３は、キャッシュ検索がミスヒットした場合にステップＳ１８にすすみ、キャッシュ検索がミスヒットしていない場合にステップＳ２１にすすむ。
【００８４】
［ステップＳ１８］検索部３３は、受信済ノード数管理表を用いて検索キーのノード数が受信済か否かを判定する。検索部３３は、検索キーのノード数が受信済である場合にステップＳ１９ａにすすみ、検索キーのノード数が受信済でない場合にステップＳ２０にすすむ。
【００８５】
［ステップＳ１９ａ］検索部３３は、検索キーのノード数が動的に更新される閾値（キャッシュ使用閾値）より大きいか否かを判定する。検索部３３は、検索キーのノード数がキャッシュ使用閾値より大きい場合にステップＳ２０にすすみ、検索キーのノード数がキャッシュ使用閾値より大きくない（小さい）場合にステップＳ２１にすすむ。
【００８６】
［ステップＳ２０］検索部３３は、キャッシュ登録処理を実行する。
［ステップＳ２１］検索部３３は、ツリー検索とキャッシュ検索のいずれもが検索ミスヒットしたか否かを判定する。検索部３３は、ツリー検索とキャッシュ検索のいずれもが検索ミスヒットした場合にステップＳ２２にすすみ、いずれかが検索ヒットしている場合に検索処理を終了する。
【００８７】
［ステップＳ２２］検索部３３は、ミスヒット処理を実行し、検索処理を終了する。
次に、第３の実施形態のキャッシュ使用閾値判定表更新処理について図１２を用いて説明する。図１２は、第３の実施形態のキャッシュ使用閾値判定表更新処理のフローチャートを示す図である。
【００８８】
キャッシュ使用閾値判定表更新処理は、キャッシュ使用閾値判定表を用いて、キャッシュ登録の判定に用いる閾値を動的に更新する処理である。キャッシュ使用閾値判定表更新処理は、検索処理のステップＳ１６１で検索部３３によって実行される処理である。
【００８９】
［ステップＳ３１］検索部３３は、検索キーのノード数を取得する。
［ステップＳ３２］検索部３３は、キャッシュ検索が検索結果を得るのに要したキャッシュ検索時間とツリー検索が検索結果を得るのに要したツリー検索時間とを比較する。検索部３３は、キャッシュ検索時間がツリー検索時間より大きいときにステップＳ３３にすすみ、キャッシュ検索時間がツリー検索時間より大きくないときにステップＳ３４にすすむ。
【００９０】
［ステップＳ３３］検索部３３は、キャッシュ使用閾値判定表における検索キーのノード数に対応する比較結果を「ツリー検索」に更新する。なお、キャッシュ使用閾値判定表については、後で図１３から図１６を用いて説明する。
【００９１】
［ステップＳ３４］検索部３３は、キャッシュ使用閾値判定表における検索キーのノード数に対応する比較結果を「キャッシュ検索」に更新する。
［ステップＳ３５］検索部３３は、キャッシュ使用閾値判定表を参照して、比較結果「ツリー検索」から比較結果「キャッシュ検索」への変化点を抽出する。
【００９２】
［ステップＳ３６］検索部３３は、抽出した変化点のうち検索キーのノード数が最大の変化点を抽出する。
［ステップＳ３７］検索部３３は、検索キーのノード数が最大の変化点にしたがいキャッシュ使用閾値を決定し、キャッシュ使用閾値判定表更新処理を終了する。
【００９３】
次に、キャッシュ使用閾値判定表と、キャッシュ使用閾値判定表更新処理におけるキャッシュ使用閾値判定表の更新過程について図１３から図１６を用いて説明する。まず、キャッシュ使用閾値判定表の初期状態と、キャッシュ登録の是非の判定に用いる閾値（キャッシュ使用閾値）の初期値について図１３を用いて説明する。図１３は、第３の実施形態のキャッシュ使用閾値判定表の一例（その１）を示す図である。
【００９４】
キャッシュ使用閾値判定表２３０は、キャッシュ使用閾値の決定に用いられる表である。キャッシュ使用閾値判定表２３０は、項目「ノード数」と、項目「比較結果」とを含む。項目「ノード数」は、ツリー検索における検索キーに対応するノード数を示す。たとえば、項目「ノード数」は、ツリー検索が３２ビットの検索をおこなうとき「１」から「３２」までの３２個のレコードを有する。項目「比較結果」は、ツリー検索とキャッシュ検索のうちいずれが検索時間が短いかを示す。項目「比較結果」は、初期状態としてすべてのレコードで「キャッシュ検索」であり、ツリー検索時間がキャッシュ検索時間より短いときに「ツリー検索」に更新される。
【００９５】
たとえば、キャッシュ使用閾値判定表２３０は、ノード数「１」からノード数「３２」のすべてが比較結果「キャッシュ検索」であることを示す。このとき、検索部３３は、比較結果「ツリー検索」から比較結果「キャッシュ検索」への変化点が存在しないことから、初期値としてキャッシュ使用閾値を「０」とする。
【００９６】
次に、ノード数「９」の検索キーにおいてツリー検索時間がキャッシュ検索時間より短かったときに、検索部３３によって更新されたキャッシュ使用閾値判定表を図１４に示す。図１４は、第３の実施形態のキャッシュ使用閾値判定表の一例（その２）を示す図である。
【００９７】
キャッシュ使用閾値判定表２３１は、ノード数「９」の検索キーにおいてツリー検索時間がキャッシュ検索時間より短かったときに、キャッシュ使用閾値判定表２３０が検索部３３によって更新された表である。
【００９８】
検索部３３は、ノード数「９」のレコードで比較結果を「ツリー検索」に更新する（ハッチングで示す）。これにより、検索部３３は、ノード数「９」とノード数「１０」との境界に変化点を検出する。このとき、検索部３３は、変化点を超えない最大のノード数「９」をキャッシュ使用閾値に決定する。
【００９９】
次に、ノード数「１３」の検索キーにおいてキャッシュ検索時間がツリー検索時間より短かったときに、検索部３３によって更新されたキャッシュ使用閾値判定表を図１５に示す。図１５は、第３の実施形態のキャッシュ使用閾値判定表の一例（その３）を示す図である。
【０１００】
キャッシュ使用閾値判定表２３２は、ノード数「１３」の検索キーにおいてキャッシュ検索時間がツリー検索時間より短かったときに、キャッシュ使用閾値判定表２３１が検索部３３によって更新された表である。
【０１０１】
検索部３３は、ノード数「１３」のレコードで比較結果を「キャッシュ検索」に更新（上書き）する（ハッチングで示す）。ただし、ノード数「１３」のレコードは、比較結果の初期値が「キャッシュ検索」であったことから、実体として変化がない。したがって、検索部３３は、ノード数「９」とノード数「１０」との境界にある変化点以外に、新たに変化点を検出しない。そのため、検索部３３は、キャッシュ使用閾値を更新しない。
【０１０２】
次に、ノード数「１１」の検索キーにおいてツリー検索時間がキャッシュ検索時間より短かったときに、検索部３３によって更新されたキャッシュ使用閾値判定表を図１６に示す。図１６は、第３の実施形態のキャッシュ使用閾値判定表の一例（その４）を示す図である。
【０１０３】
キャッシュ使用閾値判定表２３３は、ノード数「１１」の検索キーにおいてツリー検索時間がキャッシュ検索時間より短かったときに、キャッシュ使用閾値判定表２３２が検索部３３によって更新された表である。
【０１０４】
検索部３３は、ノード数「１１」のレコードで比較結果を「ツリー検索」に更新する（ハッチングで示す）。これにより、検索部３３は、ノード数「１１」とノード数「１２」との境界に新たな変化点を検出する。したがって、検索部３３は、ノード数「９」とノード数「１０」との境界と、ノード数「１１」とノード数「１２」との境界の２つの変化点を検出する。検索部３３は、２つの変化点のうちノード数「１１」とノード数「１２」との境界にある変化点をノード数が最大の変化点として抽出する。このとき、検索部３３は、ノード数が最大の変化点を超えない最大のノード数「１１」をキャッシュ使用閾値に決定する。
【０１０５】
このように、検索部３３は、キャッシュ使用閾値を動的に更新することができる。これにより、検索部３３は、キャッシュ検索時間がツリー検索時間より大きい検索キーをキャッシュ登録せず、ツリー検索時間がキャッシュ検索時間より大きい検索キーをキャッシュ登録することができる。
【０１０６】
これにより、検索部３３は、キャッシュ検索においてツリー検索より先に検索結果を得られるときの検索ヒット率を改善することができる。そして、検索部３３は、ツリー検索より先に検索結果を得られるときのキャッシュ検索の検索ヒット率を改善することによって、ツリー検索とキャッシュ検索を並行しておこなうときの検索性能を改善する。
【０１０７】
［第４の実施形態］
次に、第４の実施形態のＬ２ＳＷについて説明する。第４の実施形態のＬ２ＳＷは、閾値を用いないでキャッシュ登録の是非を判定する点で、第２の実施形態や第３の実施形態と相違する。第４の実施形態のＬ２ＳＷは、閾値を用いることに代えて、ツリー検索時間とキャッシュ検索時間の比較によってキャッシュ登録の是非を判定する。ただし、キャッシュ検索がミスヒットしたとき、本来のキャッシュ検索がヒットしたときの検索時間を得ることができないため、これに代えてキャッシュ検索がミスヒットしたときの検索時間を用いる。これは、キャッシュ検索がヒットしたときであってもミスヒットしたときであっても、ハッシュ計算にかかる負荷がある点で変わらないことによる。ただし、厳密には、宛先ＩＰアドレスによる全ビットの一致比較をおこなわないため、ミスヒット時のキャッシュ検索時間は、ヒット時のキャッシュ検索時間より若干ながら短くなる。
【０１０８】
まず、第４の実施形態の検索処理について図１７を用いて説明する。図１７は、第４の実施形態の検索処理のフローチャートを示す図である。
検索処理は、キャッシュ検索とツリー検索を並行して実行し、検索結果を得る処理である。検索処理は、検索部３３によって実行される処理である。なお、第２の実施形態の検索処理と同様の処理については、ステップ番号を同じにして説明を簡潔にする。
【０１０９】
［ステップＳ１１］検索部３３は、受信パケットから検索キー（宛先ＩＰアドレス）を抽出する。
［ステップＳ１２］検索部３３は、検索キーを用いてツリー検索とキャッシュ検索を並行処理する。
【０１１０】
［ステップＳ１３］検索部３３は、ツリー検索とキャッシュ検索のいずれかが検索ヒットしたか否かを判定する。検索部３３は、ツリー検索とキャッシュ検索のいずれかが検索ヒットした場合にステップＳ１４にすすみ、いずれも検索ヒットしない場合にステップＳ１７ａにすすむ。
【０１１１】
［ステップＳ１４］検索部３３は、ツリー検索がヒットしたか否かを判定する。検索部３３は、ツリー検索がヒットした場合にステップＳ１５にすすみ、ツリー検索がヒットしていない場合にステップＳ１６にすすむ。
【０１１２】
［ステップＳ１５］検索部３３は、ツリー検索結果でヒット処理をおこなう。
［ステップＳ１６］検索部３３は、キャッシュ検索結果でヒット処理をおこなう。
［ステップＳ１７ａ］検索部３３は、キャッシュ検索がミスヒットしたか否かを判定する。検索部３３は、キャッシュ検索がミスヒットした場合にステップＳ１７１にすすみ、キャッシュ検索がミスヒットしていない場合にステップＳ２１にすすむ。
【０１１３】
［ステップＳ１７１］検索部３３は、キャッシュ検索時間がツリー検索時間より小さいか否かを判定する。検索部３３は、キャッシュ検索時間がツリー検索時間より小さい場合にステップＳ２０にすすみ、キャッシュ検索時間がツリー検索時間より小さくない場合にステップＳ２１にすすむ。
【０１１４】
ただし、ここで用いるキャッシュ検索時間は、キャッシュ検索が検索ヒットした場合の検索時間に限らず、検索ミスヒットした場合の検索時間を含む。
［ステップＳ２０］検索部３３は、キャッシュ登録処理を実行する。
【０１１５】
このように、検索部３３は、キャッシュ検索が検索ミスヒットした場合にもキャッシュ検索時間をツリー検索時間と比較してキャッシュ登録の是非を判定することができる。したがって、検索部３３は、キャッシュ検索において最初のパケットからキャッシュ検索時間をツリー検索時間と比較してキャッシュ登録の是非を判定することができる。
【０１１６】
したがって、検索部３３は、ツリー検索より先に検索結果を得られるときの検索ヒット率をより早く改善することができる。結果として、検索部３３は、ツリー検索とキャッシュ検索を並行しておこなうときの検索性能を改善する。
【０１１７】
［ステップＳ２１］検索部３３は、ツリー検索とキャッシュ検索のいずれもが検索ミスヒットしたか否かを判定する。検索部３３は、ツリー検索とキャッシュ検索のいずれもが検索ミスヒットした場合にステップＳ２２にすすみ、いずれかが検索ヒットしている場合に検索処理を終了する。
【０１１８】
［ステップＳ２２］検索部３３は、ミスヒット処理を実行し、検索処理を終了する。
次に、キャッシュ登録判定例について図１８を用いて説明する。図１８は、第４の実施形態のキャッシュ登録判定例を示す図である。
【０１１９】
キャッシュ登録判定例２４０は、受信順序「１」から受信順序「４」までの４つのパケットにおけるキャッシュ登録判定例を示す。
まず、ツリー検索と比較してキャッシュ検索が速いとされるノード数の検索キーを有するパケットを受信したときのキャッシュ登録判定例について、受信順序「１」，「２」のパケットのキャッシュ登録判定例を用いて説明する。
【０１２０】
受信順序「１」のパケットは、検索キー（ハッシュ値）が「Ｈ１」、ノード数が「Ｎ１」であり、キャッシュ登録のないパケットである。なお、ノード数「Ｎ１」は、ツリー検索と比較してキャッシュ検索が速いとされるノード数である。
【０１２１】
検索部３３は、受信順序「１」のパケットを検索した結果、ツリー検索でヒットし、キャッシュ検索でミスヒットする。ただし、検索部３３は、ヒットしたツリー検索からツリー検索時間を取得できるだけでなく、ミスヒットしたキャッシュ検索からもキャッシュ検索時間を取得できる。これにより、検索部３３は、ツリー検索時間とキャッシュ検索時間とを比較してキャッシュ検索時間がツリー検索時間よりも短いという比較結果を得るが、キャッシュ検索がミスヒットしているためツリー検索の検索結果を用いてヒット処理をおこなう。検索部３３は、キャッシュ検索時間がツリー検索時間よりも短いという比較結果にしたがい検索キー「Ｈ１」に対応するエントリをキャッシュ登録する。
【０１２２】
受信順序「２」のパケットは、検索キーが「Ｈ１」、ノード数が「Ｎ１」であり、受信順序「１」のパケットによりキャッシュ登録されているパケットである。
検索部３３は、受信順序「２」のパケットを検索した結果、ツリー検索でヒットし、キャッシュ検索でもヒットする。検索部３３は、ヒットしたツリー検索からツリー検索時間を取得し、ヒットしたキャッシュ検索からもキャッシュ検索時間を取得する。これにより、検索部３３は、ツリー検索時間とキャッシュ検索時間とを比較してキャッシュ検索時間がツリー検索時間よりも短いという比較結果を得て、キャッシュ検索の検索結果を用いてヒット処理をおこなう。
【０１２３】
このように、検索部３３は、検索キー「Ｈ１」のパケットの最初の受信時から、ツリー検索時間とキャッシュ検索時間とを比較して検索キー「Ｈ１」に対応するエントリをキャッシュ登録することができる。したがって、検索部３３は、ツリー検索より先に検索結果を得られるときの検索ヒット率をより早く改善することができる。
【０１２４】
次に、ツリー検索と比較してキャッシュ検索が遅いとされるノード数の検索キーを有するパケットを受信したときのキャッシュ登録判定例について、受信順序「３」，「４」のパケットのキャッシュ登録判定例を用いて説明する。
【０１２５】
受信順序「３」のパケットは、検索キーが「Ｈ２」、ノード数が「Ｎ２」であり、キャッシュ登録のないパケットである。なお、ノード数「Ｎ２」は、ツリー検索と比較してキャッシュ検索が遅いとされるノード数である。
【０１２６】
検索部３３は、受信順序「３」のパケットを検索した結果、ツリー検索でヒットし、キャッシュ検索でミスヒットする。ただし、検索部３３は、ヒットしたツリー検索からツリー検索時間を取得できるだけでなく、ミスヒットしたキャッシュ検索からもキャッシュ検索時間を取得できる。これにより、検索部３３は、ツリー検索時間とキャッシュ検索時間とを比較してキャッシュ検索時間がツリー検索時間よりも長いという比較結果を得る。検索部３３は、キャッシュ検索がミスヒットしているためツリー検索の検索結果を用いてヒット処理をおこなう。検索部３３は、キャッシュ検索時間がツリー検索時間よりも長いという比較結果にしたがい検索キー「Ｈ２」に対応するエントリをキャッシュ登録しない。
【０１２７】
受信順序「４」のパケットは、検索キーが「Ｈ２」、ノード数が「Ｎ２」である。受信順序「４」のパケットは、受信順序「３」のパケットと同様の処理を繰り返し、検索キー「Ｈ２」に対応するエントリをキャッシュ登録しない。
【０１２８】
このように、検索部３３は、検索キー「Ｈ２」のパケットの最初の受信時から、ツリー検索時間とキャッシュ検索時間とを比較して検索キー「Ｈ２」に対応するエントリをキャッシュ登録しないことができる。したがって、検索部３３は、検索ヒット率の改善に貢献しないエントリをキャッシュテーブルから排除することができる。したがって、検索部３３は、ツリー検索より先に検索結果を得られるときの検索ヒット率を改善することができる。
【０１２９】
［第５の実施形態］
次に、第５の実施形態のＬ２ＳＷについて説明する。第５の実施形態のＬ２ＳＷは、検索キーのノード数に応じたキャッシュ登録の優先度を設定する点で、第２の実施形態から第４の実施形態と相違する。第５の実施形態のＬ２ＳＷは、キャッシュ登録の優先度の設定を実現するため、第２の実施形態で図９を用いて説明した検索処理のステップＳ２０におけるキャッシュ登録処理に代えて図１９に示すキャッシュ登録処理を実行する。また、第５の実施形態のＬ２ＳＷは、キャッシュテーブルにノード数を特定可能な情報を含む。
【０１３０】
第５の実施形態の検索処理は、第２の実施形態の検索処理と同様であるため説明を省略し、第５の実施形態のキャッシュ登録処理について図１９を用いて説明する。図１９は、第５の実施形態のキャッシュ登録処理のフローチャートを示す図である。
【０１３１】
キャッシュ登録処理は、検索処理のステップＳ１８またはステップＳ１９により、検索キーに対応するエントリをキャッシュ登録するときに、追加対象のエントリと削除対象のエントリとを優先度で比較して登録の是非を判定してから追加対象のエントリの登録をおこなう処理である。キャッシュ登録処理は、図９に示した検索処理のステップＳ２０で検索部３３によって実行される処理である。
【０１３２】
［ステップＳ６１］検索部３３は、追加対象のエントリ（新エントリ）のハッシュ値がキャッシュテーブルに登録済のエントリ（登録済エントリ）のハッシュ値と衝突したか否かを判定する。検索部３３は、ハッシュ値が衝突した場合にステップＳ６２にすすみ、ハッシュ値が衝突しない場合にステップＳ６４にすすむ。
【０１３３】
［ステップＳ６２］検索部３３は、新エントリのノード数が登録済エントリのノード数より大きいか否かを判定する。検索部３３は、新エントリのノード数が登録済エントリのノード数より大きい場合にステップＳ６３にすすみ、新エントリのノード数が登録済エントリのノード数より大きくない場合にキャッシュ登録処理を終了する。
【０１３４】
なお、検索部３３は、登録済みのエントリのノード数をキャッシュテーブルから取得することができる。第５の実施形態のキャッシュテーブルについては、後で図２０および図２１を用いて説明する。
【０１３５】
［ステップＳ６３］検索部３３は、登録済エントリをキャッシュテーブルから消去する。
［ステップＳ６４］検索部３３は、新エントリをキャッシュテーブルに登録（キャッシュ登録）して、キャッシュ登録処理を終了する。
【０１３６】
このように、検索部３３は、ハッシュ値が衝突した場合に、新エントリと登録済エントリのキャッシュ登録の是非をエントリのノード数を比較して判定する。すなわち、エントリのノード数は、キャッシュ登録の優先度に相当する優先情報である。
【０１３７】
次に、第５の実施形態のキャッシュテーブルについて図２０および図２１を用いて説明する。まず、キャッシュテーブルに先に登録されているエントリ（登録済エントリ）について図２０を用いて説明する。図２０は、第５の実施形態のキャッシュテーブルの一例（その１）を示す図である。
【０１３８】
キャッシュテーブル２１１は、キャッシュ検索において更新されるデータであり、メモリ１０１に記憶される。キャッシュテーブル２１１は、フォワーディングテーブルの一態様であり、宛先ＩＰアドレス（検索キー）のハッシュ値をインデックスとするテーブルデータ構造を有する。たとえば、キャッシュテーブル２１１は、項目「ハッシュ値」と、項目「宛先ＩＰアドレス」と、項目「ノード数」と、項目「処理」を含む。
【０１３９】
項目「ハッシュ値」は、宛先ＩＰアドレス（検索キー）を入力値としたときのハッシュ演算の結果を示す。検索キー「００００００００」は、ハッシュ値「３」であり、ノード数「６」であり、処理「Ａ」が対応付けられている。
【０１４０】
つぎに、キャッシュテーブル２１１に追加登録されたエントリ（新エントリ）について図２１を用いて説明する。図２１は、第５の実施形態のキャッシュテーブルの一例（その２）を示す図である。
【０１４１】
キャッシュテーブル２１２は、キャッシュテーブル２１１が新エントリの追加登録により更新されたキャッシュテーブルである。
新エントリは、宛先ＩＰアドレス（検索キー）「０００００１１１」であり、ハッシュ値「３」であり、ノード数「７」である。したがって、新エントリは、ハッシュ値「３」の登録済エントリとハッシュ値が衝突する。ここで、検索部３３は、キャッシュテーブル２１１から取得した登録済エントリのノード数「６」と、新エントリのノード数「７」とを比較する。検索部３３は、新エントリのノード数が登録済エントリのノード数より大きいことから、登録済エントリに優先して新エントリを登録（登録済エントリを上書き）し、キャッシュテーブル２１２を得る。
【０１４２】
したがって、キャッシュテーブル２１２は、検索キー「０００００１１１」、ハッシュ値「３」、ノード数「７」、処理「Ｂ」が対応付けられた新エントリが登録される。
なお、新エントリがハッシュ値「３」、ノード数「５」であった場合、検索部３３は、新エントリの登録をキャンセルし、キャッシュテーブル２１１を更新しない。
【０１４３】
これにより、検索部３３は、検索ヒット率の改善に貢献しないエントリをキャッシュテーブルから排除することができる。したがって、検索部３３は、ツリー検索より先に検索結果を得られるときの検索ヒット率を改善することができる。
【０１４４】
なお、検索部３３は、ハッシュが衝突した場合にノード数を参照して登録の是非を判定するようにしたが、これに限らず、エントリ数が上限に達したなどエントリの入替が生じる場合にノード数を参照してキャッシュ登録の是非を判定するようにしてもよい。
【０１４５】
［第６の実施形態］
次に、第６の実施形態のＬ２ＳＷについて説明する。第６の実施形態のＬ２ＳＷは、検索キーのノード数に応じたキャッシュ登録の優先度の設定に加えて、検索対象となるパケットの帯域（通信量）に応じたキャッシュ登録の優先度の設定をおこなう点で第５の実施形態と相違する。
【０１４６】
まず、第６の実施形態のＬ２ＳＷの機能構成について図２２を用いて説明する。図２２は、第６の実施形態のＬ２ＳＷの機能構成の一例を示す図である。なお、第２の実施形態のＬ２ＳＷ２０と同様の構成については符号を同じにして説明を省略する。
【０１４７】
Ｌ２ＳＷ２０ａは、受信部３１と、検索キー抽出部３２と、検索部３３ａと、アクション処理部３４と、送信部３５とを含む。
検索部３３ａは、検索キー抽出部３２から入力した検索キーにもとづく検索をおこない、検索結果をアクション処理部３４に出力する。検索部３３ａは、ツリー検索部３６と、キャッシュ検索部３７と、検索結果選択部３８と、キャッシュ管理部３９ａと、帯域測定部４０とを含む。ツリー検索部３６は、検索キーを用いてツリー検索方式によるツリーテーブルの検索をおこなう。キャッシュ検索部３７は、検索キーを用いてキャッシュ検索方式によるキャッシュテーブルの検索をおこなう。
【０１４８】
検索結果選択部３８は、ツリー検索部３６から得られた検索結果とキャッシュ検索部３７から得られた検索結果のうち、より先に得られた検索結果を選択してアクション処理部３４に出力する。
【０１４９】
帯域測定部４０は、検索キーごとの帯域を測定し、測定結果をキャッシュ管理部３９ａに出力する。たとえば、帯域測定部４０は、単位時間（たとえば１秒）当たりの通信量を所定間隔（たとえば１０秒）でキャッシュ管理部３９ａに出力する。
【０１５０】
キャッシュ管理部３９ａは、ツリー検索部３６から得られた検索結果とキャッシュ検索部３７から得られた検索結果とにもとづいてキャッシュテーブルを更新する。また、キャッシュ管理部３９ａは、検索キー（エントリ）ごとの帯域測定結果を帯域測定部４０から入力し、キャッシュテーブルに記録する。
【０１５１】
Ｌ２ＳＷ２０ａは、キャッシュ登録の優先度の設定を実現するため、第２の実施形態で図９を用いて説明した検索処理のステップＳ２０におけるキャッシュ登録処理に代えて図２３に示すキャッシュ登録処理を実行する。また、Ｌ２ＳＷ２０ａは、キャッシュテーブルにノード数を特定可能な情報と、検索キーごとの帯域を評価可能な情報を含む。
【０１５２】
第６の実施形態の検索処理は、第２の実施形態の検索処理と同様であるため説明を省略し、第６の実施形態のキャッシュ登録処理について図２３を用いて説明する。図２３は、第６の実施形態のキャッシュ登録処理のフローチャートを示す図である。
【０１５３】
キャッシュ登録処理は、検索処理のステップＳ１８またはステップＳ１９により、検索キーに対応するエントリをキャッシュ登録するときに、追加対象のエントリと削除対象のエントリとを優先度で比較して登録の是非を判定してから追加対象のエントリの登録をおこなう処理である。キャッシュ登録処理は、図９に示した検索処理のステップＳ２０で検索部３３ａによって実行される処理である。
【０１５４】
［ステップＳ７１］検索部３３ａは、追加対象のエントリ（新エントリ）のハッシュ値がキャッシュテーブルに登録済のエントリ（登録済エントリ）のハッシュ値と衝突したか否かを判定する。検索部３３ａは、ハッシュ値が衝突した場合にステップＳ７２にすすみ、ハッシュ値が衝突しない場合にステップＳ７５にすすむ。
【０１５５】
［ステップＳ７２］検索部３３ａは、新エントリのノード数が登録済エントリのノード数より大きいか否かを判定する。検索部３３ａは、新エントリのノード数が登録済エントリのノード数より大きい場合にステップＳ７３にすすみ、新エントリのノード数が登録済エントリのノード数より大きくない場合にキャッシュ登録処理を終了する。
【０１５６】
なお、検索部３３ａは、登録済みのエントリのノード数をキャッシュテーブルから取得することができる。第６の実施形態のキャッシュテーブルについては、後で図２４および図２５を用いて説明する。
【０１５７】
［ステップＳ７３］検索部３３ａは、新エントリの帯域が登録済エントリの帯域より大きいか否かを判定する。検索部３３ａは、新エントリの帯域が登録済エントリの帯域より大きい場合にステップＳ７４にすすみ、新エントリの帯域が登録済エントリの帯域より大きくない場合にキャッシュ登録処理を終了する。
【０１５８】
なお、検索部３３ａは、登録済みのエントリの帯域をキャッシュテーブルから取得することができる。
［ステップＳ７４］検索部３３ａは、登録済エントリをキャッシュテーブルから消去する。
【０１５９】
［ステップＳ７５］検索部３３ａは、新エントリをキャッシュテーブルに登録（キャッシュ登録）して、キャッシュ登録処理を終了する。
このように、検索部３３ａは、ハッシュ値が衝突した場合に、新エントリと登録済エントリのキャッシュ登録の是非をエントリのノード数の比較と帯域の比較とから判定する。すなわち、エントリのノード数は、キャッシュ登録の第１の優先度に相当する優先情報であり、エントリの帯域は、キャッシュ登録の第２の優先度に相当する優先情報である。
【０１６０】
次に、第６の実施形態のキャッシュテーブルについて図２４および図２５を用いて説明する。まず、キャッシュテーブルに先に登録されているエントリ（登録済エントリ）について図２４を用いて説明する。図２４は、第６の実施形態のキャッシュテーブルの一例（その１）を示す図である。
【０１６１】
キャッシュテーブル２１３は、キャッシュ検索において更新されるデータであり、メモリ１０１に記憶される。キャッシュテーブル２１３は、フォワーディングテーブルの一態様であり、宛先ＩＰアドレス（検索キー）のハッシュ値をインデックスとするテーブルデータ構造を有する。たとえば、キャッシュテーブル２１３は、項目「ハッシュ値」と、項目「宛先ＩＰアドレス」と、項目「ノード数」と、項目「帯域」と、項目「処理」を含む。
【０１６２】
項目「ハッシュ値」は、宛先ＩＰアドレス（検索キー）を入力値としたときのハッシュ演算の結果を示す。検索キー「００００００００」は、ハッシュ値「３」であり、ノード数「３」であり、帯域「１０（Ｍｂｐｓ（Megabits per second））」であり、処理「Ａ」が対応付けられている。
【０１６３】
つぎに、キャッシュテーブル２１３に追加登録されたエントリ（新エントリ）について図２５を用いて説明する。図２５は、第６の実施形態のキャッシュテーブルの一例（その２）を示す図である。
【０１６４】
キャッシュテーブル２１４は、キャッシュテーブル２１３が新エントリの追加登録により更新されたキャッシュテーブルである。
新エントリは、宛先ＩＰアドレス（検索キー）「０００００１１１」であり、ハッシュ値「３」であり、ノード数「５」であり、帯域「２０」である。したがって、新エントリは、ハッシュ値「３」の登録済エントリとハッシュ値が衝突する。ここで、検索部３３ａは、キャッシュテーブル２１３から取得した登録済エントリのノード数「３」と、新エントリのノード数「５」とを比較して第１の優先判定をおこなう。検索部３３ａは、新エントリのノード数が登録済エントリのノード数より大きいことから、新エントリについて第１の優先判定を是として、第２の優先判定をおこなう。検索部３３ａは、キャッシュテーブル２１３から取得した登録済エントリの帯域「１０」と、新エントリの帯域「２０」とを比較して第２の優先判定をおこなう。検索部３３ａは、新エントリの帯域が登録済エントリの帯域より大きいことから、新エントリについて第２の優先判定を是としてキャッシュ登録をおこなう。
【０１６５】
これにより、検索部３３ａは、登録済エントリに優先して新エントリを登録（登録済エントリを上書き）し、キャッシュテーブル２１４を得る。
したがって、キャッシュテーブル２１４は、検索キー「０００００１１１」、ハッシュ値「３」、ノード数「５」、帯域「２０」、処理「Ｂ」が対応付けられた新エントリが登録される。
【０１６６】
なお、新エントリがハッシュ値「３」、ノード数「２」であった場合、あるいは新エントリがハッシュ値「３」、ノード数「５」、帯域「１」であった場合、検索部３３ａは、新エントリの登録をキャンセルし、キャッシュテーブル２１３を更新しない。
【０１６７】
これにより、検索部３３ａは、検索ヒット率の改善に貢献しないエントリをキャッシュテーブルから排除することができる。また、検索部３３ａは、優先情報として帯域情報を用いることにより、検索機会の多いパケットについて検索ヒットする機会を多く設定することができる。したがって、検索部３３ａは、ツリー検索より先に検索結果を得られるときの検索ヒット率を改善することができる。
【０１６８】
なお、検索部３３は、ハッシュが衝突した場合にノード数を参照して登録の是非を判定するようにしたが、これに限らず、エントリ数が上限に達したなどエントリの入替が生じる場合にノード数を参照してキャッシュ登録の是非を判定するようにしてもよい。
【０１６９】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、スイッチ１、ルータ１３，１５，１７，２１，２４や、Ｌ２ＳＷ１６，２０，２０ａなどのデータ転送装置が有すべき機能の処理内容を記述したプログラムが提供される。また、検索キー抽出部３２、検索部３３，３３ａ、アクション処理部３４などは、データ転送制御装置としての一側面を有し、データ転送制御装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【０１７０】
プログラムを流通させる場合には、たとえば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１７１】
プログラムを実行するコンピュータは、たとえば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１７２】
また、上記の処理機能の少なくとも一部を、ＤＳＰ、ＡＳＩＣ、ＰＬＤなどの電子回路で実現することもできる。
【符号の説明】
【０１７３】
１  スイッチ
２  記憶部
２ａ  ツリーデータ
２ｂ  キャッシュデータ
３  制御部
４  受信データ
５  転送制御識別情報
６，７  検索結果
１０  ネットワークシステム
１１  ＶＰＮコアＮＷ
１２  ＩＳＰ
１３，１５，１７，２１，２４  ルータ
１４  コア・メトロＮＷ
１６，２０，２０ａ  Ｌ２ＳＷ
１８，１９，２２，２３，２５，２６  端末装置
３０  パケット
３１  受信部
３２  検索キー抽出部
３３，３３ａ  検索部
３４  アクション処理部
３５  送信部
３６  ツリー検索部
３７  キャッシュ検索部
３８  検索結果選択部
３９，３９ａ  キャッシュ管理部
４０  帯域測定部
１００  プロセッサ
１０１  メモリ
１０２  入出力インタフェース
１０３  バス
１０４，１０５，１０６，１０７  ネットワークインタフェース
【図１】
2018056739.tif 000003
【図２】
2018056739.tif 000004
【図３】
2018056739.tif 000005
【図４】
2018056739.tif 000006
【図５】
2018056739.tif 000007
【図６】
2018056739.tif 000008
【図７】
2018056739.tif 000009
【図８】
2018056739.tif 000010
【図９】
2018056739.tif 000011
【図１０】
2018056739.tif 000012
【図１１】
2018056739.tif 000013
【図１２】
2018056739.tif 000014
【図１３】
2018056739.tif 000015
【図１４】
2018056739.tif 000016
【図１５】
2018056739.tif 000017
【図１６】
2018056739.tif 000018
【図１７】
2018056739.tif 000019
【図１８】
2018056739.tif 000020
【図１９】
2018056739.tif 000021
【図２０】
2018056739.tif 000022
【図２１】
2018056739.tif 000023
【図２２】
2018056739.tif 000024
【図２３】
2018056739.tif 000025
【図２４】
2018056739.tif 000026
【図２５】
2018056739.tif 000027