Using virtual networking devices to manage routing information

• US 10,225,146 B2
• Filed: 09/12/2017
• Issued: 03/05/2019
• 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, Bo Hui A
• Application Number:
  US15/702,589
• Publication Number:
  US 20180013624A1
• Time in Patent Office: 539 Days
• Field of Search: 370254, 370255, 370256, 370401
• 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 non-transitory computer-readable storage medium with stored contents that cause a computing system to perform automated operations including at least:

providing, by the computing system, a virtual computer network for a client in accordance with configuration information from the client, including overlaying the virtual computer network on one or more substrate networks and forwarding communications over the one or more substrate networks between multiple computing nodes of the virtual computer network;

determining, by the computing system, routing cost information based at least in part on network characteristics which characterize alternative routing paths over the one or more substrate networks that are selectable to send one or more additional communications by at least one computing device of the client; and

sending, by the computing system and to the at least one computing device of the client, one or more communications that include information based at least in part on the determined routing cost information, for use with the one or more additional communications sent by the at least one computing device.

2. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information based, at least in part, on the network characteristics includes measuring network bandwidth available over the one or more substrate networks, and including the measured network bandwidth in the determined routing cost information.

3. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information based, at least in part, on the network characteristics includes measuring network latency on the one or more substrate networks, and including the measured network latency in the determined routing cost information.

4. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information based, at least in part, on the network characteristics includes measuring network reliability for the one or more substrate networks, and including the measured network reliability in the determined routing cost information.

5. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information based, at least in part, on the network characteristics includes measuring network load for the one or more substrate networks, and including the measured network load in the determined routing cost information.

6. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information based, at least in part, on the network characteristics includes measuring network path availability for one or more network paths in the one or more substrate networks, and including the measured network path availability in the determined routing cost information.

7. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information based, at least in part, on the network characteristics includes measuring network node availability for one or more network nodes, and including the measured network node availability in the determined routing cost information.

8. The non-transitory computer-readable storage medium of claim 1 wherein the determining of the routing cost information further includes determining one or more additional network characteristics of the virtual computer network for forwarding communications between the multiple computing nodes of the virtual computer network, and including the determined one or more additional network characteristics in the determined routing cost information.

9. The non-transitory computer-readable storage medium of claim 1 wherein the sending of the one or more communications includes sending one or more routing communications to the at least one computing device using a defined routing protocol, and wherein the stored contents include software instructions that, when executed by the computing system, further cause the computing system to, after the sending of the one or more routing communications:

receive, by the computing system, the one or more additional communications from the at least one computing device, wherein the one or more additional communications are routed to the computing system by the client based at least in part on the determined routing cost information included in the sent one or more routing communications; and

forward, by the computing system, the one or more additional communications to one or more indicated destinations.

10. The non-transitory computer-readable storage medium of claim 9 wherein the determined routing cost information includes information about differing costs for multiple alternative routes to the one or more indicated destinations, and wherein the forwarding of the one or more additional communications includes forwarding the additional communications along one of the multiple alternative routes selected based at least in part on one or more actions of the client after the sending of the one or more routing communications.

11. The non-transitory computer-readable storage medium of claim 9 wherein the determined routing cost information includes information about differing costs for multiple alternative computing nodes via which communications are routed to the one or more indicated destinations, and wherein the forwarding of the one or more additional communications includes forwarding the additional communications via one of the multiple alternative computing nodes selected based at least in part on one or more actions of the client after the sending of the one or more routing communications.

12. The non-transitory computer-readable storage medium of claim 1 wherein the sending of the one or more communications to the at least one computing device of the client includes forwarding the one or more further communications to at least one of the multiple computing nodes.

13. The non-transitory computer-readable storage medium of claim 1 wherein the computing system is part of a configurable network service that provides multiple virtual computer networks to multiple clients over one or more intervening computer networks, and wherein the sending of the one or more communications to the at least one computing device of the client includes providing information to a user of the at least one computing device on behalf of the client via at least one interface provided by the configurable network service.

14. The non-transitory computer-readable storage medium of claim 1 wherein the computing system is part of a configurable network service that provides multiple virtual computer networks to multiple clients over one or more intervening computer networks, wherein the information received from the client is configuration information for the virtual computer network that specifies one or more networking devices that are part of the specified interconnections for the virtual computer network, and wherein the forwarding of the communications between the multiple computing nodes includes providing at least some of the functionality that would be performed by the one or more networking devices if the one or more networking devices of the virtual computer network were physically provided.

15. A computer-implemented method comprising:

providing, by a configurable network service implemented on one or more computing systems, a virtual computer network for a client of the configurable network service in accordance with configuration information from the client, including overlaying the virtual computer network on one or more substrate networks of the configurable network service and forwarding communications over the one or more substrate networks between multiple computing nodes of the virtual computer network;

determining, by the configurable network service, routing cost information corresponding to network characteristics which characterize alternative routing paths over the one or more substrate networks that are selectable to send one or more additional communications by at least one computing device of the client; and

sending, by the configurable network service and to the at least one computing device of the client that is external to the virtual computer network, one or more routing communications that include the determined routing cost information, to cause changes based at least in part on the determined routing cost information in routing the one or more additional communications for the client by the at least one computing device.

16. The computer-implemented method of claim 15 wherein the determining of the routing cost information corresponding to the network characteristics includes measuring network characteristics of the one or more substrate networks that include at least one of network bandwidth, network latency, network reliability, network load, network path availability for one or more network paths in the one or more substrate networks, or network node availability for one or more network nodes in the one or more substrate networks, and including the measured network characteristics in the determined routing cost information.

17. The computer-implemented method of claim 15 wherein the configurable network service further provides multiple other virtual computer networks to multiple other clients over one or more intervening computer networks, and wherein the sending of the one or more routing communications to the at least one computing device of the client includes providing information to a user of the at least one computing device on behalf of the client via at least one interface provided by the configurable network service.

18. A system, comprising:

one or more hardware processors; and

one or more memories with stored instructions that, when executed by at least one hardware processor of the one or more hardware processors, cause the system to perform automated operations including at least;

providing a virtual computer network for a client of a configurable network service in accordance with configuration information from the client, including overlaying the virtual computer network on one or more substrate networks of the configurable network service;

determining network cost information corresponding to network characteristics which characterize alternative routing paths over the one or more substrate networks that are selectable to send one or more additional communications by at least one computing device of the client; and

sending, to the at least one computing device of the client that is external to the virtual computer network, one or more communications that include the determined network cost information, to cause changes based at least in part on the determined network cost information in forwarding the one or more additional communications for the client.

19. The system of claim 18 wherein the determining of the network cost information corresponding to the network characteristics includes measuring network characteristics of the one or more substrate networks that include at least one of network bandwidth, network latency, network reliability, network load, network path availability for one or more network paths in the one or more substrate networks, or network node availability for one or more network nodes in the one or more substrate networks, and including the measured network characteristics in the determined network cost information.

20. The system of claim 18 wherein the performing of the automated operations further includes implementing functionality of the configurable network service for providing multiple other virtual computer networks to multiple other clients over one or more intervening computer networks, and wherein the sending of the one or more communications to the at least one computing device of the client includes providing information to a user of the at least one computing device on behalf of the client via at least one interface provided by the configurable network service.