Longest best match search

Details Longest best match search Longest best match search

2005-04-05

2005-04-05

Mizrahi, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06877005

ABSTRACT:
A method and apparatus for efficiently performing a longest match search are provided. According to one aspect of the present invention, an entry in a forwarding database, a routing table, or the like is located using an improved longest match search. A mask is applied to an address, such as a destination Internet Protocol (IP) address, to determine a masked address that is to be used for purposes of locating a matching entry in the forwarding database. The forwarding database is searched for an entry that matches the masked address. Subsequent masks are produced by performing an address-sensitive decimation of the former mask. For example, the former mask may be shortened based upon the location of the least significant bit containing a one in the masked address. According to another aspect of the present invention, data forwarding employs the improved longest match search. Data is received at a port. An address is extracted from the data. A forwarding database is searched for a longest match for the address by comparing a portion of the address indicated by a mask to entries in the forwarding database and using progressively shorter masks, determined based upon the masked address, for each subsequent search until a matching entry is located. If a matching entry is found, the data is forwarded to a destination associated with the matching entry.

REFERENCES:
patent: 5420862 (1995-05-01), Perlman
patent: 5446881 (1995-08-01), Mammel, Jr.
patent: 5555405 (1996-09-01), Griesmer et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5794244 (1998-08-01), Brosch et al.
patent: 5835720 (1998-11-01), Nelson et al.
patent: 5841683 (1998-11-01), Bechade et al.
patent: 5920699 (1999-07-01), Bare
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6697756 (2004-02-01), Wettstein et al.
patent: 620994 (1992-02-01), None
Y. Rekhter, et al., “Cisco Systems Tag Switching Architecture Overview”, RFC2105, Feb. 1997, pp. 1-12.
V. Srinivasan, et al., “Faster IP Lookups Using Controlled Prefix Expansion”, Proceeding of ACM Sigmetrics, Sep. 1998, pp. 1-10.
M. Waldvogel, et al., “Scalable High Speed IP Routing Lookups”, Computer Communications Review, ACM Sigcomm, vol. 27, No. 4, Oct. 1997, pp. 25-36.
M. Degermark, et al., “Small Forwarding Tables for Fast Routing Lookups”, Computer Communication Review, ACM Sigcomm, vol. 27, No. 4, Oct. 1997, pp.
W. Doeringer, et al., “Routing On Longest-Matching Prefixes”, IEEE/ACM Transactions on Networking, vol. 4, No. 1, Feb. 1996, pp. 86-97.
P. Gupta, et al., “Routing lookups In Hardware At Memory Access Speeds”, submitted to IEEE Infocom '98, pp. 1240-1247.
A.J. Mcauley, et al., “Fast Routing Table Lookup Using CAMs”, IEEE Infocom vol. 3, 1993, pp. 1382-1391.
P. Newman, et al., “Flow Labelled IP: A Connectionless Approach to ATM”, IEEE Infocom vol. 3, 1996, pp. 1251-1260.
C. Partridge, et al., “Big Fast Routers: Multi-Megapacket Forwarding Engines Fro Internet II”, Networld/Interop '97, 17 pages.

Affiliated with

Also associated with

Rating

Longest best match search does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Longest best match search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest best match search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3379928