Network router search engine using compressed tree forwarding table
First Claim
1. Apparatus for identifying a next hop address of a network to which packets should be forwarded, the apparatus comprising a memory storing a forwarding table, the forwarding table comprising a first-level table having entries directly addressable by a first field of address bits from an address field of the packets, and a second-level table having entries associatively addressable by a second field of address bits from the address field of the packets, the first-level table being operative to provide (i) a next hop index indicative of a next hop network address for those packets having addresses for which the first field of address bits is sufficient to determine the next hop address, and (ii) a pointer to the second-level table for those packets having addresses for which the first field of address bits is not sufficient to determine the next hop address, and the second-level table being operative to provide a next hop index indicative of a next hop network address for those packets having address for which the first and second fields of address bits are sufficient to determine the next hop address.
2 Assignments
0 Petitions
Accused Products
Abstract
Network routing apparatus employs multi-level tree data structures in a centralized routing table and in distributed forwarding tables. Each level of each structure is associated with a different field of a network address appearing in received packets. Pointers in each structure are used to identify either an address of a next hop network, or a next-level tree to be examined for a next-hop address. An uncompressed tree routing table uses directly addressed trees in order to simplify the storage and retrieval of pointers, and the next-tree pointers directly identify next trees. Compressed tree forwarding tables are generated from the uncompressed routing table by reducing the number of pointers stored at one or more levels to substantially the number of unique next hop addresses associated with network addresses at that level. A single mapping table maps pointer values at one level to the locations of trees at the next level in the compressed trees. Next hop address lookup logic performs lookups in accordance with the structure of the compressed trees. Also, the lookup logic stores and selectively operates on multiple forwarding tables in order to provide support for virtual router operation.
-
Citations
14 Claims
- 1. Apparatus for identifying a next hop address of a network to which packets should be forwarded, the apparatus comprising a memory storing a forwarding table, the forwarding table comprising a first-level table having entries directly addressable by a first field of address bits from an address field of the packets, and a second-level table having entries associatively addressable by a second field of address bits from the address field of the packets, the first-level table being operative to provide (i) a next hop index indicative of a next hop network address for those packets having addresses for which the first field of address bits is sufficient to determine the next hop address, and (ii) a pointer to the second-level table for those packets having addresses for which the first field of address bits is not sufficient to determine the next hop address, and the second-level table being operative to provide a next hop index indicative of a next hop network address for those packets having address for which the first and second fields of address bits are sufficient to determine the next hop address.
-
10. A method of operating a network device, comprising the steps of:
-
establishing and maintaining an uncompressed multi-level tree routing table, each level of the routing table containing at least one table directly addressable by a corresponding field of an address field of received packets, each table being operative to provide a pointer indicative of an address of a next hop network to which packets are to be forwarded, the number of unique pointer values in each table being substantially less than the number of pointers in the table; and
periodically creating an updated compressed multi-level tree forwarding table from the uncompressed routing table and distributing the updated forwarding table to forwarding controllers within the network device for use by the forwarding controllers in routing packets received by the network device, the compressed forwarding table containing at least one table at each of one or more levels, each table reflecting the same forwarding information as a counterpart table of the uncompressed routing table using a number of pointers substantially equal to the number of unique pointer values.
-
-
11. 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.
-
-
12. 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.
-
13. A method of operating a network device, comprising the steps of:
-
establishing and maintaining at a centralized controller within the network device a multi-level tree routing table, each level of the routing table containing one or more binary trees indexed by a corresponding field of an address field of received packets, each location in each binary tree containing a pointer to a routing entry indicating the address of a next hop network to which packets whose address contains the index value of the pointer are to be routed, the number of routing entries associated with each binary tree being generally being less than the number of pointers, so that in general multiple pointers in a given binary tree point to the same routing entry; and
periodically creating an updated compressed multi-level tree forwarding table from the uncompressed routing table and distributing the updated forwarding table to forwarding controllers within the network device for use by the forwarding controllers in routing packets received by the network device, the compressed forwarding table containing binary trees at one or more levels, each binary tree reflecting the same forwarding information as a counterpart binary tree of the routing table using a number of pointers substantially equal to the number of unique routing entries associated with the counterpart binary tree.
-
-
14. 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.
-
Specification