(57)【要約】データキューサービスセンタとその運用方法が、サービスクラスが異なるデータパケットの送信経路上におけるルーティング用に提供される。キューは、各異なるサービスクラス（１２、１４、１６、１８、２０）が各サービスクラス用のクラスベース重み付け均等化キューイングの重み付け係数で送信されるように設定される。各サービスクラスに対する所望のキュー常駐時間は、要求されたサービスの品質レベルに基づき予め割当てられる。各サービスクラスに対するパケットの実際常駐時間が決定（４４）され、また、各サービスクラスに対する予め割当てられた常駐時間と比較される。そのサービスクラスに対するＣＢＷＦＱによる重み付けは、実際常駐時間と予め割当てられた常駐時間との比較に基づき、動的に調整される（５４）。
2004514324.tif 000002
【特許請求の範囲】
【請求項１】
伝送路を介して異なるサービスクラスにおけるデータパケットのルーティングを行うためのデータキューサービスセンタにおいて、
送信される各異なるサービスクラスにおけるデータパケットの個別キュー（１２−２０）を確立する段階と、
各異なるサービスクラスにおける各個別キューに、クラスベース重み付け均等化キューイングの重み付け係数を適用し、各サービスクラスにおけるデータパケットの各個別キューの予め割当てられたキュー常駐時間を生成する段階（４６）と、
各サービスクラスにおけるデータパケットの実際キュー常駐時間を決定する段階（４４）と、
各サービスクラスにおけるデータパケットの前記実際キュー常駐時間と、各サービスクラスにおけるデータパケットの前記予め割当てられたキュー常駐時間とを比較する段階（５２）と、
特定のサービスクラスにおけるデータパケットの前記実際キュー常駐時間が、前記予め割当てられたキュー常駐時間を超過する場合、そのサービスクラスに対するクラスベース重み付け均等化キューイングの重み付け係数を動的に増加する段階（５４）と、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、
前記実際キュー常駐時間は、サービスクラス用データパケットのキュー深さに、そのサービスクラスにおけるデータパケットに対する予想常駐時間を掛けて求めることによって算出することを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、更に、
前記データキューサービスセンタの負荷係数を算出して、計算負荷係数を生成する段階と、
前記計算負荷係数を、予め設定されたデータキューサービスセンタ負荷係数限界値と比較する段階と、
前記計算負荷係数が前記予め設定されたデータキューサービスセンタ負荷係数限界値を超過した場合、前記データキューサービスセンタへの新たなパケットのアドミッション制御を開始する段階と、
を含むことを特徴とする方法。
【請求項４】
伝送路を介して異なるサービスクラスにおけるデータパケットのルーティングを行うためのデータキューサービスセンタであって、
送信される各異なるサービスクラスにおけるデータパケットの個別キュー（１２−２０）と、
各サービスクラスにおけるデータパケットの所望のキュー常駐時間を予め割当てることを、クラスベース重み付け均等化キューイングの重み付け係数を各サービスクラスにおけるデータパケットの前記キューに適用することによって行うためのプロセッサ（２８）であって、オンデマンドで前記クラスベース重み付け均等化キューイングの重み付け係数を動的に調整するための前記プロセッサ（２８）と、
各サービスクラスにおけるデータパケットの実際キュー常駐時間を決定する（４４）ための手段と、
各サービスクラスにおけるデータパケットの前記実際キュー常駐時間と、各サービスクラスにおけるデータパケットの前記予め割当てられた所望のキュー常駐時間とを比較する（４８）ための手段と、
特定のサービスクラスにおけるデータパケットの前記実際キュー常駐時間が、そのサービスクラスにおけるデータパケットの前記予め割当てられた所望のキュー常駐時間を超過する場合、そのサービスクラスに対するクラスベース重み付け均等化キューイングの重み付け係数を動的に増加する（５４）ための、前記プロセッサを含む、手段と、
から構成されることを特徴とするデータキューサービスセンタ。
【請求項５】
請求項４に記載のデータキューサービスセンタであって、
各サービスクラスにおけるデータパケットの前記実際キュー常駐時間は、サービスクラスに対する前記個別キューのデータパケット深さに、そのサービスクラスにおけるデータパケットに対する前記実際キュー常駐時間を掛けて求めることによって算出することを特徴とするデータキューサービスセンタ。
【発明の詳細な説明】
【０００１】
発明の分野
本発明は、クラスベース重み付け均等化キューイング（ＣＢＷＦＱ）に関し、特に、ネットワークを介して、高い優先順位クラスのトラフィックにおけるスループットを維持するためにＣＢＷＦＱ係数を適切に変更することに関する。
【０００２】
発明の背景
クラスベースのネットワークサービスは、通信ネットワークシステムにおいて、新たに出現しつつある傾向である。クラスベースのサービスでは、音声、映像、データトラフィック等、様々な種類のトラフィックを効率的に処理することが可能である。クラスは、ピークデータ要求に加えて、それが遅延、ジッタ、又は損失に耐え得るか否かに基づき、また、バースト性であるか否かに基づき区別される。
【０００３】
ネットワークのトラフィッククラスの性質を利用すると、法外なコストで過度にネットワーク資源を備えること無く、システムの性能要求を満たし得る。往々にして、バックグラウンド処理や他のデータサービスの待ち時間は、重要ではなく、また、優先順位が高いトラフィックスループットレートや待ち時間を維持するために、犠牲にすることができる。
【０００４】
クラスベース重み付け均等化キューイングには、異なるサービスクラスの重み付けのためのシステムを確立し、そのクラスに関連するデータパケットの送信やサービスにおいて、サービスクラスの内どれに優先権が与えられているか設定することが含まれる。
【０００５】
与えられたキューサービスセンタ（ＱＳＣ）から送信を要求する各データのパケットは、そのパケットが属するサービスクラスへのマッピングを行うヘッダを有する（すなわち、ＤｉｆｆＳｅｒｖｅ）。例えば、サービスクラスには、音声、映像、データ及び電子メール等を含むものがある。送信の優先権の観点では、認知し得る遅延が最小限である理解可能な音声を再現できるように、受信機は近接して音声パケットを受信する必要があるため、音声パケットの優先権が最も高い可能性がある。また、受信機が、ジッタの多いあるいは不明瞭な画像ではなく、比較的滑らかな映像イメージを受信するように、映像も高い優先順位を持つ種類のパケットである。音声が映像を伴う場合、対応する音声パケットは、映像と音声との間の同期を取るために同じ優先権を享受し得る。
【０００６】
反対に、電子メールはリアルタイムに受信する必要がほとんどないため、電子メールの優先権は、比較的低い。
クラスベース重み付け均等化キューイングシステムにおいて、ネットワークオペレータが、与えられたサービスクラスに積極的に割当てる送信の優先権と総帯域幅の割合に基づき、各サービスクラスに重み付けがなされる。従って、音声は、比較的高い重み付けになり、また、電子メールは、比較的低い重み付けになる。データ送信セッションの途中、特に、アドミッション制御やフロー制御が存在しない又は応答が遅いシステムにおいて、１つ以上のサービスクラスでオーバーロードが発生することがある。現行のシステムでは、通常、システム管理者が優先権を調整して、データフローを均等化したり、又は、適切に優先順位付けするまで、このオーバーロードによって、優先順位が高いトラフィックが遅延を受けたり又は中断されたりする。最終的には、輻輳を解決して高い優先権のサービスクラスが効率的に送信されるように、フロー制御を用いて、あるサービスクラスのキューサービスセンタへの進入を低減する。
【０００７】
発明の概要
データキューサービスセンタとその運用方法が、サービスクラスが異なるデータパケットの送信経路上におけるルーティングに対して提供される。異なるサービスクラスが処理され又は送信されるようにキューが設定され、また、各サービスクラスに対する所望のキュー常駐時間は、クラスベース重み付け均等化キューイングによる重み付けを各サービスクラスのキューに適用することによって予め割当てられる。各サービスクラスに対するパケットの実際の常駐時間が決定され、また、各サービスクラスに対する予め割当てられた常駐時間と比較される。特定のサービスクラスの測定常駐時間が、予め割当てられた常駐時間を超過した場合、そのサービスクラスに対するＣＢＷＦＱによる重み付けは、動的に大きくなる。
【０００８】
好適な実施形態の説明
図１は、ルータ、パケット処理機能、又は他のパケットデータ処理用装置等、本発明による特徴を組み込んだ代表的なデータキューサービスセンタ（ＱＳＣ）のブロック図を示す。ルータは、全体的に１０で示す。ルータ１０内にあるものは、一連のキュー、すなわちバッファ１２、１４、１６、１８、２０である。バッファ１２−２０は、各々のバッファとして割当てられ、与えられたサービスクラス用の一連のデータパケットに対するキューイング及び処理を行う。例えば、バッファ１２には全ての音声パケットを、バッファ１４には全映像パケットを、バッファ１６には他のデータパケットを、そして、バッファ１８には全ての電子メールパケットを割当てることができる。
【０００９】
通常、各個別のパケットは、パケットのヘッダ内にある文字によって識別可能であり、また、例えば、送信者情報、宛先アドレス、送信元アドレス、ポート番号、シーケンス番号、そこに含まれる文字数及び他の分類又は処理情報も含み得る。
【００１０】
各キューすなわちバッファ１２−２０は、中央処理装置（ＣＰＵ）２２に接続され、ＣＰＵ２２は、各所定のシーケンスでバッファすなわちキューからパケットを受信する。プロセッサは、パケットに対する適切なルーティングを提示されたように決定し、また、一連のパケットを後続の処理又はパケット処理機能、あるいは同軸ケーブルや銅線又は光ファイバケーブル等の送信媒体へ送信する。当然、処理媒体の特定の要求事項に合わせて、プロセッサの出力を送信又は変換するために、然るべきバッファリング及び信号変換（図示せず）が必要である。
【００１１】
また、交換パターン生成器２６もＣＰＵ２２に接続され、各バッファ１２−２０からＣＰＵ２２がどのシーケンスでパケットを受信するか決定する。通常、この交換パターンは、各サービスクラスに対する全体的なシステム容量、ルーティングされるデータの種類、及び個々のサービスクラスの優先ニーズに基づき予め設定される。
【００１２】
上述したクラスベース重み付け均等化キューイングには、異なるサービスクラスの重み付けを行い、そのクラスに関連するデータパケットの処理又は送信において、サービスクラスの内どれに注目するのか設定するためのシステムを確立することが含まれる。
【００１３】
既設のクラスベース重み付け均等化キューイングシステムにおいて、重み付けは、送信の優先権に基づき、各サービスクラスに割当てられる。従って、音声は、比較的高い重み付けを有し、また、電子メールは、比較的低い重み付けを有する。例えば、あるクラスベース重み付け均等化キューイングシステムでは、以下のように、様々なサービスクラスに対する重み付けを設定できる。
【００１４】
ＣＢＷＦＱ＝０．５ＣｏＳ１＋０．２ＣｏＳ２＋０．１ＣｏＳ３＋０．２ＣｏＳ４
ここで、ＣｏＳｎの項は、異なるサービスクラス又はデータタイプを表し、また、数値プレフィックスは、各サービスクラスに与えられた利用可能な総サービスサイクルの相対的な重み付け又は割合を設定する。従って、０．５の比較的大きな重み付けを有するＣｏＳ１は、受信側で理解可能な音声を提供するために、ほぼリアルタイムのスピードで処理して送信すべき音声データを表すことができる。同様に、０．１の比較的小きな重み付けを有するＣｏＳ３は、通常、時間の制約が厳しくない電子メールパケットを表すことができる。これらは、可能な重み付け方式の代表的なものであるが、システム特性もまた考慮される。例えば、ネットワークの特定の性質のために、音声送信の期待量が少ない場合、あるいは、何らかの理由で、ある他の種類のデータが音声より高い優先権を有している場合、音声ＣｏＳには、比較的低い優先権が割当てられる。
【００１５】
このタイプのアルゴリズムを用いて、交換パターン生成器２６の交換パターンを決定し得る。通常のシステムでは、このアルゴリズムは、固定されており、オペレータの介入によってのみ変更が可能である。
【００１６】
データ送信セッションの過程において、１つ以上のサービスクラスでオーバーロードが起こり得る。通常、現行のシステムでは、システム管理者が優先権を調整して、データフローを均等化したり、又は、適切に優先順位付けするまで、このオーバーロードによって、優先順位が高いトラフィックが遅延を受けたり又は中断されたりする。最終的には、高い優先権のサービスクラスを効率的に送信できるように、フロー制御を用いて、あるサービスクラスのキューサービスセンタへの流入を低減する。
【００１７】
本発明において、プロセッサ２８は、ＱＳＣ１０から回線３０を介して、詳細は後述するように、キューの長さと常駐時間に関するある情報を受信し、また、その情報を用いてＣＢＷＦＱアルゴリズムの重み付けの値を動的に調整する。調整された重み付け値は、回線３２を介して、交換パターン生成器に供給され、そして、交換パターン生成器は、新たな重み付けの形式を利用して、ＣＰＵ２２の交換パターンを調整する。更に、総システム負荷係数が算出され、また、総システム負荷係数が所定の値を超える場合、フロー制御が行われる。
【００１８】
図２は、図１の装置に基づく、本発明の作用を示すフロー図である。
図２のアルゴリズムは、４０で初期化され、ここで、以下の初期条件が設定される。
すなわち、Ｗ１は、キューサービスセンタがＣｏＳキューｉに適用する整数の巡回の数を表すものとする場合、交換パターンは、［Ｗ１Ｗ２．．．Ｗｎ］であり、交換サイクル当り合計ΣＷｉのサービスとなる。
【００１９】
これを用いて、上述のＣＢＷＦＱ式に記載の初期重み付け値を決定し得る。
アルゴリズムを続けると、各キューイング局でのキュー深さは、サービスクラス全てに対して４２で判断される。このことは、各ＣｏＳ用のバッファがどれだけ一杯であるかを判断することによって成し得る。これによって４４で用いられる情報が提供され、各サービスクラスに対する常駐時間が判断される。ブロック４４において、特定のキューに対するキューイングサービス時間が与えられると、対応する予想パケット常駐時間が、各サービスクラスと組み合わされた全てのサービスクラスに対して算出されＲｃｏｓ（ｎ）となる。
【００２０】
ブロック４６において、組み合わされた全てのサービスクラスに対する総常駐時間を全てのＣｏＳに対する設定されたシステム設計の総常駐時間で除算することによって、システム負荷係数が次のように決定される。すなわち、ｋ＝与えられたサービスクラスに対する常駐時間の限界値とすると、
負荷係数＝ΣＲｃｏｓ（ｎ）／Σｋ（ｎ）
【００２１】
システム負荷係数が、ブロック４８のそれより大きい場合、セッションマネージャには、システムがオーバーロード状態になり、また、優先順位が高いサービスクラスのデータフローを中断するためにフロー制御を実施すべきであることが５０で通知される。セッションマネージャは、ネットワーク進入フローレートを絞る役割又はネットワークへのアドミッション制御を提供する役割を果たす。システム負荷係数が、境界内にある場合、優先順位が高いサービスクラスは、５２で確認され、各サービスクラスの常駐時間Ｒｃｏｓが、所望のクラス限界ｋｃｏｓ内にあるか否か判断される。優先順位が高いパケットに対する常駐時間が、設定されたクラス限界値より大きい場合、この係数は５４において大きくなり、新たなパラメータが、調整のために初期化アルゴリズム４０に提供される。
【００２２】
Ｗｃｏｓ（ｎ＋１）＝Ｗｃｏｓ（ｎ）＋１
優先順位が高いパケットに対する常駐時間が、設定された限界値より低い場合、５６において、Ｗｃｏｓが下限より低いか否か判断される。そうである場合、変更は起こらない。Ｗｃｏｓがそのクラスに対して下限より低くない場合、重み付けは、５８において次のように減する。
【００２３】
Ｗｃｏｓ（ｎ＋１）＝Ｗｃｏｓ（ｎ）−１
また、その結果は、初期化アルゴリズム４０に渡され、全体的なアルゴリズムの次の繰り返しループに備えて調整される。
上述のアルゴリズムによって、ＣＢＷＦＱ重み付けシステムの重み付けパラメータが動的に調整されるため、導き出した情報を用いて、後続のサービス又は送信媒体への効率的な送信に対して様々なサービスクラスを適切に優先順位付けするために、交換パターン生成器２６が、新たな交換パターンをＣＰＵ２２に提供するようにプログラムする。
【００２４】
このように、クラスベース重み付け均等化キューイングネットワーク要素において、サービスクラスの各々に対する重み付け係数を動的に変えるための方法と装置が提供される。この装置と方法によって、一旦初期係数が決定されると、システムは、必要に応じて、優先順位が最も高いサービスクラスのパケットの整合性を保つために、その係数を動的に調整する。全体の設計負荷係数を超過した場合のみ、セッションマネージャに通知して、幾つかの又は全てのサービスクラスに対してフロー制御を導入する必要がある。
【００２５】
本発明の好適な実施形態を説明し、また、その形態を詳細に説明したが、当業者には、本発明の精神から、また、添付の請求項の範囲から逸脱することなく、これらに対して様々な修正が可能であることが容易に明らかであろう。
【図面の簡単な説明】
【図１】本発明による特徴を組み込んだ通常のデータルータを示すブロック図。
【図２】図１の装置に基づく、本発明の作用を示すフロー図。
【図１】
2004514324.tif 000003
【図２】
2004514324.tif 000004
【国際公開パンフレット】
2004514324.tif 000005
2004514324.tif 000006
2004514324.tif 000007
2004514324.tif 000008
2004514324.tif 000009
2004514324.tif 000010
2004514324.tif 000011
2004514324.tif 000012
2004514324.tif 000013
2004514324.tif 000014
2004514324.tif 000015
2004514324.tif 000016
2004514324.tif 000017
2004514324.tif 000018
2004514324.tif 000019
2004514324.tif 000020
【国際公開パンフレット（コレクトバージョン）】
2004514324.tif 000021
2004514324.tif 000022
【国際公開パンフレット（コレクトバージョン）】
2004514324.tif 000023
2004514324.tif 000024
【国際調査報告】
2004514324.tif 000025
2004514324.tif 000026
2004514324.tif 000027
2004514324.tif 000028
2004514324.tif 000029
2004514324.tif 000030