Perfect Hash Function for High-Speed Searching
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Software-based hash function has been popularly applied to current networking searching area, but it is difficult to meet the demand of high-speed real-time applications in backbone network and services with mass data. In the general design of hardware-based hash function, there are still some drawbacks such as complex logic circuit memory inefficiency, and incremental updates for dataset needed to be solved. This paper proposed a design of hardware perfect hash function on FPGA based on bit-extraction algorithm, using simple bit-selection and bit logic operation. The achievable load factor can be up to 1, and the amortized memory cost of the hash function is about 2.8-5.6 bits/key for 32-bit keys, and the system clock frequency is about 300MHz(Throughput more than 14Gbps). The proposed method can be applied to real-time applications that require high-speed table lookup, e.g. IP address lookup, packet classification, string matching and intrusion detection systems.

    Reference
    1 Dharmapurikar S, Krishnamurthy P, Sproull TS, et al. Deep Packet Inspection Using Parallel Bloom Filters. IEEE Micro, 2004, 24(1):52-61.
    2 杜飞,董治国,苗琳,等.基于无冲突哈希表和多比特树的两级IPv6路由查找算法.计算机应用,2013,33(5):1194-1196.
    3 Xu Y, Liu ZB, Zhang ZY, et al. High-throughput and memory-efficient multimatch packet classification based on distributed and pipelined hash tables. IEEE/ACM Trans. on Networking, 2014, 22(3):982-995.
    4 Baker ZK, Prasanna VK. A computationally efficient engine for flexible intrusion detection. IEEE Trans. on VLSI Systems, 2005, 13(10):1179-1189.
    5 Alicherry M, Muthuprasanna M, Kumar V. High speed matching for network IDS/IPS. Proc. of the IEEE Int. Conf. on Network Protocols. Washington, DC. IEEE CS Press. 2006. 187-196.
    6 Sourdis I, Pnevmatikatos D, Wong S, et al. A reconfigurable perfect-hashing scheme for packet inspection. Proc. of the IEEE Int. Conf. on Field Programmable Logic and Applications. Washington, DC. IEEE CS Press. 2005. 644-647.
    7 Pagh R, Rodler FF. Cuckoo hashing. Journal of Algorithm, 2004, 51(2):122-144.
    8 Ficara D, Giordano S, Kumar S, et al. Divide and discriminate:Algorithm for deterministic and fast hash lookups. Proc. of ACM/IEEE ANCS. Los Alamitos, CA. IEEE CS Press. 2009. 133-142.
    9 Kumar S, Turner J, Crowley P. Peacock hashing:Deterministic and updatable hashing for high performance networking. Proc. of IEEE INFOCOM. Washington, DC. IEEE CS Press. 2008. 101-105.
    10 István Z, Alonso G, Blott M, et al. A flexible hash table design for 10Gbps key-value stores on FPGAs. Proc. of the 23rd Int. Conf. on Field Programmable Logic and Applications(FPL 2013). Washington, DC. IEEE CS Press. 2013. 1-8.
    11 Bando M, Artan NS, Chao HJ. Flashlook:100-gbps hash-tuned route lookup architecture. Proc. of the Int. Conf. on High Performance Switching and Routing. Washington, DC. IEEE CS Press. 2009. 1-8.
    12 Bloom B. Space/time trade-offs in hash coding with allowable errors. Communications of ACM, 1970, 13(7):422-426.
    13 Lu Y, Prabhakar B, Bonomi F. Perfect hashing for network applications. IEEE Symp. on Information Theory. Washington, DC. IEEE CS Press. 2006. 2774-2778.
    14 Song H, Dharmapurikar S, Turner J, et al. Fast hash table lookup using extended bloom filter:An aid to network processing. ACM SIGCOMM. New York. ACM. 2005. 181-192.
    15 Bando M, Artan NS, Chao HJ. Highly memory-efficient loglog hash for deep packet inspection. IEEE GLOBECOM. Washington, DC. IEEE CS Press. 2008. 1-6.
    16 Antichi G, Ficara D, Giordano S, et al. Blooming trees for minimal perfect hashing. IEEE GLOBECOM. Washington, DC. IEEE CS Press. 2008. 1-5.
    17 张良,刘敬浩,李卓.命名数据网络中基于Hash映射的命名检索.计算机工程,2014,40(4):108-111.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王兴,鲍志伟.适用于高速检索的完美Hash函数.计算机系统应用,2016,25(2):250-256

Copy
Share
Article Metrics
  • Abstract:1595
  • PDF: 3622
  • HTML: 0
  • Cited by: 0
History
  • Received:May 16,2015
  • Revised:September 16,2015
  • Online: February 23,2016
Article QR Code
You are the first990465Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063