BDD/MDD を用いたパケット処理理手法

2014-‐‑‒09-‐‑‒08 ERATO湊Pワークショップ
BDD/MDD を⽤用いた
パケット処理理⼿手法
井上武（NTT未来ねっと研究所）
Joint work with
•  間野暢, ⽔水⾕谷后宏, 明⽯石修 (NTT未来研)
•  湊真⼀一 (北北⼤大) Copyright©2014 NTT corp. All Rights Reserved.
アウトライン
パケット
コンピュータNW
•  パケット分類処理理とは
•  新しいNWアーキテクチャにおける課題
•  BDD/MDD演算を⽤用いた提案⼿手法
•  MDD（multi-‐‑‒valued decision diagram）
•  実験結果
Copyright©2014 NTT corp. All Rights Reserved.
2
パケット分類処理理とは
•  ルータのパケット処理理⽅方法を決定するNWの基本機能
•  転送先ルータの選択
•  セキュリティのためのアクセス制御
•  通信トラフィックの統計情報収集
•  パケットにマッチする最上位ルールを選択
•  ルール：パケットヘッダのビットパターン → 処理理⽅方法
•  ヘッダ：IPアドレス，TCPポートなど（5-‐‑‒12種，数百ビット）
•  ビットパターン：各フィールドを範囲（preﬁx）で指定
IPアドレス
TCPポート
処理理⽅方法
1.1.1.0〜～7
80
ルータ1に転送
1.1.1.0〜～255
any
廃棄
1.1.2.0〜～255
<1024
ルータ1に転送
any
any
ルータ2に転送
Copyright©2014 NTT corp. All Rights Reserved.
3
伝統的なパケット分類⼿手法
•  ⾼高い性能要件
•  数⼗十万ルール
•  毎秒 10M パケット（100 nsec/パケット）
•  Trie
ルール数がさほど多くないことを利利⽤用
•  ルール集合をフィールド条件に従って分割していく
•  葉葉に複数のルールが残るときは，線形検索索で最上位ルールを選択
•  段数が少なく，CPUキャッシュに収まるくらい⼩小さいこと
IP∈1.1.2.0〜～255
{4}
1024
{1,2,4}
TCP=80
{3,4}
{2,4}
Trie
80
ルータ2
{3,4}
IP=1.1.1.0〜～255
ルータ1
TCP
{ルール1,2,3,4}
IP
{1,2,4}
Copyright©2014 NTT corp. All Rights Reserved.
4
ヘッダ空間の分割新しいNWアーキテクチャへの移⾏行行
•  インターネットは分散アーキテクチャ
•  各ルータが⾃自律律的に動作するため，運⽤用管理理が困難だった
•  組織内NWのルータは⾃自律律分散でなくてもよいのでは?
•  SDN（software-‐‑‒deﬁned networking）へ
•  コントローラでNW全体を集中管理理し，ルータを制御する
•  NW全体を⾒見見渡して⾏行行う⾼高度度な運⽤用管理理がやりやすくなる
•  例例）品質保証，設定検証，故障箇所特定（下図）
パケット観測
観測パケットに期待される挙動
パケットが出ていかない？
コントローラ
ルータ誤動作によりファイアウォールを
通さなかったので廃棄された，と判明
Copyright©2014 NTT corp. All Rights Reserved.
5
パケット分類の新たな課題（1/3）
•  従来は各ルータの処理理⽅方法を決定すれば⼗十分だった
A3
A1
Field2
A2
B2
A1 A3
7
Drop
0
C2
B3
C3
7
Drop
Field2
7
B1
B2
B1
B3
0
0
Field1
7
C
Drop
C1 C3
C2
A2
B
Field2
A
C1
0
0
Field1
0
7
Field1
7
各ルータのヘッダ空間
（3ビット×2フィールド）
Copyright©2014 NTT corp. All Rights Reserved.
6
パケット分類の新たな課題（2/3）
•  ルータ単体の処理理⽅方法ではなく，NW全体での経路路ごと
にパケットを分類する必要がある
•  すると，ヘッダ空間は複雑に細分化される
A
Drop
II A
B
C
B
C
III A
:
B
C
XII A
B
C
NW全体での経路路パターン
7 I
II
III
Field2
I
0
0
VII IX
IV
V
VI
VIII XXI
Field1
XII
7
細分化されるヘッダ空間
Copyright©2014 NTT corp. All Rights Reserved.
7
パケット分類の新たな課題（3/3）
•  ヘッダ空間は数億にも（！）細分化される
•  従来の trie はルール集合を分割しながら構築していくため，
肥⼤大化してしまう（CPUキャッシュやメモリから溢れる）
Field2
7 I
II
III
0
0
•  既存研究と同程度度の性能要件（10M/s）を満たせないと，
パケットロスや障害の⾒見見逃しなどの問題が発⽣生する
VII IX
IV
V
VI
VIII XXI
Field1
XII
7
数億ルール
IPアドレス TCPポート NW全体での経路路
1.1.1.0〜～7 80
{…}
:
:
{ルール1,…,億}
IP=1.1.1.1
…
{…}
…
この巨⼤大な表を作ったら負け
なお，経路路パターン数は数万でおさまる
Copyright©2014 NTT corp. All Rights Reserved.
8
アイデア：BDD/MDD演算の利利⽤用
•  NW全体のヘッダ空間を，巨⼤大なルール表にしてはならない
•  各ルータのルール表を直接「演算」して，NW全体を表すデー
タ構造を構築できないか
A3
Field2
A2
B2
A1 A3
Drop
0
0
BDD
BDD
7
Field1
BDD
7
C2
B3
B2
7
B1
B3
0
0
7 I
II
III
C
C3
Drop
Field2
7
B
BDD
BDD7
Field1
BDD
Field2
A1
B1
Drop
C1 C3
C2
A2
Field2
A
C1
0
0
BDD
BDD7
Field1
BDD
演算
0
MDD
0
VII IX
IV
V
VI
VIII XXI
XII
7
Field1
•  まず，ルールごとに⼩小さな BDD を作り，BDD の演算を利利⽤用
して⼀一つのデータ構造にまとめたらいいのではないか
•  複数の値（経路路パターン）に対応づけたいので，ゴールは
MDD（葉葉種の多い BDD）にしよう
Copyright©2014 NTT corp. All Rights Reserved.
9
パケット分類BDD/MDDの構築（1/3）
1.  ルール表の各エントリにマッチする BDD を構築する
•  ヘッダの各ビットを変数とする
2.  直積のような操作をし，経路路パターンごとにヘッダ空
間を表す別の BDD（次スライド）を構築する
A3
A
A1
B
B2
B3
C3
BDD
BDD
直積
Field1
Field2
Action
Field1
Field2
Action
[0,3]
[2,5]
B2
[2,2]
[1,3]
C2
[4,5]
*
B1
[4,5]
*
C1
[7,7]
[1,3]
B3
[6,7]
*
C3
*
*
Drop
*
*
Drop
直積
Copyright©2014 NTT corp. All Rights Reserved.
…
処理理⽅方法
廃棄
A1から転送
A3から転送
A2から転送
C
C2
…
Field2
[3,4]
any
any
any
B1
…
Field1
any
[4,5]
[6,7]
[0,3]
A2
C1
10
パケット分類BDD/MDDの構築（2/3）
2.  経路路パターンごとにヘッダ空間を表す BDD を構築する
Field2
7 I
II
III
経路路 I（⿊黒）のみを
表す BDD
I
A
B
C
0
01
0
1
0
21
32
45
43
43
45
45
56
1
0
II
A
B
VII IX
IV
V
VI
VIII XXI
Field1
XII
7
C
……
この BDD をひとつずつ検査して
パケットを分類することもできるが，
とても遅い
Copyright©2014 NTT corp. All Rights Reserved.
経路路パターン（I, …）と同数の BDD
11
パケット分類BDD/MDDの構築（3/3）
3.  経路路パターン（I, …）を葉葉とする MDD に集約する
…
01
0
1
21
32
経路路 I の BDD
45
43
43
45
45
56
1
0
0
1
1
3
2
3
3
3
Field2
2
7 I
II
III
3
0
NW全体の経路路パターンを表すMDD
4
5
5
II
III
4
I
4
4
5
5
VI
V
4
5
IV
VII
4
5
5
5
VIII
XI
XII
4
0
4
5
VII IX
IV
V
VI
VIII XXI
Field1
XII
7
5
IX Copyright©2014 X
NTT corp. All Rights Reserved.
12
実験：BDD/MDDサイズ（ノード数）
•  （実験的には）BDD 合計サイズより MDD が⼩小さくなる
•  ただし，ビット順（変数順）を逆にすると，MDD のほう
が⼤大きくなる
•  MDD は葉葉の種類が多い（〜～数万）ため，suﬃx ルール
（逆順）にするとノードが共有されにくいようだ
MDDサイズ
アドレス・ポート番号の構造（preﬁx） 1.E+07
は MDD にとって好ましいようだ
ビット正順
ビット逆順
パデュー⼤大NW
パデュー⼤大NW
1.E+06
1.E+05
Internet2
スタンフォード⼤大NW
1.E+04
1.E+04
1.E+05
1.E+06
1.E+07
Copyright©2014 NTT corp. All Rights Reserved.
BDD合計サイズ
13
ビット集約によるMDDパスの短縮
0
1
•  メモリと引き替えに⾼高速化
2
•  Kビット集約：パス⻑⾧長 1/K倍
•  2K 枝：メモリ∝2K/K
4
•  ノード数 1/K倍
•  ⼦子／ノード 2K
K=2
0,1
5
5
II
III
1
2
3
3
6ホップ
4
4
4
I
5
5
VI
V
3
4
5
IV
VII
1
2
3
0
K=8 にしても
16倍ですむ
21/1 = 2
22/2 = 1
24/4 = 4
28/8 = 32
3,4
2,3
1
3
4
4
4
5
5
5
5
VIII
XI
XII
IX
5
X
K=2
1,2
0,1
0
3
2
3
3,4
2,3
3,4
2,3
3,4
2,3
3ホップ
3 2 0
1
5,6
4,5
3
2
3
III
0
2
1
3
5,6
4,5
1
0 1
2
II
3 2
1I
0
4
IV
3
0
0
5,6
4,5
5,6
4,5
2
1
1
2
2 0
1
3
0
5,6
4,5
3
1 2 3
5,6
4,5
0
3
1
Copyright©2014 NTT corp. All Rights Reserved.
5
V
6
VI
7
VII
1 3
8
VIII
10
X
2
2
5,6
4,5
0
0
14
23
9
IX
5,6
4,5
1
0
3
11
XI
実験：メモリ使⽤用量量と分類速度度
•  メモリ使⽤用量量と分類速度度を評価（ビット集約 K=8）
•  CPUキャッシュを効果的に利利⽤用できるほどのメモリ使⽤用量量
•  BDD/MDD 変換中のメモリ使⽤用量量は数⼗十倍（<2GB）で問題ない
•  ⽬目標である 10M/s を超える分類速度度を達成
60
50
40
30
20
10
0
メモリ使⽤用量量 [MB]
50
40
30
20
10
0
分類速度度 [M packet/s]
⽬目標
Copyright©2014 NTT corp. All Rights Reserved.
15
まとめ
•  新しいNWアーキテクチャに適したパケット分類
⼿手法を提案した
•  各ルールを表す BDD の集合から，演算によって MDD を構築する
•  実験により，毎秒 10M パケットの分類速度度を確
認した
•  今後の予定
•  信学会IN研（⽊木曜），IEEE ICNP（2014/10）発表
•  ドラフト版 http://bit.ly/pcsdn
•  実⽤用化に向けた研究開発も進展中
Copyright©2014 NTT corp. All Rights Reserved.
16

Download Report