Managing encoded multi-part communications

• US 8,972,603 B1
• Filed: 11/15/2013
• Issued: 03/03/2015
• Est. Priority Date: 03/03/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brandwine, Eric Jason
• Primary Examiner(s): Whipple, Brian P
• Assistant Examiner(s): Chambers, Michael A
• Application Number:
  US14/081,980
• Time in Patent Office: 473 Days
• Field of Search: None
• US Class Current: 709/238
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 2001/0096 Channel splitting in point-to-point links
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols

Abstract

Techniques are described for providing managed computer networks. In some situations, the techniques include managing communications for computing nodes of a managed computer network by automatically determining to separate a particular outgoing packet or other outgoing communication from a source computing node into multiple parts (e.g., multiple packets) to be independently sent using two or more alternative network paths between the sending computing node and the destination for the communication. For example, a manager module associated with the source computing node may automatically determine to encode the outgoing communication into a dynamically determined quantity of multiple parts (e.g., by using a configurable erasure code), such as based on current information about available alternative paths, and another manager module associated with the destination may receive at least some of the multiple parts and decode them into the original outgoing communication, which is then provided to the destination.

Claims

1. A computer-implemented method comprising:

receiving, by one or more programmed computing systems, an indication of a communication to be sent from a first computing node of a virtual computer network to a second computing node of the virtual computer network;

determining, by the one or more programmed computing systems, multiple alternative paths between the first and second computing nodes over one or more intervening networks;

before forwarding the communication over the one or more intervening networks, determining, by the one or more programmed computing systems, a quantity of multiple parts into which to encode the communication based at least in part on information about the determined multiple alternative paths;

encoding, by the one or more programmed computing systems, the communication into the determined quantity of multiple parts; and

initiating forwarding each of the multiple parts of the encoded communication from the first computing node to the second computing node along one of the multiple alternative paths, wherein each of the multiple alternative paths is used to forward at least one of the multiple parts.

2. The computer-implemented method of claim 1 wherein the encoding of the communication into the determined quantity of multiple parts is performed using an erasure code.

3. The computer-implemented method of claim 2 further comprising:

receiving at least some of the multiple parts of the encoded communication after the received at least some parts are forwarded along two or more of the multiple alternative paths to the second computing node;

decoding the received at least some parts into the communication based on the erasure code; and

after the decoding, providing the communication to the second computing node.

4. The computer-implemented method of claim 2 wherein the determined quantity of the multiple parts is based at least in part on a quantity of the multiple alternative paths.

5. The computer-implemented method of claim 2 wherein the one or more intervening networks are a substrate network on which the virtual computer network is overlaid.

6. The computer-implemented method of claim 1 further comprising:

receiving an indication of a second communication to be sent from the first computing node to a third computing node;

determining, by the one or more programmed computing systems, to not encode the second communication into multiple parts; and

initiating forwarding the second communication from the first computing node to the third computing node along a single path over the one or more intervening networks.

7. The computer-implemented method of claim 1 further comprising:

receiving an indication of a second communication to be sent from the first computing node to the second computing node;

determining, by the one or more programmed computing systems, a second quantity of multiple parts into which to encode the second communication, the determined second quantity being distinct from the determined quantity and being based at least in part on information about the multiple alternative paths;

encoding, by the one or more programmed computing systems, the second communication into the determined second quantity of multiple parts; and

initiating forwarding each of the multiple parts of the encoded second communication from the first computing node to the second computing node along one of the multiple alternative paths.

8. The computer-implemented method of claim 7 wherein the determined second quantity of multiple parts for the second communication is distinct from the determined quantity of multiple parts for the communication based on a change in path availability from the first computing node to the second computing node between times of sending the communication and the second communication.

9. The computer-implemented method of claim 7 wherein the determined second quantity of multiple parts for the second communication is distinct from the determined quantity of multiple parts for the communication based on a change in operational characteristics of one or more of the multiple alternative paths between times of sending the communication and the second communication, the operational characteristics of the one or more alternative paths corresponding to loss of communications sent along the one or more alternative paths.

10. The computer-implemented method of claim 1 wherein the multiple alternative paths from the first computing node to the second computing node are based on at least one of a group that includes multiple alternative network links between two or more locations in the one or more intervening networks, multiple physical network interfaces available for sending the communication from the first computing node to the one or more intervening networks, multiple logical network interfaces available for sending the communication from the first computing node to the one or more intervening networks, multiple physical network interfaces available for the second computing node for receiving the communication from the one or more intervening networks, and multiple logical network interfaces available for the second computing node for receiving the communication from the one or more intervening networks.

11. The computer-implemented method of claim 1 wherein the first computing node is at a first geographical location and the second computing node is at a distinct second geographical location, wherein multiple alternative communication links are available for sending communications between the first and second geographical locations, and wherein the multiple alternative paths each includes one of the multiple alternative communication links.

12. The computer-implemented method of claim 11 wherein the one or more intervening networks include multiple edge modules at the first geographical location that are each associated with at least one of the alternative communication links, wherein the multiple alternative paths further include two or more of the edge modules and two or more of the alternative communication links, and wherein the forwarding of each of the multiple parts of the communication from the first computing node to the second computing node along one of the multiple alternative paths includes using a network address associated with a selected one of the multiple edge modules.

13. The computer-implemented method of claim 1 wherein the communication is one of multiple packets for use in transferring one or more memory pages from the first computing node to the second computing node to enable a migration of one or more executing programs from the first computing node to the second computing node.

14. The computer-implemented method of claim 1 wherein the one or more programmed computing systems are part of a configurable network service that provides the virtual computer network to a first client and that provides multiple other virtual computer networks to multiple other clients, and wherein communications sent between computing nodes for the virtual computer network and for the multiple other virtual computer networks are transmitted on a substrate network and are encoded to use information specific to the substrate network during transmission.

15. A system, comprising:

one or more hardware processors of one or more computing systems; and

a module that is configured to, when executed by at least one of the one or more hardware processors, manage communications for a computing node by;

receiving an indication of a first communication to be sent from the computing node to a first indicated destination;

encoding the first communication into a first quantity of multiple parts, wherein the first quantity is based at least in part on a first group of multiple alternative paths from the computing node to the first indicated destination;

initiating forwarding each of the multiple parts of the encoded first communication along one of the multiple alternative paths of the first group, wherein each of the multiple alternative paths of the first group is used to forward at least one of the multiple parts of the first communication;

receiving an indication of a second communication to be sent from the computing node to a second indicated destination;

encoding the second communication into a second quantity of multiple parts, wherein the second quantity is distinct from the first quantity and is based at least in part on a second group of multiple alternative paths from the computing node to the second indicated destination; and

initiating forwarding each of the multiple parts of the encoded second communication along one of the multiple alternative paths of the second group, wherein each of the multiple alternative paths of the second group is used to forward at least one of the multiple parts of the second communication.

16. The system of claim 15 wherein the module includes software instructions that, when executed, further configure the module to determine the first quantity of multiple parts for the first communication based at least in part on a third quantity of the multiple alternative paths of the first group, and to determine the second quantity of multiple parts for the second communication based at least in part on a fourth quantity of the multiple alternative paths of the second group, the third and fourth quantities being distinct.

17. The system of claim 15 wherein the computing node and the first indicated destination and the second indicated destination are each part of a virtual computer network overlaid on a substrate network, wherein the multiple alternative paths of the first and second groups are paths through the substrate network, and wherein the multiple alternative paths of the second group are distinct from the multiple alternative paths of the first group based at least in part on a change in path availability between distinct times of sending the first and second communications.

18. The system of claim 15 wherein the encoding of the first communication into the first quantity of multiple parts is performed using a first determined erasure code, and wherein the encoding of the second communication into the second quantity of multiple parts is performed using a second determined erasure code distinct from the first determined erasure code.

19. The system of claim 15 wherein the encoding of the first communication into the first quantity of multiple parts is performed using an erasure code, and wherein the encoding of the second communication into the second quantity of multiple parts is also performed using the erasure code.

20. The system of claim 15 wherein the encoding of the first communication into the first quantity of multiple parts is performed using an erasure code, and wherein the system further comprises a second module including software instructions that, when executed, configure the second module to manage communications for the first indicated destination by:

receiving at least some of the multiple parts of the encoded first communication after the received at least some parts are forwarded along two or more of the multiple alternative paths of the first group to the first indicated destination;

decoding the received at least some parts into the first communication based on the erasure code; and

after the decoding, providing the first communication to the first indicated destination.

21. A non-transitory computer-readable medium having stored contents that configure a computing system to:

receive an indication of a communication to be sent from a first computing node to a second computing node over one or more intervening networks;

before forwarding the communication over the one or more intervening networks, determine, by the configured computing system, a quantity of multiple parts into which to encode the communication based at least in part on multiple alternative paths that are available between the first and second computing nodes over the one or more intervening networks;

encode, by the configured computing system, the communication into the determined quantity of multiple parts; and

forward each of the multiple parts of the encoded communication from the first computing node to the second computing node along one of the multiple alternative paths, wherein each of the multiple alternative paths is used to forward at least one of the multiple parts.

22. The non-transitory computer-readable medium of claim 21 wherein the first and second computing nodes are part of a virtual computer network overlaid on the one or more intervening networks, and wherein the encoding of the communication into the determined quantity of multiple parts is performed using an erasure code.

23. The non-transitory computer-readable medium of claim 22 wherein the stored contents further configure the computing system to determine the multiple alternative paths that are available between the first and second computing nodes over the one or more intervening networks, and wherein the determined quantity of the multiple parts is based at least in part on a quantity of the multiple alternative paths.

24. The non-transitory computer-readable medium of claim 21 wherein the first computing node is at a first geographical location and the second computing node is at a distinct second geographical location, wherein multiple alternative communication links are available for sending communications between the first and second geographical locations, and wherein the multiple alternative communication links are each part of one of the multiple alternative paths.

25. The non-transitory computer-readable medium of claim 21 wherein the configured computing system is part of a configurable network service that provides, to a client, a virtual computer network that includes the first and second computing nodes, wherein the one or more intervening networks are a substrate network on which the virtual computer network is overlaid, and wherein communications sent between computing nodes for the virtual computer network are transmitted on the substrate network and are encoded to use information specific to the substrate network during transmission.