(57)【要約】共用リンクを介するサービス処理のために待ち行列を選択する方法およびシステムが提供される。該方法およびシステムは、下記のことをおこなうステップもしくは構成要素を有し、すなわち、複数の入力端（１０２）内の各待ち行列に対する優先度を決定する(２０２)ことと；１つの所定の出力端（１０４）向けのパケットを持つ各入力端（１０４）内の待ち行列の各グループに対して第１の優先度を持つ１つの待ち行列を選択することと；所定の出力端（１０４）向けのパケットを持つ、第１の優先度を持つ待ち行列の各サブセットに対して第２の優先度を持つ待ち行列を選択することと；所定のタイムスロット中共有リンクを介するサービス処理のための第２の優先度を持つ待ち行列を選択することとをおこなうステップもしくは構成要素を有し、ここで上記優先度は、データ伝送向けの１つの所定のタイムスロットに対して瞬時的に成り立つものである。【選択図】図３Ａ
2004534462.tif 000002
【特許請求の範囲】
【請求項１】
共用リンクを介する伝送のためにパケットを選択する方法であって、
複数入力端のうちの各入力端内の複数待ち行列の各々における先出しパケットに対する優先度を決定するステップと、
１つの所定の出力端向けの各入力端の待ち行列内の先出しパケットの各グループに対して、第１の優先度を持つ先出しパケットを選択するステップと、
所定の出力端に向けられた、第１の優先度を持つ選択された先出しパケットの各サブセットに対して、第２の優先度を持つ先出しパケットを選択するステップと、
第２の優先度を持つ選択された先出しパケットを、少なくとも１つの入力端から共用リンクを介して伝送するステップを有することを特徴とする方法。
【請求項２】
共用リンクを介したサービス処理のために待ち行列を選択する方法であって、
複数の入力端内の各待ち行列に対して、データ伝送向けの１つの所定のタイムスロットに対して瞬時的に成り立つ優先度を決定するステップと、
１つの所定の出力端向けのパケットを持つ複数の入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択するステップと、
所定のタイムスロット中で共用リンクを介して、各グループに対して第１の優先度を持つ選択された待ち行列をサービス処理するステップを有することを特徴とする方法。
【請求項３】
共用リンクを介するサービス処理のために待ち行列を選択する方法であって、
複数の入力端内の各待ち行列に対して、データ伝送に対する所定のタイムスロットに対して瞬時的に成り立つ優先度を決定するステップと、
１つの所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択するステップと、
第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択するステップと、
所定のタイムスロット中で共用リンクを介して、各サブセットに対して第２の優先度を持つ選択された待ち行列をサービス処理するステップを有することを特徴とする方法。
【請求項４】
第１の優先度を持つ待ち行列を選択するステップを各入力端内で実施することを特徴とする請求項３記載の方法。
【請求項５】
第２の優先度を持つ待ち行列を選択するステップをアービトレーションモジュール内で実施することを特徴とする請求項４記載の方法。
【請求項６】
第１の優先度を持つ待ち行列を選択するステップは、最高の優先度を持つ待ち行列を選択するステップを含むことを特徴とする請求項５記載の方法。
【請求項７】
第２の優先度を持つ待ち行列を選択するステップは、最高の優先度を持つ待ち行列を選択するステップを含むことを特徴とする請求項６記載の方法。
【請求項８】
同じ最高の優先度を持つ２つ以上の競合関係にある待ち行列の間で、いずれがより高い優先度を持つべきかを、共用リンクを介して最近最もサービス処理を受けていない待ち行列を選択することによって決定するステップを有することを特徴とする請求項７記載の方法。
【請求項９】
同じ最高の優先度を持つ２つ以上の待ち行列の間で、いずれがより高い優先度を持つべきかを、当該の２つ以上の競合関係にある待ち行列からランダムに１つの待ち行列を選択することによって決定するステップを有することを特徴とする請求項７記載の方法。
【請求項１０】
同じ最高の優先度を持つ２つ以上の待ち行列の間で、いずれがより高い優先度を持つべきかを、２つ以上の競合関係の待ち行列からのラウンドロビン選択を使用することによって決定するステップを有することを特徴とする請求項７記載の方法。
【請求項１１】
さらに、
各待ち行列内の先出しパケットのサイズを確認するステップと、
任意の待ち行列内の先出しパケットのサイズが単一のタイムスロット中における共用リンクを介する伝送のためには過大である場合に、その待ち行列が第２の優先度を有する選択された待ち行列である場合には、所定のタイムスロットの直後に続く少なくとも１つのタイムスロットに対する最高の優先度をその待ち行列に割り当てるステップと、
所定のタイムスロットの直後に続くタイムスロット中サービス処理に対する最高の優先度を持つ待ち行列を選択するステップを有することを特徴とする請求項３記載の方法。
【請求項１２】
さらに、
待ち行列が所定のタイムスロット中にサービス処理される場合に、待ち行列の優先度をデクリメントするステップと、
所定のタイムスロットの後に待ち行列の優先度をインクリメントすることによって、各待ち行列に対する優先度を更新するステップを含むことを特徴とする請求項３記載の方法。
【請求項１３】
共用リンクを介するサービス処理のために待ち行列を選択するシステムであって、
（ａ）入力端内の各待ち行列に対して、データ伝送用の所定のタイムスロット中瞬時的に成り立つ優先度を決定するための、そして、（ｂ）所定の出力端向けのパケットを有する入力端内の待ち行列の各グループに対して第１の優先度を持つ１つの待ち行列を選択するための入力端内の計量モジュールと、
第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択するためのアービトレーションモジュールとを有し、第２の優先度を持つ選択された待ち行列は、所定のタイムスロット中で共用リンクを介するサービス処理のための待ち行列であることを特徴とするシステム。
【請求項１４】
マイクロプロセッサに指示する命令を記憶するコンピュータ可読媒体であって、命令は、下記の動作を行うようマイクロプロセッサに指示するものである、すなわち、
複数の入力端中の各待ち行列に対して、データ伝送のための所定のタイムスロット中瞬時的に成り立つ優先度を決定し、
所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択し、
第１の優先度を持ち所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択し、
所定のタイムスロット中に共用リンクを介して、各サブセットに対して第２の優先度を有する選択された待ち行列をサービス処理するようにマイクロプロセッサに指示するものであることを特徴とするコンピュータ可読媒体。
【請求項１５】
共用リンクを介するサービス処理のために待ち行列を選択するシステムであって、
複数入力端の中の各待ち行列に対して、データ伝送のための所定のタイムスロット中瞬時的に成り立つ優先度を決定する手段と、
１つの所定出力端向けのパケットを持つ各入力端内の待ち行列の各グループに対して、第１の優先度を持つ１つの待ち行列を選択する手段と、
第１の優先度を持ち所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択する手段と、
所定のタイムスロット中に共用リンクを介して、各サブセットに対して第２の優先度を有する選択された待ち行列をサービス処理する手段を有することを特徴とするシステム。
【請求項１６】
共用リンクを介するサービス処理のために待ち行列を選択する方法であって、各待ち行列は所定のタイムスロット中瞬時的に成り立つデータ伝送に対する優先度を有するものであり、上記方法は、下記ステップを有し、すなわち：
１つの所定出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列についての情報を各入力端から受け取るステップと、
第１の優先度を持ち所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ１つの待ち行列を選択するステップと、
所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択するステップを有することを特徴とする方法。
【請求項１７】
第２の優先度を持つ待ち行列を各入力端から受け取り、選択し、そして、サービス処理のために第２の優先度を持つ待ち行列を選択するステップは、１つのアービタチップ内で実行することを特徴とする請求項１６記載の方法。
【請求項１８】
さらに、所定のタイムスロットの期間中そこに入力端がサービス処理のために接続されるべき所定の出力端についての情報を各入力端に送るステップをさらに有することを特徴とする請求項１６に記載の方法。
【請求項１９】
共用リンクを介するサービス処理のために待ち行列を選択する装置であって、各待ち行列は所定のタイムスロット中瞬時的に成り立つデータ伝送に対する優先度を有し、
プログラムを記憶するメモリと、
メモリと通信するプロセッサとを有し、ここで、該プロセッサは、下記動作を行うよう、プログラムによって指示されるものである、すなわち、
所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列についての情報を各入力端から受け取り、
第１の優先度を持ち所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択し、
所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択するよう、プログラムによって指示されるものであることを特徴とする装置。
【請求項２０】
共用リンクを介するサービス処理のために待ち行列を選択するコンピュータ可読媒体であって、ここで、各待ち行列はデータ伝送のための所定のタイムスロット中瞬時的に成り立つ優先度を有し、上記、コンピュータ可読媒体は、下記の動作を行うようマイクロプロセッサに指示する命令を記憶するものである、すなわち、
１つの所定出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列についての情報を各入力端から受け取り、
第１の優先度を持ち所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択し、
所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択するようにマイクロプロセッサに指示する命令を記憶するものであることを特徴とするコンピュータ可読媒体。
【請求項２１】
共用リンクを介するサービス処理のために待ち行列を選択する方法であって、
複数入力端の中の各待ち行列に対して、データ伝送用の１つの所定のタイムスロット中瞬時的に成り立つ優先度を決定するステップと、
各入力端内において、１つの所定出力端における１つの所定ポート向けのパケットを持つ待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択するステップと、
アービタチップ内において、第１の優先度を持ち同じ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択するステップと、
アービタチップ内において、第２の優先度を持ち同じ所定の出力端向けのパケットを持つ複数の入力端からの選択された待ち行列の各サブセットに対して、第３の優先度を持つ待ち行列を選択するステップと、
所定のタイムスロット中に共用リンクを介して、各サブセットに対して第３の優先度を持つ選択された待ち行列をサービス処理するステップを有することを特徴とする方法。
【請求項２２】
第１の優先度を持つ待ち行列を選択するステップは、様々なサービス処理クラスを持つ待ち行列から選択するステップを含むことを特徴とする請求項２１記載の方法。
【請求項２３】
第２の優先度を持つ待ち行列を選択するステップは、同じ所定の出力端の様々なポート向けのパケットを持つ待ち行列から選択するステップを含むことを特徴とする請求項２２記載の方法。
【請求項２４】
第２の優先度を持つ待ち行列を選択するステップは、同じ所定出力端のポートの充満状態についての情報を使用するステップを含むことを特徴とする請求項２３記載の方法。
【請求項２５】
マイクロプロセッサに指示する命令を記憶するコンピュータ可読媒体であって、上記命令は、下記の動作を行うようマイクロプロセッサに指示するものである、すなわち
複数入力端の中の各待ち行列に対して、データ伝送のための１つの所定タイムスロット中瞬時的に成り立つ優先度を決定し、
各入力端内において、１つの所定の出力端における１つの所定のポート向けのパケットを持つ待ち行列の各グループに対して、第１の優先度を持つ１つの待ち行列を選択し、
アービタチップ内において、第１の優先度を持ち同じ所定の出力端向けのパケットを有する選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択し、
アービタチップ内において、第２の優先度を持ち同じ所定の出力端向けのパケットを持つ複数の入力端からの選択された待ち行列の各サブセットに対して、第３の優先度を持つ１つの待ち行列を選択し、
所定のタイムスロット中に共用リンクを介して、各サブセットに対して第３の優先度を有する選択された待ち行列をサービス処理するようにマイクロプロセッサに指示するものであることを特徴とするコンピュータ可読媒体。
【請求項２６】
共用リンクを介するサービス処理のために待ち行列を選択するシステムであって、
複数入力端の中の各待ち行列に対して、データ伝送のための１つの所定のタイムスロット中瞬時的に成り立つ優先度を決定する手段と、
各入力端内において、所定出力端の所定のポート向けのパケットを持つ待ち行列の各グループに対して、第１の優先度を持つ１つの待ち行列を選択する手段と、
アービタチップ内において、第１の優先度を持ち同じ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択する手段と、
アービタチップ内において、第２の優先度を持ち、同じ所定の出力端向けのパケットを持つ複数の入力端からの選択された待ち行列の各サブセットに対して、第３の優先度を持つ１つの待ち行列を選択する手段と、
所定のタイムスロット中に共用リンクを介して、各サブセットに対して第３の優先度を有する選択された待ち行列をサービス処理する手段とを備えることを特徴とするシステム。
【請求項２７】
共用リンクを介する帯域幅割り当て方法であって、
待ち行列グループの中の各待ち行列に対する待ち行列計量情報を維持するステップと、
待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて各待ち行列に対する保証レートを計算するステップと、
待ち行列が所定のタイムスロット中にサービス処理される場合に、適切な量だけ待ち行列のクレジット値を調整することと、所定のタイムスロットの後に保証レートに基づいて幾らかの量だけ待ち行列のクレジット値を調整することとによって、各待ち行列に関連する１つのクレジット値を調整するステップと、
帯域幅を割り当てる働きをする待ち行列に対する優先度を決定するために、クレジット値、部分パケット情報、シェーピングリミット、および、待ち行列が空であるかどうかの表示から成るグループの中の１つ以上のうちから選択される待ち行列ステート状態情報を使用するステップとを有することを特徴とする方法。
【請求項２８】
待ち行列計量情報は待ち行列長さ情報を含むことを特徴とする請求項２７記載の方法。
【請求項２９】
待ち行列計量情報は待ち行列到着レート情報を含むことを特徴とする請求項２７記載の方法。
【請求項３０】
さらに、各待ち行列の優先度と他の待ち行列の優先度とに基づいて、各待ち行列をサービス処理するかどうかを決定することを特徴とする請求項２７記載の方法。
【請求項３１】
クレジット値は待ち行列に対する優先度であることを特徴とする請求項２７記載の方法。
【請求項３２】
待ち行列状態情報を使用することは、待ち行列に対する優先度の形にクレジット値をスケーリングすることを含み、優先度に対するスケールサイズがクレジット値に対するスケールサイズよりも著しく小さいことを特徴とする請求項２７記載の方法。
【請求項３３】
保証レートに基づいて幾らかの量だけ待ち行列のクレジット値を調整するステップは、待ち行列に対する保証レートの分だけクレジット値をインクリメントすることを含むことを特徴とする請求項２７記載の方法。
【請求項３４】
待ち行列がタイムスロット中にサービス処理される場合に適切な量だけ待ち行列のクレジット値を調整することは、適切な量だけクレジット値をデクリメントすることを含むことを特徴とする請求項２７記載の方法。
【請求項３５】
適切な量は、最終の調整の時以降に待ち行列から共用リンクを介して伝送されたパケットの数の関数であることを特徴とする請求項３４記載の方法。
【請求項３６】
適切な量は、最終の調整の時以降に待ち行列から共用リンクを介して伝送されたバイトの数の関数であることを特徴とする請求項３４記載の方法。
【請求項３７】
待ち行列ステート状態情報を使用するステップは、クレジット値が待ち行列に対するシェーピングリミットよりも小さい場合に優先度を最小値に設定することを含むことを特徴とする請求項２７記載の方法。
【請求項３８】
シェーピングリミットは、待ち行列が受け取る帯域幅を最大の大きさに制限することを特徴とする請求項３７記載の方法。
【請求項３９】
待ち行列ステート状態情報を使用するステップは、部分パケット変数が待ち行列に対して存在する場合に優先度を最大レベルに設定することを含むことを特徴とする請求項２７記載の方法。
【請求項４０】
共用リンクシステムの出力端に対する帯域幅を保証する方法であって、
出力端向けのパケットを持つ、待ち行列グループ内の各待ち行列に対して、待ち行列計量についての情報を維持するステップと、
待ち行列計量情報と出力端に対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、
帯域幅を割り当てるために使用される、待ち行列グループ内の各待ち行列に対するクレジット値を計算するために、保証レートを使用するステップを有し、上記待ち行列は、共用リンクシステムの１つ以上の入力端内に常駐しているものであることを特徴とする方法。
【請求項４１】
各待ち行列に対するクレジット値を計算するために保証レートを使用するステップは、
待ち行列が所定のタイムスロット中にサービス処理される場合に、クレジット値を適切な量だけデクリメントすることと、所定のタイムスロットの後に保証レートに基づいてある量だけクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整することを含むことを特徴とする請求項４０記載の方法。
【請求項４２】
待ち行列サブセット内の各待ち行列は、それに関連するサービス処理クラスを持ち、グループ内の各待ち行列のサービス処理クラスは同じであることを特徴とする請求項４０記載の方法。
【請求項４３】
各待ち行列に対する保証レートを計算することは、
グループ内の待ち行列に対する待ち行列計量の合計で除算された、待ち行列に対する待ち行列計量と出力端に対する保証された帯域幅の大きさとの積に等しい量を、各待ち行列に対する保証レートとして求めることを特徴とする請求項４２記載の方法。
【請求項４４】
待ち行列計量情報は待ち行列長さ情報を含むことを特徴とする請求項４３記載の方法。
【請求項４５】
共用リンクの入力端に対する帯域幅を保証する方法であって、
入力端内の待ち行列グループの中の各待ち行列に対する待ち行列計量についての情報を維持するステップと、
待ち行列計量情報と入力端に対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、
帯域幅を割り当てるために使用される、待ち行列グループ内の各待ち行列に対するクレジット値を計算するために、保証レートを使用するステップを有し、上記待ち行列内のパケットは共用リンクシステムの１つ以上の出力端向けのものであることを特徴とする方法。
【請求項４６】
クレジット値を計算するために保証レートを使用するステップは、
待ち行列が所定のタイムスロット中にサービス処理される場合に待ち行列のクレジット値を適切な量だけデクリメントすることと、所定のタイムスロットの後に保証レートに基づいて幾らかの量だけ待ち行列のクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整することを特徴とする請求項４５記載の方法。
【請求項４７】
待ち行列グループ内の各待ち行列はそれに関連するサービス処理クラスを持ち、グループ内の各待ち行列のサービス処理クラスは同じであることを特徴とする請求項４５記載の方法。
【請求項４８】
各待ち行列に対する保証レートを計算するステップは、
グループ内の待ち行列に対する待ち行列計量の合計で除算された、待ち行列に対する待ち行列計量と入力端に対する保証された帯域幅の大きさとの積に等しい量を、各待ち行列に対する保証レートとして求めることを特徴とする請求項４７記載の方法。
【請求項４９】
待ち行列計量情報は待ち行列長さ情報を含むことを特徴とする請求項４８記載の方法。
【請求項５０】
共用リンクを介する帯域幅の割当てに使用するための保証レートを決定する方法であって、
待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を維持するステップと、
待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、
帯域幅を割り当てるために使用される保証レートを、各待ち行列に関連する入力端に送ることを特徴とする方法。
【請求項５１】
保証された帯域幅の大きさは出力端に対する保証された帯域幅の大きさであり、待ち行列グループ内の各待ち行列は出力端向けのパケットを持ち、保証レートを計算することは、出力端に対する保証された帯域幅の大きさを少なくとも１つの入力端内に常駐する待ち行列のグループの中で割り当てる、保証レートを計算することを特徴とする請求項５０記載の方法。
【請求項５２】
保証レートを計算するステップは、
グループ内の待ち行列に対する待ち行列計量の合計で除算された、待ち行列に対する待ち行列計量と出力端に対する保証された帯域幅の大きさとの積に等しい量を、各待ち行列に対する保証レートとして求めることを特徴とする請求項５１記載の方法。
【請求項５３】
保証された帯域幅の大きさは入力端に対する保証された帯域幅の大きさであり、保証レートを計算するステップは、入力端に対する保証された帯域幅の大きさを、少なくとも１つの出力端向けのパケットを持つ待ち行列のグループの中で割り当てる、保証レートの計算を含むことを特徴とする請求項５０記載の方法。
【請求項５４】
保証レートを計算する動作は、
グループ内の待ち行列に対する待ち行列計量の合計で除算された、待ち行列に対する待ち行列計量と入力端に対する保証された帯域幅の大きさとの積に等しい量を、各待ち行列に対する保証レートとして求めることを特徴とする請求項５３記載の方法。
【請求項５５】
共用リンクを介する帯域幅の割当てに使用するための保証レートを決定する装置であって、
プログラムを記憶するメモリと、
メモリと通信するプロセッサを有し、該プロセッサは、プログラムによって下記の動作を行うように指示されるものである、すなわち、
待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を維持し、
待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算し、
帯域幅を割り当てるために使用される保証レートを、各待ち行列に関連する入力端に送るようにプログラムによって指示されるものであることを特徴とする装置。
【請求項５６】
共用リンクを介する帯域幅の割当てに使用するための保証レートを決定するためのコンピュータ可読媒体であって、
該コンピュータ可読媒体は、下記の動作を行うようマイクロプロセッサに指示するものである、すなわち、
待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を維持し、
待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算し、
帯域幅を割り当てるために使用される保証レートを、各待ち行列に関連する入力端に送るようにマイクロプロセッサに指示するものであることを特徴とするコンピュータ可読媒体。
【請求項５７】
共用リンクを介する帯域幅を割り当てる方法であって、
待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を求めるステップと、
待ち行列計量情報を帯域幅アロケータモジュールに伝送するステップと、
帯域幅アロケータモジュールからグループ内の各待ち行列に対する保証レートを受け取るステップと、
待ち行列が所定のタイムスロット中にサービス処理される場合に待ち行列のクレジット値を適切な量だけデクリメントするステップと、所定のタイムスロットの後に待ち行列の保証レートに基づいて幾らかの量だけ待ち行列のクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整するステップと、
帯域幅を割り当てる働きをする、グループ内の各待ち行列に対して優先度を、クレジット値を使用して決定するステップを有すること特徴とする方法。
【請求項５８】
共用リンクを介する帯域幅を割り当てる装置であって、
プログラムを記憶するメモリと、
メモリと通信するプロセッサとを有し、該プロセッサは、プログラムによって下記の動作を行うように指示されるものである。
待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を求め、
待ち行列計量情報を帯域幅アロケータモジュールに伝送し、
帯域幅アロケータモジュールからグループ内の各待ち行列に対する保証レートを受け取り、
待ち行列が所定のタイムスロット中にサービス処理される場合に待ち行列のクレジット値を適切な量だけデクリメントすることと、所定のタイムスロットの後に待ち行列の保証レートに基づいて幾らかの量だけ待ち行列のクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整し、
帯域幅を割り当てる働きをする、グループ内の各待ち行列に対する優先度を、クレジット値を使用して決定する動作を行うようにプログラムによって指示されるものであることを特徴とする装置。
【請求項５９】
共用リンクを介する帯域幅を割り当てる方法であって、
待ち行列計量情報と保証された帯域幅の大きさとに基づいて、少なくとも１つの入力端内の各待ち行列に対する保証レートを計算するステップと、
各待ち行列に対する優先度を、所定のタイムスロットの期間中に共用リンクに接続するために計算するステップと、
各待ち行列の優先度に基づいて、所定のタイムスロットの期間中にサービス処理するために少なくとも１つの待ち行列を決定するステップを有し、上記の優先度は、所定のタイムスロットに対して瞬時的に成り立つものであり、また各待ち行列に対する保証レートに基づいていることを特徴とする方法。
【請求項６０】
共用リンクを介する帯域幅を割り当てる方法であって、
複数の入力端内の各待ち行列に対する待ち行列計量情報を求めるステップと、
待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて、各待ち行列に対する保証レートを計算するステップと、
待ち行列が所定のタイムスロット中にサービス処理される場合に、適切な量だけ待ち行列のクレジット値を調整することと、所定のタイムスロットの後に保証レートに基づいて幾らかの量だけ待ち行列のクレジット値を調整することとによって、各待ち行列に関連するクレジット値を調整するステップと、
データ伝送のための所定のタイムスロットに対して瞬時的に成り立つ優先度を各待ち行列に対して計算するために、クレジット値を使用することと、
所定の出力端向けの先出しパケットを持つ複数の入力端の中の待ち行列の各グループに対して、最高の優先度を持つ待ち行列を選択するステップと、
所定のタイムスロット中に共用リンクを介して最高の優先度を持つ選択された待ち行列をサービス処理すること、各入力端は所定のタイムスロットの期間中に単一の出力端と通信することを特徴とする方法。
【請求項６１】
共用リンクを介する帯域幅を割り当てるシステムであって、
待ち行列計量情報と保証された帯域幅の大きさとに基づいて少なくとも１つの入力端内の各待ち行列に対する保証レートを計算する帯域幅アロケータモジュールと、
所定のタイムスロット中に共用リンクと接続するために、入力端内の各待ち行列に対して優先度を計算する各入力端内の計量モジュールであって、各待ち行列に対する優先度は所定のタイムスロットに対して瞬時的であり、各待ち行列に対する保証レートに基づいている計量モジュールと、
各待ち行列の優先度に基づいて所定のタイムスロットの期間中にサービス処理するために、少なくとも１つの待ち行列を決定するアービトレーションモジュールを備えることを特徴とするシステム。
【請求項６２】
共用リンクを介する帯域幅を割り当てるシステムであって、
所定のタイムスロット中に共用リンクと接続するための優先度を入力端チップ内で各待ち行列に対して計算するための、複数の待ち行列と計量モジュールとを含む入力端チップであって、各待ち行列に対する優先度は所定のタイムスロットに対して瞬時的であり、各待ち行列に対する保証レートに基づいている入力端チップと、
（ａ）待ち行列計量情報と保証された帯域幅の大きさとに基づいて１つ以上の入力端チップ内の各待ち行列に対する保証レートを計算する帯域幅アロケータモジュールと、（ｂ）各待ち行列の優先度に基づいて所定のタイムスロットの期間中にサービス処理するために少なくとも１つの待ち行列を決定するアービトレーションモジュールとを含むアービタチップを備えることを特徴とするシステム。
【請求項６３】
共用リンクを介する帯域幅を割り当てる方法であって、
待ち行列のグループ内の各待ち行列に対する待ち行列計量についての情報を維持するステップと、
待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、
各入力端が待ち行列に対する保証レートを使用して入力端内の各待ち行列に対する優先度を計算することが可能である、各待ち行列に関連する入力端に対して、各待ち行列に対する保証レートを送るステップと、
所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列に対する情報を各入力端から受け取るステップと、
第１の優先度を持ち所定の出力端向けのパケットを持つ待ち行列の各サブセットに対して、第２の優先度を有する待ち行列を選択するステップと、
所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択することを特徴とする方法。
【請求項６４】
共用リンクを介する帯域幅を割り当てる方法であって、
入力端内の各待ち行列に対する待ち行列計量についての情報を求めるステップと、
帯域幅アロケータモジュールに待ち行列計量情報を伝送するステップと、
待ち行列計量情報を少なくとも部分的に使用して計算された各待ち行列に対する保証レートを帯域幅アロケータモジュールから受け取るステップと、
待ち行列が所定のタイムスロット中にサービス処理される場合に、待ち行列のクレジット値を適切な量だけデクリメントするステップと、所定のタイムスロットの後に待ち行列の保証レートに基づいて幾らかの量だけ待ち行列のクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整するステップと、
所定のタイムスロットに対して瞬時的に成り立つ優先度を、入力端内の各待ち行列に対して決定するステップと、
所定の出力端向けのパケットを持つ入力端内の待ち行列の各グループに対して、第１の優先度を持つ少なくとも１つの待ち行列を選択するステップと、
第１の優先度を持つ入力端内の各待ち行列に対する情報をアービトレーションモジュールに送るステップと、
入力端がどの出力端と所定のタイムスロットの期間中に通信することになるかを決定する第２の優先度を持つ待ち行列に対する情報を、アービトレーションモジュールから受け取ることを特徴とする方法。
【請求項６５】
共用リンクを介して待ち行列をサービス処理する方法であって、
入力端内の各待ち行列に対する先出しパケットのサイズを確認するステップと、
いずれかの待ち行列内の先出しパケットのサイズが、データ伝送のための単一の所定のタイムスロット中の共用リンクを介する伝送には過大である場合に、先出しパケットを持つ待ち行列が、先出しパケット全体がデータ伝送のための２つ以上のタイムスロットの期間中に共用リンクを介して伝送されるようにデータ伝送のために選択される時に、共用リンクに対する接続を維持することを特徴とする方法。
【請求項６６】
共用リンクに対する接続を維持することは、
先出しパケットを持つ待ち行列がデータ伝送のために選択される時に、所定のタイムスロットの直後の少なくとも１つのタイムスロットに対する最高の優先度をその待ち行列に割り当てることを含み、最高の優先度を持つ待ち行列は、所定のタイムスロットの直後の少なくとも１つのタイムスロットの期間中にサービス処理されることを特徴とする請求項６５記載の方法。
【請求項６７】
システム内の複数の待ち行列の各待ち行列に対する優先度を決定する方法であって、優先度は共用リンクを介する帯域幅の割当てを決定し、最高の優先度を持つ待ち行列が所定のタイムスロットの期間中にサービス処理される方法であって、
待ち行列が部分パケットを含む場合には、優先度を最高の優先度に設定するステップと、
待ち行列が空である場合には、優先度を最低の優先度に設定するステップと、
待ち行列がゼロよりも大きいクレジット値を持つ場合には、スケーリング因子によって除算されたクレジット値に等しい最高の優先度と最低の優先度との間の丸められた数として優先度を決定することを特徴とする方法。
【請求項６８】
システムであって、
スイッチリンクと、
少なくとも１つの入力端チップと少なくとも１つの出力端チップと、第１の優先度を持ち所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ少なくとも１つの待ち行列を選択するためのアービトレーションモジュールを持つアービタチップとを有し、第２の優先度を持つ選択された待ち行列は、所定のタイムスロット中のスイッチリンクを介するサービス処理のための待ち行列であり、上記スイッチリンクは少なくとも１つの入力端チップと少なくとも１つの出力端チップとの間に配置されており、入力端チップは、（ａ）入力端内の各待ち行列に対する、データ伝送のための所定のタイムスロットに対して瞬時的に成り立つ優先度を決定するための、そして、（ｂ）所定の出力端チップ向けのパケットを持つ入力端チップ内の待ち行列の各グループに対して、第１の優先度を持つ少なくとも１つの待ち行列を選択するための計量モジュールを有することを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、共有リンクを介する帯域幅を割り当てるための方法とシステムに関し、より特定的には、プロトコル処理を円滑化しかつサービス処理品質の保証を維持するこうした方法とシステムとに関する。
【背景技術】
【０００２】
図１が、ネットワークバックボーンを介する情報のパケットのトラフィックを管理する典型的な交換システム１０を示す。システム１０は、１つ以上の入力入力端Ｉ１、Ｉ２、Ｉ３と、１つ以上のアウトプット出力端Ｅ１、Ｅ２、Ｅ３と、スイッチすなわちクロスバ１２とを含む。３つの入力端Ｉ１、Ｉ２、Ｉ３と３つの出力端Ｅ１、Ｅ２、Ｅ３とが図１に示されているが、任意の数の入力端と出力端が交換システム１０内で接続されることが可能である。データのパケットがトラフィックソース１４を通って入力端Ｉ１、Ｉ２、Ｉ３に入り、トラフィック出口１６を通って出力端Ｅ１、Ｅ２、Ｅ３から出て行く。通常の動作では、交換システム１０は、入力端と出力端の間に１対１の対応付けマッピングが存在するように、所定の入力端をクロスバすなわちスイッチ１２を介して所定の出力端に接続することが可能であり、または、入力端と出力端の間に１対多の対応付けマッピングが存在するように、所定の入力端を１つ以上の出力端に接続することが可能である。言い換えると、各出力端は、交換システム１０を介するデータ伝送のいずれのタイムスロットに対しても、単一の入力端からデータを受け取ることしかできない。しかし、１つの入力端は複数の出力端にデータを送ることが可能である。さらに、各入力端Ｉ１、Ｉ２、Ｉ３は、データのパケットを記憶するための複数の待ち行列を含み、各出力端Ｅ１、Ｅ２、Ｅ３は複数のバッファＦＩＦＯＳ（先入れ先出し）を含む。各タイムスロット毎に、各入力端内の単一の待ち行列が、１つ以上の出力端の中の１つ以上のポートに接続されることが可能である。例えば、所定のタイムスロットの期間中に、入力端Ｉ１内の待ち行列Ｑ２が出力端Ｅ３内のバッファＦＩＦＯ１に接続され、入力端Ｉ２内の待ち行列Ｑ１が出力端Ｅ１内のバッファＦＩＦＯ１に接続され、入力端Ｉ３内の待ち行列Ｑ１が出力端Ｅ２のバッファＦＩＦＯ３に接続可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
一般的に、図１の交換システム１０のような交換システムの目的の１つは、スイッチすなわちクロスバ１２の貴重な帯域幅（いわゆる稀少リソース）が効率的に使用されるように、スイッチすなわちクロスバ１２の利用度を最大化することである。交換システムの第２の目的は、サービス処理品質（ＱｏＳ）保証に依拠して顧客のためのパケットをサービス処理することである。交換システムのさらに別の目的は、交換システム１０を通して所定のパケットを伝送する前に、受忍できないほど長い時間にわたってそのパケットが交換システム１０内で待機させられることを防ぐことである。改良された方法とシステムによって、こうした目的を実現する必要性がある。
【０００４】
図１の交換システム１０内のスイッチすなわちクロスバ１２を介するデータ伝送のためのタイムスロットのサイズが、一般的に、単一のタイムスロット内で送ることが可能なデータの量を決定する。パケットサイズが大きく変動する、図１の交換システム１０のような現在実現されている交換システムにおいては、データ伝送のためのタイムスロットサイズを選択するために、一般に２つの方法が使用されている。第１の方法は、待ち行列中の大半の情報パケットが所定のタイムスロットの期間中にスイッチすなわちクロスバ１２を介して伝送できるほどに十分に大きいタイムスロットサイズを使用することである。しかし、この方法の問題点は、システム１０の利用度が低いということである。各タイムスロットが十分に詰まっていない可能性が高く、したがって、一般に高いコストを要する利用可能な帯域幅が未使用状態におかれることになる。
【０００５】
タイムスロットサイズを選択するために使用される第２の方法が、第１の方法で使用されるタイムスロットサイズよりも小さいタイムスロットサイズを使用することである。しかし、この場合には、タイムスロットよりも大きいパケットは、そのパケットの各セグメントが単一のタイムスロット内において交換システム１０を通過できるように、２つ以上のセグメントに分割されなければならない。この第２の方法は、上述の第１の方法に関連した利用度の低さという問題を低減させることができる。しかし、この第２の方法は、入力端Ｉ１、Ｉ２、Ｉ３においてパケットを複数のセグメントに分割（セグメント化）することと、その次に出力端Ｅ１、Ｅ２、Ｅ３においてそのセグメントを再構成（再アセンブリ）することが必要である。こうしたセグメント化と再アセンブリは、交換システム１０の性能を制限するおそれがある。
【０００６】
帯域幅の利用度を最大化し、ＱｏＳ保証を確実なものにし、パケットが交換システム内で不確定的に待機させられることを防止すると同時に、その方法とシステムが「適正」な仕方で動作することを確実にするように帯域幅を適正に割り当てる、リンクを介する帯域幅を割り当てる方法とシステムとが必要とされている。最後に、セグメント化と再アセンブリという問題を生じさせることなしにデータ伝送のためのタイムスロットの使用度を最大化するための方法とシステムとが必要とされている。
【課題を解決するための手段】
【０００７】
本発明の一実施形態が、共用リンクを介する伝送のためにパケットを選択する方法に関する。この方法の実施形態では、共用リンクを介する伝送のためにパケットを選択する方法であって、複数入力端のうちの各入力端内の複数待ち行列の各々における先出しパケットに対する優先度を決定するステップと、１つの所定の出力端向けの各入力端の待ち行列内の先出しパケットの各グループに対して、第１の優先度を持つ先出しパケットを選択するステップと、所定の出力端に向けられた、第１の優先度を持つ所定の出力端に向けられた、第１の優先度を持つ選択された先出しパケットの各サブセットに対して、第２の優先度を持つ先出しパケットを選択するステップと、第２の優先度を持つ選択された先出しパケットを、少なくとも１つの入力端から共用リンクを介して伝送するステップを有することを特徴とする。
【０００８】
本発明の別の実施形態が、共用リンクを介したサービス処理のために待ち行列を選択する方法に関する。この方法は複数の入力端内の各待ち行列に対して、データ伝送向けの１つの所定のタイムロットに対して瞬時的に成り立つ優先度を決定するステップと、１つの所定の出力端向けのパケットを持つ複数の入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択するステップと、所定のタイムスロット中で共用リンクを介して、各グループに対して第１の優先度を持つ選択された待ち行列をサービス処理するステップを有することを特徴とする。
【０００９】
本発明の別の実施形態が、共用リンクを介するサービス処理のために待ち行列を選択する方法に関する。この方法の実施形態では複数の入力端内の各待ち行列に対して、データ伝送に対する所定のタイムスロットに対して瞬時的に成り立つ優先度を決定するステップと、１つの所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択するステップと、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ待ち行列を選択するステップと、所定のタイムスロット中で共用リンクを介して、各サブセットに対して第２の優先度を持つ選択された待ち行列をサービス処理するステップを有することを特徴とする。
【００１０】
本発明の別の実施形態は、共用リンクを介するサービス処理のために待ち行列を選択するシステムに関する。このシステムの実施形態では（ａ）入力端内の各待ち行列に対して、データ伝送用の所定のタイムスロット中瞬時的に成り立つ優先度を決定するための、そして、（ｂ）所定の出力端向けのパケットを有する入力端内の待ち行列の各グループに対して第１の優先度を持つ待ち行列を選択するための入力端内の計量モジュールと、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択するためのアービトレーションモジュールとを有し、第２の優先度を持つ選択された待ち行列は、共用リンクを介するサービス処理のための待ち行列であることを特徴とする。
【００１１】
本発明の別の実施形態が所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択し、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ待ち行列を選択し、所定のタイムスロット中に共用リンクを介して、各サブセットに対して第２の優先度を有する選択された待ち行列をサービス処理するようにマイクロプロセッサに指示するものであることを特徴とするコンピュータ可読媒体が提供される。
【００１２】
本発明の別の実施形態が、共用リンクを介するサービス処理のために待ち行列を選択するシステムに関する。このシステムの実施形態では複数入力端の中の各待ち行列に対して、データ伝送のための所定のタイムスロット中瞬時的に成り立つ優先度を決定する手段と、１つの所定出力端向けのパケットを持つ各入力端内の待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択する手段と、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ待ち行列を選択する手段と、所定のタイムスロット中に共用リンクを介して、各サブセットに対して第２の優先度を有する選択された待ち行列をサービス処理する手段を有することを特徴とするシステムを提供する。
【００１３】
本発明の別の実施形態は共用リンクを介するサービス処理のために待ち行列を選択する方法に関する。このシステムの実施形態では、各待ち行列は所定のタイムスロット中瞬時的に成り立つデータ伝送に対する優先度を有する、すなわち１つの所定出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列に対する情報を各入力端から受け取るステップと、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択するステップと、所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択するステップを有することを特徴とする。
【００１４】
本発明のさらに別の実施形態は、共用リンクを介するサービス処理のために待ち行列を選択する装置に関する。この実施形態では、各待ち行列は所定のタイムスロット中瞬時的に成り立つデータ伝送に対する優先度を有し、プログラムを記憶するメモリと、メモリと通信するプロセッサとを有し、ここで、該プロセッサは、下記動作を行うよう、プログラムによって指示されるものである、すなわち、所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列に対する情報を各入力端から受け取り、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択し、所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択するよう、プログラムによって指示される。
【００１５】
本発明のさらに別の実施形態は、共用リンクを介するサービス処理のために待ち行列を選択するコンピュータ可読媒体に関する。ここで、各待ち行列はデータ伝送のための所定のタイムスロット中瞬時的に成り立つ優先度を有する。この可読媒体は下記の動作を行うようマイクロプロセッサに指示する命令を記憶するものである、すなわち、１つの所定出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列についての情報を各入力端から受け取り、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットから、第２の優先度を持つ待ち行列を選択し、所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択するようマイクロプロセッサが指示する命令を記憶する。
【００１６】
本発明の別の実施形態は、共用リンクを介するサービス処理のために待ち行列を選択する方法である。この方法の実施形態は、複数入力端の中の各待ち行列に対して、データ伝送用の１つの所定のタイムスロット中瞬時的に成り立つ優先度を決定することを特徴とする。ここで上記方法は、各入力端内において、１つの所定出力端における１つの所定ポート向けのパケットを持つ待ち行列の各グループに対して、第１の優先度を持つ待ち行列を選択することを特徴とする。このグループ内の待ち行列は、種々のサービスクラスを持つことができる。次に、アービタチップ内において、第１の優先度を持ちかつ同じ所定の出力端向けのパケットを持つ選択された待ち行列の各サブセットに対して、第２の優先度を持つ１つの待ち行列を選択する。この選択は同じ所定の出力端の異なるポート向けのパケットを持つ待ち行列からのものであってよい。
【００１７】
次にアービタチップ内において、第２の優先度を持ちかつ同じ所定の出力端向けのパケットを持つ複数の入力端からの選択された待ち行列の各サブセットに対して、第３の優先度を持つ待ち行列を選択する。所定のタイムスロット中に共用リンクを介して、各サブセットに対して第３の優先度を持つ選択された待ち行列をサービス処理することを特徴とする。
【００１８】
本発明の別の実施形態は、共用リンクを介する帯域幅割り当て方法に関する。この方法の実施形態では、待ち行列グループの中の各待ち行列に対する待ち行列計量情報を維持するステップと、（ａ）待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて各待ち行列に対する保証レートを計算するステップと、（ｂ）待ち行列が所定のタイムスロット中にサービス処理される場合に、適切な量だけ待ち行列のクレジット値を調整することと、所定のタイムスロットの後に保証レートに基づいて幾らかの量だけ待ち行列のクレジット値を調整することとによって、各待ち行列に関連するクレジットを調整するステップと、帯域幅を割り当てる働きをする待ち行列に対する優先度を決定するために、クレジット値、部分パケット情報、シェーピングリミット、および、待ち行列が空であるかどうかの表示から成るグループの中の１つ以上のうちから選択される待ち行列ステート状態情報を使用するステップとを有することを特徴とする。
【００１９】
本発明の別の実施形態は、共用リンクシステムの出力端に対する帯域幅を保証する方法に関する。この方法の実施形態では、出力端向けのパケットを持つ、待ち行列グループ内の各待ち行列に対して、待ち行列計量に対する情報を維持するステップと、待ち行列計量情報と出力端に対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、帯域幅を割り当てるために使用される、待ち行列グループ内の各待ち行列に対するクレジット値を計算するために、保証レートを使用するステップを有し、上記待ち行列は、共用リンクシステムの１つ以上の入力端内に常駐しているものであることを特徴とする。
【００２０】
本発明の別の実施形態は、共用リンクシステムの入力端に対する帯域幅を保証する方法に関する。この方法の実施形態では、入力端内の待ち行列グループの中の各待ち行列に対する待ち行列計量についての情報を維持するステップと、待ち行列計量情報と入力端に対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、帯域幅を割り当てるために使用される、待ち行列グループ内の各待ち行列に対するクレジット値を計算するために、保証レートを使用するステップを有し、上記待ち行列内のパケットは共用リンクシステムの１つ以上の出力端向けのものであることを特徴とする。
【００２１】
本発明の別の実施形態は、共用リンクを介する帯域幅の割当てに使用するための保証レートを決定する方法であって、待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を維持するステップと、待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、帯域幅を割り当てるために使用される保証レートを、各待ち行列に関連する入力端に送ることを特徴とする。
【００２２】
本発明の別の実施形態は、共用リンクを介する帯域幅の割当てに使用するための保証レートを決定する装置に関する。この装置の実施形態では、プログラムを記憶するメモリと、メモリと通信するプロセッサを有し、該プロセッサは、プログラムによって下記の動作を行うように指示されるものである、すなわち、待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を維持し、待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算し、帯域幅を割り当てるために使用される保証レートを、各待ち行列に関連する入力端に送るようにプログラムによって指示されるものである。
【００２３】
本発明の実施形態は、共用リンクを介する帯域幅を割り当てる方法に関する。この方法の実施形態では、待ち行列グループ内の各待ち行列に対する待ち行列計量についての情報を求めるステップと、待ち行列計量情報を帯域幅アロケータモジュールに伝送するステップと、帯域幅アロケータモジュールからグループ内の各待ち行列に対する保証レートを受け取るステップと、（ａ）待ち行列が所定のタイムスロット中にサービス処理される場合に待ち行列のクレジット値を適切な量だけデクリメントするステップと、（ｂ）所定のタイムスロットの後に待ち行列の保証レートに基づいて幾らかの量だけ待ち行列のクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整するステップと、帯域幅を割り当てる働きをする、グループ内の各待ち行列に対する優先度を、クレジット値を使用して決定するステップとを有することを特徴とする。
【００２４】
共用リンクを介する帯域幅を割り当てる方法に関する。この方法の実施形態では、待ち行列計量情報と保証された帯域幅の大きさとに基づいて、少なくとも１つの入力端内の各待ち行列に対する保証レートを計算するステップと、各待ち行列に対する優先度を、所定のタイムスロットの期間中に共用リンクに接続するために計算するステップと、各待ち行列の優先度に基づいて、所定のタイムスロットの期間中にサービス処理するために少なくとも１つの待ち行列を決定するステップを有し、上記の優先度は、所定のタイムスロットに対して瞬時的に成り立つものであり、また各待ち行列に対する保証レートに基づいていることを特徴とする。
【００２５】
共用リンクを介する帯域幅を割り当てるシステムに関する。このシステムの実施形態では、待ち行列計量情報と保証された帯域幅の大きさとに基づいて少なくとも１つの入力端内の各待ち行列に対する保証レートを計算する帯域幅アロケータモジュールと、所定のタイムスロット中に共用リンクと接続するために、入力端内の各待ち行列に対して優先度を計算する各入力端内の計量モジュールであって、各待ち行列に対する優先度は所定のタイムスロットに対して瞬時的であり、そして、各待ち行列に対する保証レートに基づいている計量モジュールと、各待ち行列の優先度に基づいて所定のタイムスロットの期間中にサービス処理するために、少なくとも１つの待ち行列を決定するアービトレーションモジュールを備えることを特徴とする。
【００２６】
本発明の別の実施形態は、共用リンクを介する帯域幅を割り当てるシステムに関する。このシステムの実施形態では、所定のタイムスロット中に共用リンクと接続するための優先度を入力端チップ内で各待ち行列に対して計算するための、複数の待ち行列と計量モジュールとを含む入力端チップであって、各待ち行列に対する優先度は所定のタイムスロットに対して瞬時的であり、そして、各待ち行列に対する保証レートに基づいている入力端チップと、（ａ）待ち行列計量情報と保証された帯域幅の大きさとに基づいて１つ以上の入力端チップ内の各待ち行列に対する保証レートを計算する帯域幅アロケータモジュールと、（ｂ）各待ち行列の優先度に基づいて所定のタイムスロットの期間中にサービス処理するために少なくとも１つの待ち行列を決定するアービトレーションモジュールとを含むアービタチップを備えることを特徴とする。
【００２７】
本発明の実施形態は、共用リンクを介する帯域幅を割り当てる方法に関する。この方法の実施形態では、待ち行列のグループ内の各待ち行列に対する待ち行列計量についての情報を維持するステップと、待ち行列計量情報と待ち行列グループに対する保証された帯域幅の大きさとに基づいて待ち行列グループ内の各待ち行列に対する保証レートを計算するステップと、各入力端が待ち行列に対する保証レートを使用して入力端内の各待ち行列に対する優先度を計算することが可能である、各待ち行列に関連する入力端に対して、各待ち行列に対する保証レートを送るステップと、所定の出力端向けのパケットを持つ各入力端内の待ち行列の各グループから選択された第１の優先度を持つ少なくとも１つの待ち行列に対する情報を各入力端から受け取るステップと、第１の優先度を持ちかつ所定の出力端向けのパケットを持つ待ち行列の各サブセットに対して、第２の優先度を有する待ち行列を選択するステップと、所定のタイムスロット中の共用リンクを介するサービス処理のために、第２の優先度を持つ待ち行列を選択することを特徴とする。
【００２８】
本発明の別の実施形態は、共用リンクを介する帯域幅を割り当てる方法に関する。この方法の実施形態では、入力端内の各待ち行列に対する待ち行列計量についての情報を求めるステップと、帯域幅アロケータモジュールに待ち行列計量情報を伝送するステップと、待ち行列計量情報を少なくとも部分的に使用して計算された各待ち行列に対する保証レートを帯域幅アロケータモジュールから受け取るステップと、待ち行列が所定のタイムスロット中にサービス処理される場合に、待ち行列のクレジット値を適切な量だけデクリメントするステップと、所定のタイムスロットの後に待ち行列の保証レートに基づいて幾らかの量だけ待ち行列のクレジット値をインクリメントすることとによって、各待ち行列に関連するクレジット値を調整するステップと、所定のタイムスロットに対して瞬時的に成り立つ優先度を、入力端内の各待ち行列に対して決定するステップと、所定の出力端向けのパケットを持つ入力端内の待ち行列の各グループに対して、第１の優先度を持つ少なくとも１つの待ち行列を選択するステップと、第１の優先度を持つ入力端内の各待ち行列に対する情報をアービトレーションモジュールに送るステップと、入力端がどの出力端と所定のタイムスロットの期間中に通信することになるかを決定する第２の優先度を持つ待ち行列に対する情報を、アービトレーションモジュールから受け取ることを特徴とする。
【００２９】
本発明の別の実施形態は、共用リンクを介して待ち行列をサービス処理する方法に関する。この方法の実施形態では、入力端内の各待ち行列に対する先出しパケットのサイズを確認するステップと、いずれかの待ち行列内の先出しパケットのサイズが、データ伝送のための単一の所定のタイムスロット中の共用リンクを介する伝送には過大である場合に、先出しパケットを持つ待ち行列が、先出しパケット全体がデータ伝送のための２つ以上のタイムスロットの期間中に共用リンクを介して伝送されるようにデータ伝送のために選択される時に、共用リンクに対する接続を維持することを特徴とする方法。
【００３０】
本発明のさらに別の実施形態は、システム内の複数の待ち行列の各待ち行列に対する優先度を決定する方法に関する。この方法の実施形態では、優先度は共用リンクを介する帯域幅の割当てを決定し、最高の優先度を持つ待ち行列が所定のタイムスロットの期間中にサービス処理される。この方法は待ち行列が部分パケットを含む場合には、優先度を最高の優先度に設定するステップと、待ち行列が空である場合には、優先度を最低の優先度に設定するステップと、待ち行列がゼロよりも大きいクレジット値を持つ場合には、スケーリング因子によって除算されたクレジット値に等しい最高の優先度と最低の優先度との間の丸められた数として優先度を決定するステップを有する。
【発明を実施するための最良の形態】
【００３１】
Ａ．概要
本発明の実施形態は、データ伝送に対する通信品質ＱｏＳ保証を実現するために、所定のタイムスロットの期間中にどの待ち行列をサービス処理すべきかを適正に決定するために使用できる、構成設定可能であり、重み付けされた、分散型のスケジューリングの方法およびシステムを提供する。
１．システムアーキテクチャ
図２が本発明の実施形態によるシステム１００のブロック図を示す。図２のシステム１００は、一実施形態ではチップである幾つかのモジュール構成要素を含む。図２のシステム１００は、１つ以上の入力端チップ１０２と、１つ以上の出力端チップ１０４と、アービタチップ１０６と、パイプライン１１０を使用していずれかの入力端１０２をいずれかの出力端１０４に接続できる共用スイッチすなわちクロスバチップ、すなわち、共用リンク１０８とを含む。さらに、各入力端１０２は、それに関連する転送エンジンすなわち待ち行列マネージャ１１２を持つことが可能である。データのパケットがトラフィックリソース１１４から入力端１０２に入り、トラフィック出口１１６に出力端１０４を出て行く。複数の入力端１０２は、共用リンク１０８を介して複数の出力端１０４にリンクさせることができる。例えば、一実施形態では、６４個の入力端１０２が共用リンク１０８を介して６４個の出力端にリンクできる。
【００３２】
後述の実施形態は共用リンクシステムで動作し、この共用リンクシステムは、１つ以上の入力端１０２を１つ以上の出力端１０４に接続する共用リンク１０８を持つ。システム１００を介するデータ伝送のためのタイムスロット毎に、各出力端１０４は単一の入力端１０２だけにしか接続できないが、一方、単一の入力端１０２は１つ以上の出力端１０４に接続できる。したがって、本明細書全体を通して、術語「共用リンクシステム」は、１つの所定のタイムスロットの期間中に、データを転送するために１つ以上の出力端を単一の入力端に接続できるシステムを意味する。同様に、本明細書全体において、術語「共用リンク」は、データ伝送のためのタイムスロット毎に構成設定可能であり、かつ、データを伝送するために１つ以上の出力端を単一の入力端に接続するように共用リンクシステムで使用される、リンキング装置、スイッチ、すなわち、クロスバを意味するものとして使用される。
【００３３】
本発明の分子構成要素としてチップを使用する実施形態では、各チップは、信号処理ユニットとインタフェースユニットとを持つ集積回路チップであってよい。信号処理ユニットは、本明細書で説明されている動作を行うのに十分な任意の速度で実現できる。例えば、一実施形態では、１ＧＨｚプロセッサがアービタチップ１０６で使用される。本発明の各モジュールの機能はソフトウェアまたはハードウェアの形で実現できる。図３Ａは、レジスタファイル１５８を持つ入力端チップ１０２を示し、こうした入力端チップ１０２は、本発明の機能を実現するためにハードウェアモジュールまたはファームウェアモジュールをその内部に持つことが可能である。
【００３４】
各入力端１０２に接続されている各トラフィックソース１１４と、各出力端１０４に接続されている各トラフィック出力１１６は、例えば１０Ｇｂｐｓのような関連付けられた帯域幅レートを持つ。一実施形態では、入力端１０２または出力端１０４を共用リンク１０８に接続する各パイプライン１１０が、トラフィックソース１１４の帯域幅レートまたはトラフィック出力１１６の帯域幅レートよりも大の関連した帯域幅レートを持つ。したがって、パイプライン１１０は高速リンクであることが可能である。例えば、入力端１０２の中へのトラフィックソース１１４の帯域幅レートが１０Ｇｂｐｓである場合には、共用リンク１０８に接続するためにトラフィックソース１１４に関連するパイプラインは、１０−２０Ｇｂｐｓの帯域幅レートを持つことが可能である。この実施形態では、本発明のシステム１００は、入力端１０２の中への帯域幅レートまたは出力端１０４から外への帯域幅レートに比較して、リンク１０８の中に出入りする高速のパイプライン１１０を部分的に原因として、共用リンク１０８を介する帯域幅の保証を行うことが可能である。他の実施形態では、パイプライン１１０は、トラフィックソース１１４の帯域幅レートまたはトラフィック出力１１６の帯域幅レートと同じ帯域幅レートを持つ。
【００３５】
図３Ａは、単一のアービタチップ１０６と、入力端チップ１０２と、本発明の転送エンジンすなわち待ち行列マネージャ１１２とを示す、一実施形態のブロック図である。一実施形態では、アービタチップ１０６は帯域幅アロケータモジュール１５０と、アービトレーションモジュール１５２とを含む。図３Ａに示されているように、計量モジュール１５４が入力端１０２内にあり、この計量モジュール１５４は、優先度計算モジュール１５６と、レジスタファイル１５８と、計量更新モジュール１６０と、待ち行列長さモジュール１６２とを含む。一実施形態では、帯域幅アロケータモジュール１５０とアービトレーションモジュール１５２は、入力端１０２内に常駐し、待ち行列マネージャ１１２も同様に、入力端１０２内に常駐できる。図２のシステム１００のような、共用リンク１０８に取り付けられた複数の入力端１０２を持つシステムでは、単一のアービタチップ１０６が複数の入力端１０２をサービス処理するために使用されるように、別々のアービタチップ１０６内に帯域幅アロケータモジュール１５０とアービトレーションモジュール１５２とを持つことが望ましい。各モジュールの機能については詳細に後述する。
【００３６】
図３Ａの実施形態は、単一の入力端１０２と単一のアービトレータチップ１０６とを示す。しかし、さらに典型的には、単一のアービトレータチップ１０６が、図２のシステム１００のような、複数の入力端１０２を持つシステムで使用される。
【００３７】
システム１００の各入力端１０２は複数のバッファ待ち行列を含む。図２は、４つの待ち行列Ｑ１、Ｑ２、Ｑ３、Ｑ４を各々が持つ入力端１０２を示すが、任意の数の待ち行列が各入力端１０２内に存在することができる。一実施形態では、入力端チップ１０２は１０２４個の待ち行列を含む。各待ち行列に対するサービス処理クラス（ＣＯＳ）が、各待ち行列に関連する。各々のＣＯＳは、当該ＣＯＳに関連する待ち行列内のパケットに対する異なるレベルのサービス処理を表す。例えば図２の各入力端１０２内の待ち行列Ｑ１はＣＯＳ１を有し、待ち行列Ｑ２はＣＯＳ２を有し、待ち行列Ｑ３はＣＯＳ３を有し、待ち行列Ｑ４はＣＯＳ４を持つ。ＣＯＳ１は１ギガバイト／秒（Ｇｂｐｓ）の帯域幅レートに関連し、ＣＯＳ２は０．２５Ｇｂｐｓの帯域幅レートを持つことが可能であり、その他のＣＯＳも同様に関連することができ、したがって、相異なるＣＯＳを持つ待ち行列内のパケットが異なるレートでサービス処理を受ける。データのパケットが各入力端１０２に入ると、そのパケットは、そのパケットに対するＣＯＳに対応する適切な待ち行列内にバッファリングされる。待ち行列内の各パケットは所定の（しかし、必ずしも同一ではない）出力端向けのものである（すなわち、そのパケットは、所定の出力端に当該パケットを送る必要のあることを示すデータを含む）。各入力端１０２に関連する転送エンジン１１１は、入力端１０２の中に入るデータのパケットを入力端１０２内の１つの適切な待ち行列に転送する。
【００３８】
システム１００の各出力端１０３は、一般的に、パケットがトラフィック出口１１６を通して送り出される前に、共用リンク１０８を介して受け取ったパケットをバッファリングするための幾つかのＦＩＦＯ（先入れ先出し）バッファすなわちポートを含む。本発明の一実施形態では、単一のチップが、入力端１０２または出力端１０４として機能することが可能である。こうしたチップは、後述するように、入力端１０２の機能を果たすことが可能な入力端側と、出力端１０４の機能を果たすためのＦＩＦＯを持つ出力端側とを含む。
【００３９】
図３Ｂは、入力端１０２の待ち行列内のパケットの詳細図を示す。図３Ｂは、待ち行列Ｑ１、Ｑ２、Ｑ３を持つ単一の入力端１０２を示すが、上述したように、より多くの数の待ち行列が入力端１０２内に常駐してもよい。図３Ｂが略図の形で示しているように、各待ち行列Ｑ１、Ｑ２、Ｑ３は、その待ち行列内にバッファリングされた幾つかのパケットを含む。例えば、待ち行列Ｑ１はパケット１７０、１７２、１７３を含み、待ち行列Ｑ２はパケット１７４、１７６、１７８、１８０を含み、待ち行列Ｑ３はパケット１８２、１８４、１８６、１８８、１９０、１９２を含む。パケット１７０が待ち行列Ｑ１の先頭にあり、パケット１７４が待ち行列Ｑ２の先頭にあり、パケット１８２が待ち行列Ｑ３の先頭にある。この実施形態では、本発明のシステム１００の共用リンク１０８を介してデータが送られるべき各タイムスロット内において、単一のタイムスロットの中に収まる各待ち行列の先頭の１つまたは複数のパケット（１つまたは複数の先出しパケット）だけが、共用リンク１０８に対するアクセス権を求めて競い合う資格がある。したがって、その次のタイムスロットに対しては、図３Ｂに示すように、パケット１７０、１７４、１８２だけが、共用リンク１０８に対するアクセスを求めて競い合うために利用可能である。タイムスロットは固定された時間単位であり、各々のタイムスロット内において共用リンク１０８をデータ伝送のために構成できる。一実施形態では、タイムスロットが約２００−６５０ナノ秒に設定できるが、タイムスロットのサイズは個々の実施形態において様々である。例示している実施形態では、約４６０−１５００バイトのデータが２００−６５０ナノ秒のタイムスロット内において共用リンク１０８を介して伝送できる。
【００４０】
図３Ｂは、さらに、入力端１０２の待ち行列内のパケットが様々なサイズであってよいこと、そして、入力端１０２内の待ち行列のサイズも様々なサイズであってよいことをブロック図の形で示している。例えば、待ち行列Ｑ１内のパケット１７０は、待ち行列Ｑ２内のパケット１７４より大きく、そして、さらには待ち行列Ｑ３内のパケット１８２よりも大きいパケットサイズを持つ。さらに、待ち行列Ｑ３内のパケット１８２は待ち行列Ｑ２内のパケット１７４よりもサイズが大きい。このようなパケットサイズはバイトまたはビット単位で測定できる。図３Ｂは、さらに、この実施形態では共用リンク１０８を介するデータ伝送のための、単一のタイムスロットのサイズも示す。パケット１７０は単一のタイムスロットよりもサイズが大きく、一方、パケット１７４とパケット１８２は両方とも単一のタイムスロットのサイズより小さいかまたは等しいように見える。さらに、図３Ｂは、入力端１０２内の所定の瞬時における各待ち行列のサイズ（Ｑｌｅｎｇｔｈ）を示す。例えば、待ち行列Ｑ１は、待ち行列Ｑ２に対するＱｌｅｎｇｔｈＱ２よりは大きいけれども待ち行列Ｑ３に対するＱｌｅｎｇｔｈＱ３よりは小さいＱｌｅｎｇｔｈＱ１を持つ。図３Ｂは、少数のパケットだけが各待ち行列内に存在する単純化された入力端１０２を示すが、Ｑｌｅｎｇｔｈの概念が例示されている。Ｑｌｅｎｇｔｈは、所定の待ち行列内に所定の瞬時において格納されているデータのサイズの尺度であり、したがって、バイト単位で測定できる。図３Ｂに示す実施形態では、各待ち行列が、パケットのバッファリングに使用可能な同じ合計長さ（容量）を持つが、他の実施形態ではこれらの長さは変化してもよい。
２．システム動作の概要
図４Ａは本発明の動作の一実施形態を示す流れ図である。一般的に、本発明は、待ち行列に対する待ち行列計量情報に基づいて各待ち行列に対する保証レートを計算すること（ブロック２００）と、待ち行列に対する保証レートに基づいて所定のタイムスロットの期間中の各待ち行列に対する優先度を計算すること（ブロック２０２）と、各待ち行列の優先度に基づいて所定のタイムスロットの期間中にサービス処理するために待ち行列を決定すること（ブロック２０４）とを含む。
【００４１】
本明細書全体で使用されている術語「保証レート」は、一般的に、システム内において帯域幅を割り当てるために使用される待ち行列に対する更新レートを意味する。このような保証レートの単位は、例えばＧｂｐｓであってよい。保証レートは、各々の待ち行列に関連するクレジット値が時間経過に応じて増加するレートを制御するために使用されるので、各待ち行列に使用可能な帯域幅を制御する。各入力端の各待ち行列は、それに関連するクレジット値を有し、各々の待ち行列に対する保証レートは、待ち行列が所定のタイムスロットの期間中にサービス処理されない場合には、待ち行列に対するクレジット値を増加させるために使用できる。一方、クレジット値は、このシステムにおける各待ち行列に対する優先度を更新するために使用できる。本明細書の全体で使用されている術語「優先度」は、データ伝送のためのタイムスロットの期間中に所定の出力端と通信しようとする所定の待ち行列の要求を意味する。したがって、一般的に、各タイムスロットの期間中にサービス処理を受けるべき待ち行列は、各タイムスロットの期間中に各待ち行列に対して算出される優先度に基づいて決定される。所定の出力端との通信に対して高い優先度を持つ待ち行列は、例えば、同じ出力端との通信に対してより低い優先度を持つ待ち行列よりも前にサービス処理を受ける。図２の共用リンク１０８は、入力端と出力端の間の１対１の対応付けマッピングを割り当てるために優先度に基づいて各タイムスロットの間に再構成設定される。したがって、保証レートは、各待ち行列がどれだけ頻繁にサービス処理されるか、または、この代わりに、待ち行列のサブセットがどれだけ頻繁にサービス処理されるかを間接的に制御する。
【００４２】
この実施形態では、帯域幅アロケータモジュール１５０が、システム１００における各待ち行列に対する保証レートを計算するために使用される（図４Ａのブロック２００）。保証レートは、待ち行列長さモジュール１６２または待ち行列マネージャ１１２から受け取った何らかの待ち行列計量情報を使用して幾つかの方法によって計算される。保証レートを計算するために使用される待ち行列計量情報は、待ち行列のＱｌｅｎｇｔｈ（すなわち、バイト）、または、待ち行列に対するデータの到着レート（すなわち、バイト／秒）のような（これだけに限定されないが）待ち行列に対する情報である。待ち行列マネージャ１１２は、待ち行列に対するデータの到着レート情報を計算または追跡することができ、そして、待ち行列長さモジュール１６２は待ち行列の現在の長さすなわちサイズを計算することができる。保証レートの計算のための幾つかの方法については、図５−７Ｂを参照してより詳細に後述する。一般的に、保証レートを計算するために、図３Ａの待ち行列長さモジュール１６２（または、待ち行列マネージャ１１２）は、対応する入力端１０２の各待ち行列に対する待ち行列計量情報を測定して、帯域幅アロケータモジュール１５０に送る。例えば、図３Ａは、帯域幅アロケータモジュール１５０に送られる待ち行列に対するＱｌｅｎｇｔｈｓ  ５０を示す。その次に、帯域幅アロケータモジュール１５０は、後述の帯域幅割当て方法を使用して、システム１００の各入力端１０２の各待ち行列に対する保証レートを計算し、保証レート５２を対応する入力端１０２に送る。この保証レートは周期的に（すなわち、必ずしもタイムスロット毎にではなく）計算され、その次に、対応する入力端１０２に周期的に伝えることができる。
【００４３】
この実施形態では、各入力端１０２の計量モジュール１５４の計量更新モジュール１６０が、入力端１０２内の各待ち行列に対するクレジット値を更新するために保証レートを使用する。一実施形態では、計量更新モジュール１６０は、共用リンク１０８を介するデータ伝送のための各タイムスロットの期間中に、各待ち行列に対するクレジット値を更新する。図３Ａは、帯域幅アロケータモジュール１５０からレジスタファイル１５８を介して保証レート５２を受け取り、その次に、更新されたクレジット値５４をレジスタファイル１５８に伝送する計量更新モジュール１６０を示す。待ち行列についてのクレジット値５４または他の情報は、この実施形態における各待ち行列のサービス処理に対する優先度を計算するために使用される。クレジット値は、幾つかの方法によって計量更新モジュール１６０内において更新できる。一般的に、各タイムスロットの後でのキューイングの場合には、所定の待ち行列に対するクレジット値が増大する。クレジット値の増大は、待ち行列に対する対応する優先度を増大させ、したがって、その待ち行列が最終的にサービス処理されるように幾つかのタイムスロットにわたって待ち行列の優先度をインクリメントする。 この実施形態では、待ち行列が所定のタイムスロットの期間中にサービス処理される場合には、その待ち行列に対するクレジット値が、減少されて共用リンク１０８に対する接続が不確定的に維持されない（すなわち、待ち行列に対する優先度が低下させられる）。幾つかの方法が、待ち行列に対するクレジット値を更新するために使用でき、こうした方法の１つを、図８を参照してより大きい値に対して詳細に後述する。
【００４４】
この実施形態では、入力端１０２の計量モジュール１５４の優先度計算モジュール１５６は、各待ち行列が共有リンク１０８を介するサービス処理を受けることを求める場合のその各待ち行列の優先度を計算するために、待ち行列に対するクレジット値または他の情報を使用する（図４Ａのブロック２０２）。図３Ａは、入力端１０２の待ち行列に対するクレジット値５４をレジスタファイル１５８から受け取り、その次に優先度５６をアービトレーションモジュール１５２に送る優先度計算モジュール１５６を示す。各待ち行列の優先度は、一実施形態では、各待ち行列に対するクレジット値と同じ値であってよい。しかし、他の実施形態では、優先度は、各待ち行列に対するクレジット値がスケーリングされた値であり、優先度は、さらに、より詳細に後述するように、他の特徴に依拠して、単なるスケーリング以上の手法で変更されることも可能である。
【００４５】
この実施形態では、所定の入力端１０２からの優先度５６の幾つかが、図３Ａに示されるようにアービトレーションモジュール１５２に送られる。さらに、各出力端１０４は、そのＦＩＦＯの充満状態に対する情報をアービトレーションモジュール１５２に送る。その次に、アービトレーションモジュール１５２は、所定のタイムスロットの期間中に各出力端１０４に接続されるべき入力端１０２を決定する（図４Ａのブロック２０４）。図３Ａに示すように、アービトレーションモジュール１５２は出力５８を優先度計算モジュール１５６に送り返す。出力５８は、単純に、入力端１０２が１つの所定のタイムスロットの期間中にどの出力端１０４へのアクセスすることになるかを指定するものである。その次に、計量モジュール１５４は、入力端１０２がタイムスロットの期間中にアクセスする出力端１０４に基づいて、入力端１０２内のどの待ち行列にサービス処理すべきかを決定できる。
【００４６】
アービトレーションモジュール１５２内の各出力端１０４に対する入力端１０２の選択は優先度に基づいており、そして、この選択プロセスをアービトレーションと呼ぶことが可能である。一般的に、優先度５６は、１つの所定のタイムスロットの期間中にどの入力端１０２をどの出力端１０４に接続するかを決定し、そして、そのタイムスロットの期間中に入力端１０２内のどの待ち行列をサービス処理するかを決定する。一実施形態では、最高の優先度で所定の出力端１０４を要求する待ち行列を持つ入力端１０２が、１つのタイムスロットの期間中において、その所定の出力端１０４に対する接続のために選択される。さらに、出力端１０４を要求しかつ最高の優先度を持つ選択されたその入力端１０２内の待ち行列は、タイムスロットの期間中にサービス処理されるその入力端１０２内の待ち行列である。本発明の様々な実施形態において待ち行列の選択のために使用される幾つかの方法については、図９−１１に関連付けてさらに詳細に後述する。いずれの場合にも、入力端１０２と出力端１０４との間の対応付けマッピングによるタイムスロットの期間中の共有リンク１０の構成設定は、アービトレーションに従う。したがって、命令を含むメッセージ（図示していない）が、共有リンク１０８が生成すべき入力端と出力端との間の対応付けマッピングを示すために、タイムスロット毎に共有リンク１０８に送られる。その次に、共有リンク１０８は、その命令にしたがってタイムスロットの期間中に入力端と出力端との間の接続を確立する。
【００４７】
本発明の一実施形態では、最高の優先度レベルが、単一のタイムスロットよりも大きいパケットが中に含まれている待ち行列のためにリザーブされている。例えば、図３Ｂは、パケット１７０が所定のタイムスロットよりも大きいサイズを持つことを示す。本発明の一実施形態では、システム１００の共用リンク１０８を介する接続が、単一のタイムスロットよりも大きなパケット全体が中断なしに共用リンク１０８を介して連続的に伝送できるほど十分な期間の時間的長さにわたって維持される。このように維持された接続によっては、パケットが入力端１０２内で複数のパケットにセグメント化され、その次にパケットの全セグメントがリンク１０８を介して伝送された後に出力端１０４において再アセンブリが不要であることが保証される。こうしたシステムは、タイムスロットのサイズを適切な長さの時間に設定できることによって、共用リンク１０８の利用度を最大化する。すなわち、データ伝送のタイムスロットサイズは、共用リンク１０８の利用度が高いように十分に低いレベルに設定される。しかし、本発明のこの方法は、さらに、単一のタイムスロットよりも大きいパケットを伝送するために共用リンク１０８を介して単一または多重の接続を維持することによって、セグメント化と再アセンブリという問題を解決する。
【００４８】
部分パケット変数が、単一のタイムスロット内で共用リンクを介して伝送するには大きすぎるパケットを表すために、本発明のシステムで使用できる。こうした部分パケット変数は、待ち行列中にサービス処理されるべき現在のパケットが大きすぎて単一のタイムスロット内ではサービス処理不可能であるということと、パケット全体を伝送するのに十分な数のタイムスロットにわたって接続が共用リンク１０８を介して維持されなければならないということを示す。したがって、こうした部分パケット変数が所定の時点で待ち行列に関連付けられる場合には、最大の優先度レベルがその待ち行列に割り当てられることが可能である。
【００４９】
図３Ａの待ち行列マネージャ１１２は、一般的に、待ち行列をサービス処理し、１つの所定のタイムスロットの期間中に生じるイベントに依拠して待ち行列の状態に対する更新されたメッセージを送る。例えば、待ち行列マネージャ１１２は、パケットが待ち行列から送られる時に、計量更新モジュール１６０にデキュー通知６４を送る。これはデキューイベントである。さらに、待ち行列マネージャ１１２は、パケットが所定の待ち行列内に受け取られてバッファリングされる時に計量更新モジュール１６０にエンキュー通知６２を送る。これはエンキューイベントである。図３Ａは、さらに、優先度計算モジュール１５６から待ち行列マネージャ１１２に送られるデキュー要求６０を示す。このデキュー要求６０は、アービトレーションプロセスに基づいて所定のタイムスロット中にサービス処理するべき待ち行列を表す。したがって、待ち行列マネージャ１１２は、デキュー要求６０にしたがって待ち行列をサービス処理できる。
【００５０】
したがって、待ち行列マネージャ１１２によって生成されたイベントが上述の一連の計算を開始させ、待ち行列に対するクレジット値の更新とおそらくはＱｌｅｎｇｔｈの更新とを生じさせる。その次に、各待ち行列に対する優先度が、クレジット値、または、待ち行列に関連付けられた部分パケット変数のような他の情報に基づいて決定される。各入力端が各出力端を求める場合の優先度が、優先度計算モジュール１５６とアービトレーションモジュール１５２とを使用して決定される。これらの優先度は、一般的に、所定のタイムスロットの期間中に各出力端に関連付けるべき入力端を決定する。
【００５１】
計量モジュール１５４と待ち行列マネージャ１１２との機能がハードウェアの形で実施される実施形態では、上述したこれらの機能のタイミングは、約２００ナノ秒のタイムスロットサイズに対して次の通りである。リンク１０８のアービトレーションおよび構成設定の両方が、固定されたタイムスロットに基づいて行われる。しかし、システム内の待ち時間に基づき、アービトレーションが少数のタイムスロット分だけリンク１０８の構成設定に先行するのが好ましい。したがって、アービトレーションモジュール１５２は、タイムスロットの最初の約１００ナノ秒間にアービトレーションを行うことができ、その次に、所定のタイムスロットの期間中に各入力端１０２が通信するべき出力端１０４を表すメッセージが各入力端１０２に送られることが可能であり、この所定のタイムスロットは、そのメッセージが送られた後の約３００−５００ナノ秒であってよい。その次に、各入力端１０２は、更新された優先度情報によってアービタチップ１０６に応答する。さらに、各出力端１０４は、そのＦＩＦＯの充満状態に対する情報を送ることができる。例えば、図２は、この充満情報が介してして送ることができる出力端１０４とアービタチップ１０６との間の接続を示す。したがって、リンク１０８の実際の構成設定とパケットの伝送とが、入力端に対する出力端を含むメッセージを入力端１０２が受け取ってから短時間（この実施形態では３００−５００ナノ秒）後に起こる。
【００５２】
本発明の一実施形態では、各待ち行列に対する優先度はタイムスロット毎に更新され、各待ち行列に対する保証レートは、これよりも低い頻度で更新される。例えば、保証レートは１００タイムスロット毎に更新されることが可能である。システムに対するＱｏＳ保証は、２つ以上のタイムスロットから成る幾らか識別可能な時間間隔にわたって決定され、したがって、保証レートを使用して制御される帯域幅割当ては、所定の複数のタイムスロットにわたって平均して適正である必要があり、単一のタイムスロットまたは少数のタイムスロットに対しては適正でなくともよい。
【００５３】
図３Ａは、本発明の一実施形態による、動作中にシステム１００の各モジュールの間を流れるデータを示す。このデータは、上述の情報を表現するメッセージまたは信号である。上述したようにモジュール間を送られるメッセージは、先行のタイムスロット内において送られた情報からの更新された情報だけを含み、したがって二重データ伝送を排除し、モジュール間を伝送される情報の量が減少する。さらに、Ｑｌｅｎｇｔｈｓ  ５０と優先度５６とを含む単一のメッセージが、図３Ａに示されている別々のメッセージの代わりに、入力端１０２からアービトレータチップ１０６に送られる。さらに、アウトプット出力端５８と更新された保証レート５２とを含む単一のメッセージを、図３Ａに示されている別々のメッセージの代わりに、アービトレータチップ１０６から入力端１０２に送ることができる。
【００５４】
概略的に述べると、図４Ｂは、図４Ａよりも詳細に本発明の動作の一実施形態を示す流れ図である。この実施形態では、ブロック４０２で帯域幅アロケータ１５０がＱｌｅｎｇｔｈ情報を受け取る。ブロック４０４では、帯域幅アロケータ１５０は、待ち行列に対する保証レートを決定して、この保証レートを入力端チップ１０２に送る。この実施形態では、各待ち行列に対する保証レートが帯域幅アロケータ１５０内で計算されて１００タイムスロット毎に１回ずつ入力端チップ１０２に送られてもよい。ブロック４０６では、計量更新モジュール１６０が、待ち行列に対するクレジット値を更新するために、各待ち行列の保証レートを使用する。この実施形態では、クレジット値のこの更新はタイムスロット毎に生じてよい。ブロック４０８では、優先度計算モジュール１５６が、クレジット値、または、部分パケットが存在するかどうかといった待ち行列に対する他の情報に基づいて優先度を計算する。この優先度計算もタイムスロット毎に行なわれてもよい。ブロック４１０では、優先度計算モジュール１５６は、入力端がシステムの各出力端と通信することを要求する場合の優先度を決定し、または、他の実施形態では、優先度計算モジュール１５６が、各出力端に対して最高の優先度を持つ可能性がある複数の待ち行列を選択する。いずれの場合にも、これらの優先度を示す情報がアービトレーションモジュール１５２に送られる。この動作もタイムスロット毎に生じることが可能である。ブロック４１２では、アービトレーションモジュール１５２が、各出力端に対して入力端を決定するために優先度を使用し、この決定がタイムスロット毎に行われる。ブロック４１４では、優先度計算モジュール１５６が、入力端に対して選択された出力端にしたがってタイムスロット毎に待ち行列マネージャ１１２にデキュー要求を送り、待ち行列マネージャが適切な待ち行列をサービス処理する。ブロック４１６では、待ち行列マネージャ１１２が計量更新モジュール１６０にエンキュー／デキュー情報を送り、その次に、ブロック４０２で始まるプロセスが繰り返される。
Ｂ．保証レートの計算方法
幾つかの方法が、システム１００の入力端１０２の待ち行列に対する保証レートを計算するために、本発明の範囲内で使用できる。一般的に、保証レートは、帯域幅を割り当て、したがってＱｏＳ保証を維持するために使用される。本明細書では、帯域幅を保証する４つの方法、すなわち、（１）単一の待ち行列に対する帯域幅の保証、（２）出力端に対する帯域幅の保証、（３）入力端に対する帯域幅の保証、および、（４）待ち行列グループに対する帯域幅の保証を説明する。図５は、これらの帯域保証方法の中の最初の３つの方法を示す。
１．待ち行列帯域幅の保証
入力端内の所定の待ち行列Ｑに対する帯域幅を保証するために、この待ち行列に対する保証レートが適切な値ｇｑに設定され、この値ｇｑは幾つかのタイムスロットにわたって一定のままであってよい。この一定値ｇｑによっては、待ち行列に入るフローが少なくともｇｑに等しい到着レートを持つ場合には、任意の適度な期間の時間的長さにわたって、待ち行列が獲得する平均帯域幅がｇｑであることが保証される。例えば、一実施形態では、値ｇｑは、適度な期間の時間的長さにわたって０．２５Ｇｂｐｓの帯域幅レートを待ち行列に割り当てるために、０．２５Ｇｂｐｓの値に設定される。図５は、ブロック５０２における値ｇｑの設定の動作の様子を示す。
【００５５】
ハードウェアで保証レートを計算する一実施形態では、帯域幅アロケータモジュール１５０は、任意の所定の待ち行列に対する帯域幅を保証するために単純にレートレジスタにおいて適切な値を設定する。帯域幅アロケータモジュール１５０は、所定の待ち行列に対する到着レートを超えないようにレートｇｑの値を制限でき、このことにより、アイドル状態にある待ち行列が不都合に大きなクレジットを蓄積しておそらくは帯域幅を浪費しないことが確保される。
２．出力端における帯域幅の保証
図６Ａは、所定の出力端Ｅ１に対する帯域幅の保証の一実施形態を例示する。この実施形態では、単一の出力端Ｅ１に対する帯域幅が、１つ以上の入力端Ｉ１、Ｉ２のいずれかからのパケットを出力端Ｅ１に伝送できることが保証される。図６Ａの入力端Ｉ１は３つの待ち行列である待ち行列Ｑ１、Ｑ２、Ｑ３を含み、各待ち行列は所定のＣＯＳと所定の出力端とに関連する。例えば、この実施形態では、パケットは、そのパケットに対するＣＯＳに依拠するだけではなく、パケットが向けられるべき出力端にも依拠して、待ち行列内にバッファリングされる。例えば、図６Ａの待ち行列Ｑ１は出力端Ｅ１に関連しており、ＣＯＳ１を持つ。待ち行列Ｑ２は出力端Ｅ２に関連しており、ＣＯＳ２を有し、待ち行列Ｑ３は出力端Ｅ３に関連しており、ＣＯＳ３を持つ。入力端Ｉ２、Ｉ３は、入力端Ｉ１内の待ち行列と同じ関連を持つ３つの待ち行列Ｑ１、Ｑ２、Ｑ３によって同様にセットアップされている。
【００５６】
本発明のこの実施形態において保証レートを計算するために、同じ出力端Ｅ１に関連しており同じＣＯＳを持つ待ち行列が、帯域幅アロケータモジュール１５０にＱｌｅｎｇｔｈを伝える。例えば、図６Ａでは、入力端Ｉ１、Ｉ２、Ｉ３内の待ち行列Ｑ１の各々が帯域幅アロケータモジュール１５０にＱｌｅｎｇｔｈを伝える。その次に、これら３つの待ち行列に対する保証レートが、単一のサブセットまたはグループとして決定される。待ち行列に対する保証レートを決定するために、出力端ｊ（すなわち、出力端Ｅ１、Ｅ２、または、Ｅ３）向けるべき入力端ｉ（すなわち、入力端Ｉ１、Ｉ２、または、Ｉ３）内の待ち行列Ｑに対する保証レートがｇiｊ，ｑとして表されている。このレートｇiｊ，ｑは時間経過に応じて変化する。この方法は、ある期間の時間的長さにわたって平均化されたＦｊ，ｑ＝Σｉ：ｉｎｐｕｔｓｇiｊ，ｑ（ｔ）に等しい帯域幅を幾つかの出力端ｊに対して保証することによって、１つの出力端のリンクに対する帯域幅を保証できる。この事例では、ｉは全入力端にわたってまたは入力端のサブセット全体にわたって種々変化する。各々のｇiｊ，ｑ（ｔ）は、あるとすれば各入力端ｉ内の各待ち行列Ｑを含めて、出力端ｊ向けのデータを持つ関連する待ち行列Ｑに時間ｔ中割り当てられた帯域幅に相当する。このシステムは、Ｆｊ，ｑが、任意の所定の時点において個々の入力端に割り当てるべき（すなわち、各入力端内の待ち行列Ｑに割り当てられる）出力端帯域幅に匹敵することを保証する。
【００５７】
入力端ｉ内に含まれ出力端ｊ向けの待ち行列Ｑに対するＱｌｅｎｇｔｈは、Ｌiｊ，ｑ（ｔ）と表わせる。このＱｌｅｎｇｔｈの値は、帯域幅アロケータモジュール１５０に周期的に伝えられる。Ｆｊ，ｑが、待ち行列Ｑに対応するＣＯＳに対して出力端ｊにおいて保証された帯域幅である場合には、保証レートｇiｊ，ｑ（ｔ）はＦｊ，ｑ／Ｎであるように初期設定されるものである。ここでＮはこうした待ち行列Ｑを持つ入力端の数である（この実施形態では、出力端向けのものであり、ＣＯＳを持つ各入力端内の１つの待ち行列が存在するが、他の実施形態では、出力端向けのデータを有しかつＣＯＳを持つ２つ以上の待ち行列が使用される）。保証レートｇiｊ，ｑ（ｔ）は、後続のタイムスロット内で測定されるＱｌｅｎｇｔｈｓ  Ｌiｊ，ｑ（ｔ）に依拠して、次の通りにリセットまたは再計算されるものである。
【００５８】
【数１】
2004534462.tif 000003
すべてのｉに対して
この例における入力は入力端の数Ｎである。Σｋ：ｉｎｐｕｔｓＬkｊ，ｑ（ｔ）がゼロである（すなわち、待ち行列Ｑの全てが空である）場合には、保証レートｇiｊ，ｑ（ｔ）は、待ち行列Ｑを持つ全ての待ち行列ｉに対してＦｊ，ｑ／Ｎに設定される。その次に、更新された保証レートｇiｊ，ｑ（ｔ）は、対応する入力端ｉに送り返される。ハードウェアの形の実施形態では、その次に、待ち行列Ｑに対するレートレジスタが更新される。ソフトウェアによる実施形態では、待ち行列Ｑに対する保証レート変数ｇiｊ，ｑ（ｔ）が更新される。
【００５９】
図６Ａの実施形態を使用する所定の例として、入力端Ｉ１内の待ち行列Ｑ１に対するＱｌｅｎｇｔｈ  Ｌiｊ，ｑ（ｔ）が２００バイトであると仮定すると、出力端に対する帯域幅レートＦｊ，ｑは０．２Ｇｂｐｓであり、そして、２０００バイトに等しい合計Ｑｌｅｎｇｔｈ  Σｋ：ｉｎｐｕｔｓＬkｊ，ｑ（ｔ）を持つ待ち行列を含む３つの入力端が存在する。この例では、待ち行列Ｑ１に対する保証レートｇiｊ，ｑ（ｔ）は、
【００６０】
【数２】
2004534462.tif 000004
である。
【００６１】
図５は、ブロック５０４で検査されるようにΣｋ：ｉｎｐｕｔｓＬkｊ，ｑ（ｔ）がゼロである場合に、各入力端に対してブロック５０６において等しい値に保証レートを設定する動作を示す。ブロック５０８は、Σｋ：ｉｎｐｕｔｓＬkｊ，ｑ（ｔ）がゼロでない場合に、各入力端に対する個々の計算された値に保証レートを設定する動作を示す。
【００６２】
図６Ｂに示されている代替的実施形態では、各入力端内の１つより多くの待ち行列が所定のＣＯＳを有し、同じ出力端向けのデータを持つ。例えば、図６Ｂの待ち行列Ｑ１は出力端Ｅ１に関連し、ＣＯＳ１を持つ。待ち行列Ｑ５は、出力端Ｅ１に関連しており、ＣＯＳ１を持つ入力端Ｉ１内の第２の待ち行列である。入力端Ｉ２は、入力端Ｉ１内の待ち行列と同じ関連性を持つ５つの待ち行列Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５によって同様に構成されている。このような場合には、上述の数Ｎは、所定のＣＯＳを有し同じ出力端向けの待ち行列の数である。例えば、図６Ｂでは、４つの待ち行列がＣＯＳ１を有し、出力端Ｅ１向けの（２つが入力端Ｉ１内にあり、２つが入力端Ｉ２内にある）。この実施形態では、Ｎ＝４（所望のパラメータを持つ待ち行列の数）であり、Ｎ＝２（入力端の数）ではない。
【００６３】
図６Ｂは、さらに、同じ出力端向けのパケットを持つが相異なるＣＯＳを持つ待ち行列は入力端Ｉ１、Ｉ２を有することが可能であることを示す。例えば、図６Ｂは、待ち行列Ｑ１と待ち行列Ｑ２が両方とも出力端Ｅ１向けの（出力端Ｅ１向けのポケットを持つ）が、相異なるＣＯＳを持ち、すなわち、待ち行列Ｑ１の場合にはＣＯＳ１を持ち、待ち行列Ｑ２の場合にはＣＯＳ２を持つ。同じＣＯＳを持つ待ち行列からの情報だけが上述の計算に使用される。したがって、図６Ｂにおける、ＣＯＳ１を持つ、出力端Ｅ１向けの待ち行列に対する計算（Σｋ：ｉｎｐｕｔｓＬkｊ，ｑ（ｔ））における入力の数Ｎは、４であり、すなわち、入力端Ｉ１、Ｉ２の各々における待ち行列Ｑ１、Ｑ５である。入力端Ｉ１、Ｉ２の各々の中の待ち行列Ｑ２は、相異なるＣＯＳに基づき上述の計算には使用されない。したがって、出力端の出力帯域幅Ｆｊ，ｑもＣＯＳ１に関連付けられ、別の出力端の出力帯域幅の大きさがＣＯＳ２に関連付けできる。
【００６４】
上述の方法は、保証レートを計算するためにＱｌｅｎｇｔｈを使用した。保証レートを計算するために到着レートも使用できることを付け加える。こうした実施形態では、保証レートを計算するために、到着レート変数が上記の式と計算とにおいてＱｌｅｎｇｔｈ変数の代わりに使用されることになる。こうした実施形態では、到着レート情報は待ち行列マネージャ１１２（図３Ａ）からアービタチップ１０６に送ることできる。
３．入力端における帯域幅の保証
図７Ａは、１つの所定の入力端Ｉ１に対する帯域幅を保証する一実施形態を例示する。この実施形態では、単一の入力端Ｉ１に対する帯域幅が、入力端Ｉ１内の待ち行列からのパケットを出力端Ｅ１、Ｅ２、Ｅ３のいずれにも送れるように保証される。図７Ａの入力端Ｉ１は、６つの待ち行列、すなわち、待ち行列Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６を含み、各待ち行列は所定のＣＯＳに関連する。例えば、図７Ａの待ち行列Ｑ１はＣＯＳ１に関連する。待ち行列Ｑ２はＣＯＳ２に関連しており、他も同様である。帯域幅保証のこの実施形態では、各入力端Ｉ１、Ｉ２、Ｉ３の待ち行列Ｑ１、Ｑ２、Ｑ３は単一の出力端に関連する必要はない。例えば、ＣＯＳ１を持つ待ち行列Ｑ１は、システムの任意の出力端向けのパケットを持つことができる。図７Ａは、出力端Ｅ１向けの待ち行列Ｑ１内のパケットを示すが、待ち行列Ｑ１内のその次のパケットは異なる出力端向けであってよい。しかし、別の実施形態では、待ち行列Ｑは、待ち行列Ｑ内にバッファリングされているパケットのすべてが所定の出力端向けのように、その所定の出力端に関連してもよい。
【００６５】
本発明のシステムと方法の実施形態は、１つの所定の入力端に対する帯域幅を保証する。この場合には、幾らかの時間ｔにわたって平均化されたＥiｑ＝Σｊ：ｏｕｔｐｕｔｓｇiｊ，ｑ（ｔ）に等しい帯域幅が入力端ｉ（すなわち、１つの所定のＣＯＳを持つ入力端内の待ち行列のサブセット）に対して保証される。この実施形態では、Ｅiｑに等しい帯域幅が１つの入力端に対して保証され、このような帯域幅Ｅiｑを、相異なる出力端ｊにわたって均一または非均一に振り分けができる。所定の待ち行列が、任意の所定の時点において、１つの出力端向けのデータのパケットを含むことも含まないこともあるので、対応する待ち行列に対する保証レートｇiｊ，ｑ（ｔ）は、合計がＥiｑとなる定数に設定できない。図７Ａでは、ＣＯＳ１をすべてが持つ待ち行列Ｑ１、Ｑ３、Ｑ５が帯域幅アロケータモジュール１５０にＱｌｅｎｇｔｈを送り、その次に、これらの待ち行列の各々に対するレートがグループまたはサブセットとして決定されて、入力端Ｉ１に送り返される。
【００６６】
この実施形態では、出力端帯域幅に対する実施形態の場合と同様に、保証レートはＱｌｅｎｇｔｈに基づいて設定される。Ｑｌｅｎｇｔｈ  Ｌiｊ，ｑ（ｔ）は、１つの所定の入力端Ｉ１内の、出力端ｊに対応する１つの所定のＣＯＳにおける各待ち行列Ｑに対して決定される。この実施形態では、これらのＬiｊ，ｑ（ｔ）は、出力端帯域幅を保証する方法の場合とは異なって、単一の入力端内で局所的に利用可能である。保証レートｇiｊ，ｑ（ｔ）はＥiｑ／Ｍに初期化でき、ここでＭは所定のＣＯＳを持つ待ち行列の数である。一実施形態では、１つの所定の出力端に各々が関連しており所定のＣＯＳを持つ、単一の入力端内の多重の待ち行列が存在してもよい。別の実施形態では、１つの所定の出力端に関連して１つの所定のＣＯＳを持つ単一の待ち行列Ｑだけが、入力端内に存在することが可能である。さらに別の実施形態では、入力端Ｉ１内の待ち行列の各々は、それに関連したＣＯＳを持つことができるが、これらの待ち行列は１つの所定の出力端に関連していなくてもよい。いずれにしても、保証レートｇiｊ，ｑ（ｔ）は、次のように、後続のタイムスロット内において、Ｑｌｅｎｇｔｈ  Ｌiｊ，ｑ（ｔ）に依存して計算またはリセットできる。
【００６７】
【数３】
2004534462.tif 000005
すべてのｊに対して
Σｋ：ｏｕｔｐｕｔｓＬiｋ，ｑ（ｔ）がゼロである場合には、ｇiｊ，ｑ（ｔ）は待ち行列のすべてに対してＥｉｑ／Ｍに設定される。次に、更新された保証レートｇiｊ，ｑ（ｔ）の各々はその対応する入力端ｉに送り返される。ハードウェアによる実施形態では、次いで待ち行列Ｑに対するレートレジスタが更新される。ソフトウェアによる実施形態では、待ち行列Ｑに対する保証レート変数ｇiｊ，ｑ（ｔ）が更新される。
【００６８】
１つの所定の具体例として、図７Ａの実施形態の場合に、Ｑｌｅｎｇｔｈ  Ｌiｊ，ｑ（ｔ）が１００バイトであると仮定すると、入力端に対する帯域幅レートは０．５Ｇｂｐｓであり、入力端ｉ内のＣＯＳ１を持つ３つの待ち行列は、１０００バイトに等しい合計Ｑｌｅｎｇｔｈ  Σｋ：ｉｎｐｕｔｓＬkｊ，ｑ（ｔ）を持つ。この例では、待ち行列Ｑに対する保証レートｇiｊ，ｑ（ｔ）は次の通りである。
【００６９】
【数４】
2004534462.tif 000006
図７Ａを使用するこの実施形態では、入力端Ｉ１は、ＣＯＳ１を持つ３つの待ち行列Ｑ１、Ｑ３、Ｑ５を持つが、待ち行列Ｑ１、Ｑ３、Ｑ５の各々は相異なる出力端に関連する。例えば、待ち行列Ｑ１は出力端Ｅ１に関連しており、Ｑ３は出力端Ｅ２に関連する。しかし、別の実施形態では、入力端Ｉ１は、同じＣＯＳを持ち同じ出力端に関連する複数の待ち行列を持つ。さらに別の実施形態では、入力端Ｉ１内の待ち行列は所定の入力端に関連していなくてもよいが、１つの関連するＣＯＳを持つこともできる。
【００７０】
図５は、ブロック５１０において試験されたΣｋ：ｏｕｔｐｕｔｓＬiｋ，ｑ（ｔ）がゼロである場合に、ブロック５１２で各出力端に対して同じ値に保証レートを設定する動作を示す。ブロック５１４は、Σｋ：ｏｕｔｐｕｔｓＬiｋ，ｑ（ｔ）がゼロでない場合に、各待ち行列に対して個別の計算値に保証レートを設定する動作を示す。
【００７１】
上述の方法は、保証レートを計算するためにＱｌｅｎｇｔｈを使用した。保証レートを計算するためには到着レートも使用できることが付け加えられる。こうした実施形態では、到着レート変数が、保証レートを計算するために、Ｑｌｅｎｇｔｈ変数の代わりに上記の式および計算において使用される。こうした実施形態では、到着レート情報が待ち行列マネージャ１１２（図３Ａ）からアービタチップ１０６に送られる。
４．待ち行列グループに対する帯域幅の保証
図７Ｂは、待ち行列のいずれか任意のグループであることが可能な待ち行列のグループに対する帯域幅保証の一実施形態を例示する。この実施形態では、帯域幅は待ち行列グループに対して保証でき、この場合に待ち行列は相異なる入力端内に存在可能であり、相異なる出力端向けのパケットを持つことができる。さらに、このグループ中の待ち行列は同じＣＯＳまたは相異なるＣＯＳを持つことができる。帯域幅の合計量、またはトータルの大きさを待ち行列のＱｌｅｎｇｔｈに基づいて待ち行列に割り当てることができ、または、他の実施形態では、待ち行列に対するデータの到着レートに基づいて待ち行列に割り当てられる。
【００７２】
この実施形態の一例としての図７Ｂを参照すると、帯域幅が保証される待ち行列のグループが、入力端Ｉｌ内に待ち行列Ｑ１、Ｑ３を含み、入力端Ｉ２内に待ち行列Ｑ１、Ｑ４、Ｑ６を含む。このグループ内の待ち行列は同じ出力端向けでなく、同じＣＯＳを持たない。例えば、入力端Ｉ１内の待ち行列Ｑ１は、出力端Ｅ１のポート１向けのデータを含み、ＣＯＳ１を持ち、そして入力端Ｉ１内の待ち行列Ｑ３は、出力端Ｅ２のポート１向けのデータを含み、そして、ＣＯＳ３を持つ。入力端Ｉ２内の待ち行列Ｑ１は、出力端Ｅ１のポート１向けのデータを含み、ＣＯＳ１を持つ。この実施形態では、待ち行列グループ内に同様に存在する、入力端Ｉ２内の待ち行列Ｑ４と待ち行列Ｑ６も任意の特徴を持つ。
【００７３】
本発明のこの実施形態において保証レートを計算するために、任意の待ち行列グループに関連する待ち行列はＱｌｅｎｇｔｈを帯域幅アロケータモジュール１５０に伝える。例えば、図７Ｂでは、入力端Ｉ１内の待ち行列Ｑ１、Ｑ３と入力端Ｉ２内の待ち行列Ｑ１、Ｑ４、Ｑ６は各々にＱｌｅｎｇｔｈを帯域幅アロケータモジュール１５０に伝える。その次に、これら５つの待ち行列に対する保証レートは、単一のサブセットまたはグループとして求めることができる。各待ち行列に対する保証レートを求めるために、Ｎ個の待ち行列からなる待ち行列グループの中の待ち行列Ｑに対する保証レートをｇiｑと表す。このレートｇiｑは時間経過に応じて変化する。この方法は、ある期間の時間的長さにわたって平均化されたＦＡＲＢ＝Σｉ：ｉｎｐｕｔｓ  ｇiｑ（ｔ）に等しい帯域幅を保証することによって、待ち行列グループに対する帯域幅を保証することができる。この例では、ｉは、Ｎ個の待ち行列からなる待ち行列グループの中の待ち行列の各々に対して異なる。各々のｇiｑ（ｔ）は、関連する待ち行列Ｑに時間ｔにおいて割り当てられる帯域幅に対応する。このシステムは、Ｎ個の待ち行列からなる待ち行列グループ内の個々の待ち行列にわたって１つの所定の時点で割り当てられる帯域幅に匹敵するＦＡＲＢを保証する。
【００７４】
Ｎ個の待ち行列からなる待ち行列グループの中の待ち行列Ｑに対するＱｌｅｎｇｔｈはＬiｑ（ｔ）と表すことができる。これらのＱｌｅｎｇｔｈの値は周期的に帯域幅アロケータモジュール１５０に送られる。ＦＡＲＢがＮ個の待ち行列からなる待ち行列グループに対して保証されている帯域幅である場合には、保証レートｇiｑ（ｔ）はＦＡＲＢ／Ｎとして初期設定でき、ここでＮは待ち行列グループ内の待ち行列の数である。各待ち行列に対する保証レートｇiｑ（ｔ）は、次のように、後続のタイムスロット中に測定されるＱｌｅｎｇｔｈ  Ｌiｑ（ｔ）に依存してリセットまたは再計算できる。
【００７５】
【数５】
2004534462.tif 000007
それぞれの列に対して
この例では、入力がグループ内のＮ個の待ち行列にわたって変化する。Σｉ：ｉｎｐｕｔｓＬiｑ（ｔ）がゼロである（すなわち、グループ中の待ち行列すべてが空である）場合には、そのグループ中の待ち行列すべてに対して保証レートｇiｑ（ｔ）がＦＡＲＢ／Ｎに設定される。その次に、図７Ｂに示されているように、更新された保証レートｇiｑ（ｔ）の各々が、待ち行列に対応する入力端に送り返される。ハードウェアによる実施形態では、その次に、待ち行列Ｑに対するレートレジスタが更新される。ソフトウェアによる実施形態では、待ち行列Ｑに対する保証レート変数ｇiｑ（ｔ）が更新される。
【００７６】
図７Ｂの実施形態を使用する所定の例として、入力端Ｉ１内の待ち行列Ｑ１に対するＱｌｅｎｇｔｈ  Ｌiｑ（ｔ）が８００バイトであると仮定すると、待ち行列グループに対する帯域幅レートＦＡＲＢは０．８Ｇｂｐｓであり、２０００バイトに等しい合計Ｑｌｅｎｇｔｈ  Σｉ：ｉｎｐｕｔｓＬiｑ（ｔ）を持つそのグループ内の５つの待ち行列がある。この例では、入力端Ｉ１内の待ち行列Ｑ１に対する保証レートｇiｑ（ｔ）は、
【００７７】
【数６】
2004534462.tif 000008
である。
【００７８】
上述の方法は、保証レートを計算するためにＱｌｅｎｇｔｈを使用した。保証レートを計算するためには到着レートも使用可能なことを付け加えられる。こうした実施形態では、到着レート変数が、保証レートを計算するために、Ｑｌｅｎｇｔｈ変数の代わりに上記の式および計算において使用される。こうした実施形態では、到着レート情報が待ち行列マネージャ１１２（図３Ａ）からアービタチップ１０６に送られる。
Ｃ．クレジット値を更新する方法
本発明の一実施形態における、１つの所定の待ち行列に対するクレジット値を更新する方法の１つが、図８にブロック図の形で示されている。上述したように、クレジット値は、一般的に、各タイムスロットの後に未だサービス処理されていない待ち行列に対して増加し、したがって、こうした待ち行列に対する優先度が増大する。同様に、サービス処理された待ち行列は、その待ち行列に対する優先度が低下するように、その待ち行列がサービス処理されるタイムスロットの後に減少する１つの関連したクレジット値を持つ。一実施形態では、本発明の作用の前の各クレジット値の初期値はゼロであってよい。入力端の各待ち行列に対するクレジット値は一般的に各タイムスロット毎に更新される。したがって、待ち行列がサービス処理され終わった後に、クレジット値はその現在値（初期においてはゼロであるが、動作が開始した後は、クレジット値の現在値は大きな正数または大きな絶対値の負数であってよい）から減少する。クレジット値は、帯域幅アロケータモジュール１５０から受け取った待ち行列に対する保証レート５２を使用して、計量モジュール１５４の計量更新モジュール１６０内で更新できる。定常状態のシステムでは、全待ち行列に対するクレジット値は合計でゼロになり、このことは、待ち行列が所望の帯域幅レートを平均して受け取っているということを意味する。
【００７９】
図８は、本発明の実施形態において、入力端内の単一の待ち行列に対して１つの所定のタイムスロットの期間中に生じることがある３つの発生可能なイベント８００を示す。エンキューイベントが生じることがあり、このイベントはデータのパケットが待ち行列の中に入ることを意味する。デキューイベントが生じることがあり、このイベントは、待ち行列のサービス処理が済んでおり、パケットをその待ち行列から共用リンクに送ったということを意味する。第３のイベントがインクリメントイベントであり、このイベントは、この実施形態では各タイムスロットの期間中に生じる。単一のタイムスロットの期間中に、図８の３つのイベントの各々が待ち行列に対して生じることである。この実施形態におけるインクリメントイベントの場合には、図８のブロック８０２によって示されているように、待ち行列に対する保証レートを現在クレジット値に加算することによってクレジット値がインクリメントされる。ブロック８０４、８０６によって示されているように、新たなクレジット値が待ち行列に対する最大限界値（待ち行列に対するＣＯＳに基く）よりも大きい場合には、クレジット値は待ち行列に対する最大限界値にリセットされる。一実施形態では、インクリメントイベントは各々のタイムスロットの期間中に生じ、したがって各待ち行列は各タイムスロット後にその関連のクレジット値の分だけインクリメントされる。
【００８０】
待ち行列に対するクレジット値の最大限界値は、低いＣＯＳを持つ待ち行列に対するクレジット値が過剰に大きくなることを防止する。したがって、これらの待ち行列に対する優先度も上限を設けるとよい。これにより、低いＣＯＳを持つ待ち行列が、より高いＣＯＳを持つ待ち行列と同じレートではサービス処理されないことが保証される。
【００８１】
この実施形態では、イベントがデキューイベントである場合に、待ち行列に対するＱｌｅｎｇｔｈはより小さくなり、したがって、ブロック８１０によって示されているように、待ち行列に対するＱｌｅｎｇｔｈが更新される。新たな１つまたは複数のパケットがサービス処理のために待ち行列の先頭に位置し、そして、ブロック８１２に示されているように、この１つまたは複数のパケットのサイズが更新される。さらに、この新たなパケットが所定のタイムスロットよりも大きい場合には、ブロック８１４に示されているように、部分パケット変数が更新される。部分パケット変数は、共用リンク１０８への伝送が、いったん開始されると、単一のタイムスロットよりも大きいパケットが中断なしに共用リンク１０８を介して伝送されるように、待ち行列に対して維持されなければならないということを意味する。その次に、ブロック８１６によって示されているように、待ち行列に対するクレジット値が減少する。一実施形態では、クレジット値は、送られるパケットの数の関数として（すなわち、１つより多くのパケットが１つのタイムスロットの期間中に送られる場合に）、または、タイムスロットの期間中に送られるバイトの関数として減少する。別の実施形態では、クレジット値は、単一のタイムスロットの期間中に送られるデータの量（すなわち、バイト単位またはビット単位）だけ減少する。したがって、クレジット値は、帯域幅がその他の待ち行列に対して再び割り当て可能なように適切に減少させる。この実施形態では、インクリメントイベントもタイムスロット後に生じ、この結果として、クレジット値は、（例えば）単一のタイムスロットの期間中に送ることができるバイトの数だけデキューイベントに対して減少し、その次に、インクリメントイベントの待ち行列に対する保証レートだけ増加される。更新されたクレジット値が、ブロック８１８で判定された時に、待ち行列に対するＣＯＳに基づく待ち行列に対する最小限界値よりも小さい場合には、ブロック８２０においてクレジット値が待ち行列に対する最小限界値にリセットされる。
【００８２】
最小のクレジット値が、確実に所定のＣＯＳを持つ待ち行列に対する優先度が過度に小さくならないようにするために使用される。このことにより、待ち行列が十分な頻度でサービス処理されないことが防止できる。
【００８３】
イベントがエンキューイベントである場合には、待ち行列に対するＱｌｅｎｇｔｈがゼロであると示されたかどうかの判定が行われる（ブロック８３０）。待ち行列の現在のＱｌｅｎｇｔｈがゼロである場合には、先行タイムスロットの期間中はその待ち行列内にはパケットが存在しなかった。パケットがエンキューイベントの期間中に待ち行列内に入ったので、待ち行列に対するパケットサイズは、待ち行列に対する部分パケット変数と共に更新される必要がある（ブロック８３２、８３４）。Ｑｌｅｎｇｔｈがゼロでない場合には、パケットが待ち行列の先頭に存在し（そして、先行のタイムスロットの期間中にも存在した）そして、パケットサイズと部分パケット変数とが１つの先行タイムスロットの期間中にすでに設定されている。図８のブロック８３６は、待ち行列内に入れられたデータパケットに基づいてＱｌｅｎｇｔｈを更新する動作を示す。インクリメントイベントも、デキューイベント、エンキューイベントと同じタイムスロットの期間中に生じる。
Ｄ．待ち行列の優先度を決定する方法
クレジット値が待ち行列に対して更新された後に、出力端への接続の必要性もしくは要求度を示す各入力端内の各待ち行列に対する優先度を決定できる。上述したように、そして、より詳細に後述するように、この優先度は、入力端と出力端との間の共用リンク１０８の対応付けマッピングを計算するために使用できる。
【００８４】
一実施形態では、待ち行列に対する優先度が０から１５までの１６ポイントレベル上でスケーリングされる。この実施形態では、待ち行列に対する優先度は、このスケーリングされたレベル上で待ち行列に対するクレジット値から決定される。例えば、１つの所定の待ち行列に対するクレジット値が１Ｇｂｐｓのレベルになっている場合には、その待ち行列に対する優先度は５のレベルに設定できる。そして、第２の待ち行列に対するクレジット値が２Ｇｂｐｓである場合には、その第２の待ち行列に対する優先度は１０のレベルにできる。この実施形態では、負のクレジット値が、ゼロまたは１のような低い優先度に設定される。この実施形態では、最高の優先度を持つ待ち行列は、所定のタイムスロットの期間中にサービス処理されるべき待ち行列である。クレジット値を優先度に変換することにより、入力端Ｉ０２からアービタチップ１０６に送るべきデータの量を最小化することが可能である。例えば、クレジット値は１，０００，０００，０００を超えるサイズであり、一方、このようなクレジット値に対して対応する優先度は１０であることが可能である。優先度が１６ポイントスケール上でスケーリングされる場合には、ハードウェアによる実施形態において、４ビットのレジスタが優先度のために使用できる。
【００８５】
クレジット値の更新に関連して上述したように、所定の待ち行列に対するクレジット値は、待ち行列に対するＣＯＳに依存して制限することが可能である。例えば、ＣＯＳ１を伴う待ち行列は、１６ポイントスケール上の５という最低優先度レベルに相当することが可能な所定の最小クレジット値に制限されることができる。同様に、ＣＯＳ８を伴う待ち行列は、１６ポイントスケール上の１２という最高優先度レベルに相当することが可能な所定の最大クレジット値に制限されることが可能である。
【００８６】
ゼロから１５の１６ポイント優先度スケールを使用する一実施形態では、ゼロという優先度は、空であり（したがって）共用リンク１０８を介して伝送されるパケットを持たない待ち行列のためにリザーブされている。同様に、１５である最高の優先度は部分パケットのためにリザーブ可能である。上述したように、パケットが単一のタイムスロット内において共用リンク１０８を介して伝送するには大きすぎる場合には、部分パケット変数が待ち行列に関連付けられる。パケットを持つ待ち行列が最終的に共用リンク１０８へのコネクションもしくは接続を獲得すると、待ち行列は共用リンク１０８に接続され続け、そして、パケットがセグメント化および再アセンブリなしに共用リンク１０８を介して連続的に伝送できるように、その次のタイムスロット中の待ち行列に対して最高の優先度が設定される。
【００８７】
次の表１が、クレジット値から待ち行列に対する優先度への変換の別の実施形態を示す。この実施形態では、クレジット値から優先度への変換は、クレジット値から優先度への単純なスケーリング以上のものを含む。待ち行列が空であるかどうか、そして、待ち行列が過剰にサービス処理されてしまったかどうかといった他の待ち行列情報も、考慮に入れることができる。したがって、表１は、条件の１つが満たされる場合に待ち行列に割り当てできることが優先度と共に、幾つかの条件を含む。この実施形態では、上述したように、各待ち行列は、それに関連するクレジット値Ｃ（ｑ）を持つ。スケーリング因子Ｓが、より大きなクレジット値をより小さい優先度にスケーリングするために使用される定数である。
【００８８】
【表１】
2004534462.tif 000009
表１の条件１が示すように、この実施形態では、待ち行列中のパケットが先行タイムスロットからの部分パケットである場合には、その待ち行列に対する優先度が最高の優先度ＭＡＸＰＲＩに設定される。ゼロから１５までの１６ポイントスケール上では、ＭＡＸＰＲＩは１５である。一実施形態では、ＭＡＸＰＲＩが割り当てられるこうした部分パケットは、そのパケットに関連付けられた部分パケット変数を持つ。これとは逆に、表１の条件５が示すように、空である待ち行列はゼロの優先度を割り当てられる。これは、ゼロの優先度を持つ待ち行列が所定のタイムスロットの期間中にサービス処理されないことを保証する最低の優先度である。
【００８９】
表１の条件５は、条件を満たせば優先度をゼロ（すなわち、最低の優先度）に設定する第２の条件を持つ。クレジット値Ｃ（ｑ）が待ち行列に対するシェーピングリミットＳｌｉｍｉｔよりも小さい場合には、優先度はゼロに設定される。このシェーピングリミットＳｌｉｍｉｔは、待ち行列が幾らかの期間の時間的長さにわたって過大な帯域幅を受けることがないように優先度をスケーリングするために使用されるパラメータである。例えば、保証レートは、待ち行列が受け取るべき最小レートＦｍｉｎである。一方、最大レートＦｍａｘは、待ち行列が受け取るべき最大レートである。もちろん、単一のタイムスロットよりも長い識別可能な時間的な長さにわたって受け取る帯域幅を、これらのレートが得られるかどうかを決定するために測定しなければならない。例えば、５０マイクロ秒の時間間隔は、最小レートＦｍｉｎが得られるべきであり、そして最大レートＦｍａｘを超えてはならない時間間隔である。５０マイクロ秒の時間間隔は、例えば、それぞれ５００ナノ秒のタイムスロットが１００個分の長さに等しい。この実施形態では、シェーピングリミットＳｌｉｍｉｔは次のように設定される。
【００９０】
Ｓｌｉｍｉｔ＝（Ｆｍｉｎ−Ｆｍａｘ）＊時間間隔
ＦｍｉｎがＦｍａｘよりも小さいので、シェーピングリミットＳｌｉｍｉｔは一般的に負数であることになる。その待ち行列のサービス処理が最近済んでおり、したがって、その時点でその保証された帯域幅よりも大きい帯域幅をすでに受けている時にだけ、クレジット値が負になる。負のクレジット値の絶対値が大きければ大きいほど、その対応する待ち行列がすでにより多くサービス処理されており、待ち行列がその保証された帯域幅をより大きく上回っている。こうした場合には、表１の条件５に示されているように、待ち行列に対する優先度は、シェーピングリミットＳｌｉｍｉｔを使用することによって強制的にゼロにできる。時間間隔当たりのバイト数に変換されたクレジット値Ｃ（ｑ）がシェーピングリミットＳｌｉｍｉｔよりも小さい場合には、この実施形態では優先度がゼロに設定されることになり、したがって待ち行列が後続タイムスロットの期間中にサービス処理されないことが保証される。変換されたクレジット値Ｃ（ｑ）がシェーピングリミットＳｌｉｍｉｔよりも小さい場合には、待ち行列は、時間間隔にわたって許容されることになる最大帯域幅をすでに上回っており、したがって優先度はゼロに設定される。このようにして、待ち行列に対して得られる最大の帯域幅は、所定の時間間隔にわたって制限される。しかし、所定の時間間隔にわたって待ち行列がその最大帯域幅を上回ることが必要である場合には、絶対値の大きい負のクレジット値は待ち行列が頻繁にサービス処理されることを妨げることがないように、待ち行列に対するクレジット値が周期的にゼロに設定することができる。
【００９１】
表１の条件２に対しては、入力端が、優先転送待ち行列である待ち行列によってセットアップできる。この優先転送待ち行列は、クレジット値に関係なしに、入力端の他の待ち行列よりも前にサービス処理される待ち行列である。優先転送待ち行列は、所定のパケットが可能な限り速やかに伝送されることを確保するために、入力端内で使用できる。この場合には、パケットが優先転送待ち行列内にバッファリングされる。表１が条件２に対して示すように、優先転送待ち行列がパケットを含む（すなわち、その待ち行列が空ではない）場合に、優先度ＭＡＸＰＲＩ−１がこの優先転送待ち行列に設定される。優先度ＭＡＸＰＲＩ−１によっては、同じ出力端を要求する待ち行列が優先度ＭＡＸＰＲＩを持たない限り、待ち行列がサービス処理される確率が一層高くなる。同様に、２つの待ち行列がＭＡＸＰＲＩ−１を有してもよく、この場合には、後述するように、これら２つの待ち行列の間で、いずれがより高い優先度を持つべきかを、決定する必要性がある。ゼロから１５までの１６ポイントスケール上では、ＭＡＸＰＲＩ−１は１４である。
【００９２】
表１の条件３は、クレジット値が優先度にスケーリングされる通常の条件を示す。一般的に、待ち行列が部分パケットを持たない場合には、待ち行列は優先転送待ち行列ではなく、そして、待ち行列に対するクレジット値Ｃ（ｑ）が負でなく、この場合に、待ち行列に対する優先度は、スケーリング因子Ｓで待ち行列に対するクレジット値Ｃ（ｑ）を除算することによって計算可能である。優先度は、スケーリング因子で除算されたクレジット値Ｃ（ｑ）の丸められた値であり、その結果として数値６．４は優先度６に丸められる。スケーリング因子Ｓの使用は線形スケーリングを示唆する。しかし、スケーリングは必ずしも線形である必要はなく、非線形であってもよい。さらに、ルックアップテーブル、すなわち、一連の「ＩＦ−ＴＨＥＮ」決定が、クレジット値に基づいて優先度を決定するために使用可能である。設定されたスケール（例えばゼロから１５のスケール）の範囲内に優先度を保つために、待ち行列が部分パケットを含まない場合には、待ち行列に対する優先度が最高レベルＭＡＸＰＲＩ−１に設定できる。したがって、表１の条件３は、こうした待ち行列に対する優先度では、ＭＡＸＰＲＩ−１またはＣ（ｑ）／Ｓのどちらか小さい方をとることを示している。
【００９３】
表１の条件４は、待ち行列が空でない場合、条件５が当てはまらない（すなわち、クレジット値Ｃ（ｑ）がシェーピングリミットＳｌｉｍｉｔ以上である）場合には、待ち行列に対する優先度が最低の優先度であるということを示す。表１は、この最低の優先度が１であることを示す。もちろん、条件３によって示されているように、クレジット値Ｃ（ｑ）が正である場合には、待ち行列に対する優先度はより高い。しかし、待ち行列が空でない場合、条件５が存在しない場合には、条件４は最低の優先度が設定されることを示す。
【００９４】
待ち行列のクレジット値は広範囲にわたって変化する。クレジット値は数千万ほどであることも、または、絶対値が数千万である負の量であってもよい。クレジット値から優先度への変換の一例として、待ち行列に対する保証レートが０．０００５Ｇｂｐｓ、すなわち、５００，０００バイト／秒（ｂｐｓ）であると仮定する。したがって、待ち行列がタイムスロット期間中にサービス処理されることがない各タイムスロットが経過する毎に、待ち行列に関連するクレジット値が５００，０００ｂｐｓずつ増加する。この例では、スケーリング因子Ｓは１，０００，０００である。したがって、待ち行列に対するクレジット値が値１２，０００，０００に増大すると、（待ち行列が優先転送待ち行列でなく、待ち行列が部分パケットを含まないと仮定すると）その待ち行列の優先度は１２に設定される。待ち行列に対するクレジット値が−５，０００，０００である場合には、（表１の条件１、条件２、または、条件５が当てはまらない場合に）その待ち行列に対する優先度が１に設定される。
Ｅ．待ち行列サービス処理の選択の方法
各待ち行列に対する優先度を決定した後に、複数の優先度が、タイムスロットの期間中の入力端と出力端との間の共用リンクを介する対応付けマッピングを計算するために使用される。図９は、所定のタイムスロットの期間中にサービス処理のために待ち行列を選択する、単純化された一実施形態を示す。図９は２つの入力端Ｉ１、Ｉ２を示し、これらの入力端の各々が４つの待ち行列を持つ。各待ち行列Ｑ１、Ｑ２、Ｑ３、Ｑ４内では、待ち行列に対するＣＯＳとパケットとが待ち行列の先頭に示されている。待ち行列の先頭のパケットの各々は、任意の所定のタイムスロットの期間中に共用リンク１０８にアクセスすることを求めて競合する。例えば、図９では、出力端Ｅ１向けのパケットが各待ち行列Ｑ１の先頭にあり、出力端Ｅ１向けのパケットが各待ち行列Ｑ２の先頭にもあり、そして、出力端Ｅ２向けのパケットが待ち行列Ｑ３、Ｑ４の各々の先頭にある。
【００９５】
図９は、優先度Ｐ１１、Ｐ１２、Ｐ２１、Ｐ２２を待ち行列Ｑ１、Ｑ２、Ｑ３、Ｑ４の各々に対して計算したことを示す。一実施形態では、優先度の計算と待ち行列の選択とがタイムスロット毎に行われる。したがって、待ち行列の先頭の１つまたは複数のパケットだけが所定のタイムスロットの期間中に共用リンク１０８に対するアクセスを求めて競合するので、任意の所定の時点において、待ち行列の先頭の１つまたは複数のパケットに対する優先度はその待ち行列自体に対する優先度に類似している。したがって、本明細書の全体を通じて、待ち行列に対する瞬時的な、もしくは瞬時的に成り立つ優先度は、待ち行列の先頭にある１つまたは複数のパケットに対する優先度と同義であるとみなされることが可能である。さらに、「瞬時的な、もしくは瞬時的に成り立つ」優先度は、何らかの有限な持続時間を持つ時間としての瞬時的である所定のタイムスロットに対する優先度を意味し、この優先度は、その所定のタイムスロットの後に続くタイムスロット中で変化することも変化しないこともある。
【００９６】
図９では、各々が４つの待ち行列Ｑ１、Ｑ２、Ｑ３、Ｑ４を持つ２つの入力端Ｉ１、Ｉ２が共有リンク１０８を介して出力端Ｅ１、Ｅ２に接続可能である。入力端と出力端との間の対応付けマッピング選択のための２レベルプロセスが次の通りに使用可能である。第１のレベルでは、第１の瞬時的な、もしくは瞬時的に成り立つ優先度が、所定出力端向けの各入力端中の待ち行列グループの各々に対して選択される。この選択の第１のレベルを、優先度計算モジュール１５６（図３Ａ）によって入力端内で実行できる。例えば、図９の入力端Ｉ１の場合には、待ち行列Ｑ１と待ち行列Ｑ２の両方が、出力端Ｅ１向けのパケットを含む。これら２つの待ち行列Ｑ１、Ｑ２の優先度に基づいて、第１の優先度を持つこれらの待ち行列の一方が選択される。一実施形態では、例えば、関連するより高い優先度を持つ待ち行列が選択される。同様に、入力端Ｉ２内では、待ち行列Ｑ１、Ｑ２の両方が出力端Ｅ１向けのパケットを含み、これら２つの待ち行列から第１の優先度を持つ待ち行列が同様に選択される。待ち行列の選択の場合に、一実施形態では、待ち行列に対するＣＯＳが無視できることに留意すべきである。待ち行列に対するＣＯＳは、おそらくは、待ち行列に対する優先度を決定するためにすでに使用されている。図９は、さらに、各入力端Ｉ１、Ｉ２内における、出力端Ｅ２向けのパケットを持つ（第１の優先度を持つ）待ち行列の選択を示す。図９に示されているように、第１のレベルにおける第１の優先度を持つ各々の選択された待ち行列に対する待ち行列番号と入力端番号と優先度レベルとの表示が、アービタチップ１０６のアービトレーションモジュール１５２に送られる。
【００９７】
この２レベルプロセスにおける待ち行列の選択の第２のレベルがアービトレーションモジュール１５２内で実行される。この第２のレベルでは、第２の優先度を持つ待ち行列が、入力端Ｉ１、Ｉ２から受け取った第１の優先度を持つ待ち行列のサブセットから選択される。この選択の第２のレベルは、各入力端が各出力端と接続することを求める場合の優先度を調べて、各入力端に対して出力端を選択する。一例として、図９を使用して、待ち行列Ｑ１が入力端Ｉ１内において優先度Ｐ１１＝１２を有し、出力端Ｅ１に対する選択の第１のレベルにおいて入力端Ｉ１内で選択されていると仮定する。同様に、待ち行列Ｑ２が入力端Ｉ２において優先度Ｐ１２＝７を有し、出力端Ｅ１に対する選択の第１のレベルにおいて入力端Ｉ２内で選択されていると仮定する。これら２つの待ち行列と優先度と所望の出力端はアービトレーションモジュール１５２に伝送される。待ち行列の選択の第２のレベルでは、アービトレーションモジュール１５２はこれらの待ち行列（両方とも出力端Ｅ１向けのパケットを含む）から第２の優先度を持つ待ち行列を選択する。例えば、一実施形態では、最高の優先度を持つ待ち行列が出力端に対して選択される。この例では、例えば、入力端Ｉ１からの待ち行列Ｑ１は、入力端Ｉ２からの待ち行列Ｑ２の場合よりも高い優先度を出力端Ｅ１に対して持つ（すなわち、１２という優先度は７という優先度よりも高い）。したがって、この第２のレベルは、所定のタイムスロットの期間中に各入力端が接続される出力端を決定する。
【００９８】
したがって、ＮｘＭ行列の優先度をアービトレーションモジュール１５２で使用でき、ここでＮは入力端の数であり、Ｍは出力端の数である。例えば、アービトレーションモジュール１５２は、選択の第１のレベルで決定された通りに、入力端が各出力端を要求する場合の最高の優先度を各入力端から受け取ることできる。その次に、これらの優先度は、選択の第２のレベルにおいて入力端を各出力端に対して選択できるように、ＮｘＭ行列を埋める。図９に示されているように、メッセージが各入力端に送られ、このメッセージは、いずれにしても、その入力端がタイムスロットの期間中にアクセスする出力端をその入力端に通知する。その次に、入力端が、決定された出力端に対して入力端が選択した待ち行列をパケット伝送のために共用リンク１０８に接続できる。
【００９９】
単一の入力端が、待ち行列選択の第２のレベルの期間中に、異なる出力端向けのものであり、これらの出力端に対して最高の優先度を持つパケットを持つ２つ以上の待ち行列を含み得る。幾つかの実施形態では、入力端の単一の待ち行列がタイムスロットの期間中に単一の出力端だけにしか接続できないので（本発明のこの実施形態における物理的制約）、これら待ち行列の各々は、共用リンク１０８に対するアクセスに対して選択されないことになる。こうした状況では、最高の優先度を持つ待ち行列は入力端内の待ち行列から選択され、その待ち行列に対する出力端はその最高の優先度にしたがって決定される。その次に、入力端は、少なくともそのタイムスロットの期間中は他の出力端に対する接続のためには使用不可能であり、その入力端からの優先度は、このタイムスロットの期間中は、選択の第２のレベルにおける待ち行列選択の残り部分において無視できる。図９からの一例として、入力端Ｉ１からの待ち行列Ｑ１が優先度Ｐ１１＝１２を有し、アービトレーションモジュール１５２内において、全入力端において出力端Ｅ１に対する最高の優先度であると仮定する。さらに、入力端Ｉ１からの待ち行列Ｑ３が優先度Ｐ２１＝１０を有し、全入力端における出力端Ｅ２に対する最高の優先度であると仮定する。この例では、入力端Ｉ１からの待ち行列Ｑ１は入力端Ｉ１からの待ち行列Ｑ３よりも高い優先度を有し（１２は１０よりも大きい）、したがって、入力端Ｉ１からの待ち行列Ｑ１は、出力端Ｅ１に対するアクセスのために選択される。入力端Ｉ１からのその他の待ち行列は、その所定のタイムスロットの期間中に共用リンク１０８に対する接続のためには使用不可能となる。したがって、入力端Ｉ１からの待ち行列Ｑ３は、所定のタイムスロットの期間中は使用不可能であり、異なる入力端からの異なる待ち行列が出力端Ｅ２に対して選択されなければならない。
【０１００】
２つ以上の優先度が入力端またはアービトレーションモジュール１５２において互いに等しい時には，いずれがより高い優先度を持つべきかを決定する方法が必要とされる。これは、ランダム選択、ラウンドロビン選択、または、他の実施形態では、最長時間未サービス処理待ち行列を使用して行われる。図９を使用する例では、入力端Ｉ１内の待ち行列Ｑ１が出力端Ｅ１に対する優先度Ｐ１２＝１０を有し、入力端Ｉ１内の待ち行列Ｑ２も出力端Ｅ１に対する優先度Ｐ１２＝１０を持つと仮定する。最近最もサービス処理を受けていない待ち行列を使用して、いずれがより高い優先度を持つべきかを決定する手順では、そのような最近最もサービス処理を受けていない待ち行列Ｑ１または待ち行列Ｑ２が選択される。出力端に対する入力端からの優先度について、いずれがより高い優先度を持つべきかを決定する同様の手順をアービトレーションモジュール１５２内で行わせることができる。この場合には、例えば、出力端に対して最近最もサービス処理を受けていない入力端がサービス処理されることになるか、または、別の実施形態では、最長時間にわたってサービス処理されていないいずれかの入力端からの待ち行列が選択される。
【０１０１】
図９は、ライン１１０ａを通してアービタチップ１０６に送られる各出力端Ｅ１、Ｅ２内のＦＩＦＯの状態を含むメッセージを示す。出力端のＦＩＦＯがどれほど充満しているかの表示であってよいＦＩＦＯの状態が、入力端を出力端に対して対応付けマッピングするためにアービトレーションモジュール１５２内で使用することができる。待ち行列が通信することを求める出力端の中のＦＩＦＯが充満している場合には、待ち行列に対する優先度を引き下げることができる。言い換えると、出力端のＦＩＦＯが充満している場合には、パケットはそのＦＩＦＯには送られず、そして、出力端のＦＩＦＯのすべてが充満している場合は、そのタイムスロットの期間中にはパケットがその出力端に送られず、これに対応して、その出力端を求めるパケットを持つ待ち行列の優先度が、その待ち行列がその次のタイムスロットの期間中に共用リンク１０８に対してアクセスしないように引き下げられる。この実施形態では、ＦＩＦＯが充満している出力端向けの待ち行列に対する優先度は、アービタチップ１０６上のアービトレーションモジュール１５２内で引き下げられるが、他の実施形態ではＦＩＦＯの状態も入力端に送られる。別の実施形態では、ＦＩＦＯが充満している出力端向けのパケットを持つ待ち行列に対して優先度は実際には引き下げられないが、その代わりに、出力端のＦＩＦＯが充満している間中はパケットがその出力端に送られないことを保証するために、ＦＩＦＯの状態が単純に使用できる。言い換えると、ＦＩＦＯが充満している出力端は無視され、充満している出力端のＦＩＦＯポートも無視される。この実施形態では、入力端は、所定のタイムスロットの期間中は、ＦＩＦＯが充満している出力端に対してアクセスしない。
【０１０２】
サービス処理のために待ち行列を選択する別の実施形態が、入力端と出力端の間の対応付けマッピングの選択のための３レベルプロセスを含む。接続することが求められている出力端とその出力端内のポートとをデータパケットが指定する場合待ち行列選択の３レベルプロセスを使用できる。例えば、図９は、出力端Ｅ１、Ｅ２の各々の中のポートＦＩＦＯ１、ＦＩＦＯ２を示す。入力端内のデータパケットの各々は、通信することが求められている所定の出力端とその出力端内の所定のポートとを指定することができる。
【０１０３】
図１０は、待ち行列選択のための３レベルプロセスにおける選択のレベルを示す判断トリーブロック図である。待ち行列選択のためのこの３レベルプロセスでは、選択の第１のレベルが、１つの所定の出力端の１つの所定のポート向けの待ち行列グループの各々から、各入力端内で待ち行列を選択することを含む。言い換えると、第１の優先度を持つ待ち行列が、同じ出力端の同じポート向けの入力端内の待ち行列から選択され、その第１の優先度が待ち行列グループに対する最高の優先度である。この選択は、異なるＣＯＳを持つ待ち行列の中からであってよい。
【０１０４】
図１０は、４つの待ち行列を各々が持つ２つの入力端Ｉ１、Ｉ２を示し、この図における各待ち行列は同じ出力端向けのパケットを持つ。例えば、入力端Ｉ１内では、ブロック１００２が、待ち行列Ｑ１が優先度Ｐ１を有し、出力端Ｅ１のポート１と通信することを求めるということを示す。同様に、ブロック１００４は、待ち行列Ｑ２が優先度Ｐ２を有し、同様に出力端Ｅ１のポート１に接続することを求めることを示す。待ち行列Ｑ１、Ｑ２がその待ち行列に関連する相異なるＣＯＳを持つということに留意すべきである。例えば、図１０は、待ち行列Ｑ１に対するＣＯＳ１と、待ち行列Ｑ２に対するＣＯＳ２とを示す。この例では、待ち行列Ｑ１または待ち行列Ｑ２（両方とも同じ出力端の同じポート向けの）は、ブロック１０１８において選択の第１のレベルで選択される。明確に述べると、この実施形態では、最高の優先度を持つ待ち行列（図１０の待ち行列Ｑ１）がこの第１のレベルで選択される（ブロック１０２６がこの選択を示す）。図１０は、入力端Ｉ１内の待ち行列Ｑ４が、ブロック１０２８において、両方とも同じ出力端のポート２と通信することを求める待ち行列Ｑ３と待ち行列Ｑ４との間で選択される（ブロック１０２０）同様の判断トリーを示す。同様の判断トリーが図１０において入力端Ｉ２内に示されている。明確に述べると、待ち行列Ｑ２と待ち行列Ｑ３は、ブロック１０３０とブロック１０３２とにおいて、入力端Ｉ２内で第１のレベルで選択される。
【０１０５】
３レベルプロセスにおける選択の第２のレベルは、各入力端内またはアービトレーションモジュール１５内において、第１のレベルで選択された待ち行列の中から、すなわち、第１の優先度を持つ待ち行列の中から、第２の優先度を持つ待ち行列を選択することを含む。言い換えると、この第２のレベルは、同じ出力端の相異なるポートと通信することを求める待ち行列の中から各入力端に対する待ち行列を選択することを含む。この第２のレベルがアービトレーションモジュール１５２内で実行される場合には、ＦＩＦＯの充満状態が、充満のＦＩＦＯに対する接続を求める待ち行列が選択されないように使用される。図１０は、入力端Ｉ１に対する、ポート１向けの待ち行列Ｑ１の第１のレベルの選択（ブロック１０２６）と、同じ出力端のポート２向けの待ち行列Ｑ４の第１のレベルの選択（ブロック１０２８）とを示す。その次に、ブロック１０３４では、このシステムは、この２つの待ち行列の優先度に基づいて、この２つの待ち行列の間で第２のレベルにおいて選択し、図１０は、ブロック１０３８における、ポート１向けの待ち行列Ｑ１のこの第２のレベルでの選択を示す。明確に述べると、待ち行列Ｑ１に対する優先度Ｐ１が待ち行列Ｑ４に対する優先度Ｐ４よりも高いので、待ち行列Ｑ１が選択される。同様に、入力端Ｉ２内の待ち行列Ｑ３は、ブロック１０３６における待ち行列Ｑ２と待ち行列Ｑ３との間の比較に基づいて、ブロック１０４０で第２のレベルで選択される。
【０１０６】
３レベルプロセスにおける選択の第３すなわち最後のレベルが、出力端が２つ以上の入力端に接続されないように、各出力端に対して入力端を（第２の優先度を持つ待ち行列の中から）選択することを含む。この第３のレベルは、各入力端が各出力端を求める場合の優先度が存在し得るようにアービトレーションモジュール１５２内で行われるが、入力端内で行われることはない。言い換えると、第２の優先度を有しかつ所定の出力端向けの待ち行列の各グループ毎に、待ち行列が、各出力端が単一の入力端だけに接続されるように選択される。一実施形態では、最高の優先度を持つ待ち行列が選択される。
【０１０７】
図１０を参照すると、入力端Ｉ１内の待ち行列Ｑ１と入力端Ｉ２内の待ち行列Ｑ３は、ブロック１０３８とブロック１０４０とにおいて第２のレベルで選択された。ブロック１０４２では、この２つの待ち行列の優先度（優先度Ｐ１と優先度Ｐ３）の比較に基づいて選択が行われる。図１０では、ブロック１０４４で待ち行列Ｑ３がこの第３のレベルで選択され終わっている。待ち行列Ｑ３が入力端Ｉ２内にあるので、この実施形態では入力端Ｉ２は出力端に接続され、待ち行列Ｑ３は、サービス処理される待ち行列である。図１０が、２つの入力端だけしか存在せずかつ図示された待ち行列のすべてが同じ出力端向けの、単純化された手順を示すということに留意されたい。さらに概括的に述べると、選択の第３のレベルでは、例えば、入力端は複数の出力端の各々に対して選択される。さらに、単一の入力端が、２つ以上の出力端に対して最高の優先度を持つ２つ以上の待ち行列を持つことが可能なので、最高の優先度を持つこの入力端からの待ち行列が出力端に対する通信のために選択されることになり、その結果として、この入力端内のその他の待ち行列を後続のタイムスロット中の通信に対して競合した状態のままにすることになる。
【０１０８】
図１０は、さらに、選択の３つのレベルのどれにおいても同順位状態を打開するために使用されることが可能な情報も示す。図１０の各待ち行列は、その各待ち行列に関連する最低使用頻度（ＬＲＵ）数を持つ。待ち行列が最後にサービス処理された時以来の時間の長さを示す変数、すなわち、待ち行列が最後にサービス処理を受けた時以来どれだけ長い時間が経過しているかを概略的に示すスケーリングされた数であるこのＬＲＵ数は可変的である。さらに、ＬＲＵ数は待ち行列の全体的な順序付けにおける位置を表すことも可能であり、この順序付けは、各待ち行列がサービス処理を最後に受けた時以来の時間の長さの増加分に基づいている。例えば、入力端Ｉ１の待ち行列Ｑ１はＬＲＵ１を有し（ブロック１００２）、待ち行列Ｑ２はＬＲＵ２を持つ（ブロック１００４）。ブロック１０１８において、待ち行列Ｑ１の優先度Ｐ１が待ち行列Ｑ２の優先度Ｐ２と同一である場合には、ＬＲＵ数がその選択レベルにおいて同順位状態を打開するために使用されることが可能である。したがって、ブロック１０１８における待ち行列Ｑ１からのＬＲＵ１と待ち行列Ｑ２からのＬＲＵ２との間の比較が、待ち行列Ｑ１の方が最後にサービス処理を受けた時点からより長い時間を経過しているということを示す場合には、待ち行列Ｑ１は選択の第１のレベルで選択されることになる。さらに、ＬＲＵ数は、最低使用頻度（ＬＲＵ）情報を使用してアービトレーションモジュール１５２内でいずれがより高い優先度を有するべきかを決定するように、第２のレベルで選択された各待ち行列と優先度と共に、入力端からアービトレーションモジュール１５２に送られることが可能である。さらに、アービトレーションモジュール１５２は、どの出力端ポートが選択されたか、そして、各入力端が各出力端に何時接続されたかに対するそのモジュール自体のＬＲＵ情報を記憶することも可能である。
【０１０９】
図１１は、本発明の一実施形態によるシステム１００の待ち行列選択手順の別の実施形態をブロック図を使用して示す。本発明のこの実施形態では、出力端内の待ち行列は、２つ以上の出力端向けのパケットのためにリザーブされることが可能である。こうしたパケットは、本明細書全体を通して「マルチキャスト」パケットと呼ばれており、このパケットを含む待ち行列は「マルチキャスト」待ち行列と呼ばれる。例えば、図１１における入力端Ｉ１、Ｉ２、Ｉ３の各々の中の待ち行列Ｑ２は、出力端Ｅ１、Ｅ２、Ｅ３向けられる。したがって、待ち行列Ｑ２内に入れられているパケットは出力端Ｅ１、Ｅ２、Ｅ３の２つ以上向けられる。待ち行列Ｑ２内の１つのパケットは出力端Ｅ１、Ｅ２、Ｅ３向けできるが、一方、待ち行列Ｑ２内の別のパケットは出力端Ｅ１、Ｅ３向けできる。図１１の実施形態では、２つ以上の出力端向けのパケットを持つ待ち行列が共用リンク１０８を介する通信のために選択される場合には、その待ち行列は単一のタイムスロットの期間中に２つ以上の出力端に接続される。したがって、この実施形態では、共用リンク１０８はタイムスロット中に単一の入力端を２つ以上の出力端に対応付けマッピングすることができる。入力端の数が出力端の数と同じである場合には、入力端の少なくとも１つはそのタイムスロット中に共用リンク１０８に接続されない。
【０１１０】
この選択方式は、マルチキャスト待ち行列が使用される時に変化する。一実施形態では、マルチキャスト待ち行列に関連する各出力端に対する最高の優先度を待ち行列が持つ時には、マルチキャストパケットを持つ入力端内の待ち行列だけが共用リンク１０８を介する通信のために選択される。こうした実施形態では、例えば、図１１の入力端Ｉ１内の待ち行列Ｑ２は、出力端Ｅ１、Ｅ２に対する最高の優先度を持つことができ、それにも係わらず、待ち行列Ｑ２が出力端Ｅ３に対する最高の優先度を持たないので、共用リンク１０８を介する伝送のために選択されないことがある。別の実施形態では、待ち行列の先頭に位置するパケットだけが、入力端を出力端に対応付けマッピングするために調べられる。例えば、図１１の入力端Ｉ１内の待ち行列Ｑ２が、出力端Ｅ１、Ｅ２だけ向けの待ち行列の先頭のパケットを含む場合には、出力端Ｅ３に対する待ち行列Ｑ２の優先度が最高の優先度であるかどうかに無関係に、待ち行列Ｑ２が出力端Ｅ１、Ｅ２に対する最高の優先度を持つ場合に、その待ち行列Ｑ２が選択される。別の実施形態は、マルチキャスト待ち行列が単一の出力端だけに対して最高の優先度を持つ場合にそのマルチキャスト待ち行列が情報伝送のために選択される実施形態である。しかし、この実施形態は、待ち行列が各出力端に対して最高の優先度を持つことなしにその待ち行列が複数の出力端に対して選択されることになるので、効率的に帯域幅を使用しないおそれがある。
【０１１１】
図１１を参照して、マルチキャストパケットを使用する待ち行列選択方式の一例を説明することが可能である。図１１では、図９と図１０に対して上述したように、２回または３回の選択が使用される。３レベル選択方式では、選択の第１のレベルが各入力端内で行われる。第２のレベルが各入力端内またはアービトレーションモジュール１５２内で行われることが可能であり、選択の第３のレベルがアービトレーションモジュール１５２内で行われる。図１１の各入力端Ｉ１、Ｉ２、Ｉ３は同じタイプの待ち行列を含む。各入力端内では、選択の第１のレベルが、所定の出力端の所定のポート向けの待ち行列の各グループから待ち行列を選択することができる。アービトレーションモジュール１５２内では、選択の第２のレベルが、同じ出力端の異なるポートと通信することを求める待ち行列の中から、各入力端に対する待ち行列を選択することを含む。その次に、アービトレーションモジュール１５２内で行われる選択の第３すなわち最後のレベルは、各出力端に対して入力端を選択することを含む。
【０１１２】
図１１は、２レベル選択方式を示す。図１１の入力端Ｉ１の場合には、待ち行列Ｑ１、Ｑ２、Ｑ３は各々に、出力端Ｅ１向けのパケットを含む。したがって、最高の優先度を持つ待ち行列がこれら３つの待ち行列から選択される。同様に、待ち行列Ｑ２、Ｑ３、Ｑ４は、出力端Ｅ２向けのパケットを含むことができ、したがって、最高の優先度を持つ待ち行列がこれらの待ち行列の中から選択される。さらに、待ち行列Ｑ３、Ｑ５は出力端Ｅ３向けのパケットを含むことができ、したがって、最高の優先度はこれらの待ち行列から選択される。同様の選択が入力端Ｉ２、Ｉ３の各々に対して行われる。その次に、アービトレーションモジュール１５２は各出力端に対して入力端を選択することが可能である。一実施形態では、例えば、入力端Ｉ１を出力端Ｅ１、Ｅ２、Ｅ３の各々に対して選択できるである。これが当てはまる場合には、入力端Ｉ１、Ｉ２は所定のタイムスロットの期間中はアイドル状態にあることになる。したがって、この実施形態では、入力端Ｉ１内の待ち行列Ｑ２、Ｑ３は出力端Ｅ１、Ｅ２、Ｅ３の各々に接続される。第２の実施形態では、入力端Ｉ１を出力端Ｅ１、Ｅ２に接続することができ、入力端Ｉ２をアイドル状態におくことができ、入力端Ｉ３は所定のタイムスロットの期間中に出力端Ｅ３に接続できる。
【０１１３】
一実施形態では、１つまたは複数のパケットが各々の出力端に向けているか否かにかかわらず、マルチキャスト待ち行列が通信のために選択される時には、そのマルチキャスト待ち行列は、そのマルチキャスト待ち行列が関連する待ち行列の各々に対して１つまたは複数のパケットを送ることができる。例えば、図１１において、入力端Ｉ２の待ち行列Ｑ３は出力端Ｅ１、Ｅ２、Ｅ３の各々に対する情報伝送のために選択することができる。しかし、入力端Ｉ２の待ち行列Ｑ３内の１つのパケットが出力端Ｅ１、Ｅ２だけ向けられていてもよい。一実施形態では、このパケットはその３つの出力端Ｅ１、Ｅ２、Ｅ３の各々に対して送られ、その次に、そのパケットが出力端Ｅ３に属することを示すヘッダ情報をそのパケットが含まないので、出力端Ｅ３はそのパケットを無視することになる。
【０１１４】
より大きいこととより小さい、前と後ろ、右と左、頂部と底部、上部と下部、水平と垂直に対するいずれの表現も、本発明またはその構成要素をいずれかの１つの関係上の、位置上の、または、空間上の適応に限定することを意図するのではなく、説明を容易にすることを意図している。添付図面における構成要素の寸法のすべてが、本発明の範囲から逸脱することなく、本発明の実施形態の採用可能な設計と意図された使用とに応じて変化することが可能である。
【０１１５】
本発明をその幾つかの実施形態に対して説明してきたが、当業者は、この特許請求されている発明の着想と範囲とから逸脱することなしに加えられることが可能な様々な変更が理解される。したがって、本発明は、添付図面に示されており本明細書に説明されているものには限定されないが、添付された特許請求項に示されている通りのものとして規定される。
【図面の簡単な説明】
【０１１６】
【図１】従来技術の交換システムのブロック図である。
【図２】本発明のシステムの一実施形態のブロック図である。
【図３Ａ】本発明のアービタチップと入力端チップと待ち行列マネージャの一実施形態のブロック図である。
【図３Ｂ】入力端の待ち行列内のデータパケットを示すブロック図である。
【図４Ａ】本発明の方法の一実施形態を示す流れ図である。
【図４Ｂ】図４Ａよりも詳細に本発明の方法の一実施形態を示す流れ図である。
【図５】異なる３つのタイプの帯域幅割当てに対する帯域幅レートの計算の一実施形態を示す流れ図である。
【図６Ａ】単一の出力端における帯域幅割当ての一実施形態を示すブロック図である。
【図６Ｂ】単一の出力端における帯域幅割当ての第２の実施形態を示すブロック図である。
【図７Ａ】単一の入力端における帯域幅割当ての一実施形態を示すブロック図である。
【図７Ｂ】待ち行列のグループに対する帯域幅割当ての一実施形態を示すブロック図である。
【図８】本発明の一実施形態における帯域幅割当てのために使用されるクレジット値の調整を示す流れ図である。
【図９】本発明の待ち行列選択方式の一実施形態を示すブロック図である。
【図１０】待ち行列選択方法の第２の実施形態を示す流れ図である。
【図１１】待ち行列選択方式の別の実施形態を示すブロック図である。
【符号の説明】
【０１１７】
５０：ＱＬｅｎｇｔｈｓ
５２：保証レート
５４：クレジット値
５６：優先度
５８：出力
６０：デキュー要求
６２：エンキュー通知
６４：デキュー通知
１０２：入力端チップ
１０４：出力端チップ
１０６：アービタチップ
１０８：共用リンク
１１０：パイプライン
１１２：待ち行列マネージャ
１１４：トラフィックソース
１１６：トラフィック出口
１５０：帯域幅アロケータ
１５２：アービトレーションモジュール
１５４：計量モジュール
１５６：優先度計算モジュール
１５８：レジスタファイル
１６０：計量更新モジュール
１６２：待ち行列長さモジュール
【図１】
2004534462.tif 000010
【図２】
2004534462.tif 000011
【図３Ａ】
2004534462.tif 000012
【図３Ｂ】
2004534462.tif 000013
【図４Ａ】
2004534462.tif 000014
【図４Ｂ】
2004534462.tif 000015
【図５】
2004534462.tif 000016
【図６Ａ】
2004534462.tif 000017
【図６Ｂ】
2004534462.tif 000018
【図７Ａ】
2004534462.tif 000019
【図７Ｂ】
2004534462.tif 000020
【図８】
2004534462.tif 000021
【図９】
2004534462.tif 000022
【図１０】
2004534462.tif 000023
【図１１】
2004534462.tif 000024
【国際公開パンフレット】
2004534462.tif 000025
2004534462.tif 000026
2004534462.tif 000027
2004534462.tif 000028
2004534462.tif 000029
2004534462.tif 000030
2004534462.tif 000031
2004534462.tif 000032
2004534462.tif 000033
2004534462.tif 000034
2004534462.tif 000035
2004534462.tif 000036
2004534462.tif 000037
2004534462.tif 000038
2004534462.tif 000039
2004534462.tif 000040
2004534462.tif 000041
2004534462.tif 000042
2004534462.tif 000043
2004534462.tif 000044
2004534462.tif 000045
2004534462.tif 000046
2004534462.tif 000047
2004534462.tif 000048
2004534462.tif 000049
2004534462.tif 000050
2004534462.tif 000051
2004534462.tif 000052
2004534462.tif 000053
2004534462.tif 000054
2004534462.tif 000055
2004534462.tif 000056
2004534462.tif 000057
2004534462.tif 000058
2004534462.tif 000059
2004534462.tif 000060
2004534462.tif 000061
2004534462.tif 000062
2004534462.tif 000063
2004534462.tif 000064
2004534462.tif 000065
2004534462.tif 000066
2004534462.tif 000067
2004534462.tif 000068
2004534462.tif 000069
2004534462.tif 000070
2004534462.tif 000071
2004534462.tif 000072
2004534462.tif 000073
2004534462.tif 000074
2004534462.tif 000075
2004534462.tif 000076
2004534462.tif 000077
2004534462.tif 000078
2004534462.tif 000079
2004534462.tif 000080
2004534462.tif 000081
2004534462.tif 000082
2004534462.tif 000083
2004534462.tif 000084
2004534462.tif 000085
2004534462.tif 000086
2004534462.tif 000087
2004534462.tif 000088
2004534462.tif 000089
2004534462.tif 000090
2004534462.tif 000091
2004534462.tif 000092
2004534462.tif 000093
2004534462.tif 000094
2004534462.tif 000095
2004534462.tif 000096
2004534462.tif 000097
2004534462.tif 000098
2004534462.tif 000099
2004534462.tif 000100
2004534462.tif 000101
2004534462.tif 000102
2004534462.tif 000103
2004534462.tif 000104
2004534462.tif 000105
2004534462.tif 000106
2004534462.tif 000107
2004534462.tif 000108
2004534462.tif 000109
2004534462.tif 000110
【国際調査報告】
2004534462.tif 000111