Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2011-08-02
2011-08-02
Sheikh, Ayaz R (Department: 2476)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395320
Reexamination Certificate
active
07990973
ABSTRACT:
In one embodiment, IP lookup into a routing table having prefixes of different prefix lengths is performed by hashing a candidate prefix value to generate a plurality of hash values, where m seed hash values are generated by applying m seed hash functions and one or more additional hash values are generated by combining two or more of the seed hash values in different ways, e.g., using a bit-wise XOR function. The hash values are used to perform membership probes into a Bloom filter programmed with the prefixes corresponding to all of the different prefix lengths in the routing table without having to expand any of the prefixes programmed into the Bloom filter.
REFERENCES:
patent: 6473424 (2002-10-01), DeJager et al.
patent: 7126948 (2006-10-01), Gooch et al.
patent: 7289979 (2007-10-01), Wilson
patent: 7444515 (2008-10-01), Dharmapurikar et al.
patent: 7636703 (2009-12-01), Taylor
patent: 7839891 (2010-11-01), Allan
patent: 7865608 (2011-01-01), Schuba et al.
patent: 2003/0026268 (2003-02-01), Navas
patent: 2003/0169745 (2003-09-01), Gooch
patent: 2003/0174710 (2003-09-01), Gooch
patent: 2005/0086520 (2005-04-01), Dharmapurikar et al.
patent: 2005/0174272 (2005-08-01), Cadambi et al.
patent: 2005/0175010 (2005-08-01), Wilson et al.
patent: 2005/0195832 (2005-09-01), Dharmapurikar et al.
patent: 2005/0223102 (2005-10-01), Zhang et al.
patent: 2005/0249214 (2005-11-01), Peng
patent: 2006/0184690 (2006-08-01), Milliken
patent: 2006/0198379 (2006-09-01), Cadambi et al.
patent: 2007/0115986 (2007-05-01), Shankara
patent: 2007/0136331 (2007-06-01), Hasan et al.
patent: 2007/0248084 (2007-10-01), Whitehead
patent: 2007/0294506 (2007-12-01), Ross
patent: 2008/0111718 (2008-05-01), Lin et al.
patent: 2009/0030895 (2009-01-01), Eswaran et al.
patent: 2009/0046581 (2009-02-01), Eswaran et al.
patent: 2010/0023727 (2010-01-01), Lim
patent: 2010/0098081 (2010-04-01), Dharmapurikar et al.
patent: 2010/0284405 (2010-11-01), Lim
Haoyu Song; Fang Hao; Kodialam, M.; Lakshman, T.V.; “IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards,” Apr. 19-25, 2009, INFOCOM 2009, IEEE , pp. 2518-2526.
B. Bloom, “Space/Time Trade-offs in Hash Coding With Allowable Errors,” Communications of the ACM, vol. 13, No. 7, Jul. 1970, pp. 422-426.
H. Song, S. Dharmapurikar, J. S. Turner, and J. W. Lockwood, “Fast Hash Table Lookup using Extended Bloom Filter: An Aid to Network Processing,” ACM SIGCOMM, 2005, 12 pages.
S. Kumar, J. Turner, and P. Crowley, “Peacock Hashing: Deterministic and Updatable Hashing for High Performance Networking,” IEEE INFOCOM, Jan. 2008, pp. 556-564.
A. Broder and M. Mitzenmacher, “Using Multiple Hash Functions to Improve IP Lookups,” IEEE INFOCOM, 2001, pp. 1-11.
M. Ramakrishna, E. Fu, and E. Bahcekapili, “A Performance Study of Hashing Functions for Hardware Applications,” Proc. 6thInt'l. Conf. Computing and Information, 1994, pp. 1621-1636.
“Longest Prefix Matching Using Bloom Filters,” by Sarang Dharmapurikar et al., SIGCOMM'03, Aug. 25-29, 2003, 12 pages.
Hao Fang
Kodialam Muralidharan S.
Song Haoyu
Alcatel-Lucent USA Inc.
Mendelsohn, Drucker & Associates P.C.
Sheikh Ayaz R
Weidner Timothy J
LandOfFree
Hash functions for applications such as network address lookup does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hash functions for applications such as network address lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash functions for applications such as network address lookup will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2726317