Filter based longest prefix match algorithm

Details Filter based longest prefix match algorithm Filter based longest prefix match algorithm

2004-02-09

2008-10-07

Pham, Chi H. (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320, C707S793000

Reexamination Certificate

active

07433355

ABSTRACT:
Methods directed to longest prefix matching and systems directed to IP address lookups are presented. The methods and systems relate in particular to IPv6 and comprise finding the longest prefix match (LPM) for an IP address. The method of the invention results in the use of filters to perform LPM. In embodiments of the invention, partial address filtering is used to further reduce filtering requirements. Reducing the number of filtering operations has the advantage of making the LPM algorithm faster and less costly to implement than prior art approaches. Also described is an “ideal offset filter” that extracts a fixed sized sliding window of bits from the IP address being processed.

REFERENCES:
patent: 6018524 (2000-01-01), Turner
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6490592 (2002-12-01), St. Denis et al.
patent: 6499081 (2002-12-01), Nataraj et al.
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6570866 (2003-05-01), Murase et al.
patent: 6839703 (2005-01-01), Jinzaki
patent: 6947931 (2005-09-01), Bass et al.
patent: 7031320 (2006-04-01), Choe
patent: 7120630 (2006-10-01), Bass et al.
patent: 7219184 (2007-05-01), Stojancic
patent: 2004/0085953 (2004-05-01), Davis
patent: 2005/0086520 (2005-04-01), Dharmapurikar et al.
patent: 2005/0144553 (2005-06-01), Bass et al.
patent: 1156432 (2001-11-01), None
Gupta, et al., Algotrithms for Packet Classification, Stanford University, 2001.
Dharmapurikar, Sarang, et al., Longest Prefix Matching Using Bloom Filters, Washington University in St. Louis, St. Louis, MO, 2003.

Affiliated with

Also associated with

Rating

Filter based longest prefix match algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Filter based longest prefix match algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Filter based longest prefix match algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4016716