Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network access regulating
Reexamination Certificate
2008-01-29
2008-01-29
Vaughn, William (Department: 2144)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network access regulating
C709S238000, C709S245000, C711S205000, C711S206000
Reexamination Certificate
active
10439022
ABSTRACT:
The present invention provides a technique for efficiently looking up address-routing information in an intermediate network node, such as a router. To that end, the node locates routing information stored in its memory using one or more “lookup” tables (LUT) which can be searched using a small, bounded number of dependent lookups, thereby reducing the number of dependent lookups conventionally performed. The LUTs are arranged so each table provides routing information for network addresses whose subnet mask lengths are within a different range (“stride”) of mask lengths. According to the technique, the node locates a network address's routing information by searching the LUTs, in order of decreasing prefix lengths, until the routing information is found. Preferably, several tables are searched in parallel. A match in a LUT may further point to a small MTRIE that enables the final bits of a prefix to be matched. That final MTRIE is searched using a relatively small, bounded number of dependent lookups.
REFERENCES:
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6212183 (2001-04-01), Wilford
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6343072 (2002-01-01), Bechtolsheim et al.
patent: 6374326 (2002-04-01), Kanzal et al.
patent: 6424650 (2002-07-01), Yang et al.
patent: 6449256 (2002-09-01), Varghese et al.
patent: 6516383 (2003-02-01), Patra et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6581106 (2003-06-01), Crescenzi et al.
patent: 6658002 (2003-12-01), Ross et al.
patent: 6658482 (2003-12-01), Chen et al.
patent: 6678269 (2004-01-01), Michels et al.
patent: 7103035 (2006-09-01), Kanuri
patent: 2004/0013113 (2004-01-01), Singh et al.
patent: 2004/0042463 (2004-03-01), Guerrero et al.
patent: 2004/0100950 (2004-05-01), Basu et al.
patent: WO 2004/105351 (2004-12-01), None
Radia Perlman, Interconnections, Second Edition: Bridges, Routers, Switches, and Internetworking Protocol, Addison-Wesley Longman, Inc., Chapter 13, pp. 347-365, Jan. 2000.
Radia Perlman, Interconnections, Second Edition: Bridges, Routers, Switches, and Internetworking Protocols, Addison-Wesley Longman, Inc., Chapter 9, pp. 189-220, Jan. 2000.
CISCO, How to Choose the Best Router Switching Path for Your Network, http://cisco.com/warp/public/105/20.html, pp. 1-11, Jan. 2003.
EZChip Technologies, IPv4 to IPv6 is Not Merely 50% More, White Paper, pp. 1-4, Aug. 10, 2003.
R. Hinden et al., IP Version 6 Addressing Architecture, RFC 2373, The Internet Society, pp. 1-26, Jul. 1998.
S. Deering et al., Internet Protocol, Version 6 (IPv6) Specification, RFC 2460, The Internet Society, pp. 1-40, Dec. 1998.
Felix Yuan, et al., Hierarchical Hash Method for Performing Forward Route Lookup, U.S. Appl. No. 10/377,841, filed Feb. 28, 2003.
“Written Opinion of the International Searching Authority” for International Application No. PCT/US2004/015281 with an International Filing date of May 13, 2004.
“International Search Report” for International Application No. PCT/US2004/015281 with an International Filing date of May 13, 2004.
Uga M et al: “A fast and compact longest match prefix look-up method using pointer cache for very long network address” IEEE Computer Communications and Networks, Proceedings, Eighth International Conference, Boston, MA, ISBN 0-7803-5794-9, pp. 595-602, Oct. 11-13, 1999.
Barach David Richard
Batacharia Bobby
Cesari and McKenna LLP
Cisco Technology Inc.
Ibrahim Mohamed
Vaughn William
LandOfFree
Bounded index extensible hash-based IPv6 address lookup method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bounded index extensible hash-based IPv6 address lookup method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded index extensible hash-based IPv6 address lookup method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3957682