Method and apparatus for parallel and conditional data manipulation in a software-defined network processing engine

Patent metadata

Field	Value
Publication number	US-9880844-B2
Application number	US-201314144260-A
Country	US
Kind code	B2
Filing date	Dec 30, 2013
Priority date	Dec 30, 2013
Publication date	Jan 30, 2018
Grant date	Jan 30, 2018

Abstract

Embodiments of the present invention relate to fast and conditional data modification and generation in a software-defined network (SDN) processing engine. Modification of multiple inputs and generation of multiple outputs can be performed in parallel. A size of each input or output data can be large, such as in hundreds of bytes. The processing engine includes a control path and a data path. The control path generates instructions for modifying inputs and generating new outputs. The data path executes all instructions produced by the control path. The processing engine is typically programmable such that conditions and rules for data modification and generation can be reconfigured depending on network features and protocols supported by the processing engine. The SDN processing engine allows for processing multiple large-size data flows and is efficient in manipulating such data. The SDN processing engine achieves full throughput with multiple back-to-back input and output data flows.

First claim

We claim:

1. A software-defined network (SDN) processing engine comprising:
a non-transitory computer readable memory;
a control path including a Word Comparing Cone for comparing words of N inputs for conditional selection of programmable instructions stored on the memory, wherein the Word Comparing Cone includes K configurable multiplexer/comparator (MUX/CMP) Logic Cells that are each for comparing two W-byte words from the N inputs to each other; and
a data path for executing the instructions selected by the control path,
wherein the processing engine is configured to receive the N inputs and generate M outputs in parallel, wherein the N inputs are received from outside the SDN processing engine.

2. The software-defined network (SDN) processing engine of claim 1 , wherein content of each of the M outputs is one of input content that is modified or newly generated content.

3. The software-defined network (SDN) processing engine of claim 1 , wherein the control path includes:
a Control Bits Extractor for extracting control bits from the N inputs;
a multi-stage multiplexer/lookup table (MUX/LUT) Logic Cone for performing expressions and conditions on the control bits and outcome bits of the Word Comparing Cone; and
a plurality of Instruction Tables containing instructions for data manipulation.

4. The software-defined network (SDN) processing engine of claim 3 , wherein at least one of the Control Bits Extractor, the Word Comparing Cone, the multi-stage MUX/LUT Logic Cone and the plurality of Instructions Tables is reconfigurable and programmable based on network features and protocols.

5. The software-defined network (SDN) processing engine of claim 3 , wherein the Control Bits Extractor extracts the control bits from the N inputs based on predefined formats of inputs.

6. The software-defined network (SDN) processing engine of claim 1 , wherein only specific bits in the W bytes of each of the W-byte words are compared.

7. The software-defined network (SDN) processing engine of claim 1 , wherein each of the MUX/CMP Logic Cells is for comparing one W-byte word from one of the inputs with a constant value.

8. The software-defined network (SDN) processing engine of claim 1 , wherein each of the MUX/CMP Logic Cells supports at least three operations, wherein the three operations are equal to (==), greater than (>) and less than (<).

9. The software-defined network (SDN) processing engine of claim 3 , wherein the MUX/LUT Logic Cone includes S stages, wherein
a first stage of the S stages has input bits that includes the control bits of the N inputs to the processing engine and the outcome bits of the Word Comparing Cone,
all output bits of stage i are input bits for stage i+1, and
output bits of a last stage of the S stages form indexes for reading the plurality of Instruction Tables.

10. The software-defined network (SDN) processing engine of claim 9 , wherein the stage i includes P i configurable MUX/LUT Cells.

11. The software-defined network (SDN) processing engine of claim 10 , wherein each of the MUX/LUT Cells includes L multiplexers for selecting L arbitrary bits from input bits to that MUX/LUT Cell.

12. The software-defined network (SDN) processing engine of claim 11 , wherein the L selected bits are configured as a pointer for a lookup table cfg_LUT having 2 L bits, and wherein output of the cfg_LUT is 1-bit.

13. The software-defined network (SDN) processing engine of claim 12 , wherein the cfg_LUT is built from flops.

14. The software-defined network (SDN) processing engine of claim 3 , wherein a synthesis tool is to be used to map logic expressions and conditions to the MUX/LUT Logic Cone.

15. The software-defined network (SDN) processing engine of claim 3 , wherein the plurality of Instruction Tables include T programmable instruction tables, and wherein outputs of the MUX/LUT Logic Cone form indexes which are read addresses for the T programmable instruction tables, and wherein T is at least equal to the M outputs of the processing engine such that each of the M outputs is associated with at least one of the T programmable instruction tables.

16. The software-defined network (SDN) processing engine of claim 15 , wherein Table i of the T programmable instructions tables has A i -bit address, wherein the Table i has up to 2 Ai entries.

17. The software-defined network (SDN) processing engine of claim 16 , wherein each entry of Table i contains Q i , instructions.

18. The software-defined network (SDN) processing engine of claim 15 , wherein each of the T programmable instruction tables is built from SRAM or from arrays of flops.

19. The software-defined network (SDN) processing engine of claim 1 , wherein the processing engine supports at least two kinds of instructions including Copy instructions and ALU instructions.

20. The software-defined network (SDN) processing engine of claim 19 , wherein the Copy instruction copies up to C bytes from an input to an output.

21. The software-defined network (SDN) processing engine of claim 19 , wherein the Copy instruction copies a constant value to an output.

22. The software-defined network (SDN) processing engine of claim 19 , wherein the ALU instruction copies a result of an ALU operation of 2 W-byte words from inputs to an output.

23. The software-defined network (SDN) processing engine of claim 22 , wherein an input to the ALU operation is a constant value.

24. The software-defined network (SDN) processing engine of claim 23 , wherein the ALU operation is one of addition (+), subtraction (−), bitwise AND (&), bitwise OR (|), bitwise XOR (^), bitwise shift left (<<), and bitwise shift right (>>).

25. The software-defined network (SDN) processing engine of claim 19 , wherein each of the Copy or ALU instructions supports bit or byte manipulation by using bitmask fields in that instruction.

26. The software-defined network (SDN) processing engine of claim 1 , wherein the data path includes:
a Delay Matching Queue for matching a latency of the data path to a latency of the control path such that data are processed at correct times; and
an Instructions Execution block for executing all instructions produced by the control path for modifying specific inputs or generating new outputs.

27. The software-defined network (SDN) processing engine of claim 26 , wherein the Delay Matching Queue is one of a FIFO and a shift register with depth that is equal to the latency of the control path such that the processing engine achieves full throughput with back-to-back data processing.

28. The software-defined network (SDN) processing engine of claim 26 , wherein the Instructions Execution block includes hardware modules for executing, in parallel, all instructions produced by the control path, wherein each of the hardware modules executes one of the instructions.

29. The software-defined network (SDN) processing engine of claim 26 , wherein an output is a modification of a specific input when initial content of the output is the content of the specific input before all instructions are executed, and wherein the output is newly generated when the initial content of the output is all zeros before all instructions are executed.

30. A method of parallel and conditional data manipulation in a software-defined network (SDN) processing engine, the method comprising:
receiving N inp

Assignees

• Cavium Inc

Inventors

• Tran Anh T
• Schmidt Gerald
• Daniel Tsahi
• Balan Mohan

Classifications

• H04L69/12

  Protocol engines · CPC title

• H04L65/1013

  Network architectures, gateways, control or user entities · CPC title

• G06F9/3804

  for branches, e.g. hedging, branch folding · CPC title

• G06F9/30145 Primary

  Instruction analysis, e.g. decoding, instruction word fields · CPC title

• G06F15/76

  Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16) · CPC title