Method for scaling address lookups using synthetic addresses

Patent metadata

Field	Value
Publication number	US-9654409-B2
Application number	US-201414475349-A
Country	US
Kind code	B2
Filing date	Sep 2, 2014
Priority date	Nov 5, 2013
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

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.

First claim

What is claimed is:

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

Assignees

• Cisco Tech Inc

Inventors

• Yadav Navindra
• Sinha Satyam
• Edsall Thomas J
• Alizadeh Attar Mohammadreza
• Chu Kit Chiu

Classifications

• H04L47/56

  implementing delay-aware scheduling · CPC title

• H04L67/22

  Electricity · mapped topic

• H04L69/167

  Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 (translation of Internet protocol [IP] addresses H04L61/2503) · CPC title

• H04L61/2084

  Electricity · mapped topic

• H04L61/6004

  Electricity · mapped topic