Apparatus and method for searching trie trees using masks with non-symbol boundaries and flooding default routes in a massively parallel router

摘要

A router comprising a switch fabric and routing nodes coupled to the switch fabric. Each routing node comprises a trie tree search table for storing routing information associated with received variable length subnet masks. The trie tree search table comprises a plurality of stages that are searched by N-bit address symbols derived from the received variable length subnet masks. Each routing node also comprises a control processor for generating the stages associated with the trie tree search table. The control processor generates for each entry in a first one of the plurality of stages: 1) an end flag indicating whether each entry is a leaf or a branch; 2) a subnet flag indicating whether a subnet mask ends at each entry; and 3) a masked flag indicating whether a subnet mask ending at each entry ends on a boundary of an N-bit address symbol associated with entry.