JP3556557B2 - Contention control device - Google Patents
Contention control device Download PDFInfo
- Publication number
- JP3556557B2 JP3556557B2 JP2000033499A JP2000033499A JP3556557B2 JP 3556557 B2 JP3556557 B2 JP 3556557B2 JP 2000033499 A JP2000033499 A JP 2000033499A JP 2000033499 A JP2000033499 A JP 2000033499A JP 3556557 B2 JP3556557 B2 JP 3556557B2
- Authority
- JP
- Japan
- Prior art keywords
- value
- packet
- buffer
- granularity
- read
- 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 - Fee Related
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は大規模で高速なパケット交換機に利用する。本発明は複数の入力回線から到来する一つの出力回線宛てのパケットに対して互いに衝突することなく、公平に出力機会を与える技術に関する。
【０００２】
【従来の技術】
従来の競合制御装置を図１２に示す。入力回線＃１〜＃Ｎから到来したパケットは、それぞれのバッファ１−１〜１−Ｎに入力される。図１２の例では、入力回線＃１〜＃Ｎ（図１２の例では、Ｎ＝４）に対応してバッファ１−１〜１−Ｎがあるが、これらは、例えば、各入力ポート毎にバッファが備えられている場合もあるし、各クラス毎にバッファが備えられている場合もある。パケットは、一般に可変長パケットである。
【０００３】
読出制御部１０は、Ｎ個のバッファ１−１〜１−Ｎから１個のバッファ１−ｉ（ｉは１〜Ｎのいずれか）を選択し、その先頭パケットは、パケット読出部１１により読み出される。以下では、読出許可が与えられたパケットを読出パケットという。また、読出許可が与えられたバッファを読出バッファという。
【０００４】
読出パケットを選択する方法の１つに、ラウンドロビン法（以下、ＲＲ：Ｒｏｕｎｄ Ｒｏｂｉｎと記す）がある。ＲＲは、トークンが各バッファを順番に巡回し、出力のリクエストを出しているバッファを順次選択する方法である。あるバッファを読出バッファとして選択したら、巡回方向の次のバッファからスタートしてリクエストをサーチし、次の読出バッファを選択していく。
【０００５】
ＲＲでは、選択の回数が公平に与えられるが、パケット長が長いパケットを有するバッファは、パケット長が短いパケットを有するバッファに比べて、多くのトラヒックを出力回線に送出することになる。したがって、平均パケット長がバッファ毎に異なる場合には、トラヒック量（スループット）の公平性を提供することができない。
【０００６】
そこで、このＲＲの問題を解決するために、デフィシットラウンドロビン法（以下、ＤＲＲ：Ｄｅｆｉｃｉｔ Ｒｏｕｎｄ Ｒｏｂｉｎと記す）が提案されている。従来のＤＲＲについて説明する。図１３は従来のＤＲＲの読出制御部のブロック構成を示している。図１４は従来のＤＲＲの読出制御部の動作を示すフローチャートである。図１５は各バッファにパケットが蓄積されている例を示している。
【０００７】
ＤＲＲで用いられるパラメータとして、粒度ｑ、デフィシット値ｄ、キューの先頭のパケット長Ｌがある。粒度ｑは競合制御装置全体に、あらかじめ一つ与えられる数値であり、図１３に示す粒度ｑメモリ２０に設定される。これに対し、デフィシット値は、各バッファ１−１〜１−４毎に設定される数値であり、初期値はゼロとする。
【０００８】
図１４のフローを説明する。トークンは、各バッファを巡回している。前のバッファから、トークンを受けたあるバッファに着目する。キューにパケットがあるかどうかをチェックする。キューにパケットがなければ、ｄ＝０として、次のバッファへトークンを渡す。キューにパケットがあれば、ｄ←ｄ＋ｑとする。Ｌがｄ以下であれば、当該バッファの先頭パケットが読出パケットとして選択され、ｄ←ｄ−Ｌとなる。Ｌがｄ以下でないならば、ｄの値はそのままである。次のバッファにトークンを渡す。
【０００９】
図１５の場合について、図１６の具体例を用いて説明する。図１６中の数字は、各バッファのｄの値を示している。図１６では、粒度ｑ＝５００と設定する。バッファ１−１からスタートする。バッファ１−１のキューにパケットがあるので、ｄ←ｄ＋ｑにより、ｄ＝５００となる。Ｌ＝８００である。Ｌ≦ｄでないので、バッファ１−１の先頭パケットは、読出パケットとして選択されずに、バッファ１−２に進む。バッファ１−２では、ｄ＝５００となり、Ｌ＝６００なので選択されない。バッファ１−３では、ｄ＝５００となり、Ｌ＝４００で、Ｌ≦ｄを満たし、先頭パケットが読出パケットとして選択され、ｄ←ｄ−Ｌ＝５００−４００＝１００となる（図中の四角の囲みは読出バッファを示す）。次の読出バッファをサーチするために、トークンは、バッファ１−４からスタートする。バッファ１−４では、ｄ＝５００となり、Ｌ＝１０００なので選択されない。次にバッファ１−１に進む。バッファ１−１では、現在のｄの値がｄ＝６００である。トークンを受けとると、ｄ←ｄ＋ｑ＝５００＋５００＝１０００となり、Ｌ＝８００であるから、Ｌ≦ｄを満たし、先頭パケットが読出パケットとして選択され、ｄ←ｄ−Ｌ＝１０００−８００＝２００となる。次の読出バッファをサーチする。バッファ１−２も同様に、ｄ←ｄ＋ｑ＝５００＋５００＝１０００となり、Ｌ＝６００であるから、Ｌ≦ｄを満たし、読出バッファとして選択され、ｄ←ｄ−Ｌ＝１０００−６００＝４００となる。次の読出バッファをサーチする。バッファ１−３では、キューにパケットがないのでｄの値はリセットされてｄ＝０となる。同様の動作が読出バッファをサーチするために繰り返される。
【００１０】
これにより、読出バッファを選択するためには、ｄの値をＬの値以上にする必要がある。長いパケットは、短いパケットより、読出パケットに選択される回数が減るが、平均パケット長がバッファ毎に異なる場合でも、トラヒック量（スループット）の公平性を提供することができる。ただし、公平性や高スループットを提供することができるのは、ｑを適切に設定したときに限る。
【００１１】
もし、図１７のように、ｑを大きく設定すると、公平性が提供できなくなる。ｑが十分に大きい場合には、トークンが各バッファに巡回してきたときに、ｄ←ｄ＋ｑで、ｄを更新すると、Ｌより大きくなる場合が多くなり、パケット長に関係なく、読出パケットが選択されることになる。結果的に単純なＲＲを実行することと等価になり、公平性が提供できなくなる。
【００１２】
一方、図１８のように、ｑを小さく設定する場合を考える。ｑがＬに比べて十分に小さい場合には、トークンが各バッファに巡回してきたときに、ｄ←ｄ＋ｑで、ｄを更新しても、Ｌの値よりまだ小さいので、数回の巡回により、ｄを何回も更新する必要がある。図１８の例では、バッファ１−３が４回の更新後に、読出選択がされる。このように、１つの読出バッファが選択されるまでトークンが巡回する回数が多くなるので、計算量が増加して、読出選択に必要な所要時間が大きくなる。これにより、出力回線が空いている状態でも、読出選択の所要時間が大きくなり、読み出せないことにより、スループットが低下する。
【００１３】
【発明が解決しようとする課題】
このように、適切な粒度ｑを設定しない限り、ＤＲＲの性能は悪化する。適切なｑを設定するためには、あらかじめパケット長の分布を予測する必要がある。しかし、不確定なトラヒック入力に対しては、このパケット長の予測は困難である。
【００１４】
また、ある期間のパケット長の分布を予測して、適切なｑを設定したとしても、パケット長の分布は、時々刻々と変化するので、ある時刻で設定したｑは、時間が経過すると必ずしも適切であるとは限らない。
【００１５】
このように、従来の競合制御装置では、粒度ｑが固定的に設定されるので、この値が適切な値でないと、公平性や高スループットの性能が提供できない。
【００１６】
本発明は、このような背景に行われたものであって、平均パケット長が変化するトラヒック環境下でも公平性や高スループットの性能が提供できる競合制御装置を提供することを目的とする。
【００１７】
【課題を解決するための手段】
本発明は、各バッファのパケット読み出し状況を観察し、その観察結果にしたがって粒度の数値を最適な値に可変することを特徴とする。
【００１８】
すなわち、本発明は、複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、所定の数値が粒度として与えられ、前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、前記読出制御部では、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与える読出パケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含む競合制御装置である。
【００１９】
ここで、本発明の特徴とするところは、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備えるところにある。
【００２０】
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定回数になったときには粒度を増加する演算を行なう手段を含む構成とすることが望ましい。
【００２１】
すなわち、トークンが巡回したときに、デフィシット値が先頭パケット長より小さければ、その先頭パケットは読出パケットとして選択されない。このようにして先頭パケットが読出パケットとして選択されないバッファが連続するという状況は、あらかじめ設定されている粒度が適当ではなく、その粒度に対し、実際の平均パケット長が長いことが推察される。したがって、粒度を増加する演算を行うことによって、最適な粒度を与えることができる。
【００２２】
また、あらかじめ平均パケット長が緩やかに変化することが予想されるようなトラヒック環境下では、さらに長期間にわたりデフィシット値と先頭パケット長とを比較し、その上で粒度を変更した方が適当である。このような場合には、前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定周回数になったときには粒度を増加する演算を行なう手段を含む構成とすることもできる。
【００２３】
前記増加する演算を行う手段は、現在の粒度の値に所定値を加算する手段を含む構成としたり、あるいは、現在の粒度の値に１より大きい所定値を乗算する手段を含む構成とすることができる。
【００２４】
現在の粒度の値に所定値を加算する構成は、比較的緩やかな粒度の増加を期待する場合に適する。また、現在の粒度の値に１より大きい所定値を乗算する構成は、比較的急峻な粒度の増加を期待する場合に適する。
【００２５】
一方で、前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定回数になったときには粒度を減少する演算を行なう手段を含む構成とすることが望ましい。
【００２６】
すなわち、トークンが巡回したときに、デフィシット値が先頭パケット長より大きければ、その先頭パケットは読出パケットとして選択される。このようにして先頭パケットが読出パケットとして選択されるバッファが連続するという状況は、あらかじめ設定されている粒度が適当ではなく、その粒度に対し、実際の平均パケット長が短いことが推察される。したがって、粒度を減少する演算を行うことによって、最適な粒度を与えることができる。
【００２７】
また、あらかじめ平均パケット長が緩やかに変化することが予想されるようなトラヒック環境下では、さらに長期間にわたりデフィシット値と先頭パケット長とを比較し、その上で粒度を変更した方が適当である。このような場合には、前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より大きいことが連続して所定周回数になったときには粒度を減少する演算を行なう手段を含む構成とすることもできる。
【００２８】
前記減少する演算を行う手段は、現在の粒度の値に所定値を減少する手段を含む構成としたり、あるいは、現在の粒度の値に１より小さい所定値を乗算する手段を含む構成とすることができる。
【００２９】
現在の粒度の値に所定値を減少する構成は、比較的緩やかな粒度の減少を期待する場合に適する。また、現在の粒度の値に１より小さい所定値を乗算する構成は、比較的急峻な粒度の減少を期待する場合に適する。
【００３０】
また、読出帯域確保要求にしたがって、要求元のバッファに対しては、確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては、残余帯域を割当てることにより、あらかじめ各バッファに帯域が割当てられる場合には、前記複数のバッファのそれぞれに読み出す重みを与える手段が設けられ、この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含む構成とすることが望ましい。
【００３１】
このように、あらかじめ各バッファに帯域が割当てられる場合には、読出アルゴリズムに割当帯域に応じた重みを加味することにより、公平にパケットを読み出すことができる。
【００３２】
【発明の実施の形態】
本発明実施例の競合制御装置の構成を図１を参照して説明する。図１は本発明実施例の読出制御部のブロック構成図である。競合制御装置の全体構成は図１２と共通である。
【００３３】
本発明は、複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファ１−１〜１−４と、この複数のバッファ１−１〜１−４から読み出すべきパケットを選択する読出制御部１０と、パケットを出力回線へ読み出すパケット読出部１１とを備え、所定の数値が粒度ｑとして与えられ、バッファ１−１〜１−４にはそれぞれ初期値がゼロであるデフィシット値ｄが与えられ、読出制御部１０では、トークンが巡回してきたバッファ１−ｉについて、前記粒度ｑを当該バッファ１−ｉのデフィシット値ｄに加算し、当該デフィシット値ｄと当該バッファ１−ｉの先頭パケット長Ｌとを比較して当該デフィシット値ｄが先頭パケット長Ｌ以上のときに当該バッファ１−ｉの先頭パケットを読出許可を与える読出パケットとして選択を行なうとともに当該デフィシット値ｄから当該先頭パケット長Ｌを減算する競合制御装置である。
【００３４】
ここで、本発明の特徴とするところは、前記粒度ｑをバッファ１−１〜１−４のパケット読み出しの状態に基づいて可変に設定する粒度ｑ可変制御部２２を備えたところにある。
【００３５】
（第一実施例）
本発明第一実施例を図１２、図１および図２、図１４を参照して説明する。図２は粒度ｑの可変制御アルゴリズムを示す図である。図１２および図１４の動作は、従来の競合制御装置の動作と同様なので、図２を用いて粒度ｑの可変制御アルゴリズムを説明する。
【００３６】
あるバッファを読出選択後、トークンによるサーチにより、次の読出バッファを見つけたかを判定する。もし、ｎ回連続で、Ｌ＞ｄとなるならば、ｑ←ｑ（１＋△ｉｎｃ）として、粒度ｑを増加させる。ｎや△ｉｎｃは、あらかじめ設定しておいた値である。もし、ｎ回連続で、Ｌ＞ｄとならないならば、ｑは変化させない。ｑを増加させた後、さらに、ｎ回連続でＬ＞ｄとなるならば、ｑ←ｑ（１＋Δｉｎｃ）とする。この動作により、ｑが適切な値より小さい場合に、ｑを増加させることができる。
【００３７】
（第二実施例）
図３を用いて、粒度ｑの可変制御アルゴリズムを説明する。第一実施例では、ｎ回連続で、Ｌ＞ｄとなるかという判定基準であるが、第二実施例では、トークンがＲ周回連続で、Ｌ＞ｄとなるかという判定基準である。Ｒは、あらかじめ設定しておいた値である。
【００３８】
（第三実施例）
図４を用いて、粒度ｑの可変制御アルゴリズムを説明する。第一実施例では、ｑ←ｑ（１＋△ｉｎｃ）としてｑの値を増加させていた。第三実施例では、ｑ←ｑ＋△ｉｎｃとして、ｑの値を増加させる。
【００３９】
（第四実施例）
図５を用いて、粒度ｑの可変制御アルゴリズムを説明する。トークンによるサーチにより、Ｌ＞ｄとなったバッファからさらにサーチを進め、リクエストを出しているバッファが、Ｌ＞ｄであれば、読出バッファとして選択される。Ｌ≦ｄとなる場合がｍ回連続で続いたときには、ｑ←ｑ（１−△ｄｅｃ）として、粒度ｑを減少させる。ｍや△ｄｅｃは、あらかじめ設定しておいた値である。もし、ｍ回連続で、Ｌ≦ｄとならないならば、ｑは変化させない。ｑを減少させた後、さらに、ｍ回連続でＬ≦ｄとなるならば、ｑ←ｑ（１−△ｄｅｃ）とする。この動作により、ｑが適切な値より大きい場合に、ｑを減少させることができる。
【００４０】
（第五実施例）
図６を用いて、粒度ｑの可変制御アルゴリズムを説明する。第四実施例では、ｍ回連続で、Ｌ≦ｄとなるかという判定基準であるが、第五実施例では、トークンがＳ周回連続で、Ｌ≦ｄとなるかという判定基準である。Ｓは、あらかじめ設定しておいた値である。
【００４１】
（第六実施例）
図７を用いて、粒度ｑの可変制御アルゴリズムを説明する。第四実施例では、ｑ←ｑ（１−△ｄｅｃ）として、ｑの値を減少させていた。第六実施例では、ｑ←ｑ−△ｄｅｃとして、ｑの値を減少させる。
【００４２】
（第七実施例）
本発明第一ないし第六実施例までは、各バッファに対し、均等に読み出しが行えるようにしていた。本発明第七実施例では、各バッファに重みが与えられ、その重みの割合に応じてパケットを読み出す。図８は、本発明第七実施例の競合制御装置のブロック構成図である。
【００４３】
図８では、重み付与部１２により、バッファ１−ｉ（ｉは１〜４のいずれか）の重みをｗｅｉｇｈｔ［ｉ］として与えている。図９に本発明第七実施例の読み出しアルゴリズムを示す。本発明第一実施例の図１４のアルゴリズムとの相違は、先頭パケットのパケット長Ｌと、デフィシット値ｄとｗｅｉｇｈｔ［ｉ］の積とを比較しているところが異なる。重みが大きいほど、その判断式がｙｅｓとなる可能性が高いので、多くの読み出し機会が与えられる。重みが小さいほど、その判断式がｎｏとなる可能性が高いので、読み出し機会が少なくなる。したがって、読み出しの割合は、ｗｅｉｇｈｔ［ｉ］の重みに比例するようになる。
【００４４】
粒度の可変制御は、本発明第一ないし第六実施例に示した方式を適用することができる。
【００４５】
ここで、重み、ｗｅｉｇｈｔ［ｔ］の与え方を説明する。以下に、説明に使用する記号と初期化する値を示す。
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ：帯域確保していない残余帯域
Ｃ：出力回線速度
ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ：帯域確保していないポート数
Ｎ：バッファの数
ｂａｎｄｗｉｄｔｈ［ｉ］：バッファｉの割当帯域
ｒｅｓｅｖｅｄ＿ｉｃｏｎ［ｉ］：バッファｉが帯域を確保している場合は“０”、バッファｉが帯域を確保していない場合は“１”
ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ：要求帯域
ｒｅｌｅａｓｅ＿ｂａｎｄｗｉｄｔｈ：解放帯域
ｗｅｉｇｈｔ［ｉ］：バッファｉの割当帯域
初期化
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ＝Ｃ
ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ＝Ｎ
ｂａｎｄｗｉｄｔｈ［ｉ］＝Ｃ／Ｎ ｆｏｒ ａｌｌ Ｎ
ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝１
図１０は、バッファｓに帯域確保リクエストが到着した場合の重みの与え方を示している。パケット内に帯域確保リクエスト情報を含んでいて、帯域確保リクエストが実行されるやり方である。また、制御信号線を介して、帯域確保リクエストが実行されるやり方もある。
【００４６】
バッファｓに帯域確保リクエストが到着した後に、（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）−（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）が０以上であれば、リクエストを承認する。そうでなければ、リクエストを拒絶する。リクエストを承認した後に、
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）−（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）
ｂａｎｄｗｉｄｔｈ［ｓ］＝ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ
ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｓ］＝０
ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓの値を一つ減らす。
【００４７】
次にすべてのバッファｉに対して、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０であれば、
ｂａｎｄｗｉｄｔｈ［ｉ］＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）／（ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ）
ｗｅｉｇｈｔ［ｉ］＝ｂａｎｄｗｉｄｔｈ［ｉ］×Ｎ／Ｃ
とする。
ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０でないならば、ｂａｎｄｗｉｄｔｈ［ｉ］はそのままとする。
【００４８】
図１１は、バッファｓに帯域解放リクエストが到着した場合の重みの与え方を示している。まず、
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）＋（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）
ｂａｎｄｗｉｄｔｈ［ｓ］＝（ｂａｎｄｗｉｄｔｈ［ｓ］）−（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）
を実行する。ｂａｎｄｗｉｄｔｈ［ｓ］＝０ならば、バッファｓにおいて、帯域が確保されていないことになるので、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｓ］＝１とし、ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓの値を１つ増やす。
ｂａｎｄｗｉｄｔｈ［ｓ］＝０でないならば、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｓ］とｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓの値はそのままである。
【００４９】
次にすべてのバッファｉに対して、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０であれば、
ｂａｎｄｗｉｄｔｈ［ｉ］＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）／ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ
ｗｅｉｇｈｔ［ｉ］＝ｂａｎｄｗｉｄｔｈ［ｉ］×Ｎ／Ｃ
とする。ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０でないならば、ｂａｎｄｗｉｄｔｈ［ｉ］はそのままとする。
【００５０】
（実施例まとめ）
上記のｎ、Δｉｎｃ、Ｒ、ｍ、Δｄｅｃ、Ｓは、あらかじめ設定しておいた値であるが、これらの値は、競合制御装置が設置されるトラヒック環境をあらかじめ観察し、その観察結果を検討することにより決定される。
【００５１】
ｎ、Ｒ、ｍ、Ｓの数値については、数値が小さくなればなるほど、粒度ｑの変化は俊敏になる。また、Δｉｎｃ、Δｄｅｃの数値については、数値が大きくなればなるほど粒度ｑの変化巾は大きくなる。
【００５２】
例えば、到来するパケットの平均パケット長が緩やかに変化するトラヒック環境下であれば、平均トラヒック長の変化に対して緩やかに粒度ｑを可変することにより、最適な粒度ｑを与えることができる。したがって、ｎ、Ｒ、ｍ、Ｓの値は比較的大きい方がよい。また、このときの粒度ｑの変化巾は小さい方が適当である。したがって、Δｉｎｃ、Δｄｅｃの値は比較的小さい方がよい。
【００５３】
その反対に、到来するパケットの平均パケット長が頻繁に変化するトラヒック環境下であれば、平均トラヒック長の変化に対して俊敏に粒度ｑを可変することにより、最適な粒度ｑを与えることができる。したがって、ｎ、Ｒ、ｍ、Ｓの値は比較的小さい方がよい。また、このときの粒度ｑの変化巾は大きい方が適当である。したがって、Δｉｎｃ、Δｄｅｃの値は比較的大きい方がよい。
【００５４】
このような検討に基づき、上記のｎ、Δｉｎｃ、Ｒ、ｍ、Δｄｅｃ、Ｓの値は決定される。
【００５５】
また、読出帯域確保要求にしたがって、要求元のバッファに対しては、確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てることにより、あらかじめ各バッファに帯域が割当てられる場合には、各バッファに割当てられた帯域の大きさに基づく重みを各バッファに与え、この重みを加味した読出制御アルゴリズムにより、公平にパケットを読み出すことができる。
【００５６】
【発明の効果】
以上説明したように、本発明によれば、粒度ｑをパケットの読み出し状況に応じて可変制御することにより、平均パケット長が変化するトラヒック環境下でも公平性や高スループットを実現できる。
【図面の簡単な説明】
【図１】本発明実施例の読出制御部のブロック構成図。
【図２】本発明第一実施例の読出制御部の動作を示すフローチャート。
【図３】本発明第二実施例の読出制御部の動作を示すフローチャート。
【図４】本発明第三実施例の読出制御部の動作を示すフローチャート。
【図５】本発明第四実施例の読出制御部の動作を示すフローチャート。
【図６】本発明第五実施例の読出制御部の動作を示すフローチャート。
【図７】本発明第六実施例の読出制御部の動作を示すフローチャート。
【図８】本発明第七実施例の競合制御装置のブロック構成図。
【図９】本発明第七実施例の読出制御部の動作を示すフローチャート。
【図１０】バッファに帯域確保リクエストが到着した場合の重みの与え方を示すフローチャート。
【図１１】バッファに帯域解放リクエストが到着した場合の重みの与え方を示すフローチャート。
【図１２】競合制御装置の全体構成図。
【図１３】従来の読出制御部のブロック構成図。
【図１４】従来の読出制御部の動作を示すフローチャート。
【図１５】各バッファにパケットが蓄積されている例を示す図。
【図１６】粒度５００のときのパケット読出選択を説明するための図。
【図１７】粒度１０００のときのパケット読出選択を説明するための図。
【図１８】粒度１００のときのパケット読出選択を説明するための図。
【符号の説明】
１−１〜１−Ｎ バッファ
１０ 読出制御部
１１ パケット読出部
１２ 重み付与部
２０ 粒度ｑメモリ
２１ 読出選択処理部
２２ 粒度ｑ可変制御部
＃１〜＃Ｎ 入力回線[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention is applied to a large-scale and high-speed packet switch. The present invention relates to a technique for fairly giving an output opportunity to a packet addressed to one output line coming from a plurality of input lines without colliding with each other.
[0002]
[Prior art]
FIG. 12 shows a conventional conflict control device. Packets arriving from the
[0003]
The
[0004]
One of the methods for selecting a read packet is a round robin method (hereinafter referred to as RR: Round Robin). RR is a method in which a token circulates through each buffer in order, and sequentially selects a buffer that has issued an output request. When a certain buffer is selected as a read buffer, the request is searched starting from the next buffer in the circulating direction, and the next read buffer is selected.
[0005]
In RR, the number of selections is given fairly, but a buffer having a packet with a long packet length sends more traffic to an output line than a buffer having a packet with a short packet length. Therefore, if the average packet length differs for each buffer, it is not possible to provide fairness in the traffic volume (throughput).
[0006]
Therefore, in order to solve the problem of RR, a deficit round robin method (hereinafter referred to as DRR: Defined Round Robin) has been proposed. The conventional DRR will be described. FIG. 13 shows a block configuration of a read control unit of a conventional DRR. FIG. 14 is a flowchart showing the operation of a conventional DRR read control unit. FIG. 15 shows an example in which packets are stored in each buffer.
[0007]
The parameters used in the DRR include the granularity q, the default value d, and the packet length L at the head of the queue. The granularity q is a numerical value given in advance to the entire contention control device, and is set in the
[0008]
The flow of FIG. 14 will be described. The token goes around each buffer. From the previous buffer, focus on one buffer that has received the token. Check if there are any packets in the queue. If there is no packet in the queue, d = 0 and the token is passed to the next buffer. If there is a packet in the queue, d ← d + q. If L is equal to or less than d, the head packet of the buffer is selected as a read packet, and d ← d−L. If L is not less than d, the value of d remains. Pass the token to the next buffer.
[0009]
The case of FIG. 15 will be described using a specific example of FIG. The numbers in FIG. 16 indicate the value of d in each buffer. In FIG. 16, the particle size q is set to 500. Start from buffer 1-1. Since there is a packet in the queue of the buffer 1-1, d = 500 due to d ← d + q. L = 800. Since L ≦ d is not satisfied, the head packet of the buffer 1-1 is not selected as a read packet, and proceeds to the buffer 1-2. In the buffer 1-2, d = 500 and L = 600, so that no selection is made. In the buffer 1-3, d = 500, L = 400, and L ≦ d is satisfied, the leading packet is selected as a read packet, and d ← d−L = 500−400 = 100 (the square in the figure) Boxes indicate read buffers). To search for the next read buffer, the token starts from buffers 1-4. In the buffer 1-4, d = 500 and L = 1000, so that no selection is made. Next, the process proceeds to the buffer 1-1. In the buffer 1-1, the current value of d is d = 600. When a token is received, d ← d + q = 500 + 500 = 1000, and L = 800. Therefore, L ≦ d is satisfied, the leading packet is selected as a read packet, and d ← d−L = 1000−800 = 200. Search the next read buffer. Similarly, the buffer 1-2 also satisfies L ≦ d because d ← d + q = 500 + 500 = 1000 and L = 600, is selected as a read buffer, and d ← d−L = 1000−600 = 400. Search the next read buffer. In the buffer 1-3, since there is no packet in the queue, the value of d is reset to d = 0. A similar operation is repeated to search the read buffer.
[0010]
Thus, in order to select a read buffer, the value of d needs to be equal to or greater than the value of L. Long packets are less frequently selected as read packets than short packets, but can provide fairness in traffic volume (throughput) even when the average packet length varies from buffer to buffer. However, fairness and high throughput can be provided only when q is appropriately set.
[0011]
If q is set to a large value as shown in FIG. 17, fairness cannot be provided. When q is sufficiently large, when the token circulates in each buffer, if d is updated by d ← d + q, the value of L is likely to be larger than L, and the read packet is selected regardless of the packet length. Will be. As a result, it is equivalent to performing a simple RR, and fairness cannot be provided.
[0012]
On the other hand, consider a case where q is set small as shown in FIG. If q is sufficiently smaller than L, when the token circulates through each buffer, even if d is updated by d ← d + q, it is still smaller than the value of L. d needs to be updated many times. In the example of FIG. 18, the read selection is made after the buffer 1-3 is updated four times. As described above, the number of times the token circulates until one read buffer is selected increases, so that the calculation amount increases and the time required for the read selection increases. As a result, even when the output line is vacant, the time required for the read selection becomes longer, and the read cannot be performed, thereby lowering the throughput.
[0013]
[Problems to be solved by the invention]
As described above, unless an appropriate granularity q is set, the performance of the DRR deteriorates. In order to set an appropriate q, it is necessary to predict the distribution of the packet length in advance. However, it is difficult to predict the packet length for uncertain traffic input.
[0014]
Also, even if the distribution of the packet length in a certain period is predicted and an appropriate q is set, the distribution of the packet length changes every moment, so that the q set at a certain time is not necessarily appropriate after the lapse of time. Is not always the case.
[0015]
As described above, in the conventional contention control device, since the granularity q is fixedly set, fairness and high throughput cannot be provided unless this value is an appropriate value.
[0016]
The present invention has been made in such a background, and an object of the present invention is to provide a contention control device capable of providing fairness and high throughput performance even in a traffic environment where the average packet length changes.
[0017]
[Means for Solving the Problems]
The present invention is characterized in that the packet reading status of each buffer is observed, and the numerical value of the granularity is changed to an optimum value according to the observation result.
[0018]
That is, the present invention provides a plurality of buffers for temporarily storing packets arriving from a plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet reading unit for reading the packets to an output line. Control unit, a predetermined numerical value is given as a granularity, a default value of zero is given to each of the buffers, a default value is given to the buffer, the read control unit, for the buffer in which the token has circulated, said granularity Add to the deficit value of the buffer, compare the deficit value with the head packet length of the buffer, and when the deficit value is equal to or longer than the head packet length, select the head packet of the buffer as a read packet to which read permission is given. And subtract the head packet length from the deficit value A contention control apparatus which includes a stage.
[0019]
Here, the feature of the present invention resides in that there is provided a granularity control unit that variably sets the granularity based on a packet reading state of the plurality of buffers.
[0020]
It is preferable that the granularity control means include a means for performing an operation for increasing the granularity when a predetermined number of consecutive times that the deficit value is smaller than the leading packet length when the token circulates.
[0021]
That is, when the token circulates, if the deficit value is smaller than the head packet length, the head packet is not selected as a read packet. In the situation where the buffers in which the head packet is not selected as the read packet continue as described above, it is assumed that the preset granularity is not appropriate and the actual average packet length is longer than the granularity. Therefore, by performing an operation for increasing the granularity, an optimal granularity can be given.
[0022]
Also, in a traffic environment where the average packet length is expected to change gradually in advance, it is more appropriate to compare the deficit value and the head packet length for a longer period of time, and then change the granularity. . In such a case, the granularity control means includes means for performing an operation to increase the granularity when the token value circulates and when the number of consecutive rounds becomes smaller than the head packet length by a predetermined number of rounds. It can also be configured.
[0023]
The means for performing the increasing operation includes a means for adding a predetermined value to the current granularity value, or a means for multiplying the current granularity value by a predetermined value greater than one. Can be.
[0024]
The configuration in which a predetermined value is added to the current value of the granularity is suitable when a relatively gradual increase in the granularity is expected. Further, a configuration in which the current value of the granularity is multiplied by a predetermined value larger than 1 is suitable when a relatively sharp increase in the granularity is expected.
[0025]
On the other hand, the granularity control means is configured to include a means for performing an operation of reducing the granularity when a predetermined number of consecutive times that the deficit value is equal to or more than the head packet length when the token circulates. Is desirable.
[0026]
That is, when the token circulates, if the deficit value is larger than the head packet length, the head packet is selected as a read packet. In such a situation where the buffer in which the first packet is selected as the read packet is continuous, it is assumed that the preset granularity is not appropriate and the actual average packet length is shorter than the granularity. Therefore, by performing an operation for reducing the granularity, an optimal granularity can be given.
[0027]
Also, in a traffic environment where the average packet length is expected to change gradually in advance, it is more appropriate to compare the deficit value and the head packet length for a longer period of time, and then change the granularity. . In such a case, the granularity control means includes means for performing an operation of reducing the granularity when the number of rounds has become larger than the head packet length continuously for a predetermined number of rounds when the token circulates. It can also be configured.
[0028]
The means for performing the decreasing operation may be configured to include means for reducing the current granularity value by a predetermined value, or may be configured to include means for multiplying the current granularity value by a predetermined value smaller than 1. Can be.
[0029]
The configuration in which the predetermined value is reduced to the current value of the granularity is suitable when a relatively gradual decrease in the granularity is expected. Further, a configuration in which the current value of the granularity is multiplied by a predetermined value smaller than 1 is suitable when a relatively steep decrease in the granularity is expected.
[0030]
Further, in accordance with the read bandwidth securing request, the bandwidth is secured for the requesting buffer if the unreserved remaining bandwidth is larger than the required bandwidth, and the remaining bandwidth is secured for the other buffers. When a band is allocated to each buffer in advance by allocating, a means for giving a weight to be read out to each of the plurality of buffers is provided, and the means for giving a weight includes a constant coefficient for the band allocated to each buffer. includes means for the weight is multiplied by the read control unit, the buffer token has been visited, the particle size is added to the differential Ishitto value of the buffer, the value obtained by multiplying the weight of the buffer to the differential Ishitto value Is compared to the first packet length of the buffer and the multiplied value is equal to or greater than the first packet length, and the first packet of the buffer is Performs selection as a packet that gives a read permission is desirably configured to include a means for subtracting the first packet length from the Defishitto value.
[0031]
As described above, when a band is allocated to each buffer in advance, a packet can be read fairly by adding a weight corresponding to the allocated band to the reading algorithm.
[0032]
BEST MODE FOR CARRYING OUT THE INVENTION
The configuration of the contention control device according to the embodiment of the present invention will be described with reference to FIG. FIG. 1 is a block diagram of a read control unit according to an embodiment of the present invention. The overall configuration of the contention control device is common to FIG.
[0033]
The present invention provides a plurality of buffers 1-1 to 1-4 for temporarily storing packets arriving from a plurality of input lines, respectively, and a readout for selecting a packet to be read out from the plurality of buffers 1-1 to 1-4. A
[0034]
Here, the feature of the present invention resides in that a granularity q variable control unit 22 that variably sets the granularity q based on the packet reading state of the buffers 1-1 to 1-4 is provided.
[0035]
(First embodiment)
A first embodiment of the present invention will be described with reference to FIG. 12, FIG. 1, FIG. 2, and FIG. FIG. 2 is a diagram showing a variable control algorithm of the granularity q. Since the operations in FIGS. 12 and 14 are the same as the operations of the conventional competitive control device, the variable control algorithm of the granularity q will be described with reference to FIG.
[0036]
After selecting a certain buffer to be read, it is determined whether or not the next read buffer has been found by searching with a token. If L> d for n consecutive times, the grain size q is increased by setting q ← q (1 + △ inc). n and △ inc are values set in advance. If L> d does not hold for n consecutive times, q is not changed. After L is increased, if L> d continuously for n times, q ← q (1 + Δinc). By this operation, when q is smaller than an appropriate value, q can be increased.
[0037]
(Second embodiment)
The variable control algorithm of the granularity q will be described with reference to FIG. In the first embodiment, the criterion is to determine whether L> d for n consecutive times, but in the second embodiment, the criterion is for L> d to be continuous for R rounds. R is a value set in advance.
[0038]
(Third embodiment)
The variable control algorithm of the granularity q will be described with reference to FIG. In the first embodiment, the value of q is increased as q ← q (1+） inc). In the third embodiment, the value of q is increased as q ← q + △ inc.
[0039]
(Fourth embodiment)
The variable control algorithm of the granularity q will be described with reference to FIG. By the search using the token, the search is further performed from the buffer where L> d, and if the buffer issuing the request is L> d, it is selected as the read buffer. If the case where L ≦ d is continued m times in succession, the particle size q is reduced by setting q ← q (1- △ dec). m and △ dec are values set in advance. If L ≦ d does not hold for m consecutive times, q is not changed. After decreasing q, if L ≦ d for m successive times, then q ← q (1- △ dec). This operation allows q to be reduced if q is greater than an appropriate value.
[0040]
(Fifth embodiment)
The variable control algorithm of the granularity q will be described with reference to FIG. In the fourth embodiment, the criterion is to determine whether L ≦ d for m consecutive times. In the fifth embodiment, the criterion is to determine whether the token satisfies L ≦ d for S consecutive rounds. S is a value set in advance.
[0041]
(Sixth embodiment)
The variable control algorithm of the granularity q will be described with reference to FIG. In the fourth embodiment, the value of q is reduced as q ← q (1- △ dec). In the sixth embodiment, the value of q is reduced as q ← q− △ dec.
[0042]
(Seventh embodiment)
Until the first to sixth embodiments of the present invention, reading is performed evenly for each buffer. In the seventh embodiment of the present invention, each buffer is given a weight, and packets are read out according to the ratio of the weight. FIG. 8 is a block diagram of the contention control device according to the seventh embodiment of the present invention.
[0043]
In FIG. 8, the weight of the buffer 1-i (i is any one of 1 to 4) is given as weight [i] by the
[0044]
The method shown in the first to sixth embodiments of the present invention can be applied to the variable control of the particle size.
[0045]
Here, how to give weights and weight [t] will be described. The symbols used in the description and the values to be initialized are shown below.
residual_bandwidth: remaining bandwidth for which bandwidth is not secured C: output line speed unreserved_ports: number of ports for which bandwidth is not secured N: number of buffers bandwidthwidth [i]: allocated bandwidth of buffer i reserved_icon [i]: buffer i secures bandwidth "0" when the buffer i has been allocated, and "1" when the buffer i has not secured the band.
request_bandwidth: required bandwidth release_bandwidth: released bandwidth weight [i]: initialization of allocated bandwidth of buffer i residual_bandwidth = C
unreserved_ports = N
bandwidth [i] = C / N for all N
reserved_icon [i] = 1
FIG. 10 shows how to assign weights when a bandwidth reservation request arrives at the buffer s. This is a method in which bandwidth securing request information is included in the packet and the bandwidth securing request is executed. There is also a method in which a band securing request is executed via a control signal line.
[0046]
If (residual_bandwidth) − (request_bandwidth) is equal to or greater than 0 after the bandwidth reservation request arrives at the buffer s, the request is approved. Otherwise, reject the request. After approving the request,
residual_bandwidth = (residual_bandwidth)-(request_bandwidth)
bandwidth [s] = request_bandwidth
reserved_icon [s] = 0
Decrease the value of unreserved_ports by one.
[0047]
Next, for all buffers i, if reserved_icon [i] = 0,
bandwidth [i] = (residual_bandwidth) / (unreserved_ports)
weight [i] = bandwidth [i] × N / C
And
If reserved_icon [i] is not 0, the bandwidth [i] is left as it is.
[0048]
FIG. 11 shows how to assign weights when a bandwidth release request arrives at the buffer s. First,
residual_bandwidth = (residual_bandwidth) + (request_bandwidth)
bandwidth [s] = (bandwidth [s])-(request_bandwidth)
Execute If bandwidth [s] = 0, it means that no band is reserved in the buffer s, so reserved_icon [s] = 1, and the value of unreserved_ports is increased by one.
If bandwidth [s] is not equal to 0, the values of reserved_icon [s] and unreserved_ports remain unchanged.
[0049]
Next, for all buffers i, if reserved_icon [i] = 0,
bandwidth [i] = (residual_bandwidth) / unreserved_ports
weight [i] = bandwidth [i] × N / C
And If reserved_icon [i] is not 0, the bandwidth [i] is left as it is.
[0050]
(Example summary)
The above-mentioned n, Δinc, R, m, Δdec, and S are preset values. These values are obtained by observing the traffic environment in which the contention control device is installed in advance and examining the observation results. Is determined.
[0051]
As for the numerical values of n, R, m, and S, the smaller the numerical values, the quicker the change of the particle size q. As for the numerical values of Δinc and Δdec, the larger the numerical values, the larger the change width of the particle size q.
[0052]
For example, in a traffic environment where the average packet length of incoming packets gradually changes, the optimum granularity q can be given by gradually changing the granularity q with respect to the change in the average traffic length. Therefore, the values of n, R, m, and S are preferably relatively large. In addition, it is appropriate that the change width of the particle size q at this time is small. Therefore, it is better that the values of Δinc and Δdec are relatively small.
[0053]
On the other hand, in a traffic environment where the average packet length of the arriving packet changes frequently, the optimum granularity q can be given by changing the granularity q quickly with respect to the change in the average traffic length. . Therefore, the values of n, R, m, and S are preferably relatively small. Further, it is appropriate that the variation width of the particle size q at this time is large. Therefore, it is better that the values of Δinc and Δdec are relatively large.
[0054]
Based on such considerations, the values of n, Δinc, R, m, Δdec, and S are determined.
[0055]
Further, in accordance with the read bandwidth securing request, if the remaining bandwidth that is not secured is larger than the requested bandwidth for the requesting buffer, the bandwidth is secured, and the remaining bandwidth is allocated to the other buffers. Thus, when a bandwidth is allocated to each buffer in advance, a weight based on the size of the bandwidth allocated to each buffer is given to each buffer, and packets are read fairly by a read control algorithm that takes this weight into account. Can be.
[0056]
【The invention's effect】
As described above, according to the present invention, fairness and high throughput can be realized even under a traffic environment in which the average packet length changes, by variably controlling the granularity q in accordance with the packet reading situation.
[Brief description of the drawings]
FIG. 1 is a block diagram of a read control unit according to an embodiment of the present invention.
FIG. 2 is a flowchart showing the operation of a read control unit according to the first embodiment of the present invention.
FIG. 3 is a flowchart illustrating an operation of a read control unit according to a second embodiment of the present invention.
FIG. 4 is a flowchart showing the operation of a read control unit according to a third embodiment of the present invention.
FIG. 5 is a flowchart showing the operation of a read control unit according to a fourth embodiment of the present invention.
FIG. 6 is a flowchart showing the operation of a read control unit according to a fifth embodiment of the present invention.
FIG. 7 is a flowchart showing the operation of a read control unit according to a sixth embodiment of the present invention.
FIG. 8 is a block diagram of a contention control device according to a seventh embodiment of the present invention.
FIG. 9 is a flowchart showing the operation of a read control unit according to a seventh embodiment of the present invention.
FIG. 10 is a flowchart showing how to assign weights when a bandwidth securing request arrives at a buffer.
FIG. 11 is a flowchart showing how to assign weights when a bandwidth release request arrives at a buffer.
FIG. 12 is an overall configuration diagram of a contention control device.
FIG. 13 is a block diagram of a conventional read control unit.
FIG. 14 is a flowchart showing the operation of a conventional read control unit.
FIG. 15 is a diagram showing an example in which packets are stored in each buffer.
FIG. 16 is a view for explaining packet reading selection when the granularity is 500;
FIG. 17 is a diagram for explaining packet reading selection when the granularity is 1000;
FIG. 18 is a diagram for explaining packet reading selection when the granularity is 100.
[Explanation of symbols]
1-1 to 1-
Claims (16)
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
The read control unit adds the granularity to the buffer's deficit value for the buffer in which the token has circulated, compares the deficit value with the head packet length of the buffer, and determines that the deficit value is equal to or longer than the head packet length. Means for selecting the first packet of the buffer as a packet to which read permission is given and subtracting the first packet length from the default value,
A granularity control unit that variably sets the granularity based on a state of packet reading of the plurality of buffers ,
The granularity control means includes means for performing an operation of increasing the granularity when the token circulates, and when the deficit value is continuously smaller than the head packet length for a predetermined number of times. Conflict control device.
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定周回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
The read control unit adds the granularity to the buffer's deficit value for the buffer in which the token has circulated, compares the deficit value with the head packet length of the buffer, and determines that the deficit value is equal to or longer than the head packet length. Means for selecting the first packet of the buffer as a packet to which read permission is given and subtracting the first packet length from the default value,
A granularity control unit that variably sets the granularity based on a state of packet reading of the plurality of buffers,
The particle size control means, when the token is circulated, comprising means for performing an operation to increase the particle size when it is a predetermined circumferential times it is consecutively Defishitto value is smaller than the head packet length
A conflict control device characterized by the above-mentioned .
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以 上であることが連続して所定回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
The read control unit adds the granularity to the buffer's deficit value for the buffer in which the token has circulated, compares the deficit value with the head packet length of the buffer, and determines that the deficit value is equal to or longer than the head packet length. Means for selecting the first packet of the buffer as a packet to which read permission is given and subtracting the first packet length from the default value,
A granularity control unit that variably sets the granularity based on a state of packet reading of the plurality of buffers,
The particle size control means, when the token is circulated, comprising means for performing an operation to reduce the particle size when the Defishitto value becomes a predetermined number of consecutive be on a head packet Naga以
A conflict control device characterized by the above-mentioned .
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定周回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
The read control unit adds the granularity to the buffer's deficit value for the buffer in which the token has circulated, compares the deficit value with the head packet length of the buffer, and determines that the deficit value is equal to or longer than the head packet length. Means for selecting the first packet of the buffer as a packet to which read permission is given and subtracting the first packet length from the default value,
A granularity control unit that variably sets the granularity based on a state of packet reading of the plurality of buffers,
The granularity control means includes means for performing an operation of decreasing the granularity when the token has circulated and the predetermined value is continuously equal to or greater than the head packet length for a predetermined number of rounds.
A conflict control device characterized by the above-mentioned .
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
Means for allocating a bandwidth if the remaining bandwidth not reserved for the requesting buffer according to the read bandwidth securing request is larger than the requested bandwidth and allocating the remaining bandwidth to the other buffers; Means for assigning a read weight to each of the plurality of buffers,
The means for giving the weight includes means for multiplying the band allocated to each buffer by a constant coefficient to make the weight,
For the buffer in which the token has circulated, the read control unit adds the granularity to the deficit value of the buffer, and compares the value obtained by multiplying the deficit value by the weight of the buffer with the head packet length of the buffer. Means for selecting the first packet of the buffer as a packet to which read permission is given when the multiplied value is equal to or longer than the first packet length, and for subtracting the first packet length from the deficit value; Granularity control means variably set based on the state of packet reading of
The granularity control unit includes a unit for performing an operation for increasing the granularity when a predetermined number of consecutive times that the deficit value is smaller than the head packet length when the token circulates is performed.
A conflict control device characterized by the above-mentioned .
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域 が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定周回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
Means for allocating a bandwidth if the remaining bandwidth not reserved for the requesting buffer according to the read bandwidth securing request is larger than the requested bandwidth and allocating the remaining bandwidth to the other buffers; Means for assigning a read weight to each of the plurality of buffers,
The means for giving the weight includes means for multiplying the band allocated to each buffer by a constant coefficient to make the weight,
For the buffer in which the token has circulated, the read control unit adds the granularity to the deficit value of the buffer, and compares the value obtained by multiplying the deficit value by the weight of the buffer with the head packet length of the buffer. Means for selecting the first packet of the buffer as a packet to which read permission is given when the multiplied value is equal to or longer than the first packet length, and for subtracting the first packet length from the deficit value; Granularity control means variably set based on the state of packet reading of
The granularity control means includes means for performing an operation for increasing the granularity when a predetermined number of rounds of consecutive rounds where the deficit value is smaller than the head packet length when the token circulates are included. Conflict control device.
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
Means for allocating a bandwidth if the remaining bandwidth not reserved for the requesting buffer according to the read bandwidth securing request is larger than the requested bandwidth and allocating the remaining bandwidth to the other buffers; Means for assigning a read weight to each of the plurality of buffers,
The means for giving the weight includes means for multiplying the band allocated to each buffer by a constant coefficient to make the weight,
For the buffer in which the token has circulated, the read control unit adds the granularity to the deficit value of the buffer, and compares the value obtained by multiplying the deficit value by the weight of the buffer with the head packet length of the buffer. Means for selecting the first packet of the buffer as a packet to which read permission is given when the multiplied value is equal to or longer than the first packet length, and for subtracting the first packet length from the deficit value; Granularity control means variably set based on the state of packet reading of
The granularity control means includes means for performing an operation of decreasing the granularity when the token has been circulated and the predetermined number of times that the deficit value is equal to or longer than the leading packet length has been continuously reached.
A conflict control device characterized by the above-mentioned .
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みと する手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定周回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。 A plurality of buffers for temporarily storing packets arriving from the plurality of input lines, a read control unit for selecting a packet to be read from the plurality of buffers, and a packet read control unit for reading the packets to the output line,
A predetermined numerical value is given as a particle size,
Each of the buffers is given a default value of zero,
Means for allocating a bandwidth if the remaining bandwidth not reserved for the requesting buffer according to the read bandwidth securing request is larger than the requested bandwidth and allocating the remaining bandwidth to the other buffers; Means for assigning a read weight to each of the plurality of buffers,
The means for giving the weight includes means for multiplying the band allocated to each buffer by a constant coefficient to make the weight ,
For the buffer in which the token has circulated, the read control unit adds the granularity to the deficit value of the buffer, and compares the value obtained by multiplying the deficit value by the weight of the buffer with the head packet length of the buffer. Means for selecting the first packet of the buffer as a packet to which read permission is given when the multiplied value is equal to or longer than the first packet length, and for subtracting the first packet length from the deficit value; Granularity control means variably set based on the state of packet reading of
The granularity control means includes means for performing an operation of decreasing the granularity when the token has circulated and the predetermined value is continuously equal to or greater than the head packet length for a predetermined number of rounds.
A conflict control device characterized by the above-mentioned .
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000033499A JP3556557B2 (en) | 1999-12-22 | 2000-02-10 | Contention control device |
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11-365151 | 1999-12-22 | ||
| JP36515199 | 1999-12-22 | ||
| JP2000033499A JP3556557B2 (en) | 1999-12-22 | 2000-02-10 | Contention control device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001244963A JP2001244963A (en) | 2001-09-07 |
| JP3556557B2 true JP3556557B2 (en) | 2004-08-18 |
Family
ID=26581641
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000033499A Expired - Fee Related JP3556557B2 (en) | 1999-12-22 | 2000-02-10 | Contention control device |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3556557B2 (en) |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3431484B2 (en) * | 1998-03-02 | 2003-07-28 | 株式会社東芝 | Packet sending device and packet sending method |
| JP3683133B2 (en) * | 1999-08-17 | 2005-08-17 | 日本電気株式会社 | Packet scheduling device |
| JP2001217868A (en) * | 2000-02-04 | 2001-08-10 | Nippon Telegr & Teleph Corp <Ntt> | Packet schedule circuit |
| JP3566165B2 (en) * | 2000-02-09 | 2004-09-15 | 日本電信電話株式会社 | Competition control method and device |
-
2000
- 2000-02-10 JP JP2000033499A patent/JP3556557B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2001244963A (en) | 2001-09-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6092137A (en) | Fair data bus arbitration system which assigns adjustable priority values to competing sources | |
| KR100212104B1 (en) | Method for assigning transfer capacity to network | |
| US7159219B2 (en) | Method and apparatus for providing multiple data class differentiation with priorities using a single scheduling structure | |
| CA2142030C (en) | Method and apparatus for dynamically allocating shared resource access quota | |
| JP4750955B2 (en) | Limited priority queue scheduler | |
| RU2495533C2 (en) | Method and system for scheduling data selection for transmission over data network | |
| US20030105797A1 (en) | Dynamic load balancing among a set of servers | |
| CA2034518C (en) | Method and apparatus for controlling call processing based upon load conditions | |
| JP2001053807A (en) | Packet scheduling device | |
| US6463484B1 (en) | Egress port scheduling using memory efficient request storage | |
| JPH08251233A (en) | Packet communication system and method of improved memory layout | |
| JP4405806B2 (en) | Method and apparatus for allocating objects in a mixed population of multiple data storage devices | |
| GB2339371A (en) | Rate guarantees through buffer management | |
| WO1997045986A1 (en) | Data packet router | |
| EP0989770A1 (en) | Packet transfer control apparatus and scheduling method therefor | |
| JP5497541B2 (en) | Communication control device and shaping device | |
| CN106998340B (en) | Load balancing method and device for board resources | |
| RU2350027C2 (en) | Method of multilevel planning supporting plural ports and set of services | |
| CA2387208C (en) | Apparatus for scheduling packets and method of doing the same | |
| EP1528477A1 (en) | Memory management system for processing linked list data files | |
| JP2003533107A (en) | Method and apparatus for managing packet queues in a switch | |
| JP3556557B2 (en) | Contention control device | |
| JP3545931B2 (en) | Call control scheduling method | |
| JP3266139B2 (en) | Scheduling device | |
| US7120706B2 (en) | Contention resolution in a memory management system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20040212 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040217 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040415 |
|
| 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: 20040511 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040512 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090521 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090521 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100521 Year of fee payment: 6 |
|
| LAPS | Cancellation because of no payment of annual fees |