Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2008-01-29
2008-01-29
Pezzlo, John (Department: 2616)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S477000, C707S793000, C711S216000
Reexamination Certificate
active
11034839
ABSTRACT:
A method and apparatus for locating in a list of pre-defined codes, a longest code matching a given code. The method and apparatus involve producing a search mask encoding at least one portion of said given code and comparing the search mask to a search key having a Prefix Node Bit Array (PNBA) in which a bit is set active in at least one of a plurality of bit positions corresponding to possible bit combinations of bits in a bit string having a length equal to or less than the longest predefined code in the plurality of pre-defined codes and arranged by the lengths of possible bit combinations and by numeric values of the bit combinations, to identify a common active bit position in the search key and the search mask corresponding to one of the pre-defined codes having a length greater than all others of said pre-defined codes which correspond to common active bit positions.
REFERENCES:
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6526055 (2003-02-01), Perlman et al.
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6614789 (2003-09-01), Yazdani et al.
patent: 2002/0059197 (2002-05-01), Hunter et al.
Srinivasan, V.; Varghese, G.; “Faster IP Lookups using Controlled Prefix Expansion”, ACM Transactions on Computer Systems, pp. 1-10, Jun. 1998.
Eatherton, William N.; “ASIC Based IPV4 Lookups”, Washington University, Applied Research Laboratory, pp. 1-22, Jun. 23, 1998.
Eatherton, William N.; “Hardware-Based Internet Protocol Prefix Lookups”, Thesis, Washington University, pp. 1-100, May 1999.
Srinivasan, V.; Varghese, G.; “Fast Address Lookups Using Controlled Prefix Expansion”, ACM Transactions on Computer Systems, vol. 17, No. 1, pp. 1-40, Feb. 1999.
Filippi, E.; Innocenti, V.; Vercellone, V.; “Address Lookup Solutions for Gigabit Switch/Router”, Globecom '98, Sydney, Australia, Nov. 1998.
Degermark, Mikael; Brodnik, Andrej; Carlsson, Svante; Pink, Stephen; “Small Forwarding Tables Tables for Fast Routing Lookups”, Proc. of ACM SIGCOMM, pp. 3-14, Sep. 1997.
Doeringer, Willibald; Karjoth, Gunter; Nassehi, Medhi; “Routing on Longest-Matching Prefixes”, IEEE/ACM Trans. On Networking, vol. 4, No. 1, pp. 86-97, Feb. 1996.
Tzeng, Henry Hong-Yi; Przygienda, Tony; “On Fast Address-Lookup Algorithms”; pp. 1067-1082, IEEE Journal On Selected Areas In Communications, vol. 17, No. 6, Jun. 1999.
Tzeng, Henry Hong-Yi; “Longest Prefix Search Using Compressed Trees”, Globecom '98, Sydney, Australia, Nov. 1998.
Kumar, Vijay P.; Lakshman, T.V.; Stiliadis, Dimitrios; Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet, IEEE Communications Magazine, pp. 152-164, May 1998.
Gupta, Pankaj; Lin, Steven; McKeown, Nick; “Routing Lookups in Hardware at Memory Access Speeds”, IEEE INFOCOM, Apr. 1998.
Nilsson, Stefan; Karlsson, Gunnar; “Fast Address Lookup for Internet Routers”, IFIP Workshop on Broadband Communications, pp. 10-22, Apr. 1998.
Waldvogel, Marcel; Varghese, George; Turner, Jon; Plattner, Bernhard; “Scalable High Speed IP Routing Lookups”, Proc. Of ACM SIGCOM, Sep. 1997.
Lampson, B.; Srinivasan, V.; Varghese, G.; “IP Lookups Using Multiway and Multicolumn Search”, pp. 1-23, Aug. 1997.
Zitterbart, M.; Harbaum, T.; Meier, D.; Brokelmann, D.; “HeaRT: High Performance Routing Table Look Up”, IEEE Workshop Architecture & Implementation of High Performance Communications Subsystems, Thessaloniki, Greece, Jun. 1997.
Fuller, V.; Li, T.; Yu, J.; Varadhan, K.; “Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy”, RFC 1519, Internet Engineering Task Force, Sep. 1993.
Pei, Tong Bi; Zukowksi, Charles; “Putting Routing Tables in Silicon”, IEEE Network Magazine, pp. 42-50, Jan. 1992.
Morrison, Donald R.; “PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric”, Journal of the Association for Computing Machinery, pp. 514-534, vol. 15, No. 4, Oct. 1968.
Aweya James
Montuno Delfin Y.
Noretl Networks Limited
Pezzlo John
LandOfFree
Method and apparatus for encoding a plurality of pre-defined... 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 apparatus for encoding a plurality of pre-defined..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding a plurality of pre-defined... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3921145