1/27

MACD指標を用いた可用帯域推定法
長岡技術科学大学

大学院工学研究科
齋藤 綾太
中川 健治
渡部 康平

研究背景・目的

2/27

v 近年，インターネットで提供されるサービスは多様化し，帯域を大きく消費するサービスの増加
ex.
• 動画や音楽のストリーミングサービス⇒Netflix，Hulu，Spotify，etc.
• テレビ電話，テレビ会議⇒Skype，Zoom，etc.
それに伴い，「接続性」や「高速性」だけでなく，aaaaaaaaa「安定性」や「信頼性」が求められる

研究背景・目的

3/27

要求を満たすために，可用帯域幅（利用可能な帯域幅）を把握
End-to-Endによる可用帯域幅推定法• pathChirp，ASSOLO，etc.
• ユーザトラヒックを流体であると仮定し，プローブパケットの遅延を比較することにより推定を行う⇒推定精度低下の恐れがある◯目的
MACD指標を使用し，過去の遅延情報を考慮した推定法の提案⇒従来法と比較して推定精度向上を目指す

4/27

可用帯域幅v リンクnの可用帯域An：リンクnを短い時間区間Tに通過したトラヒックのレートλnの平均をリンク容量Cnから引いたもの
従って，M個のリンクからなるパスのEnd-to-Endにおける時刻tの可用帯域Aは

A[t,t +T ] = min An = min (Cn −n=1,2,...,M

n=1,2,...,M

λ n [t,t+T ]T)Bandwidth

Link capacity : Cn

Traffic : λn[t, t+T]
tAvailable BandwidthAn[t, t+T]
time [s]t+T[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

アクティブ測定による測定

v 測定用のプローブパケットを用いる方法
v 可用推定方法は，PGM，PRMに分類される

5/27

アクティブ測定による測定
v PGM（Probe Gap Model）• ペアパケット（連続する2つのプローブパケット）を固定レート（ボトルネックリンクの帯域）で送出⇒事前にボトルネックリンクの帯域を把握する必要あり• ペアパケットの間隔の変化より推定
ネットワーク内で，ペアパケット間にユーザパケットが挟まり，受信側でペアパケット間の間隔が広がる

6/27

アクティブ測定による測定
v PRM（Probe Rate Model）• パケットトレイン（N個連続するプローブパケット）を固定送信レートまたは可変送信レートで送出• 事前にボトルネックリンクの帯域を把握する必要無し• Self-Induced Congestionに基づき可用帯域を推定⇒送信レートを徐々に上げ，故意に輻輳を発生させる
可用帯域＞送信レート ⇒ 遅延は非増加傾向
可用帯域＜送信レート ⇒ 遅延は増加傾向あ7/27

従来法：pathChirpの概要

8/27

v Chirpと呼ばれる可変送信レートのパケットトレイン⇒単一パケットトレインで広範囲に可用帯域を探索
v PRMに属する可用帯域推定方法• 隣接するプローブパケットの片道遅延（OWD：One Way
Delay）を比較し，OWDが増加傾向に転じる変化点探索
v 推定の流れ
各プローブパケットのOWD計測 → 変化点の探索→ パケット毎の推定値および1トレインの推定値算出→ 推定値のフィルタリング（単純移動平均）[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

従来法：pathChirp（送信側）
N N-1

Chirp
32

4

9/27

1…
tN-1

t3

t2

t1

v プロービングパケットサイズPを一定
v パケット間隔tiを指数関数的に減少させる

ti = T / γi−1v 瞬時レートRiP
Ri =tii ：パケット番号γ：減少係数
N：パケット数(i = 1, 2,..., N −1)[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

従来法：pathChirp（送信側）
N N-1

Chirp
32

4

10/27

1

…
tN-1

t3

t2

t1

v 単一トレインで広範囲に可用帯域を探索⇒固定送信レートの方法と比較して，プローブパケットの使用量が少ない
可用帯域推定が高速あああああああ[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

11/27

従来法：pathChirp（受信側）
A：可用帯域

Ri：瞬時レート

Ri < A
OWDは非増加傾向

A < RiOWDは増加傾向

途中ユーザのバースト性により増加するが，減少傾向に転じる

変化点k[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

従来法：pathChirp（受信側）
case(a)：バースト性によるOWDが増加傾向

12/27

case(b)：OWDが非増加傾向
または変化点k以降

v パケット毎の推定値Ei⎧⎪ Ri
Ei = ⎨⎪⎩ Rk

ifif

else
else

case(a)case(a)case(b)case(b)i ：パケット番号
k ：変化点Ri：瞬時レート[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

13/27

従来法：pathChirp（受信側）
v j番目のChirpによる可用帯域の推定値Dj
N−1Et∑D =∑ t

Ei：パケット毎の推定値
ti ：パケット間隔
N ：パケット数

i i
i=1
N−1

ji=1i

v 推定値のフィルタリング（単純移動平均）

S=j∑

jt= j−M

M

Dt

S ：平滑化後の推定値
j ：Chirp番号
M ：平滑期間[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

従来法：pathChirpの問題点

14/27(a)トラヒックは離散的である⬇

閾値を設けて増加傾向の継続を判断(b)減少係数Fの決定が難しい(a)瞬時レートが可用帯域を超過してもOWDは単調増加しない可能性がある(b)閾値：Fによって決まる
設定によっては変化点が変わり推定精度の低下

提案法の概要

15/27

v 可変送信レートのパケットトレインを使用※今回はChirpを使用
利点：単一パケットトレインで広範囲に可用帯域を探索
v PRMに属する可用帯域推定方法• 受信側で各プローブパケットの片道遅延OWDの傾向を分析⇒MACD指標により変化点を探索
意図：過去のOWDの傾向も考慮して変化点を探索する
v 推定の流れ
各プローブパケットのOWD計測→MACD指標で変化点の探索→パケット毎の推定値および1トレインの推定値算出→推定値のフィルタリング（調和平均）16/27

提案法（受信側）
v 各プローブパケットの片道遅延を計測し，MACD指標により変化点を探索
MACD（Moving Average Convergence Divergence ）指標⇒EMA（指数平滑移動平均）を使用したトレンド解析
MACDライン：2つのEMAの乖離
MACDi = EMAi(s)[OWDi] − EMAi(l)[OWDi]（0<l<s<1）

Signalライン ：MACDのトレンド線（上昇 or 下降 ？？）Signali = EMAi(v)[MACDi]（0<v<1）

EMAi(α)[Oi]：i番目の観測値OiのEMA（平滑係数α）
OWDi：i番目のプローブパケットの片道遅延 s, l, v：平滑係数
MACDi, Signali ：i番目の観測値のMACDおよびSignal

提案法（受信側）
OWDが増加傾向 ：MACD > Signal
OWDが非増加傾向：MACD ≤ Signal

17/27

18/27

提案法（受信側）
ゴールデンクロス

MACDi+1

デッドクロス
MACDi

Signali

Signali+1

Signali+1Signali

MACDi

MACDi+1v MACDとSignalがクロスすると傾向の転換
ゴールデンクロス：MACDがSignalを下から上に突き抜ける
MACDi ≤ SignaliかつMACDi+1 > Signali+1
デッドクロス：MACDがSignalを上から下に突き抜ける
MACDi ≥ SignaliかつMACDi+1 > Signali+1

19/27

提案法（受信側）

最後のゴールデンクロスの始点⇒変化点kv MACDとSignalがクロスすると傾向の転換
ゴールデンクロス：MACDがSignalを下から上に突き抜ける
MACDi ≤ SignaliかつMACDi+1 > Signali+1
デッドクロス：MACDがSignalを上から下に突き抜ける
MACDi ≥ SignaliかつMACDi+1 > Signali+1

20/27

提案法（受信側）

case(a)：ゴールデンクロス発生からデッドクロス発生までの区間⇒バースト性による増加

case(b)：デッドクロス発生からゴールデンクロス発生までの区間または変化点k以降の区間
v パケット毎の推定値Ei⎧⎪ Ri
Ei = ⎨⎪⎩ Rk

ififelseelse

case(a)case(a)case(b)case(b)i ：パケット番号
k ：変化点Ri：瞬時レート

21/27

提案法（受信側）
v j番目のChirpによる可用帯域の推定値Dj∑
D =j

N−1
i=1

Ei

N −1

Ei：パケット毎の推定値
N ：パケット数

v 推定値のフィルタリング（調和平均）

H =jM
1∑t= j−M Dtj

H：平滑化後の推定値
j ：Chirp番号
M ：平滑期間

22/27

シミュレーション条件
n1

n3
User

n2

Estimation tool
pathChirp, Proposed methodn4Estimation tool
Bottleneck link（100[Mbps]，10[ms]）Other link （2.0[Gbps]，10[ms]）pathChirp パラメータ （文献[1]の推奨値を使用）
Packet size Ratemin
Ratemax
γ F L M
10003 [Mbps] 150 [Mbps] 1.2 1.5 5 5
提案法のパラメータ
Packet size Ratemin
Ratemaxγslv
1000
3 [Mbps] 150 [Mbps] 1.2 0.94 0.01 0.2

M
5[1] ﻿V.J.Ribeiro, R.H.Riedi, R.G.Baraniuk, J.Navratil and L.Cottrell, "pathChirp: efficient available bandwidth estimation
for network paths", PAM2003

23/27

シミュレーション条件
n1n3
User

n2

Estimation tool
pathChirp, Proposed methodn4Estimation tool
Bottleneck link（100[Mbps]，10[ms]）Other link （2.0[Gbps]，10[ms]）v シミュレーション
ユーザトラヒック：CBR
パケットサイズ：1000[B]
送信レート：10〜90[Mbps]（10[Mbps]刻み）
v 評価方法• 各送信レートにつき282回連続で推定を行い，平均，分散，バイアスで評価

シミュレーション結果

v pathChirpより，提案法の分散が大きい場合があるが，バイアスは常に小さい⇒pathChirpより，提案法の推定精度が高い

24/27

25/27

シミュレーション条件
n1n3
User

Estimation tool
pathChirp, Proposed method

n2n4

Estimation tool
Bottleneck link（100[Mbps]，10[ms]）Other link （2.0[Gbps]，10[ms]）v シミュレーション
ユーザトラヒック：Poisson パケットサイズ：1000[B]
送信レート：70[Mbps]
v 評価方法• 282回連続で推定を行い，MSEで評価

シミュレーション結果
MSE：512.4

MSE：88.8v pathChirpより，提案法の推定値が真値に近い

26/27

まとめ・今後の展望
v まとめ• MACDを用いた可用帯域推定法を提案した• pathChirpと比較して，推定精度が向上した
v 今後の展望• 複雑なネットワークトポロジを用いた検証• パッケトトレインを変更し，推定精度が向上するか検証
ex. 線形的に瞬時レートが大きくなるトレイン etc.

27/27