Network path selection using bandwidth prediction
First Claim
1. A computer-implemented method for routing a new data stream from a source to a destination through a network including a plurality of forwarding devices interconnected with links, comprising:
- (a) receiving, at a control device, a request to create a path through the plurality of interconnected forwarding devices for a new data stream;
(b) determining a type of the new data stream;
(c) determining, based on the determined type, historical usage characteristics of data streams having the determined type, the characteristics including a length of data streams previously transmitted of the type and an amount of bandwidth utilized by data streams previously transmitted of the type;
(d) determining which time slices the new data stream will occupy based on the length of data streams previously transmitted of the type, previous time slices during a plurality of previous time cycles, the time cycles representing periodic time intervals having a pattern of repeated utilization, the time slices representing sub-intervals in the periodic time intervals,(e) for each of a plurality of candidate paths connecting the source and destination, determining a historical utilization of links along the candidate path for the time slices determined in (d);
(f) also for each of the plurality of candidate paths, determining, based on the determined utilization of the links along the candidate path, an amount of available bandwidth on the path during the time slices determined in (d);
(g) comparing the determined amount of available bandwidth for the plurality of candidate paths with the determined amount of bandwidth utilized by data streams previously transmitted of the type to select the path requested for the new data stream, the requested path through the plurality of interconnected forwarding devices from the source to the destination;
(h) for respective forwarding devices along the path, determining a routing table indicating which port of the forwarding device to route data from the new data stream along the path determined in (g); and
(i) for each of the respective forwarding devices, transmitting the routing table determined in (h) to configure the forwarding device.
2 Assignments
0 Petitions
Accused Products
Abstract
In an embodiment, a system routes a new data stream from a source to a destination through a plurality of forwarding devices interconnected with links. The system includes a control device that receives a request to create a path through the plurality of interconnected forwarding devices for a new data stream and determines a type of the new data stream. A data flow database stores historical usage characteristics of data streams having the determined type. A path computation module determines, based on the historical usage characteristics of data streams having the determined type, the requested path through plurality of interconnected forwarding devices from the source to the destination.
33 Citations
11 Claims
-
1. A computer-implemented method for routing a new data stream from a source to a destination through a network including a plurality of forwarding devices interconnected with links, comprising:
-
(a) receiving, at a control device, a request to create a path through the plurality of interconnected forwarding devices for a new data stream; (b) determining a type of the new data stream; (c) determining, based on the determined type, historical usage characteristics of data streams having the determined type, the characteristics including a length of data streams previously transmitted of the type and an amount of bandwidth utilized by data streams previously transmitted of the type; (d) determining which time slices the new data stream will occupy based on the length of data streams previously transmitted of the type, previous time slices during a plurality of previous time cycles, the time cycles representing periodic time intervals having a pattern of repeated utilization, the time slices representing sub-intervals in the periodic time intervals, (e) for each of a plurality of candidate paths connecting the source and destination, determining a historical utilization of links along the candidate path for the time slices determined in (d); (f) also for each of the plurality of candidate paths, determining, based on the determined utilization of the links along the candidate path, an amount of available bandwidth on the path during the time slices determined in (d); (g) comparing the determined amount of available bandwidth for the plurality of candidate paths with the determined amount of bandwidth utilized by data streams previously transmitted of the type to select the path requested for the new data stream, the requested path through the plurality of interconnected forwarding devices from the source to the destination; (h) for respective forwarding devices along the path, determining a routing table indicating which port of the forwarding device to route data from the new data stream along the path determined in (g); and (i) for each of the respective forwarding devices, transmitting the routing table determined in (h) to configure the forwarding device. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system for virtually routing a new data stream from a source to a destination through a network including a plurality of forwarding devices interconnected with links, comprising:
-
a historical utilization module that collects historical usage data of the network, the historical usage data comprises utilization of the links at a plurality of time slices during a plurality of previous time cycles, the time cycles representing periodic time intervals having a pattern of repeated utilization, the time slices representing sub-intervals in the periodic time intervals; a control device that receives a request to create a path through the plurality of interconnected forwarding devices for a new data stream and determines a type of the new data stream; a data flow database that stores historical usage characteristics of data streams having the determined type, the characteristics including a length of data streams previously transmitted of the type and an amount of bandwidth utilized by data streams previously transmitted of the type; a path computation module that determines, based on the historical usage characteristics of data streams having the determined type, the requested path through plurality of interconnected forwarding devices from the source to the destination, wherein the path computation module; (i) determines which time slices the new data stream will occupy based on the length of data streams of the type previously transmitted, for a plurality of candidate paths connecting the source and destination; (ii) determines a utilization of links along the candidate path for the time slices determined in (i), (iii) determines, based on the determined utilization of the links along the candidate path, an amount of available bandwidth on the path during the time slices determined in (i), and (iv) compares the determined amount of available bandwidth for the plurality of candidate paths with the determined amount of bandwidth utilized by data streams previously transmitted of the type to select the path requested for the new data stream; a routing table module that, for respective forwarding devices along the path;
(i) determines a routing table indicating which port of the forwarding device to route data from the new data stream along the determined path; and
(ii) transmits the determined routing table to configure the forwarding device to route data along the path. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A program storage device tangibly embodying a program of instructions executable by at least one machine to perform a method for virtually routing a new data stream from a source to a destination through a plurality of forwarding devices interconnected with links, the method comprising:
-
(a) receiving, at a control device, a request to create a path through the plurality of interconnected forwarding devices for a new data stream; (b) determining a type of the new data stream; (c) determining, based on the determined type, historical usage characteristics of data streams having the determined type, the characteristics including a length of data streams previously transmitted of the type and an amount of bandwidth utilized by data streams previously transmitted of the type; (d) determining which time slices the new data stream will occupy based on the length of data streams previously transmitted of the type, the time slices during a plurality of previous time cycles, the time cycles representing periodic time intervals having a pattern of repeated utilization, the time slices representing sub-intervals in the periodic time intervals, (e) for each of a plurality of candidate paths connecting the source and destination, determining a historical utilization of links along the candidate path for the time slices determined in (d); (f) also for each of the plurality of candidate paths, determining, based on the determined utilization of the links along the candidate path, an amount of available bandwidth on the path during the time slices determined in (d); (g) comparing the determined amount of available bandwidth for the plurality of candidate paths with the determined amount of bandwidth utilized by data streams previously transmitted of the type to select a path requested for the new data stream, the requested path through the plurality of interconnected forwarding devices from the source to the destination; (h) for respective forwarding devices along the path, determining a routing table indicating which port of the forwarding device to route data from the new data stream along the path determined in (g); and (i) for each of the respective forwarding devices, transmitting the routing table determined in (h) to configure the forwarding device.
-
Specification