Trema/MyRoutingSwitch(6), 全対最短経路(2)
全対最短経路に変えた事によるアレコレ。
Topology based flooding
従来(point-to-point shortest-path)
Broadcast/Unknown-unicast による flooding は、いままで management network 経由で全スイッチに対して packet-out していたので、openflow network のトポロジを反映していませんでした。なので、openflow network が分断されていて、接続していないスイッチ/ホストに対しても flooding されてしまうようになっていました。
というのをどうにかしようとした場合、
- flooding するときに、全スイッチ間の経路を計算してやる
- いちいちそんな計算するのって、無駄…
- broadcast についてはプロアクティブにフロールール入れられるかもしれない。けど、それも結局スイッチトポロジを元にループフリーな経路を計算してフローエントリ入れてやるとかしないといけない(STP的な物を再実装?)。あと Unknown-unicast はフロールール固定できないしねえ…。
- ということで、だったら最初から全対最短経路を計算しておいてスイッチ間経路情報もっておいた方がいい。
到達不能なノードがある場合の経路情報
例えば
という環境において sw2-sw5, sw3-sw4 間を落として環境を完全に分断してみます。
stereocat@oftest04:~/training/my-routing-switch$ sudo trema port_down --switch sw2 --port 3 stereocat@oftest04:~/training/my-routing-switch$ sudo trema port_down --switch sw4 --port 3
すると経路情報はこういう状態になります。
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=> 99999, 6=> 99999, 7=> 99999, 0x3 : 1=> 10, 2=> 10, 3=> 0, 4=> 99999, 5=> 99999, 6=> 99999, 7=> 99999, 0x4 : 1=> 99999, 2=> 99999, 3=> 99999, 4=> 0, 5=> 20, 6=> 10, 7=> 10, 0x5 : 1=> 99999, 2=> 99999, 3=> 99999, 4=> 20, 5=> 0, 6=> 10, 7=> 20, 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=> 20, 6=> 10, 7=> 0, pred : 0x1 : 1=> , 2=> 1, 3=> 1, 4=> , 5=> , 6=> , 7=> , 0x2 : 1=> 2, 2=> , 3=> 2, 4=> , 5=> , 6=> , 7=> , 0x3 : 1=> 3, 2=> 3, 3=> , 4=> , 5=> , 6=> , 7=> , 0x4 : 1=> , 2=> , 3=> , 4=> , 5=> 6, 6=> 4, 7=> 4, 0x5 : 1=> , 2=> , 3=> , 4=> 6, 5=> , 6=> 5, 7=> 6, 0x6 : 1=> , 2=> , 3=> , 4=> 6, 5=> 6, 6=> , 7=> 6, 0x7 : 1=> , 2=> , 3=> , 4=> 7, 5=> 6, 6=> 7, 7=> ,
見たまま。環境が分断されていることがわかります。テーブルの参照だけでこういう情報が見えるので、環境の変化(トポロジの変動)があまりないところでは有利でしょう。
フロー情報のキャッシュのパターン
テストをしていく中でいくつか見落としがありました。
同一スイッチ内折り返しとフロー情報のキャッシュ
これまで、2ホストが同一スイッチにいるというパターンが漏れていて、2つのホストが同じスイッチに接続している場合にフロー情報がキャッシュされてしまう(path = 空)という処理になっていました。2ホスト(host_A, hostB)が同一スイッチに接続されている場合、ANY→host_A, output:X および ANY→host_B, output:Y という集約フローだけで通信できます。いまの実装上、フロー情報キャッシュ(flowindex)は src/dst で保持しますが、集約フローは dst のみなので、flow-removed が上がってきたときにキャッシュ情報とマッチせず、無駄な情報が残ってしまいます。
handle_ipv4 において、経路の last-hop あるいは 同一スイッチ内折り返し(経路が last-hop のみ)という似たような条件とそのときの処理が微妙に変わります。
| src/dst条件 | アクション | 状況 | ||
|---|---|---|---|---|
| 同一SW | 経路が空 | packet-out | cache flow-info | |
| ○ | ○ | する | しない | src/dst が同一スイッチに接続されている場合は常にこのパターン |
| ○ | × | しない | しない | src/dst が同一スイッチで経路がある、というのは何か処理がおかしい |
| × | ○ | しない | しない | src/dst が異なるスイッチにいるが経路がないという場合はネットワークが分断されている |
| × | × | する | する | src/dst が異なるスイッチにいて何かしらの経路が計算できているのは、複数スイッチ環境での通常のケース |
同一スイッチ内折り返しかどうかでフロー情報をキャッシュするかどうかを分けるってだけなんだけど。何かしらの経路があって last-hop の処理と last-hop のみ(同一スイッチ接続)のケースでちゃんと処理が見えていなかったという話でした。
計算量の影響
O(V^3) だと、環境が大きくなる(スイッチの数が増える)とてきめんに計算量が増えるので、拡張性、という面ではやっぱり不安が。いま 3秒ごとにトポロジ変化のチェックをかけていますが、3秒で計算が終わらない、みたいな規模になるとまた問題が出ると思われ。環境規模とチェック時間(→障害発生時の復帰時間)がトレードオフになるのでそこがどうなるか。
おわりに
とりとめのないことをだらだら書いていますが、書かないと忘れるんすよ…ということで個人的なメモでした。
