Very interesting paper undercut about concepts of modern network hardware architecture and computation complexity of packet processing applications.

A Network Processor Architecture with Application-Optimized Reconfigurable Processing Paths (FlexPath NP)

Table of Contents:

Table of Contents ………………………………………………………………………………………… 9
Summary of the Thesis ……………………………………………………………………………….. 13
Zusammenfassung der Arbeit ……………………………………………………………………… 14

Introduction ……………………………………………………………………………………….. 15
State of the Art …………………………………………………………………………………… 23
2.1. Network Processors……………………………………………………………………… 25
2.1.1. Commercial Network Processor Architectures …………………………… 25
2.1.2. Academic Network Processor Projects …………………………………….. 29
2.1.3. Conclusions …………………………………………………………………………. 33
2.2. Networking Applications ……………………………………………………………….. 37
2.2.1. IP Forwarding ……………………………………………………………………….. 37
2.2.2. QoS Mechanisms ………………………………………………………………….. 37
2.2.3. Security Applications……………………………………………………………… 38
2.2.4. Multimedia Applications …………………………………………………………. 40
2.2.5. Mobile Networks …………………………………………………………………… 42
2.2.6. Carrier-grade Ethernet and Internet Backbone Evolution …………….. 45
2.2.7. Conclusions …………………………………………………………………………. 46
2.3. Packet Classification …………………………………………………………………….. 49
2.3.1. Single-Field Classification ………………………………………………………. 49
2.3.2. Multi-Field Classification ………………………………………………………… 56
2.3.3. Packet Classification and Logic Minimization…………………………….. 69
2.3.4. Conclusions …………………………………………………………………………. 70
2.4. Multi-Processor Load Balancing …………………………………………………….. 73
2.4.1. Hashing-based Load Balancing Schemes …………………………………. 73
2.4.2. Hash-based Load Balancing with Overload Spraying …………………. 74
2.4.3. Adaptive HRW Hashing (AHH) …………………………………………………. 75
2.4.4. Adaptive Burst Shifting (ABS) ………………………………………………….. 75
2.4.5. Hashing Adapted by Burst Shifting (HABS) ……………………………….. 76
2.4.6. Conclusions …………………………………………………………………………. 77
FlexPath NP Architecture……………………………………………………………………… 79
3.1. Motivation and Problem Formulation ………………………………………………. 79
3.2. FlexPath NP Concept …………………………………………………………………… 83
3.3. Concept Evaluation ………………………………………………………………………. 89
3.3.1. Analytical Evaluation of AutoRoute in FlexPath NP …………………….. 89
3.3.2. Simulative Evaluation of Hardware-Offload in FlexPath NP ………….. 93
3.4. Conclusions ………………………………………………………………………………. 105
Concept and Implementation of Path Dispatcher …………………………………… 107
4.1. Introduction and Problem Formulation …………………………………………… 107
10
4.2. The Heterogeneous Decision Graph Algorithm (HDGA) …………………….. 113
4.2.1. Formulation of Rule Base using Boolean Variables ……………………. 114
4.2.2. Matrix Representation of Rule Base and Pre-Processing …………… 116
4.2.3. Construction of a Binary Decision Tree ……………………………………. 117
4.2.4. Transforming the Tree into the HDGA Decision Graph……………….. 125
4.2.5. Updates of the Rule Base and HDGA Data Structures ………………. 127
4.3. HDGA Performance and Scalability ……………………………………………….. 129
4.4. Implementation Issues …………………………………………………………………. 133
4.4.1. Path Dispatcher Interfaces …………………………………………………….. 133
4.4.2. Design Space Exploration for HDGA Implementation ………………… 135
4.4.3. FPGA Implementation Results ……………………………………………….. 145
4.5. Conclusions ……………………………………………………………………………….. 147
Multi-Processor Load Balancing in FlexPath NP …………………………………….. 149
5.1. Introduction ……………………………………………………………………………….. 149
5.2. Load Balancing Strategies for Different Application Classes ……………… 151
5.2.1. Stateless Network Processing Applications ……………………………… 151
5.2.2. Stateful Network Processing Applications ……………………………….. 153
5.2.3. Combination of Stateless and Stateful Networking Applications …. 158
5.3. Functional Simulation of Load Balancing Techniques ………………………. 159
5.3.1. Simulation Model …………………………………………………………………. 159
5.3.2. Individual Performance of Load Balancing Techniques ……………… 162
5.3.3. Performance of S&H Load Balancing ……………………………………… 167
5.4. Conclusions ……………………………………………………………………………….. 173
FlexPath NP Demonstrator ………………………………………………………………….. 175
6.1. Demonstrator Goals and Platform …………………………………………………. 175
6.2. FlexPath NP System Overview ……………………………………………………… 179
6.3. Measurement Setup ……………………………………………………………………. 185
6.4. Processor-centric Reference Measurements …………………………………… 187
6.5. Hardware-offload Aspects of FlexPath NP ……………………………………… 189
6.5.1. Forwarding Performance Using Pre-Processor …………………………. 189
6.5.2. Forwarding Performance Using Pre- and Post-Processors ………… 192
6.5.3. Forwarding Performance Using AutoRoute………………………………. 194
6.5.4. Packet Latencies …………………………………………………………………. 196
6.5.5. Packet Loss ………………………………………………………………………… 199
6.6. Load Balancing Algorithms on FlexPath NP ……………………………………. 201
6.6.1. QoS-aware AutoRoute ………………………………………………………….. 202
6.6.2. QoS-aware Packet Spraying ………………………………………………….. 204
6.6.3. Spraying and HLU (S&H) ……………………………………………………….. 206
6.7. Conclusions ……………………………………………………………………………….. 209
Conclusion ……………………………………………………………………………………….. 211
7.1. Contributions of this Thesis ………………………………………………………….. 211
11
7.2. Outlook to Further Work ……………………………………………………………… 215
Appendix ………………………………………………………………………………………………… 219
Implementation Details of selected FlexPath NP-specific Functional Modules.. 221
Pre-Processor …………………………………………………………………………………… 221
Context Assembler ……………………………………………………………………………. 223
Path Dispatcher ………………………………………………………………………………… 225
SmartMem ……………………………………………………………………………………….. 230
Context Generation Engine …………………………………………………………………. 232
Traffic Manager …………………………………………………………………………………. 235
References ………………………………………………………………………………………….. 237
List of Figures ………………………………………………………………………………………. 249
List of Tables ……………………………………………………………………………………….. 252
Code Listings ………………………………………………………………………………………. 253
Abbreviations ………………………………………………………………………………………. 255
List of Prior-Printed Publications …………………………………………………………….. 261

Original

Comments

2015-08-20