(57)【要約】【課題】各コネクションや各フローに対する帯域の割り当てをユーザごとに細かに行う。【解決手段】ｎ個の入力手段とｍ個の出力ポートの間の各コネクションの帯域割当量に応じたｎ×ｍのウエイトマトリクスに従い、かつ各コネクションごとにパケットが存在するか否かを検知したｎ×ｍのリクエストマトリクスに基づいて、各入力ポートと各出力ポートが競合しないようにコネクションに帯域を１タイムスロットごとに割り当てる。【選択図】　　　　図７
2004023769.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の入力ポートの各々ごとに設けられたｎ個の入力手段と、
前記ｎ個の入力手段を介して入力されたパケットをｍ個の出力ポートの内の宛て先出力ポートにパケット交換するスイッチ手段と、
前記ｎ個の入力手段のパケットスケジューリングと前記スイッチ手段のスイッチング制御を行うスイッチコントロール手段と、
前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの帯域割当量をｎ×ｍのウェイトマトリクスとして記憶する記憶手段とを備え、
前記ｎ個の入力手段の各々は、
当該入力ポートを介して入力されたパケットを同じ大きさに分割し、前記ｍ個の出力ポートの各々ごとに分配するパケット分割分配手段と、
前記パケット分割分配手段により出力ポートごとに分配されたパケットをそれぞれ記憶するｍ個の出力ポート別記憶手段と、
前記出力ポート別記憶手段から出力されるパケットを多重し、前記スイッチ手段に転送する入力パケット多重手段とを備え、
前記スイッチコントロール手段は、
前記出力ポート別記憶手段にパケットが存在するか否かを前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションごと、及び１タイムスロットごとに検知し、検知した結果をｎ×ｍのリクエストマトリクスとして前記記憶手段に格納するパケット検知手段と、
前記記憶手段に記憶されたウエイトマトリクスに従い、かつリクエストマトリクスに基づいて、各入力ポートと各出力ポートが競合しないように各コネクションに帯域を１タイムスロットごとに割り当てて前記ｎ個の入力手段のパケットスケジューリングと前記スイッチ手段のスイッチング制御を行うことによりコネクション毎の帯域制御を行う帯域割当制御手段とを、
備えた帯域制御装置。
【請求項２】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの最低帯域を基に、一定時間における最低保証パケット量を計算してその結果をｎ×ｍのウエイトマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段は、前記変換されたウエイトマトリクスを基に各コネクションに最低保証パケット量を割り当てることによりコネクション毎の最低帯域保証制御を行うよう構成された請求項１に記載の帯域制御装置。
【請求項３】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションのピーク帯域を基に、一定時間における各コネクションのピークパケット量を計算してその結果をｎ×ｍのピークマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段は前記ピークマトリクスを基に、ピーク帯域に達したコネクションに対し帯域を割り当てないことによりコネクション毎のピーク帯域制御を行うことを特徴とする請求項１又は２に記載の帯域制御装置。
【請求項４】
前記帯域割当制御手段は、前記最低帯域を基に変換されたウエイトマトリクスを基にコネクション毎の最低帯域保証制御を行って、あるコネクションに最低保証パケット量を割り当てた後、前記あるコネクションの出力ポートが開いているときには他のコネクションに最低保証パケット量を割り当てていないときにも前記あるコネクションに帯域を割り当てることにより、余剰帯域のスループットを上げるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項５】
前記帯域割当制御手段は、前記最低帯域を基に変換されたウエイトマトリクスを基にコネクション毎の最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後、前記ウエイトマトリクスの各要素を要素数で重み付けすることにより余剰帯域を各コネクションに公平に割り当てるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項６】
前記帯域割当制御手段は、前記最低帯域を基に変換されたウエイトマトリクスを基にコネクション毎の最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を元のウエイトマトリクスで初期化することにより、余剰帯域を各コネクションに最低帯域の比で割り当てるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項７】
前記帯域割当制御手段は、前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれコネクション毎の最低帯域保証制御、ピーク帯域制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスで初期化することにより、余剰帯域を各コネクションにピーク帯域の比で割り当てるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項８】
前記帯域割当制御手段は、前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれコネクション毎の最低帯域保証制御、ピーク帯域制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスと前記ウエイトマトリクスの差で初期化することにより、余剰帯域を各コネクションにピーク帯域と最低帯域の差の比で割り当てるよう構成された請求項３に記載の帯域制御装置。
【請求項９】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの余剰帯域の割当比を基に、ｎ×ｍの余剰帯域割当マトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段は、前記最低帯域を基に変換されたウエイトマトリクスを基に最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記余剰帯域割当用マトリクスで初期化することにより、余剰帯域を外部から設定した余剰帯域の割当比で割り当てるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項１０】
前記帯域割当制御手段は、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの最低帯域を基に生成されたウエイトマトリクスを、各出力ポートごとの総割当が同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各出力ポートの総スループットが公平になるように割り当てるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項１１】
前記帯域割当制御手段は、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの最低帯域を基に生成されたウエイトマトリクスを、各入力ポートごとの総割当を同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各入力ポートの総スループットが公平になるように割り当てるよう構成された請求項２又は３に記載の帯域制御装置。
【請求項１２】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの優先順位を基に、ｎ×ｍの優先度マトリクスを前記記憶手段に格納し、
前記帯域割当制御手段は、前記優先度マトリクスを参照して、優先順位が高いコネクションを優先して割り当てるよう構成された請求項１から１１のいずれか１つに記載の帯域制御装置。
【請求項１３】
前記帯域割当制御手段は、前記ウエイトマトリクスを基に、それぞれ最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後に、請求項１２記載の優先割当を行うことを特徴とする帯域制御装置。
【請求項１４】
前記ｍ個の出力ポート別記憶手段に、それぞれ記憶されている各パケットの量及び／又は数を監視して、一定の閾値を超過した出力ポート別記憶手段を前記帯域割当制御手段に報告するパケット検知手段を更に備え、
前記帯域割当制御手段は、前記閾値を超過した出力ポート別記憶手段と対応するコネクションを優先するよう構成された請求項１から１３のいずれか１つに記載の帯域制御装置。
【請求項１５】
前記帯域割当制御手段は、前記ウエイトマトリクスを基に、それぞれ各コネクションの最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後に、請求項１４に記載の優先割当を行うよう構成された帯域制御装置。
【請求項１６】
ｎ個の入力ポートの各々ごとに設けられたｎ個の入力手段と、
前記ｎ個の入力手段を介して入力されたパケットをｍ個の出力ポートの内の宛て先出力ポートにパケット交換するスイッチ手段と、
前記ｎ個の入力手段のパケットスケジューリングと前記スイッチ手段のスイッチング制御を行うスイッチコントロール手段と、
前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの帯域割当量をｎ×ｍのウェイトマトリクスとして記憶する記憶手段とを備え、
前記ｎ個の入力手段の各々は、
当該入力ポートを介して入力されたパケットを同じ大きさに分割し、フローごとに分配するパケット分割分配手段と、
前記パケット分割分配手段によりフローごとに分配されたパケットをそれぞれ記憶する複数のフロー別記憶手段と、
前記フロー別記憶手段から出力されるパケットを多重し、前記スイッチ手段に転送する入力パケット多重手段と、
前記入力ポートと前記出力ポート間のコネクションと各フローとの対応関係が格納されているフロー対応テーブルと、
コネクションが割り当てられた場合に、前記フロー対応テーブルを参照して割当コネクションに対応するフローを決定して当該フロー別記憶手段から送信する入力コントロール手段とを備え、
前記スイッチコントロール手段は、
前記フロー別記憶手段にパケットが存在するかを１タイムスロットごとに検知し、検知した結果をコネクションごとにｎ×ｍのリクエストマトリクスとして前記記憶手段に格納するパケット検知手段と、
前記記憶手段に記憶されたウエイトマトリクスに従い、かつリクエストマトリクスに基づいて、各入力ポートと各出力ポートが競合しないように前記コネクションに１タイムスロットごとに割り当てて、前記入力コントロール手段に指示するとともに前記スイッチ手段のスイッチング制御を行うことによりフロー毎の帯域制御を行う帯域割当制御手段とを、
備えた帯域制御装置。
【請求項１７】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定されたフローごとの最低帯域を基に、一定時間における最低保証パケット量を計算してその結果をコネクションごとにまとめてｎ×ｍのウエイトマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段は、前記変換されたウエイトマトリクスを基に各コネクションに最低保証パケット量を割り当て、前記入力コントロール手段に指示することによりフロー毎の最低帯域保証制御を行うよう構成された請求項１６に記載の帯域制御装置。
【請求項１８】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定されたフローごとのピーク帯域を基に、一定時間における各コネクションのピークパケット量を計算してその結果をｎ×ｍのピークマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段は前記ピークマトリクスを基に、ピーク帯域に達したコネクションに対し帯域を割り当てないように前記入力コントロール手段に指示することにより、フロー毎のピーク帯域制御を行うよう構成された請求項１６又は１７に記載の帯域制御装置。
【請求項１９】
前記最低帯域を基に変換されたウエイトマトリクスを基にフロー毎の最低帯域保証制御を行って、あるフローに最低保証パケット量を割り当てた後、前記入力コントロール手段は、前記あるフローの出力ポートが空いているときには他のフローに最低保証パケット量を割り当てていないときにも前記あるフローに帯域を割り当てることにより、余剰帯域のスループットを上げるよう構成された請求項１７又は１８に記載の帯域制御装置。
【請求項２０】
前記最低帯域を基に変換されたウエイトマトリクスを基にフロー毎の最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後、前記ウエイトマトリクスの各要素を要素数で重み付けすることにより、余剰帯域を各フローに公平に割り当てるよう構成された請求項１７又は１８に記載の帯域制御装置。
【請求項２１】
前記最低帯域を基に変換されたウエイトマトリクスを基にフロー毎の最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を元のウエイトマトリクスで初期化することにより、余剰帯域を各フローに最低帯域の比で割り当てるよう構成された請求項１７又は１８に記載の帯域制御装置。
【請求項２２】
前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれフロー毎の最低帯域保証制御、ピーク帯域制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスで初期化することにより、余剰帯域を各フローにピーク帯域の比で割り当てるよう構成された請求項１６又は１７に記載の帯域制御装置。
【請求項２３】
前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれフロー毎の最低帯域保証制御、ピーク帯域制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスと前記ウエイトマトリクスの差で初期化することにより、余剰帯域を各フローにピーク帯域と最低帯域の差の比で割り当てるよう構成された請求項１８に記載の帯域制御装置。
【請求項２４】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定された各フローの余剰帯域の割当比を基に、コネクションごとにまとめてｎ×ｍの余剰帯域割当マトリクスとして前記記憶手段に格納し、
前記最低帯域を基に変換されたウエイトマトリクスを基に最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記余剰帯域割当用マトリクスで初期化することにより、余剰帯域を外部から設定した余剰帯域の割当比で割り当てるよう構成された請求項１７又は１８に記載の帯域制御装置。
【請求項２５】
外部インタフェース手段を通して設定された各フローの最低帯域を基に生成されたウエイトマトリクスを、各出力ポートごとの総割当が同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各出力ポートの総スループットが公平になるように割り当てるよう構成された請求項１７又は１８に記載の帯域制御装置。
【請求項２６】
外部インタフェース手段を通して設定された各フローの最低帯域を基に生成されたウエイトマトリクスを、各入力ポートごとの総割当を同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各入力ポートの総スループットが公平になるように割り当てるよう構成された請求項１７又は１８に記載の帯域制御装置。
【請求項２７】
前記スイッチコントロール手段はさらに、外部インタフェース手段を通して設定された各フローの優先順位を基に、ｎ×ｍの優先度マトリクスを前記記憶手段に格納し、
前記優先度マトリクスを参照して、優先順位が高いフローを優先して割り当てるよう構成された請求項１６から２６のいずれか１つに記載の帯域制御装置。
【請求項２８】
前記ウエイトマトリクスを基に、それぞれ最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後に、請求項２７に記載の優先割当を行うことを特徴とする帯域制御装置。
【請求項２９】
前記ｍ個のフロー別記憶手段に、それぞれ記憶されている各パケットの量及び／又は数を監視して、一定の閾値を超過したフロー別記憶手段を前記帯域割当制御手段に報告するパケット検知手段を更に備え、
前記閾値を超過したフロー別記憶手段と対応するフローを優先するよう構成された請求項１６から２８のいずれか１つに記載の帯域制御装置。
【請求項３０】
前記ウエイトマトリクスを基に、それぞれ各フローの最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後に、請求項２９に記載の優先割当を行うよう構成された帯域制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信網で収容される各コネクション及び各フローの帯域制御及び優先制御を行う帯域制御装置に関する。
【０００２】
【従来の技術】
高速通信の普及につれて、従来の通信に比べて、各ユーザ個別の通信サービスを行う必要がきている。入力バッファ型のスイッチングハブは、出力バッファ型のスイッチングハブに比べ、バッファスピードが低くて済み、その性能に対して、最も実装しやすいことで知られる。しかしながら、入力バッファ型では、出力ポートでパケットがブロックされ、スループットが低下するという大きな欠点がある。そこで、入力ポートにおけるバッファを出力ポートごとに物理的もしくは論理的に分割することでスループットの低下を防ぐことができる。
【０００３】
このような入力バッファ型のパケットスイッチ３の例を図２８に示す。パケットスイッチ３は入力ポート＃０〜＃３ごとに、接続される出力ポート＃０〜＃３先によって分割した出力ポート用バッファ３１と、タイムスロットごとにスイッチングするスイッチコントロール部３３と、同一タイムスロット内で、同じ入力ポート＃０〜＃３から別の出力ポート＃０〜＃３への接続、又は別の入力ポート＃０〜＃３から同じ出力ポート＃０〜＃３への接続を行わないようなパケットスケジューリングを行うスイッチコントロール部３３で構成される。このようなパケットスケジューリングを行う理由は　、同じ入力ポートからの接続を同一タイムスロット内で行うと、図２９で示すように、出力ポート用バッファ３１の先でパケットが衝突し、また、同じ出力ポートへの接続を同一タイムスロット内で行うと、図３０で示すようにスイッチ部３２の先でパケットが衝突を起こすからである。
【０００４】
前記のパケットスケジューリング方法については、さまざまの手法が提案されている。特開平６−２３３３３７号公報では、各入力ポートには、出力ポートの数だけＦＩＦＯ型のバッファを持つ図２８のパケットスイッチと同じ構造をもつスイッチにおいて、ｎ入力ｎ出力マルチポートシステムについてのスケジューリング方法を記している。この方法では、ｎ×ｎ対角マトリクスとパターンシーケンスマトリクスを用い、同一タイムスロット内で同じ入出力ポートを割り当てないように、それぞれのコネクションを割り当てることで、各入力ポートと各出力ポート間の割当に関して、公平なパケットスケジューリング方法を提案している。
【０００５】
【発明が解決しようとする課題】
上記の手法は、各入力ポートと各出力ポートを公平に割り当てることに関しては、高い性能を示す。しかしながら、各リンクの割り当てを、指定された重みに従って割り当てるということは考慮に入っておらず、例えばユーザＡには１Ｍｂｐｓ、ユーザＢには１．５Ｍｂｐｓのように割り当てるというような細かな帯域制御を行うということはできない。このため、ユーザの要求が多様化した現在、帯域を公平に割り当てるという機能だけでは、その要求に応えることはできない。
【０００６】
また従来は、各入力ポートと各出力ポート間のコネクション毎の制御しか行うことが、同一コネクションを用いている送信元と送信先が違う別のフローを各々別々に帯域制御するということはできなかった。
【０００７】
本発明は上記従来例の問題点に鑑み、、上記のような入力ポートと出力ポート間のコネクションに対する帯域の割り当てを、ユーザごとに細かに行うことができる帯域制御装置を提供することを目的とする。
本発明はまた、行き先ＩＰアドレスやアプリケーションなどのフロー毎の帯域制御をユーザごとに細かに行うことができる帯域制御装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
請求項１に記載の発明は上記目的を達成するために、ｎ個の入力ポートの各々ごとに設けられたｎ個の入力手段と、
前記ｎ個の入力手段を介して入力されたパケットをｍ個の出力ポートの内の宛て先出力ポートにパケット交換するスイッチ手段と、
前記ｎ個の入力手段のパケットスケジューリングと前記スイッチ手段のスイッチング制御を行うスイッチコントロール手段と、
前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの帯域割当量をｎ×ｍのウェイトマトリクスとして記憶する記憶手段とを備え、
前記ｎ個の入力手段の各々は、
当該入力ポートを介して入力されたパケットを同じ大きさに分割し、前記ｍ個の出力ポートの各々ごとに分配するパケット分割分配手段と、
前記パケット分割分配手段により出力ポートごとに分配されたパケットをそれぞれ記憶するｍ個の出力ポート別記憶手段と、
前記出力ポート別記憶手段から出力されるパケットを多重し、前記スイッチ手段に転送する入力パケット多重手段とを備え、
前記スイッチコントロール手段は、
前記出力ポート別記憶手段にパケットが存在するか否かを前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションごと、及び１タイムスロットごとに検知し、検知した結果をｎ×ｍのリクエストマトリクスとして前記記憶手段に格納するパケット検知手段と、
前記記憶手段に記憶されたウエイトマトリクスに従い、かつリクエストマトリクスに基づいて、各入力ポートと各出力ポートが競合しないように各コネクションに帯域を１タイムスロットごとに割り当てて前記ｎ個の入力手段のパケットスケジューリングと前記スイッチ手段のスイッチング制御を行うことによりコネクション毎の帯域制御を行う帯域割当制御手段とを、
備えたことを特徴とする。
請求項１に記載の発明によれば、ｎ個の入力手段とｍ個の出力ポートの間の各コネクションの帯域割当量に応じて各コネクションに帯域を１タイムスロットごとに割り当てるので、各コネクションに対する帯域の割り当てをユーザごとに細かに行うことができる。
【０００９】
請求項２に記載の発明は、請求項１に記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの最低帯域を基に、一定時間における最低保証パケット量を計算してその結果をｎ×ｍのウエイトマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段は、前記変換されたウエイトマトリクスを基に各コネクションに最低保証パケット量を割り当てることによりコネクション毎の最低帯域保証制御を行うことを特徴とする。
請求項２に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行うことができる。
【００１０】
請求項３に記載の発明は、請求項１又は２に記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションのピーク帯域を基に、一定時間における各コネクションのピークパケット量を計算し、その結果をｎ×ｍのピークマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段が前記ピークマトリクスを基に、ピーク帯域に達したコネクションに対し帯域を割り当てないことによりコネクション毎のピーク帯域制御を行うことを特徴とする。
請求項３に記載の発明によれば、コネクション毎のピーク帯域制御をユーザごとに細かに行うことができる。
【００１１】
請求項４に記載の発明は、請求項２又は３に記載の帯域制御装置において、
前記帯域割当制御手段が、前記最低帯域を基に変換されたウエイトマトリクスを基にコネクション毎の最低帯域保証制御を行って、あるコネクションに最低保証パケット量を割り当てた後、前記あるコネクションの出力ポートが開いているときには他のコネクションに最低保証パケット量を割り当てていないときにも前記あるコネクションに帯域を割り当てることにより、余剰帯域のスループットを上げる特徴とする。
請求項４に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域のスループットを上げることができる。
【００１２】
請求項５に記載の発明は、請求項２又は３に記載の帯域制御装置において、
前記帯域割当制御手段が、前記最低帯域を基に変換されたウエイトマトリクスを基にコネクション毎の最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後、前記ウエイトマトリクスの各要素を要素数で重み付けすることにより余剰帯域を各コネクションに公平に割り当てることを特徴とする。
請求項５に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各コネクションに公平に割り当てることができる。
【００１３】
請求項６に記載の発明は、請求項２又は３に記載の帯域制御装置において、
前記帯域割当制御手段が、前記最低帯域を基に変換されたウエイトマトリクスを基にコネクション毎の最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を元のウエイトマトリクスで初期化することにより、余剰帯域を各コネクションに最低帯域の比で割り当てることを特徴とする。
請求項６に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各コネクションに最低帯域の比で割り当てることができる。
【００１４】
請求項７に記載の発明は、請求項２又は３に記載の帯域制御装置において、
前記帯域割当制御手段が、前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれコネクション毎の最低帯域保証制御、ピーク帯域制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスで初期化することにより、余剰帯域を各コネクションにピーク帯域の比で割り当てることを特徴とする。
請求項７に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各コネクションにピーク帯域の比で割り当てることができる。
【００１５】
請求項８に記載の発明は、請求項３に記載の帯域制御装置において、
前記帯域割当制御手段が、前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれコネクション毎の最低帯域保証制御、ピーク帯域制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスと前記ウエイトマトリクスの差で初期化することにより、余剰帯域を各コネクションにピーク帯域と最低帯域の差の比で割り当てることを特徴とする。
請求項８に記載の発明によれば、コネクション毎の最低帯域保証制御、ピーク帯域制御をユーザごとに細かに行った後、余剰帯域を各コネクションにピーク帯域と最低帯域の差の比で割り当てることができる。
【００１６】
請求項９に記載の発明は、請求項２又は３に記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの余剰帯域の割当比を基に、ｎ×ｍの余剰帯域割当マトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段が、前記最低帯域を基に変換されたウエイトマトリクスを基に最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記余剰帯域割当用マトリクスで初期化することにより、余剰帯域を外部から設定した余剰帯域の割当比で割り当てることを特徴とする。
請求項９に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を外部から設定した余剰帯域の割当比で割り当てることができる。
【００１７】
請求項１０に記載の発明は、請求項２又は３に記載の帯域制御装置において、前記帯域割当制御手段が、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの最低帯域を基に生成されたウエイトマトリクスを、各出力ポートごとの総割当が同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各出力ポートの総スループットが公平になるように割り当てることを特徴とする。請求項１０に記載の発明によれば、各出力ポートの総スループットが公平になるように割り当てることができる。
【００１８】
請求項１１に記載の発明は、請求項２又は３に記載の帯域制御装置において、前記帯域割当制御手段が、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの最低帯域を基に生成されたウエイトマトリクスを、各入力ポートごとの総割当を同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各入力ポートの総スループットが公平になるように割り当てることを特徴とする。請求項１１に記載の発明によれば、各入力ポートの総スループットが公平になるように割り当てることができる。
【００１９】
請求項１２に記載の発明は、請求項１から１１のいずれか１つに記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定された前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの優先順位を基に、ｎ×ｍの優先度マトリクスを前記記憶手段に格納し、
前記帯域割当制御手段は、前記優先度マトリクスを参照して、優先順位が高いコネクションを優先して割り当てることを特徴とする。
請求項１２に記載の発明によれば、ユーザにより設定された優先順位が高いコネクションを優先して割り当てることができる。
【００２０】
請求項１３に記載の発明は、
前記帯域割当制御手段が、前記ウエイトマトリクスを基に、それぞれ最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後に、請求項１２に記載の優先割当を行うことを特徴とする。
請求項１３に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、ユーザにより設定された優先順位が高いコネクションを優先して割り当てることができる。
【００２１】
請求項１４に記載の発明は、請求項１から１３のいずれか１つに記載の帯域制御装置において、
前記ｍ個の出力ポート別記憶手段に、それぞれ記憶されている各パケットの量及び／又は数を監視して、一定の閾値を超過した出力ポート別記憶手段を前記帯域割当制御手段に報告するパケット検知手段を更に備え、
前記帯域割当制御手段が、前記閾値を超過した出力ポート別記憶手段と対応するコネクションを優先することを特徴とする。
請求項１４に記載の発明によれば、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するコネクションを優先することができる。
【００２２】
請求項１５に記載の発明は、
前記帯域割当制御手段が、前記ウエイトマトリクスを基に、それぞれ各コネクションの最低帯域保証制御を行って各コネクションに最低保証パケット量を割り当てた後に、請求項１４に記載の優先割当を行うことを特徴とする。
請求項１５に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するコネクションを優先することができる。
【００２３】
請求項１６に記載の発明は、
ｎ個の入力ポートの各々ごとに設けられたｎ個の入力手段と、
前記ｎ個の入力手段を介して入力されたパケットをｍ個の出力ポートの内の宛て先出力ポートにパケット交換するスイッチ手段と、
前記ｎ個の入力手段のパケットスケジューリングと前記スイッチ手段のスイッチング制御を行うスイッチコントロール手段と、
前記ｎ個の入力手段と前記ｍ個の出力ポートの間の各コネクションの帯域割当量をｎ×ｍのウェイトマトリクスとして記憶する記憶手段とを備え、
前記ｎ個の入力手段の各々は、
当該入力ポートを介して入力されたパケットを同じ大きさに分割し、フローごとに分配するパケット分割分配手段と、
前記パケット分割分配手段によりフローごとに分配されたパケットをそれぞれ記憶する複数のフロー別記憶手段と、
前記フロー別記憶手段から出力されるパケットを多重し、前記スイッチ手段に転送する入力パケット多重手段と、
前記入力ポートと前記出力ポート間のコネクションと各フローとの対応関係が格納されているフロー対応テーブルと、
コネクションが割り当てられた場合に、前記フロー対応テーブルを参照して割当コネクションに対応するフローを決定して当該フロー別記憶手段から送信する入力コントロール手段とを備え、
前記スイッチコントロール手段は、
前記フロー別記憶手段にパケットが存在するかを１タイムスロットごとに検知し、検知した結果をコネクションごとにｎ×ｍのリクエストマトリクスとして前記記憶手段に格納するパケット検知手段と、
前記記憶手段に記憶されたウエイトマトリクスに従い、かつリクエストマトリクスに基づいて、各入力ポートと各出力ポートが競合しないように前記コネクションに１タイムスロットごとに割り当てて、前記入力コントロール手段に指示するとともに前記スイッチ手段のスイッチング制御を行うことによりフロー毎の帯域制御を行う帯域割当制御手段とを、
備えたことを特徴とする。
請求項１６に記載の発明によれば、フロー毎の帯域割当量に応じて各フローに帯域を１タイムスロットごとに割り当てるので、各フローに対する帯域の割り当てをユーザごとに細かに行うことができる。
【００２４】
請求項１７に記載の発明は、請求項１６に記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定されたフローごとの最低帯域を基に、一定時間における最低保証パケット量を計算してその結果をコネクションごとにまとめてｎ×ｍのウエイトマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段が、前記変換されたウエイトマトリクスを基に各コネクションに最低保証パケット量を割り当て、前記入力コントロール手段に指示することによりフロー毎の最低帯域保証制御を行うことを特徴とする。
請求項１７に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行うことができる。
【００２５】
請求項１８に記載の発明は、請求項１６又は１７に記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定されたフローごとのピーク帯域を基に、一定時間における各コネクションのピークパケット量を計算してその結果をｎ×ｍのピークマトリクスとして前記記憶手段に格納し、
前記帯域割当制御手段が前記ピークマトリクスを基に、ピーク帯域に達したコネクションに対し帯域を割り当てないように前記入力コントロール手段に指示することにより、フロー毎のピーク帯域制御を行うことを特徴とする。
請求項１８に記載の発明によれば、フロー毎のピーク帯域制御をユーザごとに細かに行うことができる。
【００２６】
請求項１９に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
前記最低帯域を基に変換されたウエイトマトリクスを基にフロー毎の最低帯域保証制御を行って、あるフローに最低保証パケット量を割り当てた後、前記入力コントロール手段は、前記あるフローの出力ポートが空いているときには他のフローに最低保証パケット量を割り当てていないときにも前記あるフローに帯域を割り当てることにより、余剰帯域のスループットを上げる特徴とする。
請求項１９に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域のスループットを上げることができる。
【００２７】
請求項２０に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
前記最低帯域を基に変換されたウエイトマトリクスを基にフロー毎の最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後、前記ウエイトマトリクスの各要素を要素数で重み付けすることにより、余剰帯域を各フローに公平に割り当てることを特徴とする。
請求項２０に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各フローに公平に割り当てることができる。
【００２８】
請求項２１に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
前記最低帯域を基に変換されたウエイトマトリクスを基にフロー毎の最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を元のウエイトマトリクスで初期化することにより、余剰帯域を各フローに最低帯域の比で割り当てることを特徴とする。
請求項２１に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各フローに最低帯域の比で割り当てることができる。
【００２９】
請求項２２に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれフロー毎の最低帯域保証制御、ピーク帯域制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスで初期化することにより、余剰帯域を各フローにピーク帯域の比で割り当てることを特徴とする。
請求項２２に記載の発明によれば、フロー毎の最低帯域保証制御、ピーク帯域制御をユーザごとに細かに行った後、余剰帯域を各フローにピーク帯域の比で割り当てることができる。
【００３０】
請求項２３に記載の発明は、請求項１８に記載の帯域制御装置において、
前記最低帯域を基に変換されたウエイトマトリクス及びピークマトリクスを基に、それぞれフロー毎の最低帯域保証制御、ピーク帯域制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記ピークマトリクスと前記ウエイトマトリクスの差で初期化することにより、余剰帯域を各フローにピーク帯域と最低帯域の差の比で割り当てることを特徴とする。
請求項２３に記載の発明によれば、フロー毎の最低帯域保証制御、ピーク帯域制御をユーザごとに細かに行った後、余剰帯域を各フローにピーク帯域と最低帯域の差の比で割り当てることができる。
【００３１】
請求項２４に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定された各フローの余剰帯域の割当比を基に、コネクションごとにまとめてｎ×ｍの余剰帯域割当マトリクスとして前記記憶手段に格納し、
前記最低帯域を基に変換されたウエイトマトリクスを基に最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後、前記最低帯域を基に変換されたウエイトマトリクスの各要素を前記余剰帯域割当用マトリクスで初期化することにより、余剰帯域を外部から設定した余剰帯域の割当比で割り当てることを特徴とする。
請求項２４に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を外部から設定した余剰帯域の割当比で割り当てることができる。
【００３２】
請求項２５に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
外部インタフェース手段を通して設定された各フローの最低帯域を基に生成されたウエイトマトリクスを、各出力ポートごとの総割当が同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各出力ポートの総スループットが公平になるように割り当てることを特徴とする。
請求項２５に記載の発明によれば、各出力ポートの総スループットが公平になるように割り当てることができる。
【００３３】
請求項２６に記載の発明は、請求項１７又は１８に記載の帯域制御装置において、
外部インタフェース手段を通して設定された各フローの最低帯域を基に生成されたウエイトマトリクスを、各入力ポートごとの総割当を同じになるように変更し、前記変更したウエイトマトリクスにより帯域割当を行うことにより、各入力ポートの総スループットが公平になるように割り当てることを特徴とする。
請求項２６に記載の発明によれば、各入力ポートの総スループットが公平になるように割り当てることができる。
【００３４】
請求項２７に記載の発明は、請求項１６から２６のいずれか１つに記載の帯域制御装置において、
前記スイッチコントロール手段がさらに、外部インタフェース手段を通して設定された各フローの優先順位を基に、ｎ×ｍの優先度マトリクスを前記記憶手段に格納し、
前記優先度マトリクスを参照して、優先順位が高いフローを優先して割り当てることを特徴とする。
請求項２７に記載の発明によれば、優先順位が高いフローを優先して割り当てることができる。
【００３５】
請求項２８に記載の発明は、前記ウエイトマトリクスを基に、それぞれ最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後に、請求項２７に記載の優先割当を行うことを特徴とする。
請求項２８に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、優先順位が高いフローを優先して割り当てることができる。
【００３６】
請求項２９に記載の発明は、請求項１６から２８のいずれか１つに記載の帯域制御装置において、
前記ｍ個のフロー別記憶手段に、それぞれ記憶されている各パケットの量及び／又は数を監視して、一定の閾値を超過したフロー別記憶手段を前記帯域割当制御手段に報告するパケット検知手段を更に備え、
前記閾値を超過したフロー別記憶手段と対応するフローを優先することを特徴とする。
請求項２９に記載の発明によれば、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するフローを優先することができる。
【００３７】
請求項３０に記載の発明は、
前記ウエイトマトリクスを基に、それぞれ各フローの最低帯域保証制御を行って各フローに最低保証パケット量を割り当てた後に、請求項２９に記載の優先割当を行うことを特徴とする。
請求項３０に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するフローを優先することができる。
【００３８】
【発明の実施の形態】
＜第１の実施の形態＞
以下、図１〜図２０を参照して本発明の第１の実施の形態について説明する。図１は本発明の第１の実施の形態の基本アーキテクチャを示す。パケットスイッチ１は、ｎ個の入力ポート１１１〜１１ｎと、入力ポート１１１〜１１ｎに、それぞれ接続された入力手段１２１〜１２ｎと、スイッチ手段１３と、スイッチコントロール手段１４と、制御用記憶手段１５と、ｍ個の出力ポート１６１〜１６ｍを持つマルチポートスイッチである。
【００３９】
図２は各入力手段１２の詳しい構成を示す。ｋ番目（ｋは１〜ｎまでの任意の値：ｎは２以上の整数）の入力手段１２ｋは入力ポート１１ｋに入力されたパケットを出力ポート１６１〜１６ｍごとに同じ大きさに分割・分配するパケット分割・分配手段１２１と、パケット分割・分配手段１２１により出力ポート１６１〜１６ｍごとに分割・分配されたパケットをそれぞれ記憶する出力ポート用記憶手段１２２ｋ１〜１２２ｋｍと、出力ポート用記憶手段１２２ｋ１〜１２２ｋｍから出力されたパケットを多重化する出力パケット多重手段１２３ｋを有する。
【００４０】
図３にスイッチコントロール手段１４の詳しい構成を示す。スイッチコントロール手段１４は、入力手段１２１〜１２ｎのパケットの存在を検知するパケット検知手段１４１と、帯域制御を行う帯域割当制御手段１４２と、外部端末とのインタフェース手段である外部用インタフェース手段１４３により構成される。
【００４１】
帯域制御とは、帯域割当制御手段１４２が帯域周期時間（ＴＳ秒）あたり、どれくらいのタイムスロット（＝α秒とする）数を、入力ポート１１１〜１１ｎと出力ポート１６１〜１６ｍ間のコネクションに割り当てるかということである。帯域周期時間ごとに各コネクションの割当の初期化を行う。図４に示すようなそれぞれのコネクションの重み（割当ＴＳ数）を管理者が外部用インタフェース手段１４３を通して帯域割当制御手段１４２に設定すると、帯域割当制御手段１４２は入力ポート数ｎ×出力ポート数ｍのマトリクス状に重みを設定する。それぞれの重みをＭ［ｉ，ｊ］（入力ポートｉと出力ポートｊとのコネクションの重み）とすると、それぞれのコネクションの帯域周期時間あたりの割り当てられた時間は
Ｍ［ｉ，ｊ］／α×ＴＳ
となる。タイムスロットが一定時間とすると帯域周期時間が大きければ大きいほど、細かい帯域制御が可能となる。
【００４２】
図５では、指定した最低帯域をタイムスロットに変換した値をウエイトマトリクス（以下ＷＭと呼ぶ）に示したものである。横の行がある入力ポート１１に接続するリンクの割り当て帯域を表わし、縦の列がある出力ポートに接続するリンクの最低割り当て帯域を表わしている。図２において、割り当て帯域は外部からＳＮＭＰ、ＣＭＩＰなどのネットワーク管理プロトコルにより、スイッチコントロール手段１４を通して設定され、制御用記憶手段１５に各ポート間のリンクごとにタイムスロット分の重みとして格納される。
【００４３】
また現在どのキューにパケット待ちがあるかを、スイッチコントロール手段１４内のパケット検知手段がタイムスロットごとにリアルタイムに認識し、制御用記憶手段１５にリクエストマトリクス（以下ＲＭと呼ぶ）という形で、制御用記憶手段１５に保持する。図６は制御用記憶手段１５に保持しているＲＭを示したものである。ＲＭの各要素をＲ［ｉ，ｊ］（ｉは入力ポート，ｊは出力ポートのインデックスを表わす）とする。Ｒ［ｉ，ｊ］＝０は該当するキューにパケットが存在しないことを表わし、Ｒ［ｉ，ｊ］＝１は該当するキューにパケットが存在することを表わす。
【００４４】
以下のＷＭとＲＭの二つのマトリクスを基にタイムスロットごとのパケットスケジューリングアルゴリズムをフローチャートとして示したのが図７である。　以下のアルゴリズムをアルゴリズムＡとする。それぞれのコネクションに対応しているＷＭの各要素の状態を３つの状態に分ける。
「選定」…選ばれた要素
「未選定」…これから選ばれる可能性がある要素
「非選定」…これから選ばれる可能性のない要素
【００４５】
まず、ウエイトが１以上の要素をもつＷＭの要素をすべて「未選定」とし、０をもつ要素を「非選定」とする（ステップＳ１）。次いでＷＭにおける「未選定」の要素の存在のチェックを行う（ステップＳ２）。もし「未選定」の要素が存在するならば、「未選定」の要素を含む行及び列をすべて合計して最も大きい行及び列をＭａとする（ステップＳ３）。次いでＭａの中の「未選定」要素の中で最も大きいウエイトを持つ要素を選ぶ。ただし最も大きいウエイトが複数あるときは、ランダムで１つ選ぶ（ステップＳ４）。次いでその要素に対応するＲＭを参照し、パケット待ちがあるかどうかを判断する（ステップＳ５）。
【００４６】
ステップＳ５においてパケット待ちがあれば「選定」とし、同じ行、同じ列の要素をすべて「非選定」とする（ステップＳ６）。他方、パケット待ちがなければ、その要素を「非選定」とし（ステップＳ５→Ｓ７）、次いでＭａの中で「未選定」の要素があるかどうか調べる（ステップＳ８）。もしＭａの中に「未選定」の要素があればそのままステップＳ４に戻り、もしＭａの中に「未選定」の要素がなければステップＳ２に戻る。ステップＳ２において「未選定」の要素がもうなかったら、ＷＭの要素の選定作業を終了し、「選定」の要素に対応するコネクションを接続するように、スイッチ手段１３に命令し、また、「選定」の要素のウエイトを１減じる（ステップＳ９）。
【００４７】
上記のアルゴリズムＡをタイムスロットごとに繰り返し、各コネクションの接続を行う。帯域割当周期分終えたとき、ＷＭを初期状態に戻す。上記のアルゴリズムＡにより、すべてのコネクションにパケット待ちが十分ある状態において、必ず各行、又は各列の合計値の最大値が帯域割当周期を下回っている場合、すべての、ＷＭに割り当てられた帯域を割り当てることが保証されるのは明らかである。
【００４８】
上記のアルゴリズムＡを用いて、１タイムスロット内での入力ポート１１と出力ポート１６間のコネクションの割当方法を説明する。図８（１）は制御用記憶手段１５内に格納されるＷＭの一例を示す。また図８（２）はパケット検知手段１４１がスイッチ手段１３、入力手段１２、外部用インタフェース手段１４３を通して、入力手段１２内の各出力ポート用記憶手段１２２にパケットが蓄積されているかどうかを検知し、制御用記憶手段１５に格納されているＲＭの一例を示す。各要素の１はパケット待ちあり、０がパケット待ちなしに対応している。
【００４９】
図８（３）はアルゴリズムＡにより図８（１）で示したＷＭと図８（２）で示したＲＭを用いて、１タイムスロット内でどの入力ポート１１と出力ポート１６を接続するかの方法を示したものである。図８（３）▲１▼では、Ｍ（０，０）すなわち入力ポート＃０と出力ポート＃０間のコネクションが「選定」されている。図８（３）▲２▼で「選定」された要素と同じ行と列を「非選定」対象とする。これはすでに「選定」されているコネクションと同じポートは、接続することができないからである。図８（３）▲２▼で新たな「未選定」要素からＭ（２，１）すなわち入力ポート＃２と出力ポート＃１のコネクションが「選定」される。
【００５０】
図８（３）▲３▼では、Ｍ（２，１）の同一行、同一列の要素も「非選定」対象として、「選定」の対象から外す。残る「未選定」要素はＭ（１，２）しかなく、図８（２）に示すＲＭを参照すると、パケット待ち＝１が存在するので、Ｍ（２，１）が「選定」される。ここで「未選定」の要素がなくなり、結局Ｍ（０，０），Ｍ（１，２），Ｍ（２，１）に対応するコネクションの接続を１タイムスロット内で行う。そして、それぞれの要素のウエイトを１ずつ減算する。
【００５１】
図９は図８（３）で示した１タイムスロット内での選定の結果をタイムスロットごとに表したものである。ハッチングされているのが接続すべきコネクションに対応する。図９ではＲＭは全てａｌｌ１（パケット待ちあり）という条件の結果である。アルゴリズムＡを用いているので、重みの多い方から優先して、パケットスケジューリングが行われており、ＷＭの要素の比でパケットが送出される。
【００５２】
上記のアルゴリズムは、各コネクション間を相対的に割り当てたものである。そのアルゴリズムを用いて、スイッチコントロール手段は次のような方法を用いて最低帯域割当を行う。また、図１０に示すように、管理者はタイムスロットを意識せずに、管理者が設定する最低帯域を割当タイムスロット数に変換する変換手段１４４をスイッチコントロール手段１４に設ける。
【００５３】
図１１（１）は管理者による最低帯域の設定を表わす。ウエイトマトリクス（ＷＭ）の各要素をＭ［ｉ，ｊ］とすると次のような式が成り立つ。
Ｍ（ｉ，ｊ）＝ａ（ｉ，ｊ）／（Ｂ×α）×ＴＳ
ただし、
ＴＳ：帯域周期時間、
α：１タイムスロット時間
Ｂ：リンクスピード（ｂｐｓ）、
ａ（ｉ，ｊ）：入力ポート＃ｉ　と出力ポート＃ｊ間のコネクションの最低帯域（ｂｐｓ）
【００５４】
すなわち、例えば１つのタイムスロットで送ることのできるパケットのバイト数を６４バイト（ｂｙｔｅ）、各入出力ポートのリンクスピードを１０Ｍｂｐｓとすると、１つのタイムスロットは５０μ秒以上必要となる。帯域周期を２．５ｍｓとし、このとき指定された最低帯域が１．４Ｍｂｐｓとすると、
Ｍ（ｉ，ｊ）
＝１．４Ｍｂｐｓ／（１０Ｍｂｐｓ×５０μｓ）×２．５ｍｓ
＝７
となる。
【００５５】
図１１（１）を上記の条件で、ＷＭに変換した結果を図１１（２）に示す。変換手段１４４は上記の式を用いてＷＭに変換し、制御用記憶手段１５に格納する。ユーザ側から帯域制御を設定する際は、ＷＭの要素が整数になるようにＢ×（α／ＴＳ）刻みごとに設定を行う。例えばＴＳ＝５ｍｓ、α＝５０μｓ、Ｂ＝１０Ｍｂｐｓのときは、１００ｋｂｐｓ刻みの帯域制御を行うことができる。ＴＳを大きくすることで、より細かい帯域制御を行うことが可能になる。
【００５６】
次に、ピーク帯域制御の方法を示す。図１２（１）は制御用外部インタフェースを通してスイッチコントロール手段１４に設定されたピーク帯域の例である。変換手段１４４はピーク帯域についても、図１２（２）で示すピークマトリクス（以下ＰＭ）に変換を行い、制御用記憶手段１５に格納する。ＰＭは、最低帯域からＷＭを作成するのと、全く同じ方法で作成するが、次のような条件を実行する。
・ＷＭを用いてコネクションを「選定」していくと同時に、対応しているＰＭの要素を減算する。
・ＰＭ内の０になった要素は、コネクションの「非選定」要素とする。
・帯域割当周期ごとに、ＰＭを元に戻す。
上記のアルゴリズムにより各コネクション間のピーク帯域制御を行うことができる。
【００５７】
次に余剰帯域の割り当て方法について説明する。図１３のステップＳ１ａに示すように、図７で示したアルゴリズムＡのステップＳ１におけるすべてのＷＭの要素を「未選定」とする。ウエイト＝０以下でも「未選定」とするようにする。このことにより、ウエイトが０以下になっても「未選定」要素となり、「選定」とされる可能性が出てくる。上記の方法により、最低帯域に達したコネクションが他のコネクションが最低帯域に達していない状態でも、「選定」されることになるため、スループットがよくなる効果が得られる。
【００５８】
余剰帯域を各コネクションごとに公平に割り当てるアルゴリズムを説明する。図７で示したアルゴリズムＡのステップＳ１の代わりに図１４で示す次の処理を行う。ＷＭの各要素がすべて０以下かどうかを判定し（ステップＳ１−１）、ＹＥＳであればすべてのＷＭの要素に１を足す。又はＷＭの要素で０以下のもののみ「選定」とされた場合、すべてのＷＭの要素に１を足す（ステップＳ１−２）。
【００５９】
また、ステップＳ１−２の処理を「ＷＭの初期値に戻す」にすると、余剰帯域が「最低帯域の比」で割り当てられる。また、同じく「ＰＭの初期値に戻す」にすると、余剰帯域が「ピーク帯域の比」で割り当てることができる。また、同じく「ＰＭの初期値とＷＭの初期値の差＝ＰＭ−ＷＭをＷＭとする」にすると余剰帯域を「ピーク帯域から最低帯域の差の割合」で割り当てることができる。また、「ユーザ側から余剰帯域の比を設定」したい場合は、制御用外部インタフェースを通してスイッチコントロール手段１４に対して「余剰帯域の比」の入力を行い、変換手段１４４で余剰帯域の比によりマトリクスＹＭを生成する。このとき、ステップＳ１−２の処理を「ＷＭをＹＭで初期化する」にすると、余剰帯域が「ユーザ指定の通り」に割り当てることができる。
【００６０】
また余剰帯域を各出力ポート１６ごとに、公平になるように割り当てる方法を説明する。まず制御用外部インタフェースを通して設定された最低帯域制御から、スイッチコントロール手段１４は式Ｘを用いてＷＭを生成する。スイッチコントロール手段１４は各出力ポート１６ごとに、各要素の合計が同じになるように、図１５に示すように次の操作を行う。
１．ＷＭの各列を各々、合計する（図１５▲１▼）。
２．各々を合計した結果をＭ（ｘ）（ｘは列のインデックス）とすると、各要素に対してＳ／Ｍ（ｘ）を掛ける（図１５▲２▼、Ｓ：帯域割当周期）。
３．２の結果を、各入力ポート１１ごとに合計する（図１５▲３▼）。
４．各入力ポートごとの合計値で最も大きい値を帯域割当周期Ｓで割った値で、すべての要素を割る（図１５▲４▼）。
５．１〜４のアルゴリズムの結果、ＷＭの初期値よりも全ての要素が大きいときは、それを新たなＷＭとしてアルゴリズムＡを行う。ＷＭの初期値よりも小さい要素が存在する場合は、公平に割り当てることができない。
【００６１】
上記の操作されたＷＭが出力ポート１６ごとに、出力ポート１６の合計帯域を同じ値になるように割り当てられている。それを用いて、アルゴリズムＡを用いて帯域割当を行うことで、出力ポート１６ごとに公平な割当を行うことができる。また初期のＷＭの設定に依存するが、アルゴリズムＡにより操作されたＷＭが、ＷＭの初期値より小さい場合もある。この場合、最低帯域制御ができなくなるので、出力ポート１６ごとに公平に割り当てることはできない。
【００６２】
また、前記と同じように余剰帯域を各入力ポート１１ごとに、公平になるように割り当てる方法を図１６を参照して説明する。まず、制御用外部インタフェースを通して設定された最低帯域制御から、スイッチコントロール手段１４は式Ｘを用いてＷＭを生成する。スイッチコントロール手段１４は各入力ポート１１ごとに、各要素の合計が同じになるように、次の操作を行う。
１．ＷＭの各行を各々合計する（図１６▲１▼）。
２．各々を合計した結果をＭ（ｙ）（ｙは行のインデックス）とすると、各要素に対してＳ／Ｍ（ｙ）を掛ける（図１６▲２▼）。
３．２の結果を各出力ポートごとに合計する（図１６▲３▼）。
４．各出力ポートごとの合計値で最も大きい値をＳで割った値で、すべての要素を割る（図１６▲４▼）。
５．１〜４のアルゴリズムの結果、ＷＭの初期値よりも全ての要素が大きいときは、それを新たなＷＭとしてアルゴリズムＡを行う。ＷＭの初期値よりも小さい要素が存在する場合は、公平に割り当てることができない。
【００６３】
上記の操作されたＷＭが出力ポート１６ごとに、入力ポート１１の合計帯域を同じ値になるように割り当てられている。それを用いて、アルゴリズムＡを用いて帯域割当を行うことで、入力ポート１１ごとに公平な割当を行うことができる。初期設定のＷＭによりアルゴリズムＡにより操作されたＷＭが、ＷＭの初期値より小さい場合もある。この場合、最低帯域制御ができなくなるので、入力ポート１１ごとに公平に割り当てることはできない。
【００６４】
次に優先制御を行う方法を示す。ネットワーク管理者から、図１７（１）で示すような優先度がスイッチコントロール手段１４に設定され、設定された優先度は変換手段１４４により、図１７（２）で示す優先度マトリクス（以下ＰｒＭと呼ぶ）を生成し、制御用記憶手段１５に記憶させる。図１７の例では、優先度は２段階で数字が少ない方が優先される（優先度が高い順から高い順から１、２）。
【００６５】
優先制御を設けたパケットスケジューリングアルゴリズムを、フローにしたものを図１８に示す。以下のアルゴリズムをアルゴリズムＢとする。それぞれのコネクションに対応しているＷＭの各要素の状態を４つの状態に分ける。
「選定」…選ばれた要素
「未選定」…これから選ばれる可能性がある要素
「非選定」…これから選ばれる可能性のない要素
「準選定」…現在の優先度では、選ばれることができない要素
また、優先度状態という現在、どの優先度の範囲まで探索しているのかを示す値を入れる。
【００６６】
図１８において、まず、優先度状態の初期値を１とする（ステップＴ０）。次いでＰｒＭを参照し、優先度状態より同じか高い優先度を持つ要素を「未選定」とし、それ以外の要素を「準選定」とする（ステップＴ１）。次いでＷＭにおける「未選定」の要素の存在のチェックを行う（ステップＴ２）。もし「未選定」の要素が存在するならば、「未選定」の要素を含む行及び列をすべて合計して最も大きい行及び列をＭａとする（ステップＴ２→Ｔ３）。次いでＭａの中の「未選定」要素の中で最も大きいウエイトを持つ要素を選ぶ。ただし最も大きいウエイトが複数あるときは、ランダムで１つ選ぶ（ステップＴ４）。
【００６７】
次いでその要素に対応するＲＭを参照し、パケット待ちがあるかどうかを判断する（ステップＴ５）。パケット待ちがあれば「選定」とし、同じ行、同じ列の要素をすべて「非選定」とする（ステップＴ５→Ｔ６）。パケット待ちがなければ、その要素を「非選定」とし（ステップＴ５→Ｔ７）、次いでＭａの中で「未選定」の要素があるかどうか調べる（ステップＴ８）。もしＭａの中に「未選定」の要素があれば、そのままステップＴ４に戻る。もしＭａの中に「未選定」の要素がなければ、ステップＴ２に戻る。
【００６８】
ステップＴ２において「未選定」の要素がもうなかったら、次に、ＷＭの中に「準選定」の要素がないかを調べる（ステップＴ１０）。もし存在すれば、優先度状態を１足し、ステップＴ１に戻る。もし「準選定」要素が存在しなければ、ＷＭの要素の選定作業を終了し、「選定」の要素に対応するコネクションを接続するようにスイッチ手段に命令し、また、「選定」の要素のウエイトを１減じる（ステップＴ９）。
【００６９】
上記のアルゴリズムＢを用いて、１タイムスロット内での入力ポート１１と出力ポート１６間のコネクションの優先制御付き割当方法の例を説明する。図１９（１）は制御用記憶手段１５内に格納されるＷＭの例である。また図１９（２）は各コネクションのパケット待ちの存在を表すＲＭの例である。各コネクションのパケット待ちの各要素の１はパケット待ちあり、０がパケット待ちなしに対応している。また図１９（　３）は、各コネクションの優先度を設定したＰｒＭの例である。
【００７０】
図１９（４）はアルゴリズムＢにより図１９（１）で示したＷＭと図１９（２）で示したＲＭ及び図１９（３）で示したＰｒＭを用いて、１タイムスロット内で入力ポート１１と出力ポート１６の接続方法を示したものである。図１９（４）▲１▼では現在の優先度順位は１なので、優先度１の要素を探索対象として、それ以外の要素を「準選定」要素とする。その中でＭ（２，２）が「選定」される。図１９（４）▲２▼では、「選定」された要素Ｍ（２，２）と同じ行と列を「非選定」対象とし、探索対象から外す。この理由はすでに「選定」されているコネクションと同じポートは、接続することができないからである。
【００７１】
図１９（４）▲２▼では、新たな「選定」対象すなわちＭ（０，１），Ｍ（１，０），Ｍ（１，１）は、パケット待ちが存在しないので、優先度状態を２にし、今まで「準選定」だったＭ（０，０）を「未選定」にし、探索の結果Ｍ（０，０）を「選定」要素とする。図１９（４）▲３▼では、Ｍ（０，０）の同一行、同一列の要素も「非選定」対象として、探索の対象から外す。図１９（４）▲４▼では残る「未選定」の要素はＭ（１，１）しかなく、ＲＭを参照すると、パケット待ちが存在しない。図１９（４）▲５▼では、「未選定」と「準選定」対象も存在しないので、「選定」を終了する。よって探索を終了し、結局Ｍ（０，０），Ｍ（２，２）に対応するコネクションの接続を１タイムスロット内で行う。そしてそれぞれの要素のウエイトを１ずつ減算する。
【００７２】
次に余剰帯域の割当のときのみ優先制御を行う方法を示す。最初に、アルゴリズムＡによって帯域の割り当てを行い、ＷＭの要素すべて０以下になったとき、アルゴリズムＢを用いて帯域の割り当てを行う。すなわち最低帯域に達していない場合は、優先制御を用いないアルゴリズムＡを用いて最低帯域制御を優先し、すべての要素が最低帯域に達したときに、優先制御付きのアルゴリズムＢを用いて優先制御を行う。上記のアルゴリズムによって余剰帯域の割当のときのみ優先制御を行う効果が得られる。
【００７３】
また、パケット検知手段１４１を拡張して、各出力ポート用記憶手段１２２内のパケットの存在の有無だけではなく、出力ポート用記憶手段１２２内に格納されているパケット数を検出し、ある閾値を超えた場合、優先度を「最優先」にする。図２０に示すように、パケット検知手段１４１は前記したＰｒＭの要素を「最優先」用に０を設定する（ステップＴ０−１）。そしてアルゴリズムＢを用いて「選定」を行う。ただし優先度状態の初期値を１ではなく、０にする必要がある（ステップＴ０−２）。この操作により、パケットが多く格納されている出力ポート用記憶手段１２２に対応するコネクションから優先的に通信を行うことができる。
【００７４】
次に余剰帯域の割当のときのみパケット待ちの多いコネクションを優先する制御を行う方法を示す。前記と同じように、パケット検知手段１４１が各出力ポート用記憶手段１２２内で格納されているパケット数を数えて、ある一定の閾値を超えている場合は、該当するＰｒＭの要素を０にする。最初に、アルゴリズムＡによって帯域の割り当てを行い、ＷＭの要素がすべて０以下になったとき、以下のアルゴリズムＢ’を用いて帯域の割り当てを行う。すなわち最低帯域に達していない場合は、優先制御を用いないアルゴリズムＡを用いて最低帯域制御を優先し、すべての要素が最低帯域に達したときに、パケット検知機能と優先制御が追加したアルゴリズムＢ’を用いてパケットスケジューリングを行う。
【００７５】
上記のアルゴリズムによって余剰帯域の割当のときのみ優先制御を行うことができる。すなわち最低帯域に達していない場合は、優先制御を用いないアルゴリズムＡを用いて最低帯域制御の達成を優先し、すべての要素が最低帯域に達したときに、初めて、パケット待ちの多いコネクションを優先して通信する効果が得られる。
【００７６】
＜第２の実施の形態＞
次に図２１〜図２７を参照して本発明の第２の実施の形態を説明する。パケットスイッチ１の構成と違うところのみ示す。第２の実施の形態についての前記ｋ番目の入力ポート１１ｋと接続されている入力手段２２ｋに関しての構成を図２１に示す。入力手段２２ｋは、送信元ＩＰアドレスと送信先ＩＰアドレス、あるいはそれに準じるフローを識別できる情報をパケットから取りだし、フロー用記憶手段２２２ｋ１〜２２２ｋｐに分配する入力フロー分配部２２１ｋと、フロー用記憶手段２２２ｋ１〜２２２ｋｐと、入力パケットを多重しててスイッチ手段１３に送信する入力パケット多重手段２２３ｋと、どのフローを選択するかを決定する入力コントロール手段２２４ｋと、入力手段２２ｋとのコネクションとフローとの対応を格納するフロー対応テーブル２２５ｋで構成される。
【００７７】
管理者からは送信元ＩＰアドレスと送信先ＩＰアドレス及び、上位のアプリケーションなどによりフローごとに最低帯域などの割当が行われる。図３に示す帯域割当制御手段１４２はそれを受けて、フローごとにインデックスを割り当て、管理者からの情報を元にフローごとに帯域の割り当てを行うテーブルを生成する。図２２はフロー毎の帯域割り当てテーブルの例を示し、このテーブルはフロー番号ごとに、入力ポート番号＃ｉ、出力ポート番号＃ｊ、送信元ＩＰアドレス、送信先ＩＰアドレス、アプリケーション、最低帯域、ピーク帯域、優先度、パケット待ちの有無の各情報により構成されている。
【００７８】
この帯域割り当てテーブルを元に変換手段１４４は、同一のコネクションを用いるフローに設定されたフローは全て合計して、その結果を基にＷＭに変換して制御用記憶手段１５に格納する。（ＷＭの変換方法は既に説明している。）また、変換手段１４４は、その後、入力手段１２ごとにコネクションとフローとの関係を示したフロー対応テーブルを生成し、それを該当する各入力手段１２のフロー用記憶手段２２２に保持させる。上記のテーブルはＷＭだけではなく、ピーク帯域制御用のウエイトマトリクスＰＭ、余剰帯域用のマトリクスを生成するときも、同時にフロー対応テーブルに保持させる。各フロー用記憶手段２２２に保持させる各ウエイトテーブルの例を図２３に示し、このウエイトテーブルはフロー番号ごとに、入力ポート番号＃ｉ、出力ポート番号＃ｊ、最低帯域、ピーク帯域、優先度、パケット待ちの有無の各情報により構成されている。
【００７９】
またパケット検知手段１４１は現在の各フロー用記憶手段２２２の中でパケット待ちをしているかどうかを検知し、ウエイトが１以上あるフローであってパケット待ちが存在する場合は１を立て、同一コネクション内のフローでパケット待ちが存在しない場合は０を立て、同一コネクション内のフローであってウエイトが０以下のフローのみ、パケット待ちが存在する場合は２を立てる。パケット待ちに関しては、上記の条件をリアルタイムに認識し、制御用記憶手段１５にリクエストマトリクス（ＲＭ）という形で保持する。
【００８０】
図２４に示すように、帯域割当方法については、１タイムスロットごとにコネクションを探索するのは第１の実施の形態と同じである。図７のステップＳ５の探索した要素が、パケット待ちかどうかを判別するところで、ステップＳ５’において対応するＲＭの値が２のときも０と同じようにステップＳ７に飛んでその要素を「非選定」にする。この上記のアルゴリズムにより、「選定」とされた要素は、必ずウエイト１以上のフローがパケット待ちをしていることが保証されている。上記のアルゴリズムをアルゴリズムＡ’とする。
【００８１】
また「選定」とされた要素に対応するコネクションに関して、スイッチ手段１３がそれぞれのコネクションを接続するときに１つのコネクションに複数のフローが設定されているので、入力手段２２の中でどのフローを流すかを決めるアルゴリズムが必要である。このアルゴリズムは入力手段２２の中の入力コントロール手段２２４が実行する。そのアルゴリズムＸをフローにしたものが図２５である。
【００８２】
入力コントロール手段２２４は自入力ポートが「選定」要素に対応するコネクションが存在するかどうかをチェックし（ステップＵ１）、存在すれば、入力手段２２は「選定」された要素に対応するコネクションを用いるフローを、フロー用記憶手段２２２から読み出して抜き出す。そのとき識別子をそれぞれのフローに新たに０から順に付け直す。そのとき重みＷｋに対応するフローをＦｋとする（ｋはフロー識別子）（ステップＵ２）。
【００８３】
Ｗｋ＞０、かつＦｋが格納されているフロー用記憶手段２２２にパケットが格納されているならば（ステップＵ３）、Ｆｋを出力対象とし、Ｗｋを１減じ（ステップＵ６）、終了する。ステップＵ３のチェックでＮＯならば、フロー識別子ｋをインクリメントし（ステップＵ４）、次いですべてのＷｋを検索していなければ（ステップＵ５）、ステップＵ３に戻る。すべてのＷｋを検索していればそのまま終了する。
【００８４】
帯域割り当てを、スイッチコントロール手段１４の帯域割当制御手段１４２が行うアルゴリズムＡ’と入力コントロール手段２２４が行うアルゴリズムＸによる組み合わせで行う場合、すべてのフローが最低帯域に達するまで、最低帯域を超えることができない。
【００８５】
そこで、アルゴリズムＡ’と図２６に示すようにアルゴリズムＸを変えることで、他のフローが最低帯域に達していなくても、余剰帯域を使うことができる。帯域割当制御手段１４２が用いるアルゴリズムＡ’に関して、図２４のステップＳ５’の探索した要素がパケット待ちかどうかを判別するところで、対応するＲＭの値が２のときは、該当コネクションにパケットが存在するので、その要素を「選定」にする。
【００８６】
入力コントロール手段２２４が用いるアルゴリズムＸはＷｋが１以上のときしか、重みを割り当てることができないので、余剰帯域を割り当てるためには、図２６に示すように次の処理を追加する。追加したステップＵ７〜ステップＵ９により、Ｗｋが０以下でもパケット待ちがあれば送信を行う。上記のアルゴリズムによって、余剰帯域を有効に使うことができる。
【００８７】
余剰帯域の割当は、図１４で示したフローチャートのステップＳ１−２を、各フローを公平にする時、ステップＳ１−２のＷＭの初期化処理のところで、ＷＭは該当コネクションのフロー数だけ足す必要がある。最低帯域、ピーク帯域、ピーク帯域―最低帯域、余剰を指定した比で比例に関しては、図１４と同じでよい。一緒に入力手段２２のフロー対応テーブル２２５も書き換える。
【００８８】
また第１の実施の形態において、ＷＭを出力ポート１６又は入力ポート１１ごとに公平に帯域を割り当てる操作を行っているが、操作前と操作後のＷＭの各要素の比を計算し、その比に同じ割合で、フロー対応テーブル２２５の中身を変更することで、フローごとに帯域割り当て制御を行うことができる。
【００８９】
また、管理者からフロー毎の優先度を設定したとき、優先度の制御を基に入力コントロール手段２２４はそのコネクションに対応する優先度テーブルを生成する（図２３）。コネクションごとの優先度を表わすＰｒＭは次のようにして、決める。下記のアルゴリズムをアルゴリズムＹとする。
・該当コネクションに属するフローの中でパケット待ちがあるフローの優先度で最も高い優先度をＰｒＭの要素とする。
・該当コネクションに属するフローの中でパケット待ちのフローがない場合、優先度は１に固定する。
【００９０】
そのＷＭ、ＰｒＭを用いて、図１８で示したアルゴリズムＢにより「選定」要素を決める。その「選定」要素に接続する入力手段２２の入力コントロール手段２２４は、前記優先度テーブルによりフローの選出を決める。図２７は優先制御を行うときの入力コントロール手段２２４のフローチャートを示したものである。重み及びパケット待ちの判定のところで、現在の優先度状態よりＰｒＭの該当フローが優先度が低い場合は、フローを送出しないという処理（ステップＵ’３）とする。この処理によってＰｒＭの要素より優先度が低いフローは、パケットを送出できず、フロー毎の優先度処理が可能となる。上記の処理を余剰帯域の割り当てのときのみ行うことで、余剰帯域のみ、フロー毎の優先処理を行うことができる。
【００９１】
また、図３に示すパケット検知手段１４１を拡張して、各フロー用記憶手段２２２内のパケットの存在の有無だけではなく、フロー用記憶手段２２２内に格納されているパケット数を検出し、ある閾値を超えた場合、優先度を「最優先」し、入力コントロール手段２２４に伝える。パケット検知手段１４１は前記したＰｒＭの要素を「最優先」用に０を設定し、入力コントロール手段２２４はフロー対応テーブル２２５を同じく更新する。そしてアルゴリズムＢを用いて「選定」を行う。ただし優先度状態の初期値を１ではなく、０にする必要がある。入力コントロール手段２２４はアルゴリズムＹを用いる。
【００９２】
また、余剰帯域の割当のときのみパケット待ちの多いコネクションを優先する制御を行う方法を示す。前記と同じように、パケット検知手段１４１が各出力ポート用記憶手段２２２内で格納されているパケット数を数えて、ある一定の閾値を超えている場合は、該当するＰｒＭの要素を０にする。最初に、アルゴリズムＡによって帯域の割り当てを行い、ＷＭの要素すべてが０以下になったとき、アルゴリズムＢを用いて帯域の割り当てを行う。上記の処理を余剰帯域の割当のときのみ行うことで、余剰帯域のみ、パケット待ちの多いフローから優先処理を行うことができる。
【００９３】
【発明の効果】
請求項１に記載の発明によれば、ｎ個の入力手段とｍ個の出力ポートの間の各コネクションの帯域割当量に応じて各コネクションに帯域を１タイムスロットごとに割り当てるので、各コネクションに対する帯域の割り当てをユーザごとに細かに行うことができる。
請求項２に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行うことができる。
請求項３に記載の発明によれば、コネクション毎のピーク帯域制御をユーザごとに細かに行うことができる。
請求項４に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域のスループットを上げることができる。
請求項５に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各コネクションに公平に割り当てることができる。
請求項６に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各コネクションに最低帯域の比で割り当てることができる。
請求項７に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各コネクションにピーク帯域の比で割り当てることができる。
請求項８に記載の発明によれば、コネクション毎の最低帯域保証制御、ピーク帯域制御をユーザごとに細かに行った後、余剰帯域を各コネクションにピーク帯域と最低帯域の差の比で割り当てることができる。
請求項９に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を外部から設定した余剰帯域の割当比で割り当てることができる。
請求項１０に記載の発明によれば、各出力ポートの総スループットが公平になるように割り当てることができる。
請求項１１に記載の発明によれば、各入力ポートの総スループットが公平になるように割り当てることができる。
請求項１２に記載の発明によれば、ユーザにより設定された優先順位が高いコネクションを優先して割り当てることができる。
請求項１３に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、ユーザにより設定された優先順位が高いコネクションを優先して割り当てることができる。
請求項１４に記載の発明によれば、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するコネクションを優先することができる。
請求項１５に記載の発明によれば、コネクション毎の最低帯域保証制御をユーザごとに細かに行った後、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するコネクションを優先することができる。
請求項１６に記載の発明によれば、フロー毎の帯域割当量に応じて各フローに帯域を１タイムスロットごとに割り当てるので、各フローに対する帯域の割り当てをユーザごとに細かに行うことができる。
請求項１７に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行うことができる。
請求項１８に記載の発明によれば、フロー毎のピーク帯域制御をユーザごとに細かに行うことができる。
請求項１９に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域のスループットを上げることができる。
請求項２０に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各フローに公平に割り当てることができる。
請求項２１に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を各フローに最低帯域の比で割り当てることができる。
請求項２２に記載の発明によれば、フロー毎の最低帯域保証制御、ピーク帯域制御をユーザごとに細かに行った後、余剰帯域を各フローにピーク帯域の比で割り当てることができる。
請求項２３に記載の発明によれば、フロー毎の最低帯域保証制御、ピーク帯域制御をユーザごとに細かに行った後、余剰帯域を各フローにピーク帯域と最低帯域の差の比で割り当てることができる。
請求項２４に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、余剰帯域を外部から設定した余剰帯域の割当比で割り当てることができる。
請求項２５に記載の発明によれば、各出力ポートの総スループットが公平になるように割り当てることができる。
請求項２６に記載の発明によれば、各入力ポートの総スループットが公平になるように割り当てることができる。
請求項２７に記載の発明によれば、優先順位が高いフローを優先して割り当てることができる。
請求項２８に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、優先順位が高いフローを優先して割り当てることができる。請求項２９に記載の発明によれば、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するフローを優先することができる。
請求項３０に記載の発明によれば、フロー毎の最低帯域保証制御をユーザごとに細かに行った後、パケットの量及び／又は数が一定の閾値を超過した出力ポート別記憶手段と対応するフローを優先することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態において使用されるパケットスイッチの構成を示すブロック図
【図２】図１の入力手段の構成を詳しく示すブロック図
【図３】図１のスイッチコントロール手段の構成を詳しく示すブロック図
【図４】本発明の第１の実施の形態の動作を説明するための図であり、管理者が設定する各コネクションごとの割当の比を示す説明図
【図５】本発明の第１の実施の形態の動作を説明するための図であり、ウエイトマトリクスを示す説明図
【図６】本発明の第１の実施の形態の動作を説明するための図であり、リクエストマトリクスを示す説明図
【図７】図３の帯域割当制御手段がタイムスロットごとに割当を行うコネクションを決定するため処理を示すフローチャート
【図８】図７の処理による各コネクションに対する選定の過程を示す説明図
【図９】図７の処理を続けて行った場合の各コネクションの割当結果例を示す説明図
【図１０】図３のスイッチコントロール手段に変換手段を付加した態様を示すブロック図
【図１１】（１）本発明の第１の実施の形態において、管理者が設定する各コネクションごとの最低帯域を示す説明図
（２）図１１（１）に対応するウエイトマトリクスを示す説明図
【図１２】（１）本発明の第１の実施の形態において、管理者が設定する各コネクションごとのピーク帯域を示す説明図
（２）図１２（１）に対応するピークマトリクスを示す説明図
【図１３】本発明の第１の実施の形態において、図７の処理に比べて余剰帯域を有効にする処理を示すフローチャート
【図１４】本発明の第１の実施の形態において、余剰帯域を指定した割合に割り当てた処理を図７に追加したフローチャート
【図１５】本発明の第１の実施の形態において、各出力ポートの総スループットが公平になるようにウエイトマトリクスを変更する過程を示す説明図
【図１６】本発明の第１の実施の形態において、各入力ポートの総スループットが公平になるようにウエイトマトリクスを変更する過程を示す説明図
【図１７】（１）本発明の第１の実施の形態において、管理者が設定する各コネクションごとの優先度を示す説明図
（２）図１７（１）に対応する優先度マトリクスを示す説明図
【図１８】本発明の第１の実施の形態において、優先制御を追加した帯域割当処理を示すフローチャート
【図１９】図１８の処理による各コネクションに対する選定の過程を示す説明図
【図２０】本発明の第１の実施の形態において、図１８の処理にパケット待ちが多いコネクションを優先する処理を追加したフローチャート
【図２１】本発明の第２の実施の形態における入力手段の構成を示すブロック図
【図２２】本発明の第２の実施の形態のスイッチコントロール手段が生成するフローテーブルの概要を示す説明図
【図２３】本発明の第２の実施の形態の入力手段で保持するコネクションとフローの対応を示す説明図
【図２４】本発明の第２の実施の形態におけるコネクションを決定するための処理を示すフローチャート
【図２５】本発明の第２の実施の形態における入力コントロール手段でのフロー選定処理を示すフローチャート
【図２６】本発明の第２の実施の形態において、図２５から余剰帯域を有効にしたフロー選定処理を示すフローチャート
【図２７】本発明の第２の実施の形態において、図２６から優先処理を追加したフロー選定処理を示すフローチャート
【図２８】従来の出力ポート数だけバッファを持つ複数ポートを持つパケットスイッチの構成を示すブロック図
【図２９】図２８のパケットスイッチの動作において、同一タイムスロット内で同一入力ポートから別の出力ポートへの接続によりパケットの衝突が起こることを示す説明図
【図３０】図２８のパケットスイッチの動作において、同一タイムスロット内で別の入力ポートから同一出力ポートへの接続によりパケットの衝突が起こることを示す説明図
【符号の説明】
１　パケットスイッチ
１１　入力ポート
１２、２２　入力手段
１２１　パケット分割分配手段
１２２　出力ポート用記憶手段
１２３　出力パケット多重手段
１３　スイッチ手段
１４　スイッチコントロール手段
１４１　パケット検知手段
１４２　帯域割制御手段
１４３　外部用インタフェース手段
１４４　変換手段
１５　制御用記憶手段
１６　出力ポート
２２１　入力フロー分配部
２２２　フロー用記憶手段
２２３　入力パケット多重手段
２２４　入力コントロール手段
２２５　フロー対応テーブル
【図１】
2004023769.tif 000003
【図２】
2004023769.tif 000004
【図３】
2004023769.tif 000005
【図４】
2004023769.tif 000006
【図５】
2004023769.tif 000007
【図６】
2004023769.tif 000008
【図７】
2004023769.tif 000009
【図８】
2004023769.tif 000010
【図９】
2004023769.tif 000011
【図１０】
2004023769.tif 000012
【図１１】
2004023769.tif 000013
【図１２】
2004023769.tif 000014
【図１３】
2004023769.tif 000015
【図１４】
2004023769.tif 000016
【図１５】
2004023769.tif 000017
【図１６】
2004023769.tif 000018
【図１７】
2004023769.tif 000019
【図１８】
2004023769.tif 000020
【図１９】
2004023769.tif 000021
【図２０】
2004023769.tif 000022
【図２１】
2004023769.tif 000023
【図２２】
2004023769.tif 000024
【図２３】
2004023769.tif 000025
【図２４】
2004023769.tif 000026
【図２５】
2004023769.tif 000027
【図２６】
2004023769.tif 000028
【図２７】
2004023769.tif 000029
【図２８】
2004023769.tif 000030
【図２９】
2004023769.tif 000031
【図３０】
2004023769.tif 000032