(57)【要約】【課題】  同時に複数のパケットを高速に処理することが可能なパケット転送装置を提供する。【解決手段】  各々が異なる複数のキーにそれぞれ対応づけられた複数の処理情報を含むルックアップテーブルから、複数のキーにそれぞれ対応する複数の処理情報を並行して検索し、検索された複数の処理情報の各々に基づいて、対応するパケットを処理する。【選択図】        図２
2007013246.tif 000002
【特許請求の範囲】
【請求項１】
パケットを順次受信するパケット受信手段と、
順次受信したパケットから、キーとなる情報を順次取得するキー取得手段と、
各々が、異なる値を有する複数のキーにそれぞれ対応づけられた複数の処理情報を含むルックアップテーブルを記憶する記憶手段と、
前記ルックアップテーブルから、前記複数のキーにそれぞれ対応する複数の処理情報を並行して検索するための検索手段と、
前記検索手段により検索された前記複数の処理情報の各々に基づいて、対応するパケットを処理するためのパケット処理手段とを備える、パケット転送装置。
【請求項２】
前記パケット処理手段は、受信した複数のパケットのうちの一部のパケットであって、複数の同種パケットについては、ｎ（自然数）番目に受信した同種パケットを処理した後、ｎ＋１番目に受信した同種パケットを処理する、請求項１に記載のパケット転送装置。
【請求項３】
前記検索手段は、複数の処理手段を含み、
前記複数の処理手段の各々は、互いに異なるキーを使用して、前記ルックアップテーブルから、前記互いに異なるキーに対応する処理情報を検索する、請求項１または請求項２に記載のパケット転送装置。
【請求項４】
前記ルックアップテーブルは、第１ルックアップテーブルと、第２ルックアップテーブルとを含み、
前記第２ルックアップテーブルは、前記第１ルックアップテーブルよりも多くの処理情報を含むテーブルであり、
前記多くの処理情報の各々には、互いに異なるキーが対応付けられており、
前記複数の処理手段の各々は、前記互いに異なるキーを使用して、前記第１ルックアップテーブルから、前記互いに異なるキーに対応する処理情報を検索した後、前記互いに異なるキーを使用して、前記第２ルックアップテーブルから、前記互いに異なるキーに対応する処理情報を検索する、請求項３に記載のパケット転送装置。
【請求項５】
前記ルックアップテーブルは、第１ルックアップテーブルと、第２ルックアップテーブルとを含み、
前記第２ルックアップテーブルは、前記第１ルックアップテーブルよりも多くの処理情報を含むテーブルであり、
前記多くの処理情報の各々には、互いに異なるキーが対応付けられており、
前記複数の処理手段のうちの一部の１以上の第１処理手段は、前記第１ルックアップテーブルに対して検索処理をし、
前記複数の処理手段のうち、前記１以上の第１処理手段以外の１以上の第２処理手段は、前記第２ルックアップテーブルに対して検索処理をし、
前記第１処理手段は、前記キーを使用して、前記第１ルックアップテーブルから、前記キーに対応する処理情報を検索し、検索結果を前記第２処理手段に送り、
前記第２処理手段は、取得した前記検索結果が所定の結果の場合、前記キーを使用して、前記第２ルックアップテーブルから、前記キーに対応する処理情報を検索する、請求項３に記載のパケット転送装置。
【請求項６】
前記記憶手段は、第１の記憶手段と、第２の記憶手段とを含み、
前記第１の記憶手段は、前記第２の記憶手段よりも高速アクセス可能なものであり、
前記第１ルックアップテーブルに含まれる複数の処理情報の各々は、高速に処理することが必要なパケットに対応する情報であり、
前記第２ルックアップテーブルに含まれる複数の処理情報の各々は、高速に処理することが不必要なパケットに対応する情報であり、
前記第１の記憶手段には、前記第１ルックアップテーブルが記憶され、
前記第２の記憶手段には、前記第２ルックアップテーブルが記憶される、請求項４または請求項５に記載のパケット転送装置。
【請求項７】
前記キーは、発信元ＩＰアドレス、発信先ＩＰアドレス、発信元ポート番号および発信先ポート番号の少なくとも１つからなる、請求項１〜請求項６のいずれかに記載のパケット転送装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット転送装置に関し、特に、受信したパケットに基づいて検索処理を行なうパケット転送装置に関する。
【背景技術】
【０００２】
近年のインターネットの急速なブロードバンド化に伴い、パケットを高速に転送する技術が求められている。パケットを高速に転送する技術は、特開２００３−２９８６１３号公報（特許文献１）（以下、従来技術Ａともいう）、特開２００３−１９８６０７号公報（特許文献２）（以下、従来技術Ｂともいう）、特開２００１−２２３７５０号公報（特許文献３）（以下、従来技術Ｃともいう）に開示されている。
【特許文献１】特開２００３−２９８６１３号公報
【特許文献２】特開２００３−１９８６０７号公報
【特許文献３】特開２００１−２２３７５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来技術Ａ，Ｂ，Ｃでは、受信したパケットの順番にパケットを処理する。したがって、たとえば、処理に時間の要するパケットを処理している間に、高速な転送が要求されるパケットを受信した場合、先のパケットの処理が終了しないと、次のパケットの処理に移れないという問題がある。そのため、１つのパケットのために、全体のパケットの処理速度が低下するという問題がある。
【０００４】
本発明は、上述の問題点を解決するためになされたものであって、その目的は、同時に複数のパケットを高速に処理することが可能なパケット転送装置を提供することである。
【課題を解決するための手段】
【０００５】
上述の課題を解決するために、この発明のある局面に従うと、パケット転送装置は、パケットを順次受信するパケット受信手段と、順次受信したパケットから、キーとなる情報を順次取得するキー取得手段と、各々が、異なる値を有する複数のキーにそれぞれ対応づけられた複数の処理情報を含むルックアップテーブルを記憶する記憶手段と、ルックアップテーブルから、複数のキーにそれぞれ対応する複数の処理情報を並行して検索するための検索手段と、検索手段により検索された複数の処理情報の各々に基づいて、対応するパケットを処理するためのパケット処理手段とを備える。
【０００６】
好ましくは、パケット処理手段は、受信した複数のパケットのうちの一部のパケットであって、複数の同種パケットについては、ｎ（自然数）番目に受信した同種パケットを処理した後、ｎ＋１番目に受信した同種パケットを処理する。
【０００７】
好ましくは、検索手段は、複数の処理手段を含み、複数の処理手段の各々は、互いに異なるキーを使用して、ルックアップテーブルから、互いに異なるキーに対応する処理情報を検索する。
【０００８】
好ましくは、ルックアップテーブルは、第１ルックアップテーブルと、第２ルックアップテーブルとを含み、第２ルックアップテーブルは、第１ルックアップテーブルよりも多くの処理情報を含むテーブルであり、多くの処理情報の各々には、互いに異なるキーが対応付けられており、複数の処理手段の各々は、互いに異なるキーを使用して、第１ルックアップテーブルから、互いに異なるキーに対応する処理情報を検索した後、互いに異なるキーを使用して、第２ルックアップテーブルから、互いに異なるキーに対応する処理情報を検索する。
【０００９】
好ましくは、ルックアップテーブルは、第１ルックアップテーブルと、第２ルックアップテーブルとを含み、第２ルックアップテーブルは、第１ルックアップテーブルよりも多くの処理情報を含むテーブルであり、多くの処理情報の各々には、互いに異なるキーが対応付けられており、複数の処理手段のうちの一部の１以上の第１処理手段は、第１ルックアップテーブルに対して検索処理をし、複数の処理手段のうち、１以上の第１処理手段以外の１以上の第２処理手段は、第２ルックアップテーブルに対して検索処理をし、第１処理手段は、キーを使用して、第１ルックアップテーブルから、キーに対応する処理情報を検索し、検索結果を第２処理手段に送り、第２処理手段は、取得した検索結果が所定の結果の場合、キーを使用して、第２ルックアップテーブルから、キーに対応する処理情報を検索する。
【００１０】
好ましくは、記憶手段は、第１の記憶手段と、第２の記憶手段とを含み、第１の記憶手段は、第２の記憶手段よりも高速アクセス可能なものであり、第１ルックアップテーブルに含まれる複数の処理情報の各々は、高速に処理することが必要なパケットに対応する情報であり、第２ルックアップテーブルに含まれる複数の処理情報の各々は、高速に処理することが不必要なパケットに対応する情報であり、第１の記憶手段には、第１ルックアップテーブルが記憶され、第２の記憶手段には、第２ルックアップテーブルが記憶される。
【００１１】
好ましくは、キーは、発信元ＩＰアドレス、発信先ＩＰアドレス、発信元ポート番号および発信先ポート番号の少なくとも１つからなる。
【発明の効果】
【００１２】
本発明に係るパケット転送装置は、各々が異なる複数のキーにそれぞれ対応づけられた複数の処理情報を含むルックアップテーブルから、複数のキーにそれぞれ対応する複数の処理情報を並行して検索し、検索された複数の処理情報の各々に基づいて、対応するパケットを処理する。
【００１３】
したがって、同時に複数のパケットを高速に処理することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照しつつ、本発明の実施の形態について説明する。以下の説明では、同一の部品には同一の符号を付してある。それらの名称および機能も同じである。したがって、それらについての詳細な説明は繰り返さない。
【００１５】
＜第１の実施の形態＞
図１は、典型的なネットワークの概念図を示す。
【００１６】
図１を参照して、本発明におけるネットワーク装置は、アクセスネットワークにおいて使用されるものとする。ここで、アクセスネットワークとは、たとえば、ネットワークプロバイダーが提供しているネットワークである。なお、本発明におけるネットワーク装置は、アクセスネットワークで使用されることに限定されない。
【００１７】
ＬＡＮ（Local Area Network）には、１００から１０００程度のノードが接続されているようなネットワークを想定しており、それらのノードをソースアドレス（以下、発信元ＩＰアドレスともいう）もしくはディスティネーションアドレス（以下、発信先ＩＰアドレスともいう）とするようなトラフィックフローの分類処理を、本発明では行なう。
【００１８】
図２は、本実施の形態におけるパケット転送装置１０００の構成を示すブロック図である。パケット転送装置１０００は、たとえば、ルータ等のネットワーク装置である。
【００１９】
図２を参照して、パケット転送装置１０００は、データ受信部１１０と、ヘッダ解析部１２０と、パケットバッファ１５０と、ルックアップエンジンコントローラ部２００と、ＦＩＦＯ（First-In First-Out）メモリ２１０Ａ，２１０Ｂと、ルックアップエンジン部２２０とを備える。
【００２０】
パケットバッファ１５０は、データを一時的に記憶する機能を有する。
データ受信部１１０は、外部のネットワークから、パケットを受信する。データ受信部１１０は、受信したパケットを、ヘッダ解析部１２０へ送信する。
【００２１】
ヘッダ解析部１２０は、データ受信部１１０から受信したパケットのヘッダ情報を抽出し、当該抽出したヘッダ情報をルックアップエンジンコントローラ部２００へ送信する。ヘッダ情報には、発信元ＩＰアドレス、発信先ＩＰアドレス、プロトコル特定番号、発信元ポート番号、発信先ポート番号等が含まれる。発信元ＩＰアドレスおよび発信先ＩＰアドレスの各々は、たとえば、３２ビットで表現されるものとする。発信元ＩＰアドレスおよび発信先ＩＰアドレスの各々は、たとえば、「Ｋ．Ｌ．Ｍ．Ｎ」というように表現される。Ｋ，Ｌ，Ｍ，Ｎの各々は、８ビットで表現される０〜２５５の範囲の整数である。Ｋは、発信元ＩＰアドレスまたは発信先ＩＰアドレスの各々の、最上位８ビットで表現される。Ｎは、発信元ＩＰアドレスまたは発信先ＩＰアドレスの各々の、最下位８ビットで表現される。
【００２２】
ここで、プロトコル特定番号とは、ネットワークのプロトコルを特定するための番号である。たとえば、プロトコル特定番号が、“６”の場合、当該ネットワークは、ＴＣＰ／ＩＰプロトコルであるとする。
【００２３】
また、ヘッダ解析部１２０は、受信したパケットをパケットバッファ１５０に記憶させる。
【００２４】
ルックアップエンジンコントローラ部２００は、マイクロプロセッサ（Microprocessor）、プログラミングすることができるＬＳＩ（Large Scale Integration）であるＦＰＧＡ（Field Programmable Gate Array）、特定の用途のために設計、製造される集積回路であるＡＳＩＣ（Application Specific Integrated Circuit）、その他の演算機能を有する回路のいずれであってもよい。
【００２５】
ルックアップエンジンコントローラ部２００は、受信したヘッダ情報を含む検索要求データを生成し、当該検索要求データを、ＦＩＦＯメモリ２１０Ａに記憶させる。
【００２６】
ＦＩＦＯメモリ２１０Ａは、所定のデータ量を記憶する領域を有する。ＦＩＦＯメモリ２１０Ａは、記憶されたデータのうち、一番古いデータから順に、ルックアップエンジン部２２０へ送信する。
【００２７】
ルックアップエンジン部２２０は、複数のプロセッシングエレメントを含む。
図３は、ルックアップエンジン部２２０の構成を示すブロック図である。
【００２８】
図３を参照して、ルックアップエンジン部２２０は、プロセッシングエレメント２２２Ａ，２２２Ｂ，２２２Ｃを含む。なお、ルックアップエンジン部２２０に含まれるプロセッシングエレメントの数は、３つに限定されることなく、２つであってもよいし、４つ以上であってもよい。
【００２９】
プロセッシングエレメント２２２Ａ，２２２Ｂ，２２２Ｃの各々は、ルックアップエンジンコントローラ部２００と同様なものである。プロセッシングエレメント２２２Ａ，２２２Ｂ，２２２Ｃの各々は、異なる処理を同時に並列して行なうとことができる。
【００３０】
再び、図２を参照して、パケット転送装置１０００は、さらに、記憶部２５０Ａ，２５０Ｂと、テーブル管理部３２０とを備える。
【００３１】
記憶部２５０Ａは、高価であるが、アクセス速度の高速なメモリ、たとえば、ＳＲＡＭ（Static Random Access Memory）、ＳＤＲＡＭ（Synchronous DRAM）、ダブルデータレートモードという高速なデータ転送機能を持ったＳＤＲＡＭであるＤＤＲ−ＳＤＲＡＭ（Double Data Rate SDRAM）のいずれであってもよい。
【００３２】
記憶部２５０Ａには、後述する第１ルックアップテーブル２５２Ａが記憶されている。
記憶部２５０Ｂは、記憶部２５０Ａによりもアクセス速度は遅いが、安価であるメモリ、たとえば、ＤＲＡＭ（Dynamic Random Access Memory）である。
【００３３】
記憶部２５０Ｂには、後述する第２ルックアップテーブル２５２Ｂが記憶されている。なお、記憶部２５０Ｂの容量は、記憶部２５０Ａの容量よりもはるかに大きいものとする。記憶部２５０Ａの容量は、たとえば、１２８キロバイトであるとする。記憶部２５０Ｂの容量は、たとえば、２５６メガバイトであるとする。
【００３４】
なお、記憶部２５０Ｂは、記憶部２５０Ａと同様なものであってもよい。
テーブル管理部３２０は、ルックアップエンジンコントローラ部２００と同様な構成のものである。テーブル管理部３２０は、図示しないキーボード等の装置を使用したネットワーク管理者の編集指示に基づいて、第１ルックアップテーブルおよび第２ルックアップテーブルの編集処理を行なう。
【００３５】
プロセッシングエレメント２２２Ａ，２２２Ｂ，２２２Ｃのうち、少なくとも１つのプロセッシングエレメントは、ＦＩＦＯメモリ２１０Ａから、検索要求データを受信する。そして、検索要求データを受信したプロセッシングエレメントは、検索要求データに含まれるヘッダ情報をキーとして、記憶部２５０Ａに記憶されている第１ルックアップテーブル２５２Ａまたは記憶部２５０Ｂに記憶されている第２ルックアップテーブル２５２Ｂにデータアクセスし、後述の検索処理を行なう。
【００３６】
検索処理を行なったプロセッシングエレメントは、検索処理によって得られたルール番号のデータを、ＦＩＦＯメモリ２１０Ｂへ記憶させる。ここで、ルールとは、パケットをどのように処理するかを規定したものである。ルール番号とは、番号毎に、異なるルールと対応づけられた番号である。
【００３７】
ＦＩＦＯメモリ２１０Ｂは、同様な機能を有し、記憶されたデータのうち、一番の古いデータから順に、ルックアップエンジンコントローラ部２００へ送信する。
【００３８】
パケット転送装置１０００は、さらに、記憶部２６０と、キュー処理部３００と、データ送信部３１０とを備える。
【００３９】
記憶部２６０は、記憶部２５０Ａまたは記憶部２５０Ｂのいずれの構成であってもよい。記憶部２６０は、ルール変換テーブルを記憶する。ルール変換テーブルとは、複数種類のルール番号にそれぞれ対応づけられた複数のルールが記憶されている。
【００４０】
ルックアップエンジンコントローラ部２００は、記憶部２６０にデータアクセスする。ルックアップエンジンコントローラ部２００は、ＦＩＦＯメモリ２１０Ｂからルール番号のデータを受信すると、記憶部２６０にアクセスして、当該受信したルール番号に対応するルールを読み出す。そして、ルックアップエンジンコントローラ部２００は、当該読み出したルールに基づいた指示のデータをキューとして、キュー処理部３００へ送信する。ルールには、たとえば、パケットの廃棄の指示、転送すべきキューの指示等が規定されている。
【００４１】
図４は、キュー処理部３００の構成を示すブロック図である。
図４を参照して、キュー処理部３００は、キュー管理部３１０と、記憶部３５０とを含む。キュー管理部３１０は、ルックアップエンジンコントローラ部２００と、同様な構成を有する。記憶部３５０は、記憶領域３５０．１，３５０．２、３５０．３，・・・，３５０．ｎを有する。記憶領域３５０．１，３５０．２、３５０．３，・・・，３５０．ｎの各々は、ルックアップエンジンコントローラ部２００から送信されたキューを記憶する。なお、キューは、記憶領域３５０．１，３５０．２、３５０．３，・・・，３５０．ｎの順で、対応する記憶領域に記憶される。なお、記憶部３５０は、１つのキューのみ記憶可能な領域を有するものであってもよい。
【００４２】
キュー管理部３１０は、記憶領域３５０．１に記憶されたキューを読出し、当該読み出したキューに基づいた処理を行なう。キュー管理部３１０は、キューに格納されるパケット情報が、たとえば、「パケットの廃棄」を指示するものであれば、パケットの廃棄を行なう。具体的には、キュー管理部３１０は、パケットバッファ１５０に記憶されている当該キューに格納されるパケット情報に対応するパケットの削除を行なう。
【００４３】
キュー管理部３１０は、キューが、たとえば、「パケットの転送」を指示するものであれば、当該キューに対応するパケットの転送を行なう。具体的には、キュー管理部３１０は、パケットバッファ１５０から、当該キューに対応するパケットを読出し、当該読出したパケットをデータ送信部３１０へ送信する。
【００４４】
データ送信部３１０は、キュー管理部３１０から送信されたパケットを受信すると、外部のネットワークへ、当該受信したパケットを送信する。
【００４５】
キュー管理部３１０は、記憶領域３５０．１に記憶されたキューに基づいた処理を行なうと、記憶領域３５０．２、３５０．３，・・・，３５０．ｎに記憶されているキューを、記憶領域３５０．１，３５０．２、３５０．３，・・・，３５０．（ｎ−１）に上書き記憶させる。そして、キュー管理部３１０は、記憶領域３５０．ｎの領域のデータを削除する。キューが記憶されていない記憶領域が、記憶領域３５０．ｎのみの場合は、記憶領域３５０．ｎに新たなキューが記憶される。
【００４６】
次に、本実施の形態における検索処理について説明する。なお、以下に説明する検索処理は、たとえば、プロセッシングエレメント２２２Ａが、ＦＩＦＯメモリ２１０Ａから、検索要求データを受信したことに基づいて行なわれる処理である。
【００４７】
検索要求データには、ヘッダ情報が含まれる。ヘッダ情報には、発信元ＩＰアドレス、発信先ＩＰアドレス、プロトコル情報、発信元ポート番号、発信先ポート番号が含まれるとする。
【００４８】
本実施の形態では、一例として、発信元ＩＰアドレス、発信先ＩＰアドレス、プロトコル特定番号、発信元ポート番号および発信先ポート番号が、それぞれ、１．１．０．１、２．１．１．１、１、１０１、１０２であるとする。
【００４９】
発信元ＩＰアドレスは、１．１．０．１で表現されるため、下位１０ビットを２進数で表現すると、“０００００００００１”で表現される。すなわち、発信元ＩＰアドレスが、１．１．０．１で表現される場合、下位１０ビットで表現される十進数は“１”である。以下においては、検索処理に使用するヘッダ情報を、検索対象ヘッダ情報とも称する。
【００５０】
図５は、第１の実施の形態における検索処理のフローチャートである。
図５を参照して、ステップＳ１００では、第１ルックアップテーブル２５２Ａ内のデータを検索するための第１ルックアップテーブル検索処理が行なわれる。ここで、第１ルックアップテーブル２５２Ａについて説明する。
【００５１】
第１ルックアップテーブル２５２Ａは、ハッシュテーブルと、第１シーケンシャルサーチテーブルとから構成される。ハッシュテーブルとは、偏りが極めてひどい入力が与えられた場合でも、高速なデータ参照を可能とするデータ構造を有するテーブルである。
【００５２】
第１シーケンシャルサーチテーブルは、高速パケット転送の必要のあるエントリを有するテーブルである。
【００５３】
図６は、第１ルックアップテーブル２５２Ａを示す図である。
図６（Ａ）は、ハッシュテーブルＴ１００を示す図である。
【００５４】
図６（Ａ）を参照して、ハッシュテーブルＴ１００は、一例として、１０２４のエントリからなるテーブルである。ハッシュテーブルＴ１００に示される「Ｖａｌｉｄ」の列の数字は、「０」ならば対応するエントリが無効、「１」ならば対応するエントリが有効であることを示す。
【００５５】
図６（Ｂ）は、第１シーケンシャルサーチテーブルＴ１２０を示す図である。
第１シーケンシャルサーチテーブルＴ１２０は、判定対象のパケットが、複数の条件を満たすか否かを判定するためのテーブルである。本実施の形態では、第１シーケンシャルサーチテーブルＴ１２０は、一例として、条件１〜条件５の５つの条件を判定するためのテーブルであるとする。第１シーケンシャルサーチテーブルＴ１２０に示される「＊」は、どんな数字でも検索条件を満たすことを示す。
【００５６】
たとえば、エントリ番号２に対応する、条件１では、発信元ＩＰアドレスが、１．１．０．＊（０〜２５５のうちの任意の数）であるときに、条件を満たすことになる。たとえば、エントリ番号２に対応する、条件２では、発信先ＩＰアドレスが、２．１．１．１であるときに、条件を満たすことになる。たとえば、エントリ番号２に対応する、条件４では、発信元ポート番号が、１以上、１０以下であるときに、条件を満たすことになる。条件３，５は、条件１，２，４と同様である。第１シーケンシャルサーチテーブルは、使用される頻度の高いルールを特定するためのルール番号が多く登録されたテーブルである。当該ルールは、たとえば、パケットを高速に転送するときに使用されるルールである。
【００５７】
第１シーケンシャルサーチテーブルＴ１２０の「連続検索」の列において、「○」の場合、次のエントリ番号の条件について、判定対象のパケットが条件を満たすか否かを判定する処理を許可する。一方、第１シーケンシャルサーチテーブルＴ１２０の「連続検索」の列において、「×」の場合、次のエントリ番号の条件について、判定対象のパケットが条件を満たすか否かを判定する処理を許可しない。なお、本実施の形態では、連続するエントリ番号に対する連続検索回数は、最大で４回まで許可するものとする。なお、連続検索回数は、４回に限定されることはない。
【００５８】
再び、図５を参照して、ステップＳ１００では、第１ルックアップテーブル検索処理が行なわれる。
【００５９】
図７は、第１ルックアップテーブル検索処理のフローチャートである。
図７を参照して、ステップＳ１１１では、ハッシュテーブルＴ１００内の対象データが有効であるか否かが判定される。具体的には、プロセッシングエレメント２２２Ａが、前述のヘッダ情報に含まれる発信元ＩＰアドレス（１．１．０．１）の下位１０ビットで示される数字（１）をキーとして、ハッシュテーブルＴ１００の検索処理を行なう。
【００６０】
プロセッシングエレメント２２２Ａは、ハッシュテーブルＴ１００において、キーとなる数字（１）に対応した行の、データが有効（１）であるか否かを判定する。ステップＳ１１１において、ＹＥＳならば、ステップＳ１１２に進む。一方、ステップＳ１１１において、ＮＯならば、ステップＳ１１１Ａに進む。
【００６１】
ステップＳ１１１Ａでは、プロセッシングエレメント２２２Ａが、第１検索成功フラグをオフに設定する。ここで、第１検索成功フラグとは、第１ルックアップテーブル検索処理において、検索処理が成功したか否かを示すフラグである。第１検索成功フラグは、記憶部２５０Ａに設けられている。第１検索成功フラグは、オンに設定されている場合、検索処理が成功したことを示し、オフに設定されている場合は、検索処理が失敗したことを示す。その後、この第１ルックアップテーブル検索処理は終了し、図５の検索処理に戻り、ステップＳ１１０の次のステップＳ１２０に進む。
【００６２】
ステップＳ１１２では、プロセッシングエレメント２２２Ａが、ハッシュテーブルＴ１００において、キーとなる数字（１）に対応した行のエントリ番号ｎを取得する。本実施の形態で取得されるｎは、２であるとする。その後、ステップＳ１１３に進む。
【００６３】
ステップＳ１１３では、第１シーケンシャルサーチテーブルＴ１２０内のエントリ番号ｎに対応する条件を全て満たすか否かが判定される。具体的には、プロセッシングエレメント２２２Ａにより、検索対象ヘッダ情報（発信元ＩＰアドレス、発信先ＩＰアドレス、プロトコル特定番号、発信元ポート番号、発信先ポート番号）が、エントリ番号ｎに対応する行の条件１〜条件５を全て満たすか否かが判定される。ステップＳ１１３において、ＹＥＳならば、後述するステップＳ１１３Ａに進む。一方、ステップＳ１１３において、ＮＯならば，ステップＳ１１４に進む。
【００６４】
本実施の形態では、発信元ＩＰアドレス、発信先ＩＰアドレス、プロトコル特定番号、発信元ポート番号および発信先ポート番号は、それぞれ、１．１．０．１、２．１．１．１、１、１０１、１０２である。したがって、この場合、検索対象ヘッダ情報は、条件４と、条件５を満たさない。そのため、ステップＳ１１４に進む。
【００６５】
ステップＳ１１４では、プロセッシングエレメント２２２Ａが、次のエントリ番号の条件で、判定することが許可されているか否かを判定する。具体的には、第１シーケンシャルサーチテーブルＴ１２０のエントリ番号ｎに対応する「連続検索」の欄が、「○」であるか否かが判定される。
【００６６】
ステップＳ１１４において、ＹＥＳならば、ステップＳ１１５に進む。一方、ステップＳ１１４において、ＮＯならば、ステップＳ１１４Ａに進む。
【００６７】
本実施の形態では、第１シーケンシャルサーチテーブルＴ１２０の取得したエントリ番号２に対応する「連続検索」の欄は、「○」であるので、ステップＳ１１５に進む。
【００６８】
ステップＳ１１４Ａでは、ステップＳ１１１Ａと同様な処理が行なわれるので詳細な説明は繰り返さない。その後、この第１ルックアップテーブル検索処理は終了し、図５の検索処理に戻り、ステップＳ１１０の次のステップＳ１２０に進む。
【００６９】
ステップＳ１１５では、プロセッシングエレメント２２２Ａが、エントリ番号ｎを“１”インクリメントする。その後、再度、ステップＳ１１３の処理が行なわれる。
【００７０】
本実施の形態では、ステップＳ１１５において、ｎが３に設定される。その後、ステップＳ１１３では、検索対象ヘッダ情報が第１シーケンシャルサーチテーブルＴ１２０内のｎ（３）に対応する条件を全て満たすか否かが判定される。この場合、ステップＳ１１３の条件を満たすので、ステップＳ１１３Ａに進む。
【００７１】
ステップＳ１１３Ａでは、ルール番号の取得が行なわれる。具体的には、ステップＳ１１３の条件を満たしたときの、エントリ番号ｎに対応する第１シーケンシャルサーチテーブルＴ１２０内のルール番号を、プロセッシングエレメント２２２Ａが取得する。本実施の形態では、ｎは３なので、“１００１”のルール番号が取得される。その後、ステップＳ１１３Ｂに進む。
【００７２】
ステップＳ１１３Ｂでは、プロセッシングエレメント２２２Ａが、第１検索成功フラグをオンに設定する。その後、この第１ルックアップテーブル検索処理は終了し、図５の検索処理に戻り、ステップＳ１１０の次のステップＳ１２０に進む。
【００７３】
ステップＳ１２０では、プロセッシングエレメント２２２Ａが、第１検索成功フラグがオンであるか否かを判定する。すなわち、第１ルックアップテーブル検索処理において、検索処理が成功したか否かが判定される。ステップＳ１２０において、ＹＥＳならば、検索処理は成功として終了する。一方、ステップＳ１２０において、ＮＯならば，検索処理は失敗としてステップＳ１３０に進む。
【００７４】
ステップＳ１３０では、第２ルックアップテーブル検索処理が行なわれる。ここで、第２ルックアップテーブルについて説明する。
【００７５】
第２ルックアップテーブルは、ハッシュテーブルと、複数のツリー検索用テーブルと、第２シーケンシャルサーチテーブルとから構成される。
【００７６】
複数のツリー検索用テーブルの各々は、ツリー上に関連付けられたテーブルである。本実施の形態におけるツリーでは、一例として、４つの階層からなるものとする。第１階層では、２５６個の第１ツリー検索用テーブルが設けられる。第２階層では、第１ツリー検索用テーブルの属性が「Ｎ」であるエントリに対して、２５５個の第２ツリー検索用テーブルが関連付けられる。第３階層では、第２ツリー検索用テーブルの属性が「Ｎ」であるエントリに対して、２５５個の第３ツリー検索用テーブルが関連付けられる。第４階層では、第３ツリー検索用テーブルの属性が「Ｎ」であるエントリに対して、２５５個の第４ツリー検索用テーブルが関連付けられる。
【００７７】
なお、第２シーケンシャルサーチテーブルは、第１シーケンシャルサーチテーブルＴ１２０よりもはるかに多くのエントリを有するとする。たとえば、第２シーケンシャルサーチテーブルは、第１シーケンシャルサーチテーブルＴ１２０の１０００倍の数のエントリを有するテーブルであるとする。したがって、第２ルックアップテーブル２５２Ｂのデータ量は、第１ルックアップテーブル２５２Ａのデータ量よりもはるかに大きい。
【００７８】
図８は、第２ルックアップテーブル２５２Ｂを示す図である。
図８（Ａ）は、ハッシュテーブルＴ２００を示す図である。ハッシュテーブルＴ２００は、ハッシュテーブルＴ１００と比較して、エントリ番号の代わりに「ＲＰＴ」が使用されている点が異なる。それ以外は、ハッシュテーブルＴ１００と同様なので詳細な説明は繰り返さない。ハッシュテーブルＴ２００において、「ＲＰＴ」とは、記憶部２５０Ｂに記憶されている複数のツリー検索用テーブルのルートノードとなる第１階層の第１ツリー検索用テーブルの先頭アドレスを示すルートポインタである。
【００７９】
図８（Ｂ）は、第１ツリー検索用テーブルＴ２１０Ａを示す図である。第１ツリー検索用テーブルＴ２１０Ａは、ハッシュテーブルＴ２００の１つエントリに対応するルートポインタにより特定された１つの先頭アドレスに対応するものである。第１ツリー検索用テーブルＴ２１０Ａは、２５６個のエントリを有する。第１ツリー検索用テーブルＴ２１０Ａにおいて、「Ｔ」は、第１ツリー検索用テーブルＴ２１０Ａの各エントリの属性を示す。「Ｔ」の列に示される「Ｎ」は、対応するエントリが、ノードであることを示す。「ＰＴ」は、第２階層の第２ツリー検索用テーブルの先頭アドレスを示すためのポインタである。なお、「ＰＴ」が、「Ｎｕｌｌ」を示すエントリにアクセスされると、検索処理は失敗となる。
【００８０】
図８（Ｃ）は、第２ツリー検索用テーブルＴ２１０Ｂを示す図である。第２ツリー検索用テーブルＴ２１０Ｂは、第１ツリー検索用テーブルＴ２１０Ａの１つエントリに対応するポインタにより特定された１つの先頭アドレスに対応するものである。第２ツリー検索用テーブルＴ２１０Ｂは、第１ツリー検索用テーブルＴ２１０Ａと比較して、「ＰＴ」が、第３階層の第３ツリー検索用テーブルの先頭アドレスを示すためのポインタである点が異なる。それ以外は、第１ツリー検索用テーブルＴ２１０Ａと同様なので詳細な説明は繰り返さない。
【００８１】
図８（Ｄ）は、第３ツリー検索用テーブルＴ２１０Ｃを示す図である。第３ツリー検索用テーブルＴ２１０Ｃは、第２ツリー検索用テーブルＴ２１０Ｂの１つエントリに対応するポインタにより特定された１つの先頭アドレスに対応するものである。第３ツリー検索用テーブルＴ２１０Ｃは、第１ツリー検索用テーブルＴ２１０Ａと比較して、「ＰＴ」が、第４階層の第４ツリー検索用テーブルの先頭アドレスを示すためのポインタである点が異なる。それ以外は、第１ツリー検索用テーブルＴ２１０Ａと同様なので詳細な説明は繰り返さない。
【００８２】
図８（Ｅ）は、第４ツリー検索用テーブルＴ２１０Ｄを示す図である。第４ツリー検索用テーブルＴ２１０Ｄは、第３ツリー検索用テーブルＴ２１０Ｃの１つエントリに対応するポインタにより特定された１つの先頭アドレスに対応するものである。第４ツリー検索用テーブルＴ２１０Ｄは、第１ツリー検索用テーブルＴ２１０Ａと比較して、各エントリの属性が、「Ｎ」の代わりに「Ｌ」である点と、「ＰＴ」の代わりに「エントリ番号」で示される点と、２５５番目のエントリがＮｕｌｌでない点が異なる。「Ｌ」は、対応するエントリがリーフノードであることを示す。「エントリ番号」は、後述する第２シーケンシャルサーチテーブルのエントリ番号を示す。それ以外は、第１ツリー検索用テーブルＴ２１０Ａと同様なので詳細な説明は繰り返さない。
【００８３】
なお、第１ツリー検索用テーブルＴ２１０Ａ、第２ツリー検索用テーブルＴ２１０Ｂおよび第３ツリー検索用テーブルＴ２１０Ｃの各々が有する２５６個のエントリの全ての属性は、「Ｎ」に限定されることない。たとえば、当該２５６個のエントリのうちの数個（たとえば、３個）のエントリの属性が、「Ｌ」であってもよい。エントリの属性が「Ｌ」の場合、当該エントリには、第２シーケンシャルサーチテーブルのエントリ番号が対応づけられる。
【００８４】
図９は、第２シーケンシャルサーチテーブルＴ２２０を示す図である。
図９を参照して、第２シーケンシャルサーチテーブルＴ２２０は、第１シーケンシャルサーチテーブルＴ１２０と比較して、１０００倍の数のエントリを有する点と、連続するエントリ番号に対する連続検索回数は、４回の代わりに８回まで許可される点とが異なる。なお、連続検索回数は、８回に限定されることはなく、第１シーケンシャルサーチテーブルＴ１２０よりも多い回数であればよい。
【００８５】
なお、第２シーケンシャルサーチテーブルＴ２２０は、ルールが対応づけられた非常に多くのエントリを有するので、非常に多くの種類のパケットの処理をサポートすることができる。
【００８６】
また、第２シーケンシャルサーチテーブルは、使用される頻度が比較的低いルールを特定するためのルール番号が登録されたテーブルである。当該ルールは、たとえば、パケットを高速に転送する必要がないときに使用されるルールである。
【００８７】
それ以外は、第１シーケンシャルサーチテーブルＴ１２０と同様なので詳細な説明は繰り返さない。
【００８８】
図１０は、第２ルックアップテーブル検索処理のフローチャートである。
図１０を参照して、ステップＳ１３１では、ハッシュテーブルＴ２００内の対象データが有効であるか否かが判定される。具体的には、プロセッシングエレメント２２２Ａが、前述のヘッダ情報に含まれる発信元ＩＰアドレス（１．１．０．１）の下位１０ビットで示される数字（１）をキーとして、ハッシュテーブルＴ２００の検索処理を行なう。
【００８９】
プロセッシングエレメント２２２Ａは、ハッシュテーブルＴ２００において、キーとなる数字（１）に対応した行の、データが有効（１）であるか否かを判定する。ステップＳ１３１において、ＹＥＳならば、ステップＳ１３１Ｂに進む。一方、ステップＳ１３１において、ＮＯならば、ステップＳ１３１Ａに進む。
【００９０】
ステップＳ１３１Ａでは、プロセッシングエレメント２２２Ａが、第２検索成功フラグをオフに設定する。ここで、第２検索成功フラグとは、第２ルックアップテーブル検索処理において、検索処理が成功したか否かを示すフラグである。第２検索成功フラグは、記憶部２５０Ｂに設けられている。第２検索成功フラグは、オンに設定されている場合、検索処理が成功したことを示し、オフに設定されている場合は、検索処理が失敗したことを示す。その後、この第２ルックアップテーブル検索処理は終了し、図５の検索処理に戻り、ステップＳ１３０の次のステップＳ１４０に進む。
【００９１】
ステップＳ１３１Ｂでは、ツリー検索処理が行なわれる。ツリー検索処理では、プロセッシングエレメント２２２Ａが、ハッシュテーブルＴ２００において、キーとなる数字（１）に対応した行のアドレス番号（５０００）を取得する。
【００９２】
次に、プロセッシングエレメント２２２Ａは、記憶部２５０Ｂにおいて、５０００番地を先頭アドレスとする第１ツリー検索用テーブルＴ２１０Ａを読み出す。プロセッシングエレメント２２２Ａは、第１ツリー検索用テーブルＴ２１０Ａにおいて、発信先ＩＰアドレス（２．１．１．１）の最上位８ビットの示す数字“２”に対応するエントリのポインタが示す第１のアドレスを取得する。
【００９３】
次に、プロセッシングエレメント２２２Ａは、記憶部２５０Ｂにおいて、第１のアドレスを先頭アドレスとする第２ツリー検索用テーブルＴ２１０Ｂを読み出す。プロセッシングエレメント２２２Ａは、第２ツリー検索用テーブルＴ２１０Ｂにおいて、発信先ＩＰアドレス（２．１．１．１）の最上位８ビットの次の８ビットの示す数字“１”に対応するエントリのポインタが示す第２のアドレスを取得する。
【００９４】
次に、プロセッシングエレメント２２２Ａは、記憶部２５０Ｂにおいて、第２のアドレスを先頭アドレスとする第３ツリー検索用テーブルＴ２１０Ｃを読み出す。プロセッシングエレメント２２２Ａは、第３ツリー検索用テーブルＴ２１０Ｃにおいて、発信先ＩＰアドレス（２．１．１．１）の最上位８ビットの次の次の８ビットの示す数字“１”に対応するエントリのポインタが示す第３のアドレスを取得する。その後、ステップＳ１３２に進む。
【００９５】
ステップＳ１３２では、プロセッシングエレメント２２２Ａが、記憶部２５０Ｂにおいて、第３のアドレスを先頭アドレスとする第４ツリー検索用テーブルＴ２１０Ｄを読み出す。プロセッシングエレメント２２２Ａは、第４ツリー検索用テーブルＴ２１０Ｄにおいて、発信先ＩＰアドレス（２．１．１．１）の最下位８ビットの示す数字“１”に対応するエントリのポインタが示すエントリ番号ｎを取得する。その後、ステップＳ１３３に進む。
【００９６】
ステップＳ１３３では、第２シーケンシャルサーチテーブルＴ２２０内のエントリ番号ｎに対応する条件を全て満たすか否かが判定される。それ以外は、ステップＳ１１３と同様なので、詳細な説明は繰り返さない。ステップＳ１３３において、ＹＥＳならば、ステップＳ１３３Ａに進む。一方、ステップＳ１３３において、ＮＯならば，ステップＳ１３４に進む。
【００９７】
ステップＳ１３３Ａでは、ルール番号の取得が行なわれる。具体的には、ステップＳ１３３の条件を満たしたときの、エントリ番号ｎに対応する第２シーケンシャルサーチテーブルＴ２２０内のルール番号を、プロセッシングエレメント２２２Ａが取得する。その後、ステップＳ１３３Ｂに進む。
【００９８】
ステップＳ１３３Ｂでは、プロセッシングエレメント２２２Ａが、第２検索成功フラグをオンに設定する。その後、この第２ルックアップテーブル検索処理は終了し、図５の検索処理に戻り、ステップＳ１３０の次のステップＳ１４０に進む。
【００９９】
ステップＳ１３４では、前述のステップＳ１１４と同様な処理が行なわれるので詳細な説明は繰り返さない。ステップＳ１３４において、ＹＥＳならば、ステップＳ１３５に進む。一方、ステップＳ１３４において、ＮＯならば、ステップＳ１３４Ａに進む。
【０１００】
ステップＳ１３４Ａでは、ステップＳ１３１Ａと同様な処理が行なわれるので詳細な説明は繰り返さない。その後、この第２ルックアップテーブル検索処理は終了し、図５の検索処理に戻り、ステップＳ１３０の次のステップＳ１４０に進む。
【０１０１】
ステップＳ１３５では、プロセッシングエレメント２２２Ａが、エントリ番号ｎを“１”インクリメントする。その後、再度、ステップＳ１３３の処理が行なわれる。
【０１０２】
前述したように、本実施の形態では、検索処理を行なうためのキーとして、発信元ＩＰアドレス、発信先ＩＰアドレス、発信元ポート番号および発信先ポート番号の情報を使用する。すなわち、パケットの通信に関連の深い情報をキーとして検索するので、通信の性質に応じた的確な検索をすることができるという効果を奏する。また、発信元の情報と発信先の情報の組合わせによって要求される処理の速度や頻度が異なる場合においても、本発明によれば、こういった相違を反映した検索をすることができるという効果を奏する。
【０１０３】
再び、図５を参照して、ステップＳ１４０では、プロセッシングエレメント２２２Ａが、第２検索成功フラグがオンであるか否かを判定する。すなわち、第２ルックアップテーブル検索処理において、検索処理が成功したか否かが判定される。ステップＳ１４０において、ＹＥＳならば、検索処理は成功として終了する。一方、ステップＳ１４０において、ＮＯならば，検索処理は失敗として終了する。
【０１０４】
次に、図５の検索処理が成功として終了した場合、プロセッシングエレメント２２２Ａは、前述の検索処理によって得られたルール番号（以下、ルール番号Ａともいう）のデータを、ＦＩＦＯメモリ２１０Ｂへ記憶させる。
【０１０５】
そして、ルール番号ＡのデータをＦＩＦＯメモリ２１０Ｂから受信したルックアップエンジンコントローラ部２００は、記憶部２６０にアクセスして、ルール番号Ａに対応するルール（以下、ルールＡともいう）を読み出す。この場合、検索処理は成功しているので、ルールＡは、たとえば、パケットの転送を指示するものとなる。
【０１０６】
そして、ルックアップエンジンコントローラ部２００は、ルールＡに基づいた指示のデータをキュー（以下、キューＡともいう）として、キュー処理部３００へ送信する。
【０１０７】
そして、キューＡは、前述のキュー処理部３００内の記憶部３５０内の記憶領域に記憶される。そして、前述のキュー管理部３１０の処理により、記憶領域３５０．１にキューＡが記憶されると、キュー管理部３１０は、記憶領域３５０．１に記憶されたキューＡを読出し、キューＡに基づいた処理、すなわち、パケットの転送を行なう。
【０１０８】
具体的には、キュー管理部３１０は、パケットバッファ１５０から、キューＡに対応するパケットを読出し、当該読出したパケットをデータ送信部３１０へ送信する。
【０１０９】
データ送信部３１０は、キュー管理部３１０から送信されたパケットを受信すると、外部のネットワークへ、当該受信したパケットを送信する。
【０１１０】
本実施の形態では、第１ルックアップテーブル検索処理および第２ルックアップテーブル検索処理において、検索範囲を絞り込むために、まず、発信元ＩＰアドレスを利用している。これは、ネットワークの上り方向に向かうパケットの検索の場合を想定している。ネットワークの下り方向に向かうパケットの検索の場合は、本実施の形態の検索処理において、発信元ＩＰアドレスを発信先ＩＰアドレスに置き換えて使用し、発信先ＩＰアドレスを発信元ＩＰアドレスに置き換えて使用すればよい。
【０１１１】
また、本実施の形態では、第１シーケンシャルサーチテーブルＴ１２０において、連続するエントリ番号に対する連続検索回数は、最大で４回まで許可される。したがって、第１ルックアップテーブル検索処理では、１回のハッシュテーブルＴ１００へのアクセスと、４回の第１シーケンシャルサーチテーブルＴ１２０へのアクセスとの合計５回のアクセスで、検索結果を得ることができる。
【０１１２】
また、本実施の形態では、第２シーケンシャルサーチテーブルＴ２２０において、連続するエントリ番号に対する連続検索回数は、最大で８回まで許可される。したがって、第２ルックアップテーブル検索処理では、１回のハッシュテーブルＴ１００へのアクセスと、４回のツリー検索用テーブルへのアクセスと、８回の第２シーケンシャルサーチテーブルＴ２２０へのアクセスとの合計１３回のアクセスで、検索結果を得ることができる。
【０１１３】
なお、前述した検索処理は、プロセッシングエレメント２２２Ａに限定されることなく、プロセッシングエレメント２２２Ｂ，２２２Ｃのいずれが行なってもよい。本実施の形態における検索処理は、プロセッシングエレメント２２２Ａ，２２２Ｂ，２２２Ｃの各々が、並列的に行なう。したがって、たとえば、プロセッシングエレメント２２２Ａが、検索処理を行なっている間に、ルックアップエンジン部２２０が、ＦＩＦＯメモリ２１０Ａから、検索要求データを受信すると、検索処理を行なっていない、他のプロセッシングエレメント、たとえば、プロセッシングエレメント２２２Ｂが、検索要求データを受信し、前述した検索処理を行なう。
【０１１４】
そのため、検索処理に時間がかかるパケットの検索処理を、たとえば、プロセッシングエレメント２２２Ａが行なっている間に、高速な転送が要求されるパケットを受信した場合、他のプロセッシングエレメントが、当該パケットについて検索処理をすることで、検索処理に時間がかかるパケットに影響されることなく、複数のパケットを同時に高速に処理できるという効果を奏する。
【０１１５】
なお、同種の複数のパケットのうち、ｎ番目に受信したパケットと、ｎ＋１番目に受信したパケットとにおいては、以下に説明する処理が行なわれる。
【０１１６】
同種のパケットは、必ず同一のエントリにマッチする。従って、ｎ番目に受信したパケットの検索処理は、必ずｎ＋１番目に受信したパケットの検索処理よりも早く終了するため、ＦＩＦＯメモリ２１０Ｂへは、必ず、ｎ番目に受信したパケットの検索処理により得られたルール番号を送信した後、ｎ＋１番目に受信したパケットの検索処理により得られたルール番号を送信する。すなわち、同種のパケットの順番は、変化させないようにする。
【０１１７】
したがって、ルックアップエンジンコントローラ部２００は、ｎ番目に受信したパケット処理した後、ｎ＋１番目に受信したパケットを処理することになる。
【０１１８】
したがって、同種のパケットの順序が入れ替わることがないので、データが複数の同種パケットに分割されても、当該データを正確に伝送することができるという効果を奏する。また、同種のパケットの順序が入れ替わることがないので、受信側の装置により受信パケットの並べ替えを行なう必要がなく、受信処理が簡単になるという効果を奏する。
【０１１９】
また、本実施の形態では、複数のプロセッシングエレメント（処理手段）の各々が、互いに異なるキーを使用して、シーケンシャルサーチテーブルから、キーに対応する情報を検索する処理を並行して行なうので、検索結果を早く取得できるという効果を奏する。その上、前述したように、複数種類のパケットにおいて、同種のパケット同士の順序は入れ替えず、異種のパケット同士の順序を入れ替えてでも早く検索結果が得られることになり、処理の効率化が著しいという効果を奏する。
【０１２０】
以上説明したように、本実施の形態におけるパケット転送装置１０００では、高価であるが、アクセス速度の高速な記憶部２５０Ａに、複数のルール番号がそれぞれ対応づけられた複数のエントリを有する第１シーケンシャルサーチテーブルＴ１２０を記憶させている。また、パケット転送装置１０００では、アクセス速度は遅いが、安価である記憶部２５０Ｂに、第１シーケンシャルサーチテーブルの１０００倍の数のルール番号がそれぞれ対応付けられた複数のエントリを有する第２シーケンシャルサーチテーブルＴ２２０を記憶させている。
【０１２１】
そして、受信したパケットの情報に基づいて、まず、高速に検索が可能で、かつ、使用される頻度の高いルールを特定するためのルール番号が多く登録された第１シーケンシャルサーチテーブルＴ１２０を検索する。そして、検索が失敗したら、検索は低速になるが、多くのルールを有する第２シーケンシャルサーチテーブルＴ２２０を検索する。
【０１２２】
したがって、パケット転送装置１０００のコストを低く抑え、かつ、非常に多くの種類のパケットの処理をサポートしながら、かつ、受信したパケットの処理に対応するルールを高速に検索することができる。すなわち、パケットを高速に処理（たとえば、転送）することができるという効果を奏する。
【０１２３】
＜第２の実施の形態＞
第１の実施の形態では、プロセッシングエレメント２２２Ａ，２２２Ｂ，２２２Ｃの各々は、パケットの検索処理を行なう際、第１ルックアップテーブル２５２Ａおよび第２ルックアップテーブル２５２Ｂの両方を使用していた。
【０１２４】
本実施の形態では、第１ルックアップテーブル２５２Ａおよび第２ルックアップテーブル２５２Ｂの各々に対し、使用するプロセッシングエレメントを予め決めておく。
【０１２５】
たとえば、パケットの検索処理において、第１ルックアップテーブル２５２Ａを使用するプロセッシングエレメントは、プロセッシングエレメント２２２Ａ（以下、第１テーブル専用プロセッシングエレメントともいう）とする。
【０１２６】
また、パケットの検索処理において、第２ルックアップテーブル２５２Ｂを使用するプロセッシングエレメントは、プロセッシングエレメント２２２Ｂ，２２２Ｃ（以下、第２テーブル専用プロセッシングエレメントともいう）とする。
【０１２７】
なお、第１ルックアップテーブル２５２Ａを使用するプロセッシングエレメントは、１つに限定されることなく、２つ以上であってもよい。また、第２ルックアップテーブル２５２Ｂを使用するプロセッシングエレメントは、２つに限定されることなく、１つまたは３つ以上であってもよい。
【０１２８】
本実施の形態における、パケット転送装置は、第１の実施の形態のパケット転送装置１０００であるとする。
【０１２９】
次に、本実施の形態における検索処理について説明する。以下においては、第１ルックアップテーブル２５２Ａを使用する検索処理を、第１検索処理という。また、第２ルックアップテーブル２５２Ｂを使用する検索処理を、第２検索処理という。
【０１３０】
まず、第１検索処理について説明する。なお、以下に説明する第１検索処理は、第１テーブル専用プロセッシングエレメントであるプロセッシングエレメント２２２Ａが、ＦＩＦＯメモリ２１０Ａから、検索要求データＡを受信したことに基づいて行なわれる処理である。
【０１３１】
図１１は、第２の実施の形態における第１検索処理のフローチャートである。
図１１を参照して、ステップＳ２１０では、第１ルックアップテーブル検索処理が行なわれる。第１ルックアップテーブル検索処理は、第１の実施の形態で説明した図７の第１ルックアップテーブル検索処理において、第１ルックアップテーブル検索処理が終了すると、ステップＳ２２０に進む点のみが異なり、それ以外は同様なので詳細な説明は繰り返さない。第１ルックアップテーブル検索処理が終了すると、ステップＳ２２０に進む。
【０１３２】
ステップＳ２２０では、プロセッシングエレメント２２２Ａが、第１検索成功フラグがオンであるか否かを判定する。すなわち、第１ルックアップテーブル検索処理において、検索処理が成功したか否かが判定される。ステップＳ２２０において、ＹＥＳならば、第１検索処理は成功として終了する。その後に行なわれる処理は、第１の実施の形態と同様なので詳細な説明は繰り返さない。一方、ステップＳ２２０において、ＮＯならば，ステップＳ２３０に進む。
【０１３３】
ステップＳ２３０では、第２テーブル専用プロセッシングエレメントに、検索要求データＡを送信する。その後、この第１検索処理は終了する。
【０１３４】
図１２は、第２の実施の形態における第２検索処理のフローチャートである。なお、第２検索処理を行なう第２テーブル専用プロセッシングエレメントは、たとえば、プロセッシングエレメント２２２Ｂであるとする。
【０１３５】
図１２を参照して、ステップＳ３０５では、プロセッシングエレメント２２２Ｂが、第１テーブル専用プロセッシングエレメント（プロセッシングエレメント２２２Ａ）から、検索要求データ（たとえば、検索要求データＡ）を受信したか否かが判定される。ステップＳ３０５において、ＹＥＳならば、ステップＳ３１０に進む。一方、ステップＳ３０５において、ＮＯならば、再度、ステップＳ３０５の処理が行なわれる。
【０１３６】
ステップＳ３１０では、第２ルックアップテーブル検索処理が行なわれる。第２ルックアップテーブル検索処理は、第１の実施の形態で説明した図１０の第２ルックアップテーブル検索処理において、プロセッシングエレメント２２２Ａの代わりにプロセッシングエレメント２２２Ｂが処理を行なう点と、第２ルックアップテーブル検索処理が終了すると、ステップＳ３４０に進む点のみが異なり、それ以外は同様なので詳細な説明は繰り返さない。第２ルックアップテーブル検索処理が終了すると、ステップＳ３４０に進む。
【０１３７】
ステップＳ３４０では、プロセッシングエレメント２２２Ｂが、第２検索成功フラグがオンであるか否かを判定する。すなわち、第２ルックアップテーブル検索処理において、検索処理が成功したか否かが判定される。ステップＳ２４０において、ＹＥＳならば、検索処理は成功として終了する。一方、ステップＳ２４０において、ＮＯならば，検索処理は失敗として終了する。その後に行なわれる処理は、第１の実施の形態と同様なので詳細な説明は繰り返さない。
【０１３８】
以上説明したように、本実施の形態では、第１ルックアップテーブル２５２Ａおよび第２ルックアップテーブル２５２Ｂの各々に対し、使用するプロセッシングエレメントを予め決めておく。すなわち、受信したパケットの処理に対応するルール番号を高速に検索することできる第１ルックアップテーブル２５２Ａ対し、常に、専用のプロセッシングエレメントが対応づけられている。
【０１３９】
したがって、第２ルックアップテーブル検索処理まで行なわないと、対応するルールがないような検索処理に時間がかかるパケットを受信した場合でも、第２ルックアップテーブル検索処理が行なわれている間は、第１テーブル専用プロセッシングエレメントは、パケットを処理可能な状態になる。
【０１４０】
その結果、検索処理に時間がかかるパケットを受信した場合、すなわち、第２ルックアップテーブル検索処理が行なわれている間に、高速な転送が要求されるパケットを受信しても、第１テーブル専用プロセッシングエレメントにより高速にパケットに対応するルール番号を検索処理することができる。
【０１４１】
したがって、本実施の形態では、第１の実施の形態に奏する効果に加え、第１の実施の形態よりも、より少ない数のプロセッシングエレメントで高速転送の必要なパケットをより高速に処理（たとえば、転送）することができるという効果を奏する。
【０１４２】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０１４３】
【図１】典型的なネットワークの概念図である。
【図２】第１の実施の形態におけるパケット転送装置の構成を示すブロック図である。
【図３】ルックアップエンジン部の構成を示すブロック図である。
【図４】キュー処理部の構成を示すブロック図である。
【図５】第１の実施の形態における検索処理のフローチャートである。
【図６】第１ルックアップテーブルを示す図である。
【図７】第１ルックアップテーブル検索処理のフローチャートである。
【図８】第２ルックアップテーブルを示す図である。
【図９】第２シーケンシャルサーチテーブルを示す図である。
【図１０】第２ルックアップテーブル検索処理のフローチャートである。
【図１１】第２の実施の形態における第１検索処理のフローチャートである。
【図１２】第２の実施の形態における第２検索処理のフローチャートである。
【符号の説明】
【０１４４】
１１０  データ受信部、１２０  ヘッダ解析部、１５０  パケットバッファ、２００  ルックアップエンジンコントローラ部、２１０Ａ，２１０Ｂ  ＦＩＦＯメモリ、２２０  ルックアップエンジン部、２２２Ａ，２２２Ｂ，２２２Ｃ  プロセッシングエレメント、２５０Ａ，２５０Ｂ  記憶部、１０００  パケット転送装置。
【図１】
2007013246.tif 000003
【図２】
2007013246.tif 000004
【図３】
2007013246.tif 000005
【図４】
2007013246.tif 000006
【図５】
2007013246.tif 000007
【図６】
2007013246.tif 000008
【図７】
2007013246.tif 000009
【図８】
2007013246.tif 000010
【図９】
2007013246.tif 000011
【図１０】
2007013246.tif 000012
【図１１】
2007013246.tif 000013
【図１２】
2007013246.tif 000014