High Performance Hash Mechanism Research And Implementation Based On Split Model

The IP lookup algorithm is one of the key technology of modern IP routers or switches in TCP/IP network.With increasing popularity of the Internet,the network size continues to increase,the scale of routing table is ever-increasing.The Internet has confronted with more and more serious challenges in mem ory efficiency.Most existing solutions that achieve high memory efficiency have a poor update performance or complicated lookup logics,but the split model could achieve the both.By contrast,the split model can sharply compress the on-chip memory consumption while improve the update and lookup performance,at the cost of low off-chip memory efficiency.But this cost is the key reason limits its application in practice.As such,this paper focuses on the split model and aims at improving the off-chip memory efficiency with only a reasonable additional on-chip cost.And this paper will across the split model from theory to practice last gap.Firstly,with the split model deeply searched and analyzed,it has the character of the fixed range for the hash key and the hash entries can be easily grouped.A Key-Mapping based Group Hashing(KMGH)mechanism is proposed with an fixed-size on-chip array for key mapping.Besides,the off-chip hash table is divided into groups according to the on-chip split trie structure,each of which is associated with a linked list for all candidate hash slots.Although the key-mapping array will consume some on-chip memory,the gains on off-chip are so significant that the overall tradeoff is still reasonable in practice.According to the evaluation experiments,KMGH can compress the off-chip memory by 70% at least,while consuming only 256 KB more on-chip memories.Furthermore,the combination of split model and KMGH outperforms the existing excellent algorithm in both on-chip and off-chip memory efficiency,achieving improvements over 80% and 90% respectively.In addition,this paper further studied the KMGH mechanism used into multi-step prefix tree with leaf pushed.This paper proposed a set of efficient hash fusion algorithm(Hash Group Fusion algorithm,HGFA),and three step preferred algorithm(three-level optimal Strides algorithm,TOSA),dynamic programming method to determine the optimum step length,and presented a comprehensive assessment quota for system-level deployments.And it successfully applied split model with KMGH mechanism into outstanding algorithm.Experiments show that without changing the nature and advantages of the algorithm,the algorithm based on split model and KMGH mechanism can be significantly improved not only in on-chip memory but also in off-chip memory.