(57)【要約】    【課題】  バッファの使用量を少なくし、かつユーザ間の公平利用を実現する。    【解決手段】  ＦＩＦＯ１１に到着したフレームごとにユーザのユーザ番号等を検知する検知手段１２を設け、ユーザごとの重みに応じてＦＩＦＯ１１の出力権利バイト数を割り当てる割当手段１３を設け、実際利用バイト数を計測する計測手段１４を設け、出力権利バイト数と実際利用バイト数との差分値を算出する算出手段１５を設け、ＦＩＦＯ１１におけるユーザごとの蓄積フレームの有無を検出する検出手段１６を設け、差分値を重みで除した除算値を各ユーザごとに算出して、蓄積フレームを有するユーザのうちで除算値が小さい順にユーザを特定する特定手段１７を設け、ＦＩＦＯ１１に廃棄閾値以上となるフレームが到着したとき、蓄積フレームを有するユーザのうちで順次除算値が小さいユーザ順にフレームを廃棄する廃棄手段１８を設ける。【選択図】        図１
2005027256.tif 000002
【特許請求の範囲】
【請求項１】
可変長のデータ塊をＦＩＦＯ型スイッチで帯域制御するＦＩＦＯ型スイッチの帯域制御方式において、ＦＩＦＯに到着したデータ塊ごとにユーザの識別情報およびデータ塊量を検知する検知手段と、ユーザごとに定められた重みに応じて上記ＦＩＦＯの出力権利量を割り当てる割当手段と、ユーザごとの上記ＦＩＦＯの実際利用量を計測する計測手段と、上記出力権利量と上記実際利用量との差分値を算出する算出手段と、上記ＦＩＦＯにおけるユーザごとの蓄積データ塊の有無を検出する検出手段と、上記差分値を上記重みで除した除算値を各ユーザごとに算出して、上記ＦＩＦＯに上記蓄積データ塊を有するユーザのうちで上記除算値が最小である最大利用ユーザを特定する特定手段と、上記ＦＩＦＯに廃棄閾値以上となる上記データ塊が到着したとき、上記最大利用ユーザの上記データ塊を廃棄する廃棄手段とを具備することを特徴とするＦＩＦＯ型スイッチの帯域制御方式。
【請求項２】
上記特定手段が、上記ＦＩＦＯに上記蓄積データ塊を有するユーザのうちで上記除算値が小さい順にユーザを特定し、上記廃棄手段が、上記ＦＩＦＯに上記廃棄閾値以上となる上記データ塊が到着したとき、廃棄するデータ塊量の合計が到着データ塊量よりも大きくなるまで、上記特定手段が特定したユーザ順に上記データ塊を廃棄することを特徴とする請求項１に記載のＦＩＦＯ型スイッチの帯域制御方式。
【請求項３】
上記データ塊が廃棄されたときに上記ＦＩＦＯに収容された上記データ塊の単一ＦＩＦＯポインタ値を変更する再構成手段を有することを特徴とする請求項１または２に記載のＦＩＦＯ型スイッチの帯域制御方式。
【請求項４】
上記データ塊が廃棄されたときに上記ＦＩＦＯに収容された上記データ塊の個別ＦＩＦＯポインタ値を変更する再構成手段を有することを特徴とする請求項１または２に記載のＦＩＦＯ型スイッチの帯域制御方式。
【請求項５】
上記データ塊が廃棄されたときに上記ＦＩＦＯに収容された上記データ塊の単一ＦＩＦＯポインタ値および個別ＦＩＦＯポインタ値を変更する再構成手段を有することを特徴とする請求項１または２に記載のＦＩＦＯ型スイッチの帯域制御方式。
【請求項６】
上記データ塊がフレームであることを特徴とする請求項１〜５のいずれかに記載のＦＩＦＯ型スイッチの帯域制御方式。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はイーサネット(登録商標)（Ethernet(登録商標)）フレーム、ＩＰ（Internet Protocol）パケット等の可変長のデータ塊をＦＩＦＯ型スイッチで帯域制御するＦＩＦＯ型スイッチの帯域制御方式に関するものである。
【背景技術】
【０００２】
インターネットの急速な普及に伴い、やり取りされるデータ塊は可変長のＩＰパケットおよびそれを格納し転送する可変長のイーサネットフレームが主になっている。
【０００３】
図６はＩＰ技術、イーサネット技術をベースにした通信サービスの全体構成を示す図である。図に示すように、ユーザの通信端末１にＤＳＵ（Digital Service Unit）等の回線接続装置２が接続され、回線接続装置２にアクセス装置３が接続され、複数のアクセス装置３に集約スイッチ（イーサネットスイッチ）４が接続され、集約スイッチ４にコアスイッチ（ＩＰスイッチ）５が接続されている。
【０００４】
これまでのインターネットサービスは、Web閲覧、電子メール等が主に利用されているサービスであり、そのデータ（トラヒック）量は比較的少ない。一方、昨今、ＡＤＳＬ、ＦＴＴＨ（Fiber To The Home）等の普及により、動画像等の大容量のデータ（コンテンツ）がやり取りされるようになっている。このような大容量のデータは一定時間回線に対して大きな負荷をかけるため、同一伝送路に収容された他のユーザのデータの通信を圧迫する。この状況を回避するためには、各ユーザに公平なパケット送出権利を与えることが必要である。よって、これらのデータを収容するスイッチでは、ユーザごとに帯域制御を行なう機能を具備しなければならない。そして、ユーザごとに公平な帯域制御を行なう帯域制御方式としてはＷＲＲ（Weighted Round Robin）方式があり、このＷＲＲ方式においては、ユーザごとにバッファを用意し、バッファに蓄積されたフレームを一定バイト（Byte）数ごとに周期的に読み出しを行なう制御を行なう。
【０００５】
これに対して、スイッチング方式としてはＦＩＦＯ方式が一般的に用いられている。図７は従来のＦＩＦＯ型スイッチの帯域制御方式による読出制御のモデル例を示す図である。なお、ＦＩＦＯ（キュー）内のユーザ識別子は、ＶＬＡＮ、ソースＭＡＣアドレスなど帯域制御を行なう単位であれば何でもかまわないが、ここでは便宜上ＶＬＡＮ単位に帯域制御を行なう例をとる。そして、従来のＦＩＦＯ型スイッチの帯域制御方式では、複数ＶＬＡＮを同一ＦＩＦＯに収納し、ＦＩＦＯに収納されたフレームは必ず出力ポートに出力される。また、ＦＩＦＯに廃棄閾値が設定され、ＦＩＦＯ内の滞留フレームバイト数が廃棄閾値を超過するときには、ＦＩＦＯへの入力制限をする。この入力制限はＦＩＦＯに空きができるまで、ユーザ番号（ＶＩＤ（VLAN IDentifier）値）にかかわらず到着したフレームを廃棄することにより行なう。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、ＷＲＲ方式においては、ユーザごとにバッファを用意する必要があるから、ＦＩＦＯ方式に対して数倍から数十倍のバッファを用意する必要があり、ＦＩＦＯ方式に対してコスト高になる。
【０００７】
また、ＦＩＦＯ方式においては、表１に示すように、各ユーザの出力帯域およびＦＩＦＯでの廃棄確率が各ユーザの入力帯域に比例するため、帯域の公平利用を実現できない。
【０００８】
【表１】
2005027256.tif 000003
本発明は上述の課題を解決するためになされたもので、バッファの使用量が少なく、かつユーザ間の公平利用を実現することができるＦＩＦＯ型スイッチの帯域制御方式を提供することを目的とする。
【課題を解決するための手段】
【０００９】
この目的を達成するため、本発明においては、可変長のデータ塊をＦＩＦＯ型スイッチで帯域制御するＦＩＦＯ型スイッチの帯域制御方式において、ＦＩＦＯに到着したデータ塊ごとにユーザの識別情報およびデータ塊量を検知する検知手段と、ユーザごとに定められた重みに応じて上記ＦＩＦＯの出力権利量を割り当てる割当手段と、ユーザごとの上記ＦＩＦＯの実際利用量を計測する計測手段と、上記出力権利量と上記実際利用量との差分値を算出する算出手段と、上記ＦＩＦＯにおけるユーザごとの蓄積データ塊の有無を検出する検出手段と、上記差分値を上記重みで除した除算値を各ユーザごとに算出して、上記ＦＩＦＯに上記蓄積データ塊を有するユーザのうちで上記除算値が最小である最大利用ユーザを特定する特定手段と、上記ＦＩＦＯに廃棄閾値以上となる上記データ塊が到着したとき、上記最大利用ユーザの上記データ塊を廃棄する廃棄手段とを設ける。
【００１０】
この場合、上記特定手段が、上記ＦＩＦＯに上記蓄積データ塊を有するユーザのうちで上記除算値が小さい順にユーザを特定し、上記廃棄手段が、上記ＦＩＦＯに上記廃棄閾値以上となる上記データ塊が到着したとき、廃棄するデータ塊量の合計が到着データ塊量よりも大きくなるまで、上記特定手段が特定したユーザ順に上記データ塊を廃棄するようにしてもよい。
【００１１】
これらの場合、上記データ塊が廃棄されたときに上記ＦＩＦＯに収容された上記データ塊の単一ＦＩＦＯポインタ値を変更する再構成手段を設けてもよい。
【００１２】
また、上記データ塊が廃棄されたときに上記ＦＩＦＯに収容された上記データ塊の個別ＦＩＦＯポインタ値を変更する再構成手段を設けてもよい。
【００１３】
また、上記データ塊が廃棄されたときに上記ＦＩＦＯに収容された上記データ塊の単一ＦＩＦＯポインタ値および個別ＦＩＦＯポインタ値を変更する再構成手段を設けてもよい。
【００１４】
これらの場合、上記データ塊をフレームとしてもよい。
【発明の効果】
【００１５】
本発明に係るＦＩＦＯ型スイッチの帯域制御方式においては、ユーザごとにバッファを用意する必要がないから、バッファの使用量が少なく、かつＦＩＦＯに蓄積データ塊を有するユーザのうちで除算値が最小である最大利用ユーザのデータ塊を廃棄し、またはＦＩＦＯに蓄積データ塊を有するユーザのうちで除算値が小さい順にユーザを特定し、特定したユーザ順にデータ塊を廃棄するから、ユーザ間の公平利用を実現することができる。
【００１６】
また、データ塊が廃棄されたときにＦＩＦＯに収容されたデータ塊の単一ＦＩＦＯポインタ値、個別ＦＩＦＯポインタ値を変更する再構成手段を設けたときには、ＦＩＦＯのバッファから順次出力するデータ塊の順序性、各ユーザごとのＦＩＦＯ内のデータ塊の順序性を確保することができる。
【発明を実施するための最良の形態】
【００１７】
図１は本発明に係るＦＩＦＯ型スイッチの帯域制御方式の構成を示すブロック図である。図に示すように、ＦＩＦＯ１１に到着したフレーム（データ塊）ごとにユーザを特定するユーザ番号（識別情報）およびフレームバイト数（データ塊量）を検知する検知手段１２が設けられ、ユーザごとに契約等に基づいて定められた重みに応じてＦＩＦＯ１１の出力権利バイト数（出力権利量）を割り当てる割当手段１３が設けられ、実際利用バイト数（実際利用量）を計測する計測手段１４が設けられ、出力権利バイト数と実際利用バイト数との差分値を算出する算出手段１５が設けられ、ＦＩＦＯ１１におけるユーザごとの蓄積フレーム（蓄積データ塊）の有無を検出する検出手段１６が設けられ、検出手段１６は各ユーザごとの蓄積フレームフラグ（蓄積フレームが有れば「１」、無ければ「０」）を記憶する。また、差分値を重みで除した除算値を各ユーザごとに算出して、蓄積フレームフラグが１であるユーザのうちで除算値が小さい順にユーザを特定する特定手段１７が設けられ、ＦＩＦＯ１１に滞留フレームバイト数（ＦＩＦＯ１１に収容された全フレームのバイト数の合計）が廃棄閾値以上となるバイト数のフレームが到着したとき、廃棄するフレームのバイト数の合計が到着フレームバイト数（到着したフレームのバイト数）よりも大きくなるまで、蓄積フレームフラグが１のユーザのうちで順次除算値が小さいユーザ順にフレームを廃棄する廃棄手段１８が設けられ、フレームが廃棄されたときにＦＩＦＯ１１に収容されたフレームの単一ＦＩＦＯポインタ値および個別ＦＩＦＯポインタ値（説明後述）等を変更する再構成手段１９が設けられ、割当手段１３等によりバッファ制御部２０が構成されている。
【００１８】
このＦＩＦＯ型スイッチの帯域制御方式においては、図２に示すように、検知手段１２がＦＩＦＯ１１に到着したフレームごとにユーザ番号および到着フレームバイト数を検知する。そして、バッファ制御部２０はユーザ番号、到着フレームバイト数に基づいてＦＩＦＯ１１に到着フレームを書き込む（書込制御）。この場合、割当手段１３がユーザごとに定められた重みに応じてＦＩＦＯ１１の出力権利バイト数を割り当てる。すなわち、図３に示すように、ユーザ番号が１〜３のユーザの重みがそれぞれＷ１〜Ｗ３であるとすると、ユーザ番号が１〜３のユーザの出力権利バイト数Ｘ１〜Ｘ３は重みＷ１〜Ｗ３に応じて割り当てられる。また、計測手段１４が実際利用バイト数すなわちＦＩＦＯ１１に収容された各ユーザのフレームのバイト数の合計を計測する。つぎに、算出手段１５が出力権利バイト数Ｘ１〜Ｘ３と実際利用バイト数との差分値Ｙ１〜Ｙ３を算出し、検出手段１６がＦＩＦＯ１１におけるユーザごとの蓄積フレームの有無を検出し、各ユーザごとの蓄積フレームフラグＺ１〜Ｚ３を記憶する。そして、特定手段１７が差分値Ｙ１〜Ｙ３を重みＷ１〜Ｗ３で除した除算値Ｄ１〜Ｄ３を各ユーザごとに算出して、蓄積フレームフラグＺ１〜Ｚ３が１であるユーザのうちで除算値Ｄ１〜Ｄ３が小さい順にユーザを特定する。さらに、ＦＩＦＯ１１に滞留フレームバイト数が廃棄閾値以上となるバイト数のフレームが到着したとき、廃棄手段１８が廃棄するフレームのバイト数の合計が到着フレームバイト数よりも大きくなるまで、蓄積フレームフラグＺ１〜Ｚ３が１のユーザのうちで順次除算値Ｄ１〜Ｄ３が小さいユーザ順にフレームを廃棄する（廃棄制御）。たとえば、図４(ａ)に示すように、ＦＩＦＯ１１のバッファにアドレス番号が１〜１０のフレームが収容されており、アドレス番号が１〜１０のフレームのＦＩＦＯ１１への到着順が図５(ａ)に示す順番であるとすると、ユーザ番号１〜３のユーザは蓄積フレームを有するから、蓄積フレームフラグＺ１〜Ｚ３は１であり、そして蓄積フレームフラグＺ１〜Ｚ３が１のユーザのうちで除算値Ｄ１〜Ｄ３が最小である最大利用ユーザがユーザ番号２のユーザであるとすると、廃棄手段１８はユーザ番号２のユーザの先頭フレームであるアドレス番号２のフレームを廃棄する。この場合、廃棄するアドレス番号２のフレームのバイト数が到着フレームバイト数よりも大きいときには、廃棄手段１８はアドレス番号２のフレームのみを廃棄する。なお、図５において、第１段は各フレームのアドレス番号を示し、第２段はユーザ番号を示し、第３段はＦＩＦＯ１１に収納された各フレームの次に出力されるフレームのアドレス番号である単一ＦＩＦＯポインタ値を示し、第４段はＦＩＦＯ１１に収納された各フレームの次に出力される同一ユーザのフレームのアドレス番号である個別ＦＩＦＯポインタ値を示し、各フレームのアドレス番号、単一ＦＩＦＯポインタ値、個別ＦＩＦＯポインタ値、バイト数はアドレス管理テーブルとしてＦＩＦＯ１１の記憶手段に記憶される。また、図４(ｂ)に示すように、ユーザ番号１のユーザの到着フレームがアドレス番号２としてＦＩＦＯ１１のバッファに収容されたとき、再構成手段１９は、図５(ｂ)に示すように、アドレス���号６のフレームの単一ＦＩＦＯポインタ値を４に変更し、ユーザ番号２のユーザの先頭フレームのアドレス番号を２から４に変更する。また、アドレス番号３のフレームの単一ＦＩＦＯポインタ値を２とし、アドレス番号１０のフレームの個別ＦＩＦＯポインタ値を２とする。そして、ＦＩＦＯ１１の先頭のフレームであるアドレス番号１のフレームが読み出される（読出制御）。
【００１９】
また、アドレス番号２のフレームのバイト数が到着フレームバイト数よりも小さいときには、蓄積フレームフラグＺ１〜Ｚ３が１のユーザのうちで除算値Ｄ１〜Ｄ３が次に小さいユーザがユーザ番号３のユーザであるとすると、廃棄手段１８はアドレス番号２のフレームおよびユーザ番号３のユーザの先頭フレームであるアドレス番号６のフレームを廃棄する。また、ユーザ番号１のユーザの到着フレームがアドレス番号２としてＦＩＦＯ１１のバッファに収容されたとき、再構成手段１９は、図５(ｃ)に示すように、アドレス番号１のフレームの単一ＦＩＦＯポインタ値を４に変更し、ユーザ番号２のユーザの先頭フレームのアドレス番号を２から４に変更し、ユーザ番号３のユーザの先頭フレームのアドレス番号を６から３に変更する。また、アドレス番号３のフレームの単一ＦＩＦＯポインタ値を２とし、アドレス番号１０のフレームの個別ＦＩＦＯポインタ値を２とする。
【００２０】
以下、同様にして、廃棄手段１８は、廃棄するフレームのバイト数の合計が到着フレームバイト数よりも大きくなるまで、蓄積フレームフラグが１のユーザのうちで順次除算値が小さいユーザ順にフレームを廃棄する。
【００２１】
このようなＦＩＦＯ型スイッチの帯域制御方式においては、ユーザごとにバッファを用意する必要がないから、バッファの使用量が少ないので、コストが安価になる。また、輻輳が発生した場合、最も利用率の高いユーザのフレームを廃棄し、または利用率が高いユーザ順にフレームを廃棄するから、表２に示すように、帯域の公平利用を実現できる。また、再構成手段１９がフレームが廃棄されたときにＦＩＦＯ１１に収容されたフレームの単一ＦＩＦＯポインタ値、個別ＦＩＦＯポインタ値を変更するから、ＦＩＦＯ１１内のフレームが廃棄されても、ＦＩＦＯ１１のバッファから順次出力するフレームの順序性および各ユーザごとのＦＩＦＯ１１内のフレームの順序性を確保することができる。
【００２２】
【表２】
2005027256.tif 000004
なお、各ユーザの最低保証帯域を表す重みに従って出力権利バイト数を一定周期ごとにカウントアップし、ＦＩＦＯ１１にフレームが到着したとき、到着したフレームのユーザの出力権利バイト数を到着フレームのバイト数だけカウントダウンし、またフレームが廃棄されたときには、廃棄されたフレームのユーザの出力権利バイト数を廃棄フレームのバイト数だけカウントアップしてもよい。この場合、出力権利バイト数の累積値はバースト許容値を意味するから、出力権利バイト数の上限値を設ける必要がある。そして、出力権利バイト数を一定周期ごとにカウントアップする手段が割当手段に相当し、到着フレームのバイト数、廃棄フレームのバイト数を計測する手段が計測手段に相当し、到着したフレームのユーザの出力権利バイト数を到着フレームのバイト数だけカウントダウンし、また廃棄されたフレームのユーザの出力権利バイト数を廃棄フレームのバイト数だけカウントアップする手段が算出手段に相当し、出力権利バイト数が差分値に相当する。
【００２３】
また、上述実施の形態においては、可変長のデータ塊がフレームである場合について説明したが、他の可変長のデータ塊の場合にも本発明を適用できることは明らかである。
【産業上の利用可能性】
【００２４】
本発明は、図６に示した集約スイッチ４、コアスイッチ５を始め、ＩＰ技術、イーサネット技術等の可変長のデータ塊をＦＩＦＯ型スイッチで帯域制御するＦＩＦＯ型スイッチの帯域制御方式に適用可能である。
【図面の簡単な説明】
【００２５】
【図１】本発明に係るＦＩＦＯ型スイッチの帯域制御方式の構成を示すブロック図である。
【図２】図１に示したＦＩＦＯ型スイッチの帯域制御方式の動作説明図である。
【図３】図１に示したＦＩＦＯ型スイッチの帯域制御方式の動作説明図である。
【図４】図１に示したＦＩＦＯ型スイッチの帯域制御方式の動作説明図である。
【図５】図１に示したＦＩＦＯ型スイッチの帯域制御方式の動作説明図である。
【図６】ＩＰ技術、イーサネット技術をベースにした通信サービスの全体構成を示す図である。
【図７】従来のＦＩＦＯ型スイッチの帯域制御方式による読出制御のモデル例を示す図である。
【符号の説明】
【００２６】
１１…ＦＩＦＯ
１２…検知手段
１３…割当手段
１４…計測手段
１５…算出手段
１６…検出手段
１７…特定手段
１８…廃棄手段
１９…再構成手段
【図１】
2005027256.tif 000005
【図２】
2005027256.tif 000006
【図３】
2005027256.tif 000007
【図４】
2005027256.tif 000008
【図５】
2005027256.tif 000009
【図６】
2005027256.tif 000010
【図７】
2005027256.tif 000011