Toeplitz Hash Algorithm
From HandWiki
| General | |
|---|---|
| Related to | Receive Side Scaling |
The Toeplitz Hash Algorithm describes hash functions that compute hash values through matrix multiplication of the key with a suitable Toeplitz matrix.[1] The Toeplitz Hash Algorithm is used in many network interface controllers for receive side scaling.[2][3]
As an example, with the Toeplitz matrix [math]\displaystyle{ T }[/math] the key [math]\displaystyle{ k }[/math] results in a hash [math]\displaystyle{ h }[/math] as follows:
- [math]\displaystyle{ 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} }[/math]
where the entries are bits and all operations are modulo 2. In implementations the highly redundant matrix is not necessarily explicitly stored.
References
- ↑ Krawczyk, Hugo (1995). "New Hash Functions for Message Authentication". EUROCRYPT '95. 921. 301–310. doi:10.1007/3-540-49264-X_24.
- ↑ "Scaling in the Linux Networking Stack". Archived from the original on 22 May 2014. https://web.archive.org/web/20140522233520/https://www.kernel.org/doc/Documentation/networking/scaling.txt. Retrieved 2014-05-22.
- ↑ "Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS". Archived from the original on 22 May 2014. https://web.archive.org/web/20140522235610/http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc. Retrieved 2014-05-22.
 |  |
