Distributed quality of service routing

1. A routing method comprising:

receiving at a current node a construct path message from a neighboring previous node, the construct path message including first and second values for first and second additive parameters;

checking whether the first value satisfies an optimality condition and whether the second value indicates a feasible path given a path constraint; and

if the first value satisfies an optimality condition and the second value indicates a feasible path given a path constraint, then testing whether each outgoing link satisfies a link constraint;

if an outgoing link to a next neighboring node satisfies the link constraint, then (i) sending out a construct path message to the next neighboring node, (ii) incrementing a number-of-acknowledgement-messages variable by the number of construct path messages sent, and (iii) adding an entry to a predecessor array stored at the current node, the entry including an identifier for the predecessor neighboring node, the first path value, and the second path value.

2. The routing method of claim 1 , wherein the method further comprises:

storing a current node value corresponding to the first additive parameter; and wherein checking whether the first value satisfies an optimality condition comprises:

determining whether the first value of the first additive parameter plus a measure of a link value for the first additive parameter is less than the stored current node value corresponding to the first parameter; and

if the first value of the first additive parameter plus a measure of a link value for the first additive parameter is less than the stored current node value corresponding to the first parameter, setting the stored current node value equal to the first value of the first additive parameter plus a measure of a link value for the first additive parameter.

3. The routing method of claim 1 , further comprising:

prior to receiving at a current node a construct path message, receiving at a source node a path request from an application for a path from the source node to a destination node;

checking whether a feasible path exists given a path constraint;

if a feasible path exists, then testing whether each outgoing link satisfies a link constraint;

if an outgoing link to a next neighboring node satisfies the link constraint, then sending out a construct path message to the next neighboring node;

else sending a no feasible path message to the application;

else sending a no feasible path message to the application; and

incrementing the variable for the number of acknowledge messages that need to be received by the number of construct path messages sent.

4. The routing method of claim 3 , wherein the method further comprises:

prior to receiving at a current node a construct path message, initializing first and second stored values associated with first and second additive parameters and stored at each node.

5. The routing method of claim 3 , wherein the method further comprises:

receiving at a node an acknowledgement message;

decrementing the number-of-acknowledgement-messages variable by one;

determining whether the node's number-of-acknowledgement-messages variable is equal to zero; and

if the node's number-of-acknowledgement-messages variable is equal to zero, then determining if the node is the source node;

if the node is the source node, then sending out terminate messages to neighboring nodes;

else sending out an acknowledgement message to the most recent predecessor node as listed in the predecessor array.

6. The routing method of claim 5 , wherein the method further comprises:

receiving at a node a terminate message; and determining if the node is the destination node;

if the node is the destination node, then sending a back track message to the predecessor node as listed in the predecessor array;

else sending out terminate messages to neighboring nodes.

7. The routing method of claim 6 , wherein the method further comprises:

receiving a backtrack message at a node;

determining if the receiving node is the source node;

if the receiving node is the source node, then sending path_found message to the application;

else (i) determining a predecessor node from the predecessor array, (ii) sending a back track message to the predecessor node, and (iii) creating a permanent entry for the application in a routing database for the node.

8. The routing method of claim 7 , wherein determining a predecessor node from the predecessor array comprises:

receiving first predecessor identification data from a neighboring node;

searching the predecessor array for a first entry corresponding to the first predecessor identification data; and

forwarding second predecessor identification data to the predecessor node associated with the first entry.

9. The routing method of claim 8 , wherein the predecessor identification data includes an identifier for a predecessor neighboring node, a first path value, and a second path value.

10. The routing method of claim 1 , wherein the method further comprises:

creating a construct path message entry, the entry including data related to a requesting application, a source node, a destination node, a path constraint and a link constraint.

11. The routing method of claim 1 , wherein the construct path message includes data related to a requesting application, a destination, the path constraint, the link constraint, and a previous node.

12. A routing system comprising:

a construct path message receiving module operative to receive a construct path message from a neighboring node, the construct path message including first and second values for first and second additive parameters;

an optimality and path constraint feasibility testing module in communication with the construct path message receiving module and operative to check whether the first value satisfies an optimality condition and whether the second value indicates a feasible path given a path constraint; and, if the first value satisfies an optimality condition and the second value indicates a feasible path given a path constraint, operative to send out a construct path message to a next neighboring node;

a number of acknowledgment messages management module in communication with the testing module and, after the operation of the testing module, the number of acknowledgement message management module is then operative to increment a number-of-acknowledgement-messages variable by the number of construct path messages sent; and

a predecessor array management module in communication with the testing module and, after the operation of the testing module, the predecessor array management module is then operative to add an entry to a predecessor array stored at the current node, the entry including an identifier for the predecessor neighboring node, the first path value, and the second path value.

13. A routing method comprising:

receiving at a current node a construct path message from a neighboring previous node, the construct path message including first and second values for first and second additive parameters;

checking whether the first value satisfies an optimality condition and whether the second value indicates a feasible path given a path constraint; and

if the first value satisfies an optimality condition and the second value indicates a feasible path given a path constraint, then (i) sending out a construct path message to a next neighboring node, (ii) incrementing a number-of-acknowledgement-messages variable by the number of construct path messages sent, and (iii) adding an entry to a predecessor array stored at the current node, the entry including an identifier for the predecessor neighboring node, the first path value, and the second path value.

14. The routing method of claim 13 , wherein checking whether the first value satisfies an optimality condition and whether the second value indicates a feasible path given a path constraint comprises: if the first value satisfies an optimality condition and the second value indicates a feasible path given a path constraint, then testing whether each outgoing link satisfies a link constraint; if an outgoing link to a next neighboring node satisfies the link constraint, then (i) sending out a construct path message to a next neighboring node, (ii) incrementing a number-of-acknowledgement-messages variable by the number of construct path messages sent, and (iii) adding an entry to a predecessor array stored at the current node, the entry including an identifier for the predecessor neighboring node, the first path value, and the second path value; else sending an acknowledgement message to the neighboring previous node.

15. The routing method of claim 13 , wherein the method further comprises:

storing a current node value corresponding to the first additive parameter; and wherein checking whether the first value satisfies an optimality condition comprises:

determining whether the first value of the first additive parameter plus a measure of a link value for the first additive parameter is less than the stored current node value corresponding to the first parameter; and

if the first value of the first additive parameter plus a measure of a link value for the first additive parameter is less than the stored current node value corresponding to the first parameter, setting the stored current node value equal to the first value of the first additive parameter plus a measure of a link value for the first additive parameter.

16. The routing method of claim 13 , further comprising:

prior to receiving at a current node a construct path message, receiving at a source node a path request from an application for a path from the source node to a destination node;

checking whether a feasible path exists given a path constraint;

if a feasible path exists, then testing whether each outgoing link satisfies a link constraint;

if an outgoing link to a next neighboring node satisfies the link constraint, then sending out a construct path message to the next neighboring node;

else sending a no feasible path message to the application;

else sending a no feasible path message to the application; and

incrementing the variable for the number of acknowledge messages that need to be received by the number of construct path messages sent.

17. The routing method of claim 16 , wherein the method further comprises:

prior to receiving at a current node a construct path message, initializing first and second stored values associated with first and second additive parameters and stored at each node.

18. The routing method of claim 16 , wherein the method further comprises:

receiving at a node an acknowledgement message;

decrementing the number-of-acknowledgement-messages variable by one;

determining whether the node's number-of-acknowledgement-messages variable is equal to zero; and

if the node's number-of-acknowledgement-messages variable is equal to zero, then determining if the node is the source node;

if the node is the source node, then sending out terminate messages to neighboring nodes;

else sending out an acknowledgement message to the most recent predecessor node as listed in the predecessor array.

19. The routing method of claim 18 , wherein the method further comprises:

receiving at a node a terminate message; and

determining if the node is the destination node;

if the node is the destination node, then sending a back track message to the predecessor node as listed in the predecessor array;

else sending out terminate messages to neighboring nodes.

20. The routing method of claim 19 , wherein the method further comprises:

receiving a back track message at a node;

determining if the receiving node is the source node;

if the receiving node is the source node, then sending path_found message to the application;

else (i) determining a predecessor node from the predecessor array, (ii) sending a back track message to the predecessor node, and (iii) creating a permanent entry for the application in a routing database for the node.

21. The routing method of claim 20 , wherein determining a predecessor node from the predecessor array comprises:

receiving first predecessor identification data from a neighboring node;

searching the predecessor array for a first entry corresponding to the first predecessor identification data; and

forwarding second predecessor identification data to the predecessor node associated with the first entry.