Exploiting Degrees of Freedom for Efficient Hashing in Network Applications

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:6685b7aae2f2b08021122492d14cde1b

ZINK, Thomas, Marcel WALDVOGEL, 2011. Exploiting Degrees of Freedom for Efficient Hashing in Network Applications

@misc{Zink2011Explo-13356, title={Exploiting Degrees of Freedom for Efficient Hashing in Network Applications}, year={2011}, author={Zink, Thomas and Waldvogel, Marcel} }

Hashing has yet to be widely accepted as a component of hard real-time systems and hardware implementations, due to still ex- isting prejudices concerning the unpredictability of space and time re- quirements resulting from collisions. While in theory perfect hashing can provide optimal mapping, in practice, finding a perfect hash function is too expensive, especially in the context of high-speed applications.<br />The introduction of hashing with multiple choices, d-left hashing and Bloom filter-based hash table summaries, has caused a shift towards guaranteed single-DRAM access. However, these guarantees come at a high price. High amounts of rare and expensive high-speed SRAM needs to be traded off for predictability. Moreover, it is infeasible for many applications to provide enough on-chip memory.<br />In this paper we show that previous suggestions suffer from the false pre- condition of full generality. To provide a workable solution, our approach exploits four individual degrees of freedom available in many practical applications, especially hardware and high-speed lookups. This reduces the requirement of on-chip memory up to an order of magnitude at the cost of only minute amounts of additional hardware. Our design makes fast hash table implementations cheaper, more predictable and above all, more practical. Exploiting Degrees of Freedom for Efficient Hashing in Network Applications Waldvogel, Marcel 2011-05-24T11:22:24Z deu deposit-license 2011-05-24T11:22:24Z Zink, Thomas 2011 Waldvogel, Marcel Zink, Thomas

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

Report1.pdf 130

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto