(57)【特許請求の範囲】
【請求項１】
複数の端末が接続されているパケットスイッチ網における端末間の利用可能帯域を推定する方法であって、送信端末から受信端末に向けて送信間隔Ｉk で複数のプローブパケットを連続して送信し、受信端末において前記プローブパケットを受信し、その受信間隔Ｉk’を測定し、これら送信間隔Ｉkと受信間隔Ｉk’とに基づいて端末間の利用可能帯域を推定する帯域推定方法において、 送信端末は、プローブパケットの送信間隔Ｉkを変えながら前記プローブパケットの 連続送信を繰り返し、受信端末は、受信したプローブパケットの受信間隔Ｉk’を順次測定し、得られた一連のデータ(Ｉk ,Ｉk’−Ｉk)について一次近似することにより送信端末と受信端末との間の通信経路の利用可能帯域を計算することを特徴とする帯域推定方法。
【請求項２】
複数の端末が接続されているパケットスイッチ網における端末間の利用可能帯域を推定するシステムであって、送信端末から受信端末に向けて送信間隔Ｉk で複数のプローブパケットを連続して送信するプローブパケット送信手段と、受信端末において前記プローブパケットを受信し、その受信間隔Ｉk’を測定する受信間隔測定手段と、これら送信間隔Ｉkと受信間隔Ｉk’とに基づいて端末間の利用可能帯域を計算手段とを具え、
前記プローブパケット送信手段は、プローブパケットの送信間隔Ｉkを変えながら前記プローブパケットの連続送信を繰り返し、受信間隔測定手段は、受信したプローブパケットの受信間隔Ｉk’を順次測定し、
前記計算手段は、得られた一連のデータ(Ｉk ，Ｉk’−Ｉk )について一次近似することにより送信端末と受信端末との間の通信経路の利用可能帯域を計算することを特徴とする帯域推定システム。
【請求項３】
複数の端末が接続されているパケットスイッチ網における端末間の利用可能帯域を推定する方法であって、送信端末から受信端末に向けて送信間隔Ｉk で複数のプローブパケットを連続して送信し、受信端末において前記プローブパケットを受信し、受信したプローブパケットに対応する応答パケットを送信端末に向けて送信し、前記送信端末は、受信した応答パケットの受信間隔Ｉk’を測定し、これら送信間隔Ｉkと受信間隔Ｉk’とに基づいて端末間の利用可能帯域を推定する帯域推定方法において、
送信端末は、プローブパケットの送信間隔Ｉkを変えながら前記プローブパケットの送信を繰り返すと共に、受信した応答パケットの受信間隔Ｉk’を順次測定し、得られた一連のデータ(Ｉk ，Ｉk’−Ｉk)について一次近似することにより送信端末と受信端末との間の通信経路の利用可能帯域を計算することを特徴とする帯域推定方法。
【請求項４】
複数の端末が接続されているパケットスイッチ網における端末間の利用可能帯域を推定するシステムであって、送信端末から受信端末に向けて送信間隔Ｉk で複数のプローブパケットを連続して送信するプローブパケット送信手段と、受信端末において前記プローブパケットを受信し、対応する応答パケットを送信端末に送信する手段と、前記応答パケットを受信し、その受信間隔Ｉk’を測定する受信間隔測定手段と、これら送信間隔Ｉkと受信間隔Ｉk’とに基づいて端末間の利用可能帯域を計算手段とを具え、
前記プローブパケット送信手段は、プローブパケットの送信間隔Ｉkを変えながら前記プローブパケットの連続送信を繰り返し、受信間隔測定手段は、受信した応答パケットの受信間隔Ｉk’を順次測定し、
前記計算手段は、得られた一連のデータ(Ｉk  ，Ｉk’−Ｉk)について一次近似することにより送信端末と受信端末との間の通信経路の利用可能帯域を計算することを特徴とする帯域推定システム。
【請求項５】
請求項１又は３に記載の帯域推定方法において、前記一次近似として、ｙ＝−ａx＋ｂの一次関数を用い、前記プローブパケットのパケット長をＬとした場合に、利用可能帯域Ｂを、式
Ｂ＝（ａ×L）／ｂ
に基づいて利用可能帯域を計算することを特徴とする帯域推定システム。
【請求項６】
請求項２又は４に記載の帯域推定システムにおいて、前記計算手段は、前記一次近似として、ｙ＝−ａx＋ｂの一次関数を用い、前記プローブパケットのパケット長をＬとした場合に、利用可能帯域Ｂを、式
Ｂ＝（ａ×L）／ｂ
に基づいて利用可能帯域を計算することを特徴とする帯域推定システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、パケットスイッチ網に接続された端末からネットワークにプローブパケットを送信し、受信端末において受信したプローブパケットの遅延情報を収集してネットワーク内の利用可能帯域を推定する方法及びシステムに関するものである。
【０００２】
【従来の技術】
パケットスイッチ網に接続された端末からネットワークにプローブパケットを送信し、受信端末において受信したプローブパケットの遅延情報を収集してネットワーク内の帯域を計算する方式、あるいは宛先端末は送られたプローブパケットに対して即座に応答パケットを送信し、送信端末において受信した応答パケットの遅延情報からネットワーク内の帯域を計算する方式が既知である。この既知の帯域計算方法では、図１（ａ）に示すように、パケットスイッチ網に接続された端末から受信端末に向けて複数のプローブパケットを最小の間隔で連続送信し、受信端末においてそのプローブパケットを受信し、この受信間隔を収集する方式が採用されている。また、図１（ｂ）に示すように、宛先端末がプローブパケットを受信後直ちに応答パケットを送信し、その応答パケット受信間隔を用いて受信間隔を収集し、その送信間隔と受信間隔から経路上のボトルネックとなる帯域情報を推定するパケットペア方式が知られている（例えば、非特許文献１又は２参照）。この方式ではネットワーク内のボトルネックとなるリンクにおけるリンク速度をＣとすると、送信端末における連続送信する際の送信間隔Ｉと受信端末における受信したパケットの受信間隔Ｉ′とプローブパケットサイズLから、以下の関係が成り立つ。
【数１】
0003911244.tif 000002
【０００３】
図２に示すようにあるパケットサイズのＩCMPまたはUDＰパケットをプローブパケットとし、ある個数連続して最小の間隔で宛先端末に送信し、その応答パケットの受信間隔からＩ′の平均値を計算することにより、送受信端末間の利用可能帯域値の計算を行っていた。またその後、プローブパケットの送信間隔を変化させながら連続送信し、その送信間隔Ｉと受信間隔Ｉ′との相関を観測し、その相関の有無から利用可能帯域を求める試みがされている(例えば、非特許文献３又は４参照)。
【０００４】
【非特許文献１】
R.L.Carter and M.E.Crovella,「Dynamic server selection using bandwidth probing in wide area networks」,Technical report, Boston University Computer Science Department, March 1996.
【非特許文献２】
R.L.Carter and M.E.Crovella, 「Measuring bottleneck link speed in packet-switched networks」,Technical report, Boston University Computer Science Department, March 1996.
【非特許文献３】
B.Melander, M.Bjorkman, andP.Gunningberg, 「A New End-to-End Probing and Analysis Method for estimating Bandwidth Bottleneck」,In IEEE Global Internet Symposium, November 2000.
【非特許文献４】
M.jain and C.Dovlis, 「Pathload:A masurement too for end-to-end available bandwidth」,Proceedings of Passive and Measurements Workshop, March 2002.
【０００５】
【発明が解決しようとする課題】
（１）式および図２によって求められる帯域情報は、プローブパケットがキューイングされるリンクにおいて負荷トラヒックが発生していない場合は、経路上のボトルネックとなるリンクにおけるリンク速度として用いることができる。しかしながら、実際には負荷トラヒックが発生しており、そのときに（1）式を用いて平均値を求めたとしても、それは利用可能帯域値とすることはできない。また、送信間隔Ｉの大きさを変化させ、その送信間隔Ｉと受信間隔Ｉ′との相関を観測する場合においても負荷トラヒックのキューイング遅延とプローブパケットの遅延の関係は明らかにされておらず、そのため、従来の利用可能帯域の算出法は、遅延の確率的な影響を考慮して定式化されていない。
【０００６】
本発明は上記要因により、阻害されていた利用可可能帯域の算出を解決するもので、連続して送信されるプローブパケットと負荷トラヒックのキューイング遅延の影響を明らかにし、その関係を定式化することで、計算に要するプローブパケット量と計算時間を小さくし、かつ精度の良い利用可能帯域値を算出する帯域推定システムを提供することをその目的とする。
【０００７】
【課題を解決するための手段】
同一のパケットサイズＬのプローブパケットn個（n≧2）を最小の間隔で制御して受信端末に送信し、その送信間隔をＩ0として記録し、受信端末での各プローブパケットの受信間隔、または送信端末からの応答パケットの受信間隔を記録し、その平均値をＩ0′として記録する。次に、ΔＩだけ送信間隔を大きくしながらこの処理をＩｋ≧Ｉ0′となるまで繰り返し行い、Ｉｋ及びＩｋ′を記録し、（x，y）＝（Ｉｋ，Ｉｋ′−Ｉｋ）データから最小二乗法を利用し一次近似を実行してｙ＝−ax＋bとなる定数a，bを求め、利用可能帯域Bを以下の式により求める。
【数２】
0003911244.tif 000003
ここで、送信端末及び受信端末として、ネットワークのエンドに接続されている端末装置を用いることができ、又はネットワーク中に接続されているルータとすることができる。従って、端末装置間の通信経路並びにルータと端末装置間の通信経路及びルータと別のルータとの間の通信経路の利用可能帯域を求めることができる
【０００８】
【作用】
あるG／G／1待ち行列にpacket pairプローブが到着した状態を考える。packet pairの送出間隔（この待ち行列に到着する間隔）をＩ、受信間隔（待ち行列から送出される間隔）をＩ′、このプローブパケットがこの待ち行列システム内でサービスされる時間をＸとすると、Ｘ時間内に負荷トラヒックが到着しなかった場合には
【数３】
0003911244.tif 000004
となる。この関係は多段に待ち行列が形成されていて、Ｘをボトルネックとなるリンクの待ち行列においてプローブパケットがサービスされる時間と考えると、待ち行列を多段に経由する場合においても成り立つ。したがって、ＸをＩ′によって知ることができるので、packet pairのパケットサイズからボトルネックでのリンク速度を計算することができ、負荷トラヒックが存在していない場合にはこれを利用可能帯域とすることができる。しかしながら、実際には時間期間Ｘ内に到着する負荷トラヒックにより、Ｉ′は影響を受けるため、そのまま計算値を利用可能帯域とすることはできない。
【０００９】
図3のように、ボトルネックリンクの待ち行列システムにおいて、Cnをn番目にシステムに到着した負荷トラヒックパケットとし、Cnの到着間隔をｔｎ、サービス時間をxｎ、待ち行列時間をwnと確率変数を定義すると、Lindleyの関係式が成り立ち（L.Kleinrock, Queueing Systems. Volume I:Theory, Wiley-Interscience, New York 1975）、
【数４】
0003911244.tif 000005
となる。tn+1とｘn との差分を
【外１】
0003911244.tif 000006
と定義し、この関係式を以下のように表す。
【数５】
0003911244.tif 000007
この待ち行列システムにpacket pairが到着し、なおかつＩ間に負荷トラヒックが到着しており、待ち時間が必ず発生していたとする。このとき、（5）式から再帰的に考えると、以下の（６）式が成立する。
【数６】
0003911244.tif 000008
（6）式をpacket pair到着時の状態として考えるとＩ間にｎ個のパケットが到着していたとして、Ｉ′は、
【数７】
0003911244.tif 000009
とすることができる。この状態を確率変数Ｙとして定義すると、負荷トラヒックが発生している場合も考慮した（3）式は以下のように表すことができる。
【数８】
0003911244.tif 000010
ｎはＩ間に到着する負荷トラヒックパケット数である。（8）式ではＩが十分小さい領域においてはＩ′＝Ｙ、逆に大きい領域においてはＩ′＝Ｉであると予測できるが、境界条件は不明である。Ｉ′＝Ｙの領域において定常状態から期待値E[un]が得られたとすると、
【数９】
0003911244.tif 000011
とすることができる。さらに、待ち行列システムにおけるパケットの平均到着時間を
【外２】
0003911244.tif 000012
平均サービス時間を
【外３】
0003911244.tif 000013
とすると、
【数１０】
0003911244.tif 000014
であるから、以下のよう差分Ｄを定義すると、
【数１１】
0003911244.tif 000015
とすることができる。(11)式は、Ｉ′＝Ｙの領域においてＩ′の変化はＩの一次関数で近似できることを示している。またプローブパケットサイズをＬ、この待ち行列が存在するリンクでのリンク速度をＣとするとX＝L／Cであるから、（11）式の両辺＝0のとき、
【数１２】
0003911244.tif 000016
となり、利用可能帯域を求めることができる。これは（8）式の境界条件に対する必要条件である。そこで、Ｉがback-to-backの状態で得られたＩ′の大きさの範囲では(9)式及び（11）式は十分成り立つと考えられるため、この範囲で（11）式を適用することにより、最小二乗近似を用いて利用可能帯域を求めることができる。
【００１０】
【発明の実施形態】
【実施例１】
図4は本発明による利用可能帯域推定方法の一実施例を示す。本帯域推定システムは、送信端末と受信端末で構成されているものとする。送信端末ではMTUから検出される最大のパケットサイズＬと接続されているリンク速度を把握し、受信端末では同様に接続されているリンク速度を把握するとともに、それを送信端末へ通知する。送信端末ではLと送受信端末のリンク速度から最小の送信間隔を把握する。送信端末は把握した最小送信間隔でUDPパケットを受信端末へn個（n＞1）連続送信し、送信間隔Ｉ0を記録する。受信端末ではＵDPパケットの受信間隔を記録し、送信端末へ通知する。送信端末では通知された受信間隔より平均値Ｉ0′を計算し記録する。次に送信端末では送信間隔をＩk＝Ｉｋ-１+ΔＩとしてUDPパケットをn個連続送信し、送信間隔Ｉkを記録する。受信端末はＵDPパケットの受信間隔を送信端末へ通知する。送信端末では通知された受信間隔より平均値Ｉk′を計算し記録する。送信時刻と受信端末からの通知パケットの受信時刻のRTT分だけ処理待ちをする。送信端末においてＩkとＩ0′との大小関係を比較し、Ｉk.≧Ｉ0′となるまでこれを繰り返し行う。次に送信端末では、最小二乗法としてｙ＝−ax+bを仮定して（x,y）＝(Ｉk ,Ｉk −Ｉk）データから最小二乗法を実行し、定数a,ｂを算出し、利用可能帯域Bを以下の式により求める。
【数１３】
0003911244.tif 000017
【００１１】
【実施例２】
図５は本発明による帯域推定方法の第２実施例を示す。本帯域推定システムは、送信端末のみで構成されているものとする。送信端末ではMTUから検出される最大のパケットサイズＬと接続されているリンク速度を把握し、Lとリンク速度から最小の送信間隔を把握する。把握した最小送信間隔でlCMPパケットまたはUDPパケットを宛先端末へn個（n＞1）連続送信し、送信間隔Ｉ0を記録する。宛先端末からの1CMP応答パケットの受信間隔を記録し、その平均値Ｉ0′を記録する。次に送信端末では送信間隔をＩk＝Ｉｋ-１+ΔＩとしてICMPパケットまたはＵDPパケットをｎ個連続送信し、送信間隔Ｉkを記録し、ICMＰ応答パケットの受信間隔を記録しその平均値Ｉk′を記録する。その後、送信時刻と受信時刻のRTT分だけ処理待ちをする。送信端末においてＩkとＩ0′の大小関係を比較し、Ｉk. ≧Ｉ0′となるまでこれを繰り返し行う。次に送信端末では、最小二乗法としてy＝−ax+bを仮定して（x,y)＝(Ｉk ,Ｉk ′−Ｉk）データから最小二乗法を実行し、定数a,bを算出し、利用可能帯域Bを以下の式により求める。
【数１４】
0003911244.tif 000018
【００１２】
【実施例３】
図６は本発明による帯域推定方法の第３実施例を示す。本帯域推定システムは、送信端末のみで構成されているものとする。送信端末ではMTUから検出される最大のパケットサイズＬと接続されているリンク速度を把握し、Lとリンク速度から最小の送信間隔を把握する。把握した最小送信間隔でICMP Timestamp要求を宛先端末へｎ個（ｎ＞1）連続送信し、送信間隔Ｉ0を記録する。宛先端末からのICMP Timestamp応答パケットのTimestampを記録し、その平均値Ｉ0′を記録する。次に送信端末では送信間隔をＩk＝Ｉｋ-１+ΔＩとしてICMP Timestamp要求をn個連続送信し、送信間隔Ｉkを記録し、ICMP Timestamp応答パケットのTimestampを記録しその平均値Ｉk′を記録する。その後、送信時刻と受信時刻のRTT分だけ処理待ちをする。送信端末においてＩkとＩ0′の大小関係を比較し、Ｉk ≧Ｉ0′となるまでこれを繰り返し行う。次に送信端末では、最小二乗法としてy＝−ax+bを仮定して（x,y）＝(Ｉk ，Ｉk’−Ｉk）データから最小二乗法を実行し、定数a,ｂを算出し、利用可能帯域Bを以下の式により求める。
【数１５】
0003911244.tif 000019
【００１３】
【発明の効果】
以上に述べたように本発明によれば、負荷トラヒックのキューイング遅延とプローブパケットの遅延の関係を定式化し、利用可能帯域を求めることにより、計算に要する不要なプローブパケット量を削減し、計算時間を短縮し、かつ精度が向上されるという効果が得られる。
【図面の簡単な説明】
【図１】  従来の帯域推定方法の原理を説明する図である。
【図２】  従来の帯域推定方法のアルゴリズムを示す図である。
【図３】  本発明による帯域推定方法の原理を説明するための待ち行列システムにおけるパケット到着間隔とサービス時間、待ち行列時間の関係を示す図である。
【図４】  本発明による帯域推定方法の第１実施例の処理フローを示す図である。
【図５】  本発明による帯域推定方法の第２実施例の処理フローを示す図である。
【図６】  本発明による帯域推定方法の第３実施例の処理フローを示す図である。
【図１】
0003911244.tif 000020
【図２】
0003911244.tif 000021
【図３】
0003911244.tif 000022
【図４】
0003911244.tif 000023
【図５】
0003911244.tif 000024
【図６】
0003911244.tif 000025