Publication Details
Adaptive Development of Hash Functions in FPGA-Based Network Routers
Kořenek Jan, doc. Ing., Ph.D. (DCSY)
Sekanina Lukáš, prof. Ing., Ph.D. (DCSY)
Evolution, hash function, Cuckoo hash, feedback shift register, IP, FPGA, Zynq
Accelerated network technologies are crucial for implementing packet processing
in high-speed computer networks and therefore, network routers accelerated by
field-programmable gate arrays (FPGAs) are becoming common. One of the
time-critical jobs in routers is packet classification which requires rapid
lookup in tables. Fast hash computation is a must in order to process the packets
in time. Adaptive development of hash functions is proposed in this paper. The
hash functions are based on non-linear feedback shift registers and configured by
an evolutionary algorithm. The hash functions are developed inside of an
FPGA-based network router and fine-tuned for the given table content. The
experiments on the problem of hashing Internet Protocol (IP) addresses
demonstrate that the evolved simple hash functions provide faster hash
computation, better memory resource utilization and require smaller chip area in
comparison with conventional hash functions. The best conventional hash function
was able to store by a couple of hundred less IP addresses in a 8k hash table,
the computation of hashes was by 42% slower, and the implementation required
15-times more hardware area.
@inproceedings{BUT131001,
author="Roland {Dobai} and Jan {Kořenek} and Lukáš {Sekanina}",
title="Adaptive Development of Hash Functions in FPGA-Based Network Routers",
booktitle="2016 IEEE Symposium Series on Computational Intelligence",
year="2016",
pages="1--8",
publisher="IEEE Computational Intelligence Society",
address="Athens",
doi="10.1109/SSCI.2016.7850171",
isbn="978-1-5090-4240-1",
url="http://ieeexplore.ieee.org/document/7850171/"
}