(57)【特許請求の範囲】
【請求項１】
複数のサービスクラスを有するパケット交換網のルータにおいてパケットをスケジュール設定するための方法であって、前記ルータは、各サービスクラスに対して１つのキューを有し、各キューは、関連するサービスクラスに応じて送信されるパケットを格納し、
前記キューの特定の１つに対する平均キュー長さを測定し、
前記平均キュー長さに応じて前記複数のサービスクラスのそれぞれに帯域幅を割り付ける
ことを備えた方法。
【請求項２】
前記複数のサービスクラスは、プレミアムサービス、確定サービスおよびベストエフォートサービスを含み、前記特定のキューは前記プレミアムサービスクラスに関連している請求項１に記載の方法。
【請求項３】
前記平均は、指数重み付け移動平均である請求項１に記載の方法。
【請求項４】
ローパスフィルタを指数重み付け移動平均に適用することをさらに備えた請求項３に記載の方法。
【請求項５】
前記平均キュー長さは、１つのパケットが前記特定のキュー内に格納される度に測定される請求項１に記載の方法。
【請求項６】
ａｖｇは平均キュー長さ、ｌは瞬間キュー長さ、ｆlはローパスフィルタであり、前記平均キュー長さは
【数１】
0004619584.tif 000005
によって決定される請求項１に記載の方法。
【請求項７】
前記ｆlは０．０１である請求項６に記載の方法。
【請求項８】
前記特定のキューは、最小閾値および最大閾値を含み、前記最小閾値は所望の送信遅延を示し、前記最大閾値は受容可能な送信遅延を示す請求項１に記載の方法。
【請求項９】
前記特定のキューに関連する前記サービスクラスの帯域は、前記平均が前記最小閾値を越えると増加する請求項８に記載の方法。
【請求項１０】
前記サービスクラスに割り付けられた前記帯域幅は、前記平均が前記最大閾値を越えるとき所定の上限未満に維持される請求項９に記載の方法。
【請求項１１】
前記複数のサービスクラスはプレミアムサービスＥＦを含み、前記特定のキューは前記プレミアムサービスクラスと関連し、前記特定のキューは、最小閾値Ｔminおよび最大閾値Ｔmaxを含み、前記最小閾値は所望の送信遅延を示し、前記最大閾値は受容可能な送信遅延を示し、ａｖｇは平均キュー長さであり、ｌは瞬間キュー長さであり、ｆlはローパスフィルタであり、前記プレミアムサービスの帯域幅の初期重みはｗpであり、前記プレミアムサービスの割り付けられた帯域幅重みＥＦwは、ａｖｇの関数として、次式で表され、
【数２】
0004619584.tif 000006
ここで、ｕｐｐｅｒは、前記平均が前記最大閾値を越えるとき所定の上限を示し、ｓは、パケット内で測定される前記特定のキューのサイズである請求項１に記載の方法。
【請求項１２】
前記ｕｐｐｅｒは０．７である請求項１１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信ネットワークに関し、特に、パケット交換網においてサービスを向上させることに関する。
【０００２】
【従来の技術】
サービス品質（ＱｏＳ）対策がない場合には、ベストエフォート（最善の努力（best-effort））のサービスがパケット交換網のデフォルト動作となる。ネットワーク内のルータは、パケットの搬送に最善を尽くすが、万一ネットワークの輻輳が発生した場合には、パケットを無差別に落としてしまうことがある。ルータは帯域幅を管理し、遅延による影響の大きいパケットを優先させる。今日のインターネットは、ベストエフォートサービスの良い例である。ベストエフォートは、一般的なファイル転送または電子メールなどの広範囲のネットワーク化アプリケーションに適する。
【０００３】
しかしながら、他よりも比較的重要であるまたは切迫していると見なされる機能が多く存在する。例えば、ワールドワイドウェブ（「ウェブ」）を含むいくつかのアプリケーションでは、特定のタイプの情報の検索を可能にするよりも、商取引を受信および処理することの方がより重要であると見なされることがある。機能はまた、コンテクストに応じても、比較的、より重要であるまたは切迫していると見なされ得る。例えば、処理リソースは過負荷状態になる。このような場合、特定のパケットを優先させることが望まれることがある。音声／映像の配信などのリアルタイムストリーミングアプリケーションでは、ジッタが問題となる。
【０００４】
ジッタは、ネットワークを伝播する際の信号の歪みである。この場合、信号は元の基準タイミングから変化し、パケットは、連続した順序でまたは適時に目的地に到達しない。即ち、パケットの待ち時間が変化する。パケット交換網では、ジッタは、オリジナル送信のパケット間の時間と比較したパケット間の受信時間の歪みである（ジッタは遅延分散とも呼ばれる）。この歪みは、特にマルチメディアトラヒックに損傷を与える。
【０００５】
従って、インターネットなどの多くのネットワークは、サービス品質（ＱｏＳ）と呼ばれる概念を定義している。ＱｏＳは、特定のトラヒック分類に応じて構成および合図のためにネットワークが取るアクションのセットである。ＱｏＳは、配信されるサービスのレベルを集合的に測定する。ＱｏＳは、利用可能性、エラー性能、応答時間およびスループット、ネットワーク輻輳のために損失した呼または送信、接続セットアップ時間、ならびに故障検出および訂正の速度を含むいくつかの基本的な性能基準によって特徴づけることができる。インターネットサービスプロバイダ（ＩＳＰ）は、サービスレベル合意書（ＳＬＡ）によって定義されている特定のレベルのＱｏＳを保証し得る。ＱｏＳ法によってパケットリクエストは異なるトラヒッククラスに選別および分類され、アプリケーションタイプ、ユーザまたはアプリケーションＩＤ、ソースまたは送信先ＩＰアドレス、時間、および他のユーザ指定変数を含む様々な基準に基づいて、適切なリソースがトラヒックを方向づけるために割り付けられる。
【０００６】
インターネットにおいてエンド−ツ−エンドサービス品質を提供するために、インターネットエンジニアリングタスクフォース（技術標準化委員会）（ＩＥＴＦ）は、ベストエフォートのサービス、即ち、統合化（Integrated）サービス（ＩｎｔＳｅｒｖ）および差別化(Differentiated)サービス（ＤｉｆｆＳｅｒｖ）を増加させるための２つの主要なアーキテクチャを定義している。
【０００７】
ＩｎｔＳｅｒｖアーキテクチャのネットワークデータ面では、保証されたサービスをサポートするために、重み付けフェアキューイング（ＷＦＱ）、バーチャルクロック（ＶＣ）およびレート制御最早期限ファースト（Rate-Controlled Earliest Deadline First（ＲＣ−ＥＤＦ）)などのスケジューリング方式が提案されている。制御面では、許可制御およびリソース保留のために、リソース保留プロトコル(ReSerVation Protocol（ＲＳＶＰ）)が必要である。ＩｎｔＳｅｒｖは、優れた品質のサービスを提供するが、コアルータにおいてフロー毎の管理を要求し、これはコアルータに耐えられない負担を負わせる。
【０００８】
ＩｎｔＳｅｒｖアーキテクチャのスケーラビリティは良好でないため、ＤｉｆｆＳｅｒｖが、代替アーキテクチャとして提案されている。ＤｉｆｆＳｅｒｖは、パケット毎の構築ブロックの良好に定義づけられた小さなセットを用いるＩＥＴＦ標準である。このブロックからは、様々なサービスが構築され、ネットワーク内にサービス品質（ＱｏＳ）を搬送するためのフレームワークを提供し得る。少なくとも２つのサービスクラス、即ち、「確定サービス(Assured Service)」および「好ましいサービス(Preferred Service)」が、このような努力の下で定義されている。
【０００９】
ＤｉｆｆＳｅｒｖは、任務が重大なアプリケーションおよびパケットボイスアプリケーションに対する低い遅延を含む、広いクラスのアプリケーションに適した迅速な処理を提供することが可能である。ＤｉｆｆＳｅｒｖ対応のルータは、少数のホップ毎のビヘイビア（behaviors）および単一のバイトに基づいたルータサービスパケットを追跡するだけでよい。通常、ＤｉｆｆＳｅｒｖは、粗いレベルのパケット分類と関連している。
【００１０】
ＤｉｆｆＳｅｒｖのネットワークデータ面では、コアルータにおけるフロー毎の状態管理は除去される。ＩＰヘッダーにおける差別化サービス（ＤＳ）フィールドのビットパターンに基づいて、ＩＰフローは異なる集合体に分類される。コアルータは、単に、単一のスケジューリングおよびバッファリング機構を実行し、集合フローにサービスする。換言すると、サービスは、個々のフローではなく、集合体のために提供され、小セットのホップ毎のビヘイビア（Per-Hop Behaviors（ＰＨＢ)）によって定義される。
【００１１】
ホップ毎のビヘイビアは、ＤＳにおいて定義される基準に基づいて、特定のクラスのトラヒックに与えられる転送処理である。ルータおよびスイッチは、ＰＨＢを用いて、様々なトラヒックフローにサービスするための優先度を決定する。ＰＨＢグループは、キューサービスまたはキュー管理ポリシーなどのセットにおけるすべてのＰＨＢに適用される共通の制約のために、単に有意に特定され同時に実現される１つまたは複数のＰＨＢのセットである。ＰＨＢグループは、関連する転送動作のセットを共に特定（例えば、４つのドロッピング優先度）させるサービス構築ブロックを提供する。
【００１２】
複雑さをエッジルータに押しつけることによって、ＤｉｆｆＳｅｒｖのデータ面は、ＩｎｔＳｅｒｖよりもはるかにスケーラブルである。ＤｉｆｆＳｅｒｖはさらにスケーラブルであるが、許可制御の支持、リソース提供、および制御面におけるサービスレベルの合意を必要とする。
【００１３】
各ネットワークドメインにおいて許可制御およびリソース提供を行うために、帯域幅ブローカアーキテクチャが提案されている。帯域幅ブローカは、ネットワークリソースへのアクセスを制限する、ルータなどの輻輳点において展開されるトラヒックマネージャである。帯域幅ブローカは、コアルータからのＱｏＳ制御を分断する。コアルータは、ＱｏＳ保留状態を維持せず、すべての保留状態は、帯域幅ブローカによって格納および管理される。しかし、帯域幅ブローカは、多数のトラヒックフローを調整するまたは多数のドメインによってなされるＱｏＳリクエストの競合を解決することはできないため、エンド−ツーエンドＱｏＳの解決法とはならない。
【００１４】
データ面におけるパケットスケジューリング規律については、粗粒ＱｏＳ支援を実現するために、多数の機構が利用可能である。優先度キューイングおよび重み付けラウンドロビンスケジューラ以外に、クラスベーストキューイング（ＣＢＱ）スケジュラーは、ＥＦキューに構成レートまでの優先度が与えられるＤｉｆｆＳｅｒｖアーキテクチャにおける転送ビヘイビアの要件に合致する可能なインプリメンテーションである。
【００１５】
現在、３つのタイプのＰＨＢがＤｉｆｆＳｅｒｖアーキテクチャに含まれる。即ち、迅速転送（Expedited Forwarding（ＥＦ）)ＰＨＢ、確定転送(Assured Forwarding（ＡＦ）ＰＨＢ、およびベストエフォート（ＢＥ）ＰＨＢである。ＥＦは、ＤｉｆｆＳｅｒｖにおけるプレミアムサービスを支援し、バーチャル専用線として提案されている。低損失レート、低遅延、低遅延ジッタ、および確定スループットを提供することは、プレミアムサービスによってなされるコミットメントである。ＡＦは単に低損失レートを提供するが、遅延および遅延ジッタに関する保証は提供しない。
【００１６】
ＩＰネットワークにおいてプレミアムサービスを実現するために、ルータにおけるパケットスケジュラは、ＥＦコミットメントに合致するために不可欠である。提案されている様々なパケットスケジューリング方式の中で、優先度キューイングおよび重み付けラウンドロビンは、その簡便さのために、ＥＦを実現するために注目されている。優先度キューイングは、重み付けラウンドロビンよりも低い遅延および遅延ジッタをＥＦフローに提供することが可能であるという結果が示されている。この結果は、驚くべきものではない。なぜなら、優先度キューイングスケジューラでは、優先度キューは、常に、他のキューよりも前にサービスされ、適時パケット搬送が保証されるからである。
【００１７】
しかし、優先度キューイングは、より大きなバースチネスを導入し得る。ＥＦパケットは、異なるビヘイビア集合体（ＢＡ）に属する他のパケットにインターリーブしないからである。ビヘイビア集合体は、転送路における同じＤＳフィールドパターンをもつパケットのセットである。
【００１８】
ＥＦフローが集合すると、ＥＦパケットのクラスタとなり、ＥＦバースチネスは、コアルータにおいてより多くのＥＦフローが集合するにつれて増加する。優先度キューイングによってもたらされるこれらの副作用によって、ＥＦパケット受信レートは、コアルータにおける保留サービスレートを超え、パケット損失となる。
【００１９】
優先度キューイングがバースチネスの増加およびバーストパケット損失（bursty packet loss）につながり得ることも既知である。さらに、優先度キューイングは、ＥＦフローによる徹底的な帯域幅消費を可能にし、これによって、他のビヘイビア集合体に対して不足が生じる。重み付けラウンドロビンまたは重み付けフェアキューイングスケジューリング方式は、このような欠点を有していないが、ネットワーク内におけるトラヒック歪みおよび動的フロー集合によって、ルータにおける静的重みは良好に作用することが困難になる。
【００２０】
キューイング遅延を全く提供しないか、または非常に小さいキューイング遅延を提供するためには、プレミアムサービスは、すべての通過ノードにおけるＥＦ集合体の最大受信レートが常に集合体の最小送信レートよりも小さくなることを要求する。この要件に合致するためには２つの前提条件がある。即ち、ＥＦ集合体は、任意のルータの動的状態とは独立した、良好に定義された最小送信レートを有すること、ならびにルータにおける受信レートがルータの構成された最小送信レートよりも確実に小さくなるようにＥＦ集合体を条件づけること（割り当ておよび成形（policing and shaping）を含む）である。
【００２１】
残念なことに、トラヒック条件付けは、エッジルータにおいてのみ行われる。パケットクラスタ化などの、ネットワーク内のトラヒック歪みは、確約されたトラヒック仕様を容易に違反し得る。さらに、各ルータでは、ＥＦ集合体におけるフローの数は、個々のＥＦフローの結合または脱離（leaving）と共に変化する。このため、ＥＦ集合体についての最小の送信レートは、トラヒックプロファイルの変化に合致するように動的に調整されなければならない。厳密な許可制御の支援および正確なトラヒック条件付けの支援なしでは、重みの静的な設定は、バーストパケット損失を引き起こし得る。なぜなら、比較的小さなバッファスペースがプレミアムサービスに対して用いられるからである。
【００２２】
【発明が解決しようとする課題】
従って、通信ネットワークにおけるプレミアムサービスを支持するパケットスケジューラが求められている。スケジューラは、厳密な許可制御を必要とすることなく、異なるトラヒックフロー集合体に動的に適応しなければならない。ネットワークにおけるバースチネス（burstiness）は、パケット損失またはキューイング遅延の増加なしに吸収されなければならない。
【００２３】
【課題を解決するための手段】
本発明は、差別化サービスアーキテクチャネットワークにおけるプレミアムサービスのためのパケット搬送をスケジュール設定するための方法を提供する。この方法は、重み付けラウンドロビンまたはフェアキューイングなどの重み付けパケットスケジューリングポリシーを用いることができる。本発明の目的として、本スケジューリング方法は、従来のような特定の固定値に固執する代わりに、動作集合体のスケジューリング重み付けを適宜変化させる。プレミアムサービスの平均キューサイズのダイナミクスを用いて重みを適宜調整することにより、本発明による方法は、プレミアムサービスのための低パケット損失レート、低遅延および低遅延ジッタを成し遂げる。
【００２４】
さらに、本方法は、柔軟性があり、差別化サービスアーキテクチャにおいてプレミアムサービスを支援するために、厳密な許可制御および正確なトラヒック調整を必要としない。ネットワーク内のトラヒック歪みによって引き起こされる迅速転送集合体の一過性のバースチネスは、パケット損失およびキューイング遅延の増加なしに吸収され得る。
【００２５】
本発明による方法は、バッファを用いて、プレミアムサービスのための一過性のバースチネスを収容する。この方法は、プレミアムサービスのための平均キューサイズを見積もるために、指数重み移動平均（ＥＷＭＡ）を用いる。これは、重みを較正するために用いられる指標である。プレミアムサービスの重みは、平均キューサイズのダイナミクスに従って適宜調整される。
【００２６】
非常に小さな平均キューサイズを維持することにより、低キューイング遅延が成し遂げられる。また、小さなキュー重みは、瞬間的なキューサイズの変動を低減させるために用いられ、低遅延ジッタへとつながる。ＤｉｆｆＳｅｒｖアーキテクチャにおいて異なる転送サービスを提供するために、各動作集合体は、一般的な共用バッファの代わりに、それ自体のバッファ空間をコアルータに有する。
【００２８】
【発明の実施の形態】
図１は、本発明を用いるパケット交換網通信ネットワークを示す。このネットワークは、メッセージ（パケット）を送受信することが可能な多数のホストコンピュータ１１０を有する。ネットワークのルータは、パケットを処理する。エッジルータ（ＥＲ）１２０は、ホストコンピュータ１１０に接続され、コアルータ（ＣＲ）１３０は、ネットワーク内でルータを互いに接続する。
【００２９】
図２は、ルータを示す。ルータは、入力ポートにおいて入力ライン２０１をスイッチ２２０に接続する。スイッチ２２０は、ルーティングテーブル２２１を用いて、パケットを、出力ライン２０６に接続された出力ポートにおける出力バッファ２３０に経路指定する。
【００３０】
図３は、出力バッファ２３０の１つを示す。各バッファは、３つのキューを含む。ＥＦキュー３０１は、プレミアムサービスパケットを格納し、ＡＦキュー３０２は、確定サービスパケットを格納し、ＢＥキュー３０３は、ベストエフォートパケットを格納する。他のタイプのパケット交換網は、異なるセットのサービスを含み得るため、異なる数のキューを含み得ることを理解されたい。
【００３１】
各キューは、キュー内に格納することが可能なパケットの最大数を示すサイズｓ、およびキュー内に格納されるパケットの現在の数を示す長さｌを有する。サイズｓは、静的であるのに対して、長さｌは、経時的に変化する。
【００３２】
パケットは、帯域幅重み付けの次式に従って対応する出力ライン２０９に搬送される。
【００３３】
【数３】
0004619584.tif 000002
【００３４】
ここで、ＥＦwは、プレミアムサービスの重み、ＡＦwは、確定サービスの重み、ＢＥwは、ベストエフォートの重みである。即ち、重みは、対応するキューにおいてパケットに割り付けられた出力ラインの帯域幅の相対的な量を決定する。ＥＦキューに関連した重みが高い場合、例えば、プレミアムサービスパケットは、さらに帯域幅を割り付けられ、優先的なサービスを受ける。
【００３５】
図４は、経時的なＥＦキュー３０１の動的ビヘイビアを示す。ｘ軸は時間（Ｔ）を示し、ｙ軸はＥＦキュー３０１において格納されているパケットの現在の数を示す。曲線４０３は、経時的な瞬間キュー長さｌを示し、曲線４０４は平均キュー長さを示す。
【００３６】
本発明によるプレミアムサービスの重みＥＦwを適宜較正するために、最小閾値（Ｔmin）４０１および最大閾値（Ｔmax）４０２が提供される。最小閾値は所望の遅延を示し、最大閾値（Ｔmax）は許容可能な遅延を示す。遅延は、キュー内に現在格納されているパケットの数に対応する。即ち、キューが長くなれば、パケットが送信される前の遅延は長くなる。
【００３７】
本発明は、通信ネットワークにおいてパケットをスケジュール設定するための適応重み付け方法を提供する。このスケジューリング方法は、トラヒック歪みおよびネットワーク内のフロー集合のダイナミクスに対して順応性がある。この方法は、重み付けラウンドロビンおよびフェアキューイング方式の両方に適用され得る。
【００３８】
適応重み付け較正
図５に示すように、本方法５００は、プレミアムサービスキュー３０１の平均キュー長さ（ａｖｇ）５１１を決定する（５１０）。この平均長さは、ステップ５２０において重みＥＦw５２１、ＡＦw５２２およびＢＥw５２３を適宜調整するための指標として用いられる。平均値は、パケットがキュー３０１内に格納される度に再計算される。
【００３９】
プレミアムサービスキュー３０１の平均キュー長さａｖｇは、指数重み付け移動平均を有するローパスフィルタｆiを用いて決定される。ローパスフィルタの目的は、変化するネットワーク条件に応じてキュー長さが迅速に変化する際の平均値の振動を減衰させることである。
【００４０】
ａｖｇ５１１が平均キュー長さ、ｌ５０１が瞬間キュー長さ、およびｆlがローパスフィルタである場合、平均キュー長さは以下の式によって決定される。
【００４１】
【数４】
0004619584.tif 000003
【００４２】
平均キュー長さにおける変動を低減させるために、ローパスフィルタｆlは、０．０１に設定される。これにより低遅延ジッタとなる。
【００４３】
低キューイング遅延は、平均キュー長さａｖｇを最大閾値Ｔmax未満に保つことによって成し遂げられ得る。これを成し遂げるために、プレミアムサービス（ＥＦw）５２１の重みは、平均キュー長さが最小閾値Ｔmin４０１を越えるときはいつでも増加する。
【００４４】
しかしながら、平均キュー長さが最大閾値Ｔmax４０２に到達すると、プレミアムサービスの重みは、所定の上限（ｕｐｐｅｒ）を越えることはできない。これにより、方法が単純な優先度キューイングに低下することが防止され、上記のようなパケットクラスタ化を引き起こし得る。
【００４５】
本発明の方法では、プレミアムサービスの重みと、平均キューサイズとの関係は線形である。プレミアムサービスの元の重みがｗpであるとき、プレミアムサービスＥＦw５２１の重み関数は、ａｖｇの関数として以下のように表される。
【００４６】
【数５】
0004619584.tif 000004
【００４７】
重み全体がｌである場合、ＥＦw＋ＡＦw＋ＢＥw＝ｌであり、ここでＥＦwはプレミアムサービスの重みであり、ＡＦwは確定サービスの重みであり、ＢＥwはベストエフォートの重みである。
【００４８】
上限（ＥＦwの上限）を０．７に設定すると、重みの残り（０．３）は確定サービスおよびベストエフォートサービスに用いられる。共有リンクに対する重み全体は固定されているため、プレミアムサービスの重みが増加すると、ベストエフォートの重みまたは確定サービスの重みは同量だけ減少する。
【００４９】
以下の規則を適用する。まず、ベストエフォートの重みのいくらかをプレミアムサービスに転送する。プレミアムサービスの重みが、その上限に到達しない場合、確定サービスの重みの一部はプレミアムサービスに転送される。プレミアムサービスの平均キューサイズがＴmax未満に減少した後、ベストエフォートまたは確定サービスから得られる重みはそれに応じて戻される。
【００５０】
プレミアムサービスに対するキューイング遅延が全くない場合または非常に少量である場合にはそのコミットメントを満たすため、パケットにおいて測定されるように、最小閾値Ｔminを０．５に設定し、最大閾値Ｔmaxを２に設定する。
【００５１】
本発明によるＤｉｆｆＳｅｒｖにおけるプレミアムサービスの適応重み付けスケジューリング方法は、プレミアムサービスの平均キューサイズのダイナミクスと共に、ビヘイビア集合体のスケジューリング重みを適宜変化させる。この方法は、遅延またはジッタを悪化させずに、トラヒック歪みをネットワーク内に吸収させる。さらに、この方法は、ＤｉｆｆＳｅｒｖアーキテクチャにおけるプレミアムサービスを支持するために、厳密な許可制御および正確なトラヒック条件付けを必要としない。
【００５２】
本発明を好ましい実施形態を例示することにより記載したが、様々な他の適応および変更は、本発明の趣旨および範囲内でなされ得ることを理解されたい。従って、添付の請求の範囲の目的は、このようなすべての改変および変更を本発明の真の趣旨および範囲内に入るものとして網羅することである。
【図面の簡単な説明】
【図１】  本発明によるスケジューラを用いるパケット交換網のブロック図である。
【図２】  図１のネットワークのルータのブロック図である。
【図３】  ３つのキューを含む図２のルータの出力バッファのブロック図である。
【図４】  経時的な平均キュー長さのグラフ図である。
【図５】  本発明によるスケジューリングのための流れ図である。
【図１】
0004619584.tif 000007
【図２】
0004619584.tif 000008
【図３】
0004619584.tif 000009
【図４】
0004619584.tif 000010
【図５】
0004619584.tif 000011