Toeplitz Hash Algorithm: Difference between revisions
Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Fix complaint about missing journal= parameter in {{cite journal}}. TODO: Explain connection between Toeplitz hash and (truncated) cyclic redundancy check |
||
| Line 19: | Line 19: | ||
}} |
}} |
||
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 |
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 conference|last1=Krawczyk|first1=Hugo|authorlink1=Hugo Krawczyk|title=New Hash Functions for Message Authentication|conference=EUROCRYPT '95|journal=Lecture Notes in Computer Science|volume=921|year=1995|pages=301–310|issn=0302-9743|doi=10.1007/3-540-49264-X_24|doi-access=free}}</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|url-status=live}}</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|url-status=live}}</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: |
As an example, with the Toeplitz matrix <math>T</math> the key <math>k</math> results in a hash <math>h</math> as follows: |
||
Revision as of 02:43, 6 January 2024
| 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 the key results in a hash as follows:
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. Lecture Notes in Computer Science. Vol. 921. pp. 301–310. doi:10.1007/3-540-49264-X_24. ISSN 0302-9743.
- ^ "Scaling in the Linux Networking Stack". Archived from the original on 22 May 2014. Retrieved 2014-05-22.
- ^ "Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS". Archived from the original on 22 May 2014. Retrieved 2014-05-22.
 | This computer-programming-related article is a stub. You can help Wikipedia by expanding it. |