Current PoP Architecture Core Packet Hub Layer 阿 Routers ATM Ethernet Customer Access HIGH PERFORMANCE SWITCHES AND ROUTERS H.JONATHAN CHAO AND BIN LIU
CONTENTS PREFACE XV ACKNOWLEDGMENTS xvii 1 INTRODUCTION 1 1.1 Architecture of the Internet:Present and Future /2 1.1.1 The Present /2 1.1.2 The Future /4 1.2 Router Architectures /5 1.3 Commercial Core Router Examples /9 1.3.1 T640 TX-Matrix /9 1.3.2 Carrier Routing System(CRS-1)/11 1.4 Design of Core Routers /13 1.5 IP Network Management 16 1.5.1 Network Management System Functionalities 16 1.5.2 NMS Architecture /17 1.5.3 Element Management System 18 1.6 Outline of the Book /19 2 IP ADDRESS LOOKUP 25 2.1 Overview /25 2.2 Trie-Based Algorithms /29 2.2.1 Binary Trie /29 2.2.2 Path-Compressed Trie /31
Book1099 — “ftoc” — 2007/2/16 — 21:26 — page v — #1 CONTENTS PREFACE xv ACKNOWLEDGMENTS xvii 1 INTRODUCTION 1 1.1 Architecture of the Internet: Present and Future / 2 1.1.1 The Present / 2 1.1.2 The Future / 4 1.2 Router Architectures / 5 1.3 Commercial Core Router Examples / 9 1.3.1 T640 TX-Matrix / 9 1.3.2 Carrier Routing System (CRS-1) / 11 1.4 Design of Core Routers / 13 1.5 IP Network Management / 16 1.5.1 Network Management System Functionalities / 16 1.5.2 NMS Architecture / 17 1.5.3 Element Management System / 18 1.6 Outline of the Book / 19 2 IP ADDRESS LOOKUP 25 2.1 Overview / 25 2.2 Trie-Based Algorithms / 29 2.2.1 Binary Trie / 29 2.2.2 Path-Compressed Trie / 31 v
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
Book1099 — “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
CONTENTS vii 3.5 TCAM-Based Algorithms 108 3.5.1 Range Matching in TCAM-Based Packet Classification 108 3.5.2 Range Mapping in TCAMs 110 4 TRAFFIC MANAGEMENT 114 4.1 Quality of Service /114 4.1.1 QoS Parameters 115 4.1.2 Traffic Parameters /116 4.2 Integrated Services 117 4.2.1 Integrated Service Classes 117 4.2.2 IntServ Architecture 117 4.2.3 Resource ReSer Vation Protocol(RSVP)/119 4.3 Differentiated Services /121 4.3.1 Service Level Agreement /122 4.3.2 Traffic Conditioning Agreement /123 4.3.3 Differentiated Services Network Architecture 123 4.3.4 Network Boundary Traffic Classification and Conditioning /124 4.3.5 Per Hop Behavior(PHB)/126 4.3.6 Differentiated Services Field 127 4.3.7 PHB Implementation with Packet Schedulers 128 4.4 Traffic Policing and Shaping /129 4.4.1 Location of Policing and Shaping Functions 130 4.4.2 ATM's Leaky Bucket 131 4.4.3 IP's Token Bucket 133 4.4.4 Traffic Policing /134 4.4.5 Traffic Shaping 135 45 Packet Scheduling /136 4.5.1 Max-Min Scheduling 136 4.5.2 Round-Robin Service 138 4.5.3 Weighted Round-Robin Service /139 4.5.4 Deficit Round-Robin Service 140 4.5.5 Generalized Processor Sharing(GPS)/141 4.5.6 Weighted Fair Queuing (WFQ)/146 4.5.7 Virtual Clock 150 4.5.8 Self-Clocked Fair Queuing 153 4.5.9 Worst-Case Fair Weighted Fair Queuing (WP2Q)/155 4.5.10W℉2Q+/158 4.5.11 Comparison /159 4.5.12 Priorities Sorting Using a Sequencer /160
Book1099 — “ftoc” — 2007/2/16 — 21:26 — page vii — #3 CONTENTS vii 3.5 TCAM-Based Algorithms / 108 3.5.1 Range Matching in TCAM-Based Packet Classification / 108 3.5.2 Range Mapping in TCAMs / 110 4 TRAFFIC MANAGEMENT 114 4.1 Quality of Service / 114 4.1.1 QoS Parameters / 115 4.1.2 Traffic Parameters / 116 4.2 Integrated Services / 117 4.2.1 Integrated Service Classes / 117 4.2.2 IntServ Architecture / 117 4.2.3 Resource ReSerVation Protocol (RSVP) / 119 4.3 Differentiated Services / 121 4.3.1 Service Level Agreement / 122 4.3.2 Traffic Conditioning Agreement / 123 4.3.3 Differentiated Services Network Architecture / 123 4.3.4 Network Boundary Traffic Classification and Conditioning / 124 4.3.5 Per Hop Behavior (PHB) / 126 4.3.6 Differentiated Services Field / 127 4.3.7 PHB Implementation with Packet Schedulers / 128 4.4 Traffic Policing and Shaping / 129 4.4.1 Location of Policing and Shaping Functions / 130 4.4.2 ATM’s Leaky Bucket / 131 4.4.3 IP’s Token Bucket / 133 4.4.4 Traffic Policing / 134 4.4.5 Traffic Shaping / 135 4.5 Packet Scheduling / 136 4.5.1 Max-Min Scheduling / 136 4.5.2 Round-Robin Service / 138 4.5.3 Weighted Round-Robin Service / 139 4.5.4 Deficit Round-Robin Service / 140 4.5.5 Generalized Processor Sharing (GPS) / 141 4.5.6 Weighted Fair Queuing (WFQ) / 146 4.5.7 Virtual Clock / 150 4.5.8 Self-Clocked Fair Queuing / 153 4.5.9 Worst-Case Fair Weighted Fair Queuing (WF2Q) / 155 4.5.10 WF2Q+ / 158 4.5.11 Comparison / 159 4.5.12 Priorities Sorting Using a Sequencer / 160
viii CONTENTS 4.6 Buffer Management 163 4.6.1 Tail Drop 163 4.6.2 Drop on Full 164 4.6.3 Random Early Detection(RED)/164 4.6.4 Differential Dropping:RIO 167 4.6.5 Fair Random Early Detection(FRED)/168 4.6.6 Stabilized Random Early Detection(SRED)/170 4.6.7 Longest Queue Drop (LQD)/172 5 BASICS OF PACKET SWITCHING 176 5.1 Fundamental Switching Concept 177 5.2 Switch Fabric Classification /181 5.2.1 Time-Division Switching 181 5.2.2 Space-Division Switching 183 5.3 Buffering Strategy in Switching Fabrics /187 5.3.1 Shared-Memory Queuing 188 5.3.2 Output Queuing(OQ)/188 5.3.3 Input Queuing 189 5.3.4 Virtual Output Queuing (VOQ)/189 5.3.5 Combined Input and Output Queuing /190 5.3.6 Crosspoint Queuing 191 5.4 Multiplane Switching and Multistage Switching /191 5.5 Performance of Basic Switches /195 5.5.1 Traffic Model 196 5.5.2 Input-Buffered Switches /197 5.5.3 Output-Buffered Switches 199 5.5.4 Completely Shared-Buffered Switches /201 6 SHARED-MEMORY SWITCHES 207 6.1 Linked List Approach 208 6.2 Content Addressable Memory Approach /213 6.3 Space-Time-Space Approach 215 6.4 Scaling the Shared-Memory Switches /217 6.4.1 Washington University Gigabit Switch /217 6.4.2 Concentrator-Based Growable Switch Architecture /218 6.4.3 Parallel Shared-Memory Switches 218 6.5 Multicast Shared-Memory Switches 220 6.5.1 Shared-Memory Switch with a Multicast Logical Queue 220 6.5.2 Shared-Memory Switch with Cell Copy /220 6.5.3 Shared-Memory Switch with Address Copy 222
Book1099 — “ftoc” — 2007/2/16 — 21:26 — page viii — #4 viii CONTENTS 4.6 Buffer Management / 163 4.6.1 Tail Drop / 163 4.6.2 Drop on Full / 164 4.6.3 Random Early Detection (RED) / 164 4.6.4 Differential Dropping: RIO / 167 4.6.5 Fair Random Early Detection (FRED) / 168 4.6.6 Stabilized Random Early Detection (SRED) / 170 4.6.7 Longest Queue Drop (LQD) / 172 5 BASICS OF PACKET SWITCHING 176 5.1 Fundamental Switching Concept / 177 5.2 Switch Fabric Classification / 181 5.2.1 Time-Division Switching / 181 5.2.2 Space-Division Switching / 183 5.3 Buffering Strategy in Switching Fabrics / 187 5.3.1 Shared-Memory Queuing / 188 5.3.2 Output Queuing (OQ) / 188 5.3.3 Input Queuing / 189 5.3.4 Virtual Output Queuing (VOQ) / 189 5.3.5 Combined Input and Output Queuing / 190 5.3.6 Crosspoint Queuing / 191 5.4 Multiplane Switching and Multistage Switching / 191 5.5 Performance of Basic Switches / 195 5.5.1 Traffic Model / 196 5.5.2 Input-Buffered Switches / 197 5.5.3 Output-Buffered Switches / 199 5.5.4 Completely Shared-Buffered Switches / 201 6 SHARED-MEMORY SWITCHES 207 6.1 Linked List Approach / 208 6.2 Content Addressable Memory Approach / 213 6.3 Space-Time-Space Approach / 215 6.4 Scaling the Shared-Memory Switches / 217 6.4.1 Washington University Gigabit Switch / 217 6.4.2 Concentrator-Based Growable Switch Architecture / 218 6.4.3 Parallel Shared-Memory Switches / 218 6.5 Multicast Shared-Memory Switches / 220 6.5.1 Shared-Memory Switch with a Multicast Logical Queue / 220 6.5.2 Shared-Memory Switch with Cell Copy / 220 6.5.3 Shared-Memory Switch with Address Copy / 222