(57)【要約】【課題】スケジューリング部を分散配置し、かつ、多数のコネクション又はコネクション群のトラフィックに対して公平に帯域を割り当てる分散型帯域割当回路を提供する。【解決手段】回路は、入力カードと、出力カードと、入力カードから出力カードへフレームを転送するフレーム転送手段と、収容される入力カードと、出力カード又は出力カードの出力ポートとを共に同一とするコネクションを束ねた論理的なパスであるカード間パスのトラフィック状況に基づき、各カード間パスへの要求帯域を決定する要求帯域決定手段と、予め設定された各コネクションの帯域種別及びその帯域値と、要求帯域とに基づき、各カード間パスに割り当てる帯域である割当帯域を決定する帯域割当手段とを有し、入力カードは、割当帯域に基づきカード間パスごとに振り分けられたフレームのフレーム転送手段への出力のタイミングを決定するスケジュール手段を備えている。【選択図】図１
2007134779.tif 000002
【特許請求の範囲】
【請求項１】
１以上のコネクションを収容し、コネクションのフレームを伝送する伝送装置に使用される回路であって、
フレーム入力のための入力ポートを１以上有する１以上の入力カードと、
フレーム出力のための出力ポートを１以上有する１以上の出力カードと、
入力カードから出力カードへフレームを転送するフレーム転送手段と、
収容される入力カードと、出力カード又は出力ポートとを共に同一とするコネクションを束ねた論理的なパスであるカード間パスのトラフィック状況に基づき、各カード間パスへの要求帯域を決定する要求帯域決定手段と、
予め設定された各コネクションの帯域種別及びその帯域値と、要求帯域とに基づき、各カード間パスに割り当てる帯域である割当帯域を決定する帯域割当手段とを有し、
入力カードは、割当帯域に基づき、カード間パスごとに振り分けられたフレームのフレーム転送手段への出力のタイミングを決定するスケジュール手段を備えていることを特徴とする分散型帯域割当回路。
【請求項２】
回路内の、カード間パスを収容する構成要素の許容帯域と、それぞれの構成要素に収容されるカード間パスの割当帯域の総和を比較し、許容帯域が大きい場合には、割当帯域の再分配を行う帯域割当調整手段を有することを特徴とする請求項１に記載の分散型帯域割当回路。
【請求項３】
各カード間パスに割り当てた割当帯域、及び／又はカード間パスで観測したトラフィック状況の履歴を保持する履歴保持手段を有し、
要求帯域決定手段は、割当帯域及び／又はトラフィック状況の履歴も要求帯域の決定に使用することを特徴とする請求項１又は２に記載の分散型帯域割当回路。
【請求項４】
入力カードは、コネクションごとのバッファと、
カード間パスごとに設けられ、対応するカード間パスに属するコネクションのバッファからのフレーム読出しのタイミングを決定するコネクション帯域スケジュール手段と、
を有することを特徴とする請求項１から３のいずれか１項に記載の分散型帯域割当回路。
【請求項５】
回路内の、カード間パスを収容する構成要素を流れるトラフィックを監視し、構成要素の許容帯域を超えるトラフィックが存在する場合には、帯域割当手段に対する割当帯域の抑制、及び／又は入力カードに対するトラフィック転送の抑制を指示するバックプレッシャ手段を有することを特徴とする請求項１から４のいずれか１項に記載の分散型帯域割当回路。
【請求項６】
１以上のコネクションを収容し、コネクションのフレームを伝送する伝送装置に使用され、
フレーム入力のための入力ポートを１以上有する１以上の入力カードと、
フレーム出力のための出力ポートを１以上有する１以上の出力カードと、
入力カードから出力カードへフレームを転送するフレーム転送部とを有する回路において、
収容される入力カードと、出力カード又は出力ポートとを共に同一とするコネクションを束ねた論理的なパスであるカード間パスに対して帯域の割当てを行う方法であって、
カード間パスのトラフィックを監視するステップと、
カード間パスのトラフィック状況に基づき、各カード間パスへの要求帯域を決定するステップと、
予め設定された各コネクションの帯域種別及びその帯域値と、要求帯域とに基づき、各カード間パスに割り当てる帯域である割当帯域を決定するステップと、
割当帯域に基づき、各入力カードにおいて、フレーム転送部へ出力するフレームの読出しスケジュールを決定するステップと、
を有することを特徴とする方法。
【請求項７】
回路内の、カード間パスを収容する構成要素の許容帯域と、それぞれの構成要素に収容されるカード間パスの割当帯域の総和を比較し、許容帯域が大きい場合には、割当帯域の再分配を行うステップを有することを特徴とする請求項６に記載の方法。
【請求項８】
各カード間パスに割り当てた割当帯域、及び／又はカード間パスで観測したトラフィック状況の履歴も要求帯域の決定に使用することを特徴とする請求項６又は７に記載の方法。
【請求項９】
入力カードにおいて、同一のカード間パスに属するコネクションのフレームについて、読出しのためのスケジューリングを行い、スケジューリング後のフレームを、前記読出しスケジュールを決定するステップでの対象フレームとすることを特徴とする請求項６から８のいずれか１項に記載の方法。
【請求項１０】
回路内の、カード間パスを収容する構成要素を流れるトラフィックを監視し、構成要素の許容帯域を超えるトラフィックが存在する場合には、割当帯域の抑制、及び／又は入力カードに対するトラフィック転送の抑制を行うことを特徴とする請求項６から９のいずれか１項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｅｔｈｅｒｎｅｔ（登録商標）フレーム等を扱うスイッチ等で使用され、公平制御を行うスケジューリングアルゴリズムに基づき、コネクション又はコネクション群に対して公平な帯域分配を行う回路、特に、大容量のトラフィックを収容する分散型帯域割当回路に関する。
【背景技術】
【０００２】
ネットワーク上に配置され、複数のコネクションを収容するスイッチにおいて、トラフィックの集線又は多重を行う場合、コネクションごとに設定される保証帯域や優先度などの情報に基づいたコネクション間での公平な帯域分配が行われる。ユーザ間での公平な帯域分配のためには、例えば、ＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ）や、ＷＲＲ（Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）や、ＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）等の制御を用いて各コネクションにフレームの読出し権利であるトークンを与え、与えられたトークン量に応じたフレームの読出しを行う方法がある（例えば、非特許文献１参照。）。
【０００３】
【非特許文献１】吉田幸弘、笠原康信、前田洋一、“高速パケット網に適した帯域公平割当制御方式の提案”、電子情報通信学会論文誌  Ｂ、ｖｏｌ．Ｊ８８−Ｂ、Ｎｏ．５、ｐｐ．８７５‐８８１、２００５年５月
【発明の開示】
【発明が解決しようとする課題】
【０００４】
スイッチに収容するコネクション数や、各コネクションの割当帯域が増大することにより、スイッチ内で扱うトラフィックの総和が増大し、スイッチ内のフレーム読出のためのスケジューリング部が処理する入出力帯域の合計が、スケジューリングのために使用できるメモリのアクセス帯域を超過すると、単一回路としてスケジューリング部を構成できなくなる。
【０００５】
このため、スケジューリング部を分散配置する方法が考えられる。一般的に、スイッチ内を転送されるフレームは、スイッチ内のある入力ポートで受信され、ある出力ポートから送信されるため、分散配置するためには、入力ポート及び／又は出力ポートと、分散配置するスケジューリング部の接続方式が重要となる。
【０００６】
複数のスケジューリング部を出力ポートに関連付けて分散配置する場合、ある出力ポートが総ての入力ポートからのトラフィックを集める可能性があるため、トラフィックに対する帯域制限を付与しないのであれば、単一のスケジューリング部を用いてスイッチを構成する場合と同等の処理能力が各スケジューリング部に必要となり、分散配置する効果が失われる。
【０００７】
複数のスケジューリング部を入力ポートに関連付けて分散配置する場合、スケジューリング部が扱うトラフィックの総和は、対象とする入力ポート数によって制限できるので、メモリのアクセス帯域の制限を回避することができる。しかし、複数の異なるスケジューリング部において帯域制御されたトラフィックが集まる出力ポートには、扱うことのできるトラフィック量の合計に制限があり、これを超過した場合にはフレーム廃棄が発生する。出力ポートにおけるフレーム廃棄は、入力ポート側でのスケジューリング部における帯域制御結果、例えば、帯域保証やユーザ間の公平性等に影響を与える。
【０００８】
複数のスケジューリング部を入力ポート及び出力ポートに関連付けて、２段構成とする場合、各フレームは、スケジューリング部を２回通過することとなり、スケジューリングに伴う遅延時間が増加する。更に、スケジューリング部の数が多くなるため実装面積及びコストが増大する。
【０００９】
また、入力ポート及び出力ポートで収容可能なトラフィックの上限の他に、入力及び／又は出力ポートを備えるインタフェースカード間を接続する装置内伝送路についても考慮する必要がある。例えばインタフェースカード間をクロスバ回路等で接続する場合には、インタフェースカード間の帯域にも上限があるため、この上限を超過しないように、装置内伝送路等を通過するトラフィックの総和を制限する必要がある。
【００１０】
したがって、本発明は、スケジューリング部を分散配置し、かつ、多数のコネクション又はコネクション群のトラフィックに対して公平に帯域を割り当てる分散型帯域割当回路及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明による分散型帯域割当回路によれば、
１以上のコネクションを収容し、コネクションのフレームを伝送する伝送装置に使用される回路であって、フレーム入力のための入力ポートを１以上有する１以上の入力カードと、フレーム出力のための出力ポートを１以上有する１以上の出力カードと、入力カードから出力カードへフレームを転送するフレーム転送手段と、収容される入力カードと、出力カード又は出力ポートとを共に同一とするコネクションを束ねた論理的なパスであるカード間パスのトラフィック状況に基づき、各カード間パスへの要求帯域を決定する要求帯域決定手段と、予め設定された各コネクションの帯域種別及びその帯域値と、要求帯域とに基づき、各カード間パスに割り当てる帯域である割当帯域を決定する帯域割当手段とを有し、入力カードは、割当帯域に基づき、カード間パスごとに振り分けられたフレームのフレーム転送手段への出力のタイミングを決定するスケジュール手段を備えていることを特徴とする。
【００１２】
本発明の分散型帯域割当回路における他の実勢形態によれば、
回路内の、カード間パスを収容する構成要素の許容帯域と、それぞれの構成要素に収容されるカード間パスの割当帯域の総和を比較し、許容帯域が大きい場合には、割当帯域の再分配を行う帯域割当調整手段を有することも好ましい。
【００１３】
また、本発明の分散型帯域割当回路における他の実勢形態によれば、
各カード間パスに割り当てた割当帯域、及び／又はカード間パスで観測したトラフィック状況の履歴を保持する履歴保持手段を有し、要求帯域決定手段は、割当帯域及び／又はトラフィック状況の履歴も要求帯域の決定に使用することも好ましい。
【００１４】
更に、本発明の分散型帯域割当回路における他の実勢形態によれば、
入力カードは、コネクションごとのバッファと、カード間パスごとに設けられ、対応するカード間パスに属するコネクションのバッファからのフレーム読出しのタイミングを決定するコネクション帯域スケジュール手段とを有することも好ましい。
【００１５】
更に、本発明の分散型帯域割当回路における他の実勢形態によれば、
回路内の、カード間パスを収容する構成要素を流れるトラフィックを監視し、構成要素の許容帯域を超えるトラフィックが存在する場合には、帯域割当手段に対する割当帯域の抑制、及び／又は入力カードに対するトラフィック転送の抑制を指示するバックプレッシャ手段を有することも好ましい。
【００１６】
本発明による帯域割当方法によれば、
１以上のコネクションを収容し、コネクションのフレームを伝送する伝送装置に使用され、１以上のフレーム入力のための入力ポートを有する１以上の入力カードと、１以上のフレーム出力のための出力ポートを有する１以上の出力カードと、入力カードから出力カードへフレームを転送するフレーム転送部とを有する回路において、収容される入力カードと、出力カード又は出力ポートとを共に同一とするコネクションを束ねた論理的なパスであるカード間パスに対して帯域の割当てを行う方法であって、カード間パスのトラフィックを監視するステップと、カード間パスのトラフィック状況に基づき、各カード間パスへの要求帯域を決定するステップと、予め設定された各コネクションの帯域種別及びその帯域値と、要求帯域とに基づき、各カード間パスに割り当てる帯域である割当帯域を決定するステップと、割当帯域に基づき、各入力カードにおいて、フレーム転送部へ出力するフレームの読出しスケジュールを決定するステップとを有することを特徴とする。
【００１７】
本発明の帯域割当方法における他の実勢形態によれば、
回路内の、カード間パスを収容する構成要素の許容帯域と、それぞれの構成要素に収容されるカード間パスの割当帯域の総和を比較し、許容帯域が大きい場合には、割当帯域の再分配を行うステップを有することも好ましい。
【００１８】
また、本発明の帯域割当方法における他の実勢形態によれば、
各カード間パスに割り当てた割当帯域、及び／又はカード間パスで観測したトラフィック状況の履歴も要求帯域の決定に使用することも好ましい。
【００１９】
更に、本発明の帯域割当方法における他の実勢形態によれば、
入力カードにおいて、同一のカード間パスに属するコネクションのフレームについて、読出しのためのスケジューリングを行い、スケジューリング後のフレームを、前記読出しスケジュールを決定するステップでの対象フレームとすることも好ましい。
【００２０】
更に、本発明の帯域割当方法における他の実勢形態によれば、
回路内の、カード間パスを収容する構成要素を流れるトラフィックを監視し、構成要素の許容帯域を超えるトラフィックが存在する場合には、割当帯域の抑制、及び／又は入力カードに対するトラフィック転送の抑制を行うことも好ましい。
【発明の効果】
【００２１】
カード間パスのトラフィック量に基づき、各カード間パスへの要求帯域を決定し、予め設定された各コネクションの帯域種別及びその帯域値と、要求帯域とに基づき、各カード間パスに割り当てる帯域である割当帯域を決定することで、カード間パス間の公平性を確保しながら帯域使用効率を向上させる効果がある。また、割当帯域調整手段を設けることで、カード間パス間の公平性を確保しながら、割当帯域を最大化して帯域使用効率をより向上させる効果がある。
【００２２】
また、割当帯域の履歴を要求帯域の決定に使用することで、カード間パスに対する不要な帯域割当を減らし、より多くの帯域割当てを必要とするカード間パスへ帯域を分配することができるため、帯域効率を向上させる効果があり、更に、非輻輳状態においても未要求帯域を各カード間パスに分配することで帯域割当における制御遅延を減少させる効果がある。
【００２３】
更に、入力カードにおいて、同一カード間パスに属するコネクション間のスケジューリングを行うことで、カード間パス間及びカード間パスに収容されるコネクション間で、それぞれ割当帯域について帯域設定を満足しながら公平性を確保することができる。つまり、装置全体におけるコネクション間の割当帯域について、公平性を満足できる効果がある。
【００２４】
更に、バックプレッシャ手段を設けることで、カード間パスのトラフィックの実効帯域の揺らぎに起因する不規則なフレーム廃棄により、カード間パスに割り当てる帯域が不公平となることを防止する効果がある。
【発明を実施するための最良の形態】
【００２５】
本発明を実施するための最良の実施形態について、以下では図面を用いて詳細に説明する。
【００２６】
（第１実施形態）  図１は、本発明による分散型帯域割当回路の第１実施形態の機能ブロック図である。図１によると、分散型帯域割当回路は、入力カード１と、フレーム交換部２と、出力カード３と、要求帯域決定部４１と、帯域割当部４２とを備えている。また、入力カード１と、フレーム交換部２は、入力側装置内伝送路５１により接続され、出力カード３と、フレーム交換部２は、出力側装置内伝送路５２により接続され、入力側装置内伝送路５１と、フレーム交換部２と、出力側装置内伝送路５２とにより入力カード１から出力カード３に至るフレームの転送経路、即ちフレーム転送部が構成されている。
【００２７】
図２は、入力カード１及び出力カード３の機能ブロック図である。図２（ａ）によると、入力カード１は、１つ以上の入力ポート１１と、フレーム振分部１２と、スケジュール部１３とを備えており、図２（ｂ）によると、出力カード３は、１つ以上の出力ポート３１と、フレーム振分部３２とを備えている。
【００２８】
符号６は、ある入力カード１から、同一の出力カード３又は出力ポート３１へ転送されるフレームが流れるカード間パスであり、本発明での帯域の割当て対象である。即ち、カード間パス６は、本発明による回路を通過するコネクションのうち、収容される入力カード１と、出力カード３又は出力ポート３１とを共に同一とするコネクションを束ねた論理的なパスである。
【００２９】
分散型帯域割当回路の外部からのフレームは、入力ポート１１で受信されてフレーム振分部１２に出力される。フレーム振分部１２は、フレームの宛先に基づき、フレームを出力カード３又は出力ポート３１ごとに振分を行う。スケジュール部１３は、帯域割当部４２から通知された各カード間パス６の割当帯域に基づき、カード間パス６ごとに振り分けられたフレームの入力側装置内伝送路５１への出力制御を行う。
【００３０】
入力側装置内伝送路５１へ送信されたフレームは、フレーム交換部２で宛先となる出力カード３と接続している出力側装置内伝送路５２へ転送されて、宛先となる出力カード３に到達する。フレーム交換部２は、例えばクロスバスイッチで構成される。
【００３１】
出力側装置内伝送路５２から出力カード３に入力されたフレームは、フレーム振分部３２で、そのフレームの宛先となる出力ポート３１へ振り分けられ、出力ポート３１より分散型帯域割当回路の外部へ送信される。
【００３２】
要求帯域決定部４１は、各カード間パス６のトラフィック状況に基づき、各カード間パス６に必要な帯域である要求帯域を決定して帯域割当部４２に通知する。各カード間パスのトラフィック状況は、フレーム振分部１２で振り分けられたフレームのうち、スケジュール部１３により入力側装置内伝送路５１へ送信されるのを待っているフレーム数や、各カード間パス６上を一定時間内に通過するフレーム数から把握する。図１及び２において、要求帯域決定部４１は、入力カード１のフレーム振分部１２とスケジュール部１３との間にある図示しないバッファに蓄積されているフレーム数と、出力カード３のフレーム振分部３２と出力ポート３１との間にある図示しないバッファに蓄積されているフレーム数と、入力側装置内伝送路５１と、出力側装置内伝送路５２を通過するフレーム数からトラフィック状況を取得しているが、これは例示であり、これら総ての点で同時に監視する必要はなく、どれか１つ、あるいは、任意の監視点を組み合わせて使用でき、また、他の監視点を使用することも可能である。
【００３３】
帯域割当部４２は、外部より予め設定された各コネクション又はカード間パスの設定値と、要求帯域決定部４１が決定した要求帯域とに基づき、実際に各カード間パス６に割り当てる割当帯域を決定して各入力カード１に通知する。各カード間パス６の設定値とは、帯域種別とその帯域値からなり、各カード間パス６には同時に複数の帯域種別を規定できる。帯域種別としては、例えば、固定帯域、保証帯域、非保証帯域があり、固定帯域が設定されている場合は、要求帯域の有無に係らず固定帯域の帯域値の優先的な割当てを行う。保証帯域が設定されている場合は、要求帯域から固定帯域を引いた値を保証帯域として割り当てるが、要求帯域から固定帯域を引いた値が保証帯域の帯域値より大きい場合には保証帯域の帯域値を割り当てる。非保証帯域が設定されている場合は、要求帯域から固定帯域及び保証帯域を引いた値を非保証帯域として割り当てるが、要求帯域から固定帯域及び保証帯域を引いた値が非保証帯域の帯域値より大きい場合には非保証帯域の帯域値を割り当てる。ただし、輻輳等の要因により、非保証帯域の割り当てを減少させることがある。固定帯域、保証帯域、非保証帯域の各帯域値の総和が、カード間パスに対して割り当て可能な最大帯域となる。
【００３４】
同一の入力側装置内伝送路５１、同一の出力側装置内伝送路５２又はフレーム交換部２に収容されるカード間パス６の要求帯域の総和が、それぞれの許容できる帯域を超える場合、帯域分配比に基づく比例分配を行い、各カード間パス６に対する公平な帯域分配を実現する。カード間パス６へ非保証帯域を比例分配することにより、カード間パスの要求帯域又は最大帯域を超過する場合には、超過分の帯域を帯域分配比に基づき、分配帯域が要求帯域に満たない他のカード間パス６に対して再分配を行う。この再分配処理を複数回繰り返すことにより、帯域使用効率を向上させることができる。
【００３５】
また、帯域割当部４２は、例えば、同一の入力側装置内伝送路５１に収容されるカード間パス６に割り当てようとする帯域の総和が、収容する入力側装置内伝送路５１の許容できる帯域を超える場合、割り当てようとする帯域から非保証帯域などの優先度の低い帯域を、各カード間パス６から公平に減らし、収容する入力側装置内伝送路５１が許容できる帯域に、その総和を抑えた上で割当帯域を決定する。前記処理は、フレーム交換部２や、出力側装置内伝送路５２や、出力ポート３１等、複数のカード間パス６を収容する構成要素であって、許容帯域の上限があるもの総てについて実行する。
【００３６】
スケジュール部１３は、割当帯域に基づきフレーム読出しのタイミングの決定、即ち、スケジューリングを行う。スケジューリング法としては、ＷＦＱ、ＷＲＲ、ＤＲＲ等の公平な分配を行うアルゴリズムを適用することができる。例えば、一定周期内において、カード間パス６への割当帯域に比例するタイムスロットを、カード間パス６ごとに均等な間隔で分散配置する。複数のカード間パス６の間で分散配置したタイムスロット位置が重複した場合には、該当タイムスロットを許容可能な範囲内で前後に移動させる。この方法を図７（ａ）に示す。また、タイムスロットを分散させるときに、一定期間内の複数のタイムスロットをまとめてブロック化し、タイムスロットをブロックに対して均等分散させることでスケジューリング処理を簡易化することができる。この様子を図７（ｂ）に示す。更に、別の例としては、各カード間パス６に割り当てることのできるタイムスロット数をカウンタ値として与え、カード間パス６ごとに備えるカウンタを順次減算することによりスケジューリングすることもできる。但しこの方法を用いる場合、帯域を割り当てる周期が長いと、カード間パス６に割り当てられるタイムスロットの並びがバーストとなる可能性があるので、上記例と同様に周期内を複数のタイムスロットのブロックに分割し、ブロックごとにカウンタ減算によるスケジューリングを実施することが望ましい。この様子を図８に示す。
【００３７】
本発明による帯域割当フロー、即ち、要求帯域決定部４１によるトラフィック情報の収集に始まり、要求帯域決定部４１による要求帯域の決定、帯域割当部４２による割当帯域の決定を経て、スケジュール部１２による割当帯域結果の反映、つまり、スケジューリングの実行を、１フレームが通過する時間程度で実行できない場合には、一定周期内で帯域割当フローにおけるそれぞれの処理を実行する周期処理を行う。図９に帯域割当フローの周期処理へのマッピング例を示す。
【００３８】
以上、本実施形態では、カード間パス６間の公平性を確保しながら帯域使用効率を向上させる効果がある。
【００３９】
（第２実施形態）  図３は、本発明による分散型帯域割当回路の第２実施形態の機能ブロック図である。尚、以後の説明において既に説明したものと同じ機能ブロックには同一の符号を付与して説明は省略する。図３によると、分散型帯域割当回路は、図１に示す構成に対し、帯域割当調整部４３が追加されている。
【００４０】
第１実施形態においては、入力側装置内伝送路５１や、出力側装置内伝送路５２といった、複数のカード間パス６が束ねられる箇所においては、束ねられるカード間パス６に割り当てようとする帯域の総和が、束ねられている箇所で許容できる帯域を超過する場合には、許容できる帯域以下となるように割り当てようとする帯域を減少させた上で、割当帯域を決定していた。しかしながら、例えば、入力側装置内伝送路５１の許容帯域の超過により、カード間パス６に割り当てる帯域を減少させた場合、減少させたカード間パス６を収容している出力側装置内伝送路５２では、逆に割り当てることができる帯域に余りが生じる場合がある。
【００４１】
帯域割当調整部４３は、上述したように、回路内において、複数のカード間パス６を収容する各構成要素の許容帯域と、それぞれの構成要素に収容されるカード間パス６の割当帯域の総和を比較し、許容帯域が大きい場合には、余った帯域の分配処理を行う。このとき、例えば、帯域の余りが、他の構成要素の許容帯域の超過を避けるために、カード間パス６の割当帯域を減少させたことにより生じたものである場合には、減少させたカード間パス６以外のカード間パス６に、余りの帯域を再分配する。このため、帯域割当調整部４３は、帯域割当部４２が出力する割当帯域を入力として再分配のための調整結果を帯域割当部４２に出力する。
【００４２】
帯域の再分配方法は、帯域割当部４２における帯域の再分配と同等の方法を用いることができる。カード間パス６の割当帯域が変更された場合には、変更されたカード間パス６が収容される入力側装置内伝送路５１や、出力側装置内伝送路５２等の帯域の余りを確認し、余りが生じた場合には帯域割当調整部４３は再分配処理を実施する。再分配処理のトリガとなったカード間パス６には再分配されないため、再分配処理を複数回繰り返すことで帯域割当結果は集束する。
【００４３】
以上、本実施形態では、カード間パスの公平性を確保しながら、割当帯域を最大化して帯域使用効率をより向上させる効果がある。
【００４４】
（第３実施形態）  図４は、本発明による分散型帯域割当回路の第３実施形態の機能ブロック図である。図４によると、分散型帯域割当回路は、図１の構成に対し、履歴保持部４４が追加されている。
【００４５】
履歴保持部４４は、帯域割当部４２が出力した割当帯域を入力して、各カード間パス６に割り当てた割当帯域の履歴を保持する。第１実施形態において、要求帯域決定部４１は、フレーム蓄積状況や、各部からのトラフィック量に基づいて要求帯域を決定していたが、本実施形態においては、更に、履歴保持部４４が保持する割当帯域の履歴も要求帯域の決定に使用する。つまり、過去の履歴から要求帯域を予測する。予測した要求帯域と、実際に使用された帯域を比較することにより帯域の過不足を検知することができ、カード間パス６が必要としている帯域をより正確に決定することができる。また、要求帯域を予測することにより、入力側装置内伝送路５１や、出力側装置内伝送路５２といった、カード間パス６を束ねている場所における輻輳の有無を予測できるので、どのカード間パス６からも要求されない、余った帯域を各カード間パス６に再分配することにより、予測ミスに対するマージンとすることができる。また、余った帯域を分配することにより、急激なトラフィックの変動に対して帯域割当のための遅延時間を減少させることができる。
【００４６】
また、履歴保持部４４に各カード間パスのトラフィック状況の履歴を保存させ、要求帯域決定部４１が、カード間パスのトラフィック状況の履歴も要求帯域の決定に使用する構成としても良く、更に、割当帯域の履歴及びカード間パスのトラフィック状況の履歴の両方を使用する構成であっても良い。履歴保持部４４は、カード間パスの履歴を、トラフィック状況を直接監視することで、又は、要求帯域決定部４１より取得する。
【００４７】
以下に、予測を行った場合における要求帯域予測処理と帯域分配処理の具体的な動作例を説明する。帯域割当に用いる制御周期は、図９に示すモデルを使用する。
【００４８】
周期（ｔ−２）に割り当てた帯域Ａ＿ＢＷ（ｔ−２）と、使用帯域Ｕ＿ＢＷ（ｔ−２）を基に、周期（ｔ）に割り当てるべき帯域を要求帯域Ｒ＿ＢＷ（ｔ）として予測する。
【００４９】
まず、既割当帯域の過不足の確認を行う。周期（ｔ−２）に割り当てた帯域Ａ＿ＢＷ（ｔ−２）と使用帯域Ｕ＿ＢＷ（ｔ−２）を比較し、割り当てた帯域Ａ＿ＢＷ（ｔ−２）が大きければ、割当帯域が過剰と判断し、次の要求帯域Ｒ＿ＢＷ（ｔ）を使用帯域Ｕ＿ＢＷ（ｔ−２）と等しくする。一方、割り当てた帯域Ａ＿ＢＷ（ｔ−２）と使用帯域Ｕ＿ＢＷ（ｔ−２）が等しく、かつ、フレーム蓄積がある場合は、割当帯域が不足していると判断し、使用帯域Ｕ＿ＢＷ（ｔ−２）に、蓄積されているキュー数、蓄積フレーム数、コネクションの設定帯域比を勘案した割増帯域を加算した値を、次の要求帯域Ｒ＿ＢＷ（ｔ）とする。例えば、カード間パス６ごとに有効な、つまり、通信を行っているコネクションの重みの総和をＷ（ｔ−２）とし、ａを定数とすると、Ｒ＿ＢＷ（ｔ）＝Ｕ＿ＢＷ（ｔ−２）＋Ｗ（ｔ−２）×ａとすることができる。
【００５０】
また、固定帯域Ｆ＿ＢＷ（ｔ）を設定した場合、常に固定帯域以上の帯域が割り当てられるようにするため、要求帯域Ｒ＿ＢＷ（ｔ）が固定帯域Ｆ＿ＢＷ（ｔ）より小さくならないように補正する。
【００５１】
上記の予測法により求めた要求帯域Ｒ＿ＢＷ（ｔ）を使用した、割当帯域Ａ＿ＢＷ（ｔ）を決定する。まず、出力ポート３１において、帯域制限などを考慮したときに、予測したＲ＿ＢＷ（ｔ）が割当可能か判別する。これは、着目する出力ポート３１におけるカード間パス６の要求帯域の総和ΣＲ＿ＢＷ（ｔ）と、当該出力ポート３１の最大帯域ＭＡＸ＿ＢＷを比較することにより判別できる。
【００５２】
輻輳している場合、つまり、ΣＲ＿ＢＷ（ｔ）が最大帯域ＭＡＸ＿ＢＷより大きい場合は、各カード間パス６の要求帯域Ｒ＿ＢＷ（ｔ）をそのまま割り当てることはできないので、まず優先的に固定帯域Ｆ＿ＢＷ（ｔ）を分配する。残りの帯域は、カード間パス６で経路ごとに有効な、つまり通信を行っているコネクションの重みの総和Ｗ（ｔ−２）により比例分配する。カード間パス６に分配した帯域Ｄ＿ＢＷ（ｔ）が要求帯域Ｒ＿ＢＷ（ｔ）を超過する場合には、超過分を他の要求帯域を満たしていないカード間パス６に再分配する。この再分配処理を複数回行うことで無効な割当が減少するので、帯域の使用効率を向上させることができる。一方、輻輳していない場合、つまり、ΣＲ＿ＢＷ（ｔ）が最大帯域ＭＡＸ＿ＢＷ以下である場合は、未割当の帯域が存在する。この未割当の帯域を未要求帯域Ｅ＿ＢＷ（ｔ）と呼び、当該出力ポート３１に収容されている全カード間パス６に均等分配する。よって、各カード間パスに割り当てる帯域Ａ＿ＢＷ（ｔ）は、Ｄ＿ＢＷ（ｔ）＋Ｅ＿ＢＷ（ｔ）として表すことができる。図１０は、非輻輳時の帯域分配の例を示す図である。
【００５３】
本実施形態では、カード間パス６に対する不要な帯域割当を減らし、より多くの帯域割当てを必要とするカード間パス６へ帯域を分配することができるため、帯域効率を向上させる効果があり、更に、非輻輳状態においても未要求帯域を各カード間パス６に分配することで帯域割当における制御遅延を減少させる効果がある。
【００５４】
（第４実施形態）  図５は、本発明による分散型帯域割当回路の第４実施形態での入力カード１の機能ブロック図である。図５によると、入力カードは、コネクション毎に設けられるバッファ１６と、カード間パス６ごとに設けられ、同一カード間パス６に収容されるコネクションのスケジューリングを行うコネクション帯域スケジュール部１５とを有する。
【００５５】
帯域割当部４２は、カード間パス６に対して帯域を割り当てる。カード間パスは複数のコネクションを収容することができるが、帯域割当部４２及びスケジュール部１３は、カード間パス６に収容されているコネクション間については、割り当てられる帯域の公平性を保証しない。カード間パス６をコネクションに分割し、カード間パス６をコネクションと等価とすることも可能であるが、この場合にはカード間パス６の増大につながり、結果、帯域割当処理の処理時間が増加し、よって、図９に示す制御周期及び制御遅延処理時間が長くなってしまう。したがって、本実施形態においては、カード間パス６に収容されるコネクション間での帯域分配を入力カード１において実行する。
【００５６】
フレーム振分部１２により、入力フレームは、カード間パス６のコネクションごとに振り分けられ、対応するバッファ１６に蓄積される。コネクション帯域スケジュール部１５は、カード間パス６ごとに設けられ、対応するカード間パス６に収容されるコネクションのフレームの、バッファ１６からの読出し順序を決定する。コネクション帯域スケジュール部１５によるスケジューリング方法は、スケジュール部１３と同様、ＷＦＱ、ＷＲＲ、ＤＲＲ等の公平な分配を行うアルゴリズムを適用することができる。
【００５７】
同一カード間パス６に収容されているコネクション間の帯域割当を入力カード１内で実施することにより、バッファ１６におけるフレームの有無と、コネクション帯域スケジュール部１５のスケジューリングテーブルのみでスケジューリングを行うことができる。これにより、帯域制御に要する時間を短縮できるので、フレーム単位での帯域制御が容易となり、よりダイナミックなトラフィックの変動に帯域割当が追従できるようになる。
【００５８】
以上、本実施形態では、カード間パス６間及びカード間パス６に収容されるコネクション間で、それぞれ割当帯域について帯域設定を満足しながら公平性を確保することができる。つまり、装置全体におけるコネクション間の割当帯域について、公平性を満足できる効果がある。
【００５９】
（第５施形態）  図６は、本発明による分散型帯域割当回路の第５実施形態の機能ブロック図である。図６によると、分散型帯域割当回路は、図１の構成に対し、バックプレッシャ部４５が追加されている。
【００６０】
帯域割当部４２は、入力側装置内伝送路５１や、出力側装置内伝送路５２といった、複数のカード間パス６が束ねられている箇所、つまり集線箇所において、束ねられているカード間パス６の総和が、集線箇所ごとの許容帯域を超過しないように割当帯域を決定する。しかし、カード間パス６の割当帯域を決定したのみでは、フレームの送出タイミングは決まらないので、異なるカード間パス６からのフレームの送出タイミングが重複する、つまり、同時に集線箇所に、異なるカード間パス６のフレームが入力されようとすることが生じ得る。複数のフレームを同時に転送することはできないので、フレームは集線される前段でバッファリングされる。入力カード１のスケジュール部１３のシェーピング精度が低いことや、可変長フレームによるフレーム長の変動などは、バッファのキュー長を伸張させる要因となる。キュー長がバッファ長を超過してフレーム廃棄が発生すると、カード間パス６に割り当てた帯域の公平性が崩れる。ただし、この帯域超過現象は、カード間パス６のトラフィックの実効帯域の揺らぎによる一時的な現象であり、帯域計算に時間のかかる帯域割当部４２によって割当帯域を抑制することは適当でない。このため、本実施形態においては、バックプレッシャ部４５を設けている。
【００６１】
バックプレッシャ部４５は、回路内の、複数のカード間パス６を収容する構成要素を流れるトラフィックを監視し、構成要素の許容帯域を超えるトラフィックが存在する場合には、帯域割当部４２に対して割当帯域の抑制を指示する。具体的には、カード間パス６が束ねられる前段に設けられるバッファのキュー長を監視し、キュー長が帯域抑制閾値を超えた場合には、入力されるトラフィックを抑制するため、帯域割当部４２に帯域抑制を指示し、帯域割当部４２は、対応するスケジュール部１３の割当帯域を減少、即ち、バックプレッシャをかけてバッファ溢れを防止する。その後、キュー長が減少して帯域抑制閾値以下になった場合にはバックプレッシャを解除する。
【００６２】
尚、バックプレッシャ部４５は、帯域割当部４２に対する割当帯域の抑制指示に替えて、入力カード１に対するトラフィック転送の抑制指示を行っても良く、更に、帯域割当部４２に対する割当帯域の抑制指示と、入力カード１に対するトラフィック転送の抑制指示を併用しても良い。入力カード１に対するトラフィック転送の抑制指示では、一般的に帯域抑制のための計算量が少ないので高速な帯域抑制を行うことができる。
【００６３】
バックプレッシャをかけることで、カード間パス６の割当帯域が一時的に減少させられるが、割当帯域の減少分の分配方法としては、輻輳箇所を経由する総てのカード間パス６に対して均等とする方法や、設定帯域値の帯域比等に基づき比例配分する方法や、トラフィック量に比例させる方法などがある。
【００６４】
また、バックプレッシャによって割当帯域が抑制された場合に、スケジュール部１３が転送対象フレームの保証・非保証や優先度を識別することにより、優先して転送するフレームを保護することができる。これは、フレームに保証・非保証・優先度を示すマーキングを行ったり、スケジュール部１３にクラスバッファ及び優先読出制御を備えたりすることで実現できる。
【００６５】
バースト的なトラフィックが断続的に入力されるなどにより、入力カードに対する一時的なトラフィック転送の抑制が頻発する場合には、帯域割当部４２に対して割当帯域を抑制させることによりフレーム廃棄を防止する。
【００６６】
以上、本実施形態では、カード間パス６のトラフィックの実効帯域の揺らぎに起因する不規則なフレーム廃棄により、カード間パス６に割り当てる帯域が不公平となることを防止する効果がある。
【図面の簡単な説明】
【００６７】
【図１】本発明による分散型帯域割当回路の第１実施形態の機能ブロック図である。
【図２】入力カード及び出力カードの機能ブロック図である。
【図３】本発明による分散型帯域割当回路の第２実施形態の機能ブロック図である。
【図４】本発明による分散型帯域割当回路の第３実施形態の機能ブロック図である。
【図５】本発明による分散型帯域割当回路の第４実施形態での入力カードの機能ブロック図である。
【図６】本発明による分散型帯域割当回路の第５実施形態の機能ブロック図である。
【図７】スケジューリング方法の例を示す図である。
【図８】スケジューリング方法の他の例を示す図である。
【図９】帯域割当フローの周期処理へのマッピングを示す図である。
【図１０】非輻輳時の帯域分配の例を示す図である。
【符号の説明】
【００６８】
１  入力カード
１１  入力ポート
１２  フレーム振分部
１３  スケジュール部
１５  コネクション帯域スケジュール部
１６  バッファ
２  フレーム交換部
３  出力カード
３１  出力ポート
３２  フレーム振分部
４１  要求帯域決定部
４２  帯域割当部
４３  帯域割当調整部
４４  履歴保持部
４５  バックプレッシャ部
５１  入力側装置内伝送路
５２  出力側装置内伝送路
【図１】
2007134779.tif 000003
【図２】
2007134779.tif 000004
【図３】
2007134779.tif 000005
【図４】
2007134779.tif 000006
【図５】
2007134779.tif 000007
【図６】
2007134779.tif 000008
【図７】
2007134779.tif 000009
【図８】
2007134779.tif 000010
【図９】
2007134779.tif 000011
【図１０】
2007134779.tif 000012