Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2003-06-20
2008-03-11
Duong, Oanh (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S239000, C709S240000, C709S242000, C370S238000
Reexamination Certificate
active
07343424
ABSTRACT:
In accordance with an aspect of the invention, one or more shortest paths is determined through a portion of a computer network, from a source vertex to one or more destination vertices according to a link-state protocol. A graph representation of the network portion is processed. The graph representation includes nodes and edges representing the vertices and connections therebetween. The processing includes operating on the graph representation according to a Djkstra-like algorithm. A subset of the Djkstra-like algorithm processing includes candidate list processing, to maintain and operate upon a candidate list (OSPF, IS-IS) of nodes that have been visited in the Djkstra-like algorithm processing. Finally, the candidate list processing is optimized relative to standard Djkstra algorithm processing for the link-state protocol. The optimized candidate list processing may be, for example, such that the candidate list processing operates on a candidate list of nodes that is stored in a generic format, as a Fibonacci heap of Fibonacci nodes in a generic format that is independent of the link-state protocol. Furthermore, the candidate list processing may be accessible via a generic application programming interface (API). As a result, the candidate list processing is useable for various link-state protocols, including various link-state routing protocols such as OSPF and IS-IS.
REFERENCES:
patent: 5570466 (1996-10-01), Oechsle
patent: 6098107 (2000-08-01), Narvaez-Guarnieri et al.
patent: 6477515 (2002-11-01), Boroujerdi et al.
patent: 6992988 (2006-01-01), Reynders et al.
patent: 7062743 (2006-06-01), Kahng et al.
patent: 2001/0032272 (2001-10-01), Fujita
patent: 2001/0033556 (2001-10-01), Krishnamurthy et al.
patent: 2002/0067693 (2002-06-01), Kodialam et al.
patent: 2002/0067720 (2002-06-01), Garcia-Luna-Aceves et al.
patent: 2002/0141345 (2002-10-01), Szviatovszki et al.
patent: 2002/0141346 (2002-10-01), Garcia-Luna-Aceves et al.
patent: 2002/0172157 (2002-11-01), Rhodes
patent: 2003/0005149 (2003-01-01), Haas et al.
patent: 2003/0026268 (2003-02-01), Navas
patent: 2003/0043756 (2003-03-01), Reynders et al.
patent: 2003/0165117 (2003-09-01), Garcie-Luna-Aceves et al.
patent: 2003/0185209 (2003-10-01), Lee
patent: 2003/0185226 (2003-10-01), Tang et al.
Paolo Narvaez et al., “New Dynamic Algorithm for shortest Path Tree Computation”, IEE/ACM Transactions on Networking, vol. 8, No. 6, Dec. 2000.
Dong et al., “Accuulative Competition Neural Network for Shortest Path Tree Computation”, Proceedings of the second International Conference on Machine Learning and Cybernetics, Xian, Nov. 2-5, 2003.
Xiao et al., “Dynamic Shortest Path Tree Update for Multiple Link State Decrements”, Apr. 2007.
Fredman et al., “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithm”, Journal of the Association for Computing Machinery, vol. 34, No. 3, Jul. 1987.
Duong Oanh
NextHop Technologies, Inc.
Perkins Coie LLP
LandOfFree
Fibonacci heap for use with internet routing protocols does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fibonacci heap for use with internet routing protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fibonacci heap for use with internet routing protocols will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3972325