Efficient hash tables for network applications.

Area of Science:

• Computer Science
• Algorithm Design
• Hardware Acceleration

Background:

• Hashing is not widely adopted in hard real-time systems due to unpredictable performance from collisions.
• Perfect hashing is theoretically optimal but computationally expensive for high-speed applications.
• Existing methods like d-left hashing require significant high-speed SRAM for predictable DRAM access.

Purpose of the Study:

• To address the limitations of current hashing techniques in real-time systems.
• To propose a more practical and predictable hashing solution for hardware and high-speed lookups.
• To reduce the reliance on expensive on-chip memory while maintaining performance.

Main Methods:

• Exploiting four specific degrees of freedom in practical applications.
• Developing a hashing approach tailored for hardware and high-speed lookup scenarios.
• Designing a system that guarantees constant lookup and update times.

Main Results:

• Reduced on-chip memory requirements by up to an order of magnitude.
• Guaranteed constant lookup and update times.
• Achieved these improvements with only minor additional hardware.

Conclusions:

• The proposed hashing method overcomes the limitations of previous general-purpose approaches.
• This design makes efficient hash table implementations cheaper, more predictable, and more practical for real-time systems.
• It offers a viable solution for applications requiring deterministic memory access without excessive hardware costs.