コンピュータネットワークのリンク状態ルーティングアルゴリズム(LS)

一、知識の準備
リンクステータスルーティングアルゴリズムは、グローバルルーティングアルゴリズムである.このアルゴリズムでは、すべてのネットワークトポロジおよびリンク料金が既知であると仮定し(実際には、通常、各ノードがネットワーク内の他のすべてのノードにリンク状態パケットをブロードキャストすることによって達成される)【OSPFプロトコル】であり、ノードブロードキャストによってすべてのノードがネットワークと同等の完全なビューを備えている.ビューを得る後、ソースノードからネットワークの任意のノードへの最低費用経路をLSアルゴリズムにより算出することができる.以下に示すリンク状態ルーティングアルゴリズムをDijkstraアルゴリズムと呼び,このアルゴリズムを理解する前に,まず以下の記号を理解する.

D(v)：           v          
p(x)：         v（      ）      （v   ）
N'：     v         ，     v  N'   
w：     N'    ，        

.
二、LSアルゴリズムの原理
ルーティング問題をイメージ的に記述し,G=(N,E)はN個のノード(ルータを表す),E個のエッジ(リンクを表す)を有する図(ネットワークトポロジを表す)である.各リンクの数字は、このリンクの料金を表す、図1-1のネットワークトポロジおよびリンク料金図である.
ソースノードがuであると仮定すると、ソースノードから他のノードへの最低消費経路を見つけ、そのアルゴリズムは以下の通りである.

1、   ：
   N' = {u}                                                                                      D(u)  ， u   N'   
   for all nodes for n                                                                       u       n 
        if n is a neighbor of u                                                           n   u       
            then D(n) = c(u，n)                                                           n   D(n) c(u，n)
        else D(n) = ∞                                                                        D(n)    

2、    
    find w not in N' such that D(w) is a minimum                          N'  w【   D(w)】
    add w to N'                                                                              w   N' 
    update D(n) for each neighbor n of w and not in N'              w       n D(n)， n   N' 
        D(n) = min(  D(n) ， D(w)+c(w，n)  ）                                 D(n)  D(n) D(w)+c(w，n)     
    until N' = N                                                                               N' = N     

.
表1-1図1-1におけるネットワーク動作の状態リンクアルゴリズムステップ※初期化段階:uに隣接する全ての隣接ノードv,x,wを探し出し、D(v)=2,D(x)=1,D(w)=5とする.残りuに隣接しないy,zノード,そのリンク料金D(y)=∞,D(z)=∞※第1サイクル:初期化フェーズ終了時に最も費用がかかるノードxを探し出し,その費用は1であり,ノードxをN′に加え,xノードに隣接しN′にないノード(実はv,w,yノード)のD(n)値を更新し,計算式はD(n)=min(D(n)であり,D(x)+c(x,n)),得D(v)=2,D(w)=4,D(y)=2※第2サイクル:第1サイクルフェーズの終了時に最も費用がかかるノードvとyを探し出し,まずyをN′に加え,w,zノードの値を更新し,得D(w)=3,D(z)=4.....すべてのノードがN′に加わるまでサイクルが終了し、最低料金経路:c(u,v)=2,c(u,w)=3,c(u,x)=1,c(u,y)=2,c(u,z)=4が得られる.
LSアルゴリズムが終了すると,各ターゲットノードについて,テーブルから最短料金経路の前のノードを見つけることができる.この前のノードには、最短パスの前のノードがあります.順次類推すると、ソースノードから任意のターゲットノードへの最低消費経路の完全な経路:(u,v):u-v(u,w):u-x-y-w(u,x):u-x(u,y):u-x-y(u,z):u-x-y-uを得ることができるので、uノードルーティングについては、各宛先ノードに記憶するルート最低料金経路の次のホップノードであればよいので、uノードルートテーブルは以下のように生成する.
三、LS振動現象
仮定:1、リンク費用はそのリンクが担持するデータ量である.2、初期ルートはBが反時計回りにAに1単位、Dが時計回りにAに1単位、Cが反時計回りにBにe単位、BがAに1単位を送る.
従って、初期状態は、図3-1 a)に示すように、3-1 a)初期状態のネットワーク料金状態となる.
LSアルゴリズムを再実行すると、B,C,Dルーティングともに時計回りのルーティング料金が最も低いと判断する、図3-1 b)に示すような料金情報:3-1 b)がLSアルゴリズムを再実行した後のネットワーク料金状態が生じる.
図3-1 b)に示すような料金情報を記録する後、再びLSアルゴリズムを実行すると、B、C、Dルータはまた反時計回り方向にパケットを渡し、結果として図3-1 c)に示すように、3回目のLSアルゴリズム実行後のネットワーク料金状態となる.
再びLSアルゴリズムを実行すると、図3-1 d)に示すように、3回目のLSアルゴリズムを実行した後のネットワークコスト状態となる.
このような現象を混雑に敏感なルーティング振動現象と呼ぶが,この現象は,Bルーティングが図3−1 b)の状態にあると仮定し,データをCに転送し,CをDに転送するが,このときDのルーティングテーブルが更新されるとリンク状態が3−1 cになる)という現象を引き起こす可能性が高い.Dは、以前のデータをCに転送し、CはBに転送し、このときルーティングテーブルが更新を開始すると、図3−1 d)に示すようになる.このようにすれば、B,C,D間でデータが転送するAに到達せず、データのTTL=0になるとデータが破棄される.
このような現象に対して、リンク状態アルゴリズムの生産は、すべてのルータがLSアルゴリズムを同時に実行しないことを確保するために、各ルータにリンク通知を送信する時間をランダム化するメカニズムを採用する(すなわち、各ルータがLSアルゴリズムを実行するのは実際には異なる)
転載先:https://blog.51cto.com/13547664/2161510