DocumentCode :
1905428
Title :
Hybrid open hash tables for network processors
Author :
Ye, Qing ; Parson, Dale ; Cheng, Liang
Author_Institution :
Dept. of Comput. Sci. & Eng., Lehigh Univ., Bethlehem, PA, USA
fYear :
2005
fDate :
12-14 May 2005
Firstpage :
113
Lastpage :
117
Abstract :
Packet classification by analyzing the traffic header information is an essential task of network processors. To efficiently store, retrieve and update information, key-based data accessing algorithms such as hashing are usually used to improve the processing performance. In this paper, we propose the hybrid open hash, a composite algorithm that combines open addressing hash tables with the temporal responsiveness of incremental garbage collection. By dynamically switching between a novel table with incremental construction via selective copying of used entries, and an aged table with incremental cleaning via emptying of deleted entries, this algorithm solves the structural problem of conventional open hashing due to remnants left by deleted keys. Thus, it increases the data accessing speed. We also implement and compare our algorithm with Brutil, the latest proposed hashing mechanism designed for real-time embedded systems, from the concurrency issue of multithreading to the performance simulation by taking the real traffic information to construct hashed keys. Our results show that hybrid open hash has better performance. Several possible enhancement approaches are also discussed to improve the performance further.
Keywords :
embedded systems; file organisation; table lookup; Brutil; dynamically switching; hybrid open hash tables; incremental cleaning; key-based data accessing algorithms; network processors; packet classification; real-time embedded systems; traffic header information; Aging; Algorithm design and analysis; Cleaning; Concurrent computing; Delay; Embedded system; Information analysis; Information retrieval; Real time systems; Telecommunication traffic;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Switching and Routing, 2005. HPSR. 2005 Workshop on
Print_ISBN :
0-7803-8924-7
Type :
conf
DOI :
10.1109/HPSR.2005.1503205
Filename :
1503205
Link To Document :
بازگشت