Patent ID: 12244499

DETAILED DESCRIPTION

Overview

The present disclosure provides for protocol-independent receive side scaling (RSS) and hypervisor bypass for virtual servers. A flow hash is defined over any arbitrary N-tuple, providing flexible forwarding lookup for a destination queue set. Moreover, an RSS hash is used to pick a single queue from the destination queue set, enabling direct packet distribution among receive queues owned by a virtual machine without hypervisor involvement.

A ternary content-addressable memory (TCAM) can be used to identify a pattern of protocol headers for an incoming packet based on a header of the packet. A number of initial bytes of the packet, such as the first 128 bytes, may be used as a lookup key for the TCAM to identify a pattern of protocol headers in the packet. The result of the TCAM lookup is a lowest-numbered matching TCAM row. A length of the packet header, which corresponds to a width of the TCAM, is a design parameter chosen to cover the longest protocol headers to be supported. The matching row number points to an entry in a packet classifier static random access memory (SRAM) that defines a flow hash N-tuple. The entry also defines an RSS hash M-tuple. Each definition selects particular bits from initial bytes of the packet based on the detected header protocols. The bits selected using the flow hash definition are then compacted to form a flow hash N-tuple header vector, and the bits selected using the RSS hash definition are compacted to form a RSS hash M-tuple header vector.

A flow hash function is used to compute a flow hash from the flow hash N-tuple header vector, and an RSS hash function is used to compute a RSS hash from the RSS hash M-tuple header vector. For example, the flow hash function could be secure hash algorithm SHA3, and the RSS hash function could be Toeplitz.

The computed flow hash is used for forwarding lookup. For example, the flow hash is used to lookup a flow hash table to determine a set of destination queues for the packet. If the set of queues are owned by a virtual machine (VM), the hypervisor is bypassed to deliver the packet directly to the VM. In case that there is a lookup miss, the default queue set is the queues owned by the hypervisor. Because the flow hash is defined over any arbitrary N-tuple detected by the TCAM, the forwarding lookup for the destination queue set is protocol independent. This provides increased RSS flexibility to support different protocols. For example, in addition to a typical layer 2- or layer 3-based forwarding lookup, a virtual network ID for a newly developed protocol can be added to the flow hash table for forwarding lookup. Moreover, a secure transport layer can be added to the network, allowing for addition of a security header as part of the forwarding lookup.

The computed RSS hash is used to pick a single queue from the determined set of destination queues. This enables hardware based packet distribution among a set of receive queues owned by the VM directly without hypervisor involvement. For example, the destination may be a queue in user-mode memory, directly emptied by software running in a virtual machine, bypassing a machine's operating system. Moreover, the hash used in the packet distribution is protocol independent, and therefore can be defined over arbitrary header M-tuples over arbitrary protocol headers. For example, in addition to a typical 2-tuple or 4-tuple RSS hash, a good RSS hash for remote direct memory access over converged Ethernet (RoCE) can be supported. Hashing of inner headers on any tunnel protocols can also be supported.

The techniques described above enable server NICs to support protocol independent RSS and hypervisor bypass for virtual servers at line rate. Moreover, the NIC is scalable to support faster rates, such as 400 Gbps and above. The techniques are also advantageous in that it enables fast implementation of newly developed protocols and significantly reduces cost by eliminating the need to replace hardware for every protocol innovation.

Example Systems

FIG.1illustrates a system100, including a protocol detector110, a packet classifier120, hash functions130,140, and other components. As a packet is received at a chip, such as a NIC or a switch chip, the protocol detector110is used to detect one or more header protocols in the packet. For example, the incoming packet may include any combination of protocol headers, such as link, GRE, TCP, IPv4, IPV6, VLAN, and others. The chip may read a predetermined first number of bytes, such as the first 128 bytes, from the packet headers to determine a pattern of the protocol headers. Based on this pattern, the protocol detector110may determine a header protocol definition to be applied.

The protocol detector110may be, for example, a ternary content addressable memory (TCAM) that identifies a header protocol definition corresponding to the detected combination of protocol headers. In this example, initial bytes of the packet may be used as a lookup to the TCAM to identify a pattern of protocol headers in the packet. The result of the TCAM lookup is the lowest-numbered matching TCAM row. The length of the packet header portion used as the lookup, which corresponds directly with a width of the TCAM, may be predetermined. For example, the length of the packet header may be a design parameter chosen to cover the longest protocol headers to be supported.

Based on the detected protocol headers, the packet classifier120identifies a flow hash N-tuple definition and a RSS hash M-tuple definition. For example, where the protocol detector110is a TCAM, the matching row number points to an entry in the packet classifier120that defines a flow hash N-tuple and an RSS hash M-tuple. The packet classifier120may be, for example, a static random access memory (SRAM) or any other data structure in memory.

Each of the flow hash N-tuple definition and the RSS M-tuple definition selects any desired bits from the packet header over any combination of header protocols. For example, the flow hash definition and RSS hash definition may each be a bit- or byte mask of the packet header, resulting in first and second selected sets of bits, respectively. In one example, the flow hash definition and the RSS hash definition are applied to different portion of the packet header, which portions may or may not overlap. Moreover, the RSS M-tuple definition may be applied to encapsulated packets, thereby selecting bits from inner headers in addition to or instead of selecting bits from outer headers.

The first selected set of bits may be compacted to form a flow hash N-tuple header vector. In some examples, such as described in U.S. Pat. No. 10,320,568, hereby incorporated herein by reference, the flow hash N-tuple header vector may be zero-padded to a predetermined length, and other information such as a flow hash identifier and metadata may be pre-appended thereto. The second selected set of bits may also be compacted to form an RSS hash M-tuple header vector, as discussed in further detail below in connection withFIG.3.

Flow hash function130computes a flow hash from the flow hash N-tuple header vector. For example, the flow hash function130could be SHA3, or any other hash function.

RSS hash function140computes a RSS hash from the RSS hash M-tuple header vector. The RSS hash may be, for example, a Toeplitz hash or any other hash.

The computed flow hash is used to lookup a flow hash table150to determine a set of destination queues for the packet. Because the flow hash is defined over any arbitrary N-tuple detected by the protocol detector110, the destination queue set is flexible and protocol independent. The set of destination queues may be owned by a hypervisor, a virtual machine, or other components. If the set of destination queues is owned by a virtual machine, the hypervisor may be bypassed and the packet is delivered directly to the virtual machine. If there is a lookup miss, a default queue set may be selected. The default queue set may be, for example, the set of queues owned by the hypervisor.

The RSS hash is used to select a single queue from the set of destination queues, thereby distributing packets among the set of destination queues. For example, the destination queue selection table160, described in further detail in connection withFIG.2, correlates the RSS hash with a destination. The destination may be, for example, a memory address or other instructions for handling the packet. Because the RSS hash can be defined over arbitrary M-tuples over arbitrary protocol headers, the packet distribution is protocol independent. If new protocols are developed, the packet classifier120and destination queue selection table160may be updated, without needing to replace the hardware.

FIG.2illustrates an example of the destination queue selection table160. The table160includes a number of entries250, each entry correlating an RSS hash and destination information, such as a memory address where to send the packet. For example, the destination information may identify a particular receive queue in a hypervisor or virtual machine.

The RSS hash lookup is generated using the RSS definition and hash function, as described in further detail below in connection withFIG.3. The entries250in the destination queue selection table160may be updated with RSS hashes and corresponding values when new protocols are developed. In this regard, hardware implementing the flow tables and hash table need not be replaced to accommodate new routing protocols. While only a few entries250are shown inFIG.2, it should be understood that any number of entries may be included in the destination queue selection table160.

FIG.3provides an example of generating the RSS hash for a packet. An M-tuple definition is applied to a packet header300, wherein the packet header may include any number of header fields for any combination of protocols. The M-tuple definition may be programmed in the packet classifier120for the protocol header detected in the packet.

The M-tuple definition may be a bit- or byte-mask of the first M-bits of the packet. For example, referring back toFIG.3, applying the bit-mask may result in bits310,312,314,316of the packet header300being selected. In this example, the bits310include all or a portion of a source IP address field of the packet header300, and bits312include all or a portion of destination IP fields. Bits314includes all or a portion of a source port field, and bits316includes all or a portion of a destination port field. While four sets of bits are selected inFIG.3, the definition may select any number of sets of bits in any arrangement. For example, the selected bits may include bits of inner encapsulated headers as well as outer headers.

The bits selected using the RSS M-tuple definition may be different than bits selected for the flow hash using the flow hash N-tuple definition. In some examples, the bits may overlap. For example, bits selected for the flow hash using the N-tuple definition and bits selected for the RSS hash using the M-tuple definition may both include some common bits. However, the N-tuple bits and the M-tuple bits may also include other bits which differ from one set to the next.

The selected sets of M-tuple bits310-316are compacted into an RSS M-tuple vector340. Unselected bits, such as321-323, may be ignored. The RSS vector340is hashed, for example, using a Toeplitz or other hash. As a result, an RSS hash350is generated.

FIG.4illustrates an example computing device400implementing the protocol-independent receive side scaling described above. The computing device400may be, for example, an application specific integrated circuit (ASIC), such as a switch chip or a network interface controller (NIC). In other examples, the computing device400may be any network component or device capable of receiving and forwarding data or data packets to appropriate destinations of a computer network, such as a network router, a switch, a hub, etc. While only one computing device400is shown, numerous computing devices may be interconnected. For example, the computing devices may be wired or wirelessly connected. The computing device400may be used for routing packets, for example through a system, datacenter, or network.

The computing device400may support various routing protocols, such as link, IPv, IPv6, TCP, UDP, GRE, Internet Control Message, VLAN, etc. Moreover, the computing device400may support protocols that have not yet been developed. The computing device400may provide a dedicated, full-time connection to a network and also have hardware capable of processing instructions and data stored in the one or more memories. For example, the computing device400may be a computer hardware component that may deliver an incoming packet to one or more queues in a computing device's main memory to be forwarded to other network components. In addition, the computing device400may provide the connection to other network devices via a wired connection or a wireless connection.

The computing device400may include one or more processors430, one or more memories420, as well as other components, such as any other hardware used for routing data packets through a network. For example, in one example the computing device400may be a switch chip inside a network switch, and may include ingress and egress ports462,464. In another example the computing device400may be a NIC, and may include a CPU interface (not shown).

The memory420may store information accessible by the one or more processors430, including data422instructions428that may be executed or otherwise used by the one or more processors430. For example, memory420may be of any type capable of storing information accessible by the processor(s), including a computing device-readable medium, or other medium that stores data that may be read with the aid of an electronic device, such as a volatile memory, non-volatile as well as other write-capable and read-only memories. By way of example only, memory420may be a static random-access memory (SRAM) configured to provide fast lookups. Systems and methods may include different combinations of the foregoing, whereby different portions of the instructions and data are stored on different types of media.

The data422may be retrieved, stored or modified by the one or more processors430in accordance with the instructions428. For instance, data422may include protocol detector442, packet classifier444, flow hash table446, and destination queue selection table448. In accordance with the instructions428, protocol headers of an incoming packet are detected, and first and second set of bits of the packet are selected based on the detected protocols. A flow hash N-tuple vector is constructed using the first set of selected bits, and then used to compute a flow hash. An RSS hash M-tuple vector is constructed using the second set of bits, and then used to compute an RSS hash. A set of destination queues for the packet is determined based on the computed flow hash, and a particular queue is selected based on the computed RSS hash. Although the claimed subject matter is not limited by any particular data structure, the data may be stored in computing device registers, in a relational database as a table having a plurality of different fields and records, XML documents or flat files. The data may also be formatted in any computing device-readable format.

The instructions428may be any set of instructions to be executed directly (such as machine code) or indirectly (such as scripts) by the one or more processors430. For example, the instructions may be stored as computing device code on the computing device-readable medium. In that regard, the terms “instructions” and “programs” may be used interchangeably herein. The instructions may be stored in object code format for direct processing by the processor, or in any other computing device language including scripts or collections of independent source code modules that are interpreted on demand or compiled in advance. Functions, methods and routines of the instructions are explained in more detail below.

The one or more processors430may be logic circuitry (e.g., logic gates, flip-flops, etc.) hard-wired into the computing device400itself or may be a dedicated application specific integrated circuit (ASIC). It should be understood that the one or more processors430are not limited to hard-wired logic circuitry, but may also include any commercially available CPU, or any hardware-based processors, such as a field programmable gate array (FPGA).

AlthoughFIG.4functionally illustrates the processor, memory, and other elements of computing device400as being within the same block, it will be understood by those of ordinary skill in the art that the processor and memory may actually include multiple processors and memories that may or may not be stored within the same physical housing. For example, memory420may be a volatile memory or other type of memory located in a casing different from that of computing device400. Accordingly, references to a processor or memory should be understood to include a collection of processors and memories that may or may not operate in parallel. Moreover, the various components described above may be arranged on one or more circuit boards, one or more NICs, or part of one or more computing devices.

Example Methods

In addition to the operations described above, various operations will now be described. It should be understood that the following operations do not have to be performed in the precise order described below. Rather, various operations can be handled in a different order or simultaneously, and operations may also be added or omitted.

FIG.5provides a flow diagram illustrating an example method500of protocol-independent receive side scaling.

At block510, a NIC, switch chip, or other computing device capable of reading packet contents may receive a data packet to be queued in the computing device's memory and eventually forwarded to a particular network destination.

Upon receipt of the data packet, the computing device may detect (block520) one or more protocol headers of the packet. For example, the computing device may read a predetermined number of initial bytes from a first data packet, such as the first 128 bytes of the packet, and match the bytes to a plurality patterns stored in a memory, such as a protocol detector TCAM. The memory may store, in correlation with the pattern, an identification of the protocol types. In other examples, the memory may store, in correlation with the pattern, an indication of how the packet should be further processed.

Further processing of the packet may include different sequences of operations, which may be performed in parallel or at different times. One sequence of operations, for example, may be a protocol-independent determination of a set of destination queues for the packet using a flow hash, as described in connection with blocks530,540,550,560. Another sequence of operations may be a protocol-independent computation of an RSS hash, used for selecting a particular destination queue, as described in connection with blocks535,545,555.

In block530, a first set of bits of the packet are selected based on the detected protocol headers. For example, the memory may include a packet classifier table identifying a first flow hash definition corresponding to the detected protocols. The definition may include mask bits, mask bytes, or other types of information identifying the portions of the data packet to be selected. The definitions stored in the memory may be updated in order to accommodate new types of protocols. For example, new definitions for newly developed protocols may be added, or old definitions for obsolete protocols may be removed.

In block540, a flow hash N-tuple vector is constructed using the first selected set of bits. For example, the first selected set of bits may be compacted and concatenated. Moreover, the compacted and concatenated bits may be pre-appended with a unique flow identifier for a flow table and metadata. In some examples, the flow hash N-tuple vector is zero-padded such that the resulting hash vector has a predetermined length.

In block550, a flow hash is computed using the flow hash N-tuple vector. For example, the flow hash N-tuple vector is hashed with a secret hash key, resulting in a lookup key signature for a flow hash table. The hash function used for this hash may be a secure hash or a simple hash.

In block560, a set of destination queues for the received packet is determined based on the computed flow hash. For example, the computed flow hash may be used as a lookup in a flow hash table, with a value corresponding to the lookup identifying the set of destination queues.

The set of destination queues may be in operating system memory and be emptied by operating system networking code. In other examples, the set of destination queues may be in user-mode memory and directly emptied by software running in a virtual machine, bypassing the operating system of a real machine and thereby benefitting from increased performance. In further examples, a lookup miss may occur. For example, it may be unknown whether the set of destination queues is owned by a hypervisor or by a virtual machine. In this case, the packet may be routed to the hypervisor. Regardless of where the set of destination queues are, protocol-independent receive side scaling may be used to distribute packets among destinations in the set, as described below.

In block535, a second set of bits of the packet is selected based on the detected protocol headers. For example, the memory may include a packet classifier table identifying a second RSS hash definition corresponding to the detected protocols. Similar to the flow hash definition, the RSS hash definition may include mask bits, mask bytes, or other types of information identifying the portions of the data packet to be selected. The second set of bits may be the same, different, or overlapping with the first selected set of bits. The RSS hash definitions stored in the memory may also be updated in order to accommodate new types of protocols.

In block545, an RSS hash M-tuple vector is constructed using the second selected set of bits. For example, the second selected set of bits may be compacted.

In block555, an RSS hash is computed using the RSS hash M-tuple vector. For example, the RSS hash M-tuple vector is hashed, resulting in an RSS hash. The hash function used for this hash may be a Toeplitz or other hash.

In block570, the computed RSS hash is used to select a particular destination queue from the set of destination queues determined in block560. For example, the RSS hash may be used as a lookup for a destination queue selection table. A value corresponding to the RSS hash lookup may identify a destination for the packet.

The above-described aspects of the disclosure may be advantageous in that that a network device may be able to route packets to various destinations at a full line rate regardless of the protocols associated with the packets. Moreover, the above-described features provide for versatility of network chips, which results in reduced costs for updates and efficient use of resources. For example, the routing is protocol independent, and does not assume any fixed distribution of packet headers. Packet distribution uses all available hardware resources.

Unless otherwise stated, the foregoing alternative examples are not mutually exclusive, but may be implemented in various combinations to achieve unique advantages. As these and other variations and combinations of the features discussed above can be utilized without departing from the subject matter defined by the claims, the foregoing description of the embodiments should be taken by way of illustration rather than by way of limitation of the subject matter defined by the claims. In addition, the provision of the examples described herein, as well as clauses phrased as “such as,” “including” and the like, should not be interpreted as limiting the subject matter of the claims to the specific examples; rather, the examples are intended to illustrate only one of many possible embodiments. The examples and other arrangements may be devised without departing from the spirit and scope of the subject matter defined by the appended claims. Further, the same reference numbers in different drawings can identify the same or similar elements.