複数観測点結果との比較

(1) 検証方法

インターネット全体での経路変動を対象とした検証を行うため，複数点観測の結果と比 較する検証方法を考案した．本方法は，複数点観測で得たイベントをリファレンスとし，

一点観測で得たイベントがこれと矛盾しないかどうかを確認する．このため，以下の3つ の条件により，複数点観測と一点観測のイベントクラスタの対応づけを行う．一点目は発 生時刻の差がイベント間閾値 te 以下であること，二点目は双方のイベントクラスタの発 生箇所候補が1つ以上の共通のASを持つこと，三点目は双方のイベントクラスタが1つ

以上の共通のプレフィクスを有することである．

イベントクラスタ間の対応関係は，図 7-6のように分類される．全てのプレフィクスが 完全に一致するか((a-1)の場合)，一点観測のプレフィクスの全てが複数点観測のイベント クラスタに含まれる場合((a-2)の場合)は，イベント推定結果に矛盾がないと判断する．一 点観測において，複数点観測に存在しないプレフィクスを含むか((b-1)の場合)，複数点観 測が，複数の一点観測のイベントクラスタと対応づけられる場合((b-2)の場合)は，イベン ト推定結果に矛盾があると判断する．また，複数点観測に対応する一点観測のイベントク ラスタが存在しない場合((c)の場合)も考えられるが，これについては解析対象外とする．

複数点観測

(a-1)

(a) 矛盾がない場合

一点観測

p₁, p₂ p₁, p₂

(a-2) p₁, p₂ p₁

(c) 不明な場合 p₁, p₂ (b) 矛盾がある場合

(b-1) p₁, p₂ p₁, p₂, p₃

(b-2) p₁, p₂ p₁

p2

複数点観測の イベントクラスタ

一点観測の イベントクラスタ

t_e t_e p₁

p₁

none p₂

p₂

p_1-3: プレフィクス，　t_e: イベント間閾値

図 7-6 複数観測点結果を用いた検証方法

(2) 検証結果

表 7-2に，上記の場合別のイベントクラスタ数とその割合，および，一点観測結果が矛 盾を生じなかった割合（無矛盾率と呼ぶ）を示す．トポロジー優先アルゴリズムにおける 無矛盾率は90.2％であり，時間優先アルゴリズムでの無矛盾率45.9％に比べて著しく高か った．従って，BGPビーコンのような限定されたイベントだけでなく，インターネット上 のイベント全体においても，時間優先アルゴリズムに比べてトポロジー優先アルゴリズム は，イベントを，より正確に識別できたと言える．また，3 ヶ月間のイベントクラスタ総

数917,842をもとに計算すると，1分間平均で6.93イベントを観測していることとなり，

イベント間閾値 90 秒以内に，多数の同時イベントが発生していることを裏付ける結果と 言える．

表 7-2 複数点観測と一点観測の比較結果

矛盾あり 矛盾なし アルゴリズム 総数

(a-1) (a-2) (b-1) (b-2) 無矛盾率

時間優先 400,568 (43.6％)

20,916 (2.28％)

445,820 (48.6％)

50,538

(5.51％) 45.9％

トポロジー優先

917,842

781,367 (85.1％)

46,324 (5.05％)

84,055 (9.16％)

6,096

(0.66％) 90.2％

一点観測は AS7018 を，複数点観測では AS7018, AS293, AS3257, AS1668, AS5511,

AS2497を使用．無矛盾率は，100×(矛盾なし数／総数)で計算．

(3) トポロジー優先アルゴリズムの導入効果

トポロジー優先アルゴリズムの導入効果を分析するため，時間優先アルゴリズムにおい て矛盾を生じた原因について分析した．時間優先アルゴリズムにおいて，(b-1)に該当する 全てのサンプルにおいて，観測点の隣接AS が候補として含まれていた．つまり，インタ ーネット全体で48.6％のイベントが，隣接ASが偶然一致する同時イベントが原因で，ク ラスタ化の誤りを生じたものと考えられる．なお，(b-2)のサンプルは，(b-1)のサンプルと 近い時刻に発生しており，同じイベントクラスタに入るべきプレフィクス別クラスタの一 部が，上記の隣接ASの一致が原因で，先に別のイベントクラスタに入れられたために発 生したものであった．

これに該当する典型的な例を，図 7-7に示す．この事例は，複数点観測における2つの イベントクラスタ e1, e2 が，一点観測において，異なるプレフィクスで構成されるイベン トクラスタ e1, e2 として誤って推定されており，それぞれ図 7-6の(b-1),(b-2)の場合に相 当する．一点観測において，AS701 がAS5839よりも先に共通部として抽出されたため，

推定誤りが発生している．この現象は，図 7-3で示した事例と類似しており，トポロジー 優先アルゴリズムの導入により，矛盾を回避できた．

複数点観測 (o₁-o₆)

e₁': 2005/08/01 09:39:08, プレフィクス数: 8, 共通部: 701 一点観測 (o₁)

701 688 1239 701 688 701 688 145 701 688 145 701 702 1913 5839 702 1913 5839 1239 1913 5839 702 1913 5839 p₁-p₂

p₁-p₂ p₃-p₇ p₃-p₇ o₁-o₂, o₄, o₆ o₅

o₁-o₂, o₄, o₆ o₃, o5

e₁: 2005/08/01 09:39:08, プレフィクス数: 7, 共通部: 701 688

o₁, o₆, o₈ o₁, o₆, o₈ o2, o4-o5

o₃, o8

p₈ p9

p_8-p₉ p_8-p₉

e2: 2005/08/01 09:39:54, プレフィクス数: 2, 共通部: 1913 5839

701 688 701 688 145 701 702 1913 5839 o₁

o₁ o1

p₁-p₂ p₃-p₇ p₈

e2': 2005/08/01 09:39:08, プレフィクス数: 1, 共通部: 702 1913 5839 702 1913 5839

o₁ p₉

o_1-8: 観測点，　p_1-9: プレフィクス e_1-2, e'_1-2: イベントクラスタ

図 7-7 時間優先アルゴリズムでの推定誤りの例

(4) トポロジー優先アルゴリズムにおける矛盾

トポロジー優先アルゴリズムにおいて矛盾を生じた原因について分析した．主な原因は，

複数の同時イベントにおいて，観測点の隣接ASが共通に含まれていたことであった．こ れに該当するイベントクラスタは相対的にプレフィクス数が少ない傾向があり，AS ホッ プ数が大きい共通のASが見つからなかったことが要因（要因1とする）と考えられる．

トポロジー優先アルゴリズムでの矛盾のうち約80％はこれに該当した．

その他の要因として，優先経路の選択の誤りに起因するものがあった（要因2とする）．

提案手法では，AS パス長が短い方を優先経路と判断している．トポロジー優先アルゴリ ズムで矛盾を生じたサンプルのいくつかにおいて，AS パス長が長い方を優先経路と推定 した場合，複数点観測の結果と矛盾を生じない場合が存在した．

次に，上記の推定誤りを回避するための，トポロジー優先アルゴリズムの改良案につい て提案する．要因1については，隣接ASのみが発生箇所候補となるイベントクラスタに ついては，プレフィクス数に閾値を設け，プレフィクス数が閾値以下の場合には，推定対 象から除外する方法が考えられる．なお，正しく抽出されたイベントクラスタを除外する リスクを伴う方法である．要因2については，旧経路，新経路の双方を優先経路として試

行する方法が考えられる．これにより，発生箇所候補は増えるものの，優先経路の判定誤 りによる推定誤りを回避することができる．