Routing lookup method, routing lookup device and method for constructing B-Tree tree structure

Abstract

Disclosed are a routing lookup method and device, and a construction method for a B-Tree structure. The device comprises: a routing lookup algorithm software module, a routing update interface module and a routing lookup hardware module, wherein the routing lookup algorithm software module is set to execute software calculations and update entry instruction issuance for a routing entry; the routing update interface module is set to control a data stream of the routing lookup hardware module according to the actual operating state of the routing lookup hardware module after receiving the update entry instruction issued by the routing lookup algorithm software module, and write an update entry into a memory of the routing lookup hardware module; and the routing lookup hardware module is set to respond to a routing lookup request of a hardware system and return a lookup result of the longest prefix match to the hardware system, wherein the routing lookup hardware module is in a pipelined architecture. By means of the present invention, a hardware pipeline operation is realized, the number of pipeline stages is small, and the volume is not sensitive to the routing prefix distribution.

Description

technical field [0001] The invention relates to the field of network switching, in particular to a route search method and device, and a method for building a B-Tree tree structure. Background technique [0002] With the rapid development of the Internet, the interface rate of the core router used for the interconnection of the backbone network reaches 100Gbps, which requires the core router to achieve a route lookup rate of several million times per second under the condition of supporting a large-capacity routing table. The Internet Protocol (IP) search needs to obtain the longest matching prefix. Due to the need for high-speed search, the software search method is no longer applicable. In recent years, researchers have proposed a variety of hardware search methods to improve the search rate. Among them, Trie Tree structures and Ternary Content Addressable Memory (TCAM for short) are the most popular. [0003] The Trie tree structure is the most widely used tree structure...

AI Technical Summary

Problems solved by technology

[0005] Aiming at the problem that the memory consumption of the route search scheme in the related art is relatively large and affects the efficiency of the route search, the present invention provides a route search method and device, and a method for constructing a B-Tree tree structure to solve the above technical problems

Images