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

Patent metadata

Field	Value
Publication number	US-9716592-B1
Application number	US-201113157925-A
Country	US
Kind code	B1
Filing date	Jun 10, 2011
Priority date	Jun 10, 2011
Publication date	Jul 25, 2017
Grant date	Jul 25, 2017

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.

First claim

The invention claimed is:

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.

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

Assignees

• Mandal Subhasree
• Singh Arjun
• Naik Ashish
• Google Inc

Inventors

• Mandal Subhasree
• Singh Arjun
• Naik Ashish

Classifications

• H04L69/14

  Multichannel or multilink protocols · CPC title

• H04L45/245

  Link aggregation, e.g. trunking · CPC title

• H04L67/1023

  based on a hash applied to IP addresses or costs · CPC title

• H04L45/24

  Multipath · CPC title

• H04L45/7453

  using hashing · CPC title