Method for sharding address lookups

• US 9,716,665 B2
• Filed: 08/28/2014
• Issued: 07/25/2017
• Est. Priority Date: 11/05/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yadav, Navindra, Alizadeh Attar, Mohammadreza, Chu, Kit Chiu, Sinha, Satyam, Edsall, Thomas J.
• Primary Examiner(s): Pasia, Redentor
• Assistant Examiner(s): MAK, PETER K
• Application Number:
  US14/472,148
• Publication Number:
  US 20150124820A1
• Time in Patent Office: 1,062 Days
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 2101/695 using masks or ranges of addresses
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04L 61/5084 Providing for device mobility network addressing or numbering for mobility support in wireless networks H04W8/26; mobile IP H04W80/04
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Various embodiments of the present disclosure provide methods for randomly mapping entries in a suitable lookup table across multiple switch devices and/or multiple switch chipsets in each of the multiple switch devices by using two or more independent hash functions. In some embodiments, the number of entries in the lookup table is equal to be the least common multiple of all possible M (i.e., a number of switch devices) choosing R values (i.e., a desired redundancy level).

Claims

1. A computer-implemented method, comprising:

receiving an incoming packet;

determining an address of the incoming packet;

generating a pointer by hashing the address of the incoming packet, the pointer pointing into a shard table, wherein the shard table has a number of entries that is equal to a least common multiple of M and a combination of M choose R values, wherein M represents a number of multiple switch devices and R represents an integer from one to M;

selecting one or more corresponding entries in the shard table according to the pointer;

based at least upon the one or more corresponding entries in the shard table, determining a specific switch device from the multiple switch devices to send the incoming packet; and

sending the incoming packet to the specific switch device.

2. The computer-implemented method of claim 1, wherein the address of the incoming packet is a media access control (MAC), Internet protocol version 4 (IPv4), Internet protocol version 6 (IPv6), or synthetic address.

3. The computer-implemented method of claim 1, wherein each of the multiple switch devices include two or more switch chipsets, a portion of the shard table residing on each of the two or more switch chipsets in the multiple switch devices.

4. The computer-implemented method of claim 3, wherein the address of the incoming packet resides on multiple chipsets of the multiple switch devices depending on a redundancy level, the multiple switch chipsets of the multiple switch devices belonging to different switch devices.

5. The computer-implemented method of claim 3, wherein the pointer is generated according to one of a plurality of hash functions, hash functions in the plurality of hash functions being distinctive from each other, further comprising:

hashing the address of the incoming packet according to the one of the plurality of hash functions; and

generating the pointer by taking modulo M of an outcome of the hashing the address of the incoming packet, wherein M is a number of entries in the shard table.

6. The computer-implemented method of claim 5, wherein each entry in the shard table has R bits set to a value “

1”

, wherein R is a redundancy level representing a number of times each address is stored on one or more chipsets of the multiple switch devices.

7. The computer-implemented method of claim 5, further comprising:

hashing the one or more corresponding entries in the shard table according to two or more hash functions selected from the plurality of hash functions, the two or more hash functions being distinctive from the one of the plurality of hash functions that was used to hash the address of the incoming packet; and

determining one or more switch chipsets to send the incoming packet by taking modulo N of an outcome of the hashing the one or more corresponding entries in the shard table, wherein N is a number of switch chipsets in each of the multiple switch devices.

8. The computer-implemented method of claim 7, further comprising:

determining a specific switch chipset to send the incoming packet by using one or more hash functions from the plurality of hash functions, the one or more hash functions being distinctive from the one of the plurality of hash functions used to hash the address of the incoming packet and the two or more hash functions used to hash the one or more corresponding entries in the shard table.

9. The computer-implemented method of claim 8, further comprising:

in response to the specific switch chipset being indeterminable, asserting a nonvalidshard signal to cause an address of the incoming packet to be changed to a configured IP address; and

forwarding the incoming packet to a particular switch device according to the configured IP address to determine an ultimate destination for the incoming packet.

10. The computer-implemented method of claim 1, further comprising:

in response to a change in M or R, updating a subset of the entries in the shard table based at least upon the change; and

removing addresses that are no longer needed in one or more switch chipsets of the multiple switch devices.

11. 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;

determine an address of the incoming packet;

generate a pointer by hashing the address of the incoming packet, the pointer pointing into a shard table, wherein the shard table has a number of entries that is equal to a least common multiple of M and a combination of M choose R values, wherein M represents a number of multiple switch devices and R represents an integer from one to M;

select one or more corresponding entries in the shard table according to the pointer;

based at least upon the one or more corresponding entries in the shard table, determine a specific switch device from the multiple switch devices to send the incoming packet; and

send the incoming back to the specific switch device.

12. The system of claim 11, wherein each of the multiple switch devices include two or more switch chipsets, a portion of the shard table residing on each of the two or more switch chipsets in the multiple switch devices.

13. The system of claim 12, wherein the pointer is generated according to one of a plurality of hash functions, hash functions in the plurality of hash functions being distinctive from each other, and wherein the instructions when executed further cause the system to:

hash the address of the incoming packet according to the one of the plurality of hash functions; and

generate the pointer by taking modulo M of an outcome of the hashing the address of the incoming packet, wherein M is a number of entries in the shard table.

14. The system of claim 13, wherein the instructions when executed further cause the system to:

hash the one or more corresponding entries in the shard table according to two or more hash functions selected from the plurality of hash functions, the two or more hash functions being distinctive from the one of the plurality of hash functions that was used to hash the address of the incoming packet; and

determine one or more switch chipsets to send the incoming packet by taking modulo N of an outcome of the hashing the one or more corresponding entries in the shard table, wherein N is a number of switch chipsets in each of the multiple switch devices.

15. The system of claim 14, wherein the instructions when executed further cause the system to:

determine a specific switch chipset to send the incoming packet by using one or more hash functions from the plurality of hash functions, the one or more hash functions being distinctive from the one of the plurality of hash functions used to hash the address of the incoming packet and the two or more hash functions used to hash the one or more corresponding entries in the shard table.

16. The system of claim 11, wherein the instructions when executed further cause the system to:

in response to a change in M or R, update a subset of the entries in the shard table based at least upon the change, wherein each of the multiple switch devices include two or more switch chipsets, a portion of the shard table residing on each of the two or more switch chipsets in the multiple switch devices; and

remove addresses that are no longer needed in the switch chipsets of the multiple switch devices.

17. 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;

determine an address of the incoming packet;

generate a pointer by hashing the address of the incoming packet, the pointer pointing into a shard table, wherein the shard table has a number of entries that is equal to a least common multiple of M and a combination of M choose R values, wherein M represents a number of multiple switch devices and R represents an integer from one to M;

select one or more corresponding entries in the shard table according to the pointer;

based at least upon the one or more corresponding entries in the shard table, determine a specific switch device from the multiple switch devices to send the incoming packet; and

send the incoming back to the specific switch device.