Trema/MyRoutingSwitch(3), ダイクストラ法デバッグ - # cat /var/log/stereocat

えーと。案の定というかなんというか。最短経路検索の実装がおかしかったですね。

下図のようなトポロジでデバッグプリント出して L2 routing の処理を追いかけてみました。非対称なトポロジにしないと動作テストとしてはダメだよねやっぱり。

ofvm01 (192.168.11.126) から ofvm07 (192.168.11.120) へ ping を撃つときに出力されるデバッグプリントを追って確認してみます。(とりあえずは個人的なメモとして。)

[追記 2013-05-03] わりと投げやりな感じで書いたので + またコードいじったので全体的に内容見直し。

Step.1

以下「ノード」はスイッチ(OFS)の事だと思ってください。あと、リンクコストは固定で全部 10 にしてあります。(LLDPで動的にリンク情報を取得しているので、リンクコストとして適切な値が取れていない。)

IPv4: dpid:1, port:5, 192.168.11.126->192.168.11.120
[get_path], start:7, goal:1
---------------:--------------------------
remains        : [5, 6, 1, 2, 3, 4]
dist table     : {5 => 99999, 6 => 99999, 1 => 99999, 7 => 0, 2 => 99999, 3 => 99999, 4 => 99999, }
pred table     : {5 => , 6 => , 1 => , 7 => , 2 => , 3 => , 4 => , }
base (dist)    : 7 (0)
neighbors      : [6, 4]
next dist tbl  : {5 => 99999, 6 => 10, 1 => 99999, 7 => 0, 2 => 99999, 3 => 99999, 4 => 10, }

最終的には dpid:0x1 (ovsbr0) → dpid:0x7 (ovsbr6) への経路を求めるわけですが、経路探索上は逆順になっています。探索していく中で、あるノード(ここではOFS)の一つ前のホップがわかるようになっているからで、ゴール→スタートまで探索がおわると、スタート→ゴールの経路がたどれるような結果が得られます。これが pred で、pred[dpid] で dpid の一つ前にたどるノードの dpid が得られます。初期状態ではまだ何も確定していないので中身は空っぽです。

その他使っているデータはこんな感じ

base: 現在基点としているノードの dpid
dist: 各ノードのスタートからのコスト(距離) (dist[dpid] #=> 基点からdpidまでの距離)
remains: 未確定のノードのリスト
neighbors: 基点としているノードに隣接しているノードのリスト(dpidのリスト)
next dist: 基点隣接ノードのコスト更新後の dist

処理

最初は初期状態なので、基点 = スタート(dpid:0x7), コストは初期値(99999は定数として決めてあります)。
未確定(remains)ノードのうち、距離(dist)が最小のノードを基点として選択 (Step.1ではstart:0x7)
- 選択されたら remains からは削除
- 本当は priority queue から取り出す、というような操作だけど priority queue クラス作るのが面倒だったので、距離最小ノード選択だけ実装してる。
基点(0x7)に隣接するノード: 0x4, 0x6
隣接ノードのコストを更新
- コストは、今テーブルに入っている値より今の基点(base_dpid)を元にしたコストの方が小さければテーブルの値を更新します。更新するときに、pred に基点 dpid を入れておきます。(ノードのコストがどのノードを基点とした値で更新されたのか→どのノードが「ひとつ前」なのか、を記録しておく)

step	remains	base	neighbors	distance
1	0x1,0x2,0x3,0x4,0x5,0x6	0x7	0x4,0x6	0x4(10),0x6(10)

Step.2

---------------:--------------------------
remains        : [5, 6, 1, 2, 3]
dist table     : {5 => 99999, 6 => 10, 1 => 99999, 7 => 0, 2 => 99999, 3 => 99999, 4 => 10, }
pred table     : {5 => , 6 => 7, 1 => , 7 => , 2 => , 3 => , 4 => 7, }
base (dist)    : 4 (10)
neighbors      : [3, 6, 7]
next dist tbl  : {5 => 99999, 6 => 10, 1 => 99999, 7 => 0, 2 => 99999, 3 => 20, 4 => 10, }

未確定のうち距離が最小: 0x4 → 基点
基点の隣接ノード: 0x3, 0x6, 0x7(0x7は確定済みなのでパス)
隣接ノードのコストを更新

step	remains	base	neighbors	distance
2	0x1,0x2,0x3,0x5,0x6	0x4	0x3.0x6.~~0x7~~	0x3(20).0x6(10)

Step.3-6

---------------:--------------------------
remains        : [5, 1, 2, 3]
dist table     : {5 => 99999, 6 => 10, 1 => 99999, 7 => 0, 2 => 99999, 3 => 20, 4 => 10, }
pred table     : {5 => , 6 => 7, 1 => , 7 => , 2 => , 3 => 4, 4 => 7, }
base (dist)    : 6 (10)
neighbors      : [4, 5, 7]
next dist tbl  : {5 => 20, 6 => 10, 1 => 99999, 7 => 0, 2 => 99999, 3 => 20, 4 => 10, }
---------------:--------------------------
remains        : [1, 2, 3]
dist table     : {5 => 20, 6 => 10, 1 => 99999, 7 => 0, 2 => 99999, 3 => 20, 4 => 10, }
pred table     : {5 => 6, 6 => 7, 1 => , 7 => , 2 => , 3 => 4, 4 => 7, }
base (dist)    : 5 (20)
neighbors      : [6, 2]
next dist tbl  : {5 => 20, 6 => 10, 1 => 99999, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }
---------------:--------------------------
remains        : [1, 2]
dist table     : {5 => 20, 6 => 10, 1 => 99999, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }
pred table     : {5 => 6, 6 => 7, 1 => , 7 => , 2 => 5, 3 => 4, 4 => 7, }
base (dist)    : 3 (20)
neighbors      : [1, 2, 4]
next dist tbl  : {5 => 20, 6 => 10, 1 => 30, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }
---------------:--------------------------
remains        : [2]
dist table     : {5 => 20, 6 => 10, 1 => 30, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }
pred table     : {5 => 6, 6 => 7, 1 => 3, 7 => , 2 => 5, 3 => 4, 4 => 7, }
base (dist)    : 1 (30)
neighbors      : [3, 2]
next dist tbl  : {5 => 20, 6 => 10, 1 => 30, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }

step	remains	base	neighbors	distance
3	0x1,0x2,0x3,0x5	0x6	~~0x4~~.0x5.~~0x7~~	0x5(20)
4	0x1,0x2,0x3	0x5	0x2,~~0x6~~	0x2(30)
5	0x1,0x2	0x3	0x1,0x2,~~0x4~~	0x1(30),0x2(30)
6	0x2	0x1	0x2,~~0x3~~	0x2(30)

というのを繰り返していきます。リンクコストが固定で、リンクが交差する面倒なところがないので、コストの書き換えとかほとんど起こらないですね。

Step.7

---------------:--------------------------
remains        : []
dist table     : {5 => 20, 6 => 10, 1 => 30, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }
pred table     : {5 => 6, 6 => 7, 1 => 3, 7 => , 2 => 5, 3 => 4, 4 => 7, }
base (dist)    : 2 (30)
neighbors      : [1, 5, 3]
next dist tbl  : {5 => 20, 6 => 10, 1 => 30, 7 => 0, 2 => 30, 3 => 20, 4 => 10, }
flow_mod: dpid:1/port:1 -> dpid:3
flow_mod: dpid:3/port:3 -> dpid:4
flow_mod: dpid:4/port:3 -> dpid:7

未確定(remains)がなくなったら終わりです。