Method for finding shortest network routing paths subject to system constraints

摘要

A method is disclosed for determining the shortest paths between a source node and a destination node in a network wherein the paths satisfy imposed system constraints. In accordance with the method of the invention, candidate paths are evaluated by accumulating system parameter information from a source node and projecting the system parameter information ahead to the destination node. When the accumulated and projected system parameter information for the candidate path satisfies the imposed system constraints, the candidate path is saved for further evaluation. The candidate paths are sorted in the order such that those paths most-likely to have the shortest lengths and satisfy the imposed system constraint are evaluated first. In one embodiment of the invention, candidate paths that fail to satisfy the imposed system constraints are removed from further processing. Thus, only candidate paths that have at least one complete path that satisfies the imposed system constraints are evaluated further.