Efficiently decoupling reservation and data forwarding of data flows in a computer network

• US 8,976,672 B2
• Filed: 10/03/2006
• Issued: 03/10/2015
• Est. Priority Date: 10/03/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Levy-Abegnoli, Eric, Le Faucheur, Francois, Thubert, Pascal
• Primary Examiner(s): Vu, Huy D
• Assistant Examiner(s): Baig, Adnan
• Application Number:
  US11/542,186
• Publication Number:
  US 20080080473A1
• Time in Patent Office: 3,080 Days
• Field of Search: 370/348, 370229-238
• US Class Current: 370/238
• CPC Class Codes: G06F 13/4045 where the bus bridge performs an extender function

Abstract

In one embodiment, a node (e.g., a router) performs reservations for data flows, each on a corresponding selected (reserved) path having adequate reservation availability. Also, the node forwards data from data flows, each over a corresponding selected (forwarded) path having adequate load availability, wherein forwarded paths are decoupled from reserved paths for the data flows.

Claims

1. A node for efficiently decoupling reservation and data forwarding of data flows in a computer network, the node comprising:

one or more network interfaces;

a processor coupled to the one or more network interfaces and adapted to execute software processes;

a memory adapted to store a reservation process executable by the processor, the reservation process configured to select a reserved path for a data flow that passes data from a source node to a destination node, and place a reservation for the data flow on the selected reserved path, the selected reserved path for the data flow to have adequate reservation availability for the data flow; and

the memory further adapted to store a forwarding process executable by the processor, the forwarding process configured to select, based on a directed acyclic graph adapted for determining acyclic paths available to reach the destination node, a forwarded path other than the selected reserved path for the data flow for transferring data from the source node to the destination node, forward data for the data flow over the selected forwarded path while maintaining the reservation for the data flow upon the selected reserved path, determine whether a load availability for the selected forwarded path is above a threshold, and if so, increase a first proportion of data flows forwarded over the selected forwarded path and decrease a second proportion of data flows transmitted over the selected reserved path, the selected forwarded path being a non-shortest path between the source node and the destination node and having adequate load availability for the data flow, wherein selection of the selected forwarded path is decoupled from the selected reserved path for the data flow such that the selected forwarded path is selected independently from the selected reserved path.

2. The node as in claim 1, wherein the selected forwarded path for the data flow is not the selected reserved path for the data flow.

3. The node as in claim 1, wherein the selected forwarded path for the data flow is the selected reserved path for the data flow.

4. The node as in claim 1, wherein the selected forwarded path for the data flow is shorter than or equal to the selected reserved path for the data flow.

5. The node as in claim 1, wherein the reservation process is further configured to:

determine a reservation availability of paths to the destination node of the data flow through use of a Shortest Path First Then Other Path (SPF TOP) mechanism.

6. The node as in claim 1, wherein the forwarding process is further configured to:

determine load availability of paths and determine the selected forwarded path through use of a Shortest Path First Then Other Path (SPF TOP) mechanism.

7. The node as in claim 1, wherein the forwarding process is further configured to:

forward data flow data based on hash-based forwarding rules.

8. The node as in claim 1, wherein the selected forwarded path for the data flow is a best path having adequate load availability based on one or more metrics.

9. The node as in claim 1, wherein the selected reserved path for the data flow is a best path having adequate reservation availability based on one or more metrics.

10. The node as in claim 1, wherein the forwarding process is further configured to:

determine whether the load availability for the selected forwarded path is below a threshold; and

if so, decrease a first proportion of data flows forwarded over the selected forwarded path and decrease a second proportion of data flows transmitted over the selected reserved path.

11. The node as in claim 1, wherein the reservation process is further configured to:

inform one or more intermediate nodes of the selected reserved path for the data flow.

12. The node as in claim 1, wherein the node is an intermediate node of the reservation.

13. The node as in claim 1, wherein the forwarding process is further configured to:

utilize multi-topology routing (MTR) to distinguish between data flow data on the selected reserved path and data flow data not on the selected reserved path.

14. A method comprising:

selecting a reserved path for a data flow that pass data from a source node to a destination node;

placing a reservation for the data flow on a selected reserved path, the selected reserved path for the data flow being a path that has adequate reservation availability for the data flow;

selecting, based on a directed acyclic graph adapted for determining acyclic paths available to reach the destination node, a forwarded path for the data flow for transferring data from the source node to the destination node, wherein the forwarded path is a non-shortest path between the source node and the destination node;

forwarding data for the data flow over the selected forwarded path while maintaining the reservation for the data flow upon the selected reserved path;

the selected forwarded path for the data flow being a path that has adequate load availability for the data flow, wherein selection of the selected forwarded path is decoupled from selection of the selected reserved path for the data flow such that the selected forwarded path is selected independently from the selected reserved path;

determining whether a load availability for the selected forwarded path is above a threshold; and

if so, increasing a first proportion of data flows forwarded over the selected forwarded path and decreasing a second proportion of data flows transmitted over the selected reserved path.

15. The method as in claim 14, wherein the selected forwarded path for the data flow is not the selected reserved path for the data flow.

16. A method comprising:

requesting a reserved path for passing data of a data flow from a source node to a destination node;

placing a reservation for the data flow to create the reserved path along a reservable path of a plurality of paths from the source node to the destination node that has reservation availability sufficient to accommodate the data flow, the reservable path being a path other than a shortest path between the source node and the destination node;

subsequent to the reserving, determining a current load availability on the plurality of paths from the source node to the destination node, the plurality of paths including the shortest path between the source node and the destination node;

selecting, based on a directed acyclic graph adapted for determining acyclic paths available to reach the destination node, one or more forwarded paths from the source node to the destination node from among the plurality of paths from the source node to the destination node based on the current load availability;

the selected one or more forwarded paths being selected independently from the reserved path so that at least one of the one or more forwarded paths is not the reserved path, at least one of the one or more forwarded paths being the shortest path between the source node and the destination node;

forwarding data of the data flow from the source node to the destination node over the selected one or more forwarded paths, while maintaining the reservation for the data flow upon the reserved path, wherein the reserved path is still operational when the forwarding occurs;

determining whether a load availability for the selected forwarded path is above a threshold; and

if so, increasing a first proportion of data flows forwarded over the selected forwarded path and decreasing a second proportion of data flows transmitted over the selected reserved path.

17. The method of claim 16, wherein the reservation availability sufficient to accommodate the data flow is reservable bandwidth sufficient to accommodate a bandwidth of the data flow, and wherein the current load availability is a current unutilized bandwidth.

18. The method of claim 16, wherein the one or more forwarded paths are a plurality of forwarded paths, and the forwarding forwards a portion of data of the data flow over each path of the selected plurality of forwarded paths.

19. The method of claim 18, wherein the forwarding attempts to place data of the data flow on a best available path of the plurality of forwarded paths as determined by one or more link or path metrics, while remaining data that is not placed on the best available path of the plurality of forwarded paths is placed on one or more next-best paths as determined by the one or more link or path metrics.

20. The method of claim 16, wherein the requesting further comprises:

sending one or more Resource ReSerVation Protocol (RSVP) messages.

21. An apparatus comprising:

one or more network interfaces;

a processor coupled to the one or more network interfaces and configured to execute software processes; and

a memory configured to store a process executable by the processor, the process operable to request a reserved path for passing data of a data flow from a source node to a destination node, cause a reservation to be placed to create the reserved path along a reservable path of a plurality of paths from the source node to the destination node that has reservation availability sufficient to accommodate the data flow, the reservable path being a path other than a shortest path from the source node to the destination node, determine a current load availability on the plurality of paths from the source node to the destination node, the plurality of paths including the shortest path from the source node to the destination node, select, based on a directed acyclic graph adapted for determining acyclic paths available to reach the destination node, one or more forwarded paths other than the reserved path from the source node to the destination node from among the plurality of paths from the source node to the destination node based on the current load availability, the selected one or more forwarded paths being selected independently from the reserved path so that at least one of the one or more forwarded paths is not the reserved path and at least one of the one or more forwarded paths is the shortest path between the source node and the destination node, and forward data of the data flow from the source node to the destination node over the selected one or more forwarded paths, while the reservation for the data flow is maintained upon the reserved path and the reserved path is still operational, determine whether the load availability for the selected forwarded path is above a threshold; and

if so, increase a first proportion of data flows forwarded over the selected forwarded path and decrease a second proportion of data flows transmitted over the selected reserved path.

22. The apparatus of claim 21, wherein the reservation availability sufficient to accommodate the data flow is reservable bandwidth sufficient to accommodate a bandwidth of the data flow, and wherein the current load availability is a current unutilized bandwidth.

23. The apparatus of claim 21, wherein the one or more forwarded paths are a plurality of forwarded paths, and the process is further operable to forward a portion of data of the data flow over each path of the selected plurality of forwarded paths.

24. The apparatus of claim 21, wherein the process is further operable to attempt to place data of the data flow on a best available path of the plurality of forwarded paths as determined by one or more link or path metrics, and place remaining data that can not be placed on the best available path of the plurality of forwarded paths on one or more next-best paths as determined by the one or more link or path metrics.

25. The apparatus of claim 21, wherein the reservation process is a Resource ReSerVation Protocol (RSVP) process.