Response: Improving Flow Based Hashing on ECMP with Cuckoo hashing

There are many algorithms that can be used to for flow-based hashing to provide the best load balancing method over multiple IP or Ethernet connections but I recently learned that Cuckoo Hashing the preferred method.

Ember

Since I’ve only known about simpler mechanisms using XOR or similar functions to calculate the path hash I will be adding this to my question for SDN vendors when they offer a multi-path solution. This Wikipedia article explain the Cuckoo Hashing and its reasonably obvious why this works better for networking – odd numbers of paths, faster performance and relatively low memory use.

The basic idea is to use two hash functions instead of only one. This provides two possible locations in the hash table for each key. In one of the commonly used variants of the algorithm, the hash table is split into two smaller tables of equal size, and each hash function provides an index into one of these two tables.

Cuckoo hashing – Wikipedia, the free encyclopedia.

  • http://gplus.to/kduda Kenneth Duda

    Greg, I don’t think this makes any sense. To use cuckoo hashing for flow distribution across LAG members, you’d need the ASIC to keep state about which hash function a given flow is using, so that it could use the same hash function for all packets on that flow. But if you’re going to keep per-flow state, then you can simply select the least-loaded link at the time the flow shows up, and you don’t need hashing at all, cuckoo or otherwise.

    In other words, Cuckoo hashing is dramatically more expensive than ordinary flow hashing (because of the need to keep per-flow state on chip), and if you’re willing to pay that cost, then Cuckoo hashing is uncompetitive with a simpler scheme, namely, picking the least loaded link.

    Am I missing anything?

    -Ken

    Kenneth Duda
    CTO & SVP Software
    Arista Networks, Inc.