Patent ID: 7343424
Filing Date: 2008-03-11
Classification: H04L

Abstract:
1. A method for determining one or more shortest paths through a network portion of a computer network from a source vertex to one or more destination vertices according to a link-state protocol, the method comprising: processing a graph representation of the network portion, the graph representation including nodes and edges representing vertices and connections therebetween, respectively wherein maintaining the candidate list of nodes as a Fibonacci heap of Fibonacci nodes, wherein the Fibonacci heap of Fibonacci nodes is stored in a generic format that is independent of the link-state protocol; and operating on the Fibonacci heap of Fibonacci nodes to determine one or more shortest paths by processing the Fibonacci heap of Fibonacci nodes according to a particular algorithm that is independent of the link-state protocol, wherein the operating on the Fibonacci heap is performed by a plurality of operations, each of the operations is capable of operating on a plurality of link state protocols, wherein the plurality of operations includes an extract minimum operation for extracting a node from the candidate list of nodes that has a minimum cost according to the Dijkstra-like algorithm, and the extract minimum operation is operable for any of the plurality of link state protocols, wherein the candidate list processing includes initially accepting a prior-created generic description of the Fibonacci heap of Fibonacci nodes that is independent of the link-state protocols, and wherein the initially accepting the prior-created generic description for the Fibonacci heap of Fibonacci nodes includes accepting the prior-created generic description via a generalized application program interface, the generalized application programming interface including interfaces for the plurality of operations.