(57)【特許請求の範囲】
【請求項１】
入力ポートを介して第1のデータ・ネットワークから着信したデータ・フレームを、出力ポートを介して第２のデータ・ネットワークへ送信するネットワーク・プロセッサにおいて、前記出力ポートを介して送信すべきデータ・フレームのフロー（データ・フロー）を制御する方法であって、
前記ネットワーク・プロセッサ内に設けられ、その各々が複数のキュー・スロットを有し、当該複数のキュー・スロットのいずれかに、データ・フレームに関連付けられたフロー情報が付加される、１つまたは複数のスケジューリング・キューのうち、各々のスケジューリング・キューについて、当該スケジューリング・キューに付加されたフロー情報が関連付けられたデータ・フレームを前記第２のデータ・ネットワークへ送信するために介すべき１つまたは複数の出力ポートを割り当てるステップと、
前記割り当てるステップにおいて、複数の出力ポートが割り当てられた場合に、当該複数の出力ポートの各々について帯域幅を読み取り、それらのうちの最大の帯域幅を判定し、当該各帯域幅と当該最大の帯域幅とから当該複数の出力ポートの各々についての重みスケーラ（ＷＳ）を算出するステップと、
前記算出するステップの後、前記複数の出力ポートのうちのいずれか１つの出力ポートを介して送信すべきデータ・フレームが着信され、前記ネットワーク・プロセッサ内に設けられたデータ・フレーム用のデータ・バッファに蓄積されたことに応答して、当該データ・フレームに関連付けられたフロー情報が前記スケジューリング・キューに既に付加（エンキュー）されているかどうかを判断するステップと、
前記判断するステップにおいて、未だ付加されていないと判断した場合には、前記スケジューリング・キューに前記フロー情報を付加する位置となるキュー・スロットを、前記１つの出力ポートについて算出された前記重みスケーラに基づいて特定し、当該キュー・スロットに前記フロー情報を付加するステップと、
前記フロー情報を付加する前記ステップの後、前記フロー情報が付加された前記キュー・スロットが前記スケジューリング・キュー内の、非空で現在ポインタにもっとも近いキュー・スロットである場合に、前記キュー・スロットに付加された前記フロー情報を前記キュー・スロットから取り出す（デキューする）ステップと、
前記取り出すステップの後、前記１つの出力ポートに対応する出力データ・フロー・キューが、これ以上更なるデータ・フレームを受け付けることができないバック・プレッシャ状態ではない場合に、前記フロー情報が関連付けられた前記データ・フレームを前記データ・バッファから取り出して当該出力データ・フロー・キューに移動することで前記１つの出力ポートを介して前記データ・フレームが送信されるようにするステップと、  前記取り出すステップの後、前記１つの出力ポートに対応する出力データ・フロー・キューが、バック・プレッシャ状態である場合には、前記スケジューリング・キューに前記フロー情報を再度付加するためのキュー・スロットを、前記１つの出力ポートについて算出された前記重みスケーラに基づいて特定し、前記キュー・スロットに前記フロー情報を再度付加するステップと
を有する方法。
【請求項２】
前記出力ポートを割り当てるステップは、前記１つまたは複数の出力ポートの各々を識別する識別番号を表すビット列のうち最下位ビットから所定のビット数分の部分ビット列の値が同一であるすべての出力ポートを、同一のスケジューリング・キューに割り当てるステップを含む、請求項１に記載の方法。
【請求項３】
複数の出力ポートの各々についての重みスケーラ（ＷＳ）を算出する前記ステップは、前記最大の帯域幅の値を、前記複数の出力ポートの各々の出力ポートの帯域幅の値で除した値を各々の重みスケーラ（ＷＳ）値とするステップを含む、請求項１に記載の方法。
【請求項４】
前記キュー・スロットを特定し前記フロー情報を付加する前記ステップは、
前記データ・フレームに係るフローに対するサービス品質（ＱＯＳ）に従って当該フローに割り当てられた重み値と、前記１つの出力ポートについて算出された前記重みスケーラとの積として、前記フローに対する重み付け係数（ＷＦ）算出するステップと、
公式
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ
（ここで、ＣＰは前記スケジューリング・キューの現在ポインタ（カレント・ポインタ）値であり、ＷＦは前記重み付け係数であり、ＦＳは前記フローに関連したフレーム・サイズであり、ＳＦはスケーリング係数である）に従って前記フロー情報を付加すべき前記キュー・スロットを特定するステップと
を含む、請求項３に記載の方法。
【請求項５】
入力ポートを介して第1のデータ・ネットワークから着信したデータ・フレームのフローを制御して、出力ポートを介して第２のデータ・ネットワークへ送信するネットワーク・プロセッサにおけるデータ通信装置であって、
１つまたは複数の出力ポートの各々に対応した出力データ・フロー・キューを有するデータ・フロー制御部と、
前記データ・フロー制御部とデータ・フレームを相互にやり取り可能に接続され、着信したデータ・フレームを蓄積するデータ・バッファ部と、
前記データ・フロー制御部と相互に情報伝達可能に接続されたフロー・スケジューラ部であって、
各々が複数のキュー・スロットを有し、当該複数のキュー・スロットのいずれかに、データ・フレームに関連付けられたフロー情報が付加される、１つまたは複数のスケジューリング・キューであって、付加されたフロー情報が関連付けられたデータ・フレームを前記第２のデータ・ネットワークへ送信するために介すべき１つまたは複数の出力ポートをその各々に割り当る、１つまたは複数のスケジューリング・キューと、
前記１つまたは複数のスケジューリング・キューのいずれかに複数の出力ポートが割り当てられた場合に、当該複数の出力ポートの各々について帯域幅を読み取り、それらのうちの最大の帯域幅を判定し、当該各帯域幅と当該最大の帯域幅とから当該複数の出力ポートの各々についての重みスケーラ（ＷＳ）を算出する、重みスケーラ算出部と、
前記複数の出力ポートのうちのいずれか１つの出力ポートを介して送信すべきデータ・フレームが着信され、前記データ・バッファに蓄積されたことに応答して、当該データ・フレームに関連付けられたフロー情報が前記スケジューリング・キューに既に付加（エンキュー）されているかどうかを判断する、付加判断部と、
前記付加判断部において、未だ付加されていないと判断した場合に、前記スケジューリング・キューに前記フロー情報を付加する位置となるキュー・スロットを、前記１つの出力ポートについて算出された前記重みスケーラに基づいて特定し、当該キュー・スロットに前記フロー情報を付加する、付加制御部と、
前記付加制御部によって前記フロー情報が付加された前記キュー・スロットが前記スケジューリング・キュー内の、非空で現在ポインタにもっとも近いキュー・スロットである場合に、前記キュー・スロットに付加された前記フロー情報を前記キュー・スロットから取り出す（デキューする）、取り出し制御部と、
前記取り出し制御部によって取り出された前記フロー情報に係る前記１つの出力ポートに対応する出力データ・フロー・キューが、これ以上更なるデータ・フレームを受け付けることができないバック・プレッシャ状態であるかどうかを判断する、バック・プレッシャ判断部と、
前記バック・プレッシャ判断部が、前記１つの出力ポートに対応する前記出力データ・フロー・キューがバック・プレッシャ状態であると判断した場合に、前記スケジューリング・キューに前記フロー情報を再度付加するためのキュー・スロットを、前記１つの出力ポートについて算出された前記重みスケーラに基づいて特定し、前記キュー・スロットに前記フロー情報を再度付加する、再付加制御部と
を有するフロー・スケジューラ部と
を有するデータ通信装置。
【請求項６】
前記１つまたは複数のスケジューリング・キューの各々は、前記１つまたは複数の出力ポートの各々を識別する識別番号を表すビット列のうち最下位ビットから所定のビット数分の部分ビット列の値が同一であるすべての出力ポートを、当該スケジューリング・キューに割り当てる、請求項５に記載のデータ通信装置。
【請求項７】
前記重みスケーラ算出部は、前記最大の帯域幅の値を、前記複数の出力ポートの各々の出力ポートの帯域幅の値で除した値を各々の重みスケーラ（ＷＳ）値として算出する、請求項５に記載のデータ通信装置。
【請求項８】
前記付加制御部は、
前記データ・フレームに係るフローに対するサービス品質（ＱＯＳ）に従って当該フローに割り当てられた重み値と、前記１つの出力ポートについて算出された前記重みスケーラとの積として、前記フローに対する重み付け係数（ＷＦ）算出する、算出部と、
公式
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ
（ここで、ＣＰは前記スケジューリング・キューの現在ポインタ（カレント・ポインタ）値であり、ＷＦは前記重み付け係数であり、ＦＳは前記フローに関連したフレーム・サイズであり、ＳＦはスケーリング係数である）に従って前記フロー情報を付加すべき前記キュー・スロットを特定する、特定部と
を有する、請求項７に記載のデータ通信装置。
【請求項９】
入力ポートを介して第1のデータ・ネットワークから着信したデータ・フレームを、出力ポートを介して第２のデータ・ネットワークへ送信するネットワーク・プロセッサにおいて、前記出力ポートを介して送信すべきデータ・フレームのフロー（データ・フロー）を制御するためのコンピュータ・プログラムであって、
前記ネットワーク・プロセッサ内に設けられ、その各々が複数のキュー・スロットを有し、当該複数のキュー・スロットのいずれかに、データ・フレームに関連付けられたフロー情報が付加される、１つまたは複数のスケジューリング・キューのうち、各々のスケジューリング・キューについて、当該スケジューリング・キューに付加されたフロー情報が関連付けられたデータ・フレームを前記第２のデータ・ネットワークへ送信するために介すべき１つまたは複数の出力ポートを割り当てるステップと、
前記割り当てるステップにおいて、複数の出力ポートが割り当てられた場合に、当該複数の出力ポートの各々について帯域幅を読み取り、それらのうちの最大の帯域幅を判定し、当該各帯域幅と当該最大の帯域幅とから当該複数の出力ポートの各々についての重みスケーラ（ＷＳ）を算出するステップと、
前記算出するステップの後、前記複数の出力ポートのうちのいずれか１つの出力ポートを介して送信すべきデータ・フレームが着信され、前記ネットワーク・プロセッサ内に設けられたデータ・フレーム用のデータ・バッファに蓄積されたことに応答して、当該データ・フレームに関連付けられたフロー情報が前記スケジューリング・キューに既に付加（エンキュー）されているかどうかを判断するステップと、
前記判断するステップにおいて、未だ付加されていないと判断した場合には、前記スケジューリング・キューに前記フロー情報を付加する位置となるキュー・スロットを、前記１つの出力ポートについて算出された前記重みスケーラに基づいて特定し、当該キュー・スロットに前記フロー情報を付加するステップと、
前記フロー情報を付加する前記ステップの後、前記フロー情報が付加された前記キュー・スロットが前記スケジューリング・キュー内の、非空で現在ポインタにもっとも近いキュー・スロットである場合に、前記キュー・スロットに付加された前記フロー情報を前記キュー・スロットから取り出す（デキューする）ステップと、
前記取り出すステップの後、前記１つの出力ポートに対応する出力データ・フロー・キューが、これ以上更なるデータ・フレームを受け付けることができないバック・プレッシャ状態ではない場合に、前記フロー情報が関連付けられた前記データ・フレームを前記データ・バッファから取り出して当該出力データ・フロー・キューに移動することで前記１つの出力ポートを介して前記データ・フレームが送信されるようにするステップと、
前記取り出すステップの後、前記１つの出力ポートに対応する出力データ・フロー・キューが、バック・プレッシャ状態である場合には、前記スケジューリング・キューに前記フロー情報を再度付加するためのキュー・スロットを、前記１つの出力ポートについて算出された前記重みスケーラに基づいて特定し、前記キュー・スロットに前記フロー情報を再度付加するステップと
を前記ネットワーク・プロセッサに実行させる為のコンピュータ・プログラム。
【請求項１０】
前記出力ポートを割り当てるステップは、前記１つまたは複数の出力ポートの各々を識別する識別番号を表すビット列のうち最下位ビットから所定のビット数分の部分ビット列の値が同一であるすべての出力ポートを、同一のスケジューリング・キューに割り当てるステップを含む、請求項９に記載のコンピュータ・プログラム。
【請求項１１】
複数の出力ポートの各々についての重みスケーラ（ＷＳ）を算出する前記ステップは、前記最大の帯域幅の値を、前記複数の出力ポートの各々の出力ポートの帯域幅の値で除した値を各々の重みスケーラ（ＷＳ）値とするステップを含む、請求項９に記載のコンピュータ・プログラム。
【請求項１２】
前記キュー・スロットを特定し前記フロー情報を付加する前記ステップは、
前記データ・フレームに係るフローに対するサービス品質（ＱＯＳ）に従って当該フローに割り当てられた重み値と、前記１つの出力ポートについて算出された前記重みスケーラとの積として、前記フローに対する重み付け係数（ＷＦ）算出するステップと、
公式
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ
（ここで、ＣＰは前記スケジューリング・キューの現在ポインタ（カレント・ポインタ）値であり、ＷＦは前記重み付け係数であり、ＦＳは前記フローに関連したフレーム・サイズであり、ＳＦはスケーリング係数である）に従って前記フロー情報を付加すべき前記キュー・スロットを特定するステップと
を含む、請求項１１に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ及びストレージ通信システムに関し、特に、ネットワーク・プロセッサのスケジューラ・コンポーネントに関する。
【０００２】
【従来の技術】
データ及びストレージ通信ネットワークは広範囲に使用されている。多くのデータ及びストレージ通信ネットワークでは、送信元と宛先との間の２地点間でデータ・パケット又はフレームを経路指定するためにデータ・パケット交換が使用され、データ・スイッチへの及びデータ・スイッチからのデータの伝送を処理するために、ネットワーク・プロセッサが使用される。
【０００３】
図１は、本発明を適用し得る一般的なネットワーク・プロセッサのブロック図である。参照番号１０によって全体的に表されたネットワーク・プロセッサは、カード又は「ブレード（blade）」上に装着された数多くのコンポーネントによって構成され得る。データ通信ネットワークでは、データ・スイッチとデータ・ネットワークの間に、ネットワーク・プロセッサを含むかなりの数のブレードが配置され得る。
【０００４】
ネットワーク・プロセッサ１０は、データ・フロー・チップ１２及び１４を含む。第１のデータ・フロー・チップ１２が、第１のスイッチ・ポート１６を介してデータ・スイッチ１５（破線で示される）に接続され、第１のネットワーク・ポート１８を介してデータ・ネットワーク１７（破線で示される）に接続される。第１のデータ・フロー・チップ１２は、スイッチ１５の入力側に位置付けられ、スイッチ１５に入って来るデータ・フレームを処理する。
【０００５】
第２のデータ・フローチップ１４は、第２のスイッチ・ポート２０を介してデータ・スイッチ１５に接続され、第２のネットワーク・ポート２２を介してデータ・ネットワーク１７に接続される。第２のデータ・フロー・チップ１４は、スイッチ１５の出口側に位置付けられ、スイッチ１５から出て行くデータ・フレームを処理する。
【０００６】
図１に示されるように、第１のデータ・バッファ２４が第１のデータ・フロー・チップ１２に結合される。第１のデータ・バッファ２４は、インバウンド・データ・フレームをスイッチ１５に伝送するまで、そのインバウンド・データ・フレームを記憶する。第２のデータ・バッファ２６が第２のデータ・フロー・チップ１４に結合され、アウトバウンド・データ・フレームをデータ・ネットワーク１７に伝送するまで、そのアウトバウンド・データ・フレームを記憶する。
【０００７】
ネットワーク・プロセッサ１０は、更に、第１のデータ・フロー・チップ１２に結合された第１のプロセッサ・チップ２８を含む。第１のプロセッサ・チップ２８は、第１のデータ・フロー・チップ１２のオペレーションを監視し、しかも複数のプロセッサを含み得る。第２のプロセッサ・チップ３０が第２のデータ・フロー・チップ１４に結合され、第２のデータ・フロー・チップ１４のオペレーションを監視し、しかも複数のプロセッサを含み得る。
【０００８】
制御信号パス３２が、第２のデータ・フロー・チップ１４の出力端子を第１のデータ・フロー・チップ１２の入力端子に結合する（例えば、それらの間におけるデータ・フレームの伝送を可能にするために）。
【０００９】
ネットワーク・プロセッサ１０は、更に、第１のデータ・フロー・チップ１２に結合された第１のスケジューラ・チップ３４を含む。第１のスケジューラ・チップ３４は、インバウンド・データ・フレームが第１のスイッチ・ポート１６を介してスイッチ１５に伝送されるシーケンスを管理する。高速ＳＲＡＭのような第１のメモリ３６が（例えば、後述のように、データ・フレーム・ポインタ及びフロー制御情報を記憶するために）第１のスケジューラ・チップ３４に結合される。第１のメモリ３６は、例えば、ＱＤＲ（４倍データ転送速度）ＳＲＡＭであってもよい。
【００１０】
第２のスケジューラ・チップ３８が第２のデータ・フロー・チップ１４に結合される。第２のスケジューラ・チップ３８は、データ・フレームが第２のデータ・フロー・チップ１４の第２のネットワーク・ポート２２から出力されるシーケンスを管理する。第２のスケジューラ・チップ３８には、データ・フレーム・ポインタ及びフロー制御情報を記憶するために少なくとも１つの、或いは、２つのメモリ（例えば、高速ＳＲＡＭ４０）が結合される。メモリ４０は、第１のメモリ３６のように、ＱＤＲであってもよい。第２のネットワーク・ポート２２を介したフロー出力の数が第１のスイッチ・ポート１６を介したフロー出力よりも多いので、ネットワーク・プロセッサ１０の出口側においてその付加的メモリ４０が必要とされ得る。
【００１１】
図２は、図１のネットワーク・プロセッサ１０においてデータ・フロー・チップ／スケジューラのペア（第１のデータ・フロー・チップ１２及び第１のスケジューラ・チップ３４、又は第２のデータ・フロー・チップ１４及び第２のスケジューラ・チップ３８）のために設けることが可能である一般的なキューイング配列を概略的に示す。図２に示された特定の例では、第１のデータ・フロー・チップ１２及び第１のスケジューラ・チップ３４が示されるが、第２のデータ・フロー・チップ１４及び第２のスケジューラ・チップ３８に関連した全く同じキューイング配列を設けることも可能である。第１のデータ・フロー・チップ１２及び第１のスケジューラ・チップ３４に対するキューイング配列では、着信データ・フレームが第１のデータ・フロー・チップ１２（図１）に関連した入力データ・バッファ２４においてバッファされる。各データ・フレームがデータ・フロー又は「フロー」と関連付けられる。当業者にはよく知られているように、「フロー」は、発信元と宛先との間の単方向接続を表す。
【００１２】
着信データ・フレームが関連するフローが、第１のスケジューラ・チップ３４に維持されたスケジューリング・キュー４２においてエンキューされる。スケジューリング・キュー４２は、そこにエンキューされたフローがサービスされるべきシーケンスを定義する。本発明と関連した特定のスケジューリング・キューは、「ベスト・エフォート（best effort）」又は「最善帯域幅（available bandwidth）」というサービス品質（ＱＯＳ）を与えられたフロー間で調停する重み付けされたフェア・キュー（fair queue）である。
【００１３】
図２に示されるように、スケジューリング・キュー４２は、第１のデータ・フロー・チップ１２のそれぞれの出力ポート４４に関連付けられる。出力ポート４４が、図１に示された第１のスイッチ・ポート１６の１つであることは明らかであろう。（しかし、考察中のデータ・フロー・チップ／スケジューラのペアが出口側のデータ・フロー・チップ１４及びスケジューラ・チップ３８である場合、出力ポート４４はネットワーク・ポート２２の１つとなるであろう）。１つだけのスケジューリング・キュー４２及び１つの対応する出力ポート４４が示されているけれども、実際には、複数の出力ポート、及び各々がそれぞれのポートに割り当てられた対応するスケジューリング・キューが存在することは明らかであろう。
【００１４】
図２には示されてないけれども、第１のスケジューラ・チップ３４は、更に、保証付き帯域幅を有するスケジュールされたＱＯＣを与えられたフローに対する出力スケジュールを定義し、従ってスケジューリング・キュー４２によって管理されるフローよりも高い優先順位を享受する、フロー・スケジューリング・カレンダを含む。
【００１５】
第１のスケジューラ・チップ３４に関連したメモリ３６が、第１のデータ・バッファ２４におけるロケーションに対するポインタ（フレーム・ポインタ）を保持する。そのロケーションは、スケジューリング・キュー４２においてエンキューされたフローに関連するデータ・フレームに対応するメモリ３６は、フローに与えられるＱＯＳを表す情報のようなフロー制御情報も記憶する。
【００１６】
スケジューリング・キュー４２においてエンキューされた特定のフローがサービスされるべき次のフローであるということをそのスケジューリング・キュー４２が表す時、問題のフローに対する第１の保留データ・フレームに対応するメモリ３６におけるフレーム・ポインタに対して参照が行われ、その対応するフレーム・データが第１のデータ・バッファ２４から出力ポート４４に関連した出力キュー（データ・フロー・キュー）４６に転送される。
【００１７】
図３には、スケジューリング・キュー４２の更に詳細な図が示される。上述のように、スケジューリング・キュー４２は、「ベスト・エフォート」に基づいてサービスされたフローの重み付けされたフェア・キューイングのための使用される。図３に示されるようなスケジューリング・キューの特定の例では、スケジューリング・キュー４２は、５１２個のスロット（各スロットが参照番号４８によって表される）を有する。別の数のスロットを使用することも可能である。一般的な実施方法によれば、エンキューされるべきフローに関連したデータ・フレームの長さ及びそのフローに与えられるＱＯＣに対応した重みの両方を考慮した公式に基づいて、フローがエンキューされ又はスケジューリング・キュー４２に付加される。
【００１８】
更に詳しく云えば、エンキューする時にフローが入れられるキュー・スロットは、次のような公式、
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ）
に従って計算される。但し、ＣＰは、スケジューリング・キュー４２における現在位置（現在サービスされつつあるスロット）を表すポインタ（カレント・ポインタ）であり、ＷＦは、エンキューされるべきフローに関連した重み付け係数であり、そのフローに与えられるＱＯＳに基づいて決定されたものである。ＦＳは、エンキューされるべきフローに関連したカレント・フレームのサイズであり、ＳＦは、結果として生じた商がスケジューリング・キュー４２によって定義された範囲内にあるように積（ＷＦｘＦＳ）をスケーリングするために選択されたスケーリング係数である。（一般的な実施方法によれば、スケーリング係数ＳＦは、２の整数累乗として、即ち、ｎが正の整数である場合に  ＳＦ＝２n として定義され、従って、積（ＷＦｘＦＳ）のスケーリングは右シフトすることによって行われる）。この既知の重み付けされたフェア・キューイング技法によれば、各フローに割り当てられたＱＯＳに従って種々のフローに割り当てられた重み付け係数は、各フローがエンキューされるキューのカレント・ポインタに如何に近いかを管理する。更に、大きいフレーム・サイズを示すフローが、キューのカレント・ポインタから更にエンキューされ、そのようなフローがキューの使用可能な帯域幅を不当な比率で充当しないようにする。エンキューの時、フローを識別するデータ（フローＩＤ）が適切なキュー・スロット４８に記憶される。
【００１９】
アプリケーションによっては、約６４バイト乃至６４ＫＢ或いはその３倍程度の広範囲にわたる、フローに関連付けられたデータ・フレーム・サイズが存在し得る。更に、帯域幅が大きな融通性及び精度でもって売買されるように、広範囲の重み付け係数をフローに割り当てることが望ましい。従って、重み付けされたフェア・キューイングが適用されるスケジューリング・キューが大きな範囲を有することが望ましい。そのスケジューリング・キューの範囲は、着信フローをカレント・ポインタから入れることが可能な最大距離であると定義される。当業者には明らかであるように、スケジューリング・キュー４２は、最後のキュー・スロット（本願の例ではスロット番号５１１）が最初のキュー・スロット（スロット番号０）に隣接するように循環することによって、リングとして機能する。
【００２０】
スロットの数を増加させることによってスケジューリング・キューの範囲を増大させることが考えられる。しかし、これは、チップ上の必要な領域の増大、大きな製造コスト及び電力消費、並びにキュー・サーチ時間の増大による欠点を有する。従って、スケジューリング・キューの範囲とスケジューリング・キューのために必要な物理アレーを設ける場合に消費されるリソースとの間にトレードオフが存在する。このトレードオフは、サービスされるべき出力ポート（図１におけるスイッチ・ポート１６及び（又は）ネットワーク・ポート２２）の数が増加する時、特に深刻になる。一般的な実施方法は、各出力ポートがそれぞれの専用のスケジューリング・キューによってサービスされることを必要とする。要求する。従って、出力ポートの数が増加する時、対応するスケジューリング・キューのために設けられる物理的アレー・スペースがリソースの消費における対応した増加と共に増加しなければならず、或いは、各スケジューリング・キューのサイズが減少し、それによって、そのスケジューリング・キューによって与えられるべき重み付けされたフェア・キューイングの範囲及び効果を減少させなければならない。
【００２１】
【発明が解決しようとする課題】
従って、スケジューリング・キューの効果を減少させることなく、又はスケジューリング・キューのための物理的アレー・スペースにより消費されるリソースを増加させることなく、スケジューリング・キューによってサービスされるべき出力ポートの数を増加させることが望ましく、本発明の目的はそのような装置及び方法を提供することである。
【００２２】
【課題を解決するための手段】
本発明の１つの視点によれば、データ通信装置が提供される。その装置は、複数の出力ポートと、データ・フレームをアウトバウンドするために優先順位を割り当てるためのスケジューラとを含む。スケジューラは、１つ又は複数のスケジューリング・キューを含み、各スケジューリング・キューは、データ・フローがサービスされる順序を表す。少なくとも１つのスケジューリング・キューが、そのスケジューリング・キューにそれぞれの複数の出力ポートを割り当てられる。例えば、それぞれ２つの出力ポートが１つのスケジューリング・キューに割り当てられることがあり得る。別の方法として、それぞれ４つの出力ポートが１つのスケジューリング・キューに割り当てられることがあり得る。本発明の１つの実施例では、それら複数の出力ポートは２５６個の出力ポートを含み得るし、スケジューラは、それら２５６個の出力ポートが割り当てられる６４個のスケジューリング・キューを持ち得る。一般には、１つのスケジュ−リング・キューに対して、任意の数の出力ポートが割り当てられ得る。
【００２３】
本発明のもう１つの視点は、ネットワーク・プロセッサのためのスケジューラにおいてフローをエンキューする方法を提供する。その方法は、第１の出力ポートから送信するように指示された第１のフローに対応する第１のデータ・フレームを受け取ること、及びその第１のフローを、第１の出力ポートと関連した第１のスケジューリング・キューにエンキューすることを含む。その方法は、更に、第２の出力ポートから送信するように指示された第２のフローに対応する第２のデータ・フレームを受け取ること、及び第１のスケジューリング・キューが第２の出力ポートにも関連付けられている場合、その第２のフローを第１のスケジューリング・キューにエンキューすることを含む。
【００２４】
本発明のこの視点による方法は、更に、第３の出力ポートから送信するように指示された第３のフローに対応する第３のデータ・フレームを受け取ること、及び第１のスケジューリング・キューが第３の出力ポートにも関連付けられている場合、その第３のフローを第１のスケジューリング・キューにエンキューすることを含む。その方法は、更に、第４の出力ポートから送信するように指示された第４のフローに対応する第４のデータ・フレームを受け取ること、及び第１のスケジューリング・キューが第４の出力ポートにも関連付けられている場合、その第４のフローを第１のスケジューリング・キューにエンキューすることを含む。一般に、任意の数の出力ポートが使用され得る。
【００２５】
本発明の更にもう１つの視点によれば、ネットワーク・プロセッサからデータ・フレームを伝送する方法が提供される。その方法は、第１のスケジューリング・キューから第１のフローをデキューすること、及びそのデキューされた第１のフローに関連したデータ・フレームを第１の出力ポートから送信することを含む。その方法は、更に、第１のスケジューリング・キューから第２のフローをデキューすること、及びそのデキューされた第２のフローに関連したデータ・フレームを第２の出力ポートから送信することを含む。この場合、第２の出力ポートは、第１の出力ポートとは異なる。
【００２６】
更に、その方法は、第１のスケジューリング・キューから第３のフローをデキューすること、及び第３の出力ポートが第１及び第２の出力ポートとは異なる場合、そのデキューされた第３のフローに関連したデータ・フレームを第３の出力ポートから送信することを含む。更に、その方法は、第１のスケジューリング・キューから第４のフローをデキューすること、及び第４の出力ポートが第１、第２、及び第３の出力ポートとは異なる場合、そのデキューされた第４のフローに関連したデータ・フレームを第４の出力ポートから送信することを含む。一般に、任意の数の出力ポートが使用され得る。
【００２７】
本発明の更なる視点によれば、データ通信装置を操作する方法は、ネットワーク・プロセッサのためのスケジューラにスケジューリング・キューを設けること、及びそのスケジューリング・キューに複数の出力ポートを割り当てることを含む。
【００２８】
各スケジューリング・キューを複数の出力ポートの間で共用することによって、スケジューリング・キューの効果を危うくすることなく、及びスケジューリング・キューに対して与えられた物理的アレーに追加のリソース（例えば、チップ・エリア）を充当することなく、サービスされる出力ポートの数を増加させることができる。
【００２９】
以下の実施例の詳細な説明、特許請求の範囲の記載、及び添付図面から、本発明の他の目的、特徴、及び利点が十分に明らかとなるであろう。
【発明の実施の形態】
【００３０】
図１を再び参照すると、１つの実施例では、第１のデータ・フロー・チップ１２の第１のスイッチ・ポート１６（出力ポート）の数が２５６個であり、それらは、スイッチ１５と関連してインストールされた２５６個の「ブレード」に対応する。更に、本発明の実施例によれば、２５６個の出力ポートをサービスするために第１のスケジューラ３４に含まれた重み付けされたフェア・キューイング・スケジューリング・キュー４２（図２及び図３）の数が６４個である。そのような実施例では、本発明に従って、第１のスケジューリング・キュー４２の各々が４個の出力ポート（例えば、４個の第１のスイッチ・ポート１６）によって共用される。
【００３１】
対照的に、第２のデータ・フロー・チップ１４のための出力ポートとして働く第２のデータ・フロー・チップ１４のための第２のネットワーク・ポート２２の数は６４個である。第２のスケジューラ・チップ３８は、第１のスケジューラ・チップ３４と同じであり、第２のデータ・フロー・チップ１４の６４個の出力ポート（第２のネットワーク・ポート２２）をサービスするために６４個のスケジューリング・キューを有する。従って、第２のデータ・フロー・チップ１４及び第２のスケジューラ３８のペアでは、出力ポートと第２のスケジューラ３８のスケジューリング・キュートの間に一般的な１対１の関係が一般的である。第１のデータ・フロー・チップ１２／スケジューラ３４及び（又は）第２のデータ・フロー・チップ１４／スケジューラ３８に対する出力ポートの数及びスケジューリング・キューの数の間には、後述するように、別の関係が考えられる。
【００３２】
図４は、図１の第１のスケジューラ３４の６４個のスケジューリング・キュー４２（図４では、リング０−リング６３として示される）を概略的に示す。
【００３３】
図４における参照番号５０によって示されるように、第１のデータ・フロー・チップ１２の出力ポート（図１における第１のスイッチ・ポート１６）が、それぞれの出力ポートを識別する番号の下位ビットに従って、第１のスケジューラ３４のスケジューリング・キュー４２に割り当てられる。従って、図示のように、出力ポート０、６４、１２８、及び１９２がスケジューリング・キュー０（リング０）に割り当てられ、出力ポート１、６５、１２９、及び１９３がスケジューリング・キュー１（リング１）に割り当てられ、出力ポート２、６６、１３０、及び１９４がスケジューリング・キュー２（リング２）に割り当てられる。同様に、出力ポート６３、１２７、１９１、及び２５５がスケジューリング・キュー６３（リング６３）に割り当てられる。本願において使用されるように、スケジューリング・キューに対する出力ポートの割り当ては、出力ポートが割り当てられるスケジューリング・キューに、特定の出力ポートからの送信を指示されたフローがエンキューされることを意味する。従って、スケジューリング・キューのうちの任意の１つにエンキューされたフローの中には、スケジューリング・キューからフローをデキューした時に複数の出力キューから送信されるようにそれぞれ指示されたフローがある。
【００３４】
更に、図４は、一般的なカレント・ポインタ５２の使用を含む、本発明のスケジューリング・キュー４２の数多くの別の特徴を示している。各スケジューリング・キュー４２に関して、カレント・ポインタ５２は、それぞれのスケジューリング・キューに対する最近サービスされたスロット又は現在サービスされつつあるスロットを表す。それぞれのスケジューリング・キューがエンプティであるかどうかを表すインディケータが、図４における参照番号５４によって示される。。少なくとも１つの実施例には、２００１年１１月１日に出願された米国特許出願番号第１０／００２,０８５号に開示された発明に従って、インディケータ５４が設けられる。即ち、スケジューラは、更に、１つ又は複数のエンプティ・インディケータを含む。各エンプティ・インディケータは、それぞれのスケジューリング・キューがエンプティであるかどうかを表すように、それぞれのスケジューリング・キューと関連付けられる。各エンプティ・インディケータは、レジスタにおけるビットであってもよい。一般に、シフト・レジスタ・ラッチ（ＳＲＬ）のような任意の一般的なレジスタ又は他の記憶手段が各エンプティ・インディケータの代わりに使用され得る。各スケジューリング・キュー４２がエンプティであるかどうかを表すために、別の表示方式が利用され得る。図４における参照番号５６によって、ラウンド・ロビン・プロセスが６４個のスケジューリング・キュー４２の各々を順次にサーチし得ることが示される。他のサーチ・プロセスも使用可能である。
【００３５】
図５は、本発明に従って、データ・フレーム及びフローがエンキューされ得る手順を示すフローチャートである。図５を参照すると、着信データ・フレーム及び（又は）フローをエンキューする（ブロック６２）時間まで、図５の手順がアイドリングする（ブロック６０）。次に、着信データ・フレームが関連するフローが既にスケジューリング・キュー４２（例えば、図４におけるリング１ー６３）の１つに付加されているかどうかが決定される（ブロック６４）。フローが既にスケジューリング・キューに付加されている場合、図５の手順はアイドリング状態に戻る（ブロック６０）。（この場合、一般的な実施方法によれば着信データ・フレームに関連したフローが付加されるスケジューリング・キューにその着信データ・フレームが加えられる。（例えば、第１スケジューラ３４に関連したメモリ３６（図２）に維持される対応したフローに対するフロー・キュー））。
【００３６】
着信データ・フレームに関連したフローがスケジューリング・キュー４２の１つに付加されてない場合、ブロック６６がブロック６４に続く。ブロック６６において、対応するフローが６４個のスケジューリング・キュー４２の１つ（例えば、図４のリング０−６３の１つ）に付加される。フローが送信されるべき出力ポートの番号に基づいて、特定のスケジューリング・キューが選択される。更に詳しく云えば、フローが付加されるべきスケジューリング・キューの番号が、図４を参照して前述したように、そのフローに対する出力ポートの番号の下位６ビットによって表され得る。フローを付加すべきスケジューリング・キューを識別するために、別の方法が使用可能である。表示されたスケジューリング・キューへのフローの付加は、重み付けされた係数ＷＦが問題の出力ポートに調和した相対的低域幅に部分的に基づき得ることを除いて、一般的な公式
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ）
に従って進行する。ＣＰは、それぞれのスケジューリング・キュー４２のカレント・ポインタのことであり、ＦＳは、エンキューされるべきフローに関連したカレント・フレームのサイズのことであり、ＳＦは、スケーリング係数であるということを想起してほしい。
【００３７】
本発明による相対的な出力ポート帯域幅に基づいた適当な重み付け係数の計算が図６に示される。従って、図６は、重み付けされたフェア・キューイングのための重み付け係数ＷＦが本発明に従って計算される手順を示すフローチャートである。図６の手順は、問題のスケジューリング・キュー４２（図４における１つ又は複数のリング０−６３）が複数の出力ポートによって共用されるべきかどうかが決定されるまでアイドリングする（ブロック７２）。そのような事実がない場合、図６の手順はアイドリング状態に戻る（ブロック７０）。複数の出力ポートによる特定のスケジューリング・キュー４２の共用が実施される場合、ブロック７４がブロック７２に続く。ブロック７４において、スケジューリング・キュー４２を共用する出力ポートにそれぞれ割り当てられた帯域幅の比率が決定される。しかる後、ブロック７６において、最大の帯域幅を割り当てられたスケジューリング・キュー４２を共用する出力ポートが識別される。この目的のために、最大帯域幅に対する出力ポートがポートＡと呼ばれること、及び４つの出力ポートがスケジューリング・キュー４２を共用するために割り当てられること（しかし、別の数の出力ポートがスケジューリング・キュー４２を共用することも可能である）が仮定される。
【００３８】
４つの出力ポートのそれぞれの帯域幅を基準にして、ポートＡ、Ｂ、Ｃ及びＤと指定された４つの出力ポートの各々に対して、それぞれの重みスケーラ（weight scaler - ＷＳ）が計算される（ブロック７８）。ポートＡに割り当てられた重みスケーラＷＳは、値「１」を割り当てられ、ポートＢに割り当てられた重みスケーラＷＳは、ポートＡに割り当てられた帯域幅（ＡBW）をポートＢに割り当てられた帯域幅（ＢBW）で除したものに等しく、ポートＣに割り当てられた重みスケーラＷＳは、ポートＡに割り当てられた帯域幅（ＡBW）をポートＣに割り当てられた帯域幅（ＣBW）で除したものに等しく、ポートＤに割り当てられた重みスケーラＷＳは、ポートＡに割り当てられた帯域幅（ＡBW）をポートＤに割り当てられた帯域幅（ＤBW）で除したものに等しい。別の重みスケーラの割り当ても使用可能である。
【００３９】
次に、ブロック８０において、特定のフローに対する重み付け係数ＷＦが、そのフローに対するサービス品質（ＱＯＳ）に従ってそのフローに割り当てられた重みと、伝送されるフローの発信元である出力ポートに対する重みスケーラＷＳとの積として計算される。フローに対するＱＯＳ重み係数は、例えば、メモリ３６（図２）に記憶され得る。大きな重みスケーラは、小さい帯域幅を有する出力ポートに割り当てられることがわかるであろう。従って、それらの出力ポートから出力されるべきフローが現在ポインタから比例的に更にエンキューされ、従って、使用可能な帯域幅の小さな部分を受け取る。
【００４０】
図７は、本発明に従って、フローがスケジューリング・キューからデキューされるプロセスを示すフロー・チャートである。先ず、問題のスケジューリング・キュー４２からフローをデキューする時間であることが決定されるまで、図７のプロセスはアイドリングする（ブロック９０）。しかる後、ブロック９２において、スケジューリング・キュー内にあって現在ポインタに対して最も近い非エンプティ・スロット４８（図３）が読み取られる。ブロック９４に続くのは、判断ブロック９６である。判断ブロック９６では、フローを送信する出力ポートが決定され、その出力ポートがバックプレッシャ状態にあるかどうかが更に決定される。（ポート・バックプレッシャの概念は、当業者にはよく知られており、本願では後述される必要がないであろう）。しかし、一般には、出力ポート・バックプレッシャ状態は、出力ポートに対応する出力／データ・フロー・キュー４６（図２）がフルである（例えば、更なるフレームを受け付けることができない）状態のことである。
【００４１】
出力ポートがバックプレッシャ状態にない場合、ブロック９８が判断ブロック９６に続く。ブロック９８では、フローに対応し且つメモリ３６（図２）に維持されたフロー・キューが参照され、そのフロー・キューにおけるヘッド・フレームが決定される。しかる後、そのヘッド・フレームが入力データ・バッファ２４（図１及び図２）から、問題の出力ポートに対応する出力キュー４６（図２）に転送される。順当に行けば、しかる後、データ・フレームが出力ポートから伝送されることは明らかであろう。
【００４２】
図７をもう１度参照すると、判断ブロック１００がブロック９８に続く。判断ブロック１００では、そのフロー・キュー（図２のメモリ３６）には、伝送のためにちょうどディスパッチされたヘッド・フレーム以外の更なるフレームが存在するかどうかが、一般的な実施方法に従って決定される。それが肯定される場合、ブロック１０２が続く。ブロック１０２では、一般的な公式
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ
に従ってフローがスケジューリング・キュー４２に再付加される。通例のように、フレーム・サイズＦＳは、フロー・キューにおけるカレント・データ・フレームのサイズである。ブロック１０２におけるスケジューリング・キュー４２へのフローの再付加に続いて、図７の手順はアイドリング状態に戻る（ブロック９０）。
【００４３】
再び、判断ブロック１００を考察すると、伝送のためにちょうどディスパッチされたデータ・フレームがフロー・キュー（図２におけるメモリ３６）における最後のフレームであることがわかった場合、図７の手順は、フローをスケジューリング・キューに再付加することなく、アイドリング状態に戻る（ブロック９０）。
【００４４】
再び、判断ブロック９６を考察すると、出力ポートがバックプレッシャ状態にあるということが判断ブロック９６において決定される場合、ブロック１０２がブロック９６に直接に続く。即ち、出力ポートを介した伝送のためにフローのデータ・フレームをディスパッチすることなく、それのカレント・スロット４８からの距離でスケジューリング・キュー４２に再付加される。出力ポート・バックプレッシャに応答してデータ・フレームをディスパッチすることなくフローを再付加する場合、その再付加は、重み付け計数及びフレーム・サイズを使用する一般的な公式に基づき得る。別の方法として、その再付加は、バックプレッシャ状態がクリアされるまでスケジューリング・キュー４２においてフローがアクセスされる回数を最小にするために、多くの一般的な公式に基づてもよく、又はカレント・ポインタからの最大距離にあってもよい。
【００４５】
図５乃至図７のプロセスは、ハードウェア、ソフトウェア、又はそれらの組み合わせで実施され得る。本発明の少なくとも１つの実施例では、図５乃至図７のプロセスは、アダー、コンパレータ、セレクタ等のような一般的な論理回路の適当な結合を使用するハードウェアで実施される。そのようなハードウェアは、例えば、スケジューラ３４及び（又は）スケジューラ３８（図１）において設置され得る。図５乃至図７を参照して説明された本発明のプロセスを遂行することができる論理回路を、当業者が開発してもよい。本発明のソフトウェアの実施例では、図５乃至図７のプロセスは、１つ又は複数のコンピュータ・プログラム製品を含み得る。各コンピュータ・プログラム製品は、コンピュータによる読み取り可能な媒体（例えば、搬送波信号、フロッピー（R)ディスク、ハード・ドライブ、ランダム・アクセス・メモリ等）によって実行され得る。
【００４６】
スケジューリング・キュー当たり２つ又はそれ以上の出力ポートの間でキューを共用又はスケジューリングする場合、スケジューリング・キューの維持に充当するリソースが効率的に使用され、大量の出力ポートが所与の数のスケジューリング・キューのために働き得る。
【００４７】
前記の説明は、本発明の実施例のみを開示している。本発明の技術的範囲内にある上記装置及び方法の修正は、当業者には容易に明らかであろう。例えば、４個の出力ポートの間で各スケジューリング・キューを共用することが上で説明されたが、各スケジューリング・キューに割り当てられた２個、３個、或いは５個又はそれ以上の出力ポートの数も考えられる。本明細書及び特許請求の範囲において使用される出力ポートという用語は、言及されたスイッチ又はネットワーク・ポートを含み、とりわけ、出力フローに関連の出力チャネルに関連した装置のポートを含む。
【００４８】
更に、上記の実施例では、スケジューリング・キューへの出力ポートの割り当てが、出力ポート及びスケジューリング・キューに割り当てられた数に従って一定の基準で行われる。しかし、スケジューリング・キューへの出力ポートの割り当ては可変的であり、スケジューリング・キューへの出力ポートの割り当てを表すデータを記憶したプログラム可能レジスタ（図示されてない）又は他の記憶ロケーションに記憶されたデータによって表示され得るということも考えられる。
【００４９】
スケジューラ３４内に維持されたスケジューリング・キューの数は上記の例では６４であるとして表されるけれども、勿論、スケジューラ３４においてもっと多い又は少ない数のスケジューリング・キューを含むことが考えられる。更に、スケジューリング・キューは、別個のチップとして実装されるスケジューラの一部分であるとして示されているけれども、スケジューリング・キューが、データ・フロー・チップ又はプロセッサ・チップに統合されたスケジューラの一部分としても維持され得る。
【００５０】
更に、拡張された範囲を有するスケジューリング・キューに関連して本発明を実施することが考えられる。そのようなスケジューリング・キューは、２００１年１１月１日出願の米国特許出願番号第１０／０１６,５１８号の明細書に開示されている異なるそれぞれの範囲及び解決法を有するサブキューを含み得る。
【００５１】
従って、本発明がそれの実施例に関連して開示されたけれども、別の実施例が本発明の精神及び技術的範囲内にあり得ることは勿論である。
【００５２】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００５３】
（１）複数個の出力ポートと、
アウトバウンド・データ・フレームに優先順位を割り当てるように適応したスケジューラにして、１つ又は複数個のスケジューリング・キューを含む、スケジューラと、
を含み、各スケジューリング・キューは、データ・フローがサービスされる順序を表すように適応し、少なくとも１つのスケジューリング・キューが当該スケジューリング・キューに割り当てられた複数個の出力ポートを有する、データ通信装置。
（２）前記１つ又は複数個のスケジューリング・キューが重み付けされたフェア・キューイングのために使用される、（１）に記載のデータ通信装置。
（３）前記データ・フレームは、サイズが変わるものである、（１）に記載のデータ通信装置。
（４）前記出力ポートのうちのそれぞれの２つが１つのスケジューリング・キューに割り当てられる、（１）に記載のデータ通信装置
（５）前記出力ポートのうちのそれぞれの４つが１つのスケジューリング・キューに割り当てられる、（１）に記載のデータ通信装置
（６）前記複数個の出力ポートは２５６個の出力ポートであり、前記スケジューラは、前記２５６個の出力ポートが割り当てられる６４個のスケジューリング・キューを有する、（５）に記載のデータ通信装置。
（７）前記スケジューラは第１の集積回路を含み、前記出力ポートは、前記第１の集積回路に結合された第２の集積回路に含まれる、（１）に記載のデータ通信装置。
（８）ネットワーク・プロセッサのためのスケジューラにおいてフローをエンキューする方法にして、
第１の出力ポートから送信するように指定された第１のフローに対応する第１のデータ・フレームを受け取るステップと、
前記第１の出力ポートに関連した第１のスケジューリング・キューに前記第１のフローをエンキューするステップと、
第２の出力ポートから送信するように指定された第２のフローに対応する第２のデータ・フレームを受け取るステップと、
前記第１のスケジューリング・キューに前記第２のフローをエンキューするステップであって、前記第１のスケジューリング・キューが前記第２の出力ポートにも関連するステップと、
を含む方法。
（９）第３の出力ポートから送信するように指定された第３のフローに対応する第３のデータ・フレームを受け取るステップと、
前記第１のスケジューリング・キューに前記第３のフローをエンキューするステップであって、前記第１のスケジューリング・キューが前記第３の出力ポートにも関連する、ステップと、
第４の出力ポートから送信するように指定された第４のフローに対応する第４のデータ・フレームを受け取るステップと、
前記第１のスケジューリング・キューに前記第４のフローをエンキューするステップであって、前記第１のスケジューリング・キューが前記第４の出力ポートにも関連する、ステップと、
を更に含む、（８）に記載の方法。
（１０）前記第１のスケジューリング・キューが、重み付けされたフェア・キューイングのために使用される、（８）に記載の方法。
（１１）前記エンキューするステップの各々は、公式
ＣＰ＋（（ＷＦｘＦＳ）／ＳＦ
に従って前記第１のスケジューリング・キューにそれぞれのフローを付加することを含む（但し、ＣＰはそれぞれのフローに関連したカレント・ポインタ値であり、ＷＦはそれぞれのフローに関連した重み付け係数であり、ＦＳはそれぞれのフローに関連したフレーム・サイズであり、ＳＦはスケーリング係数である）、（１０）に記載の方法。
（１２）前記重み付け係数ＷＦは、それぞれのフローが送信を指定される出力ポートに関連した重みスケーラＷＳに部分的に基づている、（１１）に記載の方法。
（１３）ネットワーク・プロセッサからデータ・フレームを送信する方法にして、
第１のスケジューリング・キューから第１のフローをデキューするステップと、
デキューされた第１のフローに関連したデータ・フレームを第１の出力ポートから送信するステップと、
前記第１のスケジューリング・キューから第２のフローをデキューするステップと、
デキューされた第２のフローに関連したデータ・フレームを第２の出力ポートから送信するステップであって、前記第２の出力ポートが前記第１の出力ポートとは異なる、ステップと、
を含む方法。
（１４）前記第１のスケジューリング・キューから第３のフローをデキューするステップと、
デキューされた第３のフローに関連したデータ・フレームを第３の出力ポートから送信するステップであって、前記第３の出力ポートが前記第１及び第２の出力ポートとは異なる、ステップと、
前記第１のスケジューリング・キューから第４のフローをデキューするステップと、
デキューされた第４のフローに関連したデータ・フレームを第４の出力ポートから送信するステップであって、前記第４の出力ポートが前記第１、第２、及び第３の出力ポートとは異なる、ステップと、
を含む、（１３）に記載の方法。
（１５）前記第１のスケジューリング・キューが、重み付けされたフェア・キューイングのために使用される、（１３）に記載の方法。
（１６）データ通信装置を操作する方法にして、
ネットワーク・プロセッサのためのスケジューラにおいてスケジューリング・キューを設けるステップと、
前記スケジューリング・キューに複数の出力ポートを割り当てるステップと、
を含む、方法。
（１７）前記スケジューリング・キューは前記スケジューラに設けられた複数のスケジューリング・キューの１つであり、前記スケジューリング・キューの各々はそれぞれの複数個の出力ポートを割り当てられる、（１６）に記載の方法。
（１８）前記スケジューリング・キューに４つの出力ポートが割り当てられる、（１６）に記載の方法。
（１９）複数個の出力ポートと、
少なくとも１つのスケジューリング・キューを有するスケジューラと、
を含み、前記スケジューラは、
前記出力ポートのうちの第１の出力ポートから送信するために指定された第１のフローに対応する第１のデータ・フレームを受け取り、
前記第１のフローを、前記出力ポートのうちの第１の出力ポートに関連した第１のスケジューリング・キューにエンキューし、
前記出力ポートのうちの第２の出力ポートから送信するために指定された第２のフローに対応する第２のデータ・フレームを受け取り、
前記第２のフローを前記第１のスケジューリング・キューにエンキューする、
ように適応し、
前記第１のスケジューリング・キューが前記出力ポートのうちの第２の出力ポートにも関連する、データ通信装置。
（２０）複数個の出力ポートと、
少なくとも１つのスケジューリング・キューを有するスケジューラと、
を含み、前記スケジューラは、
第１のスケジューリング・キューから第１のフローをデキューし、
デキューされた第１のフローに関連したデータ・フレームを前記出力ポートのうちの第１の出力ポートから送信し、
第１のスケジューリング・キューから第２のフローをデキューし、
デキューされた第２のフローに関連したデータ・フレームを前記出力ポートのうちの第２の出力ポートから送信する、
ように適応する、データ通信装置。
（２１）ネットワーク・プロセッサのためのスケジューラにおいてフローをエンキューするためのコンピュータ・プログラムにして、
コンピュータによる読み取りが可能な媒体を含み、
前記コンピュータによる読み取りが可能な媒体は、
第１の出力ポートから送信するように指定された第１のフローに対応する第１のデータ・フレームを受け取りと、
前記第１の出力ポートと関連した第１のスケジューリング・キューに前記第１のフローをエンキューし、
第２の出力ポートから送信するように指定された第２のフローに対応する第２のデータ・フレームを受け取り、
前記第１のスケジューリング・キューに前記第２のフローをエンキューする、
ように適応したコンピュータ・プログラム・コードを有し、前記第１のスケジューリング・キューは前記第２の出力ポートとも関連する、コンピュータ・プログラム。
（２２）ネットワーク・プロセッサからデータ・フレームを送信するためのコンピュータ・プログラムにして、
コンピュータによる読み取りが可能な媒体を含み、
前記コンピュータによる読み取りが可能な媒体は、
第１のスケジューリング・キューから第１のフローをデキューし、
デキューされた第１のフローに関連したデータ・フレームを第１の出力ポートから送信し、
前記第１のスケジューリング・キューから第２のフローをデキューし、
デキューされた第２のフローに関連したデータ・フレームを第２の出力ポートから送信する
ように適応したコンピュータ・プログラム・コードを有し、前記第２の出力ポートは前記第１の出力ポートとは異なる、コンピュータ・プログラム。
（２３）１つ又は複数個のスケジューリング・キューを有するスケジューラを含むデータ通信装置を操作するコンピュータ・プログラムにして、
コンピュータによる読み取りが可能な媒体を含み、
前記コンピュータによる読み取りが可能な媒体は、前記１つ又は複数個のスケジューリング・キューのうちの第１のスケジューリング・キューに複数個の出力ポートを割り当てるようにコンピュータ・プログラム・コードを適応させる、コンピュータ・プログラム。
【図面の簡単な説明】
【図１】本発明を適用し得る一般的なネットワーク・プロセッサのブロック図である。
【図２】図１のネットワーク・プロセッサに含まれるデータ・フロー・チップ／スケジューラ・ペアにおいて設けられた一般的なキューイング配列のブロック図表示である。
【図３】一般的な実施方法に従って提供された重み付けされたフェア・キューイング・スケジューリング・キューの概略図である。
【図４】図２のスケジューラ内に維持されたスケジューリング・キューの概略的表示であり、本発明に従って各スケジューリング・キューに対する複数の出力ポートの割り振りを示す。
【図５】本発明に従ってフローをエンキューするためのプロセスを示すフロー・チャートである。
【図６】本発明に従ってフローに対する重み付け計数を決定するためのプロセスを示すフロー・チャートである。
【図７】本発明に従ってフローをデキューするためのプロセスを示すフロー・チャートである。
【符号の説明】
４２  スケジューリング・キュー
５０  出力ポート
５２  カレント・ポインタ
５４  インディケータ
５６  ラウンド・ロビン・プロセスの表示
【図１】
0003989817.tif 000002
【図２】
0003989817.tif 000003
【図３】
0003989817.tif 000004
【図４】
0003989817.tif 000005
【図５】
0003989817.tif 000006
【図６】
0003989817.tif 000007
【図７】
0003989817.tif 000008