Hash table-based and extended memory-based high-performance IPv6 address searching method

Abstract

The invention discloses a hash table searching-based and extended memory searching-based IPv6 address searching scheme. A system comprises one searching classifier, one updating classifier, seven parallel hash processing units, six extended memory processing units, seven hash collision processing units and one priority comparing unit. The first six hash processing units are correlated with the corresponding extended memories in two stages and combined with the corresponding hash collision processing units to form six paths of processing modules; the seventh hash processing unit and the corresponding hash collision processing unit form one path of processing module; and the seven paths of modules searches the IPv6 address in parallel so as to determine the next hop of information. Due to the adoption of the method, the searching operation of the IPv6 address is finished in one to two storage periods in combination with the principle of hash searching and extended memory searching according to the distribution rule of the prefix of the IPv6 address. The method has high searching and updating performance and high extensibility, so that the method is a searching scheme suitable for the high-performance IPv6 router.

Description

Technical field [0001] The invention relates to a method for searching routing table entries in a high-speed IPv6 router, and to be precise, to an IPv6 address searching method adopting a hash table and extended memory, and belongs to the technical field of IPv6 network equipment routing and forwarding. Background technique [0002] The IP router acts as a bridge in the network, connecting multiple small networks into a large network and communicating with each other through the IP (Internet Protocol) protocol. The main function of the router is the forwarding of IP data packets, that is, receiving IP data packets from the input interface, and according to the destination address in the IP packet header, find the corresponding output interface information from the routing information table RIB (Routing Information Base). Then forward the IP packet to the corresponding output interface to complete the packet forwarding function. [0003] In order to solve the problem of the rapid g...

AI Technical Summary

Problems solved by technology

[0005] Existing IPv6 address lookup methods are designed directly or indirectly using the traditional IPv4 address lookup scheme. Since the lookup keyword increases from 32 bits to 128 bits, there are many problems in this design idea. For example, using TCAM to IPv6 address lookup will greatly increase the design cost and system power consumption. The routing table with the same number of entries must be cascaded with multi-level TCAM to complete the lookup work. In this way, the high cost and The large power consumption prevents this scheme from being directly applied; using the Trie tree and its derivative algorithms (for example: layer compression Trie tree, path compression Trie tree, multi-bit Trie tree, etc.) will make the number of memory accesses become Doubling, resulting in greater lookup delay and lower system lookup efficiency; using the lookup method based on memory expansion will increase the storage cost exponentially. In IPv6 addresses, the most distributed number is the routing prefix with a length of 32 bits. Directly use the method of memory expansion to design, use it as the first level of search, the required memory size is 2 32 bit, coupled with the second-level larger memory, it is impossible to directly apply this scheme to IPv6 address lookup

Images