Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2005-05-03
2005-05-03
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000
Reexamination Certificate
active
06888838
ABSTRACT:
A novel compression method uses bitmaps to reduce the memory storage requirement of routing table information to about 3 MB. The data structure can be used for both route lookup and update. It does not require a separate data structure to be used for route update. A fast route lookup method is also disclosed. An efficient update method supports incremental route update. Through configuring a processor properly and developing a few customized instructions specifically for route lookup, the system can achieve more than 10 million lookups per second (MLPS) at 200 MHz. Using a configurable processor for route lookup/update provides more flexibility and extensibility which supports different data structures and lookup/update methods to meet application specific needs. The data structure and lookup method can be implemented in pure hardware in a pipelined fashion to achieve approximately 100 MLPS.
REFERENCES:
patent: 6018524 (2000-01-01), Turner et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6571313 (2003-05-01), Filippi et al.
patent: 6631419 (2003-10-01), Greene
patent: 6658482 (2003-12-01), Chen et al.
patent: 6697363 (2004-02-01), Carr
Gupta, et al., “Routing Lookups in hardware at Memory access Speeds,” IEEE, 1998, pp. 1240-1246.
Chiueh, et al., “High-Perfomance IP Routing Table Lookup Using CPU Caching,” IEEE, 1999, pp. 1421-1427.
Degermark, et al., “Small Forwarding Tables for Fast Routing Lookups,” ACM, 1997, pp. 3-13.
Srinivsan et al., “Fast Address Lookups Using Controlled Prefix Expansion,” pp. 1-37.
Huang, et al., “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers,” IEEE Journal on Selected Areas in Communications, vol. 17, No. 6, Jun. 1999, pp. 1093-1104.
Ji Hongbin
Srinivasan Rangarajan
Patel Ajit
Pillsbury & Winthrop LLP
Shah Chirag
Tensilica, Inc.
LandOfFree
Fast IP route lookup with configurable processor and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast IP route lookup with configurable processor and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast IP route lookup with configurable processor and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3413078