(57)【要約】  通信環境におけるタイムベースのスケジューリング用のシステムと方法が提供される。１実施例では、前記方法は、少なくとも１つのトークンを所定期間の間に複数のアクティブなキューの各々に割り当てる工程を含む。各トークンは、前記キューからデキューされるデータ量を許可する。前記方法は、新たな一連の割当を開始する前に前記所定期間が終了するまで待つ工程を更に有する。少なくとも１つの前記キューが前記キューに割り当てられたトークンに基づいて指定され、この指定は前記キューからデキューされるデータの量を許可する。前記指定はメモリシステムに送られて、前記データがデキューされ、且つネットワークアップリンクに送信される。【選択図】      なし
2007504787.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークでのトラフィックのスケジューリング方法であって、
少なくとも１つのトークンを所定期間内に複数のアクティブなキューのそれぞれに割り当てる工程であって、各トークンは前記キューからデキューされるデータ量を許可する、工程と、
新たに一連の割当を開始する前に前記所定期間の終了まで待機する工程と、
前記キューに割り当てられた前記少なくとも１つのトークンに基づいて少なくとも１つのキューを指定する工程であって、前記キューから前記データ量のデキューを許可する、工程と、
前記データをデキューし、前記データをネットワークアップリンクに送信するために前記指定をメモリシステムに送信する工程と、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法において、前記キューのうち少なくとも１つを指定する工程は、
複数エントリを前記の複数トークンに基づいて指定テーブルにロードする工程であって、キュー別に直線的に行われるものである、前記のロード工程と、
ランダムアドレスを生成して前記ランダムアドレスにあるエントリを取り出すことによって前記の指定テーブルから前記エントリの少なくとも１つを選択する工程と、
を有することを特徴とする方法。
【請求項３】
請求項２記載の方法において、前記選択する工程は、所定期間の間、確定した回数分繰り返し行われ、前記確定された回数は合計のアップリンクバンド幅に比例するものであることを特徴とする方法。
【請求項４】
請求項１記載の方法において、
各キュー用に第１と第２のトークンを計算する工程を更に有し、空のキューでないことを前提として、前記第１のトークンは前記ネットワークへのトラフィックが許可される最低レートを定義する第１のキュー毎のレートに基づき、前記第２のトークンは前記ネットワークへのトラフィックが許可される最高レートを定義するキュー毎のレートに基づくことを特徴とする方法。
【請求項５】
請求項５記載の方法において、キューに対し前記第１と第２のトークンを計算する前に前記キューが有効であるかどうかを判定する工程を更に有することを特徴とする方法。
【請求項６】
請求項５記載の方法において、前記判定するが、前記キューがデキューされることになるトラフィックを有しているかどうかを識別する、前記キューと関連のある識別子に基づいていることを特徴とする方法。
【請求項７】
請求項１記載の方法において、キュー用に少なくとも１つのトークンを計算する前にそのキューのプロビジョニング情報を読み出す工程を更に有することを特徴とする方法。
【請求項８】
請求項１記載の方法において、キュー用に少なくとも１つのトークンを計算する前に前記メモリシステムからそのキューの情報を読み出す工程を更に有することを特徴とする方法。
【請求項９】
請求項８記載の方法において、前記キュー情報は、前記メモリシステムへエンキューされたバイト数、データが待機状態にされたキューのキュー番号、前記メモリシステムからデキューされたバイト数、データがデキューされたキューのキュー番号を含むことを特徴とする方法。
【請求項１０】
請求項１記載の方法において、１キューから関連するキューに未使用のバンド幅を割り当てる工程を更に有することを特徴とする方法。
【請求項１１】
請求項１０記載の方法において、前記未使用のバンド幅は、空のキューでないことを前提として、そのキューに前記ネットワークへのトラフィックが許可される最低レートに基づいて計算されることを特徴とする方法。
【請求項１２】
請求項１記載の方法において、各フレームベースで使用されるアップリンクのオーバーヘッドバンド幅を計算する工程を更に有することを特徴とする方法。
【請求項１３】
請求項１記載の方法において、前記アップリンクの最高の可能バンド幅を満たすために必要なレートを超えたレートで指定が行なわれることを特徴とする方法。
【請求項１４】
通信ネットワークでのアップリンクトラフィックをスケジュールするシステムであって、
第１と第２のトークンを複数キューの各々に対して計算するように構成された低速サイドモジュールであって、前記第１のトークンは、キューが空でない場合に前記ネットワークへのトラフィックを許可する最低レートを表し、前記第２のトークンはキューが空でない場合に前記ネットワークへのトラフィックを許可する最高レートを表す、前記低速サイドモジュールと、
前記第１と第２のトークンに基づき前記複数キューから情報をデキューするのを導くように構成された高速サイドモジュールと、
前記低速サイド及び高速サイドモジュール間に位置するトークンバンクであって、前記低速サイドモジュールは前記の第１及び第２のトークンを前記トークンバンクに保管し、前記高速サイドモジュールは前記トークンバンクから前記第１及び第２のトークンを取り出すことを特徴とするシステム。
【請求項１５】
請求項１４記載のシステムにおいて、前記低速サイドモジュールは、前記第１と第２のトークンの各々を所定期間の間に計算するように構成されることを特徴とするシステム。
【請求項１６】
請求項１５記載のシステムにおいて、前記低速サイドモジュールは前記の複数キューの各々に対して新たに第１及び第２のトークンの計算を開始する前に、前記所定期間が終了するまで待つように構成されることを特徴とするシステム。
【請求項１７】
請求項１４記載のシステムにおいて、前記低速サイドモジュールは前記の第１及び第２のトークンの各々を各ビットベースで計算するように構成されることを特徴とするシステム。
【請求項１８】
請求項１４記載のシステムであって、前記低速サイドモジュールは、前記の第１及び第２のトークンの各々を各オクテットベースで計算するように構成されることを特徴とするシステム。
【請求項１９】
請求項１４記載のシステムにおいて、第１及び第２のキューが関連付けられ、前記低速サイドは未使用のトークンを前記第１のキューから前記第２のキューへ割り当てるように構成されることを特徴とするシステム。
【請求項２０】
請求項１４記載のシステムにおいて、前記低速サイド及び高速サイドモジュールは、キューイングシステムと交信状態にあることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願では、２００３年５月２９日に出願された、発明の名称「タイムベースのスケジューリング方法（ＭＥＴＨＯＤ  ＦＯＲ  ＴＩＭＥ−ＢＡＳＥＤ  ＳＣＨＥＤＵＬＩＮＧ）」、米国仮出願番号第６０／４７４，００８号からの優先権を主張し、そこに開示されたすべての内容はこの参照により本明細書に組み込まれるものとする。
【背景技術】
【０００２】
通信システムは、単一の物理的通信チャネル上で送信可能な異なるタイプの情報（データ、音声、ビデオ等）を頻繁に処理する。それぞれの情報タイプは、例えばバッファリング、待ち時間、待ち時間変数等、異なる送信要件を持つ場合がある。これらの異なる要件を満たすために、情報のネットワーク入りが許可される際に、システムはスケジューラを使って各タイプの情報を個別に処理することが可能である。しかし、現在のスケジューラでは能力が限られている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
そのため、通信ネットワーク上での改良されたスケジューリングを提供するシステム及び方法が必要とされている。  
【課題を解決するための手段】
【０００４】
本願は、一般に通信システムに関するものであり、特に通信ネットワークにおいてタイムベースのスケジューリングのシステム及び方法を提供するものである。
【発明を実施するための最良の形態】
【０００５】
以下の開示では、当然のことながら多くの異なる実施形態と実施例が提供される。本開示を簡素化するために、構成要素及び配置の特定の例を以下に説明する。これらは、当然ながら単なる例であり、限定するためのものではない。更に、本開示において同じ参照符号及び文字が各種の例で使用されている。同符号の使用は、簡素化と明確さのためであり、それらが説明される各種実施形態及び／または構成間の関係を決定するものではない。
【０００６】
図１ａを参照すると、通信ネットワークでのトラフィックをスケジュールするための典型的な方法１０が示されている。下記に更に詳細に説明されるように、前記方法１０は１つ若しくはそれ以上のトークンを１つ若しくはそれ以上のキューのそれぞれに計算して割り当ててもよい。次に、前記トークンは、各キューから情報をデキューするのを規制するために使用される。
【０００７】
ステップ１２では、前記方法１０は、所定期間内で、１つ若しくはそれ以上のトークンをアクティブな複数のキューのそれぞれに割り当ててもよい。各トークンは、前記キューからデキューさせるデータ量を許可する。後述されるように、前記所定期間によってスケジューリングの制御が向上する。ステップ１４において、前記方法１０は、前記所定期間が終了するまで新たな一連の割当の開始を待つ。順次に、または同時に、前記キューの少なくとも１つは、そのキューに割り当てられた少なくも１つのトークンに基づいて指定されてもよい。キューの指定は、そのキューから（トークンにより許可された）データ量のデキューを許可する。ステップ１８では、前記指定はメモリシステムに送られて、データがデキューされて、ネットワークのアップリンクに転送される。
【０００８】
次に図１ｂを参照すると、典型的システム１００の１実施形態が図示されている。前記システム１００は、第１のネットワーク構成要素１０２を含み、これは同期光ファイバネットワーク（ＳＯＮＥＴ）１０４を通じて第２のネットワーク構成要素１０６に接続されている。明瞭化のために、ＳＯＮＥＴという用語は、本明細書においてＳＯＮＥＴ及び／または同期デジタルハイアラーキ（ＳＤＨ）を示すために使用される。そのため、ＳＯＮＥＴへの言及はＳＤＨへの言及と置き換えることが可能であり、その際、若干変更が必要となる場合があるが、それらは当業者にとって周知のことである。本明細書のネットワーク構成要素は、ネットワークにアクセス可能な任意のコンポーネント、装置、またはシステム（ハードウェア及び／またはソフトウェア）でもよいが、前記ネットワーク構成要素１０２は、ＰＰＰ処理を実行するように構成されたイーサネットオーバーソネット（Ｅｔｈｅｒｎｅｔ−ｏｖｅｒ−ＳＯＮＥＴ）構成要素が可能である。
【０００９】
この例では、前記ネットワーク構成要素１０６はＮＯＣ  １０８内に位置し、前記ＮＯＣ  １０８は前記ネットワーク構成要素１０６にデータ通信ネットワーク（ＤＣＮ）１１０を通じて接続されるＥＭＳ／ＮＭＳ  １１２も含む。ユーザ１１４ａ及び１１６ａは前記ネットワーク１０４に前記ネットワーク構成要素１０２を通じてアクセス可能で、一方、ユーザ１１４ｂ及び１１６ｂは前記ネットワーク１０４を前記ネットワーク構成要素１０６を経由してアクセス可能である。当然のことながら、図１の様々な要素に追加のユーザ、ネットワーク構成要素、ネットワーク及び／またはサブネットが接続可能である。したがって、図１は例示のためだけのものであり、本発明をよく説明するために簡素化されている。更に、当然のことながら、イーサネット（登録商標）やトークンリング等の他のネットワーク及び／またはプロトコールも使用可能である。
【００１０】
更に図２を参照すると、図１のシステム１００のような通信システムにおいて、様々なタイプの情報（データ、音声、ビデオ等）が単一の物理的通信チャネル上で送信可能である。しかし、各タイプ情報は、バッファリング、待ち時間、待ち時間変数等の要件を含む、異なる送信要件を持つ場合がある。これらの異なる要件を満たすために、前記システムは各タイプの情報をその情報がネットワーク入りするのを許可する際に個別に処理してもよい。したがって、多くのソースから受け取った情報が単一の通信チャネルへ入るのを許可するために、様々なタイプの情報の処理要件を満たす回路及び／またはソフトウェアが使用可能である。これを実行する処理は「スケジューリング」と呼ばれ、このスケジューリングを実行するハードウェア及び／またはソフトウェアはスケジューラを呼ばれる。
【００１１】
一般に、トラフィックは複数のカスタマポート１〜Ｍからネットワーク要素（ＮＥ）に送信される。これらのポートからのトラフィックは分類され、キューシステムに入れられるが、ここで前記ポートからの異なるトラフィックは１〜Ｎの異なるキューに入れられてもよい。前記キューシステムとポートは一般に直交空間である。前記カスタマポートからのトラフィックがどのように個別のキューに送られるかを決定するマッピング機能がある（「分類」と呼ばれる）。
【００１２】
一旦トラフィックが複数のＮキューに入れられると、１つ以上のネットワークアップリンに送られる。例えば、多くのキューからのトラフィックは、ＳＴＳ−１２に含まれる１〜Ｐの論理アップリンクの１つである、特定のＳＴＳ−１同期ペイロードエンベロープ（ＳＰＥ）に送られてもよい。このプロセスは、当然のことながら、ＳＯＮＥＴ、ＳＤＨ，イーサネット、及びトークンリング等の多くの異なる技術に適用可能である。前述したように、前記キューイングシステムと論理アップリンクは直交空間であり、あるキューのトラフィックがどのアップリンクに行くかを決定するマッピング機能が存在する。前記スケジューラは、どのように前記アップリンクのバンド幅が競合するクライアント（キュー）間で小さい時間インクリメントに分割するかを決定する。前記スケジューラによって実行される方法は、各キューのトラフィックがどれだけの遅れ、遅れ変数、トラフィックバーストサイズ等を経験するかを決定することもできる。前記方法は、ＰＤＵ（プロトコールデータ単位：  セル、フレーム、またはパケット等）テクニック等の異なる序列テクニックに基づいてもよい。
【００１３】
図３を参照すると、スケジューラ３００の１実施例が示される。前記スケジューラ３００はプロビジョニングランダムアクセスメモリ（ＲＡＭ）３０２、低速サイドモジュール３０４、トークンバンクＲＡＭ３０６、及び高速サイドモジュール３０８を含む。本例では、前記スケジューラはキューイング（メモリシステム等）３１０と交信状態にある。以下に更に詳細に説明するが、前記スケジューラ３００はメモリシステムに命令を送り、前記メモリシステムが特定のキューからＰＤＵをデキューするように設計されている。前記ＰＤＵがそのキューから出されると、選択されたアップリンクの論理チャネルに送られるが、その前に前記メモリシステムからデキューされたデータに対しアップリンクデータのレートマッチングを可能にする小保持域（例えばｆｉｒｓｔ  ｉｎ  ｆｉｒｓｔ  ｏｕｔ  （ＦＩＦＯ）キュー）に入れられる。
【００１４】
当然のことながら、図３の前記スケジューラ３００は、スケジューラの１つの可能な実施例である。例えば、前記スケジューラは、論理合成ツールによって同期化され、且つＶＬＳＩチップで、またはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）として実現されたデジタル回路ＲＴＬ（レジスタトランスファーレベル）記述を使用して実施されてもよい。前記スケジューラは、様々なメモリ（レジスター等）、且つソフトウエア及び／またはハードウェア中で実現される複数の機能を含んでもよい。したがって、次の説明は、説明された特定の構造に限定されるものではない。
【００１５】
前記スケジューラ３００が制御してもよい、デキューされたＰＤＵの例示的なパラメータには、各キューの認定インプットレート（ｃｏｍｍｉｔｔｅｄ  ｉｎｐｕｔ  ｒａｔｅ：  ＣＩＲ）、各キューのアップリンクアベイラビリティに従属するピークインプットレート（ＰＩＲ）、ＶｏＩＰキューの待ち時間（待ち時間変数が重要でなくなるようにスケジューラが待ち時間を低く保とうと試みる等）、キューに対するデータトラフィックのバースト度、及びアップリンクをフルに保つために必要なレート（プロビジョニングごとにフルが可能な場合）が含まれる。前記ＣＩＲは、空でないキューであることを前提として、ネットワークへのトラフィックに許可される最低レートであり、前記ＰＩＲは、空でないキューであることを前提として、ネットワークへのトラフィックに許可される最高レートである。説明のために、余分なバンド幅（例えばＰＩＲとＣＩＲ間の差など）はＰＩＲ＊で示される。前記用語、ＣＩＲ及びＰＩＲへの言及は、当然のことながら、これらのレートを表すＣＩＲ及びＰＩＲトークンについても指すものである場合がある。
【００１６】
上記の情報を使用して、前記スケジューラは、どのキューからトラフィックをデキューするかについて遅延またはリアルタイムの決定を行い、次にこれらのデキューの命令を前記キューイングシステムに送信する。デキューされたトラフィックは、固定または様々なサイズのセル、パケット、またはフレームの形式のＰＤＵデータでもよい。
【００１７】
本実施例では、前記スケジューラ３００は２つの主要部分、前記低速サイドモジュール３０４と高速サイドモジュール３０８とを含む。前記低速サイドモジュール３０４は、ミリ秒のタイムベースを使って実行され、これにより時間依存計算の正確な実行が確実になる。前記高速モジュール３０８は前記低速モジュールより更に早く実行し、デキューの用意ができていて、前記デキューに使用できるバンド幅が使用可能なデータを持つキューを探す。前記２つのモジュールは、前記スケジューラ３００の低速サイドモジュール３０４と高速サイドモジュール３０８間で移動される情報を保持するために使用されるトークンバンクＲＡＭ３０６（デュアルポート  ＲＡＭ等）によって分離される。
【００１８】
例示目的のために、前記スケジューラ３００は、様々なキューからＰＤＵをデキューする権威として、いくぶん動作の面で銀行または手形交換所にたとえる事ができる。実質的に、前記低速サイドモジュール３０４は、正しいレートで銀行の様々なアカウントを満たし、前記高速サイドモジュール３０８は前記アカウントで使用可能な全資金をできるだけ早く引き出す。前記高速サイドモジュール３０８は次に、前記低速サイドモジュール３０４に各アカウントからどれだけ引き出したかを通知し、前記低速サイドモジュール３０４によって前記様々なアカウントへ適切な金額が確実に入れ続けられるようにする。更に前記高速サイドモジュール３０８は、前記アップリンク及びキュー間でのトラフィックシェ−ピング、渋滞コントロール及び公平さの問題の解決を試みる。
【００１９】
スケジューラ全体としてスケジューラ用の２つの競合する要件が存在するために、前記スケジューラ３００が低速サイドと高速サイドモジュールを使用するように設計されることもある。まず第１に、高度の絶対的な時間の正確さと解決度（ｔｉｍｅ  ｒｅｓｏｌｕｔｉｏｎ）で実行するために、前記スケジューラはよく制御された実行レートを持つ。第２に、前記スケジューラはまた、場合によっては様々なサイズのＰＤＵを使って、最高レベルにアップリンクが満たされるように試み、これは前記第１の目的と反目する。
【００２０】
前記低速サイドモジュール３０４はＣＩＲ及びＰＩＲ＊「トークン」を前記高速サイドモジュール３０８に割り当てるために使用される。本実施例では、５１２のキューが存在し、前記低速サイドモジュール３０４は次のプロビジョニングインプット、すなわちＣＩＲ、ＰＩＲ＊、Ｖａｌｉｄ、ＶｏＩＰ、Ｍａｓｔｅｒ、Ｓｌａｖｅ、及びＰａｉｒｅｄ  ＱＩＤを前記プロビジョニングＲＡＭ３０２から各キューベースで獲得する。上記に説明したようにＣＩＲは、キューが空でないことを前提にして、ネットワークへのトラフィックが許可される最低レートで、ＰＩＲ＊はキューが空でないことを前提にして、ネットワークへのトラフィックが許可される最高レートである。「Ｖａｌｉｄ」は、前記スケジューラにキューがトラフィックを運ぶ際にこのキュー用に前記計算を行なうように指示する。「ＶｏＩＰ」は、このキューが遅れ及び遅れ変化に敏感な情報を含むことを前記スケジューラに指示する。「Ｍａｓｔｅｒ」は一対のバイナリキューのリーダーであることを示し（下記に詳しく説明）、一方「Ｓｌａｖｅ」は一対のバイナリキューの後者を示す。「Ｐａｉｒｅｄ  ＱＩＤ」はマスターにのみ有効で、このマスターと対になるＳｌａｖｅ  ＱＩＤへのポインターを含む。前記低速サイドモジュール３０４はまた、各アップリンクベースのプロビジョニングインプットとしてアップリンクデータレート（例えば１２論理アップリンク等）を受け取る（スケジュールで入れられるチャネルの容量等）。前記アップリンクデータレートは前記低速サイドモジュール３０４によって計算されたＣＩＲに影響する。
【００２１】
前記低速サイドモジュール３０４はまた、前記キューイングシステム３１０から次のリアルタイム情報：メモリシステムで待機状態にあるバイト数、トラフィックが待機状態にされたキュー番号、前記メモリシステムからデキューされたバイト数、トラフィックがデキューされたキュー番号を獲得してもよい。
【００２２】
次に図４を参照すると、時間セグメント４００は所定の期間がどのように更に分割されて、図３の前記低速サイドモジュール３０４によって使用されるかが図示されている。例示の目的でミリ秒のタイムベースが使用されるが、当然のことながら、その他のタイムベースが使用されてもよい。前記低速サイドモジュール３０４は正確に知られている単位（１ミリ秒等）に分割され、その定義されたタイムベースに基づいて計算が行なわれる。これにより、ネットワークオペレータにより要求されたスケジューリングパラメータの精密なコントロールが可能になる。例えば、本実施例では、各キューの計算は１秒毎に正確に１０００回実行され、それにより前記スケジューラに１．０００００ミリ秒のタイムベースを提供する。前記低速サイドモジュール３０４の精度は、関連する回路を実行するために使用されるクロックの機能である場合もある（百万分（ＰＰＭ）の２０のクロックソースを使用すると２０ｐｐｍの精度のスケジュールが確保される）。前記計算が各ビットベースに実行される場合は、前記低速サイドモジュール３０４は、１ｋｂｐｓのバンド幅分解能で操作可能である。前記計算が各オクテットベースで実行される場合は、前記低速サイドモジュール３０４は８．０ｋｂｐｓのバンド幅分解能で作動される。
【００２３】
前記時間セグメント４００は、期間Ａ，Ｂ，及びＣに分割される。期間Ａは、Ｎキュー用の各キュー毎の計算に使用される期間を含む。期間Ｂは、Ｐアップリンクの各アップリンク毎の計算に使用される期間を含む。これらの計算については下記で更に詳細に説明される。期間Ｃは「ｄｅａｄ  ｔｉｍｅ」として予約され、前記時間セグメント４００＝１ミリ秒の使用を確保し（例えば、前記「ｄｅａｄ  ｔｉｍｅ」の間、前記低速サイドモジュールはこの１．０００００ミリ秒境界にできるだけ近くなるように配置されるように待機に専念する）、且つ必要に応じて前記期間Ａ及びＢのどちらかによって使用されてもよい。幾つかの実施形態において、前記Ａ及び／またはＢによって期間全部が使用される場合には、当然のことながら、前記期間Ｃが０になる。前記デットタイムが終了した後に、前記低速サイドモジュール３０４が新規のミリ秒境界で次のセットの計算を始めてもよい。
【００２４】
本実施例では、前記スケジューラ３００で行われる計算は、後続する計算インターバル間（例えば１．０ｍｓ）で自己修正されるものである。したがって、長期で累積するスケジューリングエラーは０になる。この結果は、１つのスケジュールインターバルで使用されるバンド幅を次のスケジューリングインターバルで認識されるように構成することにより達成できる。例えば、あるキューが１インターバルにおいて１０００オクテット余分なトラフィックをアップリンクに送った場合、使用可能な１０００オクテットが次のインターバルで差し引かれる。
【００２５】
当然のことながら、多くの異なる計算が実行可能である。例えば、前記時間セグメント４００の期間Ｂの間に、アップリンクの使用可能な総計バンド幅は、前記アップリンクバンド幅から前記アップリンク用に要求されたＣＩＰを引いたものとして計算してもよい。前記スケジューラ３００が各フレームベースで使用されたアップリンクの実際のオーバーヘッドバンド幅を計算するので、各ユーザーは要求したアップリンク量を受け取る。これは、前記アップリンクがある種のカプセル化技術（例えば、ＰＰＰオーバーＳＯＮＥＴ、イーサネットオーバーＳＯＮＥＴ）の使用を要求する場合に、使用される必要なカプセル化バンド幅の点で、各ユーザを他から分離するという長所を提供する。したがって、１ユーザがアップリンクバンド幅の公平な取り分以上を使うことはない。
【００２６】
次に図５を参照すると、方法５００は、各ＱＩＤ用の所定の期間（図４の期間Ａ等）に所定のタイムベース（図４の１ミリ秒タイムベース等）を使用して実行されてもよく、これにより時間依存計算が正しく実行されることが確実となる。前記方法５００は、ステップ５０２で前記ＱＩＤをＮに進めて開始する。ステップ５０４では、Ｎが最高ＱＩＤより大きいかどうかの判定が行なわれる。もし、Ｎが大きい場合、現在のセグメントで処理されるキューがなくなり、前記方法はステップ５０５まで進み、そこでＳＰＥ計算を実行する（セグメント４００の期間Ｂに対応する場合がある）。ステップ５０６では、前記方法５００は待ち状態（例えば、セグメント４００の期間Ｃ）に入り、その後、ステップ５０７で前記ＱＩＤをゼロに設定してステップ５０４に戻る。もしＮが前記ＱＩＤより大きくない場合（このブランチは前記セグメント４００の期間Ａに対応する場合がある）、前記方法はステップ５０８まで進み、そこで現在のキュー（ＱＩＤ  Ｎ）用にプロビジョニング情報とトークンバンク情報を得る。獲得されるプロビジョニング情報には、ＣＩＲ、ＰＩＲ＊、Ｖａｌｉｄ、ＶｏＩＰ、Ｍａｓｔｅｒ、Ｓｌａｖｅ、Ｐａｉｒｅｄ  ＱＩＤ、及びアップリンクデータリンクが含まれる。得られたトークンバンク情報には、最後の所定時間インターバル（ミリ秒等）の間に前記メモリシステムからデキューされたバイト数、また前回のＰＩＲ及びＣＩＲが含まれてもよい。
【００２７】
ステップ５１０では、獲得された情報が有効なＱＩＤを含むかどうかの判定が行われる。前述したように、有効なＱＩＤとは、キューがトラフィックを運ぶ際にこのキュー用に前記スケジューラが計算を実行することを意味する。もし、そのＱＩＤが有効でない場合は、前記方法５００はステップ５０２に戻り、前記ＱＩＤは前進する。もし、前記ＱＩＤが有効である場合は、前記方法はステップ５１２に進み、例えば、前述のＭａｓｔｅｒ、Ｓｌａｖｅ，  及び／またはＰａｉｒｅｄ  ＱＩＤ等のプロビショニング情報を使用して、そのキューがｍａｓｔｅｒ／ｓｌａｖｅであるかが判定される。もし、前記キューがマスターであると判定された場合、前記方法はステップ５１４に進み、獲得されたＣＩＲ及びアップリンクデータレートプロビショニング情報等を使用して、マスタ用のＣＩＲ計算が行われる。獲得されたＣＩＲプロビショニング情報は、割当可能なＣＩＲトークン数を規制するために使用される上限を提供する。
【００２８】
更に、未使用のＣＩＲバンド幅は、ステップ５１４でそのスレーブに受け渡される。この未使用のバンド幅の割当は、１対のキュー間に存在するマスタ／スレーブ関係のために起こり、未使用のアウトプットバンド幅があるキュー（双対のキュー等）から関連のある別のキューに供与されることを可能にする。そのような双対のキューは、キューがペアになることにより単一のプロビジョニング命令を使って２つのサービスの同時プロビジョニングを平行に行うことが可能になる。そのような同時プロビショニングは、ネットワークオペレータが、２つのサービスに対して、カスタマとの単一のサービスレベルアグリーメント（ＳＬＡ）を交渉、供給及び管理することを可能にする。例えば、双対のキューは、ＶｏＩＰとデータ接続を一緒に交渉して、前記データ接続が自動的に未使用のＶｏＩＰバンド幅をリアルタイムで受け取ることを可能にするために使用される。そのような場合は、前記のＶｏＩＰトラフィックは特定のＣＩＲと一緒にプロビションされ、前記データトラフィックは特定のＰＩＲと一緒にプロビションされる。したがって、前記ＶｏＩＰキューで未使用のＣＩＲは、ＣＩＲとして前記データキューに受け渡される。
【００２９】
更に図６ａを参照すると、例示的方法６００は前記ＣＩＲの計算の１プロセスと、該当する場合は未使用のＣＩＲのスレーブキューへの割当が図示される。ステップ６０２では現在のＱＩＤのＣＩＲが次のように計算される。
【００３０】
【数１】
2007504787.tif 000003
【００３１】
ここで、「ｔｂ，ｎ」は現在の期間での現在のＱＩＤのトークンバンクエントリを示し、「ｐｒｏｖ」はプロビション済みのＣＩＲを示し、「ｕｓｅｄ，ｎ−１」は前の期間で使用されたＣＩＲトークンを示す。このＣＩＲ計算がマスタキュー用である場合は、前記方法６００はステップ６０４に進み、スレーブに割り当てる未使用のＣＩＲがあるかどうかが下記を使って計算される。
【００３２】
【数２】
2007504787.tif 000004
【００３３】
ステップ６０６で前記方法６００はＱＩＤ  Ｎ用に計算されるＣＩＲトークンをＱＩＤ  Ｎに許可される最高トークンまでに制限する。
【００３４】
【数３】
2007504787.tif 000005
【００３５】
もう一度、特に図５を参照すると、ステップ５１６でスレーブ情報が獲得され（前記Ｐａｉｒｅｄ  ＱＩＤ等を使用して）、ＣＩＲ及びＰＩＲ＊計算が前記スレーブのために実行されてもよい。前記ＣＩＲ計算は前述したように実行され、典型的ＰＩＲ＊計算は図６ｂで更に詳細に説明するように実行される。
【００３６】
更に図６ｂを参照すると、例示的方法６１０はＰＩＲ＊の計算の１プロセスを示す。ステップ６１２では、前記方法６１０はＣＩＲトークンの必要数を次のように計算する。
【００３７】
【数４】
2007504787.tif 000006
【００３８】
更に前記方法６１０は、下記を使って、ＣＩＲトークンの必要数をプロビジョンされたＣＩＲトークン数までに制限する。
【００３９】
【数５】
2007504787.tif 000007
【００４０】
ステップ６１４では、アップリンク用に必要なＣＩＲトークン数はアップリンクでのすべての接続用に次のように計算される。
【００４１】
【数６】
2007504787.tif 000008
【００４２】
ステップ６１６では、ＰＩＲトークンの全許可数は次のように計算される。
【００４３】
【数７】
2007504787.tif 000009
【００４４】
ステップ６１８では、前記方法６１０は次のようにＰＩＲトークンの好ましい数を計算する。
【００４５】
【数８】
2007504787.tif 000010
【００４６】
更に、前記方法６１０は、下記を使ってＰＩＲの好ましい数をプロビションされたＰＩＲトークン数にまで制限する。
【００４７】
【数９】
2007504787.tif 000011
【００４８】
ステップ６２０では、前記アップリンク用に好ましいＰＩＲトークン量を次のように計算する。
【００４９】
【数１０】
2007504787.tif 000012
【００５０】
ステップ６２２では、ステップ６１６と６２０からの計算を使用して、追加されるＰＩＲ＊トークンが次のように計算される。
【００５１】
【数１１】
2007504787.tif 000013
【００５２】
ステップ６２４では、Ｎで索引されるトークンバンク用のＰＩＲが次のように計算される。
【００５３】
【数１２】
2007504787.tif 000014
【００５４】
ステップ６２６では、前記方法６１０は、下記を使用して、前記トークンバンク内でＱＩＤ  Ｎに与えられるＰＩＲ＊トークン数を最高ＰＩＲ＊トークン数までに制限する。
【００５５】
【数１３】
2007504787.tif 000015
【００５６】
更に特に図５を参照すると、ステップ５１８で、前記で計算されたＣＩＲｔｂ，ｎ  及びＰＩＲ＊ｔｂ，ｎ値（トークン等）は、ＱＩＤ  Ｎ及びスレーブＱＩＤ用に前記トークンバンクに書き込まれる。
【００５７】
ステップ５１２に戻り、もしＱＩＤ  Ｎがマスタ／スレーブでない場合は、前記方法は、ステップ５２０と５２２に進み、そこでそれぞれＣＩＲ及びＰＩＲ＊計算をＱＩＤ  Ｎ用に行う。前記計算は、図６ａ及び図６ｂに関して前述したように計算される。ステップ５２４では、前記の計算されたＣＩＲ及びＰＩＲ＊値はＱＩＤ  Ｎ用に前記トークンバンクに書き込まれ、前記方法は、ステップ５０２に戻る。
【００５８】
次に図７を参照すると、図３の前記高速サイドモジュール３０８の更に詳細な例が図示される。前記高速サイドモジュールが使用され、前記低速サイドモジュール３０４から前記トークンバンクＲＡＭ３０６経由で受領したＣＩＲおよびＰＩＲ＊「トークン」を基に前記キューの情報のデキューがコントロールされる。本実施例では、前記高速サイドモジュールは、ＲＡＭアービター７００、デキューアキュームレータ７０２、指定決定モジュール７０４、ランダムアドレスジェネレータ７０６、指定テーブルローダ７０８、及び指定テーブルＲＡＭ７１０を含む。前記ＲＡＭアービター７００は、前記トークンバンクＲＡＭ３０６と前記高速サイドモジュール３０８の対話を補助する。デキューアキュムレータ７０２はＲＡＭアービター７００を使用して、前記トークンバンクＲＡＭ３０６中に前記ミリ秒ウィンドウ上でデキューされたバイトの現在合計数を保存する。指定テーブルローダ７０８等の構成要素は他の構成要素（指定決定モジュール７０４等）の要求を通じて、前記要求に「聞き入る」ことにより前記トークンバンクからの情報を獲得してもよい。前述したように、この情報は、その計算の間に前記低速サイドモジュール３０４によって使用されてもよい。
【００５９】
前記高速サイドモジュール３０８は、前記メモリシステムへのデキューの命令の指定をなるべく公正に近づけるためのプロセスを使用する。これを行うために、前記高速サイドモジュール３０８は、指定テーブル（前記指定テーブルＲＡＭ７１０に保存された）を使用するが、これには全プロビジョン済みのキューＩＤが含まれ、且つ実際にプロビジョン済みのＰＩＲに比例する多くの指定テーブルエントリを持つ。その結果、キュー間で異なる重みが予期されるバンド幅に基づいて作成される。
【００６０】
前記ランダムアドレスジェネレータ７０６で提供される無作為配分機能が前記の指定テーブルＲＡＭ７１０の読み込みに使用されてもよい。これにより、前述したミリ秒ウインドウ上のキュー指定の配分を可能にし、前記アップリンクにトラフィックシェーピイング効果を生み出す。前記無作為配分機能はまた前記指定テーブルを複数回読み込んで前記キュー及び／またはアップリンクのバンド幅より高いが比例する指定レートを提供するようにしてもよい。これにより、後ろから圧迫される状態で起こる前記メモリシステムによる指定の損失が補われる。
【００６１】
更に図８を参照すると、例示的方法８００は、前記指定テーブルＲＡＭ７１０に前記指定テーブルをロードするために前記の図７の指定テーブルローダ７０８によって使用される１プロセスを示す。前記指定テーブルのローディングではキューＩＤを直線上にタイムベースウインドウの開始部分に保存してもよい。これにより、最低の施行要件で且つデータレートに影響を与えずに前記指定テーブルのライフ再プロビショニングを補助する。アップリンクの指定経路またはキュー間での干渉は少し、または皆無で複数アップリンクに対する任意の数のキューがサポートされることがわかる。
【００６２】
ステップ８０２では、前記指定テーブルのインデックス（ｎｔａｂｌｅ＿ｉｎｄｅｘ）及びＱＩＤはどちらも０に設定される。ステップ８０４では、前記方法がタイムベースウインドウ（例えば、図４の１ミリ秒セグメント４００の開始部分等）の開始部分にあるかどうかの判定が行われる。そうでない場合、前記方法はステップ８０２に戻る。そうである場合、前記方法はステップ８０６に進み、そこでＱＩＤ用の指定テーブルエントリの数を得る。ステップ８０８で、ＱＩＤ及び指定テーブルエントリのアップリンクチャネル数が指定テーブルに保存され、ステップ８１０で前記ＱＩＤがインクリメントされる。
【００６３】
ステップ８１２では、最後のキューが処理されたかどうかの判定が行われる。そうでない場合は、前記方法８００はステップ８０６に戻る。処理された場合は、前記方法は、ステップ８１４に進み、ｎｔａｂｌｅ＿ｉｎｄｅｘインデックスが前記指定テーブルエントリの最後であるかどうかを判定する。その場合は、前記方法８００はステップ８０２に戻る。そうでない場合は、前記方法は、ステップ８１６まで進み、ステップ８０２に戻る前に前記指定テーブルの残りのエントリを消去する。図８には示されていないが、前記指定テーブルの全エントリはリセットの際に無効とマークされる。
【００６４】
前記スケジューラ３００の高速サイドモジュール３０８は、ミリ秒ウインドウを参照として使用して実行する。更に、また認識制御機構として、タイムベースウインドウをサブウインドウに分割してトラフィックを評価してもよく、それによりトークンバンクのファンドを使い切った接続が、前記ウインドウで早期に指定するのをブロックすることが可能である。これにより他のキューのデキュー指定に影響を与える可能性がある不必要な指定が前記メモリシステムに到達するのを防ぐ。これは、最小対最大のＰＤＩサイズの場合に有用である。更にＳＰＥごとの強制機能を追加し、１ミリ秒ウインドウの間で遅くなった接続が後続のウインドウで追いつくことが可能になる。更に、サブウインドウ内で使用される更に早い反応の「ラグ」機能を使って接続の遅れを防ぐことができる。前記機能は、キューが前のサブウインドウのバンド幅の配分で遅れていないか、また現在強制されていないかを評価してもよい。前記キューがこれらの要件を満たした場合、「ラグ状態」キューとして選択される。前記スケジューラ３００は、前記高速サイドモジュール３０８が他の指定をまったくしていない場合は、このＱＩＤを指定する。これらの特徴は、前記スケジューラ３００のデキュー指定の生成をもっと効率よくさせ、最後の手段として強制ロジックを設定することによりバースト度を減少させ、前記スケジューラがバーストサイズプロビジョニングを必要とせずに任意のフレームサイズのトラフィックをサポートすることを可能にする。更に複数アップリンクへの任意数のキューをアップリンク指定経路またはキュー間での干渉なしにサポートすることが可能である。
【００６５】
次に図９ａと９ｂを参照すると、例示的な方法９００によって前記図７の高速サイドモジュールでのキュー指定で使用可能な１プロセスが図示される。次の例では、各サブウインドウ（ｓｕｂ＿ｗｉｎ＿ｂｗ）は前記トークンバンク（ＴＢａｎｋ  ＣＩＲ）の全ＣＩＲの一部分である。この一部分は現在のサブウインドウに依存する。更に各タイムアウトカウンタ用の最高限度は、アクティブなアップリンク（ＳＰＥ等）の数に応じて異なる。
【００６６】
ステップ９０２では、エントリ（ＮＴＥｎｔｒｙ等）が無作為機能（図７のランダムアドレスジェネレータ７０６等）を使った指定テーブルから読み込まれる。ステップ９０４では、ＮＴＥｎｔｒｙが有効であるかどうか判定が行われる。ＮＴＥｎｔｒｙが有効でない場合（すなわちＱＩＤでない）、前記方法９００はステップ９０６に進み、そこで前記キューがＳＰＥ毎に強制されているか（例えば、ＳＰＥを選択するためにラウンドロビンを使用）どうかの判定を行う。前記キューがＳＰＥ毎に強制されていない場合は、ステップ９０８でラグ機能が選択されたＳＰＥで使用可能にされているどうかの判定が行われる。そうでない場合は、前記方法は、ステップ９０２に戻る。そうである場合は、前記方法は、ステップ９１０に進み、そこでｃｕｒｒｅｎｔ  ＿｛ＱＩＤ，  ＳＰＥ｝はｌａｇ＿｛ＱＩＤ，  ＳＰＥ｝と等しくなるように設定される。ステップ９０６に戻るが、ｆｏｒｃｅ＿ｒｏｕｎｄ＿ｒｏｂｉｎ  ＳＰＥが使用可能になっている場合、前記方法９００はステップ９１２に移動し、そこでｃｕｒｒｅｎｔ＿｛ＱＩＤ，  ＳＰＥ｝はｆｏｒｃｅ＿｛ＱＩＤ，  ＳＰＥ｝に等しくなるように設定される。ステップ９１０と９１２の両方はステップ９１８まで進み、これについては下記に詳しく説明する。
【００６７】
ステップ９０４に戻り、ＮＴＥｎｔｒｙが有効の場合、前記指定テーブルから受け取ったＱＩＤとＳＰＥはステップ９１３で保存される。ステップ９１４では、ＳＰＥが強制されているかどうかの判定がされる。強制されている場合、前記方法９００はステップ９１２に進み、そこでｃｕｒｒｅｎｔ＿｛ＱＩＤ，ＳＰＥ｝は前述したようにｆｏｒｃｅ＿｛ＱＩＤ，ＳＰＥ｝と同じに設定される。そうでない場合は、前記方法はステップ９１６に進み、ｃｕｒｒｅｎｔ＿｛ＱＩＤ，ＳＰＥ｝はｎｏｒｍａｌ＿｛ＱＩＤ，ＳＰＥ｝と同じに設定される。任意のステップ９１０、９１２、及び９１６から、前記方法はステップ９１８に進む。
【００６８】
ステップ９１８では、ＰＩＲ、ｄｑ＿ｃｏｕｎｔ、及び強制インジケータ（例えば、現在のＱＩＤが強制される必要があることを示す）が現在のＱＩＤ用に前記トークンバンクから得られる。ステップ９２０では、現在のＱＩＤ  ＰＩＲが許可される最小デキュー値より大きいかどうかが判定される。そうでない場合は、前記方法９００はステップ９０２に戻る。そうである場合は、ステップ９２２で現在のサブウインドウでデキューされるＣＩＲの量（ＣＩＲトークンの数等）について計算される。
【００６９】
ステップ９２４では、現在のＳＰＥが強制されているかどうかの判定がされる。強制されている場合、前記方法は、ステップ９２６に進み、もしｆｏｒｃｅ＿ｓｕｂ＿ｗｉｎｄｏｗ＿ｂｗ（例えば、現在のサブウインドウで強制されることになるＣＩＲトークンの最低量を示す）がｄｑ＿ｃｏｕｎｔより小さいかまたは等しく、あるいはタイマーが切れている場合、前記強制機能が使用不可になる。ステップ９２８では、ｆｏｒｃｅ＿ｓｕｂ＿ｗｉｎｄｏｗ＿ｂｗがｄｑ＿ｃｏｕｎｔよりも大きいかどうかの判定がされる。そうでない場合は、前記方法９００はステップ９０２に戻る。そうである場合、前記方法９００はステップ９３０に進み、そこで指定はｃｕｒｒｅｎｔ＿｛ＱＩＤ，  ＳＰＥ｝用に前記メモリシステムに送られる。
【００７０】
ステップ９２４に戻り、現在のＳＰＥが強制されていない場合、前記方法９００はステップ９３２に移動する。ステップ９３２では、前記強制インジケータが設定されており、ｆｏｒｃｅ＿ｓｕｂ＿ｗｉｎｄｏｗ＿ｂｗがｄｑ＿ｃｏｕｎｔより大きい場合、前記強制機能がＱＩＤ用に使用可能になり、タイムアウトカウントが開始される。そうでなければ、もし前記ラグ機能が使用不可で且つＱＩＤが遅れている場合、前記ラグ機能がＱＩＤ用に使用可能にされ、前記タイムアウトカウントが開始される。ステップ９３４では、もし前記ラグ機能が使用可能にされており、且つＱＩＤが遅れを取り戻したかまたはタイムアウトカウンタが時間切れになった場合、前記ラグ機能は使用不可にされ、タイムアウトカウントは停止されてクリアされる。ステップ９３６では、前記の選択されたＳＰＥからの後圧があるかどうかが判定される。後圧がない場合は、前記方法はステップ９３０に進み、指定はｃｕｒｒｅｎｔ＿｛ＱＩＤ，ＳＰＥ｝用に前記メモリシステムに送られる。もし、後圧がある場合、前記方法はステップ９３８に移動する。ステップ９３８では、もしＱＩＤが現在のサブウインドウ用のそのＣＩＲ分を満たしていない場合、前記方法はステップ９３０まで進み、そこで指定はｃｕｒｒｅｎｔ＿｛ＱＩＤ，  ＳＰＥ｝用に前記メモリシステムに送られる。そうでなければ、もしそれが満たしているが（あるいはＣＩＲがない）余分なバンド幅を持っている場合、ｄｑ＿ｃｏｕｎｔがＳＰＥのＦＩＦＯの略フルレベル以下であるかどうかの判定がされる。これは、ＦＩＦＯを埋めた可能性を持つ１つ以上のキューを識別するのを助け、埋めなかったキューからデキューを続行できるようにする。そうでない場合は、前記方法はステップ９０２に戻る。そうである場合、前記方法はステップ９３０に戻る。
【００７１】
したがって、上述したように、前記スケジューラ３００は、各キューが少なくともプロビション済みのＣＩＲバンド幅を受け取ることを確保し（前記キューがデキューするＰＤＵを含むことを前提に）、また各接続が確実にプロビジョン済みのＰＩＲバンド幅以上を受け取らないようにする（前記キューがデキューされるＰＤＵを含む場合）。実施例によっては、前記スケジューラは前記アップリンクのバンド幅が完全に満たされることを確保する（前記プロビション済みパラメータ内で前記アップリンクを一杯にするのに十分なトラフィックが提供されている場合）。さらに別の実施例では、前記スケジューラが余分なバンド幅が常に比率ベースで均一にシェアされることを確保する。
【００７２】
上記の記載で１つ以上の実施形態が示され説明されたが、本開示の要旨及び範囲から逸脱せずに形及び詳細をさまざまに変更することが可能であることが当業者には理解される。例えば、前記に説明された方法のさまざまなステップは異なる順序で実行されてもよく、あるいは順次に、組み合わされ、更に分割され、代替のステップと置き換えられ、またはまったく削除されて実行さてもよい。更に、前記方法または本明細書のどこかで示されたさまざまな機能が追加及び／または代替の機能を提供するために組み合わされてもてもよい。更にさまざまな変更が前記方法及び／またはスケジューラに施されて、さまざまなネットワーク及び／またはプロトコールに準拠するようにしてもよい。したがって、請求項は広義に、本明細書に一致するように解釈されるべきである。
【図面の簡単な説明】
【００７３】
【図１ａ】図１ａは、スケジューリング方法の典型的なフローチャートである。
【図１ｂ】図１ｂは、スケジューラが使用される典型的な通信システムの１実施例を示す。
【図２】図２は図１のシステムにデータが入ることが許可される過程の典型的なデータフローを示す図である。
【図３】図３は、図２での１つ若しくはそれ以上のアップリンクへのデータフローの制御に使用される低速サイド及び高速サイドのモジュールを持つスケジューラの１実施例である。
【図４】図４は、所定の時間セグメントと、この時間セグメントの間に図３のスケジューラの低速サイドモジュールによって実行される様々なタスクを示す。
【図５】図５は、図３の低速サイドモジュールによってキュー毎に実行される典型的な方法のフローチャートである。
【図６ａ】図６ａは、図５の方法の実行の際に１キューに確約するインプットレートを計算するために使用する典型的な方法のフローチャートである。
【図６ｂ】図６ｂは、図５の方法の実行の間に１キューに対しピークインプットレートを計算するために使用する典型的な方法のフローチャートである。
【図７】図７は、図３のスケジューラの高速サイドモジュールの更に詳細な実施例の図である。
【図８】図８は、図７の高速サイドモジュールに関連する指定テーブルをロードするための典型的な方法のフローチャートである。
【図９ａ】図９ａ及び９ｂは、図８の前記指定テーブルを使用して図７の高速サイドモジュール内で実行される指定プロセスの典型的な方法のフローチャートである。
【図９ｂ】図９ａ及び９ｂは、図８の前記指定テーブルを使用して図７の高速サイドモジュール内で実行される指定プロセスの典型的な方法のフローチャートである。
【図１ａ】
2007504787.tif 000016
【図１ｂ】
2007504787.tif 000017
【図２】
2007504787.tif 000018
【図３】
2007504787.tif 000019
【図４】
2007504787.tif 000020
【図５】
2007504787.tif 000021
【図６ａ】
2007504787.tif 000022
【図６ｂ】
2007504787.tif 000023
【図７】
2007504787.tif 000024
【図８】
2007504787.tif 000025
【図９ａ】
2007504787.tif 000026
【図９ｂ】
2007504787.tif 000027
【国際調査報告】
2007504787.tif 000028