Method for scaling address lookups using synthetic addresses
Various examples of the present disclosure provide methods for unifying various types of end-point identifiers, such as IPv4 (e.g., Internet protocol version 4 represented by a VRF and an IPv4 address), IPv6 (e.g., Internet protocol version 6 represented by a VRF and an IPv6 address) and L2 (e.g., Layer-2 represented by a bridge domain (BD) and a media access control (MAC) address), by mapping end-point identifiers to a uniform space (e.g., a synthetic IPv4 address and a synthetic VRF) and allowing different forms of lookups to be uniformly handled. In some examples, a lookup database residing on a switch device can be sharded into a plurality of lookup table subsets, each of which resides on a different one of multiple switch chipsets (e.g., Tridents) in the switch device.
1. A computer-implemented method, comprising:
receiving an incoming packet;
encapsulating the incoming packet with an outer IP address to generate an encapsulated packet;
generating a synthetic IP address for the incoming packet according to a hash algorithm by concatenating a virtual network identifier (VNID) of the incoming packet and the outer IP address of the encapsulated packet;
generating a pointer by hashing the synthetic IP address of the incoming packet, the pointer pointing into a lookup table of a proxy function module that resides on each of a plurality of switch systems, and wherein the hashing is performed using a hash algorithm that has an input including at least one of a combination of: an IPv4 address and a VNID, an IPv6 address and a VNID, or a MAC address and a VNID, and wherein the lookup table includes a plurality of lookup table subsets, and each of the plurality of switch systems contains two or more switch chipsets, each of the plurality of lookup table subsets residing on a different one of the two or more switch chipsets in one of the plurality of switch systems;
selecting one of the switch systems to send the incoming packet;
selecting one of the two or more switch chipsets in the selected switch system to send the incoming packet, a selected switch chipset containing a lookup table subset including one or more entries corresponding to the pointer;
in response to a longest prefix match (LPM) hit, duplicating the synthetic IP address of the incoming packet into each of the plurality of lookup table subsets; and
sending the incoming packet to the selected switch chipset of the selected switch system.
2. The computer-implemented method of claim 1 , further comprising:
in response to a determination that the pointer is not correlated to any entry in the lookup table, sending the incoming packet to a default switch system configured to forward the incoming packet to its destination.
3. The computer-implemented method of claim 1 , further comprising:
in response to a determination that there is a longest prefix match (LPM) hit, duplicating the synthetic IP address of the incoming packet into each lookup table subset residing on the switch chipsets in the plurality of switch systems; and
selecting one of the switch chipsets in the plurality of switch systems to send the incoming packet with load-balancing.
4. The computer-implemented method of claim 1 , further comprising:
in response to a determination that the selected chipset fails, selecting a backup switch chipset in the plurality of switch systems, the backup switch chipset containing a lookup table subset including one or more entries corresponding to the pointer; and
sending the incoming packet to the backup switch chipset.
5. The computer-implemented method of claim 1 , further comprising:
generating the synthetic IP address by hashing an IP address of the incoming packet to a specific bit range of the synthetic IP address.
6. The computer-implemented method of claim 1 , wherein the hash algorithm is Jenkins' one-at-a-time hashing algorithm.
7. The computer-implemented method of claim 1 , wherein the incoming packet has an IP address including at least one of a Layer-2 MAC address, a Layer-3 IPv4 address, or a Layer-3 IPv6 address.
8. A system, comprising:
at least one processor; and
memory including instructions that, when executed by the at least one processor, cause the system to:
receive an incoming packet;
encapsulate the incoming packet with an outer IP address to generate an encapsulated packet;
generate a synthetic IP address for the incoming packet according to a hash algorithm by concatenating a virtual network identifier (VNID) of the incoming packet and the outer IP address of the encapsulated packet;
generate a pointer by hashing the synthetic IP address of the incoming packet, the pointer pointing into a lookup table of a proxy function module that resides on each of a plurality of switch systems, and wherein the hashing is performed using a hash algorithm that has an input including at least one of a combination of: an IPv4 address and a VNID, an IPv6 address and a VNID, or a MAC address and a VNID, and wherein the lookup table includes a plurality of lookup table subsets, and each of the plurality of switch systems contains two or more switch chipsets, each of the plurality of lookup table subsets residing on a different one of the two or more switch chipsets in one of the plurality of switch systems;
select one of the switch systems to send the incoming packet;
select one of the two or more switch chipsets in the selected switch system to send the incoming packet, a selected switch chipset containing a lookup table subset including one or more entries corresponding to the pointer;
in response to a longest prefix match (LPM) hit, duplicating the synthetic IP address of the incoming packet into each of the plurality of lookup table subsets; and
send the incoming packet to the selected switch chipset of the selected switch system.
9. The system of claim 8 , wherein the instructions when executed further cause the system to:
in response to a determination that there is a longest prefix match (LPM) hit, duplicate the synthetic IP address of the incoming packet into each lookup table subset residing on the switch chipsets in the plurality of switch systems; and
select one of the switch chipsets in the plurality of switch systems to send the incoming packet with load-balancing.
10. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of a computing system, cause the computing system to:
receive an incoming packet;
encapsulate the incoming packet with an outer IP address to generate an encapsulated packet;
generate a synthetic IP address for the incoming packet according to a hash algorithm by concatenating a virtual network identifier (VNID) of the incoming packet and the outer IP address of the encapsulated packet;
generate a pointer by hashing the synthetic IP address of the incoming packet, the pointer pointing into a lookup table of a proxy function module that resides on each of a plurality of switch systems, and wherein the hashing is performed using a hash algorithm that has an input including at least one of a combination of: an IPv4 address and a VNID, an IPv6 address and a VNID, or a MAC address and a VNID, and wherein the lookup table includes a plurality of lookup table subsets, and each of the plurality of switch systems contains two or more switch chipsets, each of the plurality of lookup table subsets residing on a different one of the two or more switch chipsets in one of the plurality of switch systems;
select one of the switch systems to send the incoming packet;
select one of the two or more switch chipsets in the selected switch system to send the incoming packet, a selected switch chipset containing a lookup table subset including one or more entries corresponding to the pointer;
in response to a longest prefix match (LPM) hit, duplicating the synthetic IP address of the incoming packet into each of the plurality of lookup table subsets; and
send the incoming packet to the selected switch chipset of the selected switch system.
11. The non-transitory computer-readable storage medium of claim 10 , wherein the instructions when executed further cause the system to:
in response to a determination that the selected chipset fails, select a backup switch chipset in the plurality of switch systems, the backup switch chipset containing a lookup table subset including one or more entries corresponding to the pointer; and
send the incoming packet to the backup switch chipset.