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

2003-04-14

2008-11-18

Chan, Wing F. (Department: 2619)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S389000, C370S392000, C370S395310

Reexamination Certificate

active

07453883

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: 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: 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: 6801950 (2004-10-01), O'Keeffe et al.
patent: 6859455 (2005-02-01), Yazdani et al.
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: 7230912 (2007-06-01), Ghosh et al.
patent: 7308495 (2007-12-01), Ishiyama et al.
patent: 7315900 (2008-01-01), Ofelt et al.
“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-4020275