Topology Discovery for Large Ethernet Networks

★前提知識
ブリッジaのポートx上の転送テーブルの内容をF(a, x)、
それ以外のポートの転送テーブルの内容の和集合をT(a, x)とする。
つまり、ポートx1, x2,...,xnを持つブリッジaのT(a, x1)は
T(a, x1) = F(a, x2) ∪ F(a, x3) ∪ ... ∪ F(a, xn)
となる。

★単純接続定理(Simple Connection Theorem)
あるbridge network上にあるブリッジaとb、aのポートx、bのポートyというペアが
T(a, x) ∩ T(b, y) = φ　を満たすならば、それらは単純接続している。
さらに、aのx, bのｙが接続しているならば、T(a, x) ∩ T(b, y) = φである。

ところが、T(a, x) ∩ T(b, y) = φを満たしても、転送テーブルが不十分だったりすると
成立しない。たとえば、
HostA -- BridgeX ------- BridgeY -- HostB
　　　　x:{A}　　y:{B}　x:{A}　　y:{B}
であった場合、BridgeX,Yが接続していることは分かるが、
T(X, y) ∩ T(Y, x) = φ　さらに T(X, x) ∩ T(Y, y) = φ　であるため、
下のように接続しているのか判断できない。
HostA -- BridgeY ------- BridgeX -- HostB

このようなことを防ぐため、最小知識要件(Minimum Knowledge Requirement)が定義されている。
★最小知識要件(Minimum Knowledge Requirement)
単純接続定理を成立させるためには、以下のどれかを満たす必要がある。
1. それぞれのブリッジがお互いのアドレスのエントリを転送テーブルに保持している場合。
　　(out-of-band portsは除く)
　　　　　　　　--- お互いにどっちにいるか分かっているので問題なし。
または、
2. ブリッジaがF(a, x)にブリッジbのエントリをもち、∃k != x: F(b, y)∩F(a,k) != φ
　　　　　　　　--- 片方(a)の在るポートでだけ片方(b)のエントリを持っている場合。
　　　　　　　　　　a上のx以外のあるポートkにおいて、F(b, y)∩F(a,k) != φを満たす。
　　　　　　　　　　すなわち、ブリッジbのポートyがブリッジaのポートxに向いているならば、
　　　　　　　　　　aの他のどれかのポート上の転送テーブルの内容と重複があるはずである。
　　　　　　　　　　ということを言っている。
　　　　　　　　　
または
3. 3つのノードのエントリがaとbで共有され、片方のブリッジでは少なくとも
2つの異なるポートに分かれて保持され、もう一方では３つのポートに分かれていなくては
ならない。対象となっているx, yはそれらのポートに含まれなくてはならない。
∃i,j, i!=j: (F(a, x)∩F(b, i) != φ ∧ F(a, x)∩F(b, j) != φ), さらに、∃k != x: F(b, y)∩F(a,k) != φ
　　　　　　　　--- どっちのエントリにも入ってない場合

　　　　x:{A}　　y:{B,C} 　x: {A}　y:{B}
HostA -- BridgeY ------- BridgeX -- HostB
　　　　　　　　　　　　　　　　　 | z:{C}
　　　　　　　　　　　　　　　　HostC
であるとき、
T(Y, y) = {A}, T(X, x) = {B, C}でT(Y, y) ∩ T(X, x) = φ
かつT(Y, x) ∩ T(X, y) != φ

7.3: VLANがあると、object id等にvlan idを指定する必要あり。
7.5: 取得フェーズで移動が起きるとconflictの原因になる。この場合は、もう一度やり直す。
javaのコードで、2000ノード/50ブリッジで25秒でトポロジを把握。問題なし。