Projekte

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

This report discusses our proposed improvements to Fast Hash Ta- bles (FHT) which we name 'Efficient Hash Table' (EHT) where 'efficient' relates to both memory efficiency and lookup performance. The mecha- nism we use to design the EHT lead to improvements in terms of sram memory requirements by the factor of ten over the FHT. Our results back the theoretical analysis and allow accurate predictions. A cost function is provided that allows the adjustment of EHT parameter to different user requirements.

Efficient IPv6 packet forwarding is still a major bottleneck in todays networks. Especially in the internet core we are faced with very large routing tables and a high number of high-speed links. In addition economical restrains exist in terms of manufacturing and operation costs. So demand is high for efficient IPv6 packet forwarding mechanisms. In the last few years a lot of work has been done on hash tables and summaries that allow compact representations and constant lookup time. The features sound attractive for IPv6 routing, thus a survey and evaluation of these data structures seems appropriate.