Network path selection using bandwidth prediction

• US 10,091,107 B2
• Filed: 05/25/2017
• Issued: 10/02/2018
• Est. Priority Date: 04/10/2014
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Sella, William Thomas
• Primary Examiner(s): Chery, Dady
• Application Number:
  US15/605,468
• Publication Number:
  US 20170339057A1
• Time in Patent Office: 495 Days
• Field of Search: 370216, 370217, 370218, 370225, 370228, 370235, 370237, 370229, 370230
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/56 Routing software
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/645 Splitting route computation layer and forwarding layer, e.g. routing according to path computational element [PCE] or based on OpenFlow functionality
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

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.

Claims

1. A computer-implemented method for routing a 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 for the data stream from the source to the destination through the plurality of forwarding devices, the data stream having a type;

(b) determining the path based on historical usage characteristics of data streams having the type, the historical usage characteristics including an amount of bandwidth utilized by previously transmitted data streams of the type and a length of previously transmitted data streams of the type;

(c) for respective forwarding devices along the path, determining a routing table indicating which port of the respective forwarding device to route data from the new data stream along the path determined in (b); and

(d) for each of the respective forwarding devices, transmitting the routing table determined in (c) to configure the forwarding device.

2. The computer-implemented method of claim 1, further comprising:

(e) determining the type of the data stream based on at least one of a source Internet protocol (IP) address, a destination IP address, a source transport control protocol (TCP) port, a destination TCP port, a source universal datagram protocol (UDP) port, and destination UDP port.

3. The computer-implemented method of claim 1, wherein the determining (b) is further based on at least one of historical link utilization information for the links and respective capacities of the links.

4. The computer-implemented method of claim 3, wherein the determining (b) is further based on the historical link utilization information, and the historical link utilization information for the links includes an average of link utilization and a variance of link utilization over a predetermined period of time.

5. The computer-implemented method of claim 1, wherein the determining (b) is further based on at least one of a latency requirement, a jitter requirement, a packet loss requirement, and a user'"'"'s service level agreement.

6. The computer-implemented method of claim 1, further comprising:

(e) before the receiving (a), determining the historical usage characteristics of data streams having the type by statistically sampling previously transmitted data streams having the type.

7. The computer-implemented method of claim 1, wherein the data stream is identified with a label, and wherein the routing table determined in (c) indicates how to forward packets having the label.

8. The computer-implemented method of claim 1, wherein the path includes a server that performs scrubbing operations on packets of the data stream.

9. The computer-implemented method of claim 8, wherein the scrubbing operations include scanning the data stream for malicious content.

10. The computer-implemented method of claim 1, wherein the determining (b) includes retrieving a predetermined path for the data stream from a path database, wherein the predetermined path is determined prior to receiving the request based on the historical usage characteristics of data streams having the type.

11. A system for routing a data stream from a source to a destination through a network including a plurality of forwarding devices interconnected with links, comprising:

a control device configured to receive a request to create a path for the data stream from the source to the destination through the plurality of forwarding devices, the data stream having a type;

a path computation module configured to determine the path based on historical usage characteristics of data streams having the type, the historical usage characteristics including an amount of bandwidth utilized by previously transmitted data streams of the type and a length of previously transmitted data streams of the type; and

a routing table module configured to (i) for respective forwarding devices along the path, determine a routing table indicating which port of the respective forwarding device to route data from the new data stream along the path, and (ii) for each of the respective forwarding devices, transmit the determined routing table to configure the forwarding device.

12. The system of claim 11, wherein the control device is further configured to determine the type of the data stream based on at least one of a source interact protocol (IP) address, a destination IP address, a source transport control protocol (TCP) port, a destination TCP port, a source universal datagram protocol (UDP) port, and destination UDP port.

13. The system of claim 11, wherein determining the path is further based on at least one of historical link utilization information for the links and respective capacities of the links.

14. The system of claim 13, wherein the determining the path is based on the historical link utilization information, and the historical link utilization information for the links includes an average of link utilization and a variance of link utilization over a predetermined period of time.

15. The system of claim 11, wherein the determining of the path is further based on at least one of a latency requirement, a jitter requirement, a packet loss requirement, and a user'"'"'s service level agreement.

16. The system of claim 11, further comprising:

a historical utilization module configured to determine the historical usage characteristics of data streams having the type by statistically sampling previously transmitted data streams having the type.

17. The system of claim 11, wherein the data stream is identified with a label, and wherein the routing table indicates how to forward packets having the label.

18. A non-transitory program storage device tangibly embodying a program of instructions executable by at least one machine to perform a method for routing a 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 for the data stream from the source to the destination through the plurality of forwarding devices, the data stream having a type;

(b) determining the path based on historical usage characteristics of data streams having the type, the historical usage characteristics including an amount of bandwidth utilized by previously transmitted data streams of the type and a length of previously transmitted data streams of the type;

(c) for respective forwarding devices along the path, determining a routing table indicating which port of the respective forwarding device to route data from the new data stream along the path determined in (b); and

(d) for each of the respective forwarding devices, transmitting the routing table determined in (c) to configure the forwarding device.

19. The non-transitory program storage device of claim 18, the method further comprising:

(e) determining the type of the data stream based on at least one of a source Internet protocol (IP) address, a destination IP address, a source transport control protocol (TCP) port, a destination TCP port, a source universal datagram protocol (UDP) port, and destination UDP port.

20. The non-transitory program storage device of claim 18, wherein the determining (b) is further based on at least one of historical link utilization information for the links and respective capacities of the links.