Managing encoded multi-part communications for provided computer networks

• US 8,612,627 B1
• Filed: 03/03/2010
• Issued: 12/17/2013
• 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): Backer, Firmin
• Assistant Examiner(s): Chambers, Michael A
• Application Number:
  US12/717,058
• Time in Patent Office: 1,385 Days
• Field of Search: 709/227, 709/240, 370/238, 370/399
• US Class Current: 709/240
• 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 non-transitory computer-readable storage medium having stored contents that configure a computing system to perform a method, the method comprising:

obtaining information regarding a first virtual computer network having multiple computing nodes, the first virtual computer network being overlaid on a distinct substrate network that interconnects the multiple computing nodes; and

automatically managing one or more communications sent by one or more of the multiple computing nodes of the first virtual computer network, the multiple communications each being sent by a sending one of the multiple computing nodes and having an intended final destination, the managing of each of the one or more communications being performed by the configured computing system and including;

automatically determining one or more alternative paths from the sending computing node for the communication to the intended final destination of the communication;

automatically determining a first quantity of one or more parts into which to encode the communication based at least in part on information about the determined alternative paths, and encoding the communication into the determined first quantity of parts; and

forwarding each of the parts of the communication from the sending computing node for the communication to the intended final destination of the communication along one of the determined alternative paths, wherein each of the determined alternative paths is used to forward at least one of the parts.

2. The non-transitory computer-readable storage medium of claim 1 wherein, for each of at least one of the one or more communications, the automatically determined alternative paths for the communication include multiple alternative paths, the information about the determined alternative paths on which the automatic determining of the first quantity of parts for the communication is based includes a second quantity of the multiple alternative paths, the determined first quantity for the communication is greater than one such that the encoded parts of the communication include multiple parts, and the encoding of the communication is performed to enable the communication to be decoded from a subset of the encoded multiple parts that has a third quantity less than the determined first quantity.

3. The non-transitory computer-readable storage medium of claim 1 wherein, for each of at least one of the one or more communications, the automatically determined one or more alternative paths for the communication have operational characteristics that correspond to communications sent along the determined alternative paths that are not successfully received at destinations of those communications, the information about the determined alternative paths on which the automatic determining of the first quantity of parts for the communication is based includes the operational characteristics of the determined alternative paths, the determined first quantity for the communication is greater than one such that the encoded parts of the communication include multiple parts, and the encoding of the communication is performed to enable the communication to be decoded from a subset of the encoded multiple parts that has a third quantity less than the determined first quantity.

4. The non-transitory computer-readable storage medium of claim 1 wherein the intended final destination for one of the one or more communications is at a second location remote from a first location of the sending computing node for the one communication, wherein the automatically determined alternative paths for the one communication include multiple alternative paths between the first and second locations, wherein the determined first quantity for the one communication is greater than one such that the encoded parts of the one communication include multiple parts, and wherein the forwarding of the multiple parts of the one communication along the multiple alternative paths includes using multiple edge modules at the first location that are each associated with at least one of the multiple alternative paths.

5. The non-transitory computer-readable storage medium of claim 1 wherein the intended final destination for one of the one or more communications is one of the multiple computing nodes, wherein the automatically determined alternative paths for the one communication include multiple alternative paths through at least a portion of the substrate network, wherein the determined first quantity for the one communication is greater than one such that the encoded parts of the one communication include multiple parts, wherein each of the multiple computing nodes has at least one associated first virtual network address for the first virtual computer network and has at least one distinct associated second substrate network address that corresponds to a location of the computing node in the substrate network, and wherein the forwarding of the multiple parts of the one communication along the multiple alternative paths includes using multiple substrate network addresses corresponding to the multiple alternative paths.

6. The non-transitory computer-readable storage medium of claim 5 wherein the forwarding of the multiple parts of the one communication along the multiple alternative paths using the multiple substrate network addresses corresponding to the multiple alternative paths includes, for each of the multiple parts, automatically selecting one of the multiple alternative paths to use for forwarding the part by performing hashing using information specific to the part being forwarded.

7. The non-transitory computer-readable storage medium of claim 1 wherein, for each of at least one of the one or more communications, the automatically determined alternative paths for the communication include a single alternative path, the determined first quantity for the communication is one such that the encoded parts of the communication include a single part, and the encoding of the communication includes adding additional information to the encoded single part related to error correction to enable the communication to be decoded from a subset of the encoded single part.

8. The non-transitory computer-readable storage medium of claim 1 wherein the obtained information is configuration information specified by a user on whose behalf the first virtual computer network is provided, wherein the determined first quantity for one of the one or more communications is greater than one such that the encoded parts of the one communication include multiple parts, wherein the encoding of the one communication into the determined first quantity of parts is performed using an erasure code, and wherein the method further comprises:

receiving at least some of the multiple parts of the one communication after the received at least some parts are forwarded along the determined alternative paths to the intended final destination for the one communication;

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

after the decoding, providing the one communication to the intended final destination for the one communication.

9. The non-transitory computer-readable storage medium of claim 1 wherein the computer-readable medium is a memory of the configured computing system that stores the contents, and wherein the contents are instructions that when executed program the computing system to perform the method.

10. A computer-implemented method comprising:

obtaining information regarding a first virtual computer network having multiple computing nodes, the first virtual computer network being overlaid on a distinct substrate network that interconnects the multiple computing nodes; and

managing, by one or more configured computing systems, a communication sent by a sending one of the multiple computing nodes of the first virtual computer network to an intended final destination, the managing of the communication including;

determining, by the one or more configured computing systems, one or more alternative paths from the sending one computing node to the intended final destination;

determining, by the one or more configured computing systems, a first quantity of one or more parts into which to encode the communication based at least in part on information about the determined alternative paths, and encoding the communication into the one or more parts of the determined first quantity; and

forwarding, by the one or more configured computing systems, each of the parts of the encoded communication from the sending one computing node to the intended final destination along one of the determined alternative paths, wherein each of the determined alternative paths is used to forward at least one of the parts.

11. The method of claim 10 wherein the determined one or more alternative paths include multiple alternative paths.

12. The method of claim 11 wherein the information about the determined alternative paths on which the determining of the first quantity of parts is based includes a quantity of the multiple alternative paths.

13. The method of claim 10 wherein the determined first quantity is greater than one, and wherein the encoding of the communication includes generating multiple parts of the encoded communication.

14. The method of claim 13 wherein the encoding of the communication is further performed to enable the communication to be decoded from a subset of less than all of the multiple parts.

15. The method of claim 10 wherein the determined one or more alternative paths have operational characteristics corresponding to communications that are not successfully received at destinations of those communications, and wherein the information about the determined alternative paths on which the determining of the first quantity of parts is based includes the operational characteristics of the determined alternative paths.

16. The method of claim 10 wherein the intended final destination is at a second location remote from a first location of the sending one computing node, wherein the determined alternative paths for the communication include multiple alternative paths between the first and second locations, and wherein the forwarding of the parts of the encoded communication includes using multiple edge modules at the first location that are each associated with at least one of the multiple alternative paths.

17. The method of claim 10 wherein the intended final destination is one of the multiple computing nodes, and wherein the determined alternative paths for the communication include multiple alternative paths through at least a portion of the substrate network.

18. The method of claim 17 wherein each of the multiple computing nodes has at least one associated first virtual network address for the first virtual computer network and has at least one distinct associated second substrate network address that corresponds to a location of the computing node in the substrate network, and wherein the forwarding of the parts of the encoded communication includes using multiple substrate network addresses corresponding to the multiple alternative paths.

19. The method of claim 18 wherein the encoding of the communication includes generating multiple parts of the encoded communication, and wherein the forwarding of the parts of the encoded communication using the multiple substrate network addresses includes, for each of the multiple parts, selecting one of the multiple alternative paths to use for forwarding the part by performing hashing using information specific to the part being forwarded.

20. The method of claim 10 wherein the determined alternative paths for the communication include a single alternative path.

21. The method of claim 20 wherein the determined first quantity is one such that the one or more parts of the encoded communication include a single part, and wherein the encoding of the communication includes adding additional information to the single part related to error correction to enable the communication to be decoded from a subset of less than all of the single part.

22. The method of claim 10 wherein the one or more configured computing systems are part of a configurable network service that provides the first virtual computer network to a first client and that provides multiple other virtual computer networks to multiple other clients, wherein the obtained information is configuration information specified by the first client, and wherein the method further comprises providing the first virtual computer network in accordance with the configuration information by overlaying the first virtual computer network on the substrate network.

23. The method of claim 10 wherein the determined first quantity is greater than one such that the one or more parts of the encoded communication include multiple parts, and wherein the encoding of the communication into the determined first quantity of parts is performed using an erasure code.

24. The method of claim 23 further comprising:

receiving at least some of the multiple parts after the received at least some parts are forwarded along the determined alternative paths to the intended final destination;

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

after the decoding, providing the communication to the intended final destination.

25. The method of claim 10 further comprising:

receiving an indication of a second communication to be sent over the substrate network from the sending one computing node to a second intended final destination;

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

forwarding the second communication from the sending one computing node to the second intended final destination along a single path.

26. The method of claim 10 wherein the communication is a first communication and the intended final destination for the first communication is a first intended final destination, and wherein the method further comprises:

receiving an indication of a second communication to be sent over the substrate network from the sending one computing node to a second intended final destination;

determining, by the one or more configured computing systems, a second quantity of multiple parts into which to encode the second communication, the determined second quantity being distinct from the determined first quantity;

encoding the second communication into the multiple parts of the determined second quantity; and

forwarding each of the multiple parts of the second communication from the sending one computing node to the second intended final destination.

27. The method of claim 26 wherein the second intended final destination is the first intended final destination and the second communication is sent at a different time than the first communication, and wherein the determined second quantity differs from the determined first quantity based on a change in path availability from the second one computing node to the first intended final destination between the different times of sending the first and second communications or on a change in operational characteristics of the determined one or more alternative paths between the different times of sending the first and second communications.

28. The method of claim 10 wherein the determined one or more alternative paths include multiple alternative paths, the multiple alternative paths including multiple alternative network links between two or more locations in the substrate network, multiple physical network interfaces available for sending the communication from the sending one computing node to the substrate network, multiple logical network interfaces available for sending the communication from the sending one computing node to the substrate network, multiple physical network interfaces available for receiving the communication from the substrate network for the intended final destination, of multiple logical network interfaces available for receiving the communication from the substrate network for the intended final destination.

29. The method of claim 10 wherein the communication is one of multiple packets for use in transferring one or more memory pages from the sending one computing node to the intended final destination as part of a migration of one or more executing programs from the sending one computing node to the intended final destination, and wherein the method further comprises, for each of the multiple packets other than the communication, encoding the packet into multiple other parts and forwarding the multiple other parts as distinct packets over the determined alternative paths from the sending one computing node to the intended final destination.

30. A system comprising:

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

one or more modules that are configured to, when executed by at least one of the one or more processors;

obtain information regarding a first virtual computer network having multiple computing nodes, the first virtual computer network being overlaid on a distinct substrate network that interconnects the multiple computing nodes; and

managing one or more communications sent by one or more of the multiple computing nodes of the first virtual computer network, the multiple communications each being sent by a sending one of the multiple computing nodes and having an intended final destination, the managing of each of the one or more communications including;

determining one or more alternative paths from the sending computing node for the communication to the intended final destination of the communication;

determining a first quantity of one or more parts into which to encode the communication based at least in part on information about the determined alternative paths, and encoding the communication into the one or more parts of the determined first quantity; and

forwarding each of the parts of the encoded communication from the sending computing node for the communication to the intended final destination of the communication along one of the determined alternative paths, wherein each of the determined alternative paths is used to forward at least one of the parts.

31. The system of claim 30 wherein, for each of at least one of the one or more communications, the determined alternative paths for the communication include multiple alternative paths, and the determined first quantity for the communication is greater than one, and wherein the one or more modules include software instructions for execution by the at least one processors.