(57)【特許請求の範囲】
【請求項１】
通信網に収容される各コネクションの最低帯域の保証を行う帯域制御装置において、
各コネクションからのパケットを受け入れ、出力回線へ送出するバッファと、
前記バッファのキュー長を観測する手段と、
観測したキュー長と各コネクションの最低保証帯域とから、各コネクションに分配されるべき帯域として許可レートを計算する手段と、
コネクション毎に網に入力するトラヒック流量としてパケットの入力レートを計測する手段と、
計測した入力レートを格納する手段と、
計測した入力レートを前記許可レートと比較し、入力レートが許可レート以下であれば、そのコネクションのパケットをバッファに入力し、許可レートを超えれば超えた分だけ廃棄することにより、各コネクションのバッファへの入力レートが常に許可レート以下になるように制御する帯域制御手段とを具え、
前記許可レートを計算する手段は、ＡＣＲ(m)をコネクションｍの許可レート、ＭＣＲ(m)をコネクションｍの最低保証帯域、Ｆ(q)をキュー長ｑの減少関数とするとき、
ＡＣＲ(m)＝Ｆ(q)＊ＭＣＲ(m)
に従って許可レートを計算することを特徴とする帯域制御装置。
【請求項２】
前記帯域制御手段は前記入力レートと許可レートを比較し、入力レートが許可レート以下であれば、そのコネクションに属するパケットをバッファに入力し、入力レートが許可レートを超えた場合、超えた割合を算出し、その割合の確率で受信パケットを廃棄することを特徴とする請求項１記載の帯域制御装置。
【請求項３】
前記許可レートを計算する手段で使用するキュー長の減少関数Ｆ(q)は、キュー長が０のとき最大値Ｍを有し、キュー長が閾値以上のとき最小値１を有するキュー長の減少関数であることを特徴とする請求項１記載の帯域制御装置。
【請求項４】
前記許可レートを計算する手段で使用するキュー長ｑとして、一定時間内のキュー長の平均値を使用することを特徴とする請求項１記載の帯域制御装置。
【請求項５】
通信網に収容される各コネクションの最低帯域の保証を行う帯域制御方法において、各コネクションのトラヒック流量としてパケットの入力レートを計測し、計測した入力レートを格納し、各コネクションのパケットを受け入れ出力回線へ送出するバッファのキュー長を観測し、観測したキュー長と各コネクションの最低保証帯域とから、各コネクションに分配されるべき帯域として許可レートを計算し、この許可レートの計算は、ＡＣＲ(m)をコネクションｍの許可レート、ＭＣＲ(m)をコネクションｍの最低保証帯域、Ｆ(q)をキュー長ｑの減少関数とするとき、
ＡＣＲ(m)＝Ｆ(q)＊ＭＣＲ(m)
に従って実行し、次に、計測した入力レートと計算した許可レートを比較し、入力レートが許可レート以下であれば、そのコネクションのパケットをバッファに入力させ、入力レートが許可レートを超えれば超えた分だけ廃棄することにより、各コネクションのバッファへの入力レートが常に許可レート以下になるように制御することを特徴とする帯域制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信網、特にＡＴＭ通信網に収容される各コネクションの最低帯域の保証を行う装置及び方法に関するものである。
【０００２】
【従来技術】
近年、インターネットやＬＡＮの急速な普及から、ＩＰトラヒックなどのデータ系トラヒックが指数関数的に増加している。これにともないネットワーク上で輻輳発生頻度が増加しており、ユーザに対するサービス品質の低下が問題になっている。例えば、従来のインターネットでは転送品質を保証しないベストエフォートサービスが主流であったが、ベストエフォートサービスのみでは十分なスループットが得られないケースが増えており、ＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）間や企業間を高速回線で接続する場合に回線ごとに最低帯域や遅延品質を保証するようなサービスの要求が今後ますます増加すると考えられる。
【０００３】
ユーザ毎に契約している最低帯域を保証するサービスとしてはＧＦＲ（Ｇｕａｒａｎｔｅｅｄ  Ｆｒａｍｅ  Ｒａｔｅ）サービスがある。非輻輳時には各ユーザは互いに利用可能帯域（残余帯域）を共有して利用するできる。
【０００４】
ＧＦＲサービスを実現する方式に関しては数多くの提案がなされているが、その一つにＷＲＲ（Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）方式がある。
図６はＷＲＲ方式の概略を示す図である。ＷＲＲ方式はコネクション毎にキューを持ち、コネクション毎に重みが付けられており、重みに応じた読み出し制御を各キューに対して行うことでコネクション間に帯域を分配する。例えば図６ではコネクション１に重み２が、コネクション２に重み１が、コネクション３に重み３が付けられており、重みに応じたスケジュールリストに従ってコネクション１、２又は３のキューからパケット（又はセル）１、２又は３が読み出され、コネクション１、２、３に重みに応じて帯域が分配される。
【０００５】
このように、ＷＲＲ方式は、帯域を共有する全てのコネクションに対してＷＲＲスケジューリングに基づいて読み出し制御を行なうことによって、収容コネクションに重みに応じて帯域を分配することができる。ＷＲＲ方式によれば、最低帯域を保証しつつ、余剰帯域をある規則にしたがってコネクション間に公平に分配することが可能である。
【０００６】
しかし、ＷＲＲ方式のハードウエアの複雑さは収容するコネクション数に比例し、回線の高速化のボトルネックとなる。また、コネクション毎にキューを持つ必要があるため、バッファ部のハード量も問題となる。つまり、ＷＲＲ方式は回線が高速化され、回線に収容されるコネクション数が増加すると、経済的にＧＦＲサービスを実現することが困難になる。したがって、簡易なハードウエア構成でＧＦＲサービスを実現する方式が求められている。
【０００７】
簡易なハードウエア構成でＧＦＲサービスを実現する方式として、ＦＩＦＯ−タギング方式が知られている。この方式では、バッファはコネクションごとに持つ必要はなく、回線ごとに一つあればよい。ＦＩＦＯ−タギング方式ではコネクション毎に網の入口で網へ入力するパケット（又はセル）の入力レートを計測し、計測された入力レートが最低セルレートＭＣＲ（Ｍｉｎｉｍｕｍ  Ｃｅｌｌ  Ｒａｔｅ）以下であれば、そのコネクションのパケットはそのまま通過し、ＭＣＲを超えていればそのコネクションのパケットのヘッダ部にタグが付けられる。ここで、最低セルレートＭＣＲとは網がコネクションに対して転送を保証する帯域のことである。
【０００８】
ＦＩＦＯバッファには閾値が設定されており、キュー長が閾値を超えているか否か常に観測されている。仮にキュー長が設定された閾値を超えている場合には、ヘッダ部にタグが付けられているパケットはＦＩＦＯバッファに入る前に廃棄され、ＦＩＦＯバッファにはタグが付いていないパケット、つまり網への入力レートがＭＣＲ以下のコネクションのパケットのみ通過する。
【０００９】
ＦＩＦＯ−タギング方式では、ＦＩＦＯバッファの出力速度を収容する複数のコネクションのＭＣＲの合計以上にすることにより、輻輳時におけるＭＣＲの保証が可能である。また、非輻輳時に各コネクションのＭＣＲの和を超えた部分の帯域、即ち余剰帯域がある場合には、その帯域は複数のコネクションでシェアされる。
【００１０】
しかし、この方式では収容する複数のコネクションで一つのＦＩＦＯバッファを共有するので、各コネクションのＭＣＲの和を超えた部分の帯域、即ち余剰帯域に関してはＦＩＦＯバッファへの入力レートに比例するかたちで各コネクション間に分配されるため、「公平性」という面で問題があった。つまり、ＦＩＦＯ−タギング方式では、余剰帯域が生じた場合にその帯域をどのようにコネクション間で分配するかを、方式上規定できないため、極端な場合には余剰帯域を１つのコネクションが占有してしまうという不公平な状況が生ずるという問題があった。
【００１１】
【発明が解決しようとする課題】
本発明の目的は、通信網に収容される各コネクションに対して、輻輳時においても契約している最低帯域を保証しつつ、通常（非輻輳時）には余剰帯域をコネクション間で公平に分配し、より効率的な網資源の利用を可能にする装置及び方法を提供することにある。
【００１２】
【課題を解決するための手段】
本発明は、通信網に収容される各コネクションの最低帯域の保証を行う帯域制御装置において、
各コネクションからのパケットを受信し、出力回線へ送出するバッファと、
前記バッファのキュー長を観測する手段と、
観測したキュー長と各コネクションの最低保証帯域とから、各コネクションに分配されるべき帯域として許可レートを計算する手段と、
コネクション毎に網に入力するトラヒック流量としてパケットの入力レートを計測する手段と、
計測した入力レートを格納する手段と、
計測した入力レートを前記許可レートと比較し、計測した入力レートが許可レート以下であれば、そのコネクションのパケットをバッファに入力し、許可レートを超えれば超えた分だけ廃棄することにより、各コネクションのバッファへの入力レートが常に許可レート以下になるように制御する帯域制御手段と、
を具えることを特徴とする。
【００１３】
本発明は、更に、通信網に収容される各コネクションの最低帯域の保証を行う帯域制御方法において、各コネクションのトラヒック流量としてパケットの入力レートを計測し、計測した入力レートを格納し、各コネクションのパケットを受信し出力回線へ出力するバッファのキュー長を観測し、観測したキュー長と各コネクションの最低保証帯域とから、各コネクションに分配されるべき帯域として許可転送レートを計算し、次に、計測した入力レートと計算した許可レートを比較し、入力レートが許可レート以下であれば、そのコネクションのパケットをバッファに入力させ、入力レートが許可レートを超えれば超えた分だけ廃棄することにより、各コネクションのバッファへの入力レートが常に許可レート以下になるように制御することを特徴とする。
【００１４】
【発明の実施の形態】
以下、図面を参照して本発明を実施例につき説明する。
図１は本発明の帯域制御装置の一実施例の機能構成図である。本例帯域制御装置は、コネクション識別部１と、ポリシング部２と、バッファ部３とで構成されている。コネクション識別部１では、例えばＡＴＭ通信網に収容される複数のコネクションを経て到着したパケットのヘッダからコネクションを識別する。ポリシング部２では、そのコネクション情報をもとに帯域制御に関する処理を行う。バッファ部３は通信網に収容されている複数のコネクションに共通の単純なＦＩＦＯ型のバッファ３１とキュー長監視部３２とで構成されている。
【００１５】
ポリシング部２における帯域制御処理について詳細に説明する。ポリシング部２は、レート計測部２１と、許可レート計算部２２と、コネクション情報格納２３と、廃棄制御部２４とで構成されている。
レート計測部２１はコネクション毎のトラヒック流量としてパケット又はセルの入力レートを測定する。測定されたコネクション毎の入力レートはコネクション情報格納部２３に供給され、ここに格納される。
【００１６】
図２はコネクション情報格納部２３の一例で、レート計算部２１で測定された各コネクション１，．．ｋの入力レートに関する情報Ｒ１，．．Ｒｋと、契約している最低保証帯域ＭＣＲに関する情報ＭＣＲ１，．．ＭＣＲｋが格納されている。
【００１７】
キュー長監視部３２はＦＩＦＯバッファ３１のキュー長を監視し、キュー長に関する情報を許可レート計算部２２に供給する。許可レート計算部２２はキュー長に関する情報とコネクション毎に契約している最低保証帯域ＭＣＲとからコネクション毎の許可レートＡＣＲ（Ａｌｌｏｗｅｄ  Ｃｅｌｌ  Ｒａｔｅ）を計算する機能を持つ。
【００１８】
コネクションｍの許可レートＡＣＲ（ｍ）の計算方法について具体的に説明する。コネクションｍの契約している最低保証帯域ＭＣＲをＭＣＲ（ｍ）、パケット到着時のキュー長をｑとすると、
ＡＣＲ（ｍ）＝Ｆ（ｑ）・ＭＣＲ（ｍ）
で計算される。Ｆ（ｑ）はキュー長の関数であり、図３及び図４のグラフはキュー長の関数Ｆ（ｑ）の一例である。この関数Ｆ（ｑ）は、キュー長が所定の閾値Ｑ以上のとき、即ち輻輳状態を生ずるとき、１の値を取り、キュー長が０のときＭの値を取る連続関数である。つまり、キュー長が閾値Ｑ以上であって輻輳状態を生ずるときには、許可レートはＭＣＲと等しくなり、キュー長が閾値Ｑより小さくて輻輳状態を生じないときには、許可レートはキュー長に応じて変化し、キュー長が０のときＭＣＲのＭ倍のレートまでの入力が許可される。
【００１９】
この関数Ｆ（ｑ）はコネクション間で共通である。このため、キュー長がある値のときの各コネクションの許可レートは各コネクションのＭＣＲに比例するかたちになる。関数Ｆ（ｑ）は基本的にはキュー長の減少関数で、図３のような反比例や図４のような直線などで与えられる。
また、上述の実施例ではｑとしてはパケット到着時のキュー長（キュー長の瞬間値）を使用しているが、ｑとして一定時間内のキュー長の平均値を採用してもよい。
【００２０】
廃棄制御部２４は、許可レートとレート計測部２１で計測された入力レートから、到着したパケットをＦＩＦＯバッファ３１に入力するか廃棄するか決定する。基本的には、入力レートが許可レート以下であれば、到着したパケットをＦＩＦＯバッファに入力し、許可レートを超えていれば超えた分だけ廃棄することにより、常に各コネクションのＦＩＦＯバッファへの入力速度が許可レート以下になるように制御する。したがって、常に許可レート以下で網にパケットを送出しているコネクションのパケットは網で廃棄されることなく転送される。
【００２１】
この廃棄処理による帯域制御のアルゴリズムについて説明する。廃棄処理の方法には２つあり、先ず確率的に廃棄する方法から説明する。
確率的に廃棄する方法では、入力レートが許可レートを超えた場合、超えた割合を算出し、その割合の確率的でパケットを廃棄するものである。コネクションｍの許可レートをＡＣＲ（ｍ）、計測された入力レートをＲ（ｍ）とし、廃棄確率をＰ（ｍ）とすると、
Ｐ（ｍ）＝（Ｒ（ｍ）−ＡＣＲ（ｍ））／Ｒ（ｍ）    （ただし、Ｒ（ｍ）＞ＡＣＲ（ｍ））
で与えられる。例えば、入力レートが４Ｍｂｐｓ、許可レートが３Ｍｂｐｓのとき、廃棄確率は０．２５となる。到着したパケットは確率０．２５で廃棄されるため、ＦＩＦＯバッファへの通過レートは３Ｍｂｐｓとなり、許可レートに等しくなる。
【００２２】
もう一つの方法は、カウンタを用いて廃棄する方法である。この方法ではコネクション毎にカウンタを持ち、到着したパケットを超えた割合だけなるべく等間隔に廃棄しようとするものである。例えば、入力レートが４Ｍｂｐｓで、許可レートが３Ｍｂｐｓの場合、３つのパケットが通過する毎に１つのパケットを廃棄する処理を行う。
このように許可レート以下でＦＩＦＯバッファへと入力されたパケットはＦＩＦＯ規則に従って出力回線へ送出される。
【００２３】
また、入力レートが許可レートを超えた場合、パケットをポリシング部で廃棄する代わりに、パケットのヘッダにタグを付けて優先的に廃棄すべきパケットであることを明示し、ＦＩＦＯバッファに入力させ、バッファ部でパケットの廃棄処理を行うこともできる。バッファ部で廃棄する方法は、前段のポリシング部で廃棄する方法に比べて、キュー長情報の伝達時間が短いため、より有効にバッファを使用できる利点がある。
【００２４】
図５は上述した本発明の帯域制御装置において実行される帯域制御方法の流れを示す図である。本発明の帯域制御方法では、ステップＳ１で各コネクションのトラヒック流量としてパケットの入力レートを計測し、ステップＳ２で得られた入力レートＲ（ｍ）を格納するとともに、ステップＳ３でＦＩＦＯバッファのキュー長ｑを測定し、得られたキュー長ｑと各コネクションの最低保証帯域ＭＣＲとから各コネクションの許可レートＡＣＲを計算する。本例では、この計算はＡＣＲ＝Ｆ（ｑ）＊ＭＣＲにしたがって計算する。Ｆ（ｑ）は、例えば図３及び４に示すようなキュー長ｑの減少関数である。次に、ステップＳ５において計測された入力レートＲを計算された許可レートＡＣＲと比較し、入力レートが許可レート以下であれば、ステップＳ６で当該コネクションのパケットをＦＩＦＯバッファに入力させ、入力レートが許可レートを超えた場合には、ステップＳ７で超えた分だけ廃棄する。
【００２５】
以上説明したように、本発明ではキュー長をもとに網の輻輳状態を推定し、輻輳であると判断されれば、許可レートをＭＣＲに等しくし、ＭＣＲ以下でパケットを送出しているコネクションのパケットのみを網を経て転送する。網資源が十分に利用されていない場合、つまり余剰帯域が存在する場合には、各コネクションの許可レートを各コネクションのＭＣＲに比例して増加させることにより余剰帯域をコネクション間に各コネクションのＭＣＲに比例して分配する。
【００２６】
また、上述した実施例によれば、ハードウエア構成が簡易なＦＩＦＯバッファによって、ＧＦＲサービスを実現しつつ、ＷＲＲ方式などのようにコネクション毎に個別のバッファを用いてパケットの読出し制御を行う方法と同様に余剰帯域を公平にコネクション間に分配することができる。また、１つのバッファを多数のコネクションで共用するため、コネクション毎に個別のバッファを使用する方式に比べて、必要とされるバッファ量を削減できるという利点もある。
【００２７】
【発明の効果】
したがって、本発明によれば、通信網に収容されている各コネクションに対して、契約している最低帯域を保証しつつ、余剰帯域を契約している最低保証帯域ＭＣＲと網資源の使用状況を考慮してコネクション間に公平に分配することができ、通信網のより効率的な利用が可能になる。また、本発明によれば、ハードウエア構成が簡易なＦＩＦＯバッファを採用しているため、高速回線においても経済的に実現可能である。
【図面の簡単な説明】
【図１】本発明の帯域制御装置の一実施例の機能構成図である。
【図２】図１に示す帯域制御装置のコネクション情報格納部の格納データの一例を示す図である。
【図３】図１の帯域制御装置の許可レート計算部において許可レートの計算に使用する関数Ｆ（ｑ）の一例を示すグラフである。
【図４】図１の帯域制御装置の許可レート計算部において許可レートの計算に使用する関数Ｆ（ｑ）の他の例を示すグラフである。
【図５】本発明の帯域制御方法の処理フローを示す図である。
【図６】既知のＷＲＲ方式の概要を示す図である。
【符号の説明】
１  コネクション識別部
２  ポリシング部
３  バッファ部
２１  レート計測部
２２  許可レート計算部
２３  コネクション情報格納部
２４  廃棄制御部
３１  ＦＩＦＯバッファ
３２  キュー長監視部
【図１】
0003583711.tif 000002
【図２】
0003583711.tif 000003
【図３】
0003583711.tif 000004
【図４】
0003583711.tif 000005
【図５】
0003583711.tif 000006
【図６】
0003583711.tif 000007