Congestion mitigation in networks using flow-based hashing

• US 10,187,309 B1
• Filed: 08/20/2012
• Issued: 01/22/2019
• Est. Priority Date: 08/20/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vincent, Pradeep, Marr, Michael David, Klein, Matthew D., McKelvie, Samuel J.
• Primary Examiner(s): Amara, Mohamed K
• Application Number:
  US13/589,822
• Time in Patent Office: 2,346 Days
• Field of Search: 370235, 370229, 370241, 370230
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/11 Identifying congestion

Abstract

Disclosed are various embodiments for mitigating congestion in networks employing flow-based hashing to assign flows to routes. A flow of packets is sent from a source endpoint to a destination endpoint by way of a network. The flow of packets is associated with flow identification information. It is detected whether congestion is affecting the flow of packets in the network. A perturbation to the flow identification information for the flow of packets is effected in response to determining that congestion is affecting the flow of packets in the network.

Claims

1. A non-transitory computer-readable medium comprising machine readable instructions that, when executed, cause a network device to at least:

send a flow of packets from a source endpoint to a destination endpoint by way of a network, the flow of packets being associated with flow identification information;

obtain network congestion information from a network monitoring service;

detect that congestion is affecting the flow of packets in the network and determine, based at least in part on the network congestion information, whether the congestion experienced by the flow of packets may be caused by flow collisions; and

effect a perturbation to a port field in the flow identification information for the flow of packets in response to determining that congestion is affecting the flow of packets in the network and in response to a determination that the congestion may be caused by flow collisions, the machine readable instructions that effect the perturbation being configured to cause the network device to at least;

detect an interruption in the flow of packets; and

schedule the perturbation relative to the interruption.

2. A system, comprising:

at least one device connected to a network, the at least one device comprising a processor and a memory; and

machine readable instructions stored in the memory that, when executed by the processor, cause the at least one device to at least;

send a flow of packets from a source endpoint to a destination endpoint by way of the network, the flow of packets being associated with flow identification information;

detect whether congestion is affecting the flow of packets in the network; and

effect a perturbation to the flow identification information for the flow of packets in response to determining that congestion is affecting the flow of packets in the network.

3. The system of claim 2, wherein the flow of packets corresponds to a transmission control protocol (TCP) flow.

4. The system of claim 2, wherein the machine readable instructions, when executed, further cause the at least one device to at least detect that congestion is affecting the flow of packets based at least in part on congestion statistics maintained by at least one of the source endpoint or the destination endpoint.

5. The system of claim 2, wherein the machine readable instructions, when executed, further cause the at least one device to at least:

detect an interruption in the flow of packets; and

schedule the perturbation relative to the interruption.

6. The system of claim 2, wherein the machine readable instructions that cause the at least one device to effect the perturbation further cause the at least one device to update a state associated with the flow of packets in the network.

7. The system of claim 2, wherein the flow identification information comprises a source port and a destination port, and the machine readable instructions that cause the at least one device to effect the perturbation further cause the at least one device to change at least one of the source port or the destination port.

8. The system of claim 2, wherein the machine readable instructions that cause the at least one device to effect the perturbation further cause the at least one device to notify the destination endpoint of the perturbation.

9. The system of claim 2, wherein the machine readable instructions, when executed, further cause the at least one device to at least:

obtain network congestion information from a network monitoring service;

determine, based at least in part on the network congestion information, that the congestion experienced by the flow of packets may be caused by flow collisions; and

refrain from effecting the perturbation in response to determining that the congestion experienced by the flow of packets is not caused by flow collisions.

10. The system of claim 2, wherein the machine readable instructions that cause the at least one device to effect the perturbation further cause the at least one device to at least:

notify the destination endpoint of the perturbation;

obtain an acknowledgement from the destination endpoint; and

implement the perturbation in response to the acknowledgement.

11. A method, comprising:

obtaining, in at least one device coupled to a first network, a second network, or both, a plurality of first flows of packets sent via the first network, individual ones of the first flows of packets being associated with respective first flow identification information;

mapping, in the at least one device, each one of the first flows of packets into a corresponding one of a plurality of second flows of packets, individual ones of the second flows of packets being associated with respective second flow identification information, the respective second flow identification information including a same second source endpoint and a same second destination endpoint;

sending, in the at least one device, the second flows of packets via the second network;

detecting, in the at least one device, whether at least one of the first flows of packets is experiencing congestion; and

effecting, in the at least one device, a perturbation to the respective second flow identification information corresponding to the at least one of the first flows of packets in response to determining that the at least one of the first flows of packets is experiencing congestion.

12. The method of claim 11, further comprising:

detecting, in the at least one device, a temporary interruption in the at least one of the first flows of packets; and

scheduling, in the at least one device, the perturbation relative to a temporary interruption in the at least one of the first flows of packets.

13. The method of claim 11, wherein the first network is an overlay network, and the second network is a substrate network.

14. The method of claim 11, wherein effecting, in the at least one device, the perturbation further comprises changing, in the at least one device, a port field in the respective second flow identification corresponding to the at least one of the first flows of packets.

15. The method of claim 11, wherein effecting, in the at least one device, the perturbation further comprises changing, in the at least one device, a hashing function employed to generate a port field in the respective second flow identification corresponding to the at least one of the first flows of packets.

16. The method of claim 11, wherein effecting, in the at least one device, the perturbation further comprises changing, in the at least one device, a hash seed used by a hashing function employed to generate a port field in the respective second flow identification corresponding to the at least one of the first flows of packets.

17. The method of claim 11, wherein effecting, in the at least one device, the perturbation further comprises notifying, in the at least one device, the same second destination to implement the perturbation.

18. The method of claim 11, wherein effecting, in the at least one device, the perturbation further comprises:

notifying, in the at least one device, the same second destination endpoint of the perturbation;

obtaining, in the at least one device, an acknowledgement from the same second destination endpoint; and

implementing, in the at least one device, the perturbation in response to the acknowledgement.

19. The method of claim 11, wherein the detecting further comprises detecting, in the at least one device, whether the at least one of the first flows of packets is experiencing congestion based at least in part on congestion statistics maintained by at least one of the same second source endpoint or the same second destination endpoint.

20. The method of claim 11, further comprising:

determining, in the at least one device, whether all of the first flows of packets are experiencing congestion; and

refraining from effecting, in the at least one device, the perturbation in response to determining that all of the first flows of packets are experiencing congestion.

21. The method of claim 11, further comprising:

obtaining, in the at least one device, network congestion information from a network monitoring service;

determining, in the at least one device, based at least in part on the network congestion information, whether the congestion experienced by the at least one of the first flows of packets is caused by flow collisions; and

refraining from effecting the perturbation, in the at least one device, in response to determining that the congestion experienced by the at least one of the first flows of packets is not caused by flow collisions.