Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2006-01-31
2006-01-31
Duong, Frank (Department: 2666)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06993025
ABSTRACT:
A method of encoding a plurality of pre-defined codes into a search key and a method of using the search key to locate a longest matching pre-defined code to a given code is disclosed. Encoding the pre-defined codes into a search key involves producing a prefix node bit array (PNBA) having a plurality of bit positions corresponding to possible bit combinations of a bit string having a length equal to or less than the longest predefined code in said plurality of said pre-defined codes such that said bit positions are arranged by the lengths of said possible bit combinations and by numeric value of said possible bit combinations and to setting bits active in bit positions which correspond to bit combinations identified by said pre-defined codes. The method of locating involves producing a search mask encoding at least one portion of said given code and comparing said 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 said plurality of said pre-defined codes and arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations, to identify a common active bit position in said search key and said search mask corresponding to a one of said 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 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.
Srinivasan et al, Faster IP Lookups using Controlled Prefix Expansion, pp. 1-10, ACM, Jun. 1998.
Eatherton, ASIC Based IPV4 Lookups, Washington University, Applied Research Laboratory, pp. 1-22, Jun. 23, 1998.
Eatherton, Hardware-Based Internet Protocol Prefixed Lookups, Thesis, Washington University, pp. 1-100, May 1999.
Tzeng, Henry-Yi and Przygienda, Tony; “On Fast Address-Lookup Algorithms”; pp. 1067-1082, IEEE Journal On Selected Areas In Communications, vol. 17, No. 6, Jun. 1999.
Fuller, V.; T. Li; J. Yu and K. Varadhan, “Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy”, RFC 1519, Internet Engineetring Task Force, Sep. 1993.
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.
Degermark, Mikael; Brodnik, Andrej; Carlsson, Svante; Pink, Stephen; “Small Forwarding Tables for Fast Routing Lookups”, Proc. of ACM SIGCOMM, pp. 3-14, Sep. 1997.
Gupta, Pankaj: Steven Lin and Nick McKeown, “Routing Lookups in Hardware at Memory Access Speeds”, IEEE INFOCOM, Apr. 1998.
Kumar, Vijay P.; T.V. Lakshman and Dimitrios Stiliadis, Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet, IEEE Communication Magazine, pp. 152-164, May 1998.
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.
Nilsson, Stefan and Gunnar Karlsson, “Fast Address Lookup for Internet Routers”, IFIP Workshop on Broadband Communications, pp. 10-22, Apr. 1998.
Pei, Tong Bi and Charles Zukowksi, “Putting Routing Tables in Silicon”, IEEE Network Magazine, pp. 42-50, Jan. 1992.
Tzeng, Henry Hong-Yi, “Longest Prefix Search Using Compressed Trees”, Globecom '98, Sydney, Australia, Nov. 1998.
Waldvogel, Marcel; George Varghese; Jon Turner and Bernhard Plattner, “Scalable High Speed IP Routing Lookups”, Proc. of ACM SIGCOM, Sep. 1997.
Zitterbart, M.; T. Harbaum; D. Meier; D. Brokelmann, “HeaRT: High Performance Routing Table Look Up”, IEEE Workshop Architecture & Implementation of High Performance Communications Subsystems, Thessaloniki, Greece, Jun. 1997.
Lampson, B.; V. Srinivasan and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search”, pp. 1-23, Aug. 1997.
Doeringer, Willibald; Karjoth, Gunter; “Routing on Longest-Matching Prefixes”, IEEE Trans. on Networking, vol. 4, No. 1, pp. 86-97, Feb. 1996.
Filippi, E.; Innocenti, V.; Vercellone, V.; “Address Lookup Solutions for Gigabit Switch/Router”, Globecom '98, Sydney, Australia, Nov. 1998.
Aweya James
Montuno Delfin Y.
Duong Frank
Nortel Networks Limited
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-3577966