GRAPH BASED ROUTING THROUGH MULTIPLE PUBLIC CLOUDS

• US 20190104052A1
• Filed: 05/04/2018
• Published: 04/04/2019
• Est. Priority Date: 10/02/2017
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Cidon, Israel, Dar, Chen, Venugopal, Prashanth, Zohar, Eyal, Markuze, Alex, Bergman, Aran
• Granted Patent: US 10,608,844 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 12/14 Charging , metering or billing arrangements for data wireline or wireless communications
• CPC Class Codes: H04L 12/1403 Architecture for metering, charging or billing
• CPC Class Codes: H04L 12/1428 Invoice generation, e.g. customization, lay-out, database processing, algorithms for calculating the bill or formatting invoices as WWW pages invoicing in general G06Q30/04
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 12/2859 Point-to-point connection between the data network and the subscribers encapsulation H04L12/4633; virtual LANs H04L12/4641; routing of packets H04L45/00
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• 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 2101/35 containing special prefixes
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/64 : using an overlay routing layer
• CPC Class Codes: H04L 45/74 : Address processing for routing
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 61/25 : of the same type
• CPC Class Codes: H04L 61/2514 : between local and global IP addresses
• CPC Class Codes: H04L 61/255 : Maintenance or indexing of mapping tables
• CPC Class Codes: H04L 61/4511 : using domain name system [DNS]
• CPC Class Codes: H04L 63/0245 : Filtering by information in the payload
• CPC Class Codes: H04L 63/0263 : Rule management
• CPC Class Codes: H04L 63/0272 : Virtual private networks
• CPC Class Codes: H04L 63/0281 : Proxies
• CPC Class Codes: H04L 63/20 : for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04M 15/00 : Arrangements for metering, time-control or time indication ; Metering, charging or billing arrangements for voice wireline or wireless communications, e.g. VoIP
• CPC Class Codes: H04M 15/51 : for resellers, retailers or service providers

Abstract

Some embodiments establish for an entity a virtual network over several public clouds of several public cloud providers and/or in several regions. In some embodiments, the virtual network is an overlay network that spans across several public clouds to interconnect one or more private networks (e.g., networks within branches, divisions, departments of the entity or their associated datacenters), mobile users, and SaaS (Software as a Service) provider machines, and other web applications of the entity. The virtual network in some embodiments can be configured to optimize the routing of the entity'"'"'s data messages to their destinations for best end-to-end performance, reliability and security, while trying to minimize the routing of this traffic through the Internet. Also, the virtual network in some embodiments can be configured to optimize the layer 4 processing of the data message flows passing through the network.

Claims

1. A method of defining routes for data message flows associated with an entity through a virtual network defined over a plurality of public cloud datacenters, the method comprising:

generating a routing graph that comprises a plurality of nodes representing a plurality of forwarding elements in at least two public cloud datacenters of two different public cloud providers, wherein at least a set of nodes are edge nodes that connect to external machines of the entity that are outside of the public cloud datacenters; and

performing path-search processes to identify a plurality of paths each of which is between two edge nodes in the routing graph and specifies a route through the virtual network for a data message flow from an external machine of the entity.

2. The method of claim 1, wherein generating the routing graph comprises:

defining a plurality of nodes representing a plurality of forwarding elements in the two public cloud datacenters of the two public cloud providers;

defining a link between each pair of nodes that correspond to two forwarding elements that are communicatively connected through one or more networks; and

assigning a cost value to each link to represent a cost associated with using the two forwarding elements corresponding to the link'"'"'s node pair to forward a data message for the entity.

3. The method of claim 2, wherein performing the path-search processes comprises:

using a set of defined links to define each identified path between two edge nodes in the routing graph;

for each of a plurality of identified path, using a set of cost values associated with the path'"'"'s set of defined links to compute a cost for the path; and

for at least a first pair of edge nodes, using the computed costs for a plurality of paths between the first pair of edge nodes to select one path as the designated path for the first pair of edge nodes.

4. The method of claim 2, wherein performing the path-search processes further comprises for at least a second pair of edge nodes, using the computed costs for a plurality of paths between the second pair of edge nodes to select at least two paths as two designated paths for the second pair of edge nodes, said two designated paths for performing multi-path operations.

5. The method of claim 2, wherein the cost value for each link relates to at least one of:

(i) data message throughput speed of a network connection between the two forwarding elements corresponding to the two nodes connected by the link,

(ii) data message loss metric of the network connection,

(iii) a financial expense associated with the network connection, and

(iv) a financial expense associated with a data compute node that is associated with one or both of the forwarding elements corresponding to the two nodes connected by the link.

6. The method of claim 5, wherein the financial expense for the network connection or for the data compute node is an expense charged by one or more public cloud providers.

7. The method of claim 1, wherein each of at least two different edge nodes connects to multi-machine compute locations of the entity, in order to connect the machines at the connected compute location to machines at another compute location.

8. The method of claim 7, wherein at least one compute location is a branch office or private datacenter of the entity.

9. The method of claim 1, wherein at least one edge node connects to a datacenter of a SaaS (Software as a Service) provider of the entity.

10. The method of claim 1 further comprising iteratively performing path-search processes to identify new paths between edges nodes in the routing graph to account for changes in conditions in the public cloud datacenters, said changes including changes to network conditions.

11. The method of claim 1 further comprising:

for each of a plurality of forwarding elements, collecting individual measurements quantifying quality of connections between the forwarding element and other forwarding elements operating in the public cloud datacenters;

from the collected measurements, generating an overall measurement value for each of the plurality of forwarding elements; and

generating a measurement graph based on the generated measurements values,

wherein generating the routing graph comprises generating the routing graph based on the measurement graph.

12. The method of claim 11, wherein both the routing and measurement graphs comprise (i) a plurality of nodes representing a plurality of forwarding elements in the two public cloud datacenters of the two public cloud providers, and (ii) links between each of a plurality of pairs of nodes, the method further comprising:

including in the routing graph each link in the measurement graph that represents a connection with a generated measurement value that exceeds a threshold value; and

not including in the routing graph each link in the measurement graph that represents a connection with a generated measurement value that is below a threshold value.

13. The method of claim 11, wherein generating the routing graph comprises:

defining the routing graph to have the same forwarding-element nodes and links as the measurement graph; and

from the routing graph, removing any link that represents a forwarding-element connection that has a generated measurement value that falls below a threshold value.

14. The method of claim 13 further comprising distributing the routes specified by the identified paths to the forwarding elements in the public cloud datacenters.

15. A non-transitory machine readable medium storing a program for defining routes for data message flows associated with an entity through a virtual network defined over a plurality of public cloud datacenters, the program for execution by at least one hardware processing unit, the program comprising sets of instructions for:

generating a routing graph that comprises a plurality of nodes representing a plurality of forwarding elements in at least two public cloud datacenters of two different public cloud providers, wherein at least a set of nodes are edge nodes that connect to external machines of the entity that are outside of the public cloud datacenters; and

performing path-search processes to identify a plurality of paths each of which is between two edge nodes in the routing graph and specifies a route through the virtual network for a data message flow from an external machine of the entity.

16. The non-transitory machine readable medium of claim 15, wherein the set of instructions for generating the routing graph comprises sets of instructions for:

defining a plurality of nodes representing a plurality of forwarding elements in the two public cloud datacenters of the two public cloud providers;

defining a link between each pair of nodes that correspond to two forwarding elements that are communicatively connected through one or more networks; and

assigning a cost value to each link to represent a cost associated with using the two forwarding elements corresponding to the link'"'"'s node pair to forward a data message for the entity.

17. The non-transitory machine readable medium of claim 16, wherein the set of instructions for performing the path-search processes comprises sets of instructions for:

using a set of defined links to define each identified path between two edge nodes in the routing graph;

for each of a plurality of identified path, using a set of cost values associated with the path'"'"'s set of defined links to compute a cost for the path; and

for at least a first pair of edge nodes, using the computed costs for a plurality of paths between the first pair of edge nodes to select one path as the designated path for the first pair of edge nodes.

18. The non-transitory machine readable medium of claim 16, wherein the set of instructions for performing the path-search processes further comprises a set of instructions for using the computed costs for a plurality of paths between the second pair of edge nodes to select at least two paths as two designated paths for the second pair of edge nodes, said two designated paths for performing multi-path operations.

19. The non-transitory machine readable medium of claim 16, wherein the cost value for each link relates to at least one of:

(i) data message throughput speed of a network connection between the two forwarding elements corresponding to the two nodes connected by the link,

(ii) data message loss metric of the network connection,

(iii) a financial expense associated with the network connection, and

(iv) a financial expense associated with a data compute node that is associated with one or both of the forwarding elements corresponding to the two nodes connected by the link.

20. The non-transitory machine readable medium of claim 19, wherein the financial expense for the network connection or for the data compute node is an expense charged by one or more public cloud providers.