Network router search engine using compressed tree forwarding table

Apparatus used to determine next hop addresses of networks to which data packets are to be forwarded, each data packet including an address field containing an address indicative of a network node to which the packet is ultimately to be delivered, the apparatus including memory storing a data structure, the data structure comprising:

• a plurality of routing entries, each routing entry containing a key address, a subnet mask value, and a next hop address which is the address of a network to which packets whose address matches the key address in a number of most-significant bit positions indicated by the subnet mask value are to be forwarded, the routing entries being divided into at least two classes according to subnet mask values such that a first class of routing entries includes level-1 routing entries whose subnet mask values are no more than a first number, and a second class of routing entries include level-2 routing entries whose subnet mask values are greater than the first number and no more than the sum of the first number and a second number, the level-2 routing entries being further divided into groups such that the key addresses of the routing entries within each group match each other in the first number of most significant bit positions;
• and
• a plurality of pointers, the pointers being associated with addresses of packets and being divided into at least two classes according to fields of the addresses with which the pointers are associated, a first class of pointers being level-1 pointers associated with a first field containing the first number of the most significant address bits of the address, and a second class of pointers being level-2 pointers associated with a second sub-field containing the second number of the next most significant address bits of the address, the level-1 pointers being arranged in a level-1 tree indexed by the first field of the address, the level-2 pointers being divided into a plurality of level-2 trees according to groups of the level-2 routing entries with which the level-2 pointers are associated, each level-2 tree being indexed by the second field of the address, the pointers at both the first and second level including real leaf pointers and fill leaf pointers, each real leaf pointer pointing to an associated routing entry having a key address value equal to the index of the pointer in the data structure, each fill leaf pointer pointing to an associated routing entry whose key address value best matches the index of the fill leaf pointer based on the value of the subnet mask, the pointers at the first level including next tree pointers each pointing to a corresponding level-2 tree containing a pointer to a routing entry whose key address is equal to the index of the next tree pointer in the data structure.

Apparatus used to determine the addresses of next hop networks to which data packets are to be forwarded, each data packet including an address field having an address indicative of a network to which the packet is ultimately to be delivered, the apparatus including a memory storing a data structure, the data structure comprising a plurality of pointers, the pointers being associated with addresses of packets and being divided into two or more classes according to fields of the addresses with which the pointers are associated, a first class of pointers being level-1 pointers associated with a first field containing a first number of the most significant address bits of the address, the level-1 pointers being arranged in a level-1 binary tree indexed by the first field of the address, a second class of pointers being level-2 pointers associated with a second sub-field containing a second number of the next most significant address bits of the address, the level-2 pointers being divided into a plurality of level-2 binary trees each being indexed by the second field of the address, the level-1 pointers including next hop pointers and next tree pointers, each next hop pointer identifying the address of a network to which packets having an address whose first field is equal to the index of the next hop pointer in the level-1 binary tree should be forwarded, and each next tree pointer identifying a level-2 binary tree which should be used to determine the address of a network to which packets having an address whose first field is equal to the index of the next tree pointer in the level-1 binary tree should be forwarded, each level-2 binary tree including next hop pointers each identifying the address of a network to which packets having an address whose second field is equal to the index of the next hop pointer in the level-2 binary tree and whose first field is equal to the index of the next tree pointer in the level-1 binary tree that identifies the level-2 tree containing the next hop pointer should be forwarded.

Apparatus used to determine the addresses of next hop networks to which data packets are to be forwarded, comprising:

• a memory for storing a plurality of level pointer blocks and a plurality of forwarding tables, each forwarding table containing data structures associated with values of one or more fields of the address field of the data packets, the data structures containing entries identifying the addresses of next hop networks to which data packets having address sub-fields containing values associated with the data structures are to be forwarded, and each level pointer block being associated with a corresponding different one of the forwarding tables and containing pointers identifying the data structures within the associated forwarding table;
• one or more input buffers operative to receive next hop address lookup requests, each lookup request containing an address and an identifier of a level pointer block to be used in performing the lookup;
• selection logic coupled to the input buffers, the selection logic being operative to select among the following:
• (i) the lookup requests in the different input buffers, (ii) the address and the level pointer block identifier contained in each request, and (iii) the fields of the address contained in each request;
• a cache coupled to the memory, the cache being operative to store for the duration of a lookup a level pointer block retrieved from the memory upon the initiation of the lookup;
• a memory input buffer coupled to the memory, the memory input buffer being operative to store a plurality of forwarding table data structure entries retrieved from the memory during a lookup;
• addressing logic having inputs coupled to the selection logic, the cache, and the memory input buffer, the addressing logic being operative to calculate the addresses of level pointer blocks within the memory and the addresses of forwarding table data structure entries within the memory based on (i) values selected by the selection logic, (ii) values stored in the cache, and (iii) values stored in the memory input buffer, the addressing logic also being operative to provide the calculated addresses to the memory in order to retrieve level pointer blocks and forwarding tables therefrom;
• comparison logic having inputs coupled to the selection logic and the memory input buffer, the comparison logic being operative during a lookup to compare a value selected by the selection logic to one or more forwarding table data structure entries stored in the memory input buffer;
• and
• one or more output buffers coupled to the memory input buffer, each output buffer being associated with a corresponding input buffer, each output buffer being operative to store the results of lookups whose requests are received in the associated input buffer and to provide the results as responses to the lookup requests, the result of each lookup including a next hop address from a selected forwarding table data structure entry stored in the memory output buffer, the selected entry being the entry indicated by the comparison logic as matching the value selected by the selection logic.