Flow Path Discovery In Network To Guarantee Multiple Metric QoS Constraints

• US 20100278069A1
• Filed: 10/31/2008
• Published: 11/04/2010
• Est. Priority Date: 06/05/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Mondal, Amit, Banerjee, Sujata, Sharma, Puneet
• Granted Patent: US 8,565,218 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

Route discovery for an end-to-end path in a network is performed for a flow. A path is attempted to be discovered that satisfies QoS constraints for multiple metrics for the flow. The route discovery includes determining whether a path request for a path satisfying the QoS constraints is feasible, infeasible or undecideable based on information in a local QoS table. If the path request is determined to be undecideable, route discovery is performed with neighbors.

Claims

1. A method of route discovery for an end-to-end path in a network for a flow, wherein a path is attempted to be discovered that satisfies QoS constraints for multiple metrics for the flow, the method comprising:

receiving a path request for the flow, wherein the path request identifies the QoS constraints for the flow;

determining whether the path request is infeasible or undecideable;

if the path request is determined to be undecideable, sending route discovery messages only to neighbors that previously sent an advertisement for a destination for the flow.

2. The method of claim 1, wherein if a determination is made that the feasible path exists based on the information in the local QoS table, sending a flow set up request to overlay nodes in the feasible path.

3. The method of claim 2, wherein a path is determined to be feasible if the path satisfies all the QoS constraints.

4. The method of claim 1, wherein if a determination is made that the path request is infeasible, sending a message indicating the path request is rejected.

5. The method of claim 4, wherein the path request is infeasible if one or more of the QoS constraints cannot be satisfied for any paths to the destination for the flow that are identified by the overlay node.

6. The method of claim 1, wherein the path request is undecideable if a determination is made that a feasible path does not exist based on information from the local QoS table and a determination is made that the path request is not infeasible.

7. The method of claim 6, wherein the path request is undecideable if the QoS constraints for the path request fall in an undecideable region on a graph of the metrics for the QoS constraints, the undecideable region being an area in the graph outside of areas for any feasible paths and an area for an infeasible region.

8. The method of claim 1, wherein sending route discovery messages only to neighbors that previously sent an advertisement for a destination for the flow further comprises:

sending route discovery messages from the overlay node only to first immediate downstream neighbors that previously sent advertisements for the destination, wherein the route discovery messages are requests for metrics for any paths not includes in the previous advertisements; and

repeating the step of sending route discovery message for further downstream neighbors to the destination until a feasible path is found or until a feasible path cannot be found.

9. The method of claim 1, further comprising:

receiving advertisements from upstream neighbors, each advertisement including the metrics for paths to the destination from the neighbor;

determining measurements of the metrics for links between the upstream neighbors and the overlay node;

aggregating the advertisements and the measurements;

determining best paths for each QoS metric from the aggregation; and

populating the local QoS table with the best paths for each QoS constraint, and the best paths are a subset of all known paths in the overlay network to the destination from the overlay node.

10. The method of claim 1, further comprising:

after a feasible path is created for the flow that satisfies the QoS constraints, monitoring links in the overlay path to determine whether any of the QoS constraints are violated.

11. The method of claim 10, further comprising:

if any of the QoS constraints are violated for a link, determining from the local QoS table whether an alternative path from the overlay node to the destination exists that satisfies the QoS constraints; and

if the alternative path exists, sending a flow set up request to any new overlay nodes for the alternative path to provide a new path to the destination.

12. The method of claim 11, if a determination is made that the alternative path does not exist based on the local QoS table, sending a message to an immediate upstream overlay node in the current path requesting discovery of an alternative path from the immediate upstream overlay node to the destination that satisfies the QoS constraints.

13. The method of claim 12, further comprising:

repeating the step of sending a message requesting discovery of an alternative path satisfying the QoS constraints for further upstream nodes until an alternative path to the destination is found that satisfies the QoS constraints or until an alternative path cannot be found.

14. A node in a network configured to route flows, the node comprising:

a flow engine configured to identify feasible paths to destinations for flows;

a QoS table, wherein the flow engine is configured to determine whether an overlay path that satisfies QoS constraints for multiple metrics for a flow is feasible based on information in the QoS table for the destination, and the information only includes information for a best path for each QoS constraint to a destination of the path; and

a router receiving flow set up information from the flow engine for a feasible path for the flow, the flow set up information including a flow ID and a next hop in the path from the node, wherein the router is configured to receive information from the flow and forward the information to the next hop.

16. The node of claim 14, wherein after the path is established, the flow engine is configured to attempt to identify an alternative path from the QoS table that satisfies the QoS constraints if a downstream link from the overlay node fails to satisfy any of the QoS constraints.

17. The node of claim 16, the flow engine is configured to request an immediate upstream neighbor to identify an alternative path if the flow engine is unable to identify an alternative path from the QoS table that satisfies the QoS constraints.

18. The node of claim 14, wherein the flow engine is configured to aggregate advertisements for reachable destinations with local link metrics, and populate the QoS table with only metrics for best paths to the reachable destinations.

19. The node of claim 18, wherein the flow engine is configured to send advertisements to neighbors only for the best paths to the reachable destinations.

15. The node of claim 15, wherein the node is an overlay node in an overlay network and the flow engine is configured to perform on-demand route discovery with its neighbors that previously sent advertisements for the destination, if the flow engine is unable to identify a feasible path from the information in the QoS table and the flow engine determines that a path request for the flow is undecideable.

20. A computer readable storage medium storing software including instructions that when executed perform a method of route discovery for an end-to-end path in a network for a flow, wherein a path is attempted to be discovered that satisfies QoS constraints for multiple metrics for the flow, the method comprising:

receiving a path request for the flow, wherein the path request identifies the QoS constraints for the flow;

determining whether the path request is infeasible or undecideable;

if the path request is determined to be undecideable, sending route discovery messages only to neighbors that previously sent an advertisement for a destination for the flow.