Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
2007-01-30
2007-01-30
Dalencourt, Yves (Department: 2157)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S238000, C711S161000, C711S162000, C707S793000, C707S793000, C370S352000
Reexamination Certificate
active
10246204
ABSTRACT:
A method and apparatus for reducing the number of write operations during route updates in router forwarding engines eliminates “excess” (i.e., “redundant”) writes to the routing trie. One or more writes are “redundant” with respect to another write if the timestamp of the other write is the same as or later than (by an amount less than a given threshold) the timestamp of each of the one or more writes, and if the state of the routing trie after the other write has been applied is equivalent whether or not any of the one or more writes have also been applied. Excess writes may be advantageously eliminated when routes are either added to or withdrawn from the routing trie, and deleted subtrees may be advantageously cached for subsequent re-addition thereto.
REFERENCES:
patent: 6643671 (2003-11-01), Milillo et al.
patent: 2003/0026246 (2003-02-01), Huang et al.
Cheng, G. et al.,Optimal Routing Table Design of IP Address Lookups Under memory Constraints. In Proceedings of Infocom '99, pp. 1437-1444, New York, NY, Mar. 1999.
Degemark, M. et al.,Small Forwarding Tables for Fast Routing Lookups. In Proceedings of SIGCOMM '97, p. 3-14, Cannes, France, Sep. 1997.
Draves, R. P. et al.,Constructing Optimal IP Routing Tables. In Proceedings of Infocom '99, New York, NY, Mar. 1999.
Gupta, P. et al.,Routing Lookups in Hardware at Memory Access Speeds. In Proceedings of Infocom '98, p. 1240-1247, San Francisco, CA, Apr. 1998.
Gupta, P. et al.,Near-Optimal Routing Lookups with Bounded Worst Case Performance. In Proceedings of Infocom '00, p. 1184-1192, Tel Aviv, Israel, Mar. 2000.
Lampson B., et al.,IP Lookups Using Multiway and Multicolumn Search. In Proceedings of Infocom '98, p. 1248-1256, San Francisco, CA, Apr. 1998.
Nilsson, S. et al.,IP-address Lookup Using LC-tries. IEEE Journal on Selected Areas in Communications, p. 1083-1092, Jun. 1999.
Sikka, S. et al.,Memory-Efficient State Lookups with Fast Updates. In Proceedings of SIGCOMM '00, p. 335-347, Stockholm, Sweden, Aug. 2000.
Srinivasan, V. et al.,Fast Address Lookups Using Controlled Prefix Expansion. ACM Transactions on Computer Systems, p. 1-40, Feb. 1999.
Waldvogel, G. et al.,Scalable High Speed IP Routing Lookups. In Proceedings of SIGCOMM '97, p. 25-38, Cannes, France, Sep. 1997.
Basu Anindya
Narlikar Girija J.
Brown Kenneth M.
Dalencourt Yves
Lucent Technologies - Inc.
LandOfFree
Method and apparatus for reducing the number of write... 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 and apparatus for reducing the number of write..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing the number of write... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3764075