A Hash-based Routing Lookup Algorithm

With the rapid development of Internet, the interface rate of backbone routers is up to 100Gbit/s. Core routers must process a ten million or more packets per second, and the most important step of forwarding process is to lookup routing table, so that high-speed routing lookup algorithm is the major technology to improve router performance. In this paper, the specific design of classical route lookup algorithm is researched. The advantages and disadvantages of the existing route lookup algorithm are analyzed, and a new route lookup algorithm which could improve the routing lookup speed is given. Paper is studied on the following aspects.First, a variety of classical routing lookup algorithms are discussed, the problems of the routing lookup algorithm and the performance parameters of routing lookup algorithm are analyzed, and the complexity of all routing lookup algorithm is analyzed. Second, a hash routing lookup algorithm based on full binary tree of hierarchical is proposed, which focuses on the search to find the prefix between 16 and 24 bits. The distribution of IP routing prefix is fully considered, so that the speed of routing lookup algorithm could greatly increased. Third, one optimized hash dynamic load balancing strategy is given, which used in routing lookup algorithm. The disadvantage is that the hash algorithm will produce a hash collision. the optimized hash dynamic load balancing strategy could effectively reduce the probability of hash collisions, which could improve the performance of the hash algorithm. Hence, it could improve the performance of routing lookup algorithm. Finally, simulation experiments show that the routing lookup algorithm based on full binary tree of hierarchical hash is significantly better than the previous algorithm.