(57)【要約】【課題】  制限されたシステム帯域幅へのアクセスを提供するための改善された階層型スケジューリング方法を提供すること。【解決手段】  本発明の第１の態様において、階層型スケジューリングのための第１の方法が提供される。この第１の方法は、（１）各々が複数のパイプ・フローを含む１つ又はそれ以上のパイプからデータを受信するステップと、（２）データが伝送されることになる勝者パイプを、該勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、１つ又はそれ以上のパイプから選択するステップと、（３）選択されるパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、勝者パイプ内に含まれる複数のパイプ・フローからパイプ・フローを選択するステップと、（４）選択されたパイプ・フローからデータを伝送するステップとを含む。他の多数の態様も提供される。【選択図】      図３
2007507938.tif 000002
【特許請求の範囲】
【請求項１】
階層型スケジューリング方法であって、
各々が複数のパイプ・フローを含む１つ又はそれ以上のパイプからデータを受信するステップと、
データが伝送されることになる勝者パイプを、前記勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記１つ又はそれ以上のパイプから選択するステップと、
選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記勝者パイプ内に含まれる前記複数のパイプ・フローからパイプ・フローを選択するステップと、
前記選択されたパイプ・フローからデータを伝送するステップと
を含む方法。
【請求項２】
前記選択されたパイプ・フローからデータを伝送するステップは、前記勝者パイプ・フローに対応する帯域幅を用いて、前記選択されたパイプ・フローからデータを伝送するステップを含む、請求項１に記載の方法。
【請求項３】
データが伝送されることになる勝者パイプを、前記勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記１つ又はそれ以上のパイプから選択する前記ステップは、パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、パイプを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込むステップと、前記メモリ・アドレスのグループを走査してパイプを識別するデータを見つけ出すステップとを含む、請求項１又は請求項２に記載の方法。
【請求項４】
前記勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、該勝者パイプを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに再書き込みするステップをさらに含む、請求項３に記載の方法。
【請求項５】
選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記勝者パイプ内に含まれる前記複数のパイプ・フローからパイプ・フローを選択する前記ステップは、
パイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、パイプ・フローを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込むステップと、
前記メモリ・アドレスのグループを走査してパイプ・フローを識別するデータを見つけ出すステップと、
前記選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記識別されたパイプ・フローを前記勝者パイプに対応するキューに書き込むステップと、
前記勝者パイプに対応する前記キューから前記識別されたパイプ・フローを選択するステップと
を含む、請求項１、請求項２、又は請求項３に記載の方法。
【請求項６】
前記選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記選択されたパイプ・フローを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込むステップをさらに含む、請求項５に記載の方法。
【請求項７】
階層型スケジューリング方法であって、
パイプ内に含まれるパイプ・フローを識別するデータを受信するステップと、
前記パイプに関するデータを第１のカレンダーに書き込むステップと、
前記パイプ・フローに関するデータを第２のカレンダーに書き込むステップと、
勝者パイプを定めるために前記第１のカレンダーを走査するステップと、
勝者パイプ・フローを定めるために前記第２のカレンダーを走査するステップと、
前記勝者パイプ・フローを対応するパイプ・キューに書き込むステップと、
前記勝者パイプを用いて、対応するパイプ・キューからパイプ・フローを選択するステップと、
前記選択されたパイプ・フローからデータを伝送するステップと
を含む方法。
【請求項８】
前記勝者パイプ・フローに関するデータを前記第２のカレンダーに再書き込みするステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記勝者パイプに関するデータを前記第１のカレンダーに再書き込みするステップをさらに含む、請求項７又は請求項８に記載の方法。
【請求項１０】
１つ又はそれ以上のパイプ及びパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータを格納するように適合された少なくとも１つのメモリと、
前記少なくとも１つのメモリに接続され、かつ、各々が複数のパイプ・フローを含む１つ又はそれ以上のパイプからデータを受信し、勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、データが伝送されることになる勝者パイプを、前記１つ又はそれ以上のパイプから選択し、前記選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記勝者パイプ内に含まれる前記複数のパイプ・フローからパイプ・フローを選択し、前記選択されたパイプ・フローからデータを伝送するように適合されたスケジューラ論理と
を備えるネットワーク・プロセッサ。
【請求項１１】
前記スケジューラ論理は、サービスがスケジュールされた自律型フロー及びパイプの少なくとも１つを格納するための一次カレンダーと、サービスがスケジュールされたパイプ・フローを格納するための二次カレンダーと、勝者パイプ・フローを前記パイプ・フローに対応するパイプのためのキューに格納するためのパイプ・キュー・テーブルとを備える、請求項１０に記載のネットワーク・プロセッサ。
【請求項１２】
前記スケジューラ論理は、サービスされることになる自律型フロー及びパイプ・フローの少なくとも１つをスケジュールするためのエンキュー・新規アタッチ論理と、サービスされることになる自律型フロー及びパイプ・フローの少なくとも１つを選択するためのデキュー・再アタッチ論理とをさらに備える、請求項１１に記載のネットワーク・プロセッサ。
【請求項１３】
前記スケジューラ論理は、前記勝者パイプ・フローに対応する帯域幅を用いて、前記選択されたパイプ・フローからデータを伝送するようにさらに適合される、請求項１０、請求項１１、又は請求項１２に記載のネットワーク・プロセッサ。
【請求項１４】
前記スケジューラ論理は、パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、パイプを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込み、前記メモリ・アドレスのグループを走査してパイプを識別するデータを見つけ出すようにさらに適合される、請求項１０から請求項１３までのいずれか１項に記載のネットワーク・プロセッサ。
【請求項１５】
前記スケジューラ論理は、前記勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記勝者パイプを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに再書き込みするようにさらに適合される、請求項１４に記載のネットワーク・プロセッサ。
【請求項１６】
前記スケジューラ論理は、パイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、パイプ・フローを識別するデータをメモリ・アドレス・グループ内のメモリ・アドレスに書き込み、前記メモリ・アドレスのグループを走査してパイプ・フローを識別するデータを見つけ出し、前記選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、前記識別されたパイプ・フローを前記勝者パイプに対応するキューに書き込み、前記勝者パイプに対応する前記キューから前記識別されたパイプ・フローを選択するようにさらに適合される、請求項１０から請求項１５までのいずれか１項に記載のネットワーク・プロセッサ。
【請求項１７】
前記スケジューラ論理は、前記選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、該選択されたパイプ・フローを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込むようにさらに適合される、請求項１６に記載のネットワーク・プロセッサ。
【請求項１８】
１つ又はそれ以上のパイプ及びパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータを格納するように適合された少なくとも１つのメモリと、
前記少なくとも１つのメモリに接続され、かつ、パイプ内に含まれるパイプ・フローを識別するデータを受信し、前記パイプに関するデータを前記第１のカレンダーに書き込み、前記パイプ・フローに関するデータを前記第２のカレンダーに書き込み、勝者パイプを定めるために前記第１のカレンダーを走査し、勝者パイプ・フローを定めるために前記第２のカレンダーを走査し、前記勝者パイプ・フローを対応するパイプ・キューに書き込み、前記勝者パイプを用いて、対応するパイプ・キューからパイプ・フローを選択し、前記選択されたパイプ・フローからデータを伝送するように適合された、第１のカレンダー及び第２のカレンダーを含むスケジューラ論理と
を備えるネットワーク・プロセッサ。
【請求項１９】
前記スケジューラ論理は、勝者パイプ・フローを前記パイプ・フローに対応するパイプのためのキューに格納するためのパイプ・キュー・テーブルと、サービスされることになる自律型フロー及びパイプ・フローの少なくとも１つをスケジュールするためのエンキュー・新規アタッチ論理と、サービスされることになる自律型フロー及びパイプ・フローの少なくとも１つを選択するためのデキュー・再アタッチ論理とをさらに含む、請求項１８に記載のネットワーク・プロセッサ。
【請求項２０】
前記スケジューラ論理は、前記勝者パイプ・フローに関するデータを前記第２のカレンダーに再書き込みするようにさらに適合される、請求項１８又は請求項１９に記載のネットワーク・プロセッサ。
【請求項２１】
前記スケジューラ論理は、前記勝者パイプに関するデータを前記第１のカレンダーに再書き込みするようにさらに適合される、請求項１８、請求項１９、又は請求項２０に記載のネットワーク・プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、ネットワーク・プロセッサに関し、より具体的には、階層型スケジューリングのための方法及び装置に関する。
【背景技術】
【０００２】
ネットワーク・プロセッサは、ネットワーク・プロセッサの入力ポートを介して、コンピュータといった１つ又はそれ以上のネットワーク装置に接続させることが可能である。ネットワーク・プロセッサの各出力ポートは、制限されたシステム帯域幅のネットワークに接続される。そのネットワークによって、一度に一定量のデータしか伝送することができない。
【０００３】
ネットワークへのアクセスを確実にするために、消費者は、システム帯域幅の所有者から該システム帯域幅の一部へのアクセス権を購入することを厭わない。したがって、システム帯域幅の所有者は、該システム帯域幅を部分に分け、該部分を１人又はそれ以上の消費者に販売することができる。一般に、システム帯域幅の部分の購入者は、常時該システム帯域幅の購入した部分の全てを使用するわけでない。その結果、収益を増大させるために、システム帯域幅の所有者は、一般に、一度に利用可能なものより多くのシステム帯域幅を販売する（すなわち、申し込み超過になる）。消費者がシステム帯域幅の購入した部分の全体を使用したいと願う場合、該消費者は、余分な帯域幅（例えば、別の消費者によって購入されたが、その時点で使用されていない帯域幅）を一時的に使用することができる。しかしながら、多数の消費者が購入した帯域幅の全て又は大部分を同時に使用しようとした場合、帯域幅の可用性は予測できない。一部の消費者は、システム帯域幅の購入した部分全体を使用できるが、他の消費者は、購入した帯域幅の一部しか使用することができない可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって、制限されたシステム帯域幅へのアクセスを提供する改善されたシステムが必要とされる。
【課題を解決するための手段】
【０００５】
本発明の第１の態様において、階層型スケジューリングのための第１の方法が提供される。この第１の方法は、（１）各々が複数のパイプ・フローを含む１つ又はそれ以上のパイプからデータを受信するステップと、（２）データが伝送されることになる勝者パイプを、勝者パイプに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、１つ又はそれ以上のパイプから選択するステップと、（３）選択されたパイプ・フローに対応する１つ又はそれ以上のサービス品質パラメータに基づいて、勝者パイプ内に含まれる複数のパイプ・フローからパイプ・フローを選択するステップと、（４）選択されたパイプ・フローからデータを伝送するステップとを含む。
【０００６】
本発明の第２の態様において、階層型スケジューリングのための第２の方法が提供される。この第２の方法は、（１）パイプ内に含まれるパイプ・フローを識別するデータを受信するステップと、（２）パイプに関するデータ（例えば、イベント・データ）を第１のカレンダーに書き込むステップと、（３）パイプ・フローに関するデータ（例えば、イベント・データ）を第２のカレンダーに書き込むステップと、（４）勝者パイプを定めるために第１のカレンダーを走査するステップと、（５）勝者パイプ・フローを定めるために第２のカレンダーを走査するステップと、（６）勝者パイプ・フローを対応するパイプ・キューに書き込むステップと、（７）勝者パイプを用いて、対応するパイプ・キューからパイプ・フローを選択するステップと、（８）選択されたパイプ・フローからデータを伝送するステップとを含む。本発明のこれらの他の態様に従ったシステム及び装置である、他の多数の態様が提供される。
【０００７】
本発明の他の特徴及び態様は、以下の詳細な説明、添付の特許請求の範囲、及び添付の図面に基づいてより十分に明らかになるであろう。
【発明を実施するための最良の形態】
【０００８】
図１は、従来のネットワーク・プロセッサ・システム１００の例示的な概略図である。ネットワーク・プロセッサ・システム１００は、ネットワーク・プロセッサ１０２を含むことができる。ネットワーク・プロセッサ１０２は、自律型フロー１０４−１１８又はパイプ１２０、１２２、１２４からデータを受信することができる。自律型フロー及びパイプは、対等なものである（例えば、システム帯域幅について同等に競合する）。各々の自律型フロー１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８は、ネットワーク・プロセッサ１０２から別のネットワーク装置（図示せず）への個別接続を示す。各々のパイプ１２０、１２２、１２４は、１つ又はそれ以上のパイプ・フロー１３０を含むことができる。パイプ・フロー１３０は、ネットワーク・プロセッサ１０２から別のネットワーク装置（図示せず）への個別接続を示し、ネットワーク装置への他の個別接続と共にグループ化され、パイプ１２０、１２２、１２４を形成する（例えば、インターネット・サービス・プロバイダは、システム帯域幅の所有者から、パイプ・フローを含むパイプを購入し、個別のパイプ・フローを消費者に販売することができる）。
【０００９】
図１に示される従来のネットワーク・プロセッサ・システム１００において、ネットワーク・プロセッサ１０２は、複数の自律型フロー１０４−１１８及び各々が複数のパイプ・フロー（例えば、１３０）を含む複数のパイプ１２０、１２２、１２４から、データを受信する。受信したデータは、同じ出力ポート１３２から伝送されることになる。ネットワーク・プロセッサ１０２の各出力ポート１３２（１つの出力ポート１３２だけが示されている）は、制限されたシステム帯域幅を有するネットワーク接続に接続される。したがって、全ての自律型フロー及びパイプからのデータが同時にサービスされない可能性がある（すなわち、各々の自律型フロー又はパイプからのデータが、同時に伝送されない可能性がある）。図１に示される従来のネットワーク・プロセッサ１０２においては、全ての自律型フロー１０４−１１８又はパイプ１２０−１２４に、例えば、高優先順位、中優先順位、低優先順位などの優先順位と帯域幅とを割り当てることができる。自律型フロー又はパイプに割り当てられた優先順位は、自律型フロー又はパイプをサービスする頻度を決定する。自律型フロー又はパイプに割り当てられる帯域幅は、サービスするときに自律型フロー又はパイプが利用可能なシステム帯域幅の部分を決定する。
【００１０】
図１に示される従来のネットワーク・プロセッサ・システム１００は、サービスすることになる自律型フロー及び／又はパイプをスケジュールするために、各優先順位タイプについて別個のカレンダー（例えば、高優先順位カレンダー、中優先順位カレンダー、及び低優先順位カレンダー）を使用することができる。こうしたカレンダーの各々は、メモリ・アドレスのグループを含み、このメモリ・アドレスのグループは、サービスを必要とする自律型フロー又はパイプを識別するエントリについて繰り返しチェックされる。代替的に、単一のカレンダーが、１つ又はそれ以上の優先順位タイプの自律型フロー及び／又はパイプを識別するエントリを含むこともできる。カレンダーのメモリ・アドレスの異なるグループ又は領域を用いて、各優先順位タイプの自律型フロー及び／又はパイプを識別するエントリを格納することができる。これらのグループの各々を繰り返し、サービスを必要とするエントリを識別する。メモリ・アドレス・グループを繰り返しチェックするとき、各々の一連の時間単位中に、第１の時間単位中にグループ内の第１のメモリ・アドレスを指示するポインタを進め、グループ内の次のメモリ・アドレスを指示させることができる。時間単位中にカレンダーの最後のアドレスがチェックされたとき、次の時間単位中にカレンダーの第１のアドレスをチェックすることができる。したがって、便宜上、本明細書中のカレンダーは、単一のボックスとして概略的に示され、単数形で称されるが、カレンダーは、複数の優先順位を含む単一のカレンダー、又は、好ましくは各々が単一の優先順位だけを含む一組のカレンダーを含み得ることが理解されるであろう。
【００１１】
カレンダー内のスケジュールされたエントリのメモリ・アドレスと、現在カレンダー内でチェックされているメモリ・アドレスとの間の距離が大きい程、スケジュールされるカレンダーのエントリによって識別される自律型フロー又はパイプのサービスを、より長い時間待たなければならない。ネットワーク・プロセッサ１０２が受信するデータを用いて、該データに対応する自律型フロー又はパイプを識別することができる。予め割り当てられた優先順位及び帯域幅に基づいて、ネットワーク・プロセッサ１０２は、自律型フロー又はパイプについての、カレンダー内の適切なメモリ・アドレスを決定することができる。
【００１２】
ネットワーク・プロセッサ・システム１００が、各々が異なる優先順位タイプを有する複数のカレンダーを含むとき、ある時間単位中（例えば、スケジューリング機会中）にサービスを必要とする自律型フロー又はパイプを識別する低優先順位のカレンダーからのエントリは、その時間単位中にサービスを必要とする自律型フロー又はパイプを識別する高優先順位カレンダー及び／又は中優先順位カレンダー内のエントリがサービスされるまで、勝者として選択されず、サービスされない。同様に、ある時間単位中にサービスを必要とする自律型フロー又はパイプを識別する中優先順位カレンダー内のエントリは、その時間単位中にサービスを必要とする自律型フロー又はパイプを識別する高優先順位カレンダー内の全てのエントリがサービスされるまで、勝者として選択されず、サービスされない。
【００１３】
図１の従来のネットワーク・プロセッサ・システムにおいて、自律型フローをサービスすべきことが識別された場合、該自律型サービスから受信したデータが、出力ポート１３２から伝送される。対照的に、パイプは１つ又はそれ以上のパイプ・フローを含むので、カレンダーがサービスを必要とするパイプを識別したときに、付加的な参照を行わなければならない。ネットワーク・プロセッサは、パイプ内に含まれる全てのパイプ・フローを含む各フローについてのテーブルを保持しなければならない。各テーブルは、該テーブルからサービスされた最後のパイプ・フローを示す。カレンダーが、サービスを必要とするパイプを識別したとき、識別されたパイプに対応するテーブル内の参照が行われ、該テーブル内の次のパイプ・フローがサービスされる。
【００１４】
図２は、図１の従来のネットワーク・プロセッサ・システム１００内に含まれるスケジューラ論理２００のブロック図である。サービスされることになる自律型フロー又はパイプをスケジュールするために、従来のネットワーク・プロセッサ・システム１００によって、スケジューラ論理２００を使用することができる。スケジューラ論理２００は、主カレンダー２０２（様々な優先順位の１つ又はそれ以上のカレンダーを含むことができる）を含むことができる。主カレンダー２０２は、（例えば、エンキュー・新規アタッチ論理２０８及びアービトレーション・ユニット２１０を介して）メモリ２０４に、かつ、（例えば、デキュー・再アタッチ論理２１２を介して）各パイプについてのパイプ・フローのテーブル２０６に接続することができる。アービトレーション・ユニット２１０は、メモリ２０４との間の読み取り及び書き込みをアービトレートする。例えば、エンキュー・新規アタッチ論理２０８は、パイプを識別するデータを受信することができる。エンキュー・新規アタッチ論理２０８は、（例えば、アービトレーション・ユニット２１０を介して）メモリ２０４にアクセスし、受信したデータによって識別されるパイプが低優先順位のものであり、特定の帯域幅に割り当てられると判断することができる。この情報に基づいて、エンキュー・新規アタッチ論理２０８は、受信したデータに対応するパイプを識別するエントリを書き込む主カレンダー２０２における適切なアドレスを判断して、識別するエントリをそこに書き込む（すなわち、サービスされることになるパイプをスケジュールする）。
【００１５】
エントリを主カレンダー２０２に書き込むとき、該エントリを単一のエントリとして主カレンダー２０２の場所に書き込むことができる。カレンダーに書き込まれるエントリは、自律型フロー又はパイプ（本例においては、パイプ）に対応する制御構造へのポインタ（下記に詳述される）とすることができる。しかしながら、便宜上、カレンダー内のエントリを、制御構造へのポインタではなく、自律型フロー又はパイプ自体と呼ぶ。
【００１６】
カレンダーの作動について説明したときに上述したように、主カレンダー２０２は、サービスを必要とするパイプ又は自律型フローを識別するエントリについて、メモリ・アドレスをチェックする。主カレンダー２０２が、ある時間単位中に受信されたデータに対応するパイプを識別するエントリに達したとき、該主カレンダー２０２は、サービスされることになるそのパイプのエントリを選択し（すなわち、そのパイプを勝者として選択し）、その単位時間中にサービスを必要とする該カレンダーからの高優先順位エントリがないと仮定する。
【００１７】
上述のように、パイプは１つ又はそれ以上のパイプ・フローを含むので、主カレンダー２０２が時間単位中にサービスを必要とするパイプを識別するとき、付加的な参照を行わなければならない。したがって、主カレンダー２０２が、サービスを必要とする低優先順位のパイプを識別し（すなわち、勝者を選択し）、同じ時間単位中にサービスを必要とするより高優先順位のパイプがないと仮定するとき、スケジューラ論理２００は、（例えば、デキュー・再アタッチ論理２１２を介して）各パイプについてのパイプ・フローを列挙するテーブル２０６における参照を行う。このように、スケジューラ論理２００は、識別されるパイプに対応するパイプ・フローのテーブルを参照する。このテーブルは、サービスされることになる次のパイプ・フローを示す。そのパイプ・フローが、サービスされる（すなわち、そのパイプ・フローからのデータが、ネットワーク・プロセッサ・システム１００の出力ポート１３２から伝送される）。
【００１８】
従来のネットワーク・プロセッサ・システム１００は、パイプ内に含まれるパイプ・フローを区別する手段を提供していない。いずれかのパイプ・フローが二度目にサービスされる前に、各パイプ・フローを一度サービスする。したがって、従来のネットワーク・プロセッサ・システム１００は、高優先順位のフロー及び低優先順位のフローの両方について、一様に低速で伝送する。しかしながら、パイプ・フローは様々なサイズ及び重要度を有するデータを含むことができることから、ネットワーク管理者は、第２のパイプ・フローを一度サービスする前に、第１のパイプ・フローを多数回サービスすることを望むことがある。また、ネットワーク管理者は、第１のパイプ・フローをサービスする際に大きな帯域幅を用い、第２のパイプ・フローをサービスする際に小さな帯域幅を用いることを望むこともある。
【００１９】
本発明は、パイプ内のパイプ・フローを区別する階層型スケジューリングのための方法及び装置を提供するものであり、図３及び図４を参照して以下に説明される。
【００２０】
図３は、階層型スケジューリングのための本発明の方法及び装置を実装することができる例示的なスケジューラ論理３００のブロック図である。例示的なスケジューラ論理３００を、ネットワーク・プロセッサ・システム（例えば、図１に示される従来のネットワーク・プロセッサ・システムに類似したネットワーク・プロセッサ・システム）内に含ませることができる。従来のネットワーク・プロセッサ・システム１００におけるように、本発明のスケジューラ論理３００を含むネットワーク・プロセッサ・システム（図示せず）は、自律型フロー及び／又はパイプからデータを受信することができる。自律型フロー及びパイプは、対等なものである。各々のパイプは、１つ又はそれ以上のパイプ・フローを含むことができる。従来のネットワーク・プロセッサ・システム１００とは対照的に、スケジューラ論理３００は、パイプ・フローをスケジュールするために使用される二次カレンダー３１０と、所定のパイプに対応する１つ又はそれ以上のパイプ・フローを含むことができるパイプ・キュー・テーブル３１４とを含む。二次カレンダー３１０及びパイプ・キュー・テーブル３１４については、以下に詳述される。
【００２１】
スケジューラ論理３００は、（例えば、アービトレーション・ユニット３０６を介して）メモリ３０４に接続されるエンキュー・新規アタッチ論理３０２を含む。従来のスケジューラ論理２００におけるように、アービトレーション・ユニット３０６は、メモリ３０４との間の読み取り及び書き込みをアービトレートする。エンキュー・新規アタッチ論理３０２は、（例えば、自律型フロー又はパイプ・フローなどの）フローを識別するデータを受信することができる。図２に示される従来のスケジューラ論理２００のメモリ２０４におけるように、各々の自律型フロー又はパイプについての優先順位及び帯域幅を格納するように、スケジューラ論理３００のメモリ３０４を構成することができる。さらに、メモリ３０４は、各パイプ内に含ませ得る各パイプ・フローについての優先順位及び帯域幅を格納することもできる。
【００２２】
メモリ３０４を用いて、キューの構造を説明する情報（例えば、フローから受信したデータフレーム又はデータセルのキューの構造を説明する情報）を格納することもできる。例えば、システム初期化時に、メモリ３０４に格納される自律型フロー、パイプ、及び／又はパイプ・フローに対応する優先順位及び帯域幅情報を、ネットワーク管理者のようなユーザによって提供することが可能である。
【００２３】
データによって識別されたフロー（すなわち、自律型フロー又はパイプ・フロー）に基づいて、以下のサブヘッドラインのもとで説明されるように、エンキュー・新規アタッチ論理３０２が、識別されたフローに対応する優先順位及び帯域幅情報を取り出し、データが自律型フローであるか又はパイプ・フローであるかによってデータを異なるように処理する。
【００２４】
データによって識別されるフローが自律型フローに対応する
受信されたデータが自律型フローを識別する場合、その自律型フローに対応する優先順位及び帯域幅情報が、メモリ３０４から取り出される。エンキュー・新規アタッチ論理３０２は、データによって識別された自律型フローについて、エントリが一次（又は、主）カレンダー３０８内に存在するかどうかを判断する。前述のように、単一の一次カレンダー３０８だけが、図３のスケジューラ論理３００内に示されているが、異なる優先順位タイプに対応する付加的なカレンダーも存在し得る。識別された自律型フローについて、エントリが一次カレンダー３０８内に存在する場合、エンキュー・新規アタッチ論理３０２は、エントリを一次カレンダー３０８に書き込まない。識別された自律型フローについて、エントリが一次カレンダー３０８内に存在しない場合、その自律型フローに関するデータが一次カレンダー３０８に書き込まれる。従来のスケジューラ論理２００の主カレンダー２０２と同様に、一次カレンダー３０８は、（例えば、１つ又はそれ以上のカレンダー内に）メモリ・アドレスのグループを含み、このメモリ・アドレスのグループは、サービスを必要とする自律型フロー又はパイプを識別するエントリを繰り返しチェックする。
【００２５】
スケジューラ論理３００は、従来のスケジューラ論理２００によって用いられるものと同様の方法で、自律型フローのスケジューリングを処理する。エンキュー・新規アタッチ論理３０２は、自律型フローについてのカレンダー内の適切なメモリ・アドレスを決定する。例えば、自律型フローが低優先順位のものである場合、この自律型フローは、一次カレンダー３０８の低優先順位の部分内に配置される。さらに、自律型フローが一次カレンダーの低優先順位の部分に対して新しいエントリである場合、この自律型フローは、一次カレンダー内の該低優先順位の部分内で現在チェックされているメモリ・アドレスの近くに配置される。スケジュールされたエントリのメモリ・アドレスと、現在チェックされているカレンダーのメモリ・アドレスとの間の距離が大きい程、スケジュールされたカレンダーのエントリによって識別される自律型フロー又はパイプがサービスされるのを、より長い時間待たなければならない。一次カレンダーは、ある単位時間中に各々の優先順位グループからサービスを必要とするエントリを識別することができる。その後、識別されたエントリから、一次カレンダーは、時間単位中にサービスされることになる勝者を選択する。代替的に、サービスされることになる自律型フロー及び／又はパイプをスケジュールするために、各々の優先順位に対して別個のカレンダー（例えば、高優先順位カレンダー、中優先順位カレンダー、及び低優先順位カレンダー）を用いることもできる。こうしたカレンダーの各々は、サービスを必要とする自律型フロー又はパイプを識別するエントリについて繰り返しチェックされるメモリ・アドレスのグループを含む。したがって、便宜上、本明細書中のカレンダーは、単一のボックスとして概略的に示され、単数形で称されるが、カレンダーは、複数の優先順位を含む単一のカレンダー、又は、好ましくは各々が単一の優先順位のみを含む一組のカレンダーのいずれかを含み得ることが理解されるであろう。上記の例において、別個の一次カレンダーが各優先順位タイプについて使用される場合、エンキュー・新規アタッチ論理３０２は、自律型フローについての適切な一次カレンダー内の適切なメモリ・アドレスを決定する。各々の一次カレンダーは、時間単位中にサービスを必要とするエントリを識別することができる。最も高い優先順位の一次カレンダーからのサービスを必要とするエントリが、時間単位中にサービスされることになる勝者として選択される。
【００２６】
一次カレンダー３０８は、デキュー・再アタッチ論理３１２に接続することができる。一次カレンダー３０８は、選択された勝者に関して、デキュー・再アタッチ論理３１２に通知する。勝者が自律型フローである場合、自律型フローから受信されたデータは、その自律型フローに割り当てられた帯域幅を用いて、出力ポート１３２から伝送される。
【００２７】
エンキュー・新規アタッチ論理３０２と同様に、デキュー・再アタッチ論理３１２は、（例えば、アービトレーション・ユニット３０６を介して）メモリ３０４に接続することができる。デキュー・再アタッチ論理３１２は、勝者として選択された自律型フローに対応する優先順位及び帯域幅情報を、メモリ３０４から取り出すことができる。デキュー・再アタッチ論理３１２は、取り出された情報に基づいて、一次カレンダー３０８の適切なメモリ・アドレス内の自律型フロー・エントリを再アタッチ（例えば、再書き込み）し、サービスされることになる自律型フローを再びスケジュールする。
【００２８】
データによって識別されるフローがパイプ・フローに対応する
上述のように、スケジューラ論理３００は、メモリ３０４に接続されるエンキュー・新規アタッチ論理３０２を含む。エンキュー・新規アタッチ論理３０２は、（例えば、自律型フロー又はパイプ・フローなどの）フローを識別するデータを受信することができる。エンキュー・新規アタッチ論理３０２によって受信されたデータがパイプ・フローを識別した場合、そのパイプ・フローに対応する優先順位及び帯域幅情報をメモリ３０４から取り出すことができる。エンキュー・新規アタッチ論理３０２は、パイプ・フローを含むパイプに対応する優先順位及び帯域幅情報を、メモリ３０４から取り出すこともできる。上述のように、エンキュー・新規アタッチ論理３０２は、一次カレンダー３０８に接続することができる。
【００２９】
エンキュー・新規アタッチ論理３０２は、受信したデータによって識別されるパイプ・フローに対応するパイプについて、エントリが一次カレンダー３０８内に存在するかどうかを判断する。こうしたエントリが一次カレンダー３０８内に存在しない場合、パイプに関するデータは、自律型フローのものと類似した方法で、一次カレンダー３０８に書き込まれる。一次カレンダーは、上述のように機能し、識別されたエントリからサービスされる勝者を選択する。具体的には、一次カレンダー３０８を、デキュー・再アタッチ論理３１２に接続することができ、選択された勝者に関して該デキュー・再アタッチ論理３１２に通知することができる。
【００３０】
エンキュー・新規アタッチ論理３０２は、サービスされるように予めスケジュールされたパイプ・フローを含む二次カレンダー３１０に接続することができる。したがって、自律型フローについてのプロセスとは異なり、パイプ・フローが、受信したデータによって識別されたとき、二次カレンダー３１０がチェックされる。エンキュー・新規アタッチ論理３０２は、受信したデータによって識別されるパイプ・フローについて、エントリが二次カレンダー３１０内に存在するかどうかを判断する。存在しない場合、そのパイプ・フローに関するデータが、二次カレンダー３１０に書き込まれる。一次カレンダーと同様に、二次カレンダー３１０は、サービスを必要とするパイプ・フローを識別するエントリを繰り返しチェックするメモリ・アドレスの優先順位グループを含むことができる（例えば、１つ又はそれ以上のカレンダー内に）。二次カレンダーは、各々の優先順位グループから、ある時間単位中にサービスを必要とするエントリを該時間単位中に識別することができる。その後、識別されたエントリから、二次カレンダーは、その時間単位中にサービスされることになる勝者を選択する。
【００３１】
二次カレンダー３１０は、１つ又はそれ以上（例えば、２５６個）のパイプ・キューを格納できるパイプ・キュー・テーブル３１４（例えば、メモリ）に接続することができる。各々のパイプ・キューは、１つ又はそれ以上のパイプ・フロー・エントリを含む。二次カレンダー３１０は、二次カレンダー３１０から選択された勝者をパイプ・キュー・テーブル３１４に通知する。パイプ・キュー・テーブル３１４は、パイプ・フローである選択された勝者を、そのパイプ・フローを含むパイプについてのキュー上に配置する。
【００３２】
パイプ・キュー・テーブル３１４は、デキュー・再アタッチ論理３１２に接続される。一次カレンダーから、勝者（本例においては、パイプと仮定される）がデキュー・再アタッチ論理３１２に通知されたとき、デキュー・再アタッチ論理３１２は、一次カレンダー３０８からの勝者パイプに対応するパイプ・キュー・テーブル３１４内のキューから、パイプ・フローを選択する。デキュー・再アタッチ論理３１２は、そのパイプ・フローに割り当てられた帯域幅を用いて、ネットワーク・プロセッサ・システム（図示せず）の出力ポート１３２を通して、該パイプ・フローから受信されたデータを伝送する。
【００３３】
デキュー・再アタッチ論理３１２は、（例えば、アービトレーション・ユニット３０６を介して）メモリ３０４に接続することができる。デキュー・再アタッチ論理３１２は、二次カレンダー３１０から、勝者として選択されたパイプ・フローに対応する優先順位及び帯域幅情報を取り出すことができる。勝者として選択されたパイプ・フローを再びサービスするようにスケジュールするために、デキュー・再アタッチ論理３１２は、取り出された情報に基づいて、二次カレンダー３１０の適切なメモリ・アドレス内のパイプ・フロー・エントリを再アタッチする。同様に、デキュー・再アタッチ論理３１２は、取り出された情報に基づいて、一次カレンダー３０８から勝者として選択されたパイプに対応する優先順位及び帯域幅情報を取り出し、パイプ・フローを一次カレンダー３０８の適切なメモリ・アドレス内に再アタッチすることができる。
【００３４】
エンキュー・新規アタッチ論理３０２及びデキュー・再アタッチ論理３１２は、特定用途向け集積回路、プログラム可能な論理回路、又は同様の標準論理といった論理装置を含むことができることに留意すべきである。一次カレンダー３０８、二次カレンダー３１０、及びパイプ・キュー・テーブル３１４は、ＳＲＡＭ等のようなオンチップ・メモリを含むことができる。オフチップ・メモリのような他のメモリを使用することもできる。メモリ３０４は、例えば、ＤＲＡＭ等のような外部メモリとすることもできる。
【００３５】
ここで、フローから受信したデータの階層型スケジューリングの例示的な方法を示す図３及び図４を参照して、スケジューラ論理３００の作動について説明する。便宜上、全てのデータがパイプ・フローから受信されるものと仮定する。しかしながら、階層型スケジューリング方法は、パイプ・フロー及び／又は自律型フローからデータを受信するネットワーク・プロセッサ・システム上で用い得ることに留意すべきである。自律型フローのスケジューリング方法については上に説明されており、従来の方法に従って実行することができるので、繰り返し説明しない。
【００３６】
図３及び図４を参照すると、ステップ４０２において、フローから受信されたデータの階層型スケジューリング方法が始まる。ステップ４０４において、パイプ・フローを識別するデータが受信される。例えば、スケジューラ論理３００のエンキュー・新規アタッチ論理３０２は、フローを識別するデータを受信することができる。データは、フローにおいて受信されるフレーム又はセルのサイズと、フローにおいて受信されるフレーム又はセルへのポインタとを含むことができる。
【００３７】
エンキュー・新規アタッチ論理３０２は、受信したデータによって識別されるフローに対応する、優先順位及び帯域幅情報のようなサービス品質（ＱｏＳ：Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）パラメータとして格納される情報を、メモリ３０４から取り出す。上述のように、本例において、受信したデータがパイプ・フローを識別すると仮定する。メモリ３０４は、ネットワーク・プロセッサ・システム（図示せず）によって受信することができる各々のフロー（例えば、自律型フロー及び／又はパイプ・フロー）についての制御構造（例えば、制御ブロック）を含むことができる。自律型フロー及び／又はパイプ・フローの各々についての制御ブロックは、１つ又はそれ以上の優先順位パラメータ及び１つ又はそれ以上の帯域幅パラメータについての値を含むことができる。優先順位パラメータは、パイプ・フローがサービスされる頻度を定義する。帯域幅パラメータは、パイプ・フローをサービスするように選択されたとき、該パイプ・フローが利用可能なシステム帯域幅の部分を定義する。
【００３８】
エンキュー・新規アタッチ論理３０２は、受信したデータによって識別されるパイプ・フローを含むパイプに対応する、優先順位及び帯域幅情報のようなクオリティ・オブ・サービス（ＱｏＳ）パラメータとして格納される情報を、メモリ３０４から取り出す。パイプの帯域幅及び優先順位パラメータを含む制御構造（例えば、制御ブロック）に加えて、メモリ３０４は、各々のパイプについて、優先順位及び帯域幅パラメータのようなサービス品質（ＱｏＳ）パラメータについての値を含む１つ又はそれ以上の制御構造を含むことができる。
【００３９】
エンキュー・新規アタッチ論理３０２は、受信したデータによって識別されるパイプ・フローに対応するパイプについて、一次（第１の）カレンダー３０８内にエントリが存在するかどうかを判断する。パイプについてのエントリが第１のカレンダー３０８内に存在する場合、該パイプは、サービスが既にスケジュールされており、エンキュー・新規アタッチ論理３０２は、該パイプに関するデータを第１のカレンダー３０８に書き込む必要がない。しかしながら、ステップ４０６において、パイプについてのエントリが存在しない場合、エンキュー・新規アタッチ論理３０２は、該パイプに関するデータを第１のカレンダー３０８に書き込む。
【００４０】
エンキュー・新規アタッチ論理３０２は、受信したデータによって識別されるパイプ・フローについて、二次（第２の）カレンダー３１０内にエントリが存在するかどうかを判断する。パイプ・フローについてのエントリが存在する場合、該パイプ・フローは、サービスが既にスケジュールされており、エンキュー・新規アタッチ論理３０２は、該パイプ・フローに関するデータを第２のカレンダー３１０に書き込む必要がない。しかしながら、ステップ４０８において、パイプ・フローについてのエントリが存在しない場合、エンキュー・新規アタッチ論理３０２は、該パイプ・フローに関するデータを第２のカレンダー３１０の適切なアドレス内に書き込む。このデータは、パイプ・フローを含むパイプに関する情報へのポインタを含む。例えば、パイプ・フローが高優先順位のものである場合、該パイプ・フローは、二次カレンダー３１０の高優先順位の部分内に配置される。さらに、パイプ・フローが、二次カレンダー３１０の高優先順位の部分に対して新しいエントリである場合、該パイプ・フローは、二次カレンダー３１０の高優先順位の部分において現在チェックされているメモリ・アドレスの近くに配置されるので、該パイプ・フローがより迅速にサービスされる。
【００４１】
ステップ４１０において、第１のカレンダー３０８が勝者パイプをチェックする。一次カレンダーは、ある時間期間（例えば、１又はそれ以上のクロック周期）中にサービスされることになる一次カレンダーの各優先順位部分からエントリを識別することができる。一次カレンダーは、時間単位中にサービスされるように識別されたエントリから、勝者（例えば、サービスされることになるエントリ）を選択する。本例においては、勝者であるエントリは、パイプに対応すると仮定される。一次カレンダー３０８は、例えばバスを介して、勝者パイプをデキュー・再アタッチ論理３１２に通知する。
【００４２】
ステップ４１２において、二次カレンダー３１０が、全ての勝者パイプ・フローを個別にチェックする。より具体的には、二次カレンダーは、時間単位中に各優先順位グループからサービスを必要とするエントリを識別することができる。二次カレンダーは、時間単位中にサービスされることになる識別されたエントリから勝者を選択する。一実施形態においては、ネットワーク・プロセッサ・システムによって受信されたパイプ及びフローをスケジュールするために、４つの優先順位タイプを用いることができ、したがって、二次カレンダー３１０を４つのグループに分けることができる。これらのグループ又は領域の各々が繰り返しチェックされる。他の数の優先順位タイプを用いることもできる。二次カレンダー３１０は、これらのグループ又は領域の各々からエントリを識別する（例えば、サービスされることになる高優先順位のパイプ・フロー、中優先順位のパイプ・フロー、及び低優先順位のパイプ・フローを識別する）ことができる。スケジューラ論理３００を含むネットワーク・プロセッサ（図示せず）の各クロック周期中に、二次カレンダーによって識別されるエントリの１つが、勝者であるエントリとして（例えば、サービスされることになるエントリとして）選択される。勝者であるエントリは、パイプ・フローに対応する。二次カレンダー３１０は、例えば、バスを介して、勝者パイプ・フローをパイプ・キュー・テーブル３１４に通知する。
【００４３】
ステップ４１４において、勝者パイプ・フローが、対応するパイプ・キューに書き込まれる。より具体的には、パイプ・キュー・テーブル３１４は、勝者パイプ・フロー及び該勝者パイプ・フローを含むパイプに関する情報を受信することができる。パイプ・キュー・テーブル３１４は、そのパイプ・フローに対応する優先順位及び帯域幅情報を、メモリ３０４から取り出すことができる。各キュー内のエントリを、優先順位順に配置することができる。２つ又はそれ以上のエントリが同じ優先順位を有する場合、各エントリがキューに格納されていた時間の長さによって、それらのエントリを配置することができる。二次カレンダー３１０から受信された情報、及びメモリ３０４から取り出された情報に基づいて、該二次カレンダー３１０からの勝者パイプ・フローは、パイプ・キュー・テーブル３１４に格納されたキューの１つの中に配置される。より具体的には、勝者パイプ・フローのエントリは、勝者パイプ・フローを含むパイプについてのキューの中に配置される。
【００４４】
パイプ・キューにおける勝者パイプ・フロー・エントリの配置は、メモリ３０４から取り出された情報によって決定することができる。例えば、パイプ・キューが、高優先順位のパイプ・フロー・エントリ、次に中優先順位のパイプ・フロー・エントリ、次に低優先順位のパイプ・フロー・エントリを既に含んでおり、勝者パイプ・フローが高優先順位のものである場合、該勝者パイプについてのエントリは、中優先順位のパイプ・フロー・エントリの前で、既に存在していた高優先順位のパイプ・フロー・エントリの後に、パイプ・キューに挿入される。
【００４５】
ステップ４１６において、対応するパイプ・キューからパイプ・フローを選択するために、第１のカレンダー３０８からの勝者パイプが用いられる。上述のように、一次カレンダー３０８は、勝者パイプをデキュー・再アタッチ論理３１２に通知する。デキュー・再アタッチ論理３１２は、勝者パイプに対応するパイプ・キュー（パイプ・キュー・テーブル３１４に格納された）が空である（すなわち、パイプ・キューが、時間単位中にサービスを必要とするいずれのパイプ・フローも含んでいない）かどうかを判断することができる。勝者パイプに対応するパイプ・キューが空であるときに実行されるステップは、本発明の新規な態様を含み、後に説明される。
【００４６】
本例においては、勝者パイプに対応するパイプ・キューは空でないと仮定する。デキュー・再アタッチ論理３１２は、勝者パイプに対応するパイプ・キュー（パイプ・キュー・テーブル３１４に格納された）から、パイプ・フロー・エントリを選択する。より具体的には、デキュー・再アタッチ論理３１２は、サービスされることになるパイプ・フロー・エントリのような、最も長い時間キュー内に存在した最も高い優先順位のパイプ・フロー・エントリをパイプ・キューから選択する。
【００４７】
ステップ４１８において、選択されたパイプ・フローからのデータが伝送される。選択されたパイプ・フローからネットワーク・プロセッサ・システム（図示せず）によって受信されたフレーム又はセルが、該ネットワーク・プロセッサ・システムの出力ポートを介して伝送される。ネットワーク・プロセッサ・システムの出力ポートを通して、他の数のフレーム又はセルを伝送することもできる。ステップ４２０において、選択されたパイプ・フローについて付加的なデータがないと仮定されると、図４の方法が終了する。他の場合には、以下に説明されるようなプロセスが続行する。
【００４８】
選択されたパイプ・フローについての付加的なデータがある場合、デキュー・再アタッチ論理３１２は、選択されたパイプ・フローを識別する付加的なデータ（例えば、フレーム又はセル）をサービスを必要とすると判断する。この判断を行うために、デキュー・再アタッチ論理３１２は、キューの構造を説明する、メモリに格納された情報にアクセスする。選択されたフローを識別する付加的なデータをサービスする必要がある場合、デキュー・再アタッチ論理３１２は、そのパイプ・フローに対応する優先順位及び帯域幅情報をメモリ３０４から取り出す。この情報に基づいて、デキュー・再アタッチ論理３１２は、選択されたパイプ・フロー・エントリが再アタッチされる（すなわち、再書き込みされる）ことになる二次カレンダー３１０における適切なメモリ・アドレスを判断して、選択されたパイプ・フローの再サービスをスケジュールすることができる。
【００４９】
例えば、選択されたパイプ・フローが高優先順位のものであると仮定すると、パイプ・フローが、二次カレンダー３１０の高優先順位の部分に書き込まれる。パイプ・フローはサービスされたばかりなので、二次カレンダーの高優先順位の部分において選択されたメモリ・アドレスは、パイプ・フローが二次カレンダー３１０に最初にアタッチされた（例えば、書き込まれた）ときより、高優先順位グループにおいて現在チェックされているメモリ・アドレスからの距離が大きい可能性がある。したがって、パイプ・フローは、該パイプ・フローが最初に二次カレンダー３１０にアタッチされたときより、該二次カレンダー３１０に再アタッチされた後に、より長い時間サービスされるのを待たなければならないことがある。
【００５０】
代替的に、全てのデータが伝送され、フローが空であるとデキュー・再アタッチ論理３１２が判断した場合、選択されたパイプ・フローは、二次カレンダー３１０に再アタッチされない。
【００５１】
デキュー・再アタッチ論理３１２は、メモリ３０４に格納された、選択されたパイプ内に含まれる各パイプ・フローについてのキュー構造を説明する情報にアクセスすることによって、該選択されたパイプが空であるかどうか（すなわち、選択されたパイプ内に含まれるパイプ・フローを識別する、この時間単位中にサービスを必要とする受信データがないこと）を判断することができる。選択されたパイプ内に含まれるフローを識別する付加的なデータをサービスする必要がある場合、デキュー・再アタッチ論理３１２は、選択されたパイプに対応する優先順位及び帯域幅情報をメモリ３０４から取り出す。この情報に基づいて、デキュー・再アタッチ論理３１２は、選択されたパイプ・エントリが再アタッチされる（すなわち、再書き込みされる）ことになる一次カレンダー３０８における適切なメモリ・アドレスを判断することができる。
【００５２】
例えば、二次カレンダー３１０へのパイプ・フロー・エントリの再アタッチと同様に、選択されたパイプが高優先順位のものである場合、そのパイプは、一次カレンダー３０８の高優先順位部分のメモリ・アドレスに書き込まれる。パイプはサービスされたばかりなので、一次カレンダー３０８の高優先順位部分において選択されたメモリ・アドレスは、パイプが最初にアタッチされた（例えば、一次カレンダー３０８に書き込まれた）ときより、カレンダーのその部分において現在チェックされているメモリ・アドレスからの距離が大きい可能性がある。したがって、パイプは、該パイプが最初に一次カレンダー３０８にアタッチされたときより、該一次カレンダー３０８に再アタッチされた後に、より長い時間サービスされるのを待たなければならないことがある。
【００５３】
代替的に、このパイプに関連した全てのパイプ・フローが空であるとデキュー・再アタッチ論理３１２が判断した場合、選択されたパイプは、一次カレンダー３０８に再アタッチされない。
【００５４】
ステップ４１６の説明の際に上述したように、勝者パイプの通知を受信したとき、デキュー・再アタッチ論理３１２は、勝者パイプに対応するパイプ・キューが空であるかどうかを判断する。勝者パイプに対応するパイプ・キューが空である（すなわち、パイプ・キューが、時間単位中にサービスを必要とするパイプ・フロー・エントリを有していない）場合、デキュー・再アタッチ論理３１２は、時間単位中に、クレジットを選択されたパイプに対応するパイプ・キューに与えることができる（例えば、パイプ・キュー・テーブル３１４内のそのパイプ・キューについてのパイプ・クレジット・ビットを設定することによって）。しかしながら、時間単位中にパイプ又はフローをサービスすることができない。その後、ステップ４１０を実行することができる。
【００５５】
ステップ４１４の際に、勝者パイプ・フローが書き込まれたパイプ・キューがクレジットを有しているかどうかの判断を行うことができる。勝者パイプ・フローが書き込まれたパイプ・キューが勝利クレジットを有していないと判断された場合、二次カレンダー３１０が別の勝者パイプ・フローをチェックするステップ４１２を実行することができる。代替的に、パイプ・キューがクレジットを有していると判断された場合、例えば、次の時間単位において勝者となるパイプ・フロー・エントリがパイプ・キュー上に配置されたとき、パイプ・キュー・テーブル３１４が、このエントリをデキュー・再アタッチ論理３１２に通知する。デキュー・再アタッチ論理３１２は、パイプ・キューからパイプ・フロー・エントリを選択し、該パイプ・キューの勝利クレジットを消去する。
デキュー・再アタッチ論理３１２がパイプ・キューからパイプ・フロー・エントリを選択すると、ステップ４１８が実行される。上述のように、選択されたパイプ・フローについての付加的なデータがある場合、デキュー・再アタッチ論理３１２は、選択されたパイプ・フローを識別する付加的なデータ（例えば、フレーム又はセル）をサービスする必要があるかどうかを判断する。この判断を行うために、デキュー・再アタッチ論理３１２は、キューの構造を説明する、メモリに格納された情報にアクセスする。選択されたフローを識別する付加的なデータをサービスする必要がある場合、デキュー・再アタッチ論理３１２は、そのパイプ・フローに対応する優先順位及び帯域幅情報をメモリ３０４から取り出す。この情報に基づいて、デキュー・再アタッチ論理３１２は、選択されたパイプ・フロー・エントリが再アタッチされる（すなわち、再書き込みされる）ことになる二次カレンダー３１０における適切なメモリ・アドレスを判断することができ、選択されたパイプ・フローの再サービスをスケジュールすることができる。代替的に、全てのデータが伝送され、フローが空であるとデキュー・再アタッチ論理３１２が判断した場合、選択されたパイプ・フローは、二次カレンダー３１０に再アタッチされない。
【００５６】
上述のように、デキュー・再アタッチ論理３１２は、メモリ３０４に格納された選択されたパイプ内に含まれる各パイプ・フローについてのキューの構造を説明する情報にアクセスすることによって、選択されたパイプが空であるかどうか（すなわち、選択されたパイプに含まれるパイプ・フローを識別する、この時間単位中にサービスを必要とする受信データがないかどうか）を判断することができる。選択されたパイプ内に含まれるフローを識別する付加的なデータをサービスする必要がある場合、デキュー・再アタッチ論理３１２は、選択されたパイプに対応する優先順位及び帯域幅情報をメモリ３０４から取り出す。この情報に基づいて、デキュー・再アタッチ論理３１２は、選択されたパイプ・エントリが再アタッチされる（すなわち、再書き込みされる）ことになる一次カレンダー３０８における適切なメモリ・アドレスを判断することができる。代替的に、このパイプに関連したすべてのパイプ・フローが空であるとデキュー・再アタッチ論理３１２が判断した場合、選択されたパイプは、一次カレンダー３０８に再アタッチされない。デキュー・再アタッチ論理３１２がパイプ・キューの勝利クレジットを消去すると、二次カレンダー３１０が勝者パイプ・フローをチェックするステップ４１２を実行することができる。
【００５７】
上の説明は、本発明の例示的な実施形態だけを開示するものである。本発明の範囲内に含まれる上に開示された装置及び方法の修正が、当業者には容易に明らかであろう。上の実施形態において、各々のパイプは、複数のパイプ・フロー内に含まれるが、他の実施形態においては、これらのパイプの１つ又はそれ以上が、複数のパイプ・フローを含む。上の実施形態において、自律型フロー、パイプ、及び／又はパイプ・フローは、帯域幅又優先順位のようなＱｏＳパラメータに基づいてサービスされるように選択されたが、他の実施においては、別のＱｏＳパラメータを用いて、サービスのために自律型フロー、パイプ、又はパイプ・フローを選択することもできる。さらに、１つ又はそれ以上の実施形態においては、ステップ４１０及びステップ４１２を同時に実行することができる。
【００５８】
したがって、本発明は例示的な実施形態と共に開示されたが、上記の特許請求の範囲によって定められるように、他の実施形態も本発明の精神と範囲内に含まれ得ることを理解すべきである。
【図面の簡単な説明】
【００５９】
【図１】従来のネットワーク・プロセッサ・システムの例示的な概略図である。
【図２】図１の従来のネットワーク・プロセッサ・システム内に含まれるスケジューラ論理のブロック図である。
【図３】階層型スケジューリングについての本発明を実装することができる例示的なスケジューラ論理のブロック図である。
【図４】フローから受信されたデータの階層型スケジューリング方法のための例示的な方法を示す。
【図１】
2007507938.tif 000003
【図２】
2007507938.tif 000004
【図３】
2007507938.tif 000005
【図４】
2007507938.tif 000006
【手続補正書】
【提出日】平成17年7月28日(2005.7.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
階層型スケジューリング方法であって、
各々が複数のパイプ・フローを含む１つ又は複数のパイプ及び１つ又は複数の自律型フローからデータを受信するステップと、
データが伝送されることになる勝者を、前記勝者に対応する１つ又は複数のサービス品質パラメータに基づいて、前記１つ又は複数のパイプ及び１つ又は複数の自律型フローから選択するステップと、
前記勝者がパイプである場合には、前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、前記勝者パイプ内に含まれる前記複数のパイプ・フローからパイプ・フローを選択するステップと、
前記選択されたパイプ・フローからデータを伝送するステップと
を含む方法。
【請求項２】
前記選択されたパイプ・フローからデータを伝送する前記ステップは、勝者パイプ・フローに対応する帯域幅を用いて、前記選択されたパイプ・フローからデータを伝送するステップを含む、請求項１に記載の方法。
【請求項３】
データが伝送されることになる勝者パイプを、前記勝者パイプに対応する１つ又は複数のサービス品質パラメータに基づいて、前記１つ又は複数のパイプから選択する前記ステップは、
パイプを識別するデータを、前記パイプに対応する１つ又は複数のサービス品質パラメータに基づいて、メモリ・アドレスのグループ内のメモリ・アドレスに書き込むステップと、
前記メモリ・アドレスのグループを走査してパイプを識別するデータを見つけ出すステップと
を含む、請求項１又は請求項２に記載の方法。
【請求項４】
前記勝者パイプを識別するデータを、前記勝者パイプに対応する１つ又は複数のサービス品質パラメータに基づいて、メモリ・アドレスのグループ内のメモリ・アドレスに再書き込みするステップをさらに含む、請求項３に記載の方法。
【請求項５】
前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、前記勝者パイプ内に含まれる前記複数のパイプ・フローからパイプ・フローを選択する前記ステップは、
パイプ・フローを識別するデータを、前記パイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、メモリ・アドレスのグループ内のメモリ・アドレスに書き込むステップと、
前記メモリ・アドレスのグループを走査してパイプ・フローを識別するデータを見つけ出すステップと、
前記識別されたパイプ・フローを、前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、前記勝者パイプに対応するキューに書き込むステップと、
前記識別されたパイプ・フローを、前記勝者パイプに対応する前記キューから選択するステップと
を含む、請求項１、請求項２、又は請求項３に記載の方法。
【請求項６】
前記選択されたパイプ・フローを識別するデータを、前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、メモリ・アドレスのグループ内のメモリ・アドレスに書き込むステップをさらに含む、請求項５に記載の方法。
【請求項７】
階層型スケジューリング方法であって、
パイプ・フロー及び自律型フローを識別するデータであって、前記パイプ・フローがパイプ内に含まれる、データを受信するステップと、
前記パイプ及び前記自律型フローに関するデータを第１のカレンダーに書き込むステップと、
前記パイプ・フローに関するデータを第２のカレンダーに書き込むステップと、
勝者を定めるために前記第１のカレンダーを走査するステップと、
前記勝者がパイプである場合には、勝者パイプ・フローを定めるために前記パイプ及び前記自律型フローから前記第２のカレンダーを走査するステップと、
前記勝者パイプ・フローを対応するパイプ・キューに書き込むステップと、
前記選択されたパイプ・フローからデータを伝送するステップと
を含む方法。
【請求項８】
前記勝者パイプ・フローに関するデータを前記第２のカレンダーに再書き込みするステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記勝者パイプに関するデータを前記第１のカレンダーに再書き込みするステップをさらに含む、請求項７又は請求項８に記載の方法。
【請求項１０】
１つ又は複数のパイプ及びパイプ・フロー、並びに１つ又は複数の自律型フローに対応する１つ又は複数のサービス品質パラメータを格納するように適合された少なくとも１つのメモリと、
前記少なくとも１つのメモリに接続され、かつ、
各々が複数のパイプ・フローを含む１つ又は複数のパイプ及び１つ又は複数の自律型フローからデータを受信し、
前記１つ又は複数のパイプ及び前記１つ又は複数の自律型フローから勝者を選択し、前記勝者からは、前記勝者に対応する１つ又は複数のサービス品質パラメータに基づいて、データが伝送されることになり、
前記勝者がパイプである場合には、前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、前記勝者パイプ内に含まれる前記複数のパイプ・フローからパイプ・フローを選択し、
前記選択されたフローからデータを伝送する
ように適合された
スケジューラ論理と
を備えるネットワーク・プロセッサ。
【請求項１１】
前記スケジューラ論理は、
サービスされることがスケジュールされた自律型フローとパイプとのうちの少なくとも１つを格納するための一次カレンダーと、
サービスされることがスケジュールされたパイプ・フローを格納するための二次カレンダーと、
勝者パイプ・フローを前記パイプ・フローが対応するパイプのためのキューに格納するためのパイプ・キュー・テーブルと
を備える、請求項１０に記載のネットワーク・プロセッサ。
【請求項１２】
前記スケジューラ論理は、
サービスされることになる自律型フローとパイプ・フローとのうちの少なくとも１つをスケジュールするためのエンキュー・新規アタッチ論理と、
サービスされることになる自律型フローとパイプ・フローとのうちの少なくとも１つを選択するためのデキュー・再アタッチ論理と
をさらに備える、請求項１１に記載のネットワーク・プロセッサ。
【請求項１３】
前記スケジューラ論理は、前記勝者パイプ・フローに対応する帯域幅を用いて、前記選択されたパイプ・フローからデータを伝送するようにさらに適合される、請求項１０、請求項１１、又は請求項１２に記載のネットワーク・プロセッサ。
【請求項１４】
前記スケジューラ論理は、パイプに対応する１つ又は複数のサービス品質パラメータに基づいて、パイプを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込み、前記メモリ・アドレスのグループを走査してパイプを識別するデータを見つけ出すようにさらに適合される、請求項１０から請求項１３までのいずれか１項に記載のネットワーク・プロセッサ。
【請求項１５】
前記スケジューラ論理は、前記勝者パイプに対応する１つ又は複数のサービス品質パラメータに基づいて、前記勝者パイプを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに再書き込みするようにさらに適合される、請求項１４に記載のネットワーク・プロセッサ。
【請求項１６】
前記スケジューラ論理は、
パイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、パイプ・フローを識別するデータをメモリ・アドレス・グループ内のメモリ・アドレスに書き込み、
前記メモリ・アドレスのグループを走査してパイプ・フローを識別するデータを見つけ出し、
前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、前記識別されたパイプ・フローを前記勝者パイプに対応するキューに書き込み、
前記勝者パイプに対応する前記キューから前記識別されたパイプ・フローを選択する
ようにさらに適合される、請求項１０から請求項１５までのいずれか１項に記載のネットワーク・プロセッサ。
【請求項１７】
前記スケジューラ論理は、前記選択されたパイプ・フローに対応する１つ又は複数のサービス品質パラメータに基づいて、該選択されたパイプ・フローを識別するデータをメモリ・アドレスのグループ内のメモリ・アドレスに書き込むようにさらに適合される、請求項１６に記載のネットワーク・プロセッサ。
【請求項１８】
１つ又は複数のパイプ及びパイプ・フローと１つ又は複数の自律型フローとに対応する１つ又は複数のサービス品質パラメータを格納するように適合された少なくとも１つのメモリと、
第１のカレンダー及び第２のカレンダーを含むスケジューラ論理であって、
前記少なくとも１つのメモリに接続され、かつ、
パイプ内に含まれるパイプ・フロー又は自律型フローを識別するデータを受信し、      前記パイプ又は前記自律型フローに関するデータを前記第１のカレンダーに書き込み、
前記パイプ・フローに関するデータを前記第２のカレンダーに書き込み、
勝者を定めるために前記第１のカレンダーを走査し、
前記勝者がパイプである場合には、勝者パイプ・フローを定めるために前記第２のカレンダーを走査し、
前記勝者パイプ・フロー又は前記自律型フローを対応するパイプ・キューに書き込み、
前記勝者パイプ・フロー又は前記自律型パイプ・フローによって決定されるようにデータを伝送する
ように適合された
スケジューラ論理と
を備えるネットワーク・プロセッサ。
【請求項１９】
前記スケジューラ論理は、
勝者パイプ・フローを前記パイプ・フローが対応するパイプのためのキューに格納するためのパイプ・キュー・テーブルと、
サービスされることになる自律型フローとパイプ・フローとのうちの少なくとも１つをスケジュールするためのエンキュー・新規アタッチ論理と、
サービスされることになる自律型フローとパイプ・フローとのうちの少なくとも１つを選択するためのデキュー・再アタッチ論理と
をさらに含む、請求項１８に記載のネットワーク・プロセッサ。
【請求項２０】
前記スケジューラ論理は、前記勝者パイプ・フローに関するデータを前記第２のカレンダーに再書き込みするようにさらに適合される、請求項１８又は請求項１９に記載のネットワーク・プロセッサ。
【請求項２１】
前記スケジューラ論理は、前記勝者パイプに関するデータを前記第１のカレンダーに再書き込みするようにさらに適合される、請求項１８、請求項１９、又は請求項２０に記載のネットワーク・プロセッサ。
【国際調査報告】
2007507938.tif 000007
2007507938.tif 000008
2007507938.tif 000009