Congestion avoidance in multipath routed flows

• US 10,015,096 B1
• Filed: 06/20/2016
• Issued: 07/03/2018
• Est. Priority Date: 06/20/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): Chery, Dady
• Application Number:
  US15/187,486
• Time in Patent Office: 743 Days
• Field of Search: 370209, 370229-235
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• 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 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports

Abstract

Techniques are disclosed regarding receiving a plurality of flows of network packets and determining, by processing logic of a device, a hash value for each of the network packets of the flows, wherein the hash value indicates the flow of network packets that a network packet belongs to. Based on the hash value, one of a plurality of interface ports of a multipath group of the device can be selected for output of network packets from two of the flows of network packets. Network packets from the two flows of network packets to be output by the interface port can be stored. Upon determining that a number of packets stored from the one of the two flows of network packets meets a first threshold, one of the two flows of network packets can be identified as a congestion contributing flow.

Claims

1. A network device, comprising:

a plurality of output interface ports;

a memory storing;

a plurality of multipath groups, each multipath group associated with respective ones of the output interface ports;

a plurality of output queues, each output queue corresponding to a respective one of the output interface ports and each output queue storing information indicative of network packets to be output by the network device via the respective output interface port;

a plurality of congestion control blocks, each congestion control block associated with a respective one of the multipath groups and each congestion control block storing;

a congested output interface port identifier,

two identifiers, each associated with a flow of network packets, and

two counters, each associated with one of the two identifiers;

congestion control block update logic configured to;

determine congestion experienced at a particular one of the output queues;

inspect network packets stored at the particular output queue to determine, for each network packet, a group identifier and a flow of network packets identifier;

update a congestion control block of the plurality of congest control blocks corresponding to each of the multipath groups associated with the network packets from the particular output queue with flow identification information and network packet count information; and

network flow detection logic configured to;

determine, using the congestion control block for an multipath group, whether a value of a counter of the two counters meets a threshold; and

upon determining that a counter of the two counters meets the threshold, identify, using an identifier of the two identifiers, a flow of network packets contributing to the congestion experienced at the particular output queue.

2. The network device of claim 1, further comprising:

congestion avoidance logic configured to, based on the identifying the flow of network packets contributing to the congestion experienced at the particular output queue, route the flow of network packets to an alternate output interface port from an multipath group, an output interface port corresponding to the particular output queue being identified from the plurality of output interface ports as congested based on the congested output interface identifier.

3. The network device of claim 2, wherein the congestion avoidance logic is further configured to change two flows of network packets from being associated with a single output interface port from a multipath group to two separate output interfaces from the multipath group, the two flows of network packets indicated by the two identifiers of the congestion control block associated with the multipath group.

4. The network device of claim 2, wherein the congestion avoidance logic is further configured to:

modify ranges of hash reference values, wherein each range of hash reference values is associated with selection of an output interface port by one of the multipath groups;

wherein the flow of network packets identifier includes a hash value; and

wherein the modifying includes reducing a range of hash reference values associated with an output interface port indicated by the congested output interface identifier to include a hash value associated with a flow of network packets indicated by a first identifier of the two identifiers of a congestion control block associated with the multipath group, and not to include a hash value associated with a flow of network packets indicated by a second identifier of the two identifiers of the congestion control block associated with the multipath group.

5. The network device of claim 1, wherein the congestion control block update logic is further configured to:

determine a count of network packets stored within the particular output queue over a time period, the network packets each sharing a same flow of network packets identifier and a same group identifier;

update an identifier of the two identifiers of a congestion control block associated with one of the multipath groups indicated by the group identifier with the same flow of network packets identifier; and

update a counter of the congestion control block associated with the multipath group indicated by the group identifier with the count.

6. A device, comprising:

a plurality of output interface ports;

a memory storing;

a plurality of multipath groups, each multipath group associated with respective ones of the output interface ports;

a plurality of output queues, each output queue corresponding to a respective one of the plurality of output interface ports, and each output queue storing information indicative of network packets to be output by the device via the corresponding output interface port;

a plurality of congestion control blocks, each congestion control block associated with a respective one of the multipath groups and each congestion control block storing statistical information for the associated multipath group;

congestion control block update logic configured to;

determine congestion at one of the output queues;

update the statistical information stored at each congestion control block of the plurality of congestion control blocks with information determined based on network packet information in the congested output queue; and

network flow detection logic configured to identify, using the congestion control block for a particular one of the multipath groups, a flow of network packets contributing to congestion at the congested output queue.

7. The device of claim 6, wherein the congestion control block logic is configured to determine the congestion based on a number of network packets indicated by information in the output queue.

8. The device of claim 6, further comprising congestion avoidance logic configured to, based on the identifying the flow of network packets contributing to the congestion, route the flow of network packets to an alternate output interface port from the particular multipath group.

9. The device of claim 8, further comprising:

processing logic configured to generate a hash value based on information associated with a network packet received by the device, wherein the hash value is used to select an output interface port from several output interfaces ports associated with the particular multipath group.

10. The device of claim 9, wherein each output interface port associated with the particular multipath group is associated with a range of reference hash values, the output interface ports selected to route each network packet received by the device being based on a determination of whether the hash value of each network packet received by the device falls within one of the ranges of hash reference values;

and

the device further comprising congestion avoidance logic configured to modify, based on statistical information from the congestion control block for the particular multipath group, a range of hash reference values associated with an output interface port selected by the particular multipath group to route a flow of network packets to an alternate output port by the particular multipath group.

11. The device of claim 6, wherein the device includes at least one of:

a processor, microcontroller, system on a chip, field programmable gate array, complex programmable logic device, or digital signal processor.

12. The device of claim 6, wherein the memory comprises sets of output queues, each set of output queues comprising a plurality of output queues, a certain output queue of each plurality of output queues being associated with a certain output interface port of the plurality of output interface ports.

13. The device of claim 6, wherein the congestion control block update logic is further configured to select which congestion control block to update based on a group identifier associated with network packets in the congested output queue.

14. The device of claim 6, wherein the device is configured to store network packets within the plurality of output queues associated, each network packet associated with a group identifier and a flow identifier.

15. The device of claim 14, wherein the statistics information includes two identifiers, each identifier determined based on the identifiers associated with network packets of the congested output queue.

16. The device of claim 15, further comprising congestion avoidance logic configured to, based on the identifying the flow of network packets contributing to the congestion, modify routing one of two flows of network packets identified by the two identifiers of the statistics information, wherein the modifying the routing includes routing the two flows of network packets to two different output interface ports of the plurality of output interface ports.

17. A method, comprising:

receiving a plurality of flows of network packets;

determining, by processing logic of a device, a hash value for each of the network packets of the flows, wherein the hash value indicates the flow of network packets that a network packet belongs to;

selecting, based on the hash value, one of a plurality of interface ports of a multipath group of the device for output of network packets from two of the flows of network packets;

storing, at an output queue of the device, information associated with network packets from the two flows of network packets to be output by the interface port;

determining whether a number of packets stored by identifiers, in the output queue, from one of the two flows of network packets, meets a first threshold; and

upon determining that the number of packets stored from the one of the two flows of network packets meets the first threshold, identifying the one of the two flows of network packets as a congestion contributing flow.

18. The method of claim 17, further comprising outputting the congestion contributing flow and the other of the two flows on different interface ports.

19. The method of claim 18, wherein the different interface ports are associated with different output queues.

20. The method of claim 17, wherein the identifying includes identifying the two flows of network packets based on a total number of packets stored via the output queue for a time period.