Method for compressing route data in a router

Details Method for compressing route data in a router Method for compressing route data in a router

2008-10-15

2010-12-14

Kumar, Pankaj (Department: 2467)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S389000, C370S392000, C370S395310

Reexamination Certificate

active

07852852

ABSTRACT:
A method for a router having a routing table and a forwarding table. In an embodiment, the method includes creating an entry for use in the forwarding table, the entry corresponding to multiple entries of the routing table. The entry may correspond to a set of entries of the routing table which specify overlapping IP addresses and a same next hop router, in one example. In another example, the entry may be an aggregate entry corresponding to a set of entries of the routing table which specify the same next hop router.

REFERENCES:
patent: 4885744 (1989-12-01), Lespagnol et al.
patent: 5140417 (1992-08-01), Tanaka et al.
patent: 5734649 (1998-03-01), Carvey et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5905725 (1999-05-01), Sindhu et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5920699 (1999-07-01), Bare
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6308219 (2001-10-01), Hughes
patent: 6434148 (2002-08-01), Park et al.
patent: 6526055 (2003-02-01), Perlman et al.
patent: 6614789 (2003-09-01), Yazdani et al.
patent: 6721316 (2004-04-01), Epps et al.
patent: 6731633 (2004-05-01), Sohor et al.
patent: 6778490 (2004-08-01), Achilles et al.
patent: 6795886 (2004-09-01), Nguyen
patent: 6859455 (2005-02-01), Yazdani et al.
patent: 6934281 (2005-08-01), Kanehara
patent: 6965615 (2005-11-01), Kerr et al.
patent: 7031320 (2006-04-01), Choe
patent: 7069372 (2006-06-01), Leung, Jr. et al.
patent: 7111071 (2006-09-01), Hooper
patent: 7184440 (2007-02-01), Sterne et al.
patent: 7230912 (2007-06-01), Ghosh et al.
patent: 7289517 (2007-10-01), Shimonishi
patent: 7308495 (2007-12-01), Ishiyama et al.
patent: 7315900 (2008-01-01), Ofelt et al.
patent: 7339930 (2008-03-01), Mehta
patent: 7362763 (2008-04-01), Wybenga et al.
patent: 7418505 (2008-08-01), Lim et al.
patent: 7433355 (2008-10-01), Wilson et al.
patent: 7453883 (2008-11-01), Lynch et al.
patent: 7483430 (2009-01-01), Yuan et al.
patent: 7536476 (2009-05-01), Alleyne
patent: 2009/0046724 (2009-02-01), Lynch et al.
U.S. Appl. No. 10/414,137, Non Final Office Action mailed Mar. 13, 2007, 11 pgs.
U.S. Appl. No. 10/414,137, Response filed Jun. 7, 2007 to Non Final Office Action mailed Mar. 13, 2007, 11 pgs.
U.S. Appl. No. 10/414,137, Final Office Action mailed Sep. 11, 2007, 16 pgs.
U.S. Appl. No. 10/414,137, Response filed Dec. 11, 2007 to Final Office Action mailed Sep. 11, 2007, 13 pgs.
U.S. Appl. No. 10/414,137, Advisory Action mailed Jan. 18, 2008, 3 pgs.
U.S. Appl. No. 10/414,137, Request for Continued Examination filed Feb. 7, 2008, 2 pgs.
U.S. Appl. No. 10/414,137, Non-Final Office Action mailed Feb. 21, 2008, 15 pgs.
U.S. Appl. No. 10/414,137, Notice of Allowance mailed Jul. 1, 2008, 2 pgs.
“Xelerated Packet Devices”,MicroDesign Resources Presentation, Network Processor Forum, (Jun. 14, 2001), 11 pgs.
Belenkiy, A., “Deterministic IP Table Lookup at Wire Speed”,The Internet Global Summit(INET '99), http://www.isoc.org/inet99/proceedings/4j/4j—2.htm, (observed May 12, 2003), 18 pgs.
Chiueh, T.-C., et al., “High-Performance IP Routing Table Lookup Using CPU Caching”,Proceedings, Eighteenth Annual Joint Conference of the IEEE Computer and Communication Societies(INFOCOM '99), vol. 3, (1999), 1421-1428.
Degermark, M., et al., “Small Forwarding Tables for Fast Routing Lookups”,Proceedings, ACM SIGCOMM '97, (1997), 3-14.
Gupta, P., et al., “Classifying Packets With Hierarchical Intelligent Cuttings”,IEEE Micro, 21(1), (Jan./Feb. 2000), 34-41.
Gupta, P., et al., “Packet Classification on Multiple Fields”,Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication(ACM SIGCOMM '99), (1999), 147-160.
Gupta, P., et al., “Routing Lookups in Hardware at Memory Access Speeds”,Proceedings, Seventeen Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM '98), vol. 3, (1998), 1240-1247.
Lakshman, T. V., et al., “High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching”,Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications(ACM SIGCOMM '98), (1998), 203-214.
Lampson, B., et al., “IP Lookups Using Multiway and Multicolumn Search”,IEEE/ACM Transactions on Networking, 7(3), (Jun. 1999), 324-334.
Lindberg, K., “Multi-Gigabit Routers”,Proceedings, HUT Internetworking Seminar, http://www.tml.hut.fi/Opinnot/Tik-110.551/1998/papers/02MultiGigabitRouter/paper.html, (observed May 12, 1998), 14 pgs.
McAuley, A. J., et al., “Fast Routing Table Lookup Using CAMs”,Proceedings, Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking: Foundation for the Future(INFOCOM '93), vol. 3, (1993), 1382-1391.
Partridge, C., et al., “A 50-Gb/s IP Router”,IEEE/ACM Transactions on Networking, 6(3), (Jun. 1998), 237-248.
Qui, L., et al., “Fast Firewall Implementations for Software and Hardware-Based Routers”,Microsoft Technical Report MSR-TR-2001-61, (Jun. 2001), 18 pgs.
Srinivasan, V., et al., “Fast and Scalable Layer Four Switching”,Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications(ACM SIGCOMM '98), (1998), 191-202.
Srinivasan, V., et al., “Packet Classification Using Tuple Space Search”,Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols(ACM SIGCOMM '99), (1999), 135-146.
Waldvogel, M., et al., “Scalable High Speed IP Routing Lookups”,Proceeding, ACM SIGCOMM '97, (1997), 25-36.

Affiliated with

Also associated with

Rating

Method for compressing route data in a router 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 for compressing route data in a router, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for compressing route data in a router will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4192803