(57)【特許請求の範囲】
【請求項１】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項２】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定周回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項３】
前記増加する演算を行う手段は、現在の粒度の値に所定値を加算する手段を含む請求項１または２記載の競合制御装置。
【請求項４】
前記増加する演算を行う手段は、現在の粒度の値に１より大きい所定値を乗算する手段を含む請求項１または２記載の競合制御装置。
【請求項５】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項６】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、
前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定周回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項７】
前記減少する演算を行う手段は、現在の粒度の値に所定値を減算する手段を含む請求項５または６記載の競合制御装置。
【請求項８】
前記減少する演算を行う手段は、現在の粒度の値に１より小さい所定値を乗算する手段を含む請求項５または６記載の競合制御装置。
【請求項９】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項１０】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定周回数になったときには粒度を増加する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項１１】
前記増加する演算を行う手段は、現在の粒度の値に所定値を加算する手段を含む請求項９または１０記載の競合制御装置。
【請求項１２】
前記増加する演算を行う手段は、現在の粒度の値に１より大きい所定値を乗算する手段を含む請求項９または１０記載の競合制御装置。
【請求項１３】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項１４】
複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、
所定の数値が粒度として与えられ、
前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、
読出帯域確保要求にしたがって要求元のバッファに対しては確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てる手段と、前記複数のバッファのそれぞれに読み出す重みを与える手段とが設けられ、
この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、
前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含み、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備え、
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定周回数になったときには粒度を減少する演算を行なう手段を含む
ことを特徴とする競合制御装置。
【請求項１５】
前記減少する演算を行う手段は、現在の粒度の値に所定値を減算する手段を含む請求項１３または１４記載の競合制御装置。
【請求項１６】
前記減少する演算を行う手段は、現在の粒度の値に１より小さい所定値を乗算する手段を含む請求項１３または１４記載の競合制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は大規模で高速なパケット交換機に利用する。本発明は複数の入力回線から到来する一つの出力回線宛てのパケットに対して互いに衝突することなく、公平に出力機会を与える技術に関する。
【０００２】
【従来の技術】
従来の競合制御装置を図１２に示す。入力回線＃１〜＃Ｎから到来したパケットは、それぞれのバッファ１−１〜１−Ｎに入力される。図１２の例では、入力回線＃１〜＃Ｎ（図１２の例では、Ｎ＝４）に対応してバッファ１−１〜１−Ｎがあるが、これらは、例えば、各入力ポート毎にバッファが備えられている場合もあるし、各クラス毎にバッファが備えられている場合もある。パケットは、一般に可変長パケットである。
【０００３】
読出制御部１０は、Ｎ個のバッファ１−１〜１−Ｎから１個のバッファ１−ｉ（ｉは１〜Ｎのいずれか）を選択し、その先頭パケットは、パケット読出部１１により読み出される。以下では、読出許可が与えられたパケットを読出パケットという。また、読出許可が与えられたバッファを読出バッファという。
【０００４】
読出パケットを選択する方法の１つに、ラウンドロビン法（以下、ＲＲ：Ｒｏｕｎｄ  Ｒｏｂｉｎと記す）がある。ＲＲは、トークンが各バッファを順番に巡回し、出力のリクエストを出しているバッファを順次選択する方法である。あるバッファを読出バッファとして選択したら、巡回方向の次のバッファからスタートしてリクエストをサーチし、次の読出バッファを選択していく。
【０００５】
ＲＲでは、選択の回数が公平に与えられるが、パケット長が長いパケットを有するバッファは、パケット長が短いパケットを有するバッファに比べて、多くのトラヒックを出力回線に送出することになる。したがって、平均パケット長がバッファ毎に異なる場合には、トラヒック量（スループット）の公平性を提供することができない。
【０００６】
そこで、このＲＲの問題を解決するために、デフィシットラウンドロビン法（以下、ＤＲＲ：Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎと記す）が提案されている。従来のＤＲＲについて説明する。図１３は従来のＤＲＲの読出制御部のブロック構成を示している。図１４は従来のＤＲＲの読出制御部の動作を示すフローチャートである。図１５は各バッファにパケットが蓄積されている例を示している。
【０００７】
ＤＲＲで用いられるパラメータとして、粒度ｑ、デフィシット値ｄ、キューの先頭のパケット長Ｌがある。粒度ｑは競合制御装置全体に、あらかじめ一つ与えられる数値であり、図１３に示す粒度ｑメモリ２０に設定される。これに対し、デフィシット値は、各バッファ１−１〜１−４毎に設定される数値であり、初期値はゼロとする。
【０００８】
図１４のフローを説明する。トークンは、各バッファを巡回している。前のバッファから、トークンを受けたあるバッファに着目する。キューにパケットがあるかどうかをチェックする。キューにパケットがなければ、ｄ＝０として、次のバッファへトークンを渡す。キューにパケットがあれば、ｄ←ｄ＋ｑとする。Ｌがｄ以下であれば、当該バッファの先頭パケットが読出パケットとして選択され、ｄ←ｄ−Ｌとなる。Ｌがｄ以下でないならば、ｄの値はそのままである。次のバッファにトークンを渡す。
【０００９】
図１５の場合について、図１６の具体例を用いて説明する。図１６中の数字は、各バッファのｄの値を示している。図１６では、粒度ｑ＝５００と設定する。バッファ１−１からスタートする。バッファ１−１のキューにパケットがあるので、ｄ←ｄ＋ｑにより、ｄ＝５００となる。Ｌ＝８００である。Ｌ≦ｄでないので、バッファ１−１の先頭パケットは、読出パケットとして選択されずに、バッファ１−２に進む。バッファ１−２では、ｄ＝５００となり、Ｌ＝６００なので選択されない。バッファ１−３では、ｄ＝５００となり、Ｌ＝４００で、Ｌ≦ｄを満たし、先頭パケットが読出パケットとして選択され、ｄ←ｄ−Ｌ＝５００−４００＝１００となる（図中の四角の囲みは読出バッファを示す）。次の読出バッファをサーチするために、トークンは、バッファ１−４からスタートする。バッファ１−４では、ｄ＝５００となり、Ｌ＝１０００なので選択されない。次にバッファ１−１に進む。バッファ１−１では、現在のｄの値がｄ＝６００である。トークンを受けとると、ｄ←ｄ＋ｑ＝５００＋５００＝１０００となり、Ｌ＝８００であるから、Ｌ≦ｄを満たし、先頭パケットが読出パケットとして選択され、ｄ←ｄ−Ｌ＝１０００−８００＝２００となる。次の読出バッファをサーチする。バッファ１−２も同様に、ｄ←ｄ＋ｑ＝５００＋５００＝１０００となり、Ｌ＝６００であるから、Ｌ≦ｄを満たし、読出バッファとして選択され、ｄ←ｄ−Ｌ＝１０００−６００＝４００となる。次の読出バッファをサーチする。バッファ１−３では、キューにパケットがないのでｄの値はリセットされてｄ＝０となる。同様の動作が読出バッファをサーチするために繰り返される。
【００１０】
これにより、読出バッファを選択するためには、ｄの値をＬの値以上にする必要がある。長いパケットは、短いパケットより、読出パケットに選択される回数が減るが、平均パケット長がバッファ毎に異なる場合でも、トラヒック量（スループット）の公平性を提供することができる。ただし、公平性や高スループットを提供することができるのは、ｑを適切に設定したときに限る。
【００１１】
もし、図１７のように、ｑを大きく設定すると、公平性が提供できなくなる。ｑが十分に大きい場合には、トークンが各バッファに巡回してきたときに、ｄ←ｄ＋ｑで、ｄを更新すると、Ｌより大きくなる場合が多くなり、パケット長に関係なく、読出パケットが選択されることになる。結果的に単純なＲＲを実行することと等価になり、公平性が提供できなくなる。
【００１２】
一方、図１８のように、ｑを小さく設定する場合を考える。ｑがＬに比べて十分に小さい場合には、トークンが各バッファに巡回してきたときに、ｄ←ｄ＋ｑで、ｄを更新しても、Ｌの値よりまだ小さいので、数回の巡回により、ｄを何回も更新する必要がある。図１８の例では、バッファ１−３が４回の更新後に、読出選択がされる。このように、１つの読出バッファが選択されるまでトークンが巡回する回数が多くなるので、計算量が増加して、読出選択に必要な所要時間が大きくなる。これにより、出力回線が空いている状態でも、読出選択の所要時間が大きくなり、読み出せないことにより、スループットが低下する。
【００１３】
【発明が解決しようとする課題】
このように、適切な粒度ｑを設定しない限り、ＤＲＲの性能は悪化する。適切なｑを設定するためには、あらかじめパケット長の分布を予測する必要がある。しかし、不確定なトラヒック入力に対しては、このパケット長の予測は困難である。
【００１４】
また、ある期間のパケット長の分布を予測して、適切なｑを設定したとしても、パケット長の分布は、時々刻々と変化するので、ある時刻で設定したｑは、時間が経過すると必ずしも適切であるとは限らない。
【００１５】
このように、従来の競合制御装置では、粒度ｑが固定的に設定されるので、この値が適切な値でないと、公平性や高スループットの性能が提供できない。
【００１６】
本発明は、このような背景に行われたものであって、平均パケット長が変化するトラヒック環境下でも公平性や高スループットの性能が提供できる競合制御装置を提供することを目的とする。
【００１７】
【課題を解決するための手段】
本発明は、各バッファのパケット読み出し状況を観察し、その観察結果にしたがって粒度の数値を最適な値に可変することを特徴とする。
【００１８】
すなわち、本発明は、複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファと、この複数のバッファから読み出すべきパケットを選択する読出制御部と、パケットを出力回線へ読み出すパケット読出制御部とを備え、所定の数値が粒度として与えられ、前記バッファにはそれぞれ初期値がゼロであるデフィシット値が与えられ、前記読出制御部では、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値と当該バッファの先頭パケット長とを比較して当該デフィシット値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与える読出パケットとして選択を行なうとともに当該デフィシット値から当該先頭パケット長を減算する手段を含む競合制御装置である。
【００１９】
ここで、本発明の特徴とするところは、前記粒度を前記複数のバッファのパケット読み出しの状態に基づいて可変に設定する粒度制御手段を備えるところにある。
【００２０】
前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定回数になったときには粒度を増加する演算を行なう手段を含む構成とすることが望ましい。
【００２１】
すなわち、トークンが巡回したときに、デフィシット値が先頭パケット長より小さければ、その先頭パケットは読出パケットとして選択されない。このようにして先頭パケットが読出パケットとして選択されないバッファが連続するという状況は、あらかじめ設定されている粒度が適当ではなく、その粒度に対し、実際の平均パケット長が長いことが推察される。したがって、粒度を増加する演算を行うことによって、最適な粒度を与えることができる。
【００２２】
また、あらかじめ平均パケット長が緩やかに変化することが予想されるようなトラヒック環境下では、さらに長期間にわたりデフィシット値と先頭パケット長とを比較し、その上で粒度を変更した方が適当である。このような場合には、前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より小さいことが連続して所定周回数になったときには粒度を増加する演算を行なう手段を含む構成とすることもできる。
【００２３】
前記増加する演算を行う手段は、現在の粒度の値に所定値を加算する手段を含む構成としたり、あるいは、現在の粒度の値に１より大きい所定値を乗算する手段を含む構成とすることができる。
【００２４】
現在の粒度の値に所定値を加算する構成は、比較的緩やかな粒度の増加を期待する場合に適する。また、現在の粒度の値に１より大きい所定値を乗算する構成は、比較的急峻な粒度の増加を期待する場合に適する。
【００２５】
一方で、前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長以上であることが連続して所定回数になったときには粒度を減少する演算を行なう手段を含む構成とすることが望ましい。
【００２６】
すなわち、トークンが巡回したときに、デフィシット値が先頭パケット長より大きければ、その先頭パケットは読出パケットとして選択される。このようにして先頭パケットが読出パケットとして選択されるバッファが連続するという状況は、あらかじめ設定されている粒度が適当ではなく、その粒度に対し、実際の平均パケット長が短いことが推察される。したがって、粒度を減少する演算を行うことによって、最適な粒度を与えることができる。
【００２７】
また、あらかじめ平均パケット長が緩やかに変化することが予想されるようなトラヒック環境下では、さらに長期間にわたりデフィシット値と先頭パケット長とを比較し、その上で粒度を変更した方が適当である。このような場合には、前記粒度制御手段は、トークンが巡回したときに、デフィシット値が先頭パケット長より大きいことが連続して所定周回数になったときには粒度を減少する演算を行なう手段を含む構成とすることもできる。
【００２８】
前記減少する演算を行う手段は、現在の粒度の値に所定値を減少する手段を含む構成としたり、あるいは、現在の粒度の値に１より小さい所定値を乗算する手段を含む構成とすることができる。
【００２９】
現在の粒度の値に所定値を減少する構成は、比較的緩やかな粒度の減少を期待する場合に適する。また、現在の粒度の値に１より小さい所定値を乗算する構成は、比較的急峻な粒度の減少を期待する場合に適する。
【００３０】
また、読出帯域確保要求にしたがって、要求元のバッファに対しては、確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては、残余帯域を割当てることにより、あらかじめ各バッファに帯域が割当てられる場合には、前記複数のバッファのそれぞれに読み出す重みを与える手段が設けられ、この重みを与える手段は、各バッファに割当てられた帯域に一定の係数を乗じて重みとする手段を含み、前記読出制御部は、トークンが巡回してきたバッファについて、前記粒度を当該バッファのデフィシット値に加算し、当該デフィシット値に当該バッファの重みを乗算した値と当該バッファの先頭パケット長とを比較して当該乗算した値が先頭パケット長以上のときに当該バッファの先頭パケットを読出許可を与えるパケットとして選択を行うとともに当該デフィシット値から当該先頭パケット長を減算する手段を含む構成とすることが望ましい。
【００３１】
このように、あらかじめ各バッファに帯域が割当てられる場合には、読出アルゴリズムに割当帯域に応じた重みを加味することにより、公平にパケットを読み出すことができる。
【００３２】
【発明の実施の形態】
本発明実施例の競合制御装置の構成を図１を参照して説明する。図１は本発明実施例の読出制御部のブロック構成図である。競合制御装置の全体構成は図１２と共通である。
【００３３】
本発明は、複数の入力回線から到着するパケットをそれぞれ一時的に蓄積する複数のバッファ１−１〜１−４と、この複数のバッファ１−１〜１−４から読み出すべきパケットを選択する読出制御部１０と、パケットを出力回線へ読み出すパケット読出部１１とを備え、所定の数値が粒度ｑとして与えられ、バッファ１−１〜１−４にはそれぞれ初期値がゼロであるデフィシット値ｄが与えられ、読出制御部１０では、トークンが巡回してきたバッファ１−ｉについて、前記粒度ｑを当該バッファ１−ｉのデフィシット値ｄに加算し、当該デフィシット値ｄと当該バッファ１−ｉの先頭パケット長Ｌとを比較して当該デフィシット値ｄが先頭パケット長Ｌ以上のときに当該バッファ１−ｉの先頭パケットを読出許可を与える読出パケットとして選択を行なうとともに当該デフィシット値ｄから当該先頭パケット長Ｌを減算する競合制御装置である。
【００３４】
ここで、本発明の特徴とするところは、前記粒度ｑをバッファ１−１〜１−４のパケット読み出しの状態に基づいて可変に設定する粒度ｑ可変制御部２２を備えたところにある。
【００３５】
（第一実施例）
本発明第一実施例を図１２、図１および図２、図１４を参照して説明する。図２は粒度ｑの可変制御アルゴリズムを示す図である。図１２および図１４の動作は、従来の競合制御装置の動作と同様なので、図２を用いて粒度ｑの可変制御アルゴリズムを説明する。
【００３６】
あるバッファを読出選択後、トークンによるサーチにより、次の読出バッファを見つけたかを判定する。もし、ｎ回連続で、Ｌ＞ｄとなるならば、ｑ←ｑ（１＋△ｉｎｃ）として、粒度ｑを増加させる。ｎや△ｉｎｃは、あらかじめ設定しておいた値である。もし、ｎ回連続で、Ｌ＞ｄとならないならば、ｑは変化させない。ｑを増加させた後、さらに、ｎ回連続でＬ＞ｄとなるならば、ｑ←ｑ（１＋Δｉｎｃ）とする。この動作により、ｑが適切な値より小さい場合に、ｑを増加させることができる。
【００３７】
（第二実施例）
図３を用いて、粒度ｑの可変制御アルゴリズムを説明する。第一実施例では、ｎ回連続で、Ｌ＞ｄとなるかという判定基準であるが、第二実施例では、トークンがＲ周回連続で、Ｌ＞ｄとなるかという判定基準である。Ｒは、あらかじめ設定しておいた値である。
【００３８】
（第三実施例）
図４を用いて、粒度ｑの可変制御アルゴリズムを説明する。第一実施例では、ｑ←ｑ（１＋△ｉｎｃ）としてｑの値を増加させていた。第三実施例では、ｑ←ｑ＋△ｉｎｃとして、ｑの値を増加させる。
【００３９】
（第四実施例）
図５を用いて、粒度ｑの可変制御アルゴリズムを説明する。トークンによるサーチにより、Ｌ＞ｄとなったバッファからさらにサーチを進め、リクエストを出しているバッファが、Ｌ＞ｄであれば、読出バッファとして選択される。Ｌ≦ｄとなる場合がｍ回連続で続いたときには、ｑ←ｑ（１−△ｄｅｃ）として、粒度ｑを減少させる。ｍや△ｄｅｃは、あらかじめ設定しておいた値である。もし、ｍ回連続で、Ｌ≦ｄとならないならば、ｑは変化させない。ｑを減少させた後、さらに、ｍ回連続でＬ≦ｄとなるならば、ｑ←ｑ（１−△ｄｅｃ）とする。この動作により、ｑが適切な値より大きい場合に、ｑを減少させることができる。
【００４０】
（第五実施例）
図６を用いて、粒度ｑの可変制御アルゴリズムを説明する。第四実施例では、ｍ回連続で、Ｌ≦ｄとなるかという判定基準であるが、第五実施例では、トークンがＳ周回連続で、Ｌ≦ｄとなるかという判定基準である。Ｓは、あらかじめ設定しておいた値である。
【００４１】
（第六実施例）
図７を用いて、粒度ｑの可変制御アルゴリズムを説明する。第四実施例では、ｑ←ｑ（１−△ｄｅｃ）として、ｑの値を減少させていた。第六実施例では、ｑ←ｑ−△ｄｅｃとして、ｑの値を減少させる。
【００４２】
（第七実施例）
本発明第一ないし第六実施例までは、各バッファに対し、均等に読み出しが行えるようにしていた。本発明第七実施例では、各バッファに重みが与えられ、その重みの割合に応じてパケットを読み出す。図８は、本発明第七実施例の競合制御装置のブロック構成図である。
【００４３】
図８では、重み付与部１２により、バッファ１−ｉ（ｉは１〜４のいずれか）の重みをｗｅｉｇｈｔ［ｉ］として与えている。図９に本発明第七実施例の読み出しアルゴリズムを示す。本発明第一実施例の図１４のアルゴリズムとの相違は、先頭パケットのパケット長Ｌと、デフィシット値ｄとｗｅｉｇｈｔ［ｉ］の積とを比較しているところが異なる。重みが大きいほど、その判断式がｙｅｓとなる可能性が高いので、多くの読み出し機会が与えられる。重みが小さいほど、その判断式がｎｏとなる可能性が高いので、読み出し機会が少なくなる。したがって、読み出しの割合は、ｗｅｉｇｈｔ［ｉ］の重みに比例するようになる。
【００４４】
粒度の可変制御は、本発明第一ないし第六実施例に示した方式を適用することができる。
【００４５】
ここで、重み、ｗｅｉｇｈｔ［ｔ］の与え方を説明する。以下に、説明に使用する記号と初期化する値を示す。
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ：帯域確保していない残余帯域
Ｃ：出力回線速度
ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ：帯域確保していないポート数
Ｎ：バッファの数
ｂａｎｄｗｉｄｔｈ［ｉ］：バッファｉの割当帯域
ｒｅｓｅｖｅｄ＿ｉｃｏｎ［ｉ］：バッファｉが帯域を確保している場合は“０”、バッファｉが帯域を確保していない場合は“１”
ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ：要求帯域
ｒｅｌｅａｓｅ＿ｂａｎｄｗｉｄｔｈ：解放帯域
ｗｅｉｇｈｔ［ｉ］：バッファｉの割当帯域
初期化
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ＝Ｃ
ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ＝Ｎ
ｂａｎｄｗｉｄｔｈ［ｉ］＝Ｃ／Ｎ  ｆｏｒ  ａｌｌ  Ｎ
ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝１
図１０は、バッファｓに帯域確保リクエストが到着した場合の重みの与え方を示している。パケット内に帯域確保リクエスト情報を含んでいて、帯域確保リクエストが実行されるやり方である。また、制御信号線を介して、帯域確保リクエストが実行されるやり方もある。
【００４６】
バッファｓに帯域確保リクエストが到着した後に、（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）−（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）が０以上であれば、リクエストを承認する。そうでなければ、リクエストを拒絶する。リクエストを承認した後に、
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）−（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）
ｂａｎｄｗｉｄｔｈ［ｓ］＝ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ
ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｓ］＝０
ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓの値を一つ減らす。
【００４７】
次にすべてのバッファｉに対して、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０であれば、
ｂａｎｄｗｉｄｔｈ［ｉ］＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）／（ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ）
ｗｅｉｇｈｔ［ｉ］＝ｂａｎｄｗｉｄｔｈ［ｉ］×Ｎ／Ｃ
とする。
ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０でないならば、ｂａｎｄｗｉｄｔｈ［ｉ］はそのままとする。
【００４８】
図１１は、バッファｓに帯域解放リクエストが到着した場合の重みの与え方を示している。まず、
ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）＋（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）
ｂａｎｄｗｉｄｔｈ［ｓ］＝（ｂａｎｄｗｉｄｔｈ［ｓ］）−（ｒｅｑｕｅｓｔ＿ｂａｎｄｗｉｄｔｈ）
を実行する。ｂａｎｄｗｉｄｔｈ［ｓ］＝０ならば、バッファｓにおいて、帯域が確保されていないことになるので、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｓ］＝１とし、ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓの値を１つ増やす。
ｂａｎｄｗｉｄｔｈ［ｓ］＝０でないならば、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｓ］とｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓの値はそのままである。
【００４９】
次にすべてのバッファｉに対して、ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０であれば、
ｂａｎｄｗｉｄｔｈ［ｉ］＝（ｒｅｓｉｄｕａｌ＿ｂａｎｄｗｉｄｔｈ）／ｕｎｒｅｓｅｒｖｅｄ＿ｐｏｒｔｓ
ｗｅｉｇｈｔ［ｉ］＝ｂａｎｄｗｉｄｔｈ［ｉ］×Ｎ／Ｃ
とする。ｒｅｓｅｒｖｅｄ＿ｉｃｏｎ［ｉ］＝０でないならば、ｂａｎｄｗｉｄｔｈ［ｉ］はそのままとする。
【００５０】
（実施例まとめ）
上記のｎ、Δｉｎｃ、Ｒ、ｍ、Δｄｅｃ、Ｓは、あらかじめ設定しておいた値であるが、これらの値は、競合制御装置が設置されるトラヒック環境をあらかじめ観察し、その観察結果を検討することにより決定される。
【００５１】
ｎ、Ｒ、ｍ、Ｓの数値については、数値が小さくなればなるほど、粒度ｑの変化は俊敏になる。また、Δｉｎｃ、Δｄｅｃの数値については、数値が大きくなればなるほど粒度ｑの変化巾は大きくなる。
【００５２】
例えば、到来するパケットの平均パケット長が緩やかに変化するトラヒック環境下であれば、平均トラヒック長の変化に対して緩やかに粒度ｑを可変することにより、最適な粒度ｑを与えることができる。したがって、ｎ、Ｒ、ｍ、Ｓの値は比較的大きい方がよい。また、このときの粒度ｑの変化巾は小さい方が適当である。したがって、Δｉｎｃ、Δｄｅｃの値は比較的小さい方がよい。
【００５３】
その反対に、到来するパケットの平均パケット長が頻繁に変化するトラヒック環境下であれば、平均トラヒック長の変化に対して俊敏に粒度ｑを可変することにより、最適な粒度ｑを与えることができる。したがって、ｎ、Ｒ、ｍ、Ｓの値は比較的小さい方がよい。また、このときの粒度ｑの変化巾は大きい方が適当である。したがって、Δｉｎｃ、Δｄｅｃの値は比較的大きい方がよい。
【００５４】
このような検討に基づき、上記のｎ、Δｉｎｃ、Ｒ、ｍ、Δｄｅｃ、Ｓの値は決定される。
【００５５】
また、読出帯域確保要求にしたがって、要求元のバッファに対しては、確保されていない残余帯域が当該要求帯域よりも大きい場合には帯域を確保し、他のバッファに対しては残余帯域を割当てることにより、あらかじめ各バッファに帯域が割当てられる場合には、各バッファに割当てられた帯域の大きさに基づく重みを各バッファに与え、この重みを加味した読出制御アルゴリズムにより、公平にパケットを読み出すことができる。
【００５６】
【発明の効果】
以上説明したように、本発明によれば、粒度ｑをパケットの読み出し状況に応じて可変制御することにより、平均パケット長が変化するトラヒック環境下でも公平性や高スループットを実現できる。
【図面の簡単な説明】
【図１】本発明実施例の読出制御部のブロック構成図。
【図２】本発明第一実施例の読出制御部の動作を示すフローチャート。
【図３】本発明第二実施例の読出制御部の動作を示すフローチャート。
【図４】本発明第三実施例の読出制御部の動作を示すフローチャート。
【図５】本発明第四実施例の読出制御部の動作を示すフローチャート。
【図６】本発明第五実施例の読出制御部の動作を示すフローチャート。
【図７】本発明第六実施例の読出制御部の動作を示すフローチャート。
【図８】本発明第七実施例の競合制御装置のブロック構成図。
【図９】本発明第七実施例の読出制御部の動作を示すフローチャート。
【図１０】バッファに帯域確保リクエストが到着した場合の重みの与え方を示すフローチャート。
【図１１】バッファに帯域解放リクエストが到着した場合の重みの与え方を示すフローチャート。
【図１２】競合制御装置の全体構成図。
【図１３】従来の読出制御部のブロック構成図。
【図１４】従来の読出制御部の動作を示すフローチャート。
【図１５】各バッファにパケットが蓄積されている例を示す図。
【図１６】粒度５００のときのパケット読出選択を説明するための図。
【図１７】粒度１０００のときのパケット読出選択を説明するための図。
【図１８】粒度１００のときのパケット読出選択を説明するための図。
【符号の説明】
１−１〜１−Ｎ  バッファ
１０  読出制御部
１１  パケット読出部
１２  重み付与部
２０  粒度ｑメモリ
２１  読出選択処理部
２２  粒度ｑ可変制御部
＃１〜＃Ｎ  入力回線
【図１】
0003556557.tif 000002
【図２】
0003556557.tif 000003
【図３】
0003556557.tif 000004
【図４】
0003556557.tif 000005
【図５】
0003556557.tif 000006
【図６】
0003556557.tif 000007
【図７】
0003556557.tif 000008
【図８】
0003556557.tif 000009
【図９】
0003556557.tif 000010
【図１０】
0003556557.tif 000011
【図１１】
0003556557.tif 000012
【図１２】
0003556557.tif 000013
【図１３】
0003556557.tif 000014
【図１４】
0003556557.tif 000015
【図１５】
0003556557.tif 000016
【図１６】
0003556557.tif 000017
【図１７】
0003556557.tif 000018
【図１８】
0003556557.tif 000019