講義スライド

インターネット計測とデータ解析 第 7 回
長 健二朗
2010 年 11 月 17 日
前回のおさらい
インターネットの多様性と複雑さを計る
I
ロングテールとさまざまな分布
I
サンプリング
I
統計解析 (期待値と大数の法則、信頼区間と検定)
2 / 31
今日のテーマ
インターネットの時間変化を計る
I
インターネットと時刻
I
時系列解析
I
課題 2
3 / 31
計測と時間
I
絶対時刻
I
協定世界時 UTC (Universal Coordinated Time)
I
I
I
I
セシウム原子時計をもとに取り決められている標準時
相対時刻
時刻の差分
時刻調整
I
I
時計の時刻は前後に補正される
NTP では 128ms 未満の誤差は一度に、それ以上だと徐々に
修正
4 / 31
クロックの誤差
I
クロックの誤差
I
同期
I
正確さ
I
解像度
I
I
I
UTC からのずれ
クロックの精度
スキュー
I
I
2 つのクロックの差
I
時間とともに同期や正確さがずれる
時間粒度
I
I
I
PC クロック: 0.1-1sec/日ぐらいずれる
NTP: 10-100ms の正確さにクロックを同期
tcpdump などのタイムスタンプ:
I
100usec-100msec (通常 < 1msec だが保証なし)
5 / 31
PC のクロック
i8254 プログラムインターバルタイマー
I 16-bit フリーラニング ダウンカウンター
I
I
1,193,182 Hz の水晶発振器を基にしている
カウンターがゼロになると割り込み信号を上げてカンターレ
ジスタ値をリロード
Read
Latch
Clock Counter
Osc
Prescaler
Adjust
PD
I/O Bus
6 / 31
クロックドリフト
I
水晶発振器のドリフト
I
ハードウエア仕様の許容誤差: 10−5
I
I
0.86 sec/day は許容誤差内
ドリフトは温度に大きく影響される
clock
time
clock A
ideal clock
clock B
time
7 / 31
その他の PC クロック
I
Pentium TSC (Time Stamp Counter)
I
I
I
ACPI (Advanced Counfiguration and Power Interface)
I
I
各プロセッサに内蔵される割り込み機能付きタイマー
HPET (High Precision Event Timer)
I
I
I
パワー管理機能が提供するフリーラニングカウンター
Local APIC (Advanced Programmable Interrupt Controller)
I
I
CPU クロックで駆動される CPU 内蔵フリーラニングカウ
ンター
可変クロックやマルチ CPU で問題
IA-PC の新しいタイマー仕様
2005 年頃からチップセットに組み込み
外部クロック
I
GPS、CDMA など時刻情報を含む
I
インターフィスにより読み込みオーバーヘッド
8 / 31
OS 時刻管理
I
OS はソフトウエアにより時刻を管理
I
I
I
起動時にカレンダーチップから時刻を得る
ハードウエアクロック割り込み毎に時刻をアップデート
従来の UNIX では、デフォルトで 10ms ごとにクロック割り
込みが発生するようにクロックカウンターを設定
9 / 31
UNIX gettimeofday
I
I
古い OS ではクロック割り込みの粒度しかなかった
いまどきの OS ではより高精度の時刻を得られる
I
クロックカウンター値を読み出してソフトウエアクロックを
補間
I
I
OS 内部処理時間
I
I
I
i8254 レジスタアクセス: 1-10usec
struct timeval への変換: 1-100usec
ユーザ空間から OS 内部へのアクセス
I
I
I
i8254 の解像度: 838ns (1 / 1193182)
システムコール オーバーヘッド: 10-500usec
プロセススケジューリングの影響: 1-100msec or more
タイマーイベント ソフトウエア処理時間 (e.g., setitimer):
I
I
ソフトウエアタイマー割り込みから処理 (10msec by default)
プロセススケジューリングの影響を受ける
10 / 31
NTP (Network Time Protocol)
I
インターネット上の複数サーバー間で時刻同期
I
I
I
I
スケーラビリティ
I
I
プライマリサーバ: 直接 UTC ソースに繋がる
セカンダリサーバ: プライマリに同期
3 段目以降のサーバ: セカンダリ以降に同期
20-30 プライマリ、 2000 セカンダリを < 30ms に同期
さまざまな機能
I
耐故障性、認証などをサポート
1
2
3
2
3
3
11 / 31
NTP 同期モード
I
マルチキャスト (LAN 向け)
I
I
リモートプロシージャコール
I
I
定期的に時刻情報をマルチキャストで広報
クライアントが (複数) サーバーに時刻情報を要求
ピアプロトコル
I
複数のピアの間で同期
12 / 31
NTP ピアプロトコル
相手とのオフセットと通信遅延を計測
I a = T2 − T1
b = T3 − T4
I clock offset: θ = (a + b)/2 (RTT が対称だと仮定)
I roundtrip delay: δ = a − b
T2
T3
A
B
T1
T4
全てのメッセージに以下を含める
I T3: send time (current time)
I T2: receive time
I T1: send time in received message
13 / 31
NTP システムモデル
I
クロックフィルタ
I
I
クロック選択
I
I
I
I
各ピアからの時刻情報を時系列に平滑化
互いに一致しているクロックを抜き出す
インターセクションアルゴリズム: 外れ値の除外
クラスタリング: 最善値の選択
クロック統合
I
推定値を 1 個に統合
Phase-Locked
Oscillator
Clock Filter
Network
Clock Filter
Clock
Selection
Clock
Combining
Loop Filter
Clock Filter
VCO
14 / 31
BSD UNIX の BPF タイムスタンプ
I
通常、割り込み処理 2 回の後タイムスタンプ
I
recv packet, DMA complete
interrupt
service time
interrupt
service time
OS
network
card
wire
packet input
processing
filtering
BPF
device
driver
header
copy
packet
recv
interrupt
DMA
setup
DMA
complete
interrupt
DMA to
OS memory
timestamp
packet
time
15 / 31
ネットワークトラフィックの時系列解析
時間とともに変化する動的な挙動の解析
I
数学的な取り扱いは難しい
I
限られたツール
トピック
I
自己相関 (autocorrelation)
I
定常過程 (stationary process)
I
長期記憶 (long-range dependence)
I
自己相似トラフィック (self-similar traffic)
16 / 31
ネットワークトラフィックの自己相関
I 過去の状態の影響 (トレンド) と周期性 (日、週、季節)
I 自己相関 (autocorrelation): 同一変数の異なる時間の値の相関
4e+07
4
3.5e+07
normalized traffic volume
traffic volume (bps)
3e+07
2.5e+07
2e+07
1.5e+07
1e+07
5e+06
2
0
-2
-4
0
100
200
300
400
time (sec)
500
0
600
1
1
0.8
0.8
correlation
correlation
0
0.6
0.4
0.2
500
1000
1500
2000
time (sec)
2500
3000
3500
0.6
0.4
0.2
0
0
0
20
40
60
k
80
100
0
20
40
60
80
100
k
(左) 実トラフィック (右) 乱数から生成したトラフィック (上) 時系列グラフ (下) 自己相関
17 / 31
自己相関とラグプロット
I
ラグ (lag) プロット: xi と xi+k の散布図
I
I
自己相関の存在を確認する簡単な方法
k を大きくすると長周期の繰り返しパターンを発見可能
4e+07
4
3.5e+07
3
2
3e+07
1
xi+1
xi+1
2.5e+07
0
2e+07
-1
1.5e+07
-2
1e+07
-3
5e+06
-4
0
5e+06 1e+07 1.5e+07 2e+07 2.5e+07 3e+07 3.5e+07 4e+07
xi
-4
-3
-2
-1
0
xi
1
2
3
4
ラグプロットの例: (左) 実トラフィック (右) 乱数から生成したトラフィック
18 / 31
自己相関
I
確率過程 (stochastic process)
{x(t), t ∈ T }
I
自己相関 (autocorrelation): 同一変数の時刻 t1 の値と t2 の値
の相関
I
自己相関関数 (autocorrelation function)
R(t1 , t2 ) = E [x(t1 )x(t2 )]
I
自己共分散 (autocovariance)
Cov (t1 , t2 ) = E ((x(t1 )−µt1 )(x(t2 )−µt2 )] = E [x(t1 )x(t2 )]−µt1 µt2
19 / 31
定常過程 (stationary process)
I
時系列 Xt が定常過程
I
I
平均が変化しない: E (Xt ) = µ
かつ自己共分散が k にのみ依存
γk = Cov (Xt , Xt+k ) = E ((Xt − µ)(Xt+k − µ))
γ0 = Var (Xt ) = E ((Xt − µ)2 )
I
自己相関係数 (autocorrelation coefficient)
I
I
自己共分散を分散で正規化
過去からの影響を示す
ρk =
γk
γ0
20 / 31
ホワイトノイズ
ホワイトノイズ: 定常過程で自己相関係数が 0
ρk = 0 (k 6= 0)
IID 過程 (independent identically distributed process)
I 平均と分散が一定のホワイトノイズ
I
I
確率過程の話に必ず出てくる
Xt が互いに独立で同じ分布に従う
I
I
independent: Xt が互いに独立 (無相関)
identically distributed: Xt が同じ分布に従う
21 / 31
非定常過程
I
非定常
I
I
数学的な扱いが困難
I
I
平均または自己共分散が時間とともに変化
一般には時系列の差分を取って定常化する必要
定常判定
I
パワースペクトル密度を調べ
I
I
べき指数が 1.0 より大きい場合は非定常
ネットワークでは非定常なトラフィックが観測される
I
輻輳、DoS/flooding 等の攻撃
22 / 31
パワースペクトル密度 (power spectral dencity)
I
定常過程のパワースペクトル密度は自己相関関数のフーリエ
変換
I
I
時間領域から周波数領域への変換
時系列データを sin,cos の重ね合わせで表現
∫ ∞
S(f ) =
R(τ )e −2πif τ dτ
−∞
I
パワースペクトル密度
P(f ) ≡ |S(f )|2 + |S(−f )|2 , 0 ≤ f < ∞
I
パワースペクトル密度は各周波数成分の平均パワーを示す
23 / 31
パワースペクトル密度の性質
I
ホワイトノイズ (無相関): P(f ) ∼ const
I
自己相似 (長期記憶): P(f ) ∼ f −α , 0 < α ≤ 1.0
I
1/f ゆらぎ (パワーが周波数に反比例): α = 1.0
非定常: α > 1.0
1e+10
real
surrogate
1e+08
1e+06
P(f)
I
10000
100
1
0.01
1
10
100
1000
10000
f
例: (赤) 実トラフィック (緑) 乱数から生成したトラフィック
24 / 31
短期記憶と長期記憶
自己共分散は各々の時差 k の影響を個別に示す。
全体を見るために全ての時差 k について自己共分散の総和を取る
I
短期記憶性
I
∑
k
ρ(k) が有限
∞
∑
|ρ(k)| < ∞
k=0
I
I
ρ(k) が指数関数と同様か、より早く減衰
特徴
I
I
I
平均値周辺でゆらぐ
遠い過去の影響はない
長期記憶性
I
∑
k
ρ(k) が発散
∞
∑
|ρ(k)| = ∞
k=0
I
I
自己相関係数が双曲線的に減衰
特徴
I
平均から大きく外れた値が観測される
25 / 31
パレート分布 (pareto distribution)
確率密度関数 (PDF)
f (x) =
α κ α+1
( )
, (x > κ, α > 0)
κ x
κ : minimum value of x, α : pareto index
if α ≤ 2, variance → ∞. if α ≤ 1, mean and variance → ∞.
1
pareto ( =1, =1)
pareto ( =2, =1)
pareto ( =3, =1)
exponential (µ=1)
0.1
ccdf
0.01
0.001
0.0001
1e-05
1
10
x
100
パレート分布の CCDF (log-log scale)
26 / 31
自己相似トラフィック
ネットワークトラフィックは厳密な自己相似ではないが、場合に
よって他より良いモデルを与える
I
スケールフリー
I
長期記憶
I
自己共分散がべき的に減衰
ρ(k) ∼ k −α (k → ∞) 0 < α < 1
I
同様にパワースペクトル密度もべき的に減衰
I
低周波成分 (遠い過去) の影響が大きい
P(f ) ∼ |f |−α (f → 0)
I
分散が発散
27 / 31
ネットワークトラフィックの自己相似性
I
(左) 指数関数モデル (中) 実トラフィック (右) 自己相似モデル
I
時間粒度: (上)10sec (中)1 sec (下)0.1 sec
15000
10000
5000
20
40
60
Time (10sec)
80
20
40
60
Time (10sec)
80
5000
0
0
100
20
40
60
Time (1sec)
80
500
0
0
100
20
40
60
Time (1sec)
80
Packet flow
20
40
60
Time (0.1sec)
80
100
50
0
0
80
100
20
40
60
Time (1sec)
80
100
500
0
0
150
100
50
40
60
Time (10sec)
1000
100
150
100
20
1500
Flow density
Packet flow
Flow density
0
1000
500
150
Flow density
0
10000
1500
1000
0
0
5000
100
1500
0
0
10000
Flow density
0
0
15000
Flow density
Packet flow (byte)
Flow density
15000
20
40
60
Time (0.1sec)
80
100
100
50
0
0
20
40
60
Time (0.1sec)
80
100
28 / 31
課題 2
I
正規分布する疑似乱数の生成
I
I
ヒストグラムの作成
I
I
一様乱数から正規乱数を生成するプログラム作成
適切なビン幅の選択、プロットの作成
信頼区間の計算
I
サンプル数によって信頼区間が変化することを確認
29 / 31
まとめ
インターネットの時間変化を計る
I
インターネットと時刻
I
時系列解析
I
課題 2
30 / 31
次回予定
12/1 休講 12/11 に振替
第 8 回 インターネットの挙動を計る (12/8)
I
トラフィック量
I
経路情報
I
インターネット計測とプライバシー
第 9 回 インターネットの異常や問題を計る (12/11)
I
異常検出
I
スパム判定
I
ベイズ理論
31 / 31