(57)【特許請求の範囲】
【請求項１】
第１優先度の１つまたは複数のキュー（１０）からなるグループと、第２優先度の１つまたは複数のキュー（２０、３０）からなるグループとを含み、データを出力（６０、２１４）に解放する複数のキュー（０、・・・、Ｎ、１０、２０、３０、４０、５０）を有する待ち行列化構造のキュースケジューリング方法であって、第１と第２の優先度が異なっており、あるキュー（５０）は限定された帯域幅を有しており、
第１優先度の１つまたは複数のキュー（１０）のグループについて、解放すべきデータおよび利用可能な帯域幅を有するキューがあるかどうかチェックすること、および
第１優先度の、解放すべきデータおよび利用可能な帯域幅を有する１つまたは複数のキュー（１０）が見つかった場合に、見つかったキュー（１０）のうちの１つから出力（６０、２１４）へデータを解放することを含み、解放すべきデータを有する前記１つまたは複数のキューが複数のキュー状態変数に応じて選択され、複数のマスク（２３２）が使用され、各マスク（３１２、３１４、３１６、３１８）が複数のビットを有し、
マスクの前記ビットの各々が、各マスク（３１２、３１４、３１６、３１８）に関連したキュー状態変数に関する、異なるキュー（０、・・・、Ｎ）のステータスを表し、別個の優先度マスク（３１８）が優先度レベルごとに保持され、優先度マスク（３１８）のビットが、前記ビットに関連したキューが前記優先度マスク（３１８）の優先度を割り当てられるかどうかを指示し、特定のキュー（０、・・・、Ｎ）に関連しかつ１つの前記優先度マスク（３１８）のビットを含む前記マスク（３１２、３１４、３１６、３１８）の各ビットは、前記特定のキューが選択されたかどうかを決定するためにマスク比較手段（３２４）によってビットごとの論理積演算で組み合わされる、キュースケジューリング方法。
【請求項２】
第１優先度の、解放すべきデータおよび利用可能な帯域幅を有するキューが見つからない場合、第２優先度のキュー（２０、３０）のグループについて、解放すべきデータおよび利用可能な帯域幅を有するキューがあるかどうかチェックするステップをさらに含む、請求項１に記載のキュースケジューリング方法。
【請求項３】
第１優先度の、解放すべきデータおよび利用可能な帯域幅を有するキュー（１０）が複数見つかった場合、出力（６０、２１４）へデータを解放するように、見つかったキューのうちの１つをラウンドロビンで選択するステップをさらに含む、請求項１に記載のキュースケジューリング方法。
【請求項４】
データが出力（６０、２１４）に解放されるキューが限定された帯域幅を有する場合、データが出力（６０、２１４）に解放されるキュー用の利用可能な帯域幅を減少させるステップをさらに含む、請求項１に記載のキュースケジューリング方法。
【請求項５】
データが出力（６０、２１４）に解放されるキューのクレジットを増大するステップをさらに含む、請求項１に記載のキュースケジューリング方法。
【請求項６】
データが出力（６０、２１４）に解放されるキューのクレジットを、解放されたデータの長さに従って減少させるステップをさらに含む、請求項５に記載のキュースケジューリング方法。
【請求項７】
限定された帯域幅を有するキューの利用可能な帯域幅を周期的に増大するステップをさらに含む、請求項５に記載のキュースケジューリング方法。
【請求項８】
それぞれの入力（２１２）でデータを受け取り、出力（２１４）へデータを解放する、異なるプロファイルの複数のキュー（０、・・・、Ｎ）を有するキュー構造（２１０）のスケジューリング装置であって、
複数のキュー状態変数に応じて、複数のキュー（０、・・・、Ｎ）から１つのキューを選択し、キュー選択情報を送るセレクタ（２３０）と、
キュー選択情報を受け取り、選択されたキューからのデータの解放を制御するドライバ（２４０）とを備え、前記セレクタ（２３０）が複数のマスク（２３２）を備え、各マスク（３１２、３１４、３１６、３１８）が複数のビットを有し、マスクの前記ビットの各々が、各マスク（３１２、３１４、３１６、３１８）に関連したキュー状態変数に関する、異なるキュー（０、・・・、Ｎ）のステータスを表し、別個の優先度マスク（３１８）が優先度レベルごとに保持され、優先度マスク（３１８）のビットが、前記ビットに関連したキューが前記優先度マスク（３１８）の優先度を割り当てられるかどうかを指示し、前記セレクタ（２３０）が、特定のキュー（０、・・・、Ｎ）に関連しかつ１つの前記優先度マスク（３１８）のビットを含む前記マスク（３１２、３１４、３１６）の各ビットを、前記特定のキューがデータを出力に解放するために選択可能であるかどうかを決定するためにビットごとの論理積演算で組み合わせるマスク比較手段（３２４）を備える、スケジューリング装置。
【請求項９】
キュー状態変数にバックログが含まれる、請求項８に記載のスケジューリング装置。
【請求項１０】
キュー状態変数に帯域幅利用可能性が含まれる、請求項８に記載のスケジューリング装置。
【請求項１１】
キュー状態変数に優先度が含まれる、請求項８記載のスケジューリング装置。
【請求項１２】
１つまたは複数のキュー状態変数に関して複数のキュー（０、・・・、Ｎ）のステータスを更新するためのマネージャ（２２０）をさらに備える、請求項８に記載のスケジューリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
【従来の技術】
データ通信交換機は、複数の入力からパケットを受け取り、それらを複数の出力に送る。時には、同一の出力宛てのパケットが、２つ以上の入力に到来することがある。そのようなパケット間の衝突を最小にするために待ち行列化が使われる。キューは一部のパケットを一時的に格納し、その他のパケットが、待ち行列化されたパケットを出力へ送達するために必要な帯域幅を消費する。
【０００２】
出力帯域幅を求めて競合するキューからのパケットの解放は、一般にはスケジューラによって調整される。多くのスケジューラは、優先度に基づくスケジューリングの厳密な規則、すなわちキューに異なる優先度レベルが割り当てられ、相対的に高い優先度レベルに関連するキューは相対的に低い優先度レベルに関連するキューよりも先にパケットを解放することが許されるという規則に従う。厳密な優先度に基づくスケジューリングでは、比較的タイムクリティカルなものと指定されたフローが、比較的タイムクリティカルでないものと指定されたフローより優先される。
【０００３】
厳密な優先度に基づくスケジューリングは、一般に効果があるものの、問題がないわけではない。１つの望ましくない効果は、優先度ブロッキングである。優先度ブロッキングは、相対的に高い優先度のキューのサービスを行うために、相対的に低い優先度のキューからのパケットの送達が持続的に遅れるときに起こる。優先度ブロッキングにより、最終的に、ブロックされたキューにあるパケットが解放を待っている間に上書される（ドロッピングとして知られる状態）ことになる可能性がある。ドロッピングは、ドロップされたパケットが関係するフローを乱すので望ましくない。
【０００４】
優先度に基づくスケジューリングは、設計により、一部のキューに他のキューよりも高速なサービスを提供するものと想定されているが、優先度付けの厳密な規則から逸脱することが場合によっては保証されることがある。例えば、優先度ブロッキングは、サービスを受ける優先度レベルにある１つのキューに、タイムクリティカルでない、または冗長でさえある（たとえば、未解決のスパンニングツリーループの場合）トラフィックが「詰め込まれる（ｓｔｕｆｆｉｎｇ）」ことによって引き起こされる可能性がある。優先度に基づくスケジューリングを厳密に固守すると、この「詰め込み」のために、すべての出力帯域幅（ｂａｎｄ  ｗｉｄｔｈ）が実際に占有され、相対的に低い優先度のキューが犠牲になることになる。
【０００５】
したがって、優先度付けの一般的方針に対して妥当な制限を課すことによって、優先度ブロッキングを減らす、限定された優先度に基づくスケジューリング方法が求められている。限定された優先度に基づくスケジューリングを実施するための、効率の良いスケジューリングハードウェアも求められている。
【０００６】
【発明が解決しようとする課題】
本発明は、出力の帯域幅を求めて競合する複数のキューを含むデータ待ち行列化構造のための限定された優先度に基づくスケジューリング方法および装置を提供する。各グループは、少なくとも１つのキューを有し、異なる優先度レベルに結び付けられる。さらに、少なくとも１つのグループ内の少なくとも１つのキューは、限定された帯域幅のキューであり、すなわちそれを上回ることのできない帯域幅制限（ｃｏｎｔｒａｃｔ）を有する。
【０００７】
【課題を解決するための手段】
このキュースケジューリング方法によれば、（ｉ）出力へと解放すべきデータを有し、（ｉｉ）利用可能な帯域幅を有する、すなわちその帯域幅制限がある場合にはそれに違反していない、現優先度レベルに関連するグループ内のあるキューが、出力にデータを解放するように選択される。そのようなキューが複数存在する場合、ラウンドロビン順序付けで、複数のキューのうちどれが選択されるかが決定される。現優先度レベルは、最初は最高の優先度レベルに設定され、あるキューが選択されるか、またはすべての優先度レベルがチェックされるかのどちらかが最初に起きるまで、次々に減分される。キューは限定された、または限定されない帯域幅を有することができる。限定されない帯域幅のキューは、常に利用可能な帯域幅を有し、限定された帯域幅のキューは、クレジットを有する場合のみ利用可能な帯域幅を有する。クレジットは、周期的に限定キューに割り振られ、解放されるデータの長さに従って減らされる。データはクレジット量（ｑｕａｎｔａ  ｏｆ  ｃｒｅｄｉｔ）ずつ解放される。
【０００８】
このキュースケジューリング装置によれば、セレクタは、複数のキュー状態変数に応じて複数のキューのうちから１つのキューを選択し、キュー選択情報を送るように構成される。セレクタは、好ましくは、異なるキューのキュー状態変数に関するステータスを表す複数のビットマスクを含み、それぞれのマスクは、ビットごとの論理積演算で組み合わされて、どのキューが出力へとデータを解放するために選択可能かどうかが決定される。好ましくはさらに、決定結果を受け取り、選択可能なキューのうちから単一のキューをラウンドロビンで選択し、選択されたキューから解放するためラウンドロビン選択の結果をドライバに送るアービタを、セレクタが含む。
【０００９】
本発明の前記その他の態様は、以下の詳細な説明を添付の図面と共に参照することによってより良く理解できるであろう。
【００１０】
【発明の実施の形態】
本発明は、主として、出力の帯域幅を求めて競合する複数のキューからのデータの解放をスケジュールするための方法および装置を対象とする。図１には、スケジューリングの機能を備える例示的な共用出力待ち行列化構造がポリシーレベル（ｐｏｌｉｃｙ  ｌｅｖｅｌ）で示されている。この例示的な構造では、出力６０の帯域幅を求めて競合する５個のキュー１０、２０、３０、４０、５０がある。競合を避けるため、キュー１０、２０、３０、４０、５０からのデータの解放がスケジューリング、すなわち時間多重化される。キュー１０、２０、３０、４０、５０は、出力６０へデータを解放するための高優先度キュー１０、中優先度キュー２０、３０および低優先度キュー４０、５０を含む優先度レベルによって特徴付けられる。キュー１０、２０、３０、４０、５０はさらに、出力６０へデータを解放するための帯域幅のタイプによっても特徴付けられる。唯一の高優先度キュー１０は限定されない帯域幅のキューである。中優先度キュー２０、３０はどちらも限定された帯域幅のキューである。一方の低優先度キュー４０は限定されない帯域幅のキューであり、他方の低優先度キュー５０は限定された帯域幅のキューである。キュー１０、２０、３０、４０、５０はさらに、フロータイプ、すなわちユニキャストかフラッドかによって特徴付けられる。ただし、フロータイプは、データが出力６０に解放される順序に対して独立の関係を有さない。もちろん、図１に示す共用出力待ち行列化構造はそのような構造の一例に過ぎない。キューの数、優先度レベル、および帯域幅タイプは、本発明に基づいて動作する他の共用出力待ち行列化構造では、実装しようとする方針に応じて異なることになる。
【００１１】
共用出力待ち行列化構造に対する好ましいスケジューリング方法では、現優先度レベルに関連するグループ内にあり、出力に解放するためのデータを有し、利用可能な帯域幅を有する、すなわちその帯域幅制限がある場合はそれに違反しないキューが、出力へのデータ解放のために選択される。そのようなキューが複数ある場合、ラウンドロビン順序付けによって複数のキューのうちのどのキューを選択するかどうかが決定される。以下に示すようにこの基本的なスケジューリング方法の様々な改良が可能である。とはいえ、基礎レベルでは、この基本的方法は見かけ上単純ではあっても、従来技術のスケジューリング方法に勝る重要な進歩をもたらすと考えられる。
【００１２】
前記好ましいスケジューリング方法を、図１に示す例示的な共用出力待ち行列化構造に適用すると、限定されない帯域幅の高優先度キュー１０が、出力６０に解放すべきデータを有する場合、キュー１０が選択される。キュー１０が選択されない場合、限定された帯域幅の中優先度キュー２０、３０がチェックされる。より具体的には、キュー２０、３０が、それぞれ出力６０に解放するデータを有し、それぞれ利用可能な帯域幅を有する場合、キュー２０、３０のうちラウンドロビン順序で次の順番のものが選択される。キュー２０、３０がそれぞれ解放するデータを有するが、キュー２０、３０のうち一方だけが、利用可能な帯域幅を有する場合、キュー２０、３０のうちその利用可能な帯域幅を有する方が選択される。キュー２０、３０の一方だけが、解放するデータと、利用可能な帯域幅を有する場合は、キュー２０、３０のうちその一方が選択される。キュー２０、３０がどちらも選択されない場合は、低優先度キュー４０、５０がチェックされる。より具体的には、キュー４０、５０が、それぞれ出力６０に解放すべきデータを有し、限定された帯域幅の低優先度キュー５０が利用可能な帯域幅を有する場合、キュー４０、５０のうちラウンドロビン順序で次の順番のものが選択される。キュー４０、５０が、それぞれ解放すべきデータを有するが、限定された帯域幅の低優先度キュー５０が利用可能な帯域幅を有さない場合は、限定されない帯域幅の低優先度キュー４０が選択される。キュー４０だけが解放すべきデータを有する場合、キュー４０が選択される。キュー５０だけが解放すべきデータを有する場合、キュー５０が利用可能な帯域幅を有する場合にはキュー５０が選択される。キュー４０、５０がどちらも選択されない場合は、出力６０にデータは解放されない。
【００１３】
次に図２を参照すると、好ましい共用出力スケジューリング装置が、関連するキュー構造と共に構成要素レベルで示されている。待ち行列化構造２１０は、それぞれの入力２１２の０〜Ｎでデータを受け取り、出力２１４へデータを解放するためのデータキュー０〜Ｎを含む。待ち行列化構造２１０からのデータの解放は、スケジューラ２００によって制御される。スケジューラ２００は、マネージャ２２０、多段セレクタ２３０、ドライバ２４０、および統計ブロック２５０を含む。マネージャ２２０は統計ブロックからデータを取り出し、セレクタ２３０および統計ブロック２５０を更新する。セレクタ２３０は、キュー選択を容易にするための選択マスク２３２、優先帯域幅セレクタ２３４、およびラウンドロビンアービタ２３６を含む。セレクタ２３０は、出力２１４へデータを解放するためのデータキューを選択し、キュー選択情報をドライバ２４０へ送る。ドライバ２４０は、キュー選択情報を受け取り、統計ブロック２５０からデータを取り出し、統計ブロック２５０を更新し、選択されたキューからのデータの解放を制御する。
【００１４】
次に図３を参照すると、セレクタ２３０がより詳細に示されている。セレクタ２３０は、イネーブル（ｅｎａｂｌｅｍｅｎｔ）マスク３１２、バックログマスク３１４、帯域幅マスク３１６、および優先度マスク３１８を含む選択マスク２３２を有する。マスクはそれぞれ、記憶要素２１０内のキュー０〜Ｎに対するステータスビットを保持する。イネーブルマスク３１２は、キュー０〜Ｎのうち、どれが出力２１４へデータを送るようにイネーブルされているかを示す。特定のキューのために予約されたビット位置が「１」であれば、イネーブルされていることを表し、「０」であれば、イネーブルされていないことを表す。バックログマスク３１４は、０〜Ｎのキューのうち、どれが出力２１４への送出を待っているかを示す。キューに対して予約されたビット位置が「１」であれば、未処理（ｐｅｎｄｉｎｇ）データの存在を表し、「０」であれば、未処理データが存在しないことを表す。帯域幅マスク３１６は０〜Ｎのキューのうち、どれが出力２１４へデータを送るための帯域幅を有するかを示す。「１」は帯域幅が利用可能であることを表し、「０」は帯域幅が利用不能であることを表す。優先度マスク３１８は、キュー０〜Ｎの優先度レベルを集合的に示す。各優先度レベルごとに別々の優先度マスクが保持される。ある優先度マスクで、特定のキューのために予約されたビット位置が「１」であれば、そのマスクの表す優先度レベルにそのキューが割り当てられていることを示し、「０」であれば、その優先度レベルに割り当てられていないことを示す。マスク２３２はマネージャ２２０によって構成設定可能である。バックログマスク３１４および帯域幅マスク３１６は、統計ブロック２５０から取り出された情報に応答して、マネージャ２２０によって更新される。
【００１５】
選択マスク２３２は、優先度帯域幅セレクタ２３４に結合されている。セレクタ２３４は、関与（ｐａｒｔｉｃｉｐａｎｔ）キューのうちからのラウンドロビン選択に、選択を還元することによって、キュー選択を容易にする。関与キューの選択がイネーブルされるとき、イネーブルマスク３１２、バックログマスク３１４、帯域幅マスク３１６、および優先度マスク３１８のうちの１つが、ビットごとの論理積演算のためにマスク比較ブロック３２４へ同時に提示される。優先度マスク３１８のうち、ビットごとの論理積演算処理にかけられる前記優先度マスクは、優先度カウンタ３２８によって決定され、優先度カウンタ３２８は、マルチプレクサ３２２に、カウンタ３２８の現在の値に基づいて、優先度マスク３１８のうちの１つを解放するよう指示する。関与キューの各選択ラウンドごとに、カウンタ３２８は、最初に最高の優先度マスクを選択し、現在の優先度レベルでウィナ選択イネーブル（ｗｉｎｎｅｒ  ｓｅｌｅｃｔ  ｅｎａｂｌｅｍｅｎｔ）が示されるまで、またはすべての優先度マスクが処理にかけられるまで、次々にすぐ下の優先度の優先度マスクを選択する。
【００１６】
マスク比較ブロック３２４により処理されるビットごとの論理積演算の結果は、現在の優先度レベルにキューがあるなら、どのキューがラウンドロビンアービタ２３６で処理されるウィナ選択（ｗｉｎｎｅｒ  ｓｅｌｅｃｔｉｏｎ）に関与する資格があるかを示すマスクである。具体的には、結果として生じる前記マスクは、下記のようなキューがあれば、そのキューのために予約されたすべてのビット位置で「１」を有する。そうしたキューとは、出力ポート２１４に対してイネーブルされており、未処理データを有し、利用可能な帯域幅を有し、しかも現在の優先度レベルにあるものである。結果として生じる前記マスクは、他のビット位置では「０」を有する。したがって結果として生じる前記マスクは、関与キューを「１」、非関与キューを「０」で示す。結果、マスクは、論理和演算のためにウィナ選択イネーブルブロック３２６に提示される。結果マスクの少なくとも１つのビット位置が「１」を有する場合は、前記論理和演算は「１」を生じ、ウィナ選択はそのときの優先度レベルでイネーブルされる。そうでない場合は、前記論理和演算は「０」となり、ウィナ選択は現在の優先度レベルでイネーブルされず、次の優先度レベルがあるならば、その優先度レベルで前記論理積演算が処理される。前記論理和演算結果は、追加の優先度マスク選択が必要かどうかをカウンタ３２８に通知するために、フィードバックとして供給される。すべての優先度レベルで、前記ビットごとの論理積演算の結果として「ヌル」マスクが生ずる場合、ウィナ選択はイネーブルされず、ラウンドロビンアービトレーションが実施されないことを理解されたい。
【００１７】
優先度帯域幅セレクタ２３４は、ラウンドロビンアービタ２３６に結合されている。ラウンドロビンアービタ２３６は、セレクタ２３４で決定された関与キューのうちから、ラウンドロビン選択によってウィニングキュー（ｗｉｎｎｉｎｇｑｕｅｕｅ）を決定する。図４に移ると、ラウンドロビンアービタ２３６がより詳細に示されている。ウィナ選択がイネーブルされるとき、関与キューマスク、すなわちセレクタ２３４で実行されるビットごとの論理積演算の結果得られるマスクが、候補キュー決定のため予備選択配列４１０に提示される。具体的には、配列４１０中の各予備選択要素は、関与キューマスクからビットの一部分を受け取り、関与キューのうちから、それが表す単一の候補キュー（ｑｕａｌｉｆｙｉｎｇ  ｑｕｅｕｅ）を選択する。より具体的には、その候補キューが直前のラウンドロビンアービトレーションで最終選択ブロック４２０によってウィニングキューとして選択された予備選択要素は、その関与キューのうちラウンドロビン順序で次の順番にあたるキューがあればそれを候補キューとして選択する。それ以外の予備選択要素は、その予備選択要素のそれぞれの関与キューのうち最初のものを候補キューとして選択する。候補キューセレクションは、何の関与キューも表さない予備選択要素があれば、そこからの「候補なし（ｎｏ  ｑｕａｌｉｆｉｅｒ）」通知と共に、最終選択ブロック４２０へ提示される。さらに、その候補キューが直前のウィニングキューとして選ばれた予備選択要素が、ラップアラウンド（ｗｒａｐ−ａｒｏｕｎｄ）した、つまり選択を行う過程で予備選択要素のラウンドロビン順序で最後のキューから最初のキューに戻った場合、予備選択要素は、「ラップアラウンド」通知を最終選択ブロック４２０に提示する。最終選択ブロック４２０は、その候補キューが直前のウィニングキューとして選択された予備選択要素からの候補キューを、その予備選択要素が「候補なし」または「ラップアラウンド」通知を提示したのでない限り、ウィニングキューとして選択する。その予備選択要素が「候補なし」または「ラップアラウンド」通知を提示した場合は、最終選択ブロック４２０は、予備選択要素のうちラウンドロビン順序で次の順番のものからの候補キューをウィニングキューとして選択する。ラウンドロビンアービトレーションが完了したときに最終選択ブロック４２０は、ウィニングキュー識別子（ＩＤ）をキュードライバ２４０に送る。ウィニングキュー識別子はまた、後続の候補キュー選択で予備選択要素が使用するために、配列４１０へフィードバックとして供給される。
【００１８】
図５と一緒に図２を参照すると、セレクタ２３０から受け取ったウィニングキュー識別子に応答して、ドライバ２４０は、統計ブロック２５０を照会してキューの状態情報を取り出し、ウィニングキューから出力２１４へのデータ解放を制御する。統計ブロック２５０は、待ち行列化構造２１０内の各キュー０〜Ｎごとに、キュー識別子、ヘッドポインタ、テールポインタ、現デプス、最大デプス、現クレジット、および全クレジットの値を含むマルチフィールドエントリを保持する。ウィニングキュー識別子は、統計ブロック２５０での対応するエントリを「ルックアップ」するために使われる。対応するエントリについて、所定のクレジット量が、現クレジット値に加えられる。クレジット量は、例えばイーサネットパケットにでは１５１８バイトとするなど、有利には個々のプロトコルに従ってフォーマットされたパケットの最大長との関連で選択することができる。ドライバ２４０は、ウィニングキューから出力２１４へのデータ解放が対応するエントリ中のヘッドポインタによって示されるキュー位置のデータから始めて、すべてのデータがウィニングキューから解放されるか、現クレジットが使い果たされているか、または限定された帯域幅のキューである場合は全クレジットが使い果たされるかのうちのいずれかが最初に起こるまでデータ解放を制御する。ドライバ２４０は、変化するキュー状態を反映するように、ヘッドポインタ、現デプス、全クレジット、および相当するエントリについての現クレジット値をデータ解放時に更新する。すべてのデータが解放されてしまっている場合、または限定された帯域幅のキューであるケースで現クレジットの前に全クレジットが使い果たされている場合に現クレジット値は「ゼロ」にされる。
【００１９】
マネージャ２２０は、選択マスク２３２がドライバ２４０によってなされたキュー状態変化を確実に反映するために統計ブロック２５０に照会する。バックログマスク３１２をリフレッシュするために、エントリでの現デプス値が照会され、帯域幅マスク３１６をリフレッシュするために、エントリでの全クレジット値が照会される。マネージャ２２０はまた、限定された帯域幅のキューごとに保持されるエントリーでの全クレジット値を周期的にリフレッシュする。
【００２０】
次に図６に移ると、優先度帯域幅キュー選択のフローダイアグラムが示されている。関与キュー選択がイネーブルされ（６１０）、最高の優先度が、現優先度として選択される（６２０）。現優先度での関与キューが、キューイネーブル、バックログおよび帯域幅状態、および優先度に基づいて決定される（６３０）。少なくとも１つの現優先度の関与キューがある場合（６４０）、ウィナ選択がイネーブルされ、ラウンドロビンアービタに通知される（６５０）。そうでない場合、次に高い優先度が、現優先度として選択される（６６０）。すべての優先度がチェックされてはいない場合、フローはステップ６３０に戻る。そうでなければフローは終了する（６７０）。
【００２１】
図７に移ると、代表的な予備選択要素についてラウンドロビンアービトレーションでの候補キュー選択のフローダイアグラムが示されている。前記要素は、その要素が代表するキューについての情報を受け取り（７１０）、直前のウィニングキューがその要素の直前の候補キューであったかどうかをチェックする（７２０）。直前のウィニングキューが前記要素の直前の候補キューである場合、その要素は、その要素が表すラウンドロビン順序で次の（関与または非関与）キューを選択する（７３０）。直前のウィニングキューが前記要素の直前の候補キューでない場合、その要素は、その要素が表す最初の（関与または関与）キューを現キューとして選択する（７４０）。どちらの場合でも、前記要素は、現キューがこの選択ラウンドで関与についてすでにチェックされているかどうかをチェックする（７５０）。現キューが関与についてすでにチェックされている場合、前記要素は、この選択ラウンドで候補キューを持たず、最終選択ブロックにその旨が通知される（７５５）。現キューが関与についてまだチェックされていない場合、現キューはチェックされる（７６０）。現キューが関与キューである場合、現キューは候補キューであり、最終選択ブロックに通知される（７６５）。現キューが関与キューでない場合、さらにチェックが行われ、現キューが前記要素の表す最後のキューかどうかが判定される（７７０）。現キューが最後のキューである場合、前記要素はラップアラウンドし、最終選択ブロックに通知され、フローはステップ７４０に戻る。現キューが最後のキューでない場合、フローはステップ７３０に戻る。
【００２２】
最後に図８に移ると、ラウンドロビンアービトレーションでのウィニングキュー選択フローダイアグラムが示されている。候補キュー、「候補なし」通知、および「ラップアラウンド」通知があればそれが受け取られ（８１０）、候補キューが直前のアービトレーションを勝ち残った予備選択が、現要素として選ばれる（８２０）。現要素が、この選択ラウンドで候補キューを有するかどうかチェックされる（８３０）。現要素が、この選択ラウンドで候補キューを有する場合、現要素がラップアラウンドしたかどうかさらにチェックされる（８４０）。現要素がラップアラウンドしていない場合、現要素からの候補キューがウィニングキューであり、キュードライバおよび要素に通知され、このフローが終了する（８５０）。しかし、現要素が候補キューを有さないか、現要素がラップアラウンドした場合、ラウンドロビン順序で次の要素が現要素として選択される（８６０）。新しい現要素が、この選択ラウンドですでにチェックされている場合（８７０）、前の要素が現要素として戻され、フローはステップ８５０に進む。新しい現要素が、この選択ラウンドでまだチェックされていない場合、フローはステップ８３０に戻る。
【００２３】
本発明の趣旨または本質的特徴から逸脱することなく、本発明は、他の特定の形態で実施できることを、当業者は理解されよう。したがってこの記述は、あらゆる点において例示的であって、限定的なものでないと考えられる。本発明の範囲は添付の請求の範囲によって示され、本発明の均等物の意味および範囲に含まれるあらゆる変更形態は、本発明に包含されるものとする。
【図面の簡単な説明】
【図１】スケジューリングの機能を備えた例示的な共用出力待ち行列化構造をポリシーレベルで示す図である。
【図２】共用出力待ち行列化構造および関連する待ち行列化構造についての好ましいスケジューリング装置のブロックダイアグラムである。
【図３】図２の多段セレクタのブロックダイアグラムである。
【図４】図２のラウンドロビンアービタのブロックダイアグラムである。
【図５】図２の統計ブロックの、ブロックダイアグラムである。
【図６】優先度帯域幅キュー選択ステップのブロックダイアグラムである。
【図７】ラウンドロビンアービトレーションの候補キュー選択ステップのフローダイアグラムである。
【図８】ラウンドロビンアービトレーションのウィニングキュー選択ステップのフローダイアグラムである。
【符号の説明】
１０  限定されない帯域幅の高優先度キュー
２０、３０  限定された帯域幅の中優先度キュー
４０  限定されない帯域幅の低優先度キュー
５０  限定された帯域幅の低優先度キュー
２１０  待ち行列化構造（記憶要素）
２１２  入力
２２０  マネージャ
２３２  選択マスク
２３４  優先度帯域幅セレクタ
２３６  ラウンドロビンアービタ
２４０  ドライバ
２５０  統計ブロック
３１２  イネーブルマスク
３１４  バックログマスク
３１６  帯域幅マスク
３１８  優先度マスク
３２４  マスク比較ブロック
３２６  ウィナー選択イネーブルブロック
３２８  優先度カウンタ
４１０  予備選択配列
４２０  最終選択ブロック
【図１】
0004750955.tif 000002
【図２】
0004750955.tif 000003
【図３】
0004750955.tif 000004
【図４】
0004750955.tif 000005
【図５】
0004750955.tif 000006
【図６】
0004750955.tif 000007
【図７】
0004750955.tif 000008
【図８】
0004750955.tif 000009