More Related Content
What's hot (20)
Similar to 罢颁础惭のしくみ (6)
罢颁础惭のしくみ
- 1. スイッチ?ルータのしくみ ?罢颁础惭のしくみ? @yogata 2013/2/24 1
- 2. 高速に転送するには —?? 受信?転送先決定?転送 を高速に行う ← 結論 —?? でも，，， —?? 送受信のEO/変換やSerDes(シリアル化，非シリアル化)な はハードウェアで実装されていて，既に高速で処理可能 —?? そこで，転送先決定の中身に着目 3.転送 1.受信 2.転送先決定 Switch/Router 2
- 3. 転送部でやること —?? パケットヘッダとエントリ(ルーティング?フォワーディング? NDP/ARPテーブル等)を比較してマッチするエントリを探す —?? ポイント —?? 例えばACLの探索 —?? プレフィックス指定やANY指定でのマッチングを行う —?? 例えばルーティングの探索 —?? ロンゲストマッチを行う →複数のエントリにマッチする場合，プレフィックス長をみて探索 3
- 4. マッチング —?? いろんなやりかた (たとえばルーティングの場合) —?? ソフトウェア —?? パケットヘッダに対して，エントリを1つずつ比較して，最後にマッ チした全エントリの中からプレフィックス長が最大のエントリを探 す (シーケンシャルマッチング) —?? 事前にプレフィックス長でルーティングエントリをグループ化して おき，プレフィックス長が大きい方から順番にマッチングする ( シーケンシャルマッチング＋エントリソート) —?? 探索木を作ってマッチングする (探索木) —?? ハードウェア —?? TCAM 4
- 5. マッチするエントリの探索 —?? (1)パケットヘッダに対してエントリを1つずつ比較して，(2) 最後にマッチした全エントリの中からプレフィックス長が最 大のエントリを探す (シーケンシャルマッチング) パケットヘッダ ルーティングテーブル (1)全部とマッチして DstIP:192.0.2.100 192.0.0.0/8 192.168.0.0/24 192.0.2.0/24 10.0.0.0/8 (2)プレフィックス長が 最大のエントリを探す 5
- 6. マッチするエントリの探索 —?? 事前にプレフィックス長でルーティングエントリをグループ化 しておき，プレフィックス長が大きい方から順番にマッチング する パケットヘッダ ルーティングテーブル DstIP:192.0.2.100 /8 192.0.0.0 10.0.0.0 ??? /24 192.168.0.0 192.0.2.0 ??? —?? マッチした時点で処理を終えることができる 6
- 7. マッチするエントリの探索 —?? 探索木 111* 110* 101* 100* 011* 010* 001* 000* R0,R1,R5,R6 R2,R3,R4 R7 R8 R9 R10,R11 引用元 http://cseweb.ucsd.edu/~susingh/papers/hyp-sigcomm03.pdf HiCutアルゴリズムの場合 7
- 8. マッチするエントリの探索 —?? TCAM —?? Ternary Content Addressable Memory —?? TCAM：マッチングを行う専用のハードウェア —?? 0, 1, どちらでも良いの3値(ternary)でマッチングを行う —?? CAMだと，0, 1の2値でマッチングを行う 8
- 9. (罢)颁础惭のしくみ —?? (T)CAMの3つのしくみ (1)?入力 (2)?マッチング (3)?出力 (2)マッチング (3)出力 (1)入力 引用元 http://www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf 9
- 10. (罢)颁础惭のしくみ —?? (1)入力 —?? パケットヘッダXをもとに，Xと?Xを比較部に渡す ?X0 X0 X 引用元 http://www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf 10
- 11. (罢)颁础惭のしくみ —?? (2)マッチング (CAMの場合) ルールのプライオリティ順に事前に並べておく ルーティングテーブルやACLの各ルール CAMのワードビットサイズ 各ルールの1ビット マッチング ? 結果（出力） Priority Encoder エントリ数 C C ヘッダ情報 SRAMベース とルールの ヘッダ情報 のメモリ マッチング （入力） ? (6トランジスタ) 引用元 http://www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf 11
- 12. (罢)颁础惭のしくみ —?? (2)マッチング (CAMの場合) C=0 C=1 ?緑枠はマッチしているパターン X0=0 ?この例では，Xと?C??XとCを 比較 ?マッチすれば不一致なので MLをLOWにする (GNDに落とす) X0=1 ?全ビットでマッチすれば終端で ML(Match Line)がHIGHの ままとまる HIGH LOW 引用元 http://www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf 12
- 13. (罢)颁础惭のしくみ —?? (2)マッチング (TCAMの場合) —?? CAMにSRAMをつけたもの ?SRAMが1だと このビットはマッチとなる ?SRAMが0だと下のマッチングに したがって結果を返す CAM 引用元 http://www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf 13
- 14. (罢)颁础惭のしくみ —?? (3)出力 —?? 比較部ではマッチしたすべてのエントリを返すので，出力部で 最もプライオリティの高いエントリを選択する →プライオリティエンコーダ 14
- 15. (罢)颁础惭のしくみ —?? (3)出力 (プライオリティエンコーダ) —?? マッチしたエントリD0-3の結果に応じた出力xyVを求める 引用元 http://filebox.ece.vt.edu/~jgtront/introcomp/encoder.swf 15
- 16. (罢)颁础惭のしくみ —?? (3)出力 (プライオリティエンコーダ) —?? 結果を回路にする 引用元 http://filebox.ece.vt.edu/~jgtront/introcomp/encoder.swf —?? エントリ数が多いと大変 16
- 17. まとめ —?? TCAMはマッチングが早いが，消費電力が大きい (らしい) —?? パケットとエントリのマッチングをビット単位で並列で実施する —?? その結果を集約することでマッチしたエントリを探索する —?? 複数エントリをマッチした場合は，事前に最上位エントリほど 優先度が高いように設定しているため，専用回路(プライオリ ティエンコーダ)を使って最優先エントリを確定する —?? これらすべてのマッチングを行う専用回路を用意し，1クロック でマッチングが完了することから，非常に高速にマッチングを 行える —?? ただし，回路全体を使う必要があるため消費電力が大きい 17
- 18. 参考 —?? Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey —?? http://www.pagiamtzis.com/pubs/pagiamtzis- jssc2006.pdf —?? Intro to Computer Engineering Tutorial Material —?? http://filebox.ece.vt.edu/~jgtront/introcomp/ —?? Packet Classification Using Multidimensional Cutting —?? http://cseweb.ucsd.edu/~susingh/papers/hyp- sigcomm03.pdf 18