Yoichi Hariguchi

6665297, Dec 16, 2003

Dec 9, 1999

09/458535

Yoichi Hariguchi - Menlo Park CA
Jayant K. Talajia - San Jose CA
G. Paul Ziemba - Redwood City CA

Mayan Networks Corporation - Sunnyvale CA

H04L 1228

370392, 37039532

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.

6717946, Apr 6, 2004

Oct 31, 2002

10/284759

Yoichi Hariguchi - Menlo Park CA
Rina Panigrahy - Sunnyvale CA
Samar Sharma - Sunnyvale CA
Ashwath Nagaraj - Los Altos CA

Cisco Technology Inc. - San Jose CA

H04L 1228

370392, 370389

Methods and apparatus are disclosed for maintaining one or more ranges and identifying whether a value matches one of the ranges and optionally which range is matched. One implementation includes a range programming engine for generating one or more mapped subtrie values identifying each range, each of the mapped subtrie values identifying a different subset of the range. An associative memory stores the mapped subtrie ranges. A mapping engine receives a particular value and generates a lookup word including a mapped representation of the particular value. The associative memory performs a lookup operation to identify whether or not the particular value is within one of the ranges. In this manner, only a small number of associative memory entries are required to identify whether a mapped particular value falls within the range. The particular range matched can be identified such as by a read operation in an adjunct memory based on the address of the matching entry.

6956858, Oct 18, 2005

Jun 29, 2001

09/895972

Yoichi Hariguchi - Menlo Park CA, US
Thomas A. Herbert - San Jose CA, US
Ryan T. Herbst - Redwood City CA, US

Mayan Networks Corporation - San Jose CA

H04L012/28
H04L012/56

37039531, 379272, 379273, 379274, 379275, 379276, 379277, 709238, 709239, 709240, 709241, 709242, 709243, 709244, 711221

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.

63078554, Oct 23, 2001

Jul 7, 2000

9/611881

Yoichi Hariguchi - Menlo Park CA

H04L 1228

370392

A routing table comprises routing table entries [230], a word line driver [92], prioritizer [100], and memory [106]. Each routing table entry [230] comprises content addressable memory (CAM) cells [220] and an entry masking circuit. The routing table looks up in parallel an entry matching an input network address, and outputs the search result in deterministic time. Only the bits specified by the masking circuit in each entry are compared when searching. If multiple entries match the input, the prioritizer [100] uses mask information from the masking circuits of the matching entries to select the best entry, e. g. the entry having the most matching bits.

61816981, Jan 30, 2001

Jul 9, 1997

8/890350

Yoichi Hariguchi - Palo Alto CA

H04L 1228

370392

A routing table comprises routing table entries [230], a word line driver [92], prioritizer [100], and memory [106]. Each routing table entry [230] comprises content addressable memory (CAM) cells [220] and an entry masking circuit. The routing table looks up in parallel an entry matching an input network address, and outputs the search result in deterministic time. Only the bits specified by the masking circuit in each entry are compared when searching. If multiple entries match the input, the prioritizer [100] uses mask information from the masking circuits of the matching entries to select the best entry, e. g. the entry having the most matching bits.