一覧NW-09-1 · 動的ルーティングの入口

ルーティング情報の更新と収束

古い情報による転送ループと、リンク状態更新後の経路を確認します。

説明

動的ルーティングでは、装置が経路やリンクの情報を交換して転送先を更新します。障害が起きても、すべての装置が同時に新しい情報へ切り替わるわけではありません。

前半は距離ベクトルの単純なモデルで古い情報を信じた場合の循環を確認します。後半はリンク状態から最短経路を計算し、障害検出・情報交換・計算・転送表更新という収束までの流れを調べます。

1隣接装置の古い距離を信じた場合

宛先Nへ直接つながるAは距離1、A経由のBは距離2でした。AとNのリンクが切れた直後、Bが古い距離2を通知した条件です。

distance=変更前の距離{"A":1,"B":2}; next_hop=変更前の次ホップ{"A":"N","B":"A"}; distance["A"]=古い広告を採用distance["B"]+1; next_hop["A"]="B"Aの転送先を変更; (distance,next_hop)循環する対応

AはB経由で距離3と誤認し、BはA経由のままです。A→B→Aと循環します。このモデルではsplit horizon等の抑止策を外して、古い情報で起きる問題を確認します。

2距離が増え続ける過程

AとBが交互に相手の値へ1を加え、RIPと同じく16を到達不能の上限にします。

for turn in range(7):広告の交換を繰り返す

distance["B"]=Bの距離を更新

min(16,distance["A"]+1)

distance["A"]=Aの距離を更新

min(16,distance["B"]+1)

print各回の値(turn+1,distance.copy())

実際には宛先へ届かないのに距離だけが増え、最後に16へ達します。16は利用可能な16ホップではなく到達不能です。更新タイマーやトリガーは省略したモデルなので、この回数から実時間の収束秒数は求めません。

3学習元への広告を変える

BがAから学んだ経路をAへ通知するとき、poisoned reverseでは距離16を通知します。

learned_from=経路を学んだ相手"A"; advertised_to=広告する相手"A"; metric=保持している距離2; advertised=学習元へは16を通知16 if learned_from==advertised広告する値_to else metric; advertised

Aへ到達不能を通知するため、先ほどの二装置の誤った相互依存を抑えられます。split horizonは学習元への広告を省く方式、poisoned reverseは到達不能として知らせる方式です。これだけであらゆる多装置のループが消えるとは限りません。

4リンク状態の表を用意する

次はA-B-C-Dの構成です。A-Bが1、B-Cが1、A-Cが5、C-Dが1で、逆方向も同じコストです。

graph=リンクとコスト{"A":{"B":1,"C":5},"B":{"A":1,"C":1},"C":{"A":5,"B":1,"D":1},"D":{"C":1}}; graphトポロジーの表

この表は単一エリア内で共有したリンク状態のモデルです。宛先までの距離だけを隣接から聞く方式と異なり、トポロジーを元に各ルーターが経路を計算します。

5最短経路を計算する関数

優先度付きキューで累積コストが最小の候補から取り出します。

def shortest(g,start,goal):始点と終点を指定

import heapq小さいコストから処理

queue=探索の初期状態

[(0,start,[start])]; visited=set()

while queue:候補がある間の探索


        cost,node,path=heapq.heappop(queue)
        if node in visited: continue
        if node==goal: return cost,path
        visited.add(node)
        for peer,weight in g[node].items():
            heapq.heappush(queue,(cost+weight,peer,path+[peer]))

return None経路なし

これは正のコストを持つ小さなグラフの最短経路計算です。OSPF全体の実装ではなく、共有情報から経路を計算する部分を確認します。隣接確立やLSAの配送は、この関数に入る前の処理です。

6故障前の経路

AからDまで計算します。

shortest(graph,"A","D")AからDへの最短経路

A-B-C-Dでコスト3です。A-C-Dのコスト6より小さいため、AはBを次ホップにします。コストはこの例の設定値であり、常に実測遅延を表すわけではありません。

7リンク断を反映して再計算する

B-Cの両方向を削除し、新しいリンク状態が共有された後を計算します。

del graph["B"]["C"]BからCのリンク断; del graph["C"]["B"]逆方向も削除; shortest更新後の計算(graph,"A","D")

A-C-Dのコスト6へ切り替わります。新しい表で計算した結果であり、物理的な切断と同時に全装置がこの状態へ移るという意味ではありません。

8収束までに必要な処理

この例の時刻は、断線0ms、検出30ms、情報共有50ms、計算完了55ms、転送表反映60msです。

events=この例の処理時刻[("link down",0),("detected",30),("LSDB updated",50),("SPF finished",55),("FIB installed",60)]; [(events[i][0]各段階に要した時間,events[i][1]-events[i-1][1]) for i in range(1,len(events))]

検出30ms、共有20ms、計算5ms、反映5msです。収束には計算以外の時間もかかります。途中で旧経路と新経路が混在すると一時的な損失やループが起こり得るため、最終経路だけで障害中の挙動までは説明できません。

まとめ

古い距離情報の相互参照で転送先が循環する場合があります。

リンク状態の共有後に再計算し、転送表へ反映して初めて新しい経路を使えます。

操作履歴と解説を振り返れます。

Python 3

distance={"A":1,"B":2}; next_hop={"A":"N","B":"A"}; distance["A"]=distance["B"]+1; next_hop["A"]="B"; (distance,next_hop)

({'A': 3, 'B': 2}, {'A': 'B', 'B': 'A'})

for turn in range(7):
    distance["B"]=min(16,distance["A"]+1)
    distance["A"]=min(16,distance["B"]+1)
    print(turn+1,distance.copy())

1 {'A': 5, 'B': 4}
2 {'A': 7, 'B': 6}
3 {'A': 9, 'B': 8}
4 {'A': 11, 'B': 10}
5 {'A': 13, 'B': 12}
6 {'A': 15, 'B': 14}
7 {'A': 16, 'B': 16}

learned_from="A"; advertised_to="A"; metric=2; advertised=16 if learned_from==advertised_to else metric; advertised

graph={"A":{"B":1,"C":5},"B":{"A":1,"C":1},"C":{"A":5,"B":1,"D":1},"D":{"C":1}}; graph

{'A': {'B': 1, 'C': 5}, 'B': {'A': 1, 'C': 1}, 'C': {'A': 5, 'B': 1, 'D': 1}, 'D': {'C': 1}}

def shortest(g,start,goal):
    import heapq
    queue=[(0,start,[start])]; visited=set()
    while queue:
        cost,node,path=heapq.heappop(queue)
        if node in visited: continue
        if node==goal: return cost,path
        visited.add(node)
        for peer,weight in g[node].items():
            heapq.heappush(queue,(cost+weight,peer,path+[peer]))
    return None

shortest(graph,"A","D")

(3, ['A', 'B', 'C', 'D'])

del graph["B"]["C"]; del graph["C"]["B"]; shortest(graph,"A","D")

(6, ['A', 'C', 'D'])

events=[("link down",0),("detected",30),("LSDB updated",50),("SPF finished",55),("FIB installed",60)]; [(events[i][0],events[i][1]-events[i-1][1]) for i in range(1,len(events))]

[('detected', 30), ('LSDB updated', 20), ('SPF finished', 5), ('FIB installed', 5)]

演習完了