vi CONTENTS 2.2.3 Multi-Bit Trie /33 2.2.4 Level Compression Trie /35 2.2.5 Lulea Algorithm 37 2.2.6 Tree Bitmap Algorithm /42 2.2.7 Tree-Based Pipelined Search /45 2.2.8 Binary Search on Prefix Lengths /47 2.2.9 Binary Search on Prefix Range 48 2.3 Hardware-Based Schemes /51 2.3.1 DIR-24-8-BASIC Scheme /51 2.3.2 DIR-Based Scheme with Bitmap Compression(BC-16-16)/53 2.3.3 Ternary CAM for Route Lookup /57 2.3.4 Two Algorithms for Reducing TCAM Entries /58 2.3.5 Reducing TCAM Power-CoolCAMs 60 2.3.6 TCAM-Based Distributed Parallel Lookup /64 2.4 IPv6 Lookup /67 2.4.1 Characteristics of IPv6 Lookup /67 2.4.2 A Folded Method for Saving TCAM Storage /67 2.4.3 IPv6 Lookup via Variable-Stride Path and Bitmap Compression /69 2.5 Comparison /73 3 PACKET CLASSIFICATION 77 3.1 Introduction /77 3.2 Trie-Based Classifications /81 3.2.1 Hierarchical Tries /81 3.2.2 Set-Pruning Trie /82 3.2.3 Grid of Tries /83 3.2.4 Extending Two-Dimensional Schemes /84 3.2.5 Field-Level Trie Classification (FLTC)/85 3.3 Geometric Algorithms /90 3.3.1 Background /90 3.3.2 Cross-Producting Scheme /91 3.3.3 Bitmap-Intersection /92 3.3.4 Parallel Packet Classification (P2C)/93 3.3.5 Area-Based Quadtree /95 3.3.6 Hierarchical Intelligent Cuttings /97 3.3.7 HyperCuts /98 3.4 Heuristic Algorithms /103 3.4.1 Recursive Flow Classification 103 3.4.2 Tuple Space Search /107Book1099 — “ftoc” — 2007/2/16 — 21:26 — page vi — #2 vi CONTENTS 2.2.3 Multi-Bit Trie / 33 2.2.4 Level Compression Trie / 35 2.2.5 Lulea Algorithm / 37 2.2.6 Tree Bitmap Algorithm / 42 2.2.7 Tree-Based Pipelined Search / 45 2.2.8 Binary Search on Prefix Lengths / 47 2.2.9 Binary Search on Prefix Range / 48 2.3 Hardware-Based Schemes / 51 2.3.1 DIR-24-8-BASIC Scheme / 51 2.3.2 DIR-Based Scheme with Bitmap Compression (BC-16-16) / 53 2.3.3 Ternary CAM for Route Lookup / 57 2.3.4 Two Algorithms for Reducing TCAM Entries / 58 2.3.5 Reducing TCAM Power – CoolCAMs / 60 2.3.6 TCAM-Based Distributed Parallel Lookup / 64 2.4 IPv6 Lookup / 67 2.4.1 Characteristics of IPv6 Lookup / 67 2.4.2 A Folded Method for Saving TCAM Storage / 67 2.4.3 IPv6 Lookup via Variable-Stride Path and Bitmap Compression / 69 2.5 Comparison / 73 3 PACKET CLASSIFICATION 77 3.1 Introduction / 77 3.2 Trie-Based Classifications / 81 3.2.1 Hierarchical Tries / 81 3.2.2 Set-Pruning Trie / 82 3.2.3 Grid of Tries / 83 3.2.4 Extending Two-Dimensional Schemes / 84 3.2.5 Field-Level Trie Classification (FLTC) / 85 3.3 Geometric Algorithms / 90 3.3.1 Background / 90 3.3.2 Cross-Producting Scheme / 91 3.3.3 Bitmap-Intersection / 92 3.3.4 Parallel Packet Classification (P2C) / 93 3.3.5 Area-Based Quadtree / 95 3.3.6 Hierarchical Intelligent Cuttings / 97 3.3.7 HyperCuts / 98 3.4 Heuristic Algorithms / 103 3.4.1 Recursive Flow Classification / 103 3.4.2 Tuple Space Search / 107