Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2005-02-09
2009-10-13
Kumar, Pankaj (Department: 2419)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395320, C707S793000, C709S245000
Reexamination Certificate
active
07602785
ABSTRACT:
The present invention relates to a method and system of performing parallel membership queries to Bloom filters for Longest Prefix Matching, where address prefix memberships are determined in sets of prefixes sorted by prefix length. Hash tables corresponding to each prefix length are probed from the longest to the shortest match in the vector, terminating when a match is found or all of the lengths are searched. The performance, as determined by the number of dependent memory accesses per lookup, is held constant for longer address lengths or additional unique address prefix lengths in the forwarding table given that memory resources scale linearly with the number of prefixes in the forwarding table. For less than 2 Mb of embedded RAM and a commodity SRAM, the present technique achieves average performance of one hash probe per lookup and a worst case of two hash probes and one array access per lookup.
REFERENCES:
patent: 3601808 (1971-08-01), Vlack
patent: 3611314 (1971-10-01), Pritchard, Jr. et al.
patent: 3729712 (1973-04-01), Glassman
patent: 3824375 (1974-07-01), Gross et al.
patent: 3848235 (1974-11-01), Lewis et al.
patent: 3906455 (1975-09-01), Houston et al.
patent: 4081607 (1978-03-01), Vitols
patent: 4298898 (1981-11-01), Cardot
patent: 4314356 (1982-02-01), Scarbrough
patent: 4385393 (1983-05-01), Chaure et al.
patent: 4464718 (1984-08-01), Dixon et al.
patent: 4550436 (1985-10-01), Freeman et al.
patent: 4823306 (1989-04-01), Barbic et al.
patent: 4941178 (1990-07-01), Chuang
patent: 5023910 (1991-06-01), Thomson
patent: 5050075 (1991-09-01), Herman et al.
patent: 5077665 (1991-12-01), Silverman et al.
patent: 5101424 (1992-03-01), Clayton et al.
patent: 5126936 (1992-06-01), Champion et al.
patent: 5140692 (1992-08-01), Morita
patent: 5163131 (1992-11-01), Row et al.
patent: 5179626 (1993-01-01), Thomson
patent: 5226165 (1993-07-01), Martin
patent: 5243655 (1993-09-01), Wang
patent: 5249292 (1993-09-01), Chiappa
patent: 5255136 (1993-10-01), Machado et al.
patent: 5265065 (1993-11-01), Turtle
patent: 5270922 (1993-12-01), Higgins
patent: 5274679 (1993-12-01), Abe et al.
patent: 5319776 (1994-06-01), Hile et al.
patent: 5327521 (1994-07-01), Savic et al.
patent: 5339411 (1994-08-01), Haton, Jr. et al.
patent: 5347634 (1994-09-01), Herrell et al.
patent: 5371794 (1994-12-01), Diffie et al.
patent: 5388259 (1995-02-01), Fleischman et al.
patent: 5396253 (1995-03-01), Chia
patent: 5418951 (1995-05-01), Damashek
patent: 5421028 (1995-05-01), Swanson
patent: 5432822 (1995-07-01), Kaewell, Jr.
patent: 5440723 (1995-08-01), Arnold et al.
patent: 5461712 (1995-10-01), Chelstowski et al.
patent: 5465353 (1995-11-01), Hull et al.
patent: 5481735 (1996-01-01), Mortensen et al.
patent: 5487151 (1996-01-01), Kikuchi et al.
patent: 5488725 (1996-01-01), Turtle et al.
patent: 5497488 (1996-03-01), Akizawa et al.
patent: 5544352 (1996-08-01), Egger
patent: 5546578 (1996-08-01), Takada
patent: 5629980 (1997-05-01), Stefik et al.
patent: 5651125 (1997-07-01), Witt et al.
patent: 5701464 (1997-12-01), Aucsmith
patent: 5710757 (1998-01-01), May
patent: 5721898 (1998-02-01), Beardsley et al.
patent: 5740244 (1998-04-01), Indeck et al.
patent: 5740466 (1998-04-01), Geldman et al.
patent: 5761431 (1998-06-01), Gross et al.
patent: 5774835 (1998-06-01), Ozawa
patent: 5774839 (1998-06-01), Shlomot
patent: 5781772 (1998-07-01), Wilkinson, III
patent: 5781921 (1998-07-01), Nichols
patent: 5805832 (1998-09-01), Brown et al.
patent: 5813000 (1998-09-01), Furlani
patent: 5819273 (1998-10-01), Vora et al.
patent: 5819290 (1998-10-01), Fujita
patent: 5826075 (1998-10-01), Bealkowski et al.
patent: 5864738 (1999-01-01), Kessler et al.
patent: 5870730 (1999-02-01), Furya et al.
patent: 5884286 (1999-03-01), Daughtery, III
patent: 5913211 (1999-06-01), Nitta
patent: 5930753 (1999-07-01), Potamianos et al.
patent: 5943421 (1999-08-01), Grabon
patent: 5943429 (1999-08-01), Handal
patent: 5974414 (1999-10-01), Stanczak et al.
patent: 5978801 (1999-11-01), Yuasa
patent: 5987432 (1999-11-01), Zusman et al.
patent: 5991881 (1999-11-01), Conklin et al.
patent: 5995963 (1999-11-01), Nanba et al.
patent: 6023760 (2000-02-01), Karttunen
patent: 6028939 (2000-02-01), Yin
patent: 6044407 (2000-03-01), Jones et al.
patent: 6058391 (2000-05-01), Gardner
patent: 6061662 (2000-05-01), Makivic
patent: 6067569 (2000-05-01), Khaki et al.
patent: 6070172 (2000-05-01), Lowe
patent: 6073160 (2000-06-01), Grantham et al.
patent: 6105067 (2000-08-01), Batra
patent: 6108782 (2000-08-01), Fletcher et al.
patent: 6112181 (2000-08-01), Shear et al.
patent: 6115751 (2000-09-01), Tam et al.
patent: 6134551 (2000-10-01), Aucsmith
patent: 6138176 (2000-10-01), McDonald et al.
patent: RE36946 (2000-11-01), Diffie et al.
patent: 6147976 (2000-11-01), Shand et al.
patent: 6169969 (2001-01-01), Cohen
patent: 6173276 (2001-01-01), Kant et al.
patent: 6175874 (2001-01-01), Imai et al.
patent: 6205148 (2001-03-01), Takahashi et al.
patent: 6216173 (2001-04-01), Jones et al.
patent: 6219786 (2001-04-01), Cunningham et al.
patent: 6226676 (2001-05-01), Crump et al.
patent: 6233618 (2001-05-01), Shannon
patent: 6233684 (2001-05-01), Stefik et al.
patent: 6237028 (2001-05-01), Jackson
patent: 6259909 (2001-07-01), Ratayczak et al.
patent: 6263321 (2001-07-01), Daughtery
patent: 6279113 (2001-08-01), Vaidya
patent: 6317795 (2001-11-01), Malkin et al.
patent: 6336150 (2002-01-01), Ellis et al.
patent: 6343324 (2002-01-01), Hubis et al.
patent: 6363384 (2002-03-01), Cookmeyer, II et al.
patent: 6370645 (2002-04-01), Lee
patent: 6377942 (2002-04-01), Hinsley
patent: 6381242 (2002-04-01), Maher, III et al.
patent: 6389532 (2002-05-01), Gupta et al.
patent: 6397259 (2002-05-01), Lincke et al.
patent: 6397335 (2002-05-01), Franczek et al.
patent: 6412000 (2002-06-01), Riddle et al.
patent: 6418419 (2002-07-01), Nieboer et al.
patent: 6430272 (2002-08-01), Maruyama et al.
patent: 6456982 (2002-09-01), Pilipovic
patent: 6463474 (2002-10-01), Fuh et al.
patent: 6499107 (2002-12-01), Gleichauf et al.
patent: 6546375 (2003-04-01), Pang et al.
patent: 6564263 (2003-05-01), Bergman et al.
patent: 6578147 (2003-06-01), Shanklin et al.
patent: 6628652 (2003-09-01), Chrin et al.
patent: 6643717 (2003-11-01), Rustad et al.
patent: 6704816 (2004-03-01), Burke
patent: 6711558 (2004-03-01), Indeck et al.
patent: 6728929 (2004-04-01), Luong
patent: 6765918 (2004-07-01), Dixon et al.
patent: 6772136 (2004-08-01), Kant et al.
patent: 6772345 (2004-08-01), Shetty
patent: 6775290 (2004-08-01), Merchant et al.
patent: 6778968 (2004-08-01), Gulati
patent: 6785677 (2004-08-01), Fritchman
patent: 6804667 (2004-10-01), Martin
patent: 6807156 (2004-10-01), Veres et al.
patent: 6850906 (2005-02-01), Chadha et al.
patent: 6856981 (2005-02-01), Wyschogrod et al.
patent: 6870837 (2005-03-01), Ho et al.
patent: 6877044 (2005-04-01), Lo et al.
patent: 6886103 (2005-04-01), Brustoloni et al.
patent: 6901461 (2005-05-01), Bennett
patent: 6928549 (2005-08-01), Brock et al.
patent: 6931408 (2005-08-01), Adams et al.
patent: 6944168 (2005-09-01), Paatela et al.
patent: 7457834 (2005-11-01), Jung et al.
patent: 6978223 (2005-12-01), Milliken
patent: 6981054 (2005-12-01), Krishna
patent: 7019674 (2006-03-01), Cadambi et al.
patent: 7024384 (2006-04-01), Daughter, III
patent: 7046848 (2006-05-01), Olcott
patent: 7065475 (2006-06-01), Brundobler
patent: 7093023 (2006-08-01), Lockwood et al.
patent: 7099838 (2006-08-01), Gastineau et al.
patent: 7103569 (2006-09-01), Groveman et al.
patent: 7103799 (2006-09-01), Dixon
patent: 7117370 (2006-10-01), Khan et al.
patent: 7127510 (2006-10-01), Yoda et al.
patent: 7139743 (2006-11-01), Indeck et al.
patent: 7149715 (2006-12-01), Browne et al.
patent: 7167980 (2007-01-01), Chiu
patent: 7181437 (2007-02-01), Indeck et al.
patent: 7181608 (2007-02-01), Fallon et al.
patent: 7181765 (2007-02-01), Patel et al.
patent: 7222114 (2007-05-01), Chan et al.
patent: 7224185 (2007-05-01), Campbell et al.
patent: 7225188 (2007-05-01), Gai et al.
patent: 7251629 (2007-07-01), Marynowski et al.
patent: 7286564 (2007-10-01), Roberts
patent: 7305383 (2007-12-
Dharmapurikar Sarang
Krishnamurthy Praveen
Taylor David Edward
Foud Hicham B
Glenn Patent Group
Kumar Pankaj
Radlo Edward J.
Washington University
LandOfFree
Method and system for performing longest prefix matching for... 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 performing longest prefix matching for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing longest prefix matching for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4055024