RFC7938を読んだのでメモしておく。 ちょっとかじった程度の話なので、言葉づかいは不適切かもしれない。

概要

サーバが10万台を超えるラージスケールなインフラにおいて、単純かつ高安定性なネットワーク設計手法についてまとめる。BGPを唯一のルーティングプロトコルとして採用する。

イントロ

Web検索エンジンのような大規模な分散システムのインフラを、単純かつ高安定性なネットワークによって少ない人数で運用したい。

ネットワーク要件

帯域と遅延が重要な要素。伝統的な木構造のネットワークはnorth-southのトラフィックに対しては対応できる。ただ最近Hadoopのようなサーバ間のトラフィックパターンが増えたことから、east-westのトラフィックが増えることになり、伝統的な木構造のネットワークで対応するには、ポート密度など物理的な制約から難しくなってきた。

データセンタの設備投資額についてみると、データセンタ全体の10~15%をネットワークが占める。削減にあたって、2つのアプローチがある。1つ目は、同一のハードウェアやデバイスを使うなど、全てのネットワーク機器を統合するということ。まとめて購入することで購入コストや管理コストの削減につながる。2つ目は、ネットワークベンダ間で価格を競争させるということ。もしベンダを分散させるなら、ソフトウェア要件を最小にして、柔軟性を持たせることが重要になる。

オペレーションについてみると、L2ネットワークではブロードキャストやユニキャストのストームがそのドメインで大規模なパフォーマンス上の問題や稼働率の低下を引き起こす。これはL3ルーティングを組み込んだ設計を行うと、その影響範囲を縮小できる。一方で、L3ルーティングでは、コントロールプレーンの分散に起因する障害を考慮する必要が出てくる。これはルーティングプロトコルの種類の削減することで対応する。

アプリケーションのロードバランシングも重要な観点になる。これまでは経路上に専用のデバイスを置くことで実現したが、トラフィックの増大へは対応しづらい。そこで、複数台のローバランシング専用ノードを並べることで、水平にスケールできる構成が望ましい。これはAnycast Prefix AdvertisementとEqual Cost Multipath(ECMP) によって実現できる。

要件をまとめると、

  • REQ1: デバイスのアップグレードではなく、同種のデバイス追加によって、水平にスケールする構成が望ましい
  • REQ2: ソフトウェアのfeatureやprotocolを最小化したい
  • REQ3: 運用コストが小さくてシンプルな実装を持つルーティングプロトコルが良い
  • REQ4: 機器やプロトコル起因の障害範囲を小さくしたい
  • REQ5: プロトコルのfeatureによってトラフィックエンジニアリングを実現したい

データセンタトポロジ

トラディショナルなtree-basedなトポロジと、Clos-basedなトポロジを比較してみる。前者は、下図のように3層のスイッチ(Coreレイヤ、Aggregation/Distributionレイヤ、Accessレイヤ)から構成され、上位の層では帯域を確保するために、ポート密度や帯域容量を上げることになる。この構成では前述したように、Tier 2を増やしたときに、それを格納できるほどまでTier 1のポート密度を上げることができない。つまり、各スイッチの次数(グラフのある頂点から出る辺の数)の制約でスケールしない。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
             +------+  +------+
             |      |  |      |
             |      |--|      |           Tier 1
             |      |  |      |
             +------+  +------+
               |  |      |  |
     +---------+  |      |  +----------+
     | +-------+--+------+--+-------+  |
     | |       |  |      |  |       |  |
   +----+     +----+    +----+     +----+
   |    |     |    |    |    |     |    |
   |    |-----|    |    |    |-----|    | Tier 2
   |    |     |    |    |    |     |    |
   +----+     +----+    +----+     +----+
      |         |          |         |
      |         |          |         |
      | +-----+ |          | +-----+ |
      +-|     |-+          +-|     |-+    Tier 3
        +-----+              +-----+
         | | |                | | |
     <- Servers ->        <- Servers ->

                   Figure 1: Typical DC Network Topology

後者のfolded Closトポロジ(fat treeとも呼ばれる)は水平スケールのためのアプローチである。奇数台のステージ(次元とも呼ばれる)を一様な要素で構成する。この構成はLeaf・Spine構成とも呼ばれる。SpineがTier 1、LeafがTier 2に対応する。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
   +-------+
   |       |----------------------------+
   |       |------------------+         |
   |       |--------+         |         |
   +-------+        |         |         |
   +-------+        |         |         |
   |       |--------+---------+-------+ |
   |       |--------+-------+ |       | |
   |       |------+ |       | |       | |
   +-------+      | |       | |       | |
   +-------+      | |       | |       | |
   |       |------+-+-------+-+-----+ | |
   |       |------+-+-----+ | |     | | |
   |       |----+ | |     | | |     | | |
   +-------+    | | |     | | |   ---------> M links
    Tier 1      | | |     | | |     | | |
              +-------+ +-------+ +-------+
              |       | |       | |       |
              |       | |       | |       | Tier 2
              |       | |       | |       |
              +-------+ +-------+ +-------+
                | | |     | | |     | | |
                | | |     | | |   ---------> N Links
                | | |     | | |     | | |
                O O O     O O O     O O O   Servers

                  Figure 2: 3-Stage Folded Clos Topology

Closトポロジの特徴をまとめると、以下の通り。

  • M >= N の場合には完全のノンブロッキングとなる。それ以外の場合には、N/Mの比率による。ここでNはdownlink、Mはuplinkのポート数
  • M以上にファンアウトするために、ECMPのサポートが必要になる
  • Tier 1スイッチは、サーバごとに唯一のパスを持つ
  • サーバ間トラフィックはECMPによりロードバランシングされる

Closトポロジはポート密度の向上あるいはステージの追加によってスケールする。下図は5ステージへと拡張させたときのトポロジ。ここでは、サーバとそれに接続されたTier 2とTier 3のスイッチをまとめてクラスタと呼ぶ。クラスタはデプロイやメンテナンスの単位として使われる。Tier 3は実践的にはToRに相当する。OverSubscriptionはこのレイヤでのみ使われる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
                                      Tier 1
                                     +-----+
          Cluster                    |     |
 +----------------------------+   +--|     |--+
 |                            |   |  +-----+  |
 |                    Tier 2  |   |           |   Tier 2
 |                   +-----+  |   |  +-----+  |  +-----+
 |     +-------------| DEV |------+--|     |--+--|     |-------------+
 |     |       +-----|  C  |------+  |     |  +--|     |-----+       |
 |     |       |     +-----+  |      +-----+     +-----+     |       |
 |     |       |              |                              |       |
 |     |       |     +-----+  |      +-----+     +-----+     |       |
 |     | +-----------| DEV |------+  |     |  +--|     |-----------+ |
 |     | |     | +---|  D  |------+--|     |--+--|     |---+ |     | |
 |     | |     | |   +-----+  |   |  +-----+  |  +-----+   | |     | |
 |     | |     | |            |   |           |            | |     | |
 |   +-----+ +-----+          |   |  +-----+  |          +-----+ +-----+
 |   | DEV | | DEV |          |   +--|     |--+          |     | |     |
 |   |  A  | |  B  | Tier 3   |      |     |      Tier 3 |     | |     |
 |   +-----+ +-----+          |      +-----+             +-----+ +-----+
 |     | |     | |            |                            | |     | |
 |     O O     O O            |                            O O     O O
 |       Servers              |                              Servers
 +----------------------------+

                      Figure 3: 5-Stage Clos Topology

もしネットワークサイズが小さい場合にはTier 1やTier 2スイッチの数を減らすことができる。例えばTier 1スイッチのポートが半分しか使われていない場合には、Tier 1スイッチの数を半分にすることができる。その場合には、Tier 2スイッチから同一のTier 1スイッチに2つのリンクを張ることになる。ただ、2ポートのうち片方のリンクが落ちたとき、もう一方のリンクに想定の2倍のトラフィックが流れ、輻輳やサービスの低下に繋がってしまうとまずい。そこで2つのリンクをLAGによって集約し、片方のリンクが落ちたときには、2ポートまとめて落ちるような構成をとると良い。同様の技術として fate-sharing を使うのも良い。

データセンタールーティング

L2のみ、L2/L3のハイブリッド、L3のみという3種の設計についてみていく。

L2構成では、Spanning Tree Protocol(STP)を使っていた。当時のデータセンタースイッチでは、L3ルーティングをサポートしていなかったり、追加ライセンス費用がかかったり、という状況だった。STPとそれに類似する技術では、ループ回避のために、パス選択において、Active/Standby構成になってしまう。さらに設定ミスなどによる障害範囲が大きかった。その後、Multi-Chassis Link-Aggregation(M-LAG)技術によって、Active/Activeでパスを選択できるようになったが、標準的な実装がなく、またデバイス間同期によるリスクがあった。Transparent Interconnection of Lots of Links(TRILL)によってSTPを使わずに、巨大で水平にスケールするL2のみの構成を実現できるようになった。ただ、実装の数が制限されており、特定の機器でしか利用することができない。

ハイブリッド構成では、データプレーンの障害を制限するために、ルーティングプロトコルを導入した。結果としてL2ドメインを縮小することができ、スケールアップも可能になった。ただ以下のような理由でTier 2配下あるいはTier 3配下でL2ドメインを維持する必要があった。

  • 直接L2ドメインに属することが要件となっているレガシーなソフトウェアのサポート
  • IPを維持した仮想マシンのマイグレーション
  • Layer 2 Direct Server Return(L2DSR)によるロードバランシング

時代が進み、完全にTier 3より上位をIPルーティングで設計することも普及してきた。普通はOpen Shortest Path FIrst(OSPF)のようなInterior Gateway Protocol(IGP)を主要なルーティングプロトコルとして採用する。サーバが1万台を超えたあたりから、この構成が魅力的になる。L2ドメインを必要とする要件があれば、オーバレイやトンネリング技術によって対応できる。

ルーティングプロトコル

External BGP(EBGP)を唯一のルーティングプロトコルとして採用する動機についてみていく。EBGPはドメイン間の接続としてインターネットにおいて広く使われているが、以下の理由からデータセンター内では使われていなかった。

  • BGPはWANのみという認識から、データセンター内では考慮されなかった
  • BGPはIGPに比べて収束が遅いという認識があった
  • BGPは設定上のオーバヘッドがあり、またネイバーの自動検出ができないと思われていた

この辺りについて議論していく。

BGPはプロトコル設計としてそこまで複雑性ではない。OSFPのようなリンクステートIGPと比べても内部のデータ構造や状態機械は単純に構成されている。transport はTCPのみに依存している。 BGPルータはルート計算の結果、ベストパスのみを伝播させる。そのためにネットワーク障害を早い段階でマスクできる。 Autonomous System Number(ASN)を適切に割り当ててAS_PATHループを検出すると、BGP path huntingをコントロールできる。 最小のポリシーで運用されていた場合、トラブルシュートが楽になる。ほとんどの実装では、素直にBGP Loc-RIB と Routing Information Base(RIB) を見比べるだけで良い。また、Adj-RIB-INとAdj-RIB-Outも見れるので、ピアとやりとりしているNetwork Layer Reachability Information(NLRI)を確認することもできる。

下図はASNの割り当てを図示したもの。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
                                ASN 65534
                               +---------+
                               | +-----+ |
                               | |     | |
                             +-|-|     |-|-+
                             | | +-----+ | |
                  ASN 646XX  | |         | |  ASN 646XX
                 +---------+ | |         | | +---------+
                 | +-----+ | | | +-----+ | | | +-----+ |
     +-----------|-|     |-|-+-|-|     |-|-+-|-|     |-|-----------+
     |       +---|-|     |-|-+ | |     | | +-|-|     |-|---+       |
     |       |   | +-----+ |   | +-----+ |   | +-----+ |   |       |
     |       |   |         |   |         |   |         |   |       |
     |       |   |         |   |         |   |         |   |       |
     |       |   | +-----+ |   | +-----+ |   | +-----+ |   |       |
     | +-----+---|-|     |-|-+ | |     | | +-|-|     |-|---+-----+ |
     | |     | +-|-|     |-|-+-|-|     |-|-+-|-|     |-|-+ |     | |
     | |     | | | +-----+ | | | +-----+ | | | +-----+ | | |     | |
     | |     | | +---------+ | |         | | +---------+ | |     | |
     | |     | |             | |         | |             | |     | |
   +-----+ +-----+           | | +-----+ | |           +-----+ +-----+
   | ASN | |     |           +-|-|     |-|-+           |     | |     |
   |65YYY| | ... |             | |     | |             | ... | | ... |
   +-----+ +-----+             | +-----+ |             +-----+ +-----+
     | |     | |               +---------+               | |     | |
     O O     O O              <- Servers ->              O O     O O

                 Figure 4: BGP ASN Layout for 5-Stage Clos
  • EBGPでは直接接続されたノード間にのみ、シングルホップのBGPセッションを張る。マルチホップは使わない。
  • 衝突を避けるために、プライベートなASN(64512-65534)を使う
  • Tier 1全体で一つのASNを割り当てる
  • Tier 2では、クラスタごとに個別のASNを割り当てる
  • Tier 3では、全てのデバイスに個別のASNを割り当てる

元々プライベートなASNは1023個しかなかったので、Tier 3 のデバイスにはクラスタ間で共通したASNを使うといったワークアラウンドが必要だった。例えば、ASN 65002 ~ 65032 を全てのクラスタで再利用するイメージ。あるいは、4オクテットのASNを使うことでも対応できる。

Closトポロジでは、リンクが大量に存在するので、そのルートを全てBGPに乗せようとするとFIBのオーバヘッドが大きい。そこで、以下の対応が必要になる。

  • point-to-point のリンクをBGPに乗せない。ただtracerouteなどが使えなくなる。
  • point-to-pont のリンクをBGPに乗せるが、全ての機器で集約する。IPアドレスを連続させる必要がある。

サーバ用のサブネットは、Tier 1やTier 2で集約せずに、広報すべきである。なぜなら、ある一箇所のリンク故障時にブラックホールが生まれることを避けるため。

Closトポロジと外部のネットワークとの接続性についてみていく。 外部との接続は、ある専用のクラスタが担当するとみなせば良い。 例えば、Tier 3デバイスをWANルータ、Tier 2デバイスをボーダールータとみなせる。

ここでWANルータへ広報する際に、プライベートASNをAS_PATH属性から削除する必要がある。 データセンタ内のデバイスに対して、デフォルトルートをOriginateする必要か、あるいはWANルータから受け取ったデフォルトルートを広報させる必要がある。前者であれば、あるボーダールータからWANルータへのリンクが同時に全て落ちた時に、ブラックホールとなってしまう。一方、後者であれば、そのボーダールータからデフォルトルートが広報されなくなるので、こちらの方が望ましい。

以下のどちらかの手法を採用すると、ボーダルータから広報する際にブラックホールのリスクを避けて、サーバ用のサブネットを集約させることができる。(ここよく分かっていないので見直す)

  • ボーダールータをフルメッシュで接続する
  • Tier 1デバイスからボーダールータへリンクを追加する

ECMP

Closトポロジにおいて負荷分散のために使われる重要な特徴。あるレイヤのデバイスは、直接接続された一つ上にある全てのデバイスに対してトラフィックを分散できる。下図では、デバイスAからサーバXへの経路は4つある。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
                                Tier 1
                               +-----+
                               | DEV |
                            +->|  1  |--+
                            |  +-----+  |
                    Tier 2  |           |   Tier 2
                   +-----+  |  +-----+  |  +-----+
     +------------>| DEV |--+->| DEV |--+--|     |-------------+
     |       +-----|  B  |--+  |  2  |  +--|     |-----+       |
     |       |     +-----+     +-----+     +-----+     |       |
     |       |                                         |       |
     |       |     +-----+     +-----+     +-----+     |       |
     | +-----+---->| DEV |--+  | DEV |  +--|     |-----+-----+ |
     | |     | +---|  C  |--+->|  3  |--+--|     |---+ |     | |
     | |     | |   +-----+  |  +-----+  |  +-----+   | |     | |
     | |     | |            |           |            | |     | |
   +-----+ +-----+          |  +-----+  |          +-----+ +-----+
   | DEV | |     | Tier 3   +->| DEV |--+   Tier 3 |     | |     |
   |  A  | |     |             |  4  |             |     | |     |
   +-----+ +-----+             +-----+             +-----+ +-----+
     | |     | |                                     | |     | |
     O O     O O            <- Servers ->            X Y     O O

               Figure 5: ECMP Fan-Out Tree from A to X and Y

複数のTier 3デバイスから同一のPrefixが広報されることになるので、例えばAS_PATH属性の中身が違っていたとしても、その長さが等しければ、負荷分散される仕組みが必要になる。これは"multipath relax"や"multipath multipe-AS"と呼ばれる。

あるECMPのグループに、サーバを追加したり削除したりした時に、既存のフローのネクストホップのアフィニティ(既存のフローの経路が変わらない性質)を担保したくなる。これはコンシステントハッシュによって実現できる。ただ、Ternary Contest-Addressable Memory(TCAM)容量を消費するので注意する。

収束

もしリンク故障があったとしても、RIBやFIBが即時に更新され、かつfast EBGPをサポートしていれば、数秒で収束するはずである。 典型的にはAS内のリンクやノード故障については、IGPが担当する。 ただ今回はIGPを使わないので、BGPのKeep-aliveかリンク障害のトリガーを使うことになる。 単にBGPのkeep-aliveだけに頼ると、ホールドタイマーが最小で3秒なので、収束に時間がかかってしまう。 一方で、“fail fallover"という仕組みによって、インターフェイスの障害を検知した場合には即座にEBGPセッションを閉じることができる。

イーサネットのリンクは、Connectivity Fault Management(CFM)という仕組みを持っているので、さらに堅牢に障害を検知できる。 別のアプローチとして、Bidirectional Forwarding Detection(BFD)を使うことによって、障害を即座にBGPプロセスへと通知できる。

MinRouteAdvertisementIntervalTImer(MIRAI Timer)についても考慮しておく必要がある。 この設定値は、どれくらいの間隔を開けてBGP UPDATEメッセージを送るかを制御する。 もしこの値が大きければ、全体の収束にも時間がかかる。

ECMP環境では"Up->Down"の収束が難しい。例えば、あるTier2 デバイスがあるPrefixを引き抜こうとした時、それ以外のTier 2デバイスはこのBGP UPDATEメッセージを全てのTier 1デバイスから受け取ることになる。ここで、Tier 2デバイスは全てのTier 1デバイスからBGP UPDATEメッセージを受け取ってはじめて対象のPrefixを引き抜くことができる。また、タイミング次第ではBGP UPDATEメッセージが分散することになる。これは、“update groups"という概念によって、同時に複数のネイバーへメッセージを送ることで解決できる。

BGPはディスタンスベクタ型のプロトコルなのでベストパスだけを保持している。小規模なリンク障害があったとしても、それ以外のリンクを経由して疎通が取れるなら、その障害はある範囲に閉じることになる。

Tier 2デバイスが全てのパスを消失したという状況を考えてみる。この状況でデフォルトルートがアップストリームを指すように設定していたとすると、トラフィックはTier 1デバイスとTier 2デバイスの間でピンポンすることになる。これを避けるために、DiscardルートあるいはNullルートを静的に設定しておくと良い。

追加のオプション

すでに触れたが、ルートの集約はリンク障害時にブラックホールに陥るため導入し辛い。もし、集約したいのであれば、複数のリンク障害だけでなくfiler pathwayや光学的な障害も考慮してモデリングすべきである。