Network routing table

• US 6,665,297 B1
• Filed: 12/09/1999
• Issued: 12/16/2003
• Est. Priority Date: 12/09/1999
• Status: Expired due to Term

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Mayan Networks Corporation (Vital Network Services /Koehler/)
• Inventors: Ziemba, G. Paul, Talajia, Jayant K., Hariguchi, Yoichi
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): SHAH, CHIRAG G
• Application Number:
  US09/458,535
• Time in Patent Office: 1,468 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/395.32, 370/395.71, 370/395.72, 370/395.7, 370/395.31
• US Class Current: 370/392
• 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
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane

Abstract

A deterministic routing table includes a set of hash circuits and a CAM. The routing table searches for the longest matching destination address stored in any of the hash circuits and the CAM, if any, and outputs an output pointer associated with that destination address within a fixed predetermined time.

Claims

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

a content addressable memory (CAM) storing a plurality of data pairs, each data pair including an address value and a prefix length, the CAM outputting an output pointer associated with the address value when a portion of the message destination address matches a corresponding portion of the address value specified by the prefix length stored in the data pairs;

a plurality of hash circuits, connected in parallel with the CAM, each hash circuit being connected in parallel with other hash circuits, each hash circuit hashing a portion of the message destination address to provide a hashed-message-destination address, each hash circuit having a hash bucket storing output pointers at associated hash bucket addresses in the hash bucket, each hash circuit outputting the stored output pointer, if any, associated with the hashed-message-destination address; and

a selection circuit, connected in series with the CAM and the plurality of hash circuits, that selects one of the output pointers output by the plurality of hash circuits and the CAM to provide a selected output pointer;

wherein the CAM and the plurality of hash circuits are configured to all perform address lookup operations simultaneously, and wherein each hash circuit of the plurality of hash circuits has associated therewith a distinct respective prefix length, and is configured to perform an address lookup on a message destination address prefix having a length equal to said distinct respective prefix length.

2. The routing table circuit of claim 1 wherein each of the hash circuits is further configured to store at most one output pointer at each distinct hash bucket address in the hash bucket.

3. The routing table circuit of claim 1 wherein the data pairs are stored in sorted order in the CAM based on the prefix length.

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

one or more look-up tables, connected in parallel with the plurality of hash circuits, each look-up table being associated with a distinct prefix length, each look-up table providing an output pointer in response to the portion of the message destination address associated with the distinct prefix length,

wherein the selection circuit is connected in series with the one or more look-up tables, and selects one of the output pointers output by the plurality of hash circuits, the CAM and the one or more look-up tables.

5. The routing table circuit of claim 1 wherein the output pointer from the CAM is associated with a storage location of the destination address in the CAM.

6. The routing table circuit of claim 1 wherein the output pointer from the CAM is associated with a storage location having a longest matching prefix length.

7. The routing table circuit of claim 1 wherein the CAM stores an output pointer associated with each destination address.

8. The routing table circuit of claim 1 wherein the hash bucket stores a predefined null output pointer for hash bucket addresses for which there is no associated output pointer.

9. The routing table circuit of claim 1 wherein the CAM outputs a prefix length associated with the output pointer, each hash circuit is also associated with a prefix length, and the selection circuit selects the output pointer associated with the largest prefix length.

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

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

11. The routing table circuit of claim 1 wherein each hash circuit includes:

a mask circuit, each mask circuit masking a unique number of bits of the destination address to provide a masked address; and

a hash generator that generates the hashed-message-destination address based on the masked address.

15. The routing table circuit of claim 1 wherein the selection circuit includes:

a priority encoder that selects one of the output pointers from the plurality of hash circuits based on the prefix length associated with the hash circuits as a selected hash output pointer; and

a multiplexor that selects the output pointer from the CAM or the selected hash output pointer as the selected output pointer.

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

a content addressable memory (CAM) storing a plurality of data pairs, each data pair including an address value and a prefix length, the CAM outputting an output pointer associated with the address value when a portion of the message destination address matches a corresponding portion of the address value specified by the prefix length stored in the data pairs;

a plurality of hash circuits, connected in parallel with the CAM, each hash circuit being connected in parallel with other hash circuits, each hash circuit hashing a portion of the message destination address to provide a hashed-message-destination address, each hash circuit having a hash bucket storing output pointers at associated hash bucket addresses in the hash bucket, each hash circuit outputting the stored output pointer, if any, associated with the hashed-message-destination address; and

a selection circuit, connected in series with the CAM and the plurality of hash circuits, that selects one of the output pointers output by the plurality of hash circuits and the CAM to provide a selected output pointer;

wherein each hash circuit includes;

a mask circuit, each mask circuit masking a unique number of bits of the destination address to provide a masked address; and

a hash generator that generates the hashed-message-destination address based on the masked address; and

wherein the mask circuit and hash generator form a first pipeline stage, the hash bucket circuit forms a second pipeline stage and the selection circuit forms a third pipeline stage.

13. The routing table circuit of claim 12 wherein each pipeline stage is associated with a clock cycle, and the selected output pointer is output in a predetermined number of clock cycles.

14. The routing table circuit of claim 13 wherein the predetermined number of clock cycles is equal to three.

16. A router comprising:

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

a plurality of output ports that output the message in accordance with an output pointer;

a content addressable memory (CAM) storing a plurality of data pairs, each data pair including an address value and a prefix length, the CAM outputting an output pointer associated with the address value when the message destination address matches the address value specified by the prefix length stored in the data pairs;

a plurality of hash circuits, connected in parallel with the CAM, each hash circuit being connected in parallel with other hash circuits, each hash circuit hashing a portion of the message destination address to provide a hashed-message-destination address, each hash circuit having a hash bucket storing output pointers at associated hash bucket addresses in the hash bucket, each hash circuit outputting the stored output pointer, if any, associated with the hashed-message-destination address; and

a selection circuit, connected in series with the CAM and the plurality of hash circuits, that selects one of the output pointers output by the plurality of hash circuits and the CAM to provide a selected output pointer;

wherein the CAM and the plurality of hash circuits are configured to perform address lookup operations simultaneously, and wherein each hash circuit of the plurality of hash circuits has associated therewith a distinct respective prefix length, and is configured to perform an address lookup on a message destination address prefix having a length equal to said distinct respective prefix length.

17. The router of claim 16 wherein each of the hash circuits is further configured to store at most one output pointer at each distinct hash bucket address in the hash bucket.

18. The router of claim 16 wherein the CAM outputs a prefix length associated with the output pointer, each hash circuit is also associated with a prefix length, and the selection circuit selects the output pointer associated with the largest prefix length.

19. The router of claim 16 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. The router of claim 16 wherein each hash circuit includes:

a mask circuit, each mask circuit masking a unique number of bits of the destination address to provide a masked address; and

a hash generator that outputs a hash address based on the masked address, wherein the hash address is applied as the hash bucket address.

24. The router of claim 16 wherein the selection circuit includes:

a priority encoder that selects one of the output pointers from the plurality of hash circuits based on the prefix length associated with each hash circuit as a selected hash output pointer; and

a multiplexor that selects the output pointer from the CAM or the selected hash output pointer as the selected output pointer.

21. A router comprising:

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

a plurality of output ports that output the message in accordance with an output pointer;

a content addressable memory (CAM) storing a plurality of data pairs, each data pair including an address value and a prefix length, the CAM outputting an output pointer associated with the address value when the message destination address matches the address value specified by the prefix length stored in the data pairs;

a plurality of hash circuits, connected in parallel with the CAM, each hash circuit being connected in parallel with other hash circuits, each hash circuit hashing a portion of the message destination address to provide a hashed-message-destination address, each hash circuit having a hash bucket storing output pointers at associated hash bucket addresses in the hash bucket, each hash circuit outputting the stored output pointer, if any, associated with the hashed-message-destination address; and

a selection circuit, connected in series with the CAM and the plurality of hash circuits, that selects one of the output pointers output by the plurality of hash circuits and the CAM to provide a selected output pointer;

wherein each hash circuit includes;

a mask circuit, each mask circuit masking a unique number of bits of the destination address to provide a masked address; and

hash generator that outputs a hash address based on the masked address, wherein the hash address is applied as the hash bucket address; and

wherein the mask circuit and hash generator form a first pipeline stage, the hash bucket circuit forms a second pipeline stage and the selection circuit forms a third pipeline stage.

22. The router of claim 21 wherein each pipeline stage is associated with a clock cycle, and the selected output pointer is output in a predetermined number of clock cycles.

23. The router of claim 22 wherein the predetermined number of clock cycles is equal to three.

25. A method of determining an output port for a datagram use in a router, comprising:

receiving a datagram having a datagram destination address;

storing, in a content addressable memory (CAM), a plurality of data pairs, each data pair including an address value and a prefix length;

storing output pointers at associated hash bucket addresses in a hash bucket;

storing a predefined null port pointer for hash bucket addresses in the hash bucket for which there is no associated port pointer;

hashing a portion of the message destination address to provide a hashed-message-destination address;

outputting from the hash bucket, the stored output pointer, if any, associated with the hashed-message-destination address;

outputting from the CAM, the output pointer associated with the address value in one of the stored data pairs when the message destination address matches at least a portion of the address value based on the associated prefix length; and

selecting one of the output pointers output by the plurality of hash circuits and the CAM;

wherein said step of hashing is performed in a first pipeline clock cycle, said step of outputting from the hash bucket is performed in a second pipeline clock cycle, said step of outputting from the CAM is performed in the first and the second pipeline clock cycles, and said step of selecting is performed in a third pipeline clock cycle.

26. A method of routing a message having a message destination address, comprising:

performing a lookup operation in a content addressable memory (CAM) storing a plurality of data pairs, each data pair including an address value and a prefix length, the CAM outputting an output pointer associated with the address value when a portion of the message destination address matches a corresponding portion of the address value specified by the prefix length stored in the data pairs;

performing simultaneous address lookup operations in a plurality of hash circuits, including, in each hash circuit, hashing a portion of the message destination address to provide a hashed-message-destination address, and outputting a stored output pointer, if any, associated with the hashed-message-destination address; and

selecting one of the output pointers output by the plurality of hash circuits and the CAM to provide a selected output pointer.

27. The method of claim 26, wherein each hash circuit of the plurality of hash circuits has associated therewith a distinct respective prefix length, and is configured to perform an address lookup on a message destination address prefix having a length equal to said distinct respective prefix length.