Network routing table and packet routing method

• US 6,956,858 B2
• Filed: 06/29/2001
• Issued: 10/18/2005
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Mayan Networks Corporation (Vital Network Services /Koehler/)
• Inventors: Herbert, Thomas A., Herbst, Ryan T., Hariguchi, Yoichi
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Fox, Jamal A.
• Application Number:
  US09/895,972
• Publication Number:
  US 20020080798A1
• Time in Patent Office: 1,572 Days
• Field of Search: 370/395.31, 370/392, 370/312, 370/352, 370/355, 370/356, 370/389, 370/395, 370/432, 370/472, 370/400, 370/351, 370/255, 370/363, 370/368, 370/374, 370/381, 370/386, 370/395.32, 370/395.7, 370/395.71, 370/395.72, 709238-244, 709/245, 709/249, 711/205, 711/206, 711/207, 711/221, 711/117, 711/114, 711/122, 707/2, 707/100, 379272-277
• US Class Current: 370/395.31
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A routing table circuit for a router has one or more input ports and output ports for message communication. In the routing table circuit, one or more routing table memories store a plurality of routing table arrays. The routing table arrays are arranged hierarchically in levels, and each routing table array is associated with a predetermined subset of prefixes. Each routing table array has entries. The entries include a block default route pointer field to store a block default route pointer, if any, and a routing field. The route engine may access any level of table array by using a next level route pointer stored in the routing field. Using the block default route and the routing field, the present invention further reduces the number of memory accesses and the update cost for route insertion and deletion by identifying and skipping elements that do not require route updating.

Claims

1. A routing table circuit for a router having one or more input ports for receiving a message having a destination address, the router having a plurality of output ports for transmitting the message, the routing table circuit comprising:

one or more routing table memories to store a plurality of routing table arrays, said plurality of routing table arrays being arranged hierarchically in a plurality of levels, wherein each of said plurality of routing table arrays is associated with a predetermined subset of prefixes of said destination address, and has entries, said entries including a block default route pointer field to store a block default route pointer and a routing field, wherein said routing field stores a route pointer or a next level pointer pointing to one of said plurality of routing table arrays in a next level; and

a route engine to select said block default route pointer or said route pointer as a return route pointer based on said destination address, wherein said return route pointer determines one of said plurality of output ports for routing said message, said route engine to access said plurality of routing table arrays in said plurality of levels.

2. The routing table circuit of claim 1 wherein said plurality of routing table arrays further include a tag field to designate said block default route pointer as said return route pointer.

3. The routing table circuit of claim 1 wherein said entries include a tag field.

4. The routing table circuit of claim 3 wherein said block default route pointer field includes said tag field.

5. The routing table circuit of claim 3 wherein said tag field indicates whether said routing field has said route pointer.

6. The routing table circuit of claim 3 wherein the tag field designates whether said routing field has said next level pointer.

7. The routing table circuit of claim 1 wherein at least one of said plurality of routing table arrays is associated with a table block default entry field that specifies a table block default route pointer for a subset of entries in said at least one of said plurality of routing table arrays, wherein said route engine selects said table block default route pointer as said return route pointer when a particular entry in said at least one of said plurality of routing table arrays has no particular block default route pointer or said routing field of said particular entry has no pointer.

8. The routing table circuit of claim 1 wherein at least one of said plurality of routing table arrays is associated with a table block default entry field that specifies a table block default route pointer for all entries in said at least one of said plurality of routing table arrays, wherein said route engine selects said table block default route pointer as said return route pointer when a particular entry in said at least one of said plurality of routing table arrays has no particular block default route pointer or said routing field of said particular entry has no pointer.

9. The routing table circuit of claim 1 further comprising a table default entry register to store a table block default route pointer that specifies block default route pointers for a subset of entries in an associated routing table array, wherein at least one of said plurality of routing table arrays are associated with said table block default entry register, wherein said route engine selects said table block default route pointer as said return route pointer when a particular entry in said associated routing table array has no particular block default route pointer or said routing field of said particular entry has no pointer.

10. The routing table circuit of claim 1 wherein a routing field of at least one element of said plurality of routing table arrays is populated with a pointer from the group consisting of (A) said route pointer, (B) said next level pointer, and (C) a table default route pointer.

11. The routing table circuit of claim 1 wherein a subset of said one or more routing table memories is associated with a linked list of overlapping routes, said linked list comprising a plurality of list entries including a first list entry, wherein said first list entry includes a longest route.

12. The routing table circuit of claim 11 wherein said list entries include a prefix and a prefix length, and sorted in a descending order of said prefix length so that said first list entry includes said longest prefix.

13. The routing table circuit of claim 1 further comprising:

a route entry table that associates said return route pointer with a next hop identifier to select one of said plurality of output ports for outputting said message.

14. The routing table circuit of claim 1 wherein

said block default route pointer of a particular entry associated with said destination address is designated as said return route pointer when said route pointer associated with said particular entry is NULL,

said route pointer of said routing field is designated as said return route pointer when said route pointer is not NULL, and

said next level pointer is used to access one of said plurality of routing table arrays in said next level.

15. A routing table circuit for a router having an input port for receiving a message having a destination address, said router having a plurality of output ports for transmitting said message, said routing table circuit comprising:

one or more routing table memories to store a plurality of routing table arrays to provide a return route pointer based on plurality of said destination address, said plurality of routing table arrays being arranged hierarchically in a plurality of levels, wherein each of said plurality of routing table arrays is associated with a predetermined subset of bits of the destination address, and have a plurality of elements, said plurality of elements including a block default route pointer field to store a block default route pointer and a route pointer field to store a longest-matching route pointer and a next-table pointer field to store a next level pointer to one of said plurality of routing table arrays in a next level; and

a route engine to select said block default route pointer or said longest-matching route pointer as a return route pointer based on said destination address, wherein said return route pointer is used to determine one of said plurality of output ports for routing said message, said route engine to access one of said plurality of routing table arrays in said next level.

16. The routing table circuit of claim 15 wherein said route engine applies said next level route pointer in combination with a subset of said destination address to access a next element in one of said plurality of routing table arrays in said next level to return said block default route pointer or said longest-matching route pointer of said next element as said return route pointer.

17. The routing table circuit of claim 15 wherein said block default pointer of a particular element is equal to NULL when said particular element has no block default route pointer, and said longest-matching route pointer of said particular element is equal to NULL when said particular element has no longest matching route.

18. A router comprising:

a plurality of input ports that receive a message having a destination address;

a plurality of output ports that output said message based on a return route pointer;

a routing table circuit to receive said message having said destination address, including;

one or more routing table memories to store a plurality of routing table arrays, wherein said plurality of routing table arrays are arranged hierarchically in a plurality of levels, wherein each of said plurality of routing table arrays is associated with a predetermined subset of prefixes of said destination address, and have entries, said entries including a block default route pointer field to store a block default route pointer and a routing field to store a route pointer or a next level pointer to one of said plurality of routing table arrays in a next level; and

a route engine to select said block default route pointer or said route pointer as said return route pointer based on said destination address, wherein said return route pointer determines one of said plurality of output ports for routing said message, said route engine to access said plurality of routing table arrays in said plurality of levels.

19. The router of claim 18 further comprising:

a route entry table that maps the selected output pointer to a next hop identifier for selecting one of the plurality of output ports for outputting the message.

20. A method of determining an output port for a message having a destination address for a router having a plurality of routing table arrays arranged hierarchically including at least a first level routing table array and a second level routing table array, said plurality of routing table arrays having elements, said method comprising:

receiving said message;

determining a first index into said first level routing table array based on at least a first subset of said destination address;

accessing said first level routing table array based on said first index, said first level routing table array having a first plurality of elements, where said first plurality of elements include a first block default route pointer field to store a first block default route pointer and a first routing field to store a first route pointer or a first next level pointer, said first level routing table comprises a first tag field, said first tag field to indicate whether to select said first block default route pointer or said first route pointer as a return route pointer, said first tag field to indicate whether said first routing field contains said first next level pointer;

selecting said block default route pointer as said return route pointer based on said first tag field;

selecting said first route pointer based on said first tag field;

determining a second index into said second level routing table array based on said first tag field and at least a second subset of said destination address;

accessing said second level routing table array based on said second index, said second level routing table array having a second plurality of elements including a second block default route pointer field to store a second block default route pointer and a second routing field to store a second route pointer and a second next level pointer, said second level routing table array further including a second tag field to indicate whether to select said second block default route pointer or said second route pointer as said return route pointer, said second tag field to indicate whether said second routing field contains said second next level pointer;

selecting said second block default route pointer from said second level routing table array as said return route pointer based on said second tag field; and

selecting said second route pointer of said second level routing table array based on said second tag field.

21. The method of claim 20 wherein said second level routing table array is associated with a table default route field to store a table default route pointer, said method further comprising:

selecting said table default route pointer when a particular element associated with said destination address has no second block default route pointer and said second routing field contains no pointer.

22. A method of adding a route to a routing table, comprising:

receive a new route pointer associated with a new route destination address including a new route prefix and a new route prefix length;

allocate a first level routing table, and allocate a second level routing table when the new route prefix length exceeds a first predetermined threshold, the first predetermined threshold specifying a number of bits of the destination address associated with the first level routing table, the first and second level routing tables having elements, the elements including a block default route field to store a block default route, if any, and also having a routing pointer field to store a routing pointer selected from the group consisting of (A) a route pointer and (B) a next level pointer;

determine a first particular element of the first level routing table associated with the new route destination address;

store a particular next level pointer in the routing pointer field of the particular element;

determine a second particular element of the second level routing table associated with the new route destination address;

store the new route pointer in the routing field of the second particular element; and

update the block default routes for a subsequent subset of elements of the second routing table based on the new route prefix length.

23. The method of claim 22 further comprising:

identify among said subsequent subset of elements of the second routing table a second particular element having a routing field that has a route pointer having a prefix length greater than the new route prefix length;

obtaining a number of elements covered by said second particular element; and

skipping memory access to said number of elements.

24. The method of claim 22 further comprising:

receive a delete-route pointer associated with a delete-route destination address including a delete-route prefix and a delete-route prefix length;

determine a third particular element in a lowest level table of the hierarchy that stores the delete-route pointer as the route pointer to provide a start element;

identify a block default route, if any, of the start element;

determine a fourth particular element in the lowest level table of the hierarchy that stores the delete-route pointer as the block default route pointer as an end element;

for a next element after the start element to the end element;

when the block default route for said next element equals the delete-route pointer, set the block default route of said next element equal to said block default route of said start element.

25. The method of claim 24 further comprising:

determining when said next element has a routing field that has a route pointer having a prefix length greater than the delete-route prefix length;

obtaining a number of elements covered by said next element; and

skipping memory access to said number of elements.

26. A method of moving entries in a routing table, comprising:

receive a first new route pointer associated with a first new route destination address including a first new route prefix and a first new route prefix length;

allocate a first level routing table, the first new route prefix length being less than a first predetermined threshold, the first predetermined threshold specifying a number of bits of the destination address associated with the first level routing table, the first routing table having first table elements, the first table elements including a block default route field to store a block default route, if any, and also having a routing pointer field to store a routing pointer selected from the group consisting of (A) a route pointer and (B) a next level pointer;

determine a first particular element of the first level routing table associated with the first new route destination address;

store the first new route pointer in a routing field of the first particular element;

update block default routes for a subsequent subset of elements of the first routing table with the first new route pointer based on the first new route prefix length;

receive a second new route pointer associated with a second new route destination address including a portion of the first new route prefix and a second new route prefix length being longer than the first new route prefix length, wherein the second new route prefix length is greater than the first predetermined threshold;

allocate a second level routing table, the second level routing table having second table elements, the second table elements including a block default route field to store a block default route, if any, and also having a routing pointer field to store a routing pointer selected from the group consisting of (A) a route pointer and (B) a next level pointer;

store a next table pointer in the routing field of the first particular element;

determine a second particular element of the second level routing table associated with the second new route destination address;

store the second new route pointer in a routing field of the second particular element;

store the first new route pointer in a routing field of elements of the second level routing table that precede the second particular element;

store the first new route pointer in a default block route field for a second through last element of the second level routing table; and

update block default routes for a subsequent subset of elements of the second level routing table with the second new route pointer based on the second new route prefix length.