Use of Resillient Hashing to Minimize Flow Remapping

In deployments between network endpoints, it is necessary to preserve established connections and associated Layer 2 and Layer 3 paths. If there is any change in the network, such as failure of a networking device or a server, the packets take a new path.

Resilient hashing reduces the impact of the network change. Each ECMP with resilient hashing is assigned a 256-entry region in the load-balancing table (also known as macro-flow table). Each entry in the table stores member link ID assigned to that macro-flow.

Resilient hashing works as described below:

• Hash incoming packets to one of these macro-flow entries or buckets.

• You then link packets to the paths in the ECMP group.

If we use a "basket" to represent each member link/path, the resilient hashing operations can be modeled as putting buckets (macro flows) into one of the baskets.

If we have N buckets and P paths for ECMP group, use the following sequence:

1. The initial bucket mapping is generated using a round-robin method. Thus, all buckets are almost equally (N/P) distributed among the ECMP group members. Later, the buckets move around based on the path addition or deletion events.

   If N=64 buckets and P=4 paths, you distribute all 64 buckets in a round-robin manner. Since you have 4 paths, there are 4 stacks. Each stack corresponds to one path. Each stack has the same number of buckets, N/P=16.

   

   Last_processed_path= 0 (refer to Step 5 of the algorithm).

2. If there is a path failure or removal, you suddenly remove all the buckets from the failed path/stack and push them into remaining paths/stacks in a circular round-robin manner.

   If you remove path 3 (Stack 3 in the above image), you need to move all the buckets from Stack 3 (orange in the figure below) to remaining stacks.

   

3. If there is a path addition, you suddenly remove N/(P+1) buckets from the existing paths in circular round-robin manner and push them into the newly added path/stack.

   If you add a new path, you need to move N/P+1=64/4=16 buckets from existing stacks (stacks 0, 1, 2). All orange buckets are now back in stack 3, blue stacks are not moved and are intact.

   Last_processed_path= 0

   

4. Circular round-robin direction for Step 2 and Step 3 is opposite. It is important to determine the first stack from which circular round-robin starts. You keep an index pointer last_processed_path that provides the start stack index for Step 2 and before start stack for Step 3.

5. 5. To set last_processed_path, do the following:

   • When you push buckets as in Step 2, last_processed_path is the next stack of the last stack where you pushed the last bucket.

   • When you remove buckets as in Step 3, last_processed_path is the last stack from where the bucket was removed.