トポロジー優先アルゴリズムの提案

本研究では，同時イベント時において，メッセージ群をより正解にクラスタ化する改良 手法を提案する．なお，前節で説明したプレフィクス間のクラスタ化アルゴリズムは，プ レフィクス別クラスタを単純に発生時刻順に比較するため，時間優先アルゴリズムと呼ぶ．

従来手法はクラスタ化の順序について明確に記述していないが，本研究では，従来手法が 時間優先アルゴリズムに従っているものと考えている．

提案アルゴリズムは，観測点から遠いASを共通に持つ2つのプレフィクス別クラスタ を，より優先的にクラスタ化する．これは，一般に，観測点で得られる経路は観測点を根 とする木構造となり，観測点から遠いASを含む経路変動ほど，異なるイベントにより発 生した可能性が低い可能性が高いからである．そこで，この観測点からの遠さ（距離）を，

観測点からのAS数で表し，ASホップ数と呼ぶ．提案アルゴリズムは，ASパスの情報を 用いるため，トポロジー優先アルゴリズムと呼ぶ．

アルゴリズムの詳細手順を以下に述べる．第1ステップとして，図 7-4上部に示すよう に，イベント間閾値 te 以内に発生した，プレフィクス別クラスタの集合を抽出する．次 に，第2 ステップとして，全プレフィクス別クラスタより全AS を抽出し，AS ホップ数 が大きい順に並べたAS順序列を作成する．あるAS が，異なるASホップ数として複数 の経路に存在する場合は，その最大値がそのASのASホップ数として使用される．複数 のASが同じASホップ数の場合には，これらのASの順序は発生時刻順とする．

第3（最終）ステップでは，図 7-4下部に示すように，3つの集合を用いて，プレフィ

クス別クラスタを再クラスタ化する．初期状態では，全てのプレフィクス別クラスタは未 決定集合に含め，一時的集合，決定集合は空とする．プレフィクス別クラスタは，クラス タ化を実施後，一時的イベントクラスタとして一時的集合に入れる．一時的イベントクラ スタは，プレフィクス別クラスタや他の一時的イベントクラスタと再クラスタ化する．再 クラスタ化できなくなった一時的イベントクラスタは，イベントクラスタとして確定し，

決定集合に入れる．

本アルゴリズムでは，AS順序列より順にASを参照し，そのAS（参照ASと呼ぶ）に 関わる下記の条件 1～6 に従って，全てのプレフィクス別クラスタ，一時的イベントクラ スタについて，クラスタ化の可否を決定する．

そのASに関して，複数の条件に従い，随時クラスタ化を行う．再クラスタ化を行う場 合として，複数のプレフィクス別クラスタ間（条件 1），プレフィクス別クラスタと一時 的イベントクラスタ（条件2），複数の一時的イベントクラスタ間（条件3）が存在する．

また，プレフィクス別クラスタ，一時的イベントクラスタが，再クラスタ化できない場合，

イベントクラスタとして確定する．よりAS ホップ数が小さいところで再クラスタ化でき ない行う方針である．参照AS が同じものが存在する場合（条件 4）は，その一時的イベ ントクラスタに，条件2，3が適用できないので，終了する．

条件1: 参照ASが一時的集合のいずれのプレフィクス別クラスタにも含まれず，2つ以上 のプレフィクス別クラスタに含まれる場合，それらのプレフィクス別クラスタを含む新し い一時的イベントクラスタを作成し，一時的集合に入れる．

条件2: 参照ASがプレフィクス別クラスタに含まれ，かつ，ある一時的イベントクラスタ 内の全プレフィクス別クラスタに含まれる場合，この一時的イベントクラスタとプレフィ クス別クラスタを，新しい一時的イベントクラスタとして，再クラスタ化する．

条件 3: 参照 AS が複数の一時的イベントクラスタの全てのプレフィクス別クラスタにも 含まれる場合，これらの一時的イベントクラスタを，新しい一時的イベントクラスタとし て再クラスタ化する．

条件 4: 参照 AS がある一時的イベントクラスタの少なくとも一つのプレフィクス別クラ スタに含まれ，参照ASが同じ一時的イベントクラスタの他のプレフィクス別クラスタに 含まれない場合，この一時的イベントクラスタをイベントクラスタとして確定し，決定集 合に入る．

条件5: 参照ASがある一時的イベントクラスタの全プレフィクス別クラスタにも含まれ，

かつ，それらのプレフィクス別クラスタの経路において参照ASのASホップ数が1の場 合，その一時的イベントクラスタをイベントクラスタとして確定し，決定集合に入れる．

条件6: 全てのAS順序列を検査した後，参照ASがある未決定集合の一つのプレフィクス 別クラスタのみに含まれる場合，そのプレフィクス別クラスタを，イベントクラスタとし て確定し，決定集合に入れる．

条件4

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

プレフィクス別クラスタ

AS順序列:

a

a

a

a

a

a

a

a

a

a

:

te

t_e

プレフィクス別クラスタ

参照AS 優先経路

<第1ステップ>

< 第 2 ステップ >

未決定集合 一時的集合 決定集合

a

a

a

a

a

a

a

a

a

a

a

a

a

一時的イベントクラスタ プレフィクス別クラスタ

a

a

a

a

a

a

a

a

共通のAS 条件1

< 第 3 ステップ >

a

a

a

a

a

共通のAS

a

a

a

a

a

a

a

a

a

a

a

条件6

a

a

a

a

a

a

a

a

a

a

a

a

a

未決定集合 一時的集合 決定集合

< 第 1 ステップおよび第 2 ステップ >

プレフィクス別クラスタ 一時的イベントクラスタ

プレフィクス別クラスタ イベントクラスタ

条件2

図 7-4 トポロジー優先アルゴリズムの振舞い

本アルゴリズムを用いて，図 7-3で例示したプレフィクス別クラスタの集合が，正しい イベントクラスタとして抽出される様子を図 7-5に示す．AS順序列に従い，参照AS と して a2 が検査される前に，a4 が検査される．その結果，参照 AS を a4 としたときに，

p2 と p3 のプレフィクス別クラスタを，一つの一時的イベントクラスタにクラスタ化する．

次に，参照AS を a8 としたとき，p1 と p4 のプレフィクス別クラスタを，別の一時的イ ベントクラスタにクラスタ化する．最終的に，2 つの同時イベントを，独立なイベントと して正しく抽出する．

図 7-5 トポロジー優先アルゴリズムの適用例