JP3777161B2 - マルチキャスト伝送の効率的処理 - Google Patents

Description

本発明は、全般的には、ネットワーク・プロセッサにおけるマルチキャスト伝送に関し、より詳細には、ネットワーク・プロセッサにおけるマルチキャスト伝送を従来の手法よりも効率的に実施する方法に関する。

ネットワーク・プロセッサにおけるマルチキャスト伝送方式の実施においては、ユニキャスト方式では起こらないいくつかの問題に対処しなければならない。たとえば、１つまたは複数のフレームを単一のターゲットに伝送する（すなわち、ユニキャスト伝送）場合、フレームに関連づけられたバッファ（すなわち、メモリ・バッファ中に格納されたすべての関連データ）は、データが各バッファから読み出されると、空きバッファ・キュー（すなわち、フレーム・データ用に利用可能なメモリ・バッファの、リンク・リスト）に戻すことができる。しかし、いくつかのターゲット位置が存在するマルチキャストのシナリオでは、フレームに関連づけられたバッファは、空きキューに直接戻すことができず、その代わり、最後のマルチキャスト伝送が行われた後、リンク・リストを「再歩行（re-walk）」して戻さなければならない。ユニキャスト伝送では起こらない、マルチキャストの問題の別の要因は、各マルチキャスト・ターゲットの位置が参照フレーム中で異なる開始位置を必要とする可能性があり、あるいは、さらなる情報の追加を必要とする可能性があることである。こうした問題に対する一般的な解決策は、各マルチキャスト要求ごとに（したがって、各マルチキャスト・ターゲットごとに）、参照フレーム全体のコピーを作成することである。複数のコピーを作成することにより、問題は解決するが、マルチキャスト要求を満たすために多数のメモリ・バッファを借りる必要があり、その結果、システム性能に負担がかかることになる。

フレームのコピーを複数作成する代わりに、参照フレームにリンクすることによってマルチキャスト伝送を実施する場合、一部のポートが他のポートよりも高い性能レベルで動作することがあるので、ポート性能の不一致が、対処しなければならない問題となる。特に、参照フレームにリンクバックすることによって、問題が起こる。というのは、最後に伝送を開始するフレームが、最後に終了するフレームではないことがあるからである。開始フレームと停止フレームの間のこの不一致により、いつ参照フレーム・バッファを空きバッファ・キューに戻すべきかを知らなければならないという問題が生じる。具体的には、開始フレームが終了した後、単純にバッファを戻すことはできない。１つの解決策は、すべてのマルチキャスト伝送が完了するまで待つことであるが、やはりこのような手法も、不必要にシステム性能を妨げることがある。

高性能ネットワーク・プロセッサにおいて、マルチキャスト伝送メモリの必要量を最小限にし、かつポート性能の不一致を補償する新規な解決策が必要である。

本発明は、請求項１に記載の、ネットワーク・プロセッサにおけるマルチキャスト伝送方法に関する。

本発明はまた、請求項７に記載のネットワーク・プロセッサ、および請求項６に記載のコンピュータ・プログラムに関する。

本発明によると、新しい手法によって、各マルチキャストのインスタンス（すなわち、各マルチキャスト・ターゲット）ごとにフレーム全体をコピーする必要がなくなり、それによって、メモリの必要量が削減され、かつポート性能の不一致による問題が解決される。さらに、好ましくは、借りたバッファは、使用されると（他のインスタンスがいつ伝送を完了するかとは無関係に）空きキューに戻される。また、好ましくは、すべてのインスタンスがいつ伝送されるかをカウンタを使用して判定し、したがって参照フレームも同様に空きキューに戻すことができる。

前述および他の目的、態様、利点は、以下の本発明の好ましい実施形態の詳細な説明を、図面を参照しながら読めば、よりよく理解されるであろう。

ここで図面、より具体的には図１を参照すると、本発明の好ましい実施形態によるデータ構造を示してある。フレームが、一連のバッファ１０１_１〜１０１_５中に格納される。各バッファ１０１は、対応するバッファ制御ブロック（ＢＣＢ）１０２_１〜１０２_５を有し、このＢＣＢは、一連のバッファをフレームにリンクするのに使用する。各フレームは、対応するフレーム制御ブロック（ＦＣＢ）１０３_１〜１０３_ｎを有し、このＦＣＢは、一連のフレームをキューにリンクするのに使用する。各キューは、キュー制御ブロック（ＱＣＢ）１０４を有し、このＱＣＢは、キュー中の最初および最後のＦＣＢ１０３のアドレスと、キュー中のフレーム数のカウントとを保持する。

データ構造の定義
バッファ１０１は、データの格納に使用する。各バッファ１０１は、大きさが６４バイトであり、１〜６４バイトの有効データを格納することができる。バッファ１０１内部のすべての有効データは、単一の隣接するバイト範囲として格納しなければならない。複数のバッファを、リンク・リストを介して互いに連鎖し、６４バイトより大きいフレームを格納する。

最初に、すべてのバッファを、空きバッファ・キューに入れる。フレームが届くと、バッファは、空きバッファ・キューの先頭からポップ（削除）され、フレーム・データの格納に使用される。最後のフレーム伝送が実施されると、フレーム・データの格納に使用したバッファは、空きバッファ・キューの末尾にプッシュされる。

バッファ制御ブロック（ＢＣＢ）１０２は、複数のバッファをフレームに連鎖するために、リンク・リストを形成する。また、バッファ１０１のどのバイトが有効データを含むかを記録する。各バッファ１０１ごとに、対応するＢＣＢ１０２がある。データ記憶メモリ（図２に示す２０５および２０６）内のバッファ１０１のアドレスは、ＢＣＢアレイ中の対応するＢＣＢ１０２のアドレスとしても使用される。ＢＣＢ１０２は、以下のフィールドを含む。

・次のバッファ・アドレス（ＮＢＡ）フィールドは、フレーム中の次のバッファ１０１へのポインタを格納するのに使用される。現在のバッファ１０１用のＢＣＢ１０２中のＮＢＡフィールドは、フレームの次のバッファ１０１（および対応するＢＣＢ１０２）のアドレスを含む。

・開始バイト位置（ＳＢＰ）フィールドは、フレームの次のバッファ１０１中のデータの最初の有効バイトのオフセットを格納するのに使用される。有効な値は、０〜６３である。

・終了バイト位置（ＥＢＰ）フィールドは、フレームの次のバッファ１０１中のデータの最後の有効バイトのオフセットを格納するのに使用される。有効な値は、０〜６３である。

・非常駐バッファ（ＴＢＵＦ）ビットは、フレーム中の次のバッファ１０１を、そのデータを伝送のために読み出した後で空きバッファ・キューに戻すべきかどうかを指定するために、マルチキャスト・フレームを伝送するときだけ使用される。このビットは、マルチキャスト・フレームに対してのみ有効である。これは、フレームの受信の際、デフォルト状態である０に設定される。

ＳＢＰ、ＥＢＰ、ＴＢＵＦフィールドは、フレーム中の「次の」バッファ１０１に適用され、現在のＢＣＢ１０２に対応するバッファ１０１には適用されないことに留意されたい。これらのフィールドは、次のバッファ１０１のＳＢＰ、ＥＢＰ、ＴＢＵＦ情報をそのアドレス（ＮＢＡ）と同時に取り出せるようにするためにこのように定義される。

ＢＣＢ１０２内のフィールドのそれぞれは、フレームの受取り中、最初にデータフロー・ハードウェア２０２（図２）によってロードされる。その後、ピココードが、ＢＣＢ１０２内のフィールドを修正して、伝送の前にフレームを「編集」することができる。ＮＢＡフィールドは、フレーム中にバッファを追加または削除するために、修正することができる。ＳＢＰおよびＥＢＰフィールドは、バッファ１０１中の有効バイト数を変えるために、修正することができる。マルチキャスト・フレームの一部であるバッファに対するＴＢＵＦビットを設定して、バッファ１０１を、そのデータを伝送したらすぐに空きバッファ・キューに戻すよう要求することができる。

ＢＣＢ１０２のＮＢＡフィールドは、また、空きバッファ・キュー中のバッファのリンク・リストを形成するのに使用する。ＮＢＡは、対応するバッファ１０１が空きバッファ・キュー中にあるときに有効な情報を含む、ＢＣＢ１０２内の唯一のフィールドである。

フレーム制御ブロック（ＦＣＢ）１０３は、キュー中のフレームのリンク・リストを形成する。また、フレーム中の有効バイトの総数と、フレーム中の第１バッファ１０１のバッファ・アドレスおよびＳＢＰ／ＥＢＰと、２ビットのフレーム「Type」フィールドとを記録する。ＦＣＢ１０３は、以下のフィールドを含む。

・次のフレーム・アドレス（ＮＦＡ）フィールドは、フレーム・キュー中の次のフレームへのポインタを格納するのに使用する。現在のフレームに対するＦＣＢ１０３のＮＦＡフィールドは、キュー中の次のフレームに対するＦＣＢ１０３のアドレスを含む。このフィールドは、対応するフレームがキュー中の最後のフレームである場合、有効データを含まない。ＱＣＢの「ＱＣＮＴ」フィールドがゼロの場合、キューにはフレームが存在しない。ＱＣＢの「ＱＣＮＴ」フィールドが１の場合、キューの先頭にあるＦＣＢの「ＮＦＡ」フィールドは、キューに「次のフレーム」がないので、無効である。

・バイト・カウント（ＢＣＮＴ）フィールドは、フレーム・キュー中の次のフレームのすべてのバッファ中の有効バイトの総数のカウントを格納するのに使用される。ＢＣＮＴは、キュー中の「次の」フレームに適用され、そのＢＣＮＴフィールドを格納するＦＣＢ１０３に関連づけられたフレームには適用されないことに留意されたい。ＢＣＮＴフィールドは、キュー中の次のフレームのアドレス（ＮＦＡ）および長さ（ＢＣＮＴ）を同時に取り出すことを可能にするためにこのように定義される。

・第１バッファ・アドレス（ＦＢＡ）フィールドは、フレーム中の第１バッファ１０１（および対応するＢＣＢ１０２）のアドレスを格納するのに使用される。

・ＳＢＰおよびＥＢＰフィールドは、フレームの第１バッファ１０１中の有効データの開始および終了バイト位置を格納するのに使用される。

・Typeフィールドは、データフロー・ハードウェア２０２に、伝送されるフレームの形式およびタイプを知らせるためにピココードによって使用される。

・００ 「ＦＡＣＢを有するユニキャスト・フレーム」 フレームは、単一の宛先に伝送され（ユニキャスト）、各バッファ１０１は、伝送用にデータが読み出されると、空きバッファ・キューに戻される。１つまたは複数のフレーム変更制御ブロック（ＦＡＣＢ）が、フレームの第１バッファ１０１に格納される。

・０１ 「ＦＡＣＢを有する静的フレーム」 このフレームは、どのバッファも空きバッファ・キューに戻さずに伝送される。１つまたは複数のフレーム変更制御ブロック（ＦＡＣＢ）が、フレームの第１バッファ１０１に格納される。

・１０ 「ＦＡＣＢをもたないユニキャスト・フレーム」 このフレームは、単一の宛先に伝送され（ユニキャスト）、各バッファ１０１は、データが伝送のために読み出されると、空きバッファ・キューに戻される。フレーム変更制御ブロック（ＦＡＣＢ）は、フレームの第１バッファ１０１に格納されない。

・１１ 「ＦＡＣＢを有するマルチキャスト・フレームで、第１バッファがＴＢＵＦ」 このフレームは、複数の宛先に伝送され（マルチキャスト）、フレームのすべてのインスタンスに共通のバッファは、フレームがすべての宛先に完全に伝送された後でのみ、空きバッファ・キューに戻される。１つまたは複数のフレーム変更制御ブロック（ＦＡＣＢ）が、各フレーム・インスタンスの第１バッファ１０１に格納される。また、フレームの第１バッファ１０１、およびＢＣＢ１０２中のＴＢＵＦビットがセットされているどの後続のバッファ１０１も、１つのフレーム・インスタンスに関連づけられていると仮定され、データがバッファ１０１から伝送された直後に、空きバッファ・キューに戻される。

ＦＣＢ１０３中のフィールドはそれぞれ、まず、フレームの受取り中に、データフロー・ハードウェア２０２（図２）によってロードされる。続いてフレーム伝送の前に、ピココードが、ＦＣＢ１０３のＢＣＮＴ、ＦＢＡ、ＳＢＰ、ＥＢＰ、およびTypeフィールドをオーバーレイする。編集の結果、フレームの長さが変わった場合、ＢＣＮＴフィールドを修正することができる。フレームの第１バッファ１０１のアドレスまたは有効データ範囲に変化があった場合、ＦＢＡ、ＳＢＰ、およびＥＢＰフィールドを修正することができる。Typeフィールドは、フレーム伝送のタイプを設定するために書き込まれる。

空きＦＣＢキューは、フレームに現在割り当てられていないＦＣＢのリンク・リストを維持するのに使用する。ＦＣＢ１０３のＮＦＡフィールドは、空きＦＣＢキュー中のＦＣＢのリンク・リストを形成するに使用する。ＮＦＡは、対応するＦＣＢ１０３が空きＦＣＢキュー中にあるときに、ＦＣＢ１０３の中で有効な情報を含む唯一のフィールドである。

キュー制御ブロック（ＱＣＢ）１０４は、キュー中の最初および最後のＦＣＢのアドレス、およびキュー中の総フレーム数のカウントを格納することによって、フレームのキューを維持する。ＱＣＢ１０４は、以下のフィールドを含む。
・先頭ＦＣＢＡ：キューの先頭にあるフレームのＦＣＢアドレス（ＦＣＢＡ）を格納するのに使用する。
・先頭ＢＣＮＴ：キューの一番上にあるフレーム中の有効バイトの総数のカウントを格納するのに使用する。
・末尾ＦＣＢＡ：キューの末尾にあるフレームのＦＣＢアドレス（ＦＣＢＡ）を格納するのに使用する。
・ＱＣＮＴ：キュー中に現在あるフレーム数のカウントを格納するのに使用する。

フレームは、以下のようにしてキューの末尾に追加される。
１．１つまたは複数のフレームが既にキュー中にある場合（ＱＣＮＴが１以上）、元々キューの末尾にあったＦＣＢ１０３中のＮＦＡおよびＢＣＮＴフィールドは、キューの末尾に新しいフレームを連鎖するように書き込まれる。それ以前にキュー中にフレームがなかった場合（ＱＣＮＴ＝０）、ＱＣＢ１０４の先頭ＦＣＢＡおよび先頭ＢＣＮＴフィールドは、キューの先頭として新しいフレームを確立するように書き込まれる。
２．ＱＣＢ１０４の末尾ＦＣＢＡは、キューの末尾に追加された新しいＦＣＢ１０３をポイントするように書き込まれる。
３．ＱＣＢ１０４のＱＣＮＴは、キュー中の１つの追加フレームを反映するように１だけ増分される。

フレームは、キューの先頭から以下のようにして削除される。
１．複数のフレームが既にキュー中にある場合（ＱＣＮＴが１以上）、キューの先頭にあるＦＣＢ１０３中のＮＦＡおよびＢＣＮＴフィールドは、キューの先頭にある新しいフレームに対するＦＣＢＡおよびＢＣＮＴを取得するために読み出される。次いで、このＦＣＢＡおよびＢＣＮＴの値が、キューの先頭にある新しいフレームを確立するために、ＱＣＢ１０４の先頭ＦＣＢＡおよび先頭ＢＣＮＴに書き込まれる。
２．ＱＣＢ１０４のＱＣＮＴは、キュー中のフレームが１つ減ったことを反映するように１だけ減分される。

フレームの受取り
このセクションでは、フレームの受取りからネットワーク・プロセッサへのディスパッチまでの間のデータ構造の使用を説明する。
ステップ１：第１フレーム・データが受け取られると、空きバッファ・アドレスが空きバッファ・キューの先頭からポップされ、空きＦＣＢ１０３が空きＦＣＢキューの先頭からポップされる。最大６４バイトのフレーム・データが、バッファ１０１に書き込まれる。ＦＣＢ１０３には、第１バッファ１０１に対するＦＢＡ、ＳＢＰ、およびＥＢＰ値が書き込まれる。作業用バイト・カウント・レジスタは、第１バッファ１０１に書き込まれたバイト数に設定される。フレーム全体が第１バッファ１０１に収まる場合はステップ３に進むが、それ以外の場合はステップ２に進む。

ステップ２：追加バッファ１０１が空きバッファ・キューからポップされ、最大６４バイトのデータがバッファ１０１に書き込まれる。直前のバッファ１０１に対するＢＣＢ１０２には、現在のバッファ１０１に対するＮＢＡ、ＳＢＰ、およびＥＢＰ値が書き込まれる。バッファ１０１に書き込まれるバイト数が、作業用バイト・カウント・レジスタに加えられる。フレームの最後が受け取られた場合はステップ３に進むが、それ以外の場合はステップ２を繰り返す。

ステップ３：次いで、フレームは、入力キューの末尾に入れられ、ネットワーク・プロセッサへのディスパッチを待つ。
１．それ以前に入力キュー中にフレームがなかった場合、入力キューのＱＣＢ１０４中の先頭ＦＣＢＡおよび末尾ＦＣＢＡには、新しいフレームのＦＣＢ１０３のアドレスが書き込まれる。ＱＣＢ１０４中の先頭ＢＣＮＴには、新しいフレームの全長を記録する、作業用バイト・カウント・レジスタが書き込まれる。ＱＣＢ１０４中のＱＣＮＴは、１だけ増分される。

２．入力キュー中に１つまたは複数のフレームが既にあった場合、入力キューの末尾にある１つ前のフレーム用のＦＣＢ１０３のＮＦＡおよびＢＣＮＴフィールドが書き込まれる。ＮＦＡフィールドには、新しいフレームのＦＣＢ１０３のアドレスが書き込まれる。ＢＣＮＴフィールドには、新しいフレームの長さを記録する作業用バイト・カウント・レジスタの値が書き込まれる。次いで、入力キューのＱＣＢ１０４の末尾ＦＣＢＡには、新しいフレームのＦＣＢ１０３のアドレスが書き込まれる。ＱＣＢ１０４中のＱＣＮＴは、１だけ増分される。

フレームは、入力キューの先頭に達すると、ネットワーク・プロセッサへのディスパッチのためにキューからはずされる。先頭ＦＣＢＡおよび先頭ＢＣＮＴフィールドは、入力キューのＱＣＢ１０４から読み出される。次いで、先頭ＦＣＢＡの値を使用して、キューの先頭にあるＦＣＢ１０３の内容が読み出される。ＦＣＢ１０３から読み出されるＮＦＡおよびＢＣＮＴの値は、フィールドＱＣＢ１０４の先頭ＦＣＢＡおよび先頭ＢＣＮＴの更新に使用される。ＦＣＢ１０３から読み出されるＦＢＡ、ＳＢＰ、およびＥＢＰの値は、ネットワーク・プロセッサへのディスパッチのためのフレーム・データの位置決めおよび読出しに使用される。ディスパッチに必要なフレーム・データが読み出されるまで、ＢＣＢ１０２の連鎖が続く。ＱＣＢ１０４中のＱＣＮＴは、１だけ増分される。

図２は、本発明の好ましい実施形態を実施するチップ・セット・システム環境を示す。より具体的に言うと、データは、交換ファブリック２０１からデータフロー・チップ２０２に流れ、次いで、ＰＯＳ（Packet-Over-SONET）フレーマまたはイーサネット（Ｒ）ＭＡＣ（媒体アクセス制御）２０３に流れる。ＰＯＳフレーマまたはイーサネット（Ｒ）ＭＡＣ２０３から、データは、データフロー・チップ２０４に流れ、次いで、交換ファブリック２０１に流れる。データフロー・チップ２０２および２０４は、データ記憶機構（ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ））２０５および２０６、ならびに制御記憶機構（スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ））２０７および２０８によってそれぞれサポートされる。データフロー・チップ２０２および２０４は、それぞれの組込みプロセッサ複合体（ＥＰＣ）２０９および２１０とそれぞれ通信し、スケジューラ・チップ２１１および２１２とそれぞれ任意選択で通信する。ＥＰＣチップ２０９および２１０は、ＤＲＡＭで実装されるルックアップ・テーブル２１３および２１４、ならびにＳＲＡＭで実装されるルックアップ・テーブル２１５および２１６によってそれぞれサポートされる。ＥＰＣチップ２０９は、さらに、コプロセッサ・インタフェースおよびＰＣＩ（周辺装置相互接続）ローカル・バスを備え、ＥＰＣチップ２１０は、さらに、ＣＡＭ（連想記憶装置）２１７によってサポートされる。スケジューラ・チップ２１１および２１２が使用される場合、それらは、それぞれ、ＳＲＡＭで実装されるフロー・キュー２１８および２１９によってサポートされる。

図３は、データフロー・チップ２０２（２０４）、ＥＰＣチップ２０９（２１０）およびスケジューラ・チップ２１１（２１２）をより詳細に示す。ＥＰＣチップ２０９（２１０）は、ネットワーク・トラフィックの転送に責任のあるソフトウェアを実行する。ＥＰＣチップは、テーブル探索、ポリシング（policing）、およびカウントなど、共通動作を実行するハードウェア補助機能を含む。データフロー・チップ２０２（２０４）は、ネットワーク・ポートまたは交換ファブリック・インタフェースあるいはその両方を経由してトラフィックを送受信する主要データ経路として働く。データフロー・チップは、トラフィックがネットワーク・プロセッサ・サブシステムを介して流れるときに、それをバッファリングする大型データ記憶メモリ２０５（２０６）へのインタフェースを提供する。データフロー・チップは、処理のためにフレーム・ヘッダをＥＰＣにディスパッチし、ＥＰＣからの要求に応答してフレームをそのターゲットの宛先に転送する。任意選択のスケジューラ・チップ２１１（２１２）を追加して、ネットワーク・プロセッサ・サブシステムによって提供されるサービス品質（ＱｏＳ）を高めることができる。スケジューラ・チップは、数千のネットワーク・トラフィックの「フロー」が、その割り当てられたＱｏＳレベルごとに別々にスケジューリングされるようにする。

ＥＰＣチップ２０９（２１０）は、ネットワーク・トラフィックの並列処理を提供する、１２個の２項プロトコル・プロセッサ・ユニット（ＤＰＰＵ）３０１を含む。各ＤＰＰＵは、２つの「ピココード」エンジンを含む。各ピココード・エンジンは、２つのスレッドをサポートする。スレッド間では、ゼロ・オーバヘッドのコンテキスト切換えがサポートされる。ピココード命令格納は、ＥＰＣチップ内部で統合される。入力フレームは、データフロー・チップ２０２（２０４）から、データフロー・インタフェース３０２を介して受け取られ、パケット・バッファ３０３に一時的に格納される。ディスパッチ機能は、入力フレームをプロトコル・プロセッサ３０１に分配する。１２個の入力キューのカテゴリは、フレームが特定のスレッドに向けられるように、またはすべてのスレッドに分配されるようにする。完了ユニット機能は、プロトコル・プロセッサ３０１の出力の所でフレーム順序が確実に維持されるようにする。

組込み型ＰｏｗｅｒＰＣ（Ｒ）マイクロプロセッサのコア３０４が、より高いレベルのシステム管理ソフトウェアの実行を可能にする。外部ＤＤＲ ＳＤＲＡＭへの１８ビットのインタフェースが、最大６４Ｍバイトの命令格納を提供する。３２ビットのＰＣＩインタフェースが、他の制御機能への接続のために、またはＭＡＣやフレーマ構成要素などの周辺回路を構成するために提供される。

ハードウェアベースの分類機能は、フレームがプロトコル・プロセッサにディスパッチされると、それを解析して、公知のレイヤ２およびレイヤ３のフレーム形式を識別する。分類装置の出力は、各フレームの処理を開始する前に、ピココード・スレッドの状態の事前条件を決定するのに使用される。

テーブル探索エンジンは、テーブル探索を実施するためのハードウェア補助を提供する。テーブルは、探索を終了すると「リーフ」項目のアドレスが得られる、パトリシア・ツリーとして保持される。リーフ項目は、ピココードがそれを使ってフローに適した情報を格納する。３つのテーブル探索アルゴリズムがサポートされる。すなわち、複合規則に基づく探索のための、固定マッチ（ＦＭ）、最長接頭部マッチ（ＬＰＭ）、およびユニークなソフトウェア管理ツリー（ＳＭＴ）アルゴリズムである。制御記憶メモリ２０７（２０８）は、数百万のフローのワイア速度の分類をサポートするために、大型ＤＲＡＭテーブルおよび高速ＳＲＡＭテーブルを提供する。ルックアップ性能の向上のために、任意選択でＳＲＡＭインタフェースを、連想記憶装置（ＣＡＭ）（図２の２１７）の接続に使用することもできる。

ピココードは、データフロー・チップ２０２（２０４）に接続されたデータ記憶メモリ２０５（２０６）を読み出し、かつそこに書き込むことによって、フレームを直接編集することができる。性能をより高めるために、ピココードは、データフロー・チップに、フレームが出力ポートを介して送信されるときに修正を実施するよう命令するフレーム変更コマンドを生成することもできる。

カウンタ管理機能は、統計カウンタを保持する際にピココードを助ける。オンチップのＳＲＡＭおよび任意選択の外部ＳＲＡＭ（方針マネージャと共有）を、フレームが到着する間隔の割合で起こるイベントをカウントするのに使用することができる。外部制御記憶機構ＤＤＲ ＳＤＲＡＭ（テーブル探索機能と共有）の１つを、より遅い割合で起こるイベント用の多数のカウンタを保持するのに使用することができる。

方針マネージャ機能は、入力トラフィック・フローをポリシングする際に、ピココードを助ける。この機能は、選択可能なパラメータおよびアルゴリズムを有する数千のリーキー・バケット・メータを保持する。千個のポリシング制御ブロック（ＰｏｌＣＢｓ）をオンチップのＳＲＡＭ中に保持することができる。任意選択の外部ＳＲＡＭ（カウンタ・マネージャと共有）を追加して、ＰｏｌＣＢｓの数を増やすことができる。

データフロー・チップ２０２（２０４）は、「ポート」または「交換」インタフェース・モードで動作するように独立して構成することができる、送受信インタフェースを実装する。ポート・モードでは、データフロー・チップは、イーサネット（Ｒ）ＭＡＣやＰＯＳ（Ｐａｃｋｅｔ−Ｏｖｅｒ−ＳＯＮＥＴ）フレーマなど様々なネットワーク媒体を接続するためフレームを交換する。これは、受信コントローラ３０５および送信コントローラ３０６によって行われる。交換モードでは、データフロー・チップは、セル・ベースの交換ファブリックに接続するため６４バイトのセル・セグメントの形のフレームを交換する。データフロー・チップの送受信インタフェース３０６および３０５によってそれぞれ実装される物理バスは、６４ビットのデータ・バスである。インタフェースは、業界ＰＯＳフレーマの直接接続をサポートし、プログラマブル・ゲート・アレイ（ＦＰＧＡ）論理を介して、業界イーサネット（Ｒ）ＭＡＣおよび交換ファブリック・インタフェース（ＣＳＩＸなど）に適合させることもできる。

データベース・アービタ３０７を介してデータフロー・チップ２０２（２０４）に接続された大型データ・メモリ２０５（２０６）は、入力フレームの速度が出力フレームの速度を超えたときにトラフィックのバーストを吸収する、「ネットワーク・バッファ」を提供する。大型データ・メモリはまた、ＩＰフラグメントを再アセンブルするリポジトリとしても、ＴＣＰ終了などのアプリケーションにおいて可能な再伝送を待つフレームのためのリポジトリとしても働く。ポート・インタフェースおよび交換インタフェースのための持続型送受信帯域幅を提供するために、ＤＲＡＭインタフェースが複数サポートされる。追加の帯域幅が、ＥＰＣピココードによるデータ記憶メモリの直接読出し／書込みのために予約される。データ記憶メモリ２０５（２０６）は、バッファのリンク・リストを介して管理される。２つの外部ＳＲＡＭが、バッファおよびフレームのリンク・リストの保持に使用される。

データフロー・チップ２０２（２０４）は、データ記憶メモリ２０５（２０６）のオーバフローを防止するために、「ランダム早期破棄」（ＲＥＤ）などの高度な輻輳制御アルゴリズムを実装する。輻輳制御アルゴリズムは、どちらもＥＰＣインタフェース３０８を介して通信する、ＥＰＣピココードが提供する入力と、ＥＰＣポリシング機能と、データフローおよびスケジューラ・チップが保持する、様々なキューの閾値とによって動作する。データフロー内部の「破棄確率メモリ」は、ＥＰＣピココードによって保持され、様々な標準または固有の破棄アルゴリズムの実装を可能にする輻輳制御機能によって参照される。

データフロー・チップ２０２（２０４）は、フレーム変更制御ブロック（ＦＡＣＢ）（図５）に格納されたコマンドに基づいてフレーム変更論理３０９内でフレーム変更を実施する、多くのハードウェア補助機能からなるセットを実装する。よく知られている変更には、以下のフレーム・フィールドの修正がある。すなわち、イーサネット（Ｒ）ＤＡ／ＳＡ、ＶＬＡＮ、ＤＩＸ、ＳＡＰ、ＳＮＡＰ、ＭＰＬＳ、ＩＰ ＴＴＬ、ＩＰ ＴＯＳバイト、およびＩＰヘッダ・チェックサムである。ＦＡＣＢは、２つの目的を果たす。すなわち、マルチキャスト・アルゴリズム内で使用する参照ＦＣＢアドレスを格納し、フレーム変更論理３０９（データフローの伝送コントローラ３０６の一部）に、フレーム・データが出力ポートを介して送信されるときにそのデータに修正を施すよう命令するフレーム変更コマンドを格納する。フレーム変更論理３０９が実施する公知のフレーム修正の例として、以下のものがある。すなわち、イーサネット（Ｒ）宛先またはソース・アドレス・オーバレイ、イーサネット（Ｒ）・プロトコル・タイプ・オーバレイ、マルチプロトコル・ラベル交換（ＭＰＬＳ）ラベルの挿入および削除、インターネット・プロトコル（ＩＰ）活動時間（ＴＴＬ）減分などである。フレーム変更論理は、本発明の実施に必要ないことに留意されたい。データフロー・チップ２０２（２０４）がフレーム変更論理機能を含まない場合でも、同じマルチキャスト技術を使用することができる。

データフロー・チップ２０２（２０４）は、異なる出力ポートまたはターゲットの宛先向けのフレームのために別々の出力キューが保持される、「仮想出力キュー」として知られる技術を実装する。この方式は、単一の出力ポートが閉塞される場合に「ラインの先頭の閉塞」が起こるのを防止する。優先順位が高いキューおよび低いキューが各出力ポートごとに保持されて、予約されたまたは予約されていない帯域幅のトラフィックがそれぞれ独立にキューに入れられるようにする。

任意選択によるスケジューラ・チップ２１１（２１２）は、「保証帯域幅」、「ベスト・エフォート」、「ピーク帯域幅」など、様々なアルゴリズムを使用してスケジューリングできるフロー・キューを保持することにより、「サービス品質」を提供する。２つの外部ＳＲＡＭは、アクティブなフレームが数十万個入っている、数千のフロー・キューを保持するのに使用される。スケジューラ・チップ２１１（２１２）は、フレームがフロー・キューごとの閾値に基づいて破棄されるようにすることによって、データフロー・チップの輻輳制御アルゴリズムを補足する。

データフロー２０２（２０４）、ＥＰＣ２０９（２１０）およびスケジューラ２１１（２１２）の間のすべての情報の流れは「メッセージ」と呼ばれる形で交換されることに留意されたい。交換ファブリック２０１、データフロー２０２、およびＰＯＳフレーマ／イーサネット（Ｒ）ＭＡＣ２０３の間の情報の流れは、「フレーム」の形である。メッセージは、データフロー、ＥＰＣおよびスケジューラ・チップの間の「制御」情報の交換にのみ使用される。このようなメッセージの例として、次のようなものがある。すなわち、ディスパッチ、キュー作成、中断／例外、データ読出し、データ書込み、レジスタ読出しおよびレジスタ書込みである。メッセージは、要求からなるものでも、応答からなるものでもよい。

一般的なメッセージ形式を図４に示す。図４を参照すると、メッセージ形式は、以下の構成要素を含む。
メッセージＩＤ：Message_IDフィールドは、メッセージ・タイプを一義的に識別する、メッセージの第１ワードにある符号化された８ビットの値である。
メッセージ・パラメータ：Message_Parametersフィールドは、メッセージの第１ワードにある２４ビットの値である。このフィールドは、以下のような様々な目的のために、メッセージ・タイプごとに指定することができる。
・他のメッセージ・タイプを定義するために、Message_IDフィールドへの拡張として使用することができる。
・メッセージの目的をさらに修飾（qualify）するために、各メッセージ・タイプに基づいて使用することができる。
・「シーケンス番号」、または応答で戻されたデータを相関させる他の「参照ｉｄ」情報を搬送するのに使用することができる
・可変長メッセージの場合、メッセージ長を指定するのに使用することができる。
・そのメッセージ特有の他のデータ・パラメータを搬送するのに使用することができる。
データ：メッセージの残りの部分は、「０」〜「Ｎ−１」個の、追加の３２ビットの「データ」ワードで構成することができる。

マルチキャスト伝送
このセクションでは、マルチキャスト・フレームのキュー作成および伝送の処理を説明する。図５は、マルチキャスト伝送の例を示す。この場合、マルチキャスト・フレームは、３つの宛先に伝送されつつあり、したがって３つの「インスタンス」を有すると言うことができる。フレームを最初に受け取ったときに割り当てられたＦＣＢは、フレームの寿命がある間保存され、「参照ＦＣＢ」５０１と呼ばれる。ネットワーク・プロセッサは、（図５にＦＣＢ１、ＦＣＢ２、およびＦＣＢ３で示す）さらなるＦＣＢ５０２_１、５０２_２、５０２_３、およびバッファ５０３_１、５０３_２、５０３_３を取得し、それらを元の参照フレーム５０１にリンクしてマルチキャスト・フレーム伝送の各インスタンスを作成する。次いで、各インスタンスは伝送のためにキューに入れられる。

各インスタンスに独自のＦＣＢ５０２およびバッファ５０３は、各インスタンスが伝送されるたびに破棄される。しかし、参照ＦＣＢ５０１およびそれに関連づけられたバッファ５０５_１〜５０５_５は、すべてのインスタンスが伝送された後でのみ破棄される。フレームの各インスタンスは、異なるポートを介して送信することができるので、キューに入れられたのとは異なる順序で伝送を完了することができる。マルチキャスト・カウンタ（ＭＣＣ）は、いつすべてのインスタンスが伝送されて、参照フレームを破棄することができるかを判定するのに使用される。ＭＣＣは、図５の左上に示すように、参照ＦＣＢ５０１の未使用のＮＦＡフィールドに格納される。ＭＣＣは、マルチキャストにおけるインスタンス数で初期化され、その後、各マルチキャスト・インスタンスが伝送されるたびに減分される。ＭＣＣがゼロになると、参照ＦＣＢ５０１およびそれに関連づけられたバッファ５０５_１〜５０５_５は、それぞれ空きＦＣＢおよび空きバッファ・キューに戻されることによって破棄される。

参照ＦＣＢ５０１および他のＦＣＢ５０２_１、５０２_２および５０２_３はすべて、同じＦＣＢの空きプールから来たものである。ＦＣＢが参照ＦＣＢとして使用されているとき、ＮＦＡ／ＭＣＣフィールドはＭＣＣとして使用される。ＦＣＢが正規のもの（非参照ＦＣＢ）として使用されているとき、ＮＦＡ／ＭＣＣフィールドはＮＦＡとして使用される。ＱＣＢとＦＣＢの間の関係は、図１に示してある。ＦＣＢ５０２_１、５０２_２および５０２_３はすべて、伝送のためにキューに入れられる。データフローは、各出力キューごとにＱＣＢを含む。各出力キューは通常、ポート（すなわち、ＰＯＳフレーマ／イーサネット（Ｒ）ＭＡＣを介したネットワーク通信リンク、または交換ファブリックを介した別のネットワーク・プロセッサ）と関連づけられる。図５に示す３つのマルチキャスト・インスタンスはそれぞれ、出力キューに入れられる。３つのインスタンスをすべて、同じポートを介して送信するためにキューに入れることも、異なるポートを介して送信するためにキューに入れることも可能である。しかし、３つのＦＣＢはそれぞれ、ちょうど１つのポートを介して送信する場合には、フレームの１つのキューに配置される。こうしたＦＣＢ中のＮＦＡフィールドは、キュー中のフレームのリンク・リストを形成するのに使用される。ただし、参照ＦＣＢ５０１は、どのキューにも含められない。参照ＦＣＢは、フレームのすべてのインスタンスが伝送された後で元の（参照）フレームのバッファをバッファの空きキューに戻すのに使用されるパラメータを格納する。参照ＦＣＢ５０１は、フレームのキューに含められず、ＮＦＡフィールドは、リンク・リストの形成に必要ない。そうではなく、ＮＦＡのこれらのビットは、ＭＣＣを記憶するために使用される。各フレーム・インスタンスが伝送されるたびに参照ＦＣＢを配置するのに使用されるフレーム・データの前に、参照ＦＣＢのアドレスがＦＡＣＢ（図５）に格納される。

ＥＰＣチップ２０２は、マルチキャスト・フレームの各インスタンスをキューに入れるために、以下の動作を実施する。

１．ＦＣＢ５０２を空きＦＣＢキューから取得して、インスタンスに割り当てる。

２．ＦＡＣＢおよびインスタンスに独自のヘッダ・データを含めるための、１つまたは複数のバッファ５０３を空きバッファ・キューから取得する。ＦＡＣＢの使用は、マルチキャスト伝送に必須である。

３．インスタンスに独自のデータを、上で取得したバッファ５０３に書き込む。マルチキャストの異なるインスタンスが異なるヘッダ・データを有するのは一般的である。たとえば、マルチキャストのあるインスタンスは、イーサネット（Ｒ）・ポートを介して送信されるのでイーサネット（Ｒ）・ヘッダを有し、別のインスタンスは、ＰＯＳポートを介して送信されるのでＰＯＳヘッダを必要とする。

４．独自のインスタンス・バッファに関連づけられたＢＣＢ５０４は、ＢＣＢを元の「参照フレーム」のバッファに接続するリンク・リストを作成するために書き込まれる。独自のインスタンス・バッファは、参照フレームの第１バッファにリンクされる必要はない。参照フレームの先行バイトの一部がインスタンスから除外される場合、インスタンスに独自のバッファを参照フレーム中の第１バッファとは別のバッファにリンクすることができる。次のバッファ中の有効バイトを反映するＳＢＰおよびＥＢＰの値が、各ＢＣＢ５０４に書き込まれる。これにより、インスタンスに独自の最後のバッファに対するＢＣＢ５０４が、他のインスタンス用に指定された他のバイト・オフセットとは異なる、参照フレームからリンクされた第１のバッファ中の開始バイト・オフセットを指定するようになる。ＴＢＵＦビットは、次のバッファが、そのデータが伝送された後ですぐに空きバッファ・キューに戻されるべきかどうかを示すように設定される。インスタンスに独自の最後のバッファは、そのＢＣＢ５０４中のＴＢＵＦビットを０に設定しなければならない。インスタンスに独自の他のすべてのバッファのＢＣＢ５０４中のＴＢＵＦビットは、そのＴＢＵＦビットを１に設定しなければならない。

５．次いで、ネットワーク・プロセッサが、キュー作成動作を発行して、インスタンスを伝送のためにデータフロー２０２に解放する。キュー作成動作の一部として、以下の情報がデータフロー２０２に提供される。

・ターゲット・キューの番号：どの出力キューにマルチキャスト・インスタンスを入れるかを指定する。

・ＦＣＢＡ：ネットワーク・プロセッサによってマルチキャスト・インスタンスに割り当てられたフレーム制御ブロック・アドレス（ＦＣＢＡ）を指定する。

・ＢＣＮＴ：フレームの全長を指定する。各マルチキャスト・インスタンスごとに異なることがある。

・ＦＢＡ：マルチキャスト・インスタンスにおける第１バッファ１０１のアドレスを指定する。第１バッファ１０１は、常にマルチキャスト・インスタンスに独自である。

・ＳＢＰ／ＥＢＰ：第１バッファ１０１中の有効データの開始および終了バイト位置を指定する。

・Ｔｙｐｅ：伝送されるフレームのタイプおよび形式を指定する。「マルチキャスト」フレームの場合、常にバイナリ値「１１」に設定される。この値は、１）フレームがマルチキャスト・インスタンスであること、２）第１バッファ１０１がＦＡＣＢを含むこと、３）第１バッファ１０１が非常駐バッファ（ＴＢＵＦ＝１）であることを意味する。

・ＦＡＣＢ：フレーム・データが伝送されるときにそれに適用される、データフロー２０２に関する変更を指定する、フレーム変更制御ブロック（ＦＡＣＢ）情報。ＦＡＣＢは、マルチキャスト・インスタンスごとに異なるフレーム変更要求を含むことができる。ただし、各インスタンスは、すべてのインスタンスが伝送された後で参照フレームを破棄するのに使用される、参照ＦＣＢ５０１のアドレスを含まなければならない。

・マルチキャスト動作：マルチキャスト・インスタンスをキューに入れるとき、ネットワーク・プロセッサが、現在のキュー作成がマルチキャスト伝送の最初、中間、または最後のインスタンスのどれであるかを指定する。
＊０１：マルチキャストの最初：キューに入れられる最初のインスタンスは、「マルチキャストの最初」と識別される。
＊１０：マルチキャストの中間：マルチキャスト・フレームが２つより多いインスタンスから構成される場合、間にあるインスタンスはどれも「マルチキャストの中間」と識別される。
＊１１：マルチキャストの最後：キューに入れられる最後のインスタンスは、「マルチキャストの最後」と識別される。

以下では、キュー作成動作の受信から、ターゲット出力ポートを介したマルチキャスト・フレーム・インスタンスの送信までのデータフロー・チップの動作を説明する。

１．データフロー・チップ２０２は、情報が書き込まれるバッファ・アドレスおよびオフセットとしてキュー作成中に提供されるＦＢＡおよびＳＢＰの値を使って、ＦＡＣＢ情報をフレームの第１バッファ５０２_１に書き込む。

２．データフロー・チップ２０２は、ＦＡＣＢ情報内部から、参照ＦＣＢ５０１のアドレスを抽出する。このアドレスを使用して、ＭＣＣの値を記憶する参照ＦＣＢ５０１にアクセスする。ＭＣＣの値は、参照ＦＣＢ５０１のＮＦＡフィールドに格納される（参照フレームがどのキュー中にも直接存在しないので、参照ＦＣＢ５０１のＮＦＡフィールドは未使用である）。ＭＣＣ５０６の値は、キュー作成に基づいて以下のように更新される。
・マルチキャスト動作が０１（マルチキャストの最初）の場合、ＭＣＣ５０６は２に設定される。
・マルチキャスト動作が１０（マルチキャストの中間）の場合、ＭＣＣ５０６は１だけ増分される。
・マルチキャスト動作が１１（マルチキャストの最後）の場合、ＭＣＣ５０６は変更されない。

３．データフロー・チップ２０２は、ＦＢＡ、ＳＢＰ、ＥＢＰおよびTypeの値を、キュー作成中に提供されるＦＣＢＡの値で指定されたＦＣＢ５０２に書き込む。

４．データフロー・チップ２０２は、キュー作成中に提供されるターゲット・キュー番号の値で指定される、要求された出力キューにフレームを入れる。これは以下のように行われる。
ａ．それ以前に出力キュー中にフレームがなかった場合、出力キューのＱＣＢ１０４（図１）中の先頭ＦＣＢＡおよび末尾ＦＣＢＡには、キュー作成中に提供されるＦＣＢＡの値が書き込まれる。ＱＣＢ１０４中の先頭ＢＣＮＴには、キュー作成中に提供されるＢＣＮＴの値が書き込まれる。ＱＣＢ１０４中のＱＣＮＴは、１だけ増分される。
ｂ．出力キュー中にすでに１つまたは複数のフレームがあった場合、それ以前は出力キューの末尾にあったフレームに対するＦＣＢ５０２のＮＦＡおよびＢＣＮＴフィールドが書き込まれる。ＮＦＡおよびＢＣＮＴフィールドには、キュー作成中に提供されるＦＣＢＡおよびＢＣＮＴの値が書き込まれる。次いで、出力キューのＱＣＢ１０４（図１）の末尾ＦＣＢＡフィールドには、キュー作成中に提供されるＦＣＢＡの値が書き込まれる。ＱＣＢ１０４中のＱＣＮＴは、１だけ増分される。

５．フレームは、出力キューの先頭に到達すると、出力ポートを介して送信するためにキューからはずされる。先頭ＦＣＢＡおよび先頭ＢＣＮＴフィールドは、出力キューのＱＣＢ１０４から読み出される。先頭ＢＣＮＴの値は、フレーム伝送の間使用するために、作業用バイト・カウント・レジスタにロードされる。先頭ＦＣＢＡの値は、キューの先頭にあるＦＣＢ５０２の内容を読み出すのに使用される。ＦＣＢ５０２から読み出されるＮＦＡおよびＢＣＮＴの値は、ＱＣＢ１０４（図１）の先頭ＦＣＢＡおよび先頭ＢＣＮＴフィールドを更新するのに使用される。ＦＣＢ５０２から読み出されるＦＢＡ、ＳＢＰ、ＥＢＰ、およびTypeフィールドは、第１バッファ５０４_１からのデータ伝送中に使用するために、作業用レジスタにロードされる。次いで、ＦＣＢ５０２は、そのアドレスが空きＦＣＢキューの末尾にプッシュされると、破棄される。ＱＣＢ１０４中のＱＣＮＴは、１だけ減分される。

６．ＦＣＢ１０３から読み出されたＦＢＡ、ＳＢＰ、ＥＢＰ、およびTypeの値は、フレームの第１バッファ１０１の内容の位置決定および読出しに使用する。Typeフィールドはマルチキャストを示し、すなわちＦＡＣＢが存在することを意味する。したがって、次いでＦＡＣＢが、読み出されてフレーム変更論理に転送される。このフレーム変更論理は、フレーム・データが伝送されるとき、それに要求された修正を施すのに使用する。参照ＦＣＢ５０１のアドレスも、ＦＡＣＢから抽出され、フレーム伝送が完了した後で使用するために、作業用レジスタに格納される。バッファ１０１（存在するものがある場合）のフレーム・データは、次いで、出力ポートを介して送信するために、出力ＦＩＦＯ（先入れ先出しバッファ）に配置される。出力ＦＩＦＯに配置されるバイト数は、作業用バイト・カウント・レジスタと、ＳＢＰおよびＥＢＰの値で示される、バッファ１０１中の有効バイト数とのうちの小さい方である。作業用バイト・カウント・レジスタは、次いで、出力ＦＩＦＯに配置されたデータのバイト数だけ減分される。作業用バイト・カウント・レジスタ中の値が依然としてゼロより大きい場合、ＮＢＡ、ＳＢＰ、ＥＢＰ、およびＴＢＵＦの値が、第１バッファ１０１に対応するＢＣＢ１０２から読み出され、次のバッファ１０１の伝送に使用するために作業用レジスタにロードされる。第１バッファ１０１は、次いで、そのバッファ・アドレスが空きバッファ・キューの末尾にプッシュされたとき、破棄される。

７．ＢＣＢ１０２から読み出されたＮＢＡ、ＳＢＰ、ＥＢＰ、およびＴＢＵＦの値は、フレームの次のバッファ１０１の内容の位置決定および読出しに使用される。バッファ１０１のフレーム・データは、次いで、出力ポートを介して送信するために出力ＦＩＦＯに入れられる。出力ＦＩＦＯに入れられるバイト数は、作業用バイト・カウント・レジスタと、ＳＢＰおよびＥＢＰの値で示される、バッファ１０１中の有効バイト数とのうちの小さい方である。作業用バイト・カウント・レジスタは、次いで、出力ＦＩＦＯに入れられたデータのバイト数だけ減分される。作業用バイト・カウント・レジスタ中の値が依然としてゼロより大きい場合、ＮＢＡ、ＳＢＰ、ＥＢＰ、およびＴＢＵＦの値は、現在のバッファ１０１に対するＢＣＢ１０２から読み出され、次のバッファ１０１の伝送に使用するために作業用レジスタにロードされる。現在のバッファ１０１に対するＴＢＵＦビットが設定されている場合、現在のバッファ１０１は、そのバッファ・アドレスを空きバッファ・キューの末尾にプッシュすることによって、破棄される。次いで、作業用バイト・カウント・レジスタがゼロに減分されるまで、ステップ７を繰り返す。

８．フレーム伝送の完了後、それ以前に作業用レジスタに格納されていた参照ＦＣＢアドレスを、参照ＦＣＢ５０１のＮＦＡフィールドに格納されていた、参照ＦＣＢ５０１中のＭＣＣフィールドを読み出すのに使用する。次いで、以下の２つの動作のうち一方を実施する。
・ＭＣＣの値が０より大きい場合、その値を１だけ減分して参照ＦＣＢ５０１のＮＦＡフィールドに戻して書き込む。次いで、このマルチキャスト・インスタンスの伝送が完了する。ただし、他のマルチキャスト・インスタンスが伝送を完了していないので、参照フレームは破棄しなくてよい。
・ＭＣＣの値が１の場合、参照ＦＣＢ５０１は、参照フレームに関連づけられたＦＣＢおよびバッファを空きキューに戻すために、「破棄キュー」に入れられる。次いで、マルチキャスト・フレームのすべてのインスタンスの伝送が完了する。

静的フレーム伝送も、図５にあてはまる。ＦＣＢおよびバッファが、空きＦＣＢおよびバッファ・キューに戻されず、参照ＦＣＢ５０１中のＭＣＣの値が減分されないという点を除けば、静的フレーム伝送は、マルチキャスト伝送と同一である。静的フレーム伝送は、以降の再伝送のためにフレームのコピーを保持する必要がある場合に使用される。図５に示すフレーム・インスタンスはそれぞれ、（ＦＣＢのタイプ・フィールドを、静的フレームを示すようにバイナリ「０１」に設定することによって）１回または複数回、静的フレームとして伝送することができる。フレーム・インスタンスは、（ＦＣＢのTypeフィールドを、マルチキャスト・フレームを示すようにバイナリ「１１」に設定することによって）最後の伝送が行われているとき、通常のマルチキャスト・フレームとして伝送される。したがって、各フレーム・インスタンスは、１〜「Ｎ」回、静的フレームとして伝送することができ、その後で通常のマルチキャスト・フレームとして１回伝送される。各インスタンスが通常のマルチキャスト・フレームとして伝送されると、参照フレームの参照ＦＣＢ５０１およびバッファは、空きＦＣＢおよびバッファ・キューに戻される。ＥＰＣチップ２０９内で実行されるピココード・ソフトウェアが、フレーム・インスタンスを静的またはマルチキャスト・フレームのどちらとして伝送するか決定する。

データフロー・チップ２０２は、フレームのＦＣＢ１０３およびバッファ１０１が空きキューに戻されないという１つの例外を除き、「ＦＡＣＢを有するユニキャスト」のフレームのTypeと全く同じ静的フレームを伝送する。次いで、ＥＰＣチップ２０２は、同じＦＣＢ１０３を、フレームを再伝送するように指定して、別のキュー作成動作を発行することができる。フレームは、静的フレーム・タイプの値を指定することによって、何回でも再伝送することができる。静的フレーム・タイプは、ユニキャストまたはマルチキャスト・フレーム・タイプいずれの再伝送の許可にも適用することができる。マルチキャストの場合、ＴＢＵＦビットが設定されていてもバッファが破棄されないように、静的フレームではＴＢＵＦパラメータは無視される。

静的フレームの最後の再伝送が実施されるとき、静的フレームは、Typeバイナリ「００」（ＦＡＣＢを有するユニキャスト）、またはTypeバイナリ「１１」（マルチキャスト）として、単にキューに入れられる。次いで、フレームは、前のセクションで説明したのと同様にして伝送され、ＦＣＢ１０３および関連づけられたバッファ１０１は、空きキューに戻される。

図６は、本発明の好ましい実施形態の動作を説明するフロー図を示す。処理は、機能ブロック６０１で始まり、ＥＰＣ２０９が、データフロー・チップ２０２がフレームをＥＰＣ２０９にディスパッチするために、クレジットを発行する。判断ブロック６０２で、フレームがディスパッチされたかどうかに関する判定が行われる。ディスパッチされていない場合、機能ブロック６０３で待機する。フレームがディスパッチされると、機能ブロック６０４で、ＥＰＣ２０９は、「Ｎ」個の空きＦＣＢアドレスの借用をデータフロー・チップ２０２に要求する。判断ブロック６０５で、ＦＣＢアドレスが転送されたかどうかに関する判定が行われる。転送されていない場合、処理は機能ブロック６０６で待機する。ＦＣＢアドレスが転送された場合、機能ブロック６０７で、ＥＰＣ２０９は、「Ｎ」個のバッファの借用をデータフロー・チップ２０２に要求する。次いで、判断ブロック６０８で、バッファが転送されたかどうかに関する判定が行われる。転送されていない場合、処理は機能ブロック６０９で待機する。バッファが転送されると、機能ブロック６１０で、ＥＰＣ２０９は、１つまたは複数の新しい第１バッファを元の第１バッファ１０１に連鎖する。次に、機能ブロック６１１で、ＥＰＣ２０９は、ＦＡＣＢ（フレーム変更制御ブロック）情報を有する各インスタンスをキューに入れる。最後に、機能ブロック６１２で、ＥＰＣ２０９は、パケットが１つ伝送される度にカウンタを更新するよう、データフロー・チップ２０２に信号を送る。同様の処理が、ＥＰＣチップ２１０およびデータフロー・チップ２０２にも適用される。ここで説明したフローは、入力にも出力にも等しく適用される。図２に示すように、３つの主要チップ、すなわちＥＰＣ、データフロー、およびスケジューラが、入力および出力の両方で使用される。データの流れる方向が異なるだけである。マルチキャストなど、すべての機能が入力および出力において同一である。

データ構造を示すブロック図である。 本発明の好ましい実施形態のチップ・セット・システム環境を示すブロック図である。 図２のチップ・セット中で使用する、組込みプロセッサ複合体およびデータフロー・チップをより詳細に示すブロック図である。 一般的なメッセージ形式を示す図である。 本発明の好ましい実施形態によるデータ構造を示すブロック図である。 本発明の好ましい実施形態によって実装される処理を示すフロー図である。

Claims (10)

1. ネットワーク・プロセッサにおけるマルチキャスト伝送方法であって、
   伝送されるフレームを、リンク・リストによって互いに連鎖された一連のバッファに格納するステップと、
   バッファ制御ブロックを各バッファに関連づけるステップと、
   フレーム制御ブロックを各フレームに関連づけるステップと、
   ネットワーク・プロセッサによるディスパッチを待つために、フレームをキュー中で受け取るステップと、
   キュー制御ブロックを、前記伝送されるフレーム・キューに関連づけるステップと、
   追加バッファおよび追加フレーム制御ブロックを各マルチキャスト・ターゲットに割り当て、これらの追加フレーム制御ブロックを、前記フレームに関連づけられた前記元のフレーム制御ブロックとリンクするステップと、
   前記フレームが前記マルチキャスト・ターゲットのそれぞれにいつ送られたかを判定するために、マルチキャスト・カウンタを使用するステップと、
   前記フレームが各ターゲットに送られると、各マルチキャスト・ターゲットに割り当てられた前記バッファおよびフレーム制御ブロックを空きキューに戻すステップと、
   前記フレームが前記マルチキャスト・ターゲットのすべてに送られた後で、前記元のバッファおよびフレーム制御ブロックを前記空きキューに戻すステップとを含む、マルチキャスト伝送方法。
2. 各バッファに関連づけられた前記バッファ制御ブロックが、バッファをフレームに連鎖するリンク・リストを形成し、かつ複数のフィールドを含み、前記フィールドには、
   前記フレーム中の次のバッファへのポインタを格納するフィールド、
   次のフレーム・バッファ中のデータの最初の有効バイトのオフセットを格納するフィールド、
   前記次のフレーム・バッファ中のデータの最後の有効バイトのオフセットを格納するフィールド、および
   前記フレーム中の次のバッファを、前記空きバッファまたはキューに戻すべきか、それともマルチキャスト伝送を続けるために保持するべきかを示すフィールドがある、請求項１に記載のマルチキャスト伝送のための方法。
3. 各フレームに関連づけられた前記フレーム制御ブロックが、フレームをキューに連鎖するリンク・リストを形成し、かつ複数のフィールドを含み、前記フィールドには、
   前記キュー中の次のフレームへのポインタを格納するフィールド、
   前記キュー中の次のフレームの総バイト数のカウントを格納するフィールド、
   フレーム中の第１バッファの前記アドレスを格納するフィールド、
   フレームの第１バッファ中の有効データの開始バイト位置を格納するフィールド、
   フレームの第１バッファ中の有効データの終了バイト位置を格納するフィールド、および
   伝送される前記フレームの形式およびタイプに関する情報を格納するフィールドがある、請求項１または２に記載のマルチキャスト伝送のための方法。
4. フレームをキュー中で受け取る前記ステップが、
   前記空きバッファ・キューの先頭から空きバッファ・アドレスをポップするステップと、
   前記空きフレーム制御ブロック・キューの先頭から空きフレーム制御ブロックをポップするステップと、
   フレーム・データを前記バッファに書き込むステップと、
   第１バッファ・アドレス、前記第１バッファ中の有効データの開始および終了バイト位置を含む制御情報を、前記フレーム制御ブロックに書き込むステップと、
   作業用バイト・カウント・レジスタを前記第１バッファに書き込むバイト数に設定するステップと、
   前記フレーム全体がバッファに書き込まれるまでこの処理を繰り返すステップと、
   前記ネットワーク・プロセッサへのディスパッチを待つために、前記フレームを入力キューの末尾に追加するステップとをさらに含む、請求項１ないし３のいずれかに記載のマルチキャスト伝送のための方法。
5. 伝送される前記フレーム・キューに関連づけられた前記キュー制御ブロックが、複数のフィールドを含み、前記フィールドには、
   前記キューの先頭にある前記フレームに関連づけられた前記フレーム制御ブロックの前記アドレスを格納するフィールド、
   前記キューの先頭にある前記フレーム中の有効バイトの総数のカウントを格納するフィールド、および
   前記キューの末尾にある前記フレームに関連づけられた前記フレーム制御ブロックの前記アドレスを格納するフィールドがある、請求項１ないし４のいずれかに記載のマルチキャスト伝送のための方法。
6. 方法に関する請求項１ないし５のいずれかに記載の方法の前記各ステップをコンピュータに実行させる、コンピュータ・プログラム。
7. マルチキャスト伝送をサポートするネットワーク・プロセッサであって、
   伝送されるフレームを、リンク・リストによって互いに連鎖された一連のバッファに格納する手段と、
   バッファ制御ブロックを各バッファに関連づけ、フレーム制御ブロックを各フレームに関連づける手段と、
   ディスパッチを待つために、フレームをキュー中で受け取る手段と、
   キュー制御ブロックを、伝送される前記フレーム・キューに関連づける手段と、
   追加バッファおよび追加フレーム制御ブロックを各マルチキャスト・ターゲットに割り当て、これらの追加フレーム制御ブロックを、前記フレームに関連づけられた前記元のフレーム制御ブロックにリンクする手段と、
   前記フレームが前記マルチキャスト・ターゲットのそれぞれにいつ送られたかを判定するために、マルチキャスト・カウンタを使用する手段と、
   前記フレームが各ターゲットに送られると、各マルチキャスト・ターゲットに割り当てられた前記バッファおよびフレーム制御ブロックを空きキューに戻し、かつ、前記フレームが前記マルチキャスト・ターゲットのすべてに送られた後で、前記元のバッファおよびフレーム制御ブロックを前記空きキューに戻す手段とを備える、ネットワーク・プロセッサ。
8. 各バッファに関連づけられた前記バッファ制御ブロックが、バッファをフレームに連鎖するためにリンク・リストを形成し、かつ複数のフィールドを含み、前記フィールドには、
   前記フレーム中の次のバッファへのポインタを格納するフィールド、
   フレームの次のバッファ中のデータの最初の有効バイトのオフセットを格納するフィールド、
   フレームの次のバッファ中のデータの最後の有効バイトのオフセットを格納するフィールド、および
   前記フレーム中の次のバッファを、前記空きバッファまたはキューに戻すべきか、それともマルチキャスト伝送を続けるために保持するベきかを示すフィールドがある、請求項７に記載のネットワーク・プロセッサ。
9. 各フレームに関連づけられた前記フレーム制御ブロックが、フレームをキューに連鎖するためのリンク・リストを形成し、かつ複数のフィールドを含み、前記フィールドには、
   前記キュー中の次のフレームへのポインタを格納するフィールド、
   前記キュー中の次のフレームの総バイト数のカウントを格納するフィールド、
   フレーム中の第１バッファの前記アドレスを格納するフィールド、
   フレームの第１バッファ中の有効データの開始バイト位置を格納するフィールド、
   フレームの第１バッファ中の有効データの終了バイト位置を格納するフィールド、および
   伝送される前記フレームの形式およびタイプに関する情報を格納するフィールドがある、請求項７または８に記載のネットワーク・プロセッサ。
10. フレームをキュー中で受け取る前記手段が、
    前記空きバッファ・キューの先頭から空きバッファ・アドレスをポップする手段と、
    前記空きフレーム制御ブロック・キューの先頭から空きフレーム制御ブロックをポップする手段と、
    フレーム・データを前記バッファに書き込む手段と、
    第１バッファ・アドレス、第１バッファ中の有効データの開始および終了バイト位置を含む制御情報を、前記フレーム制御ブロックに書き込む手段と、
    作業用バイト・カウント・レジスタを、第１バッファに書き込むバイト数に設定する手段と、
    前記フレーム全体がバッファに書き込まれるのに応答して、前記ネットワーク・プロセッサへのディスパッチを待つために、前記フレームを入力キューの末尾に追加する手段とを備える、請求項７、８、または９に記載のネットワーク・プロセッサ。

Images