ネットワーク装置におけるトラフィック制御及びその方法
【課題】プロセスキャッシュのパケットの到着順序に依存するヒット率の低下を防ぎ、ネットワーク装置の性能低下を防ぐ技術を提供する。
【解決手段】トラフィック管理部として、プロセスキャッシュの前段にプロセスキャッシュのタグを収めるプロセスキャッシュタグと、前記タグの各エントリに対応するＦＩＦＯキューを持つ機能ブロックを設ける。トラフィック管理部では、同一フローと判断したパケット群を到着順に同一のＦＩＦＯキューに積む。各ＦＩＦＯキューは対応するプロセスキャッシュの登録状況を記録しており、プロセスキャッシュに未登録状態のエントリのＦＩＦＯキューにパケットが到着すると、先頭のパケットのみをプロセスキャッシュミス処理を実施する機能ブロックへ渡し、プロセスキャッシュに登録されるのを待つ。以降のパケットはプロセスキャッシュへの登録が完了した時点でＦＩＦＯキューからプロセスキャッシュへのアクセスを実施する。
【解決手段】トラフィック管理部として、プロセスキャッシュの前段にプロセスキャッシュのタグを収めるプロセスキャッシュタグと、前記タグの各エントリに対応するＦＩＦＯキューを持つ機能ブロックを設ける。トラフィック管理部では、同一フローと判断したパケット群を到着順に同一のＦＩＦＯキューに積む。各ＦＩＦＯキューは対応するプロセスキャッシュの登録状況を記録しており、プロセスキャッシュに未登録状態のエントリのＦＩＦＯキューにパケットが到着すると、先頭のパケットのみをプロセスキャッシュミス処理を実施する機能ブロックへ渡し、プロセスキャッシュに登録されるのを待つ。以降のパケットはプロセスキャッシュへの登録が完了した時点でＦＩＦＯキューからプロセスキャッシュへのアクセスを実施する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大容量パケットの低遅延交換システム向けのルータやスイッチ等のネットワーク装置構成方法にかかわる技術である。特に、ネットワーク装置の構成要素として、キャッシュを利用してＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）パケットやＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）フレームの処理を実施するネットワークプロセッサやＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）のためのトラフィック制御に効果的な技術である。
【背景技術】
【０００２】
通信分野においては、複数のネットワーク間を接続するためにルータやスイッチ等のネットワーク装置が用いられる。ネットワーク装置は、レイヤ３のＩＰに基づくパケット、レイヤ２のＭＡＣに基づくフレームと呼ばれるデータを送受信することにより通信を行う。以下では、ひとつのデータ単位をパケットと呼び議論を進める。ネットワーク装置は、受信したパケットの宛先アドレスを調べてパケットの転送先を決定し、所定の転送先にパケットを転送することを繰り返し、目的の宛先へパケットを届ける。世界のネットワークで送受信されるパケットの総量は増大する一方であり、ネットワーク装置のパケット転送性能も、トラフィック量の増大に伴って向上させていく必要がある。また、パケットを単に転送するだけではなく、所定のルールを定めて該ルールに適合するものだけを転送（フィルタリング）したり、該ルールに従い単位時間あたりのパケット送出量を規定以下に制限（シェイピング）したり、該ルールに従いパケット間に優先順位を設けて転送したり、該ルールに従いパケットの情報を修正する等の処理も行う。
【０００３】
安価なネットワーク媒体としてイーサネットが利用されている。イーサネットのスピードは１９９０年代半ばまでは１０Ｍｂｐｓ（Ｍｅｇａｂｉｔ ｐｅｒ ｓｅｃｏｎｄ）から１００Ｍｂｐｓと比較的低速であったため、パケット処理は汎用プロセッサを用いたソフトウェア処理でも十分な余裕があった。しかしながら、１９９０年代後半よりイーサネットのスピードは１Ｇｂｐｓ（Ｇｉｇａｂｉｔ ｐｅｒ ｓｅｃｏｎｄ）から１０Ｇｂｐｓと高速化が進んでおり、この速度でパケット処理を実施するために、ネットワーク装置にはパケット処理専用に設計されたネットワークプロセッサやＡＳＩＣが用いられるようになっている。
【０００４】
ネットワークインタフェースの速度が上がるにつれ、パケットひとつあたりにかけられる処理時間は短くなっていく。ネットワークプロセッサでは、内部に複数のプロセッサ（パケット処理エンジン）を組み込み、パケットを並列処理することにより、パケットあたりの処理時間を確保しスループット向上を果たしている。しかしながら、ネットワークプロセッサのスループットを向上させ、より高速なネットワークインタフェースに対応させるために、ネットワークプロセッサ内部のパケット処理エンジンの数を増加させる手法は、ネットワークプロセッサの巨大化と消費電力の増加を引き起こす。
【０００５】
そこで、内部パケット処理エンジンの数を増加させる代わりに、キャッシュメモリを追加し、該パケット処理エンジン群での処理結果をプロセスキャッシュと呼ぶキャッシュに記録し、同一処理で済むパケットは前記プロセスキャッシュの内容を利用するネットワークプロセッサアーキテクチャが特願２００３−０４８７３０号公報にて提案されている。前記ネットワークプロセッサアーキテクチャ、もしくはそれに順ずるアーキテクチャを以降ではキャッシュ型パケット処理部と呼ぶ。ネットワークを流れるパケット流（トラフィック）には、同一のヘッダ情報、例えば送信元と宛先のペアが一緒といった情報を持つパケットが短時間の間に多数出現しやすい性質（時間的局所性）があるため、パケット流の混ざり合いの度合いが濃くないネットワークの末端近くのエッジ網やアクセス網、及びネットワーク中心から末端の間に位置するミドルマイル網ではキャッシュ型パケット処理部は比較的有効に働くと考えられる。
【０００６】
前記のキャッシュ型ネットワークプロセッサによりネットワーク装置を構成する場合、パケットの到着順序によってはキャッシュのヒット率が低下し、ひいてはネットワーク装置全体のスループットが低下する恐れがある。具体的には、同一のヘッダを持つパケット群が短時間に大量に到着し、最初のパケットのキャッシュ登録がそれ以降のパケットの到着に間に合わないケースである。
【０００７】
前記状況で発生する問題を解決するためには、パケットのスケジューリングが必要である。スケジューリング手法には、有用な多くの公知例が存在する。例えば、複数のセッション（フロー）をクラス毎に分類した第１レベルのスケジューリングを実施した後、それらのいくつかの出力に対し第２レベルのスケジューリングを行い、残りの第１レベルの出力と第２レベルの出力に対して優先順位付けを行う第３レベルのスケジューリングを行う方法が特表２００１−５１９１２０にて公開されている。また、優先度付きのキューと出力キューを縦列に接続し、前段の優先度キューは低優先度のパケットを滞留させマークを付け、後段の出力キューで輻輳検出を行い輻輳発生時にはマーク付けされているパケットを廃棄することにより優先度毎のトラフィック量の変動と無関係に一定の帯域を確保し、保証帯域を有効利用するスケジューリング技術が特開２００２−１８５５０１にて公開されている。
また、パケットを格納する複数本のキューを備え、各キューの先頭パケットに転送終了予定時刻の早い順に転送順序の重み付けを行い、転送帯域制御を実施するスケジューラに関して特開２０００−１０１６３７にて公開されている。ただし、事実上、比較的少数のキューしかハードウェアへの実装が困難とし、特開２００３−３２４４７１で、事実上実装可能なキューの数を増加させ、帯域制御を高精度化させるために複数個の演算器を並列且つ時分割で動作させ前記のスケジューリングを実施する手法に関して公開している。
しかしながら、いずれのスケジューリングも、本発明が解決しようとする課題、プロセスキャッシュのヒット率の低下を防ぐためのスケジューリングを実施することができない。
本願発明者が出願した特願２００３−３４６５１９では、プロセスキャッシュにミスしたパケットを処理する機能ブロックにおいて、キャッシュミスしたフローの先頭パケットのみプロセッサで処理させ、該フローの二つ目以降はキャッシュミスを扱う前記機能ブロックで保持しておく手法が開示されている。しかし、プロセスキャッシュにアクセスする以前にパケットをスケジューリングする手法に関しては言及していない。
【０００８】
【特許文献１】特願２００３−０４８７３０号
【０００９】
【特許文献２】特表２００１−５１９１２０号公報
【特許文献３】特開２０００−１０１６３７号公報
【特許文献４】特開２００２−１８５５０１号公報
【特許文献５】特開２００３−３２４４７１号公報
【特許文献６】特願２００３−３４６５１９号
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の課題は、ネットワークまたはスイッチファブリックからの入力トラフィックを管理し、パケット転送処理を高速化するためにパケット処理結果を保持するプロセスキャッシュと呼ばれるキャッシュのパケットの到着順序に依存するヒット率の低下を防ぎ、結果としてプロセスキャッシュ技術を利用したネットワーク装置の性能低下を防ぐ技術を提供することにある。
また、可能な限りプロセスキャッシュにヒットする状態を作り出すことで、プロセスキャッシュミス時に利用するパケット処理プロセッサの稼働率を低下させ、消費電力を低減することにある。
【課題を解決するための手段】
【００１１】
本発明は、ネットワークプロセッサの巨大化を避けつつ、パケット転送処理を高速化するためのプロセスキャッシュと呼ばれる技術を補助し、ネットワークトラフィックを管理することで、プロセスキャッシュのヒット率低下を防ぐための技術である。プロセスキャッシュ技術では、受信パケットに対する処理結果を記録するためのキャッシュがキャッシュ型パケット処理部に設けられる。プロセスキャッシュ技術では、パケット群を利用者が定めたルールに従い分類し、分類したパケット群の中で最初のパケットのみをキャッシュ型パケット処理部の内部に組み込むプロセッサにおいて処理する。前記処理結果をプロセスキャッシュに記録して、以後同一フローと判断するパケットにはプロセスキャッシュに記録してある結果を即座に受信パケットに適用する。この操作により、ネットワークプロセッサに内蔵された組み込みプロセッサでの処理を削減し、ネットワーク装置のパケット処理速度を向上する。
【００１２】
本発明では、ネットワークトラフィックを管理するためのトラフィック管理部として、プロセスキャッシュの前段にプロセスキャッシュのタグを収めるプロセスキャッシュタグと、前記タグの各エントリに対応するＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）キューを持つ機能ブロックを設ける。トラフィック管理部では、同一フローと判断したパケット群を到着順に同一のＦＩＦＯキューに積む。各ＦＩＦＯキューは対応するプロセスキャッシュの登録状況を記録しており、プロセスキャッシュに未登録状態のエントリのＦＩＦＯキューにパケットが到着すると、先頭のパケットのみをプロセスキャッシュミス処理を実施する機能ブロックへ渡し、プロセスキャッシュに登録されるのを待つ。二つ目以降のパケットはプロセスキャッシュへの登録が完了した時点でＦＩＦＯキューからプロセスキャッシュへのアクセスを実施する。前記操作により、フローの先頭以外のパケットのプロセスキャッシュアクセスは必ずキャッシュヒットとすることが可能となる。
【００１３】
前記の手段により、パケットの到着順序に依存するキャッシュヒット率の低下を防ぐ。尚、二つ目以降のパケットを保持している間、同一フローではないと判断したパケット群の先頭のパケットもプロセスキャッシュミス処理を実施する機能ブロックへ渡すことを可能とする。前記操作により、異なるフローに属するパケットの並列処理を実施することで組み込みプロセッサ資源の有効利用も図る。
【００１４】
本発明のパケット処理方法は、より詳細には、キャッシュメモリを用い、先行するパケットに関する処理結果をキャッシュメモリに記録し、先行するパケットと同一処理を行う後続のパケットの処理は該キャッシュメモリの内容を利用する、キャッシュ型のパケット処理方法であって、パケットを受信するステップと、受信したパケットをフロー毎に分類するステップと、フロー毎に分類したパケットを、パケットの到着順序を維持してＦＩＦＯ型のキューにフロー毎に記録するステップと、キュー内のフローの所定パケットがキャッシュに未登録である場合、所定パケットを処理して処理結果をキャッシュメモリに格納するとともに、同一キュー内の所定パケット以降のパケットは、キューに待機させておくステップと、所定パケットに関する処理結果のキャッシュメモリへの格納の完了の後に、上記キューに待機させておいたパケットの処理を行うステップと、を有する。
各フローの先頭パケットは、他のフローで待機中のパケットを追い越して処理されるようにすることで、全体のスループットを向上させることができる。
【００１５】
また、さらに、具体的には、各キューは対応するキャッシュを有しており、各キューが対応するキャッシュの登録情報を記録するステップと、キャッシュに未登録状態のキューにパケットが到着すると、先頭のパケットのみを処理し、処理結果が上記キャッシュに登録されるのを待つステップと、二つ目以降のパケットは上記キャッシュへの登録が完了した時点で処理が開始されるように構成することができる。
【００１６】
本発明のネットワーク装置は、パケットを受信する入力インタフェースと、受信したパケットを解析および分類して、種類毎にフローを生成するパケット解析部と、生成されたフローを、種類毎にパケットの受信順序を保持して管理するトラフィック管理部と、パケットを処理するパケット処理部と、パケット処理部の処理結果をフロー毎に登録するプロセスキャッシュとを有するネットワーク装置であって、該ネットワーク装置は、
(1)上記プロセスキャッシュに処理結果が未登録な第１のフローの第１のパケットを、上記パケット処理部で処理し、
(2)上記第１のフローの第１のパケットに後続するパケットは、上記第１のパケットの処理結果が上記プロセスキャッシュに登録されるまで待機させ、登録の後、上記プロセスキャッシュの情報を用いて処理を行い、
(3)上記第１のフローの第１のパケットに後続するパケットを待機させている間に、第２のフローのパケットが該待機中のパケットより先に処理されるように、
フローを制御することを特徴とする。
具体的には、トラフィック管理部は、生成されたフローに対応する内部処理情報列を、フローの種類毎にパケットの受信順序を保持して格納するキューを有し、キューに格納される内部処理情報列は、対応するパケットの処理結果がプロセスキャッシュに登録されているか否かを示す登録済み情報を含む。この登録済み情報を用いてパケットを処理部へおくる順番を制御し、フローの制御を行う。
【００１７】
パケット処理部の前段には、登録済み情報に基づいて、パケットをパケット処理部で処理するか、プロセスキャッシュを参照して処理するかを選択する解析部を有することが望ましい。
解析部の選択により、パケットがパケット処理部で処理された場合、当該処理結果がプロセスキャッシュに登録完了されたことをトラフィック管理部に通知するキャッシュミス処理部を設けることが可能である。トラフィック管理部は、キャッシュミス処理部からの通知に基づいて、内部処理情報列に登録済み情報を付加することができる。このようにすると、トラフィック管理部は、内部処理情報列に負荷された登録済み情報を参照してフローを制御することができる。
第１のフローの第１のパケットは、第１のフローの先頭パケットであってもよい。また、第２のフローのパケットは、プロセスキャッシュに処理結果が未登録な先頭パケットまたは、プロセスキャッシュに処理結果が登録済みの後続パケットであってもよい。
【発明の効果】
【００１８】
本発明のトラフィック管理部を利用すると、キャッシュ型ネットワークプロセッサなどのキャッシュを利用するパケット処理部を持つネットワーク装置において、パケットの到着順序に依存するキャッシュヒット率の低下を防ぎ、結果としてネットワーク装置のスループット低下を回避する効果がある。
また、本発明のトラフィック管理部を利用すると、前記キャッシュヒット率の低下抑止によりプロセスキャッシュミス時に利用するパケット処理を実施するプロセッサの稼働率を低下させ、消費電力を低減する効果がある。
【発明を実施するための最良の形態】
【００１９】
以下、より詳細な内容を実施例で示す。
【実施例１】
【００２０】
図１には、本実施例におけるネットワーク装置の構成例を示す。
本実施例では、ネットワーク装置は、ネットワークからパケットを送受信するためのネットワークインタフェース部１０１、ネットワークトラフィックを制御するためのキャッシュ用トラフィック制御部１０２、キャッシュ型パケット処理部１０３、前記１０１、１０２、１０３を含むネットワークインタフェースカード１０、複数のネットワークインタフェースカード１０を結合しパケットを交換するスイッチファブリック１１等で構成される。この他に複数のネットワークインタフェースカード１０の間の経路情報等の集中管理を行うホストプロセッサやホストプロセッサへのインタフェース等もある。
【００２１】
本実施例におけるパケット処理動作と効果に関して、まず全体の概要を説明する。ネットワークインタフェース部１０１よりパケットを受信し、キャッシュ用トラフィック制御部１０２が、パケットをフローと呼ぶグループに分類し、パケットの到着順序を維持するためにＦＩＦＯ型のキューにフロー毎記録する。そして、まず、キャッシュ型パケット処理部１０３のキャッシュに未登録である各フローの先頭パケットのみをキャッシュ型パケット処理部１０３へ渡し、各フローの二つ目以降のパケットは、ＦＩＦＯ型のキューに保持しておく。各フローの先頭パケットは、他のフローの二つ目以降のパケットを追い越して、キャッシュ型パケット処理部１０３へ渡すことを可能とする。前記二つ目以降のパケットは、キャッシュ型パケット処理部１０３においてキャッシュ登録完了通知を受けてからキャッシュ型パケット処理部１０３へ渡す。
前記動作により、キャッシュ型パケット処理部１０３では、フローの先頭のパケット以外は全てキャッシュヒットさせることができる。即ち、パケットの到着順序に依存するキャッシュヒット率の低下を防ぎ、結果としてネットワーク装置のスループット低下を回避する効果がある。
【００２２】
キャッシュ型パケット処理部１０３は、一つ以上のプロセッサと、前記プロセッサでのプログラム処理結果を格納するためのプロセスキャッシュと呼ぶキャッシュメモリを持つ。前記フローの先頭のパケットはプロセッサを利用して、パケットの宛先情報を得るために経路検索を実施し、必要であればその他の操作、例えばパケットを通過させるか否かを決定するためのフィルタリング情報取得や、ＭＰＬＳ（Ｍｕｌｔｉｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）やＶＬＡＮ（Ｖｉｒｔｕａｌ Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）等のヘッダ情報の取得等を実施する。前記実施の結果を専用ハードウェア、もしくは簡易プロセッサでビット列操作だけでパケットに適用できる情報列にしてプロセスキャッシュへ登録し、後段の処理を実施する部分へパケットを渡す。前記フローの二つ目以降のパケットは、プロセスキャッシュにヒットするため、プロセスキャッシュの内容を利用してプロセッサでの処理をバイパスし、後段の処理を実施する部分へパケットを渡す。前記後段の部分は、専用のビット列操作用のハードウェア等によりパケットに必要な処理を施しパケットをスイッチファブリック１１へ渡し、当該パケットに対する処理を終了する。一般にプロセッサの稼働率が高くなるほど、消費電力は上昇する。キャッシュ型パケット処理部１０３はパケット処理のために一つ以上のプロセッサを含むが、前記プロセッサは前記プロセスキャッシュにミスする先頭のパケットのみを処理すれば良いため、本発明によるキャッシヒット率の低下抑止により消費電力を低減することが可能となる。本発明のキャッシュ用トラフィック制御部１０２の分の消費電力は増加するが、以降に述べるトラフィックマネージャの替わりに用いることを考慮すると、キャッシュ用トラフィック制御部１０２の分の消費電力はトラフィックマネージャ相当と見做し、無視することができる。
【００２３】
スイッチファブリック１１は、各ネットワークインタフェースカード１０から受信したパケットを指定された宛先のネットワークインタフェースカード１０に向けて送信する。スイッチファブリック側からネットワークインタフェースカード１０へ渡されるパケットは、キャッシュ用トラフィック制御部１０２、キャッシュ型パケット処理部１０３を同様に通過してネットワークへ送信される。
【００２４】
本発明によるキャッシュ用トラフィック制御部１０２は、ネットワークトラフィックの管理を行う点で従来のネットワーク装置で利用されるトラフィックマネージャと呼ばれるデバイスに類似するが、実施する制御で決定的に異なる点を持つ。
まず、トラフィックマネージャについて説明する。トラフィックマネージャとは、規定帯域以上の入力がないか監視し、規定帯域以上の場合には入力を廃棄するポリシングや、規定帯域以上の出力を規定以下に制限するためのシェイピング、フローの順序を優先順位に応じて調整するスケジューリング等を実施するデバイスである。トラフィックマネージャを利用したネットワーク装置は、例えば図２に示すように、ネットワークからパケットを送受信するためのネットワークインタフェース部１０１、パケット処理部としてのネットワークプロセッサ（もしくはそれに順ずるＡＳＩＣ）１１０、トラフィック制御部としてのトラフィックマネージャ（もしくはそれに順ずるＡＳＩＣ）１１１、前記１０１、１１０、１１１を含むネットワークインタフェースカード１０、複数のネットワークインタフェースカード１０を結合しパケットを交換するスイッチファブリック１１等で構成される。この他に複数のネットワークインタフェースカード１０の間の経路情報等の集中管理を行うホストプロセッサやホストプロセッサへのインタフェース等もある。
【００２５】
次に、本発明のキャッシュ用トラフィック制御部１０２が従来のトラフィックマネージャと決定的に異なる点について説明する。キャッシュ用トラフィック制御部１０２は、フローの先頭以外のパケットがプロセスキャッシュにヒットするアクセスになるように入力トラフィックを制御する点で、従来のトラフィックマネージャと異なる。また、ネットワーク装置構成時のネットワーク入力からスイッチファブリックへ向かう側での設置位置が異なる。通常、トラフィックマネージャは、ネットワークプロセッサやＡＳＩＣ等のパケット処理部の後段に設置されるが、本発明によるキャッシュ用トラフィック制御部は、キャッシュ型ネットワークプロセッサやＡＳＩＣ等の前段に設置する。本実施例では、ネットワークからの入力側で、キャッシュ用トラフィック制御部１０２がパケット処理部である１０３より前段にある。これは、パケット流の制御をキャッシュアクセスより前に行うためである。
【００２６】
次に、キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３の内部構成例の詳細を図３に示し、パケット処理動作について説明する。キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３は、同一チップ上に集積できるならば、単一のチップとして実装しても良いし、それぞれを別のチップとして実装しても良い。図３では、キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３が別々のチップに実装するケースを想定している。
キャッシュ用トラフィック制御部１０２は、一実施例として、入力インタフェース２０１、パケット解析部２０２、トラフィック管理部２０３、出力データ生成部２０４、出力インタフェース２０５、プロセスキャッシュ登録信号２０８、パケットメモリ２１０より構成される。前記のキャッシュ用トラフィック制御部１０２の構成要素は、低レイテンシかつ高速なパケット処理を実現するには単一のチップ上に実装するのが望ましい。パケットメモリ２１０についても、例えば、混載ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）技術や１Ｔ−ＳＲＡＭ（１Ｔｒａｎｓｉｓｔｏｒ Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）技術等の高密度実装可能な高速オンチップメモリを利用してキャッシュ用トラフィック制御部１０２の他の構成要素と同一チップ上に実装するのが望ましいが、パケットメモリ２１０の一部もしくは全てをチップ外部に実装する選択肢もある。
【００２７】
キャッシュ用トラフィック制御部１０２は、パケットを入力インタフェース２０１により受信後、パケット解析部２０２によりパケットの解析を行い、内部処理専用の情報列を生成する。ここでは、前記内部処理専用情報列をトークンと呼ぶ。元のパケットは、パケットメモリ２１０に格納する。図４に前記トークン４００の構成を示す。前記トークン４００は、固有情報４０１、解析情報４０２、抽出情報４０３により構成する。
固有情報４０１は、各トークンを区別するために用いるパケット毎の固有の情報である。例えば、パケットメモリ２１０へのパケット格納アドレスが挙げられ、パケット格納アドレスにより各トークンを区別可能になる。また、パケット処理に利用するために、実装によっては、パケットのサイズ、パケットのフラグメント情報、パケットを解析した結果判明したエラー情報、ＴＣＰの制御情報等を含めてもよい。例えば、パケットサイズは、複数のフローがキャッシュ用トラフィック制御部１０２から発行可能になった時に、後述するＱｏＳ（Ｑｕａｒｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）制御の一環としてパケットサイズを利用しながら出力するフローを選択するのに利用できる。また、ＴＣＰの制御ビットでは、例えばＦＩＮ及びＲＳＴビットを利用しフローの最終パケットのトークンであることを示し、当該トークン通過後、対応するプロセスキャッシュのエントリ、ＦＩＦＯキューのエントリをクリアするのに利用できる。
【００２８】
解析情報４０２は、パケットの各ネットワークレイヤで利用されているプロトコルや転送に関する情報である。レイヤ２、レイヤ３、レイヤ４、レイヤ５〜７における利用プロトコル（例えば、レイヤ２でＭＰＬＳを利用、ＶＬＡＮを利用、レイヤ３でＩＰｖ４を利用、ＩＰｖ６を利用、レイヤ４でＴＣＰを利用、レイヤ７でＨＴＴＰを利用等）や、レイヤ２におけるパケット転送情報（ユニキャスト、ブロードキャスト、または、マルチキャスト）を示す。利用プロトコル種の解析情報４０２中での表記形式は、実際のパケットのヘッダに含まれる形式（例えば、レイヤ２のタイプフィールドそのもの）でも良いし、必要と判断した数種類（例えば16種類程度）に限定し、それをエンコードした形式（例えば16種類なら4ビットにエンコードが可能）でも良い。どのレイヤまで解析するかは、解析情報４０２を生成するためにパケット解析部２０２が持つ命令メモリに格納するプログラムにより規定することを可能とする。このため、利用形態によりレイヤ２スイッチ用、レイヤ３スイッチ用、レイヤ４スイッチ用、レイヤ７スイッチ用等への柔軟な対応が可能である。
【００２９】
抽出情報４０３は、パケットから抽出したヘッダ情報の一部である。例えば、レイヤ３の抽出情報としてＩＰｖ４の宛先ＩＰアドレスと送信元ＩＰアドレスを抽出することができる。また別の例では、前記のレイヤ３抽出情報に加えレイヤ４のＴＣＰ宛先ポート番号とＴＣＰ送信元ポート番号を抽出できる。抽出内容は、解析情報４０２と同様に、パケット解析部２０２が持つ命令メモリに格納するプログラムを書き換えることにより変更可能である。
【００３０】
ある二つのパケットが同一フローに属するか、異なるフローに属するかを判断するために、トークン４００の解析情報４０２と抽出情報４０３を利用する。ある二つのパケットを比較したとき、それぞれの解析情報４０２および抽出情報４０３の組が同一であれば、二つのパケットは同一フローに属すとみなすことができる。一方で、ある二つのパケットを比較したとき、それぞれの解析情報４０２および抽出情報４０３の組が異なれば、二つのパケットは異なるフローに属すとみなすことができる。
【００３１】
パケット解析部２０２により生成したトークン４００は、フロー毎に分類可能な状態にあるため、トラフィック管理部２０３において分類及び管理を行う。トラフィック管理部２０３の内部構成例を図５に示す。トラフィック管理部２０３は、ハッシュ部５０１、タグ部５０２、ＦＩＦＯキュー５０５、比較器５０３、書込制御部５０４、読出制御部５０６、待機バッファ５０７により構成される。
【００３２】
トラフィック管理部２０３は、フローの二つ目以降のパケットがプロセスキャッシュにミスしないようにするために、プロセスキャッシュの状態、即ち当該トークンがプロセスキャッシュに登録されている状態（ヒット状態）か、登録されていない状態（ミス状態）か知る必要がある。そこで、プロセスキャッシュの状態を知るために、トラフィック管理部２０３は、プロセスキャッシュのタグに相当するタグ部５０２を具備している。タグ部５０２は、トークンの解析情報４０２と抽出情報４０３を保持する。タグを参照するためのアクセスキーは、ハッシュ部５０１を利用してトークンの解析情報４０２と抽出情報４０３全体に対してハッシュをかけて生成する。ハッシュ部５０１は、キャッシュ型パケット処理部１０３のプロセスキャッシュ３０３の具備するハッシュ部５１１と同一のアルゴリズムを利用する。ハッシュには様々な手法があるが、例えばＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ）演算等の攪拌能力に優れたものを利用する方法が、キャッシュのエントリ競合を起こしにくくなりヒット率向上に繋がるため望ましい。比較器５０３を利用してタグ５０２を参照後に出力されるタグ内容と、アクセスを行ったトークンの解析情報４０２と抽出情報４０３を比較することにより、当該トークンがプロセスキャッシュにヒットするか否かを判断可能である。
【００３３】
トラフィック管理部２０３は、キャッシュ型パケット処理部１０３へのパケットフローを制御するために、トークンをフローごとに到着順に管理するＦＩＦＯキュー５０５をタグ５０２のエントリ毎に具備している。タグ５０２への登録形式の例を図４の４２０に、ＦＩＦＯキュー５０５への登録例を図４の４３０に示す。
【００３４】
タグ登録情報４２０は、エントリが利用されていることを示す有効ビット４２１、トークンの解析情報４０２、抽出情報４０３をプロセスキャッシュのタグ相当の情報として持つ。また、タグ５０２及びＦＩＦＯキュー５０５への読書き制御のために、対応するＦＩＦＯキュー５０５のエントリのトークンが入っていないことを示すＦＩＦＯキューエンプティビット４２２、プロセスキャッシュに現在登録要求を出していることを示すプロセスキャッシュ登録中ビット４２４、プロセスキャッシュに登録が完了したことを示すプロセスキャッシュ登録済みビット４２３を持つ。また、フロー毎にＱｏＳ制御を実施する場合には、当該フローの優先順位を示す優先順位情報４２５、当該フローに許される利用帯域幅を示す帯域情報４２６を持つ。
【００３５】
ＦＩＦＯキュー登録情報４３０は、エントリが利用されていることを示す有効ビット４３１とトークンの固有情報４０１等により構成される。
ＦＩＦＯキュー５０５は、プロセスキャッシュのエントリ数Ｋと同じだけの本数を具備する。例えば、４０００エントリのプロセスキャッシュを利用する場合、４０００本のＦＩＦＯキューを具備する。各ＦＩＦＯキュー５０５は独立したメモリで実現してもよいし、複数本または全体をひとまとめにしたメモリで実現してもよい。
まず、タグ５０２及びＦＩＦＯキュー５０５への書込み制御に関して説明する。トークンは、前記の方法でハッシュ部５０１によりタグ５０２を参照し、プロセスキャッシュのヒット判定を行い書き込み制御部５０４へ通知する。ヒットしていれば、書込み制御部５０４は、対応するＦＩＦＯキューにトークンの固有情報４０１を書き込み、ＦＩＦＯキューエンプティビット４２２を空ではないことを示す値（例えば０）にする。
プロセスキャッシュにミスしていれば、当該トークンの解析情報４０２と抽出情報４０３を対応するエントリのタグ５０２へ、当該トークンの固有情報４０１を対応するＦＩＦＯキュー５０５に登録する。また、プロセスキャッシュ登録中ビット４２４に登録中を示す値（例えば１）をセットする。
【００３６】
次に、タグ５０２及びＦＩＦＯキュー５０５への読出し制御に関して説明する。読出し制御部５０６は、タグ５０２の各ＦＩＦＯキューのプロセスキャッシュ登録済みビット４２３とプロセスキャッシュ登録中ビット４２４及び、ＦＩＦＯキューエンプティビット４２２を監視する。ＦＩＦＯキュー５０５から読み出しが行われるのは、次の二つの場合がある。
（１）フローの先頭、即ちプロセスキャッシュに未登録のパケットである場合。この場合、プロセスキャッシュ登録済みビット４２３は未登録を示す値（例えば０）、プロセスキャッシュ登録中ビット４２４は登録中で無いことを示す値（例えば０）、ＦＩＦＯキューエンプティビット４２２は空ではない値（例えば０）を示している。
（２）フローの二つ目以降、即ちプロセスキャッシュに登録済みのパケットである場合。この場合、プロセスキャッシュ登録済みビット４２３は登録済を示す値（例えば１）、プロセスキャッシュ登録中ビット４２４の値は無視し、ＦＩＦＯキューエンプティビット４２２は空ではない値（例えば０）を示している。
前記（１）、（２）いずれかの状況になったエントリがあれば、対応するＦＩＦＯキュー５０５に登録されている固有情報４０１と、タグ５０２の解析情報４０２、抽出情報４０３を読出して結合してトークンに戻し、登録ＦＩＦＯキュー番号４５１（タグ５０２のエントリ番号にも対応している）と一緒に出力データ生成部２０４へ渡す。尚、あるフローの（２）の状態のパケットを、異なるフローの（１）もしくは（２）の状態のパケットは追い越しを行うことができる。基本的には、（１）の状態のエントリのトークンを優先的に出力データ生成部２０４へ渡すことで、プロセスキャッシュになるべく早期にエントリ登録を実現する。
尚、ＦＩＦＯキュー５０５は、メモリ容量が許すのであれば固有情報４０１だけでなく解析情報４０２と抽出情報４０３を記録しておいてもよい。また、読出しを行ったＦＩＦＯキュー５０５が空になる場合、対応するＦＩＦＯキュー情報４３０を消し、タグ登録情報４２０のＦＩＦＯキューエンプティビット４２２に空を示す値（例えば1）を設定する。
【００３７】
図５の複数のＦＩＦＯキュー５０５にトークンが溜まり、複数のＦＩＦＯキュー５０５からトークン送信可能な状況について説明する。前記状況が発生した時、プロセスキャッシュ登録済みビット４２３が登録済みを示す値（例えば１）になった順に該当するＦＩＦＯキュー５０５からトークンを取り出すＦＩＦＯ出力方式や、取り出し順番をトークン毎もしくは複数のトークン毎に順番に変えていくＲＲ（Ｒｏｕｎｄ Ｒｏｂｉｎ）方式が簡易であるが、タグ登録情報４２０の優先順位情報４２５を利用し、従来から用いられる様々な出力方式をとることで優先度の高いフロー及び優先度の低いフローの間でサービスに差をつけることが可能となる。例えば、優先順位情報４２５にＫ種類（例えば、Ｈｉｇｈ・Ｍｉｄｄｌｅ・Ｎｏｒｍａｌ・Ｌｏｗの4種類）の優先順位情報を加えることでＰＱ（Ｐｒｉｏｒｉｔｙ Ｑｕｅｕｉｎｇ）が実現できる。取り出し時にトークンの元となるパケットサイズをトークンの固有情報４０１から判定し、例えば閾値として設定するサイクルの中で出力候補となったＦＩＦＯキュー５０５からの出力パケットサイズの和が公平となるように重み付けを行うＷＦＱ（Ｗｅｉｇｈｔｅｄ Ｆａｉｒ Ｑｕｅｕｉｎｇ）方式等を適用することが可能である。
【００３８】
同様に、図４タグ登録情報４２０の帯域情報４２６とトークンの固有情報４０１に含まれるパケットサイズを利用し、送信可能なＦＩＦＯキューから、設定された帯域までの間でＦＩＦＯキュー５０５から送信を行うことが可能である。例えば、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）におけるＣＢＲ（Ｃｏｎｓｔａｎｔ Ｂｉｔ Ｒａｔｅ）サービスクラスに対応するためには、当該ＦＩＦＯキュー５０５が出力可能になったときに、帯域情報４２６で指定された値に相当する期間だけ、当該ＦＩＦＯキュー５０５にキャッシュ型パケット処理部１０３への出力パスを占有させ、期間終了後に次のＦＩＦＯキュー５０５へ前記出力パスを渡す。また、ＡＴＭにおけるｒｔ−ＶＢＲ（Ｒｅａｌ Ｔｉｍｅ Ｖａｒｉａｂｌｅ Ｂｉｔ Ｒａｔｅ）サービスクラスに対応するためには、当該ＦＩＦＯキュー５０５が出力可能になったときに、帯域情報４２６で指定された値に相当する期間が終了しても当該ＦＩＦＯキュー５０５にトークンがあれば、続けてキャッシュ型パケット処理部１０３への出力パスを占有させる。また、ＡＴＭにおけるｎｒｔ−ＶＢＲ（Ｎｏｎ Ｒｅａｌ Ｔｉｍｅ Ｖａｒｉａｂｌｅ Ｂｉｔ Ｒａｔｅ）サービスクラスに対応するためには、当該ＦＩＦＯキュー５０５が出力可能になったときに、帯域情報４２６で指定された値に相当する期間が終了しても当該ＦＩＦＯキュー５０５にトークンがあれば、帯域情報４２６に追加で指定される値までの追加期間分、前記ＦＩＦＯキュー５０５からの出力を可能とする。その他のサービスクラスにも対応可能である。
【００３９】
図５のハッシュ部５０１は、無数にあるパケットフローをプロセスキャッシュのエントリ数まで縮約するため、トークンにハッシュをかけた結果、異なるフローが同一のプロセスキャッシュのエントリに割り当てられる状況が発生する。図５の構成は、ハッシュして得られた値によるタグ５０２の割り当て位置が一意に決まるダイレクトマップ方式の構成である。ダイレクトマップ方式は実装が容易であり、データの読出しに不要な選択論理が入らないため高速であるメリットがあるが、異なるフローに属するトークンが同一エントリに割り当てられる状況が発生しやすくキャッシュのヒット率の向上の点からは不利である。
そこで、同一エントリの割り当てが発生してもキャッシュヒットにできるように、タグ及びＦＩＦＯキュー部分をＮ個持たせる（Ｎウェイ・）セット・アソシアティブ方式をとることも可能である。（Ｎウェイ・）セット・アソシアティブ方式では、図１１に示すように、ハッシュして得られた値による割り当て位置をＮ個まで増加させることができる。（Ｎウェイ・）セット・アソシアティブ方式のタグ及びＦＩＦＯキューを用いた場合、トークンにハッシュをかけた結果、未登録のウェイがあれば、前記未登録ウェイへトークンを登録する。Ｎ箇所全ての割り当て箇所が既登録であれば、任意のウェイを選択して上書きする。尚、キャッシュに登録されている情報が可能な限り有効に利用されるよう、前記任意ウェイを選択するためには、通常のプロセッサで利用されるキャッシュ同様、最も利用されていないエントリを選択するＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）アルゴリズムや一番古いエントリを選択するためのＦＩＦＯ(Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ)アルゴリズム等を実装する。ＬＲＵアルゴリズムを正確に実装するためには一エントリあたりＮ！（Ｎの階乗）ビット、ＦＩＦＯアルゴリズムを正確に実装するためには一エントリあたりＬｏｇ２Ｎビットの情報が必要になる。
【００４０】
ダイレクトマップ方式でも、（Ｎウェイ・）セット・アソシアティブ方式の場合でも、異なるフローが同一エントリを要求し、尚且つ対応するエントリが全て利用中であるケースが発生する。前記状況が発生した場合、当該エントリのタグ登録情報４２０のＦＩＦＯキューエンプティビット４２２、プロセスキャッシュ登録済みビット４２３、プロセスキャッシュ登録中ビット４２４を利用してトークンの登録を制御する。
当該エントリを後発のトークンにより上書きしても構わないのは、第一の場合として、タグ５０２の対応するエントリが空いている場合である。第二の場合として、タグ５０２の対応するエントリにフローが登録されているが、対応するＦＩＦＯキューに処理すべきトークンが全く無い場合である。即ち、第一の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録済みビット４２３が未登録を示す値（例えば０）であり、尚且つプロセスキャッシュ登録中ビット４２４が登録中でないことを示す値（例えば０）である場合」である。また、第二の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録済みビット４２３が登録済みを示す値（例えば１）であり、尚且つ、ＦＩＦＯキューエンプティビット４２２が、ＦＩＦＯキューが空であることを示す値（例えば１）の場合」である。
【００４１】
当該エントリを後発のトークンにより上書きしてはならないのは、第一の場合として、タグ５０２の対応するエントリにフローが登録されており、尚且つ対応するＦＩＦＯキューに処理すべきトークンが溜まっている状態である。第二の場合として、タグ５０２の対応するエントリにフローの先頭のパケットのみが登録されており、前記先頭のパケットの処理をキャッシュ型パケット処理部１０３に要求している状態である。即ち、第一の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録済みビット４２３が登録済みを示す値（例えば１）であり、尚且つ、ＦＩＦＯキューエンプティビット４２２が、ＦＩＦＯキューが空でないことを示す値（例えば０）の場合」である。また、第二の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録中ビット４２４が登録中を示す値（例えば１）の場合」である。
【００４２】
当該エントリのタグ５０２が利用中で上書きできない場合、上書きできなかったトークン以降のタグ５０２で競合を起こすトークンだけを登録する。登録する内容は図４の４４０に示すように、トークンの固有情報４０１、解析情報４０２、抽出情報４０３とエントリが有効であることを示す有効ビット４４１である。この方法は、上書きできる別のフローのトークンのタグ５０２へのアクセスを停止させないため、トークンの処理効率が低下しないことを期待できる。尚、待機バッファ５０７は、競合を起こしたエントリを監視し、上書きできる状態になったらパケット解析部２０２からタグ５０２へのトークン供給を停止させ、待機バッファ５０７から優先して先頭のトークンをタグ５０２へアクセスさせる。
【００４３】
前記の待機バッファ５０７の実装が困難な場合、トークンの処理効率は低下するが、別の実施例として、上書きできなかったトークン及び、それ以降のトークンは全て待機バッファ５０７に登録する方法がある。待機バッファ５０７は、競合を起こしたエントリを監視し、上書きできる状態になったらパケット解析２０２からのトークン供給を停止し、待機バッファ５０７から優先して先頭のトークンをタグ５０２参照に利用する。
【００４４】
トークンを受け取った出力データ生成部２０４は、受信したトークン４００に、登録ＦＩＦＯキュー番号４５１、プロセスキャッシュに登録が完了したことを示すプロセスキャッシュ登録済みビット４２３、後述のプロセスキャッシュをセット・アソシアティブ方式にする場合のウェイ番号の情報４５３、前記トークンに対応する元のパケット４５４を付加して図４の４５０の形式にして出力インタフェース２０５に渡し、キャッシュ型パケット処理部１０３へ送信する。プロセスキャッシュ登録済みビット４２３は、プロセスキャッシュにフローが未登録の状態であれば、キャッシュ未登録状態を示す値（例えば０）を、フローが既に登録されていれば、キャッシュ登録済み状態を示す値（例えば１）が書き込まれている。
【００４５】
以後、キャッシュ用トラフィック制御部１０２は、当該トークンのプロセスキャッシュ登録完了通知を待機する。前記待機状態時にも、異なるフローの先頭トークンや、プロセスキャッシュに登録済みのトークンはキャッシュ用トラフィック制御部１０２からキャッシュ型パケット処理部１０３へ送信される。登録完了通知は信号２０８により行い、プロセスキャッシュ登録が完了していれば、対応するタグ５０２のエントリのプロセスキャッシュ登録中ビット４２４を登録中ではないことを示す値（例えば０）に設定し、プロセスキャッシュ登録済みビット４２３を登録が完了したことを示す値（例えば１）に設定し、当該ＦＩＦＯキューの二つ目以降のトークンを発行可能にする。また、プロセスキャッシュ登録がなんらかの理由によりできなかった場合、前記プロセスキャッシュ登録済みビット４２３は登録がされていない状態のまま（例えば０）であり、当該ＦＩＦＯキューの二つ目のトークンが再び先頭のトークンと同様に扱われる。
【００４６】
次に図３のキャッシュ型パケット処理部１０３の実施例について、構成とパケット処理動作について説明する。キャッシュ型パケット処理部１０３は、一実施例として、入力インタフェース３０１、解析部３０２、プロセスキャッシュ３０３、キャッシュミス処理部３０４、パケット処理部３０５、後処理部３０６、出力インタフェース３０７、パケットメモリ３１０、テーブルメモリ３２０から構成される。前記のキャッシュ型パケット処理部１０３の構成要素は、低レイテンシかつ高速なパケット処理を実現するには単一のチップ上に実装するのが望ましい。パケットメモリ３１０とテーブルメモリ３２０についても、例えば、混載ＤＲＡＭ技術や１Ｔ−ＳＲＡＭ技術等の高密度実装可能な高速オンチップメモリを利用してキャッシュ型パケット処理部１０３の他の構成要素と同一チップ上に実装するのが望ましいが、パケットメモリ３１０とテーブルメモリ３２０の一部もしくは全てをチップ外部に実装する選択肢もある。
【００４７】
入力インタフェース３０１は、図４の４５０の形式でトークンとパケットを受信する。次に解析部３０２を利用し、受信したトークン及びパケット４５０のプロセスキャッシュ登録済みビット４２３を参照し、前記ビット４２３が登録済みを示す値（例えば１）であれば、プロセスキャッシュにトークン及びパケットを渡す。前記プロセスキャッシュ登録済みビット４２３が未登録を示す値（例えば０）であれば、キャッシュミス処理部へトークンとパケットを渡す。
まず、キャッシュ登録済みのトークンの処理に関して説明する。キャッシュ登録済みのトークンは、パケット処理部３０５で処理する必要が無いため、プロセスキャッシュ３０３に渡される。プロセスキャッシュ３０３は一実施例として図７に示すように、ハッシュ部５１１、プロセスキャッシュデータ部５１２、結合部５１３により構成される。本実施例では、プロセスキャッシュのタグ部分はキャッシュ用トラフィック制御部１０２に配置するため、キャッシュ型パケット処理部１０３のプロセスキャッシュ３０３はデータ部分のみを持つだけでよい。ハッシュ部５１１は、キャッシュ用トラフィック制御部１０２のタグ５０２へのトークン振分を行うハッシュ部５０１と同一のハッシュを利用する。プロセスキャッシュデータ部５１２には、プロセッサで処理後のパケット抽出情報α４１１と処理情報４１２により構成される置換トークン情報（図４の４７０）が格納される。
【００４８】
抽出情報α４１１は、パケットが利用するアドレスの書換えや新規追加ヘッダ等の情報であり、元の抽出情報４０３を上書きする形で生成される。変更が無ければ抽出情報４０３のままである。尚、新規追加ヘッダには、例えば、ＭＰＬＳのシムヘッダ、ＶＬＡＮのヘッダ、ＩＰｖ４やＩＰｖ６等のカプセリング用のヘッダ等がある。
処理情報４１２は、トークン４１０を元のパケットに対してどのように適用するかを示す情報である。例えば、抽出情報α４１１に入っている情報のサイズと前記情報をパケットのどの位置にどのように、即ち挿入するのか置換するのか、または削除するのかを示し、またパケットの廃棄指示を出したり、アドレス変換操作を支持したり、ＱｏＳ情報やスイッチファブリック１１やネットワークインタフェース１０１の出力ポートを指定したりするのに利用する。
プロセスキャッシュデータ５１２を参照するトークンは既にヒットすることが判明している状態であり、本参照により得た置換トークン情報４７０と、参照に利用したトークンの固有情報４０１、解析情報４０２により、パケット処理用トークン（図４の４１０）を結合器５１３により生成し、後処理部３０６へ渡す。
【００４９】
図７のプロセスキャッシュはダイレクトマップ方式であるが、キャッシュ用トラフィック制御部１０２のトラフィック管理部２０３が（Ｎウェイ・）セット・アソシアティブ方式を採用する場合には、図８に示すようにキャッシュ方パケット処理部のプロセスキャッシュのデータ部３０３も（Ｎウェイ・）セット・アソシアティブ構成をとる。
【００５０】
次に、キャッシュ未登録のトークンの処理に関して説明する。キャッシュ未登録のトークンは、パケット処理部３０５で必要な処理を実施する必要がある。このため、キャッシュミス処理部３０４に渡される。キャッシュミス処理部３０４は一実施例として図９に示すように、キャッシュミス管理テーブル７０１、処理情報管理テーブル７０３、結合器７０４で構成される。初期ミステーブル７０１は、受信したトークンの固有情報４０１、解析情報４０２、抽出情報４０３、登録ＦＩＦＯキュー番号４５１、キャッシュウェイ情報４５３を記録し、パケット処理部３０５へ、前記トークンとそれに付随するパケットを渡す。
【００５１】
パケット処理部３０５は、必要であれば、受信したトークン及びパケットをパケットメモリ３１０へ記録する。パケット処理部３０５の構成方法には様々な手法があるが、代表的なものとして、複数のプロセッサを集積しており、トークン及びパケットを次々に受信しても、複数のプロセッサで並列処理することにより高いスループットを維持することが可能である。パケット処理部３０５が実施する処理は、比較的レイテンシの長いメモリ参照を伴うものである。具体的には、テーブルメモリ３２０に格納される変換テーブルを参照して当該パケットの転送先を決定するための経路検索や、パケットを通過させるか否か決定するためのフィルタリング処理、転送先のネットワーク装置が処理可能なパケットフォーマットに変換するためのカプセリング処理、ＭＰＬＳのヘッダ追加・置換・削除処理、ＶＬＡＮ用ヘッダ追加・置換・削除処理、アドレス変換処理等である。メモリ参照の結果が返ってくるまでプロセッサの演算器は利用されない状態であり、プロセッサの利用効率は低下しがちである。そこで、プロセッサをマルチスレッド化して複数のアーキテクチャレジスタを具備させ、あるパケットを処理するスレッドがメモリ参照にいったら、別のパケットを処理するスレッドに切替え、演算器が有効利用可能な手法も可能である。いずれにしても、パケットに対して必要な処理を終了すると、その結果をトークンの抽出情報α４１１と処理情報４１２として生成し、キャッシュミス処理部３０４へ返す。
尚、パケット処理部で扱うには処理時間があまりに長すぎる、複雑すぎる、またはネットワーク装置の転送系ではなく制御系の処理であると判断される処理は、外部に設置するホストプロセッサ等へ要求をあげることができる。例えば、経路情報を更新・維持するためのＲＩＰ(Ｒｏｕｔｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｔｏｃｏｌ)やＯＳＰＦ(Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ)等のプロトコル処理等があげられる。
【００５２】
キャッシュミス処理部３０４は、パケット処理部３０５から処理済のトークン４７０を受信すると、処理情報テーブル７０３に登録する。そして、キャッシュミス管理テーブル７０１から、対応するトークンの登録ＦＩＦＯキュー番号４５１、キャッシュウェイ情報４５３を読出し、対応するプロセスキャッシュデータのエントリを決定し、処理情報テーブル７０３の抽出情報α４１１と処理情報４１２をプロセスキャッシュデータ５１２へ登録する。また、プロセスキャッシュに当該トークンの登録が完了したことをキャッシュ用トラフィック制御部１０２へ通知するための情報として信号２０８により、登録ＦＩＦＯキュー番号４５１とキャッシュ可能ビット４６１、更に、オプションとして当該フローの優先順位を示す優先順位情報４２５、当該フローに許される利用帯域幅を示す帯域情報４２６により構成されるデータ（図４の４６０）を信号２０８によりキャッシュ用トラフィック制御部１０２へ渡す。ここで、キャッシュ可能ビット４６１は、パケット処理部で処理した結果、プロセスキャッシュに登録可能なトークンであったことを示す場合（例えば１）と何らかの理由により登録できないトークンであったことを示す場合（例えば０）で値が異なる。通常は、プロセスキャッシュに登録可能であることを想定しているが、元のパケットに対してハードウェアで対応困難な、複雑なソフトウェア処理を施す必要ある場合等にはプロセスキャッシュには登録せず、全てパケット処理部で処理する。
また、パケット処理部で処理したトークンは、キャッシュミス管理テーブル７０１から、対応するトークンの固有情報４０１及び解析情報４０２、処理情報テーブル７０３から抽出情報α４１１と処理情報４１２を読出し、結合器７０４にて結合して後処理部３０６へ渡す。
【００５３】
以上のように、後処理部３０６は、プロセスキャッシュ３０３もしくはキャッシュミス処理部３０４から処理済トークン４１０を受信する。両方から同時に処理済トークン４１０を受信する場合は、同一フローの中でのパケットの順番を変えないためにキャッシュミス処理部３０４からの受信を優先する。
後処理部３０６は、受信したトークンの解析情報４０２、処理情報４１２を参照し、当該トークンを生成する元になったパケット４５４に対して必要な処理を実施する。パケットに対して新規に追加するヘッダ、もしくはヘッダの中に置換すべき情報がある場合、当該トークンの抽出情報α４１１に対応する情報があるため、解析情報４０２及び処理情報４１２にある情報を元にパケットヘッダの修正を実施する。
【００５４】
最後に、出力インタフェース部３０７において、パケットを送出できる形式に変換して出力する。このときネットワークプロセッサアクセラレータの先にスイッチファブリックが繋がっているならば、スイッチファブリック用のヘッダ情報をパケットに付加する。例えば、スイッチファブリックのポート番号等が含まれるが、これは、トークンの中の抽出情報α４１１、または処理情報４１２に含まれているので、それを利用すればよい。ネットワークインタフェースが繋がっているならば、そのネットワークインタフェースがサポートするレイヤ２、もしくはレイヤ３の形式にパケットを変換して出力する。尚、出力先ネットワークインタフェースが
複数の出口を持つ場合には、やはりトークンに含まれているポート番号を利用して出口のネットワークインタフェースを決定する。
【００５５】
以上、キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３を別チップに実装する例を示したが、両部分を図１０に示すように単一のチップ上に実装してもよい。この場合、キャッシュ用トラフィック制御部とキャッシュ型パケット処理部の間に専用インタフェースが不要になる。
【実施例２】
【００５６】
キャッシュを利用する場合、異なる複数のデータによりキャッシュメモリ上の同一エントリばかりが集中的に利用され、互いのデータがキャッシュエントリを書き潰しあうスラッシングと呼ばれる状況が発生し、キャッシュエントリの入れ替えが頻繁に発生する結果、キャッシュの利用効率が低下することがある。実施例１で述べた（Ｎウェイ・）セット・アソシアティブ方式のプロセスキャッシュ及びそれに対応するトラフィック管理部のＦＩＦＯキューは、スラッシングを低減するための仕組みであるが、特定のエントリに対しては実装可能な小さめのＮの値ではスラッシング抑止に不十分である可能性がある。
そこで、本発明のキャッシュ用トラフィック制御部の第二の実施の形態として、前記のスラッシングによる性能低下を防ぐために、小容量のフル・アソシアティブ・プロセスキャッシュと前記小容量フル・アソシアティブ・プロセスキャッシュに対応するタグ及びＦＩＦＯキューを具備するキャッシュ用トラフィック制御部の実施例を示す。
【００５７】
フル・アソシアティブ・プロセスキャッシュとは、エントリ総数がＭ個ある場合、登録するエントリをＭ箇所のうちのどこへでも対応付けることができるプロセスキャッシュのことを指す。フル・アソシアティブ方式はダイレクトマップ方式及び（Ｎウェイ・）セット・アソシアティブ方式と比較して最も柔軟なキャッシュエントリ関連付けの方式であり、キャッシュのヒット率を最も高くすることができる。しかし、エントリの登録場所が一意に決まらないために、高速動作させるためには全エントリを同時に比較するために全エントリ数分の比較器を持つ必要があるため、実装のコストが高い。前記理由により（Ｎウェイ・）セット・アソシアティブ方式のキャッシュをサポートするために小規模のフル・アソシアティブ方式のキャッシュを実装するのが現実的である。
【００５８】
本実施例２では、図３においてトラフィック管理部２０３の内部構成として図６で示した（Ｎウェイ・）セット・アソシアティブのタグ５０２及びＦＩＦＯキュー５０５に加え、フル・アソシアティブの連想タグ６０１及び対応するＦＩＦＯキュー６０２を持つ図１１で示す構成をとる。連想タグ６０１は各エントリが内部に比較器を持ち、各エントリが独立してヒットチェックが可能である。連想タグ６０１の実現には、ＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）の利用が適切である。また、対応する図３のプロセスキャッシュ３０３も内部構成として図８で示した（Ｎウェイ・）セット・アソシアティブのデータ５１２に加え、前記フル・アソシアティブの連想タグ６０１に対応する連想データ６１０を持つ図１２で示す構成をとる。
【００５９】
本実施例２におけるトラフィック管理部２０３の動作について説明する。パケット解析部２０２よりトークンを受信すると、ハッシュ部５０１によりハッシュをかけたトークンでセット・アソシアティブ方式のタグ５０２、同時にハッシュをかけない元のままのトークンで連想タグ６０１を参照する。本実施例２では、状況に応じた、次の二種類の管理方法がトークンに適用される。
（１）セット・アソシアティブ方式のタグ５０２でヒットする場合、もしくはミスするがセット・アソシアティブ方式のタグ５０２に利用されていないウェイがある場合は、実施例１と同様にセット・アソシアティブ方式のタグ５０２及びそれに付随するＦＩＦＯキュー５０５でトークンの管理を行う。
（２）セット・アソシアティブ方式のタグ５０２でミスして、尚且つ利用できるエントリがない場合は、連想タグ６０１の利用されていないエントリを利用してトークンの管理を行う。
【００６０】
フル・アソシアティブ・プロセスキャッシュへのエントリ格納位置を指定するために、図４のキャッシュ用トラフィック制御部からキャッシュ型パケット処理部への伝達情報４５０に、「フル・アソシアティブ・プロセスキャッシュ・エントリ情報」が付加される。前記フル・アソシアティブ・プロセスキャッシュ・エントリ情報は、キャッシュ型パケット処理部が持つプロセスキャッシュデータのデータ格納エントリを決定するために利用する。
本実施例２では、実施例１と比較して、短時間の間にプロセスキャッシュの同一エントリばかりが異なるフロー群のパケットで集中的に利用されるケースで有利となる。
【実施例３】
【００６１】
実施例１、及び実施例２では実装効率を重視し、プロセスキャッシュメモリのタグ部分をキャッシュ型パケット処理部から分離してキャッシュ用トラフィック制御部に配置する例を示した。図１のキャッシュ型パケット処理部１０３は、プロセスキャッシュメモリのタグ部分とデータ部分を完全に備える形式であってもよい。そこで、図１３に実施例３として、キャッシュ型パケット処理部１０３のプロセスキャッシュメモリがデータ部分だけではなく、タグ部分も併せ持つ構成を示す。
本実施例３において、キャッシュ用トラフィック制御部１０２の構成は、実施例１もしくは実施例２と同一であるが、出力データ生成部２０４は、キャッシュ型パケット処理部１０３へ情報を渡す時、図4の４５０から固有情報４０１、解析情報４０２、抽出情報４０３を取り除いた形式で渡す。
【００６２】
本実施例３において、キャッシュ型パケット処理部１０３は、キャッシュ用トラフィック制御部１０２のパケット解析部２０２と同等の機能を持つパケット解析部３０２を具備する。前記解析部３０２において、キャッシュ用トラフィック制御部１０２からの受信パケットを解析し、図４に示すトークン４００を生成する。また、タグ部分とデータ部分を持つプロセスキャッシュ３０３を具備する。前記プロセスキャッシュ３０３の構成をダイレクトマップ方式の場合を例にとり図１４に示す。プロセスキャッシュ３０３は、タグ部５０２及びデータ部５１２両方を具備し、トークンからアクセスキーを生成するためのハッシュ部５０１、比較器５０３、結合器５１３を具備する。
【００６３】
前記プロセスキャッシュ３０３は、トークン４００を受信するとトークンの解析情報４０２と抽出情報４０３の組全体に対してハッシュ部５０１によりハッシュをかけ、プロセスキャッシュのタグ部５０２及びデータ部５１２へのアクセスキーを生成し、タグ部５０２を参照する。そして、タグ部５０２より出力される解析情報４０２と抽出情報４０３の組と、アクセスキー生成に利用した前記トークンの解析情報４０２と抽出情報４０３の組を比較器５０３により一致検査を行い、一致すればプロセスキャッシュにヒット、一致しなければプロセスキャッシュにミスとして扱う。プロセスキャッシュヒット時には、データ部５１２からの出力である抽出情報α４１１及び処理情報４１２とアクセスキー生成に利用した前記トークンの固有情報４０１及び解析情報４０２を結合器５１３により結合し、後処理部３０６へ渡す。プロセスキャッシュミス時には、トークンをキャッシュミス処理部３０４へ渡し、パケット処理部３０５で処理後、プロセスキャッシュ３０３に処理結果のトークン４７０を登録する。そして、実施例１、実施例２と同様に図４の４６０に示す形式でキャッシュ登録完了通知を信号２０８により伝える。
【実施例４】
【００６４】
実施例４として、実施例３からプロセスキャッシュ登録完了通知２０８を取り除いた構成例を挙げる。この場合、キャッシュ用トラフィック制御部１０２は、フローの二つ目以降のパケットの正確な発行タイミングがわからないため、図１５に示すように、トラフィック管理部２０３の各エントリにタイマ５２０を設け、タイマが閾値を超えたら、キャッシュ型パケット処理部１０３のプロセスキャッシュ３０３に登録されている可能性が高いとして発行を開始する。
【００６５】
本実施例４では、プロセスキャッシュへフローの先頭パケットの処理結果が登録されたことを保証できないため、本来の目的である同一フローのパケットが連続到着した時にプロセスキャッシュのヒット率低下を完全に抑止することはできない。
【００６６】
しかしながら、本実施例４を用いると、キャッシュ型パケット処理部１０３が、キャッシュ用トラフィック制御部１０２の存在を意識しない構成をとることができる。このため、キャッシュ型パケット処理部１０３だけを搭載したネットワーク装置に、本発明のキャッシュ用トラフィック制御部１０２の機能を含むデバイスを追加搭載して前記ネットワーク装置のアップグレード（キャッシュヒット率低下の抑止）を図ることが可能になる。
【実施例５】
【００６７】
プロセスキャッシュにミスするパケットは全てパケット処理部で処理される。一実施例としては、パケット処理部の負荷も高くなることを想定し、よりスループットの高い（処理速度の速い）キャッシュ型パケット処理部のパケット処理部が必要になることがある。この場合、図１０からパケット処理部を３０５、パケットメモリ３１０、テーブルメモリ３２０を図１６に示すように別チップとして実装する方式がある。この場合、パケット処理部を複数のキャッシュ型パケット処理部で共有してもよい。トラフィック管理部２０３の方式は、実施例１、実施例２、実施例３及び実施例４いずれでも構わない。
尚、図１６においてキャッシュ用トラフィック制御部とキャッシュ型パケット処理部を更に分割して実装してもよい。
【００６８】
以上、本発明によるネットワークプロセッサアクセラレータを利用したネットワーク装置および、ネットワークプロセッサアクセラレータそのものの一実施例を説明した。本説明はあくまで一実施例の説明であり、本発明の範囲を限定するものではなく、様々な変形例に対して適用可能である。
【産業上の利用可能性】
【００６９】
本発明のキャッシュ用トラフィック制御部は、ネットワーク上を流れるパケットやフレーム等のデータを転送処理するためにキャッシュ型のパケット処理部を持つネットワーク装置への利用が可能である。本発明のキャッシュ用トラフィック制御部をキャッシュ型パケット処理部とあわせて用いることにより、ネットワーク装置へのネットワークトラフィックの到着順序により発生するキャッシュミス、および前記キャッシュミスによるネットワーク装置の処理速度低下を無くすことができる。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施の形態１における、キャッシュ用トラフィック制御部とキャッシュ型パケット処理部を持つネットワーク装置のブロック図である。
【図２】従来のトラフィック制御部とパケット処理部を持つネットワーク装置のブロック図である。
【図３】本発明の実施形態１における、キャッシュ用トラフィック制御部とキャッシュ型パケット処理部の内部ブロック図である。
【図４】キャッシュ用トラフィック制御部及びキャッシュ型パケット処理部の内部で用いるデータフォーマット一覧である。
【図５】ダイレクトマップ方式のキャッシュ用トラフィック制御部のトラフィック管理部部分のブロック図である。
【図６】Ｎウェイ・セット・アソシアティブ方式のキャッシュ用トラフィック制御部のトラフィック管理部部分のブロック図である。
【図７】ダイレクトマップ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ構造例である。
【図８】Ｎウェイ・セット・アソシアティブ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ構造例である。
【図９】キャッシュ型パケット処理部のキャッシュミス処理部のブロック図である。
【図１０】キャッシュ用トラフィック制御部とキャッシュ型パケット処理部を一体化した場合のブロック図である。
【図１１】Ｎウェイ・セット・アソシアティブ方式のキャッシュ用トラフィック制御部のタグ及びＦＩＦＯキュー部分にＭエントリのフル・アソシアティブ方式のキャッシュ用トラフィック制御部のタグ及びＦＩＦＯキュー部分を追加した場合のブロック図である。
【図１２】Ｎウェイ・セット・アソシアティブ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ部分にＭエントリのフル・アソシアティブ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ部分を追加した場合のブロック図である。
【図１３】キャッシュ型パケット処理部のプロセスキャッシュがタグ部分も持つ場合のキャッシュ用トラフィック制御部及びキャッシュ型パケット処理部のブロック図である。
【図１４】タグ部及びデータ部を具備するダイレクトマップ方式のプロセスキャッシュのブロック図である。
【図１５】図１４におけるキャッシュ用トラフィック制御部のトラフィック管理部部分のブロック図である。
【図１６】図１０において、キャッシュ型パケット処理部のパケット処理部分をキャッシュ型パケット処理部から分離した場合のブロック図である。
【符号の説明】
【００７１】
１０：ネットワークインタフェースカード
１１：スイッチファブリック
１０１：ネットワークインタフェース部
１０２：キャッシュ用トラフィック制御部
１０３：キャッシュ型パケット処理部
１１０：パケット処理部（ネットワークプロセッサ）
１１１：トラフィック制御部（トラフィックマネージャ）
２０１：キャッシュ用トラフィック制御部のパケット入力インタフェース
２０２：キャッシュ用トラフィック制御部のパケット解析部
２０３：キャッシュ用トラフィック制御部のトラフィック管理部
２０４：キャッシュ用トラフィック制御部の出力データ生成部
２０５：キャッシュ用トラフィック制御部のパケット出力インタフェース
２０８：キャッシュ型パケット処理部からキャッシュ用トラフィック制御部へのプロセスキャッシュ登録通知信号
２１０：キャッシュ用トラフィック制御部のパケットメモリ
３０１：キャッシュ型パケット処理部のパケット入力インタフェース
３０２：キャッシュ型パケット処理部のパケットの解析部
３０３：キャッシュ型パケット処理部のプロセスキャッシュ
３０４：キャッシュ型パケット処理部のキャッシュミス処理部
３０５：キャッシュ型パケット処理部のパケット処理部
３０６：キャッシュ型パケット処理部の後処理部
３０７：キャッシュ型パケット処理部のパケット出力インタフェース
３１０：キャッシュ型パケット処理部のパケットメモリ
３２０：キャッシュ型パケット処理部のテーブルメモリ
４００：キャッシュ用トラフィック制御部のパケット解析部で生成するトークン
４０１：トークンの固有情報
４０２：トークンの解析情報
４０３：トークンの抽出情報
４１０：キャッシュ型パケット処理部の後処理部で利用されるトークン
４１１：パケット処理部で修正されたトークンの抽出情報である抽出情報α
４１２：パケット処理部で生成されたトークンの処理情報
４２０：キャッシュ用トラフィック制御部のタグ
４２１：４２０の有効ビット
４２２：４２０のＦＩＦＯキューエンプティビット
４２３：プロセスキャッシュ登録済みビット
４２４：４２０のプロセスキャッシュ登録中ビット
４２５：４２０の優先順位制御情報
４２６：４２０の帯域制御情報
４３０：キャッシュ用トラフィック制御部のＦＩＦＯキューの登録内容
４３１：４３０の有効ビット
４４０：キャッシュ用トラフィック制御部の待機バッファの登録内容
４４１：４４０の有効ビット
４５０：キャッシュ用トラフィック制御部からキャッシュ型パケット処理部へ転送する情報
４５１：４５０の登録ＦＩＦＯキュー番号
４５３：４５０のウェイ情報
４５４：４５０のオリジナルパケット
４６０：キャッシュ型パケット処理部からキャッシュ用トラフィック制御部へ転送する情報
４６１：４６０のキャッシュ可能ビット
４７０：キャッシュ型パケット処理部のプロセスキャッシュのデータ部分に登録するトークン
５０１：キャッシュ用トラフィック制御部のアクセスキーを生成するハッシュ部
５０２：キャッシュ用トラフィック制御部のタグ（プロセスキャッシュのタグ）
５０３：キャッシュ用トラフィック制御部のタグ比較器
５０４：キャッシュ用トラフィック制御部のタグ及びＦＩＦＯキューの書込制御部
５０５：キャッシュ用トラフィック制御部のＦＩＦＯキュー
５０６：キャッシュ用トラフィック制御部のタグ及びＦＩＦＯキューの読出制御部
５０７：キャッシュ用トラフィック制御部の待機バッファ
５１１：キャッシュ用トラフィック制御部のアクセスキーを生成するハッシュ部
５１２：キャッシュ型パケット処理部のプロセスキャッシュのデータ部
５１３：キャッシュ型パケット処理部のプロセスキャッシュの結合器
５２０：キャッシュ用トラフィック制御部のＦＩＦＯキューのタイマ
６０１：キャッシュ用トラフィック制御部のフル・アソシアティブ方式のタグ
６０２：キャッシュ用トラフィック制御部のフル・アソシアティブ方式のＦＩＦＯキュー
６１０：キャッシュ型パケット処理部のフル・アソシアティブ方式のプロセスキャッシュのデータ部
７０１：キャッシュ型パケット処理部のキャッシュミス処理部のキャッシュミス管理テーブル
７０３：キャッシュ型パケット処理部のキャッシュミス処理部の処理情報管理テーブル
７０４：キャッシュ型パケット処理部のキャッシュミス処理部の結合器
９００：一体化したキャッシュ用トラフィック制御部とキャッシュ型パケット処理部
９０２：キャッシュ型パケット処理部の外部へのパケット処理部へのインタフェース
９０３：パケット処理部
９０４：パケットメモリ
９０５：テーブルメモリ。
【技術分野】
【０００１】
本発明は、大容量パケットの低遅延交換システム向けのルータやスイッチ等のネットワーク装置構成方法にかかわる技術である。特に、ネットワーク装置の構成要素として、キャッシュを利用してＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）パケットやＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）フレームの処理を実施するネットワークプロセッサやＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）のためのトラフィック制御に効果的な技術である。
【背景技術】
【０００２】
通信分野においては、複数のネットワーク間を接続するためにルータやスイッチ等のネットワーク装置が用いられる。ネットワーク装置は、レイヤ３のＩＰに基づくパケット、レイヤ２のＭＡＣに基づくフレームと呼ばれるデータを送受信することにより通信を行う。以下では、ひとつのデータ単位をパケットと呼び議論を進める。ネットワーク装置は、受信したパケットの宛先アドレスを調べてパケットの転送先を決定し、所定の転送先にパケットを転送することを繰り返し、目的の宛先へパケットを届ける。世界のネットワークで送受信されるパケットの総量は増大する一方であり、ネットワーク装置のパケット転送性能も、トラフィック量の増大に伴って向上させていく必要がある。また、パケットを単に転送するだけではなく、所定のルールを定めて該ルールに適合するものだけを転送（フィルタリング）したり、該ルールに従い単位時間あたりのパケット送出量を規定以下に制限（シェイピング）したり、該ルールに従いパケット間に優先順位を設けて転送したり、該ルールに従いパケットの情報を修正する等の処理も行う。
【０００３】
安価なネットワーク媒体としてイーサネットが利用されている。イーサネットのスピードは１９９０年代半ばまでは１０Ｍｂｐｓ（Ｍｅｇａｂｉｔ ｐｅｒ ｓｅｃｏｎｄ）から１００Ｍｂｐｓと比較的低速であったため、パケット処理は汎用プロセッサを用いたソフトウェア処理でも十分な余裕があった。しかしながら、１９９０年代後半よりイーサネットのスピードは１Ｇｂｐｓ（Ｇｉｇａｂｉｔ ｐｅｒ ｓｅｃｏｎｄ）から１０Ｇｂｐｓと高速化が進んでおり、この速度でパケット処理を実施するために、ネットワーク装置にはパケット処理専用に設計されたネットワークプロセッサやＡＳＩＣが用いられるようになっている。
【０００４】
ネットワークインタフェースの速度が上がるにつれ、パケットひとつあたりにかけられる処理時間は短くなっていく。ネットワークプロセッサでは、内部に複数のプロセッサ（パケット処理エンジン）を組み込み、パケットを並列処理することにより、パケットあたりの処理時間を確保しスループット向上を果たしている。しかしながら、ネットワークプロセッサのスループットを向上させ、より高速なネットワークインタフェースに対応させるために、ネットワークプロセッサ内部のパケット処理エンジンの数を増加させる手法は、ネットワークプロセッサの巨大化と消費電力の増加を引き起こす。
【０００５】
そこで、内部パケット処理エンジンの数を増加させる代わりに、キャッシュメモリを追加し、該パケット処理エンジン群での処理結果をプロセスキャッシュと呼ぶキャッシュに記録し、同一処理で済むパケットは前記プロセスキャッシュの内容を利用するネットワークプロセッサアーキテクチャが特願２００３−０４８７３０号公報にて提案されている。前記ネットワークプロセッサアーキテクチャ、もしくはそれに順ずるアーキテクチャを以降ではキャッシュ型パケット処理部と呼ぶ。ネットワークを流れるパケット流（トラフィック）には、同一のヘッダ情報、例えば送信元と宛先のペアが一緒といった情報を持つパケットが短時間の間に多数出現しやすい性質（時間的局所性）があるため、パケット流の混ざり合いの度合いが濃くないネットワークの末端近くのエッジ網やアクセス網、及びネットワーク中心から末端の間に位置するミドルマイル網ではキャッシュ型パケット処理部は比較的有効に働くと考えられる。
【０００６】
前記のキャッシュ型ネットワークプロセッサによりネットワーク装置を構成する場合、パケットの到着順序によってはキャッシュのヒット率が低下し、ひいてはネットワーク装置全体のスループットが低下する恐れがある。具体的には、同一のヘッダを持つパケット群が短時間に大量に到着し、最初のパケットのキャッシュ登録がそれ以降のパケットの到着に間に合わないケースである。
【０００７】
前記状況で発生する問題を解決するためには、パケットのスケジューリングが必要である。スケジューリング手法には、有用な多くの公知例が存在する。例えば、複数のセッション（フロー）をクラス毎に分類した第１レベルのスケジューリングを実施した後、それらのいくつかの出力に対し第２レベルのスケジューリングを行い、残りの第１レベルの出力と第２レベルの出力に対して優先順位付けを行う第３レベルのスケジューリングを行う方法が特表２００１−５１９１２０にて公開されている。また、優先度付きのキューと出力キューを縦列に接続し、前段の優先度キューは低優先度のパケットを滞留させマークを付け、後段の出力キューで輻輳検出を行い輻輳発生時にはマーク付けされているパケットを廃棄することにより優先度毎のトラフィック量の変動と無関係に一定の帯域を確保し、保証帯域を有効利用するスケジューリング技術が特開２００２−１８５５０１にて公開されている。
また、パケットを格納する複数本のキューを備え、各キューの先頭パケットに転送終了予定時刻の早い順に転送順序の重み付けを行い、転送帯域制御を実施するスケジューラに関して特開２０００−１０１６３７にて公開されている。ただし、事実上、比較的少数のキューしかハードウェアへの実装が困難とし、特開２００３−３２４４７１で、事実上実装可能なキューの数を増加させ、帯域制御を高精度化させるために複数個の演算器を並列且つ時分割で動作させ前記のスケジューリングを実施する手法に関して公開している。
しかしながら、いずれのスケジューリングも、本発明が解決しようとする課題、プロセスキャッシュのヒット率の低下を防ぐためのスケジューリングを実施することができない。
本願発明者が出願した特願２００３−３４６５１９では、プロセスキャッシュにミスしたパケットを処理する機能ブロックにおいて、キャッシュミスしたフローの先頭パケットのみプロセッサで処理させ、該フローの二つ目以降はキャッシュミスを扱う前記機能ブロックで保持しておく手法が開示されている。しかし、プロセスキャッシュにアクセスする以前にパケットをスケジューリングする手法に関しては言及していない。
【０００８】
【特許文献１】特願２００３−０４８７３０号
【０００９】
【特許文献２】特表２００１−５１９１２０号公報
【特許文献３】特開２０００−１０１６３７号公報
【特許文献４】特開２００２−１８５５０１号公報
【特許文献５】特開２００３−３２４４７１号公報
【特許文献６】特願２００３−３４６５１９号
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の課題は、ネットワークまたはスイッチファブリックからの入力トラフィックを管理し、パケット転送処理を高速化するためにパケット処理結果を保持するプロセスキャッシュと呼ばれるキャッシュのパケットの到着順序に依存するヒット率の低下を防ぎ、結果としてプロセスキャッシュ技術を利用したネットワーク装置の性能低下を防ぐ技術を提供することにある。
また、可能な限りプロセスキャッシュにヒットする状態を作り出すことで、プロセスキャッシュミス時に利用するパケット処理プロセッサの稼働率を低下させ、消費電力を低減することにある。
【課題を解決するための手段】
【００１１】
本発明は、ネットワークプロセッサの巨大化を避けつつ、パケット転送処理を高速化するためのプロセスキャッシュと呼ばれる技術を補助し、ネットワークトラフィックを管理することで、プロセスキャッシュのヒット率低下を防ぐための技術である。プロセスキャッシュ技術では、受信パケットに対する処理結果を記録するためのキャッシュがキャッシュ型パケット処理部に設けられる。プロセスキャッシュ技術では、パケット群を利用者が定めたルールに従い分類し、分類したパケット群の中で最初のパケットのみをキャッシュ型パケット処理部の内部に組み込むプロセッサにおいて処理する。前記処理結果をプロセスキャッシュに記録して、以後同一フローと判断するパケットにはプロセスキャッシュに記録してある結果を即座に受信パケットに適用する。この操作により、ネットワークプロセッサに内蔵された組み込みプロセッサでの処理を削減し、ネットワーク装置のパケット処理速度を向上する。
【００１２】
本発明では、ネットワークトラフィックを管理するためのトラフィック管理部として、プロセスキャッシュの前段にプロセスキャッシュのタグを収めるプロセスキャッシュタグと、前記タグの各エントリに対応するＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）キューを持つ機能ブロックを設ける。トラフィック管理部では、同一フローと判断したパケット群を到着順に同一のＦＩＦＯキューに積む。各ＦＩＦＯキューは対応するプロセスキャッシュの登録状況を記録しており、プロセスキャッシュに未登録状態のエントリのＦＩＦＯキューにパケットが到着すると、先頭のパケットのみをプロセスキャッシュミス処理を実施する機能ブロックへ渡し、プロセスキャッシュに登録されるのを待つ。二つ目以降のパケットはプロセスキャッシュへの登録が完了した時点でＦＩＦＯキューからプロセスキャッシュへのアクセスを実施する。前記操作により、フローの先頭以外のパケットのプロセスキャッシュアクセスは必ずキャッシュヒットとすることが可能となる。
【００１３】
前記の手段により、パケットの到着順序に依存するキャッシュヒット率の低下を防ぐ。尚、二つ目以降のパケットを保持している間、同一フローではないと判断したパケット群の先頭のパケットもプロセスキャッシュミス処理を実施する機能ブロックへ渡すことを可能とする。前記操作により、異なるフローに属するパケットの並列処理を実施することで組み込みプロセッサ資源の有効利用も図る。
【００１４】
本発明のパケット処理方法は、より詳細には、キャッシュメモリを用い、先行するパケットに関する処理結果をキャッシュメモリに記録し、先行するパケットと同一処理を行う後続のパケットの処理は該キャッシュメモリの内容を利用する、キャッシュ型のパケット処理方法であって、パケットを受信するステップと、受信したパケットをフロー毎に分類するステップと、フロー毎に分類したパケットを、パケットの到着順序を維持してＦＩＦＯ型のキューにフロー毎に記録するステップと、キュー内のフローの所定パケットがキャッシュに未登録である場合、所定パケットを処理して処理結果をキャッシュメモリに格納するとともに、同一キュー内の所定パケット以降のパケットは、キューに待機させておくステップと、所定パケットに関する処理結果のキャッシュメモリへの格納の完了の後に、上記キューに待機させておいたパケットの処理を行うステップと、を有する。
各フローの先頭パケットは、他のフローで待機中のパケットを追い越して処理されるようにすることで、全体のスループットを向上させることができる。
【００１５】
また、さらに、具体的には、各キューは対応するキャッシュを有しており、各キューが対応するキャッシュの登録情報を記録するステップと、キャッシュに未登録状態のキューにパケットが到着すると、先頭のパケットのみを処理し、処理結果が上記キャッシュに登録されるのを待つステップと、二つ目以降のパケットは上記キャッシュへの登録が完了した時点で処理が開始されるように構成することができる。
【００１６】
本発明のネットワーク装置は、パケットを受信する入力インタフェースと、受信したパケットを解析および分類して、種類毎にフローを生成するパケット解析部と、生成されたフローを、種類毎にパケットの受信順序を保持して管理するトラフィック管理部と、パケットを処理するパケット処理部と、パケット処理部の処理結果をフロー毎に登録するプロセスキャッシュとを有するネットワーク装置であって、該ネットワーク装置は、
(1)上記プロセスキャッシュに処理結果が未登録な第１のフローの第１のパケットを、上記パケット処理部で処理し、
(2)上記第１のフローの第１のパケットに後続するパケットは、上記第１のパケットの処理結果が上記プロセスキャッシュに登録されるまで待機させ、登録の後、上記プロセスキャッシュの情報を用いて処理を行い、
(3)上記第１のフローの第１のパケットに後続するパケットを待機させている間に、第２のフローのパケットが該待機中のパケットより先に処理されるように、
フローを制御することを特徴とする。
具体的には、トラフィック管理部は、生成されたフローに対応する内部処理情報列を、フローの種類毎にパケットの受信順序を保持して格納するキューを有し、キューに格納される内部処理情報列は、対応するパケットの処理結果がプロセスキャッシュに登録されているか否かを示す登録済み情報を含む。この登録済み情報を用いてパケットを処理部へおくる順番を制御し、フローの制御を行う。
【００１７】
パケット処理部の前段には、登録済み情報に基づいて、パケットをパケット処理部で処理するか、プロセスキャッシュを参照して処理するかを選択する解析部を有することが望ましい。
解析部の選択により、パケットがパケット処理部で処理された場合、当該処理結果がプロセスキャッシュに登録完了されたことをトラフィック管理部に通知するキャッシュミス処理部を設けることが可能である。トラフィック管理部は、キャッシュミス処理部からの通知に基づいて、内部処理情報列に登録済み情報を付加することができる。このようにすると、トラフィック管理部は、内部処理情報列に負荷された登録済み情報を参照してフローを制御することができる。
第１のフローの第１のパケットは、第１のフローの先頭パケットであってもよい。また、第２のフローのパケットは、プロセスキャッシュに処理結果が未登録な先頭パケットまたは、プロセスキャッシュに処理結果が登録済みの後続パケットであってもよい。
【発明の効果】
【００１８】
本発明のトラフィック管理部を利用すると、キャッシュ型ネットワークプロセッサなどのキャッシュを利用するパケット処理部を持つネットワーク装置において、パケットの到着順序に依存するキャッシュヒット率の低下を防ぎ、結果としてネットワーク装置のスループット低下を回避する効果がある。
また、本発明のトラフィック管理部を利用すると、前記キャッシュヒット率の低下抑止によりプロセスキャッシュミス時に利用するパケット処理を実施するプロセッサの稼働率を低下させ、消費電力を低減する効果がある。
【発明を実施するための最良の形態】
【００１９】
以下、より詳細な内容を実施例で示す。
【実施例１】
【００２０】
図１には、本実施例におけるネットワーク装置の構成例を示す。
本実施例では、ネットワーク装置は、ネットワークからパケットを送受信するためのネットワークインタフェース部１０１、ネットワークトラフィックを制御するためのキャッシュ用トラフィック制御部１０２、キャッシュ型パケット処理部１０３、前記１０１、１０２、１０３を含むネットワークインタフェースカード１０、複数のネットワークインタフェースカード１０を結合しパケットを交換するスイッチファブリック１１等で構成される。この他に複数のネットワークインタフェースカード１０の間の経路情報等の集中管理を行うホストプロセッサやホストプロセッサへのインタフェース等もある。
【００２１】
本実施例におけるパケット処理動作と効果に関して、まず全体の概要を説明する。ネットワークインタフェース部１０１よりパケットを受信し、キャッシュ用トラフィック制御部１０２が、パケットをフローと呼ぶグループに分類し、パケットの到着順序を維持するためにＦＩＦＯ型のキューにフロー毎記録する。そして、まず、キャッシュ型パケット処理部１０３のキャッシュに未登録である各フローの先頭パケットのみをキャッシュ型パケット処理部１０３へ渡し、各フローの二つ目以降のパケットは、ＦＩＦＯ型のキューに保持しておく。各フローの先頭パケットは、他のフローの二つ目以降のパケットを追い越して、キャッシュ型パケット処理部１０３へ渡すことを可能とする。前記二つ目以降のパケットは、キャッシュ型パケット処理部１０３においてキャッシュ登録完了通知を受けてからキャッシュ型パケット処理部１０３へ渡す。
前記動作により、キャッシュ型パケット処理部１０３では、フローの先頭のパケット以外は全てキャッシュヒットさせることができる。即ち、パケットの到着順序に依存するキャッシュヒット率の低下を防ぎ、結果としてネットワーク装置のスループット低下を回避する効果がある。
【００２２】
キャッシュ型パケット処理部１０３は、一つ以上のプロセッサと、前記プロセッサでのプログラム処理結果を格納するためのプロセスキャッシュと呼ぶキャッシュメモリを持つ。前記フローの先頭のパケットはプロセッサを利用して、パケットの宛先情報を得るために経路検索を実施し、必要であればその他の操作、例えばパケットを通過させるか否かを決定するためのフィルタリング情報取得や、ＭＰＬＳ（Ｍｕｌｔｉｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）やＶＬＡＮ（Ｖｉｒｔｕａｌ Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）等のヘッダ情報の取得等を実施する。前記実施の結果を専用ハードウェア、もしくは簡易プロセッサでビット列操作だけでパケットに適用できる情報列にしてプロセスキャッシュへ登録し、後段の処理を実施する部分へパケットを渡す。前記フローの二つ目以降のパケットは、プロセスキャッシュにヒットするため、プロセスキャッシュの内容を利用してプロセッサでの処理をバイパスし、後段の処理を実施する部分へパケットを渡す。前記後段の部分は、専用のビット列操作用のハードウェア等によりパケットに必要な処理を施しパケットをスイッチファブリック１１へ渡し、当該パケットに対する処理を終了する。一般にプロセッサの稼働率が高くなるほど、消費電力は上昇する。キャッシュ型パケット処理部１０３はパケット処理のために一つ以上のプロセッサを含むが、前記プロセッサは前記プロセスキャッシュにミスする先頭のパケットのみを処理すれば良いため、本発明によるキャッシヒット率の低下抑止により消費電力を低減することが可能となる。本発明のキャッシュ用トラフィック制御部１０２の分の消費電力は増加するが、以降に述べるトラフィックマネージャの替わりに用いることを考慮すると、キャッシュ用トラフィック制御部１０２の分の消費電力はトラフィックマネージャ相当と見做し、無視することができる。
【００２３】
スイッチファブリック１１は、各ネットワークインタフェースカード１０から受信したパケットを指定された宛先のネットワークインタフェースカード１０に向けて送信する。スイッチファブリック側からネットワークインタフェースカード１０へ渡されるパケットは、キャッシュ用トラフィック制御部１０２、キャッシュ型パケット処理部１０３を同様に通過してネットワークへ送信される。
【００２４】
本発明によるキャッシュ用トラフィック制御部１０２は、ネットワークトラフィックの管理を行う点で従来のネットワーク装置で利用されるトラフィックマネージャと呼ばれるデバイスに類似するが、実施する制御で決定的に異なる点を持つ。
まず、トラフィックマネージャについて説明する。トラフィックマネージャとは、規定帯域以上の入力がないか監視し、規定帯域以上の場合には入力を廃棄するポリシングや、規定帯域以上の出力を規定以下に制限するためのシェイピング、フローの順序を優先順位に応じて調整するスケジューリング等を実施するデバイスである。トラフィックマネージャを利用したネットワーク装置は、例えば図２に示すように、ネットワークからパケットを送受信するためのネットワークインタフェース部１０１、パケット処理部としてのネットワークプロセッサ（もしくはそれに順ずるＡＳＩＣ）１１０、トラフィック制御部としてのトラフィックマネージャ（もしくはそれに順ずるＡＳＩＣ）１１１、前記１０１、１１０、１１１を含むネットワークインタフェースカード１０、複数のネットワークインタフェースカード１０を結合しパケットを交換するスイッチファブリック１１等で構成される。この他に複数のネットワークインタフェースカード１０の間の経路情報等の集中管理を行うホストプロセッサやホストプロセッサへのインタフェース等もある。
【００２５】
次に、本発明のキャッシュ用トラフィック制御部１０２が従来のトラフィックマネージャと決定的に異なる点について説明する。キャッシュ用トラフィック制御部１０２は、フローの先頭以外のパケットがプロセスキャッシュにヒットするアクセスになるように入力トラフィックを制御する点で、従来のトラフィックマネージャと異なる。また、ネットワーク装置構成時のネットワーク入力からスイッチファブリックへ向かう側での設置位置が異なる。通常、トラフィックマネージャは、ネットワークプロセッサやＡＳＩＣ等のパケット処理部の後段に設置されるが、本発明によるキャッシュ用トラフィック制御部は、キャッシュ型ネットワークプロセッサやＡＳＩＣ等の前段に設置する。本実施例では、ネットワークからの入力側で、キャッシュ用トラフィック制御部１０２がパケット処理部である１０３より前段にある。これは、パケット流の制御をキャッシュアクセスより前に行うためである。
【００２６】
次に、キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３の内部構成例の詳細を図３に示し、パケット処理動作について説明する。キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３は、同一チップ上に集積できるならば、単一のチップとして実装しても良いし、それぞれを別のチップとして実装しても良い。図３では、キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３が別々のチップに実装するケースを想定している。
キャッシュ用トラフィック制御部１０２は、一実施例として、入力インタフェース２０１、パケット解析部２０２、トラフィック管理部２０３、出力データ生成部２０４、出力インタフェース２０５、プロセスキャッシュ登録信号２０８、パケットメモリ２１０より構成される。前記のキャッシュ用トラフィック制御部１０２の構成要素は、低レイテンシかつ高速なパケット処理を実現するには単一のチップ上に実装するのが望ましい。パケットメモリ２１０についても、例えば、混載ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）技術や１Ｔ−ＳＲＡＭ（１Ｔｒａｎｓｉｓｔｏｒ Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）技術等の高密度実装可能な高速オンチップメモリを利用してキャッシュ用トラフィック制御部１０２の他の構成要素と同一チップ上に実装するのが望ましいが、パケットメモリ２１０の一部もしくは全てをチップ外部に実装する選択肢もある。
【００２７】
キャッシュ用トラフィック制御部１０２は、パケットを入力インタフェース２０１により受信後、パケット解析部２０２によりパケットの解析を行い、内部処理専用の情報列を生成する。ここでは、前記内部処理専用情報列をトークンと呼ぶ。元のパケットは、パケットメモリ２１０に格納する。図４に前記トークン４００の構成を示す。前記トークン４００は、固有情報４０１、解析情報４０２、抽出情報４０３により構成する。
固有情報４０１は、各トークンを区別するために用いるパケット毎の固有の情報である。例えば、パケットメモリ２１０へのパケット格納アドレスが挙げられ、パケット格納アドレスにより各トークンを区別可能になる。また、パケット処理に利用するために、実装によっては、パケットのサイズ、パケットのフラグメント情報、パケットを解析した結果判明したエラー情報、ＴＣＰの制御情報等を含めてもよい。例えば、パケットサイズは、複数のフローがキャッシュ用トラフィック制御部１０２から発行可能になった時に、後述するＱｏＳ（Ｑｕａｒｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）制御の一環としてパケットサイズを利用しながら出力するフローを選択するのに利用できる。また、ＴＣＰの制御ビットでは、例えばＦＩＮ及びＲＳＴビットを利用しフローの最終パケットのトークンであることを示し、当該トークン通過後、対応するプロセスキャッシュのエントリ、ＦＩＦＯキューのエントリをクリアするのに利用できる。
【００２８】
解析情報４０２は、パケットの各ネットワークレイヤで利用されているプロトコルや転送に関する情報である。レイヤ２、レイヤ３、レイヤ４、レイヤ５〜７における利用プロトコル（例えば、レイヤ２でＭＰＬＳを利用、ＶＬＡＮを利用、レイヤ３でＩＰｖ４を利用、ＩＰｖ６を利用、レイヤ４でＴＣＰを利用、レイヤ７でＨＴＴＰを利用等）や、レイヤ２におけるパケット転送情報（ユニキャスト、ブロードキャスト、または、マルチキャスト）を示す。利用プロトコル種の解析情報４０２中での表記形式は、実際のパケットのヘッダに含まれる形式（例えば、レイヤ２のタイプフィールドそのもの）でも良いし、必要と判断した数種類（例えば16種類程度）に限定し、それをエンコードした形式（例えば16種類なら4ビットにエンコードが可能）でも良い。どのレイヤまで解析するかは、解析情報４０２を生成するためにパケット解析部２０２が持つ命令メモリに格納するプログラムにより規定することを可能とする。このため、利用形態によりレイヤ２スイッチ用、レイヤ３スイッチ用、レイヤ４スイッチ用、レイヤ７スイッチ用等への柔軟な対応が可能である。
【００２９】
抽出情報４０３は、パケットから抽出したヘッダ情報の一部である。例えば、レイヤ３の抽出情報としてＩＰｖ４の宛先ＩＰアドレスと送信元ＩＰアドレスを抽出することができる。また別の例では、前記のレイヤ３抽出情報に加えレイヤ４のＴＣＰ宛先ポート番号とＴＣＰ送信元ポート番号を抽出できる。抽出内容は、解析情報４０２と同様に、パケット解析部２０２が持つ命令メモリに格納するプログラムを書き換えることにより変更可能である。
【００３０】
ある二つのパケットが同一フローに属するか、異なるフローに属するかを判断するために、トークン４００の解析情報４０２と抽出情報４０３を利用する。ある二つのパケットを比較したとき、それぞれの解析情報４０２および抽出情報４０３の組が同一であれば、二つのパケットは同一フローに属すとみなすことができる。一方で、ある二つのパケットを比較したとき、それぞれの解析情報４０２および抽出情報４０３の組が異なれば、二つのパケットは異なるフローに属すとみなすことができる。
【００３１】
パケット解析部２０２により生成したトークン４００は、フロー毎に分類可能な状態にあるため、トラフィック管理部２０３において分類及び管理を行う。トラフィック管理部２０３の内部構成例を図５に示す。トラフィック管理部２０３は、ハッシュ部５０１、タグ部５０２、ＦＩＦＯキュー５０５、比較器５０３、書込制御部５０４、読出制御部５０６、待機バッファ５０７により構成される。
【００３２】
トラフィック管理部２０３は、フローの二つ目以降のパケットがプロセスキャッシュにミスしないようにするために、プロセスキャッシュの状態、即ち当該トークンがプロセスキャッシュに登録されている状態（ヒット状態）か、登録されていない状態（ミス状態）か知る必要がある。そこで、プロセスキャッシュの状態を知るために、トラフィック管理部２０３は、プロセスキャッシュのタグに相当するタグ部５０２を具備している。タグ部５０２は、トークンの解析情報４０２と抽出情報４０３を保持する。タグを参照するためのアクセスキーは、ハッシュ部５０１を利用してトークンの解析情報４０２と抽出情報４０３全体に対してハッシュをかけて生成する。ハッシュ部５０１は、キャッシュ型パケット処理部１０３のプロセスキャッシュ３０３の具備するハッシュ部５１１と同一のアルゴリズムを利用する。ハッシュには様々な手法があるが、例えばＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ）演算等の攪拌能力に優れたものを利用する方法が、キャッシュのエントリ競合を起こしにくくなりヒット率向上に繋がるため望ましい。比較器５０３を利用してタグ５０２を参照後に出力されるタグ内容と、アクセスを行ったトークンの解析情報４０２と抽出情報４０３を比較することにより、当該トークンがプロセスキャッシュにヒットするか否かを判断可能である。
【００３３】
トラフィック管理部２０３は、キャッシュ型パケット処理部１０３へのパケットフローを制御するために、トークンをフローごとに到着順に管理するＦＩＦＯキュー５０５をタグ５０２のエントリ毎に具備している。タグ５０２への登録形式の例を図４の４２０に、ＦＩＦＯキュー５０５への登録例を図４の４３０に示す。
【００３４】
タグ登録情報４２０は、エントリが利用されていることを示す有効ビット４２１、トークンの解析情報４０２、抽出情報４０３をプロセスキャッシュのタグ相当の情報として持つ。また、タグ５０２及びＦＩＦＯキュー５０５への読書き制御のために、対応するＦＩＦＯキュー５０５のエントリのトークンが入っていないことを示すＦＩＦＯキューエンプティビット４２２、プロセスキャッシュに現在登録要求を出していることを示すプロセスキャッシュ登録中ビット４２４、プロセスキャッシュに登録が完了したことを示すプロセスキャッシュ登録済みビット４２３を持つ。また、フロー毎にＱｏＳ制御を実施する場合には、当該フローの優先順位を示す優先順位情報４２５、当該フローに許される利用帯域幅を示す帯域情報４２６を持つ。
【００３５】
ＦＩＦＯキュー登録情報４３０は、エントリが利用されていることを示す有効ビット４３１とトークンの固有情報４０１等により構成される。
ＦＩＦＯキュー５０５は、プロセスキャッシュのエントリ数Ｋと同じだけの本数を具備する。例えば、４０００エントリのプロセスキャッシュを利用する場合、４０００本のＦＩＦＯキューを具備する。各ＦＩＦＯキュー５０５は独立したメモリで実現してもよいし、複数本または全体をひとまとめにしたメモリで実現してもよい。
まず、タグ５０２及びＦＩＦＯキュー５０５への書込み制御に関して説明する。トークンは、前記の方法でハッシュ部５０１によりタグ５０２を参照し、プロセスキャッシュのヒット判定を行い書き込み制御部５０４へ通知する。ヒットしていれば、書込み制御部５０４は、対応するＦＩＦＯキューにトークンの固有情報４０１を書き込み、ＦＩＦＯキューエンプティビット４２２を空ではないことを示す値（例えば０）にする。
プロセスキャッシュにミスしていれば、当該トークンの解析情報４０２と抽出情報４０３を対応するエントリのタグ５０２へ、当該トークンの固有情報４０１を対応するＦＩＦＯキュー５０５に登録する。また、プロセスキャッシュ登録中ビット４２４に登録中を示す値（例えば１）をセットする。
【００３６】
次に、タグ５０２及びＦＩＦＯキュー５０５への読出し制御に関して説明する。読出し制御部５０６は、タグ５０２の各ＦＩＦＯキューのプロセスキャッシュ登録済みビット４２３とプロセスキャッシュ登録中ビット４２４及び、ＦＩＦＯキューエンプティビット４２２を監視する。ＦＩＦＯキュー５０５から読み出しが行われるのは、次の二つの場合がある。
（１）フローの先頭、即ちプロセスキャッシュに未登録のパケットである場合。この場合、プロセスキャッシュ登録済みビット４２３は未登録を示す値（例えば０）、プロセスキャッシュ登録中ビット４２４は登録中で無いことを示す値（例えば０）、ＦＩＦＯキューエンプティビット４２２は空ではない値（例えば０）を示している。
（２）フローの二つ目以降、即ちプロセスキャッシュに登録済みのパケットである場合。この場合、プロセスキャッシュ登録済みビット４２３は登録済を示す値（例えば１）、プロセスキャッシュ登録中ビット４２４の値は無視し、ＦＩＦＯキューエンプティビット４２２は空ではない値（例えば０）を示している。
前記（１）、（２）いずれかの状況になったエントリがあれば、対応するＦＩＦＯキュー５０５に登録されている固有情報４０１と、タグ５０２の解析情報４０２、抽出情報４０３を読出して結合してトークンに戻し、登録ＦＩＦＯキュー番号４５１（タグ５０２のエントリ番号にも対応している）と一緒に出力データ生成部２０４へ渡す。尚、あるフローの（２）の状態のパケットを、異なるフローの（１）もしくは（２）の状態のパケットは追い越しを行うことができる。基本的には、（１）の状態のエントリのトークンを優先的に出力データ生成部２０４へ渡すことで、プロセスキャッシュになるべく早期にエントリ登録を実現する。
尚、ＦＩＦＯキュー５０５は、メモリ容量が許すのであれば固有情報４０１だけでなく解析情報４０２と抽出情報４０３を記録しておいてもよい。また、読出しを行ったＦＩＦＯキュー５０５が空になる場合、対応するＦＩＦＯキュー情報４３０を消し、タグ登録情報４２０のＦＩＦＯキューエンプティビット４２２に空を示す値（例えば1）を設定する。
【００３７】
図５の複数のＦＩＦＯキュー５０５にトークンが溜まり、複数のＦＩＦＯキュー５０５からトークン送信可能な状況について説明する。前記状況が発生した時、プロセスキャッシュ登録済みビット４２３が登録済みを示す値（例えば１）になった順に該当するＦＩＦＯキュー５０５からトークンを取り出すＦＩＦＯ出力方式や、取り出し順番をトークン毎もしくは複数のトークン毎に順番に変えていくＲＲ（Ｒｏｕｎｄ Ｒｏｂｉｎ）方式が簡易であるが、タグ登録情報４２０の優先順位情報４２５を利用し、従来から用いられる様々な出力方式をとることで優先度の高いフロー及び優先度の低いフローの間でサービスに差をつけることが可能となる。例えば、優先順位情報４２５にＫ種類（例えば、Ｈｉｇｈ・Ｍｉｄｄｌｅ・Ｎｏｒｍａｌ・Ｌｏｗの4種類）の優先順位情報を加えることでＰＱ（Ｐｒｉｏｒｉｔｙ Ｑｕｅｕｉｎｇ）が実現できる。取り出し時にトークンの元となるパケットサイズをトークンの固有情報４０１から判定し、例えば閾値として設定するサイクルの中で出力候補となったＦＩＦＯキュー５０５からの出力パケットサイズの和が公平となるように重み付けを行うＷＦＱ（Ｗｅｉｇｈｔｅｄ Ｆａｉｒ Ｑｕｅｕｉｎｇ）方式等を適用することが可能である。
【００３８】
同様に、図４タグ登録情報４２０の帯域情報４２６とトークンの固有情報４０１に含まれるパケットサイズを利用し、送信可能なＦＩＦＯキューから、設定された帯域までの間でＦＩＦＯキュー５０５から送信を行うことが可能である。例えば、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）におけるＣＢＲ（Ｃｏｎｓｔａｎｔ Ｂｉｔ Ｒａｔｅ）サービスクラスに対応するためには、当該ＦＩＦＯキュー５０５が出力可能になったときに、帯域情報４２６で指定された値に相当する期間だけ、当該ＦＩＦＯキュー５０５にキャッシュ型パケット処理部１０３への出力パスを占有させ、期間終了後に次のＦＩＦＯキュー５０５へ前記出力パスを渡す。また、ＡＴＭにおけるｒｔ−ＶＢＲ（Ｒｅａｌ Ｔｉｍｅ Ｖａｒｉａｂｌｅ Ｂｉｔ Ｒａｔｅ）サービスクラスに対応するためには、当該ＦＩＦＯキュー５０５が出力可能になったときに、帯域情報４２６で指定された値に相当する期間が終了しても当該ＦＩＦＯキュー５０５にトークンがあれば、続けてキャッシュ型パケット処理部１０３への出力パスを占有させる。また、ＡＴＭにおけるｎｒｔ−ＶＢＲ（Ｎｏｎ Ｒｅａｌ Ｔｉｍｅ Ｖａｒｉａｂｌｅ Ｂｉｔ Ｒａｔｅ）サービスクラスに対応するためには、当該ＦＩＦＯキュー５０５が出力可能になったときに、帯域情報４２６で指定された値に相当する期間が終了しても当該ＦＩＦＯキュー５０５にトークンがあれば、帯域情報４２６に追加で指定される値までの追加期間分、前記ＦＩＦＯキュー５０５からの出力を可能とする。その他のサービスクラスにも対応可能である。
【００３９】
図５のハッシュ部５０１は、無数にあるパケットフローをプロセスキャッシュのエントリ数まで縮約するため、トークンにハッシュをかけた結果、異なるフローが同一のプロセスキャッシュのエントリに割り当てられる状況が発生する。図５の構成は、ハッシュして得られた値によるタグ５０２の割り当て位置が一意に決まるダイレクトマップ方式の構成である。ダイレクトマップ方式は実装が容易であり、データの読出しに不要な選択論理が入らないため高速であるメリットがあるが、異なるフローに属するトークンが同一エントリに割り当てられる状況が発生しやすくキャッシュのヒット率の向上の点からは不利である。
そこで、同一エントリの割り当てが発生してもキャッシュヒットにできるように、タグ及びＦＩＦＯキュー部分をＮ個持たせる（Ｎウェイ・）セット・アソシアティブ方式をとることも可能である。（Ｎウェイ・）セット・アソシアティブ方式では、図１１に示すように、ハッシュして得られた値による割り当て位置をＮ個まで増加させることができる。（Ｎウェイ・）セット・アソシアティブ方式のタグ及びＦＩＦＯキューを用いた場合、トークンにハッシュをかけた結果、未登録のウェイがあれば、前記未登録ウェイへトークンを登録する。Ｎ箇所全ての割り当て箇所が既登録であれば、任意のウェイを選択して上書きする。尚、キャッシュに登録されている情報が可能な限り有効に利用されるよう、前記任意ウェイを選択するためには、通常のプロセッサで利用されるキャッシュ同様、最も利用されていないエントリを選択するＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）アルゴリズムや一番古いエントリを選択するためのＦＩＦＯ(Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ)アルゴリズム等を実装する。ＬＲＵアルゴリズムを正確に実装するためには一エントリあたりＮ！（Ｎの階乗）ビット、ＦＩＦＯアルゴリズムを正確に実装するためには一エントリあたりＬｏｇ２Ｎビットの情報が必要になる。
【００４０】
ダイレクトマップ方式でも、（Ｎウェイ・）セット・アソシアティブ方式の場合でも、異なるフローが同一エントリを要求し、尚且つ対応するエントリが全て利用中であるケースが発生する。前記状況が発生した場合、当該エントリのタグ登録情報４２０のＦＩＦＯキューエンプティビット４２２、プロセスキャッシュ登録済みビット４２３、プロセスキャッシュ登録中ビット４２４を利用してトークンの登録を制御する。
当該エントリを後発のトークンにより上書きしても構わないのは、第一の場合として、タグ５０２の対応するエントリが空いている場合である。第二の場合として、タグ５０２の対応するエントリにフローが登録されているが、対応するＦＩＦＯキューに処理すべきトークンが全く無い場合である。即ち、第一の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録済みビット４２３が未登録を示す値（例えば０）であり、尚且つプロセスキャッシュ登録中ビット４２４が登録中でないことを示す値（例えば０）である場合」である。また、第二の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録済みビット４２３が登録済みを示す値（例えば１）であり、尚且つ、ＦＩＦＯキューエンプティビット４２２が、ＦＩＦＯキューが空であることを示す値（例えば１）の場合」である。
【００４１】
当該エントリを後発のトークンにより上書きしてはならないのは、第一の場合として、タグ５０２の対応するエントリにフローが登録されており、尚且つ対応するＦＩＦＯキューに処理すべきトークンが溜まっている状態である。第二の場合として、タグ５０２の対応するエントリにフローの先頭のパケットのみが登録されており、前記先頭のパケットの処理をキャッシュ型パケット処理部１０３に要求している状態である。即ち、第一の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録済みビット４２３が登録済みを示す値（例えば１）であり、尚且つ、ＦＩＦＯキューエンプティビット４２２が、ＦＩＦＯキューが空でないことを示す値（例えば０）の場合」である。また、第二の場合とは、「タグ５０２の当該エントリのプロセスキャッシュ登録中ビット４２４が登録中を示す値（例えば１）の場合」である。
【００４２】
当該エントリのタグ５０２が利用中で上書きできない場合、上書きできなかったトークン以降のタグ５０２で競合を起こすトークンだけを登録する。登録する内容は図４の４４０に示すように、トークンの固有情報４０１、解析情報４０２、抽出情報４０３とエントリが有効であることを示す有効ビット４４１である。この方法は、上書きできる別のフローのトークンのタグ５０２へのアクセスを停止させないため、トークンの処理効率が低下しないことを期待できる。尚、待機バッファ５０７は、競合を起こしたエントリを監視し、上書きできる状態になったらパケット解析部２０２からタグ５０２へのトークン供給を停止させ、待機バッファ５０７から優先して先頭のトークンをタグ５０２へアクセスさせる。
【００４３】
前記の待機バッファ５０７の実装が困難な場合、トークンの処理効率は低下するが、別の実施例として、上書きできなかったトークン及び、それ以降のトークンは全て待機バッファ５０７に登録する方法がある。待機バッファ５０７は、競合を起こしたエントリを監視し、上書きできる状態になったらパケット解析２０２からのトークン供給を停止し、待機バッファ５０７から優先して先頭のトークンをタグ５０２参照に利用する。
【００４４】
トークンを受け取った出力データ生成部２０４は、受信したトークン４００に、登録ＦＩＦＯキュー番号４５１、プロセスキャッシュに登録が完了したことを示すプロセスキャッシュ登録済みビット４２３、後述のプロセスキャッシュをセット・アソシアティブ方式にする場合のウェイ番号の情報４５３、前記トークンに対応する元のパケット４５４を付加して図４の４５０の形式にして出力インタフェース２０５に渡し、キャッシュ型パケット処理部１０３へ送信する。プロセスキャッシュ登録済みビット４２３は、プロセスキャッシュにフローが未登録の状態であれば、キャッシュ未登録状態を示す値（例えば０）を、フローが既に登録されていれば、キャッシュ登録済み状態を示す値（例えば１）が書き込まれている。
【００４５】
以後、キャッシュ用トラフィック制御部１０２は、当該トークンのプロセスキャッシュ登録完了通知を待機する。前記待機状態時にも、異なるフローの先頭トークンや、プロセスキャッシュに登録済みのトークンはキャッシュ用トラフィック制御部１０２からキャッシュ型パケット処理部１０３へ送信される。登録完了通知は信号２０８により行い、プロセスキャッシュ登録が完了していれば、対応するタグ５０２のエントリのプロセスキャッシュ登録中ビット４２４を登録中ではないことを示す値（例えば０）に設定し、プロセスキャッシュ登録済みビット４２３を登録が完了したことを示す値（例えば１）に設定し、当該ＦＩＦＯキューの二つ目以降のトークンを発行可能にする。また、プロセスキャッシュ登録がなんらかの理由によりできなかった場合、前記プロセスキャッシュ登録済みビット４２３は登録がされていない状態のまま（例えば０）であり、当該ＦＩＦＯキューの二つ目のトークンが再び先頭のトークンと同様に扱われる。
【００４６】
次に図３のキャッシュ型パケット処理部１０３の実施例について、構成とパケット処理動作について説明する。キャッシュ型パケット処理部１０３は、一実施例として、入力インタフェース３０１、解析部３０２、プロセスキャッシュ３０３、キャッシュミス処理部３０４、パケット処理部３０５、後処理部３０６、出力インタフェース３０７、パケットメモリ３１０、テーブルメモリ３２０から構成される。前記のキャッシュ型パケット処理部１０３の構成要素は、低レイテンシかつ高速なパケット処理を実現するには単一のチップ上に実装するのが望ましい。パケットメモリ３１０とテーブルメモリ３２０についても、例えば、混載ＤＲＡＭ技術や１Ｔ−ＳＲＡＭ技術等の高密度実装可能な高速オンチップメモリを利用してキャッシュ型パケット処理部１０３の他の構成要素と同一チップ上に実装するのが望ましいが、パケットメモリ３１０とテーブルメモリ３２０の一部もしくは全てをチップ外部に実装する選択肢もある。
【００４７】
入力インタフェース３０１は、図４の４５０の形式でトークンとパケットを受信する。次に解析部３０２を利用し、受信したトークン及びパケット４５０のプロセスキャッシュ登録済みビット４２３を参照し、前記ビット４２３が登録済みを示す値（例えば１）であれば、プロセスキャッシュにトークン及びパケットを渡す。前記プロセスキャッシュ登録済みビット４２３が未登録を示す値（例えば０）であれば、キャッシュミス処理部へトークンとパケットを渡す。
まず、キャッシュ登録済みのトークンの処理に関して説明する。キャッシュ登録済みのトークンは、パケット処理部３０５で処理する必要が無いため、プロセスキャッシュ３０３に渡される。プロセスキャッシュ３０３は一実施例として図７に示すように、ハッシュ部５１１、プロセスキャッシュデータ部５１２、結合部５１３により構成される。本実施例では、プロセスキャッシュのタグ部分はキャッシュ用トラフィック制御部１０２に配置するため、キャッシュ型パケット処理部１０３のプロセスキャッシュ３０３はデータ部分のみを持つだけでよい。ハッシュ部５１１は、キャッシュ用トラフィック制御部１０２のタグ５０２へのトークン振分を行うハッシュ部５０１と同一のハッシュを利用する。プロセスキャッシュデータ部５１２には、プロセッサで処理後のパケット抽出情報α４１１と処理情報４１２により構成される置換トークン情報（図４の４７０）が格納される。
【００４８】
抽出情報α４１１は、パケットが利用するアドレスの書換えや新規追加ヘッダ等の情報であり、元の抽出情報４０３を上書きする形で生成される。変更が無ければ抽出情報４０３のままである。尚、新規追加ヘッダには、例えば、ＭＰＬＳのシムヘッダ、ＶＬＡＮのヘッダ、ＩＰｖ４やＩＰｖ６等のカプセリング用のヘッダ等がある。
処理情報４１２は、トークン４１０を元のパケットに対してどのように適用するかを示す情報である。例えば、抽出情報α４１１に入っている情報のサイズと前記情報をパケットのどの位置にどのように、即ち挿入するのか置換するのか、または削除するのかを示し、またパケットの廃棄指示を出したり、アドレス変換操作を支持したり、ＱｏＳ情報やスイッチファブリック１１やネットワークインタフェース１０１の出力ポートを指定したりするのに利用する。
プロセスキャッシュデータ５１２を参照するトークンは既にヒットすることが判明している状態であり、本参照により得た置換トークン情報４７０と、参照に利用したトークンの固有情報４０１、解析情報４０２により、パケット処理用トークン（図４の４１０）を結合器５１３により生成し、後処理部３０６へ渡す。
【００４９】
図７のプロセスキャッシュはダイレクトマップ方式であるが、キャッシュ用トラフィック制御部１０２のトラフィック管理部２０３が（Ｎウェイ・）セット・アソシアティブ方式を採用する場合には、図８に示すようにキャッシュ方パケット処理部のプロセスキャッシュのデータ部３０３も（Ｎウェイ・）セット・アソシアティブ構成をとる。
【００５０】
次に、キャッシュ未登録のトークンの処理に関して説明する。キャッシュ未登録のトークンは、パケット処理部３０５で必要な処理を実施する必要がある。このため、キャッシュミス処理部３０４に渡される。キャッシュミス処理部３０４は一実施例として図９に示すように、キャッシュミス管理テーブル７０１、処理情報管理テーブル７０３、結合器７０４で構成される。初期ミステーブル７０１は、受信したトークンの固有情報４０１、解析情報４０２、抽出情報４０３、登録ＦＩＦＯキュー番号４５１、キャッシュウェイ情報４５３を記録し、パケット処理部３０５へ、前記トークンとそれに付随するパケットを渡す。
【００５１】
パケット処理部３０５は、必要であれば、受信したトークン及びパケットをパケットメモリ３１０へ記録する。パケット処理部３０５の構成方法には様々な手法があるが、代表的なものとして、複数のプロセッサを集積しており、トークン及びパケットを次々に受信しても、複数のプロセッサで並列処理することにより高いスループットを維持することが可能である。パケット処理部３０５が実施する処理は、比較的レイテンシの長いメモリ参照を伴うものである。具体的には、テーブルメモリ３２０に格納される変換テーブルを参照して当該パケットの転送先を決定するための経路検索や、パケットを通過させるか否か決定するためのフィルタリング処理、転送先のネットワーク装置が処理可能なパケットフォーマットに変換するためのカプセリング処理、ＭＰＬＳのヘッダ追加・置換・削除処理、ＶＬＡＮ用ヘッダ追加・置換・削除処理、アドレス変換処理等である。メモリ参照の結果が返ってくるまでプロセッサの演算器は利用されない状態であり、プロセッサの利用効率は低下しがちである。そこで、プロセッサをマルチスレッド化して複数のアーキテクチャレジスタを具備させ、あるパケットを処理するスレッドがメモリ参照にいったら、別のパケットを処理するスレッドに切替え、演算器が有効利用可能な手法も可能である。いずれにしても、パケットに対して必要な処理を終了すると、その結果をトークンの抽出情報α４１１と処理情報４１２として生成し、キャッシュミス処理部３０４へ返す。
尚、パケット処理部で扱うには処理時間があまりに長すぎる、複雑すぎる、またはネットワーク装置の転送系ではなく制御系の処理であると判断される処理は、外部に設置するホストプロセッサ等へ要求をあげることができる。例えば、経路情報を更新・維持するためのＲＩＰ(Ｒｏｕｔｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｔｏｃｏｌ)やＯＳＰＦ(Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ)等のプロトコル処理等があげられる。
【００５２】
キャッシュミス処理部３０４は、パケット処理部３０５から処理済のトークン４７０を受信すると、処理情報テーブル７０３に登録する。そして、キャッシュミス管理テーブル７０１から、対応するトークンの登録ＦＩＦＯキュー番号４５１、キャッシュウェイ情報４５３を読出し、対応するプロセスキャッシュデータのエントリを決定し、処理情報テーブル７０３の抽出情報α４１１と処理情報４１２をプロセスキャッシュデータ５１２へ登録する。また、プロセスキャッシュに当該トークンの登録が完了したことをキャッシュ用トラフィック制御部１０２へ通知するための情報として信号２０８により、登録ＦＩＦＯキュー番号４５１とキャッシュ可能ビット４６１、更に、オプションとして当該フローの優先順位を示す優先順位情報４２５、当該フローに許される利用帯域幅を示す帯域情報４２６により構成されるデータ（図４の４６０）を信号２０８によりキャッシュ用トラフィック制御部１０２へ渡す。ここで、キャッシュ可能ビット４６１は、パケット処理部で処理した結果、プロセスキャッシュに登録可能なトークンであったことを示す場合（例えば１）と何らかの理由により登録できないトークンであったことを示す場合（例えば０）で値が異なる。通常は、プロセスキャッシュに登録可能であることを想定しているが、元のパケットに対してハードウェアで対応困難な、複雑なソフトウェア処理を施す必要ある場合等にはプロセスキャッシュには登録せず、全てパケット処理部で処理する。
また、パケット処理部で処理したトークンは、キャッシュミス管理テーブル７０１から、対応するトークンの固有情報４０１及び解析情報４０２、処理情報テーブル７０３から抽出情報α４１１と処理情報４１２を読出し、結合器７０４にて結合して後処理部３０６へ渡す。
【００５３】
以上のように、後処理部３０６は、プロセスキャッシュ３０３もしくはキャッシュミス処理部３０４から処理済トークン４１０を受信する。両方から同時に処理済トークン４１０を受信する場合は、同一フローの中でのパケットの順番を変えないためにキャッシュミス処理部３０４からの受信を優先する。
後処理部３０６は、受信したトークンの解析情報４０２、処理情報４１２を参照し、当該トークンを生成する元になったパケット４５４に対して必要な処理を実施する。パケットに対して新規に追加するヘッダ、もしくはヘッダの中に置換すべき情報がある場合、当該トークンの抽出情報α４１１に対応する情報があるため、解析情報４０２及び処理情報４１２にある情報を元にパケットヘッダの修正を実施する。
【００５４】
最後に、出力インタフェース部３０７において、パケットを送出できる形式に変換して出力する。このときネットワークプロセッサアクセラレータの先にスイッチファブリックが繋がっているならば、スイッチファブリック用のヘッダ情報をパケットに付加する。例えば、スイッチファブリックのポート番号等が含まれるが、これは、トークンの中の抽出情報α４１１、または処理情報４１２に含まれているので、それを利用すればよい。ネットワークインタフェースが繋がっているならば、そのネットワークインタフェースがサポートするレイヤ２、もしくはレイヤ３の形式にパケットを変換して出力する。尚、出力先ネットワークインタフェースが
複数の出口を持つ場合には、やはりトークンに含まれているポート番号を利用して出口のネットワークインタフェースを決定する。
【００５５】
以上、キャッシュ用トラフィック制御部１０２とキャッシュ型パケット処理部１０３を別チップに実装する例を示したが、両部分を図１０に示すように単一のチップ上に実装してもよい。この場合、キャッシュ用トラフィック制御部とキャッシュ型パケット処理部の間に専用インタフェースが不要になる。
【実施例２】
【００５６】
キャッシュを利用する場合、異なる複数のデータによりキャッシュメモリ上の同一エントリばかりが集中的に利用され、互いのデータがキャッシュエントリを書き潰しあうスラッシングと呼ばれる状況が発生し、キャッシュエントリの入れ替えが頻繁に発生する結果、キャッシュの利用効率が低下することがある。実施例１で述べた（Ｎウェイ・）セット・アソシアティブ方式のプロセスキャッシュ及びそれに対応するトラフィック管理部のＦＩＦＯキューは、スラッシングを低減するための仕組みであるが、特定のエントリに対しては実装可能な小さめのＮの値ではスラッシング抑止に不十分である可能性がある。
そこで、本発明のキャッシュ用トラフィック制御部の第二の実施の形態として、前記のスラッシングによる性能低下を防ぐために、小容量のフル・アソシアティブ・プロセスキャッシュと前記小容量フル・アソシアティブ・プロセスキャッシュに対応するタグ及びＦＩＦＯキューを具備するキャッシュ用トラフィック制御部の実施例を示す。
【００５７】
フル・アソシアティブ・プロセスキャッシュとは、エントリ総数がＭ個ある場合、登録するエントリをＭ箇所のうちのどこへでも対応付けることができるプロセスキャッシュのことを指す。フル・アソシアティブ方式はダイレクトマップ方式及び（Ｎウェイ・）セット・アソシアティブ方式と比較して最も柔軟なキャッシュエントリ関連付けの方式であり、キャッシュのヒット率を最も高くすることができる。しかし、エントリの登録場所が一意に決まらないために、高速動作させるためには全エントリを同時に比較するために全エントリ数分の比較器を持つ必要があるため、実装のコストが高い。前記理由により（Ｎウェイ・）セット・アソシアティブ方式のキャッシュをサポートするために小規模のフル・アソシアティブ方式のキャッシュを実装するのが現実的である。
【００５８】
本実施例２では、図３においてトラフィック管理部２０３の内部構成として図６で示した（Ｎウェイ・）セット・アソシアティブのタグ５０２及びＦＩＦＯキュー５０５に加え、フル・アソシアティブの連想タグ６０１及び対応するＦＩＦＯキュー６０２を持つ図１１で示す構成をとる。連想タグ６０１は各エントリが内部に比較器を持ち、各エントリが独立してヒットチェックが可能である。連想タグ６０１の実現には、ＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）の利用が適切である。また、対応する図３のプロセスキャッシュ３０３も内部構成として図８で示した（Ｎウェイ・）セット・アソシアティブのデータ５１２に加え、前記フル・アソシアティブの連想タグ６０１に対応する連想データ６１０を持つ図１２で示す構成をとる。
【００５９】
本実施例２におけるトラフィック管理部２０３の動作について説明する。パケット解析部２０２よりトークンを受信すると、ハッシュ部５０１によりハッシュをかけたトークンでセット・アソシアティブ方式のタグ５０２、同時にハッシュをかけない元のままのトークンで連想タグ６０１を参照する。本実施例２では、状況に応じた、次の二種類の管理方法がトークンに適用される。
（１）セット・アソシアティブ方式のタグ５０２でヒットする場合、もしくはミスするがセット・アソシアティブ方式のタグ５０２に利用されていないウェイがある場合は、実施例１と同様にセット・アソシアティブ方式のタグ５０２及びそれに付随するＦＩＦＯキュー５０５でトークンの管理を行う。
（２）セット・アソシアティブ方式のタグ５０２でミスして、尚且つ利用できるエントリがない場合は、連想タグ６０１の利用されていないエントリを利用してトークンの管理を行う。
【００６０】
フル・アソシアティブ・プロセスキャッシュへのエントリ格納位置を指定するために、図４のキャッシュ用トラフィック制御部からキャッシュ型パケット処理部への伝達情報４５０に、「フル・アソシアティブ・プロセスキャッシュ・エントリ情報」が付加される。前記フル・アソシアティブ・プロセスキャッシュ・エントリ情報は、キャッシュ型パケット処理部が持つプロセスキャッシュデータのデータ格納エントリを決定するために利用する。
本実施例２では、実施例１と比較して、短時間の間にプロセスキャッシュの同一エントリばかりが異なるフロー群のパケットで集中的に利用されるケースで有利となる。
【実施例３】
【００６１】
実施例１、及び実施例２では実装効率を重視し、プロセスキャッシュメモリのタグ部分をキャッシュ型パケット処理部から分離してキャッシュ用トラフィック制御部に配置する例を示した。図１のキャッシュ型パケット処理部１０３は、プロセスキャッシュメモリのタグ部分とデータ部分を完全に備える形式であってもよい。そこで、図１３に実施例３として、キャッシュ型パケット処理部１０３のプロセスキャッシュメモリがデータ部分だけではなく、タグ部分も併せ持つ構成を示す。
本実施例３において、キャッシュ用トラフィック制御部１０２の構成は、実施例１もしくは実施例２と同一であるが、出力データ生成部２０４は、キャッシュ型パケット処理部１０３へ情報を渡す時、図4の４５０から固有情報４０１、解析情報４０２、抽出情報４０３を取り除いた形式で渡す。
【００６２】
本実施例３において、キャッシュ型パケット処理部１０３は、キャッシュ用トラフィック制御部１０２のパケット解析部２０２と同等の機能を持つパケット解析部３０２を具備する。前記解析部３０２において、キャッシュ用トラフィック制御部１０２からの受信パケットを解析し、図４に示すトークン４００を生成する。また、タグ部分とデータ部分を持つプロセスキャッシュ３０３を具備する。前記プロセスキャッシュ３０３の構成をダイレクトマップ方式の場合を例にとり図１４に示す。プロセスキャッシュ３０３は、タグ部５０２及びデータ部５１２両方を具備し、トークンからアクセスキーを生成するためのハッシュ部５０１、比較器５０３、結合器５１３を具備する。
【００６３】
前記プロセスキャッシュ３０３は、トークン４００を受信するとトークンの解析情報４０２と抽出情報４０３の組全体に対してハッシュ部５０１によりハッシュをかけ、プロセスキャッシュのタグ部５０２及びデータ部５１２へのアクセスキーを生成し、タグ部５０２を参照する。そして、タグ部５０２より出力される解析情報４０２と抽出情報４０３の組と、アクセスキー生成に利用した前記トークンの解析情報４０２と抽出情報４０３の組を比較器５０３により一致検査を行い、一致すればプロセスキャッシュにヒット、一致しなければプロセスキャッシュにミスとして扱う。プロセスキャッシュヒット時には、データ部５１２からの出力である抽出情報α４１１及び処理情報４１２とアクセスキー生成に利用した前記トークンの固有情報４０１及び解析情報４０２を結合器５１３により結合し、後処理部３０６へ渡す。プロセスキャッシュミス時には、トークンをキャッシュミス処理部３０４へ渡し、パケット処理部３０５で処理後、プロセスキャッシュ３０３に処理結果のトークン４７０を登録する。そして、実施例１、実施例２と同様に図４の４６０に示す形式でキャッシュ登録完了通知を信号２０８により伝える。
【実施例４】
【００６４】
実施例４として、実施例３からプロセスキャッシュ登録完了通知２０８を取り除いた構成例を挙げる。この場合、キャッシュ用トラフィック制御部１０２は、フローの二つ目以降のパケットの正確な発行タイミングがわからないため、図１５に示すように、トラフィック管理部２０３の各エントリにタイマ５２０を設け、タイマが閾値を超えたら、キャッシュ型パケット処理部１０３のプロセスキャッシュ３０３に登録されている可能性が高いとして発行を開始する。
【００６５】
本実施例４では、プロセスキャッシュへフローの先頭パケットの処理結果が登録されたことを保証できないため、本来の目的である同一フローのパケットが連続到着した時にプロセスキャッシュのヒット率低下を完全に抑止することはできない。
【００６６】
しかしながら、本実施例４を用いると、キャッシュ型パケット処理部１０３が、キャッシュ用トラフィック制御部１０２の存在を意識しない構成をとることができる。このため、キャッシュ型パケット処理部１０３だけを搭載したネットワーク装置に、本発明のキャッシュ用トラフィック制御部１０２の機能を含むデバイスを追加搭載して前記ネットワーク装置のアップグレード（キャッシュヒット率低下の抑止）を図ることが可能になる。
【実施例５】
【００６７】
プロセスキャッシュにミスするパケットは全てパケット処理部で処理される。一実施例としては、パケット処理部の負荷も高くなることを想定し、よりスループットの高い（処理速度の速い）キャッシュ型パケット処理部のパケット処理部が必要になることがある。この場合、図１０からパケット処理部を３０５、パケットメモリ３１０、テーブルメモリ３２０を図１６に示すように別チップとして実装する方式がある。この場合、パケット処理部を複数のキャッシュ型パケット処理部で共有してもよい。トラフィック管理部２０３の方式は、実施例１、実施例２、実施例３及び実施例４いずれでも構わない。
尚、図１６においてキャッシュ用トラフィック制御部とキャッシュ型パケット処理部を更に分割して実装してもよい。
【００６８】
以上、本発明によるネットワークプロセッサアクセラレータを利用したネットワーク装置および、ネットワークプロセッサアクセラレータそのものの一実施例を説明した。本説明はあくまで一実施例の説明であり、本発明の範囲を限定するものではなく、様々な変形例に対して適用可能である。
【産業上の利用可能性】
【００６９】
本発明のキャッシュ用トラフィック制御部は、ネットワーク上を流れるパケットやフレーム等のデータを転送処理するためにキャッシュ型のパケット処理部を持つネットワーク装置への利用が可能である。本発明のキャッシュ用トラフィック制御部をキャッシュ型パケット処理部とあわせて用いることにより、ネットワーク装置へのネットワークトラフィックの到着順序により発生するキャッシュミス、および前記キャッシュミスによるネットワーク装置の処理速度低下を無くすことができる。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施の形態１における、キャッシュ用トラフィック制御部とキャッシュ型パケット処理部を持つネットワーク装置のブロック図である。
【図２】従来のトラフィック制御部とパケット処理部を持つネットワーク装置のブロック図である。
【図３】本発明の実施形態１における、キャッシュ用トラフィック制御部とキャッシュ型パケット処理部の内部ブロック図である。
【図４】キャッシュ用トラフィック制御部及びキャッシュ型パケット処理部の内部で用いるデータフォーマット一覧である。
【図５】ダイレクトマップ方式のキャッシュ用トラフィック制御部のトラフィック管理部部分のブロック図である。
【図６】Ｎウェイ・セット・アソシアティブ方式のキャッシュ用トラフィック制御部のトラフィック管理部部分のブロック図である。
【図７】ダイレクトマップ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ構造例である。
【図８】Ｎウェイ・セット・アソシアティブ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ構造例である。
【図９】キャッシュ型パケット処理部のキャッシュミス処理部のブロック図である。
【図１０】キャッシュ用トラフィック制御部とキャッシュ型パケット処理部を一体化した場合のブロック図である。
【図１１】Ｎウェイ・セット・アソシアティブ方式のキャッシュ用トラフィック制御部のタグ及びＦＩＦＯキュー部分にＭエントリのフル・アソシアティブ方式のキャッシュ用トラフィック制御部のタグ及びＦＩＦＯキュー部分を追加した場合のブロック図である。
【図１２】Ｎウェイ・セット・アソシアティブ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ部分にＭエントリのフル・アソシアティブ方式のキャッシュ型パケット処理部のプロセスキャッシュのデータ部分を追加した場合のブロック図である。
【図１３】キャッシュ型パケット処理部のプロセスキャッシュがタグ部分も持つ場合のキャッシュ用トラフィック制御部及びキャッシュ型パケット処理部のブロック図である。
【図１４】タグ部及びデータ部を具備するダイレクトマップ方式のプロセスキャッシュのブロック図である。
【図１５】図１４におけるキャッシュ用トラフィック制御部のトラフィック管理部部分のブロック図である。
【図１６】図１０において、キャッシュ型パケット処理部のパケット処理部分をキャッシュ型パケット処理部から分離した場合のブロック図である。
【符号の説明】
【００７１】
１０：ネットワークインタフェースカード
１１：スイッチファブリック
１０１：ネットワークインタフェース部
１０２：キャッシュ用トラフィック制御部
１０３：キャッシュ型パケット処理部
１１０：パケット処理部（ネットワークプロセッサ）
１１１：トラフィック制御部（トラフィックマネージャ）
２０１：キャッシュ用トラフィック制御部のパケット入力インタフェース
２０２：キャッシュ用トラフィック制御部のパケット解析部
２０３：キャッシュ用トラフィック制御部のトラフィック管理部
２０４：キャッシュ用トラフィック制御部の出力データ生成部
２０５：キャッシュ用トラフィック制御部のパケット出力インタフェース
２０８：キャッシュ型パケット処理部からキャッシュ用トラフィック制御部へのプロセスキャッシュ登録通知信号
２１０：キャッシュ用トラフィック制御部のパケットメモリ
３０１：キャッシュ型パケット処理部のパケット入力インタフェース
３０２：キャッシュ型パケット処理部のパケットの解析部
３０３：キャッシュ型パケット処理部のプロセスキャッシュ
３０４：キャッシュ型パケット処理部のキャッシュミス処理部
３０５：キャッシュ型パケット処理部のパケット処理部
３０６：キャッシュ型パケット処理部の後処理部
３０７：キャッシュ型パケット処理部のパケット出力インタフェース
３１０：キャッシュ型パケット処理部のパケットメモリ
３２０：キャッシュ型パケット処理部のテーブルメモリ
４００：キャッシュ用トラフィック制御部のパケット解析部で生成するトークン
４０１：トークンの固有情報
４０２：トークンの解析情報
４０３：トークンの抽出情報
４１０：キャッシュ型パケット処理部の後処理部で利用されるトークン
４１１：パケット処理部で修正されたトークンの抽出情報である抽出情報α
４１２：パケット処理部で生成されたトークンの処理情報
４２０：キャッシュ用トラフィック制御部のタグ
４２１：４２０の有効ビット
４２２：４２０のＦＩＦＯキューエンプティビット
４２３：プロセスキャッシュ登録済みビット
４２４：４２０のプロセスキャッシュ登録中ビット
４２５：４２０の優先順位制御情報
４２６：４２０の帯域制御情報
４３０：キャッシュ用トラフィック制御部のＦＩＦＯキューの登録内容
４３１：４３０の有効ビット
４４０：キャッシュ用トラフィック制御部の待機バッファの登録内容
４４１：４４０の有効ビット
４５０：キャッシュ用トラフィック制御部からキャッシュ型パケット処理部へ転送する情報
４５１：４５０の登録ＦＩＦＯキュー番号
４５３：４５０のウェイ情報
４５４：４５０のオリジナルパケット
４６０：キャッシュ型パケット処理部からキャッシュ用トラフィック制御部へ転送する情報
４６１：４６０のキャッシュ可能ビット
４７０：キャッシュ型パケット処理部のプロセスキャッシュのデータ部分に登録するトークン
５０１：キャッシュ用トラフィック制御部のアクセスキーを生成するハッシュ部
５０２：キャッシュ用トラフィック制御部のタグ（プロセスキャッシュのタグ）
５０３：キャッシュ用トラフィック制御部のタグ比較器
５０４：キャッシュ用トラフィック制御部のタグ及びＦＩＦＯキューの書込制御部
５０５：キャッシュ用トラフィック制御部のＦＩＦＯキュー
５０６：キャッシュ用トラフィック制御部のタグ及びＦＩＦＯキューの読出制御部
５０７：キャッシュ用トラフィック制御部の待機バッファ
５１１：キャッシュ用トラフィック制御部のアクセスキーを生成するハッシュ部
５１２：キャッシュ型パケット処理部のプロセスキャッシュのデータ部
５１３：キャッシュ型パケット処理部のプロセスキャッシュの結合器
５２０：キャッシュ用トラフィック制御部のＦＩＦＯキューのタイマ
６０１：キャッシュ用トラフィック制御部のフル・アソシアティブ方式のタグ
６０２：キャッシュ用トラフィック制御部のフル・アソシアティブ方式のＦＩＦＯキュー
６１０：キャッシュ型パケット処理部のフル・アソシアティブ方式のプロセスキャッシュのデータ部
７０１：キャッシュ型パケット処理部のキャッシュミス処理部のキャッシュミス管理テーブル
７０３：キャッシュ型パケット処理部のキャッシュミス処理部の処理情報管理テーブル
７０４：キャッシュ型パケット処理部のキャッシュミス処理部の結合器
９００：一体化したキャッシュ用トラフィック制御部とキャッシュ型パケット処理部
９０２：キャッシュ型パケット処理部の外部へのパケット処理部へのインタフェース
９０３：パケット処理部
９０４：パケットメモリ
９０５：テーブルメモリ。
【特許請求の範囲】
【請求項１】
入力されたパケットを分類しフローとして扱うための解析部と、
前記パケットに対して実施した処理をフロー毎に記録するための複数のエントリを有するキャッシュと、
前記キャッシュの前段に配置され、前記キャッシュのエントリと１対１に対応し、対応するエントリに割り当てられたフローに属するパケットを保持するフロー管理用のキュー群と、制御部を有し、該制御部は、
まず、前記キャッシュに未登録のフローの先頭のパケットの処理要求を出し、
次に、前記先頭パケットの処理結果が前記キャッシュに登録されたことの通知を受信した後
対応する前記キューに保持されているパケットを前記キャッシュにアクセスさせ、
更に、あるフローのパケットを保持している間に、他のフローの先頭パケットがあれば保持中の前記キャッシュ未登録フローを追い越して処理要求を出し、
あるフローの前記キャッシュ登録済みパケットがあれば、保持中の前記キャッシュ未登録フローを追い越して前記キャッシュにアクセスさせるように制御を行うことを特徴とするネットワーク装置。
【請求項２】
ネットワーク上で転送されるパケットをフローとして扱うためにパケットから内部処理情報列を生成し、
前記内部処理情報列が、
パケットと内部処理情報列を１対１に対応付ける情報、及びパケット毎に異なる情報を合わせた第一の情報と
前記パケットのネットワーク上での各階層におけるプロトコル種類を識別するための第二の情報と
前記パケットのネットワーク上での各階層に対応するヘッダから抽出した第三の情報と
で構成され、
前記第二の情報と前記第三の情報によりパケットをフロー分類し、
前記パケットに対して実施した処理を第四の情報として生成し、必要に応じて第三の情報を書換え、
前記第三、第四の情報をデータとしてフロー毎に記録し同一のフローに適用するためのキャッシュと、
前記キャッシュの前段に前記キャッシュのエントリと１対１に対応するフロー管理用のキュー群とを用いて、
前記キュー群は、割り当てられたフローに属するパケットを保持し、
まず、前記キャッシュに未登録のフローの先頭のパケットの処理要求を出し、
次に、前記先頭パケットの処理結果が前記キャッシュに登録されたことの通知を受信した後
対応する前記キューに保持されているパケットを前記キャッシュにアクセスさせ、
更に、あるフローのパケットを保持している間に、他のフローの先頭パケットがあれば保持中の前記キャッシュ未登録フローを追い越して処理要求を出し、
前記あるフローの前記キャッシュ登録済みパケットがあれば、保持中の前記キャッシュ未登録フローを追い越して前記キャッシュにアクセスさせることを特徴とするネットワーク装置の制御方法。
【請求項３】
請求項１に記載のネットワーク装置において、
ハッシュ関数によりフロー分類した情報を割り当てるパケット処理を記録するキャッシュのタグ部分と
パケット処理を記録するキャッシュのデータ部分と
前記キャッシュのタグ部分及びデータ部分の各エントリに対応するフロー管理用のキューの
情報割り当て位置が複数（Ｎ）箇所ある（Ｎウェイ・）セット・アソシアティブ形式であることを特徴とするネットワーク装置。
【請求項４】
請求項１に記載のネットワーク装置において、
フロー分類した情報を割り当てるフロー管理用のキューが利用中である場合に、
前記フロー管理用キューが解放されるまで前記フロー分類した情報及び、
それ以降の全てのフローを待機させるために
前記全てのフローを一時的に保持するためのバッファを具備することを特徴とするネットワーク装置。
【請求項５】
請求項１に記載のネットワーク装置において、
フロー分類した情報を割り当てるフロー管理用のキューが利用中である場合に、
前記フロー管理用キューが解放されるまで前記フロー分類した情報及び、
それ以降の同一フローを待機させるために
前記同一フローを一時的に保持するためのバッファを具備することを特徴とするネットワーク装置。
【請求項６】
請求項１に記載のネットワーク装置において、
フロー分類した情報を管理するフロー管理用のキューのうち、
複数本の前記フロー管理キューからの情報取り出しが可能になった時、
情報に記載されている優先順位情報を参照して情報を取り出すフロー管理キューを選択可能であることを特徴とするネットワーク装置。
【請求項７】
請求項１に記載のネットワーク装置において、
フロー分類した情報を管理するフロー管理用のキューのうち、
複数本の前記フロー管理キューからの情報取り出しが可能になった時、
情報に記載されている帯域制御情報と情報のサイズを参照して
情報を出力する前記前記フロー管理キューからの出力量を制限することを特徴とするネットワーク装置。
【請求項８】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分と
フロー分類した情報を管理するフロー管理用のキューを含む部位と
を単一のデバイス上へ実装し、
パケット処理を記録するキャッシュのデータ部分を前記のデバイスとは異なるデバイス上へ実装することを特徴とするネットワーク装置。
【請求項９】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分と
フロー分類した情報を管理するフロー管理用のキューを含む部位と、
パケット処理を記録するキャッシュのデータ部分と
を単一のデバイス上へ実装することを特徴とするネットワーク装置。
【請求項１０】
請求項１に記載のネットワーク装置において、
ハッシュ関数によりフロー分類した情報を割り当てる
パケット処理を記録するキャッシュのタグ部分と
パケット処理を記録するキャッシュのデータ部分と
前記キャッシュのタグ部分及びデータ部分の各エントリに対応するフロー管理用のキューの
情報割り当て位置が一つ以上あり、
更に、前記フロー分類後の割り当て位置が利用中であった場合に
自由に割り当て可能なフル・アソシアティブ方式の小容量の
前記キャッシュのタグ部分と
前記キャッシュのデータ部分と
前記フロー管理用のキューと
を具備することを特徴とするネットワーク装置。
【請求項１１】
請求項８に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分に相当する機能を具備する部位が
フロー管理用のキューを具備するデバイス上に実装されており、
パケット処理を記録するキャッシュのデータ部分を具備するデバイス上には実装されていないことを特徴とするネットワーク装置。
【請求項１２】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分に相当する機能を具備する部位が
フロー管理用のキューを具備するデバイス上に実装されており、
尚且つ、前記タグ部分がパケット処理を記録するキャッシュのデータ部分を具備するデバイス上にも実装されていることを特徴とするネットワーク装置。
【請求項１３】
請求項１２に記載のネットワーク装置において、
パケット処理を記録するキャッシュに、パケット処理結果が登録されても、
フロー管理用のキューへキャッシュ登録通知信号を渡さず、
前記フロー管理用キューは、各キューがタイマを持ち、
前記フロー管理用キューの先頭のパケットをパケット処理部へ送信した後、
前記タイマをスタートさせ、設定された閾値を越えた時点で
前記フロー管理用キューに残っているパケットを前記キャッシュへアクセスさせることを特徴とするネットワーク装置。
【請求項１４】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュに渡すパケット処理結果を生成するパケット処理部が前記キャッシュと異なるデバイス上に実装されていることを特徴とするネットワーク装置。
【請求項１５】
キャッシュメモリを用い、先行するパケットに関する処理結果をキャッシュメモリに記録し、先行するパケットと同一処理を行う後続のパケットの処理は該キャッシュメモリの内容を利用する、キャッシュ型のパケット処理方法であって、
パケットを受信するステップと、
該受信したパケットをフロー毎に分類するステップと、
該フロー毎に分類したパケットを、パケットの到着順序を維持してＦＩＦＯ型のキューにフロー毎に記録するステップと、
上記キュー内のフローの所定パケットがキャッシュに未登録である場合、該所定パケットを処理して処理結果をキャッシュメモリに格納するとともに、同一キュー内の所定パケット以降のパケットは、キューに待機させておくステップと、
上記所定パケットに関する処理結果のキャッシュメモリへの格納の完了の後に、上記キューに待機させておいたパケットの処理を行うステップと、
を有するパケット処理方法。
【請求項１６】
処理結果が該キャッシュメモリ未登録である各フローの先頭パケットは、他のフローで待機中のパケットを追い越して処理されることを特徴とする請求項１５記載のパケット処理方法。
【請求項１７】
各キューは対応するキャッシュを有しており、
各キューが対応するキャッシュの登録情報を記録するステップと、
キャッシュに未登録状態のキューにパケットが到着すると、先頭のパケットのみを処理し、処理結果が上記キャッシュに登録されるのを待つステップと、
二つ目以降のパケットは上記キャッシュへの登録が完了した時点で処理が開始されることを特徴とする請求項１５記載のパケット処理方法。
【請求項１８】
パケットを受信する入力インタフェースと、
受信したパケットを解析および分類して、種類毎にフローを生成するパケット解析部と、
上記生成されたフローを、種類毎にパケットの受信順序を保持して管理するトラフィック管理部と、
上記パケットを処理するパケット処理部と、
上記パケット処理部の処理結果を上記フロー毎に登録するプロセスキャッシュと、
を有するネットワーク装置であって、該ネットワーク装置は、
(1)上記プロセスキャッシュに処理結果が未登録な第１のフローの第１のパケットを、上記パケット処理部で処理し、
(2)上記第１のフローの第１のパケットに後続するパケットは、上記第１のパケットの処理結果が上記プロセスキャッシュに登録されるまで待機させ、登録の後、上記プロセスキャッシュの情報を用いて処理を行い、
(3)上記第１のフローの第１のパケットに後続するパケットを待機させている間に、第２のフローのパケットが該待機中のパケットより先に処理されるように、
フローを制御することを特徴とするネットワーク装置。
【請求項１９】
上記トラフィック管理部は、上記生成されたフローに対応する内部処理情報列を、フローの種類毎にパケットの受信順序を保持して格納するキューを有し、
該キューに格納される内部処理情報列は、対応するパケットの処理結果が上記プロセスキャッシュに登録されているか否かを示す登録済み情報を含むことを特徴とする請求項１８記載のネットワーク装置。
【請求項２０】
上記パケット処理部の前段に、
上記登録済み情報に基づいて、パケットを上記パケット処理部で処理するか、上記プロセスキャッシュを参照して処理するかを選択する解析部を有する請求項１９記載のネットワーク装置。
【請求項２１】
上記パケット処理部の選択により、パケットが上記パケット処理部で処理された場合、当該処理結果が上記プロセスキャッシュに登録完了されたことを上記トラフィック管理部に通知するキャッシュミス処理部を有する請求項２０記載のネットワーク装置。
【請求項２２】
上記トラフィック管理部は、上記キャッシュミス処理部からの通知に基づいて、上記内部処理情報列に登録済み情報を付加することを特徴とする請求項２１記載のネットワーク装置。
【請求項２３】
上記トラフィック管理部は、上記登録済み情報を参照してフローを制御することを特徴とする請求項２２記載のネットワーク装置。
【請求項２４】
上記第１のフローの第１のパケットは、処理結果が該プロセスキャッシュ未登録である第１のフローの先頭パケットであることを特徴とする請求項１８記載のネットワーク装置。
【請求項２５】
上記第２のフローのパケットは、上記プロセスキャッシュに処理結果が未登録な先頭パケットまたは、プロセスキャッシュに処理結果が登録済みの後続パケットであることを特徴とする請求項１８記載のネットワーク装置。
【請求項１】
入力されたパケットを分類しフローとして扱うための解析部と、
前記パケットに対して実施した処理をフロー毎に記録するための複数のエントリを有するキャッシュと、
前記キャッシュの前段に配置され、前記キャッシュのエントリと１対１に対応し、対応するエントリに割り当てられたフローに属するパケットを保持するフロー管理用のキュー群と、制御部を有し、該制御部は、
まず、前記キャッシュに未登録のフローの先頭のパケットの処理要求を出し、
次に、前記先頭パケットの処理結果が前記キャッシュに登録されたことの通知を受信した後
対応する前記キューに保持されているパケットを前記キャッシュにアクセスさせ、
更に、あるフローのパケットを保持している間に、他のフローの先頭パケットがあれば保持中の前記キャッシュ未登録フローを追い越して処理要求を出し、
あるフローの前記キャッシュ登録済みパケットがあれば、保持中の前記キャッシュ未登録フローを追い越して前記キャッシュにアクセスさせるように制御を行うことを特徴とするネットワーク装置。
【請求項２】
ネットワーク上で転送されるパケットをフローとして扱うためにパケットから内部処理情報列を生成し、
前記内部処理情報列が、
パケットと内部処理情報列を１対１に対応付ける情報、及びパケット毎に異なる情報を合わせた第一の情報と
前記パケットのネットワーク上での各階層におけるプロトコル種類を識別するための第二の情報と
前記パケットのネットワーク上での各階層に対応するヘッダから抽出した第三の情報と
で構成され、
前記第二の情報と前記第三の情報によりパケットをフロー分類し、
前記パケットに対して実施した処理を第四の情報として生成し、必要に応じて第三の情報を書換え、
前記第三、第四の情報をデータとしてフロー毎に記録し同一のフローに適用するためのキャッシュと、
前記キャッシュの前段に前記キャッシュのエントリと１対１に対応するフロー管理用のキュー群とを用いて、
前記キュー群は、割り当てられたフローに属するパケットを保持し、
まず、前記キャッシュに未登録のフローの先頭のパケットの処理要求を出し、
次に、前記先頭パケットの処理結果が前記キャッシュに登録されたことの通知を受信した後
対応する前記キューに保持されているパケットを前記キャッシュにアクセスさせ、
更に、あるフローのパケットを保持している間に、他のフローの先頭パケットがあれば保持中の前記キャッシュ未登録フローを追い越して処理要求を出し、
前記あるフローの前記キャッシュ登録済みパケットがあれば、保持中の前記キャッシュ未登録フローを追い越して前記キャッシュにアクセスさせることを特徴とするネットワーク装置の制御方法。
【請求項３】
請求項１に記載のネットワーク装置において、
ハッシュ関数によりフロー分類した情報を割り当てるパケット処理を記録するキャッシュのタグ部分と
パケット処理を記録するキャッシュのデータ部分と
前記キャッシュのタグ部分及びデータ部分の各エントリに対応するフロー管理用のキューの
情報割り当て位置が複数（Ｎ）箇所ある（Ｎウェイ・）セット・アソシアティブ形式であることを特徴とするネットワーク装置。
【請求項４】
請求項１に記載のネットワーク装置において、
フロー分類した情報を割り当てるフロー管理用のキューが利用中である場合に、
前記フロー管理用キューが解放されるまで前記フロー分類した情報及び、
それ以降の全てのフローを待機させるために
前記全てのフローを一時的に保持するためのバッファを具備することを特徴とするネットワーク装置。
【請求項５】
請求項１に記載のネットワーク装置において、
フロー分類した情報を割り当てるフロー管理用のキューが利用中である場合に、
前記フロー管理用キューが解放されるまで前記フロー分類した情報及び、
それ以降の同一フローを待機させるために
前記同一フローを一時的に保持するためのバッファを具備することを特徴とするネットワーク装置。
【請求項６】
請求項１に記載のネットワーク装置において、
フロー分類した情報を管理するフロー管理用のキューのうち、
複数本の前記フロー管理キューからの情報取り出しが可能になった時、
情報に記載されている優先順位情報を参照して情報を取り出すフロー管理キューを選択可能であることを特徴とするネットワーク装置。
【請求項７】
請求項１に記載のネットワーク装置において、
フロー分類した情報を管理するフロー管理用のキューのうち、
複数本の前記フロー管理キューからの情報取り出しが可能になった時、
情報に記載されている帯域制御情報と情報のサイズを参照して
情報を出力する前記前記フロー管理キューからの出力量を制限することを特徴とするネットワーク装置。
【請求項８】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分と
フロー分類した情報を管理するフロー管理用のキューを含む部位と
を単一のデバイス上へ実装し、
パケット処理を記録するキャッシュのデータ部分を前記のデバイスとは異なるデバイス上へ実装することを特徴とするネットワーク装置。
【請求項９】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分と
フロー分類した情報を管理するフロー管理用のキューを含む部位と、
パケット処理を記録するキャッシュのデータ部分と
を単一のデバイス上へ実装することを特徴とするネットワーク装置。
【請求項１０】
請求項１に記載のネットワーク装置において、
ハッシュ関数によりフロー分類した情報を割り当てる
パケット処理を記録するキャッシュのタグ部分と
パケット処理を記録するキャッシュのデータ部分と
前記キャッシュのタグ部分及びデータ部分の各エントリに対応するフロー管理用のキューの
情報割り当て位置が一つ以上あり、
更に、前記フロー分類後の割り当て位置が利用中であった場合に
自由に割り当て可能なフル・アソシアティブ方式の小容量の
前記キャッシュのタグ部分と
前記キャッシュのデータ部分と
前記フロー管理用のキューと
を具備することを特徴とするネットワーク装置。
【請求項１１】
請求項８に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分に相当する機能を具備する部位が
フロー管理用のキューを具備するデバイス上に実装されており、
パケット処理を記録するキャッシュのデータ部分を具備するデバイス上には実装されていないことを特徴とするネットワーク装置。
【請求項１２】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュのタグ部分に相当する機能を具備する部位が
フロー管理用のキューを具備するデバイス上に実装されており、
尚且つ、前記タグ部分がパケット処理を記録するキャッシュのデータ部分を具備するデバイス上にも実装されていることを特徴とするネットワーク装置。
【請求項１３】
請求項１２に記載のネットワーク装置において、
パケット処理を記録するキャッシュに、パケット処理結果が登録されても、
フロー管理用のキューへキャッシュ登録通知信号を渡さず、
前記フロー管理用キューは、各キューがタイマを持ち、
前記フロー管理用キューの先頭のパケットをパケット処理部へ送信した後、
前記タイマをスタートさせ、設定された閾値を越えた時点で
前記フロー管理用キューに残っているパケットを前記キャッシュへアクセスさせることを特徴とするネットワーク装置。
【請求項１４】
請求項１に記載のネットワーク装置において、
パケット処理を記録するキャッシュに渡すパケット処理結果を生成するパケット処理部が前記キャッシュと異なるデバイス上に実装されていることを特徴とするネットワーク装置。
【請求項１５】
キャッシュメモリを用い、先行するパケットに関する処理結果をキャッシュメモリに記録し、先行するパケットと同一処理を行う後続のパケットの処理は該キャッシュメモリの内容を利用する、キャッシュ型のパケット処理方法であって、
パケットを受信するステップと、
該受信したパケットをフロー毎に分類するステップと、
該フロー毎に分類したパケットを、パケットの到着順序を維持してＦＩＦＯ型のキューにフロー毎に記録するステップと、
上記キュー内のフローの所定パケットがキャッシュに未登録である場合、該所定パケットを処理して処理結果をキャッシュメモリに格納するとともに、同一キュー内の所定パケット以降のパケットは、キューに待機させておくステップと、
上記所定パケットに関する処理結果のキャッシュメモリへの格納の完了の後に、上記キューに待機させておいたパケットの処理を行うステップと、
を有するパケット処理方法。
【請求項１６】
処理結果が該キャッシュメモリ未登録である各フローの先頭パケットは、他のフローで待機中のパケットを追い越して処理されることを特徴とする請求項１５記載のパケット処理方法。
【請求項１７】
各キューは対応するキャッシュを有しており、
各キューが対応するキャッシュの登録情報を記録するステップと、
キャッシュに未登録状態のキューにパケットが到着すると、先頭のパケットのみを処理し、処理結果が上記キャッシュに登録されるのを待つステップと、
二つ目以降のパケットは上記キャッシュへの登録が完了した時点で処理が開始されることを特徴とする請求項１５記載のパケット処理方法。
【請求項１８】
パケットを受信する入力インタフェースと、
受信したパケットを解析および分類して、種類毎にフローを生成するパケット解析部と、
上記生成されたフローを、種類毎にパケットの受信順序を保持して管理するトラフィック管理部と、
上記パケットを処理するパケット処理部と、
上記パケット処理部の処理結果を上記フロー毎に登録するプロセスキャッシュと、
を有するネットワーク装置であって、該ネットワーク装置は、
(1)上記プロセスキャッシュに処理結果が未登録な第１のフローの第１のパケットを、上記パケット処理部で処理し、
(2)上記第１のフローの第１のパケットに後続するパケットは、上記第１のパケットの処理結果が上記プロセスキャッシュに登録されるまで待機させ、登録の後、上記プロセスキャッシュの情報を用いて処理を行い、
(3)上記第１のフローの第１のパケットに後続するパケットを待機させている間に、第２のフローのパケットが該待機中のパケットより先に処理されるように、
フローを制御することを特徴とするネットワーク装置。
【請求項１９】
上記トラフィック管理部は、上記生成されたフローに対応する内部処理情報列を、フローの種類毎にパケットの受信順序を保持して格納するキューを有し、
該キューに格納される内部処理情報列は、対応するパケットの処理結果が上記プロセスキャッシュに登録されているか否かを示す登録済み情報を含むことを特徴とする請求項１８記載のネットワーク装置。
【請求項２０】
上記パケット処理部の前段に、
上記登録済み情報に基づいて、パケットを上記パケット処理部で処理するか、上記プロセスキャッシュを参照して処理するかを選択する解析部を有する請求項１９記載のネットワーク装置。
【請求項２１】
上記パケット処理部の選択により、パケットが上記パケット処理部で処理された場合、当該処理結果が上記プロセスキャッシュに登録完了されたことを上記トラフィック管理部に通知するキャッシュミス処理部を有する請求項２０記載のネットワーク装置。
【請求項２２】
上記トラフィック管理部は、上記キャッシュミス処理部からの通知に基づいて、上記内部処理情報列に登録済み情報を付加することを特徴とする請求項２１記載のネットワーク装置。
【請求項２３】
上記トラフィック管理部は、上記登録済み情報を参照してフローを制御することを特徴とする請求項２２記載のネットワーク装置。
【請求項２４】
上記第１のフローの第１のパケットは、処理結果が該プロセスキャッシュ未登録である第１のフローの先頭パケットであることを特徴とする請求項１８記載のネットワーク装置。
【請求項２５】
上記第２のフローのパケットは、上記プロセスキャッシュに処理結果が未登録な先頭パケットまたは、プロセスキャッシュに処理結果が登録済みの後続パケットであることを特徴とする請求項１８記載のネットワーク装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２００６−１３５５７２（Ｐ２００６−１３５５７２Ａ）
【公開日】平成１８年５月２５日（２００６．５．２５）
【国際特許分類】
【出願番号】特願２００４−３２１４５８（Ｐ２００４−３２１４５８）
【出願日】平成１６年１１月５日（２００４．１１．５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成１８年５月２５日（２００６．５．２５）
【国際特許分類】
【出願日】平成１６年１１月５日（２００４．１１．５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]