Packet Forwarding Technologies

Contents......Page 5
Organization of the Book......Page 13
Acknowledgments......Page 15
About the Author......Page 16
1.1 Introduction......Page 17
1.3.1 Route Processing......Page 18
1.3.2 Packet Forwarding......Page 20
1.3.3 Router Special Services......Page 21
1.4.1 First Generation—Bus-Based Router Architectures with Single Processor......Page 23
1.4.2.1 Architectures with Route Caching......Page 24
1.4.2.2 Architectures with Multiple Parallel Forwarding Engines......Page 25
1.4.3 Third Generation—Switch Fabric-Based Router Architecture......Page 27
1.4.4 Fourth Generation—Scaling Router Architecture Using Optics......Page 28
1.5.1.2 Framer......Page 30
1.5.1.4 Traffic Manager......Page 31
1.5.2 Network Processor (NP)......Page 32
1.5.3.1 Shared Medium Switch......Page 35
1.5.3.2 Shared Memory Switch Fabric......Page 36
1.5.3.3 Distributed Output Buffered Switch Fabric......Page 37
1.5.3.4 Crossbar Switch......Page 38
1.5.3.5 Space-Time Division Switch......Page 41
References......Page 43
2.1 IP Address, Prefix, and Routing Table......Page 46
2.2 Concept of IP-Address Lookup......Page 47
2.3 Matching Techniques......Page 48
2.3.1 Design Criteria and Performance Requirement......Page 49
2.4.2 Internet Addressing Architecture......Page 51
2.5 Routing Table Characteristics......Page 54
2.5.1 Routing Table Structure......Page 55
2.5.2 Routing Table Growth......Page 56
2.5.3 Impact of Address Allocation on Routing Table......Page 58
2.5.3.1 Migration of Address Allocation Policy......Page 59
2.5.3.2 Impact of Address Allocations on Routing Table Size......Page 60
2.5.4 Contributions to Routing Table Growth......Page 61
2.5.4.2 Failure to Aggregate......Page 63
2.5.4.3 Load Balancing......Page 64
2.5.5 Route Update......Page 65
2.6.1.1 Three Filtering Rules......Page 67
2.6.1.2 Performance Evaluation......Page 69
2.6.2 Minimization of Routing Table with Address Reassignments......Page 70
2.6.2.1 Case of a Single IP Routing Table......Page 71
2.6.2.2 General Case......Page 74
2.6.3.1 Description of the Algorithm......Page 78
2.6.3.2 Improvements......Page 81
2.6.3.3 Experiments and Results......Page 82
References......Page 83
3.2 Caching......Page 84
3.2.1.1 Cache Modeling......Page 85
3.2.1.2 Trace Generation......Page 86
3.2.1.3 Measurement Results......Page 87
3.2.1.4 Caching Cost Analysis......Page 94
3.2.2.1 Locality: Concepts......Page 95
3.2.2.2 Cache Replacement Algorithms......Page 96
3.2.2.3 Stack Reference Frequency......Page 98
3.2.2.4 Analysis of Noninteractive Traffic......Page 101
3.2.2.5 Cache Design Issues......Page 102
3.3 Binary Trie......Page 104
3.4 Path-Compressed Trie......Page 106
3.5 Dynamic Prefix Trie......Page 107
3.5.1 Definition and Data Structure......Page 108
3.5.2 Properties of DP-Tries......Page 110
3.5.3.1 Insertion......Page 112
3.5.3.2 Deletion......Page 117
3.5.3.3 Search......Page 119
References......Page 120
4.1.1 Level Compression......Page 122
4.1.2 Representation of LC-Tries......Page 124
4.1.3 Building LC-Tries......Page 126
4.1.4 Experiments......Page 127
4.2 Controlled Prefix Expansion......Page 128
4.2.1 Prefix Expansion......Page 129
4.2.2 Constructing Multibit Tries......Page 130
4.2.3 Efficient Fixed-Stride Tries......Page 131
4.2.4 Variable-Stride Tries......Page 133
4.3 Lulea Algorithms......Page 138
4.3.1 Level 1 of the Data Structure......Page 139
4.3.2 Levels 2 and 3 of the Data Structure......Page 142
4.4 Elevator Algorithm......Page 143
4.4.1 Elevator-Stairs Algorithm......Page 144
4.4.2 logW-Elevators Algorithm......Page 147
4.4.3 Experiments......Page 151
4.5.1 Construction of Block Trees......Page 153
4.5.2 Lookup......Page 155
4.5.3 Updates......Page 157
4.5.4 Stockpiling......Page 158
4.5.5 Worst-Case Performance......Page 160
4.5.6 Experiments......Page 163
4.6.1 Stanford Hardware Trie......Page 164
4.6.2 Tree Bitmap......Page 165
4.6.3 Tree Bitmap Optimizations......Page 169
4.6.4 Hardware Reference Design......Page 172
References......Page 177
5.1.1 Pipelined Lookups Using Tries......Page 179
5.1.2 Forwarding Engine Model and Assumption......Page 181
5.1.3 Routing Table and Route Update Characteristics......Page 183
5.1.4 Constructing Pipelined Fixed-Stride Tries......Page 184
5.1.5.1 Separating Out Updates to Short Routes......Page 191
5.1.5.2 Node Pullups......Page 192
5.1.5.3 Eliminating Excess Writes......Page 194
5.1.5.4 Caching Deleted SubTrees......Page 195
5.1.6 Summary and Discussion......Page 198
5.2 Two-Phase Algorithm......Page 199
5.2.2 Computing MMS(W – 1, k)......Page 200
5.2.3 Computing T(W – 1, k)......Page 204
Accelerating Algorithm PFST......Page 205
5.2.4 A Faster Two-Phase Algorithm for k = 2, 3......Page 206
5.2.5 A Partitioning Scheme......Page 208
5.2.6 Experimental Results......Page 209
5.3 Pipelined Variable-Stride Multibit Tries......Page 212
5.3.1 Construction of Optimal PVST......Page 213
5.3.2 Mapping onto a Pipeline Architecture......Page 214
5.3.3 Experimental Results......Page 216
References......Page 218
6.1.1 Table-Driven Models......Page 219
6.1.2 Dynamic Programming Algorithm......Page 221
6.1.3 Lagrange Approximation Algorithm......Page 223
6.2.1 Definition......Page 225
6.2.2 Algorithm MINDPQ......Page 227
6.2.3 Depth-Constrained Weight Balanced Tree......Page 230
6.3 Dynamic Biased Skip List......Page 231
6.3.1 Regular Skip List......Page 232
6.3.2.1 Data Structure......Page 233
6.3.2.2 Search Algorithm......Page 234
6.3.3.1 Constructing Data Structure......Page 235
6.3.3.2 Dynamic Self-Adjustment......Page 236
6.3.3.3 Lazy Updating Scheme......Page 237
6.3.3.4 Experimental Results......Page 238
6.4.1 Prefix and Range......Page 239
6.4.2 Collection of Red-Black Trees (CRBT)......Page 240
6.4.3 Biased Skip Lists with Prefix Trees (BSLPT)......Page 241
6.4.4 Collection of Splay Trees......Page 243
6.4.5 Experiments......Page 244
References......Page 248
7.1.1.1 HAC Architecture......Page 250
7.1.1.2 Network Address Routing Table......Page 253
7.1.1.3 Simulations......Page 255
7.1.2 Host Address Range Cache......Page 256
7.1.3.1 Index Bit Selection......Page 257
7.1.3.2 Comparisons between IHARC and HARC......Page 259
7.2 Prefix Caching Schemes......Page 261
7.2.1.1 Prefix Cache......Page 262
7.2.1.2 Prefix Memory......Page 263
7.2.1.3 Experiments......Page 264
7.2.2.2 Handling Parent Prefixes......Page 265
7.2.2.3 Updating RRC......Page 266
7.2.2.4 Performance Evaluation......Page 268
7.3.1 Two-Zone Full Address Cache......Page 269
7.3.2.1 Architecture of MPC......Page 270
7.3.2.3 Outstanding Miss Buffer......Page 271
7.3.2.4 Lookup Table Transformation......Page 273
7.3.3 Design Method of Multi-Zone Cache......Page 274
7.3.3.1 Design Model......Page 275
7.3.3.2 Two-Zone Design......Page 277
7.3.3.3 Optimization Tableau......Page 278
7.4 Cache-Oriented Multistage Structure......Page 279
7.4.2 COMS Operations......Page 280
7.4.3 Cache Management......Page 282
7.4.4 Details of SEs......Page 283
7.4.5 Routing Table Partitioning......Page 284
References......Page 285
8.1.1 Linear Search of Hash Tables......Page 287
8.1.2 Binary Search of Hash Tables......Page 288
8.1.3 Precomputation to Avoid Backtracking......Page 289
8.1.4.1 Asymmetric Binary Search......Page 290
8.1.4.2 Mutating Binary Search......Page 293
8.1.5 Performance Evaluation......Page 298
8.2.1 Parallel Architecture......Page 299
8.2.2 Simulation......Page 300
8.3.1 Multiple Hash Function......Page 302
8.3.2 Multiple Hashing Using Cyclic Redundancy Code......Page 304
8.3.3 Data Structure......Page 306
8.3.5 Update and Expansion to IPv6......Page 307
8.4.1 Standard Bloom Filter......Page 309
8.4.3 Basic Configuration of LPM Using Bloom Filter......Page 311
8.4.4 Optimization......Page 313
8.4.4.1 Asymmetric Bloom Filters......Page 314
8.4.4.2 Direct Lookup Array......Page 316
8.4.4.3 Reducing the Number of Filters......Page 317
8.4.5.1 Basic Fast Hash Table......Page 319
8.4.5.2 Pruned Fast Hash Table......Page 321
8.4.5.3 Shared-Node Fast Hash Table......Page 324
References......Page 326
Main Memory Array......Page 328
Control Logic......Page 329
9.1.2 Binary versus Ternary CAMs......Page 330
Slow Update Operation......Page 331
9.2.1 Algorithm for the Prefix-Length-Ordering Constraint......Page 332
9.2.3 Level-Partitioning Technology......Page 333
9.3.1 VLMP Forwarding Engine Architecture......Page 336
9.3.3 Performance of VLMP Architecture......Page 338
9.4 Power-Efficient TCAM......Page 339
9.4.1.1 Pruned Search......Page 340
9.4.1.2 Paged TCAM......Page 341
9.4.2.1 Bit-Selection Architecture......Page 342
9.4.2.2 Trie-Based Table Partitioning......Page 345
9.4.2.3 Experiments......Page 351
9.4.2.4 Route Updating......Page 352
9.4.3.1 Mask Extension......Page 354
9.4.3.2 Prefix Aggregation and Expansion......Page 357
9.4.3.3 EaseCAM: A Two-Level Paged-TCAM Architecture......Page 358
9.4.4.1 Static Architecture......Page 361
9.4.4.2 Dynamic Architecture......Page 363
9.4.4.3 Discussions......Page 366
9.5.1 Analysis of Routing Tables......Page 367
9.5.3 LBBTC Algorithm......Page 369
9.5.3.1 Mathematical Model......Page 370
9.5.3.2 Adjusting Algorithm......Page 372
9.5.4 Analysis of the Power Efficiency......Page 373
9.5.5.1 Index Logic......Page 375
9.5.5.2 Priority Selector (Adaptive Load Balancing Logic)......Page 376
9.5.6 Performance Analysis......Page 377
Simulation 1......Page 378
Simulation 3......Page 379
References......Page 380
10.1.1 Partitioned Binary Search Table......Page 382
10.1.1.1 Encoding Prefixes as Ranges......Page 383
10.1.1.2 Recomputation......Page 384
10.1.1.3 Insertion into a Modified Binary Search Table......Page 386
10.1.1.4 Multiway Binary Search: Exploiting the Cache Line......Page 387
10.1.1.5 Performance Measurements......Page 389
10.1.2 Multilevel and Interval Partitioning......Page 390
10.1.2.1 Multilevel Partitioning......Page 391
10.1.2.2 Interval Partitioning......Page 394
10.1.2.3 Experimental Results......Page 396
10.2.1.1 Primary Lookup Table Transformation......Page 399
10.2.1.2 Partition Algorithm Based on Next Hops......Page 402
10.2.2.2 Imbalance Distribution of Prefixes......Page 404
10.2.2.3 Concept of Search Unit......Page 405
10.2.2.5 Selector Block......Page 406
10.2.2.6 IFPLUT Updates......Page 408
10.2.2.7 Implementation Using TCAM......Page 409
10.2.2.8 Design Optimization......Page 410
10.2.3 Experimental Results......Page 411
10.3.1 Concept of ROT-Partitioning......Page 412
10.3.2 Generalization of ROT-Partition......Page 413
10.3.3 Complexity Analysis......Page 415
10.3.4.1 Storage Sizes......Page 416
10.3.4.2 Worst-Case Lookup Times......Page 417
10.4 Comb Extraction Scheme......Page 418
10.4.1 Splitting Rule......Page 419
10.4.2 Comparison Set......Page 423
10.4.3 Implementation Using Binary Trie......Page 424
References......Page 425