Toeplitz Hash Algorithm

The Toeplitz Hash Algorithm describes hash functions that compute hash values through matrix multiplication of the key with a suitable Toeplitz matrix. The Toeplitz Hash Algorithm is used in many network interface controllers for receive side scaling.

Toeplitz Hash

General
Related to	Receive Side Scaling

As an example, with the Toeplitz matrix $T$ the key $k$ results in a hash $h$ as follows:

$h=T\cdot k={\begin{pmatrix}1&1&0&1\\0&1&1&0\\1&0&1&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1\\1\\0\\0\\\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\\end{pmatrix}}$

where the entries are bits and all operations are modulo 2. In implementations the highly redundant matrix is not necessarily explicitly stored.