Back to results
US 2020/0287831 A1Published application
Load Balancing Using Dynamically Resizable Consistent Hashing
AssigneeArista Networks, Inc.
InventorPeter Lam
Life of this patent
Estimating the term…
Abstract
Packet forwarding includes creating a first lookup table for mapping packets to nodes based on the number of nodes in a first set of nodes. A received packet is mapped to a mapping value using a predetermined mapping function. The first lookup table is indexed using a first subset of bits comprising the mapping value. A second lookup table is created in response to adding a node to the first set of nodes. A subsequently received packet is mapped to a mapping value using the same predetermined mapping function to index the second lookup table using a second subset of bits comprising the mapping value.
Claims20
A method in a network device, the method comprising:
- forwarding a received packet to a node in a first plurality of nodes using a first subset of bits of a mapping value, computed from the received packet with a predetermined mapping function, as an address of an entry in a first lookup table comprising a plurality of entries that are associated with the first plurality of nodes, the received packet being forwarded to the node associated with the addressed entry, the first subset of bits selected from the mapping value according to a first set of bit positions;
- creating a second lookup table in response to a new node being added to the first plurality of nodes to define a second plurality of nodes, each entry in the first lookup table corresponding to two or more entries in the second lookup table, each entry in the second lookup table being associated with either the same node as its corresponding entry in the first lookup table or the new node;
- and
- forwarding a subsequently received packet to a node from among the second plurality of nodes using a second subset of bits of a mapping value, computed from the subsequently received packet with the predetermined mapping function, as an address of an entry in the second lookup table, the subsequently received packet being forwarded to the node associated with the addressed entry, the second subset of bits selected from the mapping value according to a second set of bit positions, the second set of bit positions including the first set of bit positions plus one or more additional bit positions.
1 more element
An apparatus comprising:
- one or more computer processors;
- and
- a computer-readable storage medium comprising instructions for controlling the one or more computer processors to be operable to:
- forward a received packet to a node in a first plurality of nodes using a first subset of bits of a mapping value, computed from the received packet with a predetermined mapping function, as an address of an entry in a first lookup table comprising a plurality of entries that are associated with the first plurality of nodes, the received packet being forwarded to the node associated with the addressed entry, the first subset of bits selected from the mapping value according to a first set of bit positions;
- create a second lookup table in response to a new node being added to the first plurality of nodes to define a second plurality of nodes, each entry in the first lookup table corresponding to two or more entries in the second lookup table, each entry in the second lookup table being associated with either the same node as its corresponding entry in the first lookup table or the new node;
- and
- forward a subsequently received packet to a node from among the second plurality of nodes using a second subset of bits of a mapping value, computed from the subsequently received packet with the predetermined mapping function, as an address of an entry in the second lookup table, the subsequently received packet being forwarded to the node associated with the addressed entry, the second subset of bits selected from the mapping value according to a second set of bit positions, the second set of bit positions including the first set of bit positions plus one or more additional bit positions.
4 more elements
A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a computer device, cause the computer device to:
- forward a received packet to a node in a first plurality of nodes using a first subset of bits of a mapping value, computed from the received packet with a predetermined mapping function, as an address of an entry in a first lookup table comprising a plurality of entries that are associated with the first plurality of nodes, the received packet being forwarded to the node associated with the addressed entry, the first subset of bits selected from the mapping value according to a first set of bit positions;
- create a second lookup table in response to a new node being added to the first plurality of nodes to define a second plurality of nodes, each entry in the first lookup table corresponding to two or more entries in the second lookup table, each entry in the second lookup table being associated with either the same node as its corresponding entry in the first lookup table or the new node;
- and
- forward a subsequently received packet to a node from among the second plurality of nodes using a second subset of bits of a mapping value, computed from the subsequently received packet with the predetermined mapping function, as an address of an entry in the second lookup table, the subsequently received packet being forwarded to the node associated with the addressed entry, the second subset of bits selected from the mapping value according to a second set of bit positions, the second set of bit positions including the first set of bit positions plus one or more additional bit positions.
1 more element
Dependencies are inferred from the claim text.