Patent ID: 8780926

Claim:
A computer-implemented method for updating stored data structures representing network forwarding information used for network route lookup, the stored data structures corresponding to a plurality of levels of sub-trie data structures of a prefix-compressed trie representation of forwarding information from a routing table, each of the plurality of levels including at least one sub-trie data structure, and each of the sub-trie data structures including one or more nodes, the one or more nodes including a root node at the root of the sub-trie data structure which stores, in on-chip memory, one of (1) next hop information if the root node has associated next hop information, or (2) a null value if the root node does not have associated next hop information, wherein the null value indicates that next hop information to be used for the root node of the sub-trie data structure is located in the root node of an upper level, and wherein information defining nodes other than root nodes are stored in off-chip memory, the computer-implemented method comprising: a) receiving, by a forwarding device, information about a new route to be included as forwarding information in the sub-trie data structures, wherein the information about the new route includes an address prefix and an address length; b) identifying, by the forwarding device and using the received address prefix and address length, a node in a destination sub-trie data structure to which the new route forwarding information will be stored in; c) storing in the off-chip memory, by the forwarding device, the new route forwarding information in the identified node, wherein the identified node is located in a first sub-trie at a first level; and d) updating in the on-chip memory, by the forwarding device, the root node of any sub-trie data structures that are both (1) descendants of the identified node, and (2) located at a second level which is one level below the first level which includes the identified node, with the new route forwarding information.