パケットフォワーディングを支える技術 (2) ハードウェア処理ルータの内部詳解

Transcription

1 パケットフォワーディングを支える技術 (2) ハードウェア処理ルータの内部詳解 2012 年 11 月 20 日 アラクサラネットワークス株式会社 製品開発部

2 自己紹介 2

3 はじめに ハードウェア処理ルータといえば ワイヤーレートでのパケット処理が可能 使われている要素技術レベルで見るとサーバとの差は無い SRAM : キャッシュメモリ パケットバッファ DRAM : メインメモリ パケットバッファ テーブルメモリ CAM : キャッシュメモリ, TLB 検索 転送テーブル検索 SerDes : PCI Express XAUI, XLAUI, CAUI, Interlaken etc クロスバースイッチ : CPU( コア ) 間接続 プロセッサ間接続 高速化手法 : マルチコア / スーパースケーラ 処理のパラレル化 パイプライン : 共通の技術 何が違うのか? 柔軟性を犠牲にすることで性能の最大化 PCI Express は PCI-SIG の商標または登録商標です 3

4 本セッションの内容 ネットワーク装置におけるパケットのハードウェア処理 ハードウェア処理の基本的な考え方 転送プレーンの構成方法 ハードウェアによるパケット転送処理の流れ 高速テーブル検索手法 本セッションの対象外の内容 経路テーブルの作成のためのプロトコル処理 経路テーブルに基づいた転送テーブル作成 配布 アップデート 経路収束性能の向上 4

5 ハードウェア処理の基本的な考え方 制御プレーンと転送プレーンの分離 制御プレーンはソフトウェア処理に専念 経路制御など 高速性より柔軟性 転送プレーンはハードウェア処理に専念 パケット転送など 転送エンジンを増やすことで性能を n 倍化 経路テーブル (RIB) と転送テーブル (FIB) の分離 制御プレーンは他ルータ スイッチと通信して経路情報 (BGP OSPF など ) を交換し RIB を構築 さらに RIB から FIB を算出し 転送プレーンに配布 制御プレーン RIB 転送プレーン転送プレーン FIB FIB RIB:Routing Information Base FIB: Forwarding Information Base 5

6 転送プレーンの配置 転送エンジンを複数持つことで転送性能を n 倍化 複数の転送エンジン持つと相互接続するスイッチが必要 価格と性能のトレードオフ 分散型 集中型 CPU 一つ一つ 転送エンジン複数一つ 性能 転送エンジンを追加することで性能向上 一つの転送エンジンの性能で頭打ち 価格高い安い 主なターゲットキャリア データセンタ企業 6

7 分散型アーキテクチャ (AX7800 の例 ) BCU CSW Redundant BCU CSW PS PPU PPU PPU PPU 最大 8PPU まで snif snif snif snif dnif snif snif 1GbE(GBIC) 10/100/1000MbE 1GbE(SFP) 10GbE x 1 x 6 x 12 x 12 10/100/1000MbE x 48 OC48 POS x 4 OC192 POS x 1 BCU:Basic Control Unit PPU: Packet Processing Unit CSW: Crossbar Switch snif : single-size Network Interface dnif: double-size Network Interface PS : Power Supply 7

8 集中型アーキテクチャ (AX6300 の例 ) CPU エンジンと転送エンジンが同一のモジュールで実装 電源 ( 電源個別二重化 ) CPU MSU1 検索 転送エンジン FAN MSU2 (Redundant) 検索 転送エンジン CPU NIF 1 NIF 2 NIF 3 NIF 4 PHY PHY PHY PHY 1GbE 10GbE 1GE 10GE 8

9 高速化実現方式 パケット転送処理のパラレル / パイプライン化 機能として 4 段のパイプライン (1) 受信処理 (2) 入力検索 ( ルーティング フィルタリング ) (3) 出力検索 ( ルーティング フィルタリング ) (4) 送信処理 それぞれの機能ブロックでさらに細分化されたパイプライン 例 : TCAM 検索と RAM 検索をパイプライン可 トータルで 20 段強 高パイプライン化 9

10 クロスバースイッチ マトリックススイッチ化されたバス バックプレーンとも言う 任意の転送エンジンから任意の転送エンジンへパケットを ( 内部的に ) 転送 In と out がぶつからない限り並行転送 LSI レベルの誤り率と揺れの少ない遅延 再送は考えない ( 考える必要がない ) in out 10

11 クロスバースイッチ技術 パケットを 32 バイト単位に分割 大きさを揃えて クロスバースイッチの競合をなくす 順序性は保存されてる パケット落ちはない セル化することによってのデメリット 内部ヘッダ分のオーバーヘッドがある 1 対多通信も可能 マルチキャストで使用 in in out out 11

12 パケットフォワーディング処理の流れ (1/3) 参考 : RFC1812 ( Requirements for IP Version 4 Routers ) Start リンクレイヤより IP パケット受信 IP ヘッダの正常性チェック IP オプション処理 ( ルーティング決定以降に行う処理は除く ) パケット長チェック (20Bytes 以上 ) Header Checksum 正常性チェック Version チェック ヘッダ長チェック等 宛先 IP アドレスにより以下の何れか決定 自ルータ受信 転送 自ルータ受信かつ転送 ヘッダ長 >5 word の場合にオプション有り 次頁 12

13 パケットフォワーディング処理の流れ (2/3) 前頁 転送処理の場合 ユニキャストの場合 宛先 IP アドレスによりユニキャストかマルチキャストかを判別 フォワーディングテーブルより Nexthop (and 出力インタフェース ) を決定 宛先 IP アドレスをキーにしてテーブル検索 ( ロンゲストプリフェックスマッチ ) 転送の有効性チェック ( フィルタリング ) 送信元 / 宛先 IP アドレス正常性チェック アクセス許可リストに基づいたパケットフィルタリング TTL 減算 & チェック 減算後 0 になれば廃棄 ( 送信元に通知 ) IP オプション処理 ( ルーティング決定以降に行う処理 ) 次頁 13

14 パケットフォワーディング処理の流れ (3/3) 前頁 Fragmentation 処理 ( 必要であれば ) パケットがルーティングテーブル検索の結果得られた出力インタフェースの MTU よりも大きい場合にフラグメンテーションを行う Header checksum 更新 Nexthop に対するリンクレイヤアドレスの決定およびリンクレイヤカプセル化 TTL 減算により 再計算の必要あり 送信インタフェースに送信 End 14

15 高速アドレス検索エンジンの構成例 フォワーディング フロー検索 統計採取を 1 チップで実現! ルータ バッファメモリ ヘッダ データ ルーティングテーブル 装置管理部 ヘッダポート1 ポート2 ポート3 データ (1) パケットを一時蓄積 (4) フィルタ / QoS 制御 ( 高優先のパケットから読出し ) (2) 宛先検索 宛先 = ポート 5 (3) フィルタ QoS 決定 通過 フォワーディングテーブル フローテーブル ( フィルタ用 ) ヘッダ ポート4 データポート5 ポート6 (5) パケット送信 パケット処理部 (6) 統計情報収集 検索エンジン 高優先 フローテーブル (QoS 用 ) 統計情報テーブル 15

16 フォワーディングテーブル検索 フォワーディングは送信先ホストというより 送信先ネットワークに向けての転送である フォワーディングテーブルは ルーティングテーブルから転送に必要な情報を抽出して構成される送信先ネットワーク毎の情報を持つテーブル 送信先ネットワークサブネットマスク次ルータ (Next Hop) 出力 IF # #8 出力リンク (Ether の場合 ) 00:00:80:30:37:d1 00:00:80:42:4a:c3 フォワーディングテーブルのインプリについて IPv4 アドレスは 32bits 2 の 32 乗 ( 4.3 ギガ個 ) のアドレス空間 直接アドレッシングによる単純なテーブルで構成しようとすると 1 エントリ当たり 1Byte としても 4.3GBytes 必要! 単純なメモリアクセスでの実現不可 圧縮した ( エントリ数に制約を設けた ) テーブルおよび そのテーブルを高速に検索する手段が必要 16

17 Longest Prefix Match とは Longest Prefix Match CIDR(Classless Inter-Domain Routing) VLSM(Variable Length Subnet Mask) により 受信 IP パケットのネットワークプレフィクス ( 言いかえればマスク長 ) が一意的に決まらない マッチするマスク長が一番長い (Longest Match する ) 送信先ネットワークを検索する必要あり 処理の複雑化 Longest Prefix Match の具体例 行きのIPパケットに対しては下記の (B) を選択 (A) ( マスク : ) (B) ( マスク : ) (C) ( マスク : ) 17

18 高速テーブル検索手法 ハッシュ演算を用いたテーブル圧縮技術 IP アドレス (32bit) を特定の演算 ( わり算や CRC 等 ) を用いて圧縮し (ex.16bit) テーブル自体のサイズをコンパクト化 二分木検索アルゴリズム IP アドレスを 0,1 の bit 列に分解した木構造のテーブルによる検索 パトリシアンツリー等 多分木検索アルゴリズム 二分木検索の多ビットへの拡張 Controlled Prefix Expansion CAM ( 連想記憶メモリ ) の採用 データ入力に対し対応するアドレスを出力する特殊なメモリ ( 通常のメモリはアドレス入力するとデータを出力 ) IP アドレス検索等をターゲットにした Longest Prefix Match 対応の CAM が出てきている 18

19 ハッシュによる検索テーブルの圧縮技術 (1/2) Address Data IP アドレス aabbccdd (32bit) ハッシュ演算 演算結果 abcd (16bit) 1 Address abcd 1234 Data 初段メモリアドレス空間は 宛先 =x IP Addr = aabbccee Next Ptr = 5678 宛先 =y IP Addr = aabbccdd Next Ptr = null 段目メモリ 1IPアドレスをハッシュ演算により圧縮 2 初段のメモリリードにより宛先情報テーブルのポインタを得る 32 段目のメモリリードにより宛先情報と該当する受信アドレス情報を得る 4 受信アドレスに関するものでない場合には次の情報を読み出し 5 以下 3と4を繰り返し 受信アドレスによる検索結果を得る 19

20 ハッシュによる検索テーブルの圧縮技術 (2/2) 検索キーをある特定の演算 ( わり算や CRC 等 ) の結果に置き換えることにより ビット幅を圧縮 Ex. IPv4 DA(32bit) を CRC16 により 16 ビット化 実装が比較的容易かつ性能を出しやすい 前頁の例では最短 2 回のメモリアクセスで宛先解決可能 ハッシュ演算結果をもとに宛先情報を引き出す このときたまたま演算結果が同じになるエントリが複数あった場合にはその中のどれか 1 つを選ぶ必要有り 処理の複雑化, 遅延の増大 ( 最低保証値が見積もれない ) 最善は 100M sps( ) 以上だが 最悪は数百 k sps? LPM 検索ができないため 経路集約を行うことができず結果的にエントリ数が膨大になる sps (search per second) 1 秒あたりの検索回数 20

21 パトリシアンツリー検索 (1/2) パトリシアンツリーとは? 二分木検索法の一種 空の分木ノードを省略し 検索回数を削減 レベル15 レベル22 ルート 1 レベル 15 (A) xxx.xxx= (B) xxx= (C) xxx= (D) xxx.xxx= Internal Node: 分木ノード レベル A D 0 レベル レベル 17 External Node: エントリが登録されているノード Internal &External Node: 分木ノードでかつエントリが登録されているノード B C 21

22 パトリシアンツリー検索 (2/2) 従来からUNIXで使用 検索回数は平均 :Log 2 (N) 最大:L Nは登録エントリ数 Lはエントリのビット数 IPv4で64Kエントリ登録の場合 平均 :16 回 最大 :32 回 エントリの分布で検索回数にばらつきがある 最悪を考慮すると検索性能は数百 k~ 数 M sps 22

23 Controlled Prefix Expansion (1/3) Controlled Prefix Expansion とは? プレフィックス ( マスク ) 長を検索し易いように拡張する ツリー検索では 1 ビットずつ検索をしていく必要があったが 複数ビット単位で検索することで検索回数を削減する 例 : 検索のビット幅を 2 ビット単位に拡張する場合 以下のようにエントリを拡張し 拡張したエントリは全て同様に扱う 例 ) ** というエントリがあった場合 という 4 つのエントリに拡張してそれらを全て同一エントリとして扱う メリット 検索回数を削減 固定的に 4 ビット単位に拡張すると IPv4 の場合 最大でも 8 回 (=32/4) の検索回数で解決する 検索性能としては単一メモリの使用で数 M~ 数十 M sps ( メモリを複数個パイプライン的に並列アクセスすることで 100Msps 以上の性能を出すことも可能 ) 23

24 Controlled Prefix Expansion (2/3) 2 ビット単位の拡張の例 ) エントリ P9 を追加する場合 エントリの拡張 Original P5=0* P1=10* P2=11 1* P3= * P4=1* P6=10 00 * P7= * P8= * P9= * Expanded 00 *(P5) 01 *(P5) 10 *(P1) 11 *(P4) *(P2) *(P2) *(P6) *(P3) *(P3) *(P7) *(P9) *(P9) *(P8) *(P8) Length2 Length4 Length6 Length8 00:P7 01: 10: 11: 実際のデータ構造 00:P6 01: 10: 11: 00:P8 01:P8 10: 11: 00:P5 01:P5 10:P1 11:P4 00:P9 01:P9 10: 11: 00: 01: 10:P2 11:P2 00: 01: 10:P3 11:P3 本来 9 個のエントリが 14 個に膨れ上がる Level1 (Length2) Level2 (Length4) Level3 (Length6) Level4 (Length8) 24

25 Controlled Prefix Expansion (3/3) デメリット 拡張することにより テーブル ( メモリ ) 量の増大 例えば 4 ビット単位の拡張で 00xx 0000,0001,0010,0011 の場合 一つのエントリに対して 4 エントリの登録が必要 容量が増えると同時にメンテナンスの負荷も増大 登録 / 削除するエントリ数が増えると 転送処理に影響を与える場合がある Prefix 拡張したエントリを作成するための CPU 負荷がかかる 近年のメモリの大容量 / 高速化 Prefix 拡張演算のオフロード化を行うことで容量的にもメンテナンス的にも実用できるレベルになりつつある 25

26 CAM (1/5) Contents Addressable Memory( 連想記憶メモリ ) データを入力するとアドレスを出力する特殊なメモリで 高速検索処理に特化 ( 通常のメモリはアドレス入力するとデータを出力 ) Longest Prefix Match(LPM) が可能な CAM(Ternary CAM) も存在 検索回数は 1 回のみ 高速検索 ( 数十 M~ 数百 M sps) 検索時間はビット幅 ( ) や登録エントリ数に依存しない エントリの管理に工夫が必要 実際には制限あり 26

27 CAM (2/5) Ternary CAM によるアドレス検索動作の一例 CAM のデータとして IP アドレス およびネットマスクを登録 検索時は宛先 IP アドレスを検索データとして CAM に入力 CAM は入力された検索データとマスクデータの and をとり その後登録されているデータと一致するかどうか比較する 一致するデータがある場合は登録されているアドレスを出力 CAM の出力アドレスでアクセスするメモリからテーブル内容を出力 CAM メモリ アドレス データ データ アドレス データ 0 A.A IF#a, MAC#a 宛先 IP アドレス (A.B.C.D) i B.B j A.B.C CAM アドレス ( j ) i j IF#y, MAC#y IF#x, MAC#x 出力 (IF#x, MAC#x) m X.X.X m IF#b, MAC#b n W.X.Y.Z n IF#z, MAC#z 27

28 CAM (3/5) Ternary CAM を用いた検索動作の課題 エントリの等力順序を工夫しないと複数ヒットする場合 LPM にならなくなってしまう 検索キー address : : : i j k : : : x y z data ***.***.*** 241.***.***.*** ***.*** ***.*** *** *** *** 255.***.***.*** *** *** ***.*** ***.*** 検索結果 Address = 2 実際には 2 と j と y がヒットするが 通常の Ternary CAM は複数ヒットした場合最も若いアドレスを検索結果として出力するため LPM で考えれば j が検索結果となるべきところを 2 として出力してしまう 28

29 CAM (4/5) Ternary CAM でのエントリ管理方法の例 Prefix 長の長いものから並べる必要有り エントリを追加するための空き領域をあらかじめ用意しておく必要有り 例 ) 新たに以下のエントリを追加 *** prefix 長 24bit の空き (NULL) 領域の一番上 (m 番地 ) に登録 address data : NULL NULL : NULL i *** j *** k *** l *** : : : x y z : : NULL NULL NULL NULL ***.*** ***.*** ***.*** NULL NULL NULL Prefix 長 32bit エントリ 32bit エントリを追加するための空き領域 Prefix 長 24bit エントリ 24bit エントリを追加するための空き領域 Prefix 長 16bit エントリ 16bit エントリを追加するための空き領域 29

30 CAM (5/5) Ternary CAM でのエントリ管理方法の例 Prefix 長の長いものから並べる必要有り エントリを追加するための空き領域をあらかじめ用意しておく必要有り 例 ) 新たに以下のエントリを追加 address data *** : NULL NULL : NULL i *** j *** k *** prefix 長 24bitの空き (NULL) 領域の l *** 一番上 (m 番地 ) に登録 : m *** NULL : NULL NULL : NULL x ***.*** y ***.*** z ***.*** NULL : : NULL NULL Prefix 長 32bit エントリ 32bit エントリを追加するための空き領域 Prefix 長 24bit エントリ 24bit エントリを追加するための空き領域 Prefix 長 16bit エントリ 16bit エントリを追加するための空き領域 30

31 各種高速 IP アドレス検索法の比較 各方式の特長をベースにした長所と短所で比較 ハッシュ方式二分木方式他分木方式 CAM 方式 機能拡張性 LPM 検索できず 経路検索特化 経路検索特化 他テーブルマージ可能 性能レンジ 数百 kpps~ 数 Mpps~ 数十 Mpps~ 数十 pps~ 数百 Mpps 数十 Mpps 数百 Mpps 数百 Mpps 性能保証 メンテナンス (Unixで実績有) 部品点数 性能保証のためにはメモリを多数使用 ( 複雑 ) 性能保証のためにはメモリを多数使用 消費電力 価格 特殊メモリ不要 特殊メモリ不要 特殊メモリ不要 経路テーブル以外を収容可能 総合評価 31

32 各種高速 IP アドレス検索法の比較 ( まとめ ) 各手段とも 一長一短あり ハードウェア ( 特に ASIC) で処理する場合には固定ピッチで性能保証できる CAM が最も扱いやすく 現在は CAM を用いるのが主流であるが 大容量化に伴うコスト / 消費電力の増加が課題となっている 上記課題に対応するために最近では CAM メーカーも工夫をしている 内部をサブブロック化してアクティブになるメモリセルを局所化 ( 1) アルゴリズム検索のチップを開発 ( 2) 装置ベンダとしては技術トレンドを見極め一つの方式に拘りしすぎずに最適なインプリをしていく必要がある

33 フィルタリング /QoS 技術 フィルタリングとは 送られてきたパケットを検査して通過させるかどうか判断する機能 QoS(Quality Of Service) とは 通信サービスの品質を指しており トラフィック ( アプリケーション ) に応じ遅延 帯域 廃棄率などの品質を決めそれらを保証する 従来の IP 網は帯域を有効利用するため安価なベストエフォートが一般的であったが VoIP や動画配信等遅延や廃棄を気にするアプリケーションが増えつつある 適切なフィルタリング /QoS 処理を行うためにはフロー識別する機能が必須 フロー識別機能はパケットフォワーディングと同様検索が必要とされるため 高速化のための工夫が必要となる 33

34 ハードウェアパケット転送時のフィルタ /QoS 処理 一般的なフロー識別子 (5 tuple) Source Address(32bit) Destination Address(32bit) Protocol type(8bit) Source Port Number(16bit) Destination Port Number(16bit) 入力パケット フロー識別 ポリシング マーキング 帯域制御 出力パケット 通過 / 廃棄 ( フィルタ ) 34

35 フロー検出技術の高速化と課題 高速化 5 tuple(ipv4 では 96bit)+α という多ビットの検索キーを高速に検索する技術が必要 性能を出すためには 1 ハッシュ 2CAM の適用が考えられるが フロー検索では exact match ではなく 任意フィールドを検索キーとすることが多く ハッシュでは対応困難 課題 検索キーの肥大化 フロー検出には CAM が最適 従来の 5 tuple に加え Layer1 Layer2 の情報や QoS 情報までを検索キーに加わることで更に検索ビット数が増加 35

36 CAM を用いたフロー検出技術の課題 CAM の検索性能は万全ではない 特定のビット幅 (1 サイクルに CAM に与えることができる検索キーのビット数 ) までは検索性能を保持することが可能だが それを超えると性能が 1/2 1/4 と劣化する 検索キー クロック 検検索索デデーータ21 検索性能が1/2に劣化検アアドレタTCAM 1 ビット幅一定 TCAM の検索では 1 回のクロック動作 (1 サイクル ) で検索できるビット幅が決まっており それ以上ののビット幅では 2 サイクルかけて検索キーを渡す アス21 ドレス1 検索結果 36

37 フロー検出高速化技術の例 パケット毎にフロー検出に必要なフィールドを選択 ( 圧縮 ) し 少ないビット幅で高速検索を実現 パケットヘッダ L2 ヘッダ (MAC アドレスなど ) L3 ヘッダ (IP アドレスなど ) L4 ヘッダ (TCP/UDP ポート番号など ) セレクタ フローテーブルは CAM で構成 フロー検出条件選択方式では 検索ビット長短縮効果で性能向上 L2 ヘッダ L4 ヘッダ 検索キー入力 L2 ヘッダ L4 ヘッダ 高優先 フロー毎の QOS 制御の優先度設定 フロー検出条件選択方式の時 スイッチング処理パケット用検索キー 選択方式時のスイッチングパケット用フローテーブル L2 ヘッダ L4 ヘッダ 低優先 L3 ヘッダ L4 ヘッダ 検索キー入力 L3 ヘッダ L4 ヘッダ 高優先 フロー検出条件選択方式でない時 ルーティング処理パケット用検索キー 選択方式時のルーティングパケット用フローテーブル L3 ヘッダ L4 ヘッダ L2ヘッダ L3ヘッダ L4ヘッダ検索キー入力 L2ヘッダ L3ヘッダ L4ヘッダ 検索キー 選択方式でない 時の L2ヘッダ L3ヘッダ L4ヘッダ フローテーブル 低優先 高優先 低優先 37

38 更なる性能向上に向けて パケット転送エンジンの性能を決めるのは メモリの帯域幅 : キューイング性能 (bps) メモリのランダムアクセス性能 : テーブル検索性能 (pps) TCAM の容量 : エントリー数 TCAM の検索性能 : テーブル検索性能 (sps / pps) n 個並列に接続すれば性能は上がるが LSI のピン数増 メモリの容量 : テーブル数 / バッファ容量 容量を取れば ランダムアクセス性能が悪化 :DRAM ランダムアクセス性能を取れば容量が減少 :SRAM コスト ( 部品代 ) LSI: ダイサイズ + ピン数 ( パッケージサイズ ) に比例して上昇 DRAM : 1T+ キャパシタ SRAM : 6T TCAM : 16T 性能の向上はコストに跳ね返るだけではない bps と pps とエントリ数はトレードオフの関係 消費電力 38

39 次世代高速メモリ インターフェイスの SerDes 化 シリコン貫通電極 (TSV) 技術の導入 HC memory-FPGA/HC HybridCube-Pawlowski-Micron.pdf 39

40 40