METHOD FOR SHARDING ADDRESS LOOKUPS
First Claim
Patent Images
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;
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 multiple switch devices to send the incoming packet; and
sending the incoming packet to the specific switch device.
1 Assignment
0 Petitions
Accused Products
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).
21 Citations
20 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; 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 multiple switch devices to send the incoming packet; and sending the incoming packet to the specific switch device. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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; 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 multiple switch devices to send the incoming packet; and send the incoming back to the specific switch device. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
20. 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 equals a least common multiple of all possible M choosing R values, wherein M is a number of the multiple switch devices and R is a redundancy level; 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 multiple switch devices to send the incoming packet; and send the incoming back to the specific switch device.
-
Specification