スライド

トンネリング技術を⽤用いた
汎⽤用機器によるデータセンターマルチパスの実現 2015年年6⽉月25⽇日
第16回 インターネットテクノロジーワークショップ
東京⼤大学 情報理理⼯工学系研究科
中村 遼, ⽯石原知洋, 関⾕谷勇司, 江崎 浩
WIT 2015
15/06/25
背景
¤  データセンターネットワーク
¤  ⽇日々増え続けるデータセンタートラフィック
¤  クラウドコンピューティング etc
¤  既存機器による最短経路路だけのルーティングでは不不⼗十分
Juniper EX4200-48P
Google Data Center
Cisco Catalyst3750 Series
2
WIT 2015
15/06/25
既存⼿手法 : マルチパスの利利⽤用
¤  マルチパストポロジとその利利⽤用⼿手法
¤  Layer-3 : ECMP, VL2, MPTCP(Layer-4)
¤  Layer-2 : TRILL, SEATTLE, SPAIN,
[11] Al-Fares et.al., “A Scalable, Commodity
Data Center Network Architecture”
SIGCOMM’11
[4] Singla et.al., “Jellyfish: Networking
Data Centers Randomly“ NSDI’12
3
WIT 2015
15/06/25
Equal Cost Multi-Path
¤  実環境で最も使われている⼿手段
¤  Layer-3ネットワークの⾼高い可⽤用性
¤  P. Lapukhov, Building Scalable Data Centers: BGP is the
Better IGP, NANOG55
¤  既存の汎⽤用L3スイッチ(COTSスイッチ)で利利⽤用可能
¤  ただし、効率率率的に複数パスを利利⽤用することはできない
¤  ハッシュによる特定パスへの偏り
¤  利利⽤用できるリンクの不不⾜足
Overload!
wasted
path
4
WIT 2015
15/06/25
問題点 : デプロイの難しさ
¤  スイッチハードウェアへの変更更
¤  COTSスイッチはECMPのみ
¤  既存研究の多くはスイッチにハードウェアに変更更を追加
Ø  特殊なハードウェアはデプロイの障害に
p  ex) [6] Al-Fares et.al., “A Scalable, Commodity Data
Center Network Architecture” SIGCOMM’08
Single path
Multipath
5
WIT 2015
15/06/25
問題点 : トポロジ変更更への追従性
¤  事前にトポロジを取得、計算してセットアップ
¤  Ex) [3] Mudigonda et.al., SPAIN: COTS data-center Ethernet
for multipathing over arbitrary topologies, NSDI’10
1.  事前に全ホスト間で複数パスを通るVLANのセットアップを計算
2.  全スイッチに1.のVLANをセットアップ
¤  トポロジ変更更時には全スイッチに再設定が必要
トポロジの検知
とパスの計算
設定投⼊入
6
WIT 2015
15/06/25
既存研究の⽐比較
トポロジ
利利⽤用するパス
COTSスイッチ
を利利⽤用
トポロジ変更更
への追従性
TRILL
Arbitrary
ECMP
NO
YES
SEATTLE
Arbitrary
Single Path
NO
YES
PortLand
Fat-tree
ECMP
NO
NO
SPAIN
Arbitrary
Multiple Paths
YES
NO
VL2
Fat-tree
ECMP
YES
YES
SPAIN[12]に基づく既存研究の⽐比較
COTSスイッチを⽤用いながら、効率率率的なマルチパス利利⽤用と
トポロジ変更更への追従性(可⽤用性)を同時に実現できてはいない
7
WIT 2015
15/06/25
アプローチ
¤  前提
¤  Layer-3 Networkで構築
¤  IPネットワークの⾼高い可⽤用性、⼗十分に枯れた運⽤用技術
¤  P. Lapukhov[1], Facebook[2], VL2[13]
¤  スイッチハードウェアには⼿手を加えない
¤  COTS Layer-3スイッチを⽤用いる
¤ アプローチ
¤  エンドホスト(サーバ)がパスを選択する
¤  宛先へのトラフィックを⾃自律律的に複数パスへ分散
¤  サーバのソフトウェアネットワークスタックのみ変更更
8
WIT 2015
15/06/25
マルチパストポロジにおけるパス選択
¤  Ex) Fat-treeにおける任意のサーバ間のパスとは、
¤  送信元サーバからRootスイッチまでの最短経路路と
¤  Rootスイッチから宛先サーバへの最短経路路、の連結
Ø  つまりパスの選択とは、中継するスイッチの選択
9
WIT 2015
15/06/25
IPトンネルによる中継点の指定
¤  カプセル化を⽤用いたSource Routing
¤  最短経路路とは異異なるパスへパケットを通すには
1.  そのパスの中継スイッチを宛先としてカプセル化
2.  中継点のスイッチはカプセル化を解除
3.  オリジナルのパケットは宛先へと送信される
Switch B
Switch C
Switch A
Switch D
Dst : Switch C
Src : X.X.X.X
Dst : Server D
Src : Server S
Payload
Dst : Server D
Src : Server S
Payload
Server S
Server D
10
WIT 2015
15/06/25
トンネルの数の規模性
¤  フルメッシュトンネルは⾮非現実的
¤  全てのサーバが全てのスイッチを中継点として指定するためには
フルメッシュなトンネルが必要 = スイッチ数 ✕ サーバ数
¤  全サーバで同⼀一の送信元アドレスを利利⽤用
¤  トンネルを通るパケットは常に「サーバからスイッチ」への⽚片⽅方向
¤  全トンネルの送信元として同⼀一のアドレスを使えば、スイッチ上のト
ンネルは「From 同⼀一アドレス To スイッチ⾃自⾝身」の1本のみ
11
WIT 2015
15/06/25
利利⽤用可能なトンネリングプロトコル
¤  ステートレストンネル
¤  ステートフルトンネルは規模性の問題から使⽤用不不可
¤  ステートレスなトンネリングプロトコルは変更更無しで利利⽤用可能
プロトコル名
標準
標準化年年
IP in IP Tunneling
RFC1853
1995
GRE
RFC2784
2000
EtherIP
RFC3378
2002
LISP
RFC6830
2011
VXLAN
RFC7348
2014
NVGRE
Internet Draft
2012 ~
GUE
Internet Draft
2013 ~
Geneve
Internet Draft
2014 ~
利利⽤用可能なトンネリングプロトコル⼀一覧
12
WIT 2015
15/06/25
サーバネットワークスタックへの変更更
¤  特定宛先へのパケットにトンネルヘッダを追加
¤  トンネリングプロトコルも同時に指定 (ipip, gre, vxlan etc)
¤  ex: Dst 10.4.1.0/24 : Encap to A,B,C or D
A
B
Src X
Dst C
C
D
Src 10.1.2.2
Dst 10.4.1.2
Src 10.1.2.2
Dst 10.4.1.2
10.1.2.0/24
10.4.1.0/24
13
WIT 2015
15/06/25
iplb.ko : kernel module
¤  IP encapsulation based Load Balancing
¤  送信パケットが経路路表にマッチすると、中継点へカプセル化
¤  中継するスイッチはフロー(5-tuple)ごとに決定、保存
Netlink越しに
経路路表を操作
Userland
Match!
IP Packet
Kernel
Tun Hdr + IP
packet
iplb.ko
Dst Prefix
Relay Point
10.0.0.0/8
relay1, relay2, relay3
10.1.2.0/24
relay4, relay5
Network
14
WIT 2015
15/06/25
使⽤用例例 (iproute2 extension)
¤  宛先プレフィクスと中継点の追加
¤  経路路表の表⽰示
15
WIT 2015
15/06/25
Fat-treeトポロジへの適⽤用
¤  先⾏行行研究にて実施
¤  各フローのパスへの
割り当てアルゴリズム
¤  実機を⽤用いた予備実験
¤  Fat-treeトポロジでの評価
¤  Layer-3 Multipathing in Commodity-based Data Center
Networks, 18th IEEE Global Internet Symposium (April 27, 2015)
フローパターン
最短経路路のみ
ECMP
提案⼿手法
Same
47.91%
82.32%
100%
Random
N/A
84.00%
96.23%
Power-law
N/A
80.53%
90.39%
16
WIT 2015
15/06/25
Random Graph
¤  [4]Jellyfish: Networking Data Centers Randomly, NSDI’12
¤  「Random GraphはFat-treeよりもpath length, 障害時のス
ループットなどの観点からメリットが多い」
¤  「Random Graphでスループットを上げるにはECMPでは不不
⼗十分、k-shortest pathとMPTCPを使うのが良良い」
¤  しかし、k-shortest pathのために特殊/⾼高価なハードウェアの
利利⽤用を想定
17
WIT 2015
15/06/25
k-shortest path + Multipath TCP
¤  k-shortest path
¤  k番⽬目までの短いパス
¤  Yen’s loop-less k-shortest
path algorithm
1.  Path = shortest path by dijkstra
2.  Insert Path to path list
3.  Decide deviation link from
Path
4.  Path’ = Calculate SPF from
deviation node
5.  Path = Path’
6.  goto 2 up to len (path list) == k
¤  Multipath TCP
¤  エンドホストによる複数パ
スの利利⽤用⼿手法 ¤  DCネットワークでの利利
⽤用⼿手法も多数
¤  複数TCPセッションのため
の輻輻輳制御アルゴリズム
¤  Linked Increase
Congestion Control
Algorithm
One TCP
Session
(sub-flow)
18
WIT 2015
15/06/25
k-shortest path + Multipath TCP + iplb
¤  MPTCPでトラフィックを複数TCPサブフローに分割
¤  そして、iplbで各フローを異異なるk本のパスへ分散
Userland
Application
MPTCP
TCP
TCP
TCP
TCP
flow
flow
flow
iplb
flow
Kernel
Path 1
Path 2
Path 3
Path 4
Random Graph Network
19
WIT 2015
15/06/25
パスを代表する中継点の決定
¤  iplbはSource Routingのための⼿手法
¤  各パスの中継点とすべきスイッチは別途⾒見見つける必要がある
¤  Yen’s Algorithmでk本のパスを発⾒見見
¤  k本のパスへ通すのに中継すべき、k個の中継点リストを作成
k-paths (k = 6)
Src
< 8, 11, 1, 9, 17 >
< 8, 12, 3, 10, 17 >
< 8, 11, 2, 9, 17 >
< 8, 12, 4, 10, 17 >
< 8, 11, 1, 5, 2, 9, 17 >
< 8, 12, 3, 6, 4, 10, 17 >
Dst
20
WIT 2015
15/06/25
中継点リストの作成⼿手法
8
¤  k本のパスから⽊木構造を構築
¤  分岐する箇所を⾒見見つける
11
¤  異異なるホップにでてきた
スイッチは別ノードとして扱う
k-paths (k = 6)
< 8, 11, 1, 9, 17 >
< 8, 12, 3, 10, 17 >
< 8, 11, 2, 9, 17 >
< 8, 12, 4, 10, 17 >
< 8, 11, 1, 5, 2, 9, 17 >
< 8, 12, 3, 6, 4, 10, 17 >
1 hop
12
2 hop
1
2
4
3
5
9
10
6
2
17
9
4
10
3 hop
4 hop
5 hop
6 hop
17
21
WIT 2015
15/06/25
中継点リストの作成⼿手法 (続き)
8
¤  深さ優先探索索
¤  もし親ノードが複数の⼦子を持つなら
¤  ⾃自⾝身を中継点のリストに追加する
k-relay list (k = 6)
< 1, 5 >
< 1, 9 >
<2>
< 3, 6 >
< 3, 10 >
<4>
1 hop
11
12
2 hop
1
2
4
3
5
9
10
6
2
17
9
4
10
3 hop
4 hop
5 hop
6 hop
17
22
WIT 2015
15/06/25
コントロールプレーン
¤  OSPFによるグラフ情報の取得
¤  Link State Data Baseは完全なグラフの情報
¤  中継点のリストは前述のアルゴリズムでLSDBから計算可能
¤  トポロジ変更更にもOSPFによって追従可能
LSA Update/Delete
ospfd
processing
OSPF protocol
OSPF Protocol
iplbd
calculating relay
point from LSDB
Install relay point
via Netlink API
iplb.ko
relay point table
Kernel
Network
23
WIT 2015
15/06/25
評価
1. 
ランダムグラフにおけるスループットの向上
¤  ランダムグラフトポロジにおいて、提案⼿手法はECMPよりもネッ
トワーク全体の転送性能を上げることができるか
¤  カプセル化による転送量量の低下
2. 
サーバでのiplbモジュールによる転送性能の低下
¤  iplbはカーネル内にて、経路路表の検索索、フローごとにパスの決定、
カプセル化を⾏行行う
¤  スイッチはwire-rateで転送可能
3. 
トポロジ変更更への追従性
¤  リンクの切切断などに対して、現実的な時間でiplb内の経路路表を切切
り替えることができるか
24
WIT 2015
15/06/25
評価
1. 
ランダムグラフにおけるスループットの向上
¤  ランダムグラフトポロジにおいて、提案⼿手法はECMPよりもネッ
トワーク全体の転送性能を上げることができるか
¤  カプセル化による転送量量の低下
2. 
サーバでのiplbモジュールによる転送性能の低下
¤  iplbはカーネル内にて、経路路表の検索索、フローごとにパスの決定、
カプセル化を⾏行行う
¤  スイッチはwire-rateで転送可能
3. 
トポロジ変更更への追従性
¤  リンクの切切断などに対して、現実的な時間でiplb内の経路路表を切切
り替えることができるか
25
WIT 2015
15/06/25
実験環境
¤  ns-3 Direct Code Execution
¤  ns-3シミュレータ上でLinux Kernelが動作
¤  テストトラフィック
¤  Multipath TCP, 8サブフロー
¤  エンドホストはランダムに選択した宛先へテストトラフィックを送信
¤  評価項⽬目
¤  転送レート :
各ホストで 受信した合計量量(byte) / 送信した合計量量(byte)
¤  各テストトポロジにおいて、15回試⾏行行を⾏行行った平均
¤  テストトポロジ : ランダムグラフネットワーク
¤  最短経路路のみ, ECMP, k-shortest path (k = 2~8)
¤  4-port : 20 スイッチ 16 サーバ, 6-port : 45 スイッチ 54 サーバ,
8-port : 80 スイッチ128 サーバ
¤  上記のポート、スイッチ、サーバ数は3-level k-ary fat-treeに従う
26
WIT 2015
15/06/25
シミュレーション結果
¤  提案⼿手法は最短経路路のみとECMPよりも⾼高い転送性能を実現
¤  k = 3以上でECMP以上の性能, k = 6以上で最短経路路のみの1.3倍
¤  ECMPでは⼗十分なリンクを利利⽤用できていない
ECMP
k=2
k=3
k=4
k=5
k=6
k=7
k=8
4-port
1.120
1.178
1.222
1.231
1.221
1.230
1.190
1.171
6-port
1.213
1.192
1.278
1.304
1.279
1.300
1.304
1.314
8-port
1.246
1.162
1.277
1.309
1.306
1.314
1.301
1.304
最短経路路のみを⽤用いた場合を1として正規化した結果
27
WIT 2015
15/06/25
カプセル化のオーバーヘッド
¤  MTUサイズの減少
¤  IPIPなら20byte、GREなら24byteパケットサイズが減少
¤  複数回カプセル化すれば、パケットサイズはさらに減少
¤  8ポートなら9割以上のパスが3回のカプセル化で指定可能
¤  MTU 1500byte : 4.8 %のパケットサイズの減少
¤  MTU 9000byte : 0.8 %のパケットサイズの減少
1
CDF
0.8
0.6
0.4
0.2
0
8-port
12-port
0
1
2
3
4
Number of relay points
5
6
28
WIT 2015
15/06/25
結論論
¤  汎⽤用機器で構築したDCネットワークにおけるマルチパス⼿手法
¤ 
¤ 
¤ 
¤ 
複数パス選択の機能をエンドホストへ移⾏行行
様々な既存のトンネリングプロトコルを利利⽤用可能
ソフトウェアネットワークスタックへの⼩小さな変更更で実現可能
Random Graphトポロジにおける評価
¤  最短経路路のみを⽤用いた場合に対して1.3倍の性能向上
¤  ECMPよりも⾼高い転送率率率を実現
¤  今後の課題
¤  Random Graph以外のトポロジへの適⽤用
提案⼿手法
トポロジ
利利⽤用するパス
COTSスイッチを
利利⽤用
トポロジ変更更
への追従性
Fat-tree
Random Graph
Multiple Paths
YES
YES
29