(57)【要約】【課題】検索処理のための待ち時間を大幅に抑制して処理能力の向上を可能にする。【解決手段】パケット処理装置は、パケットの転送を経路情報対応のエントリに基づいて行うための連想メモリを含む検索エンジン部と；前記パケットの処理を前記検索エンジン部に渡す前の検索前処理を担当する第１のプロセッサと；前記検索エンジン部の検索結果に基づいて前記パケットの中継処理を行うための検索後処理を担当する第２のプロセッサとを備える。この構成において、前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの間の情報の受け渡し行うためのテーブルを更に備え；このテーブルの特定箇所の識別情報を前記検索エンジン部を透過媒体として渡す。【選択図】　図２
2004015561.tif 000002
【特許請求の範囲】
【請求項１】
パケットの転送を経路情報対応のエントリに基づいて行うための連想メモリを含む検索エンジン部と；
前記パケットの処理を前記検索エンジン部に渡す前の検索前処理を担当する第１のプロセッサと；
前記検索エンジン部の検索結果に基づいて前記パケットの中継処理を行うための検索後処理を担当する第２のプロセッサと；
を備えるパケット処理装置。
【請求項２】
前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの間の情報の受け渡し行うためのテーブルを更に備え；
このテーブルの特定箇所の識別情報を前記検索エンジン部を透過媒体として渡す請求項１記載のパケット処理装置。
【請求項３】
前記テーブルがＦＩＦＯメモリで構成される場合、前記ＦＩＦＯメモリのキュー長監視を行い、溜まり具合に応じて、前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの分担個数を動的に変更する手段を更に備える
請求項２記載のパケット処理装置。
【請求項４】
前記検索エンジン部は、ルーティング統計情報とともに、少なくとも前記検索前処理担当の第１のプロセッサ及び前記検索後処理担当の第２のプロセッサからのキューイング統計情報の一元管理を行うために、前記検索前処理担当の第１のプロセッサからの検索要求のインタフェースとは別に、統計要求のインタフェースを備える
請求項１記載のパケット処理装置。
【請求項５】
受信したパケットに含まれる宛先アドレスとこのパケットの処理に関連する情報とをそれぞれ格納する少なくとも１つの場所を示す手段と；
前記場所から格納された前記宛先アドレスに基づく経路情報の検索から得られた前記パケットの出力先を特定する情報と前記格納場所とを対応させる手段と；
前記パケットを前記格納場所から前記パケットの処理に関連する情報に基づき前記パケットに必要な処理を行い、特定された前記出力先にパケットを送出する手段と；
を備えるパケット処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケット処理装置に関し、特にマルチエンジン（Ｍｕｌｔｉ　Ｅｎｇｉｎｅ）またはマルチタスク（Ｍｕｌｔｉ　Ｔａｓｋ）のパケット処理エンジン部と検索エンジン部とで構成されるＩＰパケット処理装置に関する。
【０００２】
【従来の技術】
近年、ＩＰ（Ｉｎｔｅｒｎｅｔ　Ｐｒｏｔｏｃｏｌ）プロトコルをネットワーク層プロトコルとして利用するＩＰネットワークがインターネットや企業内網への適用の形態で急増している。これに伴い、ＩＰネットワークにおいてＩＰパケット（以下、特に限定を要するとき以外は、単にパケットと記載することもある）の中継処理を行うルータなどのＩＰパケット処理装置の高性能化が求められている。
【０００３】
また、ＩＰネットワークの導入拡張に伴いＩＰトラヒックがデータ通信の主流となっているが、ＩＰパケットは可変長のデータであるため、ショートパケットのバースト的なトラヒックに対しての処理能力不足や、ロングパケット読み出し時の他パケットへの影響など、品質（ＱｏＳ：Ｑｕａｌｉｔｙ　ｏｆ　Ｓｅｒｖｉｃｅ）保証が課題となっている。
【０００４】
一般的に、ＩＰパケット処理装置は、パケット中継処理において、パケット処理を行うためのパケット処理エンジン部と、検索処理を行うための検索エンジン部とを有する。このＩＰパケット処理装置において、パケットを中継処理する場合は、入力されたパケットのヘッダ部に含まれる宛先アドレスに基づいて検索処理を実施し、検索結果によって得られた情報で宛先（ＭＡＣアドレス等）を決定して転送する。
【０００５】
様々なサービス機能の追加や製品コストのための収容率の増加等が、製品の差別化として、ネットワーク側装置のＩＰパケット処理装置に更に要求されている。また、パケット中継処理能力の更なる向上要求に対応するために、パケット処理エンジン部では、複数のエンジン（マルチエンジン）を内蔵したネットワークプロセッサ（ＮＰ：Ｎｅｔｗｏｒｋ　Ｐｒｏｃｅｓｓｏｒ）で高速に分散処理を行う構成が主流となりつつあり、検索エンジン部では、多ビットの高速検索を処理可能な大容量のＣＡＭ（Ｃｏｎｔｅｎｔ　Ａｄｄｒｅｓｓａｂｌｅ　Ｍｅｍｏｒｙ）が主流となっている。
【０００６】
しかし、ＩＰパケット処理装置に要求される新規機能の追加は増加傾向を示し、パケット処理のスループットは２．４Ｇｂｐｓまたは１０Ｇｂｐｓと高速になり、高速動作のネットワークプロセッサでも処理能力が追従不可能になっている。
【０００７】
また、検索エンジン部に要求される検索処理は、ルーティング（経路情報）検索、フィルタリング検索、及びクラス検索と増加しており、高速なＣＡＭを用いたとしても検索処理時間が無視できなくなってきている。
【０００８】
【発明が解決しようとする課題】
本発明の課題は、検索処理のための待ち時間を大幅に抑制して処理能力の向上が可能な手法を提供することにある。
【０００９】
本発明の他の課題は、検索前処理担当（割当）のプロセッサと検索後処理担当（割当）のプロセッサとの間の情報の受け渡しを円滑に行うことが可能な手法を提供することにある。
【００１０】
本発明の他の課題は、極端なバーストトラヒックにおいても処理能力不足とならず、品質保証が可能な手法を提供することにある。
【００１１】
本発明の別の課題は、ルーティング統計とキューイング統計とを一元的に管理可能な手法を提供することにある。
【００１２】
【課題を解決するための手段】
上記課題を解決するために、本発明のパケット処理装置は、パケットの転送を経路情報対応のエントリに基づいて行うための連想メモリを含む検索エンジン部と；前記パケットの処理を前記検索エンジン部に渡す前の検索前処理を担当する第１のプロセッサと；前記検索エンジン部の検索結果に基づいて前記パケットの中継処理を行うための検索後処理を担当する第２のプロセッサとを備える。
【００１３】
この構成において、前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの間の情報の受け渡し行うためのテーブルを更に備え；このテーブルの特定箇所の識別情報を前記検索エンジン部を透過媒体として渡す。
【００１４】
また、前記テーブルがＦＩＦＯメモリで構成される場合、前記ＦＩＦＯメモリのキュー長監視を行い、溜まり具合に応じて、前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの分担個数を動的に変更する手段を更に備える。
【００１５】
また、前記検索エンジン部は、ルーティング統計情報とともに、少なくとも前記検索前処理担当の第１のプロセッサ及び前記検索後処理担当の第２のプロセッサからのキューイング統計情報の一元管理を行うために、前記検索前処理担当の第１のプロセッサからの検索要求のインタフェースとは別に、統計要求のインタフェースを備える。
【００１６】
本発明の他のパケット処理装置は、受信したパケットに含まれる宛先アドレスとこのパケットの処理に関連する情報とをそれぞれ格納する少なくとも１つの場所を示す手段と；前記場所から格納された前記宛先アドレスに基づく経路情報の検索から得られた前記パケットの出力先を特定する情報と前記格納場所とを対応させる手段と；前記パケットを前記格納場所から前記パケットの処理に関連する情報に基づき前記パケットに必要な処理を行い、特定された前記出力先にパケットを送出する手段とを備える。
【００１７】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１８】
［ＩＰパケット処理装置の基本構成］
本発明のＩＰパケット処理装置の基本構成を示す図１を参照すると、このＩＰパケット処理装置１は、パケット処理エンジン部１０と、検索エンジン部２０と、パケットバッファ部３０とを備えている。
【００１９】
このＩＰパケット処理装置１は、ＩＰプロトコルに則って通信を提供するＩＰネットワークにおいて、ＩＰパケットの転送を経路情報対応のエントリに基づいて行うルータに適用できる。
【００２０】
ＩＰパケット処理装置１は、あるＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）から別のＬＡＮあるいは専用線などと云ったＩＰネットワーク内の異なるサブネット間のパケットを中継し、直接パケットの授受が行えない通信ノード間での通信を可能にする。
【００２１】
ＩＰパケット処理装置１は、複数のインタフェースを持ち、あるインタフェースから受信したＩＰパケットをヘッダ部内の宛先アドレスに応じ、どのインタフェースからどこに送出すれば、宛先に届けることができるか否かを判定してパケット中継を行う。
【００２２】
ＩＰパケット処理装置１は、通常、このパケット中継を行う際に必要となるパケットの宛先アドレスに応じてどこへ中継したら良いかの情報を格納したルーティングテーブル（図示省略）を有する。
【００２３】
後に詳述するように、ＩＰパケット処理装置１におけるパケット処理エンジン部１０は、パケット中継処理における分散処理を行うためのマルチエンジン（Ｍｕｌｔｉ　Ｅｎｇｉｎｅ）またはマルチタスク（Ｍｕｌｔｉ　Ｔａｓｋ）のパケット処理エンジン（ＰＥ）として複数のプロセッサを有する。
【００２４】
また、検索エンジン部２０は、パケット中継処理における高速検索処理を可能にするために、連想メモリのＣＡＭなどを含む検索メモリを有する。
【００２５】
パケットバッファ部３０は、入力パケットのヘッダ部に続くデータ部のパケットデータを一時的に格納し、格納しているパケットデータを読み出し制御に応答して送出するために、バッファメモリ（キュー）を有する。
【００２６】
上記ＩＰパケット処理装置１のパケット処理エンジン部１０においては、パケット処理を検索エンジン部２０に渡す前の検索前処理と、検索エンジン部２０の結果に基づいて処理を行う検索後処理とに分け、かつその前後処理を別々のパケット処理エンジン、つまりプロセッサで処理する構成を採る。これにより、検索処理のための待ち時間を大幅に抑制することが可能となり、結果的に処理能力の向上が期待できる。
【００２７】
また、パケット処理エンジン部１０に、検索前処理担当（割当）のプロセッサと検索後処理担当（割当）のプロセッサとの間の情報の受け渡しに共通のテーブルとして情報受け渡しテーブルを設け、このテーブルの特定箇所の識別情報（インデックス値またはテーブルアドレス等）を検索エンジン部２０を透過媒体として渡す構成を採る。これにより、異なるプロセッサ間のデータの受け渡しが円滑に行える。
【００２８】
さらに、パケット処理エンジン部１０における情報受け渡しテーブルをＦＩＦＯ（Ｆｉｒｓｔ　ｉｎ　Ｆｉｒｓｔ　ｏｕｔ）メモリで構成し、複数のパケット処理エンジンとしてのプロセッサの処理分担を司るタスクマネジャーがＦＩＦＯのキュー長監視を行い、溜まり具合に応じて検索前処理及び検索後処理に当たるプロセッサの分担個数を動的に変更可能としている。これにより、極端なバーストトラヒックにおいても処理能力不足とならず、品質保証が可能となる。
【００２９】
一方、検索エンジン部２０は、上述した検索前処理担当のプロセッサと検索後処理担当のプロセッサとの間の情報の受け渡しのための引き継ぎ情報として、情報受け渡しテーブルの特定箇所の識別情報を透過させる機能を有する。
【００３０】
また、検索エンジン部２０に、検索要求のインタフェースとは別に統計要求のインタフェースを設け、パケット処理エンジン部１０からのキューイング情報の統計を行う構成を採る。これにより、ルーティング統計とキューイング統計とを一つのテーブルで一元的に収集し、管理可能とする。
【００３１】
パケット処理エンジン部１０におけるパケット処理の検索後処理は、更にフロー毎のキューへの書き込み処理（キューイング処理）と、キューからの読み出し処理（スケジューリング処理）とに分けられる。これらの処理間の情報受け渡しのテーブルも宛先毎に全ての情報がひとかたまりに記載されたディスクリプタ（Ｄｅｓｃｒｉｐｔｏｒ）構成とする。これにより、情報読み出し時間の短縮及び更新処理の短縮化が実現できる。
【００３２】
また、各フロー内には複数のクラスが存在し、一つのクラスの中に更に複数のクラスが存在する二段階構成を採る。一段目のクラスは完全優先の読み出しとし、優先度の高いパケットが最優先で読み出される。二段目のクラスは複数のクラスに読み出し比率（クレジット初期値）が設定されており、その比率に応じてパケットが読み出される。アルゴリズムは、クレジットベースの貸し借りで実現され、クレジットの一番大きいクラスのパケットを読み出す。
【００３３】
そのため、１つのパケットを読み出した直後でも、未だクレジット値が大きければ、続けて読み出すことが可能である。また、パケットを読み出した場合にだけしかクレジットを更新する必要がないため、比較的簡易な処理で公平を保障可能である。
【００３４】
［第１の実施の形態］
〈ＩＰパケット処理装置〉
本発明の第１の実施の形態におけるＩＰパケット処理装置の構成を示す図２を参照すると、このＩＰパケット処理装置１は、パケット処理エンジン部１０と、検索エンジン部２０と、パケットバッファ部３０とを備えている。
【００３５】
ＩＰパケット処理装置１におけるパケット処理エンジン部１０は、パケット中継処理における分散処理を行うためのマルチエンジンまたはマルチタスクのパケット処理エンジンとして複数のプロセッサＰＥ（ＰＥ＃１〜ＰＥ＃ｍ）を有する。これらの複数のプロセッサＰＥ＃１〜ＰＥ＃ｍはパケット処理部４０を構成する。
【００３６】
このパケット処理部４０においては、パケット処理を検索エンジン部２０に渡す前の検索前処理と、検索エンジン部２０の結果に基づいて処理を行う検索後処理とに分け、かつその前後処理を別々のプロセッサＰＥで処理する。
【００３７】
パケット処理部４０は更に情報受け渡しテーブル４１を含む。この情報受け渡しテーブル４１は、検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎと検索後処理担当のプロセッサＰＥ＃ｎ＋１〜ＰＥ＃ｍとの間の情報の受け渡しのための共通のテーブルとして機能する。
【００３８】
情報受け渡しテーブル４１は検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎと同数（ここでは、ｎ個）存在する。情報受け渡しテーブル４１の特定箇所の識別情報（インデックス値またはテーブルアドレス等）は、検索エンジン部２０のインタフェース部を透過媒体として、検索後処理担当のプロセッサＰＥ＃ｎ＋１〜ＰＥ＃ｍに渡される。この情報受け渡しテーブル４１については、後に図５を参照して、更に詳述する。
【００３９】
パケット処理エンジン部１０は更に入力インタフェース部５０及び出力インタフェース部６０を有する。
【００４０】
また、検索エンジン部２０は、パケット中継処理における高速検索処理を可能にするために、ＣＡＭとラディッシュツリー（Ｒａｄｉｓｈ　Ｔｒｅｅ）またはテーブルなどとを含む検索メモリを有する検索処理部２１と、インタフェース部２２とを備える。
【００４１】
パケットバッファ部３０は、入力パケットのヘッダ部に続くデータ部のパケットデータを一時的に格納し、格納しているパケットデータを読み出し制御に応答して送出するために、バッファメモリ（キュー）を有する。このバッファメモリの構成については、後に第４の実施の形態で詳述する。
【００４２】
ＩＰパケット処理装置１への入力パケットは、パケット処理エンジン部１０の入力インタフェース部５０で受信される。入力インタフェース部５０に受信された入力パケットは、検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎのうちの処理待ち状態のいずれかのプロセッサＰＥ（ここでは、ＰＥ＃１）によってパケット中継処理を開始される。
【００４３】
プロセッサＰＥ＃１によるパケット中継処理において、パケットデータは入力インタフェース部５０からパケットバッファ部３０に転送される。これと同時に、プロセッサＰＥ＃１は、自己対応の情報受け渡しテーブル４１の一つの未使用領域（ここでは、領域Ｉｎｆｏ．＃０）をハント（捕捉）し、検索後処理に必要な情報及び検索処理に必要な情報（検索キーとしての宛先アドレスなどやデータ格納先頭アドレス）のみを書き込む。
【００４４】
プロセッサＰＥ＃１は、領域Ｉｎｆｏ．＃０に書き込んだ情報から検索処理及び検索後処理に必要な情報の抽出・編集を行い、情報受け渡しテーブル４１のインデックス値（ここでは、Ｉｎｆｏ．＃０）と自プロセッサ（ＰＥ）番号（ここでは、ＰＥ＃１）とを合わせて検索エンジン部２０へと渡す（送出する）。これで、検索前処理担当のプロセッサＰＥ＃１の処理は終了となる。
【００４５】
検索エンジン部２０の検索処理部２１では、プロセッサＰＥ＃１から受け取った検索キーに基づいて検索処理を実施する。プロセッサＰＥ＃１から送出されたインデックス値及びＰＥ番号は、インタフェース部２２でそのまま折り返され（透過され）、検索処理部２１からの検索結果と待ち合わせて、パケット処理部４０に渡される。
【００４６】
検索エンジン部２０から戻された検索結果は、検索後処理担当のプロセッサＰＥ＃ｎ＋１〜ＰＥ＃ｍのうちのいずれかの処理待ちのプロセッサ（ここでは、ＰＥ＃ｎ＋１）によって受信される。
【００４７】
プロセッサＰＥ＃ｎ＋１は、インタフェース部２２から戻されたインデックス値（Ｉｎｆｏ．＃０）及びＰＥ番号（ＰＥ＃１）に基づいて情報受け渡しテーブル４１にアクセスして入力の情報を取得し、検索処理部２１からの検索結果の情報と合わせて該当パケットの中継処理を行う。
【００４８】
〈入力インタフェース部及び検索前処理担当のプロセッサ〉
図３は図２における入力インタフェース部５０の詳細構成例を示す。図４は図２における検索前処理担当のプロセッサＰＥの動作を説明するためのフローチャートである。図２、図３及び図４を併せ参照すると、パケット処理エンジン部１０に入力してきたパケットは入力インタフェース部５０で処理される。
【００４９】
入力インタフェース部５０において、ＦＩＦＯ（＃０〜＃ｘ）５１及びこのＦＩＦＯ５１に対応する受信情報テーブル（＃０〜＃ｘ）５２はそれぞれ物理インタフェース毎（入力ポート毎または入力物理リンク毎）に設けられている。したがって、多重分離部５３は多重化転送されてきた入力パケットを物理インタフェース対応のＦＩＦＯ５１毎に分離する。
【００５０】
各ＦＩＦＯ５１が入力パケットの先頭から所定のバイト長のデータを受信した場合、書き込み制御部５４はパケットバッファ部３０の空きアドレスを取得し、この空きアドレスをバッファ先頭アドレスとして対応の受信情報テーブル５２に書き込む。
【００５１】
この受信情報テーブル５２には、更に新規パケットの到着フラグ、受信ステータス（パケットの先頭処理中、中間処理中、または最終処理中を示す自処理ステータスのフラグ）、及びパケットのヘッダ情報が書き込み制御部５４により書き込まれる。
【００５２】
書き込み制御部５４は、各ＦＩＦＯ５１に所定のバイト長のデータが蓄積される度にパケットバッファ部３０から新たな空きアドレスを取得し、チェーン処理（チェーニング）を行いながら、入力パケットのパケットデータをパケットバッファ部３０に転送していく。
【００５３】
なお、入力パケットのエンドデータが受信されるまでは、受信情報テーブル５２には先頭の情報が保持されている。この入力インタフェース部５０を含めて検索前処理プロセッサとする構成でもよい。
【００５４】
一層詳述すると、入力インタフェース５０には、各回線終端部（図示省略）で終端されたＩＰパケットがセルまたは固定長パケットに分割され多重されて入力される。そのため、入力インタフェース部５０は入力リンク毎（物理インタフェース毎）に構成されている。
【００５５】
入力インタフェース部５０に到着したパケットは、ヘッダ部内の入力ポート番号等に基づいて各バッファ（ＦＩＦＯ５１）に振り分けられる。
【００５６】
書き込み制御部５４は、ＦＩＦＯ５１にデータが蓄積されると、パケットバッファ部３０の空きアドレスを１つ取得し、パケットバッファ部３０にパケットデータを書き込む。
【００５７】
入力インタフェース部５０では、フレームを意識した処理を行っており、ＦＩＦＯ５１に到着したセルがパケットの先頭なのか、中間なのか、最終なのかの状態遷移を監視している。
【００５８】
書き込み制御部５４は、ＦＩＦＯ５１に到着したセルが先頭（つまり、新規パケットの到着）であった場合は、取得したパケットバッファ部３０の先頭アドレス、受信ステータス、及びヘッダ情報をＦＩＦＯ５１対応の受信情報テーブル５２に書き込む。
【００５９】
この受信情報テーブル５２には、次の情報が書き込まれる。つまり、
（１）新規パケット到着フラグ（最終セル受信でＯＮ（「１」設定）、検索前処理プロセッサ受け取りでＯＦＦ（「０」設定））、
（２）パケットバッファ先頭アドレス（パケットバッファ部３０へのパケットデータの格納アドレス）、
（３）受信ステータス（フレーム受信中の状態：先頭処理、中間処理、最終処理）、
（４）ヘッダ情報（フレーム先頭のパケットヘッダ部）、
（５）パケット長（該当フレームのパケット長）。
【００６０】
この受信情報テーブル５２には１フレーム毎に上記の情報が格納され、ＦＩＦＯ５１毎に複数セル分の記憶領域がある。受信情報テーブル５２の容量（＃０〜＃ｘ）は後続の検索前処理プロセッサの処理能力に依存する。
【００６１】
受信情報テーブル５２への情報書き込み状態は新規パケット到着毎にサイクリックに更新される。この場合、書き込み制御部５４は、新規パケット到着フラグがＯＮの状態のままであるときは、書き込みを行わず、入力方向に対して受信不可の通知（バックプレッシャ）を行う。
【００６２】
入力インタフェース部５０は、到着するデータのフレームを意識しながら、各ＦＩＦＯ５１分のデータが蓄積される度にパケットバッファ部３０から新たな空きアドレスを取得し、チェーン処理を行いながらパケットデータをパケットバッファ部３０に転送する。各ＦＩＦＯ５１がパケットのエンドデータを受け取った段階で、受信情報テーブル５２の新規パケット到着フラグがＯＮされる。
【００６３】
検索前処理に割り当てられていて、かつ処理空き状態の検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎは、それぞれのタイミングで受信情報テーブル５２のポーリングスキャン（Ｐｏｌｌｉｎｇ　Ｓｃａｎ）を実施しており、新規パケット到着フラグが立った後に最初にその状態を検出した検索前処理担当のプロセッサＰＥが処理を請け負う。処理を請け負った検索前処理担当のプロセッサＰＥは、必要な情報を後述する情報受け渡しテーブル４１にコピーした後、受信情報テーブル５２の新規パケット到着フラグをＯＦＦに書き換える。これにより、受信情報テーブル５２が開放される。
【００６４】
〈情報受け渡しテーブル及び検索前処理担当のプロセッサ〉
図５は図２における情報受け渡しテーブル４１の詳細構成を示す。図２、図４及び図５を併せ参照すると、検索前処理を請け負ったプロセッサＰＥは、自己対応の専用の情報受け渡しテーブル４１から格納領域Ｉｎｆｏ．＃０〜＃Ｙのいずれかに対応する空きアドレスを取得し、必要な情報としてパケットバッファ部３０におけるパケットデータ格納先の先頭アドレス及び検索データの基となるヘッダ情報等を情報受け渡しテーブル４１に書き込む。
【００６５】
検索前処理担当のプロセッサＰＥは、情報受け渡しテーブル４１への上記必要情報の書き込み後、入力パケットのチェック処理を経て、検索処理に必要なデータの抽出を行い、検索キー（宛先ＩＰアドレス：ＩＰ−ＤＡ）と、情報受け渡しテーブル４１のインデックス値（Ｉｎｆｏ．番号）と、自プロセッサ（ＰＥ）番号とを検索エンジン部２０に送出して、検索要求を行う。
【００６６】
ここで、情報受け渡しテーブル４１の各格納領域Ｉｎｆｏ．＃０〜＃Ｙには、インデックス値としてのＩｎｆｏ．番号に続いて、ＩＰｖ４またはＩＰｖ６などを示すエントリコードと、入力ポート番号と、宛先ＩＰアドレス（ＩＰ−ＤＡ）と、送信元ＩＰアドレス（ＩＰ−ＳＡ）などが格納される。
【００６７】
ここで、検索前処理担当のプロセッサＰＥ毎のテーブル数（Ｙ）は、検索前処理及び検索後処理の処理能力の比率により決定されるパラメタである。また、検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎの数（ｎ）と検索後処理担当のプロセッサＰＥ＃ｎ＋１〜ＰＥ＃ｍの数（ｍ）とは、検索前処理及び検索後処理の処理時間の比率により決定されるパラメタである。
【００６８】
〈検索前処理担当のプロセッサと検索エンジン部との連携〉
図６は図２における検索前処理担当のプロセッサＰＥと検索エンジン部２０との連携を示す。
【００６９】
図２及び図６を併せ参照すると、検索エンジン部２０とパケット処理部４０とのインタフェース、つまり検索エンジン部２０においてＦＩＦＯで構成される検索要求テーブル２３と、パケット処理部４０における各検索前処理担当のプロセッサＰＥ及び情報受け渡しテーブル４１とのインタフェースを物理的に個別にすれば、複数の検索前処理担当のプロセッサＰＥ間での競合による待ち合わせが発生しないため、処理能力は向上する。後述するように、このインタフェースを共通とすれば、ハードウェア量の削減が可能である。
【００７０】
検索エンジン部２０に対する検索要求のインタフェースとしては、パケット処理部４０から見れば、常に検索要求テーブル２３の１要求分の領域のみがアクセス可能である。この検索要求テーブル２３に１つの検索要求が書き込まれた場合、ライトポインタＷＰが自動的に次の領域に移動する。したがって、各検索前処理担当のプロセッサＰＥは検索要求テーブル２３のアドレスを意識する必要がない、つまり常に同一のアドレスへ書き込めばよい。
【００７１】
検索エンジン部２０では、検索要求テーブル２３のＦＩＦＯの空塞状態を監視しており、このＦＩＦＯにデータが書き込まれれば、検索処理部２１がデータを読み取って検索処理を行う。検索処理部２１から検索要求テーブル２３に対して読み取りを行えば、リードポインタＲＰが次の領域に移動するので、検索処理部２１は常に同一のアドレスへのアクセスを行えばよい。
【００７２】
なお、検索要求テーブル２３は検索前処理プロセッサＰＥ毎に具備されており、一連のデータが書き込まれると回転する（アドレスが進む）ＦＩＦＯ構成となっている。
【００７３】
また、検索前処理プロセッサＰＥのインタフェースに依存しない場合、インタフェースも各プロセッサＰＥ毎に具備することにより、プロセッサＰＥ間での同時アクセスによる処理能力低下を防止できる。したがって、この場合はＰＥ番号は不要でもよい。
【００７４】
〈検索エンジン部〉
図７は図２における検索エンジン部２０の詳細構成を示す。図２及び図７を併せ参照すると、検索エンジン部２０では、検索前処理担当のプロセッサＰＥから渡された検索キーに基づいて各種検索（ルーティング（経路情報）検索、フィルターリング検索、クラス（Ｃｌａｓｓｉｆｙｉｎｇ）検索等）の処理を実施し、検索前処理担当のプロセッサＰＥから渡されたインデックス値及びＰＥ番号を検索結果の情報に付与してパケット処理部４０の検索後処理担当のプロセッサＰＥに返却する。なお、ここでＰＥ番号は検索要求テーブル２３の検索要求アドレスから引き出すことが可能である。
【００７５】
一層詳述すると、インタフェース部２２の検索要求テーブル２３には、検索前処理担当のプロセッサＰＥからＰＥ番号、テーブル番号（情報受け渡しテーブル４１の格納領域Ｉｎｆｏ．＃０〜＃Ｙ）、及び検索キーデータが書き込まれる。
【００７６】
検索要求テーブル２３が空き状態から格納情報有りに変化したのを契機に、インタフェース部ＮＰ−ＲＥＱ−ＩＦで検索キー情報とＰＥ情報（ＰＥ番号及びテーブル番号）とが分離され、検索キー情報は検索処理部２１における検索処理ルーチンへ送られ、かつＰＥ情報はインタフェース部ＮＰ−ＲＥＳ−ＩＦに送られる。
【００７７】
検索処理部２１における検索処理ルーチンでは、まず検索キーの入力ポート番号に基づいきインタフェース部ＶＰＴ−ＩＦを通してＶＰＮ（Ｖｉｒｔｕａｌ　Ｐｒｉｖａｔｅ　Ｎｅｔｗｏｒｋ）テーブルにアクセスを行い、ＶＰＮ識別情報ＶＰＮ−ＩＤが得られる。
【００７８】
続いて、検索処理部２１おいては、インタフェース部Ｒ−ＣＡＭ−ＩＦを介して検索メモリのルーティングＣＡＭを用いて、ＶＰＮ識別情報ＶＰＮ−ＩＤ及び宛先ＩＰアドレスＩＰ−ＤＡに基づいて、出力ルータポート（ルータとしてのＩＰパケット処理装置１の出力ポート番号）の検索を行う。ルーティング用メモリにエントリ毎の出力ルータポートが書き込まれている。
【００７９】
その後、Ｌ２ヘッダ、Ｌ３ヘッダ、及びＬ４ヘッダなどの全ての検索キー情報に基づいて、インタフェース部Ｆ−ＣＡＭ−ＩＦを介してフィルタリングＣＡＭでの検索を実施する。フィルタリングのアクションはフィルタリングメモリに書き込まれてあり、廃棄、透過、カプセル対象、デカプセル対象、マター（ｍａｔｅｒ）対象、及びクラス識別子などのアクションに対応するフラグをセットする。
【００８０】
また、先に検索した出力ルータポートに基づいて、入口（ｉｎｇｒｅｓｓ）の場合は後段の図示省略のスイッチ（スイッチ・ファブリック）内のタグ情報に、また出口（ｅｇｒｅｓｓ）の場合は後段のスイッチの出力物理ポートもしくはチャネルにインタフェース部ＣＨＴ−ＩＦを通してチャネル（ｃｈ）変換テーブルで変換を行う。
【００８１】
インタフェース部ＮＰ−ＲＥＳ−ＩＦにおいては、最終的に求められた送信先情報、フィルターリングアクションフラグ、及びクラス情報に、先に渡されていたＰＥ情報としてのＰＥ番号及びテーブル番号を合わせて、検索結果テーブル２４へ書き込みを行う。
【００８２】
また、検索処理部２１においては、同時にルーティングの統計情報処理、つまりルーティングＣＡＭのエントリ毎の統計情報処理を行う。なお、上述した検索エンジン部２０は処理ステージによるパイプライン処理を行っており、全ての検索処理は一定の処理時間で終了する。
【００８３】
〈検索後処理担当のプロセッサと検索エンジン部との連携〉
図８は図２における検索後処理担当のプロセッサＰＥと検索エンジン部２０との連携を示す。図９は検索後処理プロセッサＰＥの処理手順を示すフローチャートである。
【００８４】
図２、図８及び図９を併せ参照すると、検索エンジン部２０とパケット処理部４０とのインタフェース、つまり検索エンジン部２０においてＦＩＦＯで構成される検索結果テーブル２４と、パケット処理部４０における各検索後処理担当のプロセッサＰＥとのインタフェースを共通にすれば、複数の検索後処理担当のプロセッサＰＥ＃ｎ＋１〜ＰＥ＃ｍは、複数の検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎと無関係に、つまり検索前処理担当のプロセッサＰＥ＃１〜ＰＥ＃ｎに依存せずに処理可能である。
【００８５】
検索結果テーブル２４には、先頭アドレスに検索結果の有効フラグがあり、その次のアドレスから検索結果の情報が書き込まれている。検索後処理に割り当てられており、かつ処理空き状態の検索後処理担当のプロセッサＰＥはそれぞれのタイミングで検索結果テーブル２４をポーリングスキャンしており、検索結果有効フラグが有効であった場合に、それに続く検索結果の情報を用いて処理を行う。検索結果テーブル２４の検索結果有効フラグがフラグオンの状態で最初にアクセスした検索後処理担当のプロセッサＰＥが処理を請け負う。
【００８６】
検索エンジン部２０に対する検索結果のインタフェースとしては、パケット処理部４０からは１つの検索結果のみが見えており、最終アドレスへのアクセスで回転する（アドレスが次の結果に移る）構成となっている。つまり、検索後処理担当のプロセッサＰＥは有効な検索結果に対しては１度しかアクセスできない構成である。
【００８７】
検索結果テーブル２４に有効な検索結果の情報が未だある場合は、最終アドレスへのアクセスで次の情報へ移るが、検索結果テーブル２４に有効なデータがない場合（ＦＩＦＯが空の場合）は、先頭アドレスには「０」が見えるようになっており、無効データが検索後処理担当のプロセッサＰＥには見える。
【００８８】
パケット処理部４０の検索後処理担当のプロセッサＰＥから見える検索結果テーブル２４は常に未処理の情報しか見せない構成となっている。検索結果テーブル２４の読み取りを行うことでリードアドレスが更新されるため、未処理の検索結果が検索結果テーブル２４のＦＩＦＯ上に存在すれば、そのデータが次のアクセスで見える。
【００８９】
また、検索結果テーブル２４のＦＩＦＯ上にデータがない場合、検索結果情報の先頭データはＡｌｌ「０」が見えるようになっている。つまり、検索結果テーブル２４の先頭データには、検索結果情報の有効または無効を示すフラグがアサインされており、このフラグが「０」の場合はパケット処理部４０は処理を行わない。
【００９０】
検索後処理を請け負ったＰＥは、検索結果情報のＰＥ番号とインデックス値とから情報受け渡しテーブル４１にアクセスし、検索前処理担当のプロセッサＰＥの処理情報と検索エンジン部２０からの検索結果情報とを合わせた結果に基づき、宛先毎クラスキューへの登録または廃棄処理等のパケット中継処理を行う。
【００９１】
〈ＩＰパケット処理装置の処理能力〉
上述した第１の実施の形態のＩＰパケット処理装置１においては、パケット中継処理の検索前処理及び検索後処理を別々のプロセッサＰＥで実行することにより、図１０に示すように、検索前処理及び検索後処理を全く独立して遂行できる。この結果、検索時間がパケット中継処理時間から除外でき、処理能力の向上を図ることができる。また、検索結果待ちのサスペンド時間が無くせるので、プロセッサ動作率を論理的に１００％とすることが可能になる。
【００９２】
さらに、検索前処理及び検索後処理を別々のプロセッサＰＥで行う場合、プロセッサＰＥ間で直接に受け渡すときは、それなりの煩雑な手順が必要となるし、検索処理にある程度の時間がかかるときは、検索結果が返って来るまで処理を待ち合わせる必要がある。しかし、検索エンジン部２０のインタフェース部２２を検索前処理担当のプロセッサＰＥと検索後処理担当のプロセッサＰＥ間の情報受け渡しの媒体として使用することにより、待ち合わせ処理や煩雑な手順が不必要となる利点がある。
【００９３】
この利点を実現可能にするために検索エンジン部２０では、検索に必要な情報のみではなくプロセッサＰＥ間の情報受け渡し用のフィールドとしてインタフェース部２２を付加し、このフィールドは検索結果を透過する構成を採っている。
【００９４】
ここで、検索前処理の時間は最小パケット入力時間と同一、検索の潜伏期（Ｌａｔｅｎｃｙ）は最小パケット時間の８倍、及び検索後処理時間は検索前処理時間の３倍とするとともに、各プロセッサＰＥがシングルタスクであることを前提に詳述する。
【００９５】
図１０（ａ）の上部のチャートは、複数のプロセッサＰＥのそれぞれで全てのパケット処理（検索処理及びパケット中継処理）を行う場合であり、入力パケット９〜１２は、プロセッサＰＥが全て塞がっているために処理不可能となる。検索の結果待ちでタスクがサスペンド状態もしくは検索後処理中である。入力パケット９〜１２も処理可能とするためには、プロセッサＰＥを更に４つ増加させるか、処理ステップ数や検索の潜伏期を短縮させる必要がある。
【００９６】
図１０（ａ）の下部のチャートは、本発明のＩＰパケット処理装置１のように、検索前処理及び検索後処理を別々のプロセッサＰＥで処理する場合である。この場合、検索前処理及び検索後処理を別々のプロセッサＰＥで行うので、検索待ちでのタスクサスペンドが発生しないために、全てのパケットを処理可能である。また、本例の処理時間の前提においては、図１０（ｂ）に示すように、検索前処理担当のプロセッサＰＥが１個、かつ検索後処理担当のプロセッサＰＥが３個でも可能である。
【００９７】
つまり、同一プロセッサＰＥで一連のパケット中継処理（検索処理及びパケット処理）を行う場合に比して、約１／３の処理能力でも実現可能である。上部のチャートに示すように、同一プロセッサＰＥで一連のパケット処理を行う場合は、プロセッサＰＥが１２個必要となるのに対して、本発明では最低４個のプロセッサＰＥで処理可能である。
【００９８】
［第２の実施の形態］
本発明の第２の実施の形態におけるＩＰパケット処理装置について、図１１、図１２及び図１３を併せ参照して説明する。図１１は第２の実施の形態におけるＩＰパケット処理装置の構成を示す。図１２はプロセッサの検索前処理及び検索後処理の切替制御手法を説明するための図である。図１３はしきい値制御の概要を説明するための図である。
【００９９】
通常、検索処理の前後で処理を分割した場合、検索前処理に比較して検索後処理の方が処理時間を要する。したがって、検索前処理担当のプロセッサと検索後処理担当のプロセッサとの情報受け渡しテーブルでは、極端なバーストトラヒックの場合、つまりショートパケットの連続到着等の場合は、検索後処理が追いつかず、情報受け渡しテーブルに未処理の情報が溜まっていくことになる。
【０１００】
また、入力パケットのフレーム形式（ＭＰＬＳ（Ｍｕｌｔｉ　Ｐｒｏｔｏｃｏｌ　Ｌａｂｅｌ　Ｓｗｉｔｃｈｉｎｇ）、ＰＰＰ（Ｐｏｉｎｔ−ｔｏ−Ｐｏｉｎｔ　Ｐｒｏｔｏｃｏｌ）、ＩＰｖ４、ＩＰｖ６等）によって検索前処理の時間も異なるし、検索後処理においてもアドミッション制御（ＷＲＥＤ）の有無やエンカプセル有無等により処理時間が異なる。
【０１０１】
本来、プロセッサの処理能力や個数がワーストのトラヒックパターンに対して楽に上回っていれば問題無いのであるが、実際にはコスト面や実装条件、またはプロセッサの処理能力からワーストのトラヒックが偏って入力されるのはレアパターンと割り切り、平均的なトラヒックで処理能力の算出を行う。
【０１０２】
この第２の実施の形態におけるＩＰパケット処理装置１は、上述した第１の実施の形態におけるＩＰパケット処理装置１と同様に、パケット処理エンジン部１０、検索エンジン部２０、及びパケットバッファ部３０を備える。ここでは、パケット処理エンジン部１０の入力インタフェース部５０及び出力インタフェース部６０と、パケットバッファ部３０との図示を同一構成であるので省略している。
【０１０３】
このＩＰパケット処理装置１では、情報受け渡しテーブル（入力ディスクリプタ）４２のキュー長を監視し、未処理データの溜まり具合に応じて、検索前処理及び検索後処理に割り当てられるプロセッサＰＥを動的に変更し直す。
【０１０４】
これにより、本来、検索前処理に割り付られていたプロセッサＰＥが、ＦＩＦＯ同等構成の情報受け渡しテーブル４２のキュー長が伸びてくると検索後処理に割り付けられ、検索後処理を助ける。情報受け渡しテーブル４２のキュー長が戻ってくると、再度検索前処理に戻る。
【０１０５】
パケット処理部４０におけるキュー管理部４３は、情報受け渡しテーブル４２のライトポインタＷＰ及びリードポインタＲＰを制御することにより、キュー長監視を行う。
【０１０６】
ＰＥ管理部（Ｔａｓｋ　Ｍａｎａｇｅｒ）４４は、情報受け渡しテーブル４２のキュー長としきい値との比較を行い、キューの溜まり具合に応じて、検索前処理担当のプロセッサＰＥ及び検索後処理担当のプロセッサＰＥの分配を動的に変更する。
【０１０７】
具体的には、ＰＥ管理部４４は、次のように検索前処理担当のプロセッサＰＥ及び検索後処理担当のプロセッサＰＥの分配を動的に変更する。
【０１０８】
（１）情報受け渡しテーブル４２のキュー長が「大」（検索後処理が輻輳）の場合、例えば分担比率が１：３になるように、検索前処理担当のプロセッサＰＥを検索後処理担当のプロセッサＰＥに移動する。
【０１０９】
（２）情報受け渡しテーブル４２のキュー長が「中」（検索後処理がやや輻輳）の場合、例えば分担比率が１：２になるように、検索前処理担当のプロセッサＰＥを検索後処理担当のプロセッサＰＥに移動する。
【０１１０】
（３）情報受け渡しテーブル４２のキュー長が「小」（通常状態）の場合、例えば分担比率が通常値の１：１になるように、検索後処理担当のプロセッサＰＥを検索前処理担当のプロセッサＰＥに移動する。
【０１１１】
情報受け渡しテーブル４２のキュー長をＰＥ管理部４４で監視し、キュー管理部４３のキュー状態レジスタ４５に反映させる。状態遷移は発振しないようにＯｎ／Ｏｆｆの値にヒステリシスを設ける。ここでは、
（１）状態１ビット：増加しきい値１超過でセット、戻りしきい値１未満でリセット、
（２）状態２ビット：増加しきい値２超過でセット、戻りしきい値２未満でリセット。
【０１１２】
更に、細分化したい場合は、ビットを増加させることで可能である。また、各プロセッサＰＥがどの状態ビットを参照するかは、起動パラメタでプロセッサＰＥ毎に与える。
【０１１３】
例えば、全プロセッサＰＥが８個で、状態に応じて、４：４→３：５→２：６と変化させたい場合、検索前処理専用プロセッサＰＥは２個、検索後処理専用プロセッサＰＥは４個、検索前後処理兼用プロセッサＰＥは２個となる。このとき、検索前後処理兼用プロセッサＰＥの片方は状態１ビットで処理を選択し、もう一方は状態２ビットで処理を選択する。
【０１１４】
［第３の実施の形態］
次に、本発明の第３の実施の形態におけるＩＰパケット処理装置について、図１４を参照して説明する。
【０１１５】
ＩＰパケット処理装置１の保守機能として統計情報の収集が必要であるが、統計の項目としては、ルーティングエントリ毎の統計と、パケットバッファ部３０のキューでの統計との２つが要求される。
【０１１６】
本来、ルーティングの統計は検索エンジン部２０の検索処理機能部分でしか解らない情報であり、これに対してパケットキューの統計はパケット処理エンジン部１０のキューイングまたはスケジューリング機能部分でしか解らない情報である。
【０１１７】
そのため、これらの２つの情報は別々の機能部分から読み出し、再度編集を行う必要があったり、入力のインタフェース情報とキュー情報との関係が解らない問題がある。
【０１１８】
第３の実施の形態におけるＩＰパケット処理装置１においては、検索エンジン部２０と、キューイン及びスケジューリングを行うパケット処理エンジン部１０のパケット処理部４０との間に統計要求のインタフェースとして、ＦＩＦＯ構成の統計要求テーブル２５を備えている。
【０１１９】
これにより、統計情報の一元管理を可能とし、かつ検索後のキュー毎に入力インタフェース別の情報を統計することが可能である。
【０１２０】
この第３の実施の形態におけるＩＰパケット処理装置１においては、パケット処理部４０の各プロセッサと検索エンジン部２０との連携により、統計情報を検索エンジン部２０の外部統計エリアとしての統計メモリ２６に一元管理する。
【０１２１】
検索エンジン部２０は、ルーティング統計では、パケット処理部４０の検索前処理プロセッサＰＥからの検索要求に対応する検索処理で、検索処理部２１の検索メモリのＣＡＭなどのデータにヒットしたエントリ毎に統計を検索メモリ２６に収集する。
【０１２２】
また、パケット処理部４０は検索エンジン部２０の統計要求テーブル２５を通して次のキュー統計を行う。
【０１２３】
（１）検索前処理部でのキュー統計
パケット処理部４０の検索前処理プロセッサＰＥは、フレームチェック、ヘッダチェック等で廃棄処理したパケット数を入力インタフェース毎に統計要求テーブル２５に通知する。これにより、検索要求前に廃棄処理されたパケットの統計が統計メモリ２６において可能になる。
【０１２４】
（２）検索後処理でのキュー統計
パケット処理部４０の検索後処理プロセッサＰＥは、検索結果テーブル２４から読み出した検索結果に基づいて、宛先キュー毎のパケット到着数または廃棄数を入力インタフェース毎に統計要求テーブル２５を通して統計メモリ２６に通知する。
【０１２５】
また、検索後処理プロセッサＰＥは、検索結果に基づいて、アクション（廃棄処理や抽出等）を入力インタフェース毎に統計要求テーブル２５を通して統計メモリ２６に通知する。
【０１２６】
（３）スケジューリング処理でのキュー統計
パケット処理部４０のスケジューリング制御部（スケジューラ）４６は、実際にキューから読み出したパケット数（透過フレーム数）を入力インタフェース毎に統計要求テーブル２５を通して統計メモリ２６に通知する。
【０１２７】
［第４の実施の形態］
次に、本発明の第４の実施の形態におけるＩＰパケット処理装置について、図１５、図１６、図１７及び図１８を併せ参照して説明する。図１５は第４の実施の形態におけるＩＰパケット処理装置１の構成例を示す。図１６は出力ディスクリプタ４７の構成例を示す。図１７は宛先毎のキュー構成例を示す。図１８は比率読み出しアルゴリズムの一例を示す。
【０１２８】
このＩＰパケット処理装置１において、検索後処理のために検索エンジン部２０からパケット処理部４０の検索後処理プロセッサＰＥに渡される検索結果は宛先番号とＱｏＳクラス等の情報である。
【０１２９】
宛先番号は宛先毎のキュー情報等のデータテーブル（情報受け渡しテーブル４１及び出力ディスクリプタ４７）のインデックス値を示している。検索後処理プロセッサＰＥは、宛先番号に基づいて索引した情報受け渡しテーブル４１から出力ディスクリプタ４７のインデックス値（宛先）を得る。検索後処理プロセッサＰＥは、得られたインデックス値に基づいて出力ディスクリプタ４７から宛先毎のキュー情報を入手することにより、キューイング処理を行う。
【０１３０】
出力ディスクリプタ４７には、宛先毎の情報として、各ＱｏＳクラスのキュー長、廃棄しきい値、先頭アドレス、最終アドレス等の情報が全てひとかたまりで配置（格納）されている。出力ディスクリプタ４７は検索後処理プロセッサＰＥからの一回の連続アクセスで必要な情報の全てが得られるテーブル構成となっている。
【０１３１】
検索後処理プロセッサＰＥは、検索結果の情報から得られた宛先の情報で入力インタフェース部５０で入力ポート毎にキューイングされているパケットを宛先クラス毎のキューイングに変更を行う。変更されたキュー情報は出力ディスクリプタ４７に書き込まれる。
【０１３２】
出力処理プロセッサＰＥ（ＰＥ＃ｋ）は、検索後処理プロセッサＰＥとは全く独立の動作で、スケジューラ４６からの該当宛先パケットの読出し要求に応じてパケットを該当キューから読み出す。その際に、出力処理プロセッサＰＥは出力ディスクリプタ４７から該当キューの情報を入手してパケットを出力する。出力処理プロセッサＰＥはパケットを出力したら、読み出したクラスのキュー情報を更新する。出力ディスクリプタ４７でインタフェースを行うことにより、検索後処理プロセッサＰＥと出力処理プロセッサＰＥ間で情報を共有する。
【０１３３】
各クラス間の読み出し優先制御において、各クラスに指定された比率に応じて読み出す場合のアルゴリズムとして、設定された比率をクレジット（ここでは、読み出し比率のパラメタ）初期値として各クラスからパケットを読み出す度にあるパケット長の境界に応じてクレジット値を互いに貸し借りすることにより、簡易的な公平を保障して読み出す。
【０１３４】
宛先毎のキュー構成は、図１７に示すように、二段階構成となっている。キューは宛先（出力ポート番号）毎に図１６に示す構成を採る。完全優先制御で分類された一段目のクラスキューの中に、更に細分化された二段目の複数のクラスがあり、細分化された各クラス間はあらかじめ設定された比率に応じて読み出される。
【０１３５】
この構成を採ることにより、パケット読み出しの優先制御やアドミッション制御などの品質制御をより細かく行うことが可能になる。
【０１３６】
比率読み出しアルゴリズムについて示す図１８を参照すると、ＱｏＳ毎に設定されたクレジット値の比がクラス間の読み出し比率となる。各クレジット値は２の階乗で指定され、クレジット値としては、１，２，４，８，１６，３２，６４，１２８までの値となる。
【０１３７】
各クレジットは、各クラスのクレジット初期値となる。本グループ内からパケットを読み出す場合は、その時点で一番大きなクレジット値を持ったＱｏＳのパケットを読み出す。
【０１３８】
さらに、次に示す方法に基づいてＱｏＳ間でクレジット値の貸し借りを行うことにより、クラス間の比率の保証を実現する。
【０１３９】
それぞれのウエイト値を直列に並べたスケジューラを作成し、自クラスからパケットを読み出す毎に１つづつ進めていく（Ｑｏｓ　Ｗｈｅｅｌ）。
【０１４０】
パケット単位に読み出しを行い、新たなパケットを読み出す際には、クレジット値の一番大きいＱｏＳのキューから読み出す。なお、読み出すべきパケットが存在しない場合は、２番目のＱｏＳに移行する。
【０１４１】
データ読み出し時には、次の論理でクレジット値の更新処理を行う。
（１）ＱｏＳ　Ｗｈｅｅｌが指しているＱｏＳと実際に読み出されたＱｏＳとを比較する。
（２）同じＱｏＳであれば、クレジットの減算は行わない。
（３）ＱｏＳが異なる場合は、実際に読み出したＱｏＳのクレジットを１減算する。
（４）ＱｏＳ　Ｗｈｅｅｌの示すＱｏＳのクレジットに１を加算する。
【０１４２】
〔変形例〕
上述した各実施の形態における処理はコンピュータで実行可能なプログラムとして提供され、ＣＤ−ＲＯＭやフロッピーディスクなどの記録媒体、さらには通信回線を経て提供可能である。
【０１４３】
また、上述した各実施の形態における各処理または構成はその任意を選択し組合せて実施することもできる。
【０１４４】
〔その他〕
（付記１）　パケットの転送を経路情報対応のエントリに基づいて行うための連想メモリを含む検索エンジン部と；
前記パケットの処理を前記検索エンジン部に渡す前の検索前処理を担当する第１のプロセッサと；
前記検索エンジン部の検索結果に基づいて前記パケットの中継処理を行うための検索後処理を担当する第２のプロセッサと；
を備えるパケット処理装置。
【０１４５】
（付記２）　前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの間の情報の受け渡し行うためのテーブルを更に備え；
このテーブルの特定箇所の識別情報を前記検索エンジン部を透過媒体として渡す付記１記載のパケット処理装置。
【０１４６】
（付記３）　前記テーブルがＦＩＦＯメモリで構成される場合、前記ＦＩＦＯメモリのキュー長監視を行い、溜まり具合に応じて、前記検索前処理担当の第１のプロセッサと前記検索後処理担当の第２のプロセッサとの分担個数を動的に変更する手段を更に備える
付記２記載のパケット処理装置。
【０１４７】
（付記４）　前記検索エンジン部は、ルーティング統計情報とともに、少なくとも前記検索前処理担当の第１のプロセッサ及び前記検索後処理担当の第２のプロセッサからのキューイング統計情報の一元管理を行うために、前記検索前処理担当の第１のプロセッサからの検索要求のインタフェースとは別に、統計要求のインタフェースを備える
付記１記載のパケット処理装置。
【０１４８】
（付記５）　フロー毎にキューに書き込むキューイング処理と、前記キューから読み出すスケジューリング処理との情報受け渡しを行うために、宛先毎に全てのキューイング情報がひとかたまりに記載されるディスクリプタを更に備える
付記１記載のパケット処理装置。
【０１４９】
（付記６）　各フロー内には複数のクラスが存在し、一つのクラスの中に更に複数のクラスが存在する二段階キュー構成手段を更に備える
付記１記載のパケット処理装置。
【０１５０】
（付記７）　前記二段階キュー構成手段における一段目のクラスは完全優先の読み出しとして優先度の高いパケットが最優先で読み出され、二段目のクラスは複数のクラスに読み出し比率としてのクレジット値が設定され、このクレジット値に応じて前記パケットが読み出される
付記６記載のパケット処理装置。
【０１５１】
（付記８）　複数クラス間の読み出しを各クラスに指定された前記読み出し比率に応じて行う場合、前記クレジット値を互いに貸し借りさせる読み出しアルゴリズムを更に備える
付記７記載のパケット処理装置。
【０１５２】
（付記９）　受信したパケットに含まれる宛先アドレスとこのパケットの処理に関連する情報とをそれぞれ格納する少なくとも１つの場所を示す手段と；
前記場所から格納された前記宛先アドレスに基づく経路情報の検索から得られた前記パケットの出力先を特定する情報と前記格納場所とを対応させる手段と；
前記パケットを前記格納場所から前記パケットの処理に関連する情報に基づき前記パケットに必要な処理を行い、特定された前記出力先にパケットを送出する手段と；
を備えるパケット処理装置。
【０１５３】
（付記１０）　受信したパケットに含まれる宛先アドレスと、このパケットの処理に関連する情報を格納する少なくとも１つの場所とをそれぞれ示す手段と；
前記宛先アドレスに基づく経路情報の検索から得られた前記パケットの出力先を特定する情報と前記格納場所とをそれぞれ対応させる手段と；
前記パケットを前記格納場所から前記パケットの処理に関連する情報に基づき前記パケットに必要な処理を行い、特定された前記出力先にパケットを送出する手段と；
を備えるパケット処理装置。
【０１５４】
【発明の効果】
以上説明したように、本発明によれば、検索処理のための待ち時間を大幅に抑制して処理能力の向上が可能である。
【０１５５】
本発明によれば、検索前処理担当（割当）のプロセッサと検索後処理担当（割当）のプロセッサとの間の情報の受け渡しを円滑に行うことが可能である。
【０１５６】
本発明によれば、極端なバーストトラヒックにおいても処理能力不足とならず、品質保証が可能である。
【０１５７】
また、本発明によれば、ルーティング統計とキューイング統計とを一元的に管理可能である。
【図面の簡単な説明】
【図１】本発明の各実施の形態のＩＰパケット処理装置の共通構成を示すブロック図。
【図２】本発明の第１の実施の形態のＩＰパケット処理装置の構成を示すブロック図。
【図３】図２における入力インタフェース部の詳細構成例を示すブロック図。
【図４】図２における検索前処理プロセッサの処理手順を説明するためのフローチャート。
【図５】図２における情報受け渡しテーブルの詳細構成例を示すブロック図。
【図６】図２における検索前処理プロセッサと検索エンジン部との連携を説明するための図。
【図７】図２における検索エンジン部の詳細構成例を示すブロック図。
【図８】図２における検索後処理プロセッサと検索エンジン部との連携を説明するための図。
【図９】図２における検索前処理プロセッサの処理手順を説明するためのフローチャート。
【図１０】図２におけるＩＰパケット処理装置の処理能力を説明するための図。
【図１１】本発明の第２の実施の形態のＩＰパケット処理装置の構成を示すブロック図。
【図１２】図１１における検索前処理プロセッサ及び検索後処理プロセッサの切替手法を説明するための図。
【図１３】検索前処理プロセッサ及び検索後処理プロセッサの切替時のしきい値制御を説明するための図。
【図１４】本発明の第３の実施の形態のＩＰパケット処理装置を説明するためのブロック図。
【図１５】本発明の第４の実施の形態のＩＰパケット処理装置の構成を示すブロック図。
【図１６】第４の実施の形態のＩＰパケット処理装置における出力ディスクリプタの構成例を示すブロック図。
【図１７】第４の実施の形態のＩＰパケット処理装置におけるキューの構成例を示すブロック図。
【図１８】第４の実施の形態のＩＰパケット処理装置における比率読み出しアルゴリズムを説明するための図。
【符号の説明】
１　　　ＩＰパケット処理装置
１０　　パケット処理エンジン部
２０　　検索エンジン部
２１　　検索処理部
２２　　インタフェース部
２３　　検索要求テーブル
２４　　検索結果テーブル
２５　　統計要求テーブル
２６　　統計メモリ
３０　　パケットバッファ部
４０　　パケット処理部
ＰＥ　　検索前処理プロセッサ
ＰＥ　　検索後処理プロセッサ
ＰＥ　　出力処理プロセッサ
４１　　情報受け渡しテーブル
４２　　情報受け渡しテーブル
４３　　キュー管理部
４４　　ＰＥ管理部
４５　　キュー状態レジスタ
４６　　スケジューラ
４７　　出力ディスクリプタ
５０　　入力インタフェース部
６０　　出力インタフェース部
【図１】
2004015561.tif 000003
【図２】
2004015561.tif 000004
【図３】
2004015561.tif 000005
【図４】
2004015561.tif 000006
【図５】
2004015561.tif 000007
【図６】
2004015561.tif 000008
【図７】
2004015561.tif 000009
【図８】
2004015561.tif 000010
【図９】
2004015561.tif 000011
【図１０】
2004015561.tif 000012
【図１１】
2004015561.tif 000013
【図１２】
2004015561.tif 000014
【図１３】
2004015561.tif 000015
【図１４】
2004015561.tif 000016
【図１５】
2004015561.tif 000017
【図１６】
2004015561.tif 000018
【図１７】
2004015561.tif 000019
【図１８】
2004015561.tif 000020