Toeplitz Hash Algorithm: Difference between revisions

Toeplitz Hash
General
Related to	Receive Side Scaling

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Inline

Revision as of 14:13, 6 September 2019

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 $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.

References

^ Krawczyk, Hugo (1995). "New Hash Functions for Message Authentication". 921: 301–310. doi:10.1007/3-540-49264-X_24. ISSN 0302-9743. {{cite journal}}: Cite journal requires |journal= (help)
^ "Scaling in the Linux Networking Stack". Archived from the original on 22 May 2014. Retrieved 2014-05-22. {{cite web}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help)
^ "Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS". Archived from the original on 22 May 2014. Retrieved 2014-05-22. {{cite web}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help)

This computer-programming-related article is a stub. You can help Wikipedia by expanding it.

[Krawczyk1995-1] Krawczyk, Hugo (1995). "New Hash Functions for Message Authentication". 921: 301–310. doi:10.1007/3-540-49264-X_24. ISSN 0302-9743. {{cite journal}}: Cite journal requires |journal= (help)

[kernel-org-scaling-2] "Scaling in the Linux Networking Stack". Archived from the original on 22 May 2014. Retrieved 2014-05-22. {{cite web}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help)

[microsoft-ndis-rss-3] "Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS". Archived from the original on 22 May 2014. Retrieved 2014-05-22. {{cite web}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help)

[1]

[2]

[3]

@@ Line 20: / Line 20: @@
 The '''Toeplitz Hash Algorithm''' describes [[hash function]]s that compute hash values through [[matrix multiplication]] of the key with a suitable [[Toeplitz matrix]].<ref name="Krawczyk1995">{{cite journal|last1=Krawczyk|first1=Hugo|title=New Hash Functions for Message Authentication|volume=921|year=1995|pages=301–310|issn=0302-9743|doi=10.1007/3-540-49264-X_24}}</ref> The Toeplitz Hash Algorithm is used in many [[Network interface controller|network interface controllers]] for receive side scaling.<ref name="kernel-org-scaling">{{cite web|url=https://www.kernel.org/doc/Documentation/networking/scaling.txt|title=Scaling in the Linux Networking Stack|accessdate=2014-05-22|archiveurl=https://web.archive.org/web/20140522233520/https://www.kernel.org/doc/Documentation/networking/scaling.txt|archivedate=22 May 2014|deadurl=no}}</ref><ref name="microsoft-ndis-rss">{{cite web|url=http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc|title=Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS|accessdate=2014-05-22|archiveurl=https://web.archive.org/web/20140522235610/http://download.microsoft.com/download/5/D/6/5D6EAF2B-7DDF-476B-93DC-7CF0072878E6/NDIS_RSS.doc|archivedate=22 May 2014|deadurl=no}}</ref>
+As an example, with the Toeplitz matrix <math>T</math> the key <math>k</math> results in a hash <math>h</math> as follows:
+<!-- in python: import scipy as sc; T=sc.linalg.toeplitz([1,0,1],[1,1,0,1]); k=[1,1,0,0]; h=T.dot(k)%2; print('h =',h) -->
+:<math>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==