Efficiently decoupling reservation and data forwarding of data flows in a computer network
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
- one or more network interfaces;
-
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. - View Dependent Claims (15)
- selecting a reserved path for a data flow that pass data from a source node to a destination node;
-
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. - View Dependent Claims (17, 18, 19, 20)
- requesting a reserved path for passing data of a data flow from a source node to a destination node;
-
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. - View Dependent Claims (22, 23, 24, 25)
- one or more network interfaces;
Specification