Distributed quality of service routing

Abstract

The present invention relates to distributed systems and methods for finding a path from a source node to a destination node where the path chosen satisfies a path constraint for a first additive path parameter and concurrently optimizes a second additive path parameter. One embodiment of the invention provides a routing method. The method includes receiving at a current node a construct path message from a neighboring previous node. The construct path message includes first and second values for first and second additive parameters. The method includes checking whether the first value satisfies an optimality condition and whether the second value indicates a feasible path given a path constraint. If the first value satisfies an optimality condition and the second value indicates a feasible path given a path constraint, then the method (i) sends out a construct path message to a next neighboring node, (ii) increments a number-of-acknowledgement-messages variable by the number of construct path messages sent, and (iii) adds an entry to a predecessor array stored at the current node. The entry includes an identifier for the predecessor neighboring node, the first path value, and the second path value. If not, the method sends an acknowledgement message to the neighboring previous node.