Congestion avoidance in multipath routed flows using virtual output queue statistics

• US 10,069,734 B1
• Filed: 08/09/2016
• Issued: 09/04/2018
• Est. Priority Date: 08/09/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Singh, Bijendra
• Primary Examiner(s): Gidado, Rasheed
• Application Number:
  US15/232,727
• Time in Patent Office: 756 Days
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

Disclosed are techniques regarding interfaces, each configured to output network packets. The techniques can regard a memory for storing multipath groups, virtual output queues, and a histogram table for storing statistical information associated with network packets to be output by interfaces. The techniques can include generating a shared-interface list including a member that represents a union of interfaces of at least some of the multipath groups, wherein the multipath groups of the member share at least one of the interfaces. The techniques can include associating the histogram table with the member. The techniques can include collecting the statistical information pertaining to network packets indicated by information stored in one of the virtual output queues, populating the histogram table with the statistical information, and determining that one of the interfaces is congested based on the statistical information.

Claims

1. A device, comprising:

interfaces, each configured to output network packets;

a memory storing;

multipath groups, each associated with some of the interfaces;

virtual output queues, each associated with one of the interfaces and configured to store information indicating network packets to be output by an associated interface; and

histogram tables;

shared-interface discovery logic configured to;

generate a shared-interface list including members that each represents a union of interfaces between at least some of the multipath groups, wherein the multipath groups of the each member share at least one of the interfaces; and

associate each of the histogram tables with one of the members;

network routing logic configured to;

generate a hash value for each network packet to be output by an interface of the device;

select one of the interfaces to output each of the network packets including determining which of the interfaces is associated with a hash reference range that includes the hash value generated for the network packet; and

statistics collection logic configured to;

determine whether a number of network packets indicated by information of one of the virtual output queues meets a first threshold;

upon determining that the number of network packets indicated by information of one of the virtual output queues meets the first threshold, populate one of the histogram tables with counts of hash values generated for the network packets, wherein the one histogram table is selected based on determining that a network packet to be output by an interface that is included in a member of the shared-interface list, wherein the included interface is associated with the one of the virtual output queues; and

determine whether one of the interfaces is congested based on the counts of hash values.

2. The device of claim 1, wherein the statistics collection logic is further configured to populate one of the histogram tables with counts of network packets associated with specific hash values, the counts populated for each of a plurality of time periods.

3. The device of claim 2, wherein the determining whether one of the interfaces is congested includes determining whether ones of the counts of hash values meet a second threshold over the plurality of time periods.

4. The device of claim 1, wherein the determining whether one of the interfaces is congested includes determining whether one of the counts of hash values meets a second threshold.

5. The device of claim 1, wherein the device further comprises a processor, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), Digital Signal Processor (DSP), microcontroller, microprocessor, System on a Chip (SoC), or Complex Programmable Logic Device (CPLD).

6. A device, comprising:

interfaces, each configured to output network packets;

a memory for storing;

multipath groups, each associated with some of the interfaces;

virtual output queues, each associated with one of the interfaces and configured to store information indicating network packets to be output by the associated interface; and

a table for storing statistical information associated with network packets;

shared-interface discovery logic configured to;

generate a shared-interface list including a member that represents a union of interfaces of at least some of the multipath groups, wherein the multipath groups of the member share at least one of the interfaces; and

associate the table with the member; and

statistics collection logic configured to;

collect the statistical information pertaining to network packets indicated by information stored in one of the virtual output queues;

populate the table with the statistical information; and

determine that one of the interfaces is congested based on the statistical information.

7. The device of claim 6, further comprising:

congestion avoidance logic configured to modify routing of network packets to the congested interface.

8. The device of claim 6, wherein the table is selected based on determining that a network packet to be output by an interface is included in a member of the shared-interface list, wherein the interface is associated with a virtual output queue.

9. The device of claim 6, wherein the shared-interface list includes several members and each of the interfaces belongs to only one member of the shared-interface list.

10. The device of claim 6, wherein the device includes network routing logic configured to generate a hash value for each network packet to be output by the device.

11. The device of claim 10, wherein each interface within a multipath group is associated with a hash reference range.

12. The device of claim 11, wherein the network routing logic is further configured to select an interface of a multipath group to output each of the network packets, the selecting including determining whether the hash value generated for each network packet is included in the hash reference range associated with the interface.

13. The device of claim 12, further comprising congestion avoidance logic configured to modify a hash reference range associated with a congested interface.

14. The device of claim 13, wherein the modifying the hash reference range includes modifying hash reference ranges for an interface of each multipath group within a member of the shared-interface list.

15. A method, comprising:

identifying members of a shared-interface list, wherein each member represents a union of interfaces of two multipath groups that share at least one interface of a network device, wherein each multipath group indicates a group of interfaces of the network device;

associating each of the shared-interface list members with a respective histogram table, each histogram table including counters, each counter being associated with a hash value;

generating a hash value for each one of network packets to be output by one of the interfaces of the network device;

selecting a corresponding interface to output each of the network packets by comparing the hash value generated for each network packet with a hash reference range associated with each of the interfaces;

determining, using information in a virtual output queue of the network device, whether a number of network packets to be output by one of the interfaces meets a first threshold;

upon determining that the number of network packets to be output by the one of the interfaces meets the first threshold, updating a corresponding counter value of a histogram table associated with a shared-interface list member, the shared-interface list member including a multipath group including the one interface; and

determining whether the counter value of the associated histogram table indicates that the one interface is congested.

16. The method of claim 15, wherein the associated histogram table includes counters for each of a plurality of time periods;

and

the method further comprises updating the associated histogram table with counts of network packets for each of the plurality of time periods.

17. The method of claim 16, wherein the determining whether the counter value of the associated histogram table indicates that the one interface is congested includes determining whether ones of the counts that are associated with a single hash value meet a threshold for each of the plurality of time periods.

18. The method of claim 15, wherein a first congestion avoidance technique is initiated in response to determining that two hash values are contributing to the congestion and a second congestion avoidance technique is initiated in response to determining that three or more hash values are contributing to the congestion.

19. The method of claim 18, wherein the first congestion avoidance technique includes modifying hash reference ranges associated with two interfaces.

20. The method of claim 18, wherein the second congestion avoidance technique includes modifying hash reference ranges associated with three interfaces.