TY - GEN
T1 - A dynamic load-balanced hashing scheme for networking applications
AU - Artan, N. Sertac
AU - Yuan, Haowei
AU - Chao, H. Jonathan
PY - 2008
Y1 - 2008
N2 - Network applications often require large data storage resources, fast queries, and frequent updates. Hash tables support these operations with low costs, yet they cannot provide worst-case guarantees because of hash collisions. Also, the widely used, low-cost Dynamic Random Access Memory (DRAM) cannot suitably accommodate hash tables because DRAMs provide full bandwidth only if accessed in bursts, whereas hash tables require random access. In this paper, we propose a hash co-processor to support hash tables on DRAMs. The co-processor provides a load-balancing method to reduce the impact of hash collisions on the worst-case behavior by moving multiple keys within the hash table in constant time. This leads to a balanced distribution of keys in the hash table despite the collisions. Furthermore, the coprocessor guarantees the full DRAM bandwidth is always utilized by defining all fundamental hash table operations, namely insert, query, and delete, in terms of burst accesses. In the worst case, the query, delete, and insert operations take one, two, and three burst accesses, respectively. The proposed architecture reduces hash overflows by 35% compared to a naive hash table and for each key uses 6.42 bits of on-chip memory.
AB - Network applications often require large data storage resources, fast queries, and frequent updates. Hash tables support these operations with low costs, yet they cannot provide worst-case guarantees because of hash collisions. Also, the widely used, low-cost Dynamic Random Access Memory (DRAM) cannot suitably accommodate hash tables because DRAMs provide full bandwidth only if accessed in bursts, whereas hash tables require random access. In this paper, we propose a hash co-processor to support hash tables on DRAMs. The co-processor provides a load-balancing method to reduce the impact of hash collisions on the worst-case behavior by moving multiple keys within the hash table in constant time. This leads to a balanced distribution of keys in the hash table despite the collisions. Furthermore, the coprocessor guarantees the full DRAM bandwidth is always utilized by defining all fundamental hash table operations, namely insert, query, and delete, in terms of burst accesses. In the worst case, the query, delete, and insert operations take one, two, and three burst accesses, respectively. The proposed architecture reduces hash overflows by 35% compared to a naive hash table and for each key uses 6.42 bits of on-chip memory.
UR - http://www.scopus.com/inward/record.url?scp=67249160140&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67249160140&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2008.ECP.395
DO - 10.1109/GLOCOM.2008.ECP.395
M3 - Conference contribution
AN - SCOPUS:67249160140
SN - 9781424423248
T3 - GLOBECOM - IEEE Global Telecommunications Conference
SP - 2051
EP - 2056
BT - 2008 IEEE Global Telecommunications Conference, GLOBECOM 2008
T2 - 2008 IEEE Global Telecommunications Conference, GLOBECOM 2008
Y2 - 30 November 2008 through 4 December 2008
ER -