(57)【要約】【課題】帯域を公平に割り当てつつ実装が容易である単一のバッファを使った帯域割当方法を提供する。【解決手段】複数のフローのパケットを全て到着順に１つのキューバッファに収容し、キューバッファの先頭のパケットから順に出力する複数のフローのトラフィックを多重する方法において、輻輳状態においてパケットを廃棄する場合、キューバッファ内のフローごとのパケット数がフローに予め割り当てられた帯域に比例するように廃棄パケットを選択し、そのパケットを廃棄する。【選択図】図３
2010193142.tif 000002
【特許請求の範囲】
【請求項１】
複数のフローのパケットを全て到着順に１つのキューバッファに収容し、該キューバッファの先頭のパケットから順に出力することにより、複数のフローのトラフィックを多重する方法において、
前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのパケット数が該フローの割当帯域に比例するように、パケットを廃棄する廃棄ステップを含むことを特徴とする複数のフローのトラフィックを多重する方法。
【請求項２】
前記廃棄ステップは、
前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのデータ量を該フローの割当帯域で除算した値が最大となるフローを選択し、該選択したフローの最後尾のパケットを廃棄するステップであることを特徴とする請求項１に記載の複数のフローのトラフィックを多重する方法。
【請求項３】
複数のフローのパケットを全て到着順に１つのキューバッファに収容し、該キューバッファの先頭のパケットから順に出力することにより、複数のフローのトラフィックを多重する多重化装置において、
各フローの割当帯域が設定されているフロー別帯域設定テーブルと、
前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのパケット数が該フローの割当帯域に比例するように、パケットを廃棄する廃棄パケット選択部と、
を備えていることを特徴とする多重化装置。
【請求項４】
前記廃棄パケット選択部は、
前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのデータ量を該フローの割当帯域で除算した値が最大となるフローを選択し、該選択したフローの最後尾のパケットを廃棄することを特徴とする請求項３に記載の多重化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、図１に示すように、複数のユーザのトラフィックを多重する機能を有する通信装置にかかわる発明であって、トラフィックを多重するときに単一のＦＩＦＯキューバッファを使って簡易に各ユーザに帯域を公平に割り当てる方法および多重化装置を提供する。
【背景技術】
【０００２】
パケット通信網では、数多くのユーザの数多くのフローを一つの網で多重して伝送するので、複数のフローのトラフィックを多重する多重化装置が必要である。多重化装置は通常、スイッチやルータとして実現されている。多重化装置は各フローを多重化する際、各フローに設定されたＱｏＳ要求を満足するように多重化する必要がある。ＱｏＳ要求には例えば帯域がある。イーサネット（登録商標）アクセス網においては、複数のユーザを収容するイーサネット（登録商標）スイッチが設けられることがあるが、各ユーザからのトラフィックを多重化するとき、各ユーザには公平に帯域を割り当てる必要がある。ここでの公平とは、予め契約された割当帯域になるように割り当てることである。たとえあるユーザが契約帯域を超えるようなトラフィックを送信しても、他のユーザに悪影響を与えないような制御が必要である。複数入力トラフィックを多重する多重化装置１の構成例を図２に示す。本構成例では、フローごとにパケットを一時的に格納するためのキューバッファ３が複数設けられている。フロー別帯域設定テーブル２には、各フローの割当帯域が設定されており、スケジューラ４がフロー制御に使用する。スケジューラ４はある規則に従ってキューバッファの先頭からパケットを取り出して出リンクに出力する。フローごとに予め設定されている帯域を超えたトラフィックは廃棄される場合がある。パケット網の多重装置でのトラフィック制御は、入力されたパケットを出力する順序を決定するスケジューリング手法のことである。
【０００３】
パケットのスケジューリング手法として、例えば、ＷＦＱ（Weighted Fair Queuing）やＦＩＦＯ（First In First Out）がある。
【０００４】
ＷＦＱスケジューリングにおけるパケット送出順序は、参照ゲートウェイのＦＦＱ（Fluid Fair Queuing）ゲートウェイで最も早く送出が完了するフレームを送出する、というものである。ＦＦＱゲートウェイの動作は、各フローの先頭のパケットを、出リンクの容量を各フローの割当帯域で按分した帯域で出力する、というものである。つまり、あたかも帯域が確保された専用線を各フローが有しているかのように、パケットを出力する。実際は、出リンクは一つしか存在しないので、複数のパケットを同時に出力することは出来ず、ＦＦＱゲートウェイはあくまで仮想的なものである。
【０００５】
また、ＦＩＦＯスケジューリングは全てのフローのパケットを到着順に一つのキューに収容し、そのＦＩＦＯキューの先頭から順に出力する、というものである。ＦＩＦＯの特長は、実装が簡単なことである。これらの手法の詳細は、例えば、非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】戸田巌、ネットワークＱｏＳ技術、オーム社、２００１
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のＷＦＱスケジューリングは、比較的公平な帯域割当が可能ではあるが、ＦＦＱゲートウェイのシミュレーションを同時に実行する必要があり、非常に多大な計算量を必要とするため、実用的ではない。
【０００８】
また、ＦＩＦＯスケジューリングでは、入力されたトラフィックをそのまま出力するので、ＷＦＱとは異なり、帯域を公平に割り当てることはできない。入力トラフィック量が比較的少なく、出リンク容量に余裕があれば、全ての入力トラフィックを出力できるため、特には問題にならない。しかし常にこのような状態が維持されてることは考えにくい。入力トラフィックの合計が出リンク容量の帯域を超えるような輻輳状態においては、より多くのトラフィックを送信したユーザがより多くの割り当て帯域を得られることになり、著しい不公平を招く。
【０００９】
したがって、本発明は帯域を公平に割り当てつつ実装が容易である単一のバッファを使った帯域割当方法および多重化装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を実現するため本発明による複数のフローのトラフィックを多重する方法は、、複数のフローのパケットを全て到着順に１つのキューバッファに収容し、該キューバッファの先頭のパケットから順に出力することにより、複数のフローのトラフィックを多重する方法において、前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのパケット数が該フローの割当帯域に比例するように、パケットを廃棄する廃棄ステップを含む。
【００１１】
また、前記廃棄ステップは、前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのデータ量を該フローの割当帯域で除算した値が最大となるフローを選択し、該選択したフローの最後尾のパケットを廃棄するステップであることも好ましい。
【００１２】
上記目的を実現するため本発明による多重化装置は、複数のフローのパケットを全て到着順に１つのキューバッファに収容し、該キューバッファの先頭のパケットから順に出力することにより、複数のフローのトラフィックを多重する多重化装置において、各フローの割当帯域が設定されているフロー別帯域設定テーブルと、前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのパケット数が該フローの割当帯域に比例するように、パケットを廃棄する廃棄パケット選択部とを備えている。
【００１３】
また、前記廃棄パケット選択部は、前記キューバッファ内のキュー長が所定の閾値を超えた場合に、前記キューバッファ内のフローごとのデータ量を該フローの割当帯域で除算した値が最大となるフローを選択し、該選択したフローの最後尾のパケットを廃棄することも好ましい。
【発明の効果】
【００１４】
本発明によって、輻輳状態において帯域の公平な割り当てを実現することが簡易な方法で可能になる。本発明に必要な計算量はフローの数に比例する程度であり、実現は容易である。また、本発明では、キューバッファを一つしか用いない。一方、ＷＦＱではフローごとのキューバッファが必要である。つまり、本発明はフローごとにキューバッファを必要とする他の方法に比べて、ハード量を節約できる。
【図面の簡単な説明】
【００１５】
【図１】通信システムの構成を示す。
【図２】従来技術の複数入力トラフィックを多重する多重化装置の構成例を示す。
【図３】本発明によるＦＩＦＯキューを用いた公平帯域割り当てを実現するための多重化装置の構成例を示す。
【図４】パケットの構造例を示す。
【図５】バッファ内のデータ構造例を示す。
【図６】パケット廃棄アルゴリズム例を示す。
【図７】割当帯域と出力データの偏差を示す。
【図８】単純なＦＩＦＯゲートウェイでのフローごとの出力データレートを示す。
【発明を実施するための形態】
【００１６】
スケジューリング手法への要求条件は、帯域を公平に割り当てつつ実装が容易であることである。そこで、実装を簡易にするためにＦＩＦＯゲートウェイにおける単一キューを利用し、更に、ＷＦＱの考え方を取り入れた帯域割当方法を実現すればよい。
【００１７】
輻輳状態において、ＦＩＦＯキューを用いてＷＦＱスケジューリングと同一の帯域割当を実現する方法を考える。本来スケジューリングは、送出する順序の決定機構であるが、ＦＩＦＯでの送出順序をＷＦＱと同一にするのは困難である。そこで、パケットの廃棄を適切に行うことによってＷＦＱに近い帯域割当を実現することを考える。もしＷＦＱでのパケット廃棄と同一のパケット廃棄を実現出来れば、結果として、出力されるパケットのトラフィックは、ＷＦＱと同一になる。
【００１８】
ＷＦＱゲートウェイのキューバッファから出力されるのが比較的早いパケットは、パケットの格納位置がキューバッファの先頭に近くて、フローに割り当てられている帯域が大きい場合である。逆に、輻輳状態においてより廃棄されやすいパケットというのは、出力されるのが遅いパケットである。つまり、パケットの格納位置がキューバッファの最後尾に近くてフローの割当帯域が少ないと、そのパケットは廃棄されやすい、ということになる。そこで、パケット廃棄規則として、キューバッファ内で待ち合わせているパケット数が、割り当て帯域に比べて大きいフローから優先してパケットを廃棄することにする。こうすることにより、ＷＦＱスケジューリングで出力される可能性が低いパケットを優先して廃棄するので、結果として、ＷＦＱスケジューリングで出力される可能性が高いパケットが残留し、出力される帯域が、ＷＦＱに近似したものになるはずである。
【００１９】
本発明によるＦＩＦＯキューを用いた公平帯域割り当てを実現するための多重化装置の構成例を図３に示す。本構成例では、フローごとにパケットを一時的に格納するためのキューバッファ３が一つ設けられている。入力されたパケットは一つのキューバッファ３に格納される。入力トラフィックが出リンク容量に比べて過大である輻輳状態においては、キューバッファ３が溢れるためパケットを廃棄する必要がある。フロー別帯域設定テーブル２には、各フローの割当帯域が設定されており、廃棄パケット選択部５が、その割当帯域とキューバッファ内のフローごとのキュー長に基づいて廃棄するパケットを選択し、パケットを廃棄する。フローごとのキュー長は、入力したパケット数と出力したパケット数と廃棄したパケット数とをフローごとに計測することによって得ることができる。パケットの構造例を図４に示す。パケットはヘッダ部とデータ部から構成され、ヘッダ部に基づいてパケットが属するフローを識別する。例えば、ユーザがＴＣＰ／ＩＰを使ってデータの送受信を行う場合、ヘッダ部のＩＰアドレスとＴＣＰポート等の情報に基づいてフローを識別する。あるいは、パケットをキューバッファ３内に格納する際に、どのフローに属するかを示す識別子を付与しておき、必要なときにキューバッファ３内の識別子の個数をフローごとに計数することによって得る方法も考えられる。パケットに識別子を付与してバッファに格納するときのバッファ内のデータ構造の例を図５に示す。識別子とフローとを１対１に対応させ、キューバッファ３内の識別子の個数を数えることにより、フローのパケット数を知ることができる。
【００２０】
廃棄パケット選択部５は、キューバッファ３内のフローごとのパケット数がフローに予め割り当てられた帯域に比例するように廃棄パケットを選択する。例えば、キューバッファ３内のフローごとのキュー長をそのフローの割当帯域で除したものが最大のフローの最後尾のパケットとする。パケット廃棄アルゴリズムの例を図６に示す。
【００２１】
Ｓ１．多重化装置１にパケットが到着した場合、Ｓ２に移る。
Ｓ２．多重化装置１は、パケットをキューバッファ３に格納する。
Ｓ３．多重化装置１は、キューバッファ３のキュー長が閾値以下か確認する。閾値以下の場合Ｓ１に移り、閾値を超えていた場合Ｓ４に移る。
Ｓ４．廃棄パケット選択部５は、フロー別の帯域設定テーブル２の各フローの割当帯域および各フローのキュー長に基づいて廃棄するパケットを選択し、そのパケットを廃棄する。具体的には、（キューバッファ内のフローのキュー長÷フローの割当帯域）が最大のフローを見つけ、そのフローの最後に格納されたパケットの廃棄を選択し、そのパケットを廃棄する。
【００２２】
提案手法の効果を評価するために、数値シミュレーションを実施した。シミュレーションモデルは、フロー数が１０００、予め設定された割当帯域は、２５０のフローが１Ｍｂｉｔ／ｓ、２５０のフローが２Ｍｂｉｔ／ｓ、２５０のフローが３Ｍｂｉｔ／ｓ、２５０のフローが４Ｍｂｉｔ／ｓとした。ゲートウェイの出リンク容量は割当帯域の合計である２．５Ｇｂｉｔ／ｓとした。パケットの入力は、ポワソン到着とし、入力データレートを全て５Ｍｂｉｔ／ｓとした。パケット長は６４バイト以上１５１８バイト以下の一様分布の確率変数とした。１０００秒間のシミュレーションを実施し、ゲートウェイからの出力データ量を各フローについて計測した。出力データレートと割当帯域の偏差を、横軸をフロー番号にしてプロットしたものを図７に示す。グラフから分かるように、ほぼ公平な帯域割り当てを実現できている。
【００２３】
上記手法を適用しない場合の単純なＦＩＦＯゲートウェイでの同様なシミュレーション結果を図８に示す。ＦＩＦＯゲートウェイは割当帯域を使用していないので、図８ではデータレートそのものを表示している。図８から分かるように、各フローのデータレートは２．５Ｍｂｉｔ／ｓの近傍であり、帯域制御ができていない。
【００２４】
また、以上述べた実施形態は全て本発明を例示的に示すものであって限定的に示すものではなく、本発明は他の種々の変形態様および変更態様で実施することができる。従って本発明の範囲は特許請求の範囲およびその均等範囲によってのみ規定されるものである。
【符号の説明】
【００２５】
１  多重化装置
２  フロー別帯域設定テーブル
３  キューバッファ
４  スケジューラ
５  廃棄パケット選択部
【図１】
2010193142.tif 000003
【図２】
2010193142.tif 000004
【図３】
2010193142.tif 000005
【図４】
2010193142.tif 000006
【図５】
2010193142.tif 000007
【図６】
2010193142.tif 000008
【図７】
2010193142.tif 000009
【図８】
2010193142.tif 000010