Patent ID: 7120120

Claim:
A method for constructing end-to-end paths between a specified origin and a specified destination in a two-level multi-area routing domain operated according to a simple link state routing protocol, comprising the steps of: acquiring topology and routing information for each area in the routing domain; identifying an origin area and an entry point in the origin area, wherein the origin area is a level one area; retrieving a route entry in the origin area, the route entry being associated with a specified destination; extracting a set of exit points from the origin area through which the route entry associated with the specified destination can be reached; for each exit point associated with the route entry, determining a shortest path in the origin area between the entry point and the exit point; determining whether the route entry is a null or default entry; if the route entry is not a null or default entry, for each exit point associated with the route entry, calculating a cost of reaching the route entry through the exit point by adding a cost of the shortest path between the entry point and the exit point to a cost of reaching the route entry from the exit point; if the route entry is a null or default entry: selecting at least one exit point into a level two area, wherein each selected exit point corresponds to a shortest path having a minimum cost, and calculating a cost of reaching the route entry through each selected exit point by adding a cost of the shortest path to a cost of reaching the route entry from the exit point; and identifying at least one total path to the specified destination through an exit point, wherein each total path comprises a concatenation of a plurality of hops between the entry point and the specified destination.