計測自動制御学会東北支部第 296 回研究集会(2015.7.24)
資料番号 296-1

プローブトレインペアを用いた可用帯域測定方式の改良
Improvement of Available Bandwidth measurement method Using a Probe Train Pair
○西沢 英朗（秋田大），加藤 陽介（秋田大），小原 仁（秋田大）○Hideaki Nishizawa, Yosuke Kato, Hitoshi Obara

キーワード: アクティブ測定(active measurement), 可用帯域(available bandwidth),線形回帰更新(recursive linear regression)〒010-8502 秋田市手形学園町１−１ 秋田大学大学院工学資源学研究科 電気電子工学専攻
Tel. 018-889-2488, Email: m9015143@wm.akita-u.ac.jp
1.

る 6)．リンク数 N から成る通信路において，リンク i におけまえがき

る帯域幅を Ci としたとき(1≤ i ≤N)，帯域幅 C b は

近年，インターネットで提供されるサービスは多様化しており，IP 電話や動画配信などのリアルタイム通信が広く普及

Cb = min Ci

している．それに伴い，遅延時間や通信速度などの点で高い

i =1, 2,..., N

回線品質が求められている．この現状を踏まえ，ISP は一部(1)のユーザに対し，通信速度などのいくつかの項目に関して品となり，この帯域幅 C b が通信路の最大伝送速度となる．一般

質保証型サービス(Service Level Agreement，SLA)を提供して次に，的に最小の帯域を持つリンクをナローリンクと呼ぶ 4)．

いる 1)．SLA 制度の回線品質の保証を行う重要な指標の 1 つ

可用帯域とは，各リンクにおける利用可能な帯域幅の最小値に可用帯域がある．可用帯域とは End-to-End 通信路のうち最のことである．
リンク i において，使用率 U i のクロストラフィッ小の空帯域を表す指標である．

クが流れている時の可用帯域 Ai は可用帯域を推定する方法は，大きく分けて，アクティブ測

Ai = Ci (1 − U i )定とパッシブ測定がある 2,3)．特に，アクティブ測定は，プロー(2)ブ呼ばれる試験用パケットを送信し，キューイング遅延による送受信間のプローブ間隔の変化から可用帯域を推定する．と表される．なお，クロストラフィックとは他のユーザが使

この方法は可用帯域の情報取得にかかるコストが少なく，リ用中の帯域を表す．この通信路における可用帯域はアルタイムな推定が可能という点からエンドユーザー向けのA = min Ai

方法であると言える．アクティブ測定の研究は現在までに様々
4)

i =1, 2,..., N5)な研究が行われてきた ．Pathload に代表される初期の技術(3)はプローブ量が多くなりネットワークに過剰な負荷をかけるとなる．最小の可用帯域を持つリンクをタイトリンクと呼ぶ欠点があった．3 章で述べるように最近は少ないプローブ量4)で精度よく可用帯域を推定する方式が注目されている．

間隔の比は平均的に 1 に等しい． しかし，送信速度が A を．送信速度が A 以下の場合，送信に対する受信のプローブ

本報告では複数のデータ点に線形回帰を行うことで可用帯超える場合はキューイング遅延が発生するため，その比は 1域を推定する方法 7,8,9)に注目する．従来方式では送信速度とを超えるという性質がある．この性質は可用帯域を同定する送受信間隔比に関する線形回帰を行うことで可用帯域を推定際に重要な役割を果たす．時間間隔 T の領域において，プローしていたが，これらの方式は使用プローブ量が少ないというブ数を M 個，１つのプローブのデータ量を D [bits]とすると，利点がある一方で，推定値のばらつきが大きいという問題がそのプローブの速度 v は v=M D/T [bps] となる．なお，ネッあった．そこで本報告では，従来方式では利用されていなかっトワークにおいて，プローブが通過するノード数をホップ数た測定データを使用することにより，同じプローブ量で推定と呼ぶ．

精度を改善する方法を提案する．
さらに 2hop の実験ネットワー
クで実際に動作させて性能評価を行い，今後の課題を明らか

従来のアクティブ推定方式

3.

以下に，提案方式と関連が深い 3 つの代表的な可用帯域推にする．

定技術を紹介する．

2.

帯域幅と可用帯域の定義

3.1

TOPP

TOPP7)は複数のプローブトレインペアを送信し，線形回帰帯域幅とは，通信路を構成する各リンク容量の最小値であ1

より可用帯域とリンク容量を推定する．具体的には最小速度混雑していることを示している．

v min と最大速度 v max を設定し，その範囲内で速度を N 個のv > A のとき，式(5)の v′ に式(6)を代入すると， t ′ / t は均等な区間に分け，各速度においてサイズ L Bytes で k 個のt′=t

プローブペアを徐々に速度を減らして送信する．このように送信側のパケットの間隔と，受信側のパケットの間隔が等しv
1v= v + ct
CCC⋅vv + v ct

くなる速度を見つける．
3.2(7)となり， t ′ / t は v の比例直線になる．さらに，式(5)に v につ

DietTopp8)

DietTopp は線形回帰を用いて，可用帯域とリンク容量を推いて式(6)を代入すると定する．初めに，最大速度 v1 でプローブを送信し受信速度 v1′v′ ⋅ vctv
t ′ C − v′== cttv′
C − v′を算出した後，[a ⋅ v1′ , b ⋅ v1′ ] の範囲（ a, b は定数）で速度を均等分割した複数のプローブを送信する．その後，送信したプローブの送信速度と送受信間隔比から線形回帰を用いて推定を行(8)う．送信するプローブ数により精度は変わってくるが．通信となり，t ′ / t は v′ の反比例曲線になる．ここで a1 , a 2 , b1 ,b2 を路の状況により大きな誤差を生じる場合がある．
3.3

定数として式(7)と式(8)の 1 / C をそれぞれ a1 , a 2 ， C / v ct をそReADR

れぞれ b1 , b2 と置くと， t ′ / t は9)ReADR は初めにプローブ送信速度を最大で送信し，受信t′= a1v + b1tした時の速度を次のプローブ送信速度として送信する．このように速度更新を繰り返し行い，プローブ受信速度が収束した時の値を可用帯域として推定する方式である．本報告では

t′b2=t 1 − a2 ⋅ v′

この方式を用いた速度更新を採用しており，その詳細は次章で述べる．

4.

提案方式

(9)

(10)の 2 式で表すことができる．

4.1 原理可用帯域はプローブ送信間隔とプローブ受信間隔が等しく

図 1 に示すリンク容量 C ，クロストラヒック vct が流れるなる時のプローブ速度として定義できる．すなわち t ′ / t = 1 と可用帯域 A の 2 ホップのネットワークを考える．
そこへプローなるときの速度を求めればよい．従って，式(9)，式(10)よりブサイズ L [byte]のプローブを送信した場合の受信速度を v′ ，受信間隔 t ′ とすると，受信速度 v′ は次式で表される．

v′ =L ⋅8t′(4)式(4)よりプローブの速度とプローブの間隔は反比例する．
従っ

1 − b1a1(11)v′ =1 − b2a2(12)となる v および v′ が可用帯域となる．さらに式(9)，式(10)にて，プローブの送受信速度比と送受信間隔比の関係はプロー

おいて v = v ′ となる点ではプローブ送信間隔とプローブ受信ブ送信速度 v ，送信間隔 t とすると，次式で表される．

間隔が等しくなる．よって v = v ′ = v x とおくと v x はt′ v=t v′(5)vx =ここで，送信速度 v に対する理論的な v′ の推移は

v
v′ =  Cv + v ⋅ vct
v=となる．ここで a1 = a 2 = a ， b1 = b2 = b とおくと(v ≤ A)(v > A)a1 − a2b1 ± (−a1 + a2b1 ) 2 − 4a1a2 (−b1 + b2 )2a1a2(−a1 + a 2 b1 ) 2 − 4a1 a 2 (−b1 + b2 ) > 0 のとき(6)vx =となる． v ≤ A の場合，ノードでキューイング遅延が生じな

1− ba(−a1 + a 2 b1 ) 2 − 4a1 a 2 (−b1 + b2 ) ≤ 0 のとき

いため，送受信間で速度は変化しない．しかし， v > A の場

vx = 0合，遅延が生じ受信速度は減少する．ここで，C /(v + v ct ) はリンクの混雑度合いを表す．この値が小さいほど，リンクはであるため v x は2(13)vx =送信する．次に，その受信速度を算出し，その値を送信速度

a1 − a 2 b1 + (−a1 + a 2 b1 ) 2 − 4a1 a 2 (−b1 + b2 )(14)

2a1 a 2に設定したプローブを再び送信する．図 3 に示すように，受信速度は可用帯域付近で緩やかになる性質がある．よって，となる．以上より式(11)の v を ABW₁，式(12)の v′ を ABW₂，プローブを送信する度に i 段階とその直前の i − 1 段階の受信式(14)の v x を ABW₃と定義する．

速度の相対的な差を計算し，下記の収束条件を満たした時に式(9)，式(10)におけるプローブ速度-送受信間隔比の推移の測定を終了する．

例を図 2 に示す．プローブ速度が A 以下の場合，送受信間隔(16)v −v≤δvの比は平均的に 1 となる．一方，プローブ速度が A より大きくなった場合，プローブ送信速度と送受信間隔比は直線的に''i −1i'i増加する．従って，2 点以上プローブの座標をプロットすると，傾き a1 と切片 b1 が分かるため式(9)の比例直線が求められ一般に，δは 0.1 以下の微小な値に設定する．

る．
一方，プローブ受信速度と送受信間隔比は反比例的に増加する．ここで，式(10)の逆数を考えると

1t ′ − a21=v′ +tb2b2(15)となり，傾き − a 2 b2 と切片 1 b2 の比例直線が求められる．
よって，式(15)より a 2 ， b2 が分かるため式(10)の反比例曲線

図 3. 速度更新による受信速度の推移が求められる

5.

実験による性能評価

5.1 実験条件
図 4 に示す 2 ホップの実験ネットワークを用い，可用帯域を 20Mbps と想定した実験を行う．実験条件を表 1 に示す．
なおクロストラフィックの送受信はトラヒックジェネレータ
ソフトの D-ITG (ver. 2.8.1-r1023) 10)を使用する．
図 1. 2hop のネットワーク【192.168.○.○ネットワーク】①ABW₁②ABW₂③ABW₃

図 4. 実験ネットワークの構成
表 1. 実験条件
プローブ長[bytes]

1500

プローブ数[個]50

クロストラフィック

発生分布：指数分布

CT パケット長[bytes]

1000

可用帯域[Mbps]

20

従来の推定方式 3.3 の ReADR 方式により送信速度の更新を行

リンク容量[Mbps]

100

い，なるべく広い範囲でデータをとり，推定点の線形回帰に推定回数[回]30

図 2. プローブ送受信速度-送受信間隔比の推移
4.2 速度更新
提案方式では各速度におけるデータ点の線形回帰を行うことで可用帯域を推定する．ただし，速度差が小さい場合，直線区間が短くなり推定精度が劣化する問題がある．従って，より式(9)式(10)を算出する．最初に，最大速度でプローブを3

5.2 実験結果の実験ネットワークで性能評価を行った．送信速度-送受信間可用帯域の推定結果を図 5 に示す．また，その場合の可用隔比の回帰直線に受信速度-送受信間隔比の回帰曲線を加えて，帯域 ABW₁，ABW₂，ABW₃とその平均値について標準偏差3 点による可用帯域推定を行った結果，標準偏差が 3.01Mpsと推定誤差を表 2 に示す．図 5 より可用帯域の推定値は理論から 2.72Mbps に減少し，誤差が 9.86%から 8.31%に減少した．

値の上下に分布しており，過小評価，過大評価といった傾向

しかし，測定不能となる場合が存在し，回帰直線および回帰は見られなかった．また，ABW₁と ABW₂と ABW₃に極端な曲線が理論値から外れていることが分かった．

差は現れなかった．ABW₁と 3 つの平均を比較すると，標準今後の課題として，理論値に近い線形回帰方法の検討が必

偏差が 3.01Mps から 2.86Mbps に減少し，誤差が 9.86%から要で，さらに，可用帯域を変化させた場合や hop 数を増やし8.90%に減少した．従って，受信速度-送受信間隔比の回帰曲た場合など，条件を変化させて実験を行い，本提案方式の実線を加えることで，推定値のばらつき，誤差を低減できるこ

用性を評価する必要がある．とが分かった．また，本実験で ABW₃が測定不能となる場合が 30 回の実験の内 9 回発生した．これは送信速度-送受信間

参考文献

隔比の回帰直線と受信速度-送受信間隔比の回帰曲線に交点が1)

Estimation: Metrics, Measurement Techniques, and Tools ，発生しないことに起因している．ABW₃の測定不能時を除外した場合の ABW₁，ABW₂，ABW₃の標準偏差と推定誤差をIEEE Network17.6，pp.27–35，2003

表 3 に示す．表 2 と比較して，平均が標準偏差 2.86Mbps から2)

川原亮一，森達哉，上山憲昭 IP フロー計測技術の応用 ，

3)

大下裕一，荒川伸一，村田正幸， 交流トラヒック行列推

2.70Mbps に減少し，誤差が 8.90 %から 7.92%に減少した．
ABW₁

30ABW₂

電気電子情報通信学会誌 Vol.93，No.4，pp.287-292，2010

ABW₃

定手法とネットワーク制御への応用 ，電気電子情報通信

可用帯域[Mbps]

254)

20

学会誌，Vol.93，No.4，pp.293-297，2010
J.Strauss，D.Katabi，and F.Kaashoek， A measurement studyof available bandwidth estimation tools ，Proc. of ACM

15SIGCOMM Conference on Internet Measurement，pp.39-44，

1020035)

50R.Prasad, C.Dovrolis, M.Murray, and K.Claffy BandwidthJain, Manish, and Constantinos Dovrolis. "Pathload: A
measurement tool for end-to-end available bandwidth" Proc.of

01020306)

測定回数

Passive and Active Measurements (PAM) Workshop，2002
M.Jain and C.Dovrolis,
End-to-End Available Bandwidth:
Measurement Methodology, Dynamics, and Relation with

図 5. 可用帯域の推定結果

TCP Throughput
表 2. 可用帯域の標準偏差と推定誤差

IEEE/ACM Transactions on Networking,vol. 11, no. 4, pp. 537-549, 2003

標準偏差[Mbps]

誤差[%]

ABW₁

3.01

9.86

ABW₂

2.85

8.53

ABW₃2.72

8.31

平均2.868.907)

Bob Melander，Mats Bjorkman，Per Gunningberg Regression-Based Available Bandwidth Measurements， Proc. ofInternational Symposium on Performance Evaluation ofComputer
8)

and Telecommunications Systems，pp.14-19，2002

A.Johnsson, B.Melander and M.Bjorkman

DietTopp: A

first implementation and evaluation a simplified bandwidth
measurement method, Proc. of Swedish National Computer

Networking Workshop，Vol. 5，2004

表 3. 可用帯域の標準偏差と推定誤差（異常値除外）9)

作山貴洋，加藤陽介，小原仁

インターネットにおける標準偏差[Mbps]

誤差[%]

可用帯域とリンク容量の線形回帰更新による同時推定方

ABW₁

2.75

7.55

式の提案 ，計測自動制御学会東北支部 50 周年学術講演

ABW₂2.62

7.91

ABW₃2.72

8.31

平均2.70

7.92

会，B-202，2014
10) A.Botta,W.D.Donato,A.Dainotti,

D-ITG 2.8.1 Manual ，

http://traffic.comics.unina.it/software/ITG/manual/D-ITG-2.8.
1-manual.pdf

6. まとめ
本報告では End-to-End 通信路における受信速度-送受信間隔比の回帰曲線による可用帯域推定法を提案した．また，2hop

4