Method for Reading and Writing Forwarding Information Base, and Network Processor

摘要

A method for reading and writing a forwarding information base, including receiving a write an associated data (AD) request used to modify the AD and a write a keyword (Key) request used to modify the Key corresponding to the AD, and before the write AD request and the write Key request pass through a cache, transforming, when any one stage to be read and written includes the Key, a row address in the write AD request into a row address that is same as a row address of a node block on which the Key is located, or transforming, when any one stage to be read and written does not include the Key, a row address in the write AD request and a row address in the write Key request into a same row address in the any one stage.

主权项

1. A method for reading and writing a forwarding information base (FIB), wherein the FIB is of a binary search tree (Btree) structure and comprises a non-leaf node and a leaf node, wherein the non-leaf node is used to store a keyword (Key), wherein the leaf node is used to store associated data (AD) corresponding to the Key, wherein a storage location of the FIB comprises an on-chip memory and an off-chip memory, wherein the off-chip memory stores n+1 stages with sequence numbers being from 0 to n, wherein each stage comprises k branches of nodes, wherein n is an integer greater than or equal to 0, wherein k is a positive integer, wherein the nodes corresponding to a same storage address in each stage are one node block, and wherein the method comprises:
receiving, by a network processor (NP), a write AD request used to modify the AD and a write Key request used to modify the Key corresponding to the AD, wherein the write AD request and the write Key request are sent by a central processing unit (CPU) of a network device on which the NP is located, wherein the write AD request carries a row address of a node block on which the AD is located, wherein the write Key request carries a row address of a node block on which the Key is located, and wherein the row address of the node block on which the Key is located and the row address of the node block on which the AD is located are not in a same stage; and transforming, when any one stage to be read and written comprises the Key, the row address in the write AD request into another row address that is same as the row address of the node block on which the Key is located, when the any one stage is to be read and written, and before the write AD request and the write Key request pass through a cache; or transforming, when the any one stage to be read and written does not comprise the Key, the row address in the write AD request and the row address in the write Key request into same row address in the any one stage, when the any one stage is to be read and written, and before the write AD request and the write Key request pass through the cache, in order to read and write the any one stage according to the same row address.