Network routing table
AssigneeMayan Networks Corporation
InventorsYoichi Hariguchi, Jayant K. Talajia, G. Paul Ziemba
Life of this patent
Estimating the term…
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.
Claims27
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.