Method and device for updating routing lookup tree

Abstract

The invention discloses a method for updating a routing lookup tree. The method comprises the following steps: determining an update level mark table and node update information according to an updated entry when determining that a routing lookup tree needs to be updated; sequentially selecting levels from the routing lookup tree as the current layer; and if that the current layer needs to be updated is determined according to the update level mark table, locking an upper layer of the current layer in the lookup tree and synchronizing the node update information to the current layer of the lookup tree, and so on, and completing the updating of the routing lookup tree until that the current layer is the last layer needing to be updated is determined according to the update level mark table. The invention further discloses a device for updating a routing lookup tree. By the adoption of the method and the device of the invention, the time of lookup blocking during routing lookup tree updating can be reduced, and the possibility of packet error or packet loss caused by simultaneous conduction of updating and lookup can be reduced.

Description

technical field [0001] The invention relates to routing management technology of a network processor (NP, Network Processor), in particular to a method and device for updating a routing search tree. Background technique [0002] NP is a programmable chip for network data packet processing. It not only has the low price and high flexibility of a general-purpose processor, but also has the characteristics of high performance and scalability of a dedicated chip (ASIC, Application Specific Integrated Circuit). It is considered to be the core technology for the development of the next generation network. [0003] Due to the need for high-speed lookup, the method of completely using software update for the routing table is no longer applicable. In recent years, there are two methods for updating the routing table in NP: one is to lock the routing lookup before updating the routing table. Stop searching until the update router is completed, and then restart the routing search; how...

AI Technical Summary

Problems solved by technology

[0003] Due to the need for high-speed lookup, the method of completely using software update for the routing table is no longer applicable. In recent years, there are two methods for updating the routing table in NP: one is to lock the routing lookup before updating the routing table. Stop the lookup until the update of the router is completed, and then restart the route lookup; however, due to the long locking time of this method, the blocking lookup time will also become longer

The other is to update the table entry while routing lookup; however, this method will cause conflicts between lookup and update access table entry memory, resulting in wrong packet lookup and packet loss

[0004] It can be seen that the method for updating the NP routing table in the prior art either takes a long time to block the search, or may cause error packets or packet loss

Images