(57)【特許請求の範囲】
【請求項１】
フロー毎の情報を管理するエッジルータとフロー毎の情報を管理しないコアルータから構成されるコアステートレスネットワークで、
エッジルータの入力部にパケットが到着した時に、そのパケットを送出しているユーザの送信レートを測定し、その値をＩＰパケットのヘッダに書き込み、エッジルータ及びコアルータの出力部にパケットが到着した時に、ヘッダに書き込まれたレート値と各ルータが独自に計算している公平帯域値を比較することにより、そのパケットをバッファに入力するかどうかの判断を行うスケジューリング法において、
エッジルータ及びコアルータの出力部にパケットが到着した時に、到着したパケットのサイズをクレジット１に加算し、到着したパケットのヘッダに書き込まれたレート値がマックスレート値より大きいか比較し、大きいならばマックスレートの値を到着したパケットのヘッダに書き込まれたレート値にし、
現在の公平帯域値を到着したパケットのヘッダに書き込まれたレート値で割った値Ｐを計算し、確率Ｐで、到着したパケットのサイズをクレジット２に加算し、
エッジルータ及びコアルータの出力部にパケットが到着した時に、その到着時刻から記録している時刻を減算した値が予め定めている時間以上ならば、クレジット１を用いてレート1を、クレジット２を用いてレート２を計算し、
レート１がリンク帯域以上ならば、（現在の公平帯域値＊リンク帯域）をレート２で除算した値とリンク帯域の小さい方を新しい公平帯域値とし、リンク帯域以下ならば、マックスレート値を新しい公平帯域値とし、
新しい公平帯域値を決定した後、クレジット１、クレジット２、マックスレートの値を０にし、記録している時刻を現在の時刻にすることを特徴とする公平帯域計算法。
【請求項２】
フロー毎の情報を管理するエッジルータとフロー毎の情報を管理しないコアルータから構成されるコアステートレスネットワークで、
エッジルータの入力部にパケットが到着した時に、そのパケットを送出しているユーザの送信レートを測定し、その値をＩＰパケットのヘッダに書き込み、エッジルータ及びコアルータの出力部にパケットが到着した時に、ヘッダに書き込まれたレート値と各ルータが独自に計算している公平帯域値を比較することにより、そのパケットをバッファに入力するかどうかの判断を行うスケジューリング法を用いたルータにおいて、
出力部にパケットが到着した時に、到着したパケットのサイズをクレジット１に加算し、到着したパケットのヘッダに書き込まれたレート値がマックスレート値より大きいか比較し、大きいならばマックスレートの値を到着したパケットのヘッダに書き込まれたレート値にする手段と、
現在の公平帯域値を到着したパケットのヘッダに書き込まれたレート値で割った値Ｐを計算し、確率Ｐで、到着したパケットのサイズをクレジット２に加算する手段と、
出力部にパケットが到着した時に、その到着時刻から記録している時刻を減算した値が予め定めている時間以上ならば、クレジット１を用いてレート１を、クレジット２を用いてレート２を計算し、
レート１がリンク帯域以上ならば、（現在の公平帯域値＊リンク帯域）をレート２で除算した値とリンク帯域の小さい方を新しい公平帯域値とし、リンク帯域以下ならば、マックスレート値を新しい公平帯域値とし、
新しい公平帯域値を決定した後、クレジット１、クレジット２、マックスレートの値を０にし、記録している時刻を現在の時刻にする手段と、
を備えたことを特徴とするルータ。
【請求項３】
フロー毎の情報を管理するエッジルータとフロー毎の情報を管理しないコアルータから構成されるコアステートレスネットワークで、
エッジルータの入力部にパケットが到着した時に、そのパケットを送出しているユーザの送信レートを測定し、その値をＩＰパケットのヘッダに書き込み、エッジルータ及びコアルータの出力部にパケットが到着した時に、ヘッダに書き込まれたレート値と各ルータが独自に計算している公平帯域値を比較することにより、そのパケットをバッファに入力するかどうかの判断を行うスケジューリング法を用いたルータのルーティング方法において、
出力部にパケットが到着した時に、到着したパケットのサイズをクレジット１に加算し、到着したパケットのヘッダに書き込まれたレート値がマックスレート値より大きいか比較し、大きいならばマックスレートの値を到着したパケットのヘッダに書き込まれたレート値にし、
現在の公平帯域値を到着したパケットのヘッダに書き込まれたレート値で割った値Ｐを計算し、確率Ｐで、到着したパケットのサイズをクレジット２に加算し、
出力部にパケットが到着した時に、その到着時刻から記録している時刻を減算した値が予め定めている時間以上ならば、クレジット１を用いてレート1を、クレジット２を用いてレート２を計算し、
レート１がリンク帯域以上ならば、（現在の公平帯域値＊リンク帯域）をレート２で除算した値とリンク帯域の小さい方を新しい公平帯域値とし、リンク帯域以下ならば、マックスレート値を新しい公平帯域値とし、
新しい公平帯域値を決定した後、クレジット１、クレジット２、マックスレートの値を０にし、記録している時刻を現在の時刻にすることを特徴とするルーティング方法。
【請求項４】
フロー毎の情報を管理するエッジルータとフロー毎の情報を管理しないコアルータから構成されるコアステートレスネットワークで、
エッジルータの入力部にパケットが到着した時に、そのパケットを送出しているユーザの送信レートを測定し、その値をＩＰパケットのヘッダに書き込み、エッジルータ及びコアルータの出力部にパケットが到着した時に、ヘッダに書き込まれたレート値と各ルータが独自に計算している公平帯域値を比較することにより、そのパケットをバッファに入力するかどうかの判断を行うスケジューリング法を用いたルータのルーティングプログラムにおいて、
コンピュータに、
出力部にパケットが到着した時に、到着したパケットのサイズをクレジット１に加算し、到着したパケットのヘッダに書き込まれたレート値がマックスレート値より大きいか比較し、大きいならばマックスレートの値を到着したパケットのヘッダに書き込まれたレート値にする手順、
現在の公平帯域値を到着したパケットのヘッダに書き込まれたレート値で割った値Ｐを計算し、確率Ｐで、到着したパケットのサイズをクレジット２に加算する手順、および、
出力部にパケットが到着した時に、その到着時刻から記録している時刻を減算した値が予め定めている時間以上ならば、クレジット１を用いてレート1を、クレジット２を用いてレート２を計算し、
レート１がリンク帯域以上ならば、（現在の公平帯域値＊リンク帯域）をレート２で除算した値とリンク帯域の小さい方を新しい公平帯域値とし、リンク帯域以下ならば、マックスレート値を新しい公平帯域値とし、
新しい公平帯域値を決定した後、クレジット１、クレジット２、マックスレートの値を０にし、記録している時刻を現在の時刻にする手順、
を実行させるためのルーティングプログラム。
【請求項５】
請求項４記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コアステートレスネットワークで使用されるスケジューリング法において、正確な公平帯域値を計算する技術、その技術を用いたルータ、ルーティング方法、ルーティングプログラムおよび記録媒体に関する。
【０００２】
【従来の技術】
ＩＰ技術を用いた網では、ベストエフォートサービスが主流である。ベストエフォートサービスでは、通信を行っているユーザ毎に帯域を公平に分配することは必要不可欠である。帯域を公平に分配する技術として、ＤＲＲ等のフェアキューイング法が知られている。（M.Shreedhar et  al., "Efficient fair queuing using deficit round robin," IEEE/ACM trans. networking June 1996.）しかしフェアキューリング法では全てのルータが各ユーザの情報を管理しなければならない為、スケーラビリティに問題があった。そこでエッジルータのみ各ユーザの情報を管理し、コアルータでは各ユーザの情報を管理しないコアステートレスネットワークとそのようなネットワークにおいて公平に帯域を割り当てる、ＣＳＦＱ（Core Stateless Fair Queuing）と呼ばれるスケジューリング法が提案された。（Ion Stoica et al., "Core-Stateless Fair Queuing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks," SIGCOMM 98, 1998.）
ルータは、一般的に図１のように入力部、ルーティング部、出力部から構成されるが、ＣＳＦＱを実現するために、エッジルータの入力部、エッジ及びコアルータの出力部で必要とされるシステム構成をそれぞれ図２、図３に示す。エッジルータの入力部では、パケットが到着する毎に、ユーザ識別部が、そのパケットはどのユーザから送信されたかを識別する。そして、レート情報書き込み部において、そのパケットを送出しているユーザの送信レートを測定し、その値をＩＰパケットのヘッダに書き込む。エッジルータ及びコアルータの出力部では、ヘッダ読み取り部において、ヘッダに書き込まれた値を読み取る。そして、その情報と各ルータで独自に計算している公平帯域値を基にして、選択的パケット廃棄部において、そのパケットをバッファに入力するかどうかの決定を行う。
【０００３】
ＣＳＦＱにおいては、エッジルータでは、ユーザ毎の送信レートを測定するため、ユーザ毎の情報を管理する必要がある。しかしコアルータでは、パケットのヘッダに付与されている情報を利用するのみであるため、フロー毎の情報を管理する必要が生じない。その結果、フェアキューイング法と比較して、スケーラビリティに優れているという特徴がある。
【０００４】
ＣＳＦＱでは上述のように公平帯域値を計算しているが、その計算法として、以下のような方式が提案されている。
１）エッジルータ及びコアルータの出力部にパケットが到着した時に、到着したパケットのサイズをクレジット１に加算し、到着したパケットのヘッダに書き込まれたレート値がマックスレート値より大きいか比較し、大きいならばマックスレートの値を到着したパケットのヘッダに書き込まれたレート値にし、選択的パケット廃棄部でバッファに入力と判断されたパケットのサイズをクレジット２に加算する。
２）エッジルータ及びコアルータの出力部にパケットが到着した時に、その到着時刻から記録している時刻を減算した値が予め定めている時間以上ならば、クレジット１を用いてレート１を、クレジット２を用いてレート２を計算し、レート１がリンク帯域以上ならば、（現在の公平帯域値＊リンク帯域）をレート２で除算した値を新しい公平帯域とし、リンク帯域以下ならば、マックスレート値を新しい公平帯域とし、新しい公平帯域値を決定した後、クレジット１、クレジット２、マックスレートの値を０にし、記録している時刻を現在の時刻にする。
【０００５】
【発明が解決しようとする課題】
上記の従来のＣＳＦＱでは、正確な公平帯域値を計算するためには、選択的パケット廃棄部が確率Ｐ
P = max(0, 1 - 公平帯域値／パケットヘッダに書き込まれたレート値)
でパケットを廃棄する必要がある。つまりＣＳＦＱでは、廃棄確率Ｐを自由に変更できないという問題がある。特にＣＳＦＱで現在使用されている廃棄確率Ｐは、ＴＣＰにとって最適であるとは言えず、結果として、ＴＣＰに対して公平に帯域を割り当てることが出来ない。その為、確率ＰをＴＣＰに最適な確率に変更しても、正確な公平帯域値を計算できる新しいアルゴリズムが必要とされている。
【０００６】
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、ＣＳＦＱにおいて、使用する廃棄確率に関わらず、正確な公平帯域値を計算できるようにし、その結果、通信を行っているユーザに対して、公平な帯域割当を実現することである。
【０００７】
【課題を解決するための手段】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
【０００８】
従来方式では、選択的パケット廃棄部でバッファに入力と判断されたパケットのサイズをクレジット２に加算しているのに対して、本発明では、現在の公平帯域値を到着したパケットのヘッダに書き込まれたレート値で割った値Ｐを計算し、確率Ｐで、到着したパケットのサイズをクレジット２に加算している。その結果、ＣＳＦＱにおいてどのような廃棄確率を使用していたとしても、正確な公平帯域値を計算できる。
【０００９】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１０】
実施例におけるエッジルータの入力部のシステム構成とエッジルータ及びコアルータの出力部のシステム構成はそれぞれ図２、図３と同様である。ただし、ヘッダ読み取り部は、レート値だけでなく、パケットサイズ情報も読み取る。図４に実施例の公平帯域計算部の詳細を示す。図５は上記した公平帯域計算を擬似コードによって示したものであり、図６はフローチャートで示したものである。図７は具体例におけるパケットの状態を示す図である。
【００１１】
図４に示すような各部から公平帯域計算部は構成される。ヘッダ読み取り部で読み取られたレート値、パケットサイズはクレジット１計算部、クレジット２計算部、マックスレート計算部、制御部に送られる。クレジット１計算部では、送られたパケットサイズをクレジット１に加算する。クレジット２計算部では、送られたレート情報と公平帯域保持部で保持されてある現在の公平帯域値から、値Ｐ（＝公平帯域値／送られたレート情報）を計算する。そして確率Ｐで、送られたパケットサイズをクレジット２に加算する。マックスレート計算部では、送られたレート情報を保持しているマックスレート値と比較し、送られたレート情報がマックスレート値より大きい場合には、マックスレートの値を送られたレート値に更新する。制御部は、ヘッダ読み取り部から情報が送られると、その時の時刻を時刻部に問い合わせる。そして、現在の時刻から保持している時刻を減算した値が、予め定めた時間より大きいかを調べる。もし大きくなければ何もしない。大きいならば、レート１計算部にクレジット１を基にしてレートを計算するように求める。同様に、レート２計算部にクレジット２を基にしてレートを計算するように求める。レート１計算部で計算されたレート値がリンク帯域より大きければ、レート２計算部で（現在の公平帯域値＊リンク帯域）を計算されたレート値で除算した値とリンク帯域の小さい方の値を公平帯域保持部に通知する。レート１計算部で計算されたレート値がリンク帯域より小さければ、マックスレート部で保持されているマックスレートを公平帯域保持部に通知する。そして、クレジット１、２計算部に保持しているクレジット１、２を０に更新するよう通知する。またマックスレート計算部に保持しているマックスレートを０に更新するよう通知する。そして制御部自身が保持している時刻情報を現在の時刻に更新する。公平帯域保持部は、制御部から値を通知されると、保持している公平帯域値を通知された値に更新する。
【００１２】
以下、図７のようにパケットが到着した時の本発明の動作を図４、図５、図６を用いて示す。図７では、時刻0.01にサイズ1000ビット、レート値10kbits/のパケットが、時刻0.02にサイズ1000ビット、レート値20kbit/sのパケットが、時刻0.03にサイズ1000ビット、レート値30kbit/sのパケットが到着している。また図５においてfirstはtrue、TIMEは0.015秒、C（リンク帯域）は50kbit/s、BETA1、BETA2は0、alpha（公平帯域保持部が保持している値）は10kbit/sとする。
【００１３】
１番目のパケットが出力部に到着すると、ヘッダ読み取り部は1000ビット、10kbit/sの情報を通知する。到着したパケットは最初のパケットなので、クレジット１計算部、クレジット２計算部、マックスレート計算部は、それぞれ保持している値を０に更新する。制御部は、保持している値を現在時刻0.01秒に更新する。
【００１４】
２番目のパケットが出力部に到着すると、ヘッダ読み取り部は1000ビット、20kbit/sの情報を通知する。クレジット１計算部は、クレジット１の値を1000に更新する。クレジット２計算部は、値Ｐが10k/20k=0.5となり、確率0.5でクレジット２の値を更新する。ここでは更新されたと仮定し、クレジット２の値は1000となる。マックスレート計算部は、保持している値０より、通知された値20kbit/sが大きいので、保持している値を20kbit/sに更新する。制御部は、現在の時刻から保持している時間を減算した値、0.02-0.01=0.01が予め定められている時間0.015より小さいので、何もしない。
【００１５】
３番目のパケットが出力部に到着すると、ヘッダ読み取り部は1000ビット、30kbit/sの情報を通知する。クレジット１計算部は、クレジット１の値を1000+1000=2000に更新する。クレジット２計算部は、値Ｐが10k/30k=1/3となり、確率1/3でクレジット２の値を更新する。ここでは更新されなかったと仮定する。マックスレート計算部は、保持している値20kbit/sより、通知された値30kbit/sが大きいので、保持している値を30kbit/sに更新する。制御部は、現在の時刻から保持している時間を減算した値、0.03-0.01=0.02が予め定められている時間0.015より大きいので、レート１計算部にクレジット１の値を用いてレートを計算するように通知する。同様にレート２計算部にクレジット２の値を用いてレートを計算するように通知する。レート１計算部は、図５の式に従ってレートを計算するとすると、
【００１６】
【数１】
0003789338.tif 000002
より、10kbit/sとなる。レート２計算部も同様に図５の式に従ってレートを計算したとすると、
【００１７】
【数２】
0003789338.tif 000003
そして、（現在の公平帯域値＊リンク帯域）を計算したレートで除算した値は、
(10k*50k)/5k = 100k (bit/s)
となる。
【００１８】
レート１計算部で計算された値はリンク帯域Ｃより小さいので、制御部はマックスレート計算部の保持している値を公平帯域保持部に通知する。よって、公平帯域保持部で保持されている値は30kbit/sとなる。そして、クレジット１計算部が保持している値、クレジット２が保持している値、マックスレート計算部が保持している値は０に更新される。制御部が保持している値は0.03に更新される。
【００１９】
また本発明の有効性を示すコンピュータシミュレーションの結果を示す。廃棄確率Ｐを以下のように設定した。
【００２０】
【数３】
0003789338.tif 000004
【００２１】
ここで、
m ：予め設定したしきい値／現在のキュー長
L ：パケットのヘッダに書き込まれたレート値
α：公平帯域値
である。
【００２２】
図８に示すようなモデルを考える。ユーザ数は３０で、全てトランスポートプロトコルとしてＵＤＰを使用している。送信側は常に送信すべきパケットを有しているとし、それらを2Mbpsで送信するとする。受信側は一切パケットを送信しない。リンクは全て帯域が30Mbps、遅延時間が5msecとする。ルータ１とルータ２の間のリンクがボトルネックとなり、ルータ１のバッファが輻輳する。よって、ルータ１で計算される公平帯域値が30M/30=1Mbpsとなれば、正確な値が計算できているといえる。
【００２３】
図９にシミュレーション結果を示す。図９において、横軸は経過時間（Time(sec)）であり、縦軸は公平帯域値（Fair share rate(Mbps)）である。図９の結果より、廃棄確率の定義によらず、正確な値を計算できていることが分かる。
【００２４】
以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００２５】
【発明の効果】
以上説明したように、本発明によれば、どのような廃棄確率を用いた場合でも、正確な公平帯域計算が可能となり、その結果、ユーザ間で利用可能な帯域を公平に分配することができる。
【図面の簡単な説明】
【図１】ルータの構成である。
【図２】エッジルータの入力部のシステム構成である。
【図３】エッジルータ、コアルータの出力部のシステム構成である。
【図４】公平帯域計算部の詳細である。
【図５】擬似コードによる本発明のアルゴリズムである。
【図６】フローチャートによる本発明のアルゴリズムである。
【図７】パケット到着パターンである。
【図８】シミュレーションモデルである。
【図９】シミュレーション結果である。
【図１】
0003789338.tif 000005
【図２】
0003789338.tif 000006
【図３】
0003789338.tif 000007
【図４】
0003789338.tif 000008
【図５】
0003789338.tif 000009
【図６】
0003789338.tif 000010
【図７】
0003789338.tif 000011
【図８】
0003789338.tif 000012
【図９】
0003789338.tif 000013