Trema/MyRoutingSwitch(6), 全対最短経路(1)
はじめに
MyRoutingSwitch(5) のシリーズ ではトポロジの変化に対してどうやって経路迂回させるか、みたいな話をいろいろやってきました。それで、いろいろ試してみたけど、やっぱりリアクティブでやる方法って今ひとつ拡張性とか微妙だなあと。もうちょっとプロアクティブにやる方法を考えたいところだよね、とか考えていたわけです。
という流れの中で考えていたのが最短経路計算のところ。まとめ(第8回) でちょっと書いたのだけど、
- BUM Flooding がスイッチトポロジを反映しない
- 個別のフロー単位で経路計算するような仕掛けだと、マルチパス(負荷分散)などの対応が考えにくい
- unknown flow が多い環境ではコントローラの処理がスケールしなさそう
…というような話があるだろうなと。特に1点目2点目って、環境全体のトポロジ・経路情報みたいなのが把握できていないとやりにくい処理というのがあるわけで、そこをどうにかしたいなと思ったのですよ。環境全体の経路情報…となるということはつまり、全スイッチ間の最短経路か。つまり全対最短経路計算。これはフロイド・ワーシャル(Floyd-Warshall)法というので計算できるとのこと。
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本（ソフトカバー）
- 購入: 11人 クリック: 656回
- この商品を含むブログ (72件) を見る
point-to-point な dijkstra 法による経路検索の代わりに、トポロジ変化を検出した後でまとめて全対最短経路を計算するように変えてみました。今回はフロイド・ワーシャル法による経路計算の話を書きます。
テストトポロジ
Trema/MyRoutingSwitch(3), ダイクストラ法デバッグ で使ったトポロジと同じにしてみます。
graphviz で出すとこうだけど…
わかりにくいのでちゃんと図に起こすとこうなります。
動作
実装方針
- 計算量は O(V^3) (頂点数の3乗のオーダー)になります。重いのでトポロジ変化ごとにやるのは効率が良くありません…1リンクダウンでも2ポート分のイベントが出るわけで、いちいちこんな計算回すのは良くないでしょう。トポロジ変化時にはフラグだけ設定しておいて、一定時間間隔タイマで経路計算処理を回すことにします。(タイマでフラグチェックして、変化があったときに計算)する
- 計算した全対経路情報を保持しておいて、後はそれに基づいてフロー情報を生成・配布していきます。
感覚的な解説
dijkstra法は始点を中心にちょっとずつ最短経路を確定させるようなイメージですが、floyd-warshall 法も似たようなイメージがあります。まあ細かくは解説しません。上の本とかリンク先とかで調べてください…。O'Reilly のアルゴリズム クイックリファレンスがわかりやすいです。
頂点u→頂点vへの経路において中間点tを設定し、u-t-v の距離が既知のu-vの距離よりも小さければ
- u-v間の距離を u-t-v 間の距離で更新
- vへ到達するための一つ前の頂点をt経由したときの情報で更新
というのをやっていきます。中間点tを基点にした距離のテーブル(dist)と経由点のテーブル(pred)の情報を見てみます。
# calculate shortest path of all switch pair # using "Floyd-Warshall" Algorithm def build_path return false if not @watcher.updated? puts "Topology::build_path" @dist.clear @pred.clear # initialize dist/pred table each_switch do | dpid1, ports1 | @dist[dpid1] = {} @pred[dpid1] = {} each_switch do | dpid2, ports2 | link = @linkindex.link_between dpid1, dpid2 if link @dist[dpid1][dpid2] = link.cost @pred[dpid1][dpid2] = dpid1 else @dist[dpid1][dpid2] = INFINITY_LINK_COST @pred[dpid1][dpid2] = PRED_NONE end end @dist[dpid1][dpid1] = 0 end # debug print _pptables "initial" # calc dist/pred table each_switch do | dpid_t, ports_t | each_switch do | dpid1, ports1 | each_switch do | dpid2, ports2 | linkcost = @dist[dpid1][dpid_t] + @dist[dpid_t][dpid2] if linkcost < @dist[dpid1][dpid2] @dist[dpid1][dpid2] = linkcost @pred[dpid1][dpid2] = @pred[dpid_t][dpid2] end end end # debug print _pptables "t=#{dpid_t.to_hex}" end @controller.rewrite_flows @watcher.known return true end
動作
出力(を整形した物)を見ていきます。
- ループ0: 初期状態
- dist 99999 は無限大扱いです。また、スイッチ間コストは固定で 10 です。無向グラフなので対象になります。
- pred で空白になってるところは (nil) です。
- 初期状態では、直接隣接しているところについてだけ値を設定しておきます。
- dist/pred は行が source, 列が destination です。
- sw3 → sw1 については、距離 dist[0x3][0x1] => 10, pred[0x3][0x1] => 0x3 です。距離は隣接しているので 10 ですが、pred については "sw3 から sw1 に向かう場合、sw1 の前の hop は sw3 である" ということです。
--------------------- initial dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 99999, 5=> 99999, 6=> 99999, 7=> 99999, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 99999, 5=> 10, 6=> 99999, 7=> 99999, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 99999, 6=> 99999, 7=> 99999, 0x4 : 1=> 99999, 2=> 99999, 3=> 10, 4=> 0, 5=> 99999, 6=> 10, 7=> 10, 0x5 : 1=> 99999, 2=> 10, 3=> 99999, 4=> 99999, 5=> 0, 6=> 10, 7=> 99999, 0x6 : 1=> 99999, 2=> 99999, 3=> 99999, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 99999, 2=> 99999, 3=> 99999, 4=> 10, 5=> 99999, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> , 5=> , 6=> , 7=> , 0x2 : 1=> 2, 2=> , 3=> 2, 4=> , 5=> 2, 6=> , 7=> , 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> , 6=> , 7=> , 0x4 : 1=> , 2=> , 3=> 4, 4=> , 5=> , 6=> 4, 7=> 4, 0x5 : 1=> , 2=> 5, 3=> , 4=> , 5=> , 6=> 5, 7=> , 0x6 : 1=> , 2=> , 3=> , 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> , 2=> , 3=> , 4=> 7, 5=> , 6=> 7, 7=> ,
- ループ1 (t=0x5)
- sw5 を経由点としたときに各スイッチ間の経路がどうなるかを計算します。sw5 と隣接しているのは sw2, sw6 なのでその辺の値が変わってきます。(sw2-sw5-sw6 で dist/pred の再計算)
- 例えば sw2 → sw6 (dist[2][6], pred[2][6]) はループ0では不明でしたが、sw5 経由で接続できるので値が書き換わります。(dist[2][6]=dist[2][5]+dist[5][6], pred[2][6] = pred[5][6] => 0x5... sw2→sw6 には sw5 経由でたどり着ける)
--------------------- t=0x5 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 99999, 5=> 99999, 6=> 99999, 7=> 99999, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 99999, 5=> 10, 6=> 20, 7=> 99999, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 99999, 6=> 99999, 7=> 99999, 0x4 : 1=> 99999, 2=> 99999, 3=> 10, 4=> 0, 5=> 99999, 6=> 10, 7=> 10, 0x5 : 1=> 99999, 2=> 10, 3=> 99999, 4=> 99999, 5=> 0, 6=> 10, 7=> 99999, 0x6 : 1=> 99999, 2=> 20, 3=> 99999, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 99999, 2=> 99999, 3=> 99999, 4=> 10, 5=> 99999, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> , 5=> , 6=> , 7=> , 0x2 : 1=> 2, 2=> , 3=> 2, 4=> , 5=> 2, 6=> 5, 7=> , 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> , 6=> , 7=> , 0x4 : 1=> , 2=> , 3=> 4, 4=> , 5=> , 6=> 4, 7=> 4, 0x5 : 1=> , 2=> 5, 3=> , 4=> , 5=> , 6=> 5, 7=> , 0x6 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> , 2=> , 3=> , 4=> 7, 5=> , 6=> 7, 7=> ,
- ループ2 (t=0x6)
- sw6 を経由点としたときの経路を確認します。sw5-sw6-sw3-sw7 あたり。
- ループ1で sw2-sw5-sw6 については見えているので、 sw2-sw5-sw6-sw3-sw7 あたりが更新範囲になります。
--------------------- t=0x6 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 99999, 5=> 99999, 6=> 99999, 7=> 99999, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 30, 5=> 10, 6=> 20, 7=> 30, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 99999, 6=> 99999, 7=> 99999, 0x4 : 1=> 99999, 2=> 30, 3=> 10, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 99999, 2=> 10, 3=> 99999, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 0x6 : 1=> 99999, 2=> 20, 3=> 99999, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 99999, 2=> 30, 3=> 99999, 4=> 10, 5=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> , 5=> , 6=> , 7=> , 0x2 : 1=> 2, 2=> , 3=> 2, 4=> 6, 5=> 2, 6=> 5, 7=> 6, 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> , 6=> , 7=> , 0x4 : 1=> , 2=> 5, 3=> 4, 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> , 2=> 5, 3=> , 4=> 7, 5=> 6, 6=> 7, 7=> ,
- ループ3 (t=0x1)
- sw1-sw2-sw3 あたり
- sw2, sw3 はループ2までで sw4-sw7 との接続がある程度見えているのでその辺も含まれるはず…ですが、u→sw1→v みたいな経路は最短経路として選択されないので値が更新されないですね。
--------------------- t=0x1 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 99999, 5=> 99999, 6=> 99999, 7=> 99999, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 30, 5=> 10, 6=> 20, 7=> 30, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 99999, 6=> 99999, 7=> 99999, 0x4 : 1=> 99999, 2=> 30, 3=> 10, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 99999, 2=> 10, 3=> 99999, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 0x6 : 1=> 99999, 2=> 20, 3=> 99999, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 99999, 2=> 30, 3=> 99999, 4=> 10, 5=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> , 5=> , 6=> , 7=> , 0x2 : 1=> 2, 2=> , 3=> 2, 4=> 6, 5=> 2, 6=> 5, 7=> 6, 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> , 6=> , 7=> , 0x4 : 1=> , 2=> 5, 3=> 4, 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> , 2=> 5, 3=> , 4=> 7, 5=> 6, 6=> 7, 7=> ,
- ループ4 (t=0x7)
- ループ3同様で、sw7経由の経路が最短経路にならないので値が更新さなれないです。
--------------------- t=0x7 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 99999, 5=> 99999, 6=> 99999, 7=> 99999, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 30, 5=> 10, 6=> 20, 7=> 30, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 99999, 6=> 99999, 7=> 99999, 0x4 : 1=> 99999, 2=> 30, 3=> 10, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 99999, 2=> 10, 3=> 99999, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 0x6 : 1=> 99999, 2=> 20, 3=> 99999, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 99999, 2=> 30, 3=> 99999, 4=> 10, 5=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> , 5=> , 6=> , 7=> , 0x2 : 1=> 2, 2=> , 3=> 2, 4=> 6, 5=> 2, 6=> 5, 7=> 6, 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> , 6=> , 7=> , 0x4 : 1=> , 2=> 5, 3=> 4, 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> , 2=> 5, 3=> , 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> , 2=> 5, 3=> , 4=> 7, 5=> 6, 6=> 7, 7=> ,
- ループ5 (t=0x2)
- ここで一気に更新されました。sw2 がほぼ中心にいる → sw2 を経由する経路がおおいこと、これまでの経路で周辺の状況(隣接〜2ホップくらいまでのところ)がだいたい見えているからでしょう。
--------------------- t=0x2 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 40, 5=> 20, 6=> 30, 7=> 40, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 30, 5=> 10, 6=> 20, 7=> 30, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 20, 6=> 30, 7=> 40, 0x4 : 1=> 40, 2=> 30, 3=> 10, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 20, 2=> 10, 3=> 20, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 0x6 : 1=> 30, 2=> 20, 3=> 30, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 40, 2=> 30, 3=> 40, 4=> 10, 5=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> 6, 5=> 2, 6=> 5, 7=> 6, 0x2 : 1=> 2, 2=> , 3=> 2, 4=> 6, 5=> 2, 6=> 5, 7=> 6, 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> 2, 6=> 5, 7=> 6, 0x4 : 1=> 2, 2=> 5, 3=> 4, 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> 2, 2=> 5, 3=> 2, 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> 2, 2=> 5, 3=> 2, 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> 2, 2=> 5, 3=> 2, 4=> 7, 5=> 6, 6=> 7, 7=> ,
- ループ6 (t=0x3)
--------------------- t=0x3 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 20, 5=> 20, 6=> 30, 7=> 40, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 20, 5=> 10, 6=> 20, 7=> 30, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 20, 6=> 30, 7=> 40, 0x4 : 1=> 20, 2=> 20, 3=> 10, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 20, 2=> 10, 3=> 20, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 0x6 : 1=> 30, 2=> 20, 3=> 30, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 40, 2=> 30, 3=> 40, 4=> 10, 5=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> 3, 5=> 2, 6=> 5, 7=> 6, 0x2 : 1=> 2, 2=> , 3=> 2, 4=> 3, 5=> 2, 6=> 5, 7=> 6, 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> 2, 6=> 5, 7=> 6, 0x4 : 1=> 3, 2=> 3, 3=> 4, 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> 2, 2=> 5, 3=> 2, 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> 2, 2=> 5, 3=> 2, 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> 2, 2=> 5, 3=> 2, 4=> 7, 5=> 6, 6=> 7, 7=> ,
- ループ7 (t=0x4)
- ラスト。ループ6で dist=40 になっていたところが修正されました。
--------------------- t=0x4 dist : 0x1 : 1=> 0, 2=> 10, 3=> 10, 4=> 20, 5=> 20, 6=> 30, 7=> 30, 0x2 : 1=> 10, 2=> 0, 3=> 10, 4=> 20, 5=> 10, 6=> 20, 7=> 30, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 10, 5=> 20, 6=> 20, 7=> 20, 0x4 : 1=> 20, 2=> 20, 3=> 10, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 20, 2=> 10, 3=> 20, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 0x6 : 1=> 30, 2=> 20, 3=> 20, 4=> 10, 5=> 10, 6=> 0, 7=> 10, 0x7 : 1=> 30, 2=> 30, 3=> 20, 4=> 10, 5=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> 3, 5=> 2, 6=> 5, 7=> 4, 0x2 : 1=> 2, 2=> , 3=> 2, 4=> 3, 5=> 2, 6=> 5, 7=> 6, 0x3 : 1=> 3, 2=> 3, 3=> , 4=> 3, 5=> 2, 6=> 4, 7=> 4, 0x4 : 1=> 3, 2=> 3, 3=> 4, 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> 2, 2=> 5, 3=> 2, 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> 2, 2=> 5, 3=> 4, 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> 3, 2=> 5, 3=> 4, 4=> 7, 5=> 6, 6=> 7, 7=> ,
経路
sw1→sw7 について見てみます。必要なのは pred[0x1] です。
0x1 : 1=> , 2=> 1, 3=> 1, 4=> 3, 5=> 2, 6=> 5, 7=> 4,
- pred[0x1][0x7] → 0x4 (sw2→sw7 に行くためには sw4 を経由する)
- pred[0x1][0x4] → 0x3 (sw2→sw4 に行くためには sw3 を経由する)
- pred[0x1][0x3] → 0x1 (始点まで追いついたので経路がわかった: sw1-sw3-sw4-sw7)
pred そのものは dijkstra 法の計算で使ったのと同じ。それを全部のスイッチについてだしてあるだけ。
まとめ
とりあえず、Floyd-Warshall 法の実装をやってみた、というところ。実装上のアレコレとかについては次回で。
