Reduced traversal for consistent hashing for packet flow load balancing

A computing device comprising:

• a memory configured to store a hash ring that includes a plurality of buckets, wherein a non-zero subset of the plurality of buckets each includes a different output value of a plurality of output values, and a remaining subset of the plurality of buckets each includes an empty value;
• and
• one or more processors configured to:
• replace the empty value in each of the remaining subset of the plurality of buckets with the respective different output value of the plurality of output values, wherein the respective different output value includes a nearest adjacent output value from the different output values of the plurality of output values stored to the non-zero subset of the plurality of buckets in either a counterclockwise or clockwise traversal of the hash ring;
• receive, after replacing the empty value in each of the remaining subset of the plurality of buckets, a key value;
• apply a hash function to the key value to identify a bucket of the plurality of buckets;
• and
• output the output value associated with the identified bucket.

A network device comprising:

• a plurality of interface cards;
• a packet forwarding engine configured to:
• store a hash ring that includes a plurality of buckets, wherein a non-zero subset of the plurality of buckets each includes a different output value of a plurality of output values that each identify a different one of the plurality of interface cards, and a remaining subset of the plurality of buckets each includes an empty value;
• and
• replace the empty value in each of the remaining subset of the plurality of buckets with the respective different output value of the plurality of output values, wherein the respective different output value includes a nearest adjacent output value from the different output values of the plurality of output values stored to the non-zero subset of the plurality of buckets in either a counterclockwise or clockwise traversal of the hash ring;
• receive a packet;
• apply a hash function to the packet to identify a bucket of the plurality of buckets;
• and
• forward the packet to an interface card of the plurality of interface cards using the different output value stored to the identified bucket to load balance the packet across the plurality of interface cards.