Flow path discovery in network to guarantee multiple metric QoS constraints

• US 8,565,218 B2
• Filed: 10/31/2008
• Issued: 10/22/2013
• 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: Sharma, Puneet, Mondal, Amit, Banerjee, Sujata
• Primary Examiner(s): Banks Harold, Marsha D
• Assistant Examiner(s): WYLLIE, CHRISTOPHER T
• Application Number:
  US12/263,429
• Publication Number:
  US 20100278069A1
• Time in Patent Office: 1,817 Days
• Field of Search: None
• US Class Current: 370/351
• 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 computer implemented 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, by a computer system coupled to the network, a path request for the flow, wherein the path request identifies the QoS constraints for the flow;

determining, by a processor in the computer system, whether the path request is infeasible or undecideable, wherein the path request is undecideable if a determination is made that a feasible path does not exist based on information from a local QoS table and a determination is made that the path request is not infeasible, and if the QoS constraints for the path request fall in an undecideable region of metrics for the QoS constraints, the undecideable region being an area outside of areas for any feasible paths and an area for an infeasible region;

determining if the path request is infeasible and if determined to be infeasible denying the path request; and

determining if the path request is undecideable and if determined to be undecideable sending route discovery messages only to neighbors that previously sent an advertisement for a destination for the flow to determine whether to admit or reject the path request, wherein to determine whether to admit or reject the path request includes aggregating advertisements for the destination with local link metrics to determine best paths to the destination until a path is found that satisfies the QoS constraints or a determination is made that a path does not exist that satisfies the QoS constraints.

2. The method of claim 1, wherein if a determination is made that a feasible path exists based on 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 determining if the path request is infeasible and if determined to be infeasible denying the path request further comprises, sending a message indicating the path request is denied.

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 an overlay node.

6. 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 an 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 included in the previous advertisements; and

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

7. The method of claim 1, wherein aggregating advertisements for the destination with local link metrics to determine best paths to the destination further comprises:

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

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

aggregating the advertisements and the measurements;

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

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

8. The method of claim 1, further comprising:

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

9. The method of claim 8, further comprising:

if any of the QoS constraints are violated for a link, determining from the local QoS table whether an alternative path from an 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.

10. The method of claim 9, 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.

11. The method of claim 10, 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.

12. 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 a destination, and the information only includes information for a best path for each QoS constraint to a destination of the path, wherein the flow engine is configured to determine if the overlay path is feasible by determining if the QoS constraints for the overlay path fall in a feasible region of metrics for the QoS constraints, the feasible region being an area that does not include areas for undecideable or infeasible regions, and wherein the flow engine is configured to aggregate advertisements for reachable destinations with local link metrics and populate the QoS table with metrics for best paths to the reachable destinations; 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.

13. The node of claim 12, 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.

14. The node of claim 12, 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.

15. The node of claim 14, 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.

16. The node of claim 12, 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.

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

18. A non-transitory computer readable storage medium storing software including instructions that 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:

receive, by a computer system coupled to the network, a path request for the flow, wherein the path request identifies the QoS constraints for the flow;

determine, by a processor in the computer system, whether the path request is infeasible or undecideable, wherein the path request is undecideable if a determination is made that a feasible path does not exist based on information from a local QoS table and a determination is made that the path request is not infeasible, and if the QoS constraints for the path request fall in an undecideable region of metrics for the QoS constraints, the undecideable region being an area outside of areas for any feasible paths and an area for an infeasible region;

determine if the path request is infeasible and if the path request is determined to be infeasible the path request is denied; and

determine if the path request is undecideable and if the path request is determined to be undecideable send route discovery messages only to neighbors that previously sent an advertisement for a destination for the flow to determine whether to admit or reject the path request, wherein determine whether to admit or reject the path request includes aggregated advertisements for the destination with local link metrics to determine best paths to the destination until a path is found that satisfies the QoS constraints or a determination is made that a path does not exist that satisfies the QoS constraints.

19. A computer implemented 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 infeasible the path request is denied; and

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 to determine whether to admit or reject the path request, wherein the path request is undecideable if a determination is made that a feasible path does not exist based on information from a local QoS table and a determination is made that the path request is not infeasible, and further 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.