Distributed Stateful Load Balancer

A method comprising:

• storing, by a first load balancer comprising a cache, a first portion of a distributed hash table, wherein the first portion of the distributed hash table comprises a first range of hash keys, and wherein the first load balancer is in communication with a second load balancer that stores a second portion of the distributed hash table comprising a second range of hash keys;
• receiving, by the first load balancer, a packet, wherein a hash value calculated for the packet does not fall in the first range of hash keys;
• identifying, by the first load balancer and based on the hash value, that the second load balancer stores data that identifies a path associated with the packet;
• querying, by the first load balancer, the second load balancer to identify the path associated with the packet;
• receiving, by the first load balancer, the data that identifies the path;
• and
• forwarding, by the first load balancer and along the path, the packet to a network element.

A computer storage medium having computer-executable instructions stored thereon that, when executed by a processor, cause the processor to perform operations comprising:

• storing, at a first load balancer that is in communication with a second load balancer, a first portion of a distributed hash table, wherein the first portion of the distributed hash table comprises a first range of hash keys, and wherein the second load balancer stores a second portion of the distributed hash table comprising a second range of hash keys;
• receiving a packet, wherein a hash value calculated for the packet does not fall in the first range of hash keys;
• identifying, based on the hash value, that the second load balancer stores data that identifies a path associated with the packet;
• querying the second load balancer to identify the path associated with the packet;
• receiving the data that identifies the path;
• and
• forwarding, along the path, the packet to a network element.