Custom routing decisions

• US 8,296,459 B1
• Filed: 06/30/2010
• Issued: 10/23/2012
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brandwine, Eric Jason, Sivasubramanian, Swaminathan, Marshall, Bradley E., Certain, Tate Andrew
• Primary Examiner(s): JEAN GILLES, JUDE
• Application Number:
  US12/827,268
• Time in Patent Office: 846 Days
• Field of Search: 709/241, 709/225, 709/244, 709/224, 709/220, 709/206, 709/227
• US Class Current: 709/241
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects

Abstract

With the advent of virtualization technologies, networks and routing for those networks can now be simulated using commodity hardware rather than actual routers. For example, virtualization technologies such as those provided by VMWare, XEN, or User-Mode Linux can be adapted to allow a single physical computing machine to be shared among multiple virtual networks by providing each virtual network user with one or more virtual machines hosted by the single physical computing machine, with each such virtual machine being a software simulation acting as a distinct logical computing system that provides users with the illusion that they are the sole operators and administrators of a given hardware computing resource. In addition, routing can be accomplished through software, providing additional routing flexibility to the virtual network in comparison with traditional routing. As a result, in some implementations, supplemental information other than packet information can be used to determine network routing.

Claims

1. A routing system for determining a routing path for network data packets through a substrate network associated with a virtual network having virtual components, the routing system comprising:

a computing interface for receiving user-specified characteristics of virtual routes of a virtual network; and

a route manager comprising one or more computing devices, the route manager configured to;

obtain a user-specified virtual route characteristic from the computing interface, the user-specified virtual route characteristic associated with a virtual route identifying one or more virtual components of the virtual network;

associate the user-specified virtual route characteristic with at least one computing node, wherein the at least one computing node is configured to simulate a virtual component identified in the virtual route;

generate a substrate routing table based at least partly on a topology of the substrate network and the user-specified virtual route characteristic associated with the at least one computing node, the substrate routing table comprising one or more substrate network addresses, the substrate routing table identifying routes through the substrate network;

generate one or more forwarding entries for the one or more nodes of the substrate network, the one or more forwarding entries reflecting a substrate route corresponding to an identified route in the substrate routing table; and

communicate the one or more forwarding entries to the at least one computing node.

2. The routing system of claim 1, wherein the user-specified virtual route characteristic comprise at least one of a routing cost, monetary cost, a packet loss rate and a communication reliability rate.

3. The routing system of claim 1, wherein the user-specified virtual route characteristic comprise user-preferred routing paths between virtual components of the virtual network.

4. The routing system of claim 1, wherein the at least one computing node of the substrate network comprises one or more computing devices connected to one or more communications medium.

5. The routing system of claim 4, wherein the user-specified virtual route characteristic comprise routing costs between nodes of the substrate network for network traffic over the communications medium.

6. The routing system of claim 4, wherein the communications medium comprises at least one of a wired and wireless connection.

7. The routing system of claim 1, wherein generating the substrate routing table comprises executing a routing protocol to populate the substrate routing table at least partially based on the user-specified virtual route characteristic associated with the at least one computing node.

8. The routing system of claim 1, wherein the at least one computing node is associated with multiple virtual characteristics corresponding to multiple virtual networks.

9. The routing system of claim 1, wherein the at least one computing node operates virtualization software capable of simulating multiple virtual components on the same node.

10. The routing system of claim 1, wherein each virtual component simulated on the at least one computing node is associated with a separate set of forwarding entries.

11. The routing system of claim 1, wherein the virtual network spans over multiple computing nodes in multiple data centers.

12. The routing system of claim 1, wherein the route manager directs routing for a plurality of computing nodes of the substrate network.

13. The routing system of claim 1, wherein the route manager directs routing for a single computing node of the substrate network, each computing node having an associated route manager.

14. The routing system of claim 13, wherein the route manager operates on the at least one computing node.

15. A computer-implemented method for determining a routing path for network data packets through a substrate network associated with an overlay network, the method comprising:

by a computing system that comprises one or more computing devices;

in a substrate network comprising a plurality of nodes and an overlay network at least partially simulated by the substrate network, receiving network configuration data specified by a user associated with the overlay network, the network configuration data supplementary to data included in network data packets, the network configuration data specifying an overlay network characteristic that affects routing behavior of one or more overlay network components;

in response to receiving the network configuration data, automatically associating the network configuration data with one or more substrate nodes associated with the one or more overlay network components; and

adjusting routing in the substrate network based at least in part on the network configuration data associated with the one or more substrate nodes.

16. The method of claim 15, wherein the overlay network characteristic specified by the network configuration data comprises at least one of a routing cost, monetary cost, a packet loss rate and a communication reliability rate.

17. A computer-implemented method for determining a routing path for network data packets through a substrate network associated with a virtual network, the method comprising:

by a computing system that comprises one or more computing devices;

receiving network configuration data supplementary to data included in network data packets from one of a plurality of virtual network customers, the network configuration data comprising a characteristic of one or more virtual components of the virtual network; and

in response to receiving the network configuration data, automatically;

associating components of the virtual network with one or more nodes of a substrate network, the one or more nodes of the substrate network capable of simulating the operation of one or more components of the virtual network;

associating the network configuration data with the one or more substrate nodes associated with the one or more virtual components of the virtual network; and

generating substrate routes through the substrate network at least partially based on the network configuration data associated with the substrate nodes.

18. The method of claim 17, wherein the network configuration data comprise a cost function specified by a user for the virtual network.

19. The method of claim 17, wherein the network configuration data comprise routing metrics between virtual components specified by a user.

20. The method of claim 19, wherein the routing metrics comprise at least one of a routing cost, a monetary cost, a packet loss rate and a communication reliability rate.

21. The method of claim 17, wherein the network configuration data corresponds to metrics for traversing the underlying substrate network.

22. The method of claim 17, wherein generating substrate routes comprises identifying routes by using the network configuration data associated with the substrate node as input to a cost function.

23. The method of claim 17, wherein the network configuration data comprises routing costs and topology data for the substrate network and the generated virtual routes minimize the network traffic costs for the underlying substrate network.

24. Non-transitory computer-readable storage medium having stored thereon instructions that, when executed, direct a computing system to:

receive a user-specified characteristic of a virtual route from one of a plurality of virtual network users, the user-specified characteristic identifying a source and a destination component of a virtual network, the virtual network associated with a substrate network;

associate the user-specified characteristic of the virtual route with at least a first substrate node associated with the source virtual component;

identify a substrate route from the first substrate node to a second substrate node, the substrate route at least partially based on the user-specified characteristic associated with the first substrate node; and

generate a control message for the first substrate node, the control message configured to direct network packets associated with traffic from the source component to the destination component through the substrate route from the first node to the second node.

25. The non-transitory computer-readable storage medium of claim 24, wherein the virtual network comprises an overlay network over the substrate network.

26. The non-transitory computer-readable storage medium of claim 24, wherein the user-specified characteristic of the virtual route comprises user-defined costs associated with the virtual route.

27. The non-transitory computer-readable storage medium of claim 24, wherein the control message comprises at least one of a forwarding entry, a blacklist update, packet tagging data and MAC stacking data.

28. The non-transitory computer-readable storage medium of claim 24, the instructions further directing the computing system to:

transfer one of the source component and the destination component from the second node to the first node, the source and destination components simulated on the same node after the transfer in order to reduce network traffic over the substrate network between the first node and the second node.