(57)【特許請求の範囲】
【請求項１】
入力されたパケットのヘッダ部分から、該パケットの持つパケット種別が予め定められた複数種類のパケット種別のうちのいずれのパケット種別に該当するかを決定付けるために予め定められた複数のビット列を抽出し、この抽出された複数のビット列の値に基づいて、該複数のビット列により決定付けられるパケット種別を持つ入力パケットに対して施すべき処理の少なくとも一部を特定可能なパケット種別情報を１つ作成するパケット種別情報作成手段と、
この作成されたパケット種別情報に基づいて得られる、該パケット種別情報に係るパケット種別を持つ入力パケットに作用させるべき命令列を用いて、前記入力パケットを処理するパケット処理手段とを備えたことを特徴とするパケット処理装置。
【請求項２】
前記パケット種別情報作成手段は、
各パケット種別情報に対応する前記複数のビット列の各ビットパターンを保持し、入力された前記パケットから抽出された前記複数のビット列の値とこの保持されたビットパターンとを比較することにより、前記パケット種別情報を作成する手段を含むことを特徴とする請求項１に記載のパケット処理装置。
【請求項３】
前記パケット種別情報作成手段は、
予め定められたパケット種別情報に対応する複数のビット列の各ビットパターンを入力としたときに当該パケット種別情報が出力となる論理演算を、入力された前記パケットから抽出された前記複数のビット列の値に作用させることによって、前記パケット種別情報を作成する手段を含むことを特徴とする請求項１に記載のパケット処理装置。
【請求項４】
前記パケット処理手段が或るパケットに対して処理を行っている間に、前記パケット種別情報作成手段は次のパケットに対するパケット種別情報を作成するものであることを特徴とする請求項１に記載のパケット処理装置。
【請求項５】
前記パケット処理手段は、
複数のパケット種別情報にそれぞれ対応する複数の処理ルーチンを記憶するプログラムメモリと、
前記パケット種別情報作成手段により作成されたパケット種別情報を割り込み信号として、前記プログラムメモリに記憶された複数の処理ルーチンのうちの該パケット種別情報により特定される一つを起動して実行するプロセッサとを含むことを特徴とする請求項１に記載のパケット処理装置。
【請求項６】
前記パケット種別情報作成手段は、入力された前記パケットから前記処理に共されるパラメータをも抽出し、
作成された前記パケット種別情報とともに該パラメータを前記パケット処理手段に渡し、前記パケット処理手段は、前記パケット種別情報に基づいて得られた前記命令列と前記パラメータとを用いて前記パケットを処理するものであることを特徴とする請求項１に記載のパケット処理装置。
【請求項７】
前記パケット処理手段は、
マイクロ命令列をパイプライン処理する命令処理部と、
複数のパケット種別情報にそれぞれ対応する複数のマイクロ命令列を記憶する命令列テーブルと、
前記パケット種別情報作成手段により作成されたパケット種別情報に従って前記命令列テーブルから選択されたマイクロ命令列を前記命令処理部に与える手段とを含むことを特徴とする請求項１に記載のパケット処理装置。
【請求項８】
前記パケット処理手段は、
マイクロ命令列をパイプライン処理する命令処理部と、
複数のパケット種別情報にそれぞれ対応する複数のマクロ命令列を記憶する命令列テーブルと、
前記パケット種別情報作成手段により作成されたパケット種別情報に従って前記命令列テーブルから選択されたマクロ命令列を、マイクロ命令に変換する手段と、
生成されたこのマイクロ命令を前記命令処理部に与える手段とを含むことを特徴とする請求項１に記載のパケット処理装置。
【請求項９】
前記パケット種別情報作成手段は、入力された前記パケットから前記処理に用いられるパラメータをも抽出し、該パラメータを作成された前記パケット種別情報と共に前記パケット処理手段に渡し、
前記パケット処理手段は、
マイクロ命令列をパイプライン処理する命令処理部と、
複数のパケット種別情報にそれぞれ対応する複数のマクロ命令列を記憶する命令列テーブルと、
前記パケット種別情報作成手段により作成されたパケット種別情報に従って前記命令列テーブルから選択されたマクロ命令列を、前記パラメータを反映させながら、マイクロ命令に変換する手段と、
生成されたこのマイクロ命令を前記命令処理部に与える手段とを含むことを特徴とする請求項１に記載のパケット処理装置。
【請求項１０】
前記命令処理部は、前記命令列テーブルから選択された命令列と、パケットに対する処理以外の処理を行うためにメインメモリに書き込まれた命令列とを交互に実行可能に構成されたものであることを特徴とする請求項７ないし９のいずれか１項に記載のパケット処理装置。
【請求項１１】
自装置が接続されるネットワークにおけるパケット種別の混在比率に応じて該パケット種別に対応するパケット種別情報を記憶する記憶手段を更に備え、
前記パケット種別情報作成手段は、入力された前記パケットに対して前記パケット種別に対応するパケット種別情報が前記記憶手段に記憶されていない場合には、その他を示すパケット種別情報を作成し、
前記パケット処理手段は、その他を示すパケット種別情報を渡された場合には、入力された前記パケットに対してパケット種別を予め特定せずにパケット種別を調べながら処理を行うものであることを特徴とする請求項１に記載のパケット処理装置。
【請求項１２】
前記パケット処理手段は、ネットワークから入力された前記パケットが所望の宛先に転送されるよう、該パケットを自装置から前記ネットワークへ出力するための処理を行うものであることを特徴とする請求項１に記載のパケット処理装置。
【請求項１３】
前記パケット種別情報作成手段は、
前記入力パケットの宛先情報から作成される付加情報を含む前記パケット種別情報を前記パケット処理手段に渡し、
前記パケット処理手段は、複数の方路情報テーブル検索手段のうちの一つを、前記付加情報に従って選択し、該選択された方路情報テーブル検索手段を用いて方路情報テーブルを検索することで、前記入力パケットの出方路を決定することを特徴とする請求項１に記載のパケット処理装置。
【請求項１４】
入力されたパケットのヘッダ部分から、該パケットの持つパケット種別が予め定められた複数種類のパケット種別のうちのいずれのパケット種別に該当するかを決定付けるために予め定められた複数のビット列を抽出し、
この抽出された複数のビット列の値に基づいて、該複数のビット列により決定付けられるパケット種別を持つ入力パケットに対して施すべき処理の少なくとも一部を特定可能なパケット種別情報を１つ作成し、
この作成されたパケット種別情報に基づいて、該パケット種別情報に係るパケット種別を持つ入力パケットに作用させるべき命令列を選択し、
この選択された命令列を用いて、前記入力パケットを処理することを特徴とするパケット処理方法。
【請求項１５】
入力されたパケットのヘッダ部分から、該パケットの持つパケット種別が予め定められた複数種類のパケット種別のうちのいずれのパケット種別に該当するかを決定付けるために予め定められた複数のビット列を抽出し、
この抽出された複数のビット列の値に基づいて、該複数のビット列により決定付けられるパケット種別を持つ入力パケットに対して施すべき処理の少なくとも一部を特定可能なパケット種別情報を１つ作成し、
この作成されたパケット種別情報に基づいて、該パケット種別情報に係るパケット種別を持つ入力パケットに作用させるべき命令列を生成し、
この生成された命令列を用いて、前記入力パケットを処理することを特徴とするパケット処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット処理を行うパケット処理装置及びパケット処理方法に関する。
【０００２】
【従来の技術】
近年、インターネットのトラフィックが爆発的に増大しており、インターネット上で情報を転送するパケットを高速に処理する装置に対する需要が増大している。パケット処理は、外部から入力されてきたパケットのヘッダ部分を参照し、該ヘッダ部分に記載されている情報に従って所望の処理を行うことにより実現される。
【０００３】
ここで、上記の所望の処理に該当するものとしては、例えば、
（１）パケットのヘッダ部分に含まれる宛先アドレスを参照し、所定の出力リンクに転送する処理、
（２）パケットのヘッダ部分に含まれる優先度情報や該パケットを用いて通信を行っているアプリケーションの属性を示す情報を参照し、該パケットが転送されるべき出力リンクへより優先度の高いパケットが転送されている場合は、該パケットの転送を一旦停止するなど、それぞれの出力リンクにおけるパケット転送のタイミングを制御する処理、
（３）所定の出力ポートにおいて許されている最大パケット長を越える場合は予め定められた手法に従って該パケットを分割する処理、
（４）パケットの所定の情報をインクリメントし、予め定められた数値に達したならば該パケットを廃棄する処理、
（５）必要に応じて宛先アドレスや送出元アドレスの値を所定の方法に従って書き換える処理、
（６）必要に応じてパケットの誤り訂正符号を計算する処理、
など種々の処理がある。
【０００４】
歴史的に言ってパケットを処理する装置はミニコンピュータとかマイクロプロセッサといった情報処理装置にて実現されてきた。この場合、上述のパケット毎に行われる所定の処理は、ミニコンピュータとかマイクロプロセッサにて所定の命令列を実行することによって実現される。しかしながら、この手法の場合、高速なパケット処理は困難であった。このため、近年では、パケット処理をハードウェア化し、高速化を図ることが行われている。
【０００５】
ところが、インターネットのプロトコルには、常に変化をし続けるという特性がある。例えば、数年前まではパケット中の宛先アドレスや送出元アドレスはインターネット内部で書き換えられることはなかったが、近年のインターネットブームによりＩＰアドレスが枯渇してしまったことへの解決策として、インターネット内部で宛先アドレスや送出元アドレスを書き換えることがここ２〜３年の間に一般的になった。
【０００６】
このように、インターネットでは、ネットワークを運用し、運用している最中に問題が発生したならその問題を解決するようにプロトコルを書き換えていくということが行われる。この結果として、インターネットのプロトコルは常に変化し続ける。したがって、上述のような、高速にパケットを処理するためにプロトコル処理をハードウェア化する手法には、プロトコルに加えられた変更が細かなものであっても、そのハードウェアでは処理できなくなってしまい、結果としてパケット処理装置を交換する頻度が高まってしまうという問題がある。
【０００７】
また、例えばＩＰパケットのヘッダの宛先アドレスを解析する処理など、パケットを処理するために必要となるそれぞれの機能を実現するための手法は今までに種々提案されてきているが、それぞれの機能実現手法の利点を考えると、各々の機能実現手法を適用するのに適した領域が存在するが、従来技術によるパケット処理装置ではこれらの複数の機能実現手法から適切な手法を簡便に選択する手段が設けられておらず、パケットの処理手法のうちのひとつを選択して実装されているに過ぎなかった。この結果、例えばパケット種別の混在比率といったネットワーク環境によって最適な手法を選択することができず、効率的なパケット処理を実行することができなかった。
【０００８】
【発明が解決しようとする課題】
以上説明したように、従来技術によるパケット処理装置は、（１）ミニコンピュータやマイクロプロセッサにて所定の命令列を実行することで実現した場合には高速な処理が困難である、（２）パケット処理をハードウェア化することで実現した場合にはプロトコルの変化に柔軟に対処できない、（３）ネットワーク環境によって最適な機能実現手法を選択できない、という問題点があった。
【０００９】
本発明は、上記事情を考慮してなされたもので、高速にパケット処理を行うことができ且つプロトコル変更への適用性に富み、さらにネットワーク環境によって最適な機能実現手法を選択可能なパケット処理装置及びパケット処理方法を提供することを目的とする。
【００１０】
【課題を解決するための手段】
本発明に係るパケット処理装置は、入力されたパケットのヘッダ部分から、該パケットの持つパケット種別が予め定められた複数種類のパケット種別のうちのいずれのパケット種別に該当するかを決定付けるために予め定められた複数のビット列を抽出し、この抽出された複数のビット列の値に基づいて、該複数のビット列により決定付けられるパケット種別を持つ入力パケットに対して施すべき処理の少なくとも一部を特定可能なパケット種別情報（ダイジェスト情報）を１つ作成するパケット種別情報作成手段と、この作成されたパケット種別情報に基づいて得られる、該パケット種別情報に係るパケット種別を持つ入力パケットに作用させるべき命令列を用いて、前記入力パケットを処理するパケット処理手段とを備えたことを特徴とする。
【００１１】
なお、ビット列は１ビットの場合も含む。ビット列は、例えば、データリンク層ヘッダ、ネットワーク層ヘッダ、あるいはトランスポート層ヘッダの或るフィールドまたはその一部である。
【００１２】
ダイジェスト情報に対応する命令列は、予め実行可能なものを用意しておいても選択するようにしてもよいし、実行可能な命令列のもととなるものを予め用意しておき、これをもとに実行可能な命令列を作成するようにしてもよい。
【００１３】
プロセッサで所定の命令列を逐次実行していく従来方式では、パケットのヘッダ内のあるフィールドを見て処理を分岐させ、また別のフィールドを見てさらに処理を分岐させてゆくため、プロセッサ内部のパイプラインの乱れが生じやすく、処理が遅くなる。これに対して本発明では、パケットの処理に入る前に、ダイジェスト情報作成手段が、複数のフィールドを見てそのパケットの種別に適した処理内容を特定するダイジェスト情報を発生し、これにより特定される処理内容を予め選んでプロセッサに実行させるため、プロセッサのパイプラインの乱れを予防することができ、高速にパケット処理を行うことができる。
【００１４】
また、ダイジェスト情報の作成方法や対応する処理内容（またはそのもととなるもの）を書き換え可能にすることで、プロトコル変更にも柔軟に対処することができる。
【００１５】
好ましくは、前記ダイジェスト情報作成手段は、各ダイジェスト情報に対応する前記複数のビット列の各ビットパターンを保持し、入力された前記パケットから抽出された前記複数のビット列の値とこの保持されたビットパターンとを比較することにより、前記ダイジェスト情報を作成する手段を含むようにしてもよい。これにより、半導体メモリを使用することで、保持するフィールドやビットパターンを外部から容易に書き換え可能にすることができるので、プロトコル仕様の変化に柔軟に対応できる。さらに、パケット種別の混在比率の変化等といったネットワーク環境の変化に応じて、ダイジェスト情報を適切な詳細構成にする事が可能になり、効率的なプロトコル実行の可能なパケット処理装置を提供することができる。
【００１６】
好ましくは、前記ダイジェスト情報作成手段は、予め定められたダイジェスト情報に対応する複数のビット列の各ビットパターンを入力としたときに当該ダイジェスト情報が出力となる論理演算を、入力された前記パケットから抽出された前記複数のビット列の値に作用させることによって、前記ダイジェスト情報を作成する手段を含むようにしてもよい。これにより、高速にダイジェスト情報を作成することができる。なお、この場合、論理設計はより複雑にはなるが、論理演算の内容を外部から指定可能とするように設計することで、プロトコル仕様の変化に柔軟に対応することも可能となる。さらに、パケット種別の混在比率の変化等といったネットワーク環境の変化に応じて、ダイジェスト情報を適切な詳細構成にする事が可能になり、効率的なプロトコル実行の可能なパケット処理装置を提供することができる。
【００１７】
好ましくは、前記パケット処理手段が或るパケットに対して処理を行っている間に、前記ダイジェスト情報作成手段は次のパケットに対するダイジェスト情報を作成するものであるようにしてもよい。このような大きな処理のパイプライン化によって、更にパケット処理を高速化することができる。
【００１８】
好ましくは、前記パケット処理手段は、複数のダイジェスト情報にそれぞれ対応する複数の処理ルーチンを記憶するプログラムメモリと、前記ダイジェスト情報作成手段により作成されたダイジェスト情報を割り込み信号として、前記プログラムメモリに記憶された複数の処理ルーチンのうちの該ダイジェスト情報により特定される一つを起動して実行するプロセッサとを含むようにしてもよい。
【００１９】
好ましくは、前記ダイジェスト情報作成手段は、入力された前記パケットから前記処理に共されるパラメータをも抽出し、作成された前記ダイジェスト情報とともに該パラメータを前記パケット処理手段に渡し、前記パケット処理手段は、前記ダイジェスト情報に基づいて得られた前記命令列と前記パラメータとを用いて前記パケットを処理するものであるようにしてもよい。これによって、更にパケット処理を高速化することができる。
【００２０】
好ましくは、前記パケット処理手段は、マイクロ命令列をパイプライン処理する命令処理部と、複数のダイジェスト情報にそれぞれ対応する複数のマイクロ命令列を記憶する命令列テーブルと、前記ダイジェスト情報作成手段により作成されたダイジェスト情報に従って前記命令列テーブルから選択されたマイクロ命令列を前記命令処理部に与える手段とを含むようにしてもよい。この結果、命令テーブルにマイクロ命令をストアするので、命令列テーブルを書き換え可能に構成すれば、プロトコル仕様の変更等に対して柔軟に対応できる。
【００２１】
好ましくは、前記パケット処理手段は、マイクロ命令列をパイプライン処理する命令処理部と、複数のダイジェスト情報にそれぞれ対応する複数のマクロ命令列を記憶する命令列テーブルと、前記ダイジェスト情報作成手段により作成されたダイジェスト情報に従って前記命令列テーブルから選択されたマクロ命令列を、マイクロ命令に変換する手段と、生成されたこのマイクロ命令を前記命令処理部に与える手段とを含むようにしてもよい。この結果、命令テーブルにマクロ命令をストアするので、命令列テーブルを低容量化することができる。また、命令列テーブルを書き換え可能に構成すれば、プロトコル仕様の変更等に対して柔軟に対応できる。
【００２２】
好ましくは、前記ダイジェスト情報作成手段は、入力された前記パケットから前記処理に用いられるパラメータをも抽出し、該パラメータを作成された前記ダイジェスト情報と共に前記パケット処理手段に渡し、前記パケット処理手段は、マイクロ命令列をパイプライン処理する命令処理部と、複数のダイジェスト情報にそれぞれ対応する複数のマクロ命令列を記憶する命令列テーブルと、前記ダイジェスト情報作成手段により作成されたダイジェスト情報に従って前記命令列テーブルから選択されたマクロ命令列を、前記パラメータを反映させながら、マイクロ命令に変換する手段と、生成されたこのマイクロ命令を前記命令処理部に与える手段とを含むようにしてもよい。この結果、命令テーブルにマクロ命令をストアするので、命令列テーブルを低容量化することができるとともに、パケット処理を更に高速化することができる。また、命令列テーブルを書き換え可能に構成すれば、プロトコル仕様の変更等に対して柔軟に対応できる。
【００２３】
好ましくは、前記命令処理部は、前記命令列テーブルから選択された命令列と、パケットに対する処理以外の処理を行うためにメインメモリに書き込まれた命令列とを交互に実行可能に構成されたものであるようにしてもよい。これによって、別のアプリケーションも動かすことができる。
【００２４】
好ましくは、自装置が接続されるネットワークにおけるパケット種別の混在比率に応じて該パケット種別に対応するダイジェスト情報を記憶する記憶手段を更に備え、前記ダイジェスト情報作成手段は、入力された前記パケットに対して前記パケット種別に対応するダイジェスト情報が前記記憶手段に記憶されていない場合には、その他を示すダイジェスト情報を作成し、前記パケット処理手段は、その他を示すダイジェスト情報を渡された場合には、入力された前記パケットに対してパケット種別を予め特定せずにパケット種別を調べながら処理を行うものであるようにしてもよい。このようにすることによって、用意できるダイジェスト情報の数が限られる場合に、ネットワークで混在比率の高いパケット種別に優先的にダイジェスト情報を割り当てておけば、大部分のトラフィックに対してはパケット種別毎に特化した処理を予め選んで実行でき（速い）、さらに、割り当てができなかった少数のパケット種別はその他として汎用の（遅い）パケット処理を施すようにすると、多数のダイジェスト情報を準備することなく、また、その性能をあまり劣化させることなく、全てのパケット種別に対して処理を行うことができる。
【００２５】
好ましくは、前記パケット処理手段は、ネットワークから入力された前記パケットが所望の宛先に転送されるよう、該パケットを自装置から前記ネットワークへ出力するための処理（フォワーディング）を行うものであるようにしてもよい。
【００２６】
好ましくは、前記ダイジェスト情報作成手段は、前記入力パケットの宛先情報から作成される付加情報を含む前記ダイジェスト情報を前記パケット処理手段に渡し、前記パケット処理手段は、複数の方路情報テーブル検索手段のうちの一つを、前記付加情報に従って選択し、該選択された方路情報テーブル検索手段を用いて方路情報テーブルを検索することで、前記入力パケットの出方路を決定するようにしてもよい。これにより、例えば方路テーブル中のある領域と別の領域で検索アルゴリズムを変化させることができるようになり、それらの領域における宛先アドレスの出現分布に応じて適切な検索アルゴリズムを選択できるようになる。この結果、よりパケット処理をより高いスループットで実行可能となる。
【００２７】
本発明に係るパケット処理方法は、入力されたパケットのヘッダ部分から、該パケットの持つパケット種別が予め定められた複数種類のパケット種別のうちのいずれのパケット種別に該当するかを決定付けるために予め定められた複数のビット列を抽出し、この抽出された複数のビット列の値に基づいて、該複数のビット列により決定付けられるパケット種別を持つ入力パケットに対して施すべき処理の少なくとも一部を特定可能なパケット種別情報（ダイジェスト情報）を１つ作成し、この作成されたパケット種別情報に基づいて、該パケット種別情報に係るパケット種別を持つ入力パケットに作用させるべき命令列を選択し、この選択された命令列を用いて、前記入力パケットを処理することを特徴とする。
【００２８】
また、本発明に係るパケット処理方法は、入力されたパケットのヘッダ部分から、該パケットの持つパケット種別が予め定められた複数種類のパケット種別のうちのいずれのパケット種別に該当するかを決定付けるために予め定められた複数のビット列を抽出し、この抽出された複数のビット列の値に基づいて、該複数のビット列により決定付けられるパケット種別を持つ入力パケットに対して施すべき処理の少なくとも一部を特定可能なパケット種別情報（ダイジェスト情報）を１つ作成し、この作成されたパケット種別情報に基づいて、該パケット種別情報に係るパケット種別を持つ入力パケットに作用させるべき命令列を生成し、この生成された命令列を用いて、前記入力パケットを処理することを特徴とする。
【００２９】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
【００３０】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００３１】
（第１の実施形態）
図１に、本発明の第１の実施形態に係るパケット処理装置（もしくはメッセージ処理装置）の構成例を示す。
【００３２】
図１に示されるように、本実施形態のパケット処理装置は、ダイジェスト作成部１０１、パケット処理部（パケットフォワーダ）１０２、パケット送出部１０３を備えている。
【００３３】
このパケット処理装置に到着したパケットは、まず、ダイジェスト作成部１０１に入力される。
【００３４】
ダイジェスト作成部１０１は、入力されたパケットのヘッダ部分を参照し、該ヘッダ部分から予め定められた複数のビット列（ビット列は１ｂｉｔの場合も含む）を抽出し、抽出した複数のビット列にパターンマッチングや論理演算などを施すことによって、該パケットのダイジェスト情報を作成する処理を行う。
【００３５】
「ビット列」とは、例えば、パケットヘッダ内の、プロトコル仕様で規定されたフィールドの全て、もしくはその一部である。
【００３６】
上記のようにダイジェスト情報は、それぞれのパケットのヘッダ部分の予め定められた位置を参照することによって得られるパケット種別を表す情報であるが、具体的には、例えば、
（１）イーサネットフレームのＩＰｖ４パケット，ＵＤＰ、
（２）イーサネットフレームのＩＰｖ４パケット，ＴＣＰのＳＹＮ／ＦＩＮメッセージ、
（３）イーサネットフレームのＩＰｖ４パケット，ＩＣＭＰメッセージ、
（４）その他、
の４種類とする例が考えられる。
【００３７】
なお、ダイジェスト情報を４種類とした場合、ダイジェスト情報は２ｂｉｔのデータであって構わない。
【００３８】
もちろん上記の他にもダイジェスト作成部１０１が発生するダイジェスト情報の詳細構成は種々考えられる。例えば、入力されたイーサネットフレームもしくはＩＰパケットが、ブロードキャスト、もしくは、マルチキャスト、もしくは、ユニキャストである、といった分類であるとか、入力されたＩＰパケットが前提としているトランスポートプロトコルがＵＤＰもしくはＴＣＰである、といった分類を基にしてダイジェスト情報を構成することも可能である。しかしながら、本実施形態では説明が煩雑になるのを防ぐためダイジェスト情報は上記の４種類で構成されるものとして説明する。なお、ダイジェスト情報には、ここで説明した様なパケット種別を表す情報の他、方路情報テーブルの検索アルゴリズムとして最適なものを選択する目的のパケットの宛先アドレスから作成される情報、であるとか、ＱｏＳを提供する目的のパケットの優先順位を表す情報であるとかいった情報も含ませる事が可能である。このようなダイジェスト情報の種々の変形に関しては、後ほど詳細に説明を加える。
【００３９】
また、一例として、上記の４種類のダイジェスト情報を順に、“００”、“０１”、“１０”、“１１”とする。
【００４０】
さて、ダイジェスト情報を作成すると、ダイジェスト作成部１０１は、対応するパケットとともに該ダイジェスト情報をパケット処理部１０２に転送する。
【００４１】
パケット処理部１０２は、パケットとともに与えられたダイジェスト情報を用いて該パケットを処理して出力する。
【００４２】
例えば、ダイジェスト情報が“００”であった場合には、予め用意されたＵＤＰ用の処理ルーチンを起動して（もしくはこの時点でＵＤＰ用の処理ルーチンを生成し起動して）、該パケットを処理する。ダイジェスト情報が“０１”または“１０”であった場合にも同様である。また、ダイジェスト情報が“１１”であった場合にはその他のパケットであるので、汎用パケット用の処理ルーチンを起動して従来の通りにパケットの種別を分類しながら処理を行っていく。
【００４３】
また、パケット処理部１０２は、上記の処理の中において（もしくは上記の処理とは別に起動される処理において）、該パケットを出力すべき出力端（出力インタフェース）を指定する情報や該パケットを送出する際の優先度を指定する情報等を含む転送制御情報を作成して出力する処理を行う。転送制御情報の付加されたパケットは、パケット送出部１０３に入力される。
【００４４】
パケット送出部１０３は、入力されたパケットを、該パケットに付加された転送制御情報に従って所定の出力端を選択して出力する処理を行う。
【００４５】
図２に、ダイジェスト作成部１０１の一構成例を示す。
【００４６】
このダイジェスト作成部１０１は、入力されたパケットのヘッダ部分の予め定められた部分を抽出するヘッダ情報抽出部２０１と、該ヘッダ情報抽出部２０１の抽出した情報が、予め定められたビットパタンになっているか否かを判定してダイジェスト情報を作成するパターンマッチ部２０２とからなる。
【００４７】
本実施形態で用いている具体例の場合、ヘッダ情報抽出部２０１は、パケットの図３に示す部分、すなわち、
・イーサネットヘッダ中のプロトコルタイプフィールド（３０１）、
・ＩＰヘッダ中のバージョンフィールド（３０２）、
・ＩＰヘッダ中のプロトコルフィールド（３０３）、
・ＴＣＰヘッダ中のＳＹＮフラグ（３０４）、
・ＴＣＰヘッダ中のＦＩＮフラグ（３０５）、
を抽出する。
【００４８】
パターンマッチ部２０２は、これらの抽出されたフィールドの値を検査することで、上述のどのダイジェスト情報を出力するか判定する。
【００４９】
例えば、
イーサネットヘッダ中のプロトコルタイプフィールドの値が“０８００”、
ＩＰヘッダ中のバージョンフィールドの値が“４”、
ＩＰヘッダ中のプロトコルフィールドの値が“６”であり、かつ、
ＴＣＰヘッダ中のＳＹＮフラグもしくはＦＩＮフラグが立っていたなら、
ＴＣＰのＳＹＮ／ＦＩＮメッセージであると判定することになる。
【００５０】
なお、図２の構成例では、パターンマッチ部２０２がパターンマッチングを行うことによってダイジェスト情報を求めたが、その代わりに、ヘッダ情報抽出部２０１から与えられたビットパタンを入力とし、ダイジェスト情報を出力する論理演算により、ダイジェスト情報を求めるようにしてもよい。
【００５１】
なお、ダイジェスト作成部１０１において、抽出される複数のビット列や、マッチングを用いる場合におけるマッチングのとられるビットパターンあるいは論理演算を用いる場合における論理演算の内容は、それぞれ外部から変更可能とすることが望ましい。これによって、ダイジェスト情報の詳細構成を変化させることで、プロトコル仕様の変化に柔軟に対応できると共に、本パケット処理装置が適用される環境におけるパケット種別の混在比率に応じてダイジェスト情報を最適化することが可能になる。
【００５２】
また、図４に示すように、ダイジェスト作成部１０１は、入力パケットから抽出された所定の情報を（あるいはさらにこれを加工したものを）付加情報（パラメータ）として、ダイジェスト情報とともに、パケット処理部１０２に渡すようにしてもよい。パケット処理部１０２は、受け取ったパラメータを利用することによって、例えば処理の高速化などを図ることができる。
【００５３】
図５に、パケット処理部１０２の構成例を示す。
【００５４】
このパケット処理部１０２は、プログラムメモリ４０１、プロセッサ４０２、パケットバッファ４０３、入出力ポート４０４を含む。
【００５５】
プログラムメモリ４０１には、ダイジェスト情報のそれぞれに対応する処理ルーチンが格納されている。
【００５６】
本実施形態で用いている具体例の場合、プログラムメモリ４０１には、
（１）イーサネットフレームのＩＰｖ４パケット、ＵＤＰ、
（２）イーサネットフレームのＩＰｖ４パケット、ＴＣＰのＳＹＮ／ＦＩＮメッセージ、
（３）イーサネットフレームのＩＰｖ４パケット、ＩＣＭＰメッセージ、
（４）その他、
のそれぞれに対応して、
（１）ＵＤＰ処理ルーチン（４０１１）、
（２）ＴＣＰのＳＹＮ／ＦＩＮ処理ルーチン（４０１２）、
（３）ＩＣＭＰ処理ルーチン（４０１３）、
（４）汎用パケット処理ルーチン（４０１４）、
が格納されている。
【００５７】
ダイジェスト作成部１０１より入力されたパケットは、パケットバッファ４０３に一旦書き込まれる。一方、該パケットとともに与えられたダイジェスト情報は、プロセッサ４０２に割り込み信号として与えられる。プロセッサ４０２は、ダイジェスト情報に従って該当処理ルーチンを起動し、該パケットを処理して、入出力ポート４０４を通じて転送制御情報とともにパケット送出部１０３へと該パケットを送出する。
【００５８】
なお、予め実行可能な処理ルーチンを用意しておくのではなく、実行可能な処理ルーチンのもととなる（実行可能でない）プログラムを用意しておき、ダイジェスト情報を受けた時点で該当するプログラムから実行可能な処理ルーチンを生成するようにしても良い。これは、例えば、バイナリイメージとして保持されている処理ルーチンのもととなるプログラムの予め定められた部位に、図４に示した付加情報に基づいて作成されるビット列を埋め込むことで実現されても良い。
【００５９】
ここで、ダイジェスト作成部１０１により予めそれぞれのパケットの属性が区別されており、それらの属性に従った処理ルーチンが起動されるので、全てを汎用パケット処理ルーチンで実行する時に比べ、処理ルーチン内部の分岐の数を減らすことができ、もってプロセッサ内部のパイプラインの乱れを減らす事が可能になると同時に、それらの属性に従って処理ルーチンに最適化を施すこともでき、これによってパケット処理装置のスループットを向上させることができる。
【００６０】
さて、以下では、より詳細な構成例のバリエーションについて幾つか説明する。
【００６１】
まず、ダイジェスト作成部１０１とパケット処理部１０２とを独立実行する場合について説明する。
【００６２】
前述の通り、従来のようにパケットの種別を分類しながら処理しているのでは分岐が多く時間がかかり問題であった。そこで、本実施形態では、種別の分類に関する分岐をダイジェスト作成部１０１で行い、パケットの宛先などにより出力経路などを求める処理をパケット処理部１０２で行う。
【００６３】
このダイジェスト作成部１０１とパケット処理部１０２とは独立して動作させるようにするのが好ましい。
【００６４】
そのためには、例えば、それらの間をパケットのキューで結合する必要がある。ＬＳＩとして構成する場合、必要となるメモリ量、及びそのメモリへのアクセス回数が少ない構成とするのが望ましい。そこで、ここでは、図１で示した実施例の変形として、図６に示すような構成を考える。
【００６５】
外部から入力されたパケットは、メモリ管理部１２１の制御のもと、パケットメモリ１２２へ格納される。その後、第１のキュー１２３に、パケットを格納したメモリアドレスと入力インタフェースの状態を表す情報とが一つのエントリとして挿入される。
【００６６】
ダイジェスト作成部１０１は、処理すべきパケットを格納したメモリアドレスを含むエントリを第１のキュー１２３から取り出し、メモリ管理部１２１を経由してパケットメモリ１２２へとアクセスして必要な情報を確保し、ダイジェスト作成を行う。
【００６７】
作成されたダイジェスト情報は、パケットのメモリアドレスと入力インタフェース状態情報とともに、一つのエントリとして、第２のキュー１２４に挿入される。
【００６８】
パケット処理部１０２は、処理すべきパケットを含むエントリを第２のキュー１２４から取り出し、ダイジェスト情報に基づいた処理を行う。このとき、必要に応じてパケットメモリ１２２上のパケットに対して処理を施す。その後、処理の施されたパケットを格納しているアドレスと出力インタフェースを特定する情報とをパケット送出部１０３に転送する。パケット送出部１０３は、これらの情報をもとに、指定されたパケットを指定された出力端へと転送する。
【００６９】
この構成により、必要メモリ量を抑えつつ、ダイジェスト作成部１０１とパケット処理部１０２が、それぞれが異なるパケットを対象として処理を行なえるようになり、パイプライン並列動作することになる。また、ダイジェスト作成部１０１とパケット処理部１０２において処理時間がパケットごとに異なる場合でも、第２のキュー１２４の長さを十分確保すれば、処理時間の揺らぎを吸収することが可能である。
【００７０】
次に、上で述べた構成例のさらなる変形として、図７に示す構成の場合についてその動作を説明する。
【００７１】
外部から入力されたパケットは、入力インタフェースの状態を表す情報とともに、ダイジェスト作成部１０１へと入力される。ダイジェスト作成部１０１は直ちにダイジェスト作成を行い、作成したダイジェスト情報をパケットと入力インタフェース状態情報とともに、一つのエントリとして第３のキュー１２５に挿入する。パケット処理部１０２は、第３のキュー１２５に入力されたパケットを取り出し、付加されているダイジェスト情報を元にパケットに対して処理を加え、パケット送出部１０３へと該パケットを送出すべき出力端の情報と共に出力する。パケット送出部１０３は、与えられた情報を元に、パケットを所望の出力端へと出力する。
【００７２】
この場合、ダイジェスト作成部１０１はパケットメモリ１２２を参照することなくダイジェスト作成を行うことになるが、その利点としては、パケットメモリ１２２へのアクセスの競合がパケット処理部１０２との間に生じることを軽減するというものがある。また、入力インタフェースの機能の一部であると本実施例ではしているような機能をもダイジェスト作成手段に取り込むことが可能である。このような例として、リンク層でのフレーム同期やＣＲＣ演算に代表されるビットストリームを対象とするものがある。
【００７３】
次に、図５に示したパケット処理部１０２のより詳細な動作で、パケット到着時の割り込みを実現する構成例をここに示す。割り込み処理を実現する場合、いかに割り込み受付を禁止するか、といったことが技術上の課題となる。
【００７４】
プロセッサ４０２は、ダイジェスト情報を格納するレジスタが二組持つ。一つは、現在処理中のパケットに対応するダイジェスト情報を格納するものであり、もう一つは、ペンディング状態のパケットに対応するものを格納するものである。前者を処理中レジスタ、また、後者をペンディングレジスタと、それぞれ呼ぶ。
【００７５】
プロセッサ４０２にダイジェスト情報が到着すると、該ダイジェスト情報はまずペンディングレジスタに格納される。ペンディングレジスタにダイジェスト情報が到着すると、ダイジェスト情報から割り込み番号を作成し、プロセッサ４０２に割り込みがかけられる。
【００７６】
プロセッサ４０２にて割り込みが受理されると、割り込みルーチンとして存在するパケット処理プログラムに制御が移る。これと同時に、ダイジェスト情報が処理中レジスタに転送される。もし、パケット処理部１０２とダイジェスト生成部１０１の間にキューが存在するならば、このキューにキューイングされているダイジェスト情報はキューを進み、先頭のものが、ペンディングレジスタへと転送される。
【００７７】
プロセッサ４０２は、パケット処理プログラムを実行中は、割り込み禁止状態にある。パケットの処理が完了時点で、割り込み禁止解除命令を実行することにより、次のダイジェスト情報の処理が開始される。
【００７８】
ところで、上記では、ダイジェスト情報の作成とパケット処理ルーチンの構成方法について、パケットに施す処理の違いに応じて分類する場合を例にとって説明したが、必ずしも処理の違いだけが分類方法ではない。次に、ダイジェスト情報の種々の変形について説明する。
【００７９】
例えば、同一の処理を行う場合においても、複数の実現手段が存在する場合がある。例えば、パケット処理部１０２においては、パケットのヘッダの特定のフィールドを鍵としてデータベース（図示せず）の検索を行う、ということが頻繁に行われる。データベースの検索アルゴリズムが複数あり、ある主の鍵とその鍵のデータベース上の分布に応じて、検索の演算量や検索の遅延が異なるとする。このような例は、ネットワークアドレスを鍵として出力端（出力インタフェース）を決定するというデータベース検索ではよくあることである。
【００８０】
かりに、検索アルゴリズムが４種類あるとし、検索の鍵が３２ｂｉｔのフィールドであるとする。この３２ｂｉｔの空間を１２８等分し、それぞれについて平均的に最も効率の良い検索アルゴリズムを決定する。この作業は、データベースの特性によっても決まるもので、パケットの処理という実時間処理とは別にオフラインで行うものである。その結果、３２ｂｉｔの上位７ｂｉｔと検索アルゴリズムを指定する２ｂｉｔの識別子との対応関係が決まる。検索アルゴリズムを特定する情報もダイジェスト情報に含めるものとし、ダイジェスト作成部１０１が、上で述べた、３２ｂｉｔのネットワークアドレスの上位７ｂｉｔから該検索アルゴリズムを特定するような情報も作成することとしても良い。このようなダイジェスト情報であっても、半導体メモリによって実現されるテーブルルックアップによっても、また、何らかの論理演算によっても、作成することができる。
【００８１】
また、ダイジェスト生成部１０１において、パケットのヘッダからダイジェスト作成の対象となるビット列を複数抽出しているが、これらのビット列はパケット処理部１０２においても再度抽出する必要のあることが多い。ビット列の抽出には通常シフト演算やマスク演算を伴うものであり、すでにダイジェスト作成部１０１で行ったこれらの操作をパケット処理部１０２で再び行う必要はなく、これを省略しダイジェスト情報の一部として該抽出した情報を直接パケット処理部１０２に通知することは、パケット処理部１０２の負担の軽減となり、またパケットバッファへの読み出し要求の低減ともなり、スループットの向上につながる。
【００８２】
次に、ダイジェスト作成部１０１からパケット処理部１０２にダイジェスト情報とともにパラメータを渡す場合について説明する。
【００８３】
ダイジェスト作成部１０１では、ダイジェスト情報のための複数のビット列の抽出とは別に、予め定められた１または複数のビット列を抽出し、（１）該１または複数のビット列、または（２）該１または複数のビット列に、ダイジェスト情報のために抽出した複数のビット列の全部または一部のデータを加えたもの、または（３）上記１のデータを加工したもの、または（４）上記２のデータを加工したものを、パラメータとしてパケット処理部１０２に渡すようにしてもよい。あるいは、（５）ダイジェスト情報のために抽出した複数のビット列の全部または一部、または（６）上記５のデータを加工したものを、パラメータとしてパケット処理部１０２に渡すようにしてもよい。なお、パケットヘッダ全体を、付加情報とする方法もある。
【００８４】
ダイジェスト情報を生成している過程で作られているパラメータは、パケット処理部１０２でも有効に利用することができる（ただし、このようなパラメータは副作用の無いような使い方をするのが好ましい）。
【００８５】
例えば、パケット処理部１０２で、あるフィールドの値を鍵としてデータベース（図示せず）を検索する場合であって、ダイジェスト情報の作成にあたり、同じフィールドの一部あるいは全部を用いてハッシュ演算を行う場合を例にとる。この場合、データベースの鍵をそのハッシュ関数により分類して小さいデータベースの直和に分割すると、検索対象となる鍵の総数を減らせることにより、検索アルゴリズムが鍵の総数に比例する計算量を要する場合には、処理の高速化を図ることにつながる。
【００８６】
また、次のようなパケット処理部１０２を考えることができる。
【００８７】
パケット処理部１０２において、データベースの検索の高速化を図るため、頻繁に利用されるデータを高速のキャッシュメモリに一時的に蓄えることが多い。このとき、キャッシュ上のデータと実際に到着したパケットに対する検索操作で必要となるデータの関連性が高いほど、キャッシュのヒット率が高く、高速化に貢献する。
【００８８】
関連性の高いデータをキャッシュ上に存在する可能性を高める手法として、プリフェッチ操作という手法がよく使われる。これは、主記憶からキャッシュへの読み出しを投機的に行うもので、近い将来に参照される可能性の高いものを予め読んでおくことである。読み出すことによる副作用の無い場合に限って行われるもので、キャッシュに読み込んだデータが実際に使われなくてもよい。
【００８９】
このプリフェッチ操作が効果的であるためには、プリフェッチから使用するまでに経過する時間を主記憶からキャッシュへの読み出し遅延よりも十分に長く取っておく、つまり、十分に前もってプリフェッチ操作を行う必要がある。
【００９０】
ところが、パケットが到着してからパケットのフィールドを抽出しこれをもとにデータベースのアドレスを求めてプロフェッチを行ったのでは、プリフェッチの効果を得るだけの遅延時間を稼ぐことが難しい。
【００９１】
ダイジェスト作成部１０１で抽出するビット列として、データベースの検索の鍵となる部分を含むビット列を採用し、データベースの検索のメモリアクセスのアドレスとなる値をダイジェスト生成の中間結果として得られるようなダイジェスト作成方法を採用する。具体的には、例えば、データベース検索アルゴリズムとしてハッシュ表を用いるものであって、先に述べたようにそのハッシュ表で用いるハッシュ関数と同じものを用いてダイジェスト情報を作成する、という構成方法をとる。
【００９２】
ダイジェスト情報作成に関わる演算の中間結果として、ハッシュ表へのアクセスのアドレスとなるものが既に計算されているのであるから、これをダイジェスト情報に付加されるパラメータとしてパケット処理部１０２に通知する。パケット処理部１０２では、パケット処理ルーチンに入ると同時に、受け取ったパラメータの値をデータベースのアドレスとしてプリフェッチ操作を行う。これにより、パケット処理のなるべく早い段階でプリフェッチ操作を行うことが可能となり、遅延を隠蔽する効果が高くなる。
【００９３】
あるいは、ダイジェスト情報がパケット処理部１０２に通知された時点で、受け取ったパラメータの値を、データベースの検索のメモリアドレスと見なして、投機的に実行することも可能である。このときは、パケット処理ルーチンを起動する迄の時間もプリフェッチの遅延隠蔽の時間となるので、より一層プロフェッチの効果が期待できる。
【００９４】
また、以下のように、ダイジェスト情報のさらなる変形として、パケットの優先制御の情報もダイジェスト情報に含めることが可能である。
【００９５】
まず、パケットの優先制御情報と、パケットの上位プロトコルを指定するプロトコル識別子の２つの組み合わせを考える。それぞれの指定によりパケットの処理方法は大きく異なる。これを単一のプログラムで実行することの非効率は既に述べた通りである。
【００９６】
ここで、優先情報が８ｂｉｔ、上位プロトコル指定が８ｂｉｔであるとすれば、単純な組み合わせは１６ｂｉｔとなる。その１つ１つについて最適化したプログラムを用意してもよい。
【００９７】
ところで、優先制御でも、類型の処理の場合を１つにまとめることが可能である。例えば、プロトコルも、同一の処理をするものはまとめて１つのプログラムで扱うことにすると、単純な組み合わせの数よりはかなり少ない数のプログラムで処理することが可能である。
【００９８】
８ｂｉｔの優先制御情報を、類型の処理ごとに分類して例えば３ｂｉｔの識別子に変換し、また、８ｂｉｔのプロトコル番号を類型の処理ごとに分類して例えば２ｂｉｔの識別子に変換する。こうしてできた３ｂｉｔと２ｂｉｔの識別子に、さらに何らかの論理演算（単純につなぎあわせるだけでもよい）で５ｂｉｔ程度の識別子に変換する。これをダイジェスト情報とする。パケット処理部１０２では、このダイジェスト情報をもとに、起動するパケット処理ルーチンを起動する。ここで述べている例では３２種類のパケット処理ルーチンのなかのひとつが選択されることとしてもよい。これらのパケット処理ルーチンのそれぞれは、３ｂｉｔの識別子で指定される、優先制御に係る処理を含むことになる。
【００９９】
ところで、ダイジェスト情報として用いられるビット数は有限である。例えば、パケット処理ルーチン（図５の４０１１〜４０１４参照）の格納容量を越える分類種別を生成することはできない。また、ダイジェスト作成部１０１とパケット処理部１０２との間の通信路のビット幅から来る制約もある。一方で、パケットの分類種別は、それが多ければより詳細なパケット種別の判別をダイジェスト作成部１０１で行うこととなり、パケット処理ルーチンをより特殊化して、パケット処理部１０２における処理性能の向上を図ることができる。
【０１００】
よって、ダイジェスト生成部１０１で作成されるダイジェスト情報のビット長はなるべく大きく取るのが望ましい一方で、パケット処理部１０２が同時に扱うダイジェスト情報の個数はなるべく小さく取るのが望ましい。以下、この両方の要求を満足する方法について説明する。
【０１０１】
ダイジェスト作成部１０１においては、仮想的にダイジェスト情報として大きなビット数の番号を作成する。この仮想的なダイジェスト情報に対応するパケット処理ルーチンが用意されている。
【０１０２】
図８に示すように、ダイジェスト作成部１０１とパケット処理部１０２とを結合するインタフェースには、仮想的なダイジェスト情報から、実際にパケット処理部１０２に通知可能であるビット数のダイジェスト情報に変換するためのダイジェスト情報変換部１２０を用意する。パケット処理部１０２に送られるダイジェスト情報は、このダイジェスト情報変換部１２０を利用して、仮想的なダイジェスト情報から物理的なダイジェスト情報に変換して作成される。
【０１０３】
ダイジェスト情報変換部１２０の制御機能により、仮想的なダイジェスト情報と物理的なダイジェスト情報との対応関係が決定されると、この対応関係は、ダイジェスト情報変換部１２０内の変換テーブルへの書き込み手段（図示せず）を介して、変換テーブルに反映されるとともに、仮想的なダイジェスト情報の分類種別に応じたパケット処理ルーチンが、物理的なダイジェスト情報に対応するパケット処理ルーチンとしてパケット処理部１０２のプログラムメモリに格納される。
【０１０４】
仮想的なダイジェスト情報は、物理的なダイジェスト情報よりも多ビット長のものであるから、物理的なダイジェスト情報を割り当てることができない仮想ダイジェスト情報が存在する。これらの仮想ダイジェスト情報は、「その他」を表す物理ダイジェスト情報を割り当て、「その他」を表す物理ダイジェスト情報に対応するパケット処理ルーチンとしては、パケット種別の分類を仮定することなく処理する汎用物理ルーチンを割り当て、プログラムメモリに格納する。
【０１０５】
汎用処理ルーチンの処理性能は、特殊化した処理ルーチンの処理性能に比べて劣るものであるから、汎用処理ルーチンを起動する頻度は最小限に抑えるのが望ましい。そのため、変換テーブルの制御手段は、本パケット処理装置の置かれる環境において、「その他」が選択される頻度がより少なくなるような、物理ダイジェスト情報から論理ダイジェスト情報への対応関係を見出し、これを変換テーブルに反映させるべきである。
【０１０６】
また、より効果的な変換テーブルを作成する手段として、次のような構成例がある。
【０１０７】
論理ダイジェスト情報から物理ダイジェスト情報への変換テーブルは、入力である論理ダイジェスト情報が入力された回数を数えるカウンタを、論理ダイジェスト情報ごとにもつ。
【０１０８】
変換テーブルの制御機能は、論理ダイジェスト情報の発生頻度を、個々のカウンタ値をもとに求め、より発生頻度の高い論理ダイジェスト情報に物理ダイジェスト情報を割り当てることが出来る。
【０１０９】
具体的には、次のような方法をとっても良い。
【０１１０】
初期状態として、すべての論理ダイジェスト情報に「その他」を表す物理ダイジェスト情報を割り当てる。その状態で、論理ダイジェスト情報の発生頻度を有意に計測可能となる程度にパケット処理装置が動作した後に、論理ダイジェスト情報と物理ダイジェスト情報との対応関係を決定し、変換テーブルに反映させる。その後も、発生頻度の計測を続け、先に求めた対応関係と有意な差異が認められると判定できる場合には、変換テーブルとパケット処理ルーチンとを、新たな対応関係を反映するものと入れ換える。
【０１１１】
（第２の実施形態）
図９に、本発明の第２の実施形態のパケット処理装置（もしくはメッセージ処理装置）の構成例を示す。
【０１１２】
図９に示されるように、本実施形態のパケット処理装置は、システムバス５０１、メインメモリ５０２、入出力ポート５０３、メモリアクセス制御部５０４、キャッシュ５０５、パイプライン５０６、レジスタ５０７、ダイジェスト作成部５０８、パケット処理命令列作成部５０９、マイクロ命令列テーブル５１０、命令列キュー５１１を備えている。
【０１１３】
ここで、メモリアクセス制御部５０４、キャッシュ５０５、パイプライン５０６、レジスタ５０７は、これらが一体となって動作し、メインメモリ５０２に含まれる命令列を解釈実行し、該命令列にて指定される処理をデータに対して施していく機能を担っており、ここではこれらを総称して命令処理部５２０と呼ぶ。
【０１１４】
なお、ここでは、キャッシュ５０５は、命令列の一部をキャッシュしておく命令キャッシュ５０５−１と、処理を受けるデータの一部をキャッシュしておくデータキャッシュ５０５−２とに分離されている。
【０１１５】
また、命令を実行するパイプライン５０６の構成は種々考えられるが、ここでは、フェッチ５０６−１、デコード５０６−２、演算５０６−３、メモリアクセス５０６−４、ライトバック５０６−５という良く知られた５ステージのパイプラインを仮定している。
【０１１６】
情報処理手順を示す命令列や処理を受けるデータを格納するメインメモリ５０２、外部との間でデータを入出力するためのハードウェアである入出力ポート５０３、ダイジェスト作成部５０８、パケット処理命令列作成部５０９、命令処理部５２０は、システムバス５０１によって接続されている。
【０１１７】
なお、本実施形態の基本的な構成・動作は第１の実施形態と同様であるので（バリエーション等の説明も同様である）、以下では、本実施形態では図９の構成に関する内容を中心に説明する。
【０１１８】
ダイジェスト作成部５０８は、第１の実施形態と同様であり、外部から入力されたパケットのヘッダ部分を受け取り、ダイジェスト情報を生成する。もちろん、第１の実施形態と同様に、併せて付加情報（パラメータ）を生成するようにしてもよい。
【０１１９】
パケット処理命令列作成部５０９は、ダイジェスト作成部５０８からダイジェスト情報を受け取り、後ほど説明する手法に従って、該パケットを処理するための命令列を作成し、命令列キュー５１１へと渡す機能を担っている。ここで、作成される命令列は、命令列テーブル５１０の内容を参照して作成される。
【０１２０】
外部から到着したパケットは、入出力ポート５０３、システムバス５０１を経由してメインメモリ５０２の予め定められた領域に格納される。
【０１２１】
この後に、その予め定められた部分（複数のビット列）、具体例としてはデータリンクレイヤのヘッダとネットワークレイヤのヘッダとトランスポートレイヤのヘッダ、が抽出され、ダイジェスト作成部５０８に渡される。この処理は、メインメモリ５０２に蓄えられた命令列で実行されることとして良い。なお、以降、説明のため、この予め定められた部分のことを処理制御情報と呼ぶ。また、この処理制御情報には、メインメモリ５０２のパケットが格納された位置を示す情報が含まれていても良い。
【０１２２】
ダイジェスト作成部５０８は、入出力ポート５０３から処理制御情報を受け取ると、該情報からダイジェスト情報を作成する。
【０１２３】
パケット処理命令列作成部５０９は、ダイジェスト作成部５０８からダイジェスト情報を受け取ると、命令列を作成する。
【０１２４】
ここでは、命令列テーブル５１０には、図１０に示されるように、それぞれのパケット種別に応じた処理を実現するための、実行可能な命令列（マイクロ命令の列）が保持されている。パケット処理命令列作成部５０９は、作成されたダイジェスト情報に従った命令列を、命令列テーブル５１０から読み出し、命令列キュー５１１に格納する。
【０１２５】
一方、命令処理部５２０は、自身の持つプログラムカウンタ（図示せず）に従ってメインメモリ５０２から命令キャッシュ５０５−１に命令列を読み込み、パイプライン５０６によって順次、該命令列を実行している。
【０１２６】
このとき、パイプライン５０６の各ステージは、それぞれに割り当てられた役割、すなわち、
・フェッチ５０６−１は、命令キャッシュ５０５−１から命令を読み取る、
・デコード５０６−２は、該命令をデコードして以降のパイプラインやレジスタ５０７の動作内容を決定する、
・演算５０６−３は、デコード５０６−２の指示に従ってレジスタ５０７から与えられたデータに処理を加える、
・メモリアクセス５０６−４は、演算５０６−３から与えられたデータをデータキャッシュ５０５−２を通じて書き込むかもしくは次ステージに渡す、
・ライトバック５０６−５は、メモリアクセス５０６−４から与えられたデータをレジスタ５０７に書き戻す、
といった役割を担っている。
【０１２７】
本パケット処理装置の場合、メインメモリ５０２上だけではなく、命令列キュー５１１にも処理しなければならない命令列が存在しているので、フェッチ５０６−１は、予め定められた条件、例えば、命令列キュー５１１が空でないときはメインメモリ５０２からの命令列と交互に、命令列キュー５１１上の命令も取り込み、以降の各ステージへと該取り込んだ命令を渡す。これによって、パケット処理命令列作成部５０９が作成した命令列が実行されることになり、もって入力されたパケットに対して所望の処理が行われることとなる。
【０１２８】
このように、複数の独立した命令列（すなわち、メインメモリ５０２からの命令列と命令列キュー５１１からの命令列）を交互に実行する場合、それぞれの命令列に対して排他的にレジスタを割り当てることにしてもよい。これにより、レジスタハザードによるパイプライン５０６の停止を防止することができる。
【０１２９】
本実施形態の場合、命令列テーブル５１０に、ダイジェスト情報に対応した処理ルーチンそれぞれの命令列が含まれているが、この命令列テーブル１０９を再構成可能なように、すなわちＲＡＭやフラッシュＲＯＭといった書き換え可能なメモリ媒体によって、構成することにすれば、それぞれの処理ルーチンを必要に応じて書き換えることが可能になり、プロトコルの詳細部分の規定が変更になっても、柔軟に対応できるようになる。この場合、命令列テーブル５１０をシステムバス５０１に接続し、メインメモリ５０２上の命令列の実行によって該命令列テーブル５１０を書き換えることができるように構成することも可能である。
【０１３０】
さらに、本実施形態の場合、パケット処理命令列作成部５０９の作成するプロトコル処理のための命令列と、命令処理部５２０が持つプログラムカウンタ（図示せず）に従ってメインメモリから読み出される命令列との２つが、メインメモリ５０２（のデータ蓄積領域）を容易に共有可能である。このため、例えば、メインメモリ５０２の上からの命令列にて実行されるオペレーティングシステム上のアプリケーションによる、パケット処理命令列作成部５０９からの命令列にて実行されるプロトコル処理の動作の監視制御なども容易に実現することができる。
【０１３１】
ところで、上記の構成例では、命令列テーブル５１０にはダイジェスト情報に対応した処理ルーチンが保持されているものとした。ここでの処理ルーチンはパイプライン５０６で直接実行可能なものであった。この場合、ダイジェスト情報に対応した処理ルーチンを命令列キュー５１１に入力する処理は簡単になるが、一方で命令列テーブル５１０の容量が大きくなる。
【０１３２】
図１１に、命令列テーブルの容量を削減することを可能としたパケット処理装置の構成例を示す。以下、図９の構成例と相違する点を中心に説明する。
【０１３３】
パケットに対して行わなければならない処理は、ＴＴＬフィールドをインクリメントする処理あるいはルーティングテーブルを検索する処理といった定型処理がほとんどであり、ＩＰやその他のプロトコルの規定に従ってパケットのヘッダ領域に書き込まれたプロトコルを指定する識別子やフラグ群によって、実際にパケットに対して加えなければならない定型処理群を決定することができる。
【０１３４】
これらの定型処理の各々をメインメモリ１０２上のパケットへ処理を加えるマクロ命令（マクロ命令はオペコードとパラメータを含むものである；パラメータを持たないマクロ命令もある）とし、ダイジェスト情報から決定される該パケットに対する処理ルーチンを、これらのマクロ命令の列、例えば、
ｆ１（メインメモリ上へのポインタ，パラメータ1-1，パラメータ1-2，…）
ｆ２（メインメモリ上へのポインタ，パラメータ2-1，パラメータ2-2，…）
ｆ３（メインメモリ上へのポインタ，パラメータ3-1，パラメータ3-2，…）
：
：
として表し、図１２に示すように、ダイジェスト情報を構成する個々のパケット種別に対応させてマクロ命令列テーブル５３１に格納しておく。
【０１３５】
また、図１３に示すように、各マクロ命令に対応するマイクロ命令列を格納したマイクロ命令テーブル５３２を用意しておく。
【０１３６】
パケット処理命令列作成部５０９は、ダイジェスト作成部５０８からダイジェスト情報を受けた後、マクロ命令列テーブル５３１からダイジェスト情報に対応するマクロ命令列を読み出し、該マクロ命令列の各マクロ命令について、そのオペコードをインデックスとしてマイクロ命令テーブル５３２から対応するマイクロ命令列を読み出し、該マクロ命令列を実現するマイクロ命令列を生成して、命令列キュー５１１に書き込む。
【０１３７】
このマイクロ命令が必要に応じてパラメータを参照しながらパケット処理を行う。
【０１３８】
なお、マイクロ命令テーブル５３２に格納されているものは、実際にはテンプレート（不完全な命令）であって、このテンプレートにパラメータがあて込まれてマイクロ命令が生成されるようにしてもよい。
【０１３９】
もちろん、上記の命令に関するパラメータ（もしくはそのもととなる情報）は、ダイジェスト作成部５０８からパケット処理命令列作成部５０９へ、ダイジェスト情報とともに渡すようにしてもよい。
【０１４０】
さて、第１、第２の実施形態のいずれの場合であっても、入力されたパケットのヘッダ部分をもとに、該パケットの種別をまず分類し、該分類された種別に対応してパケット処理の命令列を作成することにしたので、プロトコル処理の命令列に関しては、含まれる条件分岐の数を減少させることができる。従来技術においては、ヘッダ部のフィールドを順次読み取ってパケット種別を分類しつつ必要な処理を行っていたので、プロトコル処理の命令列には多数の条件分岐が含まれ、この結果、パイプラインの乱れが多数発生していた。これが、従来技術におけるプロトコル処理の高速化の１つのネックであった。本発明により、プロトコル処理を、含まれる条件分岐の数を減少させた命令列にて実行できるようになるので、パイプラインの乱れを最小限に抑え、パイプラインの能力を最大限発揮したプロトコル処理が可能になる。
【０１４１】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０１４２】
【発明の効果】
本発明によれば、入力されたパケットから該入力パケットに対して施すべき処理の少なくとも一部を特定可能なダイジェスト情報を１つ作成し、この作成されたダイジェスト情報に基づいて得られる該記入力パケットに作用させるべき命令列を用いて該入力パケットを処理するようにしたので、高速にパケット処理を行うことができるとともに、プロトコル変更にも柔軟に対処することができる。さらに、ダイジェスト情報をパケット種別などのネットワーク環境に応じて適切に変化させることで、より効率よくプロトコル処理を実現することも可能である。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るパケット処理装置の構成例を示す図
【図２】ダイジェスト作成部の構成例を示す図
【図３】抽出するフィールドの例を示す図
【図４】同実施の形態に係るパケット処理装置の他の構成例を示す図
【図５】パケット処理部の構成例を示す図
【図６】同実施の形態に係るパケット処理装置のさらに他の構成例を示す図
【図７】同実施の形態に係るパケット処理装置のさらに他の構成例を示す図
【図８】同実施の形態に係るパケット処理装置のさらに他の構成例を示す図
【図９】同実施の形態に係るパケット処理装置のさらに他の構成例を示す図
【図１０】マイクロ命令列テーブルの構成例を示す図
【図１１】同実施の形態に係るパケット処理装置のさらに他の構成例を示す図
【図１２】マクロ命令列テーブルの構成例を示す図
【図１３】マイクロ命令テーブルの構成例を示す図
【符号の説明】
１０１，５０８…ダイジェスト作成部
１０２…パケット処理部
１０３…パケット送出部
１２０…ダイジェスト情報変換部
１２１…メモリ管理部
１２２…パケットメモリ
１２３…第１のキュー
１２４…第２のキュー
１２５…第３のキュー
２０１…ヘッダ情報抽出部
２０２…パターンマッチ部
４０１…プログラムメモリ
４０２…プロセッサ
４０３…パケットバッファ
４０４…入出力ポート
５０１…システムバス
５０２…メインメモリ
５０３…入出力ポート
５０４…メモリアクセス制御部
５０５…キャッシュ
５０６…パイプライン
５０７…レジスタ
５０９…パケット処理命令列作成部
５１０…マイクロ命令列テーブル
５１１…命令列キュー
５２０…命令処理部
５３１…マクロ命令列テーブル
５３２…マイクロ命令テーブル
【図１】
0003643507.tif 000002
【図２】
0003643507.tif 000003
【図３】
0003643507.tif 000004
【図４】
0003643507.tif 000005
【図５】
0003643507.tif 000006
【図６】
0003643507.tif 000007
【図７】
0003643507.tif 000008
【図８】
0003643507.tif 000009
【図９】
0003643507.tif 000010
【図１０】
0003643507.tif 000011
【図１１】
0003643507.tif 000012
【図１２】
0003643507.tif 000013
【図１３】
0003643507.tif 000014