Patent ID: 7551609

Claim:
A method for performing lookup operations on a forwarding information base data structure tangibly embodied in one or more tangible computer-readable media and representative of a plurality of different forwarding information bases, the forwarding information base data structure including a plurality of leaf nodes and an address lookup data structure for identifying leaf nodes of the plurality of leaf nodes based on network addresses and which of the plurality of forwarding information bases is being currently searched, wherein each leaf node of the plurality of leaf nodes includes forwarding information of at least one of the plurality of forwarding information bases for a corresponding network address, the method comprising: performing a lookup operation on an address lookup data structure based on a particular address of a particular packet and an identification that a first forwarding information base of the plurality of forwarding information bases is being currently searched to identify a particular leaf node of the plurality of leaf nodes corresponding to the particular address and the first forwarding information base, the particular leaf node including a plurality of forwarding information fields, with each of the plurality of forwarding information fields corresponding to forwarding information of different said forwarding information bases, the plurality of forwarding information fields including: the first forwarding information field and a second forwarding information field corresponding to a second forwarding information base of the plurality of forwarding information bases; and forwarding the particular packet based on the contents of the first forwarding information field and second forwarding information field without having to perform any further lookup operations on the address lookup data structure.