トポロジ検出アルゴリズム

SNMPを用いてNW機器から収集したFDBからリンクレイヤのトポロジを検出する 研究が存在する[21][22]．ネットワークのトポロジの検出にあたり，NW機器同士が一つ のNW機器を介してでも接続されている場合を「接続」，一つの物理線で接続されている 場合を「直接接続」されていると定義している．また，トポロジの検出に用いる条件式内 の表記法について以下のように定義されている．

• Cip：NW機器iのポートpに接続されているNW機器の集合

• Djq：NW機器jのポートqに直接接続されているNW機器 直接接続を検出するため，以下の三つの条件式が示されている．

• 条件1：C_ip={j} ⇒D_ip =j

• 条件2：(D_ip =j)∧(C_jq ∋i)⇒D_jq =i

• 条件3：(C_ip ∋j)∧(C_jq ∋i)∧(C_ip∩C_jq)̸=ϕ⇒D_ip̸=j

ネットワークのトポロジを検出するためには，NW機器同士が直接接続されているかどう かを決定する必要がある．まずNW機器間の接続の関係については，表4.1から抽出する ことが可能である．表4.2に図4.1のNW機器間の接続関係を示す．

表 4.2: NW機器間の接続関係

NW機器間の直接接続を決定するには，以下の(1)〜(3)を新たな直接接続を決定でき なくなるまで繰り返す．

(1) 条件1を表4.2に適用し，各列の中で唯一に決まるポートを選択し，直接接続を決 定する．

(2) (1)の結果について条件2を適用する．

(3) (2)(3)の結果から同一ポートに接続される他のNW機器は直接接続ではない．

図4.1のネットワークを上記の条件式を実際に適用していくと図4.2のようになる．こ のトポロジでは，8ステップでNW機器のみからなるトポロジの直接接続関係を検出でき ていることがわかる．図中の丸で囲われた数字は検出された直接接続関係を表し，バツで 上書きされている数字は，直接接続関係ではないことを表している．

1

条件１: 𝐶_#$= 𝑗 ⇒ 𝐷_#$ = 𝑗

𝐶_{)*+ ,}= 𝑊𝐵 ⇒ 𝐷_{)*+ ,} = 𝑊𝐵

2

3 4

5 6

7 8

条件２: (𝐷_#$= 𝑗) ∧ (𝐶₂₃∋ 𝑖) ⇒ 𝐷₂₃= 𝑖

(𝐷_{)*+ ,}= 𝑊𝐵) ∧ 𝐶_{+6 7}∋ 𝐻𝐺𝑊 ⇒ 𝐷_{+6 7}= 𝐻𝐺𝑊

条件１: 𝐶_#$= 𝑗 ⇒ 𝐷_#$= 𝑗

𝐶_{:;<7 ,}= 𝑃𝐿𝐶2 ⇒ 𝐷_{:;<7 ,}= 𝑃𝐿𝐶2

条件２: (𝐷_#$= 𝑗) ∧ (𝐶₂₃∋ 𝑖) ⇒ 𝐷₂₃= 𝑖

(𝐷_{:;<7 ,}= 𝑃𝐿𝐶2) ∧ 𝐶_{:;<, ,}∋ 𝑃𝐿𝐶1 ⇒ 𝐷_{:;<, ,}= 𝑃𝐿𝐶1

条件１: 𝐶_#$= 𝑗 ⇒ 𝐷_#$= 𝑗

𝐶_{;,A+ B}= 𝐻𝐺𝑊 ⇒ 𝐷_{;,A+ B}= 𝐻𝐺𝑊

条件２: (𝐷_#$= 𝑗) ∧ (𝐶₂₃∋ 𝑖) ⇒ 𝐷₂₃= 𝑖

(𝐷_{;,A+ B}= 𝐻𝐺𝑊) ∧ 𝐶_{)*+ 7}∋ 𝐿2𝑆𝑊 ⇒ 𝐷_{)*+ 7}= 𝐿2𝑆𝑊

条件１: 𝐶_#$= 𝑗 ⇒ 𝐷_#$= 𝑗

𝐶_{;,A+ D}= 𝑃𝐿𝐶1 ⇒ 𝐷_{;,A+ D} = 𝑃𝐿𝐶1

条件２: (𝐷_#$= 𝑗) ∧ (𝐶₂₃∋ 𝑖) ⇒ 𝐷₂₃= 𝑖

(𝐷_{;,A+ D}= 𝑃𝐿𝐶1) ∧ 𝐶_{:;<7 7}∋ 𝐿2𝑆𝑊 ⇒ 𝐷_{:;<7 7}= 𝐿2𝑆𝑊

図 4.2: トポロジ検出アルゴリズムの適用

この結果から表4.3のNW機器間の直接接続関係を得る．図4.3に検出されたNW機器

のみからなるトポロジを示す．

表 4.3: NW機器間の直接接続関係

図 4.3: NW機器のみからなるトポロジ

エンド端末に関しては，図4.4のように，各FDBからNW機器の接続元ポートの接続 先エンド端末が一つのみの場合，直接接続されていることを検出することができる．図中 の丸で囲まれた数字が直接接続を検出されたエンド端末を示している．

図 4.4: エンド端末に関する処理

条件1，2で直接接続を決定できない場合がある．図4.5に示すNW機器のみからなる トポロジについて考える．NW機器Aから情報を完全に得られない場合，HGWとNW 機器Bとが直接接続していることになり，NW機器Aの存在がわからなくなるだけであ る．一方で，NW機器Bから情報が完全に得られない場合，条件1を用いてNW機器A， C間の直接接続を決定するだけで，NW機器A，C，D間の直接接続を決定することはで きない．これは，NW機器間A，C，D間で接続媒体を共有しているようなネットワーク でも同様のことが言える．そこで，条件3を用いることで，条件1，2だけでは検出でき なかった直接接続を決定できる場合がある．

図 4.5: ネットワークトポロジ例

• (C_{P LC22}∋P LC3)∧(C_{P LC31}∋P LC2)∧(C_{P LC22}∩C_{P LC31})̸=ϕ⇒D_{P LC22}̸=P LC3

• (C_{P LC12}∋P LC3)∧(C_{P LC31}∋P LC1)∧(C_{P LC12}∩C_{P LC31})̸=ϕ⇒D_{P LC12}̸=P LC3

• (C_{P LC12}∋P LC2)∧(C_{P LC22}∋P LC1)∧(C_{P LC12}∩C_{P LC22})̸=ϕ⇒D_{P LC12}̸=P LC2