CONGESTION SENSITIVE PATH-BALANCING

• US 20170078203A1
• Filed: 11/28/2016
• Published: 03/16/2017
• Est. Priority Date: 11/24/2014
• Status: Abandoned Application

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Judge, Alan Michael, Wilson, Matthew Shawn
• Application Number:
  US15/362,742
• Publication Number:
  US 20170078203A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

Encapsulated packets may be generated for different packets transmitted between a source instance and destination instance in a computer system. The source instance and destination instance may be implemented by different physical hosts linked by multiple network paths. Congestion of the multiple network paths may be determined and path-balancing polices may be implemented in response to the determined congestion. Each encapsulation packet comprises contents of a corresponding packet, and one or more data values selected in accordance with a path-balancing policy. The data values added to one encapsulation packet may differ from those added to another. Different network paths to the destination may be selected for different encapsulation packets of a given transmission based at least in part on the added data values.

Claims

1. A computer-implemented method, comprising:

implementing, at a first computer system, a path-balancing policy at a virtualization layer of the first computer system in response to network congestion by at least;

generating a first encapsulated packet based at least in part on a first packet of a set of the packets, the first encapsulated packet including a first set of values that cause the first packet to be routed along a first network path towards a second computer system; and

generating a second encapsulated packet based at least in part on a second packet of the set of packets, the second encapsulated packet including a second set of values that cause the second packet to be routed along a second network path towards the second computer system.

2. The computer-implemented method of claim 1, wherein the set of packets further comprises a network transmission from virtual machine instance supported by the first computer system.

3. The computer-implemented method of claim 1, wherein one or more routing devices direct the first encapsulated packet along the first network path based at least in part on the first set of values and the one or more routing devices direct the second encapsulated packet along the second path based at least in part on the second set of values.

4. The computer-implemented method of claim 1, wherein the first encapsulated packet includes the first set of values in a header of the first encapsulated packet and second encapsulated packet includes the second set of values in a header of the second encapsulated packet.

5. A system, comprising:

one or more processors; and

memory including executable instructions that, as a result of being executed by the one or more processors, cause the system to;

obtain a set of packets from a first computing instance directed towards a second computing instance over a network;

determine to enable path-balancing for a portion of the set of packets;

generate a set of encapsulated packets corresponding to the portion of packets of the set of packets, the set of encapsulated packets including additional information that when processed by a routing device causes a first encapsulated packet of the set of packets to travel a first path and causes a second encapsulated packet to travel a second path that is distinct from the first path; and

transmit the set of encapsulated packets to the second computing instance.

6. The system of claim 5, wherein the memory further includes executable instructions that, as a result of being executed by the one or more processors, cause the system to:

obtain an indication of network congestion from the second computing instance based at least in part on a particular packet of the set of packets.

7. The system of claim 6, wherein the indication of network congestion includes a rate at which one or more packets of the set of packets are received at the second computing instance.

8. The system of claim 5, wherein the network further comprises a plurality of physical network connected between computing devices on the network creating a plurality of paths between the first computing instance and the second computing instance.

9. The system of claim 5, wherein the network is a Clos network.

10. The system of claim 9, wherein the additional information indicates a port number.

11. The system of claim 5, wherein the first computing instance is a virtual computing instance supported by a hypervisor.

12. The system of claim 5, wherein the executable instructions that cause the system to determine to enable path-balancing further include executable instructions that, as a result of being executed by the one or more processors, cause the system to enable path-balancing based at least in part on a failure rate of the set of packets reaching the second computing instance.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

detect an event triggering a path balancing policy;

encapsulate a first packet within a first encapsulated packet including a first set of values determine based at least in part on a path-balancing policy, the first set of values causing one or more computing devices to direct the first encapsulated packet along a first network path;

encapsulate a second packet within a second encapsulated packet including a second set of values determine, based at least in part on the path-balancing policy, the second set of values causing the one or more computing devices to direct the second encapsulated packet along a second network path, the first network path and the second network path having at least one different portion; and

provide the first and second encapsulated packets the one or more routing devices.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to implement the path-balancing policy as a result of a number of packets in a queue exceeds a threshold.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to receive an indication from a routing device that the number of packets has exceeded the threshold.

16. The non-transitory computer-readable storage medium of claim 15, wherein the routing device is a top of rack switch.

17. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to determine the first set of values and the second set of values by at least selecting values of the first set of values and the second set of values pseudo-randomly.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to determine, based at least in part on a round robin strategy, the first set of values and the second set of values.

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to determine, based at least in part on an indication of congestion of a particular routing device such that the first network path and the second network path are not directed to the particular routing device, the first set of values and the second set of values.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to determine, based at least in part on information obtained from a computer system, the first set of values and the second set of values.