JP4368979B2 - 簡易な明示的レート表示アルゴリズムの方法及び装置 - Google Patents
簡易な明示的レート表示アルゴリズムの方法及び装置 Download PDFInfo
- Publication number
- JP4368979B2 JP4368979B2 JP22062699A JP22062699A JP4368979B2 JP 4368979 B2 JP4368979 B2 JP 4368979B2 JP 22062699 A JP22062699 A JP 22062699A JP 22062699 A JP22062699 A JP 22062699A JP 4368979 B2 JP4368979 B2 JP 4368979B2
- Authority
- JP
- Japan
- Prior art keywords
- cell
- rate
- abr
- switch
- cells
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L12/5602—Bandwidth control in ATM Networks, e.g. leaky bucket
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/20—Support for services
- H04L49/205—Quality of Service based
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/25—Routing or path finding in a switch fabric
- H04L49/253—Routing or path finding in a switch fabric using establishment or release of connections between ports
- H04L49/254—Centralised controller, i.e. arbitration or scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3081—ATM peripheral units, e.g. policing, insertion or extraction
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/50—Overload detection or protection within a single switching element
- H04L49/501—Overload detection
- H04L49/503—Policing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5629—Admission control
- H04L2012/5631—Resource management and allocation
- H04L2012/5632—Bandwidth allocation
- H04L2012/5635—Backpressure, e.g. for ABR
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5679—Arbitration or scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
- H04L2012/5681—Buffer or queue management
- H04L2012/5682—Threshold; Watermark
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/10—Packet switching elements characterised by the switching fabric construction
- H04L49/103—Packet switching elements characterised by the switching fabric construction using a shared central buffer; using a shared memory
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Quality & Reliability (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、メモリメカニズムの占有のファンクション(function)として、スケジューラを用いてセルのスイッチングを行なう方法及び装置に関するものである。より具体的には、本発明は、ＡＴＭスイッチの与えられたリンクにおけるＡＢＲのトラフィックフローを制御するために、メモリメカニズムの占有のファンクションとして、スケジューラを用いて、ＡＢＲＶＣへ明示的レートをスタンプするＡＴＭスイッチに関する。
【０００２】
【従来の技術】
ＡＴＭネットワークのアベーラブルビットレートサービス(Available Bit Rate：ＡＢＲ)は、時変帯域幅(time-varying bandwidth)に適応可能で、セル損失率の低いバーストデータへの適用に限られていた[ATM Forum. Traffic management specification version 4.0, April 1996参照]。ＡＢＲの仮想コネクション(Virtual Connections：ＶＣ)は、利用可能な帯域幅をかなり共有している。ここで、利用可能な帯域幅とは、固定ビットレート(Constant Bit Rate：ＣＢＲ)と可変ビットレート(Variable Bit Rate：ＶＢＲ)のトラフィックストリームによる帯域幅の残りのことである。ＡＢＲＶＣは、利用可能な帯域幅について公平なシェア(fair share)を獲得するだけでなく、最小セルレート(Minimum Cell Rate：ＭＣＲ)を特定することができ、ＡＢＲＶＣが一旦許可を与えられると、そのレートは保証される。
【０００３】
ネットワークは、ＡＢＲソースに対して、利用可能な帯域幅に関するフィードバック情報を提供する。フィードバック制御方式に関する研究は次の２つのものがある。クレジットベース(credit-based)の方式では、ネットワークのノードは、上流のノードにＶＣごとのクレジットを送り、上流ノードでは、ＶＣに属するセルを送信する際に、そのクレジットを使い切る。レートベース(rate-based)の方式では、ソースはリソースマネジメント(Resource Management：ＲＭ)のセルを定期的に送り、このセルは、目的地(destination)に達するとリターンする。ＶＣルートにあるスイッチは、リターンするＲＭセルの輻輳状況(congestion status)を表示する。
【０００４】
クレジットベースの方法(例えば、[H. Kung and R. Morris. Credit-based flow control for ATM networks. IEEE Networks, 9(2):40-48, March/April 1995]を参照)は、概念的にはより簡単であり、セル損失が起こらないことを保証しているけれども、ＡＴＭフォーラムは、レートベースの方式(例えば、[F. Bonomi and K. Fendick. The rate-based flow control framework for the available bit rate ATM service. IEEE Networks, 9(2):25-39, March/April 1995]を参照)を選択した。その理由は、レートベースの方式の方が、構造的な自由度(フレキシビリティ)が大きいためである。レートベースの方法の場合、スイッチアルゴリズムが複雑であるので、輻輳ビット(congestion bit)のマーキングは簡単であるが、明示的レート(Explicit Rate：ＥＲ)の計算は複雑である。
【０００５】
ＡＴＭフォーラムは、エンドシステムの動作(behavior)を規定したが、ＡＢＲスイッチアルゴリズムのデザインの詳細については、ＡＴＭスイッチの設計者に委ねていた。これまでに、幾つかのＥＲ計算スイッチアルゴリズムが提案されているが、それらのアルゴリズムは、公平なシェアを厳密に計算するアルゴリズムと、公平なシェアを近似的に計算するアルゴリズムの２つのカテゴリーに分類される。公平なシェアの厳密計算アルゴリズムとして、例えばＥＲＩＣＡ、ＥＲＩＣＡ＋がある[R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. ERICA switch algorithm: A complete description. ATM Forum Document Number: ATM Forum/96-1172, August 1996]。ＥＤＥＲＡ[N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997]は、スイッチ出力ポートのネット利用可能帯域幅と、ポートを通過するアクティブＡＢＲＶＣの数を測定する。次に、利用可能な帯域幅をアクティブＡＢＲＶＣの数で割ることにより、公平なシェアの計算が行われる。一方、公平なシェアの近似的計算アルゴリズムとして、例えばＰＲＣＡ、ＥＰＲＣＡがある[L. Roberts. Enhanced PRCA (proportional rate-control algorithm), ATM Forum Document: AF-TM 94-0735R1, August 1994。ＤＭＲＣＡとＥＤＭＲＣＡ[F. M. Chiussi and Y. T. Wang. An ABR rate-based congestion control algorithm for ATM switches with per-VC queueing. In GLOBECOM '97, pages 771-778, 1997]は、浮動小数点(floating-point)の除算は行わない。それは、ポート変数を維持し、該ポート変数はスイッチ出力ポートの輻輳状況に応じて調節される。各ＶＣのＥＲは、これらのポート変数から求められる。一般に、公平なシェアの計算アルゴリズムは、厳密計算アルゴリズムの方が近似的計算アルゴリズムよりも、性能的にすぐれている[N. Ghani. Available Bit Rate Service in ATMNetworks. PhD thesis, University of Waterloo, 1997参照]。
【０００６】
しかし、公平なシェアの厳密計算方法は重大な問題があり、それは、スイッチでボトルネック(bottle-necked)されたＡＢＲＶＣに対して、どこか他の場所でボトルネックされたＡＢＲＶＣから帯域幅を再分配することである。例えば、各々がゼロＭＣＲを有する３個のアクティブＡＢＲＶＣを考えてみることにする。ネット利用可能な帯域幅を３０Ｍビット／秒とし、各々のＡＢＲＶＣの公平なシェアを１０Ｍビット／秒とする。最初の２つのＡＢＲＶＣはスイッチでボトルネックされると仮定し、第３のＡＢＲＶＣはどこか別のスイッチでボトルネックされると仮定する。なお、この別のスイッチは、第３のＡＢＲＶＣが５Ｍビット／秒を超えないようにしている。これが意味するのは、３０−（１０＋１０＋５）＝５Ｍビット／秒の帯域幅は、最初の２つのＡＢＲＶＣの間で再分配されなければならないということである。よって、３つのＶＣの公平なシェアは、それぞれ、１２.５、１２.５、５.０Ｍビット／秒となる。
【０００７】
輻輳回避のための明示的レート表示(Explicit Rate Indication for Congestion Avoidance; ＥＲＩＣＡ)、及びＥＲＩＣＡ＋[R. Jain, S. Kalyanaraman, R.Goyal, Fahmy S., and R. Viswanathan. Determining the number of activeABR sources in switching algorithms. ATM Form Document Number: ATM Forum/98-0154, February 1998; R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S.,and R. Viswanathan. ERICA switch algorithm: A complete descripition.ATM Form Document Number: ATM Forum/96-1172, August 1996]は、再分配のために複雑なスキームを採用しており、ＶＣごとのサービスレートの測定を必要とする。例えば、ＥＲＩＣＡ＋は、利用可能な帯域幅を、アクティブＡＢＲＶＣの合計数ではなく、アクティブＡＢＲＶＣの有効数で割ることにより、再分配の問題を解決している。アクティブＡＢＲＶＣの有効数は次のように定義される。スイッチでボトルネックされるＡＢＲＶＣは１としてカウントされ、他の場所でボトルネックされるＡＢＲＶＣは、（実際のＶＣレート／公平なシェア）に等しい部分としてのみカウントされる。このように、アクティブＡＢＲＶＣの有効数を計算するためには、各ＶＣのセルレートは、スイッチポートで測定されなければならない。ＶＣレートの測定には、Ｏ(ｎ)個の空間コンプレキシティ(space complexity)及び／又はＯ(ｎ)個の時間的コンプレキシティ(time complexity)を有するアルゴリズムを必要とする。ここで、ｎはポートを通過するＶＣの数である。このため、このようなスイッチアルゴリズムを高速ハードウェアで実行するには、費用が非常にかかる。
【０００８】
分散を向上させた明示的レートアルゴリズム(Enhanced Distributed Explicit Rate Algorithm(ＥＤＥＲＡ)[N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997]は、スイッチでボトルネックされたＡＢＲＶＣと、他の場所でボトルネックされたＡＢＲＶＣのトラックを、明示的に保持することにより、再分配の問題を解決する。ＥＤＥＲＡでは、ＡＢＲソースが、その分割された平均ソースレート(Segmented Average Source Rate：ＳＡＳＲ)をＲＭセルに表示すると仮定している。ここでＳＡＳＲは、２つのＲＭセル間のデータセル数の、２つのＲＭセル間の時間に対する比として規定される。ＶＣがネットワーク内のある地点でボトルネックされると、ＳＡＳＲは、許可セルレート(Allowed Cell Rate：ＡＣＲ)よりも小さくなることに留意すべきである。ＡＴＭフォーラムの標準[ATM Forum. Traffic management specification version 4.0, April 1996]では、ＲＭセルにＳＡＳＲ表示を含まないようにすることを決定したので、ＥＤＥＲＡスキームは適宜修正されなければならない。このような修正を行うためには、スイッチ出力ポートでＶＣレートを測定する必要がある。
【０００９】
【発明が解決しようとする課題】
本発明は、新規なスイッチアルゴリズム、つまり、簡易な明示的レート表示アルゴリズム(Simple Explicit Rate Indication Algorithm：ＳＥＲＩＡ)に関するものである。ＥＲＩＣＡ、ＥＲＩＣＡ＋及びＥＤＥＲＡとは異なり、ＳＥＲＩＡは、ＶＣごとのレートを測定する必要がない。実際に、ＳＥＲＩＡは、これまでに提案された公平なシェアの厳密計算スイッチアルゴリズムよりもはるかに簡単である。つまり、セル着信(cell arrival)やセル出発(cell departure)の如きイベント(events)の取扱いに必要な算術的及び論理的な演算の数は少なく、ＶＣの数から独立している。ＳＥＲＩＡが簡単になると、高速のインプリメンテーションにとって特に魅力的である[M. Vishnu, D. Basak, and H.S. Kim. Method and apparatus for a simple explicit rate indication algorithm (SERIA) U.S. Patent Pending, 1998]。
【００１０】
広範なシミュレーションを行なった結果、ＳＥＲＩＡは、最大−最小フェアネス(max-min fairness)、つまり最大−最小公平性を提供するもので、定常状態に迅速にコンバージ(converge)し、リンク帯域幅を１００％利用し、バッファ制御をしっかりと維持することを示している。
【００１１】
【課題を解決するための手段】
本発明は、ネットワークのエンティティからセルをスイッチングする装置に関する。セルスイッチング装置は、ネットワークからの全てのセルを受信する入力メカニズムを具えている。装置は、入力メカニズムが受信した全てのセルを格納するメモリメカニズムを具えており、全てのセルは装置内に格納される。メモリメカニズムは、入力ポートメカニズムに接続されている。メモリメカニズムは、セルが占有する占有場所(occupancy)を有している。セルスイッチング装置は、該装置からネットワークへセルを送信する出力メカニズムを具えている。装置は、あるサービスレートでセルにサービスを提供するサーバを具えている。サーバは、メモリメカニズムと出力メカニズムに接続されている。装置は、メモリメカニズムのセルに対してサービスを提供するスケジューラを具えている。スケジューラは、サーバとメモリメカニズムに接続されている。
【００１２】
本発明は、セルをスイッチングする方法に関する。この方法は、Ｊ個(但し、Ｊは１以上)のエンティティのセルを、スイッチの入力メカニズムでネットワークから受信するステップを含んでいる。次に、セルをスイッチのメモリメカニズムに格納するステップがある。次に、サーバにより、メモリメカニズム内のセルへサービスを提供するステップがある。次に、メモリメカニズムにセルが占有された結果、メモリメカニズムのセルが、スイッチのサーバからのサービスを受信するとき、スイッチのスケジューラを用いてスケジューリングを行なうステップがある。
【００１３】
本発明は、ＡＴＭスイッチの与えられたリンクにおけるＡＢＲのトラフィックフローを制御するために、ＡＢＲＶＣへ明示的レートをスタンプするためのＡＴＭスイッチに関する。本発明の装置は、ＶＣへのトラフィックをスイッチへキャリーする入力ポートメカニズムを具えている。装置は、入力ポートメカニズムが受信したＶＣの全てのセルを格納するためのメモリメカニズムを具えており、セルはスイッチの中に格納される。メモリメカニズムは、入力ポートメカニズムに接続されている。メモリメカニズムは、ＶＣのセルを占有する占有場所を有している。装置は、セルをスイッチからネットワークへ送信する出力ポートメカニズムを具えている。装置は、ＶＣのセルを、入力ポートメカニズムから出力ポートメカニズムへスイッチするためのスイッチングファブリックを具えている。装置は、バックワード(backward)ＲＭセルにおける明示的レート(ＥＲ)とスタンプレートを計算するＡＢＲ−ＥＲメカニズムを具えている。装置は、あるサービスレートでＶＣのセルへサービスを提供するサーバを具えている。サーバは、メモリメカニズム及び出力ポートメカニズムに接続されている。装置は、ＶＣのセルによるメモリメカニズムの占有のファンクションとして、ＶＣのセルへサービスを提供するスケジューラを具えている。スケジューラは、サーバとメモリメカニズムに接続されている。
【００１４】
【発明の実施の形態】
図面を参照すると、同一又は類似の要素については、幾つかの図を通して、同じ引用符号を付している。特に図４１を参照すると、ネットワーク(12)のエンティティからのセルをスイッチングする装置(10)が示されている。装置(10)は、ネットワーク(12)から全てのセルを受信する入力メカニズム(14)を具えている。装置(10)は、入力メカニズム(14)が受信した全てのセルを格納するメモリメカニズム(16)を具えており、全てのセルは、装置(10)の中に記憶される。メモリメカニズム(16)は、入力ポートメカニズムに接続されている。メモリメカニズム(16)は、セルの占有場所(occupancy)を有している。装置(10)は、セルを装置(10)からネットワーク(12)へ送信する出力メカニズム(18)を具えている。装置(10)は、あるサービスレートでセルへサービスを提供するサーバ(20)を具えている。サーバ(20)は、メモリメカニズム(16)及び出力メカニズム(18)に接続されている。装置(10)は、セルによるメモリメカニズムの占有のファンクションとして、セルへサービスを提供するスケジューラ(22)を具えている。スケジューラ(22)は、サーバ(20)及びメモリメカニズム(16)に接続されている。
【００１５】
望ましくは、入力メカニズム(14)はＪ個の入力ポートメカニズム(24)を含んでおり、Ｊは２以上の整数である。全ての入力ポートメカニズム(24)は、一緒に、ある着信レートでセルを受信することが望ましく、ここでスケジューラ(22)は、メモリメカニズム(16)の占有を監視する監視メカニズム(26)と、セルが全ての入力ポートメカニズム(24)により受信された着信レートを変更させる変更メカニズム(28)を含んでいる。
【００１６】
望ましくは、監視メカニズム(26)は、セルのメモリメカニズム(16)への着信レートと、メモリメカニズム(16)のセルがサーバ(20)から利用可能な提供レートとの差に基づいて、エンティティが利用可能な追加の帯域幅を決定する。各エンティティは最小セルレートを有することが望ましく、変更メカニズム(28)は、サービスを要求するエンティティの各々に割り当てられべき追加の帯域幅の公平なシェアを計算する。
【００１７】
望ましくは、入力ポートメカニズム(24)の各々は、エンティティに対応するセルのエンティティ着信レートを有しており、変更メカニズム(28)は、入力ポートメカニズムを通じてセルを供給する各エンティティのエンティティ着信レートを変更するので、全ての入力ポートメカニズム(24)からのセルの着信レートは、メモリメカニズム(16)のセルがサーバ(20)から利用可能なサービスレートに等しく、前記着信レートは全てのエンティティ着信レートの合計となる。変更メカニズム(28)は、入力ポートメカニズムを通じてセルを供給する各エンティティのエンティティ着信レートを、等量だけ変更することが望ましい。
【００１８】
望ましくは、メモリメカニズム(16)は、装置(10)が受信した全てのセルが格納される共有メモリメカニズム(shared memory mechanism)(30)か、又は別に設けたバッファ(32)のどちらか一方から構成され、各入力ポートメカニズムは、関連入力ポートメカニズム、又は各エンティティに対して独立して設けられたバッファ(32)だけが受信した全てのセルを格納する関連バッファ(associated buffer)を有している。監視メカニズム(26)は、メモリメカニズム(16)の中でサーバ(20)からのサービスを待機するセルのバックログ(backlog)を有するエンティティの個数を監視することが望ましい。
【００１９】
エンティティはＡＢＲＶＣを含むことが望ましい。エンティティは、ＣＢＲ／ＶＢＲＶＣを含むことが望ましい。監視メカニズム(26)は、サーバ(20)からのサービスを待機するセルのバックログを有するＡＢＲＶＣの数、即ち、提供されたＣＢＲ／ＶＢＲＶＣからのＣＢＲ／ＶＢＲセル(ｎvbr)の数を監視することが望ましい。
【００２０】
望ましい実施例の実施において、スイッチ(34)の出力ポートメカニズム(40)を考える。Ｎαは、ポートを通過するアクティブＡＢＲＶＣの集合(set)を表すものとする。ＡＢＲＶＣは、そのソースがゼロ以外のレートでセルを送信する場合、アクティブである。集合Ｎαは、次式で示されるように、ＮbsとＮbeに分けられた２組の集合の和である。
【数３】
ここでＮbsは、スイッチ(34)のポートでボトルネックされるアクティブＡＢＲＶＣの集合であり、Ｎbeは、別の場所でボトルネックされるアクティブＡＢＲＶＣの集合である。Ｎα、Ｎbs及びＮbeは、それぞれ、Ｎα、Ｎbs及びＮbeの集合におけるＡＢＲＶＣの個数とする。Ｃabrは、利用可能な帯域幅の量を表すものとする。
【００２１】
Ｎbe＝φ(Ｎbeが空集合)のとき、公平なシェア(Fair Share：ＦＳ)は、式(1)に等しい。
【数４】
なお、ＭＣＲ1は、ｉ番目のＡＢＲＶＣの最小セルレート(minimum cell rate：ＭＣＲ)である。また、ｉ番目のＶＣの明示的レート(ＥＲ)は、ＦＳ＋ＭＣＲｉとなる。
【００２２】
Ｎbe≠φ(Ｎbeが空集合でない)のとき、Ｎbe中のＡＢＲＶＣは、割り当てられたＦＳを利用することができないため、結果として、リンク帯域幅の利用不足(under-utilization)となる。リンク帯域幅の１００％利用を達成するには、Ｎbe中のＡＢＲＶＣが未使用の帯域幅は、Ｎbs中のＡＢＲＶＣに再分配されなければならない。未使用の帯域幅の再分配は、公平なシェアの厳密な計算ＡＢＲアルゴリズムにおいて、重大な要素の１つである。
【００２３】
Ｂiは、ｉ番目のＡＢＲＶＣが利用できる帯域幅の最大量を表すものとし、Ｌはリンク帯域幅を表すものとする。ｉ番目のＡＢＲＶＣがＮbsにある場合には、Ｂi＝Ｌと設定する。帯域幅の再分配により、ＦＳの値は次の式(2)、即ち式(3)、を満足させるようにする。
【数５】
【数６】
これは、次の式(4)を満足することを意味する。
【数７】
【００２４】
ＦＳを計算するために、公平なシェアの厳密な計算スイッチ(34)のアルゴリズムは、次式のトラックを保持(keep)する必要があり、これは些細なタスクではない。
【数８】
【００２５】
Ａのトラックをキープする代わりに、それを推定(estimation)することができる。Ａがアンダーエスティメート(又はオーバーエスティメート)される場合、つまり、Ａが低く推定(又は高く推定)される場合、ＡＢＲＶＣセルのネット着信レートは、ＡＢＲＶＣが利用可能なネットサービスレートよりも少なく(又は多く)なるであろう。ＳＥＲＩＡは、Ａの推定にこの事実を利用する。ＳＥＲＩＡは、Ｕで表される追加の帯域幅パラメータと呼ばれる変数Ｕを維持しており、この変数は、式(5)で示されるように、公平なシェアを計算するときにＣabrへ加算される。
【数９】
式(6)中、分母のmax( )は、ゼロによる割算を回避するためのものである。ＳＥＲＩＡによるＵの調節は、ＡＢＲセルのネット着信レートがＡＢＲＶＣの利用可能なネットサービスレートに等しくなるまで行われる。
【００２６】
本明細書中で用いられる記号を表１にリストアップしている。ＳＥＲＩＡの疑似コードの完全な記載は、図４４及び図４５に示している。
【００２７】
【表１】
【００２８】
〔Ｃabrの計算〕
Ｎ個のスロットの各測定期間に、ＳＥＲＩＡは、帯域幅が保証されたＶＣ(即ちＣＢＲＶＣと、ＶＢＲＶＣ)から提供されたセルｎgのトラックを保持する。なお、ＣＢＲＶＣとＶＢＲＶＣによる帯域幅の残り(bandwidth leftover)は次の式(6)に等しい。
【数１０】
【００２９】
〔Ｕの計算〕
前述したように、ＳＥＲＩＡは、ＡＢＲセルのネット着信レートがＡＢＲＶＣの利用可能なネットサービスレートに等しくなるまで、追加の加帯域幅パラメータＵを調節する。ＳＥＲＩＡは、ＡＢＲＶＣのネット着信レートが、ＡＢＲＶＣの利用可能なネットサービスレートよりも小さい(大きい)とき、Ｕを増加(減少)させる。着信レートとサービスレートとの差は、ＡＢＲバッファの占有が変化するレートにより決定される。
【００３０】
Ｂは、ＡＢＲバッファのサイズとし、Ｑnは、現在の測定間隔のＡＢＲバッファ占有の総計(aggregate)を表し、Ｑpは、以前の測定間隔のＡＢＲバッファ占有の総計を表すものとする。そして、ΔＱ＝Ｑn−Ｑpとする。各測定間隔において、Ｑnが小さい（＜Ｎ）ならば、Ｕはラインレート＋Ｌに設定される。Ｑnが非常に大きい（＞（Ｂ−Ｎ））ならば、Ｕは−Ｌに設定される。それ以外の場合には、Ｕは次の式(7)のように更新される。
【数１１】
ここでαuは、指数平均化ファクター(exponential averaging factor)であり、Ｙは後記する重み付け関数(weighting function)である。ＡＢＲバッファの占有が増加すれば(即ち、ΔＱ＞０のとき)、Ｕは減少する。同じ様に、ＡＢＲバッファの占有が減少すれば、Ｕは増加する。指数平均化ファクターαuは、Ｕのオシレーションを小さくするために用いられる。
【００３１】
リンク中のネット負荷(net load)が１００％よりも少ないとき、式(7)は、リンク帯域幅を十分に利用しようとして、Ｕの値を非常に高い値まで上昇させる。Ｕの値がそこまで高くなると、ネット負荷が後に増加したとき、Ｕの値は急速に低下することができない。それゆえ、アルゴリズムは、その高慣性(high inertia)により、速やかに反応することができず、ネットワーク(12)の負荷状態に迅速に変化するとができない。Ｕがそのような高い値まで上昇しないように、Ｕの上限を定めなければならない。これに対して、ＡＢＲセルのネット着信レートが、ＡＢＲＶＣの利用可能なネットサービスレートよりも大きい場合、ＡＢＲソースをしてそれらのセルレートを低下させるために、式(7)はＵの値を低下させる。ラウンドトリップ遅延(round trip delay)が大きい場合、ソースの反応は遅れる。この期間に、Ｕは非常に大きな負の値(negative value)まで低下する。Ｕの値がそこまで低くなると、後になって帯域幅が利用可能になったときに、正の値(positive value)へ迅やかに変化することができない。従って、Ｕの下限も同じ様に設定するのが有利である。Ｃabrの範囲は[０，Ｌ]であり、ＦＳの必要範囲もまた[０，Ｌ]であるので、Ｕの必要十分な範囲は[−Ｌ，＋Ｌ]である。
【００３２】
〔Ｎbsの計算〕
Ｎbe中のアクティブなＡＢＲＶＣは、スイッチ(34)のポートに、ＶＣごとのキューで認識可能な長さのものを一切作らない。従って、Ｎbsの良好な推定は、ＶＣごとのキュー長さ(per-VC queue length)が幾つかの低閾値Ｔを越えるＡＢＲＶＣの集合(set)である。Ｔの値の適当な範囲は、３乃至１０セルである。Ｎn bsは測定値を表し、Ｎbsは指数平均値を表すものとする。Ｎn bsは、次の要領で測定される。ポートは、初期状態では、Ｎn bsとＮbsは両方共、ゼロに設定される。セルがＡＢＲＶＣに到着し、そのＶＣごとのキュー長さをＴ−１からＴまで増加させる時はいつでも、Ｎn bsは増分される(incremented)。セルが出発し、ＶＣごとのキュー長さをＴからＴ−１まで減少させる時はいつでも、Ｎn bsは減分される(decremented)。これは、次の式(8)で表される。
【数１２】
なお、αnは指数平均化パラメータである。
【００３３】
〔ΔＱ重み付け関数〕
ＡＢＲスイッチ(34)アルゴリズムが、Ｑnの値を考慮せずに、ΔＱのみに基づいてＦＳの調節を行なう場合、Ｑnはゆっくりと高い値へドリフト、その結果、セルの損失は多くなる。従来のＡＢＲスイッチ(34)のアルゴリズムでは、閾値を用いてＡＢＲバッファをいくつかの領域に分割し、Ｑnがこれらの閾値を越えた時に、ＦＳの計算値を漸進的(progressively)に低下させることにより、このようなドリフトを防止していた。
【００３４】
ＳＥＲＩＡでは、より簡易な手法を用いており、ΔＱは、Ｑn(及びΔＱ)の関数であるＹによって重み付けされる。適当な重み付け関数として、次の例を挙げることができる。
Ｙ＝Ｑn／βＢ であって、
もし、（ΔＱ＜０）のとき、
Ｙ＝ｍａｘ(１−Ｙ，０) であり、
Ｂは、ＡＢＲＶＣが利用可能なバッファ空間の合計であり、βは、パラメータであり、現在０．８に設定されている。
【００３５】
ＡＢＲバッファの占有が増加している(即ち、ΔＱ＞０)と仮定すると、Ｕは減少するだろう。重み付けの結果、ＡＢＲバッファが略完全に占有される場合の方が、ＡＢＲバッファが殆ど占有されていない場合よりも、Ｕの減少は確実に多くなる。同じ様に、ＡＢＲバッファの占有が減少している(即ち、ΔＱ＜０)場合、Ｕは増加する。重み付けの結果、ＡＢＲバッファが殆ど占有されていない場合の方が、ＡＢＲバッファが略完全に占有される場合よりも、Ｕの増加は確実に多くなる。
【００３６】
ΔＱの重み付けにより、Ｑnは約βＢ／２となる。この結果、フリースロットを満たすために、ＡＢＲＶＣに属する十分なセルがＡＢＲバッファ内で確実に利用可能となる。さらに、シミュレーションの結果では、ΔＱを重み付けすることにより、従来のスイッチ(34)のアルゴリズムで採用された方法よりも、Ｑnの安定性がより高められることを示している。
【００３７】
図１は、ＡＴＭスイッチ(34)のポートの構成を簡略化して示している。出口ユニット(egress unit)は、ＦＳの計算、セルバッファの管理、スケジューリング、ポリーシング(policing)その他の機能を行なう。ＦＳの計算値は入口ユニット(ingress unit)へ送られ、該ユニットは、ＥＲ値をバックワードＲＭセルにスタンプする。セルはセルメモリに記憶され、ＶＣごとの情報はテーブルメモリに記憶される。ＳＥＲＩＡは、これまでの公平なシェアの厳密計算アルゴリズムよりも、高速ＡＴＭスイッチに組み込むのが遙かに簡単である。その理由は次の通りである。
【００３８】
ＳＥＲＩＡは、ＦＳを計算するのにどんなメモリアクセスを実行する必要がない。ＳＥＲＩＡで用いられる幾つかの変数は、出口ユニットのレジスタに保存することができる。これに対して、ＶＣごとのフラグ又はＶＣごとの変数を用いるスイッチ(34)のアルゴリズムでは、スロットごとにＯ(ｎ)回のテーブルメモリアクセスを実行する必要がある。
【００３９】
第２に、バックワードＲＭセルが到着するとき、ＶＣＩ／ＶＰＩのルックアップを実行する必要がない。計算されたＦＳは全てのＡＢＲＶＣに共通しており、ＲＭセルはそのＭＣＲを含んでいるので、ＶＣの特定の情報にアクセスするためにＶＣＩ／ＶＰＩをルックアップする必要はない。
【００４０】
第３に、ＳＥＲＩＡは、バッファの管理やサービスのスケジューリングに関して、特定の要求を一切行わない。従って、ＳＥＲＩＡは様々なスケジューリングとバッファ管理のスキームと共に作業することができる。
【００４１】
〔公平性(フェアネス)〕
利用可能な帯域幅は、数多くの公平性(フェアネス)の基準(criteria)を用いて分配されることができる。ＭＣＲ＋均等シェアの公平性(MCR plus equal share fairness)の基準では、利用可能な帯域幅は、アクティブＡＢＲＶＣの間で等しく分けられる。ＭＣＲ比例(proportional to MCR)の基準では、利用可能な帯域幅は、ＭＣＲに比例して分けられる。ＭＣＲ比例基準の主な欠点は、ＭＣＲを有しないＡＢＲＶＣが追加の帯域幅を全く獲得できないことである。このため、多くのＡＢＲアルゴリズムでは、ＭＣＲ＋均等シェアの公平性基準となるように設計されている。図４４及び図４５に示された疑似コードは、ＭＣＲ＋均等シェアの公平性がもたらされるＳＥＲＩＡを示している。それは、ＡＴＭフォーラム[ATM Forum. Traffic management specification version 4.0, April 1996］に掲げられたその他の公平性基準に修正することは容易である。
【００４２】
最大−最小フェアネスの定義[D. Bertsekas and R. Gallager. Data Networks, Second Edition. Printice Hall, Inc., 1992]は、ＡＴＭフォーラムドキュメント[N. Yin. Fairness definition in ABR service model. ATM Forum Document: AF-TM 94-0928R2, Number 1994]のＭＣＲも含まれるように拡張された。拡張された最大−最小フェアネス基準の定義は、次の通りである。ＦＳを式(2)の唯一の解とすると、次式の関係を有するとき、ｉ番目のＡＢＲＶＣがｍｉｎ(Ｂi，ＭＣＲi＋ＦＳ)の帯域幅を割り当てられる場合にも、拡張された最大−最小フェアネス基準は充足される。
【数１３】
ＳＥＲＩＡは、拡張された最大−最小フェアネス基準を満たす。
【００４３】
〔バーストＶＢＲＶＣが存在するときのロバストパフォーマンス〕
ＡＢＲスイッチ(34)アルゴリズムの実テストは、非常にバーストなＶＢＲストリームの存在下でのパフォーマンスである。即ち、ＡＢＲＶＣは、割り当てられていない帯域幅を利用しなければならないだけでなく、ＣＢＲ及びＶＢＲＶＣが一時的に使用していない帯域幅を使用することができなければならない。多くのＡＢＲアルゴリズムは、このようなシナリオではうまく実行できない[F.M. Chiussi and Y.T. Wang. An ABR rate-based congestion control algorithm for ATM switches with per-VC queueing. In GLOBECOM ’ 97, pages 771-778, 1997参照]。ＳＥＲＩＡの強さの１つは、非常にバーストなＶＢＲストリームのときにも、非常にうまく実行できることである。
【００４４】
〔多数のＡＢＲＶＣが存在するときのロバストパフォーマンス〕
公平なシェアの近似計算アルゴリズムは、ＮaまたはＮbsのトラックを保持しないので、ＡＢＲＶＣの数が多いと、大きなオシレーションを受ける。このアルゴリズムが自由帯域幅を検出すると、各ＡＢＲＶＣのＦＳを増加させて、着信レートを大幅に増加させる。これによって、アルゴリズムはそのＦＳを急に低下させるので、各ＡＢＲＶＣのセルレートは減少する。これは、オシレーションを生じ、過渡期間(transient period)は長くなる。この問題は、公平なシェアの厳密計算アルゴリズムでは起こらない。シミュレーション結果では、多数のＡＢＲＶＣが存在するときにも、ＳＥＲＩＡのロバストパフォーマンスを示している。
【００４５】
〔パーキングロットのようなトポロジにおけるロバストパフォーマンス〕
重要なことは、スイッチ(34)のアルゴリズムは、ホップの数が少ないＡＢＲＶＣが有利となるように、ホップの数が多いＡＢＲＶＣを識別しないことである。従来のスイッチ(34)のアルゴリズムはこの問題を抱えており、文献の中で、「ビートダウン問題(beat-down problem)」と称されている[F. Bonomi and K. Fendick. The rate-based flow control framework for the available bit rate ATM service. IEEE Networks, 9(2):25-39, March/April 1995]。シミュレーションの結果でも、ＳＥＲＩＡは、数多くのホップを有するＡＢＲＶＣを区別しないことが示されている。
【００４６】
〔シミュレーション結果〕
全てのリンクはＯＣ−３リンク(１５５.５２Ｍビット／秒)であり、スイッチは、８ＫセルのＡＢＲバッファサイズを有するＳＥＲＩＡを用いている。スイッチは、ＶＣごとのキューイングと、簡易に重み付けされたラウンドロビン(Weighted Round Robin：ＷＲＲ)スケジューラ(22)を用いている。ＷＲＲスケジューラ(22)の重み付けは、ＡＢＲＶＣの場合にはＭＣＲに比例して設定され、ＶＢＲＶＣの場合にはＰＣＲに比例して設定される。測定間隔Ｎは６４に設定される。ＶＣごとキューの閾値Ｔは５セルに設定される。指数平均化パラメータαn及びαuは共に１／８に設定される。
【００４７】
広帯域端末装置(Broadband Terminal Equipments：ＢＴＥ)は、ＡＴＭフォーラムの文献の中で定義されたエンドシステムアルゴリズムを用いている[ATM Forum. Traffic management specification version 4.0, April 1996]。ＢＴＥアルゴリズムのパラメータ値を表２に示す。これらの値は、ＡＴＭフォーラムの文献の中で推奨されるデフォールト値と同一である[ATM Forum. Traffic management specification version 4.0, April 1996]。これらの文献はその引用を以て本願への記載加入とする。
【００４８】
ＶＢＲソースは、５０msのＯＮとＯＦＦの周期で、ＯＮ／ＯＦＦのストリームを発生させる。ＯＮ周期では、ソースは指示されたピークセルレート(Peak Cell Rate：ＰＣＲ)でセルを送信し、ＯＦＦ周期では、ソースはアイドル状態である。
【００４９】
シミュレーション実験で用いられる多くのＡＢＲＶＣは持続性である(persistent)。即ち、それらは、ネットワークから指示された許可セルレート(Allowed Cell Rate：ＡＣＲ)と等しいレートで送信するのに十分なセルを常に有している。
【００５０】
【表２】
【００５１】
〔実験１〕
〔セットアップ〕
図２は、使用したトポロジを示している。セットアップは、１０個のＡＢＲソースからなる。ＡＢＲ１のＭＣＲは５０Ｍビット／秒、ＡＢＲ２のＭＣＲは１０Ｍビット／秒である。一方、ＡＢＲ３−ＡＢＲ１０のＭＣＲは１Ｍビット／秒である。ＡＢＲ２以外の全てのＡＢＲＶＣは持続性であるが、ＡＢＲ２はソースでボトルネックされて、５Ｍビット／秒となる。リンクＬ１−Ｌ１０とＬ１ｓ−Ｌ１０ｓの長さは１００kmであるのに対し、リンクＬａの長さは１０００kmである。
【００５２】
〔考察〕
実験１の結果を図３乃至図１２に示す。リターンＲＭセルのソースに対してネットワーク(12)により指示されたＡＣＲ値のプロット、実際のＡＢＲソースレート、並びにボトルネックスイッチｓｗ１のパラメータのプロット及びソースレートが示されている。式(2)に代入してＦＳの解を求めた結果を式(9)に示している。
【数１４】
【００５３】
従って、ＡＢＲ１は、６０.２８Ｍビット／秒の帯域幅を得ることになる。ＡＢＲ２は５Ｍビット／秒だけ使うことになる。ＡＢＲ３−ＡＢＲ１０は、各々が１１.２８Ｍビット／秒を得る。シミュレーションの結果では、これらの値と一致している。ＡＣＲ中の初期オーバーシュート(initial overshoots)は、ＡＢＲバッファを安定点まで満たすためであることに留意すべきである。
【００５４】
〔実験２〕
〔簡易トポロジにおける１０個のＡＢＲＶＣと１個のバーストＶＢＲＶＣ〕
〔セットアップ〕
使用したトポロジを図１４乃至図２１に示す。セットアップは、１０個のＡＢＲＶＣと１個のバーストＶＢＲソースからなる。ＡＢＲＶＣは全て持続性である。ＡＢＲ１のＭＣＲは５０Ｍビット／秒であり、その他のＡＢＲＶＣのＭＣＲは１Ｍビット／秒である。ＶＢＲ１のＰＣＲは５０Ｍビット／秒である。リンクＬ１−Ｌ１１及びＬ１ｓ−Ｌ１１ｓの長さは１０kmであるのに対し、リンクＬａ及びＬｂの長さは各々１０００kmである。
【００５５】
〔観察〕
実験２の結果を図１４乃至図２１に示す。ＡＣＲは、ＶＢＲソースがＯＦＦのときに起こるパルスでパルス整形される(pulse shaped)。ＶＢＲがＯＮのとき、Ｃabr＝Ｌ−ＶＢＲレート｝−ΣＭＣＲ＝１５５.５２−５０−（５０＋９×１）＝４６.５２Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて４６.５２／１０＝４.６５Ｍビット／秒を得る。ＶＢＲがＯＦＦのとき、Ｃabr＝１５５.５２−０−（５０＋９×１０）＝９６.５２Ｍビット／秒である。従って、各々のＡＢＲＶＣは、それらのＭＣＲに加えて９６.５２／１０＝９.６５Ｍビット／秒を得る。
【００５６】
〔実験３〕
〔簡易トポロジにおける１００個のＡＢＲＶＣと１個のバーストＶＢＲＶＣ〕
〔セットアップ〕
使用したトポロジは図２のものと同様であるが、１００個の全く同じＡＢＲソース及び１個のバーストＶＢＲソースを用いている。全てのＡＢＲＶＣは持続性であり、それらのＭＣＲは１.０Ｍビット／秒である。ＶＢＲ１のＰＣＲは５５Ｍビット／秒である。リンクＬ１−Ｌ１０１及びＬ１ｓ−Ｌ１０１ｓの長さは１０kmであり、一方、リンクＬａの長さは１０００kmである。
【００５７】
実験３の結果を図２２乃至図２９に示す。ＡＣＲは、ＶＢＲソースがＯＦＦのときに起こるパルスでパルス整形される。ＶＢＲ１がＯＮのとき、Ｃabr＝１５５−５５−（１００×１）＝０Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲ＝１.０Ｍビット／秒だけを得る。ＶＢＲ１がＯＦＦのとき、Ｃabr＝１５５−０−（１００×１）＝５５Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて５５／１００＝０.５５Ｍビット／秒を得る。即ち、その各々は１.５５Ｍビット／秒を得る。
【００５８】
〔実験４〕
〔パーキングロットトポロジにおける５個のＡＢＲＶＣと１個のバーストＶＢＲＶＣ〕
パーキングロットトポロジを図３０に示す。全てのＡＢＲＶＣは持続性である。ＡＢＲ２以外のＡＢＲＶＣのＭＣＲは全て１０Ｍビット／秒であるが、ＡＢＲ２のＭＣＲは２０Ｍビット／秒である。ＶＢＲ１のＰＣＲは９０Ｍビット／秒である。リンクＬ１−Ｌ５及びＬ１ａの長さは各々が１０kmであるのに対し、中央リンクＬａ−Ｌｅの長さは各々が１００kmである。
【００５９】
実験４の結果を図３１乃至図４０に示す。ＡＣＲは、ＶＢＲソースがＯＦＦのときに起こるパルスでパルス整形される。ＶＢＲがＯＮのとき、Ｃabr＝１５５−９０−（２０＋４×１０）＝５Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて５／５＝１Ｍビット／秒を得る。ＶＢＲがＯＦＦのとき、Ｃabr＝１５５−０−（２０＋４×１０）＝９５Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて９５／５＝１９Ｍビット／秒を得る。
【００６０】
シミュレーションの結果では、ＳＥＲＩＡは常に１００％のリンク帯域幅を獲得し、ＡＢＲバッファ占有の平均値はβＢ／２＝３２７６セルに近いことを示している。ＳＥＲＩＡは、ＡＢＲバッファの占有制御をきっちりと行なう。
【００６１】
実験１は、最大−最小フェアネスを得るために、ＳＥＲＩＡが、未使用の帯域幅をＡＢＲ２からスイッチ(34)ポートでボトルネックされた他のＡＢＲへ再分配する方法を示している。実験２、実験３及び実験４の結果に示されるように、ＳＥＲＩＡは、従来の多くのアルゴリズムとは異なり、非常にバーストなＶＢＲストリームがあるときでさえ、うまく実行する。実験３の結果は、多くの持続性ＡＢＲＶＣを取り扱う際、ＳＥＲＩＡがロバストであることを示している。実験４の結果では、ＳＥＲＩＡは、長いパスを有するＡＢＲＶＣを区別しない(即ち、ビートダウン問題がない)ことを示している。
【００６２】
ここに開示したＳＥＲＩＡは、公平なシェアを厳密に計算する新規なＡＢＲスイッチ(34)アルゴリズムである。それは、簡易で精確な方法により、スイッチ(34)でボトルネックされたＶＣに対して、その他の場所でボトルネックされたＶＣから帯域幅を分配する。ＳＥＲＩＡのその他新しい特徴には、これまでの方法よりも、より簡易でより安定したバッファ占有がもたらされるバッファ占有制御メカニズムがある。
【００６３】
シミュレーションの結果では、ＳＥＲＩＡは、最大−最小フェアネス、定常状態への迅速なコンバージェンス、リンクの１００％利用、及び安定したＡＢＲバッファ占有がもたらされることを示している。また、シミュレーションの結果では、ＳＥＲＩＡは、非常にバーストなＶＢＲストリームの存在下でも、ロバストであり、うまく作業が行われることを示している。
【００６４】
発明を例示するために、実施例を参照して発明を詳細に説明したが、これら説明は、単なる例示であって、当該分野の専門家であれば、特許請求の範囲に記載された発明の精神及び範囲から逸脱することなく、発明に種々の変形をなすことはできると理解されるべきである。
【図面の簡単な説明】
【図１】ＡＴＭスイッチポートの構成の概要説明図である。
【図２】実験１のトポロジを示す図である。
【図３】実験１の結果を示す図である。
【図４】実験１の結果を示す図である。
【図５】実験１の結果を示す図である。
【図６】実験１の結果を示す図である。
【図７】実験１の結果を示す図である。
【図８】実験１の結果を示す図である。
【図９】実験１の結果を示す図である。
【図１０】実験１の結果を示す図である。
【図１１】実験１の結果を示す図である。
【図１２】実験１の結果を示す図である。
【図１３】実験２のトポロジを示す図である。
【図１４】実験２の結果を示す図である。
【図１５】実験２の結果を示す図である。
【図１６】実験２の結果を示す図である。
【図１７】実験２の結果を示す図である。
【図１８】実験２の結果を示す図である。
【図１９】実験２の結果を示す図である。
【図２０】実験２の結果を示す図である。
【図２１】実験２の結果を示す図である。
【図２２】実験３の結果を示す図である。
【図２３】実験３の結果を示す図である。
【図２４】実験３の結果を示す図である。
【図２５】実験３の結果を示す図である。
【図２６】実験３の結果を示す図である。
【図２７】実験３の結果を示す図である。
【図２８】実験３の結果を示す図である。
【図２９】実験３の結果を示す図である。
【図３０】実験４のトポロジを示す図である。
【図３１】実験４の結果を示す図である。
【図３２】実験４の結果を示す図である。
【図３３】実験４の結果を示す図である。
【図３４】実験４の結果を示す図である。
【図３５】実験４の結果を示す図である。
【図３６】実験４の結果を示す図である。
【図３７】実験４の結果を示す図である。
【図３８】実験４の結果を示す図である。
【図３９】実験４の結果を示す図である。
【図４０】実験４の結果を示す図である。
【図４１】本発明の装置の概略説明図である。
【図４２】本発明の方法のフローチャート図である。
【図４３】本発明のスイッチの概略説明図である。
【図４４】ＳＥＲＩＡの疑似コードを示す図である。
【図４５】ＳＥＲＩＡの疑似コードを示す図である。
【符号の説明】
(10) セルスイッチング装置
(12) ネットワーク
(16) メモリメカニズム
(20) サーバ
(22) スケジューラ
【発明の属する技術分野】
本発明は、メモリメカニズムの占有のファンクション(function)として、スケジューラを用いてセルのスイッチングを行なう方法及び装置に関するものである。より具体的には、本発明は、ＡＴＭスイッチの与えられたリンクにおけるＡＢＲのトラフィックフローを制御するために、メモリメカニズムの占有のファンクションとして、スケジューラを用いて、ＡＢＲＶＣへ明示的レートをスタンプするＡＴＭスイッチに関する。
【０００２】
【従来の技術】
ＡＴＭネットワークのアベーラブルビットレートサービス(Available Bit Rate：ＡＢＲ)は、時変帯域幅(time-varying bandwidth)に適応可能で、セル損失率の低いバーストデータへの適用に限られていた[ATM Forum. Traffic management specification version 4.0, April 1996参照]。ＡＢＲの仮想コネクション(Virtual Connections：ＶＣ)は、利用可能な帯域幅をかなり共有している。ここで、利用可能な帯域幅とは、固定ビットレート(Constant Bit Rate：ＣＢＲ)と可変ビットレート(Variable Bit Rate：ＶＢＲ)のトラフィックストリームによる帯域幅の残りのことである。ＡＢＲＶＣは、利用可能な帯域幅について公平なシェア(fair share)を獲得するだけでなく、最小セルレート(Minimum Cell Rate：ＭＣＲ)を特定することができ、ＡＢＲＶＣが一旦許可を与えられると、そのレートは保証される。
【０００３】
ネットワークは、ＡＢＲソースに対して、利用可能な帯域幅に関するフィードバック情報を提供する。フィードバック制御方式に関する研究は次の２つのものがある。クレジットベース(credit-based)の方式では、ネットワークのノードは、上流のノードにＶＣごとのクレジットを送り、上流ノードでは、ＶＣに属するセルを送信する際に、そのクレジットを使い切る。レートベース(rate-based)の方式では、ソースはリソースマネジメント(Resource Management：ＲＭ)のセルを定期的に送り、このセルは、目的地(destination)に達するとリターンする。ＶＣルートにあるスイッチは、リターンするＲＭセルの輻輳状況(congestion status)を表示する。
【０００４】
クレジットベースの方法(例えば、[H. Kung and R. Morris. Credit-based flow control for ATM networks. IEEE Networks, 9(2):40-48, March/April 1995]を参照)は、概念的にはより簡単であり、セル損失が起こらないことを保証しているけれども、ＡＴＭフォーラムは、レートベースの方式(例えば、[F. Bonomi and K. Fendick. The rate-based flow control framework for the available bit rate ATM service. IEEE Networks, 9(2):25-39, March/April 1995]を参照)を選択した。その理由は、レートベースの方式の方が、構造的な自由度(フレキシビリティ)が大きいためである。レートベースの方法の場合、スイッチアルゴリズムが複雑であるので、輻輳ビット(congestion bit)のマーキングは簡単であるが、明示的レート(Explicit Rate：ＥＲ)の計算は複雑である。
【０００５】
ＡＴＭフォーラムは、エンドシステムの動作(behavior)を規定したが、ＡＢＲスイッチアルゴリズムのデザインの詳細については、ＡＴＭスイッチの設計者に委ねていた。これまでに、幾つかのＥＲ計算スイッチアルゴリズムが提案されているが、それらのアルゴリズムは、公平なシェアを厳密に計算するアルゴリズムと、公平なシェアを近似的に計算するアルゴリズムの２つのカテゴリーに分類される。公平なシェアの厳密計算アルゴリズムとして、例えばＥＲＩＣＡ、ＥＲＩＣＡ＋がある[R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S., and R. Viswanathan. ERICA switch algorithm: A complete description. ATM Forum Document Number: ATM Forum/96-1172, August 1996]。ＥＤＥＲＡ[N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997]は、スイッチ出力ポートのネット利用可能帯域幅と、ポートを通過するアクティブＡＢＲＶＣの数を測定する。次に、利用可能な帯域幅をアクティブＡＢＲＶＣの数で割ることにより、公平なシェアの計算が行われる。一方、公平なシェアの近似的計算アルゴリズムとして、例えばＰＲＣＡ、ＥＰＲＣＡがある[L. Roberts. Enhanced PRCA (proportional rate-control algorithm), ATM Forum Document: AF-TM 94-0735R1, August 1994。ＤＭＲＣＡとＥＤＭＲＣＡ[F. M. Chiussi and Y. T. Wang. An ABR rate-based congestion control algorithm for ATM switches with per-VC queueing. In GLOBECOM '97, pages 771-778, 1997]は、浮動小数点(floating-point)の除算は行わない。それは、ポート変数を維持し、該ポート変数はスイッチ出力ポートの輻輳状況に応じて調節される。各ＶＣのＥＲは、これらのポート変数から求められる。一般に、公平なシェアの計算アルゴリズムは、厳密計算アルゴリズムの方が近似的計算アルゴリズムよりも、性能的にすぐれている[N. Ghani. Available Bit Rate Service in ATMNetworks. PhD thesis, University of Waterloo, 1997参照]。
【０００６】
しかし、公平なシェアの厳密計算方法は重大な問題があり、それは、スイッチでボトルネック(bottle-necked)されたＡＢＲＶＣに対して、どこか他の場所でボトルネックされたＡＢＲＶＣから帯域幅を再分配することである。例えば、各々がゼロＭＣＲを有する３個のアクティブＡＢＲＶＣを考えてみることにする。ネット利用可能な帯域幅を３０Ｍビット／秒とし、各々のＡＢＲＶＣの公平なシェアを１０Ｍビット／秒とする。最初の２つのＡＢＲＶＣはスイッチでボトルネックされると仮定し、第３のＡＢＲＶＣはどこか別のスイッチでボトルネックされると仮定する。なお、この別のスイッチは、第３のＡＢＲＶＣが５Ｍビット／秒を超えないようにしている。これが意味するのは、３０−（１０＋１０＋５）＝５Ｍビット／秒の帯域幅は、最初の２つのＡＢＲＶＣの間で再分配されなければならないということである。よって、３つのＶＣの公平なシェアは、それぞれ、１２.５、１２.５、５.０Ｍビット／秒となる。
【０００７】
輻輳回避のための明示的レート表示(Explicit Rate Indication for Congestion Avoidance; ＥＲＩＣＡ)、及びＥＲＩＣＡ＋[R. Jain, S. Kalyanaraman, R.Goyal, Fahmy S., and R. Viswanathan. Determining the number of activeABR sources in switching algorithms. ATM Form Document Number: ATM Forum/98-0154, February 1998; R. Jain, S. Kalyanaraman, R. Goyal, Fahmy S.,and R. Viswanathan. ERICA switch algorithm: A complete descripition.ATM Form Document Number: ATM Forum/96-1172, August 1996]は、再分配のために複雑なスキームを採用しており、ＶＣごとのサービスレートの測定を必要とする。例えば、ＥＲＩＣＡ＋は、利用可能な帯域幅を、アクティブＡＢＲＶＣの合計数ではなく、アクティブＡＢＲＶＣの有効数で割ることにより、再分配の問題を解決している。アクティブＡＢＲＶＣの有効数は次のように定義される。スイッチでボトルネックされるＡＢＲＶＣは１としてカウントされ、他の場所でボトルネックされるＡＢＲＶＣは、（実際のＶＣレート／公平なシェア）に等しい部分としてのみカウントされる。このように、アクティブＡＢＲＶＣの有効数を計算するためには、各ＶＣのセルレートは、スイッチポートで測定されなければならない。ＶＣレートの測定には、Ｏ(ｎ)個の空間コンプレキシティ(space complexity)及び／又はＯ(ｎ)個の時間的コンプレキシティ(time complexity)を有するアルゴリズムを必要とする。ここで、ｎはポートを通過するＶＣの数である。このため、このようなスイッチアルゴリズムを高速ハードウェアで実行するには、費用が非常にかかる。
【０００８】
分散を向上させた明示的レートアルゴリズム(Enhanced Distributed Explicit Rate Algorithm(ＥＤＥＲＡ)[N. Ghani. Available Bit Rate Service in ATM Networks. PhD thesis, University of Waterloo, 1997]は、スイッチでボトルネックされたＡＢＲＶＣと、他の場所でボトルネックされたＡＢＲＶＣのトラックを、明示的に保持することにより、再分配の問題を解決する。ＥＤＥＲＡでは、ＡＢＲソースが、その分割された平均ソースレート(Segmented Average Source Rate：ＳＡＳＲ)をＲＭセルに表示すると仮定している。ここでＳＡＳＲは、２つのＲＭセル間のデータセル数の、２つのＲＭセル間の時間に対する比として規定される。ＶＣがネットワーク内のある地点でボトルネックされると、ＳＡＳＲは、許可セルレート(Allowed Cell Rate：ＡＣＲ)よりも小さくなることに留意すべきである。ＡＴＭフォーラムの標準[ATM Forum. Traffic management specification version 4.0, April 1996]では、ＲＭセルにＳＡＳＲ表示を含まないようにすることを決定したので、ＥＤＥＲＡスキームは適宜修正されなければならない。このような修正を行うためには、スイッチ出力ポートでＶＣレートを測定する必要がある。
【０００９】
【発明が解決しようとする課題】
本発明は、新規なスイッチアルゴリズム、つまり、簡易な明示的レート表示アルゴリズム(Simple Explicit Rate Indication Algorithm：ＳＥＲＩＡ)に関するものである。ＥＲＩＣＡ、ＥＲＩＣＡ＋及びＥＤＥＲＡとは異なり、ＳＥＲＩＡは、ＶＣごとのレートを測定する必要がない。実際に、ＳＥＲＩＡは、これまでに提案された公平なシェアの厳密計算スイッチアルゴリズムよりもはるかに簡単である。つまり、セル着信(cell arrival)やセル出発(cell departure)の如きイベント(events)の取扱いに必要な算術的及び論理的な演算の数は少なく、ＶＣの数から独立している。ＳＥＲＩＡが簡単になると、高速のインプリメンテーションにとって特に魅力的である[M. Vishnu, D. Basak, and H.S. Kim. Method and apparatus for a simple explicit rate indication algorithm (SERIA) U.S. Patent Pending, 1998]。
【００１０】
広範なシミュレーションを行なった結果、ＳＥＲＩＡは、最大−最小フェアネス(max-min fairness)、つまり最大−最小公平性を提供するもので、定常状態に迅速にコンバージ(converge)し、リンク帯域幅を１００％利用し、バッファ制御をしっかりと維持することを示している。
【００１１】
【課題を解決するための手段】
本発明は、ネットワークのエンティティからセルをスイッチングする装置に関する。セルスイッチング装置は、ネットワークからの全てのセルを受信する入力メカニズムを具えている。装置は、入力メカニズムが受信した全てのセルを格納するメモリメカニズムを具えており、全てのセルは装置内に格納される。メモリメカニズムは、入力ポートメカニズムに接続されている。メモリメカニズムは、セルが占有する占有場所(occupancy)を有している。セルスイッチング装置は、該装置からネットワークへセルを送信する出力メカニズムを具えている。装置は、あるサービスレートでセルにサービスを提供するサーバを具えている。サーバは、メモリメカニズムと出力メカニズムに接続されている。装置は、メモリメカニズムのセルに対してサービスを提供するスケジューラを具えている。スケジューラは、サーバとメモリメカニズムに接続されている。
【００１２】
本発明は、セルをスイッチングする方法に関する。この方法は、Ｊ個(但し、Ｊは１以上)のエンティティのセルを、スイッチの入力メカニズムでネットワークから受信するステップを含んでいる。次に、セルをスイッチのメモリメカニズムに格納するステップがある。次に、サーバにより、メモリメカニズム内のセルへサービスを提供するステップがある。次に、メモリメカニズムにセルが占有された結果、メモリメカニズムのセルが、スイッチのサーバからのサービスを受信するとき、スイッチのスケジューラを用いてスケジューリングを行なうステップがある。
【００１３】
本発明は、ＡＴＭスイッチの与えられたリンクにおけるＡＢＲのトラフィックフローを制御するために、ＡＢＲＶＣへ明示的レートをスタンプするためのＡＴＭスイッチに関する。本発明の装置は、ＶＣへのトラフィックをスイッチへキャリーする入力ポートメカニズムを具えている。装置は、入力ポートメカニズムが受信したＶＣの全てのセルを格納するためのメモリメカニズムを具えており、セルはスイッチの中に格納される。メモリメカニズムは、入力ポートメカニズムに接続されている。メモリメカニズムは、ＶＣのセルを占有する占有場所を有している。装置は、セルをスイッチからネットワークへ送信する出力ポートメカニズムを具えている。装置は、ＶＣのセルを、入力ポートメカニズムから出力ポートメカニズムへスイッチするためのスイッチングファブリックを具えている。装置は、バックワード(backward)ＲＭセルにおける明示的レート(ＥＲ)とスタンプレートを計算するＡＢＲ−ＥＲメカニズムを具えている。装置は、あるサービスレートでＶＣのセルへサービスを提供するサーバを具えている。サーバは、メモリメカニズム及び出力ポートメカニズムに接続されている。装置は、ＶＣのセルによるメモリメカニズムの占有のファンクションとして、ＶＣのセルへサービスを提供するスケジューラを具えている。スケジューラは、サーバとメモリメカニズムに接続されている。
【００１４】
【発明の実施の形態】
図面を参照すると、同一又は類似の要素については、幾つかの図を通して、同じ引用符号を付している。特に図４１を参照すると、ネットワーク(12)のエンティティからのセルをスイッチングする装置(10)が示されている。装置(10)は、ネットワーク(12)から全てのセルを受信する入力メカニズム(14)を具えている。装置(10)は、入力メカニズム(14)が受信した全てのセルを格納するメモリメカニズム(16)を具えており、全てのセルは、装置(10)の中に記憶される。メモリメカニズム(16)は、入力ポートメカニズムに接続されている。メモリメカニズム(16)は、セルの占有場所(occupancy)を有している。装置(10)は、セルを装置(10)からネットワーク(12)へ送信する出力メカニズム(18)を具えている。装置(10)は、あるサービスレートでセルへサービスを提供するサーバ(20)を具えている。サーバ(20)は、メモリメカニズム(16)及び出力メカニズム(18)に接続されている。装置(10)は、セルによるメモリメカニズムの占有のファンクションとして、セルへサービスを提供するスケジューラ(22)を具えている。スケジューラ(22)は、サーバ(20)及びメモリメカニズム(16)に接続されている。
【００１５】
望ましくは、入力メカニズム(14)はＪ個の入力ポートメカニズム(24)を含んでおり、Ｊは２以上の整数である。全ての入力ポートメカニズム(24)は、一緒に、ある着信レートでセルを受信することが望ましく、ここでスケジューラ(22)は、メモリメカニズム(16)の占有を監視する監視メカニズム(26)と、セルが全ての入力ポートメカニズム(24)により受信された着信レートを変更させる変更メカニズム(28)を含んでいる。
【００１６】
望ましくは、監視メカニズム(26)は、セルのメモリメカニズム(16)への着信レートと、メモリメカニズム(16)のセルがサーバ(20)から利用可能な提供レートとの差に基づいて、エンティティが利用可能な追加の帯域幅を決定する。各エンティティは最小セルレートを有することが望ましく、変更メカニズム(28)は、サービスを要求するエンティティの各々に割り当てられべき追加の帯域幅の公平なシェアを計算する。
【００１７】
望ましくは、入力ポートメカニズム(24)の各々は、エンティティに対応するセルのエンティティ着信レートを有しており、変更メカニズム(28)は、入力ポートメカニズムを通じてセルを供給する各エンティティのエンティティ着信レートを変更するので、全ての入力ポートメカニズム(24)からのセルの着信レートは、メモリメカニズム(16)のセルがサーバ(20)から利用可能なサービスレートに等しく、前記着信レートは全てのエンティティ着信レートの合計となる。変更メカニズム(28)は、入力ポートメカニズムを通じてセルを供給する各エンティティのエンティティ着信レートを、等量だけ変更することが望ましい。
【００１８】
望ましくは、メモリメカニズム(16)は、装置(10)が受信した全てのセルが格納される共有メモリメカニズム(shared memory mechanism)(30)か、又は別に設けたバッファ(32)のどちらか一方から構成され、各入力ポートメカニズムは、関連入力ポートメカニズム、又は各エンティティに対して独立して設けられたバッファ(32)だけが受信した全てのセルを格納する関連バッファ(associated buffer)を有している。監視メカニズム(26)は、メモリメカニズム(16)の中でサーバ(20)からのサービスを待機するセルのバックログ(backlog)を有するエンティティの個数を監視することが望ましい。
【００１９】
エンティティはＡＢＲＶＣを含むことが望ましい。エンティティは、ＣＢＲ／ＶＢＲＶＣを含むことが望ましい。監視メカニズム(26)は、サーバ(20)からのサービスを待機するセルのバックログを有するＡＢＲＶＣの数、即ち、提供されたＣＢＲ／ＶＢＲＶＣからのＣＢＲ／ＶＢＲセル(ｎvbr)の数を監視することが望ましい。
【００２０】
望ましい実施例の実施において、スイッチ(34)の出力ポートメカニズム(40)を考える。Ｎαは、ポートを通過するアクティブＡＢＲＶＣの集合(set)を表すものとする。ＡＢＲＶＣは、そのソースがゼロ以外のレートでセルを送信する場合、アクティブである。集合Ｎαは、次式で示されるように、ＮbsとＮbeに分けられた２組の集合の和である。
【数３】
【００２１】
Ｎbe＝φ(Ｎbeが空集合)のとき、公平なシェア(Fair Share：ＦＳ)は、式(1)に等しい。
【数４】
【００２２】
Ｎbe≠φ(Ｎbeが空集合でない)のとき、Ｎbe中のＡＢＲＶＣは、割り当てられたＦＳを利用することができないため、結果として、リンク帯域幅の利用不足(under-utilization)となる。リンク帯域幅の１００％利用を達成するには、Ｎbe中のＡＢＲＶＣが未使用の帯域幅は、Ｎbs中のＡＢＲＶＣに再分配されなければならない。未使用の帯域幅の再分配は、公平なシェアの厳密な計算ＡＢＲアルゴリズムにおいて、重大な要素の１つである。
【００２３】
Ｂiは、ｉ番目のＡＢＲＶＣが利用できる帯域幅の最大量を表すものとし、Ｌはリンク帯域幅を表すものとする。ｉ番目のＡＢＲＶＣがＮbsにある場合には、Ｂi＝Ｌと設定する。帯域幅の再分配により、ＦＳの値は次の式(2)、即ち式(3)、を満足させるようにする。
【数５】
【数７】
ＦＳを計算するために、公平なシェアの厳密な計算スイッチ(34)のアルゴリズムは、次式のトラックを保持(keep)する必要があり、これは些細なタスクではない。
【数８】
Ａのトラックをキープする代わりに、それを推定(estimation)することができる。Ａがアンダーエスティメート(又はオーバーエスティメート)される場合、つまり、Ａが低く推定(又は高く推定)される場合、ＡＢＲＶＣセルのネット着信レートは、ＡＢＲＶＣが利用可能なネットサービスレートよりも少なく(又は多く)なるであろう。ＳＥＲＩＡは、Ａの推定にこの事実を利用する。ＳＥＲＩＡは、Ｕで表される追加の帯域幅パラメータと呼ばれる変数Ｕを維持しており、この変数は、式(5)で示されるように、公平なシェアを計算するときにＣabrへ加算される。
【数９】
【００２６】
本明細書中で用いられる記号を表１にリストアップしている。ＳＥＲＩＡの疑似コードの完全な記載は、図４４及び図４５に示している。
【００２７】
【表１】
〔Ｃabrの計算〕
Ｎ個のスロットの各測定期間に、ＳＥＲＩＡは、帯域幅が保証されたＶＣ(即ちＣＢＲＶＣと、ＶＢＲＶＣ)から提供されたセルｎgのトラックを保持する。なお、ＣＢＲＶＣとＶＢＲＶＣによる帯域幅の残り(bandwidth leftover)は次の式(6)に等しい。
【数１０】
〔Ｕの計算〕
前述したように、ＳＥＲＩＡは、ＡＢＲセルのネット着信レートがＡＢＲＶＣの利用可能なネットサービスレートに等しくなるまで、追加の加帯域幅パラメータＵを調節する。ＳＥＲＩＡは、ＡＢＲＶＣのネット着信レートが、ＡＢＲＶＣの利用可能なネットサービスレートよりも小さい(大きい)とき、Ｕを増加(減少)させる。着信レートとサービスレートとの差は、ＡＢＲバッファの占有が変化するレートにより決定される。
【００３０】
Ｂは、ＡＢＲバッファのサイズとし、Ｑnは、現在の測定間隔のＡＢＲバッファ占有の総計(aggregate)を表し、Ｑpは、以前の測定間隔のＡＢＲバッファ占有の総計を表すものとする。そして、ΔＱ＝Ｑn−Ｑpとする。各測定間隔において、Ｑnが小さい（＜Ｎ）ならば、Ｕはラインレート＋Ｌに設定される。Ｑnが非常に大きい（＞（Ｂ−Ｎ））ならば、Ｕは−Ｌに設定される。それ以外の場合には、Ｕは次の式(7)のように更新される。
【数１１】
【００３１】
リンク中のネット負荷(net load)が１００％よりも少ないとき、式(7)は、リンク帯域幅を十分に利用しようとして、Ｕの値を非常に高い値まで上昇させる。Ｕの値がそこまで高くなると、ネット負荷が後に増加したとき、Ｕの値は急速に低下することができない。それゆえ、アルゴリズムは、その高慣性(high inertia)により、速やかに反応することができず、ネットワーク(12)の負荷状態に迅速に変化するとができない。Ｕがそのような高い値まで上昇しないように、Ｕの上限を定めなければならない。これに対して、ＡＢＲセルのネット着信レートが、ＡＢＲＶＣの利用可能なネットサービスレートよりも大きい場合、ＡＢＲソースをしてそれらのセルレートを低下させるために、式(7)はＵの値を低下させる。ラウンドトリップ遅延(round trip delay)が大きい場合、ソースの反応は遅れる。この期間に、Ｕは非常に大きな負の値(negative value)まで低下する。Ｕの値がそこまで低くなると、後になって帯域幅が利用可能になったときに、正の値(positive value)へ迅やかに変化することができない。従って、Ｕの下限も同じ様に設定するのが有利である。Ｃabrの範囲は[０，Ｌ]であり、ＦＳの必要範囲もまた[０，Ｌ]であるので、Ｕの必要十分な範囲は[−Ｌ，＋Ｌ]である。
【００３２】
〔Ｎbsの計算〕
Ｎbe中のアクティブなＡＢＲＶＣは、スイッチ(34)のポートに、ＶＣごとのキューで認識可能な長さのものを一切作らない。従って、Ｎbsの良好な推定は、ＶＣごとのキュー長さ(per-VC queue length)が幾つかの低閾値Ｔを越えるＡＢＲＶＣの集合(set)である。Ｔの値の適当な範囲は、３乃至１０セルである。Ｎn bsは測定値を表し、Ｎbsは指数平均値を表すものとする。Ｎn bsは、次の要領で測定される。ポートは、初期状態では、Ｎn bsとＮbsは両方共、ゼロに設定される。セルがＡＢＲＶＣに到着し、そのＶＣごとのキュー長さをＴ−１からＴまで増加させる時はいつでも、Ｎn bsは増分される(incremented)。セルが出発し、ＶＣごとのキュー長さをＴからＴ−１まで減少させる時はいつでも、Ｎn bsは減分される(decremented)。これは、次の式(8)で表される。
【数１２】
【００３３】
〔ΔＱ重み付け関数〕
ＡＢＲスイッチ(34)アルゴリズムが、Ｑnの値を考慮せずに、ΔＱのみに基づいてＦＳの調節を行なう場合、Ｑnはゆっくりと高い値へドリフト、その結果、セルの損失は多くなる。従来のＡＢＲスイッチ(34)のアルゴリズムでは、閾値を用いてＡＢＲバッファをいくつかの領域に分割し、Ｑnがこれらの閾値を越えた時に、ＦＳの計算値を漸進的(progressively)に低下させることにより、このようなドリフトを防止していた。
【００３４】
ＳＥＲＩＡでは、より簡易な手法を用いており、ΔＱは、Ｑn(及びΔＱ)の関数であるＹによって重み付けされる。適当な重み付け関数として、次の例を挙げることができる。
Ｙ＝Ｑn／βＢ であって、
もし、（ΔＱ＜０）のとき、
Ｙ＝ｍａｘ(１−Ｙ，０) であり、
Ｂは、ＡＢＲＶＣが利用可能なバッファ空間の合計であり、βは、パラメータであり、現在０．８に設定されている。
【００３５】
ＡＢＲバッファの占有が増加している(即ち、ΔＱ＞０)と仮定すると、Ｕは減少するだろう。重み付けの結果、ＡＢＲバッファが略完全に占有される場合の方が、ＡＢＲバッファが殆ど占有されていない場合よりも、Ｕの減少は確実に多くなる。同じ様に、ＡＢＲバッファの占有が減少している(即ち、ΔＱ＜０)場合、Ｕは増加する。重み付けの結果、ＡＢＲバッファが殆ど占有されていない場合の方が、ＡＢＲバッファが略完全に占有される場合よりも、Ｕの増加は確実に多くなる。
【００３６】
ΔＱの重み付けにより、Ｑnは約βＢ／２となる。この結果、フリースロットを満たすために、ＡＢＲＶＣに属する十分なセルがＡＢＲバッファ内で確実に利用可能となる。さらに、シミュレーションの結果では、ΔＱを重み付けすることにより、従来のスイッチ(34)のアルゴリズムで採用された方法よりも、Ｑnの安定性がより高められることを示している。
【００３７】
図１は、ＡＴＭスイッチ(34)のポートの構成を簡略化して示している。出口ユニット(egress unit)は、ＦＳの計算、セルバッファの管理、スケジューリング、ポリーシング(policing)その他の機能を行なう。ＦＳの計算値は入口ユニット(ingress unit)へ送られ、該ユニットは、ＥＲ値をバックワードＲＭセルにスタンプする。セルはセルメモリに記憶され、ＶＣごとの情報はテーブルメモリに記憶される。ＳＥＲＩＡは、これまでの公平なシェアの厳密計算アルゴリズムよりも、高速ＡＴＭスイッチに組み込むのが遙かに簡単である。その理由は次の通りである。
【００３８】
ＳＥＲＩＡは、ＦＳを計算するのにどんなメモリアクセスを実行する必要がない。ＳＥＲＩＡで用いられる幾つかの変数は、出口ユニットのレジスタに保存することができる。これに対して、ＶＣごとのフラグ又はＶＣごとの変数を用いるスイッチ(34)のアルゴリズムでは、スロットごとにＯ(ｎ)回のテーブルメモリアクセスを実行する必要がある。
【００３９】
第２に、バックワードＲＭセルが到着するとき、ＶＣＩ／ＶＰＩのルックアップを実行する必要がない。計算されたＦＳは全てのＡＢＲＶＣに共通しており、ＲＭセルはそのＭＣＲを含んでいるので、ＶＣの特定の情報にアクセスするためにＶＣＩ／ＶＰＩをルックアップする必要はない。
【００４０】
第３に、ＳＥＲＩＡは、バッファの管理やサービスのスケジューリングに関して、特定の要求を一切行わない。従って、ＳＥＲＩＡは様々なスケジューリングとバッファ管理のスキームと共に作業することができる。
【００４１】
〔公平性(フェアネス)〕
利用可能な帯域幅は、数多くの公平性(フェアネス)の基準(criteria)を用いて分配されることができる。ＭＣＲ＋均等シェアの公平性(MCR plus equal share fairness)の基準では、利用可能な帯域幅は、アクティブＡＢＲＶＣの間で等しく分けられる。ＭＣＲ比例(proportional to MCR)の基準では、利用可能な帯域幅は、ＭＣＲに比例して分けられる。ＭＣＲ比例基準の主な欠点は、ＭＣＲを有しないＡＢＲＶＣが追加の帯域幅を全く獲得できないことである。このため、多くのＡＢＲアルゴリズムでは、ＭＣＲ＋均等シェアの公平性基準となるように設計されている。図４４及び図４５に示された疑似コードは、ＭＣＲ＋均等シェアの公平性がもたらされるＳＥＲＩＡを示している。それは、ＡＴＭフォーラム[ATM Forum. Traffic management specification version 4.0, April 1996］に掲げられたその他の公平性基準に修正することは容易である。
【００４２】
最大−最小フェアネスの定義[D. Bertsekas and R. Gallager. Data Networks, Second Edition. Printice Hall, Inc., 1992]は、ＡＴＭフォーラムドキュメント[N. Yin. Fairness definition in ABR service model. ATM Forum Document: AF-TM 94-0928R2, Number 1994]のＭＣＲも含まれるように拡張された。拡張された最大−最小フェアネス基準の定義は、次の通りである。ＦＳを式(2)の唯一の解とすると、次式の関係を有するとき、ｉ番目のＡＢＲＶＣがｍｉｎ(Ｂi，ＭＣＲi＋ＦＳ)の帯域幅を割り当てられる場合にも、拡張された最大−最小フェアネス基準は充足される。
【数１３】
【００４３】
〔バーストＶＢＲＶＣが存在するときのロバストパフォーマンス〕
ＡＢＲスイッチ(34)アルゴリズムの実テストは、非常にバーストなＶＢＲストリームの存在下でのパフォーマンスである。即ち、ＡＢＲＶＣは、割り当てられていない帯域幅を利用しなければならないだけでなく、ＣＢＲ及びＶＢＲＶＣが一時的に使用していない帯域幅を使用することができなければならない。多くのＡＢＲアルゴリズムは、このようなシナリオではうまく実行できない[F.M. Chiussi and Y.T. Wang. An ABR rate-based congestion control algorithm for ATM switches with per-VC queueing. In GLOBECOM ’ 97, pages 771-778, 1997参照]。ＳＥＲＩＡの強さの１つは、非常にバーストなＶＢＲストリームのときにも、非常にうまく実行できることである。
【００４４】
〔多数のＡＢＲＶＣが存在するときのロバストパフォーマンス〕
公平なシェアの近似計算アルゴリズムは、ＮaまたはＮbsのトラックを保持しないので、ＡＢＲＶＣの数が多いと、大きなオシレーションを受ける。このアルゴリズムが自由帯域幅を検出すると、各ＡＢＲＶＣのＦＳを増加させて、着信レートを大幅に増加させる。これによって、アルゴリズムはそのＦＳを急に低下させるので、各ＡＢＲＶＣのセルレートは減少する。これは、オシレーションを生じ、過渡期間(transient period)は長くなる。この問題は、公平なシェアの厳密計算アルゴリズムでは起こらない。シミュレーション結果では、多数のＡＢＲＶＣが存在するときにも、ＳＥＲＩＡのロバストパフォーマンスを示している。
【００４５】
〔パーキングロットのようなトポロジにおけるロバストパフォーマンス〕
重要なことは、スイッチ(34)のアルゴリズムは、ホップの数が少ないＡＢＲＶＣが有利となるように、ホップの数が多いＡＢＲＶＣを識別しないことである。従来のスイッチ(34)のアルゴリズムはこの問題を抱えており、文献の中で、「ビートダウン問題(beat-down problem)」と称されている[F. Bonomi and K. Fendick. The rate-based flow control framework for the available bit rate ATM service. IEEE Networks, 9(2):25-39, March/April 1995]。シミュレーションの結果でも、ＳＥＲＩＡは、数多くのホップを有するＡＢＲＶＣを区別しないことが示されている。
【００４６】
〔シミュレーション結果〕
全てのリンクはＯＣ−３リンク(１５５.５２Ｍビット／秒)であり、スイッチは、８ＫセルのＡＢＲバッファサイズを有するＳＥＲＩＡを用いている。スイッチは、ＶＣごとのキューイングと、簡易に重み付けされたラウンドロビン(Weighted Round Robin：ＷＲＲ)スケジューラ(22)を用いている。ＷＲＲスケジューラ(22)の重み付けは、ＡＢＲＶＣの場合にはＭＣＲに比例して設定され、ＶＢＲＶＣの場合にはＰＣＲに比例して設定される。測定間隔Ｎは６４に設定される。ＶＣごとキューの閾値Ｔは５セルに設定される。指数平均化パラメータαn及びαuは共に１／８に設定される。
【００４７】
広帯域端末装置(Broadband Terminal Equipments：ＢＴＥ)は、ＡＴＭフォーラムの文献の中で定義されたエンドシステムアルゴリズムを用いている[ATM Forum. Traffic management specification version 4.0, April 1996]。ＢＴＥアルゴリズムのパラメータ値を表２に示す。これらの値は、ＡＴＭフォーラムの文献の中で推奨されるデフォールト値と同一である[ATM Forum. Traffic management specification version 4.0, April 1996]。これらの文献はその引用を以て本願への記載加入とする。
【００４８】
ＶＢＲソースは、５０msのＯＮとＯＦＦの周期で、ＯＮ／ＯＦＦのストリームを発生させる。ＯＮ周期では、ソースは指示されたピークセルレート(Peak Cell Rate：ＰＣＲ)でセルを送信し、ＯＦＦ周期では、ソースはアイドル状態である。
【００４９】
シミュレーション実験で用いられる多くのＡＢＲＶＣは持続性である(persistent)。即ち、それらは、ネットワークから指示された許可セルレート(Allowed Cell Rate：ＡＣＲ)と等しいレートで送信するのに十分なセルを常に有している。
【００５０】
【表２】
〔実験１〕
〔セットアップ〕
図２は、使用したトポロジを示している。セットアップは、１０個のＡＢＲソースからなる。ＡＢＲ１のＭＣＲは５０Ｍビット／秒、ＡＢＲ２のＭＣＲは１０Ｍビット／秒である。一方、ＡＢＲ３−ＡＢＲ１０のＭＣＲは１Ｍビット／秒である。ＡＢＲ２以外の全てのＡＢＲＶＣは持続性であるが、ＡＢＲ２はソースでボトルネックされて、５Ｍビット／秒となる。リンクＬ１−Ｌ１０とＬ１ｓ−Ｌ１０ｓの長さは１００kmであるのに対し、リンクＬａの長さは１０００kmである。
【００５２】
〔考察〕
実験１の結果を図３乃至図１２に示す。リターンＲＭセルのソースに対してネットワーク(12)により指示されたＡＣＲ値のプロット、実際のＡＢＲソースレート、並びにボトルネックスイッチｓｗ１のパラメータのプロット及びソースレートが示されている。式(2)に代入してＦＳの解を求めた結果を式(9)に示している。
【数１４】
従って、ＡＢＲ１は、６０.２８Ｍビット／秒の帯域幅を得ることになる。ＡＢＲ２は５Ｍビット／秒だけ使うことになる。ＡＢＲ３−ＡＢＲ１０は、各々が１１.２８Ｍビット／秒を得る。シミュレーションの結果では、これらの値と一致している。ＡＣＲ中の初期オーバーシュート(initial overshoots)は、ＡＢＲバッファを安定点まで満たすためであることに留意すべきである。
【００５４】
〔実験２〕
〔簡易トポロジにおける１０個のＡＢＲＶＣと１個のバーストＶＢＲＶＣ〕
〔セットアップ〕
使用したトポロジを図１４乃至図２１に示す。セットアップは、１０個のＡＢＲＶＣと１個のバーストＶＢＲソースからなる。ＡＢＲＶＣは全て持続性である。ＡＢＲ１のＭＣＲは５０Ｍビット／秒であり、その他のＡＢＲＶＣのＭＣＲは１Ｍビット／秒である。ＶＢＲ１のＰＣＲは５０Ｍビット／秒である。リンクＬ１−Ｌ１１及びＬ１ｓ−Ｌ１１ｓの長さは１０kmであるのに対し、リンクＬａ及びＬｂの長さは各々１０００kmである。
【００５５】
〔観察〕
実験２の結果を図１４乃至図２１に示す。ＡＣＲは、ＶＢＲソースがＯＦＦのときに起こるパルスでパルス整形される(pulse shaped)。ＶＢＲがＯＮのとき、Ｃabr＝Ｌ−ＶＢＲレート｝−ΣＭＣＲ＝１５５.５２−５０−（５０＋９×１）＝４６.５２Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて４６.５２／１０＝４.６５Ｍビット／秒を得る。ＶＢＲがＯＦＦのとき、Ｃabr＝１５５.５２−０−（５０＋９×１０）＝９６.５２Ｍビット／秒である。従って、各々のＡＢＲＶＣは、それらのＭＣＲに加えて９６.５２／１０＝９.６５Ｍビット／秒を得る。
【００５６】
〔実験３〕
〔簡易トポロジにおける１００個のＡＢＲＶＣと１個のバーストＶＢＲＶＣ〕
〔セットアップ〕
使用したトポロジは図２のものと同様であるが、１００個の全く同じＡＢＲソース及び１個のバーストＶＢＲソースを用いている。全てのＡＢＲＶＣは持続性であり、それらのＭＣＲは１.０Ｍビット／秒である。ＶＢＲ１のＰＣＲは５５Ｍビット／秒である。リンクＬ１−Ｌ１０１及びＬ１ｓ−Ｌ１０１ｓの長さは１０kmであり、一方、リンクＬａの長さは１０００kmである。
【００５７】
実験３の結果を図２２乃至図２９に示す。ＡＣＲは、ＶＢＲソースがＯＦＦのときに起こるパルスでパルス整形される。ＶＢＲ１がＯＮのとき、Ｃabr＝１５５−５５−（１００×１）＝０Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲ＝１.０Ｍビット／秒だけを得る。ＶＢＲ１がＯＦＦのとき、Ｃabr＝１５５−０−（１００×１）＝５５Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて５５／１００＝０.５５Ｍビット／秒を得る。即ち、その各々は１.５５Ｍビット／秒を得る。
【００５８】
〔実験４〕
〔パーキングロットトポロジにおける５個のＡＢＲＶＣと１個のバーストＶＢＲＶＣ〕
パーキングロットトポロジを図３０に示す。全てのＡＢＲＶＣは持続性である。ＡＢＲ２以外のＡＢＲＶＣのＭＣＲは全て１０Ｍビット／秒であるが、ＡＢＲ２のＭＣＲは２０Ｍビット／秒である。ＶＢＲ１のＰＣＲは９０Ｍビット／秒である。リンクＬ１−Ｌ５及びＬ１ａの長さは各々が１０kmであるのに対し、中央リンクＬａ−Ｌｅの長さは各々が１００kmである。
【００５９】
実験４の結果を図３１乃至図４０に示す。ＡＣＲは、ＶＢＲソースがＯＦＦのときに起こるパルスでパルス整形される。ＶＢＲがＯＮのとき、Ｃabr＝１５５−９０−（２０＋４×１０）＝５Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて５／５＝１Ｍビット／秒を得る。ＶＢＲがＯＦＦのとき、Ｃabr＝１５５−０−（２０＋４×１０）＝９５Ｍビット／秒である。従って、各々のＡＢＲＶＣは、そのＭＣＲに加えて９５／５＝１９Ｍビット／秒を得る。
【００６０】
シミュレーションの結果では、ＳＥＲＩＡは常に１００％のリンク帯域幅を獲得し、ＡＢＲバッファ占有の平均値はβＢ／２＝３２７６セルに近いことを示している。ＳＥＲＩＡは、ＡＢＲバッファの占有制御をきっちりと行なう。
【００６１】
実験１は、最大−最小フェアネスを得るために、ＳＥＲＩＡが、未使用の帯域幅をＡＢＲ２からスイッチ(34)ポートでボトルネックされた他のＡＢＲへ再分配する方法を示している。実験２、実験３及び実験４の結果に示されるように、ＳＥＲＩＡは、従来の多くのアルゴリズムとは異なり、非常にバーストなＶＢＲストリームがあるときでさえ、うまく実行する。実験３の結果は、多くの持続性ＡＢＲＶＣを取り扱う際、ＳＥＲＩＡがロバストであることを示している。実験４の結果では、ＳＥＲＩＡは、長いパスを有するＡＢＲＶＣを区別しない(即ち、ビートダウン問題がない)ことを示している。
【００６２】
ここに開示したＳＥＲＩＡは、公平なシェアを厳密に計算する新規なＡＢＲスイッチ(34)アルゴリズムである。それは、簡易で精確な方法により、スイッチ(34)でボトルネックされたＶＣに対して、その他の場所でボトルネックされたＶＣから帯域幅を分配する。ＳＥＲＩＡのその他新しい特徴には、これまでの方法よりも、より簡易でより安定したバッファ占有がもたらされるバッファ占有制御メカニズムがある。
【００６３】
シミュレーションの結果では、ＳＥＲＩＡは、最大−最小フェアネス、定常状態への迅速なコンバージェンス、リンクの１００％利用、及び安定したＡＢＲバッファ占有がもたらされることを示している。また、シミュレーションの結果では、ＳＥＲＩＡは、非常にバーストなＶＢＲストリームの存在下でも、ロバストであり、うまく作業が行われることを示している。
【００６４】
発明を例示するために、実施例を参照して発明を詳細に説明したが、これら説明は、単なる例示であって、当該分野の専門家であれば、特許請求の範囲に記載された発明の精神及び範囲から逸脱することなく、発明に種々の変形をなすことはできると理解されるべきである。
【図面の簡単な説明】
【図１】ＡＴＭスイッチポートの構成の概要説明図である。
【図２】実験１のトポロジを示す図である。
【図３】実験１の結果を示す図である。
【図４】実験１の結果を示す図である。
【図５】実験１の結果を示す図である。
【図６】実験１の結果を示す図である。
【図７】実験１の結果を示す図である。
【図８】実験１の結果を示す図である。
【図９】実験１の結果を示す図である。
【図１０】実験１の結果を示す図である。
【図１１】実験１の結果を示す図である。
【図１２】実験１の結果を示す図である。
【図１３】実験２のトポロジを示す図である。
【図１４】実験２の結果を示す図である。
【図１５】実験２の結果を示す図である。
【図１６】実験２の結果を示す図である。
【図１７】実験２の結果を示す図である。
【図１８】実験２の結果を示す図である。
【図１９】実験２の結果を示す図である。
【図２０】実験２の結果を示す図である。
【図２１】実験２の結果を示す図である。
【図２２】実験３の結果を示す図である。
【図２３】実験３の結果を示す図である。
【図２４】実験３の結果を示す図である。
【図２５】実験３の結果を示す図である。
【図２６】実験３の結果を示す図である。
【図２７】実験３の結果を示す図である。
【図２８】実験３の結果を示す図である。
【図２９】実験３の結果を示す図である。
【図３０】実験４のトポロジを示す図である。
【図３１】実験４の結果を示す図である。
【図３２】実験４の結果を示す図である。
【図３３】実験４の結果を示す図である。
【図３４】実験４の結果を示す図である。
【図３５】実験４の結果を示す図である。
【図３６】実験４の結果を示す図である。
【図３７】実験４の結果を示す図である。
【図３８】実験４の結果を示す図である。
【図３９】実験４の結果を示す図である。
【図４０】実験４の結果を示す図である。
【図４１】本発明の装置の概略説明図である。
【図４２】本発明の方法のフローチャート図である。
【図４３】本発明のスイッチの概略説明図である。
【図４４】ＳＥＲＩＡの疑似コードを示す図である。
【図４５】ＳＥＲＩＡの疑似コードを示す図である。
【符号の説明】
(10) セルスイッチング装置
(12) ネットワーク
(16) メモリメカニズム
(20) サーバ
(22) スケジューラ
Claims (32)
- ネットワークのエンティティからのセルをスイッチする装置であって：
ネットワークから全てのセルを受信する入力メカニズムであって、Ｊ個(Ｊは２以上の整数)の入力ポートメカニズムを含み、全ての入力ポートメカニズムは、一緒に、セルをある着信レートで受信する入力メカニズムと；
セルの占有場所を有し、入力メカニズムに接続されたメモリメカニズムであって、全てのセルが装置に格納されるように、入力メカニズムが受信した全てのセルを格納するメモリメカニズムと；
セルを装置からネットワークへ送信する出力メカニズムと；
メモリメカニズム及び出力メカニズムに接続され、あるサービスレートでサービスをセルへ提供するサーバと；
サーバ及びメモリメカニズムに接続され、セルによるメモリメカニズムの占有のファンクションとして、サービスをセルに提供するスケジューラであって、メモリメカニズムの占有を監視する監視メカニズムを含むスケジューラと；
全ての入力ポートメカニズムがセルを受信した時の着信レートを変更する変更メカニズムであって、各エンティティは最小のセルレートを有しており、サービスを要求するエンティティの各々に割り当てられるべき追加の帯域幅の公平なシェアを計算する、変更メカニズムと、
を具えている、セルスイッチング装置。 - 監視メカニズムは、セルのメモリメカニズムへの着信レートと、メモリメカニズムのセルが利用可能なサーバからのサービスレートとの差に基づいて、エンティティが利用可能な追加の帯域幅を決定する、請求項１に記載の装置。
- 各々の入力ポートメカニズムは、関連するエンティティに対応するセルのエンティティ着信レートを有し、変更メカニズムは、入力ポートメカニズムを通じてセルを供給する各エンティティのエンティティ着信レートを変更するようにしており、全ての入力ポートメカニズムからのセルの着信レートは、メモリメカニズムのセルが利用可能なサーバからのサービスレートと等しくなり、この着信レートは、全てのエンティティの着信レートの合計である、請求項２に記載の装置。
- 変更メカニズムは、入力ポートメカニズムを通じてセルを供給する各エンティティのエンティティ着信レートを、等しい量だけ変更する、請求項３に記載の装置。
- メモリメカニズムは、セルスイッチング装置が受信した全てのセルが格納される共有メモリメカニズム、又は別に独立して設けられたバッファのどちらかから構成され、各入力ポートメカニズムは関連バッファを有しており、該関連バッファは、関連入力ポートメカニズム又は各エンティティに対して独立して設けられたバッファだけが受信した全てのセルを格納する、請求項４に記載の装置。
- 監視メカニズムは、サーバからのサービスを待機するメモリメカニズムのセルのバックログを有するエンティティの個数を監視する、請求項５に記載の装置。
- エンティティはＡＢＲＶＣを含んでいる、請求項６に記載の装置。
- エンティティはＣＢＲ／ＶＢＲＶＣを含んでいる、請求項７に記載の装置。
- 監視メカニズムは、サーバからのサービスを待機するセルのバックログを有するＡＢＲＶＣの個数、即ち、供給されるＣＢＲ／ＶＢＲＶＣからのＣＢＲ／ＶＢＲセル(ｎvbr)の個数を監視する、請求項８に記載の装置。
- 公平なシェアＦＳを共有するための追加の帯域幅は、次式で表され、
- 監視メカニズムは、ＡＢＲセルの着信レートとＡＢＲＶＣが利用可能なサービスレートとの差を、ＡＢＲメモリメカニズム占有の変化レートに基づいて決定し、その差はΔＱ＝Ｑn−Ｑpで表され、ここでＱnは、現在の測定期間の開始時におけるＡＢＲメモリメカニズム占有の総計であり、Ｑpは、現在の測定期間より前の測定期間の開始時におけるＡＢＲメモリメカニズム占有の総計である、請求項１０に記載の装置。
- 変更メカニズムは、着信レートが、現在利用可能なサービスレートに等しくなるまでＵを変更する、請求項１１に記載の装置。
- セルをスイッチする方法であって：
スイッチの入力メカニズムにて、ネットワークからＪ個(但し、Ｊは１以上の数)のエンティティのセルを受信するステップ；
スイッチのメモリメカニズムにセルを格納するステップ；
サーバにより、メモリメカニズムのセルへサービスを提供するステップ；
メモリメカニズムのセルが、セルによるメモリメカニズムの占有のファンクションとして、スイッチのサーバからサービスを受信するとき、スイッチのスケジューラを用いてスケジューリングするステップ；
スケジューラの監視メカニズムでメモリの占有を監視するステップ；
セルによるメモリメカニズムの占有のファンクションとして、変更メカニズムにより、セルの着信レートを、入力メカニズムの全ての入力ポートメカニズムへ変更するステップであって、スイッチが受信したメモリメカニズムへのセルの着信レートが、メモリメカニズムのセルがサーバから利用可能なサーバレートに等しくなるようにするステップ；
セルのメモリメカニズムへの着信レートと、メモリメカニズムのセルがサーバから利用可能なサービスレートとの差に基づいて、エンティティが利用可能な追加の帯域幅を決定するステップ；
各エンティティは最小セルレートを有し、サービスを要求するエンティティの各々に割り当てられるべき追加の帯域幅の公平なシェアを計算するステップ；
を有しているセルスイッチング方法。 - ＡＴＭスイッチの所定リンクにおけるＡＢＲトラフィックフローを制御するために、明示的レートをＡＢＲＶＣへスタンプするＡＴＭスイッチであって、：
ＶＣのトラフィックをスイッチにキャリーする入力ポートメカニズムと；
ＶＣのセルの占有場所を有し、入力ポートメカニズムに接続されたメモリメカニズムであって、全てのセルがスイッチに格納されるように、入力ポートメカニズムが受信したＶＣの全てのセルを格納するメモリメカニズムと；
セルをスイッチからネットワークへ送信する出力ポートメカニズムと；
ＶＣのセルを、入力ポートメカニズムから出力ポートメカニズムへスイッチするスイッチングファブリックと；
明示的レート(ＥＲ)とバックワードＲＭセルにおけるスタンプレートとを計算するＡＢＲ−ＥＲメカニズムであって、各々のＡＢＲＶＣは最小セルレートを有し、サービスを要求するＡＢＲＶＣの各々に割り当てられるべき追加の帯域幅の公平なシェアを計算するＡＢＲ−ＥＲメカニズムと；
メモリメカニズム及び出力ポートメカニズムに接続され、ＶＣのセルに対して、あるサービスレートでサービスを提供するサーバと；
サーバ及びメモリメカニズムに接続され、ＶＣのセルによるメモリメカニズムの占有のファンクションとして、ＶＣのセルに対してサービスを提供するスケジューラと；
を具えているＡＴＭスイッチ。 - ＡＢＲ−ＥＲメカニズムは、メモリメカニズムの占有を監視し、メモリメカニズムの占有のファンクションとして、ＥＲ計算ファンクションを変更するメカニズムを含んでいる、請求項１４に記載のスイッチ。
- ＡＢＲ−ＥＲメカニズムは、ＡＢＲＶＣのセルがサーバから利用可能なサービスレートに基づいて、ＡＢＲＶＣが利用可能な追加の帯域幅を決定する、請求項１５に記載のスイッチ。
- ＡＢＲ−ＥＲメカニズムは、全てのエンティティからのＶＣの全てのセルの着信レートの合計が、メモリメカニズムのセルがサーバから利用可能なサービスレートに等しくなるように、各々のＡＢＲＶＣソースにスタンプされるべきレートを計算する、請求項１６に記載のスイッチ。
- メモリメカニズムは、セルスイッチング装置が受信した全てのセルが記憶される共有メモリメカニズム、又は別に独立して設けられたバッファのどちらかから構成され、各ＶＣは関連バッファを有しており、該関連バッファはＶＣの全てのセルを記憶する、請求項１７に記載のスイッチ。
- ＡＢＲ−ＥＲメカニズムは、サーバからのサービスを待機するメモリメカニズムのセルのバックログを有するＡＢＲＶＣの個数を監視する、請求項１８に記載のスイッチ。
- ＡＢＲ−ＥＲメカニズムは、アクティブＡＢＲＶＣの個数Ｎaと、ＣＢＲ／ＶＢＲＶＣに属するセルの個数ｎvbrと、必要に応じてアクティブＡＢＲＶＣのＭＣＲの合計Ｓaを、予め設定された時間のＮ個のセルスロットの測定期間中監視する、請求項１９に記載のスイッチ。
- Ｎa及びＳaなどの測定量は、急速な変化を少なくするために、部分的に又は全部が指数平均化される、請求項２０に記載のスイッチ。
- ＡＢＲ−ＥＲメカニズムは、測定結果から、ＡＢＲＶＣとそれらのＭＣＲが利用可能な合計の帯域幅Ｃabrを計算する際、Ｃabr＝（Ｎ−ｎvbr）Ｌ／Ｎ−Ｓaに基づいて行われる、請求項２１に記載のスイッチ。
- ＡＢＲ−ＥＲメカニズムは、追加の帯域幅パラメータＵと呼ばれるパラメータを維持し、該パラメータは、
（ａ）スイッチでバックログされるＶＣに対して、別の場所でバックログされるＶＣにより未使用の帯域幅を再分配し、
（ｂ）Ｓaなどの量について、測定結果が正しくないとき、又は測定が行われなかったとき、その補正を行なう、請求項２２に記載のスイッチ。 - ＭＣＲ＋均等シェアの公平性基準を用いるとき、ＥＲ計算メカニズムは、利用可能な帯域幅の公平なシェアＦＳを、
ＦＳ＝ｍａｘ（Ｃabr＋Ｕ，０）／ｍａｘ（Ｎa，１）
として計算する、請求項２３に記載のスイッチ。 - ＭＣＲの公平性基準の比例関係を用いることにより、ＥＲ計算メカニズムは、ｉ番目のＡＢＲＶＣの公平なシェアＦＳiを、
ＦＳｉ＝ｍａｘ（Ｃabr＋Ｕ，０）ＭＣＲi／ｍａｘ（Ｓa，１）
として計算する、請求項２４に記載のスイッチ。 - ＡＢＲ−ＥＲメカニズムは、ＡＴＭフォーラムＴＭ４.０によって規定された全ての公平性基準を満たすことができる、請求項２５に記載のスイッチ。
- 追加の帯域幅パラメータは、ＡＢＲバッファ占有量Ｑnと、ＡＢＲバッファ占有の変化レートであるデルタＱを用いて計算される、請求項２６に記載のスイッチ。
- Ｕは、
Ｑn＜Ｎのとき、Ｕ＝＋Ｌであり、
そうでなくＱn＞Ｎ（Ｂ−Ｎ）のとき、Ｕ＝−Ｌであり、
そうでないときは、Ｕ＝Ｕ−アルファ*ガンマ*デルタＱ*Ｌ／Ｎ、
として計算され、
ここで、ＢはＡＢＲバッファサイズであり、アルファは指数平均ファクターであり、ガンマはＡＢＲバッファ占有重み付け関数である、請求項２７に記載のスイッチ。 - ＡＢＲバッファ占有重み付け関数は、厳密なキュー制御を行ない、ＡＢＲバッファ占有のドリフティングを防止する、請求項２８に記載のスイッチ。
- ガンマは、
ガンマ＝Ｑn／Ｂであり、
デルタＱ＜０のとき、ガンマ＝ｍａｘ（１−ガンマ，０）
として計算される、請求項２９に記載のスイッチ。 - ＡＢＲ−ＥＲメカニズムは、ＶＣのＦＳをそのＭＣＲに加算することにより、ＡＢＲＶＣの明示的レートＥＲを計算する、請求項３０に記載のスイッチ。
- 公平なシェアＦＳを共有するための追加の帯域幅は、次式で表され、
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US09/129284 | 1998-08-05 | ||
| US09/129,284 US6456592B1 (en) | 1998-08-05 | 1998-08-05 | Method and apparatus for a simple explicit rate indication algorithm (SERIA) |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000069053A JP2000069053A (ja) | 2000-03-03 |
| JP4368979B2 true JP4368979B2 (ja) | 2009-11-18 |
Family
ID=22439283
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP22062699A Expired - Lifetime JP4368979B2 (ja) | 1998-08-05 | 1999-08-04 | 簡易な明示的レート表示アルゴリズムの方法及び装置 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6456592B1 (ja) |
| EP (1) | EP0979022B1 (ja) |
| JP (1) | JP4368979B2 (ja) |
| AT (1) | ATE532342T1 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6625160B1 (en) * | 1999-07-02 | 2003-09-23 | Cisco Technology, Inc. | Minimum bandwidth guarantee for cross-point buffer switch |
| US20030009560A1 (en) * | 2001-05-22 | 2003-01-09 | Motorola, Inc. | Method and system for operating a core router |
| US8681807B1 (en) * | 2007-05-09 | 2014-03-25 | Marvell Israel (M.I.S.L) Ltd. | Method and apparatus for switch port memory allocation |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| SE508284C2 (sv) * | 1996-03-15 | 1998-09-21 | Ericsson Telefon Ab L M | Metod och anordning för flödesstyrning i paketförmedlande nät |
| US5737313A (en) * | 1996-03-15 | 1998-04-07 | Nec Usa, Inc. | Design of a closed loop feed back control for ABR service |
| US5935213A (en) * | 1996-05-02 | 1999-08-10 | Fore Systems, Inc. | System and method for generating explicit rate value information for flow control in ATAM network |
| US5909443A (en) * | 1997-01-03 | 1999-06-01 | International Business Machines Corporation | ATM network congestion control system using explicit rate cell marking |
| US5991266A (en) * | 1997-03-19 | 1999-11-23 | Mitsubishi Electric Information Technology Center America, Inc. (Ita) | Queue length based ABR flow control system |
| US6081843A (en) * | 1997-03-20 | 2000-06-27 | Nokia Telecommunications | System using simulation cell and simulation buffer for regulating cell transfer rate according to occupancy level of the simulation buffer |
| US6141321A (en) * | 1997-07-08 | 2000-10-31 | Alcatel Networks Corporation | Method and apparatus for the efficient processing of ABR cells in an ATM switch |
| US6178159B1 (en) * | 1998-03-02 | 2001-01-23 | Lucent Technologies Inc. | Available bit rate flow control algorithms for ATM networks |
-
1998
- 1998-08-05 US US09/129,284 patent/US6456592B1/en not_active Expired - Lifetime
-
1999
- 1999-08-04 AT AT99306201T patent/ATE532342T1/de active
- 1999-08-04 EP EP99306201A patent/EP0979022B1/en not_active Expired - Lifetime
- 1999-08-04 JP JP22062699A patent/JP4368979B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2000069053A (ja) | 2000-03-03 |
| US6456592B1 (en) | 2002-09-24 |
| EP0979022A3 (en) | 2005-03-30 |
| EP0979022B1 (en) | 2011-11-02 |
| EP0979022A2 (en) | 2000-02-09 |
| ATE532342T1 (de) | 2011-11-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5991268A (en) | Flow control mechanism of ABR traffic in ATM networks | |
| US5754530A (en) | Flow control of ABR traffic in ATM networks | |
| Jain | Congestion control and traffic management in ATM networks: Recent advances and a survey | |
| US6512743B1 (en) | Bandwidth allocation for ATM available bit rate service | |
| Wernik et al. | Traffic management for B-ISDN services | |
| EP1009185A2 (en) | Explicit rate computation for flow control in computer networks | |
| Chiussi et al. | Dynamic max rate control algorithm for available bit rate service in ATM networks | |
| Kamolphiwong et al. | Flow control in ATM networks: A survey | |
| US7522624B2 (en) | Scalable and QoS aware flow control | |
| US5978357A (en) | Phantom flow control method and apparatus with improved stability | |
| Muddu et al. | Max-min rate control algorithm for available bit rate service in atm networks | |
| US6865156B2 (en) | Bandwidth control method, cell receiving apparatus, and traffic control system | |
| US6118764A (en) | Congestion indication/no increase (CI/NI) ABR flow control for ATM switches | |
| JP4368979B2 (ja) | 簡易な明示的レート表示アルゴリズムの方法及び装置 | |
| US6542509B1 (en) | Virtual path level fairness | |
| US6859436B2 (en) | Bandwidth control method, cell transmitting apparatus, and traffic control system | |
| Fahmy et al. | Quality of service for Internet traffic over ATM service categories | |
| Budrikis et al. | A generic flow control protocol for B-ISDN | |
| Ghani et al. | Hierarchical scheduling for integrated ABR/VBR services in ATM networks | |
| Koyama et al. | An adaptive rate-based congestion control scheme for ATM networks | |
| Al‐Hammadi et al. | Engineering ATM networks for congestion avoidance | |
| Lee et al. | A simplified approach based on source control for ATM ABR service | |
| JP3386092B2 (ja) | Ａｂｒセル流量制御方法 | |
| Chew et al. | Active fairness: improved fairness with dynamic VC weights and generalized fairness in the ATM ABR service | |
| mee Choi et al. | 52-20-07 A Survey of Congestion Control Schemes for ABR Services in ATM Networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A711 Effective date: 20040901 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20040906 |
|
| RD02 | Notification of acceptance of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7422 Effective date: 20040906 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20060705 |
|
| A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A711 Effective date: 20080514 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20080806 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080819 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20081114 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20081119 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20081217 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20081222 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20090115 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20090120 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090217 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20090804 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20090827 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 4368979 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120904 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130904 Year of fee payment: 4 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |