Flow collision avoidance

• US 10,182,010 B1
• Filed: 08/20/2012
• Issued: 01/15/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,814
• Time in Patent Office: 2,339 Days
• Field of Search: 370235, 370229, 370241, 370230
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2483 involving identification of individual flows

Abstract

Disclosed are various embodiments for avoiding flow collisions 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 is associated with flow identification information including, for example, a source port, a source network address, a destination port, and a destination address. It is determined whether to perturb the flow identification information for the flow to avoid flow collisions caused by flow-based hashing performed in the network. A state associated with the flow is updated to effect a perturbation to the flow identification information for the flow if the flow identification information for the flow is to be perturbed.

Claims

1. A non-transitory computer-readable medium embodying a program executable in at least one network device, comprising:

code that sends 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 including a source port, a source network address, a destination port, and a destination address;

code that determines whether to perturb, according to a random process, the flow identification information for the flow of packets to avoid flow collisions caused by flow-based hashing performed in the network;

code that determines whether an interruption in the flow of packets has occurred; and

code that effects a perturbation to the flow identification information for the flow of packets in response to determining that the flow identification information for the flow of packets is to be perturbed and in response to determining that the interruption in the flow of packets has occurred, the code that effects the perturbation being configured to change at least one of the source port or the destination port in the flow identification information.

2. A system, comprising:

a network device connected to a network, the network device being configured to;

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;

determine, based at least in part on at least one of a predefined interval, a random process, or detecting congestion in the network, whether to perturb the flow identification information for the flow of packets to avoid flow collisions caused by flow-based hashing performed in the network; and

update a state associated with the flow of packets to effect a perturbation to the flow identification information for the flow of packets in response to determining that the flow identification information for the flow of packets is to be perturbed.

3. The system of claim 2, wherein the flow identification information includes a source port, a source network address, a destination port, and a destination address.

4. The system of claim 2, wherein the flow identification information includes a virtual local area network (VLAN) tag.

5. The system of claim 2, wherein the flow corresponds to a transmission control protocol (TCP) flow or a user datagram protocol (UDP) flow.

6. The system of claim 2, wherein the sending comprises forwarding the flow of packets to an intermediate destination on the network.

7. The system of claim 2, wherein the flow of packets corresponds to an overlay network flow.

8. The system of claim 2, wherein updating the state associated with the flow of packets comprises notifying the source endpoint of the perturbation.

9. The system of claim 2, wherein updating the state associated with the flow of packets comprises implementing a change to an active connection associated with the flow of packets, the active connection being maintained by a network stack.

10. The system of claim 2, wherein updating the state associated with the flow of packets comprises notifying the destination endpoint of the perturbation.

11. The system of claim 10, wherein the network device is configured to effect the perturbation in response to receiving an acknowledgement from the destination endpoint.

12. The system of claim 2, wherein the destination endpoint is configured to detect the perturbation by monitoring a range of port addresses associated with the flow of packets.

13. The system of claim 2, wherein the perturbation implements a change to the source port, the destination port, or both.

14. The system of claim 2, wherein the network device is configured to determine whether to perturb the flow identification information according to a randomized process.

15. The system of claim 2, wherein the network device is further configured to:

detect an interruption in the flow of packets; and

effect the perturbation relative to the interruption in the flow of packets.

16. The system of claim 15, wherein the network device is further configured to effect the perturbation before the interruption is detected in response to an expiration of a time limit.

17. A method, comprising:

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

mapping, in the at least one device, the first flow of packets into a second flow of packets, the second flow of packets being associated with second flow identification information relative to the second network;

determining, in the at least one device, based at least in part on at least one of a predefined interval, a random process, or detecting congestion in the second network, whether to perturb the mapping to avoid flow collisions caused by flow-based hashing performed in the second network;

effecting, in the at least one device, a perturbation to the mapping in response to determining that the mapping is to be perturbed; and

sending, in the at least one device, the second flow of packets via the second network.

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

19. The method of claim 17, further comprising generating, in the network device, a portion of the second flow identification information by hashing at least a portion of the first flow identification information.

20. The method of claim 19, wherein the at least a portion of the first flow identification information includes a source port, a source network address, a destination port, and a destination address.

21. The method of claim 19, wherein effecting the perturbation further comprises changing a hash function employed in the hashing.

22. The method of claim 19, wherein effecting the perturbation further comprises changing a hash seed employed in the hashing.

23. The method of claim 17, wherein determining whether to perturb the mapping is based at least on part on whether a perturbation request is obtained from an overlay endpoint associated with the first flow of packets.

24. The method of claim 17, wherein determining whether to perturb the mapping is based at least on part on a random process.

25. The method of claim 17, wherein determining whether to perturb the mapping is based at least on part on whether the first flow of packets has been temporarily interrupted.

26. The method of claim 17, wherein determining whether to perturb the mapping is based at least on part on an expiration of a predefined time interval.

27. The method of claim 17, wherein effecting the perturbation further comprises changing a port field in the second flow identification information.

28. The method of claim 17, wherein mapping further comprises encapsulating, in the at least one device, the first flow of packets into the second flow of packets by adding additional framing to individual ones of the first flow of packets.