Virtual router function sharding for scalable multi-tenant routing

1 . A method comprising:

receiving, at an ingress of a multi-tenant network, a data packet, the data packet including a Virtual Network Identifier (VNI) identifying a corresponding tenant for the data packet in the multi-tenant network;

determining, at the ingress, a corresponding cluster of routers for processing the data packet by:

parsing an encapsulation header of the data packet to identify the VNI;

determining, using a stateless algorithmic method applied to the VNI, a shard index associated with the VNI, wherein the stateless algorithmic method is one of a modulo operation or bitmasking of bits of the VNI; and

mapping the shard index to an identifier of the corresponding cluster of routers associated with the VNI, wherein the corresponding cluster of routers is one of a plurality of clusters of routers in the multi-tenant network; and

forwarding the data packet to a router in the corresponding cluster of routers for processing.

2 . The method of claim 1 , wherein the ingress is a virtualized network function layer configured to parse the data packet for determining the VNI in the data packet.

3 . The method of claim 1 , wherein the ingress is any router in the multi-tenant network.

4 . The method of claim 1 , wherein the identifier of the corresponding cluster of routers is a Virtual IP (VIP) address of the corresponding cluster of routers.

5 . The method of claim 1 , wherein the router is in a same Layer 2 domain as remaining routers in the corresponding cluster of routers, and

forwarding the data packet to the router comprises:

altering a Media Access Control (MAC) address in the data packet to reach the router; or

forwarding the data packet to the router using an encapsulation protocol.

6 . The method of claim 1 , wherein a control plane of each router in a given cluster of the plurality of clusters of routers receives route updates for VNIs associated with the given cluster of the plurality of clusters of routers.

7 . A network element of a multi-tenant network, comprising:

one or more memories having computer-readable instructions stored therein; and

one or more processors configured to execute the computer-readable instructions to:

receive a data packet, the data packet including a Virtual Network Identifier (VNI) identifying a corresponding tenant for the data packet in the multi-tenant network;

determine a corresponding cluster of routers for processing the data packet by:

parsing an encapsulation header of the data packet to identify the VNI;

determining, using a stateless algorithmic method applied to the VNI, a shard index associated with the VNI, wherein the stateless algorithmic method is one of a modulo operation or bitmasking of bits of the VNI; and

mapping the shard index to an identifier of the corresponding cluster of routers associated with the VNI, wherein the corresponding cluster of routers is one of a plurality of clusters of routers in the multi-tenant network; and

forward the data packet to a router in the corresponding cluster of routers for processing.

8 . The network element of claim 7 , wherein the network element is a virtualized network function layer configured to parse the data packet for determining the VNI in the data packet.

9 . The network element of claim 7 , wherein the network element is any router in the multi-tenant network.

10 . The network element of claim 7 , wherein the identifier of the corresponding cluster of routers is a Virtual IP (VIP) address of the corresponding cluster of routers.

11 . The network element of claim 7 , wherein the router is in a same Layer 2 domain as remaining routers in the corresponding cluster of routers, and

the one or more processors are configured to execute the computer-readable instructions to forward the data packet to the router by:

altering a Media Access Control (MAC) address in the data packet to reach the router; or

forwarding the data packet to the router using an encapsulation protocol.

12 . The network element of claim 7 , wherein a control plane of each router in a given cluster of the plurality of clusters of routers receives route updates for VNIs associated with the given cluster of the plurality of clusters of routers.

13 . One or more non-transitory computer-readable media comprising computer-readable instructions, which when executed by one or more processors at an ingress of a multi-tenant network, cause the ingress to:

receive a data packet, the data packet including a Virtual Network Identifier (VNI) identifying a corresponding tenant for the data packet in the multi-tenant network;

determine a corresponding cluster of routers for processing the data packet by:

parsing an encapsulation header of the data packet to identify the VNI;

determining, using a stateless algorithmic method applied to the VNI, a shard index associated with the VNI, wherein the stateless algorithmic method is one of a modulo operation or bitmasking of bits of the VNI; and

mapping the shard index to an identifier of the corresponding cluster of routers associated with the VNI, wherein the corresponding cluster of routers is one of a plurality of clusters of routers in the multi-tenant network; and

forward the data packet to a router in the corresponding cluster of routers for processing.

14 . The one or more non-transitory computer-readable media of claim 13 , wherein the ingress is a virtualized network function layer configured to parse the data packet for determining the VNI in the data packet.

15 . The one or more non-transitory computer-readable media of claim 13 , wherein the ingress is any router in the multi-tenant network.

16 . The one or more non-transitory computer-readable media of claim 13 , wherein the identifier of the corresponding cluster of routers is a Virtual IP (VIP) address of the corresponding cluster of routers.

17 . The one or more non-transitory computer-readable media of claim 13 , wherein the router is in a same Layer 2 domain as remaining routers in the corresponding cluster of routers, and

the execution of the computer-readable instructions cause the ingress to forward the data packet to the router by:

altering a Media Access Control (MAC) address in the data packet to reach the router; or

forwarding the data packet to the router using an encapsulation protocol.

18 . The method of claim 1 , wherein a control plane of each router in a given cluster of the plurality of clusters subscribes to receiving route updates for VNIs having shard indices mapped to the given cluster.

19 . The network element of claim 7 , wherein a control plane of each router in a given cluster of the plurality of clusters subscribes to receiving route updates for VNIs having shard indices mapped to the given cluster.

20 . The one or more non-transitory computer-readable media of claim 13 , wherein a control plane of each router in a given cluster of the plurality of clusters subscribes to receiving route updates for VNIs having shard indices mapped to the given cluster.