Network router search engine using compressed tree forwarding table

• US 6,192,051 B1
• Filed: 02/26/1999
• Issued: 02/20/2001
• Est. Priority Date: 02/26/1999
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Redstone Communications, Inc. (Siemens AG)
• Inventors: Lipman, Michael E., Heyda, Russell L.
• Primary Examiner(s): Rao, Scema S.
• Assistant Examiner(s): Tsegaye, Saba
• Application Number:
  US09/259,064
• Time in Patent Office: 725 Days
• Field of Search: 370/254, 370/256, 370/235, 370/238, 370/389, 370/400, 370/408, 370/390, 370/392, 370/393, 370/396, 709/238, 709/241, 709/242
• US Class Current: 370/389
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

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.

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.

2. Apparatus according to claim 1, wherein the forwarding table further comprises a third-level table having entries associatively addressable by a third field of address bits from the address field of the packets, and wherein the second-level table is operative to provide a pointer to the third-level table for those packets having addresses for which the first and second fields of address bits are not sufficient to determine the next hop address, and the third-level table is operative to provide a next hop index indicative of the next hop address for those packets having addresses for which the first, second and third fields of address bits are sufficient to determine the next hop address.

3. Apparatus according to claim 2, wherein the forwarding table further comprises a table at each of one or more additional levels, each table having entries associatively addressable by a corresponding additional field of address bits from the address field of the packets, wherein each table is operative to provide a pointer to the table in the next level for those packets having addresses for which the address bits from the first field through the corresponding additional field are not sufficient to determine the next hop address, and each table is operative to provide a next hop index indicative of the next hop address for those packets having addresses for which the address bits from the first field through the corresponding additional field are sufficient to determine the next hop address.

4. Apparatus according to claim 1, wherein the second-level table is a sparse second-level table containing fewer entries than the number of unique values of the second field of the address, and wherein the forwarding table further comprises a dense second-level table being directly addressable by the second field of address bits from the address field of the packets, and wherein (i) the first-level table is operative to selectively provide pointers to the sparse and dense second-level tables based on the first field of the address field of the packets, (ii) the sparse second-level table provides a next hop index indicative of the next hop address when a pointer to the sparse second-level table is provided by the first-level table for a given packet, and (iii) the dense second-level table provides a next hop index indicative of the next hop address when a pointer to the dense second-level table is provided by the first-level table for a given packet.

5. Apparatus according to claim 4, wherein the number of storage locations in the dense second-level table is equal to the number of unique values of the second address field, the number of pointers stored in the dense second-level table is greater than or equal to a first number substantially smaller than the number of unique values of the second address field, the number of pointers stored in the sparse second-level table is less than the first number, and the number of storage locations in the sparse second-level table is the smallest multiple of a storage block size that is sufficient to store the number of pointers stored in the sparse second-level table.

6. Apparatus according to claim 5, wherein the number of unique values of the second address field is 256 and the first number is 32.

7. Apparatus according to claim 1, wherein the forwarding table further comprises a third-level table having entries associatively addressable by a third field of address bits from the address field of the packets, and wherein one of the second-level tables is operative to provide a pointer to the third-level table for those packets having addresses for which the first and second fields of address bits are not sufficient to determine the next hop address, and the third-level table is operative to provide a next hop index indicative of the next hop address for those packets having addresses for which the first, second and third fields of address bits are sufficient to determine the next hop address.

8. Apparatus according to claim 1, wherein the forwarding table further comprises additional second-level tables each having entries associatively addressable by the second field of address bits from the address field of the packets, and wherein the first-level table is operative to selectively provide pointers to the different second-level tables based on the first field of the address field of the packets, and each second-level table provides a next hop index indicative of the next hop address when a corresponding pointer to the respective second-level table is provided by the first-level table for a given packet.

9. Apparatus according to claim 8, wherein the forwarding table further comprises a mapping table operative to map each pointer in the first-level table to a corresponding second-level table.

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.