Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
2000-12-22
2004-05-25
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S005000, C711S173000, C711S216000
Reexamination Certificate
active
06742105
ABSTRACT:
BACKGROUND INFORMATION
1. Field of the Invention
The present invention relates generally to the field of computing systems, and more particularly to range matching of addresses.
2. Description of Related Art
Networking companies are scrambling in a race to design and develop high performance network processing products for the terabit router market while reducing the cost to implement 10 giga-bits per second/OC192 and above optical carrier network interfaces. Terabit routers demand a higher throughput of data packets for examining an incoming packet, retrieves a next hop location, and transfers the packet to destination. To produce a faster response time in matching an incoming address, a technique called range matching has been used. For background information on range matching, the reader is referred to multirange and multidimensional range matching algorithm as presented in: “HighSpeed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching”, Lakshman & Stiliadis, Bell Labs, 1998.
Accordingly, it is desirable to have a method and system for fast matching of an incoming address with addresses in a memory.
SUMMARY OF THE INVENTION
The invention provides a range matching circuit that determines if a field value is within the specified range of values, described as a top end boundary (“top edge”) and a bottom end boundary (“bottom edge”). This analysis is done by partitioning the incoming address into fields. In one embodiment, a 16-bit incoming address is divided into quarterly fields, or four segments of 4-bit addresses, for comparison with four 4-bit segments of the 16-bit top edge and the four 4-bit segments of the 16-bit bottom edge. Each 4-bit segment can be analyzed independently in parallel in which a combined result is generated at the output.
REFERENCES:
patent: RE31318 (1983-07-01), Kaufman et al.
patent: 5303359 (1994-04-01), Suzuki
patent: 5418956 (1995-05-01), Willman
patent: 5564030 (1996-10-01), Whitted et al.
patent: 5577219 (1996-11-01), Timko et al.
patent: 5659699 (1997-08-01), Breternitz, Jr.
patent: 5809562 (1998-09-01), Gaskins et al.
patent: 5850632 (1998-12-01), Robertson
patent: 6092151 (2000-07-01), Park
patent: 6260101 (2001-07-01), Hansen et al.
patent: 6260121 (2001-07-01), Jeddeloh
patent: 6272612 (2001-08-01), Bordaz et al.
patent: 6275894 (2001-08-01), Kuo et al.
patent: 6470414 (2002-10-01), Kuo et al.
patent: 6510507 (2003-01-01), Matt et al.
Fernandez & Associates LLP
Peugh Brian R.
Silicon Access Networks
Sparks Donald
LandOfFree
Method and system for range matching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for range matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for range matching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3224798