Resilient Hashing With Compression

A network device comprising:

• a processor configured to:
• maintain a compressed partition and an uncompressed partition for a logical hash table, wherein the logical hash table comprises a first set of mappings between bucket identifiers and active next-hop destinations in a group of next-hop destinations,
• wherein the compressed partition comprises a second set of mappings between compressed indices and the active next-hop destinations, the second set corresponding to a first subset of the first set, each compressed index in the second set addressing C consecutive bucket identifiers in the first set, and
• wherein the uncompressed partition comprises a third set of mappings between uncompressed indices and the active next-hop destinations, the third set corresponding to a second subset of the first set, each uncompressed index in the third set addressing a single bucket identifier in the first set;
• receive a network packet;
• compute a hash value using a portion of the network packet;
• and
• when the hash value is addressed by a compressed index of a first mapping in the compressed partition, send the network packet to the first mapping's active next-hop destination.

A non-transitory computer readable storage medium having stored thereon program code executable by a network device, the program code comprising:

• code that causes the network device to maintain a compressed partition and an uncompressed partition for a logical hash table, wherein the logical hash table comprises a first set of mappings between bucket identifiers and active next-hop destinations in a group of next-hop destinations,
• wherein the compressed partition comprises a second set of mappings between compressed indices and the active next-hop destinations, the second set corresponding to a first subset of the first set, each compressed index in the second set addressing C consecutive bucket identifiers in the first set, and
• wherein the uncompressed partition comprises a third set of mappings between uncompressed indices and the active next-hop destinations, the third set corresponding to a second subset of the first set, each uncompressed index in the third set addressing a single bucket identifier in the first set;
• code that causes the network device to receive a network packet;
• code that causes the network device to compute a hash value using a portion of the network packet;
• and
• when the hash value is addressed by a compressed index of a first mapping in the compressed partition, code that causes the network device to send the network packet to the first mapping's active next-hop destination.