Scheduled network layer programming within a multi-topology computer network

• US 9,438,508 B1
• Filed: 08/29/2014
• Issued: 09/06/2016
• Est. Priority Date: 12/29/2011
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Medved, Jan, Ward, David
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Rivas, Raul
• Application Number:
  US14/473,766
• Time in Patent Office: 739 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

In general, techniques are described for dynamically scheduling and establishing paths in a multi-layer, multi-topology network to provide dynamic network resource allocation and support packet flow steering along paths prescribed at any layer or combination of layers of the network. In one example, a multi-topology path computation element (PCE) accepts requests from client applications for dedicated paths. The PCE receives topology information from network devices and attempts to identify paths through a layer or combination of layers of the network that can be established at the requested time in view of the specifications requested for the dedicated paths and the anticipated bandwidth/capacity available in the network. The PCE schedules the identified paths through the one or more layers of the network to carry traffic for the requested paths. At the scheduled times, the PCE programs path forwarding information into network nodes to establish the scheduled paths.

Claims

1. A method comprising:

receiving, by a path computation element, topology information for a base network layer of a multi-topology network, the multi-topology network comprising the base network layer having a plurality of network switches interconnected by base network layer three (L3) links in a base network topology and also comprising an overlay network layer having a plurality of overlay switches interconnected by overlay network links in an overlay network topology;

receiving, by the path computation element from a client and via a client interface, a path request that specifies two endpoints, a start time for path activation, and a requested bandwidth;

computing, by the path computation element in response to receiving the path request and using the topology information for the base network layer and the topology information for the overlay network layer, a path to transport network traffic between the two endpoints;

by the path computation element and after computing the path to transport network traffic between the two endpoints, receiving additional topology information for one of the overlay network layer and the base network layer; and

sending, by the path computation element to the client via the client interface and in response to determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth at the start time for path activation, a path rejection indicating the multi-topology network is unable to satisfy the path request.

2. The method of claim 1, further comprising:

by the path computation element in response to determining the additional topology information indicates the path is capable of transporting network traffic between the two endpoints at the requested bandwidth at the start time for path activation, installing forwarding information for the path to a network switch of the plurality of network switches and to an overlay switch of the plurality of overlay switches.

3. The method of claim 2, further comprising:

scheduling the path as a scheduled path for the start time,

wherein installing the forwarding information comprises installing, by the path computation element, forwarding information for the scheduled path to the network switch and the overlay switch at the start time.

4. The method of claim 3, further comprising:

storing the scheduled path to a generated path database of the path computation element; and

marking the scheduled path in the generated path database as active upon installing the forwarding information.

5. The method of claim 1, wherein the path request specifies an end time, the method further comprising:

scheduling the path as a scheduled path for the start time and storing the scheduled path to a generated path database; and

storing other scheduled paths computed by the path computation element to the generated path database, wherein each of the other scheduled paths has an associated start time, end time, and bandwidth requirement,

wherein determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth comprises determining, by the path computation element, whether a path satisfying the bandwidth requirement exists in the multi-topology network for the interval between the start time for path activation and the end time based at least on the associated start times, end times, and bandwidth requirements of the other scheduled paths.

6. The method of claim 5,

storing, by the path computation element, policies specifying relative priorities for clients of the path computation element,

wherein determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth comprises determining at least one path of the other scheduled paths is associated with a higher-priority client of the clients that has a higher priority than the client according to the policies.

7. The method of claim 1, wherein determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth comprises:

upon determining multi-topology network resources along the path required to satisfy the requested bandwidth are not available for reservation, attempting to recompute, by the path computation element using the topology information for the base network layer and the topology information for the overlay network layer, a new path to transport network traffic between the two endpoints.

8. The method of claim 1,

wherein the path request specifies an end time,

wherein determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth comprises determining, by the path computation element, the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth for the entire interval between the start time for path activation and the end time.

9. The method of claim 1, wherein receiving additional topology information for one of the overlay network layer and the base network layer comprises receiving, by the path computation element, the additional topology information from a network switch of the plurality of network switches via a path computation element protocol (PCEP) session with the network switch.

10. A path computation element comprising:

a multi-topology traffic engineering database to store topology information for a base network layer of a multi-topology network, the multi-topology network comprising the base network layer having a plurality of network switches interconnected by base network layer three (L3) links in a base network topology and also comprising an overlay network layer having a plurality of overlay switches interconnected by overlay network links in an overlay network topology;

a topology server interface configured to receive topology information for the base network layer;

an overlay controller interface configured to receive topology information for the overlay network layer;

a client interface configured to receive a path request that specifies two endpoints, a start time for path activation, and a requested bandwidth;

a service path engine configured to compute, in response to receiving the path request and using the topology information for the base network layer and the topology information for the overlay network layer, a path to transport network traffic between the two endpoints,

wherein the topology server interface and the overlay controller interface are further configured to, after the service path engine computes the path to transport network traffic between the two endpoints, receive additional topology information for one of the overlay network layer and the base network layer, and

wherein the client interface is further configured to send, to the client in response to the service path engine determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth at the start time for path activation, a path rejection indicating the multi-topology network is unable to satisfy the path request.

11. The path computation element of claim 10, wherein the topology server interface and the overlay controller interface are further configured to, in response to the service path engine determining the additional topology information indicates the path is capable of transporting network traffic between the two endpoints at the requested bandwidth at the start time for path activation, install forwarding information for the path to a network switch of the plurality of network switches and to an overlay switch of the plurality of overlay switches.

12. The path computation element of claim 11,

wherein the service path engine is further configured to schedule the path as a scheduled path for the start time, and

wherein to install the forwarding information the topology server interface and the overlay controller interface are further configured to install forwarding information for the scheduled path to the network switch and the overlay switch at the start time.

13. The path computation element of claim 12, further comprising:

generated path database configured to store the scheduled path and mark the scheduled path as active upon installation of the forwarding information.

14. The path computation element of claim 10, further comprising:

a generated path database configured to store other scheduled paths computed by the path computation element, wherein each of the other scheduled paths has an associated start time, end time, and bandwidth requirement,

wherein the path request specifies an end time,

wherein the service path engine is further configured to schedule the path as a scheduled path for the start time and store the scheduled path to the generated path database, and

wherein to determine the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth the service path engine is further configured to determine whether a path satisfying the bandwidth requirement exists in the multi-topology network for the interval between the start time for path activation and the end time based at least on the associated start times, end times, and bandwidth requirements of the other scheduled paths.

15. The path computation element of claim 14, further comprising:

policies specifying relative priorities for clients of the path computation element,

wherein to determine the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth the service path engine is further configured to determine at least one path of the other scheduled paths is associated with a higher-priority client of the clients that has a higher priority than the client according to the policies.

16. The path computation element of claim 10, wherein to determine the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth the service path engine is further configured to, upon determining multi-topology network resources along the path required to satisfy the requested bandwidth are not available for reservation, attempt to recomputed, using the topology information for the base network layer and the topology information for the overlay network layer, a new path to transport network traffic between the two endpoints.

17. The path computation element of claim 10,

wherein the path request specifies a start time an end time,

wherein to determine the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth the service path engine is further configured to determine the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth for the entire interval between the start time for path activation and the end time.

18. A non-transitory computer-readable medium comprising instructions for causing one or more programmable processors to:

receive, by a path computation element, topology information for a base network layer of a multi-topology network, the multi-topology network comprising the base network layer having a plurality of network switches interconnected by base network layer three (L3) links in a base network topology and also comprising an overlay network layer having a plurality of overlay switches interconnected by overlay network links in an overlay network topology;

receive, by the path computation element from a client and via a client interface, a path request that specifies two endpoints, a start time for path activation, and a requested bandwidth;

compute, by the path computation element in response to receiving the path request and using the topology information for the base network layer and the topology information for the overlay network layer, a path to transport network traffic between the two endpoints;

by the path computation element and after computing the path to transport network traffic between the two endpoints, receive additional topology information for one of the overlay network layer and the base network layer; and

send, by the path computation element to the client via the client interface and in response to determining the additional topology information indicates the path is not capable of transporting network traffic between the two endpoints at the requested bandwidth at the start time for path activation, a path rejection indicating the multi-topology network is unable to satisfy the path request.