Measurement based routing through multiple public clouds

• US 10,666,460 B2
• Filed: 05/04/2018
• Issued: 05/26/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): Aung, Sai
• Application Number:
  US15/972,090
• Publication Number:
  US 20190104051A1
• Time in Patent Office: 753 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 for establishing a virtual network for an entity over a plurality of public cloud datacenters of a plurality of public cloud providers, the method comprising:

deploying first and second sets of forwarding elements in first and second multi-tenant public cloud datacenters operated by first and second public cloud providers;

configuring a set of measurement agents deployed in the first and second public cloud datacenters to obtain measurements regarding connections between forwarding elements in the first and second sets;

based on the obtained measurements, defining virtual-network routes through the first and second set forwarding elements;

distributing said routes to the first and second sets of forwarding elements to configure these elements to implement the virtual network;

wherein a set of controllers aggregates said measurements, and based on the aggregated measurements, defines the virtual-network routes; and

wherein the virtual-network routes are overlay routes established by encapsulating data messages traversing these routes with encapsulation headers that store network addresses for ingress and egress forwarding elements for entering and exiting the virtual network and network addresses of next hop forwarding elements for identifying next hop destinations for traversing the virtual network.

2. The method of claim 1, wherein the measurements include measurements that quantify data message throughput speeds of the connections.

3. The method of claim 1, wherein the measurements include measurements that quantify data message loss values or delay values of the connections.

4. The method of claim 1, wherein the entity and the virtual network are a first entity and a first virtual network, the method further comprising defining virtual-network routes through at least a subset of the first forwarding element set and at least a subset of the second forwarding element set in order to define a second virtual network for a second entity.

5. The method of claim 1, wherein at least a subset of the forwarding elements are also configured to implement virtual networks for other entities, wherein the encapsulation headers also store an entity identifier value that identifies the entity associated with the data message.

6. The method of claim 1, wherein the virtual network is a virtual wide area network (WAN) that connects machines at multiple different machine locations of the entity, said locations including at least two of an office location, a datacenter location, a remote device location, and a SaaS (Software as a Service) provider location.

7. The method of claim 1, wherein the first and second datacenters are in different regions.

8. The method of claim 7, wherein said different regions are different cities, different states, or different countries.

9. The method of claim 1, wherein the measurement agents obtain measurements by sending pinging messages to each other in order to measure signal latency.

10. The method of claim 1, wherein the measurement agents obtain measurements by sending pinging messages to each other in order to measure signal drop rates.

11. A system for establishing a virtual network for an entity over a plurality of public cloud datacenters in a plurality of regions, the system comprising:

a first set of forwarding elements in a first multi-tenant public cloud datacenter in a first region;

a second set of forwarding elements in a second multi-tenant public cloud datacenter in a second region different than the first region;

a set of measurement agents deployed in the public clouds to obtain measurements regarding connections between forwarding elements in the first and second sets;

a set of controllers to aggregate said measurements and to define virtual-network routes through the first and second set forwarding elements, said routes distributed to the first and second sets of forwarding elements to configure these elements to implement the virtual network; and

wherein the virtual-network routes are overlay routes established by encapsulating data messages traversing these routes with encapsulation headers that store network addresses for ingress and egress forwarding elements for entering and exiting the virtual network and network addresses of next hop forwarding elements for identifying next hop destinations for traversing the virtual network.

12. The system of claim 11, wherein the measurements include measurements that quantify at least one of data message throughput speeds, data loss rates, and data delay values of the connections.

13. The system of claim 11, wherein at least a subset of the forwarding elements are also configured to implement virtual networks for other entities, wherein the encapsulation headers also store an entity identifier value that identifies the entity associated with the data message.

14. The system of claim 11, wherein the virtual network is a virtual wide area network (WAN) that connects machines at multiple different machine locations of the entity, said locations including at least two of an office location, a datacenter location, a remote device location, and a SaaS (Software as a Service) provider location.

15. The system of claim 11, wherein the measurement agents obtain measurements by sending pinging messages to each other.