Patent ID: 7633875

Claim:
A method for performing route calculations in a link state routing protocol at a node within a computer network, the method comprising: receiving new route information at the node; evaluating existing routes of the node to determine if said new route information improves at least one of the existing routes or at least one of the existing routes is made worse or lost; and recalculating routes and modifying a routing table for the node only when said new route information improves at least one of the existing routes or at least one of the existing routes is made worse or lost, wherein recalculating routes comprises modifying information about links within the network without examining each of the nodes within the network, wherein each of said routes are evaluated and recalculated in an increasing order of cost and evaluating and recalculating one of said routes comprises: if said route improves, making no changes to said route and evaluating other routes comprising links in said route; if said route is made worse, recalculating routes to all nodes in a subtree of the node; and if said route is lost, identifying a parent node in a spanning tree and reattaching the node at the parent node; and applying Dijkstra's algorithm only to nodes to which a path has been identified and the path is not yet known to be minimum cost; and calculating output adjacencies for the node.