(57)【特許請求の範囲】
【請求項１】
ネットワークにおけるエンティティのスケジューリングを行なう装置であって、
サービスをエンティティに提供するサーバと、
サーバからのサービスを将来受けようとするエンティティが、サーバから将来サービスを受けようとする時に、エンティティのセッションが所定のトラヒック基準に適合するかどうかを決定する決定部と、
決定部が、エンティティのセッションは不適合であることを決定しない場合に、エンティティがサーバからのサービスを受ける時をスケジューリングするスケジューラ部と、を具えており、
決定部は、リーキバケットアカウンティング部を具え、
スケジューラ部は、リーキバケットアカウンティング部に対し、現在のスロット時間で提供されるセッションを告知し、リーキバケットアカウンティング部は、そのセッションが直ぐ次のスロット時間でスケジューリングされるとすると、リーキバケットの制約に適合するかを判断し、適合しない場合に、スケジューラ部からセッションが削除される、スケジューリング装置。
【請求項２】
セッションが適合しない場合に、セッションが後で適合して、サーバからサービスを受けることができる最早復活時間まで、決定部がセッションを格納する復活キューを含んでいる請求項１に記載の装置。
【請求項３】
復活キューは、セッションが後で適合状態になった時、スケジューラ部から以前に削除されたセッションをスケジューラ部に戻す請求項１に記載の装置。
【請求項４】
スケジューラ部は、レートベースのスケジューラ部である請求項１に記載の装置。
【請求項５】
スケジューラ部、復活キュー及びリーキバケットアカウンティング部は一緒になって、アウトバウンドシェーピングを実現する請求項１に記載の装置。
【請求項６】
スケジューラ部は、レート保証手段を具え、該レート保証手段は、サービスを保証されたセッションに対して、保証されたサービスをスケジューリングする請求項１に記載の装置。
【請求項７】
スケジューラ部は、レート保証手段が、セッションが保証された全てのセッションへサービスを提供した後、サービスを利用可能な自由帯域幅を委任する自由帯域幅デレゲータを含んでいる請求項１に記載の装置。
【請求項８】
復活キューは、復活時間に対応してセッションが格納されるビンを有しており、リーキバケットアカウンティング部によりスケジューラ部の自由帯域幅デレゲータから削除されたセッションは、リーキバケットアカウンティング部により、セッションの最早復活時間に対応する復活キューのビンへ挿入される請求項７に記載の装置。
【請求項９】
復活キューは、セッションを、その復活時間がスケジューラ部のサイクルタイムｔに等しい自由ベースデレゲータへ戻す請求項７に記載の装置。
【請求項１０】
セッションは、Ｃ１型、Ｃ２型又はＣ３型であり、Ｃ１型セッションはレート保証手段にのみ存在し、Ｃ２型セッションはレート保証手段と自由帯域幅デレゲータの両方に存在し、Ｃ３型セッションは自由帯域幅デレゲータにのみ存在する請求項９に記載の装置。
【請求項１１】
レート保証手段は、トラヒックレートの契約と一致するサービスレートを有する請求項１０に記載の装置。
【請求項１２】
リーキバケットアカウンティング部は、自由帯域幅デレゲータとのみ接続され、復活キューは自由帯域幅デレゲータとのみ接続される請求項１１に記載の装置。
【請求項１３】
各セッションは、それに関連付けられた少なくとも１組のパラメータを有し、各組のパラメータは、次のセルの理論的着信時間(ＴＡＴ)、時間増分(Ｉ)及び限界(Ｌ)からなる３つのエントリを有する請求項１２に記載の装置。
【請求項１４】
ＡＴＭネットワークにおけるエンティティをスケジューリングする方法であって、
ＡＴＭネットワークに接続されたＡＴＭスイッチのメモリにエンティティのセッションを受信する受信工程と、
ＡＴＭスイッチのサーバからエンティティが将来サービスを受けようとする時に、エンティティのセッションが所定のトラヒック基準に適合するかどうかを、ＡＴＭスイッチの決定部により決定する決定工程と、
決定部が、エンティティのセッションは不適合であることを決定しない場合に、エンティティがサーバからのサービスを受ける時を、ＡＴＭスイッチのスケジューラでスケジューリングするスケジューリング工程と、を含んでおり、
決定工程は、スケジューラが、決定部のリーキバケットアカウンティング部に、現在のスロット時間で提供されるセッションを告知する告知工程と、リーキバケットアカウンティング部が、そのセッションが直ぐ次のスロット時間でスケジューリングされるとすると、リーキバケットの制約に適合するかを判断する判断工程と、リーキバケットの制約に適合しない場合に、決定部がスケジューラからセッションを削除する削除工程とを含む、ＡＴＭネットワークにおけるエンティティのスケジューリング方法。
【請求項１５】
削除工程の後、削除されたセッションが後で適合するようになった時、削除されたセッションをスケジューラに戻して挿入する工程を有している請求項１４に記載の方法。
【請求項１６】
削除工程の後、削除されたセッションを、ＡＴＭスイッチの復活キューの中へ配置する配置工程を含んでいる請求項１５に記載の方法。
【請求項１７】
配置工程の後、セッションを復活キューからスケジューラへ送り戻す工程を含んでいる請求項１６に記載の方法。
【請求項１８】
受信工程は、スケジューラの自由帯域幅デレゲータでセッションを受信する工程を含んでいる請求項１４に記載の方法。
【請求項１９】
削除工程は、自由帯域幅デレゲータからのセッションだけを削除する工程を含んでいる請求項１８に記載の方法。
【請求項２０】
セッションのセルにサイクルタイムｔでサービスを提供する工程を含んでおり、決定工程は、リーキバケットアカウンティング部の現在状態を反映させるために、決定部のリーキバケットアカウンティング部のリーキバケットパラメータＴＡＴを更新し、セッションの別のセルがサーバからサイクルタイムｔ＋１で提供されることを、リーキバケットアカウンティング部が許可する状態にあるかどうかをチェックするチェック工程を含んでいる請求項１９に記載の方法。
【請求項２１】
削除工程は、リーキバケットアカウンティング部が、サーバからサイクルタイムｔ＋１で別のセルが提供されることを許可する状態にないときに、セルを削除する工程を含んでいる請求項１９に記載の方法。
【請求項２２】
セッションはＣ２型であり、チェック工程の後、サーバにより、別のセルがサイクルタイムｔ＋１で提供されることを確認し、リーキバケットアカウンティング部が、サーバによりセッションの第３のセルがサイクルタイムｔ＋２で提供されることを許可する状態にあるかどうかをチェックする工程を有している請求項２１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、エンティティが所定の基準に不適合でない場合に、エンティティがサーバからサービスを受けようとする時をスケジューリングする装置および方法に関する。より具体的には、本発明は、エンティティのセッションが、リーキバケット(leaky bucket)のアカウンティング(accounting)に基づいた所定の基準に不適合でない場合、エンティティがサーバからサービスを受けようとする時をスケジューリングし、不適合の場合は、セッションが復活キューに格納されるようにする装置および方法に関する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
広帯域ネットワークの出現は、種々のトラヒックパラメータを有する多数のコネクションに合わせて調整できる高速のシェーパ構造を設ける際に、新たな挑戦を生じさせている。大規模ウェブやビデオサーバのような、新たなネットワーク用アプリケーションの多くは、バーストや帯域幅の記述子(descriptor)が異なる数百乃至数千ものコネクションに対して、トラヒックシェーピングを要求する。また、ＡＴＭのスイッチは、ネットワークの端部でトラヒックシェーピングを提供することにより、多くのエンドシステムにおけるインプリメンテーションコスト(implementation cost)を償却できる。ネットワークのエンドポイントにおけるシェーピングに加えて、アベーラブルビットレート(Available Bit Rate：ＡＢＲ)式コネクションは、ネットワーク内部の各仮想ソースノードにてトラヒックの実行(enforcement)を要求する。該ノードでは、時間が経過すると、コネクションの帯域幅の割当てが、ネットワークからのフィードバックに応じて変化することがある。また、可変ビットレート(Variable Bit Rate：ＶＢＲ)式および固定ビットレート(Constant Bit Rate：ＣＢＲ)式のコネクションは、ネットワーク内部において再度シェーピングされて、下流側のスイッチ装置における遅延変動やバッファ要求を制限する。コネクションが、様々なパフォーマンス特性のスイッチやサービスプロバイダを通っているとき、トラヒックパラメータを補強することは特に重要である。
【０００３】
既存のトラヒックシェーパの多くは、幾つかのバージョンのリーキバケット制御を用いて、不適合なセルをバッファリングし、後で送信するためにスケジューリングを行なっている。概念的には、リーキバケット制御器は、レートがρのトークンを作成する。ここで、トークンは、多くてもσのクレジット(credit)を保有する。着信セルは、サービスを受ける前にトークンを要求する必要がある。各コネクションに関して、トークンバケットの状態が与えられると、シェーパは、着信セルが適合しているか否かを決定することができる。
【０００４】
従来から、リーキバケットに基づくトラヒックポリシングのアルゴリズムは、受信トラヒック(incoming traffic)が、取り決められた契約(contract)の範囲内にあることを保証するために、ネットワークの入口部(ingress)またはネットワークの構成要素で用いられてきた。同じ様に、投入されたトラヒック(injected traffic)が確実に適合するように、リーキバケットに基づくシェーピングのアルゴリズムは、ネットワークのソース部または端部で用いられてきた。ルータやスイッチのようなネットワーク要素の入口部に入ってくる適合トラヒック(conforming traffic)は、他のセッションとのバッファリングや多重化が行なわれることによって導入されるバースト化(burstiness)により、不適合となり得ることが開示されている[L. Georgiadis, R. Geurin, V. Peris, and K. N. Sivarajan.  Efficient network qoes provisioning based on per node traffic shaping.  IEEE/ACM Trans. Networking, 4(4):482-501, Aug. 1996]。この文献はその引用をもって本願への記載加入とする。そのようなトラヒックは、次のルータ又はスイッチで不適合として処理され、ドロップされるか又はタグ付けされて(dropped/tagged)、エンドとエンドの間(end-to-end)で予期せぬ挙動を生ずる。
【０００５】
レートベースのスケジューラでは、セッションが、保証された最小レートを確実に獲得できるようにする[J.C.R. Bennette and H. Zhang. Wf2q:  Worst-case fair weighted weighted fair queueing,  In INFOCOM'96, pages 120-128, Mar. 1996; S. Golestani.  A self-clocked fair queueing scheme for broadband applications.  In INFOCOM'94, pages 636-646, Jun. 1994]。この文献はその引用をもって本願への記載加入とする。そのような保証に合致した残りの帯域幅は、セッション間において、予め定められた幾つかの公平性(fairness)の方針(policy)に基づいて、分割される。従って、スケジューリングは、セッションの保証に合致する最小のものを確保するけれども、残りの帯域幅をシェアリングする(sharing)間、セッションが受け取り得る最大の帯域幅を制限することはない。従って、セッションが、バーストにて配送(serve out)され、次のネットワーク要素で最大バーストサイズの契約に違反することが起こりうる。図１には、送信リンク(outgoing link)と、送信リンクへ供給する受信リンク(incoming link)と、受信セルを格納するバッファと、バッファから送信リンクにセルを配送するスケジューラを有するブロック図が示されている。
【０００６】
さらに、ネットワーキング機器内でのバッファリングとスケジューリングの決定により、トラヒックは、入口よりも出口の方でバースト状態になることが多いことが示されている。どんなコネクションでも、出口のトラヒックは、そのトラヒック契約に適合することが要求される。不適合な出口トラヒックが別のスイッチまたはネットワークに入ると、トラヒックは規制されて(policed)、タグ付け又はドロップされることになるかもしれない。本発明は、出口で確実にトラヒックに適合させるために、リーキバケットに基づいてシェーピングを行なうことを含んでいる。そのようなアウトバンドシェーピングは、ＰＲ(Peak Rate)、ＳＣＲ(Sustain Cell Rate)およびＡＣＲ(Allowed Cell Rate)のようなトラヒック契約の仕様に確実に含まれるようにする上で重要である。
【０００７】
【課題を解決するための手段】
本発明は、スケジューリング装置に関する。該装置は、エンティティにサービスを提供するサーバを具えている。スケジューリング装置は、将来、サーバからサービスを受ける予定のエンティティが、サーバからサービスを将来受ける時に、所定の基準に適合するかどうかを決定する決定部を具えている。スケジューリング装置は、決定部がエンティティを不適合であると決定しない場合、エンティティがサーバからサービスを受けようとする時をスケジューリングするスケジューラ部を具えている。
【０００８】
本発明は、ＡＴＭネットワークにおいてエンティティをスケジューリングする方法に関する。本発明の方法は、ＡＴＭネットワークに接続されたＡＴＭスイッチのメモリにて、エンティティのセッションを受け取る工程を含んでいる。次に、ＡＴＭスイッチのサーバによるサービスに対して、セッションをスケジューリングする工程を有している。次に、セッションが将来ＡＴＭネットワークのトラヒック契約条件に適合するかどうかを、決定部により決定する工程を有している。次に、セッションが将来適合しない場合に、セッションを削除する工程を有している。
【０００９】
【発明の実施の形態】
添付の図面を参照して、本発明の望ましい実施例及び望ましい方法について説明する。
図面において、同一又は類似の要素については同じ符号を付している。図８は、スケジューリング装置(10)を示している。スケジューリング装置(10)はサービスをエンティティへ提供するためのサーバ(12)を具えている。装置(10)は、サーバ(12)からのサービスを将来受けようとするエンティティが、サーバ(12)から将来サービスを受けようとする時に所定基準に適合するかどうかを決定する決定部(14)を具えている。決定部(14)が、エンティティは不適合であることを決定しない場合、エンティティがサーバ(12)からのサービスを受ける時をスケジューリングするためのスケジューラ部(16)を具えている。
【００１０】
望ましくは、エンティティはセッションを含んでおり、スケジューラ部(16)はセッションをスケジューリングして、決定部はセッションが将来適合状態を継続するかどうかを決定する。セッションが将来適合しなくなる場合、決定部(14)は、スケジューラからセッションを削除することが望ましい。決定部(14)は、セッションが適合状態におかれることにより、サーバ(12)からサービスを受け続けるかどうかを、リーキバケット法のアカウンティングを用いて決定するリーキバケットアカウンティング部(20)を具えることが望ましい。
【００１１】
装置(10)は、セッションが適合状態にない場合、セッションが適合状態になってサーバ(12)からのサービスを受けることができる時になるまで、決定部(14)がセッションを格納する復活キュー(18)を具えることが望ましい。復活キュー(18)は、セッションが後で適合状態になった時、スケジューラ部(16)から既に削除されたセッションをスケジューラ部(16)へ戻すことが望ましい。
【００１２】
スケジューラ部(16)はレート帯域幅スケジューラであることが望ましい。スケジューラ部(16)、復活キュー(18)及びリーキバケットアカウンティング部(20)は一緒になって、アウトバウンドシェーピング(out-bound shaping)を実現することが望ましい。
【００１３】
スケジューラ部(16)は、保証されたサービスを、セッションが保証されたサービスに合わせてスケジューリングするレート保証手段(guarantor)(22)具えることが望ましい。レート方式スケジューラ部(16)は、レート保証手段(22)が、セッションが保証された全てのセッションへサービスを提供した後、サービスを利用可能な自由帯域幅を委任する自由帯域幅デレゲータ(24)を具えることが望ましい。リーキバケットアカウンティング部(20)は、自由帯域幅デレゲータ(24)とのみ接続され、復活キュー(18)は自由帯域幅デレゲータ(24)とのみ接続されることが望ましい。
【００１４】
復活キュー(18)は、復活時間に対応してセッションが格納されるビン(bins)(26)を有することが望ましく、リーキバケットアカウンティング部(20)によりスケジューラ部(16)の自由帯域幅デレゲータ(24)から削除されたセッションは、リーキバケットアカウンティング部(20)により、セッションの最早復活時間に対応する復活キュー(18)のビンへ挿入される。復活キュー(18)は、セッションを、その復活時間がスケジューラ部のサイクル時間ｔに等しい自由帯域幅デレゲータ(24)へ戻すことが望ましい。セッションは、Ｃ１型、Ｃ２型又はＣ３型のものが望ましい。なお、Ｃ１型セッションはレート保証手段(22)にのみ存在し、Ｃ２型セッションはレート保証手段(22)と自由帯域幅デレゲータ(24)の両方に存在し、Ｃ３型セッションは自由帯域幅デレゲータ(24)にのみ存在する。レート保証手段(22)のサービスレートは、契約されたトラヒックレートと一致させることが望ましい。また、各セッションは、それに関連づけられた少なくとも１組のパラメータを有し、各組のパラメータはＴＡＴ、Ｉ及びＬからなる３つのエントリを有することが望ましい。
【００１５】
本発明はＡＴＭネットワークにおけるエンティティをスケジューリングする方法に関する。この方法はＡＴＭネットワークに接続されたＡＴＭスイッチのメモリにてエンティティのセッションを受信する工程を有している。次に、ＡＴＭスイッチのサーバ(12)によるサービスに対して、セッションをスケジューリングする工程がある。次に、セッションが将来のＡＴＭネットワークのトラヒック契約条件に適合するかどうかを、決定部(14)により決定する工程がある。次に、セッションが将来適合しない場合、セッションを削除する工程がある。
【００１６】
また、削除工程の後、削除されたセッションが適合するときは、削除されたセッションを後でスケジューラ部(16)へ戻して挿入する工程を有することが望ましい。スケジューリング工程の前に、セッションをサーバ(12)によりサービスを提供する工程を有することが望ましく、決定工程は、セッションが将来サーバ(12)からのサービスを継続して受けることができるように適合しているかどうかを決定する工程を有するのが望ましい。
【００１７】
削除工程の後、削除されたセッションを復活キュー(18)の中へ配置する工程を有することが望ましい。配置工程の後、セッションを復活キュー(18)からスケジューラ部(16)へ送り戻す工程を有することが望ましい。受信工程は、スケジューラ部(16)の自由帯域幅デレゲータ(24)でセッションを受信する工程を有することが望ましい。
【００１８】
削除工程は、自由帯域幅デレゲータ(24)からのみセッションを削除する工程を含むことが望ましい。サービス提供工程は、セッションのセルをサイクルタイムｔで提供する工程を含むことが望ましい。決定工程は、リーキバケットアカウンティング部(20)の現在状態を反映させるために、決定部(14)のリーキバケットアカウンティング部(20)のリーキバケットパラメータＴＡＴを更新し、また、別のセルがサーバ(12)からサイクルタイムｔ＋１で提供されることを、リーキバケットアカウンティング部(20)が許可する状態にあるかどうかをチェックする工程を含むことが望ましい。
【００１９】
削除工程は、リーキバケットアカウンティング部(20)が、サーバ(12)からサイクルタイムｔ＋１で別のセルが提供されることを許可する状態にないときに、セルを削除する工程を含むことが望ましい。セッションはＣ２型が望ましく、チェック工程の後、サーバ(12)により、セッションの別のセルがサイクルタイムｔ＋１で提供されることを確認し、リーキバケットアカウンティング部(20)が、サーバ(12)によりセッションの第３のセルがサイクルタイムｔ＋２で提供されることを許可する状態にあるかどうかをチェックする工程を有することが望ましい。
【００２０】
本発明の実施において、ネットワークのバッファリング／スケジューリングにより生ずる摂動(perturbation)の衝撃を解消するために、ネットワークの中間位置でトラヒックのシェーピングを行なうことが望ましい。これは、スイッチのようなネットワーク構成要素の出口で行なうことができる。この考えは、リーキバケットに基づくシェーピングをスケジューリングと結合することにある。その問題の対策として、次の２つの手法がある。
a)シェーピングとスケジューリングが統合された新規なメカニズムの開発[J. Rexford, F. Bonomi, A. Greenberg, and A. Wong. A Scalable Architecture for Fair Leaky-Bucket Shaping. In INFOCOM'97, Apr. 1997]。この文献はその引用を以て本願への記載加入とする。
b)既存のスケジューリング部をレバレッジして(leveraging)、リーキバケットアカウンティングと連繋するように拡張する。この明細書中で提案した装置(10)は、後者の手法を発展させるものである。
【００２１】
図２は基本スキームのブロックレベル図を表している。スケジューリングブロックの他に、リーキバケットアカウンティング(leaky bucket accounting：ＬＢＡ)ブロックと、復活キュー(revival queue：ＲＱ)(18)の２つのブロックがさらにある。次のことが起こる。スケジューラ部(16)は、ＬＢＡに、現在のスロット時間で提供されるセッションを告知する。ＬＢＡは、リーキバケットの制約に基づいて、次に記載の決定を行なう。同じセッションが直ぐ次のスロット時間でスケジュールされるべき場合、提供されたセルは適合するか？  もし適合しない場合、セッションはスケジューラ部(16)から削除される。これは、次のスロット時間で提供されるセッションで、適合性のないセッションの可能性を排除する。
【００２２】
ＬＢＡは、セッションが適合状態にて再び提供される最早復活時間(earliest revival time：ＥＲＴ)を決定して、セッションを復活キュー(ＲＱ)(18)へ挿入する。ＲＱからのセッションは、現在時間がセッションのＥＲＴに等しいとき、スケジューラ部(16)の中へ戻して挿入される。
【００２３】
上記のスキームでは、ＥＲＴが現在のスロット数に等しいセッションは多数あるかもしれない。理想的には、そのようなセッションは全てスケジューラ部(16)へ戻される必要がある。上記スキームは、任意数のセッションが同時に復活できるインプリメンテーションにおいて、うまく機能する。スケジューラ部(16)のインプリメンテーション／ハードウエアが、スロット時間にＲＱからスケジューラ部(16)へ挿入されるセッションの数を制約するときに問題が起こる。そのような状況では、即時(immediate)リアルタイムの制約条件を受けるセッションは、ＲＱにおけるリアルタイム制約の小さい大量のセッションの背後でブロックされたままになる不都合がある。
【００２４】
上記の問題は次の２つの方法により解決することができる。
１．ＲＱからのウエイクアップを優先させること。ＲＱは、リアルタイムの制約を有するもの(保証に合致させるため)と、有しないもの(ベストエフォト(best effort))とに、セッションをソートする(sort)。リアルタイム制約を有し、資格のある(eligible)セッションは、リアルタイム制約のないセッションに優先して復活させられる。それゆえ、スキームは、よりすぐれたパフォーマンスをリアルタイムセッションに提供する。しかしながら、ＥＲＴだけでは、復活させられるべきリアルタイムセッションで資格のある全ての中から、どのセッションが特に重要かを決定することはできないことが示されている。このため、別の手法を検討する必要が生ずる。
２．リアルタイムインプリケーションを有しないセッションだけがＲＱへの挿入が許可される。保証されたセッションはＲＱへ入り込むことは決してない。このスキームについては、適用可能なスケジューリング部の種類と共に、次のセクションで説明する。
【００２５】
装置(10)は、図３に示されるように、a)レート保証手段(rate guarantor：ＲＧ)(22)と、b)自由帯域幅デレゲータ(free bandwidth delegator：ＦＢＤ)の２つの部分を具えるＡＴＭスケジューラ部(16)であればどれにも適用可能である。ＡＴＭは、サービスの種類に応じて、これら部分の一方又は両方で接続可能である。図示の装置(10)は、そのようなＡＴＭスケジューラ部(16)を増補して(augmenting)、リーキバケットに基づいてアウトバウンドシェーピングを行なうことができる。
【００２６】
望ましい実施例において、スケジューラ部(16)に関する前記２つの部分は次のような働きを有する。
〔レート保証手段(22)ＲＧ〕
ＲＧはＰＦＱスキームの変形(variant)を利用する[J.C.R.Bennett and H.Zhang. Wf2q: Worst-case fair weighted weighted fair queueing. In INFOCOM'96, pages 120-128, Mar. 1996; S.Golestani. A self-clocked fair queueing scheme for broadband applications. In INFOCOM'94, pages 636-646, Jun. 1994; A.Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Network.  PhD Thesis, Massachusetts Institute of Technology, 1992]。これらの文献はその引用を以て本願への記載加入とする。タイムスタンプを用いて、プログラミングされたレートと等しいサービスレートにて、セルをセッションから円滑に提供する。この円滑さは、変化(variance)が制御された規則的なインターデパーチャ時間(inter-departure times)に合わせてセルをセッションから提供することによりもたらされる。
〔自由帯域幅デレゲータ(24)ＦＢＤ〕
スケジューラ部(16)のこの部分は、自由帯域幅を委任する。一般的には、ＲＧの接続がまだ行われていないとき、チャンスを得る。ＦＢＤのインプリメンテーションは、優先性、公平性などを考慮して、どんなメカニズムに基づくこともできる。
【００２７】
スケジューラ部(16)内のセッションは、次の３つの種類に分類することができる。
１．Ｃ１
このセッションはＲＧの中にだけある。これは、ＣＢＲのように、保証された円滑なサービスを必要とするセッションである。
２．Ｃ２
このセッションはＲＧとＦＢＤの両方に属する。これらは、ＶＢＲのＳＣＲ、ＡＢＲのＭＣＲのように保証された帯域幅を必要とするセッションであるから、ＲＧの中にあらねばならない。しかし、それらもまたより多くの帯域幅を必要とするが、それは、ＶＢＲセッションの場合のように、バーストを取り扱うためであり、また、ＡＢＲセッションの場合のように、自由帯域幅の共有を簡単に受けるようにするためである。このため、これらセッションはＦＢＤの中にもあらねばならない。
３．Ｃ３
このセッションはＦＢＤにのみ属する。これらは、ＵＢＲのように、自由帯域幅の共有だけを必要とするセッションである。
【００２８】
スケジューラ部(16)のＦＢＤからＣ２型又はＣ３型のセッションが受けたサービスは、アウトバウンドシェーピングに関して問題が起こる。そのようなサービスは、トラヒック契約の条件と適合しないかもしれない。例えば、他にどんなトラヒックももたない特定のスイッチでバックログされるセッションを考えてみる。スケジューラ部(16)は、バックログが持続するまで、セッションからの一連のセルをスケジュールするであろう。送り出されたセルのバーストは、最大バーストサイズ及び下流要素の最大レートに関して、トラヒック契約に違反するかもしれない。それゆえ、上記問題を解決する必要性がある。
【００２９】
この発明は、上記スケジューラ部を増補して、Ｃ２型及びＣ３型セッションに関して、リーキバケットに基づいてアウトバウンドシェーピングを行なう装置及び方法に関して記載する。
【００３０】
ＲＧにのみ属するＣ１型セッションは、制御された円滑なサービスを受ける。それゆえ、ＲＧのそれらのサービスレートがトラヒックの契約レートに一致すると仮定すると、トラヒックの契約に違反する可能性は非常に低くなる。
【００３１】
図４は装置(10)のブロック図を示している。リーキバケットアカウンティング(ＬＢＡ)と復活キュー(ＲＱ)(18)の２つの新しい論理ブロックが追加されている。ＬＢＡは、セッションごとのリーキバケットパラメータとアカウンティング論理を含んでいる。ＲＱブロックは、現在、スケジューラ部(16)から削除されているセッションのトラックを維持している。ＲＱのセッションは維持されてソートされる。ソーティングは、セッションの最早復活時間(ＥＲＴ)に基づいて行われる。
【００３２】
与えられたセル時間の中で、次の工程が行われる。
１．スケジューラ部(16)の組合せ(ＲＧ＋ＦＢＤ)は、セルを送り出すためのセッションを取り出す。このセッションを、ｓと表示する。
２．ＬＢＡブロックは、＄ｓ＄について告知される。セッションが、リーキバケットに基づくバースト制約に違反することなく、すぐ次のセル時間の中で別のセルを送り出すことができる場合、ｓのサービス履歴に基づいて計算する。スケジューラ部(16)は、次に、この決定について告知される。
３．ＬＢＡの決定は次のような場合がある。
次のサイクルでサービスが提供されると、セッションがリーキバケットの制約に違反するとき、セッションはＦＢＤから取り除かれる。削除されるセッションがＣ２型に属する場合には、該セッションはＲＧにおいてのみサービスを受ける。Ｃ３型セッションは、どんなサービスも受けず、ＲＱへ送られる。ＬＢＡは、＄ｓ＄に対するリーキバケットがその制約に違反することなく別のセルを許可できる最早時間に基づいて、最早復活時間(ＥＲＴ)を予め計算する。セッションを格納する間、ＥＲＴはＲＱによって使用される。
次のサイクルでサービスが提供されても、セッションがリーキバケットの制約に違反しないときは、セッションは既にＦＢＤの中にあるかどうがチェックされる。もし、ＦＢＤの中にない場合、自由帯域幅の共有を受けることができるように、ＦＢＤの中へ戻され追加される。この場合、Ｃ２型のセッションだけが戻されることに留意されるべきである。Ｃ３型セッションの詳細については、この項目の中で後で説明する。
４．Ｃ３型セッションはＦＢＤから削除され、ＥＲＴの値と共にＲＱへディスパッチされる。セッションはＲＱの時間ＥＲＴに対応するビンの中へ挿入される。５．各セル時間の始めに、ＲＱはＥＲＴが最小のセッションを有するビンを検査する。最小ＥＲＴが現在時間よりも大きくない場合、このビンのセッションのリストは、ＦＢＤに戻され挿入される。ＦＢＤの中で同じようなリスト構造を仮定すると、これは実際には、単一リストをＦＢＤに挿入する必要があり、戻して追加されるセッションの数から独立している。それ以外は、ハードウエアの制約により許可される数のセッションだけが戻される。残りのセッションは、将来のセル時間で取り扱われる。
【００３３】
各セッションは、該セッションに関連づけられた２組のパラメータを有している。１組又は２組のパラメータがセッションに使用される。提案されたシェーピングアルゴリズムは、ＡＴＭフォーラムＴＭ４.０に記載された仮想スケジューリングアルゴリズムの場合と同様である。パラメータの各組は、表１に示されるとおり、ＴＡＴ、Ｉ及びＬの３つのエントリを有している。実際のアルゴリズムは図６に記載されている。このアルゴリズムの詳細を説明する前に、参照(reference)として、仮想スケジューリングアルゴリズムを提供する。図５はそのフローチャートを示している。
【００３４】
【表１】
0004485622.tif 000002
【００３５】
ＲＱの設計目標を、以下に掲げる。カレンダーキューに基づくサンプルインプリメンテーションを、可能性ある実施例として提案する。最早復活時間(ＥＲＴ)を有する全てのセッションはｔに等しく、このセッションは、時間ｔに対応するビンの中へ入れられる。そのように提案されたＲＱのインプリメンテーションは、図７に示される。
ＦＢＤから提供されるセッションの場合、リーキバケットアカウンティングが実行される。どんなリーキバケットも一杯になると、セッションはＦＢＤから削除される。削除されたセッションがＲＧに属していないとき、そのセッションは次のように取り扱われる。そのリーキバケットがそのセッションのセルを許可する時に基づいて、ＥＲＴは計算され、セッションは、そのようなタイムスタンプと共に、復活キュー(ＲＱ)(18)へ挿入される。
所定のセル時間ｔにおいて、時間≦ｔの条件に関連づけられたビン(26)の中で、空でないビンで最小時間のものが選択され、セッションはそれからＦＢＤへ戻される。この操作はセル時間ごとに実行されるのが理想的である。
【００３６】
本発明の実施例の詳細を説明したが、その詳細は単なる例示的なものであって、当該分野の専門家であれば、特許請求の範囲に規定された発明の精神及び範囲から逸脱することなく、種々の変形を成し得るものと理解されるべきである。
【図面の簡単な説明】
【図１】送信リンク、受信リンク、及びバッファに対するスケジューラｗ.ｒ.ｔ.の配置の概要を示す図である。スケジューラは、セッションのトラックを維持し、サービス提供すべきセッションを決定する。スケジューラは、バッファモジュールに告知して、前記セッションからのセルを送信リンクに発送する。
【図２】リーキバケットに基づくアカウンティング(ＬＢＡ)部の配置を、セッションのスケジューリング又はシェーピングを行なうスケジューラ部と共に示すブロック図である。スケジューラは、ＬＢＡに対して、現在のスロット時間にサービス提供されるセッションを告知する。ＬＢＡは、セッションが適合している場合に、同じセッションが直ぐ次のスロット時間にサービス提供されるべきか否かを、リーキバケットの制約に基づいて決定する。不適合を回避するために、ＬＢＡは、スケジューラからセッションを削除する。これにより、スケジューラは、次のスロット時刻にこのセッションを確実にサービス提供することができなくなる。ＬＢＡは、セッションが適合状態で再びサービス提供できる最早復活時間(ＥＲＴ)を決定し、セッションを復活キュー(ＲＱ)に挿入する。
【図３】本発明が適用可能なスケジューリング部の一般的な構成を示すブロック図である。スケジューラは、ａ)レート保証手段(ＲＧ)と、ｂ)自由帯域幅デレゲータ(ＦＢＤ)の２つの部分を有している。コネクションは、ＲＧおよびＦＢＤの何れかまたは両方に属することができる。ＲＧモジュールは、パケットフェアキューイング(Packet Fair Queuing：ＰＦＱ)のアルゴリズムに基づいて、特定の保証レートに合致する各コネクションに対して、円滑なサービスを提供する。ＦＢＤは、コネクション中における残りの(自由)帯域幅を委任する(delegate)。
【図４】スケジューリング装置を示すブロック図である。スケジューラには、リーキバケットアカウンティング(ＬＢＡ)と復活キュー(ＲＱ)の２つのブロックがさらに追加されている。ＬＢＡは、リーキバケットパラメータを維持する。時刻＄Ｔ＄でセルを受け取ると、ＬＢＡは、連続するセル時刻においてセッションがセルを配送できるか否かを決定する。この決定はスケジューラに伝達され、スケジューラは、その決定を用いて、ＦＢＤブロックに対してセッションの除去または追加を行なう。
【図５】仮想スケジューリングアルゴリズムに関するフローチャートである。
【図６】このサイクルｔでサービス提供されたセッションが、ＦＢＤから除去されるべきか、またはＦＢＤへ追加されるべきか否かを決定するために用いられるリーキバケットの計算(computation)に関するフローチャートである。計算は、３つの部分で行われる。最初は、リーキバケットパラメータＴＡＴは、バケット状態の最近の情報を有するように更新される。２番目は、バケットが、次のサイクルｔ＋１で、同じセッションからの別のセルが配送されることを許可する状態にあるか否かがチェックされる。許可状態にない場合には、スケジューラは、次のサイクルでセルが配送されないようにするために、セッションをＦＢＤから除去することが告知される。バケットが許可状態にあって、セッションがＣ２型の場合にのみ、計算の最後の部分が実行される。これは、Ｃ２型のセッションが時間ｔ＋２でＲＧから別のセルを受け取るかもしれないという最悪のケースを処理するものである。セッションがこの最悪のケースを処理できない場合には、セッションは、回避のためにＦＢＤから除去され、その他の場合には、(より早いサイクルで既に消去された場合に、)残存するかまたはＦＢＤに追加して戻されることができる。
【図７】復活キュー(ＲＱ)のブロックにおいて提案されたインプリメンテーションを示す図である。Ｃ３型のセッションは、ＦＢＤから削除され、セッションの最早復活時間(ＥＲＴ)に対応するビンのＲＱに挿入される。セッションは、以下の要領にて、ＲＱからＦＢＤに戻される。サイクルｔの始めに、ＥＲＴ＝ｔに対応するビンにおけるセッションのリストが、ＦＢＤに戻され、追加される。
【図８】本発明の装置の概要を示す図である。
【符号の説明】
(16)  スケジューラ
(18)  復活キュー
(20)  リーキバケットアカウンティング
(24)  自由帯域幅デレゲータ
【図１】
0004485622.tif 000003
【図２】
0004485622.tif 000004
【図３】
0004485622.tif 000005
【図４】
0004485622.tif 000006
【図５】
0004485622.tif 000007
【図６】
0004485622.tif 000008
【図７】
0004485622.tif 000009
【図８】
0004485622.tif 000010