Traffic distribution over multiple paths in a network while maintaining flow affinity

• US 9,716,592 B1
• Filed: 06/10/2011
• Issued: 07/25/2017
• Est. Priority Date: 06/10/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Singh, Arjun, Mandal, Subhasree, Naik, Ashish
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): Rivas, Salvador E
• Application Number:
  US13/157,925
• Time in Patent Office: 2,237 Days
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

System and methods for efficiently distributing data packets in a multi-path network while maintaining flow affinity are provided. In one aspect, a system and method includes calculating hash values for distributing different flows, or sets of flows, of data packets received at a routing device. The hash value is calculated not only using information in the data packets, but also based on additional information that is determined based on an N-bit derived from the data packets. In some cases, calculating a hash value based on the additional information increases the entropy of the hashing function, thus enabling a routing device to distribute different flows of data packets over a greater number of network paths. Each routing device can derive a different, and randomly generated N-bit key while maintaining flow affinity for each received data packet in a given flow of data packets.

Claims

1. A method for routing data packets in a network of interconnected networking devices, the method comprising:

receiving, at one or more input ports of a first networking device, a plurality of data packets, each of the received data packets including one or more fields of information for routing that respective data packet;

generating, with a processor, an N-bit key for each of the received data packets by selecting one or more bits from the one or more fields of information in each respective data packet;

selecting from a table, one or more tag fields for each of the received data packets, based on the generated N-bit key for the respective data packet;

replacing bit values of one or more predetermined fields in a header of each of the plurality of data packets with replacement bit values obtained from one or more of the tag fields selected from the table using the N-bit key generated for the respective data packet;

computing a hash value for each of the received data packets based on the one or more fields of information and the replacement bit values;

selecting one of a plurality of outgoing ports of the first networking device for routing each of the received data packets to a second networking device via the network, the outgoing port being selected for each data packet based on the computed hash value for that respective data packet; and

outputting each of the received data packets to the second networking device via the selected outgoing port.

2. The method of claim 1, wherein the received data packets include at least one data packet belonging to a first flow of data packets and at least one data packet belonging to a second flow of data packets.

3. The method of claim 2, wherein the outgoing port selected for the at least one data packet belonging to the first flow of data packets is different than the outgoing port selected for the at least one data packet belonging to the second flow of data packets.

4. The method of claim 1, wherein at least one of the one or more fields of information included in each of the received data packets is selected from the group consisting of a source address field, a destination address field, a source port field, a destination port field, and a protocol field.

5. The method of claim 1, wherein selecting one or more bits from the one or more fields of information in each respective data packet to generate the N-bit key for each data packet further comprises randomly selecting bits from the one or more fields of information in at least one of the received data packets.

6. The method of claim 1, wherein the N-bit key generated for each data packet includes at least one bit selected from one of the fields of information for routing each respective data packet.

7. The method of claim 1, further comprising:

tagging, at the first networking device, each of the received plurality of data packets with the one or more selected tag fields and routing the tagged data packets to the second networking device;

receiving the tagged data packets at one or more input ports of the second networking device;

selecting, based on the data contained in the one or more tag fields in the tagged data packets, one or more outgoing ports of the second networking device; and

routing the tagged data packets further into the network via the selected one or more outgoing ports of the second networking device.

8. The method of claim 7, wherein routing the tagged data packets further into the network via the selected one or more outgoing ports of the second networking device further comprises modifying the one or more tag fields of the tagged data packets and routing the tagged data packets including the modified one or more tag fields further into the network via the selected one or more outgoing ports.

17. The method of claim 1, wherein selecting one or more tag fields further comprises:

determining which of the one or more tag fields map to the N-bit key in a look-up table.

9. A system including a plurality of routing devices for an interconnection network, each routing device of the plurality of routing devices comprising:

one or more input ports coupled to one or more output ports of other routing devices in the interconnection network, the input ports being configured to receive data packets from the one or more output ports of the other routing devices;

memory for storing information regarding the data packets; and

a processor coupled to the one or more input ports and the memory, the processor being configured to;

receive at the one or more input ports a plurality of data packets, each of the received data packets including one or more fields of information for routing each the respective data packet;

generate an N-bit key for each of the received data packets by selecting one or more bits from the one or more fields of information in each respective data packet;

select from a table, one or more tag fields for each of the received data packets, based on the generated N-bit key for the respective data packet;

replace bit values of one or more predetermined fields in a header of each of the plurality of data packets with bit values of one or more of the selected tag fields selected from the table based on the N-bit key generated for the respective data packet;

compute a hash value for each of the received data packets based on the one or more fields of information and the replaced bit values of the one or more predetermined fields in the header of the respective data packet;

select one or more output ports for routing one or more of the received data packets to the one or more input ports of a downstream routing device, the one or more output ports being selected for each received data packet based on the computed hash value for that respective data packet; and

output one or more of the received data packets via the selected one or more output ports over the interconnection network to the downstream routing device.

10. The system of claim 9, wherein the interconnection network is a CLOS interconnection network.

11. The system of claim 9, wherein the interconnection network is an Equal Cost Multiple Path interconnection network.

12. The system of claim 9, wherein the received data packets include data packets belonging to a first flow of data packets and data packets belonging to a second flow of data packets.

13. The system of claim 9, wherein the processor is further configured to select a first outgoing port for the first flow of data packets and a second outgoing port for the second flow of data packets.

14. The system of claim 9, wherein at least one of the one or more fields of information included in each of the received data packets is selected from the group consisting of a source address field, a destination address field, a source port field, a destination port field, and a protocol field.

15. The system of claim 9, wherein the one or more bits selected from the one or more fields of information in each of the received data packets to generate the N-bit key for each data packet further includes bits randomly selected from the one or more fields of information in at least one of the received data packets.

16. A non-transitory computer readable recording medium having instructions stored thereon, the instructions, when executed by a processor, cause the processor to perform the operations of:

receiving a plurality of data packets over a network, each of the received data packets including one or more fields of information for routing the respective data packet further into the network;

generating, an N-bit key for each of the received data packets by selecting one or more bits from the one or more fields of information in the respective data packet;

selecting from a table, one or more tag fields for each of the received data packets, based on the generated N-bit key for the respective data packet;

replacing bit values of one or more predetermined fields in a header of each of the plurality of data packets with bit values of one or more of the selected tag fields selected from the table;

computing a hash value for each of the received data packets based on the one or more fields of information and the replaced bit values of the one or more predetermined fields in the header of each respective data packet;

selecting a downstream networking device from a plurality of networking devices for each of the received data packets, the downstream networking device for each received data packet being selected based on the computed hash value for each respective data packet; and

outputting each of the received data packets to the selected downstream networking device over the network.