Distributed tenant overlay network with centralized routing control plane

A system comprising:

• one or more processors;
• and
• one or more non-transitory computer-readable media storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
• provisioning an overlay network, wherein:
• each tenant of multiple tenants hosted by a forwarding plane of the overlay network is configured to send routing packets to a routing control plane of the overlay network, the routing packets indicating respective destinations that are served by each tenant;
• and
• the routing control plane of the overlay network is configured to, based at least in part on receiving the routing packets, determine routing paths between each tenant of the multiple tenants and the respective destinations;
• receiving, at a first tenant of the multiple tenants, a routing packet including an indication of a first destination that is served by the first tenant;
• forwarding the routing packet to the routing control plane based at least in part on determining that the routing packet includes the indication;
• and
• receiving, at a second tenant of the multiple tenants and from the routing control plane, routing data indicative of at least a portion of a routing path between the second tenant and the first destination.