Patent Description:
In data networks, network appliances such as switches, routers, and network interface cards receive packets at input interfaces, process the received packets, and then forward the packets to one or more output interfaces. It is important that such network appliances operate as quickly as possible in order to keep pace with a high rate of incoming packets. One challenge associated with network appliances relates to providing the flexibility to adapt to changes in desired feature sets, networking protocols, operating systems, applications, and hardware configurations. Document <CIT> and article "<NPL>, document <CIT> and <CIT> disclose prior art approaches.

The following presents a summary of one or more aspects of the present disclosure, in order to provide a basic understanding of such aspects.

The present invention may be embodied in other specific forms as long as they do not depart from the scope of the invention as it is depicted by the appended claims. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by this detailed description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.

In the field of data networking, the functionality of network appliances such as switches, routers, and network interface cards (NICs) is often described in terms of functionality that is associated with a "control plane" and functionality that is associated with a "data plane. " In general, the control plane refers to components and/or operations that are involved in managing forwarding information and the data plane refers to components and/or operations that are involved in forwarding packets from an input interface to an output interface according to the forwarding information provided by the control plane. The data plane may also refer to components and/or operations that implement packet processing operations related to encryption, decryption, compression, decompression, firewalling, and telemetry.

Two important aspects of a network appliance's performance are throughput and connection processing. Throughput, relating to packet processing speed, is often measured in bps (bits/sec) or Bps (bytes/sec). Connection processing, relating to the speed with which the network appliance can be configured to process new network traffic flows, is often measured in CPS (connections/sec). Throughput and CPS can be increased when processing is not repeated in different parts of the network appliance, when unnecessary processing is avoided, and when processing is performed by the fastest subsystem that can perform the processing.

Aspects described herein process packets using match-action pipelines, extended packet processing pipelines, and CPU (central processing unit) cores. The match-action pipeline is a part of a data plane that can process network traffic flows extremely quickly, but only after being configured to process those traffic flows. Upon receiving a packet of a network traffic flow, the match-action pipeline can generate an index from data in the packet header. Finding a flow table entry for the network traffic flow at the index location in the flow table is the "match" portion of "match-action". If there is no flow table entry for the network traffic flow, it is a new network traffic flow that the match action pipeline is not yet configured to process.

Entries for terminated and expired traffic flows should be deleted from the flow table to provide room for storing new entries and to speed up table lookups. Finding aged out entries can require locking the memory holding the flow table while checking timeout metadata in every flow table entry. Locking the memory can prevent the match-action pipeline from processing packets. The extended packet processing pipeline can search the flow table more rapidly than the CPU cores can. As such, using the extended packet processing pipeline instead of the CPU cores to identify aged out flow table entries reduces the amount of time that the match-action pipeline is locked out of the memory. Thus, advantages of using the extended packet processing pipeline for searching the flow table include freeing the CPU cores for tasks such as generating configurations for new traffic flows (higher CPS), and less locking of the memory used by the match action pipeline (higher throughput).

<FIG> is a functional block diagram of a network appliance <NUM> having a control plane <NUM> and a data plane <NUM> and in which aspects may be implemented. As illustrated in <FIG>, the control plane provides forwarding information (e.g., in the form of table management information) to the data plane and the data plane receives packets on input interfaces, processes the received packets, and then forwards packets to desired output interfaces. Additionally, control traffic (e.g., in the form of packets) may be communicated from the data plane to the control plane and/or from the control plane to the data plane. The data plane and control plane are sometimes referred to as the "fast" plane and the "slow" plane, respectively. In general, the control plane is responsible for less frequent and less time-sensitive operations such as updating Forwarding Information Bases (FIBs) and Label Forwarding Information Bases (LFIBs), while the data plane is responsible for a high volume of time-sensitive forwarding decisions that need to be made at a rapid pace. In some embodiments, the control plane may implement operations related to packet routing that include Open Shortest Path First (OSPF), Enhanced Interior Gateway Routing Protocol (EIGRP), Border Gateway Protocol (BGP), Intermediate System to Intermediate System (IS-IS), Label Distribution Protocol (LDP), routing tables and/or operations related to packet switching that include Address Resolution Protocol (ARP) and Spanning Tree Protocol (STP). In some embodiments, the data plane (which may also be referred to as the "forwarding" plane) may implement operations related to parsing packet headers, Quality of Service (QoS), filtering, encapsulation, queuing, and policing. Although some functions of the control plane and data plane are described, other functions may be implemented in the control plane and/or the data plane.

Often times, the high-volume and rapid decision-making that occurs at the data plane is implemented in fixed function application specific integrated circuits (ASICs). Although fixed function ASICs enable high-volume and rapid packet processing, fixed function ASICs typically do not provide enough flexibility to adapt to changing needs. Data plane processing can also be implemented in field programmable gate arrays (FPGAs) to provide a high level of flexibility in data plane processing. Although FPGAs are able to provide a high level of flexibility for data plane processing, FPGAs are relatively expensive to produce and consume much more power than ASICs on a per-packet basis.

Some techniques exist for providing flexibility at the data plane of network appliances that are used in data networks. For example, the concept of a domain-specific language for programming protocol-independent packet processors, known simply as "P4," has developed as a way to provide some flexibility at the data plane of a network appliance. The P4 domain-specific language for programming the data plane of network appliances is currently defined in the "P4<NUM> Language Specification," version <NUM>. <NUM>, as published by the P4 Language Consortium on October <NUM>, <NUM>. P4 (also referred to herein as the "P4 specification," the "P4 language," and the "P4 program") is designed to be implementable on a large variety of targets including programmable NICs, software switches, FPGAs, and ASICs. As described in the P4 specification, the primary abstractions provided by the P4 language relate to header types, parsers, tables, actions, match-action units, control flow, extern objects, user-defined metadata, and intrinsic metadata.

The data plane <NUM> includes multiple receive media access controllers (MACs) (RX MAC) <NUM>, an ingress port <NUM>, a packet buffer/traffic manager <NUM>, an egress port <NUM>, and multiple transmit MACs (TX MAC) <NUM>. The data plane elements described may be implemented, for example, as a P4 programmable switch architecture (PSA) or as a P4 programmable NIC, although architectures other than a PSA and a P4 programmable NIC are also possible.

The RX MAC <NUM> implements media access control on incoming packets via, for example, a MAC protocol such as Ethernet. In an embodiment, the MAC protocol is Ethernet and the RX MAC is configured to implement operations related to, for example, receiving frames, half-duplex retransmission and backoff functions, Frame Check Sequence (FCS), interframe gap enforcement, discarding malformed frames, and removing the preamble, Start Frame Delimiter (SFD), and padding from a packet. Likewise, the TX MAC <NUM> implements media access control on outgoing packets via, for example, Ethernet. In an embodiment, the TX MAC is configured to implement operations related to, for example, transmitting frames, half-duplex retransmission and backoff functions, appending an FCS, interframe gap enforcement, and prepending a preamble, an SFD, and padding. The packet buffer/traffic manager <NUM> includes memory and/or logic to implement packet buffering and/or traffic management. In an embodiment, operations implemented via the packet buffer/traffic manager include, for example, packet buffering, packet scheduling, and/or traffic shaping.

The ingress port <NUM> and egress port <NUM> can be packet processing pipelines that operate at the data plane of a network appliance and can be programmable via a domain-specific language such as P4. In an embodiment, the ingress port <NUM> and egress port <NUM> can be programmed to implement various operations at the data plane such as, for example, routing, bridging, tunneling, forwarding, network access control lists (ACLs), Layer <NUM> (L4) firewalls, flow-based rate limiting, VLAN tag policies, group membership, isolation, multicast, group control, label push/pop operations, L4 load-balancing, L4 flow tables for analytics and flow specific processing, distributed denial of service (DDoS) attack detection, DDoS attack mitigation, and telemetry data gathering on any packet field or flow state.

<FIG> illustrates packet headers and payloads of packets <NUM>, <NUM>, <NUM>, <NUM>, <NUM> in a network traffic flow <NUM> that can be processed according to some aspects. A network traffic flow <NUM> can have numerous packets such as a first packet <NUM>, a second packet <NUM>, a third packet <NUM>, a fourth packet <NUM>, and a final packet <NUM> with many more packets between the fourth packet <NUM> and the final packet <NUM>. The term "the packet" or "a packet" can refer to any of the packets in a network traffic flow.

In general, packets can be constructed and interpreted in accordance with the internet protocol suite. The Internet protocol suite is the conceptual model and set of communications protocols used in the Internet and similar computer networks. A packet can be transmitted and received as a raw bit stream over a physical medium at the physical layer, sometimes called layer <NUM>. The packets can be received by a RX MAC <NUM> as a raw bit stream or transmitted by TX MAC <NUM> as a raw bit stream.

The link layer is often called layer <NUM>. The protocols of the link layer operate within the scope of the local network connection to which a host is attached and includes all hosts accessible without traversing a router. The link layer is used to move packets between the interfaces of two different hosts on the same link. The packet has a layer <NUM> header <NUM> and layer <NUM> payload <NUM>. The layer <NUM> header can contain a source MAC address <NUM>, a destination MAC address <NUM>, and other layer <NUM> header data <NUM>. The input ports <NUM> and output ports <NUM> of a network appliance <NUM> can have MAC addresses. In some embodiments a network appliance <NUM> has a MAC address that is applied to all or some of the ports. In some embodiments one or more of the ports each have their own MAC address. In general, each port can send and receive packets. As such, a port of a network appliance can be configured with a RX MAC <NUM> and a TX MAC <NUM>. Ethernet, also known as Institute of Electrical and Electronics Engineers (IEEE) <NUM> is a layer <NUM> protocol. IEEE <NUM> (WiFi) is another widely used layer <NUM> protocol. The layer <NUM> payload <NUM> can include a Layer <NUM> packet.

The internet layer, often called layer <NUM>, is the network layer where layer <NUM> packets can be routed from a first node to a second node across multiple intermediate nodes. The nodes can be network appliances such as network appliance <NUM>. Internet protocol (IP) is a commonly used layer <NUM> protocol. The layer <NUM> packet can have a layer <NUM> header <NUM> and a layer <NUM> payload <NUM>. The layer <NUM> header <NUM> can have a source IP address <NUM>, a destination IP address <NUM>, a protocol indicator <NUM>, and other layer <NUM> header data <NUM>. As an example, a first node can send an IP packet to a second node via an intermediate node. The IP packet therefor has a source IP address indicating the first node and a destination IP address indicating the second node. The first node makes a routing decision that the IP packet should be sent to the intermediate node. The first node therefor sends the IP packet to the intermediate node in a first layer <NUM> packet. The first layer <NUM> packet has a source MAC address <NUM> indicating the first node, a destination MAC address <NUM> indicating the intermediate node, and has the IP packet as a payload. The intermediate node receives the first layer <NUM> packet. Based on the destination IP address, the intermediate node determines that the IP packet is to be sent to the second node. The intermediate node sends the IP packet to the second node in a second layer <NUM> packet having a source MAC address <NUM> indicating the intermediate node, a destination MAC address <NUM> indicating the second node, and the IP packet as a payload. The layer <NUM> payload <NUM> can include headers and payloads for higher layers in accordance with higher layer protocols such as transport layer protocols.

The transport layer, often called layer <NUM>, can establish basic data channels that applications use for task-specific data exchange and can establish host-to-host connectivity. A layer <NUM> protocol can be indicated in the layer <NUM> header <NUM> using protocol indicator <NUM>. Transmission control protocol (TCP), user datagram protocol (UDP), and internet control message protocol (ICMP) are common layer <NUM> protocols. TCP is often referred to as TCP/IP. TCP is connection oriented and can provide reliable, ordered, and error-checked delivery of a stream of bytes between applications running on hosts communicating via an IP network. When carrying TCP data, a layer <NUM> payload <NUM> includes a TCP header and a TCP payload. UDP can provide for computer applications to send messages, in this case referred to as datagrams, to other hosts on an IP network using a connectionless model. When carrying UDP data, a layer <NUM> payload <NUM> includes a UDP header and a UDP payload. ICMP is used by network devices, including routers, to send error messages and operational information indicating success or failure when communicating with another IP address. ICMP uses a connectionless model.

A layer <NUM> packet can have a layer <NUM> header <NUM> and a layer <NUM> payload <NUM>. The layer <NUM> header <NUM> can include a source port <NUM>, destination port <NUM>, layer <NUM> flags <NUM>, and other layer <NUM> header data <NUM>. The source port and the destination port can be integer values used by host computers to deliver packets to application programs configured to listen to and send on those ports. The layer <NUM> flags <NUM> can indicate a status of or action for a network traffic flow. For example, TCP has the RST, FIN, and ACK flags. RST indicates a TCP connection is to be immediately shutdown and all packets discarded. A TCP FIN flag can indicate the final transmission on a TCP connection, packets transmitted before the FIN packet may be processed. ACK acknowledges received packets. A recipient of a FIN packet can ACK a FIN packet before shutting down its side of a TCP connection. A traffic flow can be terminated by a flow termination dialog. Examples of flow termination dialogs include: a TCP RST packet (with or without an ACK); and a TCP FIN packet flowed by a TCP ACK packet responsive to the TCP FIN packet. Other protocols also have well known flow termination dialogs. A layer <NUM> payload <NUM> can contain a layer <NUM> packet.

The application layer, often called layer <NUM>, includes the protocols used by most applications for providing user services or exchanging application data over the network connections established by the lower level protocols. Examples of application layer protocols include the Hypertext Transfer Protocol (HTTP), the File Transfer Protocol (FTP), the Simple Mail Transfer Protocol (SMTP), and the Dynamic Host Configuration Protocol (DHCP). Data coded according to application layer protocols can be encapsulated into transport layer protocol units (such as TCP or UDP messages), which in turn use lower layer protocols to effect actual data transfer.

A layer <NUM> packet may have layer <NUM> header data <NUM> and may have a layer <NUM> payload <NUM>. In practice, many applications do not distinguish between headers and payloads at layer <NUM>. HTTP is a protocol that may be considered to have headers and payloads. The illustrated layer <NUM> headers are for an HTTP GET <NUM> and for a response to an HTTP GET <NUM>. The illustrated payload is that of the response to the HTTP GET.

<FIG> is a depiction of a network appliance <NUM> in which the data plane <NUM> is programmable according to the P4 domain-specific language and in which aspects may be implemented. As illustrated in <FIG>, a P4 program is provided to the data plane via the control plane <NUM>. The P4 program includes software code that configures the functionality of the data plane to implement particular processing and/or forwarding logic and processing and/or forwarding tables are populated and managed via P4 table management information that is provided to the data plane from the control plane. Control traffic (e.g., in the form of packets) may be communicated from the data plane to the control plane and/or from the control plane to the data plane. In the context of P4, the control plane corresponds to a class of algorithms and the corresponding input and output data that are concerned with the provisioning and configuration of the data plane and the data plane corresponds to a class of algorithms that describe transformations on packets by packet processing systems.

The data plane <NUM> includes a programmable packet processing pipeline <NUM> that is programmable using a domain-specific language such as P4 and that can be used to implement the programmable packet processing pipeline <NUM>. As described in the P4 specification, a programmable packet processing pipeline can include an arbiter <NUM>, a parser <NUM>, a match-action pipeline <NUM>, a deparser <NUM>, and a demux/queue <NUM>. The arbiter <NUM> can act as an ingress unit receiving packets from RX-MACs <NUM> and can also receive packets from the control plane via a control plane packet input <NUM>. The arbiter <NUM> can also receive packets that are recirculated to it by the demux/queue <NUM>. The demux/queue <NUM> can act as an egress unit and can also be configured to send packets to a drop port (the packets thereby disappear), to the arbiter via recirculation, and to the control plane <NUM> via an output CPU port. The control plane is often referred to as a CPU (central processing unit) although, in practice, control planes often include multiple CPU cores and other elements. The arbiter <NUM> and the demux/queue <NUM> can be configured through the domain-specific language (e.g., P4).

The parser <NUM> is a programmable element that is configured through the domain-specific language (e.g., P4) to extract information from a packet (e.g., information from the header of the packet). As described in the P4 specification, parsers describe the permitted sequences of headers within received packets, how to identify those header sequences, and the headers and fields to extract from packets. In an embodiment, the information extracted from a packet by the parser is referred to as a packet header vector or "PHV. " In an embodiment, the parser identifies certain fields of the header and extracts the data corresponding to the identified fields to generate the PHV. In an embodiment, the PHV may include other data (often referred to as "metadata") that is related to the packet but not extracted directly from the header, including for example, the port or interface on which the packet arrived at the network appliance. Thus, the PHV may include other packet related data (metadata) such as input/output port number, input/output interface, or other data in addition to information extracted directly from the packet header. The PHV produced by the parser may have any size or length. For example, the PHV may be at least <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, or <NUM> bits. In some cases, a PHV having even more bits (e.g., <NUM> Kb) may include all relevant header fields and metadata corresponding to a received packet. The size or length of a PHV corresponding to a packet may vary as the packet passes through the match-action pipeline.

The deparser <NUM> is a programmable element that is configured through the domain-specific language (e.g., P4) to generate packet headers from PHVs at the output of match-action pipeline <NUM> and to construct outgoing packets by reassembling the header(s) (e.g., Ethernet and IP headers) as determined by the match-action pipeline. In some cases, a packet payload may travel in a separate queue or buffer, such as a first-in-first-out (FIFO) queue, until the packet payload is reassembled with its corresponding PHV at the deparser to form a packet. The deparser may rewrite the original packet according to the PHV fields that have been modified (e.g., added, removed, or updated). In some cases, a packet processed by the parser may be placed in a packet buffer/traffic manager (e.g. <FIG>, element <NUM>) for scheduling and possible replication. In some cases, once a packet is scheduled and leaves the packet buffer/traffic manager, the packet may be parsed again to generate an egress PHV. The egress PHV may be passed through a match-action pipeline after which a final deparser operation may be executed (e.g., at deparser <NUM>) before the demux/queue <NUM> sends the packet to the TX MAC <NUM> or recirculates it back to the arbiter <NUM> for additional processing.

<FIG> is a high-level diagram illustrating an example of generating a packet header vector <NUM> from a packet <NUM> according to some aspects. The parser <NUM> can receive a packet <NUM> that has layer <NUM>, layer <NUM>, layer <NUM>, and layer <NUM> headers and payloads. The parser can generate a packet header vector (PHV) from packet <NUM>. The packet header vector can include many data fields including data from packet headers <NUM> and metadata <NUM>. The metadata <NUM> can include data generated by the network appliance such as the hardware port <NUM> on which the packet <NUM> was received and the packet timestamp <NUM> indicating when the packet <NUM> was received by the network appliance.

The source MAC address <NUM> can be obtained from the layer <NUM> header <NUM>. The destination MAC address <NUM> can be obtained from the layer <NUM> header <NUM>. The source IP address <NUM> can be obtained from the layer <NUM> header <NUM>. The source port <NUM> can be obtained from the layer <NUM> header <NUM>. The protocol <NUM> can be obtained from the layer <NUM> header <NUM>. The destination IP address <NUM> can be obtained from the layer <NUM> header <NUM>. The destination port <NUM> can be obtained from the layer <NUM> header <NUM>. The packet quality of service parameters <NUM> can be obtained from the layer <NUM> header <NUM> or another header based on implementation specific details. The virtual network identifier <NUM> may be obtained from the layer <NUM> header <NUM>. The multi-protocol label switching (MPLS) data <NUM>, such as an MPLS label, may be obtained from the layer <NUM> header <NUM>. The other layer <NUM> data <NUM> can be obtained from the layer <NUM> header <NUM>. The layer <NUM> application details <NUM> can be obtained from the layer <NUM> header <NUM> and layer <NUM> payload <NUM>. The other header information <NUM> is the other information contained in the layer <NUM>, layer <NUM>, layer <NUM>, and layer <NUM> headers.

The packet <NUM>-tuple <NUM> is often used for generating keys for match tables, discussed below. The packet <NUM>-tuple <NUM> can include the source IP address <NUM>, the source port <NUM>, the protocol <NUM>, the destination IP address <NUM>, and the destination port <NUM>.

Those practiced in computer networking protocols realize that the headers carry much more information than that described here, realize that substantially all of the headers are standardized by documents detailing header contents and fields, and know how to obtain those documents. The parser can also be configured to output a packet or payload <NUM>. Recalling that the parser <NUM> is a programmable element that is configured through the domain-specific language (e.g., P4) to extract information from a packet, the specific contents of the packet or payload <NUM> are those contents specified via the domain specific language. For example, the contents of the packet or payload <NUM> can be the layer <NUM> payload.

<FIG> is a functional block diagram illustrating an example of a match-action unit <NUM> in a match-action pipeline <NUM> according to some aspects. <FIG> introduces certain concepts related to match-action units and match-action pipelines and is not intended to be limiting. The match-action units <NUM>, <NUM>, <NUM> of the match-action pipeline <NUM> are programmed to perform "match-action" operations in which a match unit performs a lookup using at least a portion of the PHV and an action unit performs an action based on an output from the match unit. In an embodiment, a PHV generated at the parser is passed through each of the match-action units in the match-action pipeline in series and each match-action unit implements a match- action operation. The PHV and/or table entries may be updated in each stage of match-action processing according to the actions specified by the P4 programming. In some instances, a packet may be recirculated through the match-action pipeline, or a portion thereof, for additional processing. Match-action unit <NUM><NUM> receives PHV <NUM><NUM> as an input and outputs PHV <NUM><NUM>. Match-action unit <NUM><NUM> receives PHV <NUM><NUM> as an input and outputs PHV <NUM><NUM>. Match-action unit <NUM><NUM> receives PHV <NUM><NUM> as an input and outputs PHV <NUM><NUM>.

An expanded view of elements of a match-action unit <NUM> of match-action pipeline <NUM> is shown. The match-action unit includes a match unit <NUM> (also referred to as a "table engine") that operates on an input PHV <NUM> and an action unit <NUM> that produces an output PHV <NUM>, which may be a modified version of the input PHV <NUM>. The match unit <NUM> can include key construction logic <NUM>, a lookup table <NUM>, and selector logic <NUM>. The key construction logic <NUM> is configured to generate a key from at least one field in the PHV. The lookup table <NUM> is populated with key-action pairs, where a key-action pair includes a key (e.g., a lookup key) and corresponding action code <NUM> and/or action data <NUM>. In an embodiment, a P4 lookup table generalizes traditional switch tables, and can be programmed to implement, for example, routing tables, flow lookup tables, ACLs, and other user-defined table types, including complex multivariable tables. The key generation and lookup function constitutes the "match" portion of the operation and produces an action that is provided to the action unit via the selector logic. The action unit executes an action over the input data (which may include data <NUM> from the PHV) and provides an output that forms at least a portion of the output PHV. For example, the action unit executes action code <NUM> on action data <NUM> and data <NUM> to produce an output that is included in the output PHV. If no match is found in the lookup table, then a default action <NUM> may be implemented. A flow miss is example of a default action that may be executed when no match is found. In an embodiment, operations of the match-action unit are programmable in the control plane via P4 and the contents of the lookup table is managed by the control plane.

<FIG> is a high-level diagram of a network interface card (NIC) <NUM> configured as a network appliance according to some aspects. Aspects of the embodiments, including packet processing pipelines, fast data paths, and slow data paths, can be implemented in the NIC <NUM>. The NIC <NUM> can be configured for operation within a host system <NUM>. The host system can be a general-purpose computer with a host interface <NUM> such as a PCIe interface. The NIC <NUM> can have a PCIe interface <NUM> through which it can communicate with the host system <NUM>. The NIC can also include a memory <NUM>, a coherent interconnect <NUM>, a packet processing circuit implementing P4 pipelines <NUM>, a pipeline circuit <NUM> implementing extended packet processing pipelines (also called P4+ pipelines), CPU cores <NUM>, service processing offloads <NUM>, packet buffer <NUM>, and ethernet ports <NUM>.

As discussed above, the P4 pipelines are configured for programming via a P4 domain-specific language for programming the data plane of network appliances that is currently defined in the "P4<NUM> Language Specification," version <NUM>. <NUM>, as published by the P4 Language Consortium on October <NUM>, <NUM>. As such, the P4 pipeline's inputs, outputs, and operations may be constrained such that the P4 pipeline operates in accordance with the P4 language specification. The P4+ pipeline may be similar to a P4 pipeline bit is not constrained as the P4 pipeline is.

The NIC <NUM> can include a memory <NUM> for running Linux or some other operating system, for storing large data structures such as flow tables and other analytics, and for providing buffering resources for advanced features including TCP termination and proxy, deep packet inspection, storage offloads, and connected FPGA functions. The memory system may comprise a high bandwidth module (HBM) module which may support 4GB capacity, 8GB capacity, or some other capacity depending on package and HBM. The HBM may be required for accessing full packets at wire speed. Wire speed refers to the speed at which packets can move through a communications network. For example, each of the ethernet ports can be a <NUM> Gbps port. Wire speed for the network appliance may therefore be operation at <NUM> Gbps for each port. HBMs operating at over <NUM> Tb/s are currently available.

In an embodiment, the CPU cores <NUM> are general purpose processor cores, such as ARM processor cores, Microprocessor without Interlocked Pipeline Stages (MIPS) processor cores, and/or x86 processor cores, as is known in the field. In an embodiment, each CPU core includes a memory interface, an ALU, a register bank, an instruction fetch unit, and an instruction decoder, which are configured to execute instructions independently of the other CPU cores. In an embodiment, the CPU cores are Reduced Instruction Set Computers (RISC) CPU cores that are programmable using a general-purpose programming language such as C.

In an embodiment, each CPU core <NUM> also includes a bus interface, internal memory, and a memory management unit (MMU) and/or memory protection unit. For example, the CPU cores may include internal cache, e.g., L1 cache and/or L2 cache, and/or may have access to nearby L2 and/or L3 cache. In an embodiment, each CPU core includes core-specific L1 cache, including instruction-cache and data-cache and L2 cache that is specific to each CPU core or shared amongst a small number of CPU cores. L3 cache may also be available to the CPU cores.

In an embodiment there are four CPU cores <NUM> available for control plane functions and for implementing aspects of a slow data path that includes software implemented packet processing functions. The CPU cores may be used to implement discrete packet processing operations such as L7 applications (e.g., HTTP load balancing, L7 firewalling, and/or L7 telemetry), flow table insertion or table management events, connection setup/management, multicast group join, deep packet inspection (DPI) (e.g., URL inspection), storage volume management (e.g., NVMe volume setup and/or management), encryption, decryption, compression, and decompression, which may not be readily implementable through a domain-specific language such as P4, in a manner that provides fast path performance as is expected of data plane processing.

The service processing offloads <NUM> are specialized hardware modules purposely optimized to handle specific tasks at wire speed, such as cryptographic functions, compression/decompression, etc..

The packet buffer <NUM> can act as a central on-chip packet switch that delivers packets from the network interfaces <NUM> to packet processing elements of the data plane and vice-versa. The packet processing elements can include a slow data path implemented in software and a fast data path implemented by packet processing circuitry <NUM>. The pipeline circuit <NUM> may operate as a part of the fast data path, may offload processing from the CPUs, and may perform other functions.

The packet processing circuit implementing P4 pipelines <NUM> can be a specialized circuit or part of a specialized circuit using one or more ASICs or FPGAs to implement a programmable packet processing pipeline such as the programmable packet processing pipeline <NUM> of <FIG>. Some embodiments include ASICs or FPGAs implementing a P4 pipeline as a fast data path within the network appliance. The fast data path is called the fast data path because it processes packets faster than a slow data path that can also be implemented within the network appliance. An example of a slow data path is a software implemented data path wherein the CPU cores <NUM> and memory <NUM> are configured via software to implement a slow data path. A network appliance having two data paths has a fast data path and a slow data path when one of the data paths process packets faster than the other data path.

The pipeline circuit <NUM> can be a specialized circuit or part of a specialized circuit using one or more ASICs or FPGAs to implement an extended packet processing pipeline. Some embodiments include ASICs or FPGAs implementing a P4+ pipeline supplementing P4 pipeline in a fast data path within the network appliance.

All memory transactions in the NIC <NUM>, including host memory, on board memory, and registers may be connected via a coherent interconnect <NUM>. In one non-limiting example, the coherent interconnect can be provided by a network on a chip (NOC) "IP core". Semiconductor chip designers may license and use prequalified IP cores within their designs. Prequalified IP cores may be available from third parties for inclusion in chips produced using certain semiconductor fabrication processes. A number of vendors provide NOC IP cores. The NOC may provide cache coherent interconnect between the NOC masters, including the packet processing circuit implementing P4 pipelines <NUM>, pipeline circuit <NUM> implementing extended packet processing pipelines, CPU cores <NUM>, and PCIe interface <NUM>. The interconnect may distribute memory transactions across a plurality of memory interfaces using a programmable hash algorithm. All traffic targeting the memory may be stored in a NOC cache (e.g., <NUM> MB cache). The NOC cache may be kept coherent with the CPU core caches. The NOC cache may be used to aggregate memory write transactions which may be smaller than the cache line (e.g., size of <NUM> bytes) of an HBM.

<FIG> illustrates a block diagram of an exemplary NIC <NUM> in which aspects may be implemented. The NIC <NUM> serves as an example of implementing the P4 and P4+ pipelines and various other functions to provide improved network performance. The NIC <NUM> can include four advanced RISC machine (ARM) processors with coherent LI and L2 caches, a shared local memory system, flash non-volatile memory, DMA engines, and miscellaneous IO devices for operation and debug.

The NIC can have a host interface and a network interface. The host interface can be configured to provide communication link(s) with a host system. The host interface can expose NIC functions to the host system. The network interface can support network connections or uplinks with a computing network that may be, for example, a local area network, a wide area network, or other network.

Memory transactions in the NIC <NUM>, including host memory, high bandwidth memory (HBM), and registers may be connected via a coherent network on a chip (NOC) based on a prequalified IP core from a third party. The NOC may provide cache coherent interconnect between the NOC masters, including P4 pipeline, extended pipeline, DMA, PCIe, and ARM. The interconnect may distribute HBM memory transactions across a plurality (e.g., <NUM>) of HBM interfaces using a programmable hash algorithm. All traffic targeting HBM may be stored in the NOC cache (e.g., <NUM> MB cache). The NOC cache may be kept coherent with the ARM caches. The NOC cache may be used to aggregate HBM write transactions which may be smaller than the cache line (e.g., size of <NUM> bytes), as the HBM is not efficient when processing small writes. The NOC cache may have high bandwidth (e.g. to <NUM> Tb/s operation) as it fronts the HBM which has high bandwidth (e.g. <NUM> Tb/s HBM).

The NIC <NUM> can have an internal HBM memory system for running Linux, storing large data structures such as flow tables and other analytics, and providing buffering resources for advanced features including TCP termination and proxy, deep packet inspection, storage offloads, and connected FPGA functions. The memory system can have an HBM module which may support 4GB capacity or 8GB capacity, depending on package and HBM.

As mentioned above, the system may comprise a PCIe host interface. The PCIe host interface may support a bandwidth of, for example, <NUM> Gb/s per PCIe connection (e.g., dual PCIe Gen4x8 or single PCIe Gen3xl6).

<FIG> illustrates a block diagram of a match processing unit (MPU) <NUM> that may be used within the exemplary system of <FIG> to implement some aspects. The MPU <NUM> can have multiple functional units, memories, and a register file. For example, the MPU <NUM> may have an instruction fetch unit <NUM>, a register file unit <NUM>, a communication interface <NUM>, arithmetic logic units (ALUs) <NUM> and various other functional units.

In the illustrated example, the MPU <NUM> can have a write port or communication interface <NUM> allowing for memory read/write operations. For instance, the communication interface <NUM> may support packets written to or read from an external memory (e.g., high bandwidth memory (HBM) of a host device) or an internal static random-access memory (SRAM). The communication interface <NUM> may employ any suitable protocol such as Advanced Microcontroller Bus Architecture (AMBA) Advanced extensible Interface (AXI) protocol. AXI is a high-speed/high-end on-chip bus protocol and has channels associated with read, write, address, and write response, which are respectively separated, individually operated, and have transaction properties such as multiple-outstanding address or write data interleaving. The AXI interface <NUM> may include features that support unaligned data transfers using byte strobes, burst based transactions with only start address issued, separate address/control and data phases, issuing of multiple outstanding addresses with out of order responses, and easy addition of register stages to provide timing closure. For example, when the MPU executes a table write instruction, the MPU may track which bytes have been written to (a. dirty bytes) and which remain unchanged. When the table entry is flushed back to the memory, the dirty byte vector may be provided to AXI as a write strobe, allowing multiple writes to safely update a single table data structure as long they do not write to the same byte. In some cases, dirty bytes in the table need not be contiguous and the MPU may only write back a table if at least one bit in the dirty vector is set. Though packet data is transferred according the AXI protocol in the packet data communication on-chip interconnect system according to the present exemplary embodiment in the present specification, it can also be applied to a packet data communication on-chip interconnect system operating by other protocols supporting a lock operation, such as Advanced High-performance Bus (AHB) protocol or Advanced Peripheral Bus (APB) protocol in addition to the AXI protocol.

The MPU <NUM> can have an instruction fetch unit <NUM> configured to fetch instructions from a memory external to the MPU based on the input table result or at least a portion of the table result. The instruction fetch unit may support branches and/or linear code paths based on table results or a portion of a table result provided by a table engine. In some cases, the table result may comprise table data, key data and/or a start address of a set of instructions/program. Details about the table engine are described later herein. In some embodiments, the instruction fetch unit <NUM> can have an instruction cache <NUM> for storing one or more programs. In some cases, the one or more programs may be loaded into the instruction cache <NUM> upon receiving the start address of the program provided by the table engine. In some cases, a set of instructions or a program may be stored in a contiguous region of a memory unit, and the contiguous region can be identified by the address. In some cases, the one or more programs may be fetched and loaded from an external memory via the communication interface <NUM>. This provides flexibility to allow for executing different programs associated with different types of data using the same processing unit. In an example, a management packet header vector (PHV) can be injected into the pipeline, for example to perform administrative table direct memory access (DMA) operations or entry aging functions (i.e., adding timestamps), one of the management MPU programs may be loaded to the instruction cache to execute the management function. The instruction cache <NUM> can be implemented using various types of memories such as one or more SRAMs.

The one or more programs can be any programs such as P4 programs related to reading table data, building headers, DMA to/from memory regions in HBM or in the host device and various other actions. The one or more programs can be executed in any stage of a pipeline as described elsewhere herein.

The MPU <NUM> can have a register file unit <NUM> to stage data between the memory and the functional units of the MPU, or between the memory external to the MPU and the functional units of the MPU. The functional units may include, for example, ALUs, meters, counters, adders, shifters, edge detectors, zero detectors, condition code registers, status registers, and the like. In some cases, the register file unit <NUM> may comprise a plurality of general-purpose registers (e.g., R0, R1,. Rn) which may be initially loaded with metadata values then later used to store temporary variables within execution of a program until completion of the program. For example, the register file unit <NUM> may be used to store SRAM addresses, ternary content addressable memory (TCAM) search values, ALU operands, comparison sources, or action results. The register file unit of a stage may also provide data/program context to the register file of the subsequent stage, as well as making data/program context available to the next stage's execution data path (i.e., the source registers of the next stage's adder, shifter, and the like). In some embodiments, each register of the register file is <NUM> bits and may be initially loaded with special metadata values such as hash value from table lookup, packet size, PHV timestamp, programmable table constant and the like.

In some embodiments, the register file unit <NUM> can have a comparator flags unit (e.g., C0, C1,. Cn) configured to store comparator flags. The comparator flags can be set by calculation results generated by the ALU which in return can be compared with constant values in an encoded instruction to determine a conditional branch instruction. In some embodiments, the MPU can have one-bit comparator flags (e.g. <NUM> one-bit comparator flags). In practice, an MPU can have any number of comparator flag units each of which may have any suitable length.

The MPU <NUM> can have one or more functional units such as the ALU(s) <NUM>. An ALU may support arithmetic and logical operations on the values stored in the register file unit <NUM>. The results of the ALU operations (e.g., add, subtract, AND, OR, XOR, NOT, AND NOT, shift, and compare) may then be written back to the register file. The functional units of the MPU may, for example, update or modify fields anywhere in a PHV, write to memory (e.g. table flush), or perform operations that are not related to PHV update. For example, an ALU may be configured to perform calculations on descriptor rings, scatter gather lists (SGLs), and control data structures loaded into the general purpose registers from the host memory.

The MPU <NUM> can have other functional units such as meters, counters, action insert units, and the like. For example, an ALU may be configured to support P4 compliant meters. A meter is a type of action executable on a table match used to measure data flow rates. A meter may include a number of bands, typically two or three, each of which has a defined maximum data rate and optional burst size. Using a leaky bucket analogy, a meter band is a bucket filled by the packet data rate and drained at a constant allowed data rate. Overflow occurs if the integration of data rate exceeding quota is larger than the burst size. Overflowing one band triggers activity into the next band, which presumably allows a higher data rate. In some cases, a field of the packet may be marked as a result of overflowing the base band. This information might be used later to direct the packet to a different queue, where it may be more subject to delay or dropping in case of congestion. The counter may be implemented by the MPU instructions. The MPU can have one or more types of counters for different purposes. For example, the MPU can have performance counters to count MPU stalls. An action insert unit or set of instructions may be configured to push the register file result back to the PHV for header field modifications.

The MPU may be capable of locking a table. In some case, a table being processed by an MPU may be locked or marked as "locked" in the table engine. For example, while an MPU has a table loaded into its register file, the table address may be reported back to the table engine, causing future reads to the same table address to stall until the MPU has released the table lock. For instance, the MPU may release the lock when an explicit table flush instruction is executed, the MPU program ends, or the MPU address is changed. In some cases, an MPU may lock more than one table addresses, for example, one for the previous table write-back and another address lock for the current MPU program.

In some embodiments, a single MPU may be configured to execute instructions of a program until completion of the program. In other embodiments, multiple MPUs may be configured to execute a program. A table result can be distributed to multiple MPUs. The table result may be distributed to multiple MPUs according to an MPU distribution mask configured for the tables. This provides advantages to prevent data stalls or mega packets per second (MPPS) decrease when a program is too long. For example, if a PHV requires four table reads in one stage, then each MPU program may be limited to only eight instructions in order to maintain a <NUM> MPPS if operating at a frequency of <NUM> in which scenario multiple MPUs may be desirable.

<FIG> illustrates a block diagram of a packet processing circuit <NUM> that may be configured as a P4 ingress/egress pipeline within the exemplary system of <FIG>. A P4 pipeline can be programmed to provide various features, including, but not limited to, routing, bridging, tunneling, forwarding, network ACLs, L4 firewalls, flow based rate limiting, VLAN tag policies, membership, isolation, multicast and group control, label push/pop operations, L4 load balancing, L4 flow tables for analytics and flow specific processing, DDOS attack detection, mitigation, telemetry data gathering on any packet field or flow state and various others.

A programmer or compiler may decompose a packet processing program into a set of dependent or independent table lookup and action processing stages (i.e., match-action) that can be mapped onto the table engine and MPU stages. The match-action pipeline can have a plurality of stages. For example, a packet entering the pipeline may be first parsed by a parser (e.g., parser <NUM>) according to the packet header stack specified by a P4 program. This parsed representation of the packet may be referred to as a packet header vector (PHV). The PHV may then be passed through stages (e.g., stages <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) of the match-action pipeline. Each pipeline stage can be configured to match one or more PHV fields to tables and to update the PHV, table entries, or other data according to the actions specified by the P4 program. If the required number of stages exceeds the implemented number of stages, a packet can be recirculated for additional processing. The packet payload may travel in a separate queue or buffer until it is reassembled with its PHV in a deparser <NUM>. The deparser <NUM> can rewrite the original packet according to the PHV fields which may have been modified in the pipeline. A packet processed by an ingress pipeline may be placed in a packet buffer for scheduling and possible replication. In some cases, once the packet is scheduled and leaves the packet buffer, it may be parsed again to create an egress parsed header vector. The egress parsed header vector may be passed through a P4 egress pipeline in a similar fashion as a packet passing through a P4 ingress pipeline, after which a final deparser operation may be executed before the packet is sent to its destination interface or recirculated for additional processing. The NIC <NUM> of <FIG> has a P4 ingress pipeline and a P4 egress pipeline. The P4 ingress pipeline and the P4 egress pipeline can be implemented via a packet processing circuit <NUM>.

In some embodiments, the P4 ingress pipeline and the P4 egress pipeline may be implemented using the same physical block or processing unit pipeline.

A pipeline can have multiple parsers and can have multiple deparsers. The parser can be a P4 compliant programmable parser and the deparser can be a P4 compliant programmable deparser. The parser may be configured to extract packet header fields according to P4 header definitions and place them in a PHV. The parser may select from any fields within the packet and align the information from the selected fields to create the PHV. The deparser can be configured to rewrite the original packet according to an updated PHV.

The PHV produced by the parser may have any size or length. For example, the PHV can be a least <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits, <NUM> bits or <NUM> bits. A long PHV (e.g., a <NUM> Kb PHV containing all relevant header fields and metadata) can be time division multiplexed (TDM) across several cycles. The TDM capability provides support for variable length PHVs, including very long PHVs to enable complex features. A PHV length may vary as the packet passes through the pipeline stages.

The pipeline MPUs of the match-action units <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> can be same as the MPU <NUM> of <FIG>. Match-action units can have any number of MPUs. The match-action units of a match-action pipeline can all be identical.

A table engine <NUM> may be configured to support per-stage table match. For example, the table engine <NUM> may be configured to hash, lookup, and/or compare keys to table entries. The table engine <NUM> may be configured to control the address and size of the table, use PHV fields to generate a lookup key, and find Session Ids or MPU instruction pointers that define the P4 program associated with a table entry. A table result produced by the table engine can be distributed to the multiple MPUs.

The table engine <NUM> can be configured to control a table selection. In some cases, upon entering a stage, a PHV is examined to select which table(s) to enable for the arriving PHV. Table selection criteria may be determined based on the information contained in the PHV. In some cases, a match table may be selected based on packet type information related to a packet type associated with the PHV. For instance, the table selection criteria may be based on packet type or protocols (e.g., Internet Protocol version <NUM> (1Pv4), Internet Protocol version <NUM> (1Pv6), MPLSA, or the next table ID as determined by the preceding stage. In some cases, the incoming PHV may be analyzed by the table selection logic, which then generates a table selection key and compares the result using a TCAM to select the active tables. A table selection key may be used to drive table hash generation, table data comparison, and associated data into the MPUs.

In some embodiments, the table engine <NUM> can have a hash generation unit <NUM>. The hash generation unit may be configured to generate a hash result off a PHV input and the hash result may be used to conduct a DMA read from a DRAM or SRAM array. In an example, the input to the hash generation unit may be masked according to which bits in the table selection key contribute to the hash entropy. In some cases, the same mask may be used by the table engine for comparison with the returning SRAM read data. In some instances, the hash result may be scaled according to the table size, then the table base offset can be added to create a memory index. The memory index may be sent to the DRAM or SRAM array and to perform the read.

The table engine <NUM> can have a TCAM control unit <NUM>. The TCAM control unit may be configured to allocate memory to store multiple TCAM search tables. In an example, a PHV table selection key may be directed to a TCAM search stage before a SRAM lookup. The TCAM control unit may be configured to allocate TCAMs to individual pipeline stages to prevent TCAM resource conflicts, or to allocate TCAM into multiple search tables within a stage. The TCAM search index results may be forwarded to the table engine for SRAM lookups.

The table engine <NUM> may be implemented by hardware or circuitry. The table engine may be hardware defined. In some cases, the results of table lookups or table results are provided to the MPU in its register file.

A match-action pipeline can have multiple match-action units such as the six units illustrated in the example of <FIG>. In practice, a match-action pipeline can have any number of match-action units. The match-action units can share a common set of SRAMs and TCAMs <NUM>. The SRAMs and TCAMs <NUM> may be components of the pipeline. This arrangement may allow the six match-action units to divide match table resources in any suitable proportion which provides convenience to the compiler and eases the complier's task of resource mapping. Any suitable number of SRAM resources and any suitable number of TCAM resources may be used by each pipeline. For example, the illustrated pipeline can be coupled to ten SRAM resources and four or eight TCAM resources. In some instances, TCAMs may be fused vertically or horizontally for a wider or deeper search.

<FIG> illustrates a block diagram of a pipeline circuit that may be used as an extended packet processing pipeline, or P4+ pipeline, within the exemplary system of <FIG>. Extended packet processing pipelines are sometimes called a P4+ pipelines. The extended packet processing pipeline stages are illustrated as extended P4 pipeline stages having P4+ match-action units, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. The extended packet processing pipeline stages can be substantially similar to the P4 pipeline stages of <FIG> with a few different features. In some cases, the extended packet processing pipeline stages may not use TCAM resources and may use less SRAM resources than P4 stages. The extended packet processing pipeline can have a different number of stages than the P4 pipeline. The extended packet processing pipeline is illustrated with a payload DMA (PDMA) stage <NUM> at the end of the pipeline. In some cases, the extended packet processing pipeline may have a local PHV recirculate data path that may recirculate a PHV without using the packet buffer. A packet may be passed to the extended packet processing pipeline from a P4 pipeline which may include P4 forwarding, isolation, multicast, L4 security, and other network features.

In some embodiments, the extended packet processing pipeline <NUM> can have a PHV splitter <NUM> configured to generate an augmented PHV. For example, the metadata fields of the PHV (e.g., logical interfaces (LIF) ID) can be passed from the P4 pipeline through the packet buffer as a contiguous block of fields prepended to the packet. Before entering the first stage of extended packet processing pipeline, the PHV splitter <NUM> may extract the prepended metadata and place it in the augmented PHV. The PHV splitter <NUM> can maintain a count of number of PHVs that are currently in the extended packet processing pipeline, as well as a count of number of packet payload bytes that are in the pipeline. In some cases, when either the PHV count or the total packet byte count exceeds a high-water mark, the PHV splitter <NUM> may stop accepting new packets from the packet buffer to ensure that packets recirculated from the PDMA <NUM> have priority to be processed and exit the pipeline.

The extended packet processing pipeline can have a PDMA <NUM> configured to control ordering between dependent events. A packet data may be sent in a FIFO to the PDMA <NUM><NUM> to await DMA commands created in the extended packet processing pipeline. The DMA commands may be created by the MPU. The PDMA <NUM> at the end of the extended packet processing pipeline can execute the PDMA write commands, DMA completion queue (CQ) write commands, interrupt assertion writes, DMA operations, and other commends in the order the DMA commands are placed in the PHV. DMA commands can be placed in a PHV. In some cases, the DMA commands generated in the extended packet processing pipeline are arranged in a contiguous space such that the commands can be executed in order as long as the first command and the last command are indicated. For instance, the first DMA command may be pointed to by an intrinsic PHV field and subsequent DMA commands may be placed contiguous within the PHV, where the last DMA command may be indicated by the another intrinsic PHV field. In some cases, the order may not be maintained between some of the DMA commands. For example, the order between memory to memory command and non-memory to memory commands may not be maintained. This is beneficial to prevent memory to memory read latency from blocking packet processing commands. The extended packet processing pipeline can generate traffic flow management data such as augmented PHVs, configurations for the match-action pipeline, and other data. The flow management data can be written to a memory, such as the HMB, using a direct memory access operation.

<FIG>, which includes <FIG>, illustrates offloading tasks from the CPU cores to an extended packet processing pipeline according to some aspects. In <FIG>, the CPU cores <NUM> are configured to run processes including a process for removing expired flow tale entries <NUM>. The process <NUM> can interact with the memory <NUM> and with the packet processing pipeline <NUM> which is illustrated as containing an SRAM. The illustrated process is detailed below. In <FIG>, the illustrated process has been offloaded to the extended packet processing pipeline <NUM>. The extended packet processing pipeline <NUM> is configured to run processes including a process for removing expired flow tale entries <NUM>. The process <NUM> can interact with the memory <NUM>, the CPU cores <NUM>, and with the packet processing pipeline <NUM> which is illustrated as containing an SRAM.

<FIG> illustrates populating a key-value table according to some aspects. In the non-limiting example of <FIG>, a key <NUM> is read from the PHV <NUM> of a packet. The key can be, for example, the <NUM>-tuple of the packet or can be assembled from other data in the PHV <NUM>. A hash generator <NUM> receives the key <NUM> and generates a hash value to be used as a key <NUM>. The hash value can be a CRC-<NUM> computed using the key or can be computed using a different hashing algorithm or different PHV fields. Note that CRC-<NUM> can be used as a hashing algorithm for the purpose of generating keys in the context of a P4 pipeline. The hash value <NUM> can be divided into an index <NUM> and a hint or residue <NUM>. For example, the index <NUM> can be the <NUM> least significant bits of the key <NUM> while the residue <NUM> can be the remaining <NUM> bits. The index can provide the location of a value <NUM> in a key-value table <NUM>. The number of bits chosen for index determines the size of the table. Note that the term "key-value table" (or "key-value database"), is here used as a term of art and does not indicate that key <NUM> is the index <NUM> for the table <NUM>. The value <NUM> can contain the key <NUM>, table data <NUM>, and residue pairs. The key-value table can contain millions of values such as value <NUM>. Each of the values can be stored at a location indicated by an index. As discussed below, hash collisions can occur because multiple keys can have the same index. Index locations in the table can therefore be referred to as hash buckets because multiple values having different keys but the same index can be accessed via the index location in the key-value table.

Table data <NUM> can be stored in the table <NUM> in association with the key. The table data <NUM> can be, for example, data that is input to a function (e.g. one or more arguments of a function), or can indicate a set of instructions that can be executed by the MPUs (e.g. a pointer to function). In some embodiments, the table data is a session Id that is passed as an input to executable code such as a function (set of instructions) that is run when a table lookup produces a value having the same key as the key <NUM> from the PHV <NUM>. The table data can be or can include any one or more of: a session Id that is an index into a session table; input data for executable code; an indicator of the executable code to be executed by the MPUs; or other data. A session table can be a key-value table with the session Id being an index into the table (the key). A session table value, located in the session table via the session Id, can be or indicate executable code and data to be used to process a packet. As such, the session Id can indicate, via a session table, the executable code and data to be used to process a packet.

If a pipeline is configured for a network traffic flow, the key-value table has an entry for that flow. A table lookup uses the index <NUM> calculated from the key <NUM> and can return the value <NUM> at the indexed location in the key-value table <NUM>. A collision occurs when the index calculated for two different flows are the same.

<FIG> illustrates collision handling via a linked list according to some aspects. A value <NUM> can be returned from a key-value table using an index calculated from a packet's key, which is the key <NUM> parsed and extracted from the packet. The packet's key can be compared to the key in the value <NUM>. If the keys are the same, the table data in the value <NUM> can be used by the MPUs. If the keys are not the same, the table engine can follow the linked list head pointer P0 to the first linked list entry (L0) <NUM>. If the packet's key is the same as the key in L0, the table data in L0 can be provided to the MPUs, otherwise the table engine can follow the pointer (P1) to the second linked list entry (L1). If the packet's key is the same as the key in L1, the table data in L1 can be provided to the MPUs, otherwise the table engine can follow the pointer (P2) to the third linked list entry (L2).

If the packet's key is the same as the key in L2, the table data in L2 can be provided to the MPUs, otherwise the table engine determines that a flow miss has occurred because L2 is the final entry in the linked list. As discussed above, the table data can be provided to executable code as input data. For example, the table data can be a session Id that is provided as input to the executable code. The table data can also be or include an indicator of the executable code to be run, in which case the table can include a function pointer, subroutine identifier, a branch address, or some other indicator of executable code. The match-action unit can report the flow miss. The pipeline may be configured to process the traffic flow of the PHV generating the flow miss by, in part, adding a fourth linked list entry based on the traffic flow. The insertion point for the fourth linked list entry can be the third linked list entry, the new entry to be added, as L3, after L2. Those familiar with computer programming and data structures are familiar with linked lists.

A possible race condition can occur when a first new flow and a second new flow have the same index, the match-action pipeline is not yet configured to process the first new flow, and the match-action pipeline is not yet configured to process the second new flow. In such a case, the match-action pipeline provides the same insertion point for both traffic flows. The race condition occurs if the same insertion point is used when configuring the match-action pipeline to process the first new flow and the second new flow. Flow entry state data can be used to avoid the race condition. The flow entry state data can indicate which insertion points are valid, which are invalid, or both. Before configuring the match-action pipeline for the first new traffic flow, the flow entry status data can be checked to find that the insertion point is a valid insertion point. The match-action pipeline can therefore be configured to process the first new flow and the flow entry status data can be updated because the insertion point is now invalid. Afterwards, and before configuring the match-action pipeline for the second new traffic flow, the flow entry status data can be checked to find that the insertion point is invalid. A valid insertion point for the second new flow can then be determined. For example, the CPU can access the flow table to determine a valid insertion point or can recirculate a packet of the second new flow, thereby causing a flow miss resulting in a new augmented PHV for the second new flow. The flow entry state data can be a table held in memory. For example, the table can indicate a valid insertion point for each index value.

<FIG> illustrates collision handling via multiple linked lists according to some aspects. Placing all the collisions for an index in the same linked list can result in a large data structure that is slow to traverse. Instead of one large linked list, multiple smaller linked lists can be used to more quickly find the table data or flow miss for a key. All or some of the bits of the residue can be used to indicate one of a number of linked lists. For example, two of the residue bits can be used to indicate one of four linked lists. The value <NUM> returned from the key-value table can contain residue pairs <NUM>. The residue pairs each indicate a linked list. In the non-limiting example of <FIG>, two bits of the residue are used to indicate one of four linked lists. The first residue pair [R0, P00] indicates that the first linked list (LL0) <NUM> has a first entry (L00) located at P00. The second residue pair [R1, P10] indicates that the second linked list (LL1) <NUM> has a first entry (L10) located at P10. The third residue pair [R2, P20] indicates that the third linked list (LL2) <NUM> has a first entry (L20) located at P20. The fourth residue pair [R3, P30] indicates that the fourth linked list (LL3) is null <NUM>, it has no entries. A value can be stored in LL3 using the fourth residue pair as an entry point. The residue pairs can be a table with the residue bits indicating positions in the table. As an example, R0, R1, R2, and R3 can indicate locations <NUM>, <NUM>, <NUM>, and <NUM> in a table of pointers. P00, P10, P20, and P30 can be stored in location <NUM>, <NUM>, <NUM>, and <NUM>, respectively.

<FIG> is a high-level flow diagram <NUM> of P4 match-action unit processing a packet header vector according to some aspects. A packet has been received at by the parser of a P4 pipeline. The parser generates a PHV from the packet header. The table engine of a P4 match-action unit then attempts to locate a table entry for the PHV and to either provide table data to the MPUs or generate a flow miss. The entirety of the illustrated process can be performed within a P4 pipeline. The illustrated process of <FIG> is a non-limiting example.

A PHV from a packet is received <NUM>. A key, such as the packet <NUM>-tuple, is produced from the PHV <NUM> and a hash value is calculated from the key at block <NUM>. The hash value can contain an index and a residue. The hash algorithm can be CRC-<NUM>. At block <NUM>, a table entry can be fetched using the index to locate a value in the table. If the table stores a value at the index location then the value is fetched. If no value is stored at the index location, a flow miss occurs.

If a value is returned, no flow miss is detected at block <NUM>. At block <NUM>, the key produced at block <NUM> can be compared to the key in the returned value. If the comparison at block <NUM> indicates the returned value's key matches the packet's key, the table data in the returned value can be sent to the MPUs <NUM> which then process the packet. A table hit can locate the table data. The table data can include one or more values, such as a session Id, that can be input to executable code that is executed for each table hit. Alternatively, the table data can indicate a set of instructions that are to be executed. Yet another alternative is that the table data can indicate a set of instructions to be executed and can also contain input values for that set of instructions.

If the comparison at block <NUM> indicates the returned value's key does not match the packet's key, then the value can be checked for a valid pointer (e.g. non-null) to a linked list <NUM>. If there is a valid pointer, then a linked list exists and the pointer can be followed to the first linked list entry at block <NUM> and a value can be obtained from the first linked list entry. At block <NUM>, the packet's key, produced at block <NUM>, is compared to the key in the value obtained from the linked list. If the comparison at block <NUM> indicates a match, the table data in the value obtained from the linked list can be sent to the MPUs <NUM> which then process the packet.

If the comparison at block <NUM> indicates no match, the process can continue to block <NUM>. At block <NUM>, the pointer to the next linked list entry is checked for validity (e.g. valid if not null). As discussed above the returned values from table lookups and linked list entries contain linked list pointers. If the linked list pointer is valid, the process can loop back to following the link pointer at block <NUM>. If the linked list pointer is not valid, a flow miss is detected.

If a flow miss is detected at block <NUM> or block <NUM>, the PHV can be augmented with key derivation metadata <NUM>. The key derivation metadata can include the hash value and the insertion point. The key derivation metadata can also include a flag or other indicator of the flow miss. At block <NUM>, a CPU or a P4+ pipeline can configure the P4 pipeline to process the traffic flow.

It is important to observe that in its normal course of operations, the P4 pipeline calculates the key and hash value for every PHV it receives and that the P4 pipeline discovers the insertion point for every flow miss. Augmenting the PHV with the key derivation metadata simply places data that would otherwise be discarded (and later recalculated by the CPUs or extended P4 pipelines) into the PHV.

At block <NUM>, the traffic flow can be queued for flow table entry using the augmented PHV. In some aspects, the augmented PHV can be placed in an input queue for the CPUs. As such, the CPUs can use the key derivation metadata to configure the P4 pipeline for the new traffic flow. In some other embodiments, an extended P4 pipeline, such as the extended packet processing pipeline of <FIG> and <FIG>, can use the key derivation metadata to configure the P4 pipeline for the new traffic flow. As discussed above, the value contains the hash value and the insertion point. Without the key derivation metadata, the CPU or extended P4 pipeline may need to recalculate the hash value and determine the insertion point. Determining the insertion point can involve reads into the memory of the P4 pipeline which can slow down the P4 pipeline due to contention in accessing the P4 pipeline memory. It is wasteful for the CPUs or P4+ pipeline to determine the key derivation metadata when that data has already been determined by the P4 pipeline.

<FIG> illustrates a packet header vector <NUM> augmented with additional metadata according to some aspects. PHV <NUM> contains many of the same fields as PHV <NUM> of <FIG>. The PHV <NUM> of <FIG> can be an example of a packet PHV. A packet PHV can include data associated with a specific packet. The PHV <NUM> of <FIG> can be an example of a flow PHV or of a packet PHV. A flow PHV can include data associated with a specific network traffic flow. Flow PHVs can be held within values <NUM> stored in flow tables <NUM>. PHV <NUM> can include metadata such as hardware port <NUM>, packet timestamp <NUM>, expired/terminated indicator <NUM>, key derivation metadata, and timeout metadata. The key derivation metadata can include hash value <NUM> and flow table insertion point <NUM>. The timeout metadata can include timeout time <NUM> or most recent packet timestamp <NUM>. In practice, a packet PHV can include key insertion metadata but might not include timeout metadata. In practice, a flow PHV can include timeout metadata but might not include key insertion metadata.

The hash value <NUM> can be the same as the key <NUM> in a value <NUM>. The hash value <NUM> can include an index <NUM> and residue <NUM>. The expired/terminated indicator <NUM> can indicate that the traffic flow associated with the PHV is expired or terminated. The timeout time <NUM> can be a time after which a network traffic flow associated with the PHV is considered aged out or timed out. The most recent packet timestamp <NUM> can indicate the time at which a packet of the network traffic flow associated with the PHV was most recently received.

The hash value <NUM> can be a forward flow key hash for a forward flow of a traffic flow. A network traffic flow between a first machine and a second machine using a layer <NUM> protocol such as TCP can have a forward flow and a reverse flow. A PHV for the forward flow can have a source IP address indicating the first machine and a destination IP address indicating the second machine. A PHV for the reverse flow could therefore have a source IP address indicating the second machine and a destination IP address indicating the first machine. A PHV can be augmented with keys for both flows. The key derivation metadata can therefore include a forward flow key hash for the forward flow of the network traffic flow and a reverse flow key hash for the reverse flow of the network traffic flow.

The timeout metadata of PHV <NUM> can include a timeout time value <NUM> and a most recent packet timestamp <NUM>. In practice, a PHV may have either a timeout time value <NUM> or a most recent packet timestamp <NUM>, but might not have both.

One non-limiting example of using the timeout metadata is as follows. A network appliance receives a packet for a network traffic flow. When processing the packet, the match-action pipeline of the network appliance may locate a flow table entry (e.g. value <NUM>) for the network traffic flow. The flow table entry can contain a flow PHV containing a most recent packet timestamp <NUM>. If the packet PHV timestamp <NUM> is later than the most recent packet timestamp <NUM>, then the most recent packet timestamp <NUM> can be set to equal the packet PHV timestamp <NUM>. If the network traffic flow is a new traffic flow, then the most recent packet timestamp <NUM> for a new flow table entry for the new network traffic flow can be set to the packet PHV timestamp <NUM>. The network traffic flow can be considered timed out or aged out when the current time is later than the most recent packet timestamp <NUM> plus a time period. The time period can be, for example, <NUM> second, <NUM> seconds, or a value based on a property or type of the traffic flow. Properties of the traffic flow can include data from packet headers <NUM>, hardware port <NUM>, and other data. For example, a time period for a TCP traffic flow on a virtual local area network (VLAN) may differ from a time period for a UDP traffic flow between hosts that are not on the same VLAN.

Another non-limiting example of using the timeout metadata is as follows. A network appliance receives a packet for a network traffic flow. When processing the packet, the match-action pipeline of the network appliance may locate a flow table entry (e.g. value <NUM>) for the network traffic flow. The flow table entry can contain a flow PHV containing a timeout time <NUM>. The match-action pipeline can calculate a candidate timeout time as the packet PHV timestamp <NUM> plus a time period. The time period can be, for example, <NUM> second, <NUM> seconds, or a value based on a property or type of the traffic flow. If the candidate timeout time is later than the timeout time <NUM> of the flow PHV then the timeout time <NUM> can be set to equal to the candidate timeout time. If the network traffic flow is a new traffic flow, then the timeout time <NUM> for a new flow table entry for the new network traffic flow can be set to the candidate timeout time. The network traffic flow can be considered timed out or aged out when the current time is later than the timeout time <NUM>.

A match-action pipeline may have limited memory, thereby limiting the size of the match-action pipeline's flow table. It may therefore be necessary to delete flow table entries for expired or terminated network traffic flows so that new flow table entries can be created for new network traffic flows. Furthermore, collision handling, discussed above, can result in flow table entries saved in linked lists. Harvesting terminated and expired network traffic flows can reduce collisions and can reduce the number of flow table entries held in linked lists, resulting in faster table lookups and packet processing. Aged out network traffic flows have expired because it appears the flow will have no new packets to process. Terminated network traffic flows can include those that have been shut down by the source and destination hosts of the network traffic flows. For example, a TCP traffic flow can be terminated by a RST packet or by an ACK packet responsive to a FIN packet. A match-action pipeline, such as a P4 match-action pipeline, may be principally dedicated to processing new packets. As such, the match-action pipeline might never determine that a flow table entry is expired because it only checks flow table entries for new packets and there are no new packets for expired network traffic flows.

The CPU cores of a network appliance can search the match-action pipeline's flow table for aged out entries and can delete those flow table entries. To do so, the CPU cores must be able to access the memory of the match-action pipeline. The CPU cores may also need to lock the match-action pipeline memory while accessing it, which may halt or slow the match-action pipeline. Finding aged out flow table entries quickly can reduce the amount of time that the match-action pipeline is locked out of its memory, thereby increasing the throughput of the network appliance. Using an extended packet processing pipeline for searching the match-action pipeline's flow table for aged out entries can free the CPU cores for other tasks while searching the flow table more rapidly than the CPU cores can.

<FIG> is a high-level block diagram of an extended packet processing pipeline <NUM> reading a flow table <NUM> and scheduling aged out network traffic flows for deletion according to some aspects. As discussed above, a match-action pipeline <NUM> can have a match-action pipeline memory <NUM> in which it can store data, such as a flow table <NUM>. The match-action pipeline memory <NUM> can include RAM, TCAM, or both. An extended packet processing pipeline <NUM> can read the timeout metadata <NUM> in the flow PHVs <NUM> in the flow table entries <NUM> of flow table <NUM> to locate aged out, terminated, and expired flow table entries. A flow table entry <NUM> can be a value <NUM> stored at an index location or on a linked list as discussed above. The extended packet processing pipeline <NUM> can place a table entry deletion command <NUM> in a CPU input queue <NUM> to instruct a CPU core <NUM> to execute a traffic flow deletion operation <NUM> and thereby delete an aged out flow table entry.

<FIG> is a high-level flow diagram of a process <NUM> for deleting aged out network traffic flows from a flow table according to some aspects. An extended packet processing pipeline such as the extended packet processing pipeline of <FIG> can be configured to implement the process <NUM> of <FIG>. In some aspects, individual stages, such as the P4+ match-action units of <FIG> and <FIG> can be configured to implement the process <NUM> of <FIG>. The illustrated process searches from an initial flow table entry to a final flow table entry.

At block <NUM>, a table reference is initialized to indicate an initial flow table entry and a last reference is initialized to indicate a final flow table entry. The initial flow table entry can be the first entry in the flow table or can be any other flow table entry. At block <NUM>, the timeout metadata and a linked list reference are read from the flow table entry indicated by the table reference. At block <NUM>, the timeout metadata is checked to determine if the referenced flow table entry is aged out. As discussed above, a timeout time or a most recent packet timestamp can be used in determining if the referenced flow table entry is aged out. If the referenced flow table entry is not aged out, then the process continues to block <NUM>. Otherwise, a command to delete the flow table entry indicated by the table reference is sent at block <NUM> before continuing to block <NUM>. At block <NUM>, the linked list reference is checked for validity. If the linked list reference is valid, then there is a flow table entry on a linked list and, at block <NUM>, the timeout metadata and a next linked list reference are read from the flow table entry indicated by the linked list reference. If the flow table entry indicated by the linked list reference is not aged out then the linked list reference is set to the next linked list reference at block <NUM>. Otherwise, a command to delete the flow table entry indicated by the linked list reference is sent at block <NUM> before continuing to block <NUM>. The process then loops back to block <NUM>. At block <NUM>, the linked list reference is checked for validity. If the linked list reference is not valid, then the process continues to block <NUM>. At block <NUM>, if the table reference is the last reference then the process can stop. Otherwise, the table reference is set to the next flow table entry at block <NUM> and the process loops back to block <NUM>.

The process of <FIG> can find the aged out flow table entries in a flow table such as that of <FIG>. To search a flow table such as that of <FIG>, the linked list reference can be stepped through the residue pairs to thereby check the flow tables entries in each of the linked lists.

<FIG> is a high-level block diagram of extended packet processing pipeline stages <NUM>, <NUM>, <NUM> reading shards <NUM>, <NUM>, <NUM> of a flow table <NUM> and scheduling aged out network traffic flows for deletion according to some aspects. Flow table <NUM> has been divided into M shards. The boundaries between shards can be based on aspects of the memory that is storing the flow table. For example, blocks of the memory may be independently lockable and some of the shard boundaries may coincide with the boundaries between lockable memory blocks. The shard boundaries may be selected based on some other criteria such as dividing the flow table into M numbers of indexes, plus or minus one or two because the size of the flow table may not be divisible by M.

Stages of the extended packet processing pipeline <NUM> may be configured to implement the process of <FIG>. For example, stage <NUM><NUM> can search shard <NUM><NUM> when the initial flow table entry is the first flow table entry of shard <NUM> and the final flow table entry is the last flow table entry of shard <NUM>. The other extended packet processing pipeline stages may be similarly initialized or configured to search other shards. Each of the stages can search in parallel with, for example, stage <NUM><NUM> searching shard <NUM><NUM> at the same time that stage <NUM><NUM> is searching shard <NUM><NUM> and stage N <NUM> is searching shard M <NUM>. The stages <NUM>, <NUM>, <NUM> can send commands to delete aged out flow table entries to a flow processor <NUM> that can add and delete flow table entries while avoiding race conditions.

<FIG> is a high-level flow diagram of a parallel process <NUM> for deleting aged out network traffic flows from a flow table according to some aspects. After the start, the process splits <NUM> into a number of parallel threads. Stage <NUM> processes block <NUM> while stage <NUM> processes block <NUM> and stage N processes block <NUM>. At block <NUM>, stage <NUM> implements the process of <FIG>. For the thread running on stage <NUM>, the table reference is initialized to indicate an initial flow table entry of shard <NUM> and the last reference indicates the final flow table entry of shard <NUM>. At block <NUM>, stage <NUM> implements the process of <FIG>. For the thread running on stage <NUM>, the table reference is initialized to indicate an initial flow table entry of shard <NUM> and the last reference indicates the final flow table entry of shard <NUM>. At block <NUM>, stage N implements the process of <FIG>. For the thread running on stage N, the table reference is initialized to indicate an initial flow table entry of shard M and the last reference indicates the final flow table entry of shard M.

<FIG> illustrates a high-level diagram of a flow processor according to some aspects. As discussed above, a flow table using linked lists or other data structures for collision avoidance can have numerous flows at the same index. Race conditions can occur when numerous commands for flow table entry, deletion, or other modification are created and processed for the same index. For example, race conditions can occur when two new flows have the same index. Another race condition is possible out of order deletion of two flow table entries on the same linked list resulting in the wrong entry being deleted. In general, race conditions can occur when multiple match-action pipeline configuration operations are queued for a single hash bucket and those operations are performed out of order. Here, a hash bucket can refer to all of the flow table entries having the same index. The race condition is that match-action pipeline configuration operations and flow table deletions may be performed out of order when they can be performed in parallel. Processing operations in parallel (e.g. multiple CPUs or P4+ pipeline stages processing multiple operations at the same time), however, is desired in order to perform more operations over a given time (e.g. more connections per second). Serialization queues can serialize a plurality of match-action operations to thereby prevent race conditions. A flow processor can configure a match-action pipeline to process traffic flows, to remove traffic flows, etc. The flow processor can be implemented by the NIC <NUM> of <FIG> via its CPUs, extended packet processing pipelines, etc..

The flow processor <NUM> of <FIG> is a non-limiting example of a flow processor having four flow processor workers <NUM>, <NUM>, <NUM>, <NUM>. Flow miss processing <NUM> can generate match-action pipeline configuration operations for configuring a match-action pipeline <NUM> to process new network traffic flows. Flow expiration and termination processing <NUM> can generate match-action pipeline configuration operations for deleting network traffic flows from the match-action pipeline <NUM>. The match-action pipeline configuration operations can be entered into the flow processor serialization queue <NUM> of a flow processor <NUM>. The flow processor workers <NUM>, <NUM>, <NUM>, <NUM> can work in parallel to perform the operations. Each worker can have a worker serialization queue. Operations for flow processor worker <NUM><NUM> can be queued on flow processor serialization queue <NUM><NUM>. Operations for flow processor worker <NUM><NUM> can be queued on flow processor serialization queue <NUM><NUM>. Operations for flow processor worker <NUM><NUM> can be queued on flow processor serialization queue <NUM><NUM>. Operations for flow processor worker <NUM><NUM> can be queued on flow processor serialization queue <NUM><NUM>.

The flow processor worker for a particular match-action pipeline configuration operation can be selected based on a value calculated from the PHV such as the index <NUM> in the key <NUM> in the PHV. Embodiments having four flow processor workers can use two bits of the index to select a flow processor worker. For example, the two least significant bits (LSBs) of the index can be interpreted as the flow processor worker number of the selected flow processor worker. If the bits are "<NUM>", then the operation can be entered into flow processor serialization queue <NUM><NUM>. If the bits are "<NUM>", then the operation can be entered into flow processor serialization queue <NUM><NUM>. If the bits are "<NUM>", then the operation can be entered into flow processor serialization queue <NUM><NUM>. If the bits are "<NUM>", then the operation can be entered into flow processor serialization queue <NUM><NUM>.

Using bits from the index ensures that match-action pipeline configuration operations for a particular hash bucket are performed by the same flow processor worker. Placing those operations on a serialization queue for that flow processor worker ensures that the operations are performed in order. More or fewer flow processor workers can be used, each having a serialization queue such that operations for a particular hash bucket are always performed in order by the same flow processor worker.

In the process of <FIG>, the commands to delete flow table entries can be sent to the flow processor <NUM> or can be sent directly to an input queue for a CPU core. Sending all the operations for a particular hash bucket to the same CPU core can avoid race conditions. At blocks <NUM> and <NUM>, the table reference can be a flow table index <NUM> or can reference a flow table entry having a flow table index. A CPU core for a particular table entry deletion operation can be selected based on the flow table index <NUM> of the flow being deleted. Embodiments having four CPU cores can use two bits of the index to select a CPU core. For example, the two least significant bits (LSBs) of the index can be interpreted as the number of the selected CPU core. If the bits are "<NUM>", then the operation can be entered into the input queue for CPU core <NUM>. If the bits are "<NUM>", then the operation can be entered into the input queue for CPU core <NUM>. If the bits are "<NUM>", then the operation can be entered into the input queue for CPU core <NUM>. If the bits are "<NUM>", then the operation can be entered into the input queue for CPU core <NUM>. The number of bits can be based on the number of CPU cores. For example, a network appliance with sixteen CPU cores can use four bits of the index to select a CPU core.

<FIG> is a high-level flow diagram of a method removing expired flow table entries using an extended packet processing pipeline according to some aspects. At block <NUM>, a plurality of flow table entries is stored in a flow table of a match-action pipeline, wherein the match-action pipeline is implemented via a packet processing circuit configured to process a plurality of network traffic flows associated with the plurality of flow table entries. At block <NUM>, an extended packet processing pipeline can read a flow table entry of the flow table, wherein the extended packet processing pipeline is implemented via a pipeline circuit. At block <NUM>, the extended packet processing pipeline can determine that a network traffic flow associated with the flow table entry is expired or terminated. For example, a P4+ pipeline can detect a timeout of the traffic flow based on a timestamp in the flow table entry. At block <NUM>, the flow table entry can be deleted from the flow table by processing a traffic flow deletion operation after determining that the network traffic flow is expired or terminated.

Aspects described above can be ultimately implemented in a network appliance that includes physical circuits that implement digital data processing, storage, and communications. The network appliance can include processing circuits, ROM, RAM, CAM, and at least one interface (interface(s)). In an embodiment, the CPU cores described above are implemented in processing circuits and memory that is integrated into the same integrated circuit (IC) device as ASIC circuits and memory that are used to implement the programmable packet processing pipeline. For example, the CPU cores and ASIC circuits are fabricated on the same semiconductor substrate to form a System-on-Chip (SoC). In an embodiment, the network appliance may be embodied as a single IC device (e.g., fabricated on a single substrate) or the network appliance may be embodied as a system that includes multiple IC devices connected by, for example, a printed circuit board (PCB). In an embodiment, the interfaces may include network interfaces (e.g., Ethernet interfaces and/or InfiniBand interfaces) and/or PCI Express (PCIe) interfaces. The interfaces may also include other management and control interfaces such as I2C, general purpose I/Os, USB, UART, SPI, and eMMC.

As used herein the terms "packet" and "frame" may be used interchangeably to refer to a protocol data unit (PDU) that includes a header portion and a payload portion and that is communicated via a network protocol or protocols. In some embodiments, a PDU may be referred to as a "frame" in the context of Layer <NUM> (the data link layer) and as a "packet" in the context of Layer <NUM> (the network layer). For reference, according to the P4 specification: a network packet is a formatted unit of data carried by a packet-switched network; a packet header is formatted data at the beginning of a packet in which a given packet may contain a sequence of packet headers representing different network protocols; a packet payload is packet data that follows the packet headers; a packet-processing system is a data-processing system designed for processing network packets, which, in general, implement control plane and data plane algorithms; and a target is a packet-processing system capable of executing a P4 program.

Although the techniques are described herein in terms of processing packetized digital data as is common in digital communications networks, the techniques described herein are also applicable to processing digital data that is not packetized for digital communication using a network protocol. For example, the techniques described herein may be applicable to the encryption of data, redundant array of independent disks (RAID) processing, offload services, local storage operations, and/or segmentation operations. Although the techniques are described herein in terms of the P4 domain-specific language, the techniques may be applicable to other domain-specific languages that utilize a programmable data processing pipeline at the data plane.

It should also be noted that at least some of the operations for the methods described herein may be implemented using software instructions stored on a computer useable storage medium for execution by a computer. As an example, an embodiment of a computer program product includes a computer useable storage medium to store a computer readable program.

Claim 1:
A computer-implemented method executable by a network appliance, the computer-implemented method comprising:
(<NUM>) storing a plurality of flow table entries (<NUM>) in a flow table (<NUM>) of a match-action pipeline (<NUM>, <NUM>) of the network appliance, wherein the match-action pipeline (<NUM>) is implemented via a packet processing circuit (<NUM>) configured to process a plurality of network traffic flows associated with the plurality of flow table entries (<NUM>);
(<NUM>) reading, by an extended packet processing pipeline (<NUM>, <NUM>) of the network appliance, a flow table entry (<NUM>) of the flow table (<NUM>), wherein the extended packet processing pipeline (<NUM>, <NUM>) is implemented via a pipeline circuit (<NUM>) that is external to the packet processing circuit;
(<NUM>) determining, by the extended packet processing pipeline (<NUM>, <NUM>), that a network traffic flow associated with the flow table entry (<NUM>) is expired or terminated; and
(<NUM>) deleting, by the network appliance, the flow table entry (<NUM>) from the flow table (<NUM>) by processing a traffic flow deletion operation (<NUM>) after determining that the network traffic flow is expired or terminated,
wherein
the flow table (<NUM>) is stored in a pipeline memory (<NUM>, <NUM>) of the match-action pipeline (<NUM>, <NUM>);
a plurality of shards (<NUM>, <NUM>, <NUM>) of the flow table contain the plurality of flow table entries;
the extended packet processing pipeline includes a plurality of extended packet processing pipeline stages (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>); and
the extended packet processing pipeline stages are configured to concurrently search the plurality of shards.