Skip to content

Latest commit

 

History

History
304 lines (200 loc) · 26.4 KB

routing_switch.adoc

File metadata and controls

304 lines (200 loc) · 26.4 KB

たくさんのスイッチを制御する

大規模なネットワークを構成するたくさんのスイッチを連携させ、うまく制御する仕組みを見て行きましょう。

複数のスイッチを制御する

たくさんの OpenFlow スイッチがつながった環境では、パケットを目的地まで転送するためにスイッチを連携させる必要があります。複数の OpenFlow スイッチを連携し 1 台の大きな仮想スイッチにするコントローラが、本章で紹介するルーティングスイッチです (図 16-1)。同じスイッチ機能を提供するコントローラとしては、7 章や8 章で紹介したラーニングスイッチがありました。ラーニングスイッチとルーティングスイッチの大きな違いは、連携できるスイッチの台数です。ラーニングスイッチは OpenFlow スイッチを独立した 1 台のスイッチとして扱います。一方で、ルーティングスイッチは複数の OpenFlow スイッチを連携させることで、仮想的な 1 台のスイッチとして扱います。

routing switch
図 16-1: ルーティングスイッチはたくさんの OpenFlow スイッチを連携し 1 台の仮想スイッチとして動作させる

注意すべきは、ルーティングスイッチはルータではなく、あくまでスイッチであるという点です。ルーティングスイッチという名前は、複数のOpenFlowスイッチを経由し、まさにルーティングするようにパケットを転送することから来ています。このようにスイッチ機能を実現するという点では、ラーニングスイッチとの機能的な違いはありません。ただし制御できるネットワーク規模の面では、ルーティングスイッチは複数の OpenFlow スイッチを扱えるという違いがあります。

ルーティングスイッチの動作

ルーティングスイッチではたくさんのスイッチを接続するため、パケットの転送が複雑になります。宛先のホストまでいくつものスイッチを経由してパケットを届けなくてはならないため、宛先までの道順をスイッチに指示してやる必要があります。

routing switch flow mod
図 16-2: 最短パスでパケットを転送するフローエントリを書き込む

たとえば図 16-2において、ホスト 1 からホスト 4 へとパケットを送信する場合を考えてみましょう。もしパケットを最短のパスで届けたい場合、ホスト 1 → スイッチ 1 → スイッチ 5 → スイッチ 6 → ホスト 4 の順にパケットを転送します。ルーティングスイッチはこの転送をするフローエントリを最短パス上のスイッチ 1, 5, 6 へそれぞれ書き込みます。

このとき、実際にルーティングスイッチとスイッチ間でやりとりする OpenFlow メッセージは図 16-3のようになります:

  1. ホスト 1 がホスト 4 宛てにパケットを送信すると、ルーティングスイッチはこのパケットを Packet In としてスイッチ 1 から受け取る (この Packet In の in_port をポート s とする)

  2. ルーティングスイッチはあらかじめ収集しておいたトポロジ情報 (15章) を検索し、宛先のホスト 4 が接続するスイッチ (スイッチ 6) とポート番号 (ポート g とする) を得る

  3. ポート s から宛先のポート g までの最短パスをトポロジ情報から計算する。その結果、ポート s → スイッチ 1 → スイッチ 5 → スイッチ 6 → ポート g というパスを得る

  4. この最短パスに沿ってパケットを転送するフローエントリを書き込むために、ルーティングスイッチはパス上のスイッチそれぞれに Flow Mod を送る

  5. Packet In を起こしたパケットを宛先に送るために、ルーティングスイッチはスイッチ 6 のポート g に Packet Out を送る

routing switch packetin flowmod packetout
図 16-3: ルーティングスイッチでパケットを送信したときの OpenFlow メッセージ

ここで使っている OpenFlow メッセージはいずれも、今まで使ってきた Packet In や Flow Mod, Packet Out などおなじみの物ばかりです。以下ではステップ 3 で新たに登場した、最短パスの計算方法を詳しく見て行きましょう。

最短パスを計算する

最短パスの計算でよく登場するのがダイクストラ法というアルゴリズムです。これは、出発点から目的地までの最短パスを求める汎用アルゴリズムの 1 つで、カーナビの経路検索や鉄道の乗換案内などにも使われています。

ダイクストラ法を使った最短パス計算のアルゴリズムは、基本的には次のとおりです。まず、出発点から 1 ホップで到達できるスイッチをすべて探します。次に、見つかったスイッチから出発して 1 ホップで行けるスイッチ、つまり最初の出発点から 2 ホップで到達できるスイッチをすべて探します。これを繰り返して、出発点から 3 ホップ、 4 ホップ……というように距離を広げながら次々とスイッチを探していきます。途中で目的地のスイッチに到達したら探索完了で、そこまでのパスを最短パスとして返します。[1]

dijkstra
図 16-4: 最短パスをダイクストラ法で計算する

実際に図 16-2 のネットワークでスイッチ 1 からスイッチ 6 までの最短パスをダイクストラ法で探索する手順は図 16-4 のようになります:

  1. 始点となるスイッチ 1 を 0 ホップとする

  2. スイッチ 1 から 1 ホップで行けるすべてのスイッチを見つける。これはスイッチ 1 から出るリンクの先に繋がっているスイッチ 2, 4, 5 である

  3. 同様にステップ 2 で見つかったスイッチから 1 ホップで行けるすべてのスイッチを探し、スイッチ 3, 6 が見つかる。これらは始点からのホップ数が 2 のスイッチである

  4. ステップ 3 でゴールのスイッチ 6 が見つかったので探索を終わる。最短パスは最終的にスイッチ 1 → スイッチ 5 → スイッチ 6 とわかる

実行してみよう

動作原理がわかったところで、実際のトポロジ検出や最短パス計算の動作をルーティングスイッチを起動し確認してみましょう。ルーティングスイッチは他のサンプルと同様、GitHub で公開しています。次のコマンドでソースコードを取得してください。

$ git clone https://github.com/trema/routing_switch.git

依存する gem のインストールは、いつも通り bundle install コマンドです。

$ cd routing_switch
$ bundle install --binstubs

これで準備は完了です。

ルーティングスイッチを動かす

それでは、ルーティングスイッチを動かしてみましょう。Trema のネットワークエミュレータ機能を用いて、図 16-5 のネットワークを作ります。

routing switch sample network
図 16-5: ホスト 4 台、スイッチ 6 台からなるネットワーク

この構成を実現する設定ファイルは、ルーティングスイッチのソースツリーに入っています (trema.conf)。この設定ファイルを指定して、次のようにルーティングスイッチを起動します。

$ ./bin/trema run ./lib/routing_switch.rb -c trema.conf

最短パスを通すフローエントリを確認する

次に host1 と host4 の間でパケットを送受信し、最短パスを通すフローエントリがうまく設定されることを確認しましょう。ルーティングスイッチ起動直後は、まだ MAC アドレスの学習を行っていないので、host1 から host4 へとパケットを送っただけではフローエントリは設定されません。ラーニングスイッチと同じく、次のように両方向でパケットを送った段階でフローエントリが設定されます。

$ ./bin/trema send_packets --source host1 --dest host4
$ ./bin/trema send_packets --source host4 --dest host1
$ ./bin/trema send_packets --source host1 --dest host4

すると、ルーティングスイッチを起動したターミナルには host4 → host1 と host1 → host4 の 2 つの最短パスを発見した、というメッセージが表示されているはずです。

Creating path: 44:44:44:44:44:44 -> 0x6:1 -> 0x6:2 -> 0x5:5 -> 0x5:2 -> 0x1:4 -> 0x1:1 -> 11:11:11:11:11:11
Creating path: 11:11:11:11:11:11 -> 0x1:1 -> 0x1:4 -> 0x5:2 -> 0x5:5 -> 0x6:2 -> 0x6:1 -> 44:44:44:44:44:44

実際にどのようなフローエントリが設定されたか見てみましょう。フローエントリの確認は trema dump_flows コマンドです。まずは host1 から host4 への最短パスである switch1, switch5, switch6 のフローテーブルをそれぞれ見てみましょう。

$ ./bin/trema dump_flows switch1
cookie=0x0, duration=8.949s, table=0, n_packets=0, n_bytes=0, idle_age=8, priority=65535,udp,in_port=4,vlan_tci=0x0000,dl_src=44:44:44:44:44:44,dl_dst=11:11:11:11:11:11,nw_src=192.168.0.4,nw_dst=192.168.0.1,nw_tos=0,tp_src=0,tp_dst=0 actions=output:1
cookie=0x0, duration=4.109s, table=0, n_packets=0, n_bytes=0, idle_age=4, priority=65535,udp,in_port=1,vlan_tci=0x0000,dl_src=11:11:11:11:11:11,dl_dst=44:44:44:44:44:44,nw_src=192.168.0.1,nw_dst=192.168.0.4,nw_tos=0,tp_src=0,tp_dst=0 actions=output:4
$ ./bin/trema dump_flows switch5
cookie=0x0, duration=14.230s, table=0, n_packets=0, n_bytes=0, idle_age=14, priority=65535,udp,in_port=5,vlan_tci=0x0000,dl_src=44:44:44:44:44:44,dl_dst=11:11:11:11:11:11,nw_src=192.168.0.4,nw_dst=192.168.0.1,nw_tos=0,tp_src=0,tp_dst=0 actions=output:2
cookie=0x0, duration=9.320s, table=0, n_packets=0, n_bytes=0, idle_age=9, priority=65535,udp,in_port=2,vlan_tci=0x0000,dl_src=11:11:11:11:11:11,dl_dst=44:44:44:44:44:44,nw_src=192.168.0.1,nw_dst=192.168.0.4,nw_tos=0,tp_src=0,tp_dst=0 actions=output:5
$ ./bin/trema dump_flows switch6
cookie=0x0, duration=18.688s, table=0, n_packets=0, n_bytes=0, idle_age=18, priority=65535,udp,in_port=1,vlan_tci=0x0000,dl_src=44:44:44:44:44:44,dl_dst=11:11:11:11:11:11,nw_src=192.168.0.4,nw_dst=192.168.0.1,nw_tos=0,tp_src=0,tp_dst=0 actions=output:2
cookie=0x0, duration=13.723s, table=0, n_packets=0, n_bytes=0, idle_age=13, priority=65535,udp,in_port=2,vlan_tci=0x0000,dl_src=11:11:11:11:11:11,dl_dst=44:44:44:44:44:44,nw_src=192.168.0.1,nw_dst=192.168.0.4,nw_tos=0,tp_src=0,tp_dst=0 actions=output:1

たしかに switch1, switch5, switch6 それぞれについて、host1 と host4 間の 2 つの最短パス用のフローエントリが設定されています。

一方で、最短パス上にない switch2, switch3, switch4 はパケットが通らないため、次のようにフローエントリがありません。

$ ./bin/trema dump_flows switch2

$ ./bin/trema dump_flows switch3

$ ./bin/trema dump_flows switch4

最短パスの再計算を確認する

トポロジ上のリンクが切れた場合、ルーティングスイッチは自動的に最短パスを作り直します。たとえば図 16-5 において、switch1 と switch5 の間のリンクが切れた場合を考えます。このときルーティングスイッチは古い最短パス (host1 ⇔ switch1 ⇔ switch5 ⇔ switch6 ⇔ host4) のフローエントリを消します。そして、再び host1 が host2 へパケットを送ったタイミングで、ルーティングスイッチは新しい最短パス (host1 → switch1 → switch4 → switch5 → switch6) を作ります (図 16-6)。

routing switch update shortest path
図 16-6: 最短パスの作り直し

この動作も実際に動かして確認してみましょう。リンクの削除は trema delete_link コマンドです。

$ ./bin/trema delete_link switch1 switch5

すると、ルーティングスイッチを起動したターミナルには host1 ⇔ host4 の 2 つの最短パスを削除したというメッセージが表示されます。

Deleting path: 44:44:44:44:44:44 -> 0x6:1 -> 0x6:2 -> 0x5:5 -> 0x5:2 -> 0x1:4 -> 0x1:1 -> 11:11:11:11:11:11
Deleting path: 11:11:11:11:11:11 -> 0x1:1 -> 0x1:4 -> 0x5:2 -> 0x5:5 -> 0x6:2 -> 0x6:1 -> 44:44:44:44:44:44

再び host1 から host4 へパケットを送ってみましょう。

$ ./bin/trema send_packets --source host1 --dest host4

すると次のように、ルーティングスイッチを起動したターミナルには host1 → host4 の新たな最短パスが表示されます。

Creating path: 11:11:11:11:11:11 -> 0x1:1 -> 0x1:3 -> 0x4:2 -> 0x4:3 -> 0x5:4 -> 0x5:5 -> 0x6:2 -> 0x6:1 -> 44:44:44:44:44:44

以上でルーティングスイッチの最短パス計算と再計算の動作を見てきました。いよいよソースコードを読んでみましょう。

ルーティングスイッチのソースコード

ルーティングスイッチは次の 4 つのクラスが協調して動作します (図 16-7)。

RoutingSwitch クラス

スイッチから届く OpenFlow メッセージを振り分けます。OpenFlow スイッチと接続し、スイッチから上がってくる OpenFlow メッセージをその種類に応じて Topology または PathManager へと振り分けます

TopologyController, Topology クラス (15 章で紹介)

トポロジの変化イベントを PathManager へ通知します。トポロジ情報の変化に関連する OpenFlow メッセージを RoutingSwitch から受け取り、ネットワークトポロジ上のイベントへ変換し PathManager へ渡します

PathManager クラス

ルーティングスイッチの本体です。RoutingSwitch から Packet In メッセージを受け取ると、Topology から受け取るトポロジ情報を元に最短パスを計算し、Path クラスを通じて新しい最短パスをスイッチに反映します

Path クラス

パスの生成と削除に必要なフローエントリの操作を一手に引き受けます。FlowMod や FlowModDelete といった OpenFlow メッセージの詳細を PathManager から隠蔽します

routing switch classes
図 16-7: ルーティングスイッチのクラス構成

複雑な機能を持つコントローラは、このように機能を小さなクラスに分割することでスッキリと書けます。LLDP の送受信といったトポロジ検出処理は Topology クラスに、FlowMod といったフローエントリの処理は Path クラスにそれぞれまかせ、そして PathManager クラスが全体をとりまとめることで見通しが良くなりテストもしやすくなります。もし新しく機能を追加したくなった場合にも、既存のコードは改造せず新機能に対応するクラスを追加するだけです[2]。

RoutingSwitch クラスのソースコード (routing_switch.rb)

RoutingSwitch クラスは委譲パターンによって各 OpenFlow メッセージを他のクラスへと振り分けます。

lib/routing_switch.rb
link:vendor/routing_switch/lib/routing_switch.rb[role=include]

たとえば Topology クラスへ switch_ready イベントを転送するには、delegate メソッドを使って Topology クラスのインスタンスへ switch_ready メソッドを委譲します。なお packet_in イベントは Topology と PathManager の両方に届ける必要があるため、packet_in ハンドラの中で明示的にそれぞれの packet_in メソッドを呼び出すことで転送しています。

PathManager のソースコード (path_manager.rb)

PathManager は、Topology クラスとObserverパターンで連携します。TopologyクラスはRoutingSwitchクラスから上がってくる生のOpenFlowメッセージをトポロジ上の変化イベント(スイッチ・ポート・リンクの追加/削除とホストの追加)へと変換し、オブザーバである PathManager クラスのトポロジイベントハンドラを呼び出します。

PathManager クラスのトポロジイベントハンドラ (lib/path_manager.rb)
link:vendor/routing_switch/lib/path_manager.rb[role=include]

PathManager はトポロジイベントを受け取ると、インスタンス変数 @graph として持つ現在のネットワークグラフを更新します。たとえばLLDPによって新しいリンクを発見すると、Topology はトポロジイベント add_link を PathManager へ送ります。そして PathManager は新しく見つかったリンクを @graph へ追加します。

PathManager は packet_in イベントに反応し、届いたパケットを宛先へと届けます。

PathManager#packet_in
link:vendor/routing_switch/lib/path_manager.rb[role=include]

packet_in ハンドラの動作は図 16-6 の通りです:

path manager internals
図 16-6: PathManager の仕組み

  1. グラフ情報から送信元→宛先への最短パスを計算する。もし最短パスが見つかった場合には、最短パス上のスイッチにフローエントリを Path.create で打つ

  2. 最短パスが見つかった場合には、宛先ポートにPacketOutすることでPacketInを起こしたパケットを宛先へ届ける。見つからなかった場合には、パケットをすべての外部ポート (外部と接続しているポート) へPacketOutする

Path のソースコード (path.rb)

Path クラスはパスの生成と削除に必要なフローエントリの操作を一手に引き受けます。たとえば、パスを生成するメソッド Path.create の実装は次のようになっています:

Path.create (lib/path.rb)
link:vendor/routing_switch/lib/path.rb[role=include]

PathManager が Path.create を呼び出すと、Path クラスのインスタンスメソッド save を呼び出します。save メソッドでは最短パスに沿ってフローエントリを flow_mod_add_to_each_switch メソッドでスイッチに書き込みます。

OpenFlow を使う利点

本章のはじめで説明したように、ルーティングスイッチは OpenFlow ネットワークを 1 台の仮想的なスイッチとして動作させるコントローラです。普通のスイッチを真似るだけならば、わざわざ OpenFlow を使わなくてもよいのでは? と思うかもしれません。ここでは、OpenFlow を使った場合の利点について考えてみたいと思います。

リンク帯域を有効活用できる

通常のスイッチで構成されたネットワークでは、パケットのループを防ぐためにスパニングツリープロトコルでリンクの一部を遮断します。たとえば、図 16-7のようなループを含むネットワークでスパニングツリープロトコルを使うと、スイッチ2とスイッチ3間のリンクが遮断されループが解消します。このとき、たとえばホスト2からホスト3へのパケットは、この遮断されたリンクを通過できないため、スイッチ1を経由して転送します。これは明かに無駄な回り道で、せっかくのリンク帯域が無駄になっています。

spt1
図 16-7: スパニングツリーではループを避けるために一部のリンクを遮断する

一方、ルーティングスイッチではコントローラがトポロジ全体を把握しているため、ループを防ぐためのリンク遮断は必要ありません。パケットの転送経路を各スイッチにフローエントリとして明示的に指示するため、ループを含むトポロジであっても問題なく動作します。このためスパニングツリーを使う場合と比べて、ネットワーク中のリンクを有効に使えます（図 16-8）。

spt2
図 16-8: ルーティングスイッチではネットワーク中のリンクを有効に使える

いろいろなパス選択アルゴリズムを使える

パスの決定はコントローラで一括して行なうため、パス決定アルゴリズムを入れ替えるだけで、さまざまなパス選択を実現できます。今回、ルーティングスイッチではダイクストラ法による最短パスを使いましたが、たとえば図 16-9のようにフロー毎に異なるパスを設定することで、帯域確保のためのマルチパスを作ることも簡単にできます。

multipath
図 16-9: OpenFlowでは最短でないパスを含んだマルチパスを自由に作れる

このようなマルチパスは従来の自律分散型でも実現できますが、厳しい制限があります。IETFが標準化を行うTRILL（Transparent Interconnect of Lots of Links）や IEEE が標準化を行う SPB（Shortest Path Bridges）は、マルチパス転送に対応しています。しかし、マルチパス転送を使えるのは、最短パスが複数ある場合[3]だけです。最短ではないパスは、ループを起こす可能性があるため使えません。また最短パスが1本だけの場合にもマルチパスにできません。

まとめ

いくつものスイッチからなるネットワークを扱える、ルーティングスイッチの動作を見てきました。この章で学んだことを簡単にまとめておきましょう。

  • パケットを最短パスで宛先まで届ける方法。ダイクストラ法を使って最短パスを求め、最短パス上のスイッチにフローエントリを書き込む

  • 複数のクラスを連携しコントローラを実装する方法。メソッドの移譲やオブザーバーパターンを使い、機能ごとに分割したクラスを組み合わせる

  • OpenFlowを使う場合の利点。すべてのリンクを使うことで帯域を有効活用できるほか、マルチパスなどのパス選択アルゴリズムを自由に使える

次の章では、ネットワーク仮想化を実現する本格的なコントローラの一例として、ルーティングスイッチを発展させたスライス機能付きスイッチを見ていきます。

参考文献

  • 『最短経路の本——レナのふしぎな数学の旅』（Peter Gritzmann、Rene Brandenberg 著／シュプリンガー・ジャパン）
最短経路を題材にしたストーリ仕立てのグラフ理論入門書です。本章ではネットワーク上での最短パスを求める場合のダイクストラ法を紹介しましたが、リンクに重みがある場合の一般的なダイクストラ法についてはこの本がおすすめです。

  • 『マスタリングTCP/IP 応用編』（Philip Miller 著／オーム社
とくにレイヤ3の経路制御プロトコルについて詳しく説明した本です。ダイクストラ法を用いた経路制御プロトコルの1つであるOSPFについても説明しているので、ルーティングスイッチとの違いを比べてみるのもおもしろいでしょう。

1. ダイクストラ法はリンクに重み（距離）がある場合の最短パスを求められるので、実際にはもう少し複雑な手順になります。ネットワーク上の最短パスではそれぞれのリンクは“重み1”として考えるので、このように単純化できます。
2. 16 章ではルーティングスイッチにクラスを追加することで仮想ネットワーク機能を実装する例を紹介します。
3. このようなパスを、イコールコストマルチパス（Equal Cost Multipath）と呼びます。