Research On The Storage Structure Based On Hash Forwarding

The router with high forwarding capacity is a core device of high-speed network. Whether the router achieves high-performance forwarding is an essential factor in nowadays network development. Router lookup is the key technology in the packet forwading process, so the speed of the router lookup directly influences the performance of router packet forwarding. And it has also been a major constrain to improve network performance.The research on route lookup technology is taken widely attention. The reason is mainly attributed to two aspects: First, the lookup speed; Second, the memory consumption. This paper focuses on these two aspects. The basic working principle of the router is brief introductioned. The existing router lookup algorithms are reviewed and compared both in their space complexity and time complexity. After that, two high performance algorithms for different application are proposed.Chapter 3 briefly introduces the tranditional storage structure based on Hash forwarding. On these basics, a noval router lookup algorithms based on variable series Hash forwarding algorithms is proposed. This algorithm proposes a principle based on multi-level Hash table storage structure, which can significantly reduce the number of memory access, improved the routing lookup speed. Usually, twice is enough. Then, this algorithm realizes a customizable series, tradeing-off the primary and secondary between the router lookup speed and memory strorage based on the router configuration (memory, performance and etc.) according to the produce users'(router developers') requirements for chooseing the series of the custom Hash table. Moreover, a node adding method based on father-son relationship is proposed. It can greatly reduce the conflicting time in the traditional Hash table lookup, maximum increasing the search efficiency. The experiments show that our algorithm has better performances both in time and meory consumption compared to traditional algorithms.Chapter 4 proposes an improvement on the storage structure from the forwarding table of the tranditional algorithms. It presents a storage structure of the forwarding that prefix hop and next hop separted. Then, set a relationship between separated prefix hop and next hop, making them find another position quickly. This algorithm greatly saves memory in the space and avoids the slow refreshing problem when the next hop address information is changing. The experiments show that this method is optimized to achieve the good performance.Two router lookup algorthims mentioned before, the one based on variable series Hash table can apply to the the High-end routers for improving the handle speed in the backbone network. Likewise, it can be used in medium-end router to satisfy the processing speed and memory consumption needs. The other one based on separated storage structure can apply to low-end router or medium-end router, which is limited in memory consumption.