Compiler and hardware interactions to remove action dependencies in the data plane of a network forwarding element

Patent metadata

Field	Value
Publication number	US-10313495-B1
Application number	US-201715682365-A
Country	US
Kind code	B1
Filing date	Aug 21, 2017
Priority date	Jul 9, 2017
Publication date	Jun 4, 2019
Grant date	Jun 4, 2019

Abstract

A method of configuring a forwarding element that includes several data plane message processing stages. The method stores a set of action codes in an instruction memory in the data plane of the forwarding element. Each action code identifies an operation to perform on a field of a message received at the data plane. The method determines action codes required to process each field of the message in each message processing stage. The method configures a data-plane processing unit of the forwarding element to concurrently perform a group of the action codes in the same data plane processing stage when (i) the action codes are the same and (ii) operate on the same field of the message.

First claim

What is claimed is:

1. A method of configuring a physical forwarding element comprising (i) a data plane comprising a data plane message processing pipeline and (ii) a parser for extracting fields of messages received at the data plane of the physical forwarding element, the data plane message processing pipeline comprising a plurality of data plane message processing stages, the method comprising:
storing a set of action codes in an instruction memory in the data plane of the physical forwarding element, each action code identifying an operation to perform on a field of a message received at the data plane;
determining action codes required to process each field of the message in each message processing stage; and
when a plurality of the action codes (i) are the same and (ii) operate on a same field of the message, configuring a data-plane processing unit of the physical forwarding element to concurrently perform the plurality of the action codes in a same data plane processing stage and during a same clock cycle by utilizing a same data-plane processing unit to perform the plurality of the action codes.

2. The method of claim 1 , wherein the data plane of the physical forwarding element comprises circuitry to perform a logical OR operation on the action codes required to perform an operation on a same field of the message in a same message processing stage.

3. The method of claim 1 , the physical forwarding element comprising a plurality of data plane processing units, the method further comprising configuring each data plane processing unit to operate on a different field of a message at each message stage processing stage.

4. The method of claim 3 , wherein each data-plane processing unit is an arithmetic logic unit (ALU).

5. The method of claim 1 , wherein the physical forwarding element is one of a network router and a network switch.

6. A method of configuring a physical forwarding element comprising (i) a data plane comprising a data plane message processing pipeline and (ii) a parser for extracting fields of messages received at the data plane of the physical forwarding element, the data plane message processing pipeline comprising a plurality of data plane message processing stages, the method comprising:
storing a set of action codes in an instruction memory in the data plane of the physical forwarding element, each action code identifying an operation to perform on a field of a message received at the data plane;
determining action codes required to process each field of the message in each message processing stage;
when a plurality of the action codes (i) are the same and (ii) operate on a same field of the message, configuring a data-plane processing unit of the physical forwarding element to concurrently perform the plurality of the action codes in a same data plane processing stage; and
when the action codes are not the same, configuring the data-plane processing unit of the forwarding element to perform each of a plurality of action codes that operate on a same field of the message in a different processing stage.

7. A method of configuring a physical forwarding element comprising (i) a data plane comprising a data plane message processing pipeline and (ii) a parser for extracting fields of messages received at the data plane of the physical forwarding element, the data plane message processing pipeline comprising a plurality of data plane message processing stages, the method comprising:
receiving a set of instructions from a control plane of the physical forwarding element to identify a set of actions to perform on the fields of messages received at the data plane of the physical forwarding element;
storing a set of action codes in the instruction memory in the data plane of the physical forwarding element, the set of action codes comprising the actions identified in the set of instructions, each action code identifying an operation to perform on a field of a message received at the data plane;
determining action codes required to process each field of the message in each message processing stage; and
when a plurality of the action codes (i) are the same and (ii) operate on a same field of the message, configuring a data-plane processing unit of the physical forwarding element to concurrently perform the plurality of the action codes in a same data plane processing stage.

8. The method of claim 7 , wherein the set of instructions further comprises a set of lookup keys, each lookup key corresponding to an action code, the method further comprising storing the set of lookup keys in a plurality of match tables in the data plane of the physical forwarding element,
wherein determining the action codes required to process each field of the message in each message processing stage comprises comparing each field of the message with a lookup key to determine whether the action corresponding with the lookup key is to be performed on the field.

9. The method of claim 7 , wherein the set of instructions is specified in a data-plane programming language.

10. A non-transitory computer readable medium storing a program for configuring a physical forwarding element comprising (i) a data plane comprising a data plane message processing pipeline and (ii) a parser for extracting fields of messages received at the data plane of the physical forwarding element, the data plane message processing pipeline comprising a plurality of data plane message processing stages, the program executable by a processing unit, the program comprising sets of instructions for:
storing a set of action codes in an instruction memory in the data plane of the forwarding element, each action code identifying an operation to perform on a field of a message received at the data plane;
determining action codes required to process each field of the message in each message processing stage; and
when a plurality of the action codes (i) are the same and (ii) operate on a same field of the message, configuring a data-plane processing unit of the physical forwarding element to concurrently perform the plurality of the action codes in a same data plane processing stage and during a same clock cycle by utilizing a same data-plane processing unit to perform the plurality of action codes.

11. The non-transitory computer readable medium of claim 10 , wherein the data plane of the physical forwarding element comprises circuitry to perform a logical OR operation on the action codes required to perform an operation on a same field of the message in a same message processing stage.

12. The non-transitory computer readable medium of claim 10 , the physical forwarding element comprising a plurality of data plane processing units, the program further comprising a set of instructions for configuring each data plane processing unit to operate on a different field of a message at each message processing stage.

13. The non-transitory computer readable medium of claim 12 , wherein each data-plane processing unit is an arithmetic logic unit (ALU).

14. The non-transitory computer readable medium of claim 10 , wherein the physical forwarding element is one of a network router and a network switch.

15. A non-transitory computer readable medium storing a program for configuring a physical forwarding element comprising (i) a data plane comprising a data plane message processing pipeline and (ii) a parser for extracting fields of messages received at the data plane of the physical forwarding element, the data plane message processing pipeline comprising a plurality of data plane message processing stages, the program executable by a processing unit, the program comprising s

Assignees

• Barefoot Networks Inc

Inventors

• Bosshart Patrick
• Ferrara Michael Gregory
• Attig Michael E
• Peterson Jay Evan Scott

Classifications

• G06F15/17312

  Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion (routing on a LAN H04L45/00) · CPC title

• H04L45/38

  Flow based routing · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• G06F9/30029

  Logical and Boolean instructions, e.g. XOR, NOT · CPC title

• G06F9/3001

  Arithmetic instructions · CPC title