Very interesting paper 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

  1. Introduction ……………………………………………………………………………………….. 15
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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