Protocol-independent receive-side scaling

• US 10,361,955 B1
• Filed: 08/16/2017
• Issued: 07/23/2019
• Est. Priority Date: 06/09/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Mao, Yuhong, Sites, Richard Lee
• Primary Examiner(s): Kamara, Mohamed A
• Application Number:
  US15/678,295
• Time in Patent Office: 706 Days
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A system and method for protocol independent receive side scaling (RSS) includes storing a plurality of RSS hash M-tuple definitions, each definition corresponding to one of a set of possible protocol header combinations for routing an incoming packet, the set of possible protocol header combinations being modifiable to include later-developed protocols. Based on initial bytes of the incoming packet, a pattern of protocol headers is detected, and used to select one of the plurality of RSS hash M-tuple definitions. The selected RSS hash M-tuple definition is applied as a protocol-independent arbitrary set of bits to the headers of the incoming packet to form a RSS hash M-tuple vector, which is used to compute a RSS hash. Based on the RSS hash, a particular queue is selected from a set of destination queues identified for the packet, and the packet is delivered to the selected particular queue.

Claims

1. A method, comprising:

detecting, based on packet headers of an incoming packet, one or more protocol headers of a set of possible protocol header combinations for routing the incoming packet, the set of possible protocol header combinations being modifiable to include later-developed protocols;

determining, for the incoming packet, a flow hash N-tuple definition as a protocol-independent arbitrary set of bits based on the detected one or more protocol headers;

applying the flow hash N-tuple definition to the incoming packet to form a flow hash N-tuple header vector;

computing a flow hash from the flow hash N-tuple header vector;

identifying, based on the computed flow hash, a set of destination queues for the incoming packet;

determining whether the identified set of destination queues are owned by a virtual machine; and

delivering the packet directly to the virtual machine, bypassing a hypervisor, if the identified set of destination queues are owned by the virtual machine.

2. The method of claim 1, wherein identifying the set of destination queues for the packet comprises using the flow hash as a lookup in a flow hash table.

3. The method of claim 2, further comprising:

determining whether there is a lookup miss; and

if there is a lookup miss, returning a set of default queues, the default queues being queues owned by the hypervisor.

4. The method of claim 1, further comprising:

determining, based on the one or more detected protocol headers, a receive side scaling (RSS) hash M-tuple definition as a protocol-independent arbitrary set of bits;

applying the RSS hash M-tuple definition to the header of the incoming packet to form a RSS hash M-tuple header vector;

computing a RSS hash from the RSS hash M-tuple header vector;

selecting, based on the RSS hash, a particular queue from a set of destination queues identified for the packet; and

delivering the packet to the selected particular queue.

5. The method of claim 4, wherein determining the RSS hash M-tuple definition comprises:

looking up a header protocol definition for the packet in a ternary content addressable memory (TCAM) using initial bytes of the packet; and

looking up the RSS hash M-tuple definition in a packet classifier table based on a result of the looking up in the TCAM.

6. The method of claim 4, wherein applying the RSS hash M-tuple definition to the header of the incoming packet to form the RSS hash M-tuple header vector comprises:

selecting particular bits from the header of the packet; and

compacting the selected particular bits.

7. The method of claim 4, wherein delivering the packet to the particular queue comprises bypassing the hypervisor.

8. The method of claim 4, wherein the flow hash N-tuple definition is applied to a different set of bits than the RSS hash M-tuple definition.

9. The method of claim 8, wherein the flow hash N-tuple definition is applied to an outer set of headers and the RSS hash M-tuple definition is applied to an inner set of headers.

10. A chip, comprising:

one or more memories storing a plurality of flow hash N-tuple definitions, each flow hash N-tuple definition corresponding to one of a set of possible protocol header combinations for routing an incoming packet, the set of possible protocol header combinations being modifiable to include later-developed protocols; and

one or more processors in communication with the one or more memories, the one or more processors configured to;

detect, based on a packet header of the incoming packet, a pattern of protocol headers;

determine, for the incoming packet, a flow hash N-tuple definition based on the detected pattern of protocol headers;

apply the flow hash N-tuple definition to the incoming packet to form a flow hash N-tuple header vector;

compute a flow hash from the flow hash N-tuple header vector;

identify, based on the computed flow hash, a set of destination queues for the incoming packet;

determine whether the identified set of destination queues are owned by a virtual machine; and

deliver the packet directly to the virtual machine, bypassing a hypervisor, if the identified set of destination queues are owned by the virtual machine.

11. The chip of claim 10, wherein:

the one or more memories further store a flow hash table; and

the one or more processors are further configured to identify the set of destination queues for the packet using the flow hash as a lookup in the flow hash table.

12. The chip of claim 11, wherein the one or more processors are further configured to:

determine whether there is a lookup miss; and

if there is a lookup miss, return a set of default queues, the default queues being queues owned by the hypervisor.

13. The chip of claim 10, wherein:

the one or more memories further store a plurality of receive side scaling (RSS) hash M-tuple definitions, each definition corresponding to one of the set of possible protocol header combinations for routing the incoming packet;

the one or more processors are further configured to;

select, based on the one or more detected protocol headers, one of the plurality of RSS hash M-tuple definitions;

apply the selected RSS hash M-tuple definition as a protocol-independent arbitrary set of bits to the header of the incoming packet to form a RSS hash M-tuple vector;

compute a RSS hash from the RSS hash M-tuple vector;

select, based on the RSS hash, a particular queue from a set of destination queues identified for the packet; and

deliver the packet to the selected particular queue.

14. The chip of claim 13, wherein determining the RSS hash M-tuple definition comprises:

looking up a header protocol definition for the packet in a ternary content addressable memory (TCAM) using initial bytes of the packet; and

looking up the RSS hash M-tuple definition in a packet classifier table based on a result of the looking up in the TCAM.

15. The chip of claim 13, wherein applying the RSS hash M-tuple definition to the header of the incoming packet to form the RSS hash M-tuple header vector comprises:

selecting particular bits from the header of the packet; and

compacting the selected particular bits.

16. The chip of claim 13, wherein delivering the packet to the selected particular queue comprises bypassing the hypervisor.

17. The chip of claim 13, wherein the flow hash N-tuple definition is applied to a different set of bits than the RSS hash M-tuple definition.

18. The chip of claim 17, wherein the flow hash N-tuple definition is applied to an outer set of headers and the RSS hash M-tuple definition is applied to an inner set of headers.

19. A system, comprising:

a hypervisor having a first plurality of receive queues;

a virtual machine having a second plurality of receive queues; and

a chip coupled to the hypervisor and the virtual machine, wherein the chip is configured to;

receive an incoming packet;

determine, for the incoming packet, a flow hash N-tuple definition;

apply the flow hash N-tuple definition to the incoming packet to form a flow hash N-tuple header vector;

compute a flow hash from the flow hash N-tuple header vector;

identify, based on the computed flow hash, a set of destination queues for the incoming packet;

determine whether the identified set of destination queues are owned by a virtual machine; and

deliver the packet directly to the virtual machine, bypassing the hypervisor, if the identified set of destination queues are owned by the virtual machine.

20. The system of claim 19, wherein the chip is further configured to:

look up a definition for the packet in a ternary content addressable memory (TCAM) using initial bytes of the packet;

look up a receive side scaling (RSS) hash M-tuple definition in a packet classifier table based on a result of the looking up in the TCAM;

apply the RSS hash M-tuple definition to initial bits of the incoming packet to form an RSS hash M-tuple vector;

compute a RSS hash from the RSS hash M-tuple vector;

select, based on the RSS hash, a particular queue from the set of destination queues identified for the packet; and

deliver the packet to the selected particular queue.