Patent ID: 6665297
Filing Date: 2003-12-16
Classification: H04L

Abstract:
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.