Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2005-11-08
2005-11-08
Edelman, Bradley (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C370S254000, C707S793000
Reexamination Certificate
active
06963924
ABSTRACT:
An IP routing lookup scheme and system for a multi-gigabit switching router which can reach 3 memory accesses in the worst case using memory size less than 512 KB is disclosed. The invention can compress a routing table with 40,000 routing entries into a forwarding table of 450–470 Kbytes. According to the present invention, a segmentation table storage device stores a next hop or a pointer for looking up a next hop for an incoming packet having prefix length less than or equal to 16 bits. The Next Hop Array storage device is for storing the next hops for a packet having prefix length larger than 16 bits and offset length less than or equal to 3 bits. A Compressed Next Hop Array storage device is encoded and decoded according to a Code Word Array storage device. The Compressed Next Hop Array storage device stores next hops for the incoming packet having prefix length larger than 16 bits and offset length larger than 3 bits. Thus, in the worst case, an output port for a route prefix can be found in 3 memory accesses.
REFERENCES:
patent: 5917820 (1999-06-01), Rekhter
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6141738 (2000-10-01), Munter et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6434144 (2002-08-01), Romanov
patent: 6546391 (2003-04-01), Tsuruoka
“A Slot Interleaved Multiple Access Scheme for DQDB Metropolitan Area Networks,” by N-F Huang, IEEE, 1993.
“The Strongly Connecting Problem on Multihop Packet Radio Networks,” by N-F Huang, IEEE, 1989.
Gupta et al., “Routing Lookups in Hardware at Memory Access Speeds,” Apr. 1998, Seventeenty Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE, vol. 3, pp. 1240-1247.
Nilsson et al., “Fast Address Lookup for Internet Routers,” 1998, from IFIP 4thInternational Conference on Broadband Communications, pp. 11-22, printed from http://www.nada.kth.se/˜snilsson/public/papers/router/.
Huang Nen-Fu
Zhao Shi-Ming
Dickinson Wright PLLC
Edelman Bradley
LandOfFree
IP routing lookup scheme and system for multi-gigabit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with IP routing lookup scheme and system for multi-gigabit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and IP routing lookup scheme and system for multi-gigabit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3502169