(57)【特許請求の範囲】
【請求項１】
割当可能な共通の帯域を、所定の帯域分配周期の期間毎に複数回線の各々に対してパケット単位で分配する分配手段を備える帯域分配装置において、
前記共通の帯域を帯域分配周期の１つの期間に所定の帯域比で複数回線に分配した場合に分配ができない端数の帯域を残余帯域として検出し、帯域分配周期の各期間で検出された残余帯域を所定の回線に対して再分配するとともに、各回線に再分配される残余帯域の配分比が、帯域分配周期の複数期間にわたって平均化した場合に所定値になるように各期間における再分配対象回線を決定する分配帯域調整手段
を設けたことを特徴とする帯域分配装置。
【請求項２】
割当可能な共通の帯域を、所定の帯域分配周期の期間毎に複数回線の各々に対してパケット単位で分配する分配手段を備える帯域分配装置において、
前記共通の帯域から帯域分配周期の各期間に各回線に分配された割当帯域の内でパケット単位に満たない端数帯域を残余帯域として回収し、回収された残余帯域を所定の回線に対して再分配するとともに、各回線に再分配される残余帯域の配分比が、帯域分配周期の複数期間にわたって平均化した場合に所定値になるように各期間における再分配対象回線を決定する分配帯域調整手段
を設けたことを特徴とする帯域分配装置。
【請求項３】
請求項１又は請求項２の帯域分配装置において、複数回線の各々のパラメータの設定値を保持する設定保持手段及び複数回線の各々の所要帯域を識別する所要帯域識別手段の少なくとも一方を備え、
前記分配手段は、前記設定保持手段の保持するパラメータの設定値及び前記所要帯域識別手段が識別した所要帯域の少なくとも一方に従って、所定の帯域分配周期で回線毎にパケット単位で帯域を分配する
ことを特徴とする帯域分配装置。
【請求項４】
請求項３の帯域分配装置において、前記分配帯域調整手段に、
回線毎に前記残余帯域を積算する残余帯域積算手段と、
回線毎に再分配した残余帯域に相当する値を前記残余帯域積算手段の残余帯域積算値から減算する減算手段と、
全回線の残余帯域の総和に全回線のパラメータの設定値の総和に対する各回線のパラメータの設定値の比を乗じた値を当該回線の残余帯域積算手段の残余帯域積算値に加算する加算手段と
を設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする帯域分配装置。
【請求項５】
請求項１又は請求項２の帯域分配装置において、前記分配帯域調整手段に、
回線毎に前記残余帯域を積算する残余帯域積算手段と、
回線毎に再分配した残余帯域に相当する値を前記残余帯域積算手段の残余帯域積算値から減算する減算手段と、
回線毎に発生した残余帯域に相当する値を前記残余帯域積算手段の残余帯域積算値に加算する加算手段と
を設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする帯域分配装置。
【請求項６】
請求項３の帯域分配装置において、前記分配帯域調整手段に、
回線毎に前記残余帯域を積算する残余帯域積算手段と、
回線毎に前記残余帯域積算手段の残余帯域積算値から再分配した残余帯域に相当する値に所定の定数である残余係数を乗じた値を減算する減算手段と、
全回線の残余帯域の総和に全回線のパラメータの設定値の総和に対する各回線のパラメータの設定値の比と前記残余係数とを乗じた値を当該回線の残余帯域積算手段の残余帯域積算値に加算する加算手段と
を設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする帯域分配装置。
【請求項７】
請求項１又は請求項２の帯域分配装置において、前記分配帯域調整手段に、
回線毎に前記残余帯域を積算する残余帯域積算手段と、
回線毎に前記残余帯域積算手段の残余帯域積算値から再分配した残余帯域に相当する値に残余係数を乗じた値を減算する減算手段と、
残余帯域がある回線の残余帯域に相当する値に残余係数を乗じた値を前記残余帯域積算手段の残余帯域積算値に加算する加算手段と
を設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする帯域分配装置。
【請求項８】
請求項３の帯域分配装置において、前記分配帯域調整手段は、複数の回線の各パラメータの設定値に応じた再分配の手順を表す情報を予めテーブルに記録し、前記テーブルの内容に従って残余帯域を順次に各回線に再分配することを特徴とする帯域分配装置。
【請求項９】
請求項４，請求項５，請求項６及び請求項７のいずれかの帯域分配装置において、前記分配帯域調整手段は、前記残余帯域積算手段の残余帯域積算値が大きい順番に残余帯域を再分配する代わりに、前記残余帯域積算手段の残余帯域積算値が所定の閾値を超過する回線に対して残余帯域の再分配を受ける権利を付与し、権利を有する回線に対して順次に残余帯域を再分配することを特徴とする帯域分配装置。
【請求項１０】
請求項４，請求項５，請求項６，請求項７及び請求項８のいずれかの帯域分配装置において、前記分配帯域調整手段は、分配未了の回線又は残余帯域が該当する帯域分配周期に発生した回線又は分配未了かつ残余帯域が該当する帯域分配周期に発生した回線に対してのみ残余帯域を再分配することを特徴とする帯域分配装置。
【請求項１１】
請求項４又は請求項６の帯域分配装置において、前記加算手段は、分配未了の回線又は残余帯域が該当する帯域分配周期に発生した回線又は分配未了かつ残余帯域が該当する帯域分配周期に発生した回線に対してのみ前記残余帯域積算手段の残余帯域積算値を加算することを特徴とする帯域分配装置。
【請求項１２】
請求項５又は請求項７の帯域分配装置において、前記加算手段は、分配未了の回線に対してのみ前記残余帯域積算手段の残余帯域積算値を加算することを特徴とする帯域分配装置。
【請求項１３】
請求項４又は請求項６の帯域分配装置において、前記加算手段は、全回線のパラメータの設定値の総和の代わりに、帯域分配周期の該当する期間に残余帯域が発生した全回線のパラメータの設定値の総和、又は分配未了の全回線のパラメータの総和、又は分配未了かつ該当する期間に残余帯域が発生した全回線のパラメータの設定値の総和を用いて加算を行うことを特徴とする帯域分配装置。
【請求項１４】
割当可能な共通の帯域を、所定の帯域分配周期の期間毎に複数回線の各々に対してパケット単位で分配する分配手段を備える帯域分配装置において、分配手段が複数の演算ステップを順次に実行して帯域を分配する場合に、
前記複数の演算ステップのうち最終ステップを除く演算ステップで、それまでに分配された帯域が該当する回線の所定の帯域又は所要帯域に満たない回線からそれに分配された帯域を回収し、回収された帯域を、分配された帯域が所定の帯域又は所要帯域に満たない回線に対して次の演算ステップで分配する再分配手段を設けた
ことを特徴とする帯域分配装置。
【請求項１５】
請求項１から請求項１３のいずれかに記載の帯域分配装置において、分配手段が複数の演算ステップを順次に実行して帯域を分配する場合に、分配手段は各演算ステップで生じた分配できない端数帯域を、残余帯域とみなして該当する帯域分配周期にて再分配することを特徴とする帯域分配装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えばＢ−ＰＯＮ（Broadband Passive Optical Network）におけるＤＢＡ（Dynamic Bandwidth Assignment：動的帯域割当）のように、複数のユーザで共用する帯域を動的に分配するために用いる帯域分配装置に関する。
【０００２】
【従来の技術】
所定の帯域比に従って帯域を公平に分配するための従来の技術としてＷＲＲ（Weighted Round Robin：重み付き巡回読み出し）が提案されている。このＷＲＲでは、帯域を分配する対象となる回線の数が大きな場合や、帯域比を表す重み付けであるＷｅｉｇｈｔの合計値が大きくなると、大量のパケット又は固定長のパケットであるセルに対する読み出しを実施し、その平均としてしか帯域比に応じた分配ができない。
【０００３】
このため、短い観測周期で所定の帯域比に応じた帯域分配（公平な帯域分配）を実施することは困難であった。そのため、短い観測周期でほぼ公平な分配を行うために、従来より次に示すような帯域分配装置が提案されている。
短い観測周期で公平な帯域分配が要求されることに対応した、従来の帯域分配装置については、例えば「ＩＴＵ−Ｔ勧告Ｇ．９８３．４」に示されている。このような帯域分配装置は、例えばＢ−ＰＯＮに適用される。
【０００４】
Ｂ−ＰＯＮのシステムにおいては、顧客宅内にＯＮＵ（Optical Network Terminal：光加入者網終端装置)が設置され、通信事業者局内にＯＬＴ（光加入者線端局装置：Optical Line Terminal）が設置され、これらの間は光ファイバ及び光分岐器で接続される。ＯＮＵは顧客宅内で顧客の端末から送出される上り情報を受信する。
【０００５】
ＤＢＡを行うＯＬＴは、帯域の有効利用を目的として、伝送すべき上り情報を有するＯＮＵに対して、ＯＮＵからの顧客毎の回線（ここでは、Ｔ−ＣＯＮＴ（Transmission Container））毎に定められた固定帯域（ＦＸＢ）、保証帯域（ＧＵＢ）、最大帯域（ＭＡＢ）の各設定値（それぞれＰ．ＦＸＢ，Ｐ．ＧＵＢ，Ｐ．ＭＡＢ）と所要帯域に基づいて上り帯域を分配する。
【０００６】
Ｂ−ＰＯＮの上り帯域は、帯域分配周期毎にパケット（ここではセル）数で表される。帯域の分配はＯＬＴにおいて次の手順で実施される。
まず、共用帯域の中から保証帯域の設定値（Ｐ．ＧＵＢ）以上の帯域を各Ｔ−ＣＯＮＴに分配する（１段分配）。
分配帯域の内でＴ−ＣＯＮＴの所要帯域又は最大帯域の設定値（Ｐ．ＭＡＢ）を超過する帯域については、固定帯域の設定値（Ｐ．ＦＸＢ）を除いて、余剰帯域として（Ｐ．ＧＵＢ）から（Ｐ．ＦＸＢ）を差し引いた値（Ｐ．ＡＳＢ）の比で他のＴ−ＣＯＮＴに再分配する（２段分配）。
【０００７】
２次以降の分配については、分配済みの帯域が所要帯域及びＰ．ＭＡＢのいずれにも到達しない分配未了Ｔ−ＣＯＮＴを対象とし、余剰帯域が無くなるか又は全Ｔ−ＣＯＮＴに対する所要帯域の分配が完了するまで繰り返す（ｎ段分配，１≦ｎ≦Ｎ，Ｎ：帯域分配が完了する最終の次数）。これを多段分配と呼ぶ。
ｉ番目のＴ−ＣＯＮＴ(＃ｉ)にｎ次で分配する場合の帯域ＤＢinは次式で表される。
【０００８】
DBin＝[(EB0−ΣFXB(i))×ASB(i)／ΣASB(i)＋FXB(i)]   (ｎ＝１の時)
DBin＝[(ΣΣEB(jk)-ΣΣDB(jk))×ASB(i)/ΣASB(i)＋FXB(i)] (2≦ｎ≦Nの時)・・・（１）
ＥＢ０：１段分配での全分配帯域
ＦＸＢ(i)：Ｔ−ＣＯＮＴ(＃ｉ)のＰ．ＦＸＢ
ＡＳＢ(i)：Ｔ−ＣＯＮＴ(＃ｉ)のＰ．ＡＳＢ
ｋ：ｎ段分配までの次数（１≦ｋ≦ｎ−１）
ｊ：ｋ段分配における分配対象Ｔ−ＣＯＮＴ番号
ＥＢ(ｊｋ)：ｋ段分配におけるＴ−ＣＯＮＴ(＃ｊ)の余剰帯域
ＤＢ(ｊｋ)：ｋ段分配におけるＴ−ＣＯＮＴ(＃ｊ)の分配帯域
［・］：・の整数部
また、（２≦ｎ≦Ｎの時）の分子の（）の中の第１項及び第２項の初めのΣはｋの１から（ｎ−１）までの総和を意味し、２番目のΣはｊの１からｋまでの総和を意味する。
【０００９】
【発明が解決しようとする課題】
帯域分配周期毎の各期間における余剰帯域の総和は、前記第(1)式の（）の中の第１項で表される。この値は、所要帯域のあるＴ−ＣＯＮＴのＰ．ＡＳＢ比では必ずしも割り切れず、１セルに満たない端数（残余帯域）が発生し得る。そして、これらの端数を分配しないと無効帯域が発生する。
【００１０】
更に、帯域分配周期毎の各期間の残余帯域に加えて、第(1)式による多段分配の各分配段での切捨てにより、１セル未満の端数がそれぞれ発生し、次数分の端数が累積する可能性がある。これらの端数を分配しないと無効帯域が発生する。例えば、あるＴ−ＣＯＮＴの所要セル数が２８セルであり、１段分配で２０．６セル、２段分配で４．５セルであった時、小数部を含めて分配すると、２５．１セルとなるが、各分配段でそれぞれ切捨てを行うと２４セル分配となる。従って、各回線に実際に割り当てられる帯域は割当可能な帯域と比べて１．１セルだけ少なくなる。
【００１１】
本発明は、演算の際に生じる端数の影響を抑制し、割当可能な共用帯域を有効かつ公平に分配することが可能な帯域分配装置を提供することを目的とする。
【００１２】
【課題を解決するための手段】
請求項１は、割当可能な共通の帯域を、所定の帯域分配周期の期間毎に複数回線の各々に対してパケット単位で分配する分配手段を備える帯域分配装置において、前記共通の帯域を帯域分配周期の１つの期間に所定の帯域比で複数回線に分配した場合に分配ができない端数の帯域を残余帯域として検出し、帯域分配周期の各期間で検出された残余帯域を所定の回線に対して再分配するとともに、各回線に再分配される残余帯域の配分比が、帯域分配周期の複数期間にわたって平均化した場合に所定値になるように各期間における再分配対象回線を決定する分配帯域調整手段を設けたことを特徴とする。
【００１３】
請求項１では、帯域分配周期の各期間に発生する残余帯域は、所定の回線に対して再分配されるので、残余帯域を減らし帯域を有効に利用できる。また、特定の回線のみに残余帯域を再配分すると、その回線だけ他の回線に比べて多くの帯域が割り当てられ、回線間で不公平が生じる。
しかし、請求項１では帯域分配周期の複数期間にわたって平均化するように各期間における再分配対象の回線を決定するので公平に残余帯域を分配することができる。
【００１４】
請求項２は、割当可能な共通の帯域を、所定の帯域分配周期の期間毎に複数回線の各々に対してパケット単位で分配する分配手段を備える帯域分配装置において、前記共通の帯域から帯域分配周期の各期間に各回線に分配された割当帯域の内でパケット単位に満たない端数帯域を残余帯域として回収し、回収された残余帯域を所定の回線に対して再分配するとともに、各回線に再分配される残余帯域の配分比が、帯域分配周期の複数期間にわたって平均化した場合に所定値になるように各期間における再分配対象回線を決定する分配帯域調整手段を設けたことを特徴とする。
【００１５】
請求項２では、パケット単位に満たない端数帯域が所定の回線に対して再分配されるので、残余帯域を減らし帯域を有効に利用できる。また、帯域分配周期の複数期間にわたって平均化するように各期間における再分配対象の回線を決定するので公平に残余帯域を分配することができる。
請求項３は、請求項１又は請求項２の帯域分配装置において、複数回線の各々のパラメータの設定値を保持する設定保持手段及び複数回線の各々の所要帯域を識別する所要帯域識別手段の少なくとも一方を備え、前記分配手段は、前記設定保持手段の保持するパラメータの設定値及び前記所要帯域識別手段が識別した所要帯域の少なくとも一方に従って、所定の帯域分配周期で回線毎にパケット単位で帯域を分配することを特徴とする。
【００１６】
請求項３においては、回線毎に定めたパラメータの設定値あるいは所要帯域に応じてパケット単位で帯域を分配することができる。
請求項４は、請求項３の帯域分配装置において、前記分配帯域調整手段に、回線毎に前記残余帯域を積算する残余帯域積算手段と、回線毎に再分配した残余帯域に相当する値を前記残余帯域積算手段の残余帯域積算値から減算する減算手段と、全回線の残余帯域の総和に全回線のパラメータの設定値の総和に対する各回線のパラメータの設定値の比を乗じた値を当該回線の残余帯域積算手段の残余帯域積算値に加算する加算手段とを設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする。
【００１７】
請求項４においては、残余帯域積算手段，減算手段及び加算手段を設けることにより、残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することができる。
請求項５は、請求項１又は請求項２の帯域分配装置において、前記分配帯域調整手段に、回線毎に前記残余帯域を積算する残余帯域積算手段と、回線毎に再分配した残余帯域に相当する値を前記残余帯域積算手段の残余帯域積算値から減算する減算手段と、回線毎に発生した残余帯域に相当する値を前記残余帯域積算手段の残余帯域積算値に加算する加算手段とを設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする。
【００１８】
請求項５においては、残余帯域積算手段，減算手段及び加算手段を設けることにより、残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することができる。
請求項６は、請求項３の帯域分配装置において、前記分配帯域調整手段に、回線毎に前記残余帯域を積算する残余帯域積算手段と、回線毎に前記残余帯域積算手段の残余帯域積算値から再分配した残余帯域に相当する値に所定の定数である残余係数を乗じた値を減算する減算手段と、全回線の残余帯域の総和に全回線のパラメータの設定値の総和に対する各回線のパラメータの設定値の比と前記残余係数とを乗じた値を当該回線の残余帯域積算手段の残余帯域積算値に加算する加算手段とを設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする。
【００１９】
請求項６では、残余帯域積算値が残余係数だけ大きくなるので、整数演算だけしかできない装置においても公平に残余帯域を再分配できる。
請求項７は、請求項１又は請求項２の帯域分配装置において、前記分配帯域調整手段に、回線毎に前記残余帯域を積算する残余帯域積算手段と、回線毎に前記残余帯域積算手段の残余帯域積算値から再分配した残余帯域に相当する値に残余係数を乗じた値を減算する減算手段と、残余帯域がある回線の残余帯域に相当する値に残余係数を乗じた値を前記残余帯域積算手段の残余帯域積算値に加算する加算手段とを設け、前記分配帯域調整手段は回線毎の前記残余帯域積算手段の残余帯域積算値が大きい順番に従って各回線に残余帯域を再分配することを特徴とする。
【００２０】
請求項７では、残余帯域積算値が残余係数だけ大きくなるので、整数演算だけしかできない装置においても公平に残余帯域を再分配できる。
請求項８は、請求項３の帯域分配装置において、前記分配帯域調整手段は、複数の回線の各パラメータに応じた再分配の手順を表す情報を予めテーブルに記録し、前記テーブルの内容に従って残余帯域を順次に各回線に再分配することを特徴とする。
【００２１】
請求項８では、テーブルを参照することにより、単純な繰り返し処理だけで残余帯域を公平に各回線に再分配することができる。
請求項９は、請求項４，請求項５，請求項６及び請求項７のいずれかの帯域分配装置において、前記分配帯域調整手段は、前記残余帯域積算手段の残余帯域積算値が大きい順番に残余帯域を再分配する代わりに、前記残余帯域積算手段の残余帯域積算値が所定の閾値を超過する回線に対して残余帯域の分配を受ける権利を付与し、権利を有する回線に対して順次に残余帯域を分配することを特徴とする。
【００２２】
請求項９では、残余帯域積算値を大きい順番に並べ替える必要がないので、比較的単純な処理だけで残余帯域を公平に各回線に再分配することができる。
請求項１０は、請求項４，請求項５，請求項６，請求項７及び請求項８のいずれかの帯域分配装置において、前記分配帯域調整手段は、分配未了の回線又は残余帯域が該当する帯域分配周期に発生した回線又は分配未了かつ残余帯域が該当する帯域分配周期に発生した回線に対してのみ残余帯域を再分配することを特徴とする。
【００２３】
請求項１０では、分配未了の回線や残余帯域が発生した回線に対して優先的に残余帯域を再分配することができる。
請求項１１は、請求項４又は請求項６の帯域分配装置において、前記加算手段は、分配未了の回線又は残余帯域が該当する帯域分配周期に発生した回線又は分配未了かつ残余帯域が該当する帯域分配周期に発生した回線に対してのみ前記残余帯域積算手段の残余帯域積算値を加算することを特徴とする。
【００２４】
請求項１１では、再分配不要な回線がある場合であっても、再分配した帯域の使用効率が劣化するのを防止できる。
請求項１２は、請求項５又は請求項７の帯域分配装置において、前記加算手段は、分配未了の回線に対してのみ前記残余帯域積算手段の残余帯域積算値を加算することを特徴とする。
【００２５】
請求項１２では、再分配不要な回線がある場合であっても、再分配した帯域の使用効率が劣化するのを防止できる。
請求項１３は、請求項４又は請求項６の帯域分配装置において、前記加算手段は、全回線のパラメータの設定値の総和の代わりに、帯域分配周期の該当する期間に残余帯域が発生した全回線のパラメータの設定値の総和、又は分配未了の全回線のパラメータの設定値の総和、又は分配未了かつ該当する期間に残余帯域が発生した全回線のパラメータの設定値の総和を用いて加算を行うことを特徴とする。
【００２６】
請求項１３では、再分配が必要な回線に対して優先的に帯域を割り当てることができる。
請求項１４は、割当可能な共通の帯域を、所定の帯域分配周期の期間毎に複数回線の各々に対してパケット単位で分配する分配手段を備える帯域分配装置において、分配手段が複数の演算ステップを順次に実行して帯域を分配する場合に、前記複数の演算ステップのうち最終ステップを除く演算ステップで、それまでに分配された帯域が該当する回線の所定の帯域又は所要帯域に満たない回線からそれに分配された帯域を回収し、回収された帯域を、分配された帯域が所定の帯域又は所要帯域に満たない回線に対して次の演算ステップで分配する再分配手段を設けたことを特徴とする。
【００２７】
請求項１４では、最終ステップ以外では切り捨てを回避し、各帯域分配周期内での分配帯域を所定の比率に近付け、帯域を有効かつ公平に分配することができる。
請求項１５は、請求項１から請求項１３のいずれかに記載の帯域分配装置において、分配手段が複数の演算ステップを順次に実行して帯域を分配する場合に、分配手段は各演算ステップで生じた分配できない端数帯域を、残余帯域とみなして該当する帯域分配周期にて再分配することを特徴とする。
【００２８】
請求項１５では、帯域分配周期内での分配帯域を所定の比率に近付け、端数をなくして帯域を有効かつ公平に分配することができる。
【００２９】
【発明の実施の形態】
（実施例１）
本発明の帯域分配装置の実施例について図１及び図６〜図１１を参照して説明する。この実施例は請求項１に対応する。
【００３０】
図１はこの実施例の帯域分配装置の構成を示すブロック図である。図６〜図１１はそれぞれこの実施例の残余分配のフローチャートである。
この実施例では、請求項１の分配手段及び分配帯域調整手段は、それぞれ分配手段２０及び分配帯域調整手段３０に対応する。
この実施例の帯域分配装置１０は、帯域分配対象の回線が複数存在する場合に、複数の回線間で共用される帯域を各回線に分配するために用いられる。
【００３１】
この帯域分配装置１０は、図１の例では分配手段２０及び分配帯域調整手段３０を備えている。
分配手段２０は、回線毎にパケット単位で帯域を分配する。ここで、回線とは、Ｔ−ＣＯＮＴ，コネクション，パス，バーチャルパス，バーチャルコネクション，方路等を含み、パケットはセル，セルスロット等も含む。
【００３２】
分配帯域調整手段３０は、分配手段２０が共用帯域を帯域分配周期毎に所定の帯域比で各回線に分配しようとする場合に発生する分配できない端数帯域を残余帯域として検出する。また、分配帯域調整手段３０は残余帯域を各帯域分配周期で所定の回線に対して再分配し、再分配した残余帯域が複数帯域分配周期での平均として所定値の比になるように調整する。
【００３３】
帯域はそれぞれ異なる回線で共用するものとする。分配可能なセル数が少ない場合、分配可能なセル数を公平に分配することができない。
例えば、１：１０の比で帯域を分配するポリシーの回線間で、帯域分配周期あたり１セルを共用することを想定する。この場合、その１セルを無駄にしないためには、１０の比を有する特定の回線に１セルを分配することになる。
【００３４】
この分配を全帯域分配期間について継続的に行うと、常に１０の比の回線だけにセルが分配される。従って、１１の帯域分配周期の平均として１：１０の比での分配であるべきなのに、分配セル数の比は０：１１となり不公平が発生する。
【００３５】
そこで、この実施例の分配帯域調整手段３０は、帯域分配周期毎の未分配セル数及び分配セル数を隣接する帯域分配周期間で引き継ぐように処理するとともに、複数の帯域分配周期に跨って観測したときに全体として全ての回線に対して公平になるように残余帯域の再分配を行う。
帯域分配装置１０に関する具体的な６種類の動作例が図６〜図１１に示されている。それぞれの動作例について以下に説明する。
【００３６】
まず、図６を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
最初のステップ（１）では、分配手段２０を用いて分配可能な帯域を各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００３７】
ステップ（３）では、残余積算値が１フレーム以上の回線が存在するか否かを識別する。
残余帯域は少ないので、それを所定の帯域比で全ての回線に分配しようとしても、１つの帯域分配周期では一部の回線だけにしか分配できない。従って、各々の帯域分配周期では各回線の間に定められた帯域比に比べて分配の不公平が生じる可能性がある。
【００３８】
この例では、公平に分配した場合と比べて各帯域分配周期で不足した帯域の累積値を残余積算値として管理している。
そして、ステップ（３）で残余積算値が１フレーム以上の回線が存在する場合にはステップ（５）に進み、残余積算値が１フレーム以上の回線に対して残余帯域を分配する。また、実際に分配した帯域の値を該当する回線に割り当てられた残余積算値から減算する。
【００３９】
また、ステップ（３）で残余積算値が１フレーム以上の回線が存在しない場合には、ステップ（４）に進む。そして、全ての回線の残余積算値に対して各回線の帯域比に応じた値を加算する。
そして、これらの処理を繰り返し、ステップ（２）で未分配の帯域がなくなるとこの処理を終了する。
【００４０】
このように、各々の帯域分配周期では公平に分配しきれない帯域について、図６の例では帯域分配周期を跨いで管理される残余積算値に従って分配するので、複数の帯域分配周期の全体の期間では、全ての回線に対して割り当てられる帯域の比は定められた帯域比に近づき公平になる。
次に、図７を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
【００４１】
最初のステップ（１）では、分配手段２０を用いて分配可能な帯域を各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００４２】
ステップ（３）では、残余積算値が最大の回線に対して残余帯域を分配する。また、分配した残余帯域に応じて該当する回線に割り当てられた残余積算値を減算する。
ステップ（４）では、ステップ（３）で分配した帯域に応じて各回線の帯域比に応じた値を全回線の残余積算値に加算する。ここで加算する値Ｘｉは、回線＃ｉの帯域比の係数をＰｉ.ＡＳＢと仮定した場合には次式から求められる。
【００４３】
Ｘｉ＝Ｐｉ.ＡＳＢ×ΣＰｉ.ＡＳＢ
又は
Ｘｉ＝Ｐｉ.ＡＳＢ×ΣＰｉ.ＡＳＢ×(ステップ(3)で分配した帯域)
このような値Ｘｉを加算するのは、これに相当する帯域がステップ（３）で所定の帯域比での分配のためには分配されるべきだが分配されなかったためである。すなわち、公平な分配のためにステップ（４）で各回線の残余積算値に値Ｘｉを加算する。
【００４４】
分配すべき帯域を加算して、分配した帯域を減算することで、複数の帯域分配周期の全体の期間での平均として所定の帯域比で分配することができる。
そして、これらの処理を繰り返し、ステップ（２）で未分配の帯域がなくなるとこの処理を終了する。
次に、図８を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
【００４５】
最初のステップ（１）では、分配手段２０を用いて分配可能な帯域を各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００４６】
ステップ（３）では、残余積算値が所定値以上の回線に対して残余帯域を分配する。また、分配した残余帯域に応じて該当する回線に割り当てられた残余積算値を減算する。
残余積算値が所定値以上の回線がある場合には、ステップ（４）からステップ（２）に戻り、無ければステップ（４）からステップ（５）に進む。
【００４７】
ステップ（５）では全回線の残余積算値に、所定の帯域に応じた値を加算する。
そして、これらの処理を繰り返し、ステップ（２）で未分配の帯域がなくなるとこの処理を終了する。
【００４８】
次に、図９を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
図９の動作例は、図６の変形例であり、図６における加算と減算とを逆にした場合に相当する。
図９において、ステップ（１）では分配手段２０を用いて分配可能な帯域を各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
【００４９】
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
ステップ（３）では、残余積算値が１フレーム以下の回線が存在するか否かを識別する。
【００５０】
そして、ステップ（３）で残余積算値が１フレーム以下の回線が存在する場合にはステップ（５）に進み、残余積算値が１フレーム以下の回線に対して残余帯域を分配する。また、実際に分配した帯域の値を該当する回線に割り当てられた残余積算値に加算する。
また、ステップ（３）で残余積算値が１フレーム以下の回線が存在しない場合には、ステップ（４）に進む。そして、全ての回線の残余積算値から各回線の帯域比に応じた値を減算する。
【００５１】
そして、これらの処理を繰り返し、ステップ（２）で未分配の帯域がなくなるとこの処理を終了する。
次に、図１０を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
図１０の動作例は、図７の変形例であり、図７における加算と減算とを逆にした場合に相当する。
【００５２】
図１０のステップ（１）では、分配手段２０を用いて分配可能な帯域を各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００５３】
ステップ（３）では、残余積算値が最小の回線に対して残余帯域を分配する。また、分配した残余帯域に応じて該当する回線に割り当てられた残余積算値を加算する。
ステップ（４）では、ステップ（３）で分配した帯域に応じて各回線の帯域比に応じた値を全回線の残余積算値から減算する。減算する値については前述のＸｉと同じでよい。
【００５４】
分配すべき帯域を減算して、分配した帯域を加算することで、複数の帯域分配周期の全体の期間での平均として所定の帯域比で分配することができる。
そして、これらの処理を繰り返し、ステップ（２）で未分配の帯域がなくなるとこの処理を終了する。
次に、図１１を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
【００５５】
図１１の動作例は、図８の変形例であり、図８における加算と減算とを逆にした場合に相当する。
最初のステップ（１）では、分配手段２０を用いて分配可能な帯域を各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００５６】
ステップ（３）では、残余積算値が所定値以下の回線に対して残余帯域を分配する。また、分配した残余帯域に応じて該当する回線に割り当てられた残余積算値を加算する。
残余積算値が所定値以下の回線がある場合には、ステップ（４）からステップ（２）に戻り、無ければステップ（４）からステップ（５）に進む。
【００５７】
ステップ（５）では全回線の残余積算値から、所定の帯域に応じた値を減算する。
そして、これらの処理を繰り返し、ステップ（２）で未分配の帯域がなくなるとこの処理を終了する。
以上のように、この実施例では、所定の帯域比で分配できない端数帯域を再分配した残余帯域が複数の帯域分配周期に渡る期間での平均として所定値の比になるように分配帯域調整手段３０が調整するので、公平かつ有効に帯域を分配することができる。
【００５８】
（実施例２）
本発明の帯域分配装置の実施例について図１２〜図１７を参照して説明する。この実施例は請求項２に対応する。
この実施例では、請求項１の分配手段及び分配帯域調整手段は、それぞれ分配手段２０及び分配帯域調整手段３０に対応する。
【００５９】
図１２〜図１７はそれぞれこの実施例の残余分配のフローチャートである。
この実施例は、前述の実施例１の変形例である。実施例１に対して変更された部分は、残余帯域の扱い方のみである。すなわち、実施例１では所定の帯域比で分配できない端数帯域を残余帯域として扱っているが、この実施例では、帯域分配周期で各回線に分配する帯域の内でパケット単位に満たない端数帯域を残余帯域として扱う。想定する帯域分配装置の構成は図１と同一である。
【００６０】
実施例１と同一の部分については以下の説明を省略する。
図１２〜図１７の動作例は、それぞれ図６〜図１１の動作例と対応する変形例である。すなわち、図１２〜図１７のステップ（１）のみが次のように変更されている。
図１２〜図１７のステップ（１）では、分配手段２０は帯域分配周期（ｊ）で分配が保証される帯域である（Ｅij.ＧＵＢ）を分配する。更に、回線間で帯域分配周期（ｊ）にて共用できる余剰帯域（ＳＰＢｊ）に回線＃ｉの帯域比の係数である（Ｐi.ＡＳＢ）を乗じて、全回線の帯域比の係数の総和である（ΣＰi.ＡＳＢ）で除した値の切り下げした帯域を分配する。
【００６１】
なお、図中では（Ｅij.ＧＵＢ）等の各記号に含まれる「.」はアンダーバーに置き換えて表記してあるが同一の値を表している。以下同様である。
すなわち、図１２〜図１７のステップ（１）で分配する帯域ＤＢijは次式で表される。
ＤＢij＝Ｅij.ＧＵＢ＋[ＳＰＢｊ×Ｐi.ＡＳＢ／ΣＰi.ＡＳＢ[i=1〜Imax]]
ＤＢij：帯域分配周期ｊにて回線ｉに分配する帯域
Ｅij.ＧＵＢ：帯域分配周期ｊにて回線ｉに分配が保証されている帯域
ＳＰＢｊ：帯域分配周期ｊにて回線間で共用可能な余剰帯域
Ｐi.ＡＳＢ：回線ｉに分配する際の所定の帯域比
ΣＰi.ＡＳＢ[i=1〜Imax]]：添え字ｉが1〜Imaxの間のＰi.ＡＳＢの総和
Ｉｍａｘ：回線の総数
［・］：・の整数部を表すガウスの関数
図１２〜図１７のステップ（２）以降はそれぞれ図６〜図１１と同一である。
【００６２】
この実施例では、分配手段２０によって公平に分配できない帯域は、帯域分配周期毎の回線あたり１フレーム以下になる。
このため、この実施例は、実施例１と比べて、複数帯域分配周期での平均として公平となるように分配する残余帯域の総数が減少するため、各帯域分配周期においてより公平な分配が可能になる。
【００６３】
（実施例３）
本発明の帯域分配装置の実施例について図２及び図１８〜図２３を参照して説明する。この実施例は請求項３に対応する。
この実施例では、請求項３の設定保持手段及び所要帯域識別手段は、それぞれ設定保持手段４０及び所要帯域識別手段４５に対応する。
【００６４】
図２はこの実施例の帯域分配装置の構成を示すブロック図である。図１８〜図２３は、それぞれこの実施例の残余分配のフローチャートである。
この実施例は前述の実施例１の変形例である。ここで想定する帯域分配装置１０には、図２に示すように設定保持手段４０及び所要帯域識別手段４５が追加されている。
【００６５】
設定保持手段４０は、回線毎のパラメータ（最大帯域や帯域比など）の設定値の情報を保持している。所要帯域識別手段４５は、回線毎の所要帯域の大きさを識別する。
分配手段２０及び分配帯域調整手段３０は、設定保持手段４０が出力する値及び所要帯域識別手段４５が出力する所要帯域に従って、所定の帯域分配周期毎に各回線に対してパケット単位で帯域を分配する。
【００６６】
実施例１と同一の部分については以下の説明を省略する。
図１８〜図２３の動作例は、それぞれ図６〜図１１の動作例と対応する変形例である。この実施例では、次の点が実施例１と異なっている。すなわち、回線毎の最大帯域を定め、最大帯域と所要帯域を上限として帯域を分配する。
まず、図１８を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
【００６７】
図１８のステップ（１）では、分配手段２０の制御により、回線毎に定められた最大帯域（設定保持手段４０の出力）及び所要帯域（所要帯域識別手段４５の出力）を上限として各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
【００６８】
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。未分配の帯域がある場合には、次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
ステップ（３）では、既分配帯域が定められた最大帯域を未超過でかつ分配未了回線で残余積算値が１フレーム以上の回線が存在するか否かを識別する。ここで、分配未了回線とは、回線の所要帯域の分配が未了である回線を意味する。
【００６９】
そして、ステップ（３）の条件を満たす回線が存在する場合にはステップ（５）に進み、該当する回線に対して残余帯域を分配する。また、実際に分配した帯域の値を該当する回線に割り当てられた残余積算値から減算する。
また、ステップ（３）の条件を満たさない場合にはステップ（４）に進む。ステップ（４）では、全ての回線の残余積算値に対して各回線の帯域比に応じた値を加算する。
【００７０】
なお、加算を最大帯域設定未超過かつ分配回線に限定した場合、当該帯域分配周期で加算されない回線は当該帯域分配周期よりも後の帯域分配周期での残余分配が少なくなるが、当該帯域分配周期で残余分配しない回線に残余積算値が積み上がらない効果がある。また、残余積算値の上限値は残余分配でバースト的に分配して良い帯域を上限とするのが妥当である。
【００７１】
ステップ（５）で分配後に既分配帯域が最大帯域設定未超過かつ分配未了回線が無い場合にはステップ（６）で処理を終了し、該当する回線がある場合にはステップ（２）に戻りこれらの処理を繰り返す。
次に、図１９を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
【００７２】
図１９のステップ（１）では、分配手段２０の制御により、回線毎に定められた最大帯域（設定保持手段４０の出力）及び所要帯域（所要帯域識別手段４５の出力）を上限として各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。未分配の帯域がある場合には、次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００７３】
ステップ（３）では、既分配帯域が定められた最大帯域を未超過でかつ分配未了回線の内で最大の残余積算値の回線に帯域を分配する。そして、帯域を分配した回線の残余積算値から、分配した帯域に応じた値を減算する。
ステップ（４）では、全回線の残余積算値に所定の帯域に応じた値を加算する。
ここで加算する値は実施例１のＸｉと同じでよい。
【００７４】
なお、加算を最大帯域設定未超過かつ分配回線に限定した場合、当該帯域分配周期で加算されない回線は当該帯域分配周期よりも後の帯域分配周期での残余分配が少なくなるが、当該帯域分配周期で残余分配しない回線に残余積算値が積み上がらない効果がある。また、残余積算値の上限値は残余分配でバースト的に分配して良い帯域を上限とするのが妥当である。
【００７５】
ステップ（５）では、既分配帯域が最大帯域設定未超過かつ分配未了回線の有無を判別する。この条件を満たす場合にはこの処理を終了し、条件を満たさない場合にはステップ（２）に戻って処理を繰り返す。
次に、図２０を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。
【００７６】
図２０のステップ（１）では、分配手段２０の制御により、回線毎に定められた最大帯域（設定保持手段４０の出力）及び所要帯域（所要帯域識別手段４５の出力）を上限として各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
【００７７】
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
ステップ（３）では、既分配帯域が最大帯域設定未超過かつ分配未了回線があるか否かを判別する。
【００７８】
ステップ（２），（３）の条件を満たす場合には、次のステップ（４）に進む。ステップ（４）では、既分配帯域が最大帯域設定未超過かつ分配未了回線の内で残余積算値が所定値以上の回線に対して帯域を分配する。また、分配した回線の残余積算値から分配した帯域に相当する値を減算する。
残余積算値が所定値以上の回線が無くなると、ステップ（５）からステップ（６）に進み、あればステップ（２）に戻る。
【００７９】
なお、加算を最大帯域設定未超過かつ分配回線に限定した場合、当該帯域分配周期で加算されない回線は当該帯域分配周期よりも後の帯域分配周期での残余分配が少なくなるが、当該帯域分配周期で残余分配しない回線に残余積算値が積み上がらない効果がある。また、残余積算値の上限値は残余分配でバースト的に分配して良い帯域を上限とするのが妥当である。
【００８０】
ステップ（６）では、全回線の残余積算値に、所定の帯域に応じた値を加算する。
そして、これらの処理を繰り返し、ステップ（２）又は（３）の条件を満たさなくなるとこの処理を終了する。
次に、図２１を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。この動作例は図１８の動作例の変形例であり、残余積算値に関する加算と減算とが逆に変更されている。
【００８１】
図２１のステップ（１）では、分配手段２０の制御により、回線毎に定められた最大帯域（設定保持手段４０の出力）及び所要帯域（所要帯域識別手段４５の出力）を上限として各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。未分配の帯域がある場合には、次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
【００８２】
ステップ（３）では、既分配帯域が定められた最大帯域を未超過でかつ分配未了回線で残余積算値が１フレーム以下の回線が存在するか否かを識別する。ここで、分配未了回線とは、回線の所要帯域の分配が未了である回線を意味する。
そして、ステップ（３）の条件を満たす回線が存在する場合にはステップ（５）に進み、該当する回線に対して残余帯域を分配する。また、実際に分配した帯域の値を該当する回線に割り当てられた残余積算値に加算する。
【００８３】
また、ステップ（３）の条件を満たさない場合にはステップ（４）に進む。ステップ（４）では、全ての回線の残余積算値から各回線の帯域比に応じた値を減算する。
ステップ（５）での分配後に既分配帯域が最大帯域設定未超過かつ分配未了回線が無い場合にはステップ（６）で処理を終了し、該当する回線がある場合にはステップ（２）に戻りこれらの処理を繰り返す。
【００８４】
次に、図２２を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。この動作例は図１９の動作例の変形例であり、残余積算値に関する加算と減算とが逆に変更されている。
図２２のステップ（１）では、分配手段２０の制御により、回線毎に定められた最大帯域（設定保持手段４０の出力）及び所要帯域（所要帯域識別手段４５の出力）を上限として各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
【００８５】
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。未分配の帯域がある場合には、次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
ステップ（３）では、既分配帯域が定められた最大帯域を未超過でかつ分配未了回線の内で最小の残余積算値の回線に帯域を分配する。そして、帯域を分配した回線の残余積算値に、分配した帯域に応じた値を加算する。
【００８６】
ステップ（４）では、全回線の残余積算値から所定の帯域に応じた値を減算する。ここで減算する値は実施例１のＸｉと同じでよい。
ステップ（５）では、既分配帯域が最大帯域設定未超過かつ分配未了回線の有無を判別する。この条件を満たす場合にはこの処理を終了し、条件を満たさない場合にはステップ（２）に戻って処理を繰り返す。
【００８７】
次に、図２３を参照して説明する。この処理は、所定の帯域分配周期毎に繰り返し実行される。この動作例は図２０の動作例の変形例であり、残余積算値に関する加算と減算とが逆に変更されている。
図２３のステップ（１）では、分配手段２０の制御により、回線毎に定められた最大帯域（設定保持手段４０の出力）及び所要帯域（所要帯域識別手段４５の出力）を上限として各回線に分配する。これ以降のステップは分配帯域調整手段３０によって処理される。
【００８８】
ステップ（２）では、分配手段２０による分配の結果として未分配の帯域、すなわち残余帯域が存在するか否かを識別する。残余帯域が存在する場合には次のステップ（３）に進み、存在しない場合には今回の処理を終了する。
ステップ（３）では、既分配帯域が最大帯域設定未超過かつ分配未了回線があるか否かを判別する。
【００８９】
ステップ（２），（３）の条件を満たす場合には、次のステップ（４）に進む。ステップ（４）では、既分配帯域が最大帯域設定未超過かつ分配未了回線の内で残余積算値が所定値以下の回線に対して帯域を分配する。また、分配した回線の残余積算値に分配した帯域に相当する値を加算する。
【００９０】
残余積算値が所定値以下の回線が無くなると、ステップ（５）からステップ（６）に進み、あればステップ（２）に戻る。
ステップ（６）では、全回線の残余積算値から、所定の帯域に応じた値を減算する。
そして、これらの処理を繰り返し、ステップ（２）又は（３）の条件を満たさなくなるとこの処理を終了する。
【００９１】
以上のように、この実施例では、回線毎の最大帯域などを個別に任意に定めて帯域分配制御に反映させることができ、回線毎に所要帯域を超過する帯域の分配を避けるように制御することもできる。
（実施例４）
本発明の帯域分配装置の実施例について図３，図２４及び図２５を参照して説明する。この実施例は請求項４に対応する。
【００９２】
この実施例では、請求項４の残余帯域積算手段，減算手段及び加算手段は、それぞれ残余帯域積算カウンタ３２，減算手段３４及び加算手段３１に対応する。
図３はこの実施例の帯域分配装置の構成を示すブロック図である。図２４は、この実施例の多段分配のフローチャートである。図２５は、この実施例の残余分配のフローチャートである。
【００９３】
この実施例は前述の実施例３の変形例である。この実施例では、分配帯域調整手段３０が実施例３に対して変更されている。変更された部分について以下に説明する。
図３に示すように、この実施例の分配帯域調整手段３０には加算手段３１，残余帯域積算カウンタ３２，再分配手段３３及び減算手段３４が備わっている。
【００９４】
残余帯域積算カウンタ３２は、残余帯域積算値を回線毎に算出する。減算手段３４は、再分配した残余帯域に相当する値を残余帯域積算カウンタ３２の残余帯域積算値から減算する。加算手段３１は、全回線の残余帯域の総和に全回線の設定値の総和に対する各回線の設定値の比を乗じた値を該当する回線の残余帯域積算値に加算する。再分配手段３３は、残余帯域積算カウンタ３２における残余帯域積算値が大きい順番で選択した回線に対して残余帯域を再分配する。
【００９５】
ここでは、残余帯域を複数周期に渡って分配する場合を想定している。また、パケットはセルであると仮定する。
更に、実施例２と同様に、該当する帯域分配周期において回線に対する分配パケット数が１に満たない帯域を回線全体で合計した残余帯域を、所定の分配比率（Ｐ.ＧＵＢ−Ｐ.ＦＸＢ＝Ｐi.ＡＳＢ又は均等）で公平に分配することを想定している。
【００９６】
分配帯域調整手段３０は、各帯域分配周期にて回線に対する１セルに満たない分配セル数、すなわち残余帯域を複数の帯域分配周期で平均して公平になるように再分配する。
残余帯域積算カウンタ３２は、回線毎に残余帯域積算値を保持する。この残余帯域積算値は、残余帯域分配を行う際の優先度を示すパラメータである。残余帯域積算カウンタ３２が保持した残余帯域積算値が大きい回線から順に、残余帯域を分配する。減算手段３４は、分配されたセル数を残余帯域積算値から減算する。
【００９７】
まず、分配比率が（Ｐi.ＦＸＢ）である場合の例を示す。
この例では、加算手段３１により、残余帯域積算値は、回線毎に((余剰帯域)−(分配済み余剰帯域))×(Ｐi.ＦＸＢ)／Σ(Ｐi.ＡＳＢ)の小数部分を加算する。
ここで、［((余剰帯域)−（分配済み余剰帯域))×(Ｐi.ＡＳＢ)／Σ(Ｐi.ＡＳＢ)］は多設分配により既に対応する回線に対して分配が終了している。
【００９８】
次に、分配比率が均等である例を示す。
この例では、加算手段３１により、残余帯域積算値は、回線毎に((余剰帯域分のセル)−(分配済みのセル))×１／(回線数)の小数部分を加算される。
具体的な多段分配及び残余分配の動作はそれぞれ図２４及び図２５に示されている。これらの図中に示された各記号の定義は次の通りである。
【００９９】
ＢＡＰ(j)：ｊ番目の帯域分配周期
ＲＭＢｊ：ＢＡＰ(j)で生成した残余帯域の総和
Ｅij.ＧＵＢ：ｉ番回線のＢＡＰ(j)における保証帯域
Ｐi.ＡＳＢ：ｉ番回線の余剰帯域割当比
Ｅij.ＭＡＢ：ｉ番回線のＢＡＰ(j)における最大帯域
Ｅj.ＤＡＢ：ＢＡＰ(j)における全回線の合計として使用可能な全体帯域
ＲＱｉｊ：ｉ番回線のＢＡＰ(j)における割当要求帯域
ＤＢｉｊ：ｉ番回線のＢＡＰ(j)における割当帯域
ＲＭｉｊ：ｉ番回線のＢＡＰ(j)における残余帯域積算値
ＵｎＦij：ｉ番回線のＢＡＰ(j)における分配未了フラグ(未了=1/完了=0)
ＳＰＢｊ：ＢＡＰ(j)での余剰帯域
ＦrameＬ：フレームサイズ
Ｍｍａｘ：多段分配の最終段数
Ｉｍａｘ：回線の総数
まず図２４の動作について説明する。
【０１００】
図２４のステップ（１）では、所要帯域が０以外の回線については分配未了フラグを「１」すなわち未了とし、所要帯域が０の回線については「０」すなわち完了とする。
但し、ＲＱｉｊが固定帯域Ｐ．ＦＸＢに満たない場合、ＲＱｉｊにＰ．ＦＸＢを代入してからステップ（１）の処理を行う。
【０１０１】
ステップ（２）では、（ｍ＝０）段目の多段分配の結果として、未了回線のみについてＢＡＰ(j)での保証帯域分Ｅij.ＧＵＢをＤＢｉｊ(m=0)に分配する。
ステップ（３）では、全体の帯域Ｅｊ．ＤＡＢから、分配した保証帯域の総和を差し引いた共用可能な余剰帯域ＳＰＢとする。
【０１０２】
ステップ（４）では、ＤＢｉｊｍまでの分配帯域として、（ｍ＝ｍ−１）での分配帯域ＤＢｉｊ（ｍ−１）に分配未了回線はｍ段目での余剰帯域ＳＰＢに回線ｉの所定の帯域分配比率であるＰi.ＡＳＢを掛け、分配未了回線の帯域分配比率Ｐi.ＡＳＢの総和で除した値をフレーム単位で加えた帯域を算出する。
ステップ（５）〜（１０）の処理においては、ｍ段分配までの分配帯域が回線ｉの帯域分配周期ｊにおける最大帯域設定であるＥij.ＭＡＢか、回線ｉの帯域分配周期ｊでの所要帯域ＲＱｉｊに至っているか判別し、至っている場合にはＥij.ＭＡＢ，ＲＱｉｊの小さい方の値を選択し、分配未了フラグを「０」すなわち完了に変更する。
【０１０３】
ステップ（１１）では、ステップ（５）〜（１０）での分配帯域の調整の結果のｍ段分配での分配後の余剰帯域を全回線の合計として使用可能な全体帯域Ｅij.ＤＡＢから割当済みの帯域ＤＢｉｊｍの総和を差し引いて算出する。
ステップ（１２）〜（１４）では、多段分配終了の可否を判別する。ステップ（１２）では、全回線が分配完了であればステップ（１６）を経て終了とする。
【０１０４】
ステップ（１３）では余剰帯域が０であるか全回線の分配帯域がｍ段分配の結果の分配帯域ＤＢｉｊｍ＝ＤＢｉｊ（ｍ−１）であれば終了とする。終了の場合は、ステップ（１６）で余剰帯域ＳＰＢｊを帯域分配周期ｊで発生した残余帯域として代入する。
ステップ（１４）では、ｍ段分配の最大段数であるＭｍａｘまで分配していれば終了とする。
【０１０５】
ステップ（１２）〜（１４）で終了と判別されない場合には、ステップ（１５）でｍに１を加算して次のステップ（４）に進む。
次に、図２５に示す動作について説明する。
【０１０６】
図２５のステップ（１）では、帯域分配周期ｊでの残余帯域の総和に帯域分配比率Ｐi.ＡＳＢを乗じてＰi.ＡＳＢの総和を除した値を、各回線の残余帯域積算値のこの周期での加算分として加算する。
ステップ（２）では、残余帯域積算値が最大の回線ｉを選択する。
ステップ（３）では、選択された回線ｉがＲＭＢｊで分配可能か判別する。
【０１０７】
分配可能であれば、ステップ（４）で１フレームの帯域を回線ｉに分配し、分配した帯域分をＲＭＢｊ及び回線ｉのＲＭｉｊから差し引き、ステップ（２）に戻る。
ステップ（３）の条件を満たさない場合にはステップ（５）に進む。ステップ（５）では、ステップ（３）で選択された回線ｉよりもＲＭｉｊが小さい回線が無いか判別し、あれば、ステップ（６）で次にＲＭｉｊが大きい回線ｉを選択してステップ（３）に進む。無ければ終了する。
【０１０８】
図２４，図２５では、Ｐｉ．ＡＳＢ比での分配を示した。均等に分配する場合、全ての回線のＰｉ．ＡＳＢを１とする。
この実施例の効果について説明する。例えば、ある回線への分配が、小数部を含めて２５．１セルとなる場合を想定する。この場合、従来例ではセル未満を切り捨てる必要があるため、端数分の０．１セルが分配されない。
【０１０９】
しかしこの実施例では、１０周期毎に１セルの残余帯域の再分配が可能であるので、端数を有効かつ公平に分配することができる。
なお、各回線における多段分配を十分に行わず途中で打ち切った場合、多段分配後の端数が小数とならず整数部を含む可能性があり、前述の実施例１と同様な残余帯域となるが、この実施例の動作に影響はない。但し、打ち切らない場合は、残余帯域を発生する回線と分配未了回線とが等しいが、打ち切った場合、残余帯域を発生する回線で分配が完了している回線が存在し得る。この実施例は特に、回線毎の残余帯域を個別に識別する必要が無いため、実装が容易である特徴を有する。
【０１１０】
（実施例５）
本発明の帯域分配装置の実施例について図２６及び図２７を参照して説明する。この実施例は請求項５に対応する。
図２６は、この実施例の多段分配のフローチャートである。図２７は、この実施例の残余分配のフローチャートである。
【０１１１】
この実施例は前述の実施例４の変形例である。この実施例では、分配帯域調整手段３０の加算手段３１が実施例４と異なっている。変更された部分について以下に説明する。
実施例４と同様に、この実施例の分配帯域調整手段３０は加算手段３１，残余帯域積算カウンタ３２，再分配手段３３及び減算手段３４を備えている。
【０１１２】
残余帯域積算カウンタ３２は、残余帯域積算値を回線毎に算出する。減算手段３４は、再分配した残余帯域に相当する値を残余帯域積算カウンタ３２の残余帯域積算値から減算する。加算手段３１は、残余帯域がある回線の残余帯域に相当する値を残余帯域積算カウンタ３２の残余帯域積算値に加算する。再分配手段３３は、残余帯域積算カウンタ３２における残余帯域積算値が大きい順番で選択した回線に対して残余帯域を再分配する。
【０１１３】
具体的な多段分配及び残余分配の動作はそれぞれ図２６及び図２７に示されている。これらの図中に示された各記号の定義は次の通りである。
ＢＡＰ(j)：ｊ番目の帯域分配周期
ＲＭＢｊ：ＢＡＰ(j)で生成した残余帯域の総和
Ｅij.ＧＵＢ：ｉ番回線のＢＡＰ(j)における保証帯域
Ｐi.ＡＳＢ：ｉ番回線の余剰帯域割当比
Ｅij.ＭＡＢ：ｉ番回線のＢＡＰ(j)における最大帯域
Ｅj.ＤＡＢ：ＢＡＰ(j)における全回線の合計として使用可能な全体帯域
ＲＱｉｊ：ｉ番回線のＢＡＰ(j)における割当要求帯域
ＤＢｉｊ：ｉ番回線のＢＡＰ(j)における割当帯域
ＲＭｉｊ：ｉ番回線のＢＡＰ(j)における残余帯域積算値
ＵｎＦij：ｉ番回線のＢＡＰ(j)における分配未了フラグ(未了=1/完了=0)
ＳＰＢｊ：ＢＡＰ(j)での余剰帯域
ＦrameＬ：フレームサイズ
ＡＲＭｉｊ：ｉ番回線のＢＡＰ(j)における残余帯域積算値の加算分
Ｍｍａｘ：多段分配の最終段数
Ｉｍａｘ：回線の総数
まず図２６の動作について説明する。
【０１１４】
図２６のステップ（１）では、所要帯域が０以外の回線については分配未了フラグを「１」すなわち未了とし、所要帯域が０の回線については「０」すなわち完了とする。
但し、ＲＱｉｊが固定帯域Ｐ．ＦＸＢに満たない場合、ＲＱｉｊにＰ．ＦＸＢを代入してからステップ（１）の処理を行う。
【０１１５】
ステップ（２）では、（ｍ＝０）段目の多段分配の結果として、未了回線のみについてＢＡＰ(j)での保証帯域分Ｅij.ＧＵＢをＤＢｉｊ(m=0)に分配する。
ステップ（３）では、全体の帯域Ｅｊ．ＤＡＢから、分配した保証帯域の総和を差し引いた共用可能な余剰帯域ＳＰＢとする。
ステップ（４）では、ＤＢｉｊｍまでの分配帯域として、（ｍ＝ｍ−１）での分配帯域ＤＢｉｊ（ｍ−１）に分配未了回線はｍ段目での余剰帯域ＳＰＢに回線ｉの所定の帯域分配比率であるＰi.ＡＳＢを掛け、分配未了回線の帯域分配比率Ｐi.ＡＳＢの総和で除した値をフレーム単位で加えた帯域を算出する。更に、ｍ段分配の各段での１フレームに満たない端数を該当する回線の残余帯域積算値として積算する。
【０１１６】
ステップ（５）〜（１０）の処理においては、ｍ段分配までの分配帯域が回線ｉの帯域分配周期ｊにおける最大帯域設定であるＥij.ＭＡＢか、回線ｉの帯域分配周期ｊでの所要帯域ＲＱｉｊに至っているか判別し、至っている場合にはＥij.ＭＡＢ，ＲＱｉｊの小さい方の値を選択し、分配未了フラグを「０」すなわち完了に変更する。
【０１１７】
ステップ（１１）では、ステップ（５）〜（１０）での分配帯域の調整の結果のｍ段分配での分配後の余剰帯域を全回線の合計として使用可能な全体帯域Ｅij.ＤＡＢから割当済みの帯域ＤＢｉｊｍと残余帯域積算値の帯域分配周期ｊでの加算分の総和を差し引いて算出する。
ステップ（１２）〜（１４）では、多段分配終了の可否を判別する。ステップ（１２）では、全回線が分配完了であれば終了とする。
【０１１８】
ステップ（１３）では余剰帯域が０であるか全回線の分配帯域がｍ段分配の結果の分配帯域ＤＢｉｊｍ＝ＤＢｉｊ（ｍ−１）であれば終了とする。
ステップ（１４）では、ｍ段分配の最大段数であるＭｍａｘまで分配していれば終了とする。
ステップ（１２）〜（１４）で終了と判別されない場合には、ステップ（１５）でｍに１を加算して次のステップ（４）に進む。
【０１１９】
次に、図２７に示す動作について説明する。
図２７のステップ（１）では、帯域分配周期ｊでの残余帯域の総和を各回線の残余帯域積算値の帯域分配周期ｊでの加算分の総和として算出する。また、各回線の残余帯域積算値は、帯域分配周期（ｊ−１）での残りの値に帯域分配周期ｊでの加算分を加えて算出する。
【０１２０】
ステップ（２）では、残余帯域積算値が最大の特定の回線ｉを選択する。
ステップ（３）では、選択された回線ｉがＲＭＢｊで分配可能か判別する。
分配可能であれば、ステップ（４）で１フレームの帯域を回線ｉに分配し、分配した帯域分をＲＭＢｊ及び回線ｉのＲＭｉｊから差し引き、ステップ（２）に戻る。
【０１２１】
ステップ（３）の条件を満たさない場合にはステップ（５）に進む。ステップ（５）では、ステップ（３）で選択された回線ｉよりもＲＭｉｊが小さい回線が無いか判別し、あれば、ステップ（６）で次にＲＭｉｊが大きい回線ｉを選択してステップ（３）に進む。無ければ終了する。
この実施例では、前述の実施例４と比べて、残余セルを発生したＴ−ＣＯＮＴに対してのみ残余帯域積算値を加算することになるため、残余帯域の分配が公平になる効果がある。
【０１２２】
（実施例６）
本発明の帯域分配装置の実施例について図２８を参照して説明する。この実施例は請求項６に対応する。
図２８は、この実施例の残余分配のフローチャートである。
この実施例は前述の実施例４の変形例である。この実施例では、分配帯域調整手段３０の加算手段３１及び減算手段３４が実施例４と異なっている。変更された部分について以下に説明する。
【０１２３】
実施例４と同様に、この実施例の分配帯域調整手段３０は加算手段３１，残余帯域積算カウンタ３２，再分配手段３３及び減算手段３４を備えている。
残余帯域積算カウンタ３２は、残余帯域積算値を回線毎に算出する。減算手段３４は、再分配した残余帯域に相当する値に残余係数を乗じた値を残余帯域積算カウンタ３２の残余帯域積算値から減算する。加算手段３１は、全回線の残余帯域の総和に全回線の設定値の総和に対する当該回線の設定値の比と残余係数を乗じた値を残余帯域積算カウンタ３２の残余帯域積算値に加算する。再分配手段３３は、残余帯域積算カウンタ３２における残余帯域積算値が大きい順番で選択した回線に対して残余帯域を再分配する。
【０１２４】
この実施例における残余分配の動作は図２８に示すとおりである。図２８のステップ（１）及びステップ（４）は、図２５と比べて次の点が変更されている。ステップ（１）では、残余帯域積算値の桁をあげて演算を容易化するために、残余係数Rcoeffを乗じている。また、ステップ（１）で残余係数Rcoeffを乗じていることに対応して、ステップ（４）では残余帯域積算値から分配帯域を減ずる際に、分配した帯域に同じ残余係数Rcoeffを乗じている。
【０１２５】
この実施例では、前述の実施例４と比べて、残余帯域積算値が残余係数だけ大きくなるので、整数演算しかできない帯域分配装置に対しても適用可能である効果がある。
（実施例７）
本発明の帯域分配装置の実施例について図２９を参照して説明する。この実施例は請求項７に対応する。
【０１２６】
図２９は、この実施例の残余分配のフローチャートである。
この実施例は前述の実施例５の変形例である。この実施例では、分配帯域調整手段３０の加算手段３１及び減算手段３４が実施例５と異なっている。変更された部分について以下に説明する。
実施例５と同様に、この実施例の分配帯域調整手段３０は加算手段３１，残余帯域積算カウンタ３２，再分配手段３３及び減算手段３４を備えている。
【０１２７】
残余帯域積算カウンタ３２は、残余帯域積算値を回線毎に算出する。減算手段３４は、残余帯域積算カウンタ３２の残余帯域積算値から再分配した残余帯域に相当する値に残余係数を乗じた値を減算する。加算手段３１は、残余帯域がある回線の残余帯域に相当する値に残余係数を乗じた値を加算する。再分配手段３３は、残余帯域積算カウンタ３２における残余帯域積算値が大きい順番で選択した回線に対して残余帯域を再分配する。
【０１２８】
この実施例における残余分配の動作は図２９に示すとおりである。図２９のステップ（１）及びステップ（４）は、図２７と比べて次の点が変更されている。
ステップ（１）では、残余帯域積算値の桁をあげて演算を容易化するために、残余係数Rcoeffを乗じている。また、ステップ（１）で残余係数Rcoeffを乗じていることに対応して、ステップ（４）では残余帯域積算値から分配帯域を減ずる際に、分配した帯域に同じ残余係数Rcoeffを乗じている。
【０１２９】
この実施例は、前述の実施例５と比べて、残余帯域積算値が残余係数だけ大きくなるので、整数演算しかできない帯域分配装置に対しても適用可能である効果がある。
（実施例８）
本発明の帯域分配装置の実施例について図３０〜図３３を参照して説明する。この実施例は請求項８に対応する。
【０１３０】
図３０はこの実施例の多段分配のフローチャート（１）である。図３１はこの実施例の残余分配のフローチャート（１）である。図３２はこの実施例の多段分配のフローチャート（２）である。図３３はこの実施例の残余分配のフローチャート（２）である。
この実施例は前述の実施例４の変形例である。変更された部分について以下に説明する。
【０１３１】
この実施例では、残余帯域の再分配先の回線を特定するために利用される分配テーブルを分配帯域調整手段３０が備えている。分配帯域調整手段３０は残余帯域を分配テーブルの内容に従って順次に再分配する。この分配テーブルの構成の具体例を次の表１に示す
【表１】
0003710427.tif 000002
例えば、帯域割当対象の２つの回線＃１，＃２が存在する場合を想定し、それぞれの回線に定められた保証帯域などのパラメータ（設定値）の比が１：２である場合を仮定すると、１：２の比で残余帯域を分配すれば公平になる。
【０１３２】
従って、各帯域分配周期で発生する残余帯域が１セルである場合を想定すると、３周期に渡って、各周期で発生する１セルの残余帯域を＃１，＃２，＃２に順次に分配すれば不公平が生じない。
すなわち、各回線のパラメータに応じて予め決定した分配テーブルの内容に従って順次に残余帯域を再分配すればよい。ここで、分配が完了した回線に関しては飛ばして分配することで、残余帯域を有効に分配することができる。
【０１３３】
なお、複数回線のパラメータ間に公約数がある場合には、パラメータを公約数で除した値をもって再分配することで繰り返しが一巡するのに要する帯域分配周期数を削減できる。
具体的な動作については図３０〜図３３に示すとおりである。
まず図３０を参照して多段分配を説明する。
【０１３４】
図３０のステップ（１）では、全回線で帯域分配周期ｊにて使用可能な全体帯域Ｅj.ＤＡＢから各回線に帯域分配周期ｊにて分配が保証されているＥij.ＧＵＢの帯域の総和を差し引いて、帯域分配周期ｊでの余剰帯域ＳＰＢｊを算出する。
ステップ（２）では、余剰帯域ＳＰＢｊに帯域分配比率Ｐi.ＡＳＢの総和にフレーム長FlameLを乗じた値がいくつ含まれるか、すなわち所定の帯域分配比率Ｐi.ＡＳＢで分配可能な回数を算出し、（ΣＰi.ＡＳＢ×FlameL）の数をＮ.ＳＰＢｊとする。
【０１３５】
ステップ（３）では、Ｎ.ＳＰＢｊを用いて回線ｉへの帯域分配周期ｊでの分配帯域ＤＢｉｊとして（Ｅij.ＧＵＢ＋Ｐi.ＡＳＢ×FlameL×Ｎ.ＳＰＢｊ）を算出する。
ステップ（４）では、残余帯域積算値の総和として、帯域分配周期ｊにて使用可能な全体帯域Ｅij.ＤＡＢからステップ（２）での分配帯域の総和を差し引いた値を算出する。
【０１３６】
次に、図３１を参照して残余分配を説明する。
図３１のステップ（１）では、残余帯域積算値の総和が０以外であるか判別し、０以外であればステップ（２）に進み、０であればこの処理を終了する。
【０１３７】
ステップ（２）では、前回の残余分配で分配しかけの回線があるか判別し、あればステップ（３）へ進み、無ければステップ（４）に進む。
分配しかけの回線があるとは、例えば表１において設定値が１を超える回線（回線番号が２又は４）に対して、帯域分配周期（ｊ−１）にて設定値の内の１だけ図３１の処理に従って分配している場合を表す。
【０１３８】
分配しかけの回線があれば、ステップ（３）で分配しかけの回線に対して分配しかけの設定値相当の帯域と、ＲＭＢｊの値との中で小さい方の値を上限として分配し、分配した帯域をＲＭＢｊから減算する。
ステップ（４）では、ＲＭＢｊが０以外か判別し、０以外であればステップ（５）に進み、０であればこの処理を終了する。
【０１３９】
ステップ（５）では、先行する帯域分配周期（ｊ−１）において図３１の処理で帯域分配先として選択した回線の次の回線にｍｉｎ（ＲＭＢｊ，分配テーブルの設定値）にて帯域分配し、ステップ（４）に進む。
図３２及び図３３は、それぞれは図３０及び図３１の動作の変形例であり、これらの関係は実施例１と実施例３との関係と同じである。図３２及び図３３に対して変更された部分について、以下に説明する。
【０１４０】
まず、図３２について説明する。
図３２のステップ（３）では、帯域分配周期ｊにおける回線ｉに対する分配帯域ＤＢｉｊと回線ｉの帯域分配周期ｊでの所要帯域ＲＱｉｊと最大帯域設定Ｅij.ＭＡＢとを比較して最小の値を選択する。また、ステップ（３）の変更に伴って、ステップ（４）では全体帯域Ｅij.ＤＡＢからステップ（３）の結果のＤＢｉｊの総和を減算して算出する。
【０１４１】
次に図３３について説明する。
図３３のステップ（１）では、残余帯域積算値の総和が０以外であるか判別し、０以外であればステップ（２）に進み、０であればこの処理を終了する。
ステップ（２）では、前回の残余分配で分配しかけの回線があるか判別し、あればステップ（３）へ進み、無ければステップ（４）に進む。
【０１４２】
分配しかけの回線があり、かつ該当する回線が（ＵｎＦij＝１）であれば、ステップ（３）で分配しかけの回線に対して分配しかけの設定値相当の帯域と、ＲＭＢｊの値と、Ｅｉｊ．ＭＡＢから既分配帯域を差し引いた帯域と、ＲＱｉｊから既分配帯域を差し引いた帯域との中で小さい方の値を上限として分配し、分配した帯域をＲＭＢｊから減算する。（ＵｎＦij＝０）であれば分配しない。
【０１４３】
ステップ（４）では、ＲＭＢｊが０以外か判別し、０以外であればステップ（５）に進み、０であればこの処理を終了する。
ステップ（５）では、（ＵｎＦij＝１）の回線があるか判別し、あればステップ（６）に進み、無ければこの処理を終了する。
ステップ（６）では、先行する帯域分配周期（ｊ−１）において図３３の処理で帯域分配先として選択した回線と今回の帯域分配周期（ｊ）においてステップ（３）及びステップ（６）で選択した回線の中で最後に選択した回線の次に位置する（ＵｎＦij＝１）の回線にｍｉｎ（ＲＭＢｊ，分配テーブルの設定値，Ｅｉｊ．ＭＡＢから既分配帯域を差し引いた帯域，ＲＱｉｊから既分配帯域を差し引いた帯域）にて帯域分配し、ステップ（７）に進む。
【０１４４】
ステップ（７）では、ステップ（６）で分配した回線の分配帯域ＤＢｉｊが最大帯域設定Ｅij.ＭＡＢに等しいか又は所要帯域ＲＱｉｊに等しいか判別し、等しい場合にはステップ（８）へ進み、そうでない場合はステップ（２）に進む。ステップ（８）では、該当する回線については分配が完了したので（ＵｎＦij＝０）にする。
【０１４５】
この実施例では、図３０〜図３３に示す２種類の動作のいずれを採用する場合でも、実施例４と比べて、残余帯域力ウンタを具備する必要が無いため、残余帯域の分配に関する公平性は劣化するが実装が容易になる効果がある。
（実施例９）
本発明の帯域分配装置の実施例について図３４を参照して説明する。この実施例は請求項９に対応する。
【０１４６】
図３４はこの実施例の残余分配のフローチャートである。この実施例は前述の実施例４の変形例である。変更された部分について以下に説明する。
この実施例と実施例４との違いは分配帯域調整手段３０にある。この実施例の分配帯域調整手段３０は、残余帯域積算カウンタ３２の残余帯域積算値が大きい回線順に残余帯域を分配する代わりに残余帯域積算値が所定の閾値（例えば１）を超過する回線に残余帯域分配を受ける権利を付与し、権利を有する回線に対して順次に帯域を再分配する。
【０１４７】
図３４を参照して具体的な動作を説明する。
図３４のステップ（１）では、帯域分配周期ｊでの残余帯域の総和に帯域分配比率Ｐi.ＡＳＢを乗じて、Ｐi.ＡＳＢの総和を除した値を各回線の残余帯域積算値の帯域分配周期ｊでの加算分として加算する。
ステップ（２）では、残余帯域積算値ＲＭｉｊが所定値以上の回線があるか判別し、あればステップ（３）に進み、無ければこの処理を終了する。
【０１４８】
ステップ（３）では、ＲＭｉｊが所定値以上の回線のフレーム以上のＲＭＢｊがあるか判別し、あればステップ（４）へ進み、無ければこの処理を終了する。
ステップ（４）では、フレーム長がＲＭＢｊ以下で、ＲＭｉｊが所定値以上の回線を順次選択してステップ（５）に進む。
ステップ（５）では、フレーム単位でＲＭＢｊ以下で分配する。該当する回線のＲＭｉｊとＲＭＢｊからそれぞれ分配した帯域分を減算しステップ（２）に進む。
【０１４９】
この実施例では、実施例４と異なり、残余帯域を再分配する対象の回線を残余帯域積算値をキーとしてソートし分配対象回線を選択する処理が不要である効果がある。また、この実施例では、残余帯域積算値は正値のみとすることが可能であり、実装が容易である効果もある。
（実施例１０）
本発明の帯域分配装置の実施例について図３５を参照して説明する。この実施例は請求項１０に対応する。
【０１５０】
図３５はこの実施例の残余分配のフローチャートである。この実施例は前述の実施例５の変形例である。変更された部分について以下に説明する。
この実施例と実施例５との違いは分配帯域調整手段３０にある。この実施例の分配帯域調整手段３０は、残余帯域積算カウンタ３２の残余帯域積算値が大きい回線順に残余帯域を分配する代わりに残余帯域積算値が所定の閾値（例えば１）を超過する回線に残余帯域分配を受ける権利を付与し、権利を有する回線がある場合は権利を有する回線に対して順次に再分配する。
【０１５１】
権利を有する回線が無い場合には、所要帯域分の帯域分配がなされていない回線でかつ権利の無い回線に対して順次に再分配する。権利の無い回線に対して順次再分配する場合、残余帯域積算値が所定の値、例えば初期値（０）等を超えている回線に対して再分配することが望ましい。
図３５を参照して具体的な動作について説明する。
【０１５２】
図３５のステップ（１）では、帯域分配周期ｊにおける残余帯域の総和は各回線の残余帯域積算値の帯域分配周期ｊでの加算分の総和として算出し、各回線の残余帯域積算値は帯域分配周期（ｊ−１）での残りの値に帯域分配周期ｊでの加算分を加えて算出する。
ステップ（２）では、残余帯域積算値ＲＭｉｊが所定値以上の回線があるか判別し、あればステップ（３）に進み、無ければこの処理を終了する。
【０１５３】
ステップ（３）では、ＲＭｉｊが所定値以上の回線のフレーム以上のＲＭＢｊがあるか判別し、あればステップ（４）へ進み、無ければこの処理を終了する。
ステップ（４）では、フレーム長がＲＭＢｊ以下でＲＭｉｊが所定値以上の回線を順次選択し、ステップ（５）に進む。
ステップ（５）では、フレーム単位でＲＭＢｊ以下で分配する。該当する回線のＲＭｉｊ，ＲＭＢｊからそれぞれ分配した帯域分を減算し、ステップ（２）に進む。
【０１５４】
前述の実施例５と異なり、残余帯域を再配分する対象の回線を残余帯域積算値をキーとしてソートし、分配対象回線を選択する処理が不要である効果がある。
（実施例１１）
本発明の帯域分配装置の実施例について図３６，図３７を参照して説明する。この実施例は請求項１１に対応する。
【０１５５】
図３６，図３７はこの実施例の残余分配のフローチャートである。この実施例は前述の実施例４，実施例５の変形例である。変更された部分について以下に説明する。
この実施例と実施例４，実施例５との違いは分配帯域調整手段３０にある。この実施例の分配帯域調整手段３０は、残余帯域を再分配する対象とする回線を回線の所要帯域又は最大帯域に満たない分配未了回線又は残余帯域が当該帯域分配周期において発生した回線又はその組合せに該当する回線に対してのみ再分配する。
【０１５６】
図３６を参照して具体的な動作を説明する。この動作は実施例４の変形例に相当する。
図３６のステップ（１）では、帯域分配周期ｊでの残余帯域の総和に帯域分配比率Ｐｉ．ＡＳＢを乗じて、Ｐｉ．ＡＳＢの総和を除した値を各回線の残余帯域積算値の帯域分配周期ｊでの加算分として加算する。
【０１５７】
ステップ（２）では、（ＵｎＦij＝１）の回線があるか判別し、あればステップ（３）へ進み、無ければこの処理を終了する。
ステップ（３）では、（ＵｎＦij＝１）で残余帯域積算値ＲＭｉｊが最大の回線ｉを選択する。
ステップ（４）では、選択した回線ｉがＲＭＢｊで分配可能か判別する。分配可能であれば、ステップ（７）に進む。
【０１５８】
ステップ（７）では、１フレームを回線ｉに分配し、分配した帯域分をＲＭＢｊと回線ｉのＲＭｉｊから差し引き、回線ｉの分配帯域ＤＢｉｊに加えてステップ（８）に進む。
ステップ（４）の条件を満たさない場合には、ステップ（５）に進む。ステップ（５）では、（ＵｎＦij＝１）でステップ（３）で選択した回線よりもＲＭｉｊが小さい回線が無いか判別し、あれば次にＲＭｉｊが大きい回線ｉを選択してステップ（３）に進む。無ければこの処理を終了する。
【０１５９】
ステップ（８）では、分配帯域ＤＢｉｊが所要帯域ＲＱｉｊ未満又は最大帯域設定Ｐij.ＭＡＢ未満か判別し、共に未満であればステップ（２）に進む。
そうでない場合にはステップ（９）に進み、割当帯域ＤＢｉｊを所要帯域ＲＱｉｊ又は最大帯域設定の小さい方の値とし、Ｐij.ＭＡＢ未満の所要帯域ＲＱｉｊ未満又は最大帯域設定Ｐij.ＭＡＢに対する超過分をＲＭＢｊに戻し、（ＵｎＦij＝０）に書き換えてステップ（２）に進む。
【０１６０】
次に図３７を参照して説明する。この動作は実施例５の変形例に相当する。
図３７のステップ（１）では、帯域分配周期ｊでの残余帯域の総和は各回線の残余帯域積算値の帯域分配周期ｊでの加算分の総和として算出し、各回線の残余帯域積算値は帯域分配周期（ｊ−１）での残りの値に帯域分配周期ｊでの加算分を加えて算出する。
【０１６１】
ステップ（２）では、（ＵｎＦij＝１）の回線があるか判別し、あればステップ（３）へ進み、無ければこの処理を終了する。
ステップ（３）では、（ＵｎＦij＝１）で残余帯域積算値ＲＭｉｊが最大の回線ｉを選択する。
ステップ（４）では、選択した回線ｉがＲＭＢｊで分配可能か判別する。分配可能であれば、ステップ（７）に進む。
【０１６２】
ステップ（７）では、１フレームを回線ｉに分配し、分配した帯域分をＲＭＢｊと回線ｉのＲＭｉｊから差し引き、回線ｉの分配帯域ＤＢｉｊに加えてステップ（８）に進む。
ステップ（４）の条件を満たさない場合には、ステップ（５）に進む。ステップ（５）では、（ＵｎＦij＝１）でステップ（３）で選択した回線よりもＲＭｉｊが小さい回線が無いか判別し、あれば次にＲＭｉｊが大きい回線ｉを選択してステップ（３）に進む。無ければこの処理を終了する。
【０１６３】
ステップ（８）では、分配帯域ＤＢｉｊが所要帯域ＲＱｉｊ未満又は最大帯域設定Ｐij.ＭＡＢ未満か判別し、共に未満であればステップ（２）に進む。
そうでない場合にはステップ（９）に進み、割当帯域ＤＢｉｊを所要帯域ＲＱｉｊ又は最大帯域設定の小さい方の値とし、Ｐij.ＭＡＢ未満の所要帯域ＲＱｉｊ未満又は最大帯域設定Ｐij.ＭＡＢに対する超過分をＲＭＢｊに戻し、（ＵｎＦij＝０）に書き換えてステップ（２）に進む。
【０１６４】
このため図３６の動作を適用する場合には、実施例４と比べて分配不要な回線に帯域を分配しなくなるので、帯域の使用効率の劣化を防止できる。また、図３７の動作を適用する場合には、分配未了回線以外に分配しなくなるので更に帯域の利用効率が向上する。
（実施例１２）
本発明の帯域分配装置の実施例について図３８を参照して説明する。この実施例は請求項１２に対応する。
【０１６５】
図３８はこの実施例の残余分配のフローチャートである。この実施例は前述の実施例１１の変形例である。変更された部分について以下に説明する。
この実施例と実施例１１との違いは分配帯域調整手段３０の加算手段３１にある。この実施例の加算手段３１は、分配未了かつ残余帯域が当該帯域分配周期において発生した回線に対してのみ残余帯域積算カウンタ３２の残余帯域積算値を加算する。
【０１６６】
図３８を参照して具体的な動作について説明する。
図３８と前述の図３６との違いはステップ（１）の内容のみである。すなわち、図３８のステップ（１）では、分配未了回線のみ次式により残余帯域積算値を加算する。
ＲＭｉｊ＝ＲＭi(j-1)＋UnFij×ＲＭＢｊ×Ｐi.ＡＳＢ／Σ(Ｐi.ＡＳＢ)
このため、分配が完了した回線に不必要に残余帯域積算値が積み上がる問題を解決でき、実施例１１と同様に実施例４の特性を向上する効果がある。
【０１６７】
（実施例１３）
本発明の帯域分配装置の実施例について図３９を参照して説明する。この実施例は請求項１３に対応する。
図３９はこの実施例の残余分配のフローチャートである。この実施例は前述の実施例５の変形例である。変更された部分について以下に説明する。
【０１６８】
この実施例と実施例５との違いは分配帯域調整手段３０の加算手段３１にある。この実施例の加算手段３１は、分配未了かつ残余帯域がある回線に対してのみ残余帯域積算カウンタ３２の残余帯域積算値を加算する。
図３９を参照して具体的な動作を説明する。図３９は図２７の変形例であり、ステップ（１）が変更されている。
【０１６９】
図３９のステップ（１）では、（ＲＭｉｊ＝ＲＭi(j-1)＋UnFij×ＡＲＭij）の計算を行い、分配未了回線のみ残余帯域積算値を加算するようになっている。このため、分配が完了した回線に不必要に残余帯域積算値が積み上がる問題を解決することができる。
【０１７０】
このため、より再分配が必要な回線に対する再分配が行なわれ易い。
（実施例１４）
本発明の帯域分配装置の実施例について図４０を参照して説明する。この実施例は請求項１４に対応する。
図４０はこの実施例の残余分配のフローチャートである。この実施例は前述の実施例１２の変形例である。変更された部分について以下に説明する。
【０１７１】
この実施例と実施例１２との違いは分配帯域調整手段３０の加算手段３１にある。この実施例の加算手段３１は、全回線の設定値の総和の代わりに、該当する帯域分配周期において残余帯域が発生した全回線の設定値の総和又は分配未了の全回線の設定値の総和又は両方に該当する全回線の設定値の総和を用いる。
図４０を参照して説明する。図４０は図３８の変形例であり、ステップ（１Ａ），（１Ｂ）が異なっている。
【０１７２】
図４０のステップ（１Ａ）では、帯域分配周期ｊにて残余帯域積算値の加算がある分配未了回線のみを（分配未了フラグＵｎＦij＝１）とし、残余帯域積算値の加算がある分配未了回線のみを帯域分配対象として選択している。
ステップ（１Ｂ）では、第２項の分母のＰi.ＡＳＢにＵｎＦijを乗ずることにより第２項による加算値を大きくしている。
【０１７３】
このため実施例１３と同様に、より再分配が必要な回線に対する再分配が行なわれ易い効果がある。
実施例４と同様に、この実施例の分配帯域調整手段３０には加算手段３１，残余帯域積算カウンタ３２，再分配手段３３及び減算手段３４が備わっている。
残余帯域積算カウンタ３２は、残余帯域積算値を回線毎に算出する。減算手段３４は、再分配した残余帯域に相当する値を残余帯域積算カウンタ３２の残余帯域積算値から減算する。加算手段３１は、全回線の残余帯域の総和に全回線の設定値の総和に対する各回線の設定値の比を乗じた値を該当する回線の残余帯域積算値に加算する。再分配手段３３は、残余帯域積算カウンタ３２における残余帯域積算値が大きい順番で選択した回線に対して残余帯域を再分配する。
【０１７４】
残余帯域を複数周期にわたって分配する場合の動作例について説明する。この実施例の分配帯域調整手段３０は、各帯域分配周期にて回線に対する１セルに満たない分配セル（残余帯域）を、複数の帯域分配周期の中で平均化して公平に分配する。残余帯域積算カウンタ３２は、回線毎に残余帯域積算値を保持する。この残余帯域積算値は、残余帯域分配を行う際の優先度を表す。
【０１７５】
保持した残余帯域積算値が大きい回線から順に残余帯域を分配する。残余帯域分配によって分配されたセル数は減算手段３４により残余帯域積算値から減算される。分配未了かつ多段分配での分配セル数に１セル未満の端数がある回線に対しては、以下の値が加算手段３１により加算される。
まず、分配比率が（Ｐ.ＧＵＢ−Ｐ.ＦＸＢ＝Ｐｉ．ＡＳＢ）である場合を想定する。
【０１７６】
この場合には、加算手段３１により、残余帯域積算値は多段分配により分配未了であった回線に対して、((余剰帯域)−(分配済み余剰帯域))×ＵｎＦｉｊ×Ｐi.ＡＳＢ／Σ(Ｐi.ＡＳＢ×ＵｎＦｉｊ）の小数部分を加算する。
分配比率が均等である場合には、分配比率がＰｉ．ＡＳＢであった場合において全回線のＰｉ．ＡＳＢを同値にした場合に等しい。
【０１７７】
この実施例では、実施例１３と同様に、より再分配が必要な回線に対する再分配が行なわれ易い効果がある。
（実施例１５）
本発明の帯域分配装置の実施例について図４及び図４１を参照して説明する。この実施例は請求項１５に対応する。
【０１７８】
図４はこの実施例の帯域分配装置の構成を示すブロック図である。図４１はこの実施例の多段分配のフローチャートである。
図４に示すように、この実施例の帯域分配装置１０は分配手段２０及び分配帯域回収手段５０を備えている。
分配手段２０は、所定の帯域分配周期で回線毎にパケット単位で複数演算段を用いて段階的に逐次帯域を分配する。
【０１７９】
分配帯域回収手段５０は、分配手段２０の複数演算段の最終段以外の演算段において、それまでの演算段で分配された帯域が該当する回線の所定の帯域又は所要帯域に満たない回線から分配された帯域を回収する。
分配帯域回収手段５０が回収した分配帯域は、分配手段２０の次の演算段において、それまでに分配された帯域が回線毎に定められた所定の帯域又は所要帯域に満たない回線に対して再分配する。
【０１８０】
例えば、前述の第(1)式において、（Ｎ−１）段以下のｋ段分配では、分配帯域がＥｉｊ．ＭＡＢ又は所要帯域ＲＱｉｊに満たない回線＃ｊに対する分配帯域ＤＢｊｋを分配帯域回収手段５０により回収し、（ｋ＋１）段分配での余剰帯域に加える。これにより、最終のＮ段分配以外では切り捨てを回避し、多段分配における端数を無くし、有効かつ公平に分配することが可能になる。
【０１８１】
具体的な多段分配の動作は図４１に示す通りである。また、図４１に示された各記号の定義は次の通りである。
ＢＡＰ(j)：ｊ番目の帯域分配周期
ＦrameＬ：フレームサイズ
ＳＰＢｊ：ＢＡＰ(j)でのｍ段目の多段分配で分配する余剰帯域
ＲＭＢｊ：ＢＡＰ(j)で生成した残余帯域積算値の総和
Ｅij.ＧＵＢ：ｉ番回線のＢＡＰ(j)における保証帯域
Ｐi.ＡＳＢ：ｉ番回線の余剰帯域分配比
Ｅij.ＭＡＢ：ｉ番回線のＢＡＰ(j)における最大帯域
Ｅj.ＤＡＢ：ＢＡＰ(j)における使用可能な全体帯域
ＤＢｉｊ：ｉ番回線のＢＡＰ(j)におけるｍ段目の多段分配後の分配帯域
ＵｎＦij：ｉ番回線のＢＡＰ(j)における分配未了フラグ(未了=1/完了=0)
ＲＱｉｊ：ｉ番回線のＢＡＰ(j)における所要帯域
図４１の内容について以下に説明する。
【０１８２】
図４１のステップ（１）では、所要帯域が０以外の回線については分配未了フラグを「１」すなわち未了とし、所要帯域が０の回線については「０」すなわち完了とする。
但し、ＲＱｉｊが固定帯域Ｐ．ＦＸＢに満たない場合、ＲＱｉｊにＰ．ＦＸＢを代入してからステップ（１）の処理を行う。
【０１８３】
ステップ（２）では、（ｍ＝０）段目の多段分配の結果として未了回線のみに対して、ＢＡＰ(j)での保証帯域分Ｅij.ＧＵＢをＤＢｉｊ（ｍ＝０）に分配し、（ｍ＝１，ＡＲＭij＝０）とする。
ステップ（３）では、全体の帯域から分配した保証帯域の総和を共用可能な余剰帯域ＳＰＢとする。
【０１８４】
ステップ（４）では、ＤＢｉｊｍまでの分配帯域として、（ｍ＝ｍ−１）での分配帯域ＤＢｉｊ（ｍ−１）に分配未了回線はｍ段目での余剰帯域ＳＰＢに回線ｉの所定の帯域分配比率であるＰi.ＡＳＢを掛け、分配未了回線の帯域分配比率Ｐi.ＡＳＢの総和で除した値をフレーム単位で加えた帯域を算出する。
ステップ（５）〜（１０）では、ｍ段分配までの分配帯域が回線ｉの帯域分配周期ｊにおける最大帯域設定であるＥij.ＭＡＢか回線ｉの帯域分配周期ｊにおける所要帯域ＲＱｉｊに至っているか判別し、至っている場合にはＥij.ＭＡＢ，ＲＱｉｊの小さい方の値を選択し、分配未了フラグを「０」すなわち完了に変更する。
【０１８５】
ステップ（１１）では、ｍ段分配の最大段数であるＭｍａｘまで分配しているか識別し、Ｍｍａｘまで分配している場合にはステップ（１７）に進み、Ｍｍａｘ未満である場合にはステップ（１２）に進む。
ステップ（１２）では、分配未了回線のＤＢｉｊを割当を保証するＥij.ＧＵＢ以外は解放する。ステップ（１３）では、ステップ（１２）で解放した帯域を含めて余剰帯域を算出する。
【０１８６】
ステップ（１４）では、全回線が分配完了であれば終了とみなす。
ステップ（１５）では、余剰帯域が０であるか又は全回線の分配帯域についてｍ段分配の結果が（分配帯域ＤＢｉｊｍ＝ＤＢｉｊ（ｍ−１））であれば終了とみなす。
ステップ（１５），（１６）で終了とみなさない場合には、ステップ（１６）でｍに１を加算してそれを更新しステップ（４）に進む。
【０１８７】
ステップ（１７）では、Ｍｍａｘ段目での余剰帯域ＳＰＢに回線ｉの所定の帯域分配比率であるＰi.ＡＳＢを掛け、分配未了回線の帯域分配比率Ｐi.ＡＳＢの総和で除した値でフレーム単位に満たない端数を残余帯域積算値の帯域分配周期ｊでの加算分とし、Ｍｍａｘ段目での余剰帯域ＳＰＢに回線ｉの所定の帯域分配比率であるＰi.ＡＳＢを掛け、分配未了回線の帯域分配比率Ｐi.ＡＳＢの総和で除した値でフレーム単位になる値をＥij.ＧＵＢに加えたものを分配帯域ＤＢｉｊとする。
【０１８８】
この実施例における帯域分配の具体例について説明する。
例えば、多段分配は２段までとし、Ｔ−ＣＯＮＴの要求帯域が２８セル、１段分配で２０．６セル、２段分配で４．５セルとした場合を想定する。この実施例を適用しない場合には、小数部を含めて分配すると２５．１セルとなるべき分配が、各段の分配でそれぞれ切り捨てを行うため端数が累積し、１セル少ない２４セルが分配される。
【０１８９】
この実施例では、最終段の分配以外は（分配帯域＜所要帯域）の場合は分配を保留して最終段の分配にて最終段までのセルをまとめて分配するので、次のように各段で分配される。
１段分配：２０．６セル、分配セル＜所要セルのため分配を保留（分配値０）
２段分配：１段分を含め２５．１セルで２５セルを分配。
【０１９０】
この実施例では、例えば（Ｐ.ＧＵＢ−Ｐ.ＦＸＢ＝Ｐｉ．ＡＳＢ）比で分配する場合には、各段での分配帯域は[((余剰帯域)−(分配完了T-CONTの分配済み余剰帯域))×ＵｎＦｉｊ×Ｐｉ．ＡＳＢ／ΣＰｉ．ＡＳＢ×ＵｎＦｉｊ]で表される。
また、例えば均等に分配する場合には、各段での分配帯域は[((余剰帯域分のセル)−(分配完了T-CONTの分配済みのセル))×１／(分配未了T-CONT数)]で表される。
【０１９１】
この実施例の最終の段数は、多段分配の段数が残余帯域以外の未分配帯域が残存しなくなるか、所定の段数である。
多段分配の各段での端数帯域は回線毎に異なり、かつ段数分累積する可能性があるため、端数帯域が多く発生した回線と残余帯域の再分配を受ける回線のと間に相関が少ないと不公平な分配になる。この実施例では、各分配段での端数分配処理においてこの不公平性を抑制する効果がある。
【０１９２】
以上のように、この実施例では、多段分配における端数処理により、帯域分配周期毎の多段分配での累積端数帯域を削減し、公平に分配する効果がある。
（実施例１６）
本発明の帯域分配装置の実施例について図５及び図４２を参照して説明する。
図５はこの実施例の帯域分配装置の構成を示すブロック図である。図４２はこの実施例の多段分配のフローチャートである。
【０１９３】
図５に示すように、この実施例の帯域分配装置１０は分配手段２０，分配帯域回収手段５０及び分配段端数分配手段６０を備えている。
この実施例の分配手段２０は、端数を含めて帯域を回線に分配する。
【０１９４】
分配手段２０における多段分配の動作は図４２に示すとおりである。
また、図４２に示す各記号の定義は次の通りである。
ＢＡＰ(j)：ｊ番目の帯域分配周期
ＦrameＬ：フレームサイズ
ＳＰＢｊ：ＢＡＰ(j)でのｍ段目の多段分配で分配する余剰帯域
ＲＭＢｊ：ＢＡＰ(j)で生成した残余帯域積算値の総和
Ｅij.ＧＵＢ：ｉ番回線のＢＡＰ(j)における保証帯域
Ｐi.ＡＳＢ：ｉ番回線の余剰帯域分配比
Ｅij.ＭＡＢ：ｉ番回線のＢＡＰ(j)における最大帯域
Ｅj.ＤＡＢ：ＢＡＰ(j)における使用可能な全体帯域
ＤＢｉｊ：ｉ番回線のＢＡＰ(j)におけるｍ段目の多段分配後の分配帯域
ＵｎＦij：ｉ番回線のＢＡＰ(j)における分配未了フラグ(未了=1/完了=0)
図４２の内容は前述の図２６の変形例である。すなわち、図４２ではステップ（１６）が追加されている。このステップ（１６）では、多段分配の端数帯域でフレーム単位になるものは、分配帯域として加えている。図４２の動作によって分配される帯域は、前述の第(1)式にならって表現すると、次式で表すことができる。
【０１９５】
DBin＝((EB0−ΣＰi.FXB)×Ｐi.ASB／ΣＰi.ASB＋Ｐi.FXB（ｎ＝１の時）
DBin＝((ΣΣEB(jk)−ΣΣDB(jk)×ASB(i)／ΣASB(i)＋FXB(i)) (2≦ｎ≦Nの時)即ち、前述の実施例１５と同様に多段分配の各段でガウスの記号による切り捨てを行わない。
分配帯域回収手段５０は、分配手段２０が各回線に分配した帯域から、パケット乃至セルに満たない満たない端数の帯域のみ回収する。分配帯域回収手段５０が回収した端数帯域は、分配段端数分配手段６０によって各回線に再分配される。
【０１９６】
分配段端数分配手段６０の動作については、前述の実施例１〜実施例１２に示された様々な分配帯域調整手段３０のいずれかにおける残余帯域の処理と同等の手段を用いて実現できる。
【０１９７】
この実施例の分配帯域回収手段５０は、実施例１〜実施例１３の分配帯域調整手段３０と異なり、残余帯域積算値に相当する値として多段分配の端数帯域積算値を用い、この値は帯域分配周期を跨いで引き継がずに、帯域分配周期毎に０クリアする。
この実施例における帯域分配の具体例について説明する。
【０１９８】
例えば、多段分配は２段までとし、Ｔ−ＣＯＮＴの要求帯域が２８セル、１段分配で２０．６セルの場合に２０セルを分配して、多段分配の端数帯域積算値に０．６セルを加算し、２段分配で４．５セルの場合に４セルを分配して多段分配の端数帯域積算値に０．５セルを加算する場合を想定する。
この場合、多段分配の端数帯域の分配で、多段分配の端数帯域積算値が１以上になるため１セルを分配し、多段分配の端数帯域積算値が１減算される。
【０１９９】
ここで、多段分配の端数帯域積算値の初期値は０である。多段分配の端数帯域積算値は、分配時の端数発生時に加算され、多段分配の端数帯域積算値の分配で減算される。
以上示したように、この実施例では前述の実施例１５と同様の効果がある。
（実施例１７）
本発明の帯域分配装置の実施例について図４３を参照して説明する。図４３はこの実施例の多段分配のフローチャートである。
【０２００】
この実施例は実施例１５の変形例であり、構成は実施例１５と同一である。但し、分配手段２０及び分配帯域回収手段５０は以下に示すように部分的に変更されている。
分配手段２０及び分配帯域回収手段５０は、実施例１６と同様に分配及び回収を行う。分配帯域回収手段５０は、この実施例では、多段分配の分配終了後に、回収した帯域を分配手段２０に渡し、多段分配による端数帯域を再度分配する。
【０２０１】
多段分配による端数帯域を再度分配する場合には、前述の第(1)式に基づいて帯域分配してもよいし、実施例１６の分配段端数分配手段６０と同様の処理を行なってもよい。
多段分配の具体的な動作について、図４３を参照して以下に説明する。図４３に示された各記号の定義は次の通りである。
【０２０２】
ＢＡＰ(j)：ｊ番目の帯域分配周期
ＦrameＬ：フレームサイズ
ＳＰＢｊ：ＢＡＰ(j)でのｍ段目の多段分配で分配する余剰帯域
ＲＭＢｊ：ＢＡＰ(j)で生成した残余帯域積算値の総和
Ｅij.ＧＵＢ：ｉ番回線のＢＡＰ(j)における保証帯域
Ｐi.ＡＳＢ：ｉ番回線の余剰帯域分配比
Ｅij.ＭＡＢ：ｉ番回線のＢＡＰ(j)における最大帯域
Ｅj.ＤＡＢ：ＢＡＰ(j)における使用可能な全体帯域
ＤＢｉｊ：ｉ番回線のＢＡＰ(j)におけるｍ段目の多段分配後の分配帯域
ＵｎＦij：ｉ番回線のＢＡＰ(j)における分配未了フラグ(未了=1/完了=0)
図４３のステップ（１）では、所要帯域が０以外の回線については分配未了フラグを「１」すなわち未了とし、所要帯域が０の回線については「０」すなわち完了とする。
【０２０３】
ステップ（２）では、（ｍ＝０）段目の多段分配の結果として未了回線のみに対して、ＢＡＰ(j)での保証帯域分Ｅij.ＧＵＢをＤＢｉｊ（ｍ＝０）に分配する。
ステップ（３）では、全体の帯域から分配した保証帯域の総和を共用可能な余剰帯域ＳＰＢとする。
ステップ（４）では、ＤＢｉｊｍまでの分配帯域として、（ｍ＝ｍ−１）での分配帯域ＤＢｉｊ（ｍ−１）に分配未了回線はｍ段目での余剰帯域ＳＰＢに回線ｉの所定の帯域分配比率であるＰi.ＡＳＢを掛け、分配未了回線の帯域分配比率Ｐi.ＡＳＢの総和で除した値をフレーム単位で加えた帯域を算出する。更に、ｍ段分配の各段での１フレームに満たない端数を該当する回線の残余帯域積算値として積算する。
【０２０４】
ステップ（５）〜（１０）では、ｍ段分配までの分配帯域が回線ｉの帯域分配周期ｊにおける最大帯域設定であるＥij.ＭＡＢか回線ｉの帯域分配周期ｊにおける所要帯域ＲＱｉｊに至っているか判別し、至っている場合にはＥij.ＭＡＢ，ＲＱｉｊの小さい方の値を選択し、分配未了フラグを「０」すなわち完了に変更する。
【０２０５】
ステップ（１１）では、ｍ段分配の最大段数であるＭｍａｘまで分配しているか識別し、Ｍｍａｘまで分配している場合にはステップ（１６）に進み、Ｍｍａｘ未満である場合にはステップ（１２）に進む。
ステップ（１２）では、余剰帯域を算出する。
ステップ（１３）では、余剰帯域が０であるか又は全回線の分配帯域がｍ段分配の結果の分配帯域であるか（ＤＢｉｊｍ＝ＤＢｉｊ（ｍ−１））を識別する。ステップ（１３）の条件を満たす場合にはステップ（１６）に進み、満たさない場合にはステップ（１４）に進む。
【０２０６】
ステップ（１４）では、全回線が分配完了であれば終了とみなす。ステップ（１３），（１４）で終了とみなさない場合には、ステップ（１５）でｍに１を加算してそれを更新しステップ（４）に進む。
ステップ（１６）では、余剰帯域ＳＰＢが全体帯域Ｅij.ＤＡＢから全回線への分配帯域ＤＢｉｊの総和を差し引いた値よりも大きければステップ（１７）に進み、そうでなければ終了する。
【０２０７】
ステップ（１７）では、各回線のＡＲＭｉｊの中でフレーム単位で表される帯域を分配帯域ＤＢｉｊｍに加え、ＡＲＭｉｊの中でＤＢｉｊｍに加えた帯域をＡＲＭｉｊから減らしてステップ（４）に進む。
この実施例では、実施例１６に比べて構成要素が少なくなる効果がある。
【０２０８】
（実施例１８）
本発明の帯域分配装置の実施例について図４４を参照して説明する。図４４はこの実施例の残余分配のフローチャートである。
この実施例は、前述の実施例４の変形例である。この実施例では、分配手段２０が用いる設定値及び分配帯域調整手段３０が用いる設定値が実施例４と異なっている。
【０２０９】
この実施例における残余分配の動作は図４４に示す通りである。実施例４との違いは、図４４のステップ（１）に示されている。すなわち、所定の帯域比率を表す値として、多段分配で用いる値（Ｐi.ＡＳＢ）とは異なる（Ｐi.ＲＡＳＢ）を用いている。この違いの効果は次の通りである。
例えば、分配手段２０で用いる設定値が３２４１２セルと３２４１１セルである場合を想定する。このような場合、この実施例では、ほぼ１：１とみなすことができるため、分配帯域調整手段３０は値を丸めて１：１の帯域を用いる。
【０２１０】
従って、残余帯域積算力ウンタを利用する場合に、分配帯域調整手段３０の残余帯域積算力ウンタのカウンタ長を短くする効果がある。また、テーブルを用いて分配する場合には、テーブルに公約数が無い値を割り当ててある場合であっても、少ない帯域設定周期で公平な分配が可能になる。
（実施例１９）
本発明の帯域分配装置の実施例について図４５及び図４６を参照して説明する。図４５，図４６はこの実施例の残余分配のフローチャートである。
【０２１１】
この実施例は、前述の実施例８の変形例である。残余分配の動作は図４５に示す通りである。また、次の表２に示すような分配テーブル（設定表）を利用する。
【表２】
0003710427.tif 000003
この実施例と実施例８との違いは、回線毎のパラメータに応じて定められた分配テーブルを利用して残余帯域を順次に再分配する点にある。すなわち、図４５における帯域の分配式の内容及び分配テーブルの内容に特徴がある。
【０２１２】
この実施例の分配テーブルにおいては、所定の帯域分配比率に対応して複数フレームに相当する値を回線毎に割り当てる代わりに、所定の帯域分配比率に対応した出現頻度で各回線番号が現れるように定めてある。
この分配テーブルを用いて、図４５のステップ（３）では、複数フレームに相当する設定値の代わりに、フレーム単位で帯域を分配する。その代わり、所定の帯域分配比率に応じた回数、フレームを分配する。このような分配方法であるため、実施例８のように分配しかけの回線が発生することはない。そのため処理が簡略化されている。
【０２１３】
図４５のステップ（１）では、残余帯域積算値の総和が０以外であるか判別し、０以外であればステップ（２）に進み、０であればこの処理を終了する。
ステップ（２）では、ＲＭＢｊが０以外か判別し、０以外であればステップ（３）に進み、０であればこの処理を終了する。
ステップ（３）では、この処理によって先行するタイミングで帯域を分配した回線の次に位置する回線に（ｍｉｎ（ＲＭＢｊ，分配テーブルの設定値））で帯域を分配しステップ（２）に進む。
【０２１４】
この実施例では、実施例８のように分配テーブルに示された設定値分まとめて再分配する代わりに、再分配対象回線を順次代えながら１セルずつ分配する。
分配テーブルの設定値が回線Ａ：２，回線Ｂ：３，回線Ｃ４の場合を想定し、残余帯域が帯域分配周期毎に１セルである場合を仮定するして再分配すると、次のような違いが生じる。
【０２１５】
実施例８：ＡＡＢＢＢＣＣＣＣＡＡＢＢＢＣＣＣＣＡＡＢＢＢＣＣＣＣ・・・
本実施例：ＡＢＣＡＢＣＢＣＣＡＢＣＡＢＣＢＣＣＡＢＣＡＢＣＢＣＣ・・・
ここで、回線Ｂの残余帯域の再分配を受けることが望ましいセルが以下の１の帯域分配周期で発生し、０の周期で発生しないと仮定する。
【０２１６】
：１００１００１００・・・
この場合、実施例８では回線Ｂに対して２セルしか分配されないがこの実施例では３セル分配できる。
また、回線Ｃの場合に以下の内容であると仮定する。
：０００１０１０１０１・・・
この場合、実施例８では、回線Ｃに２セル分配したところで残余帯域で分配するセルがなくなり再分配をスキップして回線Ａへ分配するため、２セル分が不必要に少なく分配されることになる。
【０２１７】
この実施例では、仮に残余帯域で分配するセルがなくなり再分配をスキップしたとしても、１セルに過ぎないため影響が少ない。このようにこの実施例は再分配される帯域分配周期が分散しているので、バースト的な残余帯域の再分配を避ける効果がある。更に、入力周期や、実装上発生し得る帯域分配装置に入力する回線の所要帯域が揺らいだりしたために、再分配されるはずの帯域分配周期で再分配が不要と認識されて再分配を受けない可能性と再分配を受けない帯域が軽減する効果がある。
【０２１８】
なお、図４６は残余分配の動作に関する変形例である。
【０２１９】
【発明の効果】
以上のように本発明によれば、演算の際に生じる端数の影響を抑制し、割当可能な共用帯域を有効かつ公平に分配できる。
【図面の簡単な説明】
【図１】実施例１の帯域分配装置の構成を示すブロック図である。
【図２】実施例３の帯域分配装置の構成を示すブロック図である。
【図３】実施例４の帯域分配装置の構成を示すブロック図である。
【図４】実施例１５の帯域分配装置の構成を示すブロック図である。
【図５】実施例１６の帯域分配装置の構成を示すブロック図である。
【図６】実施例１の残余分配のフローチャート（１）である。
【図７】実施例１の残余分配のフローチャート（２）である。
【図８】実施例１の残余分配のフローチャート（３）である。
【図９】実施例１の残余分配のフローチャート（４）である。
【図１０】実施例１の残余分配のフローチャート（５）である。
【図１１】実施例１の残余分配のフローチャート（６）である。
【図１２】実施例２の残余分配のフローチャート（１）である。
【図１３】実施例２の残余分配のフローチャート（２）である。
【図１４】実施例２の残余分配のフローチャート（３）である。
【図１５】実施例２の残余分配のフローチャート（４）である。
【図１６】実施例２の残余分配のフローチャート（５）である。
【図１７】実施例２の残余分配のフローチャート（６）である。
【図１８】実施例３の残余分配のフローチャート（１）である。
【図１９】実施例３の残余分配のフローチャート（２）である。
【図２０】実施例３の残余分配のフローチャート（３）である。
【図２１】実施例３の残余分配のフローチャート（４）である。
【図２２】実施例３の残余分配のフローチャート（５）である。
【図２３】実施例３の残余分配のフローチャート（６）である。
【図２４】実施例４の多段分配のフローチャートである。
【図２５】実施例４の残余分配のフローチャートである。
【図２６】実施例５の多段分配のフローチャートである。
【図２７】実施例５の残余分配のフローチャートである。
【図２８】実施例６の残余分配のフローチャートである。
【図２９】実施例７の残余分配のフローチャートである。
【図３０】実施例８の多段分配のフローチャート（１）である。
【図３１】実施例８の残余分配のフローチャート（１）である。
【図３２】実施例８の多段分配のフローチャート（２）である。
【図３３】実施例８の残余分配のフローチャート（２）である。
【図３４】実施例９の残余分配のフローチャートである。
【図３５】実施例１０の残余分配のフローチャートである。
【図３６】実施例１１の残余分配のフローチャート（１）である。
【図３７】実施例１１の残余分配のフローチャート（２）である。
【図３８】実施例１２の残余分配のフローチャートである。
【図３９】実施例１３の残余分配のフローチャートである。
【図４０】実施例１４の残余分配のフローチャートである。
【図４１】実施例１５の多段分配のフローチャートである。
【図４２】実施例１６の多段分配のフローチャートである。
【図４３】実施例１７の多段分配のフローチャートである。
【図４４】実施例１８の残余分配のフローチャートである。
【図４５】実施例１９の残余分配のフローチャート（１）である。
【図４６】実施例１９の残余分配のフローチャート（２）である。
【符号の説明】
１０  帯域分配装置
２０  分配手段
３０  分配帯域調整手段
３１  加算手段
３２  残余帯域積算カウンタ
３３  再分配手段
３４  減算手段
４０  設定保持手段
４５  所要帯域識別手段
５０  分配帯域回収手段
６０  分配段端数分配手段
【図１】
0003710427.tif 000004
【図２】
0003710427.tif 000005
【図３】
0003710427.tif 000006
【図４】
0003710427.tif 000007
【図５】
0003710427.tif 000008
【図６】
0003710427.tif 000009
【図７】
0003710427.tif 000010
【図８】
0003710427.tif 000011
【図９】
0003710427.tif 000012
【図１０】
0003710427.tif 000013
【図１１】
0003710427.tif 000014
【図１２】
0003710427.tif 000015
【図１３】
0003710427.tif 000016
【図１４】
0003710427.tif 000017
【図１５】
0003710427.tif 000018
【図１６】
0003710427.tif 000019
【図１７】
0003710427.tif 000020
【図１８】
0003710427.tif 000021
【図１９】
0003710427.tif 000022
【図２０】
0003710427.tif 000023
【図２１】
0003710427.tif 000024
【図２２】
0003710427.tif 000025
【図２３】
0003710427.tif 000026
【図２４】
0003710427.tif 000027
【図２５】
0003710427.tif 000028
【図２６】
0003710427.tif 000029
【図２７】
0003710427.tif 000030
【図２８】
0003710427.tif 000031
【図２９】
0003710427.tif 000032
【図３０】
0003710427.tif 000033
【図３１】
0003710427.tif 000034
【図３２】
0003710427.tif 000035
【図３３】
0003710427.tif 000036
【図３４】
0003710427.tif 000037
【図３５】
0003710427.tif 000038
【図３６】
0003710427.tif 000039
【図３７】
0003710427.tif 000040
【図３８】
0003710427.tif 000041
【図３９】
0003710427.tif 000042
【図４０】
0003710427.tif 000043
【図４１】
0003710427.tif 000044
【図４２】
0003710427.tif 000045
【図４３】
0003710427.tif 000046
【図４４】
0003710427.tif 000047
【図４５】
0003710427.tif 000048
【図４６】
0003710427.tif 000049