(57)【要約】  パケットのストリーム上でユーザが設定することができるトラヒック管理機能を実行するための技術。この機能は、シェーピングおよびセグメント分割および再組立てを含むマルチキャスト、廃棄、スケジューリングを含む。上記技術の場合、上記機能は、ストリームのパケット上で直接実行されるのではなく、記憶したパケットを表す記述子上で実行される。パケットの記述子は、パケットに対する少なくとも１つの識別子および記述子上で実行されるトラヒック管理機能のセットに対する指定子を含む。ユーザは、記述子のトラヒック・キューに対するトラヒック管理機能のセットを構成する。マルチキャストの場合には、記述子はコピーされ、２つ以上のトラヒック・キュー上に置かれる。廃棄の場合には、記述子は廃棄トラヒック・キュー内に置かれる。廃棄トラヒック・キュー内の記述子が表すパケットは、バッファから廃棄される。廃棄トラヒック・キューを含むすべてのトラヒック・キューからの記述子の出力はスケジュールされる。スケジューリングはスケジューラの階層により行われる。この技術はトラヒック管理コプロセッサ集積回路で実施される。本明細書は、また、修正部分パケット廃棄アルゴリズムおよびフレームをベースとする不足ラウンドロビン・スケジューリング・アルゴリズムも開示している。
2005510893.tif 000002
【特許請求の範囲】
【請求項１】
第１トラヒック・ストリーム処理装置において記述子によって表されるパケットからなるトラヒック・ストリーム上で、第１の複数のストリーム処理機能を実行する前記第１トラヒック・ストリーム処理装置と、前記記述子を使用して前記トラヒック・ストリーム処理装置のために第２の複数のトラヒック管理機能を実行する第２トラヒック管理装置との間で情報を転送し、
前記記述子と前記複数のトラヒック管理機能の第１のサブセットを選択する少なくとも第１選択子とを前記第１装置から前記第２装置へ転送する前記第１装置と前記第２装置との間の第１データ経路と、
前記第１のサブセットの内の機能が実行された後に、前記記述子と前記ストリーム処理機能の第２のサブセットを選択する少なくとも第２選択子とを前記第２装置から前記第１装置へ転送する前記第１装置と前記第２装置との間の第２データ経路とを備えるインタフェース。
【請求項２】
前記インタフェースは、前記第１装置が、前記記述子によって表される前記パケット上で前記第２のサブセットの内の機能を実行することができる場合に、前記第１装置から前記第２装置へ前記第２選択子を転送する前記第１装置と前記第２装置との間の第３データ経路を備え、前記第２装置は、該第２装置から前記第１装置への前記機能が実行されるパケットを表す記述子の流れを制御するために前記第２選択子を使用する、請求項１に記載のインタフェース。
【請求項３】
前記第１装置は前記記述子を前記ストリーム処理機能の前記第２のサブセットと関連づけるために第１キューを使用し、
前記第２装置は前記記述子を前記トラヒック管理機能の前記第１のサブセットと関連づけるために第２キューを使用し、
前記第１選択子は前記第２キューを指定し、前記第２選択子は前記第１キューを指定し、
前記第１キューの先頭から記述子が除去されたときに、前記第２選択子が前記第２装置に転送される、請求項２に記載のインタフェース。
【請求項４】
前記第２装置が、前記第１データ経路を介して前記第１装置から前記第２装置への転送を受け入れることができるかどうかを示す指標を転送する前記第１装置と第２装置との間の第４データ経路と、
前記第１装置が、前記第２データ経路を介して前記第２装置から前記第１装置への転送を受け入れることができるかどうかを示す指標を転送する前記第１装置と第２装置との間の第５データ経路と、
前記第２装置が、前記第３データ経路を介して前記第２装置から前記第１装置への転送を受け入れることができるかどうかを示す指標を転送する前記第１装置と第２装置との間の第６データ経路とをさらに備える、請求項１に記載のインタフェース。
【請求項５】
複数のパケットからなり、かつトラヒック・ストリーム・プロセッサによって処理されるトラヒック・ストリームのためのトラヒック管理動作を実行する装置であって、該装置は、
複数のトラヒック管理機能と、
前記トラヒック・ストリーム・プロセッサからトラヒック管理機能指定子に関連づけられた記述子を受信する入力装置と、前記記述子は前記トラヒック・ストリーム・プロセッサによって処理されるパケットを表すことと、前記記述子に関連づけられた前記トラヒック管理機能指定子は前記トラヒック管理機能のサブセットを指定することと、
前記記述子で前記関連トラヒック管理機能指定子によって指定される前記サブセット内
の少なくとも１つのトラヒック管理機能を実行し、前記記述子を前記トラヒック・ストリーム・プロセッサにおいて機能を指定するトラヒック・ストリーム・プロセッサ機能指定子と関連づける処理構成要素と、
前記トラヒック・ストリーム・プロセッサに前記記述子および前記トラヒック・ストリーム・プロセッサ機能指定子を提供する出力装置とを備える装置。
【請求項６】
複数のパケットからなるトラヒック・ストリームに対してトラヒック管理動作を実行する装置であって、
該装置は、
トラヒック・ストリーム内のパケットを表す複数の記述子のセットと、
複数のトラヒック管理機能と、前記複数のトラヒック管理機能のサブセットと関連付けられている記述子の所与のセットと、
前記所与のセットに属する記述子において記述子のセットと関連付けられている前記サブセットにある少なくとも１つのトラヒック管理機能を実行する処理構成要素とを備える装置。
【請求項７】
記述子が前記トラヒック・ストリームを処理するストリーム・プロセッサから受信され、前記記述子のセットに関連づけられたトラヒック管理機能が前記記述子で実行された後で、前記ストリーム・プロセッサに提供される、請求項６に記載の装置。
【請求項８】
前記ストリーム・プロセッサから受信した前記記述子は、前記複数の記述子のセットうちの１つを指定するセット指定子を備える、請求項７に記載の装置。
【請求項９】
前記トラヒック管理機能はマルチキャスト機能を含み、
前記複数の記述子のセットは、前記マルチキャスト機能が前記複数の記述子のセットの内の複数の他のセットにコピーする記述子用の記述子のマルチキャスト・セットを含む、請求項８に記載の装置。
【請求項１０】
前記トラヒック管理機能は、前記記述子のセット指定子によって指定されたセット内に置く代わりに、廃棄するパケットを表す受信した記述子を選択する廃棄機能のセットを含み、前記選択した記述子は、前記記述子が表すパケットを廃棄すべきことを示す指標と共に前記ストリーム・プロセッサに提供される、請求項８に記載の装置。
【請求項１１】
前記装置は、前記セット内の前記記述子が表すパケットが属するトラヒック・ストリームの状態のモデルをさらに有し、
前記セット内の前記廃棄機能は、前記セットからのパケットを廃棄すべきかどうかを判断するために前記モデルを使用する、請求項１０に記載の装置。
【請求項１２】
前記モデルは前記ストリーム・プロセッサ内のバッファの状態をモデル化し、前記バッファは前記ストリームに属するパケットからのペイロードを記憶するために使用される、請求項１１に記載の装置。
【請求項１３】
前記モデルは前記ストリームの帯域幅の使用をモデル化する、請求項１１に記載の装置。
【請求項１４】
前記トラヒック管理機能は受信した前記ストリーム・プロセッサに記述子をいつ提供すべきかを決定するスケジューリング機能のセットを含む、請求項７に記載の装置。
【請求項１５】
前記スケジューリング機能は、前記記述子が前記ストリーム・プロセッサに提供される時、前記記述子と共に含まれている前記ストリーム・プロセッサ内の記述子のセットに対する指定子を決定する、請求項１４に記載の装置。
【請求項１６】
前記トラヒック管理機能は、前記記述子のセット指定子によって指定された前記セット内に置く代わりに、廃棄するパケットを表す受信した記述子を選択する廃棄機能のセットと、前記ストリーム・プロセッサに記述子をいつ提供すべきかを決定し、前記ストリーム・プロセッサ内の記述子のセットに対する指定子を、提供中の前記記述子に追加するスケジューリング機能のセットとを含み、
前記記述子のセットは、廃棄すべきパケットを表す記述子を含む廃棄記述子のセットを含み、
前記廃棄記述子のセットから提供された記述子に追加された追加指定子は、廃棄すべきパケットを表すストリーム・プロセッサ内の記述子のセットを指定する、請求項７に記載の装置。
【請求項１７】
前記記述子によって表される前記パケット内に少なくともその一部が含まれているメッセージが、前記ストリーム・プロセッサ内に完全に受信される前に、前記装置が前記ストリーム・プロセッサから前記記述子を受信する、請求項７に記載の装置。
【請求項１８】
前記トラヒック管理機能は、前記ストリーム・プロセッサに記述子をいつ提供すべきかを判断するスケジューリング機能のセットを含み、
前記メッセージが前記ストリーム・プロセッサ内に完全に受信された場合に、前記ストリーム・プロセッサは前記装置へ通知を提供し、
前記ストリーム・プロセッサ内に前記メッセージが完全に受信される前に、前記ストリーム・プロセッサから前記記述子を受信した場合に、前記プロセッサ構成要素は、前記通知を受信するまで前記記述子上でスケジューリング機能を実行しない、請求項１７に記載の装置。
【請求項１９】
前記トラヒック管理機能は、前記パケットに対する前記記述子からパケットの一部を表す一連の記述子を生成するセグメント分割機能を含む、請求項７に記載の装置。
【請求項２０】
前記トラヒック管理機能は、前記ストリーム・プロセッサへのより大きなパケットに再組立てされるパケットを表す連続している一連の記述子を提供する再組立て機能を含む、請求項７に記載の装置。
【請求項２１】
所与の記述子のセットと前記複数のトラヒック管理機能のサブセットとの間の関連が設定可能である、請求項６に記載の装置。
【請求項２２】
前記複数のトラヒック管理機能は設定可能である、請求項２１に記載の装置。
【請求項２３】
前記複数のトラヒック管理機能および前記処理構成要素は１つの集積回路において実施される、請求項６に記載の装置。
【請求項２４】
前記記述子のセットはキューとして編成され、その場合、受信した記述子が前記キューの末尾に置かれ、提供される記述子が前記キューの先頭から提供される、請求項７に記載の装置。
【請求項２５】
パケットからなり、トラヒック・ストリーム・プロセッサによって処理されるトラヒック・ストリームに対するトラヒック管理動作を実行する装置であって、
マルチキャスト機能、廃棄機能およびスケジューリング機能を含み、ユーザによる設定が可能なトラヒック管理機能と、
それぞれが少なくとも１つの前記トラヒック管理機能とのユーザ設定が可能な関連を有する、前記パケットを表す記述子の複数のトラヒック管理キューと、
記述子をトラヒック管理キュー内に置き、前記トラヒック・ストリーム・プロセッサ内のキューに対する指定子と共に前記トラヒック・ストリーム・プロセッサに出力される前記記述子のスケジューリングを行うために、関連するキュー指定子によって指定される前記トラヒック管理キューに関連づけられた前記トラヒック管理機能を使用することによって、前記ストリーム・プロセッサから受信する前記記述子および該記述子に関連づけられたキュー指定子に応答する処理構成要素とを備える装置。
【請求項２６】
パケットが記述子によって表されるシステムにおいて、メッセージを運ぶシーケンスに属するパケットを廃棄するための方法であって、該方法は、前記システムが前記メッセージを運ぶ前記パケットを１つの集合パケットに組立てる時に使用され、
前記シーケンスのパケットを廃棄する第１の決定の際に、前記パケットを表す前記記述子をメッセージの終わりパケットの記述子として、また不足パケットの記述子としてマークし、前記記述子によって表される前記パケットを前記集合パケットに組立てることにより、前記記述子に応答する組立装置に前記記述子を提供するステップと、
前記マークを付けた記述子の後の前記メッセージの前記パケットに対する前記記述子を、前記記述子に応じて前記パケットを廃棄する前記システム内のパケット廃棄装置に提供するステップと、
前記組立装置において、前記集合パケットを廃棄することにより、前記マークを付けた記述子に応答するステップとを含む方法。
【請求項２７】
パケットが記述子により表されるシステムにおいて、全メッセージがシステムに受信される前に、メッセージのパケットを表す記述子の処理を開始するための方法であって、
前記記述子のスケジューリングを行う以外の前記記述子上で処理を行うステップと、
全メッセージを前記システム内にすでに受信したという通知を受け取った場合に、前記記述子のスケジューリングを行うステップとを含む方法。
【請求項２８】
前記通知がおそらく到着しないと決定するステップと、
前記システムに前記記述子が示す前記パケットを廃棄させるステップとをさらに含む、請求項２７に記載の方法。
【請求項２９】
前記記述子は全メッセージを含むパケットを表す、請求項２８に記載の方法。
【請求項３０】
前記記述子は、前記メッセージを含むパケットの多重パケット・シーケンス内のパケットを表す、請求項２８に記載の方法。
【請求項３１】
パケットのストリームを処理する装置でさらに処理を行うために、前記パケットのスケジューリングを行うための装置であって、該装置は、
少なくとも１つの内部ノードと１つのリーフ・ノードを有する１つの階層のノードを形成する複数のスケジューラと、
前記リーフ・ノード・スケジューラに関連づけられたパケットのセットと、
スケジューリングを行うために、前記リーフ・ノード・スケジューラと関連する前記セットの内のパケットを選択するために、前記リーフ・ノード・スケジューラと前記内部ノード・スケジューラを実行するプロセッサとを備え、
複数のスケジューリング・アルゴリズムの中から選択した１つのスケジューリング・アルゴリズムによりスケジューリングを行うように前記スケジューラを個々に設定可能な装置。
【請求項３２】
前記パケットのセットと前記リーフ・ノード・スケジューラとの間の関連は設定可能である、請求項３１に記載の装置。
【請求項３３】
前記階層の形状は設定可能である、請求項３１に記載の装置。
【請求項３４】
前記階層は前記階層のルート・ノードである１つの内部ノード・スケジューラを有し、
前記階層を通る各リーフ・ノード・スケジューラから前記ルート・ノードへの一意的な経路が存在し、
前記一意的な経路が前記パケットに対する別の処理のモードと関連している、請求項３１に記載の装置。
【請求項３５】
前記モードは、前記経路と関連する仮想出力ポート番号によって指定される、請求項３４に記載の装置。
【請求項３６】
前記パケットのセットは、前記セット内のパケットを表す記述子のセットによって前記リーフ・ノードスケジューラと関連づけられている、請求項３１に記載の装置。
【請求項３７】
前記記述子のセットは記述子の少なくとも１つのトラヒック・キュー、および前記トラヒック・キューの少なくとも１つのスケジューラ・キューに編成され、各スケジューラ・キューは、前記記述子のセットが関連付けられている前記リーフ・ノード・スケジューラの入力と関連付けられている、請求項３６に記載の装置。
【請求項３８】
前記複数のスケジューリング・アルゴリズムは、厳格な優先順位アルゴリズム、ラウンドロビン・アルゴリズム、および加重均等化キューイングアルゴリズムを含む、請求項３１に記載の装置。
【請求項３９】
前記階層のノード内のスケジューラは、保証スケジューラ、過度スケジューラ、および前記保証スケジューラに第１の優先順位を与える厳格な優先順位スケジューラを含むスケジューラ・リソースから構成される、請求項３８に記載の装置。
【請求項４０】
複数の加重均等化キューイングアルゴリズムが存在し、該複数の加重均等化キューイングアルゴリズムは非作業保存加重均等化キューイングアルゴリズムを含む、請求項３８に記載の装置。
【請求項４１】
可変長パケットのスケジューリングを行うための方法であって、該方法は、前記パケットのセットの内の２つのセットを使用し、
スケジューリングを行うために前記パケットのセットの内の前記２つのセットの内の現在のセットに属する所与のパケットのセットを選択するステップであって、前記パケットのセットの内の現在のセットに属する各パケットのセットは最大割合および最小割合に関連づけられており、前記所与のパケットのセットは前記最小割合の決定に従ってスケジューリングのために選択された状態のままに維持され、前記最小割合は、再びスケジューリングを行うために、前記複数のセットの内の前記現在のセットに属するパケットのセットを選択する前に、前記選択したパケットのセットからスケジューリングを行うことができるパケットの全サイズを決定するステップと、
前記最大割合の決定に従って前記パケットのセットの内の前記２つのセットの内の他方の中に前記所与のパケットのセットを置くステップであって、前記最大割合が、前記選択したセットが前記パケットのセットの内の前記２つのセットの内の他方の中に入れられる前に、前記選択したセットからスケジューリングを行うことができるパケットの全サイズを決定するステップと、
前記パケットのセットの内の前記現在のセットが空になった場合に、前記パケットのセットの内の前記現在のセットと前記パケットのセットの内の他のセットとを交換するステップとを含む方法。
【請求項４２】
前記パケットのセットは、前記現在のセットから次のセットに移動した場合、実際にスケジュールされている前記パケットの全サイズと、前記パケットのセットが前記２つのパケットのセットの内の他方に入れられた時点の前記最大割合との間の違いにより新しい最大割合を計算するステップをさらに含む、請求項４１に記載の方法。
【請求項４３】
前記現在のセットに属するパケットのセットがスケジュールのために選択不能になった場合に、前記現在のセットから前記選択不能なパケットのセットを除去するステップと、
選択不能なパケットのセットがスケジュールのために選択可能になった場合に、前記選択可能なセットを次のセットに追加するステップとをさらに含む、請求項４１に記載の方法。
【請求項４４】
パケットのセットの内の前記現在のセットはある順序に配列されたセットであり、前記パケットのセットはラウンドロビン方式でスケジューリングのために選択される、請求項４１に記載の方法。
【請求項４５】
前記現在のセット内の前記パケットのセットは、ある順序で配列されたセットであり、パケットのセットがスケジューリングのために選択された場合、パケットがラウンドロビン方式でそのセットから選択される、請求項４１に記載の方法。
【請求項４６】
パケットのセットの内の前記現在のセットよりも、スケジューリングについて高い優先順位を有するパケットのセットの内の第３のセットを使用し、
前記所与のパケットのセットがパケットのセットの内の前記第３のセットに属し、一方、前記所与のパケットのセットが、前記最小割合の決定に従ってスケジューリングのために選択された状態のまま維持され、その後で、パケットのセットの内の前記現在のセットに移動し、前記最大割合の決定に従ってそこからスケジュールされる、請求項４１に記載の方法。
【請求項４７】
パケットのセットの内の前記現在のセットおよびパケットのセットの内の前記第３のセットが、ある順序で配列されたセットであり、前記パケットのセットが、前記現在のパケットのセットおよび前記第３のパケットのセット内で、ラウンドロビン方式でスケジューリングのために選択される、請求項４６に記載の方法。
【請求項４８】
前記現在のセット内の前記パケットのセットおよびパケットのセットの内の前記第３のセットは、ある順序で配列されたセットであり、スケジューリングのためにパケットのセットが選択された場合に、そのセットからパケットがラウンドロビン方式で選択される、請求項４７に記載の方法。
【請求項４９】
各パケットは記述子によって表現され、前記パケットは前記パケットのセット内でその記述子によって表現される、請求項４１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願への相互参照）
本特許出願は、２００１年４月１３日に提出された米国仮特許出願番号６０／２８３７４６の優先権を主張する。
【０００２】
本発明は、一般に、パケット・スイッチおよびルータなどの装置でのデジタル・データのストリームの処理に関する。本発明は、より詳細には、出力ストリームのシェーピングおよび出力ストリームのセグメント分割または再組立てを含む多数のストリームへのパケットのマルチキャスト、ストリーム内のパケットの廃棄、およびスケジューリングなどの処理に関する。
【背景技術】
【０００３】
＜パケットおよびプロトコル＞
デジタル・システム間の通信では、通常「パケット」が使用される。図１の参照番号１１３はパケットを示す。パケットとは、その意味がプロトコルにより決定される単なる一連のビットである。プロトコルとは、パケットを処理するデジタル装置が、パケット内のビットをどのように解釈すべきかを定義するものである。大部分のパケットは、プロトコルが何であれ、特定のパケットをプロトコルに従ってどのように処理すべきかを示すヘッダ１１５、およびパケットにより送られる実際の情報であるペイロード１１７を有する。パケットは、このほかに単にパケットの終わりを示し得るトレーラ１１９を有することがあるが、パケットの送信または処理中に発生した誤りを検出または訂正することができる情報を含むこともある。パケットは、パケットを定義するプロトコルに応じて、固定長または可変長であり得る。以下の説明においては、ヘッダ１１５およびトレーラ１１９の内容を「プロトコル・データ」と呼ぶ。この理由は、ヘッダ１１５およびトレーラ１１９の内容を解釈する方法が、プロトコルにより完全に決定されるためである。ペイロード１１７の内容は「ペイロード・データ」と呼ばれる。あるプロトコルに対するパケットは、多くの場合、「フレーム」または「セル」と呼ばれる。
【０００４】
パケットは、デジタル・システムにおいて、多様なレベルで通信のために使用される。このため、デジタル・システムのあるレベルでのパケットのグループのペイロードが、より高いレベルのパケットであることもある。このような例を、図１の参照番号１３７に示す。ＩＰパケット１２１は、ＩＰプロトコルにより解釈されるパケットである。ＩＰパケット１２１は、ＩＰヘッダ１２３および可変長ＩＰペイロード１２５を有する。ＩＰヘッダ１２３内の情報には、ＩＰペイロード１２５の長さが含まれている。ＩＰパケット１２１が物理ネットワークを介して送られる場合には、ＩＰパケットは、転送パケット１２７のストリーム１３５のペイロードで送信される。各転送パケット１２７は、自分自身のヘッダ１２９、ペイロード１３１、およびトレーラ１３３を有する。本明細書で転送パケットとの用語は、ＩＳＯ７層モデルのリンク層におけるパケットを指す。転送パケットは、リンク層内で使用するプロトコルに応じて、固定長または可変長であり得る。
【０００５】
転送パケットを処理する装置は、パケット内のヘッダ１２９およびトレーラ１３３に示されるとおりに処理を行い、ペイロード１３１の内容をチェックしない。転送パケットがその宛先に到着した場合には、ペイロードは、本例ではＩＰプロトコルにより動作する構成要素であるシステムの目的の部分に送られ、この構成要素がＩＰヘッダ１２３に示されるとおりにＩＰパケット１２１を処理する。当然ながら、ＩＰペイロード１２５は、他のより高いレベルに対するパケットであってもよい。例えば、ＩＰペイロードは、解読装置宛のパケットであってもよいし、そのパケットのペイロードは、暗号化されたＩＰパケッ
ト１２１であってもよい。このような場合、ＩＰパケット１２１を処理する構成要素は、ペイロードを解読装置に送る。解読装置は暗号化されたＩＰパケット１２１を解読し、解読したＩＰパケットをさらに処理するするため、ＩＰパケットを処理する構成要素に返送する。当然ながら、この処理は、解読したＩＰパケットの他の宛先への送信を含み、その宛先との通信が転送パケット１２７に対するプロトコルに従う場合には、ＩＰパケットを処理する構成要素は、解読したＩＰパケットを、転送パケット・ストリームを生成する構成要素に提供し、解読されたＩＰパケットは転送パケット１２７のペイロードに格納される。
＜パケット・スイッチ＞
相互に離れた場所にあるデジタル・システム間で通信を行うためにパケットを使用する場合には、パケットは、システムを接続しているデジタル・ネットワーク上を移動する。デジタル・ネットワークは、物理レベルで、２つの装置間で信号を送信するために、例えば、イーサ（ｅｔｈｅｒ）、導線または光ケーブルなどの任意の媒体を使用することができる。パケットは、パケット・スイッチにより送信経路間でルーティングされる。パケット・スイッチは、通常は、パケット・ヘッダ内に含まれている情報によりパケットをルーティングする。
【０００６】
予想されるように、各種のプロトコルは、それ自身のルーティング規則を有する。例えば、ＩＰプロトコルは、論理ルーティング（ｌｏｇｉｃａｌ  ｒｏｕｔｉｎｇ）を使用する。この場合、ＩＰパケットの各ソースまたは宛先は論理ＩＰアドレスを有し、所与の宛先へのＩＰパケットは、そのヘッダ内に宛先の論理ＩＰアドレスを有する。ヘッダは宛先の物理的な位置を示すものではない。ＩＰパケット・スイッチは、宛先への経路の少なくとも一部でＩＰアドレスをパケットを取得する物理アドレスに変換しなければならず、その物理アドレス宛てのＩＰパケットをペイロード１３１として運ぶ転送パケットのストリーム１３５を生成しなければならない。このため、ＩＰノード１０９（ｎ）はイーサネットＬＡＮ１０５（ａ）上のイーサネット・ノード１０７（ｎ）上に位置し、ＬＡＮ１０５（ａ）に接続しているＩＰパケット・スイッチは、そのペイロードとしてＩＰパケットを運ぶイーサネット・ノード１０７（ｎ）宛のイーサネット・パケットのストリームを生成することにより、ＩＰノード１０９（ｎ）宛のＩＰパケットに応答しなければならない。
【０００７】
参照番号１０３は、典型的なパケット・スイッチを示す。パケット・スイッチ１０３は、多数の物理媒体１０６に接続しており、これによって、パケット・スイッチ１０３はデータを送受信することができるようになる。このような媒体の例としては、光ファイバ・ケーブル、または導体からなるケーブル等がある。このような各媒体１０６は、媒体を介して送られるデータを定義するため、自身のプロトコルを有する。光ケーブルによりデータを送るために広く使用されている１つのプロトコルの例に、ＳＯＮＥＴプロトコルがある。図１においては、媒体１０６（ａ…ｍ）はＳＯＮＥＴプロトコルを使用する光ケーブルであり、媒体１０６（ｎ…ｚ）は電気ケーブルである。本明細書においては、媒体パケットと呼ぶ媒体レベルのパケットは、自身のペイロード転送パケットを有する。ＩＳＯ７層モデルの場合には、媒体パケットは、物理層パケットである。スイッチ１０３においては、光ケーブル上で送受信される転送パケットは、ＡＴＭワイド・エリア・ネットワーク１１１で使用されるＡＴＭプロトコルに従って形成されたパケットであり、一方、電気ケーブル上で送受信される転送パケットは、ローカル・エリア・ネットワーク１０９で使用されるイーサネット（商標）プロトコルに従って形成される。多くの場合、転送パケットは、そのペイロードとしてＩＰパケットを有し、このような場合、パケット・スイッチ１０３は、ＩＰパケットをＩＰノード１０９にルーティングする。すでに説明したように、パケット・スイッチは、その宛先に到着するためにＩＰパケットが移動しなければならない媒体１０６（ｉ）を決定し、次にそのペイロードとしてその媒体と併用する転送パケット・ストリームを有する媒体のために必要なプロトコルに従ってパケットのストリームを生成することによって上記ルーティングを行い、パケットのストリームはそのペイロード
としてＩＰパケットを有する。このため、パケット・スイッチ１０３がＷＡＮ１１１からＩＰノード１０９（ｎ）宛のＩＰパケットを受信し、ＩＰノード１０９（ｎ）がイーサネットＬＡＮ１０５（ａ）上のイーサネット・ノード１０７（ｎ）内に位置している場合には、パケット・スイッチ１０３は、そのペイロードが、そのペイロードとしてＩＰパケットを運ぶイーサネット・ノード１０７（ｎ）宛のイーサネット・パケットのストリームである媒体１０６（ｎ）が必要とする形でパケットのストリームを形成しなければならない。
【０００８】
パケット・スイッチ１０３が実行する機能は、パケット・スイッチが動作するネットワーク環境およびパケット・スイッチの能力により異なる。本明細書においては、以下の説明のために重要な機能をトラヒック管理機能と呼ぶ。トラヒック管理機能には下記の３つの一般的なグループがある。
【０００９】
・特定の発信元から受信したパケットを少なくとも１つの異なる宛先にルーティングする機能。
・ルーティングのためにパケット・ストリームを変換する機能。
【００１０】
・データを送信するスイッチ１０３も装置も、過負荷とならないように、またサービスを提供するスイッチ１０３およびネットワークが均等化に効率的に使用されるようにトラヒックを制御する機能。
【００１１】
これらの機能についてさらに詳細に説明すると、ルーティングはフィルタリングおよびマルチキャストを含む。フィルタリングはネットワーク境界において行われる。図では、パケット・スイッチ１０３は、専用網１０４と公衆網１０２の間の境界に位置する。各ＩＰパケット１２１のヘッダは、そのパケットに対する発信元ＩＰアドレスおよび宛先ＩＰアドレスを含み、専用網１０４の機密保護ポリシーは、専用網１０４へのいくつかの発信元アドレスを含む公衆網１０２からのＩＰパケットによるアクセスを禁止し、同様に公衆網１０２へのいくつかの発信元アドレスを含む専用網１０４からのパケットによるアクセスも禁止する。スイッチ１０３は、その発信元アドレスを、禁止すべき発信元アドレスのリストと比較することにより、受信した各ＩＰパケットをフィルタリングし、受信パケットの発信元アドレスがリストに存在する場合には、それを廃棄する。スイッチ１０３は同じような方法によって送信パケットをフィルタリングする。マルチキャストとは、発信元から受信したパケットのコピーを複数の宛先に送信することである。
【００１２】
ストリーム変換は、ＡＴＭ転送パケットのストリームとして受信したＩＰパケットを、イーサネット転送パケットのストリームとして、その宛先に送信されるＩＰパケットに変換する上記の変換のような動作を含む。このような動作は、通常、スイッチで高いレベルのパケットを受信した場合に、その転送パケットのペイロードからより高いレベルのパケットを再組立てするステップと、それがスイッチから送信される時に、より高いレベルのパケットを転送パケットにセグメント分割するステップとを含む。ストリーム変換には、また、ペイロードの暗号化および解読も含まれる。暗号化または解読が行われる場所としてはネットワークの境界等がある。例えば、専用網１０４の機密保護ポリシーは、公衆網１０２内のある宛先に送るＩＰパケットを暗号化することを要求する場合があり、暗号化はスイッチ１０３内で実行することができる。また、スイッチ１０３は、専用網１０４にパケットが着信した場合には、これらの宛先からのパケットを解読することができる。
【００１３】
トラヒックの制御は、スイッチ１０３およびその下流の宛先を、出力帯域幅が効率的に使用され、可能な範囲でネットワーク・リソースおよびタイミングの点で各出力ストリームの要件が満足できるようにパケットを廃棄し、スイッチ１０３からのパケットの出力のスケジュールを作成することにより過負荷にならないようにするステップを含む。この点
に関し、出力ストリームのこの要件は、「サービス・クラス」と呼ばれる。パケット・スイッチは、電子メールからパケット電話までの範囲のサービス・クラスを処理できなければならない。電子メールでは、パケットが、デジタルＴＶを介して送った後妥当な時間（数時間のこともある）の後に到着しさえすればよく、パケットは一定の時間間隔で到着する必要があるのに対し、パケット電話では、パケット間の時間間隔に対する厳しい要求のみならず、パケットが発信元からその宛先までネットワークを横断するために要する総時間に関しても厳しい制約がある。
【発明を実施するための最良の形態】
【００１４】
図面内の参照番号は、３桁またはそれ以上である。一般的に、一番左の桁は図面番号であり、右２桁は、図面内の参照番号である。このため、参照番号２０３で示す要素は、最初に図２の要素２０３として使用されている。下記の表は、この規則の例外を示す。
【００１５】
【表１】
2005510893.tif 000003
以下の詳細な説明においては、最初に、本明細書に開示する技術を実行することができる環境の概略を説明し、次に上記技術を実行するトラヒック・マネージャについて詳細に説明し、最後に、トラヒック・マネージャ集積回路および外部メモリＩＣを使用するトラヒック・マネージャの実施について説明する。
＜ルック・アサイド・データ・ストリーム操作＞
本明細書で開示するデータ・ストリーム操作のための技術は、ルック・アサイド・データ・ストリーム操作を使用する環境で実行される。ルック・アサイド・データ・ストリーム操作の場合には、パケットのペイロードがネットワーク入力から受信され、それがネットワーク出力に出力されるまで記憶される。パケットを受信すると、パケットを表す「記述子」が作成される。本明細書において記述子という用語を使用する場合、記述子は、記憶したペイロードと、環境が、ペイロードが属するパケット・ストリームを操作する方法を制御する追加情報用の識別子とを含む。データ・ストリームの操作は、それが表すパケットではなく記述子により行われる。例えば、入力から出力へのパケットの切替えは、出力によりサービスを受けるキュー上に記述子を置くことにより行われる。記述子がキューの一番前に来ると、出力は、出力のために必要な形の記述子に関連づけられたペイロードを出力するために、操作情報およびペイロード記述子を使用する。マルチキャスト、速度管理、輻輳による廃棄、スケジューリングまたはセグメント分割および再組立てのような他の動作は、ペイロードではなく記述子を操作することにより、全体またはその一部が同じような方法によって実行される。
＜ルック・アサイド・データ・ストリーム操作のための環境：図２＞
図２は、ルック・アサイド・データ・ストリーム操作が実行される環境２０１である。環境２０１は、２つの主な構成要素、すなわち、これらが示すペイロードから独立して記述子を操作するデジタル通信プロセッサ（ＤＣＰ）２０２、ならびにマルチキャスト、速度管理および廃棄、スケジューリング、シェーピング、およびデジタル通信プロセッサ２０２のための再組立ておよびセグメント分割のようなより高いレベルのデータ・ストリーム操作を行うトラヒック管理コプロセッサ（ＴＭＣ）２０３を有する。ある実施形態の場合には、ＤＣＰ２０２およびＴＭＣ２０３は、追加の外部メモリＩＣを有する集積回路として実施される。別の実施形態においては、ＤＣＰおよびＴＭＣはそのようには実施されない。また別の実施形態においては、ＴＭＣ２０３をＤＣＰ２０２に内蔵させることができる。ＤＣＰ２０２のＩＣの一実施例としては、０１８４５  米国マサチューセッツ州アンドーバー、ウォーター・ストリート１２０所在のＣポート・コーポレーション（Ｃ−Ｐｏｒｔ  Ｃｏｒｐｏｒａｔｉｏｎ）社が市販しているＣ−５（登録商標）がある。Ｃ−５のプロトタイプの実施は、１９９９年１１月１８日付けの、「デジタル通信プロセッサ」（Ｄｉｇｉｔａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｐｒｏｃｅｓｓｏｒ）という名称で、Ｃポート・コーポレーション（Ｃ−Ｐｏｒｔ  Ｃｏｒｐｏｒａｔｉｏｎ）社の国際ＰＣＴ特許出願第ＷＯ９９／５９０７８号公報に詳細に記載されている。
【００１６】
ＤＣＰ２０２についてより詳細には、ＤＣＰ２０２は、入力２１９（０…ｍ）において少なくとも１つのネットワークからデータ・ストリームを受信し、出力２２５（０…ｐ）において少なくとも１つのネットワークへデータ・ストリームを送信する。本発明に関係があるＤＣＰ２０２の内部構成要素は下記のとおりである。
【００１７】
・データ・ストリームを処理するチャネル・プロセッサ。チャネル・プロセッサは、
−入力２１９（０…ｍ）において受信したデータ・ストリームを処理する受信プロセッサ２２１、および
−出力２２５（０…ｐ）に送られるデータ・ストリームを処理する送信プロセッサ２２３を備える。
【００１８】
また、チャネル・プロセッサは、ＤＣＰ２０２の内部でペイロードを処理するために使用することもできる。
・入力２１９（０…ｍ）を介して受信したペイロードを、出力２２５（０…ｐ）を通して出力されるまでペイロード・バッファ２２９内に記憶するバッファ管理ユニット２２７。
【００１９】
・記述子のキュー２１３を記憶するキュー管理ユニット２１１。
チャネル・プロセッサは、異なるタイプの転送パケットおよび物理層データ表現を処理するように構成することができる。記述子は、チャネル・プロセッサにより作成され、読み出される。ほとんどの場合、記述子は、バッファ管理ユニット２２７内に記憶されているペイロードを表し、記述子が表すペイロードを含むペイロード・バッファ２２９（ｉ）に対する識別子を含む。記述子がＤＣＰ２０２内にとどまっている限り、その内容は、単に記述子およびそれを読むチャネル・プロセッサを作成するチャネル・プロセッサのニーズにより決定される。ＤＣＰ２０２内にとどまっている記述子は、以下の説明においては、チャネル・プロセッサ記述子と呼ぶ。参照番号２１４はそのような記述子の１つを示す。記述子がＴＭＣ２０３およびチャネル・プロセッサによって処理される場合には、記述子はＴＭＣ２０３が使用するための追加情報を含んでいなければならない。このような追加情報を含んでいる記述子は、以下の説明においてＴＭＣ記述子２１６と呼ぶ。
【００２０】
ＡＴＭパケットを転送パケットとして使用し、光物理層を有するネットワークからＩＰパケットを受信し、イーサネット・パケットを転送パケットとして使用し、電子物理層を有するネットワークへＩＰパケットを出力する例を参照しながら、データ・ストリームを
処理するために、ＤＣＰ２０２の構成要素が相互に作用する方法について説明する。受信ストリーム２１９（ｉ）は、光物理層およびＡＴＭトランスポート層を有するデータ・ストリームを処理し、ＩＰパケットを処理するように構成された受信プロセッサ２２１（ｉ）により受信される。受信プロセッサ２２１（ｉ）がストリーム２１９（ｉ）を受信すると、受信プロセッサは、ストリームからＩＰパケット・ペイロードを抽出し、バッファ管理ユニット２２７内のペイロード・バッファ２２９（ｊ）にＩＰパケット・ペイロードを書き込み、ペイロード・バッファ２２９（ｊ）のための識別子を保持する。識別子は、チャネル・プロセッサ記述子２１４（ｋ）内に置かれる。記述子は、さらに、ＩＰパケットから他のプロトコル・データを含むことができる。受信プロセッサ２２１（ｉ）は、さらに、キュー管理ユニット２１１内のどの記述子のキュー２１３（ｌ）が、ＩＰパケットのための記述子を置くべきかを決定するために、ＩＰパケット・ヘッダ内のアドレス情報を処理し、記述子２１４（ｋ）をキューの末尾に置く。このキュー２１３（ｌ）は、所望のネットワークに出力する送信プロセッサ２２３（ｊ）により読み出される。送信プロセッサ２２３（ｊ）は、イーサネット・トランスポート層および電子物理層によりＩＰパケットを出力するように構成されている。記述子２１４（ｋ）がキュー２１３（ｌ）の先頭に到着すると、送信プロセッサ２２３（ｊ）は、バッファ２２９（ｊ）の位置を発見するために記述子２１４（ｋ）内の情報を使用し、適当なトランスポート層および物理層を使用して、ペイロードをＩＰパケットとして出力する。
＜環境２０１内のトラヒック管理＞
ＤＣＰ２０２の動作の上記説明を読めば理解することができると思うが、ＤＣＰ２０２は、最も簡単なトラヒック管理機能のためだけにそれ自身の十分なリソースを有する。ＤＣＰ２０２は、特定の入力２１９（ｉ）において受信したデータ・ストリームを特定の出力２１９（ｊ）にルーティングすることができ、必要に応じてこのルーティングのためにデータ・ストリームを変換することができる。チャネル・プロセッサ内の再循環機能により、さらに、暗号化および解読のようなデータ・ストリームの変換を行うこともできる。しかし、ＤＣＰ２０２は、ＤＣＰ２０２自身の状態、またはＤＣＰ２０２により接続しているネットワーク内の装置の要件の知識を必要とする、「より高度な」トラヒック管理機能を実行するだけの十分なリソースを有さない。このような機能の例としては、パケットの廃棄、スケジューリング、シェーピング、およびパケット再組立ておよびセグメント分割等がある。
【００２１】
環境２０１においては、このようなより高度なトラヒック管理機能が、トラヒック管理コプロセッサ２０３により実行される。好ましい一実施形態では、このトラヒック管理コプロセッサ２０３は、外部メモリを有し、ＤＣＰ２０２のＩＣ実施形態と協働して作動するように設計されているＩＣである。ＤＣＰ２０２をＴＭＣ２０３と併用する場合には、キュー管理ユニットは、ＤＣＰ２０２のところで説明したように使用されるローカル・キュー２４５ばかりでなく、ＴＭＣ２０３に送られるＴＭＣ記述子２１６に対するキュー２４３、およびＴＭＣ２０３から受信した記述子に対する少なくとも１つのキュー２４７を含む。ＤＣＰ２０２が処理しているデータ・ストリームが、少なくとも１つのより高度なトラヒック管理機能を必要とする場合には、データ・ストリームを受信中の受信プロセッサ２２１（ｉ）は、ＱＭＵ２１１に、キュー２４３の末尾に追加するＴＭＣ記述子２１６を提供する。コプロセッサ２０３は、このＴＭＣ記述子２１６（ｉ）を、そのデータ・ストリームおよび、多くの場合、そのトラヒックを記述子２１６（ｉ）が関連するデータ・ストリームと共に管理しなければならない他のデータ・ストリームに対するトラヒック・キュー２０４（ｍ）内に置く。トラヒック・キューのＴＭＣ記述子は、どのＴＭＣ２０３が記述子と関連し、どう関連するのかを決定するために置かれる。このため、広義では、トラヒック・キューは、一組の記述子をＴＭＣ２０３内の一組のトラヒック管理機能と関連づける。以下にさらに詳細に説明するように、トラヒック・キューも、一組の記述子をＤＣＰ２０２内の一組のパケット処理機能と関連づける。
【００２２】
トラヒック・キューには２つの一般的なクラスがある。すなわち、ＤＣＰ２０２により廃棄されないパケットに対する記述子に対する非廃棄トラヒック・キュー２４９と、ＴＭＣ２０３が廃棄すべきであると決定したパケットに対する記述子に対する廃棄トラヒック・キュー２５１である。ＴＭＣ２０３は、参照番号２０７で示すように、特定のトラヒック・キュー２０４（ｍ）の先頭からＴＭＣ記述子２１６を読み出し、ＴＭＣ記述子２１６を処理するためにＱＭＵ２１１が必要とする情報を追加し、ＴＭＣ記述子をＱＭＵ記述子に変換し、ＱＭＵ記述子をキュー管理ユニット２１１に提供する。キュー管理ユニット２１１は、次に、ＱＭＵ記述子内に含まれているｃｐ記述子を、記述子が表すパケットに対してＤＣＰ２０２内で行わなければならないさらなる処理のために記述子キュー２１３（ｎ）の末尾に置く。以下にさらに詳細に説明するように、ＴＭＣ２０３への記述子の入力、およびＴＭＣ２０３からの記述子の出力の流れの制御が行われる。後者の場合、流れ制御は、ＴＭＣ２０３からのＱＭＵ２１１への流れを制御するばかりでなく、キュー２４７内の個々のキュー２１３への記述子の流れも制御する。
【００２３】
例えば、トラヒック・キューが、廃棄トラヒック・キューである場合には、キュー管理ユニット２１１は、記述子を、バッファ管理ユニット２２７からのキューにより表されるパケットを廃棄するために必要な処理を行うチャネル・プロセッサによりサービスの提供を受けるキュー２１３内に置く。一方、トラヒック・キューが、非廃棄トラヒック・キューである場合には、キュー管理ユニット２１１は、記述子を、送信ストリーム２２５（ｉ）にストリームを出力している送信プロセッサ２２３（ｊ）に対する記述子キュー２１３内に置くことができる。ＤＣＰ２０２内の送信プロセッサまたは受信プロセッサのいずれかは、ＱＭＵ２１１が管理するキューから記述子を読み出し、このキューに記述子を書き込むことができるので、コプロセッサ２０３とＤＣＰ２０２間の任意の複雑な相互作用ももちろん可能である。このような複雑な相互作用の例については以下に説明する。
【００２４】
トラヒック管理コプロセッサ２０３は、トラヒック・キュー２０４に多数の異なるトラヒック管理技術を適用することができる。しかし、この技術の適用方法は、各トラヒック・キュー２０４により高度に構成可能なものである。トラヒック・キュー２０４（ｉ）にどのトラヒック管理技術を適用するのかを決定する情報は、トラヒック管理情報２３５内に含まれている。論理的な用語でいうと、トラヒック管理情報２３５は、下記の３つの種類に分類される。
【００２５】
・使用できる技術を定義するトラヒック管理定義２３７。好ましい実施形態においては、これらの定義はＴＭＣ２０３に内蔵される。別の実施形態においては、ユーザは、定義２３７を修正することができるし、または新しい定義を追加することができる。
【００２６】
・２３７で定義した技術のトラヒック・キュー２０４のセットへの適用方法を定義するトラヒック管理構成データ２３９、および
・各トラヒック・キュー２０４およびトラヒック管理に関連するＴＭＣ２０３およびＤＣＰ２０２の他の構成要素の現在の状態を含む現在のトラヒック管理状態２４１。
【００２７】
トラヒック管理は、トラヒック・キュー２０４を選択するために、構成データ２３９により構成したトラヒック管理定義２３５を現在のトラヒック管理状態２４１に適用することによりＴＭＣ２０３で行われ、選択したトラヒック・キューの先頭のＴＭＣ記述子２１６に関連づけられたペイロードは、必要に応じて、トラヒック管理定義、構成および現在のトラヒック管理状態により処理される。
＜ＴＭＣ２０３の論理的概観：図３＞
図３は、トラヒック管理コプロセッサ２０３の構成要素の論理的概観である。好ましい実施形態においては、ＴＭＣ２０３は、２つの主なサブ区画、すなわち、少なくとも１つの処理素子内で実施することができる処理構成要素３０６と、ＴＭＣメモリ３０７とを含
む。好ましい実施形態においては、すべての処理構成要素３０６は、１つのＩＣ内で実施される。処理構成要素３０６は、３つの機能グループ、すなわち、エンキュー・プロセッサ３０１、トラヒック・キュープロセッサ３０５およびデキュー・スケジューラ３０３に分類される。エンキュー・プロセッサ３０１は、ＱＭＵ２１１からＴＭＣ記述子２１６を受信し、どのトラヒック・キューに記述子を入れるのかを決定する。このタスクの一部は、それが表す記述子およびパケットを廃棄すべきかどうか決定する。記述子を廃棄すべき場合には、エンキュー・プロセッサ３０１は、それを廃棄トラヒック・キュー内に入れるように指定する。トラヒック・キュープロセッサ３０５は、エンキュー・プロセッサ３０１から記述子２１６を受信し、この記述子２１６を、エンキュー・プロセッサ３０１が指定したトラヒック・キュー２０４内にリンクする。デキュー・スケジューラ３０３は、ＱＭＵ２１１に記述子２１６を提供する次のトラヒック・キュー２０４を決定し、そのトラヒック・キューの先頭に位置する記述子をＱＭＵ２１１に提供する。好ましい実施形態においては、これら３つのプロセッサは、すべて並列に動作し、これによって記述子のパイプライン処理を行うことができる。
【００２８】
好ましい実施形態においては、ＴＭＣメモリ３０７は、プロセッサ３０６が実施されるＩＣ内部のメモリと、ＩＣ外部のメモリの両方とを有する。別の実施形態においては、ＩＣと外部メモリとの間のメモリの分配は変化する。機能的な用語で言えば、メモリは、ｔｍ定義２３７用の記憶領域と、ｔｍ構成データ２３９用の記憶領域と、現在のｔｍ状態２４１用の記憶領域とに分割される。メモリ３０７のこれらの領域の内容の機能は、概論ですでに説明した。
【００２９】
ＴＭＣメモリ３０７内の内容は３つの大きなクラス、すなわち、スケジューリングの際に使用されるスケジューラ情報３３３と、記述子２１６をトラヒック・キュー２０４にエンキューするために使用されるＴＱエンキュー情報３３５と、マルチキャストの際に使用されるマルチキャスト情報３３７とに分割される。より詳細には、好ましい実施形態においては、ｔｍ定義２３７の３つの大きなクラス、すなわち、ＤＣＰ２０２に提供する次の記述子２１６を選択するための技術を指定するスケジューリング・アルゴリズム３０９と、ＤＣＰ２０２から受信したＴＭＣ記述子２１６を廃棄すべきかどうかを決定するための技術を指定するトラヒック・キューエンキュー・アルゴリズム３１１と、複数のトラヒック・キューに１つのＴＭＣ記述子２１６をコピーする方法を記述するマルチキャスト・アルゴリズム３１５とがある。
【００３０】
定義の各クラスに対応する構成データ２３９が存在する。スケジューラ構成３１７は、個々のスケジューラおよびスケジューラ階層内にスケジューラを配置する方法を定義する。トラヒック・キューエンキュー構成３１９は、廃棄を行う条件を定義する。詳細テーブル３２３は、どのトラヒック・キューが、マルチキャストされるパケットに対する記述子を置くのかを指定する。さらに、各トラヒック・キュー２０４に対する構成データ３２７が存在する。ＴＭＣ２０３のユーザは、特定のトラヒック・キューにどのＴＭ定義を適用するのか、これらの定義の適用方法を決定するために構成データ２３９を設定することができる。一例を挙げると、ＴＱ処理構成３１９内の廃棄構成は、特定のトラヒック・キュー２０４の末尾に置く代わりに、記述子２１６を廃棄する条件を決定するパラメータを指定する。好ましい実施形態においては、ＴＭＣ２０３が初期化される時だけ、構成データ２３９を設定することができる。別の実施形態においては、構成データ２３９を動的に設定することができる。
【００３１】
現在のｔｍ状態２４１は、スケジューラ階層内で各トラヒック・キュー２１３およびスケジューラの現在の状態を指定するデータを含む。現在のＴＭ状態２４１は、現在のトラヒック・キューの状態３２９、および現在のスケジューラ状態３１８を含む。現在のトラヒック・キューの状態３２９は、各キュー内に現在含まれている記述子２１６、キュー内
の記述子が表すパケットのサイズ、およびパケットを記憶しているペイロード・バッファ２２９の現在の状態を含む。パケットのサイズおよびペイロード・バッファ２２９の現在の状態は、記述子２１６をトラヒック・キュー２０４上に置く代わりに、廃棄すべきかどうか、およびどのトラヒック・キュー２０４を、次にデキュー・スケジューラ３０３により選択するのかを決定するために使用される。現在のスケジューラの状態３１８は、デキュー・スケジューラ３０３によりＤＣＰ２０２に出力するためにどのＴＭＣ記述子２１６を選択するのかを決定する。
＜ＴＭＣ２０３の一般的動作：図２５＞
図２５は、ＴＭＣ２０３およびＱＭＵ２１１の構成要素が、送信プロセッサ２２３が使用している記述子キュー２１３内のｃｐ記述子２１４の到着のスケジュールを作成し、これによって、送信プロセッサ２２３により記述子が表すペイロードの出力のスケジュールを作成する方法を示すブロック図である。
【００３２】
すでに説明したように、ＴＭＣ２０３によりスケジュールが作成されるＴＭＣ記述子２１６を作成しているチャネル・プロセッサは、ｃｐ記述子２１４に追加情報を追加しなければならない。チャネル・プロセッサは、効果的にそれにＴＭＣ情報２５１３を追加することにより、ＴＭＣ記述子２１４の詳細図に示すように、ｃｐ記述子２１４をカプセルに入れる。同じような方法で、ＴＭＣ２０３がＱＭＵ２１１にｃｐ記述子２１４を返送すると、ＴＭＣ２０３は、ＢＭＵ記述子２５０８の詳細図に再び示すように、それにＢＭＵ情報２５１５を追加することによりそれをカプセル内に収容する。最低でも、ＴＭＣ情報２５１３は下記のものを含む。
【００３３】
・ＴＭＣ２０３内のトラヒック・キュー２０４に対する識別子、および
・記述子が可変長のパケットを表している場合には、記述子２１３が表すパケットのバイトによる長さ。
【００３４】
ＴＭＣ２０３が実行するある動作に対して追加情報が必要になる場合がある。ＱＭＵ情報２５１５は、最低、どの記述子キュー２４７内に、カプセルに入れたｃｐ記述子２１４を入れるべきかを決定するために、ＱＭＵ２１１が使用する仮想出力ポート識別子を含む。当然ながら、どの記述子キュー２４７に、カプセルに入れたｃｐ記述子２１４を入れるのかにより、記述子２１４が表すパケットがＤＣＰ２０２内でさらに処理される方法が決まる。
【００３５】
図２５は、さらに、ＴＭＣ２０３のアーキテクチャ、および図３より詳細なあるレベルでのＱＭＵ２１１およびＴＭＣ２０３間のインタフェースを示す。図２５に示すように、ＱＭＵ２１１は、ＴＭＣ入力キューの先頭のＴＭＣ記述子を、記述子２１６を含むエンキュー・データ・メッセージ６０１を通してＴＭＣ２０３に送る。ＴＭＣ２０３がエンキュー・データ・メッセージを受信すると、ＴＭＣ２０３はメッセージからの記述子２１６を入力キュー２５０１の末尾に置く。
【００３６】
エンキュー・プロセッサ３０１は、入力キュー２５０１の先頭からＴＭＣ記述子２１６を読み取る。記述子２１６が、それが表すパケットをマルチキャストすべきであることを示している場合には、エンキュー・プロセッサ３０１は、どのトラヒック・キュー２０４が、記述子２１６のコピーを受信すべきかを決定するためにマルチキャスト情報３２７を使用する。そうでない場合には、ＴＭＣ記述子２１６は、記述子２１６を受信するトラヒック・キューを直接指定する。エンキュー・プロセッサ３０１が、どのトラヒック・キュー２０４に記述子２１６を置くべきかを知った場合には、エンキュー・プロセッサ３０１は、トラヒック・キューの状態が、記述子２１６および廃棄すべき記述子が表すパケットを必要としているかどうかを判断するために、ＴＱエンキュー情報３３５を使用する。この場合、エンキュー・プロセッサ３０１は、ＤＴＱＳ２５１内の廃棄トラヒック・キュー
の代わりに、ＴＭＣ記述子２１６内に元来指定されているトラヒック・キューを使用する。エンキュー・プロセッサ３０１が、記述子２１６を受信するトラヒック・キュー２０４を最終的に決定した場合には、エンキュー・プロセッサ３０１は、エンキュー・プロセッサ３０１が指定したトラヒック・キューの末尾にエンキューするために、トラヒック・キュープロセッサ３０５に記述子２１６を提供する。
【００３７】
スケジュールを作成する目的で、ＴＭＣ２０３内のトラヒック・キュー２０４は、図２５に参照番号５２３で示すスケジューラ・キューに編成される。スケジューラ・キュー５２３は、トラヒック・キュー２０４のキューを含む。デキュー・スケジューラ３０３は、スケジューリングのために一組の空でないスケジューラ・キュー５２３の内の１つを選択するために、スケジューラ情報３３３を使用する。デキュー・スケジューラ３０３が、スケジューリングのためにスケジューラ・キュー５２３を選択すると、現在選択したスケジューラ・キュー５２３の先頭に位置するトラヒック・キュー２０４（ｉ）にサービスが提供される。すなわち、現在トラヒック・キュー２０４（ｉ）の先頭に位置する記述子２１６が、キュー２５０７を出力するためにＱＭＵ記述子２５０８として出力される。ここから、ＴＭＣ２０３は、ＱＭＵ記述子２５０８をデキュー・データ・メッセージ７０１としてＱＭＵ２１１に出力する。ＱＭＵ２１１は、記述子２５０８をＴＭＣ出力キュー２５０９に入れ、次に、適当な記述子キュー２１３内のＱＭＵ記述子２５０８内に含まれるｃｐ記述子２１４をキュー２４７内に入れる。
【００３８】
スケジューリングについてさらに詳細に説明すると、トラヒック・キュープロセッサ３０５は、スケジューラ・キュー５２３内にトラヒック・キュー２０４を入れることを担い、これらのトラヒック・キューをスケジューラ・キュー５２３から除去する。トラヒック・キュー２０４は、トラヒック・キューにサービスを提供することができる場合だけ、スケジューラ・キュー５２３の先頭に位置することができる。本明細書においては、サービスを受けることができるトラヒック・キューは、選択可能なトラヒック・キューと呼ばれる。空のトラヒック・キューは、もちろん選択することはできない。トラヒック・キュー２０４の選択を行うことができない他の状況について以下に詳細に説明する。トラヒック・キュー２０４が現在選択できない場合には、トラヒック・キュープロセッサ３０５は、それをスケジューラ・キューに入れないで、その代わりに、それを一組の選択不能なトラヒック・キュー２５１１内にそのまま置く。トラヒック・キュー２０４は、また、それがスケジューラ・キュー５２３内に置かれた時間からサービスの提供を受ける時間まで、選択不能な状態になる場合がある。この場合、トラヒック・キュープロセッサ３０５は、それがサービスを受ける前に、選択不能なトラヒック・キュー２０４をスケジューラ・キュー５２３の先頭から除去し、それを選択不能なトラヒック・キュー２５１１に戻す。その先頭に選択可能なトラヒック・キューを有するスケジューラ・キュー５２３は、能動スケジューラ・キューと呼ばれる。デキュー・スケジューラ３０３は、能動スケジューラ・キューだけのスケジュールを作成する。
【００３９】
すでに説明したように、ＱＭＵ記述子２５０８は、記述子を記述子キュー２４７内のキュー２１３に関連づける仮想出力ポート識別子を含む。デキュー・スケジューラ３０３のタスクの１つは、各ＱＭＵ記述子２５０８を適当な仮想出力ポートに関連づけることである。その方法については以下に詳細に説明する。仮想出力ポート機構も、キュー２４７内の記述子キュー２１３のレベルにおけるデキュー・スケジューラ３０３の動作を流れ制御するために使用される。各仮想出力ポートは、仮想出力ポートに対応する記述子キュー２４７内の記述子キュー２１３が、どれだけ多くのｃｐ記述子２１４が、現在キューに入れるために受け入れるかを示すクレジット値と関連づけられる。クレジット値がゼロである場合には、デキュー・スケジューラ３０３は、仮想出力ポートに関連づけられた記述子キューに対するＱＭＵ記述子２５０８を出力するスケジューラ・キューのスケジュールは作成しない。デキュー・スケジューラ３０３が、所与の出力ポート用の記述子を出力するス
ケジューラ・キューのスケジュールを作成する度に、クレジット値は低減する。キュー２４７内の記述子キュー２１３からｃｐ記述子２１４が除去される度に、ＱＭＵ２１１は、デキュー肯定応答メッセージ１９２５を、記述子キューに対応する仮想出力ポートを指定するＴＭＣ２０３に送り、デキュー・スケジューラ３０３は、仮想出力ポートのクレジット値を増大させることによりメッセージ１９２５に応答する。能動状態であり、仮想出力ポートによりゼロのクレジット値でスケジュール中から禁止されていないスケジューラ・キュー５２３は、スケジュール可能なスケジューラ・キューと呼ばれる。このため、デキュー・スケジューラ３０３は、能動状態にありスケジュールを作成することが可能なスケジューラ・キュー５２３（ｊ）の先頭に位置する選択可能なトラヒック・キュー２０４（ｉ）の先頭に位置するＱＭＵ２１１へ出力される記述子キューを選択する。ここでまた、スケジューラ・キュー５２３（ｊ）の先頭に位置するトラヒック・キュー２０４（ｉ）の先頭から記述子が除去されたので、トラヒック・キュー２０４（ｉ）が選択不能にならない限り、トラヒック・キュー２０４（ｉ）は、スケジューラ・キュー５２３（ｊ）の終わりに移動することを指摘しておかなければならない。このため、能動スケジューラ・キューは、その選択可能なトラヒック・キューをラウンドロビン順にサーブする。さらに、トラヒック・キュープロセッサ３０５は、記述子２１６をトラヒック・キューに追加することができる。一方、トラヒック・キューはスケジューラ・キュー５２３内に位置する。
【００４０】
すでに説明したように、廃棄した記述子は、非廃棄トラヒック・キューのようなスケジュールが作成される廃棄トラヒック・キュー内に入れられる。廃棄トラヒック・キューからのＱＭＵ記述子２５０８は、記述子２５０８が表すパケットは廃棄すべきであることを示し、また廃棄の理由も示す。ＱＭＵ２１７は、再使用のためにバッファ管理ユニット２２７にバッファ識別子を返送するＤＣＰ２０２内にチャネル・プロセッサに対するキュー内の記述子２５０８を置くことにより、廃棄トラヒック・キューからの記述子を含む廃棄デキュー・データ・メッセージに応答し、これによって、バッファ識別子が識別したバッファの内容を効果的に廃棄する。
【００４１】
図２５は、また、好ましい実施形態のＴＭＣ２０３およびＱＭＵ２１１間のハードウェア・インタフェースの概略も示す。入力キュー２５０１内に余裕がある場合には、ＴＭＣ２０３は、入力キュー作動可能信号１９１５を出力（ａｓｓｅｒｔ）し、ＱＭＵ２１１は、ＴＭＣ  ＩＱ２４３の先頭に位置するエンキュー・メッセージをＴＭＣ２０３に出力する。ＴＭＣ出力キュー２５０９内に余裕がある場合には、ＱＭＵ２１１はＤＱＲＤＹ信号１９１９を出力（ａｓｓｅｒｔ）し、ＴＭＣ２０３は、出力キュー２５０７の先頭に位置するＱＭＵ記述子を出力する。ＤＱＡＲＤＹ１９２３およびＤＱＡＣＫ１９２１は、キュー２４７内の記述子キュー２１３からの記述子をデキューする肯定応答をするために使用される。各ＤＱＡＣＫメッセージは、そのｃｐ記述子２１４が、ＱＭＵ２１１がそれをＴＭＣ２０３から受信した後で、それが置かれた記述子キュー２１３から、チャネル・プロセッサによりデキューされたばかりのデキュー・メッセージからの仮想出力ポート指定子を含む。すでに説明したように、ＴＭＣ２０３は、その宛先記述子キュー２４７へのＱＭＵ記述子２５０８の流れを制御するために、返送された仮想出力ポート指定子を使用する。
＜トラヒック・キューおよび関連データ構造：図４＞
トラヒック管理コプロセッサ２０３のすべての活動は、トラヒック・キュー２０４を含む。トラヒック・キュー内にＴＭＣ記述子が置かれると、記述子に適用される廃棄ポリシー、記述子のスケジュールの作成方法、および記述子が出力されるＱＭＵキューが決定する。図４は、トラヒック・キュー２０４およびその関連するデータ構造を示す。各トラヒック・キュー２０４は、トラヒック・キュー識別子４２３を有し、トラヒック・キュー・パラメータ・ブロック４０３により定義される。トラヒック・キューに属するＴＭＣ記述子２１６は、ＴＭＣ記述子キュー４１９内で一緒にリンクされる。トラヒック・キュー・パラメータ・ブロック４０３は、キュー４１９内のヘッド記述子２１６を指しているｔｑ
ヘッド・ポインタ４０５、およびキュー４１９内の末尾記述子２１６を指しているｔｑ末尾ポインタ４０７を有する。パラメータ・ブロック４０３内の残りの情報は、パラメータ・ブロック４０３が示すトラヒック・キュー２０４の現在の状態についての情報、記述子２１６をトラヒック・キューに追加すべきか廃棄すべきかを決定するために使用する情報４１１、マルチキャストで使用される情報４１５、およびトラヒック・キューのスケジューリングの際に使用する情報４１３を含む。
【００４２】
関連データ構造は、トラヒック・キューを含む動作の際に使用する追加情報を含む。パケットをマルチキャストする場合には、その記述子は、トラヒック・キューの１つのグループの各トラヒック・キュー内に置かれる。このグループは、少なくとも１つのマルチキャスト詳細テーブル４２１のチェーン４２２により定義される。グループ内の各トラヒック・キューに対してテーブル４２１内にはｔｑｉｄ４２３が存在する。所与のマルチキャスト・テーブル４２１は、そのｍｅｔｉｄ４２０により識別される。パケットがマルチキャストされるものである場合には、そのＴＭＣ記述子２１６は、トラヒック・キューのグループを指定するＭＥＴチェーン４２２内のヘッド・マルチキャスト詳細テーブルのｍｅｔｉｄを含む。
【００４３】
記述子を廃棄するかどうかの決定は、いくつかのアルゴリズム３１１の内の１つにより行われる。これらの内のあるものは、バッファ管理ユニット２２７内のバッファ２２９の状態を考慮に入れる。この状態情報は、トラヒック管理コプロセッサ２０３内に、バッファのプールおよびバッファのプールのセットの形で維持される。バッファのプールおよびバッファのプールのセットは、ＤＣＰ２０２内のいくつかのバッファの状態のＴＭＣ２０３内のモデルとして機能する。ＴＭＣ２０３が状態を維持する各バッファ・プールは、ＤＣＰ２０２内のバッファ空間の量を指定するバッファ・プール仕様４３３を有する。トラヒック・キュー・パラメータ・ブロック４０３は、このような１つのバッファ・プール仕様を指定する。各バッファ・プール仕様４３３（ｉ）は、バッファ・プール仕様４３３（ｉ）が表すバッファ・プールが属するバッファ・プールのセットに対する親バッファ・プール仕様を指定する。各バッファ・プールは、それに対して予約したバッファ空間の最低量を有する。親バッファ・プール仕様は、親バッファ・プールに属するバッファ・プール間で共有するために使用することができるバッファ・プールに対する全最低バッファ空間上のバッファ空間の量を示す。
【００４４】
廃棄構成ブロック４３１は、所与のトラヒック・キュー２０４が使用する廃棄方法に対する構成情報を含み、廃棄コード４３２はその方法に対するコードである。廃棄構成ブロック４３１は、ＴＭＣ２０３のメモリ内のアレイ４４１に編成され、所与のトラヒック・キュー２０４（ｉ）は、８つの廃棄構成ブロック４３１の中から選択を行うことができる。バッファ・プール仕様４３７の場合のように、多くのトラヒック・キュー・パラメータ・ブロック４０３は、所与の廃棄構成ブロック４３１を指定することができる。記述子を所与のトラヒック・キュー２０４に追加する場合には、バッファ・プール仕様４３３および４３５内の情報が、廃棄すべき記述子かどうかを判断するために、廃棄コード４３２により、廃棄構成ブロック４３１内の情報と共に使用される。記述子を廃棄する場合には、記述子は廃棄トラヒック・キュー２５１内に入れられる。
【００４５】
現在所与のトラヒック・キュー２０４（ｉ）の先頭に位置するＴＭＣ記述子２１６をＤＣＰ２０２にいつ出力すべきかについての決定は、スケジューラの階層を使用して行われる。機能的には、スケジューラの階層は、その入力として、一組の能動およびスケジュール可能なスケジューラ・キュー５２３をとり、そのセットうちの１つをその先頭記述子２１６がＤＣＰ２０３に出力されるトラヒック・キュー２０４のソースとして選択する。このため、スケジューラ階層がスケジューラ・キューを選択する方法は、ＴＭＣ２０３、最終的にはＴＭＣ−ＤＣＰシステム２０１のどれだけの幅の帯域幅を、スケジューラ・キュ
ーのトラヒック・キュー内の記述子が表すパケットに対して使用できるかを決定する。
【００４６】
参照番号４３０により示すように、好ましい実施形態においては、スケジューラは、スケジューラ構成指定子４２５、およびスケジューラ構成指定子内の情報を使用して実行されるスケジューラ・コード４２９により定義される。トラヒック・キュー・パラメータ・ブロック４０３内のスケジューリング情報４１３は、所与のトラヒック・キュー２０４を、１つのスケジューラ４３０に属する１つのスケジュール構成指定子４２５（ｉ）と関連づける。このスケジューラは、所与のスケジューラ４３０に対するスケジューラ構成指定子４２５を有するすべてのトラヒック・キューが属するトラヒック・クラスを定義する。このため、スケジューラ４３０は、トラヒック・クラス・スケジューラ５０３と呼ばれる。好ましい実施形態においては、トラヒック・クラス・スケジューラは、またセグメント分割および再組立てを処理する。トラヒック・クラス・スケジューラは、スケジューラ階層内におけるリーフ・スケジューラであり、図４の参照番号４２７および４３４で示すように、その階層内には、いつでも少なくとも１つの他の内部スケジューラが存在していなければならない。
＜スケジューラ階層：図５＞
図５は、スケジューラ階層５０１の概要である。スケジューラ階層５０１の入力は、一組の能動スケジューラ・キュー５２３である。スケジューラ階層５０１の出力は、一組の能動スケジューラ・キュー５２３の内の１つである。ＴＭＣ２０３は、スケジューラ階層５０１が出力するスケジューラ・キューの先頭に位置するトラヒック・キュー２０４の先頭に位置するＴＭＣ記述子２１６内のｃｐ記述子２１４を含むＱＭＵ記述子２５０８を出力する。スケジューラ階層５０１は、そのノードがトラヒック・クラス・スケジューラ５０３または内部スケジューラ５０９であるツリーを形成する。階層内の各スケジューラは、一組の能動スケジューラ・キューをその入力として選択し、入力セットうちの１つをその出力として選択する。
【００４７】
階層５０１はツリーである。ツリーのリーフ・ノードは、常にトラヒック・クラス・スケジューラ５０３である。内部ノードは常に内部スケジューラ５０９である。階層のレベル０にある１つの内部スケジューラ５１５は、ツリーのルートを形成する。スケジューラ階層５０１が、所与の能動スケジューラ・キュー５２３（ｉ）のスケジュールを作成する場合には、キュー５２３（ｉ）のスケジュールを作成するスケジューラは、階層を通してトラヒック・クラス・スケジューラ５０３からツリーのルートへの経路を形成する。図５の５２９においては、太い矢印がこのような経路の１つを示す。好ましい実施形態の階層の最大深さは４つのスケジューラである。
【００４８】
図５を見れば分かるように、好ましい実施形態においては、レベル０のルート・スケジューラ５０９（ａ）は、入力として最大３２のスケジューラからの出力スケジューラ・キューを受信するように構成することができ、これにより、最大３２までのスケジューラ・キューの入力セットを有することができる。他のレベルの各内部スケジューラは、それぞれ、最大３２のスケジューラ・キューからの入力スケジューラ・キューを入力として有し、このため、最大３２までのスケジューラ・キューの入力セットを有することができるように構成することができる。各トラヒック・クラス・スケジューラ５０３は、最大３２のスケジューラ・キューを入力として有することができ、これにより、最大３２のスケジューラ・キューの一組の入力を有することができる。１つのトラヒック・クラス・スケジューラ５０３に対するスケジューラ・キューの実際の数は、トラヒック・クラス・スケジューラのタイプにより異なる。
【００４９】
内部スケジューラ５０９とトラヒック・クラス・スケジューラ５０３との重要な違いは、所与のトラヒック・クラス・スケジューラ５０３（ｊ）において、スケジューラ・キューの入力セットが、トラヒック・クラス・スケジューラ５０３（ｊ）を指定しているトラ
ヒック・キューを含む能動スケジューラ・キューであることである。所与の内部スケジューラ５０９（ｋ）においては、スケジューラ・キューの入力セットは、内部スケジューラ５０９（ｋ）に入力を提供するより低いレベルのスケジューラによりスケジュールされたスケジューラ・キューである。内部スケジューラ・キュー５０９（ｋ）への入力として使用することができるすべてのスケジューラ・キューは能動状態にあるが、内部スケジューラ・キュー５０９（ｋ）によりスケジュールを作成することはできない。それが、仮想出力ポート５２１がスケジューラ・キュー５０９（ｋ）への入力上に位置している場合であり、仮想出力ポートからＱＭＵ２１１に記述子をさらに出力することはできない。
【００５０】
スケジューラ階層５０１が動作している場合には、各スケジューラは、能動およびスケジュール可能な入力スケジューラ・キューのその現在のセットうちの１つをその出力として選択する。このため、トラヒック・クラス・スケジューラ５０３（ｃ）は、スケジューラ５２３（ｄ）がするように、その能動スケジューラ・キュー５２３の内の１つをその出力として選択し、これら２つのスケジューラ・キューは、内部スケジューラ５０９（ｃ）へ出力し、仮想出力ポートによりスケジュール不能とならないスケジューラ５０３が提供する任意の他のものと共に、内部スケジューラ５０９（ｃ）への入力であるスケジューラ・キュー５２３である。内部スケジューラ５０９（ｃ）は、内部スケジューラ５０９（ｂ）への出力に対するそれへの入力の中から１つのスケジューラ・キュー５２３を選択し、内部スケジューラ５０９（ｂ）は、ルート内部スケジューラ５０９（ａ）への出力に対して、それへの入力から１つのスケジューラ・キュー５２３を選択する。ルート内部スケジューラ５０９（ａ）は、その入力から１つのスケジューラ・キュー５２３を選択し、選択したスケジューラ・キューの先頭に位置するトラヒック・キュー２０４の先頭のＴＭＣ記述子２１６内のｃｐ記述子２１４が、ＱＭＵ記述子２５０８内の出力になる。ＱＭＵ記述子２５０８は、次に、ＤＣＰ２０２のキュー管理ユニット２１１へ送られるデキュー・データ・メッセージ７０１になる。記述子を取り出したトラヒック・キューが選択できなくならない限り、トラヒック・キュー５０４は、そのスケジューラ・キューの末尾に移動する。トラヒック・キューが選択できない場合には、そのトラヒック・キューは、スケジューラ・キューから除去され、それが選択することができるようになるまで、スケジューラ・キュー内には置かれない。図５０１の参照番号５３５が示すように、選択できないトラヒック・キュー２０４は、そのトラヒック・クラス・スケジューラ５０３に関連したままの状態で残る。再び選択できるようになった場合、トラヒック・キューは、トラヒック・キューのトラヒック・クラス・スケジューラへの入力としての働きをするスケジューラ・キュー５２３の内の１つの末尾に置かれる。
【００５１】
スケジューラ階層５０１内の流れの制御の２つのレベルは、ＱＭＵ２１７がＴＭＣ記述子２１６を処理することができるようになる前に、ＴＭＣ記述子２１６がＱＭＵ２１７に出力されるのを防止する。一方のレベルは、ＱＭＵ２１７が、ＴＭＣコプロセッサ２０３からの任意の他の記述子を全く処理できないようにする。このレベルは、ＴＭＣ２０３とＤＣＰ２０２との間のハードウェア・インタフェースにおいて動作する。ＴＭＣコプロセッサ２０３は、ＤＣＰ２０２が、このような記述子を受信する準備ができていると示した場合だけ、ＤＣＰ２０２に記述子を送る。流れ制御のもう一方のレベルは、特定の記述子キュー２１３内に、ＴＭＣ２０３からの追加の記述子に対する十分な余裕がない状況を処理する。流れ制御のこのレベルは、階層５０１内の仮想出力ポート５２１により処理される。
【００５２】
階層５０１内のリーフ・スケジューラ５０３とルート・スケジューラ５０９間の各経路は、仮想出力ポート５２１を有していなければならず、どの経路も２つ以上の仮想出力ポート５２１を有することはできない。各仮想出力ポートは、それを一意に識別する識別子を有する。仮想出力ポート５２１は、２つの機能を有する。
【００５３】
・各仮想出力ポートは、スケジューラ階層５０１の出力の一部を、ＱＭＵ２１１の記述子キュー２４７内の記述子キュー２１３に関連づける。
・各仮想出力ポートは、また、その対応する記述子キュー２１３が、どれだけの数の記述子を現在とることができかを示する。
【００５４】
第１の機能は、仮想出力ポートに対する識別子を、ＴＭＣ２０３からＱＭＵ２１１へ出力される各ＱＭＵ記述子２５０８内に挿入することにより実行される。識別子は、ＱＭＵ記述子２５０８内のｃｐ記述子２１４が属しているトラヒック・キュー２０４を含むスケジューラ・キュー５２３のスケジューラ階層５０１を通る経路５２９上の仮想出力ポート５２１の識別子である。
【００５５】
第２の機能は、下記のように実行される。仮想出力ポート５２１に対応する記述子キュー２１３が、仮想出力ポートが出力を制御するスケジューラにより選択されたスケジューラ・キュー５２３の先頭に位置するトラヒック・キュー２０４から出力される記述子に対する空きがない場合には、仮想出力ポート５２１は、階層の次のレベルのスケジューラにより、スケジューラ・キューのスケジュールの作成が行われないようにする。対応する記述子キュー２０４に再び空きができた場合には、仮想出力ポートに次のスケジューリング・レベルに対して出力できるようにする。能動スケジューラ・キューのソースであるトラヒック・クラス・スケジューラ５０３と、現在スケジュールを作成しているスケジューラ・キュー５２３（ｉ）であるスケジューラの間の経路５２９上の仮想出力ポート５２１（ｊ）が、仮想出力ポート５２１（ｊ）に対応する記述子キュー２１３が現在追加の記述子に対する空きがないことを示した場合には、能動スケジューラ・キュー５２３（ｉ）のスケジュールを作成することはできない。
【００５６】
トラヒック・キュー２０４のところですでに説明したように、トラヒック・キューには２つの種類、すなわち、廃棄トラヒック・キュー２５１と非廃棄トラヒック・キュー２４９がある。通常、２つの種類は、ＴＭＣ２０３からの記述子を受け入れている記述子キュー２１３により表されるパケットの送信を禁止し、このため、スケジューラ階層５０１を通る経路の仮想出力ポート５２１を閉鎖するイベントが、決して廃棄トラヒック・キューからの記述子を阻止しないように、階層５０１を通る別々の経路上でスケジュールされる。この理由は、廃棄トラヒック・キューからの記述子の処理は、ＤＣＰ２０２に対して完全に内部的なものであり、送信したストリーム２２５の閉鎖とは無関係に続行することができるためである。階層５０１の形状、階層内のスケジューラ５０３および５０９のスケジューリング・アルゴリズム、および階層内の仮想出力ポート５２１の位置は、すべてＴＭＣ２０３のユーザによる設定が可能である。
＜エンキュー・データ・メッセージの詳細：図６および図３１＞
すでに説明したように、ＴＭＣ２０３にＱＭＵ２１１が提供するＴＭＣ記述子２１６は、エンキュー・データ・メッセージ内に含まれている。図６および図３１は、好ましい実施形態のエンキュー・データ・メッセージ６０１の詳細を示す。好ましい実施形態においては、エンキュー・データ・メッセージは、最大１３の２４ビット語からなる。エンキュー・データ・メッセージ６０１の長さは、エンキュー・データ・メッセージの語２〜１２内に含まれているｃｐ記述子２１４の長さにより異なる。図６の場合には、エンキュー・データ・メッセージの各フィールドに対して１つの行が存在する。列６０３は１つのフィールドを含む語の語オフセットを示し、列６０５はフィールド名を示し、列６０７は語内のフィールドのビット位置を示し、列６０９はフィールドの内容および目的を記述する。参照番号６１１〜６２７は、フィールドに対する行を示す。フィールド６１５は、ｔｑｉｄ４２３またはｍｅｔｉｄ４２０を含むことができることに留意されたい。ｍｅｔｉｄは、記述子が表すパケットがマルチキャストである場合である。
【００５７】
一般的に、エンキュー・データ・メッセージ６０１のフィールドの性質および目的は、
図６および図３１を見ればよく理解することができる。タイプ・フィールド６１１を除くすべてのフィールドに対する値は、タイプ・フィールドがメッセージがないことを示す場合には、ＴＭＣ記述子２１６からのものである。記述子フィールド６２７は、ＴＭＣ記述子２１６内のカプセルに入っているｃｐ記述子２１４を含む。推論的なエンキューの場合、および廃棄優先順位フィールド６２５の場合には、さらに、コメントが必要になる。推論的エンキューは、ＤＣＰ２０２がまだ完全に受信していないパケットに対するパケット記述子をエンキューするための機構である。推論的にエンキューされたパケットをＤＣＰ２０２が完全に受信していた場合には、コミット・エンキュー・メッセージと呼ばれる第２の１語の長さのエンキュー・メッセージが、推論的エンキューを行うためにＴＭＣ２０３に転送される。エンキュー・メッセージ内のタイプ・フィールド６１１は、推論的またはコミット・エンキュー・メッセージを識別するために使用される。推論的エンキューについては以下にさらに詳細に説明する。廃棄優先順位フィールド６２５は、ＴＭＣ記述子２１６が意図するトラヒック・キューに関連づけられた最大８つの廃棄構成ブロック４３１の内の１つを選択するために使用される。
＜デキュー・データ・メッセージの詳細：図７、図３２および図３３＞
図７、図３２および図３３は、ＴＭＣ２０３がバッファ管理ユニット２１１に送るデキュー・メッセージ７０１のフォーマットを示す。これらの各メッセージは、ＱＭＵ記述子２５０８を含む。すでに説明したように、各フィールドは、列を示す６０３〜６０９、および行を示す７０１〜７２５を含む１つの行を有する。大部分のフィールドの目的および内容は、図７を見れば分かる。廃棄理由フィールド７２３の場合、このフィールドは、エンキュー・プロセッサ３０１が記述子を廃棄した場合に設定される。廃棄トラヒック・キュー２５１からのＱＭＵ記述子２５０８が、キュー管理ユニット２１１に出力された場合には、タイプ・フィールド７０３および廃棄理由フィールド７２３は、ＱＭＵ記述子内のｃｐ記述子２１４が表すパケットのペイロードを廃棄すべきことおよびその理由を示す。フィールドの内容は、ＤＣＰ２０２が、フィールド７０３内の行動を起こして応答しなければならない場合がある廃棄理由、およびフィールド７２３内の情報の目的としての働きをする理由とに分割される。この場合も、アイドル・メッセージのフィールド値を除くデキュー・データ・メッセージ７０１内のすべてのフィールド値は、ＱＭＵ記述子２０８内に含まれる。フィールド７２５はカプセルに入っているｃｐ記述子２１４を含む。
＜トラヒック・キュー・パラメータ・ブロック４０３の詳細：図８および図３４＞
図８および図３４は、好ましい実施形態のトラヒック・キュー・パラメータ・ブロック４０３のフォーマットを示す。すでに説明したように、フォーマットは、列を示す８０１〜８０９およびフィールドを示す８１１〜８６９を含む。列８０９内のフィールドの大部分は図を見れば理解することができる。以下の説明においては、フィールドは、図４の論理サブ区画に関連する。
＜スケジューリング情報４１３＞
この情報を提供するフィールドは、トラヒック・キュー・パラメータ・ブロック４０３が示すトラヒック・キュー２０４に対するトラヒック・クラス・スケジューラ５０３（ｉ）を識別するフィールド８１９、トラヒック・クラス・スケジューラ５０３（ｉ）のトラヒック・キュー２０４に属するどのスケジューラ・キュー５２３（ｊ）を、選択できる場合に、置くべきかを決定するフィールド８３１、トラヒック・キュー２０４を選択することができるかどうか、できる場合には、そのスケジューラ・キューをスケジュールする方法を決定するために使用されるトラヒック・キュー２０４内のヘッドＴＭＣ記述子２１６に関する情報を含むフィールド８４５を含む。この情報は、トラヒック・キュー２０４の記述子が表すパケットのタイプ、およびスケジューラ・キュー５２３（ｉ）が使用するスケジューリング・アルゴリズムにより異なる。ここでは２つの例について説明する。可変長のパケットを表す記述子の場合には、フィールド８４５は、パケットの長さを含み、固定長パケットを表す記述子と共に、フィールド８４５は、固定長パケットにより運ばれているメッセージ内の最後のパケットに対する記述子が、トラヒック・キュー内にすでに受信されたかどうかを示すメッセージの終わりインジケータ（ｅｏｍ）を含む。
＜マルチキャスト情報４１５＞
好ましい実施形態においては、ＴＱタグ・フィールド８６５は、ＱＭＵ２１１にトラヒック・キュー２０４を指定する識別子である。トラヒック・キューは、下記の２つの環境内で指定される。
【００５８】
・ｃｐ記述子２１４が表すパケットがマルチキャストされる場合には、識別子は、エンキュー・プロセッサ３０１がＴＭＣ記述子２１６の特定のコピーを置いたトラヒック・キュー２０４を指定する。
【００５９】
・ｃｐ記述子２１４が表すパケットを廃棄すべき場合には、識別子は、ＴＭＣ記述子がＴＭＣ２０３内に受信された場合に、ｃｐ記述子２１４を含むＴＭＣ記述子２１６内で指定されたトラヒック・キュー２０４を指定する。
＜廃棄情報４１１＞
フィールド８１３および８１４は、トラヒック・キューに対する廃棄構成ブロック４４３を識別する。これらのフィールドにＴＭＣ識別子２１６内の廃棄優先順位フィールド６２５を加えたものは、所与の記述子と併用するブロック４４３内の実際の廃棄構成ブロック４３１を識別する。フィールド８１５，８１６，８６９および８２７は、すべて種々の廃棄技術で使用されるデータを含む。
＜現在のｔｑ状態情報４０９＞
この情報はフィールド８３６内に含まれる。このフィールドはトラヒック・キューの先頭に位置する記述子に関する情報を含む。フィールド内の情報が何であるかは、トラヒック・キューの先頭に位置する記述子が表すパケットのタイプにより異なる。可変長パケットである場合には、フィールド８３６はパケットの長さを含む。固定長パケットの場合には、フィールド８３６は、多重パケット・メッセージに関するパケットの状態を示す。メッセージ内の最後のパケットが到着したかどうか、到着していた場合には、記述子が表すパケットがメッセージ内の最後のパケットであるかどうかを示す。好ましい実施形態においては、トラヒック・キュー内の各ＴＭＣ記述子２１６は、トラヒック・キュー内の次の記述子に対する現在のＴＱ状態情報を含むフィールド８３６のようなフィールドに、それを先頭に付加済みである。
＜Ｔｑヘッド４０５およびＴｑ末尾４０７＞
これらは、それぞれフィールド８２３および８１１内で実施される。好ましい実施形態においては、識別子は、記述子に対する単なるポインタである。ＴＭＣ２０３の設計の機能は、可能な限り、記述子、トラヒック・キューまたはスケジューラ・キューではなく、ポインタが操作されることである。
＜ＴＭＣ２０３が実行する動作の詳細＞
以下の説明においては、エンキュー・プロセッサ３０１が実行するマルチキャスト動作から開始して、エンキュー・プロセッサ３０１、トラヒック・キュープロセッサ３０５、およびデキュー・スケジューラ３０３が実行する動作の例について詳細に説明する。別の実施形態においては、この動作を異なる方法で実行することができることを理解されたい。
＜マルチキャスト：図９および図３５＞
パケットが１つの入力点にある切替え装置に到着すると、パケットはマルチキャストされ、複数の出力点のところから出力される。システム２０１においては、マルチキャストは、ＱＭＵ２１１またはトラヒック管理コプロセッサ２０３で行うことができる。本明細書の記述は、トラヒック管理コプロセッサ２０３でのマルチキャストである。マルチキャストは、エンキュー・データ・メッセージ６０１で受信したＴＭＣ記述子２１６のコピーを、マルチキャスト詳細テーブル４２１内で指定されたトラヒック・キュー２０４に追加することにより行われる。
＜マルチキャスト詳細テーブルの詳細＞
図９および図３５は、好ましい実施形態のマルチキャスト詳細テーブルの詳細を示す。
この場合も、フォーマットは、テーブルのフィールドを表す各行、およびフィールドに関する情報を示す列９０３〜９０９を含む表である。すでに説明したように、ＴＭＣ２０３は、マルチキャスト詳細テーブル４２１のリンクされたリストを維持する。フィールド９１１は、リスト内の次のマルチキャスト詳細テーブル４２１のｍｅｔｉｄ４２０を含む。所与の詳細テーブル４２１が、リンクされたリストの最後のものである場合には、フィールド９１３の値により示される。詳細テーブル４２１は、記述子のコピーを追加することができる最大８つのトラヒック・キューを指定することができる。参照番号９１５は、１つのトラヒック・キューに対するエントリの詳細図を示す。関連する２つのフィールドが存在する。すなわち、トラヒック・キュー２０４に対するｔｑｉｄ４２３を含むフィールド９１６およびフィールド９１６の内容が有効であるかどうかを示すフィールド９１７が存在する。参照番号９１９で示すテーブルの残りの部分は、残りのトラヒック・キューに対するトラヒック・キューエントリ９１５である。
【００６０】
エンキューした記述子の複数のコピーが、同じ仮想出力ポート宛の複数のトラヒック・キューにマルチキャスト合成される場合には、ＱＭＵ２１１は、記述子のコピーがどのトラヒック・キューからのものであるかを判断することができなければならない。トラヒック・キューを識別するフィールドは、パラメータ・ブロックのトラヒック・キュータグ・フィールド８６５である。宛先トラヒック・キューのタグは、トラヒック・キュー内に含まれる記述子から作成した各ＱＭＵ記述子のフィールド７１３内に入れられる。
＜マルチキャスト・エンキュー・データ・メッセージ処理の詳細＞
エンキュー・データ・メッセージ６０１をユニキャストするのかマルチキャストするのかは、エンキュー・データ・メッセージのフィールド６１９により示される。フィールド６１９がマルチキャストを示している場合には、フィールド６１５は、マルチキャストで使用されるＭＥＴチェーン内の第１のマルチキャスト詳細テーブル４２１に対するｍｅｔｉｄ４２０を含む。マルチキャスト・エンキュー・メッセージは、マルチキャスト合成を行うために余分な処理時間を必要とする。余分な処理時間は、エンキュー・プロセッサ３０１により処理されるまで待機している間に、エンキュー・データ・メッセージ６０１をバッファに記憶するために必要な時間である。一般的に、エンキュー・プロセッサ３０１は、ユニキャスト・エンキュー・データ・メッセージの処理に厳格な優先順位を付ける。しかし、エンキュー・プロセッサ３０１により処理される記述子の全数の固定部分がマルチキャスト記述子であることを保証する、ユーザによる設定が可能な機構がある。この部分は、処理される２つの記述子の内の１つから、処理される２５６の記述子の内の１つまでの範囲内に設定し得る。処理を待つマルチキャスト・エンキュー・メッセージは、最大３２のマルチキャスト・エンキュー・メッセージを保持するバッファ内に記憶される。マルチキャスト・エンキュー・メッセージを受信した場合で、マルチキャスト・エンキュー・メッセージ・バッファが満杯である場合は、マルチキャスト・メッセージは、エンキュー・メッセージ・ソース識別子（エンキュー・データ・メッセージのフィールド６２３）に関連づけられた廃棄キューに廃棄される。そうでない場合には、マルチキャスト記述子を廃棄する決定は、マルチキャスト・グループ内の各宛先トラヒック・キューに対するエンキュー・プロセッサ３０１により別々に行われる。
【００６１】
エンキュー・プロセッサ３０１は、関連コミット・エンキュー・メッセージを受信するまで、推論的にエンキューされるマルチキャスト・エンキュー・メッセージを処理しない。このため、推論的にエンキューされたマルチキャスト・メッセージは、関連コミット・エンキュー・メッセージを受信するまで、以降のすべてのマルチキャスト・エンキュー・メッセージを阻止する。この阻止はデキュー・パケット記述子の順序を維持するために必要である。
【００６２】
マルチキャスト・コピーの１つの使用方法は、ＤＣＰ２０２がそれ自身マルチキャスト合成をサポートしない時分割多重化チャネル化インタフェース・装置を駆動しているシス
テム２０１での使用である。マルチキャスト・コピーは、各宛先チャネルに対するパケットの１つのコピーを送信するために使用することができる。
＜記述子廃棄動作の詳細＞
すでに説明したように、エンキュー・プロセッサ３０１が、トラヒック・キュー内にリンクされるトラヒック・キュープロセッサ３０５に記述子を提供する前に、エンキュー・プロセッサ３０１は、記述子が表すパケットを廃棄すべきか、または輻輳を避け、現在の輻輳を管理し、または過去の輻輳から回復するためにタグを付けるべきかを判断する。
＜廃棄およびタグ付け動作＞
輻輳しているかどうかを判断するために、エンキュー・プロセッサ３０１が使用する技術は、バッファしきい値の決定、ランダム早期検出、および管理アルゴリズムを含む。特定のトラヒック・キューに対してどの技術エンキュー・プロセッサ３０１を使用するかは、トラヒック・キューの廃棄構成ブロック４３１により決定される。輻輳は下記のように処理される。
１．輻輳期間から抜け出すために廃棄するパケット記述子の選択。
２．輻輳を避けるために廃棄する不適合パケット記述子の選択。
３．輻輳を避けようとしている下流のネットワーク素子により、不適合パケットを選択的に廃棄できるように、不適合パケット記述子へのタグ付け。
４．下流のネットワーク素子が、元のトラヒック・ソースに速度を低減するように通知することができるように、輻輳を経験したパケット記述子へのマーク付け。
＜バッファ・プールおよび親バッファ・プール：図４＞
エンキュー・プロセッサ３０１が使用するバッファ・プール情報は、廃棄すべきパケットが、バッファ・プールおよび親バッファ・プール・データ構造内に依然として入っているかどうかを判断する。図４は、これらの構造を示す。各バッファ・プールに対するバッファ・プール仕様４３３（ｉ）は、最小しきい値、最大しきい値、およびバッファ・プールの親に対する最小しきい値を示す。トラヒック・キュー２０４（ｉ）が使用するバッファ・プール４３３（ｊ）内のこれらの値は、トラヒック・キュー２４０（ｉ）のための記述子を廃棄するかどうかを決定するために、エンキュー・プロセッサ３０１により使用される。バッファ・プール仕様４３３および親バッファ・プール仕様４３５は、ＴＭＣ記述子２１６がトラヒック・キュー２０４内でエンキューされるか、トラヒック・キュー２０４からデキューされる度に更新される。
＜廃棄トラヒック・キュー＞
トラヒック管理コプロセッサ２０３内で行われたすべての廃棄動作からの記述子は、ＴＭＣ２０３により維持されている３２の廃棄トラヒック・キュー２５１の内の１つに送られる。廃棄トラヒック・キューは、非廃棄トラヒック・キューのようにスケジューリングが行われる。スケジューラ階層は、廃棄キューに対するスケジューラの出力が、廃棄トラヒックのサービス提供専用の仮想出力ポートに送られるように通常構成される。このため、これらの仮想出力ポートは、外へ出てゆくパケット・トラヒックが、バックアップされる時阻止されないで、外へ出てゆくトラヒック・パケットを表す記述子に関連づけられた仮想出力ポート２５１がこれらの記述子のスケジューリングを阻止する。廃棄したパケット記述子に関連づけられたパケットの長さは、スケジューラ帯域幅計算の際に使用されない。この理由は、ＤＣＰ２０２が、廃棄されたパケット記述子を処理するために必要な時間は、パケットの長さとは無関係であるためである。代わりに、０〜２５５バイトの範囲内の構成可能なパケットの長さが、スケジュールを作成する目的で廃棄キュー記述子に割り当てられる。
【００６３】
廃棄されたパケット記述子に対する宛先廃棄キューは、優先順位順に配列された下記のソースの内の１つから選択される。
１．廃棄キュー識別子は、そうしたい場合には、トラヒック・キューの廃棄構成ブロック４３１内に指定することができる。
２．トラヒック・キュー廃棄構成により指定されていない場合には、ＴＭＣ２０３は、キ
ューを廃棄するために、ＴＭＣ記述子２１６のソースに関連するテーブルから廃棄キュー識別子を入手する。ＴＭＣ識別子のソースに対する識別子は、フィールド６０３から入手される。
３．前の２つのソースにより指定されていない場合には、廃棄キュー識別子は、トラヒック・キューのクラス・スケジューラ５０３内に指定される。
＜廃棄アルゴリズムのタイプの概要＞
好ましい実施形態は、多数の異なる廃棄アルゴリズムを提供する。ここで概要を示す。アルゴリズムの内の１つの詳細な例について以下に説明する。異なる各廃棄アルゴリズムに対する廃棄構成ブロック４３１に対しては異なるフォーマットが存在する。
（しきい値設定）
しきい値設定は、下記の条件の下で、バッファ・プールのサイズおよび親バッファ・プールのサイズに基づいて、パケット記述子を選択的に廃棄するために使用される。
１．トラヒック・キューの関連するバッファ・プール・サイズが最小しきい値より小さい場合には、記述子を廃棄しない。
２．トラヒック・キューの関連するバッファ・プール・サイズが最大しきい値より大きい場合には、記述子を廃棄する。
３．バッファ・プール・サイズが最小しきい値と最大しきい値との間であり、親バッファ・プール・サイズが、トラヒック・キューの選択した廃棄構成データが指定する親バッファ・プールしきい値より大きい場合には、廃棄のためにパケット記述子を選択する。そうでない場合には、記述子を廃棄しない。
（ランダム早期検出（ＲＥＤ））
バッファ・プールは、適応トラヒック・ソースに関連づけられたパケット記述子を選択的に廃棄するために、ランダム早期検出（ＲＥＤ）を使用するように設定が可能である。好ましい実施形態で使用するＲＥＤの実施は、下記の基準に基づいて行われる。
【００６４】
１９９３年８月のネットワークに関するＩＥＥＥ／ＡＣＭ議事録（ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ）掲載のフロイド、サリー（Ｆｌｏｄｙ，Ｓａｌｌｙ）およびヤコブセン、ファン（Ｊａｃｏｂｓｏｎ，Ｖａｎ）の「輻輳を避けるためのランダム早期検出（Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ  ｆｏｒ  Ｃｏｎｇｅｓｔｉｏｎ  Ａｖｏｉｄａｎｃｅ）」。
【００６５】
ＲＥＤアルゴリズムは、指数加重平均バッファ・プール・サイズ、および最小および最大平均バッファ・プール・サイズしきい値に依存するランダム廃棄の確率を計算する。平均バッファ・プール・サイズは、トラヒックの一時的バーストが無駄に廃棄されないように、瞬間サイズの代わりに使用される。ＲＥＤをＩＰパケットと併用する場合には、エンキュー・メッセージ６０１の廃棄優先順位フィールド６２５の値を、ＩＰパケットに対して指定された優先権に基づいて、異なるＲＥＤしきい値および確率パラメータを選択するために使用することができる。
（管理）
速度管理（ｒａｔｅ  ｐｏｌｉｃｉｎｇ）は、そのパケットが、トラヒック・キューの割り当てられた、または保証された伝送速度よりも速い速度で受信されているトラヒック・キューを識別するためにトラヒック・キュー毎に使用される。速度管理により、その保証された速度より速い速度を使用しているトラヒック・キューは、決してトラヒック・キューに適合する他の保証速度に悪影響を与えない。速度管理は、バッファ・プールおよび親バッファ・プールしきい値設定アルゴリズムと併用することができる。
【００６６】
速度管理パラメータは、一組または二組の漏洩バケット・パラメータ、すなわち、維持可能な最大速度およびバースト許容範囲および／または最大ピーク速度および遅延変動許容範囲を含む。漏洩バケット適合定義は、可変長パケットおよび固定長パケットをサポートするために拡張したＡＴＭフォーラムＴＭ４．０仕様（ＡＴＭ  Ｆｏｒｕｍ  ＴＭ  ４
．０）により定義される。ＴＭＣ管理機能で実施された漏洩バケットは、ＡＴＭフォーラムＴＭ４．０適合定義６つをすべてサポートするように設定することができる。漏洩バケットは、ＴＭＣ外部の条件のモデルのＴＭＣ２０３の使用のもう１つの例である。
【００６７】
各速度管理トラヒック・キューは、速度および許容範囲を強制的に実施するために、１つまたは２つのクレジット・バケット状態を維持する。トラヒック・キューが初期化された場合、各バケットは、その全許容範囲でクレジットされる。クレジット・バケットは、エンキューされた各パケット・バイトに対して１バイト・クレジットを失い、その構成されたバイト速度でバイト・クレジットを入手する。エンキューされたパケットのバイト・カウントは、トラヒック管理インタフェースを介して受信するその関連するエンキュー・メッセージのパケット・バイト長フィールドからのものである。
【００６８】
ＡＴＭフォーラムＴＭ４．０適合定義は、とるべき行動を定義し、漏洩クレジット・バケットが、エンキューされたパケット・バイト長を収容するだけの十分なバイト・クレジットを有していない場合には、廃棄したり、タグを付けたりする。例えば、ピーク速度漏洩バケットが、パケットを収容するだけの十分なクレジットを有していない場合には、関連するパケット記述子が常に廃棄のために選択される。維持可能な速度バケットが、パケットを収容するだけの十分なクレジットを有さない場合には、パケット記述子は、適合定義により廃棄のためにタグが付けられるか、選択される。
（メッセージ廃棄モード）
メッセージが一連の固定長パケットにより運ばれている場合には、各パケットはそれ自身の記述子を有する。このような一連の固定長パケットにおいては、最後のパケットのヘッダは、パケットがメッセージの終りを運んでいることを示すように設定されたメッセージの終わり（ｅｏｍ）フラグを有する。対応するメッセージの始めフラグは存在しない。代わりに、次のメッセージを開始するパケットが、そのｅｏｍフラグがセットされているパケットの直後に位置するという事実により識別される。固定長パケットを表すＴＭＣ記述子２１６は、記述子がメッセージの最後のパケットを表す場合にセットされるメッセージの終わりフラグを有する。ＥＯＭフラグは、ＴＭＣ記述子のフィールド６１３内に位置する。メッセージの始めのための記述子は、同様に、そのＥＯＭフラグ・セットを有する記述子の直後に位置するという事実により識別される。
【００６９】
メッセージを運ぶために一連のパケットを使用するシステムにおいては、メッセージを構成しているパケット記述子の任意の１つが廃棄された場合、全メッセージを再構成することができず、メッセージに属するすべてのパケットを廃棄しなければならないと仮定する。そのため、メッセージの残りのパケットの廃棄を、第１の廃棄を行った直後に開始できる場合には性能を改善することができる。ルック・アサイド・データ・ストリーム処理中にこの種の廃棄を行う際に難しいのは、メッセージ内の廃棄すべき第１のパケットに対応するＱＭＵ記述子２５０８が必ずｅｏｍフラグ・セットを有するようにすることである。その結果、記述子に対応するパケットを処理しているチャネル・プロセッサは、パケットに適当なマークを付け、次のメッセージの第１のパケットのＱＭＵ記述子を認識することができる。
【００７０】
トラヒック管理コプロセッサ２０３は、下記の４つの異なるメッセージ廃棄モードで動作することができる。
・非メッセージ廃棄モード
・早期パケット廃棄モード
・部分パケット廃棄モード
・修正部分パケット廃棄モード
廃棄モードは、トラヒックごとのキューに基づいて構成される。各トラヒック・キューは、多数の廃棄モードを使用することができる。廃棄モードは、廃棄構成ブロック４３３
内のトラヒック・キューに対して指定される。所与のトラヒック・キューに対して使用することができるこれらの廃棄モードの内のどの廃棄モードを、トラヒック・キュー内の所与の記述子が表すパケットに対して使用すべきかは、記述子内のフィールドにより指定される。どのモードも、廃棄が必要かどうかを決定するための技術の内の任意の技術を使用することができる。
【００７１】
非メッセージ廃棄モードの場合には、メッセージの終わりインジケータは、メッセージの残りのパケットの廃棄方法を決定する際に何の役割も果たさない。
早期パケット廃棄モードの場合には、より大きなメッセージを受け入れるか廃棄するかについての決定は、メッセージの第１のパケットに対する記述子を受信した場合に行われる。第１の記述子を廃棄する場合には、パケットのメッセージに対する残りのすべての記述子も廃棄する。その逆も同じである。メッセージ内に２つ以上のパケットが存在する場合には、第１の記述子はそのＥＯＭフラグ・セットを有さない。残りの記述子を廃棄するには、エンキュー・プロセッサ３０１は、多重パケット・メッセージに属するパケットに対する記述子がすでに廃棄されていて、そのＥＯＭフラグ・セットを含む記述子をまだ受信していないことを示すために、トラヒック・キュー状態フィールド８６１内のフラグをセットする。メッセージのパケットに対する各記述子を受信すると、エンキュー・プロセッサ３０１は、メッセージの終わりフラグを探してフィールド６１３をチェックする。フラグが全くセットされていない場合には、記述子は廃棄される。フィールド６１３内のＥＯＭフラグがセットされている場合には、エンキュー・プロセッサ３０１は記述子を廃棄して、ＥＯＭフラグを含む記述子を受信したことを示すために、トラヒック・キュー状態フィールド８６１内のフラグをセットする。全多重パケット・メッセージを処理できる機会を増やすために、エンキュー・プロセッサ３０１は、バッファ・プールおよび親バッファ・プール仕様が、広いバッファ空間が使用できることを示している限りは、第１のパケットを廃棄することができる。
【００７２】
部分パケット廃棄（ＰＰＤ）モードは、第１のパケットを廃棄する場合には、ＥＰＤモードと同様な動作をする。しかし、このモードの場合には、また、第１のパケットが廃棄されていなかった場合には、「中間パケット」（ｍｉｄｄｌｅ  ｐａｃｋｅｔ）上で廃棄の決定を行うことができる。このような廃棄の決定を行った場合には、決定が行われるパケットおよび最後のパケットを除く以降のすべてのパケットが廃棄される。最後のパケットは廃棄することができない。この理由は、最後のパケットは、次のメッセージの始まりを識別するのに必要なＥＯＭフラグを有するためである。最後のパケットは、また、短縮メッセージの最終受信者に、そのメッセージが不足メッセージであることを示すエラー検出情報を含む。
【００７３】
ルック・アサイド・データ・ストリーム処理の場合には、パケットを廃棄する決定は、当然ながら、パケット自身の上では行われず、パケットを表すＴＭＣ記述子２１６上で行われる。エンキュー・プロセッサ３０１が、廃棄のために中間パケットを表す記述子を選択した場合には、エンキュー・プロセッサ３０１は、多重パケット・メッセージ内のパケットに対する記述子がすでに廃棄され、そのＥＯＭフラグ・セットを含む記述子をまだ受信していないことを示すために、トラヒック・キュー状態フィールド８６１内のフラグをセットする。エンキュー・プロセッサ３０１は、次に、ＥＯＭフラグ・セットを含む記述子を含まないそれまでの記述子を廃棄し、上記のようにフィールド８６１内のフラグをリセットする。最後の記述子を廃棄しなければ、ＤＣＰ２０２からの出力としてのメッセージは、そのＥＯＭフラグ・セットを含む最後のパケットを必ず含んでいる。多重パケット・メッセージを受信しているトラヒック・キューに対して指定した廃棄モードが何であれ、エンキュー・プロセッサ３０１は、メッセージのさらなるパケットを記憶するためのＤＣＰ２０２内のバッファがない場合には、メッセージに属するパケットの残りを廃棄するためにＰＰＤを使用する。当然ながら、この状態は、メッセージのパケットに対する記述
子を受信しているトラヒック・キューに対するバッファ・プール、および親バッファ・プール情報により示される。
【００７４】
最後のメッセージ廃棄モードは、修正部分パケット（ＭＰＰ）モードである。ＭＰＰは、パケット再組立てと共に使用される特殊なメッセージ廃棄方法である。再組立ての場合、多重パケット・メッセージを構成しているパケットに対応するすべての記述子は、メッセージに対する最後のパケットが受信されるまで、ＴＭＣ２０３内に保持され、次に、バーストによりＤＣＰ２０２に出力される。ＤＣＰ２０２は、記述子のバーストが表すパケットを１つのパケットに組立てる。記述子のバーストが表すパケットがＤＣＰ２０２内で１つのパケットに組立てられるという事実は、ＰＰＤの問題を解決するための利点と考えることができる。すなわち、ＰＰＤ技術に従って形成された短縮されたメッセージは、宛先に到着して欠陥があると判断されるまで、システム２０１およびネットワークの残りの部分で引き続きリソースを使用する。ＰＰＤとＭＰＰＤとの間の違いは、ＥＯＭフラグを含むパケットの処理である。ＭＰＰＤにおいては、廃棄中の「中間パケット」に対する記述子は、セットされたＥＯＭフラグ７０５ばかりでなく、それが中間パケットの廃棄であることを示すためにセットされたタイプ・フィールド７０３も含む。中間パケットに対する記述子は、次に、メッセージの再組立てが行われるトラヒック・キュー２０４内に置かれる。メッセージの最後のパケットを含むメッセージのパケットに対する記述子の残りの部分が廃棄される。部分メッセージに対するパケットを表す記述子はスケジュールすることができる。以下に詳細に説明するように、記述子は、トラヒック・キューが指定するトラヒック・クラス・スケジューラに対して仮想ポート２５１が指定する記述子キュー２４７にインタリーブされないで出力される。記述子キュー２４７をサーブするチャネル・プロセッサは、次に、記述子が表すパケットからのペイロードを１つのパケットのペイロードに再度組み立てる。チャネル・プロセッサが、ＥＯＭフラグおよび中間パケット廃棄指標を含む記述子に遭遇した場合には、チャネル・プロセッサは再度組み立てたペイロードを含む１つのパケットを廃棄する。
＜廃棄の詳細な例：図１０および図１１＞
下記の詳細な例においては、廃棄構成ブロック４３１、バッファ・プール仕様４３３、および親バッファ・プール仕様４３５の詳細について、修正部分パケット廃棄モードが使用され、パケットを廃棄すべきかどうかを判断するために、ランダム早期廃棄検出（ＲＥＤ）技術が使用されている場合に対するエンキュー・プロセッサ３０１の動作について詳細に説明する。
＜廃棄構成ブロック４３１の詳細＞
図１０は、この場合に対する廃棄構成ブロック４３１のフィールドである。廃棄構成ブロック４３１は２つの部分、すなわち、そのフィールドがすべての廃棄構成ブロックに対して共通な部分１００１および１０１９、そのフィールド１０２３〜１０２９が、いつパケットを廃棄すべきかを判断するための技術の内の１つに特有な部分１００３からなる。部分１００１の共通なフィールドおよびフィールド１００１９から説明するが、参照番号１００２は、通常の方法による、パラメータ・ブロック４３１の共通の部分のフォーマットを示す。このフォーマットは、各フィールドに対して、列１００４〜１００６および１つの行を含む。フィールド１０１９から説明すると、このフィールドは、パケットを廃棄すべきかどうかを判断するために使用する技術を示すコードを含む。この場合、コードは０１１ｂであり、ＲＥＤ廃棄技術が適用されていることを示す。
【００７５】
フィールド１０１７は、廃棄構成ブロック４３１に関連づけられた廃棄トラヒック・キューに対するｔｑｉｄ４２３を含むことができる。記述子が廃棄構成ブロック４３１に指定されているように廃棄されると、それはフィールド１０１７内に指定された廃棄トラヒック・キューへ廃棄される。フィールド１０１５は、フィールド１０１７内に実際に有効なｔｑｉｄが存在するかどうかを示す。ｅｏｍ制御フィールド１０１３は、トラヒック・キューに対して、メッセージ廃棄モードのどれを使用すべきかを指定するコードを含む。
フィールド１０１１〜１００８は、それにトラヒック・キュー２０４が属するバッファ・プールおよびバッファ・プールの親に対するしきい値を指定する。フィールド１０１０および１０１１が指定するバッファ・プール最大しきい値は、バッファ・プールに内蔵させることができるパケットの全最大サイズを指定する。キューに新しいパケットを追加した場合に、この制限を超えた場合には、パケットに対する記述子はトラヒック・キューに追加されず、代わりに廃棄キュー内に入れられる。フィールド１００８および１００９が指定する親バッファ・プールの最大しきい値は、親バッファ・プールの子であるバッファ・プールにより共有するために使用することができる、パケット記憶装置の大きさを指定する。記述子が表す受信パケットに対して記憶装置の空間が十分ない場合には、記述子はトラヒック・キューに追加されずに、廃棄キュー内に入れられる。
【００７６】
フィールド１００７は、その内容がいつパケットを廃棄すべきかを検出するために使用する技術により変化する廃棄構成ブロック４３１の一部を含む。図１０においては、これらのフィールドは、ＲＥＤ部分１００３のフィールド１０２３〜１０２９である。ＲＥＤ技術は、この技術をいつ適用すべきかを決定するために最小しきい値を使用する。トラヒック・キューのバッファ・プール内のパケットの全サイズが、受信パケットをトラヒック・キューに追加した後のサイズより小さい場合には、受信パケットは、親バッファ・プールの状態がどうであれ廃棄されない。フィールド１０２７および１０２９はこの最小しきい値を含む。トラヒック・キューのバッファ・プール内のパケットの全サイズが、バッファの最小しきい値とバッファ・プールの最大しきい値との間である場合には、ＲＥＤ技術は、パケットを廃棄すべきかどうかを決定するために、バッファ・プール仕様４０３内に記憶している他の情報と共に、フィールド１０２３および１０２５内に定義されている確率項を使用する。フィールド１０２１はこの構成では使用されない。
＜バッファ・プール仕様４３３の詳細：図１１＞
廃棄構成ブロック４３１のように、バッファ・プール仕様４３３は、２つの部分、すなわち、参照番号１１０２で示すすべてのバッファ・プール仕様に共通な部分と、参照番号１１０３で示すいつパケットを廃棄すべきかを決定するための所与の技術に特有な部分とを含む。図１１の部分１１０３は、ＲＥＤ技術が必要とする部分である。バッファ・プール仕様４３３は、廃棄構成ブロック４３３と同じ方法で示されている。
【００７７】
部分１１０２内の共通なフィールドから説明するが、１１０７は部分１１０３が置かれるフィールドである。１１０８は、仕様４３３が表すバッファ・プールの瞬間的（すなわち現在の）サイズを含む。フィールド内の値は、バッファ・プールに属するトラヒック・キューへの記述子の追加、またはこれらのトラヒック・キューからの記述子の除去を追跡するために更新される。第１の場合には、記述子が表すパケットのサイズは、バッファ・プールの瞬間的なサイズに追加され、第２の場合には、パケットのサイズは、バッファ・プールの瞬間的なサイズから差し引かれる。フィールド１１０９および１１１０は、それ以下では、パケットをバッファ・プールに属するトラヒック・キューから廃棄されないバッファ・プールのサイズを指定する。
【００７８】
ｓｉｚｅｉｎＰａｃｋｅｔｓＮｏｔＢｙｔｅｓフィールド１１１１は、バイト数またはパケット数でバッファ・プール・サイズを指定すべきかどうかを示す。親バッファ・プール識別子１１１３は、バッファ・プールの親バッファ・プールに対する識別子である。廃棄データ構成タイプ１１１５は、最終的に、バッファ・プールに属するトラヒック・キューが使用する廃棄技術を指定する。廃棄データ構成タイプ１１１５は、これらトラヒック・キュー内のフィールド１０１９が指定したように、同じ技術を指定しなければならない。この例のフィールド１１１５内においては、廃棄データ構成タイプ１１１５は、ＲＥＤ廃棄技術を指定する。
【００７９】
参照番号１１０３は、ＲＥＤ廃棄技術に特有のフィールドを示す。ＲＥＤ技術は、その
計算の際に平均バッファ・サイズを使用し、フィールド１１１７はその値が最後に更新された時間であり、一方、フィールド１１１９は、値自身を含む。フィールド１１２１〜１１２９はすべてＲＥＤ廃棄技術で使用する値を含む。フィールド１１０１および１１１５は、バッファ・プール仕様４３３の共通部分１１０２からの情報を含む。
＜廃棄動作の詳細：図１２＞
図１２は、トラヒック・キューの廃棄構成ブロック４３１が、パケットを廃棄すべきかどうかを決定するために、ＲＥＤ技術が使用することを示す廃棄データ・タイプ・フィールド１０１９、および部分的パケット廃棄の修正ＰＰＤフォームを使用すべきことを示すｅｏｍ制御フィールド１０１３内にあるタイプを有する場合に、エンキュー・プロセッサ３０１が、多重パケット・メッセージを処理する方法のフローチャートである。トラヒック・キューが、メッセージ内のパケットに対する記述子を受信している限りは、エンキュー・プロセッサ３０１は、トラヒック・キューに関するループ１２０５を実行する。
【００８０】
すでに説明したように、エンキュー・プロセッサ３０１が、パケットを廃棄するためにＭＰＰＤアルゴリズムを使用している場合には、エンキュー・プロセッサ３０１は、ＴＭＣ記述子２１４の内の１つを廃棄しなければならなくなるまで、非廃棄トラヒック・キュー２０４へのメッセージ内のパケットを表すＴＭＣ記述子２１４を出力する。この時点以降、エンキュー・プロセッサ３０１は、自分がメッセージの最後のパケットに対する記述子を受信するまで、トラヒック・キューを廃棄するために残りのパケットに対する記述子を廃棄する。この記述子は、そのＥＯＭフラグ・セットを有し、エンキュー・プロセッサ３０１は、エラーを示すためにそれにマークを付け、それを廃棄しなかったメッセージのパケットを含む非廃棄トラヒック・キューに出力する。パケットのペイロードを１つのパケットに再組立てしているＤＣＰ２０２内のチャネル・プロセッサが、そのＥＯＭフラグ・セットを有し、欠陥ありとマークされた記述子に遭遇した場合には、チャネル・プロセッサは再度組立てたパケットを廃棄する。
【００８１】
図１２のフローチャート１２０１に示す、好ましい実施形態のアルゴリズムの実施について引き続き詳細に説明するが、まず開始点１２０３から開始してループ１２０５に入る。エンキュー・プロセッサ３０１は、最初に、メッセージに対する次の記述子を入手する。トラヒック・キューのトラヒック・キュー・パラメータ・ブロック４０１内のトラヒック・キュー状態フィールド８３７および８５３が、キューが多重パケット・メッセージのパケットに対する記述子を受信中であること、およびメッセージを廃棄すべきであること（１２０９）を示している場合には、記述子が表すパケットが廃棄トラヒック・キューに追加される。この追加を行うために、分岐１２１１が実行される。そうでない場合には、分岐１２１３はブロック１２１５へ進む。多重パケット・メッセージの一部ではない記述子の場合には、この実施形態と関係がない。ブロック１２１５においては、次の記述子が表すパケットのサイズが、新しい値、新しいＢＰｓｚを入手するために、トラヒック・キューのバッファ・プール仕様のＢｐサイズ・フィールド１１０８内の値に追加され、値、新しいＰＢＰｓｚを入手するために、親バッファ・プール仕様４３５内の対応する値に追加される。これらの値は、記述子の処理方法を決定するための、ケース・ステートメント１２１７内のバッファ・プールおよび親バッファ・プールに対する廃棄構成ブロック４３１内のしきい値の値と共に使用される。
【００８２】
下記の３つの可能性がある。
・新しいＢＰｓｚは、廃棄構成ブロック４３１のフィールド１０２７および１０２９の最小許容しきい値の値より小さい。この場合、パケットは廃棄されない（分岐１２１９）。
【００８３】
・新しいＰＢＰｓｚは、廃棄構成ブロック４３１内の親バッファ・プールに対する最大しきい値フィールド１００８および１００９の値より大きい。または新しいＢＰｓｚは、
廃棄構成ブロック４３１内のバッファ・プールに対する最大しきい値フィールドの値より大きい。この場合、パケットは廃棄される（分岐１２２３）。
【００８４】
・そうでない場合には、パケットを廃棄すべきかどうかを決定するために、ＲＥＤ技術が使用される（分岐１２２１）。ＲＥＤ技術は、決定を行うために、バッファ・プール仕様４３１内の確率項情報を使用する。
【００８５】
第１の可能性の場合、記述子は、図１２５１に示すように、非廃棄トラヒック・キューに単に追加される。第３の可能性の場合、ＲＥＤ技術がパケットが廃棄すべきでないことを示している場合には（ブロック１２２５）、分岐１２２７は分岐１２１９に進み、記述子は非廃棄トラヒック・キューに追加される。第２の可能性の場合には、またはＲＥＤ技術がパケットを廃棄すべきであると示している場合には、分岐１２２９に進む。この理由は、両方の場合とも、トラヒック・キュー状態フィールド８３６を、この記述子および以降の記述子を廃棄すべきことを示すために設定しなければならないためである。状態はブロック１２３１で設定される。
【００８６】
廃棄すべき記述子の場合には、次のステップにおいて、記述子がそのＥＯＭフラグ・セットを有するかどうかのチェックが行われる（決定ブロック１２３３）。持っている場合には（分岐１２３７）、ＭＰＰＤ技術は、記述子がエラーを含んでいるというマークを付け、非廃棄トラヒック・キューに入れることを要求する。これは１２３９および１２４１において行われる。そうでない場合には、分岐１２３５に進み、記述子が廃棄トラヒック・キューに追加される。すべての場合、それがＥＯＭ記述子であるかどうかをチェックするために、記述子が再度チェックされる。そうでない場合には、ループ１２０５は継続する（分岐１２４５）。そうでない場合には、ループは終了し（分岐１２４７）処理が終了する（１２４９）。
＜推論的エンキュー：図１３＞
推論的エンキューは、受信プロセッサ２２１が、記述子２１６が表す全パケットを受信する前に、トラヒック・キュー２０４にＴＭＣ記述子２１６を提供できるようにする技術である。ＴＭＣ２０３は、受信プロセッサ２２１が全パケットの受信に成功したか失敗した後まで、ＴＭＣ記述子２１６内に含まれているｃｐ記述子２１４が、ＱＭＵ２２１への出力でないことを保証する。受信プロセッサは、一組のエンキュー・データ・メッセージ６０１により推論的エンキューを行う。第１のエンキュー・データ・メッセージは、パケットに対するＴＭＣ記述子２１６を含み、フィールド６１１内に記述子２１６が表すパケットが推論的にエンキューされていることを示す。受信プロセッサ２２１がパケットの処理を終了した場合には、第２のエンキュー・データ・メッセージ、コミット・メッセージが後に続く。この場合も、フィールド６１１は、メッセージがコミット・メッセージであることを示す。コミット・メッセージが到着した後でだけ、ＴＭＣ２０３は、第１のエンキュー・データ・メッセージ内に含まれているｃｐ記述子２１４を出力する。
【００８７】
推論的にエンキューは、それがトラヒック・キュー２０４に提供中の受信プロセッサ２２１内で表すパケットの受信の開始から、ＴＭＣ記述子２１６に対する固定待ち時間を保証するのに有用である。このような固定待ち時間は、多数の受信プロセッサ２２１の間で、パケットの１つの高い帯域幅ストリーム（ＯＣ４８ｃパケット・ストリームのような）から受信したパケットの処理を分散するＤＣＰ２０２内で稼働しているアプリケーションにとって重要なものである。分散受信パケット処理の場合には、受信順序と同じ順序でトラヒック・キューに必ず記述子が提供されるように注意しなければならない。ＤＣＰ２０２においては、受信プロセッサが厳格なラウンドロビン順序でパケットを処理し、自分たちが処理しているパケットに対するＴＭＣ記述子２１６を同じ厳格なラウンドロビン順序でＱＭＵ２１５に出力し、また記述子キュー２１３内の記述子の順序が正しくなるように、受信プロセッサをセットアップすることにより順序が維持される。パケット受信の開始
と推論的エンキュー機構によるトラヒック・キュー２０４内のエンキュー間の固定待ち時間は、全パケットの受信をＴＭＣ２０３への記述子の提供と分離し、そのため、小さなパケットを受信しているチャネル・プロセッサが、より長いパケットを受信しているチャネル・プロセッサがその全パケットを受信するまで阻止された場合に発生する受信帯域幅を狭くしないで、この記述子の厳格なラウンドロビン処理をできるようにする。
【００８８】
続けてより詳細には、好ましい実施形態においては、コミット・エンキュー・データ・メッセージのフィールド６２３は、推論的にエンキューされているパケットのソース、すなわち、記述子が表すパケットを受信した受信プロセッサを識別する。全パケットを受信プロセッサ２２１で受信した場合には、受信プロセッサ２２１は、コミット・エンキュー・データ・メッセージを送信する。図１３の参照番号１３０１は、コミット・エンキュー・データ・メッセージの詳細図である。コミット・エンキュー・データ・メッセージ１３０１は、タイプ・フィールド６１１とソース識別子フィールド６２３だけしか含んでいない。タイプ識別子フィールド６１１は、パケットの受信に成功したことを示すコミットの成功、またはパケットを正しく受信できなかったことを示すコミットの失敗を示すように設定することができる。同じ受信プロセッサが全パケットを受信するので、デキュー・データ・メッセージ内のソース識別子フィールド６２３は、パケットを表す記述子に対するエンキュー・データ・メッセージ内の値と同じ値に設定される。
【００８９】
コミット・エンキュー・メッセージが到着すると、トラヒック・キュープロセッサ３０５は、コミット・エンキュー・メッセージを、対応する推論的エンキュー・メッセージからのＴＭＣ記述子２１６と整合するために、コミット・エンキュー・メッセージにより送られたＴＭＣ記述子内のソース識別子フィールド６２３の値を使用する。好ましい実施形態においては、整合プロセスは、ＤＣＰ２０２内には少数の受信プロセスしか存在しないし、所与のソースは、所与のトラヒック・キュー内の推論的エンキュー・メッセージから未決着のＴＭＣ記述子２１６を１つしか持つことができないので整合の処理は簡単になる。整合が行われた場合、トラヒック・キュープロセッサ３０５は、推論的にエンキューしたＴＭＣ記述子２１６内のフィールド６１１の値を、コミット・メッセージ内のフィールド６１１の値が決定したように設定する。コミット・メッセージ内のフィールドが「成功によるコミット」を示した場合には、トラヒック・キュープロセッサ３０５は、推論的エンキュー・メッセージ内のフィールド６１１の値を、正常なエンキュー・メッセージを示すように設定する。フィールドが「失敗によるコミット」を示している場合には、トラヒック・キュープロセッサ３０５は、推論的エンキュー・メッセージ内のフィールド６１１の値を、失敗を含む正常なエンキュー・メッセージを示すように設定する。修正した推論的エンキュー・メッセージの記述子が、そのトラヒック・キューの先頭に到着し、スケジューリングが行われ、キュー管理ユニット２１１にデキューされると、記述子に対するデキュー・データ・メッセージは、コミット・メッセージによりフィールド６１１が設定された値に対応するフィールド７０３内の値を有する。好ましい実施形態のキュー管理ユニット２１１は、記述子を処理しているチャネル・プロセッサ上のフィールド６１１に送り、チャネル・プロセッサは、フィールド６１１が推論的エンキューに失敗したことを示している場合には、何をするのかを決定する。当然ながら、ほとんどの場合、チャネル・プロセッサはパケットを廃棄させる。
【００９０】
推論的エンキューの重要な面は、スケジューリングに対するその影響である。推論的にエンキューされたＴＭＣ記述子２１６内のｃｐ記述子２１４は、コミット・メッセージを受信するまでＱＭＵ２１１に出力することはできないので、そのヘッドＴＭＣ記述子２１６が、コミット・メッセージがまだ受信されていない推論的にエンキューされた記述子であるトラヒック・キュー２０４は、スケジューリングのために選択することができない。このため、このようなトラヒック・キューが、スケジューラ・キュー５２３の先頭に到着すると、トラヒック・キュープロセッサ３０５は、ＴＭＣ記述子２１６がサービスを受け
る前に、スケジューラ・キュー５２３からトラヒック・キュー２０４を除去し、それをトラヒック・キューのトラヒック・クラス・スケジューラ５０３に関連づけられた選択できないトラヒック・キュー内に入れる。トラヒック・キュープロセッサ３０５が、トラヒック・キュー２０４を選択可能にするコミット・メッセージを受信した場合には、トラヒック・キュープロセッサ３０５は、トラヒック・キュー２０４をトラヒック・クラス・スケジューラに対するスケジューラ・キューに返送する。
＜デキュー・スケジューラ３０３が実行する動作の詳細＞
デキュー・スケジューラ３０３は、スケジューラ階層５０１内のスケジューラを実行し、これによってＴＭＣ２０３のスケジューリング機能、シェーピング機能、およびセグメント分割機能および再組立て機能を実行する。最初に、ＴＭＣ２０３の好ましい実施形態で使用することができるスケジューラの一般的な説明を行い、次に、好ましい実施形態のスケジューラが使用するスケジューリング・アルゴリズム、シェーピング・アルゴリズム、およびセグメント分割アルゴリズム、および再組立てアルゴリズムについて説明し、最後にスケジューラの詳細な例およびこれらスケジューラの実施および実行方法について説明する。
＜ＴＭＣ２０３内のスケジューラ＞
概論ですでに指摘したように、デキュー・スケジューリングは、ＴＭＣ２０３のユーザによる広範な設定が可能であるスケジューリング階層５０１により行われる。以下の説明においては、スケジューラの種類、スケジューラの構成方法、およびスケジューラの動作方法について詳細に説明する。
【００９１】
概論で説明したように、スケジューラは、階層内のその位置により階層５０１内で分類される。トラヒック・クラス・スケジューラ５０３は、リーフ・ノードのところに位置しており、内部スケジューラ５０９は、内部ノード内に位置している。好ましい実施形態のスケジューラは、スケジューラの入力スケジューラ・キュー５２３の間から出力する目的で、スケジューラ・キュー５２３を選択するために、下記のタイプのスケジューリング・アルゴリズムを使用することができる。
【００９２】
・入力スケジューラ・キュー５２３の間で厳格な優先順位により出力スケジューラ・キュー５２３が選択される厳格な優先順位
・ラウンドロビン
・各入力スケジューラ・キューに加重が与えられ、所与の入力スケジューラ・キューが受信した帯域幅の共有が、所与の入力スケジューラ・キューの加重と、すべての入力スケジューラ・キューの全加重との間の関係により決まる加重均等化共有
・パケット・バイト長をベースとする加重均等化共有スケジューリングを行う、フレームをベースとする不足ラウンドロビン
・その記述子が固定サイズのパケットを表す、入力トラヒック・キュー間で使用できる帯域幅を割り当てるグループ化加重均等化キューイング
好ましい実施形態においては、トラヒック・クラス・スケジューラ５０３は、上記スケジューリング・アルゴリズムの内の任意のものを使用するように設定することができるが、内部スケジューラ５０９は、厳格な優先順位アルゴリズム、ラウンドロビン・アルゴリズム、または加重均等化共有アルゴリズムだけを使用するように設定することができる。当然ながら、階層５０１を通してスケジューラ・キューが移動する経路２０９に沿ったいくつかの点で、異なるタイプのスケジューラを使用することもできる。
＜構成スケジューラ：図１４＞
図１４は、好ましい実施形態でスケジューラを構成するユーザが使用することができるリソースである。これらのリソースが、以下の説明において論理スケジューラ１４０１と呼ぶものを構成している。ユーザは、論理スケジューラ１４０１が提供するリソースの中から選択を行うことによりトラヒック・クラス・スケジューラまたは内部スケジューラを構成する。リソースは、厳格な優先順位スケジューラ１４０７、過度スケジューラ１４１
５、および保証スケジューラ１４１３を含む。
【００９３】
３つのスケジューラ１４１３、１４１５および１４０７は、下記のように相互に関連している。保証スケジューラ１４１３は、スケジューラ１４０１がスケジューリングを行うために使用することができる全帯域幅の一部が、論理スケジューラ１４０１に対する入力スケジューラ・キュー間で共有するために使用できることを保証する。保証部分の共有が帯域幅を完全に使用しない場合には、各スケジューラ・キューは、帯域幅の保証されていない部分の一部を受信し、使用するためにさらに選択することができる。過度スケジューラ１４１５は、帯域幅のこのまだ保証されていない部分のスケジューリングを行うために使用することができる。このため、その保証された帯域幅をすで使用してしまっているために、スケジューラ１４１３がスケジューラ・キュー５２３を選択することができない場合には、スケジューラ・キューは、帯域幅の保証されていない部分のスケジューリングを行う、過度スケジューラ１４１５が選択するために依然として選択することができる。スケジューラ１４１３の出力１４０９、およびスケジューラ１４１５の出力１４１１は、厳格な優先順位スケジューラ１４０７に進み、厳格な優先順位スケジューラは、スケジューラ１４１５が選択した任意のスケジューラ・キューより、スケジューラ１４１３の優先順位が選択した任意のスケジューラ・キューを与える。出力１４０３にある論理スケジューラ１４０１のスケジューラ・キュー出力は、スケジューラ１４０７が選択したものである。
【００９４】
可能な構成について引き続きより詳細には、好ましい実施形態においては、保証スケジューラは、常に非作業保存加重均等化キューイングスケジューラとして構成される。好ましい実施形態においては、特に重要な加重均等化キューイングスケジューラの１つの形は、フレームをベースとする不足ラウンドロビン・スケジューラである。過度スケジューラは、厳格な優先順位スケジューラ、ラウンドロビン・スケジューラまたは作業保存加重均等化キューイングスケジューラとして構成することができる。保証スケジューラが、非作業保存加重均等化キューイングスケジューラとして構成される場合には、過度スケジューラは、厳格な優先順位スケジューラ、ラウンドロビン・スケジューラ、または加重均等化キューイングスケジューラとして構成することができる。
＜スケジューラが使用するアルゴリズムの詳細＞
好ましい実施形態でスケジューラが使用するアルゴリズムの内のラウンドロビンおよび厳格な優先順位についてはこれ以上の説明は省略する。以下の説明においては、加重均等化キューイング、フレームをベースとする不足ラウンドロビン、およびグループ化加重均等化キューイングについてより詳細に説明する。
＜加重均等化キューイング＞
加重均等化キューイングは、動的に、システム２０１を通過するトラヒックのいくつかの流れに優先順位または加重を適用する。低い加重を有するトラヒックの流れは、すべての流れが使用することができる帯域幅のより大きな部分を入手し、所与の流れが使用することができる帯域幅の幅は、流れの現在の数および加重により変化する。加重均等化キューイングの利点は、即時送信を必要とする対話型トラヒックのようなトラヒックが、低い加重を受けとることができることであり、一方、即時送信を必要としないトラヒックは、高い加重を受け取ることができることである。種々のトラヒックのどれも、他のトラヒックを阻止しないし、すべてのトラヒックが必要とするアクセスのタイプを入手する。通常、加重均等化キューイングアルゴリズムを使用する場合、入力セッションが受信するサービスまたは帯域幅の部分的な大きさは、そのセッションの加重をすべての入力セッションの加重の合計で割ったものに等しい。ＴＭＣ２０３においては、スケジューラの各能動およびスケジュール可能な入力スケジューラ・キュー５２３は、１つの入力セッションを表す。
【００９５】
パケット・トラヒックに対する種々の「加重均等化キューイング」アルゴリズを定義す
る多くの論文がこれまでに発表されている。これらの種々の加重均等化キューイングアルゴリズムは、すべて一般化プロセッサ共有（ＧＰＳ）モデルに由来するものであって、すべてのアルゴリズムは異なる均等化特性を有する。ＴＭＣ２０３の好ましい実施形態で使用するアルゴリズムの種々のタイプは、最も簡単な構造で最善の遅延および均等化特性を達成しようとする。
【００９６】
好ましい実施形態の加重均等化キューイングスケジューラは、作業保存または非作業保存スケジューラとして構成することができる。作業保存スケジューラは、スケジューラ・キューが能動状態またはスケジューリングを行うことができる場合には、常に入力スケジューラ・キューにサービスを提供することができる。作業保存スケジューラの目標は、スケジューラの入力スケジューラ・キューが最小の多忙さでサービスを受ける一定の速度を発生するために、スケジューラ入力を完全にインタリーブすることである。作業保存スケジューラは、スケジューラがスケジューラ・キューを出力することができる速度は可変であり、そのため好ましい実施形態の加重均等化キューイングアルゴリズムで使用するシステムの潜在的または仮想時間機能は、リアルタイムの速度で進行しないで、その代わりに提供されるサービスの量により進行するものと仮定する。非作業保存スケジューラにおいては、入力スケジューラ・キューは、リアルタイムで特定のモメントが発生するまでサービスを受けない。そのモメントが起こるまで、次にサービスを受けるトラヒック・キューは、選択することができなくなったために除去されない限り、そのままスケジューラ・キューの先頭に位置する。
＜フレームをベースとする不足ラウンドロビン＞
フレームをベースとする不足ラウンドロビン・スケジューリング・アルゴリズムは、可変長パケットからなるトラヒック・ストリーム用に使用される。このアルゴリズムは、通常帯域幅保証を必要としないか、または厳格なジッタおよび遅延要件を有するトラヒック・キュー間で使用できるサービス帯域幅を加重均等化共有割当てする。このアルゴリズムは、通常、長いメッセージ・パケットおよび遥かに短い肯定応答パケットが混ざっているＴＣＰトラヒックに対して特に有用である。
【００９７】
好ましい実施形態においては、アルゴリズムは、トラヒック・クラス・スケジューラ５０３で使用される。フレームをベースとする不足ラウンドロビン・トラヒック・クラス・スケジューラは、３つの入力スケジューラ・キューを有する。１つは、高優先順位スケジューラ・キューと呼ばれ、他の２つは現在のスケジューラ・キューおよび次のスケジューラ・キューと呼ばれる。トラヒック・クラス・スケジューラ５０３は、高優先順位スケジューラ・キューおよび現在のスケジューラ・キューだけを、現在のスケジューラ・キューより高い優先順位を有する高優先順位スケジューラ・キューでスケジューリングを行う。スケジューラ５０３は、空になるまで現在のスケジューラ・キューのスケジューリングを行う。この時点で、スケジューラ５０３は、現在のスケジューラ・キューと次のスケジューラ・キューとを交換する。選択可能になったトラヒック・キューは、次のスケジューラ・キューに追加され、時間間隔中にサービスのその共有分を受信したトラヒック・キューは、現在のスケジューラ・キューまたは高優先順位スケジューラ・キューから除去され、次のスケジューラ・キューに追加される。選択不能になったトラヒック・キューは、高優先順位スケジューラ・キューまたは現在のスケジューラ・キューから除去される。
【００９８】
ＦＢＤＲＲアルゴリズムは、トラヒック・キューを高優先順位スケジューラ・キュー間で移動し、これらスケジューラ・キューの両方から次のスケジューラ・キューへ移動する。トラヒック・キューは、ＦＢＤＲＲスケジューラ内の２つのトラヒック・キュー・パラメータと、各トラヒック・キュー内の２つのカウンタの値により移動する。パラメータは下記の通りである。
【００９９】
・トラヒック・キューが、高優先順位スケジューラ・キュー、または現在のスケジュー
ラ・キューから次のスケジューラ・キューに移動する前に、トラヒック・キューが受信することができるサービスの最大量を指定する最大割合（ｍａｘｉｍｕｍ  ｑｕａｎｔｕｍ）、および
・トラヒック・キューが、高優先順位キューから現在のスケジューラ・キューへ移動する前に、トラヒック・キューが受信するサービスの量を指定する最小割合（ｍｉｎｉｍｕｍ  ｑｕａｎｔｕｍ）。
【０１００】
カウンタは、不足カウンタおよびＢｙｔｅｓＳｅｒｖｅｄＴｈｉｓＲｏｕｎｄＣｏｕｎｔｅｒである。値はトラヒック・キューのパラメータ・ブロック４０３内のスケジューラ状態フィールド８４５内に記憶される。
【０１０１】
スケジューラが、現在のスケジューラ・キューのスケジューリングを開始すると、現在のスケジューラ・キュー内の各トラヒック・キューに対する不足カウンタは、不足カウンタの現在の値に最大割合を加算した値にセットされ、トラヒック・キュー用のＢｙｔｅｓＳｅｒｖｅｄＴｈｉｓＲｏｕｎｄＣｏｕｎｔｅｒはゼロにセットされる。所与のトラヒック・キューが、現在のスケジューラ・キューまたは高優先順位キューの先頭に到着する度に、ヘッド記述子内に指定されているパケット長が、不足カウンタの現在の値から減算され、そのパケット長が、ＢｙｔｅｓＳｅｒｖｅｄＴｈｉｓＲｏｕｎｄＣｏｕｎｔｅｒに加算される。興味のある結果が３つある。
【０１０２】
・減算の結果が正である場合、および加算の結果が最小割合より小さい場合、および所与のトラヒック・キューが、まだ高優先順位スケジューラ・キュー内に存在しない場合には、所与のトラヒック・キューは、現在のスケジューラ・キューから高優先順位スケジューラ・キューへと移動する。
【０１０３】
・減算の結果が正である場合、および加算の結果が最小割合より大きい場合であって、すでに存在している場合には、トラヒック・キューは現在のスケジューラ・キュー内に留まる。そうでない場合には、トラヒック・キューは、現在のスケジューラ・キューの末尾に移動する。いずれの場合も、ＢｙｔｅｓＳｅｒｖｅｄＴｈｉｓＲｏｕｎｄはゼロにセットされる。
【０１０４】
・減算の結果が負である場合には、所与のトラヒック・キューは、現在のスケジューラ・キューまたは高優先順位キューから除去され、次のスケジューラ・キュー内に入れられる。そうした場合、不足カウンタは、不足カウンタに最大割合を加算したものにセットされ、ＢｙｔｅｓＳｅｒｖｅｄＴｈｉｓＲｏｕｎｄはゼロにセットされる。最大割合に不足カウンタを加算すると、トラヒック・キューは、このラウンドで受信できなかったサービスを次のラウンドで受信する機会が与えられる。
【０１０５】
高優先順位スケジューラ・キュー、およびトラヒック・キューを高優先順位スケジューラ上に置き、高優先順位スケジューラから除去するための規則により、そのヘッド記述子が最小割合パラメータより小さいパケットを表すトラヒック・キューは、確実に優先順位サービスを受けることになる。これにより、今度は、ＴＣＰ肯定応答パケットに対する記述子のスケジューリングが確実に迅速に行われる。ＦＢＤＲＲアルゴリズムの他のバージョンは、現在のスケジューラ・キューおよび次のスケジューラ・キューだけを必要とする。このバージョンの場合、高優先順位スケジューラ・キューへ移動する条件を満足させたトラヒック・キューは、単に、それが次のスケジューラ・キューに移動するための条件を満足するまで、現在のスケジューラ・キューの先頭にそのまま位置する。
＜グループ化加重均等化キューイング＞
トラヒック・クラス・スケジューラは、グループ化加重均等化キューイングアルゴリズムを使用することができる。このアルゴリズムは、加重均等化キューイングアルゴリズム
に類似しているが、共通のサービス加重およびパケット・サービス間隔を有する複数のグループのトラヒック・キュー間でサービス帯域幅を分配するためにすでに修正されている。このアルゴリズムは、入力スケジューラ・キュー毎の加重均等化共有とは反対に、トラヒック・キュー毎に加重均等化共有を割り当てる。
【０１０６】
グループ化加重均等化キューイングスケジューラは、下記のように機能する。
１．同じ入力スケジューラ・キューに割り当てられたすべてのトラヒック・キューは、同じサービス加重および同じパケットサービス間隔を共有する。すなわち、スケジューラは、固定の一組の加重、各入力スケジューラ・キュー内のすべてのトラヒック・キューに対する１つの加重をサポートし、また、同じ入力スケジューラ・キューに属するすべてのトラヒック・キューは、同じサイズ２のパケットを運ぶものと仮定する。スケジューラは、選択可能な各トラヒック・キューに対して加重均等化共有を保証するが、最悪の場合の最初の待ち時間上のトラヒック・キューの保証された境界は、そのトラヒック・キューのスケジューラ・キュー内の選択可能なトラヒック・キューの数により影響を受ける恐れがある。このスケジューリング・アルゴリズムは、帯域幅を保証する場合、またはＡＴＭセルのような固定サイズのパケットを運ぶトラヒック・キューの間で使用できる帯域幅を割り当てる場合に有用である。
＜シェーピングの詳細＞
ＴＭＣ２０３内でのシェーピングは、必要なデキュー伝送速度特性を達成するために、トラヒック・キューまたはトラヒック・キューの集合体からパケット記述子のデキューを遅らせるために使用する機構として定義される。ＴＭＣ２０３においては、シェーピングは非作業保存加重均等化キューイングアルゴリズムを使用するスケジューラで実施される。このようなスケジューラは、トラヒック・ストリームのデキュー・サービス速度が、所与の時間中指定の最大速度を超えないように、能動トラヒック・ストリームへのサービスを遅らせるように構成することができる。すべてのシェーピングされたスケジューリングにより、短期間のデキュー速度はバースト的になりやすくなり、場合によっては、多数の能動スケジューラ入力の多重化により導入されたジッタおよび遅延により、必要な速度制限を超える恐れもある。
＜シェーピングのためのスケジューラの構成＞
シェーピングのための論理スケジューラ１４０１を構成するために多数の技術を使用することができる。これらすべての技術の基礎は、非作業保存スケジューラとして保証スケジューラ１４１３を構成し、過度スケジューラ１４１５に帯域幅を割り当てないことである。より詳細には、グループ化加重均等化キューイングアルゴリズムを保証スケジューラ１４１３で使用する場合には、
・各トラヒック・キュー入力は、トラヒック・キューが属する入力スケジューラ・キューの加重が指定する速度にシェーピングされる。
【０１０７】
・トラヒック・クラス・スケジューラが、可変長パケット・トラヒックのスケジューリングを行っている場合には、トラヒックを運んでいるトラヒック・キューを、トラヒック・クラス・スケジューラを加重均等化キューイングスケジューラとして構成し、各入力スケジューラ・キューを可変パケット長トラヒックを運ぶ１つのトラヒック・キューに制限することにより別々にシェーピングすることができる。
（二重漏洩バケットによるシェーピング）
Ｑ５内での二重漏洩バケット（ｄｕａｌ  ｌｅａｋｙ  ｂｕｃｋｅｔ）スケジューリングは、短期間のピーク速度およびある程度長い期間中の維持速度へのデキューを制限する方法での固定長トラヒックのスケジューリングに制限される。このスケジューリングは、グループ化モードで動作している非作業保存加重均等化キューイングトラヒック・クラス・スケジューラ５０３に接続している複数のペアのスケジューラ・キュー５２３を通してサポートされている。各組の偶数のスケジューラ・キューは、必要な一次速度でパケットを出力するように構成しなければならない。奇数のスケジューラ・キューは、保持速度で
パケットを出力するように構成しなければならない。トラヒック・キューをスケジューラ・キューに追加しなければならない場合には、保持速度漏洩バケット・アルゴリズムが、パケットを今送信すれば保持速度漏洩バケットに違反するのかどうかを判断するために使用される。保持速度漏洩バケットに対する状態情報は、管理２のフィールド８１６内のトラヒック・キューのパラメータ・ブロック４０３内に、トラヒック・キュー毎にセーブされる。このため、それに対する廃棄ポリシーが二重管理であるトラヒック・キュー５０４は、デュアル・シェーピング・アルゴリズムによりスケジュールされるスケジューラを指定することはできない。トラヒック・キュー５０４は、さらに、そのスケジューラ入力構成３０１１（図３０）内にデュアル・シェーピングを指定しなければならないし、また、入力構成に適当な定数を選択しなければならない。定数は、スケジューラ入力のどのセットが使用されているのか、パケット内で測定した漏洩バケット周期、および漏洩バケット限界を定義しなければならない。
【０１０８】
トラヒック・キュー２０４が最初に選択できるようになった場合、そのトラヒック・キューは、一次速度で構成されたスケジューラ・キュー上に置かれ、漏洩バケット状態情報は、トラヒック・キューの管理２のフィールド８１６にセーブされる。トラヒック・クラス・スケジューラは、トラヒック・キューのスケジュール状態フィールド８４５内に記憶されている記述子が、サービスを受けている場合には、スケジュール状態情報を返送する。記憶されている値は、トラヒック・クラス・スケジューラに返送され、次回、トラヒック・キューはスケジューラ・キューの先頭に位置することになる。スケジュール状態情報は、その速度に対する適当な時間まで、トラヒック・キューがサービスを受けるのを防止する動作可能時間を含む。
【０１０９】
トラヒック・キューが選択できるようになり、スケジューラ・キューに追加される度に、トラヒック・キューの先頭の記述子が表すパケットへのサービス提供が、保持速度漏洩バケットを違反するのかどうかを判断するために、管理２のフィールド内の漏洩バケット状態がチェックされる。速度に違反する場合には、パケットの記述子が、一次速度キュー上ではなく、保持速度スケジューラ・キュー上に置かれる。さらに、選択できる時間の値が、トラヒック・キューが、選択可能な時間になる前にサービスを受けるのを防止するトラヒック・キューのパラメータ・ブロック４０３内にセットされる。選択可能時間になり、トラヒック・キューがサービスを受けると、（依然として選択可能であるなら）トラヒック・キューが、保持速度キューの末尾に戻される。
＜セグメント分割および再組立て＞
システム２０１は、長いパケットにより送られたメッセージを、一連の短いパケットにより送られたメッセージに変換することができるし、一連の短いパケットにより送られたメッセージを、長いパケットにより送られたメッセージに変換することもできる。これらの変換の最初の変換はセグメント分割と呼ばれ、第２の変換は再組立てと呼ばれる。その一例が、一連のＡＴＭパケットのペイロードとして送られるＩＰパケットである。セグメント分割の場合、ＩＰパケットは、一連のＡＴＭパケットのペイロードにセグメント分割される。再組立ての場合には、上記一連のＡＴＭパケットのペイロードが、ＩＰパケットに再組み立てされる。
【０１１０】
システム２０１においては、セグメント分割および再組立ての両方が、ｃｐ記述子２１４上での動作を含む。セグメント分割の場合には、長いパケットに対する１つの記述子２１４が、短いパケットに対する一連の記述子になる。再組立ての場合には、短いパケットに対する一連の記述子２１４が、長いパケットに対する１つの記述子２１４になる。好ましい実施形態においては、これらの動作の両方が、ＴＭＣ２０３内のトラヒック・キューを含み、トラヒック・クラス・スケジューラ５０３内で行われる。セグメント分割のために使用されるトラヒック・クラス・スケジューラは、セグメント分割スケジューラと呼ばれ、再組立てのために使用されるトラヒック・クラス・スケジューラは、再組立てスケジ
ューラと呼ばれる。好ましい実施形態においては、ユーザは、セグメント分割スケジューラまたは再組立てスケジューラになるように、トラヒック・クラス・スケジューラを構成することができる。セグメント分割スケジューラまたは再組立てスケジューラを指定するように構成されるトラヒック・キューは、さらに、それぞれ、セグメント分割トラヒック・キュー、または再組立てトラヒック・キューと呼ばれる。セグメント分割の場合、セグメント分割の際に使用されるパラメータの値は、セグメント分割スケジューラが構成された場合に指定される。再組立ての場合には、再組立てトラヒック・キューが構成された場合に、再組立て動作のためのパラメータが指定される。
＜セグメント分割の詳細＞
トラヒック・キューのセグメント分割の場合には、セグメント分割トラヒック・キューの先頭に到着した１つのＴＭＣ記述子２１６が、一連のＱＭＵ記述子２５０８を生成させる。一連の各ＱＭＵ記述子は、エンキューされた記述子のコピー、およびプログレス・インジケータ（フィールド７１５）を含む。このプログレス・インジケータ（フィールド７１５）により、一連のＱＭＵ記述子に対応するパケットを送信しているＤＣＰ２０２内のチャネル・プロセッサは、一連のＱＭＵ記述子が生成される１つのＴＭＣ記述子が表すパケットのペイロードのどのバイトを、一連の各ＱＭＵ記述子が表すパケットを形成するために取り出す必要があるのかを決定することができるようになる。
【０１１１】
一連のＱＭＵ記述子の数、および各ＱＭＵ記述子内のプログレス・インジケータの値は、下記情報により決定される。
・トラヒック・キューのトラヒック・キュー・パラメータ・ブロック４０３内の情報フィールド８３６；再組立てトラヒック・キュー内においては、このフィールドの値は、トラヒック・キューの先頭に現在位置する記述子が表す各パケットの長さである。
【０１１２】
・セグメント分割スケジューラ内のセグメント・サイズ・フィールド；このフィールドの値は、シーケンス内の各パケットの全サイズである。
・セグメント分割スケジューラ内のペイロード・サイズ・フィールド；このフィールドの値は、シーケンスの各パケット内のペイロードの最大サイズである。
【０１１３】
・セグメント分割スケジューラ内のオーバーヘッド・サイズ・フィールド；このフィールドの値は、セグメント・サイズ・フィールドおよびペイロード・サイズ・フィールド内に指定されているサイズの間の違いである。
【０１１４】
すべてのサイズはバイト単位で測定される。
セグメント分割スケジューラが、１つの可変長パケットを表す記述子に対するエンキュー・メッセージから生成するデキュー・データ・メッセージの数は、下記により計算される。
【０１１５】
セグメントの数＝最大限度（（パケット長＋セグメント分割オーバーヘッド・サイズ）／セグメント・ペイロード・サイズ）
シーケンスに属する各デキュー・データ・メッセージ７０１は、セグメントのこの記述子が生成される前に、セグメント分割中のパケットのペイロードのどれだけが残ったのかを示すフィールド７１５内のパケット・バイトの残りの値を含む。
【０１１６】
一例を挙げて説明すると、セグメント分割トラヒック・キューの先頭の記述子は、１５７バイトの全長を有するパケットを表す。この記述子は一連の固定長パケットにセグメント分割される。各固定長パケットは、６０バイトの全長を有する。６０バイトの内の４８バイトはペイロードである。セグメント分割の結果は、６０バイト・パケットの下記のシーケンスである。
【０１１７】
【表２】
2005510893.tif 000004
この例の場合、セグメント分割スケジューラにより生成されたＱＭＵ記述子２５０８を受信しているＤＣＰ２０２内のチャネル・プロセッサは、適当なヘッダおよびトレーラを含む６０バイトのパケットを生成するようにプログラムされる。ＱＭＵ記述子からの残りの値、および元のパケットの長さ（ＱＭＵ記述子のｃｐ記述子２１４内に含まれている）を使用して、チャネル・プロセッサは、各６０バイトのパケットの４８バイトのペイロードに内蔵する元のパケットのペイロードのどのバイトをバッファ管理ユニット２２７から取り出さなければならないか、また、所与の６０バイトのパケットは、元のパケットのペイロード、中間パケットまたは最終パケットを含むシーケンス内の第１のパケットであるのかどうかを判断する。
【０１１８】
セグメント分割がトラヒック・クラス・スケジューラにより行われるという事実から分かると思うが、パケットを廃棄するという決定は、その宛先がセグメント分割トラヒック・キューであるかどうかによっては影響を受けない。スケジューリングの場合、個々の各デキュー・データ・メッセージ内の記述子は、別々にスケジュールされる。このため、パケットのシーケンス内のパケットに対するＱＭＵ記述子を含むデキュー・データ・メッセージを他のデキュー・データ・メッセージによりインタリーブすることができる。セグメント分割トラヒック・キューにより作成された記述子に対して使用されるスケジューリング機構は、他の記述子に対するものと同じものである。唯一の違いは、記述子のスケジューリングを行うために使用するパケット長の値が、ＴＭＣ記述子２１６内に指定されているサイズからではなく、セグメント・サイズ・フィールドから検索されることである。
＜再組立て＞
再組立ては、１つのパケットのペイロードを形成するための一連のパケットのペイロードの結合を含む。ＤＣＰ２０２は結合を行う。それ自身の上で結合を行う目的で、ＤＣＰ２０２は、一連の小さなパケットから大きなパケットを正しく再構成するために、状態の種々の断片を維持しなければならない。ＴＭＣ２０３は、大きなパケットに対して必要なパケットを表すＱＭＵ記述子が、仮想出力ポートを通して出力された他のＱＭＵ記述子によりインタリーブされないで、再組立てスケジューラに対する仮想出力ポート５２１を通して出力されるように、ＴＭＣ２０３からの一連のパケットに対するＱＭＵ記述子２５０８のデキューを編成することにより結合を行うためにＤＣＰ２０２内で必要な状態を最小にする。再組立て中の再組立てトラヒック・キューの役割は、シーケンスを提供することである。再組立てに関連する問題は、シーケンス内のすべての記述子を受信し、記述子を出力することができるようになるまで、記述子を記憶する際に結合されるＴＭＣ２０３内のリソースの量である。ＴＭＣ２０３で実施される再組立ては、この問題を２つの方法で処理する。
【０１１９】
・シーケンス内の記述子の内の１つが廃棄されたらすぐに、そのシーケンス内の受信したすべての記述子を廃棄するために、修正したＰＰＤ廃棄アルゴリズムを使用する方法。
・シーケンス内のパケットの流れが中断したことを判断するために、タイムアウト機構を使用する方法。中断が検出された場合、シーケンスに対する記述子は、修正したＰＰＤ
廃棄アルゴリズムにより廃棄される。
【０１２０】
ＴＭＣ２０３が、１つのインタリーブされていないバースト内のＱＭＵ記述子２５０８のシーケンスを、再組立てスケジューラのＶＯＰ２５１が指定する記述子キューに出力した場合、ＤＣＰ２０２内のチャネル・プロセッサは、一連のパケットのペイロードを１つの大きなパケットに結合するために、ＱＭＵ記述子２５０８を処理することができ、大きなパケットに対するＴＭＣ記述子２１６を、通常の方法でスケジューリングを行うためにエンキュー・データ・メッセージ６０１内のＴＭＣ２０３に提供することができる。ＴＭＣ２０３が、大きなパケットに対するＱＭＵ記述子２５０８を含むデキュー・データ・メッセージを出力すると、大きなパケットはＤＣＰ２０２内の他のチャネル・プロセッサにより出力される。このため、再組立ては、システム２０１内で行うことができるＴＭＣ２０３とＤＣＰ２０２間の複雑な相互作用の種々のタイプの好適例である。
【０１２１】
それにより再組立てが行われる種々のタイプのトラヒック内においては、そのペイロードが、大きなパケットに再組立てされる一連のパケットに属するパケットが、下記の特徴を有するトラヒックのストリーム内のその発信元から、ＤＣＰ２０２内に到着する。
・パケットは、ソースにより送られる順序で受信される。
・ソースは、異なる一連のパケットに属するパケットとインタリーブしない。
・異なるソースにより送られたシーケンスに属するパケットはインタリーブすることができる。
【０１２２】
シーケンス内の最後のパケットには、メッセージの終わりを含んでいるというマークが付けられる。
ＴＭＣ２０３は、ＴＭＣ２０３内で再組立てされる一連のパケットの各ソースに対応するトラヒック・キューが存在するように、シーケンスを含むトラヒックのストリームを処理する受信プロセッサが、それらがＴＭＣ２０３に送るＴＭＣ記述子２１６内のソースに対応するトラヒック・キューを指定するようにすでに構成されている。このため、所与の発信元からシーケンスに対するＴＭＣ記述子２１６を受信しているトラヒック・キューは、それらがＤＣＰ２０２内で受信された順序でＴＭＣ記述子を受信する。しかし、他の発信元からの任意のインタリーブされたＴＭＣ記述子は含まない。チャネル・プロセッサは、シーケンス内の最後のパケットに対するＴＭＣ記述子に、そのパケットがＥＯＭ（メッセージの終わり）パケットであることを示すマークを付ける。このため、再組立てされるパケットに対する記述子を受信するトラヒック・キューは、少なくとも１つのＴＭＣ記述子のインタリーブされていないシーケンスを含み、記述子の各シーケンスは、トラヒック・キューが対応する発信元からの一連のパケットに対応し、ＤＣＰ２０２で受信し、まだ再組立てしていない一連のパケットを表す。パケットの最後のシーケンスに属するパケットが、すべてＤＣＰ２０２に到着していない場合には、記述子の最後のシーケンスは、そのパケットがＥＯＭパケットであることを示す記述子を含んでいない。
【０１２３】
トラヒック・キューの先頭に位置するＴＭＣ記述子２１６が、ＥＯＭパケットを表しているというマークが付けられているＴＭＣ記述子２１６をまだ含んでいないＴＭＣ記述子２１６のシーケンスに属している場合には、再組立てトラヒック・キュー２０４をスケジュールのために選択することはできない。他の任意の選択することができないトラヒック・キューのように、選択できない再組立てトラヒック・キューは、サービスを受ける場合には、スケジューラ・キューから除去される。ＥＯＭ記述子が到着すると、トラヒック・キュープロセッサ３０５は、再び、トラヒック・キューをスケジューラ・キューの中に入れる。トラヒック・キュープロセッサ３０５が、シーケンスに対するＥＯＭ記述子が到着したかどうかを判断するために使用する状態情報は、トラヒック・キューのパラメータ・ブロック４０３のフィールド８６１内に含まれている。
【０１２４】
トラヒック・キュー２０４がスケジューラ・キューの先頭に位置しており、スケジューラ階層５０１がスケジューラ・キューを選択した場合には、トラヒック・キューの先頭で一連の記述子の出力が開始する。この時点で、スケジューラ・キューにより再組立てトラヒック・クラス・スケジューラ２９３から仮想出力ポートまでスケジューラ階層を通る経路２０９内のスケジューラは、同じ仮想出力ポートを使用する他のスケジューラ・キューのスケジューリングが行われないようにロックされ、またトラヒック・キューは、シーケンス内のすべての記述子が出力されるまでスケジューラ・キューの先頭にそのまま残る。マークされたＥＯＭである記述子が出力されると、ロックされたスケジューラのロックが外され、トラヒック・キューがスケジューラ・キューの先頭から除去される。このため、トラヒック・キューの先頭の一連の記述子は、一連の記述子が対応する一連のパケットがＤＣＰ２０２内で受信された順序で、そのトラヒック・キュー２０４から経路の仮想出力ポートに対応するＱＭＵ２１７内の記述子キュー２１３に出力される。再組立てスケジューラに属するトラヒック・キュー内でのエンキューのためのＴＭＣ記述子２１６は、他のトラヒック・キュー内のエンキューのための記述子と同じ方法で廃棄することができる。好ましい実施形態で使用される廃棄モードは、ＭＰＰＤモードである。
【０１２５】
今説明した再組立て技術に関する問題は、形の崩れたメッセージ、すなわち、ＥＯＭマーカーを有さないメッセージから記述子を検出するという問題である。このようなメッセージを表す一連のＴＭＣ記述子は、マークのついた最後の記述子を決して受信しないので、シーケンス内の最初のＴＭＣ記述子がトラヒック・キューの先頭に到着すると、トラヒック・キューは選択できなくなり、引き続き選択できない状態が続く。トラヒック・キュープロセッサ３０５は、形の崩れたシーケンスの位置を発見し、そのリソースを解放するのを助けることができる、トラヒック・キューの動作不能状態を追跡するための一般的な方法により、この状況を検出する。一般的な動作不能状態の追跡は、「クロック・スイープ」方法の実施により行われる。周期的に、トラヒック・キューのパラメータ・ブロック４０３のフィールド８６９に、１回目のスイープを行ったというマークが付けられる。トラヒック・キュー上の任意のエンキュー動作により、「１回スイープ」という表示がクリアされる。「クロック・スイープ」が、次回のクロック・スイープの際にトラヒック・キューに渡されると、フィールド８６９は、最後のスイープ以来エンキュー動作によりクリアされた場合には、１回スイープ済みと再度マークが付けられるか、クリアされたことがない場合には、２回またはそれ以上スイープされたとマークされる。２回またはそれ以上スイープ済みとマークされる任意のトラヒック・キューは、少なくともそのスイープの周期の間アイドル状態でいなければならない。
【０１２６】
再組立てトラヒック・キューの場合、一般的クロック・スイープは、トラヒック・キューに、フィールド８６９が２回スイープされたとマークされた後で、進行中の再組立てを「タイムアウト」させるために使用される。タイムアウトが発生した場合、フィールド８６１は、トラヒック・キューが動作不能になり、トラヒック・キューが、能動スケジューリング・キュー内に入れられることを示すようにセットされる。形の崩れたメッセージに対する一連の記述子は、すでに説明したように、ＴＭＣ２０３からデキューされるが、形の崩れたシーケンスの最後のパケットがデキューされると、フィールド８６１が、トラヒック・キューが動作不能になることを示すためにセットされたために、デキュー・スケジューラ３０３が、シーケンスが早期に終了したこと、およびトラヒック・キューが動作不能になったことを示す特殊なＥＯＭインジケータで最後のパケットにマークを付ける。再組立てされるペイロードに対する記述子を受信しているＤＣＰ２０２内のチャネル・プロセッサが、形の崩れたメッセージを示すＥＯＭを含む記述子を受信すると、チャネル・プロセッサは記述子に対応するペイロードを廃棄する。再組立てのためにトラヒック・キュー毎の状態を維持しなければならないので、再組立てトラヒック・クラス・スケジューラは、スケジューリングのためにトラヒック・キュー毎の状態を必要とするスケジューリング・アルゴリズムを使用することができない。好ましい実施形態においては、フレームを
ベースとする不足ラウンドロビンおよびグループ化加重均等化キューイングアルゴリズムは、スケジューリングのためにトラヒック・キュー毎の状態を必要とする。
＜スケジューラの実施の詳細＞
好ましい実施形態においては、スケジューラは、ＴＭＣ  ＩＣ１５０３内のスケジューラ・メモリ１５１５で実施され、メモリ１５１５内にスケジューラの状態をセットすることにより構成される。各スケジューラは、スケジューラ階層５０１内のレベルおよびレベル内のその数により参照され、スケジューラへの所与の入力は、スケジューラのレベル、レベル内の数および入力の数により参照される。好ましい実施形態においては、各レベルは、そのレベルにおけるスケジューラ入力を指定するために使用することができる値の範囲を有し、スケジューラの数は、範囲内のオフセットであり、スケジューラに属する入力は、オフセットと（スケジューラの入力の数から１を引いたもの）の間の入力である。入力は、１つのスケジューラだけに属することができる。好ましい実施形態においては、１つのレベル０のスケジューラは、３２の入力を使用することができ、レベル１のスケジューラは５１２の入力を使用することができ、レベル２のスケジューラは４Ｋの入力を使用することができ、レベル３のスケジューラは８Ｋの入力を使用することができる。すでに説明したように、スケジューラ階層のリーフは、常にトラヒック・クラス・スケジューラ５０３であり、内部ノード内部スケジューラ５０９である。
＜トラヒック・クラス・スケジューラ５０３の詳細：図２１＞
図２１は、階層５０１内の特定のトラヒック・クラス・スケジューラ５０３（ｉ）の位置、および好ましい実施形態のその行動を定義する情報である。トラヒック・クラス・スケジューラ５０３（ｉ）は、階層内のリーフであるので、その一組の入力スケジューラ・キューは、そのトラヒック・キュー２０４が、トラヒック・クラス・スケジューラ５０３（ｉ）を指定する能動スケジューラ・キュー５２３の内の一組５３１である。その各入力２１０１に対して、トラヒック・クラス・スケジューラ５０３（ｉ）は、入力２１０１に関連づけられたスケジューラ・キュー５２３に対する入力状態２１０３を維持する。所与の入力２１０１（ｉ）に対する入力状態２１０３（ｉ）は、入力がバックログされているかどうか（フィールド２１０５）、すなわち、入力の関連するスケジューラ・キュー５２３（ｊ）が能動状態にあるかどうか、アルゴリズム依存入力状態２１０６、および入力２１０１に関連づけられたスケジューラ・キュー５２３内のヘッド・トラヒック・キュー、および末尾トラヒック・キューの識別子２１０７および２１０９を含む。アルゴリズム依存入力状態２１０６は、スケジューラが使用するスケジューリング・アルゴリズムにより変化する入力スケジューラ・キューに関連する状態である。
【０１２７】
階層５０１内のトラヒック・クラス・スケジューラ５０３（ｉ）の位置は、内部スケジューラ５０９およびスケジューラ５０３（ｉ）が、スケジューラ５０３（ｉ）が選択したバックログされたスケジューラ・キュー５２３を出力するその入力を定義する接続状態２１２１により指定される。この内部スケジューラは、スケジューラ５０３（ｉ）の親と呼ばれる。接続状態２１２１は、親が属する階層５０１内のレベル２１２３、そのレベル内のスケジューラの数２１２５、およびスケジューラ５０３（ｉ）がそれが選択するスケジューラ・キューを出力している親の入力２１２７を含む。
【０１２８】
トラヒック・クラス・スケジューラ５０３（ｉ）が、その入力に関連づけられたスケジューラ・キューのスケジューリングを行う方法は、スケジューラ状態２１１１により決まる。スケジューラ・タイプ２１１３は、スケジューラ・タイプを指定し、したがって、トラヒック・クラス・スケジューラが使用するアルゴリズム、およびそれがセグメント分割スケジューラまたは再組立てスケジューラかどうかを指定する。入力２１１５の数は、トラヒック・クラス・スケジューラに属する入力２１０１の数を指定する。ロックされているかどうか。２１１７は、スケジューラ５０３（ｉ）をロックするために使用され、一方、階層５０１を通るその経路がスケジューラ５０３（ｉ）として同じ仮想出力ポート５２１を含む再組立てスケジューラ５０３は、一連の記述子を出力している。アルゴリズム依
存状態２１１９の内容は、２１１３で指定されるスケジューラ・タイプにより異なり、そのスケジューリング・アルゴリズムを実行するために必要なスケジューラ・タイプおよび状態を構成するために必要な情報を含む。
＜内部スケジューラ５０９の詳細：図２２＞
図２２は、内部スケジューラ５０９（ｉ）の詳細なブロック図である。接続状態２１２１およびスケジューラ状態２１１１は、内部スケジューラ５０９（ｉ）に対するものも、トラヒック・クラス・スケジューラ５０３に対するものも同じである。内部スケジューラ５０９（ｉ）とトラヒック・クラス・スケジューラ５０３の間の機能的な違いは、内部スケジューラ５０９（ｉ）は、スケジューラ階層５０１の内部ノードであり、したがって、内部スケジューラ５０９（ｉ）は、それに属するものが、階層５０１内の下位のスケジューラ５０９（ｉ）であるスケジューラの動作により決まるスケジューラ・キューの内の一組５３４のスケジューリングを行うことである。この機能的な違いは、スケジューラ５０９（ｉ）が、入力に現在バウンドしているスケジューラ・キュー５２３の位置を発見し、そのスケジューラ・キューが能動状態であるばかりでなく、スケジュール可能であるかどうかを判断することができるようにする情報を含む入力状態２２０５に反映される。
【０１２９】
参照番号２２０５（０）は、入力２２０３（０）に対する入力状態２２０５の詳細を示す。フィールド２１０５は、選択したスケジューラ・キュー２２０１（ｉ）が能動状態にあり、スケジューリングを行うことができるかどうかを示す。フィールド２１０６は、図２１で説明したように、アルゴリズム依存入力状態を含む。フィールド２２０７〜２２０９は、スケジューラ・キューのトラヒック・クラス・スケジューラ５０３から伝搬する、スケジューラ・キュー２２０１（ｉ）に関する情報を含む。ソース・スケジューラ・フィールド２２０７およびソース・スケジューラ入力フィールド２２０９により、スケジューラ・キューに対するヘッドおよび末尾ポインタの位置を知ることができる。伝搬した選択可能な時間２２１１は、スケジューラ・キュー２２０１が、非作業保存スケジューリング・アルゴリズム内でスケジュールされるために次に選択可能になる時点を示す。
【０１３０】
フィールド２２１３〜２２１７は、スケジューラ５０９（ｉ）とスケジューラ・キュー２２０１（ｉ）のソースであるトラヒック・クラス・スケジューラ５０３の間の経路上に位置する任意の仮想出力ポート５２１（ｋ）に関する情報を含む。フィールド２２１３は、そのような仮想出力ポートが存在するかどうかを示す。そのような仮想出力ポートが存在する場合には、フィールド２２１５は、仮想出力ポート５２１（ｋ）に対応する記述子キュー２１３が、さらに記述子を含むことができるかどうか、すなわち、スケジューラ・キュー２２０１（ｉ）のスケジューリングを行うことができるかどうかを示す。ＶＯＰ指定子フィールド２２１７は、仮想出力ポートに対する識別子を含む。ＱＭＵ記述子２５０８がＴＭＣ２０３から出力されると、レベル０のスケジューラ５０９内のこのフィールドは、ＱＭＵ記述子２５０８のフィールド７０７内に指定されているＶＯＰ識別子のソースである。
＜仮想出力ポートの詳細：図２７＞
図２７は、仮想出力ポート５２１（ｉ）を実施するために、好ましい実施形態で使用するデータ構造である。フィールド２７０１は、仮想出力ポート５２１（ｉ）が使用することができる現在のクレジット、すなわち、仮想出力ポート５２１（ｉ）に対応する記述子キュー２１３に現在追加することができる記述子の数を含む。フィールド２７０１は、デキュー／デキュー肯定応答ループの往復の待ち時間がある場合に、仮想出力ポートの全帯域幅を確実に維持することができるように計算される最大デキュー・クレジットにより構成される。ＴＭＣ２０３が、スケジューラ階層５０１を通るその経路５２９が仮想出力ポート５２１（ｉ）を含むスケジューラ・キューに属するトラヒック・キューから記述子を出力する場合は常に、フィールド２７０１の値は減少する。ＱＭＵ２１７が、ＴＭＣ２０３に、仮想出力ポート５２１（ｉ）に対応する記述子キュー２１３から記述子が除去されたことを示すデキュー・データ・メッセージ肯定応答１９２１を送信する場合は常に、フ
ィールド２７０１の値は増大する。これらのメッセージを送る機構については以下に説明する。現在のクレジット・フィールド２７０１の値がゼロである場合には、その経路５２９が仮想出力ポート５２１（ｉ）を通るスケジューラ・キューのどれに対してもスケジューリングを行うことができない。フィールド２７０３は、仮想出力ポート２７０３の識別子である。好ましい実施形態においては、識別子は、単に、仮想出力ポートに対応する記述子キュー２１３の識別子である。フィールド２７０１および２７０３は、図２２に示すように、スケジューラ階層５０１内の仮想出力ポート５２１（ｉ）上に位置するスケジューラ５０９に送られる。２７０５で一緒にグループ分けされたフィールドは、スケジューラ階層５０１内の仮想出力ポート５２１（ｉ）の位置を指定する。この位置は、特定のスケジューラ５０９（ｊ）への入力を指定することにより指定される。スケジューラ５０９（ｊ）は、階層（フィールド２７０７）内のそのレベルおよびレベル（フィールド２７０９）内のその位置により指定され、フィールド２７１１は、スケジューラ５０９（ｊ）への入力を指定する。
＜スケジューラ階層５０１の動作の詳細＞
スケジューラ階層５０１は、スケジューラ階層５０１の状態を変更するスケジューラ・イベントに応じて、スケジューラ・キュー５２３のスケジューリングを行う。このようなイベントが発生する度に、デキュー・スケジューラ３０３は、最初、そのイベントが必要とする階層５０１の状態を変更し、次に、階層５０１の状態の変化により影響を受けた階層５０１の一部内で、スケジューラ・キュー５２３のスケジューリングを行う。３つのタイプのスケジューラ・イベントが存在する。
【０１３１】
・スケジューラ・キューエンキュー・イベント。スケジューラ・キューエンキュー・イベントは、スケジューラ・キューの先頭に位置するトラヒック・キュー２０４内で、またはヘッド・トラヒック・キューの先頭のＴＭＣ記述子２１６内で変化が起きた場合に発生する。
【０１３２】
・スケジューラ・キューデキュー・イベント。スケジューラ・キューデキュー・イベントは、スケジューラ階層５０１がデキューに対するスケジューラ・キュー５２３を選択した場合に常に発生する。
【０１３３】
・仮想出力ポート・イネーブル・イベント。仮想出力ポート・イネーブル・イベントは、ＤＣＰ２０２からのデキュー肯定応答メッセージ１９２１の受信により、仮想出力ポートのデキュー・クレジットがゼロからゼロでない状態に移行した場合に発生する。
【０１３４】
スケジューラ・イベントが発生すると、スケジューラおよび仮想出力ポートの状態の値が変化し、イベントによる変更が値で行われた場合、イベントにより影響を受けた経路５２９内のスケジューラは、スケジューリングを開始する。このスケジューリングは、経路のトラヒック・クラス・スケジューラ５２３から開始し、レベル０のスケジューラにおいて終了する。
＜スケジューラ・イベントによる状態変化＞
スケジューラ・イベントにより影響を受けた状態について、引き続きさらに詳細に説明するが、スケジューラ・キューエンキュー・イベントは、空でなくなりそのため能動状態になっているスケジューラ・キューにより発生する場合もあるし、新しいトラヒック・キューを入力スケジューラ・キューのヘッドにするスケジューラ・キューデキュー動作により発生する場合もあるし、または入力スケジューラ・キューの先頭に位置するトラヒック・キューの先頭になる新しい記述子により発生する場合もある。後者の場合、新しい記述子をデキューすることができず、そのため、トラヒック・キューを選択することができなくなった場合には、スケジューラ・キューエンキュー・イベントが、スケジューラ・キューから除去される選択不能なトラヒック・キューになる。それにより、今度は、スケジューラ・キューが空になり、そのため非能動状態になる。スケジューラ・キューエンキュー
・イベントのために、スケジューラ・キューが能動状態または非能動状態になると、当然ながら、バックログされたか？２１０５の値は変化する。
【０１３５】
デキュー・イベントは、トラヒック・キューを空にする場合があり、空になると今度はスケジューラ・キューは非能動状態になる。そうすると、今度は、そこから記述子がデキューされたスケジューラ・キューに対する入力状態２１０３のトラヒック・クラス・スケジューラ５０３のバックログしたか？フィールド２１０５が更新される。デキュー・イベントは、さらに、スケジューラ階層５０１を通るスケジューラ・キューの経路５２９沿いの仮想出力ポートの後のスケジューラ内の仮想出力ポート・イネーブル・フィールド２２１５を更新する。仮想出力ポート・イネーブル・イベントは、また、最後に、スケジューラ階層５０１を通るスケジューラ・キューの経路５２９沿いの仮想出力ポートの後の、スケジューラ内の仮想出力ポート・イネーブル・フィールド２２１５を更新する。
＜スケジューラ・イベントによるスケジューリング＞
イベントにより要求される階層５０１内の状態の更新が行われた後で、スケジューリングが、その状態がイベントにより影響を受け、レベル０のスケジューラを通る最も低いレベルで影響を受けたスケジューラから、階層を通して経路５２９上のスケジューラに続いている、階層５０１内の最も低いレベルのスケジューラから開始する。このため、スケジューラ・キューエンキューおよびデキュー・イベントの場合には、スケジューリングは、イベントにより影響を受けたトラヒック・クラス・スケジューラ５０３により開始し、仮想出力ポート・イネーブル・イベントの場合には、スケジューリングは、その入力をその状態がイベントにより影響を受ける仮想出力ポートにより制御されるスケジューラから開始する。経路上の各スケジューラにおいて、スケジューラの入力により定義される一組のスケジューラ・キューからのスケジューラ・キュー５２３の選択が、下記の規則により行われる。
【０１３６】
・イベントによる影響を受けた最も低いレベルのスケジューラが、トラヒック・クラス・スケジューラ５０３である場合には、入力スケジューラ・キューがバックログされていない限り、フィールド２１０５で示すように、トラヒック・クラス・スケジューラにより入力スケジューラ・キューを選択することはできない。
【０１３７】
・スケジューラが、仮想出力ポートにより制御される入力スケジューラ・キューを有する内部スケジューラ５０９である場合には、仮想出力ポート・イネーブル状態２２１５が入力スケジューラ・キューがスケジュール可能であると示していない限り、スケジューラにより入力スケジューラ・キューを選択することはできない。
【０１３８】
・スケジューラが内部スケジューラ５０９であり、入力スケジューラ・キューが将来のものではない送られた選択可能な時間フィールド２２１１内にある値を有する場合には、スケジュール可能な入力スケジューラ・キューの間での選択は、スケジューラの構成されたスケジューリング・アルゴリズムにより制御される（例えば、厳格な優先順位スケジューリング・アルゴリズムは、値の最も低い能動状態のスケジューラ入力を選択する）。
【０１３９】
・すべての入力スケジューラ・キューが、将来のものである時間をフィールド２２１１内に持っている場合には、最も近い選択可能な時間を有するスケジュール可能な入力スケジューラ・キューが選択される。
【０１４０】
ＤＣＰ２０２へのデキューのために選択したスケジューラ・キューは、レベル０のスケジューラが選択した入力２２０３に関連づけられた入力状態２２０５内の送られたスケジューラ／入力状態２２０７および２２０９により識別され、選択したスケジューラ・キューが通った経路に対する仮想出力ポート５２１は、入力２２０３に関連づけられた入力状態２２０５内の送られた仮想出力ポート指定子２２１７により識別される。
＜スケジューラ構成の詳細：図２３、図２４、図２９、図３６および図３７＞
図２３および図３６は、トラヒック・クラス・スケジューラ５０３、および内部スケジューラ５０９両方を構成するために使用されるスケジューラ構成データ２３０１を示す。いくつかのタイプのトラヒック・クラス・スケジューラの構成は、図２９に示す追加のトラヒック・クラス・スケジューラ構成データ２９０１を必要とする。指定子２３０１内に含まれているデータは、スケジューラ用のスケジューラ構成指定子４２５を構成するために使用される。上記と同様に、これら図面はテーブルであるが、テーブルの各行は、構成データ２３０１または２９０１内のフィールドを示す。フィールドの使用方法は行１００６内に指定してある。図２３のほとんどの部分は説明を必要としない。フィールド２３０３および２３０５は、スケジューラのレベルおよびレベル内の位置を指定し、これによって構成中のスケジューラを識別する。フィールド２３０７〜２３１１は、その親へのスケジューラの接続方法を定義する。フィールド２３１３〜２３１７は、論理スケジューラ１４０１に関してスケジューラのタイプを定義する。フィールド２３１９はスケジューラの入力に対する入力数を定義する。この数はスケジューラのタイプにより変化する。入力構成データは、図２４のスケジューラの各入力に関連する。
【０１４１】
図２９は、トラヒック・クラス・スケジューラ構成データ２９０１である。フィールド２９０３は、定義中のトラヒック・クラス・スケジューラ５０３に関連づけられた廃棄トラヒック・キューに対するｔｑｉｄ４２３である。グループ化スケジューラ・タイプ・フラグ２９０６は、スケジューラがグループ化モードで動作しているかどうかを示す。スケジューラ・タイプ・フィールド２９０７は、スケジューラがＦＢＤＲＲスケジューラであるかどうかを示す。デュアル・シェーパ・フラグ２９０９は、すべてのスケジューラの入力がデュアル・シェーピング・モードで動作していることを示す。タイプ・フィールド２９１１は、スケジューラがスケジューリング中のトラヒック・キューのタイプを指定する。このフィールドは、トラヒック・キュー２０４が可変長または固定長のパケットを有するかどうかを示し、固定長のパケットである場合には、スケジューラがトラヒック・キューでパケットをセグメント分割するのかまたは再組立てするのかを示す。タイプ・フィールド２９１１が、トラヒック・キューをセグメント分割することを示している場合には、フィールド２９１３〜２９１７は、セグメント分割の際に使用するパラメータを指定する。
【０１４２】
図２４および図３７は、スケジューラの入力を初期化するために使用されるスケジューラ入力初期化データ２４０１を示す。このデータは、また、スケジューラ構成指定子４２５の一部でもある。この場合も、これらの図はテーブルであり、各行は入力初期化データ内のフィールドを示す。フィールド２４０７および２４０９は入力が属するスケジューラを指定し、一方、フィールド２４１１は指定のスケジューラで初期化中の入力の数を示す。残りのフィールドの内のどれを使用するかは、スケジューラのタイプにより異なる。フィールド２４０３および２４０５は、加重均等化キューイングを使用するスケジューラ・タイプ内のバイト・サービス間隔を指定する。フィールド２４１３は、保証スケジューラ１４１３および過度スケジューラ１４１５への入力の接続方法を指定するために、図１４のタイプの保証−過度選択スケジューラで使用される。
【０１４３】
図３０、図４０および図４１は、トラヒック・キューを、トラヒック・クラス・スケジューラ５０３に対する入力スケジューラ・キュー５２３に関連づけるために使用するデータ３００１を示す。所与のトラヒック・キューに対して、このデータは、トラヒック・キューのパラメータ・ブロック４０３内のフィールド８３１により参照される。データの内容は、トラヒック・クラス・スケジューラが使用するスケジューリング・アルゴリズムにより異なる。３００３に示す内容は、トラヒック・キューが、トラヒック・クラス・スケジューラに属する１つの入力スケジューラ・キューに割り当てられたままになっているすべてのスケジューリング・アルゴリズムに対して使用される。データは、アルゴリズムが
固定スケジューラ・キュー内およびトラヒック・クラス・スケジューラ内の固定入力スケジューラ・キューの数を含むフィールド３００９内にトラヒック・キューを保持していることを示す００にセットされるタイプ・フラグ３００５からなる。データ３００３を使用するトラヒック・クラス・スケジューラの例としては、ラウンドロビン・スケジューラおよび厳格な優先順位スケジューラ等がある。
【０１４４】
データ３０１１は、トラヒック・キューが、ペアの入力スケジューラ・キューの部材間で移動するデュアル・シェーピング漏洩バケット・スケジューラに対して使用される。タイプ・フィールドの値は、このタイプのスケジューリングを指定し、フィールド３０１５および３０１７は、漏洩バケットスケジューリング用のパラメータを含み、フィールド３０１９は、ペアの偶数の入力スケジューラ・キューを指定する。データ３０２１は、ＦＢＤＲＲスケジューラのために使用される。タイプ・フィールド３０２３は、値「１０」と共にこれを示す。フィールド３０２５は、トラヒック・キューに対する最小割合パラメータである。フィールド３０２７は、トラヒック・キューの最大割合パラメータである。当然ながら、多くの異なるトラヒック・キュー２０４もデータ３０２１を共有することができる。
＜例：図２６：フレームをベースとする不足ラウンドロビン・スケジューリング・アルゴリズムを使用するスケジューラの構成および動作＞
図２６は、フレームをベースとする不足ラウンドロビン・スケジューラ２６０１として構成されたトラヒック・クラス・スケジューラ５０３の詳細な構成である。すでに説明したように、ＦＢＤＲＲアルゴリズムは、パケット・サイズによりスケジューリングを行い、そのためトラヒックが、ＴＣＰプロトコルの通常のパケットのような可変サイズのパケットからなる場合には、帯域幅を効果的に割当てる。ＦＢＤＲＲのこのバージョンの新規な特徴は、ＴＣＰプロトコル内の多くのメッセージが、比較的短い肯定応答メッセージであるという事実のために、将来に備える方法である。
【０１４５】
スケジューラ２６０１においては、各入力に対する接続状態２１２１および入力状態２１０３は、すでに説明した通りである。スケジューラ・タイプ・フィールド２１１３は、値ｂ１１１を有し、不足ラウンドロビン・スケジューリング・アルゴリズムを示し、入力２１１５の数は値４であり、その内の３つの入力２１０３（０…２）は、実際にそれらに関連づけられたスケジューラ・キュー５２３を有する。好ましい実施形態で使用されるＦＢＤＲＲアルゴリズムの実施に際しては、この場合、スケジューラ・キューの内の２つ、すなわち、入力２１０１（０）および２１０１（２）に取り付けられているスケジューラ・キュー２６０７および２６１１は、それぞれ、現在のスケジューラ・キュー２６０７および次のスケジューラ・キュー２６１１として交替する。現在のスケジューラ・キューが空である場合には、このスケジューラ・キューは次のスケジューラ・キューになり、次のスケジューラ・キューは現在のスケジューラ・キューになる。第３のスケジューラ・キューは、高優先順位キュー２６０９である。アルゴリズムに依存する状態２１１９は、３つの各スケジューラ・キューに対する状態の１つの項目を含む。項目２６０１は、キュー２６０７および２６１１のどちらが現在のスケジューラ・キューであるかを示す。項目２６０５は、どれが次のスケジューラ・キューであるかを示す。項目２６０３は、どのスケジューラ・キューが高優先順位キュー２６０９であるのかを示す。ＦＢＤＲＲアルゴリズムのところで説明したように、トラヒック・キューをどのスケジューラ・キュー内に置くかは、トラヒック・キューの最大割合パラメータ、および最小割合パラメータ、およびその不足カウンタ２６１５およびＢｙｔｅｓＳｅｒｖｅｄＴｈｉｓＲｏｕｎｄ（ＢＳＴＲ）カウンタ２６１６により決まる。パラメータの値は、参照番号２６１３で示すように、トラヒック・キューのパラメータ・ブロック内のフィールド８３１によりポイントされている入力データ３０２１（図３０）内に含まれている。カウンタの値はフィールド８４５に記憶される。
【０１４６】
各トラヒック・キューの一番下の表現は、最大割合２６１５、最小割合２６１３、不足カウンタ２６１５およびＢＳＴＲカウンタ２６１６の値が、トラヒック・キューが位置するどのスケジューラ・キューにどのように関連しているのかを示す。アルゴリズムのところで説明したように、記述子が、現在のスケジューラ・キュー２６０７、または高優先順位スケジューラ・キュー２６０９の先頭に位置するトラヒック・キュー２０４から除去されると、トラヒック・キューの不足カウンタ２６１５は、記述子のパケットの長さだけ減少し、そのＢＳＴＲカウンタ２６１６はその長さだけ増大する。トラヒック・キューが、高優先順位スケジューラ・キュー２６０９から現在のスケジューラ・キュー２６０７に移動すると、ＢＳＴＲ２６１６はゼロにセットされる。トラヒック・キューが、高優先順位スケジューラ・キュー２６０９または現在のスケジューラ・キュー２６０７から次のスケジューラ・キュー２６１１に移動すると、トラヒック・キューの不足カウンタ２６１５は最大割合に不足カウンタの値を加算したものにセットされ、そのＢＳＴＲカウンタ２６１６はゼロにセットされる。現在のスケジューラ・キュー２６０７または高優先順位スケジューラ・キュー２６０９の先頭に位置するトラヒック・キューが、選択できないかまたは選択できなくなった場合には、そのトラヒック・キューはスケジューラ・キューから除去される。トラヒック・キューが選択できるようになると、そのトラヒック・キューは次のスケジューラ・キュー２６１１内に入れられる。
＜ＴＭＣ２０３の物理実施：図１５〜図２０＞
＜物理実施の概要：図１５＞
図１５は、システム２０１の物理実施１５０１のブロック図である。システム２０１のところで説明したように、システム２０１は、２つの主要な構成部品、すなわち、ＤＣＰ２０２およびＴＭＣ２０３を含む。この図により詳細に示すように、ＴＭＣ２０３は、スケジューラ階層５０１が構成されているスケジューラ・メモリ１５１５、およびＴＭＣメモリ３０７の残りを実施する外部メモリ１５０９、１５１１および１５１３を含むＴＭＣメモリ３０７の一部と共に、エンキュー・プロセッサ３０１、デキュー・スケジューラ３０３、およびトラヒック・キュープロセッサ３０５が実施されているＴＭＣ  ＩＣ１５０３を含む。外部メモリ１５０９は、トラヒック・キュー・パラメータ・ブロック４０３およびトラヒック・キューに対する関連データ構造を記憶するＺＢＴ  ＳＲＡＭメモリである。外部メモリ１５１３は、トラヒック・キューの記述子キュー４１９内の記述子を記憶するＤＤＲＳＤＲＡＭメモリである。外部メモリ１５１１は、トラヒック・キュー２０４内でＴＭＣ記述子２１６をリンクし、トラヒック・キューをスケジューラ・キュー内にリンクするために使用されるデータを記憶するＺＢＴ  ＳＲＡＭメモリである。以下にさらに詳細に説明するように、ＴＭＣ  ＩＣ１５０３は、外部メモリの容量を変更するように構成される。
【０１４７】
ＴＭＣ  ＩＣ１５０３は、ＴＭＩバス１５０７を通してＤＣＰ２０２からエンキュー・データ・メッセージ６０１を受信し、ＤＣＰ２０２にデキュー・データ・メッセージ７０１を提供する。ＤＣＰ２０２およびＴＭＣ２０３の両方は、ＴＭＣメモリ３０７に書き込むために、ＰＣＩバス１５０５により構成することができる。内部および外部ＴＭＣメモリ３０７はＰＣＩバス１５０５を通して読み出したり書き込んだりすることができる。ＰＣＩバス１５０５は、標準ＰＣＩバス・プロトコルを使用する。ＴＭＩバス１５０７で使用されるプロトコルについては、以下にさらに詳細に説明する。
＜ＴＭＣ  ＩＣ１５０３の詳細：図１６＞
図１６は、ＴＭＣ  ＩＣ１５０３の内部の詳細図である。ＴＭＣ  ＩＣ１５０３はメモリも内蔵しているが、図には示していない。ＴＭＣ  ＩＣ１５０３は、ＰＣＩバス１５０５へのインタフェース１６０１、ＴＭＩバス１５０７へのインタフェース１６０３、パラメータ・メモリ１５０９用のコントローラ１６０５、リンク・メモリ１５１１用のコントローラ１６０７、および記述子メモリ１５１３用のコントローラ１６０９を含む。ＴＭＣ
ＩＣ１５０３は、また、デキュー・スケジューラ３０３、エンキュー・プロセッサ３０１、およびトラヒック・キュープロセッサ３０５を含む。構成要素をリンクしている矢印
は、これら構成要素間のデータの流れを示す。このため、ＴＭＩバス・インタフェース１６０３がエンキュー・データ・メッセージ６０１を受信すると、このインタフェースは、エンキュー・データ・メッセージ６０１をエンキュー・プロセッサ３０１に出力するが、このエンキュー・プロセッサ３０１は、記述子メモリ１５１３内に記憶するために記述子メモリ・コントローラ１６０９に、少なくともｃｐ記述子２１４、ＴＭＣ記述子２１６の残りの内容、記憶したｃｐ記述子２１４へのリンク、およびトラヒック・キュープロセッサ３０５へのトラヒック・キューの使用を提供する。トラヒック・キュープロセッサ３０５は、記述子を指定のトラヒック・キューにリンクし、またはトラヒック・キューを廃棄するために、情報、リンク・メモリ・コントローラおよびリンク・メモリ１５１１を使用する。これが行われている間に、デキュー・スケジューラ３０３は、ＴＭＣ  ＩＣ１５０３のメモリ内に記憶されているスケジューラを実行し、これによってその先頭の記述子がＴＭＩバス・インタフェース１６０３を通して次に出力されるトラヒック・キューを選択する。デキュー・スケジューラ３０３は、選択したトラヒック・キューの先頭の記述子へのリンクを検索するために、トラヒック・キュープロセッサ３０５を使用し、それをデキュー・データ・メッセージ７０１を生成するのに必要な追加情報と共に、ＴＭＩバス・インタフェース１６０３に提供し、ＴＭＩバス・インタフェース１６０３は、コントローラ１５１３へリンクを提供し、メモリ１５１３から記述子を受信し、ＴＭＩバス・インタフェース１６０３を通して記述子を含むデキュー・データ・メッセージ７０１を出力する。＜ＴＭＣ  ＩＣ１５０３によるメモリ構成：図１７および図１８＞
すでに説明したように、ＴＭＣ  ＩＣ１５０３は、異なる容量の外部メモリにより構成することができる。図１７は最大構成を示す。記述子メモリ１５１３は、最大４つまでの１２８Ｍｂ（×１６）メモリと、１つの１２８Ｍｂ（×８）ＤＤＲＳＤＲＡＭメモリＩＣ１７０３を含むことができる。リンク・メモリ１５１１は、最大５つまでの１Ｍｂ（×１８）ＺＢＴ  ＳＲＡＭメモリＩＣ１７０５を含むことができ、記述子パラメータ・メモリ１５１１は、最大４つまでの５１２Ｋ（×３６）ＺＢＴ  ＳＲＡＭメモリＩＣを含むことができる。このように構成した場合、ＴＭＣ  ＩＣ１５０３は、ＯＣ４８ライン・レートをサポートし、２Ｍ３２ビット記述子、２５６Ｋトラヒック・キュー、および８Ｋスケジューラ・キューを処理することができる。ライン・レートが低い場合または記述子が少ないかまたは小さい場合、またはトラヒック・キューの数が少ないか、またはスケジューラ・キューの数が少ない場合、外部メモリの容量を少なくすることができる。ＰＣＩバス１５０５を通してセットすることができるＴＭＣ  ＩＣ１５０３の構成レジスタは、外部メモリの最大サイズ、および外部メモリ内の区画のサイズの両方を定義する。図１８は、ＯＣ４８ライン・レートの場合の通常の構成の可能性、およびこれらの構成のために必要な各タイプの外部メモリの容量を示すテーブル１８０１である。
＜ＴＭＩバス１５０７の詳細：図１９＞
図１９は、ＴＭＩバス１５０７の略図１９０１である。テーブル１９２５は、バスの信号名のリスト、信号がＴＭＣ１５０３の観点からみて入力信号であるのか、または出力信号であるのか、および信号の記述を示すテーブルである。
（クロック信号）
ＤＱＣＬＫ／ＤＱＣＬＫＸ１９０５ペアは、ＴＭＩＣＬＫソース１９０３からＴＭＣ  ＩＣ１５０３が入手する。ＤＱＣＬＫの周波数は、ＴＭＩＣＬＫの周波数の半分である。ＤＱＣＬＫＸは、ＤＱＣＬＫを倒置したものである。ＤＱＣＬＫＸの位相とＤＱＣＬＫの位相とは正確に１８０度ずれている。ＴＭＣ  ＩＣ１５０３のすべての出力は、ＤＱＣＬＫおよびＤＱＣＬＫＸの両方の立ち上がり縁部と同期している。これらの出力は、ＤＱＤ［２３：０］、ＮＱＲＤＹ、ＤＱＡＲＤＹおよびＤＱＰＡＲを含む。ＮＱＣＬＫ／ＮＱＣＬＫＸペア１９０７は、受信したＤＱＣＬＫ／ＤＱＣＬＫＸペアからＤＣＰにより入手される。ＮＱＣＬＫＸの位相とＮＱＣＬＫの位相とは正確に１８０度ずれている。ＤＣＰ２０２のすべての出力は、ＮＱＣＬＫおよびＮＱＣＬＫＸの両方の立ち上がり縁部と同期している。これらの出力は、ＮＱＤ［２３：０］、ＤＱＲＤＹ、ＤＱＡＣＫ［１：０］およびＮＱＰＡＲを含む。ＴＭＩＣＬＫ信号に対する最大クロック周波数は２００ＭＨｚであ
るが、このことは、ＤＱＣＬＫ／ＤＱＣＬＫＸおよびＮＱＣＬＫ／ＮＱＣＬＫＸペア内の各クロックに対する最大周波数が１００ＭＨｚであることを意味する。ＴＭＩＣＬＫ周波数およびＮＱＤ／ＤＱＤバス幅は、全Ｃ−５ＤＣＰポート帯域幅（約５Ｇｂｐｓ）および４０バイトの最小平均パケット・サイズを仮定して、３２バイトの記述子をサポートするように選択される。ＴＭＩＣＬＫ周波数は、１３３ＭＨｚの最大周波数を有するＴＭＣシステム・クロック、ＳＣＬＫの周波数の２倍を超えないようにさらに制限される。
（パリティ信号）
ＮＱＰＡＲ信号１９０９は、（ＮＱＤ［２３：０］、ＤＱＲＤＹおよびＤＱＡＣＫ［１：０］を含む）ＴＭＣ  ＩＣ１５０３が受信したＤＣＰ２０２のすべての出力をカバーする奇数パリティ信号である。ＤＱＰＡＲ１９１１信号は、（ＤＱＤ［２３：０］、ＮＱＲＤＹおよびＤＱＡＲＤＹを含む）ＤＣＰ２０２が受信したＴＭＣ  ＩＣ１５０３のすべての出力をカバーする奇数パリティ信号である。
（メッセージ・バス）
ＴＭＩバス１５０７内には３つのメッセージ・バス、すなわち、エンキュー・データ・メッセージを運ぶＮＱＤ［２３：０］１９１３；デキュー・データ・メッセージを運ぶＤＱＤ［２３：０］１９１７；デキュー・データ・メッセージの肯定応答を運ぶＤＱＡＣＫ［１：０］１９２１が存在する。ＮＱＤ［２３：０］１９１３は、エンキュー・データ・メッセージの２４ビット語を運ぶ。図６、図３１および図１３は、これらメッセージのフォーマットの詳細図である。ＮＱＤ［２３：０］バス・ピンは、バスがアイドル状態の場合には、すべて高レベルである。エンキュー・メッセージの開始は、メッセージのタイプ・フィールド６１１（メッセージの最初の２４ビット語のビット２：０）内の非アイドル値により識別される。ＤＱＤ［２３：０］はデキュー・データ・メッセージの２４ビット語を運ぶ。図７、図３２および図３３は、メッセージのフォーマットの詳細図である。エンキュー・データ・メッセージの場合のように、デキュー・データ・メッセージの開始は、メッセージのタイプ・フィールド７０３（メッセージの最初の２４ビット語のビット２：０）内の非アイドル値により識別される。エンキュー・データ・メッセージまたはデキュー・データ・メッセージのサイズは、記述子のサイズにより異なる。記述子のサイズは、任意のエンキュー・メッセージがＤＣＰ２０２からＴＭＣ  ＩＣ１５０３に送られる前に、インタフェースの両側で静的に構成される。
【０１４８】
ＤＱＡＣＫ［１：０］は、デキュー肯定応答メッセージをＤＣＰ２０２からＴＭＣ  ＩＣ１５０３に運ぶ。肯定応答メッセージが送られる度に、記述子がキュー２４７内のキュー２１３からデキューされる。各メッセージは、デキューされた記述子がＴＭＣ  ＩＣ１５０３から送られてきたデキュー・データ・メッセージ７０１のフィールド７０７内に指定されている仮想出力ポート識別子を含む。メッセージは５つの２ビット語からなり、図２８の参照番号２８０１はそのフォーマットを示す。
＜ＴＭＩバス１５１０上での流れの制御：図２０、図３８、図３９＞
メッセージ・バスＮＱＤ１９１３、ＤＱＤ１９１７およびＤＱＡＣＫ１：０上のメッセージの流れは、信号ＮＱＲＤＹ１９１５、ＤＱＲＤＹ１９１９およびＤＯＡＲＤＹ１９２３によりそれぞれ制御される。ＮＱＲＤＹ信号１９１５は、エンキュー・データ・バス（ＮＱＤ［２３：０］）上でのエンキュー・データ・メッセージの流れを可能にすることを出力（ａｓｓｅｒｔ）するものでなければならない。エンキュー・データ・メッセージが、エンキュー・データ・バス上で開始すると、終わりまで実行しなければならない。この信号は、ＤＣＰ２０２からのエンキュー・データ・メッセージを整調するために、ＴＭＣ
ＩＣ１５０３により使用される。極端な例の場合には、ＴＭＣ  ＩＣ１５０３は、自分が記述子記憶リソースを使い果たした場合、外部からのエンキュー・データ・メッセージを完全にストップするためにこの信号を使用する。ＴＭＣ  ＩＣ１５０３によるＮＱＲＤＹ１９１５のアサート解除の後で、ＤＣＰ２０２は、ＮＱＣＬＫおよびＮＱＣＬＫＸ両方の１２の立ち上がり縁部のカウント内でエンキュー・データ・メッセージの発生をストップしなければならない。図２０のタイミング図２００１はこの様子を示す。ＮＱＲＤＹ１
９１５は、２００３でアサート解除され、ＤＣＰ２０２は、２００５が示す時間までにエンキュー・データ・メッセージの発生をストップしなければならない。
【０１４９】
ＮＱＲＤＹ信号がＤＱＣＬＫ／ＤＱＣＬＫＸクロック・ペアと同期していることに留意されたい。ＮＱＣＬＫ／ＮＱＣＬＫＸペアの立ち上がり縁部は、ＮＱＲＤＹのサンプリングが行われるＤＱＣＬＫ／ＤＱＣＬＫＸペアの第１の立ち上がり縁部が能動状態でなくなった後で、第１のＮＱＣＬＫ／ＮＱＣＬＫＸ立ち上がり縁部からカウントされる。ＮＱＣＬＫ／ＮＱＣＬＫＸペアがＤＱＣＬＫ／ＤＱＣＬＫＸペアと非同期しているとして処理される場合には、必要な１２からのＮＱＣＬＫ／ＮＱＣＬＫＸの１つの立ち上がり縁部が、クロックの非同期的性質のために喪失する。
【０１５０】
ＤＱＲＤＹ信号１９１９は、デキュー・データ・メッセージの流れの制御を管理する。ＤＱＲＤＹは、デキュー・データ・バス（ＤＱＤ［２３：０］）上でデキュー・メッセージが流れることができるようにするとアサートすることになる。デキュー・データ・メッセージがデキュー・データ・バスの上で開始すると、終わりまで実行すしなければならない。この信号は、ＴＭＣ  ＩＣ１５０３からのデキュー・データ・メッセージを整調するために、ＤＣＰ２０２により使用される。ＴＭＣ  ＩＣ１５０３は、図２０のタイミング図２００７に示すように、ＤＣＰによるＤＱＲＤＹのアサート解除の後で、ＤＱＣＬＫおよびＤＱＣＬＫＸの両方の６つの立ち上がり縁部のカウント中に、デキュー・データ・メッセージの発生をストップしなければならない。この場合、ＤＱＲＤＹ１９１９のアサート解除は、２００９において発生し、２０１１がこれ以上新しいデキュー・データ・メッセージを発生することができない時点をマークする。
【０１５１】
ＤＱＲＤＹ信号１９１９が、ＮＱＣＬＫ／ＮＱＣＬＫＸクロックペアと同期していることに留意されたい。ＤＱＣＬＫ／ＤＱＣＬＫＸペアの立ち上がり縁部は、ＤＱＲＤＹのサンプリングが行われるＮＱＣＬＫ／ＮＱＣＬＫＸペアの第１の立ち上がり縁部が能動状態でなくなった後で、第１のＤＱＣＬＫ／ＤＱＣＬＫＸ立ち上がり縁部からカウントされる。ＤＱＣＬＫ／ＤＱＣＬＫＸペアがＮＱＣＬＫ／ＮＱＣＬＫＸペアと非同期しているとして処理される場合には、必要な６からのＤＱＣＬＫ／ＤＱＣＬＫＸの１つの立ち上がり縁部が、クロックの非同期的性質のために喪失する。
【０１５２】
ＤＱＡＲＤＹ１９２３は、デキュー肯定応答バスＤＱＡＣＫ１９２１上でデキュー肯定応答メッセージが流れることができるようにするとアサートすることになる。デキュー肯定応答メッセージがデキュー肯定応答バスの上で開始すると、終わりまで実行しなければならない。ＤＱＡＲＤＹ１９２３は、ＤＣＰ２０２からのデキュー肯定応答メッセージを整調するために、ＴＭＣ  ＩＣ１５０３により使用される。ＤＣＰは、図２０のタイミング図２０１３に示すように、ＴＭＣ  ＩＣ１５０３によるＤＱＡＲＤＹのアサート解除の後で、ＮＱＣＬＫおよびＮＱＣＬＫＸの両方の１２の立ち上がり縁部のカウント中に、デキュー肯定応答メッセージの発生をストップしなければならない。この場合、ＤＱＡＲＤＹ１９１９のアサート解除は、２０１５において発生し、２０１７がこれ以上新しいデキュー肯定応答メッセージを発生することができない時点をマークする。
【０１５３】
ＤＱＡＲＤＹ信号１０２３が、ＤＱＣＬＫ／ＤＱＣＬＫＸクロックペアと同期していることに留意されたい。ＮＱＣＬＫ／ＮＱＣＬＫＸペアの立ち上がり縁部は、ＤＱＡＲＤＹのサンプリングが行われるＤＱＣＬＫ／ＤＱＣＬＫＸペアの第１の立ち上がり縁部が能動状態でなくなった後で、第１のＮＱＣＬＫ／ＮＱＣＬＫＸ立ち上がり縁部からカウントされる。ＮＱＣＬＫ／ＮＱＣＬＫＸペアがＤＱＣＬＫ／ＤＱＣＬＫＸペアと非同期しているとして処理される場合には、必要な１２からのＮＱＣＬＫ／ＮＱＣＬＫＸの１つの立ち上がり縁部が、クロックの非同期的性質のために喪失する。
＜結論＞
上記の詳細な説明で、関連技術の当業者に対して、本特許出願の発明が実施されるストリーム・データ処理環境の作成および使用方法を説明してきたが、上記詳細な説明は、またさらに本発明者が現在知っている本発明の最良の実施の形態も開示している。しかし、関連技術の当業者であれば、本発明は、本明細書に記載した環境以外の多くのストリーム・データ処理環境で実行することができること、および本明細書に記載した環境で、本発明の実施形態を種々に変更することができることを直ちに理解することができるだろう。
【０１５４】
いくつかの例を挙げると、本明細書に記載した本発明の技術は、パケット処理がある集積回路において実行され、トラヒック管理が他の集積回路において実行される環境で特に有用である。しかし、本発明の技術はこのような環境に制限されるものではなく、トラヒック管理とパケット処理を別々に実施することが望ましいすべての環境に適用することができ、これによって、トラヒック管理機能またはパケット処理機能を実施するものの、集積回路として実装されたものではない装置と併用することができる。さらに、記述子の形式および内容は、トラヒック管理機能およびパケット処理機能のようにインプリメンテーションごとに変わる。さらに、好ましい実施形態のパケットに対して記述子上で実行される廃棄動作およびスケジューリング動作も、パケット自身を使用して実行することができる。環境のトラヒック管理部分とパケット処理部分との間のインタフェースの詳細も、インプリメンテーションごとに変わる。
【０１５５】
上記すべての理由により、詳細な説明は、すべての点において例示的なものであり、本発明を制限するものではないと見なすべきであり、本明細書に記載した本発明の範囲は、詳細な説明から判断すべきものではなく、特許法によって規定される全範囲により解釈する特許請求の範囲から判断すべきものである。
【図面の簡単な説明】
【０１５６】
【図１】パケット・ネットワークおよびパケットの図。
【図２】ルック・アサイド・データ・ストリーム管理を使用するデジタル通信プロセッサ、およびデジタル通信プロセッサと共に使用されるトラヒック管理プロセッサのブロック図。
【図３】トラヒック管理プロセッサ２０３の概念的全体図。
【図４】トラヒック・キュー２０４およびそれに関連づけられたデータ構造の全体図。
【図５】スケジューラ階層を示す図面。
【図６】エンキュー・データ・メッセージのフォーマットの詳細図。
【図７】デキュー・データ・メッセージのフォーマットの詳細図。
【図８】トラヒック・キュー・パラメータ・ブロック４０３のフォーマットの詳細図。
【図９】マルチキャスト詳細テーブル４２１のフォーマットの詳細図。
【図１０】廃棄構成ブロック４３１のフォーマットの詳細図。
【図１１】バッファ・プール仕様４３３のフォーマットの詳細図。
【図１２】廃棄動作の詳細なフローチャート。
【図１３】コミット・エンキュー・データ・メッセージのフォーマットの詳細図。
【図１４】好ましい実施形態でスケジューラを構成することができる基本図面。
【図１５】システム２０１の現在の好ましい実施例のブロック図。
【図１６】ＴＭＣ  ＩＣ１５０３の詳細なブロック図。
【図１７】ＴＭＣ  ＩＣ１５０３の外部メモリの構成の詳細なブロック図。
【図１８】ＴＭＣ  ＩＣ１５０３の例示としての外部メモリ構成を示すテーブル。
【図１９】ＴＭＩバス１５０７上の信号の詳細図。
【図２０】ＴＭＩバス１５０７上の信号のタイミング図。
【図２１】トラヒック・クラス・スケジューラ５０３の詳細図。
【図２２】内部スケジューラ５０９の詳細図。
【図２３】スケジューラを構成するために使用するデータ構造の詳細図。
【図２４】スケジューラ入力を定義するために使用するデータの詳細図。
【図２５】ＴＭＣ２０３およびＱＭＵ２１１のハイレベル・ブロック図。
【図２６】フレームをベースとする不足ラウンドロビン・スケジューリング・アルゴリズムを使用するトラヒック・クラス・スケジューラの詳細なブロック図。
【図２７】仮想出力ポート５２１を構成するデータ構造の図面。
【図２８】デキュー肯定応答メッセージの図面。
【図２９】トラヒック・クラス・スケジューラ５０３を構成するために使用するデータ構造の図面。
【図３０】トラヒック・クラス・スケジューラ５０３に対してスケジューラ・キューを入力するために、トラヒック・キュー２０４を関連づけるために使用するデータ構造の図面。
【図３１】図６の続き。
【図３２】図７の続き。
【図３３】図７のさらに続き。
【図３４】図８の続き。
【図３５】図９の続き。
【図３６】図２３の続き。
【図３７】図２４の続き。
【図３８】図２０の続き。
【図３９】図２０のさらに続き。
【図４０】図３０の続き。
【図４１】図３０のさらに続き。
【図１】
2005510893.tif 000005
【図２】
2005510893.tif 000006
【図３】
2005510893.tif 000007
【図４】
2005510893.tif 000008
【図５】
2005510893.tif 000009
【図６】
2005510893.tif 000010
【図７】
2005510893.tif 000011
【図８】
2005510893.tif 000012
【図９】
2005510893.tif 000013
【図１０】
2005510893.tif 000014
【図１１】
2005510893.tif 000015
【図１２】
2005510893.tif 000016
【図１３】
2005510893.tif 000017
【図１４】
2005510893.tif 000018
【図１５】
2005510893.tif 000019
【図１６】
2005510893.tif 000020
【図１７】
2005510893.tif 000021
【図１８】
2005510893.tif 000022
【図１９】
2005510893.tif 000023
【図２０】
2005510893.tif 000024
【図２１】
2005510893.tif 000025
【図２２】
2005510893.tif 000026
【図２３】
2005510893.tif 000027
【図２４】
2005510893.tif 000028
【図２５】
2005510893.tif 000029
【図２６】
2005510893.tif 000030
【図２７】
2005510893.tif 000031
【図２８】
2005510893.tif 000032
【図２９】
2005510893.tif 000033
【図３０】
2005510893.tif 000034
【図３１】
2005510893.tif 000035
【図３２】
2005510893.tif 000036
【図３３】
2005510893.tif 000037
【図３４】
2005510893.tif 000038
【図３５】
2005510893.tif 000039
【図３６】
2005510893.tif 000040
【図３７】
2005510893.tif 000041
【図３８】
2005510893.tif 000042
【図３９】
2005510893.tif 000043
【図４０】
2005510893.tif 000044
【図４１】
2005510893.tif 000045
【国際調査報告】
2005510893.tif 000046
2005510893.tif 000047
2005510893.tif 000048
2005510893.tif 000049
2005510893.tif 000050
2005510893.tif 000051