Defining and distributing routes for a virtual network

• US 10,686,625 B2
• Filed: 05/04/2018
• Issued: 06/16/2020
• Est. Priority Date: 10/02/2017
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Cidon, Israel, Dar, Chen, Venugopal, Prashanth, Zohar, Eyal, Markuze, Alex, Bergman, Aran
• Primary Examiner(s): Waqas, Saad A.
• Application Number:
  US15/972,104
• Publication Number:
  US 20190104053A1
• Time in Patent Office: 774 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:

deploying, in a plurality of public cloud datacenters, a plurality of virtual machines (VMs) to operate as edge routers for the virtual network to connect machines outside of the public cloud datacenters;

based on a set of one or more optimization criteria, identifying different paths through different pairs of edge router VMs operating as ingress/egress routers in the public cloud datacenters for data message flows through the virtual network, wherein each path originates and terminates at machines associated with the entity that are located outside of the public cloud datacenters, and traverses at least (i) an ingress VM router deployed in a first public cloud datacenter and (ii) an egress VM router deployed in a second public cloud datacenter;

based on the identified paths, defining routing data for directing a plurality of edge router VMs deployed in a set of two or more public cloud datacenters to route the data message flows along the identified paths through the virtual network, wherein the routing data comprises a plurality of next hop routing records that identify a next hop along each identified path between an ingress VM router at an ingress public cloud datacenter of a data message flow to an egress VM router at an egress public cloud datacenter of the data message flow; and

distributing the routing data to the deployed edge router VMs.

2. The method of claim 1, wherein the set of optimization criteria for a path comprises a length of the path.

3. The method of claim 1, wherein the set of optimization criteria for a path comprises financial cost of the path, said financial cost including a set of costs charged for the edge router VMs by a set of public cloud providers operating a set of public cloud datacenters through which a path traverses.

4. The method of claim 1, wherein the set of optimization criteria for a path comprises minimizing a portion of the path that traverses through a public Internet between different pairs of public cloud datacenters.

5. The method of claim 1, wherein the set of optimization criteria for a path comprises maximizing portions of the path that traverse through high-speed connections between pairs of public cloud datacenters traversed by the path.

6. The method of claim 1, wherein the edge router VMs execute on host computers in the public cloud datacenters.

7. The method of claim 6, wherein at least a set of the edge router VMs execute on a set of host computers in the public cloud datacenters along with other virtual machines that perform compute operations.

8. The method of claim 1, wherein the public cloud datacenters are multi-tenant public cloud datacenters.

9. The method of claim 1, wherein the external machines associated with the entity comprise machines at office locations and private datacenters of the entity and remote user machines.

10. The method of claim 1, wherein the external machines associated with the entity comprise machines at a private datacenter of a SaaS (software as a service) provider of the entity.

11. The method of claim 1, wherein the set of optimization criteria accounts for a set of costs for each hop along an identified path, the set of costs including at least one of:

(a) data message throughput speed of a network connection between two forwarding elements corresponding to the hop,

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

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

(d) a financial expense associated with a data compute node that is associated with one or both of the forwarding elements.

12. The method of claim 11, 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.

13. 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 comprising sets of instructions for:

deploying, in a plurality of public cloud datacenters, a plurality of virtual machines (VMs) to operate as edge routers for the virtual network to connect machines outside of the public cloud datacenters;

based on a set of one or more optimization criteria, identifying different paths through different pairs of edge router VMs operating as ingress/egress routers in the public cloud datacenters for data message flows through the virtual network, wherein each path originates and terminates at machines associated with the entity that are located outside of the public cloud datacenters, and traverses at least (i) an ingress VM router deployed in a first public cloud datacenter and (ii) an egress VM router deployed in a second public cloud datacenter;

based on the identified paths, defining routing data for directing a plurality of edge router VMs deployed in a set of two or more public cloud datacenters to route the data message flows along the identified paths through the virtual network, wherein the routing data comprises a plurality of next hop routing records that identify a next hop along each identified path between an ingress VM router at an ingress public cloud datacenter of a data message flow to an egress VM router at an egress public cloud datacenter of the data message flow; and

distributing the routing data to the deployed edge router VMs.

14. The non-transitory machine readable medium of claim 13, wherein the set of optimization criteria for a path comprises a length of the path.

15. The non-transitory machine readable medium of claim 13, wherein the set of optimization criteria for a path comprises financial cost of the path, said financial cost including a set of costs charged for the edge router VMs by a set of public cloud providers operating a set of public cloud datacenters through which a path.

16. The non-transitory machine readable medium of claim 13, wherein the set of optimization criteria for a path comprises minimizing a portion of the path that traverses through a public Internet between different pairs of public cloud datacenters.

17. The non-transitory machine readable medium of claim 13, wherein the set of optimization criteria for a path comprises maximizing portions of the path that traverse through high-speed connections between pairs of public cloud datacenters traversed by the path.

18. The non-transitory machine readable medium of claim 13, wherein the external machines associated with the entity comprise machines at office locations and private datacenters of the entity and remote user machines.