(57)【特許請求の範囲】
【請求項１】
到着するパケットの受付可否を判定する手段と、この判定により受付拒否されたパケットについてはこれを廃棄する手段とを備えたパケット廃棄装置において、
前記受付可否を判定する手段は、
到着するパケットのキュー長がバッファ内でのコネクションごとの受付許可のキュー長を超え、その比が所定値を超えたときは少なくとも２個連続してパケットを受付拒否する手段と、
到着するパケットのキュー長がバッファ内でのコネクションごとの受付許可のキュー長を超え、その比が所定値以下のときは連続した受付拒否を禁止する手段と
を備えたことを特徴とするパケット廃棄装置。
【請求項２】
到着するパケットの受付可否を判定する手段と、この判定により受付拒否されたパケットについてはこれを廃棄する手段とを備えたパケット廃棄装置において、
前記受付可否を判定する手段は、
到着するパケットの到着レートが受付許可のレートを超え、その比が所定値を超えたときは少なくとも２個連続してパケットを受付拒否する手段と、
到着するパケットの到着レートが受付許可のレートを超え、その比が所定値以下のときは連続した受付拒否を禁止する手段と
を備えたことを特徴とするパケット廃棄装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信網に収容される各コネクションの最低帯域の保証を行う装置に関する。
【０００２】
【従来の技術】
近年、インターネットやＬＡＮの急速な普及から、ＩＰトラヒック等のデータ系トラヒックが指数関数的に増加している。これにともないネットワーク上で輻輳発生頻度が増加しており、ユーザに対するサービス品質の低下が問題となっている。例えば、従来のインターネットでは転送品質を保証しないベストエフォートサービスが主流であったが、ベストエフォートサービスのみでは十分なスループットが得られないケースが増えており、ＩＳＰ(Internet Service Provider)間や企業間を高速回線で接続する場合に回線毎に最低帯域や遅延品質を保証するようなサービスの要求が今後ますます増加すると考えられる。
【０００３】
ユーザ毎に契約している最低帯域を保証するサービスとしてはＧＦＲ(GuaranteedFrame Rate)サービスがある。非輻輳時には各ユーザは互いに利用可能帯域（残余帯域）を共有して利用できる。
【０００４】
ＧＦＲサービスを実現する方式に関しては数多くの提案がなされているが、その一つにＷＲＲ(WeightedRound Robin)方式がある。図１６はＷＲＲ方式の概略を表す図である。ＷＲＲ方式はコネクション毎にキューを持ち、コネクション毎に重みが付けられており、重みに応じた読出制御を各キューに対して行うことでコネクション間に帯域を分配する。
【０００５】
ＷＲＲに、帯域を共有する全てのコネクションを収容することによって、収容コネクションの重みに応じて帯域を分配することができる。ＷＲＲ方式により、最低帯域を保証しつつ、余剰帯域をある規則にしたがってコネクション間に公平に分配することが可能である。
【０００６】
しかし、ＷＲＲ方式のハードウェアの複雑さは収容するコネクション数に比例し、高速化のボトルネックとなる。また、コネクション毎にキューを持つ必要があるため、バッファ部のハード量も問題となる。つまり、ＷＲＲ方式は高速になり、収容されるコネクション数が増加すると、経済的にＧＦＲサービスを実現することが困難である。したがって、簡易なハードウェア構成でＧＦＲサービスを実現する方式が求められている。
【０００７】
簡易なハードウェア構成でＧＦＲサービスを実現する方式として、ＦＩＦＯ−Ｔａｇｇｉｎｇ方式が知られている。この方式では、バッファはコネクション毎に持つ必要はなく、回線毎に一つあればよい。ＦＩＦＯ−Ｔａｇｇｉｎｇ方式ではコネクション毎に網の入り口で網への入力レートを観測し、計測されたレートがＭＣＲ(Minimum Cell Rate)以下であれば、そのコネクションのパケットはそのまま通過し、ＭＣＲを超えていればパケットのヘッダ部にＴａｇが付けられる。ここで、ＭＣＲとは網がコネクションに対して転送を保証する帯域のことである。
【０００８】
ＦＩＦＯバッファには閾値が設けられており、キュー長が閾値を超えているか否か常に観測している。仮にキュー長が設定された閾値を超えている場合には、ヘッダ部にＴａｇが付けられているパケットはＦＩＦＯバッファに入る前に廃棄され、ＦＩＦＯバッファにはＴａｇが付いていないパケット、つまり網への入力レートがＭＣＲ以下のコネクションのパケットのみ通過する。
【０００９】
ＦＩＦＯ−Ｔａｇｇｉｎｇ方式では、ＦＩＦＯバッファの出力速度を収容するコネクションのＭＣＲの合計以上にすることで、輻輳時におけるＭＣＲの保証が可能である。また、非輻輳時、各コネクションのＭＣＲの和を超えた部分の帯域、余剰帯域がある場合には、その帯域は複数コネクションでシェアされる。
【００１０】
【発明が解決しようとする課題】
しかし、この方式では複数コネクションでバッファを共用するので、各コネクションのＭＣＲの和を超えた部分の帯域、余剰帯域に関しては、ＦＩＦＯバッファへの入力レートに比例するかたちで各コネクション間に分配されるため、「公平性」という面で問題があった。ＦＩＦＯ−Ｔａｇｇｉｎｇ方式では余剰帯域が生じた場合にその帯域をどのようにコネクション間で分配するかという規定がないため、極端な場合では余剰帯域を一つのコネクションが占有してしまうという不公平な状況が生じるという問題があった。
【００１１】
本発明は、このような背景に行われたものであって、通信網内に設置することにより、通信網に収容されている各コネクションに対し、輻輳時においても契約している最低帯域を保証しつつ、通常時（非輻輳時）には、余剰帯域をコネクション間で公平に分配し、より効率的な網資源の利用を可能にすることができるパケット廃棄装置を提供することを目的とする。本発明は、高速回線においても経済的に実現可能なパケット廃棄装置を提供することを目的とする。さらに、パケット交換スイッチ等のノード内に設置することにより、簡単なハードウェア構成を実現し、効率の良いノード内の輻輳回避を実現することができるパケット廃棄装置を提供することを目的とする。
【００１２】
【課題を解決するための手段】
本発明は、到着するパケットの受付可否を判定する手段と、この判定により受付拒否されたパケットについてはこれを廃棄する手段とを備えたパケット廃棄装置である。
【００１３】
ここで、本発明の特徴とするところは、前記受付可否を判定する手段は、到着するパケットの到着レートあるいはキュー長が受付許可のレートあるいは受付許可のキュー長を超えその比が所定値を超えたときは、少なくもと２個連続してパケットを受付拒否する手段を備えたところにある。
【００１４】
さらに、前記受付可否を判定する手段は、連続した受付拒否を禁止する手段を備えることもでき、この場合には、前記２個連続してパケットを受付拒否する手段と前記連続した受付拒否を禁止する手段とを切替選択する手段を備えることもできる。
【００１５】
例えば、急激にキュー長Ｘｊが許可キュー長ＡＱｊを超えたときには、輻輳発生を回避するために急激なトラヒック制御を行う必要がある。そのような事態が発生したときには、パケットを連続して廃棄することにより対処することができる。反対に、緩やかにキュー長Ｘｊが許可キュー長ＡＱｊを超えたときには、緩やかなトラヒック制御を行って安定したトラヒック制御を実現することができる。このような相反する制御形態は、状況に応じて切替えて用いることが望ましい。このような切替制御は、前記判定する手段の付加機能として備えることが望ましい。なお、パケットは固定長パケットであるセルであっても同様に説明することができる。
【００１６】
これにより、通信網内に設置することにより、通信網に収容されている各コネクションに対し、輻輳時においても契約している最低帯域を保証しつつ、通常時（非輻輳時）には、余剰帯域をコネクション間で公平に分配し、より効率的な網資源の利用を可能にすることができ、高速回線においても経済的に実現可能なパケット廃棄装置を実現することができる。さらに、パケット交換スイッチ等のノード内に設置することにより、簡単なハードウェア構成を実現し、効率の良いノード内の輻輳回避を実現することができる。
【００１７】
【発明の実施の形態】
（第一実施例）
本発明のパケット廃棄装置が適用される本発明第一実施例の多重化装置を図１および図１２を参照して説明する。図１は本発明第一実施例の多重化装置のブロック構成図である。図１２はモニタリングパケットを用いるキュー長検出を説明するための図である。
【００１８】
本発明のパケット廃棄装置５が適用される多重化装置は、図１に示すように、到着するパケットの属するコネクション１〜ｋを識別するコネクション識別部１と、当該パケットの受付可否を判定するパケット廃棄装置５と、このパケット廃棄装置５の判定結果にしたがってパケットを多重化するＦＩＦＯ型のバッファ６と、複数コネクションのパケットがバッファ６に蓄積されている中からコネクションｉ毎のバッファ６のキュー長Ｘｉを検出するキュー長監視部７および仮想キュー管理部３と、コネクションｉ毎にあらかじめ定められた重みＷｉの値を保持するコネクション情報格納部２とを備え、バッファ６にはあらかじめ閾値となる最大キュー長Ｑｍａｘが設定され、当該最大キュー長Ｑｍａｘを超えるとほぼゼロとなる前記キュー長Ｘｉの総和であるΣＸｉの連続関数をα（ΣＸｉ）とし、バッファ６に１以上のパケットが蓄積されているコネクションｉの前記重みの和をＷａｃｔとし、許可キュー長計算部４は、許可キュー長ＡＱｉを
ＡＱｉ＝α（ΣＸｉ）・Ｗｉ／Ｗａｃｔ
として計算し、パケット廃棄装置５は、コネクションｉ毎のキュー長Ｘｉが当該許可キュー長ＡＱｉ以下のコネクションに属するパケットについてはこれを受付許可と判定する。
【００１９】
本実施例では、複数コネクションが混在して一つのバッファ６に蓄積されている状況下における実際のバッファ６のキュー長に対してキュー長監視部７および仮想キュー管理部３によりコネクションｉ毎にバッファ６のキュー長Ｘｉを検出したものを仮想キュー長という。以下では、説明を簡単にするために、仮想キュー長を単にキュー長ＸｉまたはＸｊということにする。
【００２０】
本発明のパケット廃棄装置５の特徴としては、受付拒否したコネクションｊのキュー長Ｘｊが前記許可キュー長ＡＱｊを超えている割合を算出し、この算出された割合が所定の値を超えているときには少なくとも２個連続して前記コネクションｊのパケットを受付拒否し、また、この算出された割合が所定の値以下であるときには受付拒否したコネクションｊのパケットについて連続した受付拒否を禁止することもできる。いずれの受付判定ポリシを採用するかはユーザの操作によって切替選択することができる。
【００２１】
また、パケット廃棄装置５は、受付拒否と判定すべきコネクションｊのパケットがバッファ６に存在しないときにはこの受付拒否と判定すべきパケットを受付許可と判定することもできる。
【００２２】
最低保証帯域を超えてネットワークに到着するパケットについてはこれにタグが付与され、パケット廃棄装置５は、受付拒否と判定すべきパケットに前記タグが付与されているときにはこの受付拒否と判定すべきパケットを受付許可と判定する。
【００２３】
キュー長監視部７は、キュー長Ｘｉの所定の変化周期以下の変化周期についてキュー長Ｘｉを検出する。あるいは、キュー長監視部７は、単位時間内のキュー長Ｘの最大値をキュー長Ｘｉの検出結果として当該単位時間毎に出力する。
【００２４】
また、図１２に示すように、バッファ６にモニタリングパケットを送出するモニタリングパケット挿入部１８を備え、キュー長監視部７は、このモニタリングパケット挿入部１８から送出されたモニタリングパケットがバッファ６に入力された時刻と当該モニタリングパケットがバッファ６から出力された時刻との時間差にしたがってキュー長Ｘｉを検出することもできる。
【００２５】
また、複数のサービスクラスが設けられ、コネクション識別部１では、到着するパケットのコネクションと共にそのパケットが属する前記サービスクラスも同時に識別し、仮想キュー管理部３では、コネクションｉ毎のバッファ６の前記サービスクラス毎のキュー長Ｘｉを検出し、コネクション情報格納部２では、コネクションｉ毎にあらかじめ定められた前記サービスクラス毎の重みＷｉの値を保持し、パケット廃棄装置５は、前記サービスクラス毎の許可キュー長ＡＱｉを
ＡＱｉ＝α（ΣＸｉ）・Ｗｉ／Ｗａｃｔ
として計算し、コネクションｉ毎の前記サービスクラス毎のキュー長Ｘｉがサービスクラス毎の当該許可キュー長ＡＱｉ以下のコネクションに属するパケットについてはこれを受付許可と判定することもできる。
【００２６】
以下では、本発明第一実施例をさらに詳細に説明する。
【００２７】
図１４は本発明を適用して最低帯域保証サービスの提供を行うネットワークの構成図である。発側ユーザは着側ユーザへとネットワークを通してパケットを送出する。ネットワークはユーザに対して契約している最低帯域までの転送レートの保証を行う。ネットワークの各リンクには複数ユーザが収容されており、余剰帯域に関しては料金や最低保証帯域などに基づいて決められる重みにしたがってユーザ間に分配される。
【００２８】
このように、本発明のパケット廃棄装置を備えた多重化装置は、図１４に示すように、ネットワークに設けることにより、帯域制御装置（ＵＰＣ：Usage Parameter Control）として用いることができる。また、パケット交換スイッチ内に設けることにより、当該スイッチ内のバッファの輻輳の回避にも利用できる。
【００２９】
まず、発側ユーザがネットワークにパケットを送出すると、ネットワークの入側エッジに位置するレート観測装置でユーザのネットワークへのパケット送出レートが計測される。パケットの送出レートが最低保証帯域を超えていれば、パケットのヘッダにＴａｇが付けられ、最低保証帯域以下で送出されるパケットに関してはそのままネットワークへと送出される。Ｔａｇが付けられていないパケットをネットワーク内で廃棄することなく着側ユーザまで転送することで最低帯域の保証を行う。本発明の多重化装置は中継ノード内に位置し、複数ユーザで共用しているリンク帯域を各ユーザに重みにしたがって分配するという処理を行う。
【００３０】
本発明第一実施例を図１ないし図１１を参照して説明する。多重化装置は、図１に示すように、コネクション識別部１、帯域制御部１０、バッファ部１１から構成されている。コネクション識別部１では到着したパケットのヘッダからコネクションを識別する。帯域制御部１０では、そのコネクション情報をもとに帯域制御に関する処理を行う。バッファ部１１は単純なＦＩＦＯ型のバッファ６でリンクに収容されている全ユーザ間で共用されている。
【００３１】
バッファ６にはキュー長監視部７が接続されており、バッファ６のキュー長とパケット入出力時に入出力パケットに関する情報を前段の仮想キュー管理部３に伝達する。ここで、入出力パケットに関する情報とは、バッファ６に入力またはバッファ６から出力されるパケットのパケット長およびそのパケットが属しているコネクションの識別番号を含む。
【００３２】
入力回線側からパケットが到着すると、コネクション識別部１でパケットのコネクション識別が行われ、後段の帯域制御部１０に送られ、バッファ６に入力するか否かの判定を行い、廃棄と判定されたパケットはその場で廃棄され、廃棄と判定されなかったパケットは後段のバッファ部１１へと入力されＦＩＦＯ規範にしたがって出力回線へと出力される。
【００３３】
本発明では帯域制御部１０でのパケット廃棄に基づく帯域制御が重要な役割を果たす。したがって、帯域制御部１０の処理について詳細に説明する。帯域制御部１０は、仮想キュー管理部３、許可キュー長計算部４、コネクション情報格納部２、パケット廃棄装置５により構成されている。
【００３４】
仮想キュー管理部３では、キュー長監視部７からの情報をもとにバッファ６のキュー長とコネクション毎のキュー長とを算出する。仮想キュー管理部３はコネクション情報格納部２と接続されており、算出されたコネクション毎の仮想的なキュー長はコネクション情報格納部２に記録される。
【００３５】
各キュー長の算出方法について説明する。まず、バッファ６のキュー長の算出に関しては、キュー長監視部７から伝達されるキュー長情報をそのまま仮想キュー管理部３に保持するだけである。次にコネクション毎の仮想キュー長の算出方法であるが、初期状態ではバッファ６は空であるため、各コネクションの仮想キュー長はゼロである。バッファ６にパケットが入力されると、そのパケットのパケット長とコネクション識別番号とがキュー長監視部７を通して伝達される。その情報をもとに仮想キュー管理部３はコネクション識別部１にアクセスし、該当コネクションの仮想キュー長に送られてきたパケット長を足し込むという処理を行う。パケット出力時にはこれとは逆に仮想キュー長から伝達されたパケット長を減算するという処理を行う。
【００３６】
図２はコネクション情報格納部２の一例で、仮想キュー管理部３で算出されたコネクション毎の仮想キュー長に関する情報、コネクションの重みに関する情報が格納されている。
【００３７】
次に、許可キュー長計算部４は、仮想キュー管理部３およびコネクション情報格納部２からバッファ６のキュー長に関する情報と、コネクション毎の仮想キュー長、重みに関する情報を受け取り、それらをもとに許可キュー長を計算する機能を持つ。ここでコネクションの許可キュー長とはバッファ６への入力が認められる最大キュー長を表す。
【００３８】
コネクションｉの許可キュー長ＡＱｉの計算方法について具体的に説明する。コネクションの重みをＷｉ、現在のバッファ６のキュー長の総和をΣＸｉとすると、
ＡＱｉ＝α（ΣＸｉ）・Ｗｉ／Ｗａｃｔ
で計算される。α（ΣＸｉ）はある連続関数で、図３ないし図９のグラフはキュー長の関数α（ΣＸｉ）の一例である。横軸にキュー長の総和ΣＸｉをとり、縦軸に関数α（ΣＸｉ）の値をとる。Ｗａｃｔはアクティブなコネクションの重みの和である。ここでアクティブなコネクションとは仮想キュー長がゼロより大きなコネクション、つまり少なくとも一つ以上のパケットがバッファ６に入っているコネクションのことである。
【００３９】
関数α（ΣＸｉ）はキュー長がある閾値（図ではＱｍａｘ）を超えるとゼロとなる。つまりキュー長がある閾値を超えた場合には、輻輳であると判定され、各コネクションの許可キュー長はゼロとなる。
【００４０】
例えば、図３の例では閾値Ｑｍａｘを超えない範囲では、関数α（ΣＸｉ）は一定の値をとり、閾値Ｑｍａｘを超えたときには関数α（ΣＸｉ）はゼロとなる。すなわち、閾値Ｑｍａｘを超えない範囲で許可キュー長ＡＱｉはコネクションの重みに比例して分配される。
【００４１】
図４の例では、キュー長の総和ΣＸｉがゼロから閾値Ｑｍａｘ未満の所定の値までの間で、途中までは関数α（ΣＸｉ）は緩やかに減少し、閾値Ｑｍａｘに近付くにつれて急に減少し、閾値Ｑｍａｘではゼロとなる。すなわち、許可キュー長ＡＱｉはキュー長の総和ΣＸｉが小さいときには、コネクションｉの重み以上に分配されるが、キュー長の総和ΣＸｉが所定の値を超えると急峻に許可キュー長ＡＱｉの分配率が低下する。
【００４２】
図５の例では、キュー長の総和ΣＸｉと関数α（ΣＸｉ）の値とがリニアに反比例する。すなわち、許可キュー長ＡＱｉはキュー長の総和ΣＸｉにリニアに反比例する。最も単純かつ基本的な制御例である。
【００４３】
図６の例では、キュー長の総和ΣＸｉと関数α（ΣＸｉ）の値とが二次関数にしたがって反比例する。すなわち、許可キュー長ＡＱｉはキュー長の総和ΣＸｉが小さいときには大きいが、キュー長の総和ΣＸｉが増加するとともに急に減少を始め、キュー長の総和ΣＸｉが閾値Ｑｍａｘに近付くにつれて減少が緩やかになる。これにより、キュー長の総和ΣＸｉが増え始めた時点でトラヒックの増加を強く抑えることができる。
【００４４】
図７の例では、キュー長の総和ΣＸｉと関数α（ΣＸｉ）の値とが図６に示す二次関数とは逆転した二次関数にしたがって反比例する。すなわち、許可キュー長ＡＱｉはキュー長の総和ΣＸｉが小さいときには大きいが、キュー長の総和ΣＸｉが増加するとともに徐々に減り始め、キュー長の総和ΣＸｉが閾値Ｑｍａｘに近付くにつれて減少が急になる。これにより、キュー長の総和ΣＸｉが閾値Ｑｍａｘに近付くにつれてトラヒックの増加を強く抑えることができる。
【００４５】
図８の例では、キュー長の総和ΣＸｉと関数α（ΣＸｉ）の値とが段階的に反比例する。すなわち、許可キュー長ＡＱｉはキュー長の総和ΣＸｉが小さいときには大きいが、キュー長の総和ΣＸｉが増加するとともに徐々に減り始め、所定のキュー長の総和ΣＸｉから急に減り始め、キュー長の総和ΣＸｉが閾値Ｑｍａｘに近付くにつれて再び減少が緩やかになる。これにより、キュー長の総和ΣＸｉがゼロと閾値Ｑｍａｘとの中間付近にあるときにトラヒックの増加を強く抑えることができる。
【００４６】
図９の例では、キュー長の総和ΣＸｉと関数α（ΣＸｉ）の値とが図８の例とは逆転して段階的に反比例する。すなわち、許可キュー長ＡＱｉはキュー長の総和ΣＸｉが小さいときには大きいが、キュー長の総和ΣＸｉが増加するとともに急に減り始め、所定のキュー長ΣＸｉから緩やかに減り始め、キュー長の総和ΣＸｉが閾値Ｑｍａｘに近付くにつれて再び急に減り始める。これにより、キュー長の総和ΣＸｉがゼロから増え始めた時点と閾値Ｑｍａｘに近付いた時点とでトラヒックの増加を強く抑えることができる。
【００４７】
また、キュー長の総和ΣＸｉとしては現在のキュー長（パケット到着時のキュー長の瞬間値）を用いるとしているが、キュー長の総和ΣＸｉとして一定時間内のキュー長の平均値を採用してもよい。
【００４８】
パケット廃棄装置５は許可キュー長とコネクション毎の仮想キュー長から到着したパケットをバッファ６へ入力するか廃棄するかの判定をする。図１０は確定的な廃棄処理を行うパケット到着時の処理フローを示すフローチャートであるが、図１０に示すように、仮想キュー長Ｘｉが許可キュー長ＡＱｉ以下であればバッファ６に入力し、許可キュー長ＡＱｉを超えていれば、Ｔａｇが付けられているパケットは廃棄し、Ｔａｇが付けられていないパケットはバッファ６へ入力することにより、常に各コネクションの最低帯域は保証しつつ、バッファ６の占有率が公平になるように制御する。
【００４９】
また、仮想キュー長が許可キュー長を超えていた場合には、上記のように確定的にパケット廃棄するのではなく、確率的にパケット廃棄することも可能である。図１１は確率的な廃棄処理を行うパケット到着時の処理フローを示すフローチャートであるが、図１１に示すように、許可キュー長をＡＱｉ、仮想キュー長の総和をΣＸｉとすると、廃棄確率Ｐは、
Ｐ＝（ΣＸｉ−ＡＱｉ）／ΣＸｉ
で与えられる。つまり、仮想キュー長が許可キュー長を超えた場合には、超えた割合だけ落すというものである。確率的な廃棄によって帯域制御することで、一つのコネクションに注目した場合には、仮想キュー長が許可キュー長を超えたときでも、連続してパケットが廃棄される現象が、確定的にパケット廃棄する場合よりも減少するため、ＴＣＰのレート制御との親和性が高くなるといえる。バッファ６へと入力されたパケットはＦＩＦＯ規範にしたがって出力回線へと出力される。
【００５０】
図１１における擬似乱数Ｒａｎｄの生成は、パケット到着毎に行われ、廃棄確率Ｐと擬似乱数Ｒａｎｄとを比較した結果に基づき廃棄を実行することにより、実際に廃棄確率Ｐによる廃棄を実現することができる。例えば、廃棄確率Ｐが０．５であるときに、擬似乱数Ｒａｎｄが０．５よりも大きい値をとる確率もまた０．５であり、擬似乱数Ｒａｎｄが０．５よりも大きい場合に廃棄を実行することにより、廃棄確率Ｐにしたがった廃棄が行われる。
【００５１】
本発明のパケット廃棄装置５が適用される多重化装置はキュー長をもとに網の輻輳状態を推定し、輻輳であると判定されれば許可キュー長はゼロに等しくなり、最低保証帯域以下のレートで網に送出されているパケットのみを網は転送する。キュー長がある閾値以下のときは、余剰帯域が存在すると判断され、各コネクションは重みに比例したバッファの占有によって、帯域をコネクション間に公平に配分される。
【００５２】
また、ハードウェア構成が簡易なＦＩＦＯバッファでＧＦＲサービスを実現しつつ、ＷＲＲ方式等のようなコネクション毎に個別にバッファを持ってパケットの読出制御を行う方法と同様に余剰帯域を公平にコネクション間の分配することが可能である。また、一つのバッファを多数のコネクションで共用するため、コネクション毎に個別にバッファを持つ方式に比べて、統計多重効果により必要なバッファ量を削減できるという利点もある。
【００５３】
次に、本発明第一実施例におけるパケット廃棄装置５の特徴として、パケット廃棄装置５が受付拒否したコネクションｊのキュー長Ｘｊが前記許可キュー長ＡＱｊを超えている割合を算出し、この算出された割合が所定の値を超えているときには少なくとも２個連続してコネクションｊのパケットを受付拒否し、この算出された割合が所定の値以下であるときには受付拒否したコネクションｊのパケットについて連続した受付拒否を禁止する。
【００５４】
すなわち、急激にキュー長Ｘｊが許可キュー長ＡＱｊを超えたときには、輻輳発生を回避するために急激なトラヒック制御を行う必要がある。そのような事態が発生したときには、パケットを連続して廃棄することにより対処することができる。反対に、緩やかにキュー長Ｘｊが許可キュー長ＡＱｊを超えたときには、緩やかなトラヒック制御を行って安定したトラヒック制御を実現することができる。
【００５５】
また、キュー長監視部７の機能として、キュー長Ｘｉの所定の変化周期以下の変化周期についてキュー長Ｘｉを検出する。これにより、瞬間的なキュー長Ｘｉの変化を吸収し、外乱によるトラヒック制御の誤動作を回避することができる。
【００５６】
あるいは、キュー長監視部７の機能として、単位時間内のキュー長Ｘｉの最大値をキュー長Ｘｉの検出結果として当該単位時間毎に出力する。これにより、瞬間的なキュー長Ｘｉの変化を吸収し、外乱によるトラヒック制御の誤動作を回避することができる。
【００５７】
図１２に示すように、バッファ６にモニタリングパケットを送出するモニタリングパケット挿入部１８を備え、キュー長監視部７は、このモニタリングパケット挿入部１８から送出されたモニタリングパケットがバッファ６に入力された時刻と当該モニタリングパケットがバッファ６から出力された時刻との時間差にしたがってキュー長Ｘを検出する。
【００５８】
これにより、単にパケット蓄積数に基づくキュー長Ｘｉの検出と比較すると、実際の遅延時間等のパラメータを含めた実効的なキュー長Ｘｉを検出することができる。
【００５９】
また、一つのコネクションに属するパケットをさらに二つのサービスクラスに分類して取り扱うこともできる。一つのサービスクラスは、リアルタイム性を重要視するパケットに対するリアルタイム（Ｒ）クラスであり、もう一つのサービスクラスは、リアルタイム性を重要視しないパケットに対するノンリアルタイム（ＮＲ）クラスである。
【００６０】
このためには、図１に示すコネクション識別部１において、到着するパケットのコネクションを識別すると共にそのパケットのサービスクラスを識別する。また、仮想キュー管理部３では、バッファ６に蓄積されたパケットのコネクションの情報と共にサービスクラスの情報も取得する。これにより、コネクション情報格納部２には、図１３に示すようなテーブルを設けることができる。
【００６１】
例えば、コネクション＃１についてみると、仮想キュー長としてリアルタイムクラスに属するＸ１（Ｒ）およびノンリアルタイムクラスに属するＸ１（ＮＲ）が記録されている。また、重みとしてリアルタイムクラスの重みＷ１（Ｒ）およびノンリアルタイムクラスの重みＷ１（ＮＲ）が記録されている。重みＷ１（Ｒ）はＷ１（ＮＲ）よりも重く設定されており、リアルタイムクラスに属するパケットをノンリアルタイムクラスに属するパケットに優先して読出すことができる。
【００６２】
これにより、リアルタイム性を重要視するパケットの遅延を少なくすることができるため、ユーザに対するＱｏＳを向上させることができる。
【００６３】
（第二実施例）
本発明のパケット廃棄装置が適用される本発明第二実施例の多重化装置を図１５を参照して説明する。図１５は本発明第二実施例の多重化装置のブロック構成図である。
【００６４】
多重化装置は、図１５に示すように、到着する固定長パケットであるセルの属するコネクション１〜ｋを識別するコネクション識別部１と、当該セルの受付可否を判定する受付判定部１５と、この受付判定部１５の判定結果にしたがってセルを一時蓄積するＦＩＦＯ型のバッファ６と、コネクションｉ毎にセルの到着レートＲｉを検出するレート検出部８と、コネクションｉ毎にあらかじめ定められた重みＷｉの値を保持するコネクション情報格納部２とを備え、セルの到着レートＲｉにはあらかじめ閾値となる最大レートが設定され、当該最大レートを超えるとほぼゼロになる前記セルの到着レートＲｉの総和ΣＲｉの連続関数をβ（ΣＲｉ）とし、バッファ部１１のバッファ６に１以上のセルが蓄積されているコネクションｉの前記重みの和をＷａｃｔとし、許可到着レート計算部１４は、許可到着レートＡＣＲｉを
ＡＣＲｉ＝β（ΣＲｉ）・Ｗｉ／Ｗａｃｔ
として計算し、受付判定部１５は、コネクションｉ毎のセルの到着レートＲｉが当該許可到着レートＡＣＲｉ以下のコネクションに属するセルについてはこれを受付許可と判定する。
【００６５】
本実施例では、複数コネクションが混在して一つのバッファ６に蓄積されている状況下における実際のバッファ６のキュー長に対してキュー長監視部７および仮想キュー管理部３によりコネクションｉ毎にバッファ６のキュー長Ｘｉを検出したものを仮想キュー長という。
【００６６】
図１４は本発明を適用して最低帯域保証サービスの提供を行うネットワークの構成図である。発側ユーザは着側ユーザへとネットワークを通してパケットを送出する。ネットワークはユーザに対して契約している最低帯域までの転送レートの保証を行う。ネットワークの各リンクには複数ユーザが収容されており、余剰帯域に関しては料金や最低保証帯域などに基づいて決められる重みにしたがってユーザ間に分配される。
【００６７】
このように、本発明のパケット廃棄装置を備えた多重化装置は、図１４に示すように、ネットワークに設けることにより、帯域制御装置（ＵＰＣ：Usage Parameter Control）として用いることができる。また、パケット交換スイッチ内に設けることにより、当該スイッチ内のバッファの輻輳の回避にも利用できる。
【００６８】
まず、発側ユーザがネットワークにパケットを送出すると、ネットワークの入側エッジに位置するレート観測装置でユーザのネットワークへのパケット送出レートが計測される。パケットの送出レートが最低保証帯域を超えていれば、パケットのヘッダにＴａｇが付けられ、最低保証帯域以下で送出されるパケットに関してはそのままネットワークへと送出される。Ｔａｇが付けられていないパケットをネットワーク内で廃棄することなく着側ユーザまで転送することで最低帯域の保証を行う。本発明の多重化装置は中継ノード内に位置し、複数ユーザで共用しているリンク帯域を各ユーザに重みにしたがって分配するという処理を行う。
【００６９】
本発明第二実施例におけるパケット廃棄装置としての図１５に示す受付判定部１５の特徴として、受付判定部１５が受付拒否したコネクションｊの到着レートＲｊが許可到着レートＡＣＲｊを超えている割合を算出し、この算出された割合が所定の値を超えているときには少なくとも２個連続してコネクションｊのパケットを受付拒否し、この算出された割合が所定の値以下であるときには受付拒否したコネクションｊのパケットについて連続した受付拒否を禁止する。
【００７０】
すなわち、急激に到着レートＲｊが許可到着レートＡＣＲｊを超えたときには、輻輳発生を回避するために急激なトラヒック制御を行う必要がある。そのような事態が発生したときには、パケットを連続して廃棄することにより対処することができる。反対に、緩やかに到着レートＲｊが許可到着レートＡＣＲｊを超えたときには、緩やかなトラヒック制御を行って安定したトラヒック制御を実現することができる。
【００７１】
【発明の効果】
以上説明したように、本発明によれば、通信網内に設置することにより、通信網に収容されている各コネクションに対し、輻輳時においても契約している最低帯域を保証しつつ、通常時（非輻輳時）には、余剰帯域をコネクション間で公平に分配し、より効率的な網資源の利用を可能にすることができる。また、高速回線においても経済的に実現可能なパケット廃棄装置を実現することができる。さらに、パケット交換スイッチ等のノード内に設置することにより、簡単なハードウェア構成を実現し、効率の良いノード内の輻輳回避を実現することができる。
【図面の簡単な説明】
【図１】本発明第一実施例の多重化装置のブロック構成図。
【図２】コネクション情報格納部のテーブル例を示す図。
【図３】関数α（ΣＸｉ）の例を示す図。
【図４】関数α（ΣＸｉ）の例を示す図。
【図５】関数α（ΣＸｉ）の例を示す図。
【図６】関数α（ΣＸｉ）の例を示す図。
【図７】関数α（ΣＸｉ）の例を示す図。
【図８】関数α（ΣＸｉ）の例を示す図。
【図９】関数α（ΣＸｉ）の例を示す図。
【図１０】確定的な廃棄処理を行うパケット到着時の処理フローを示すフローチャート。
【図１１】確率的な廃棄処理を行うパケット到着時の処理フローを示すフローチャート。
【図１２】モニタリングパケットを用いるキュー長検出を説明するための図。
【図１３】コネクション情報格納部のテーブル例を示す図。
【図１４】本発明を適用したネットワーク構成の一例を示す図。
【図１５】本発明第二実施例の多重化装置のブロック構成図。
【図１６】従来のＷＲＲ方式の概要を説明するための図。
【符号の説明】
１ コネクション識別部
２ コネクション情報格納部
３ 仮想キュー管理部
４ 許可キュー長計算部
５ パケット廃棄装置
６ バッファ
７ キュー長監視部
８ レート検出部
１０ 帯域制御部
１１ バッファ部
１４ 許可到着レート計算部
１５ 受付判定部
１８ モニタリングパケット挿入部
【図１】
0003989197.tif 000002
【図２】
0003989197.tif 000003
【図３】
0003989197.tif 000004
【図４】
0003989197.tif 000005
【図５】
0003989197.tif 000006
【図６】
0003989197.tif 000007
【図７】
0003989197.tif 000008
【図８】
0003989197.tif 000009
【図９】
0003989197.tif 000010
【図１０】
0003989197.tif 000011
【図１１】
0003989197.tif 000012
【図１２】
0003989197.tif 000013
【図１３】
0003989197.tif 000014
【図１４】
0003989197.tif 000015
【図１５】
0003989197.tif 000016
【図１６】
0003989197.tif 000017