Using virtual networking devices to manage routing cost information

• US 8,995,301 B1
• Filed: 12/07/2009
• Issued: 03/31/2015
• Est. Priority Date: 12/07/2009
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Miller, Kevin Christopher, Brandwine, Eric Jason, Doane, Andrew J.
• Primary Examiner(s): Zhu, Alvin
• Application Number:
  US12/632,732
• Time in Patent Office: 1,940 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 41/0826 for reduction of network costs H04L41/0833 takes precedence
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

Techniques are described for providing managed virtual computer networks that have a configured logical network topology with virtual networking devices, such as by a network-accessible configurable network service, with corresponding networking functionality provided for communications between multiple computing nodes of the virtual computer network by emulating functionality that would be provided by the virtual networking devices if they were physically present. In some situations, the networking functionality provided for a managed computer network of a client includes receiving routing communications directed to the virtual networking devices and using included routing cost information to update the configuration of the managed computer network, and/or includes determining actual cost information corresponding to use of an underlying substrate network and providing routing cost information to the client that reflects the determined actual cost information, so as to enable the client to modify the configuration of the managed computer network accordingly.

Claims

1. A computer-implemented method comprising:

receiving, by one or more configured hardware computing systems of a configurable network service that provides virtual computer networks to clients, configuration information indicating a network topology for a first virtual computer network for a first client, the network topology indicating multiple computing nodes of the first virtual computer network that are separated into two or more groups and further specifying a virtual router device of the first virtual computer network that interconnects the two or more groups; and

providing, by the one or more configured hardware computing systems, the first virtual computer network to the first client in accordance with the configuration information by emulating functionality of the specified virtual router device for communications between the two or more groups without physically providing the specified virtual router device, the providing of the first virtual computer network including;

intercepting one or more routing communications that are each sent using a defined routing protocol to the specified virtual router device despite the specified virtual router device not being physically provided, the intercepted one or more routing communications including network routing information for the first virtual computer network;

determining, by the one or more configured hardware computing systems and during the providing of the first virtual computer network, one or more costs specified by the first client for use of multiple alternative intermediate destinations via which communications for the first virtual computer network can be directed to an indicated final destination, the determining of the one or more costs including analyzing the included network routing information in the intercepted one or more routing communications to identify the determined one or more costs;

selecting, based at least in part on the determined one or more costs specified by the first client, one of the alternative intermediate destinations as a preferred intermediate destination for the one or more indicated final destinations; and

after the selecting of the one alternative intermediate destination, forwarding one or more additional communications directed to the indicated final destination to the selected one alternative intermediate destination.

2. The method of claim 1 further comprising identifying the multiple alternative intermediate destinations based at least in part on the network routing information included in the one or more routing communications.

3. The method of claim 1 further comprising identifying the multiple alternative intermediate destinations based at least in part on the configuration information received from the first client.

4. The method of claim 1 wherein the one or more costs specified by the first client for the use of the multiple alternative intermediate destinations include multiple costs that reflects a preference of the first client regarding using the selected one alternative intermediate destination relative to using other of the alternative intermediate destinations, the selected one alternative intermediate destination having a lowest of the multiple costs.

5. The method of claim 1 wherein the analyzing of the included network routing information in the intercepted one or more routing communications further includes discarding routing cost information from the one or more routing communications that does not correspond to at least one of the alternative intermediate destinations.

6. The method of claim 1 wherein the selecting of the one alternative intermediate destination includes designating the selected one alternative intermediate destination to be used for communications forwarded to the one or more indicated final destinations until the selected one alternative intermediate destination becomes unavailable.

7. The method of claim 6 further comprising selecting one or more other of the alternative intermediate destinations for use with communications forwarded to the one or more indicated final destinations when the selected one alternative intermediate destination is unavailable, the selected other alternative intermediate destinations being distinct from the selected one alternative intermediate destination, and the selecting of the other alternative intermediate destinations being based at least in part on the determined one or more costs.

8. The method of claim 1 wherein the multiple alternative intermediate destinations are each one of the multiple computing nodes and are each configured to provide one or more capabilities related to forwarding communications to other computing nodes.

9. The method of claim 1 wherein the selected one alternative intermediate destination is an edge device that forwards communications from one or more first geographical locations of at least some of the multiple computing nodes of the first virtual computer network to one or more other computing nodes at one or more other second geographical locations that are distinct from the one or more first geographical locations.

10. The method of claim 1 wherein the selected one alternative intermediate destination is a peering router that connects the multiple computing nodes of the first virtual computer network to one or more other computing nodes of one or more other virtual computer networks provided by the configurable network service.

11. The method of claim 1 wherein the selected one alternative intermediate destination is a connection endpoint for a connection between at least some of the multiple computing nodes of the first virtual computer network and one or more other computing nodes distinct from the at least some computing nodes.

12. The method of claim 1 wherein the analyzing of the included network routing information in the intercepted one or more routing communications further includes identifying routing cost information corresponding to at least one of two or more of the multiple computing nodes that are alternatives for an indicated second final destination, and includes selecting one of the two or more computing nodes as a preferred destination for communications directed to the indicated second final destination based at least in part on the identified routing cost information.

13. The method of claim 1 wherein the configurable network service provides a plurality of computing nodes for use in provided virtual computer networks, and wherein the configurable network service further uses some of the plurality of computing nodes to provide multiple other virtual computer networks distinct from the first virtual computer network to multiple other clients.

14. The method of claim 1 wherein the multiple computing nodes are each a virtual machine hosted on one of multiple physical computing systems of the configurable network service, and wherein the providing of the first virtual computer network includes configuring one or more virtual machine communication manager modules that execute on one or more of the physical computing systems to manage communications for the hosted virtual machines.

15. A computer-implemented method comprising:

receiving, by one or more computing systems of a configurable network service that provides virtual computer networks to clients, one or more requests to provide a first virtual computer network for a first client in accordance with specified configuration information, the configuration information indicating one or more specified networking devices of the first virtual computer network that interconnect multiple computing nodes of the first virtual computer network; and

providing, by the one or more computing systems of the configurable network service, the first virtual computer network in accordance with the configuration information by overlaying the first virtual computer network on a distinct substrate network without physically providing the one or more specified networking devices, the multiple computing nodes being connected to the substrate network, the providing of the first virtual computer network including;

forwarding multiple communications between the multiple computing nodes over the substrate network in a manner that emulates functionality that would be provided by the one or more specified networking devices if the one or more specified networking devices were physically provided;

identifying two or more alternative intermediate destinations via which communications directed to one or more indicated final destinations are routed;

after the forwarding of the multiple communications, receiving one or more routing communications that are each directed to at least one of the specified networking devices and include network routing information for the first virtual computer network that is specified in accordance with one or more predefined network routing protocols, wherein the receiving of the one or more routing communications includes intercepting the one or more routing communications before the one or more routing communications are forwarded over the substrate network, and inhibiting forwarding of the intercepted routing communications to the at least one specified networking device to which the intercepted routing communications are directed;

analyzing the one or more routing communications to identify routing cost information corresponding to at least one of the alternative intermediate destinations, and selecting one of the alternative intermediate destinations as a preferred intermediate destination for the one or more indicated final destinations based at least in part on the identified routing cost information; and

after the selecting of the one alternative intermediate destination, receiving one or more additional communications from one or more of the multiple computing nodes that are each directed to at least one of the one or more indicated final destinations, and forwarding the one or more additional communications to the selected one alternative intermediate destination.

16. A non-transitory computer-readable storage medium having stored contents that configure a computing system of a configurable network service to:

provide, by the configured computing system, a first virtual computer network for a first client in accordance with configuration information from the first client, the configuration information indicating interconnections between multiple computing nodes of the first virtual computer network that include one or more virtual router devices of the first virtual computer network indicated to interconnect indicated groups of the multiple computing nodes, the providing of the first virtual computer network including emulating functionality of the one or more virtual router devices without physically providing the one or more virtual router devices, the providing of the first virtual computer network further including;

determining routing cost information that corresponds to routing communications over the substrate network from at least one of the multiple computing nodes to one or more indicated destinations;

sending, to at least one of the multiple computing nodes, one or more routing communications that are indicated to be from at least one of the one or more virtual router devices despite the at least one virtual router device not being physically provided, the sent one or more routing communications having network routing information for the first virtual computer network that includes the determined routing cost information corresponding to the one or more indicated destinations;

receiving information indicating one or more changes to configuration of the first virtual computer network that are based at least in part on the sent one or more routing communications, wherein the one or more changes are initiated by the first client and correspond to communications to the one or more indicated destinations; and

after the one or more changes to the configuration, forwarding one or more additional communications from one or more of the at least one computing nodes over the substrate network to at least one of the indicated destinations in accordance with the changed configuration.

17. The non-transitory computer-readable storage medium of claim 16 wherein the first virtual computer network includes multiple alternative routes from the at least one computing nodes to the one or more indicated destinations, wherein the determined routing cost information indicates differing costs for two or more of the multiple alternative routes, wherein the one or more changes to the configuration of the first virtual computer network correspond to using a first of the multiple alternative routes that has a lower indicated cost than one or more other of the multiple alternative routes, and wherein the forwarding of the one or more additional communications in accordance with the changed configuration includes forwarding the additional communications along the first alternative route.

18. The non-transitory computer-readable storage medium of claim 17 wherein the configurable network service provides multiple virtual computer networks to multiple remote clients over one or more networks, and wherein the receiving of the information indicating the changes to the configuration includes receiving information supplied by the first client via an application programming interface (API) provided by the configurable network service.

19. The non-transitory computer-readable storage medium of claim 17 wherein the receiving of the information indicating the changes to the configuration includes receiving information supplied via one or more additional routing communications.

20. The non-transitory computer-readable storage medium of claim 17 wherein the multiple alternative routes from the at least one computing nodes to the one or more indicated destinations include multiple alternative computing nodes of the first virtual computer network via which communications to the one or more indicated destinations are routed, and wherein the first alternative route uses at least one of the multiple alternative computing nodes that is not used by the one or more other alternative routes.

21. The non-transitory computer-readable storage medium of claim 17 wherein the configurable network service charges monetary fees to the first client based on use of particular computing nodes or on forwarding of communications to particular locations of the substrate network, and wherein the differing costs for the two or more alternative routes are based on monetary fees charged by the configurable network service.

22. The non-transitory computer-readable storage medium of claim 17 wherein the determined routing cost information includes multiple routing costs that are based on routing distances between locations of the multiple computing nodes in the substrate network or on substrate network transmission characteristics that affect routing of communications between the multiple computing nodes over the substrate network, and wherein the differing costs for the two or more alternative routes are each one of the multiple routing costs.

23. The non-transitory computer-readable storage medium of claim 16 wherein the determined routing cost information includes first cost information for routing communications to a first indicated destination of the one or more indicated destinations, and wherein the sending of the one or more routing communications includes adding to at least one of the sent routing communications one or more tags that are associated with the first indicated destination and that represent at least one of multiple factors, the first cost information being based at least in part on the at least one factor.

24. The non-transitory computer-readable storage medium of claim 23 wherein one of the at least one sent routing communications is encoded in accordance with a Border Gateway Protocol (“

BGP”

) routing protocol and includes the added one or more tags as BGP community attribute tags, and wherein the first cost information is represented in the one sent routing communication by the added one or more tags.

25. The non-transitory computer-readable storage medium of claim 23 wherein the first indicated destination corresponds to a first location in the substrate network that is one of the at least one factors on which the first cost information is based, and wherein the added one or more tags represent the first location.

26. The non-transitory computer-readable storage medium of claim 16 wherein the stored contents further configure the computing system to forward multiple communications between the multiple computing nodes.

27. The non-transitory computer-readable storage medium of claim 16 wherein the one or more indicated destinations are one or more of the multiple computing nodes, and wherein the stored contents are instructions that, when executed, program the configured computing system.

28. A computing system, comprising:

one or more hardware processors; and

a manager module that is configured to, when executed by at least one of the hardware processors, provide computer networks to one or more customers of a configurable network service by, for each of the one or more customers;

configuring a first computer network provided for the customer in accordance with configuration information from the customer, the configuration information indicating interconnections between multiple computing nodes of the provided computer network that include one or more virtual router devices of the provided first computer network indicated to interconnect indicated groups of the multiple computing nodes, the configuring of the provided first computer network including emulating functionality of the one or more virtual router devices without physically providing the one or more virtual router devices;

intercepting one or more routing communications that are each directed to at least one of the one or more virtual router devices and include routing information for the first computer network, the routing information specifying one or more costs corresponding to at least one of two or more alternative intermediate destinations for communications directed to one or more indicated final destinations, at least one of the specified one or more costs being specified by the customer for one of the two or more alternative intermediate destinations;

selecting one of the alternative intermediate destinations as a preferred intermediate destination for the one or more indicated final destinations based at least in part on the specified one or more costs from the routing information; and

after the selecting of the one alternative intermediate destination, forwarding one or more additional communications that are each directed to at least one of the one or more indicated final destinations to the selected one alternative intermediate destination.

29. The computing system of claim 28 wherein the one or more customers include multiple remote customers that communicate with the configurable network service over one or more networks, and wherein the configurable network service provides an application programming interface (API) for use by the multiple remote customers to configure the computer networks provided for use by the customers.

30. The computing system of claim 28 wherein the providing of the computer networks to the one or more customers further includes, for each of the one or more customers:

identifying the two or more alternative intermediate destinations for the computer network provided for the customer based on the configuration information from the customer or the routing information included in the one or more routing communications received for that provided computer network, and wherein the identified two or more alternative intermediate destinations are a subset of the multiple computing nodes of that provided computer network and provide capabilities related to forwarding communications to the one or more indicated final destinations for that provided computer network.

31. The computing system of claim 28 wherein the manager module includes software instructions for execution by the at least one hardware processor.