Scheduled network layer programming within a multi-topology computer network

• US 9,893,951 B1
• Filed: 09/06/2016
• Issued: 02/13/2018
• 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:
  US15/256,861
• Time in Patent Office: 525 Days
• Field of Search: None
• 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 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 computed path to transport network traffic between the two endpoints, wherein at least a portion of the computed path traverses the base network layer, and wherein a network switch of the plurality of network switches is an ingress network switch for the portion of the computed path;

by the path computation element and after computing the computed path, receiving additional topology information for at least one of the overlay network layer and the base network layer;

receiving, by the path computation element from the network switch via a communication session, a failure event message indicating a failure of the portion of the computed path;

computing, by the path computation element in response to the failure event message and using the additional topology information, a new computed path that does not include the portion of the computed path;

sending, by the path computation element, new forwarding information for the new computed path to the network switch when the path computation element successfully computes the new computed path; and

sending, by the path computation element to the client via the client interface, a path rejection when the path computation element is not able to compute the new computed path.

2. The method of claim 1, wherein the failure event message comprises a path setup failure event message that indicates the network switch failed to establish the portion of the computed path.

3. The method of claim 1, wherein the failure event message comprises a path failure event message that indicates the portion of the computed path established by the network switch has failed.

4. The method of claim 1, further comprising:

configuring, by the path computation element, an interface in the network switch for the portion of the computed path.

5. The method of claim 1, wherein sending new forwarding information for the new computed path to the network switch causes the network switch to establish a label switched path over the portion of the computed path.

6. The method of claim 1, wherein the failure event message comprises a label switched path state report message for a path computation element communication protocol (PCEP).

7. The method of claim 1, wherein the path request specifies a start time for path activation, the method further comprising:

scheduling, by the path computation element, the new computed path as a scheduled path for the start time,

wherein sending the new forwarding information to the network switch comprises sending, by the path computation element, new forwarding information for the new computed path to the network switch at the start time.

8. The method of claim 7, 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 sending the new forwarding information.

9. The method of claim 7,

wherein the path request specifies a path request parameter, and

wherein computing the new computed path comprises computing the new computed path to satisfy the path request parameter, the method further comprising:

validating, by the path computation element, the new computed path by determining whether multi-topology network resources required to satisfy the path request parameter are available for reservation,

wherein sending the new forwarding information comprises sending, by the path computation element in response to determining the new computed path is valid, the new forwarding information.

10. A path computation element comprising:

one or more programmable processors operably coupled to a memory;

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, from a client, a path request that specifies two endpoints 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 computed path to transport network traffic between the two endpoints, wherein at least a portion of the computed path traverses the base network layer, and wherein a network switch of the plurality of network switches is an ingress network switch for the portion of the computed path,

wherein the topology server interface and overlay controller interface are further configured to receive, after the service path engine computes the computed path, additional topology information for at least one of the overlay network layer and the base network layer;

a network switch interface configured to receive from the network switch via a communication session, a failure event message indicating a failure of the portion of the computed path,

wherein the service path engine is configured to compute, in response to the failure event message and using the additional topology information, a new computed path that does not include the portion of the computed path,

wherein the network switch interface is configured to send new forwarding information for the new computed path to the network switch when the path computation element successfully computes the new computed path, and

wherein the client interface is configured to send, to the client, a path rejection when the path computation element is not able to compute the new computed path.

11. The path computation element of claim 10, wherein the failure event message comprises a path setup failure event message that indicates the network switch failed to establish the portion of the computed path.

12. The path computation element of claim 10, wherein the failure event message comprises a path failure event message that indicates the portion of the computed path established by the network switch has failed.

13. The path computation element of claim 10,

wherein the network switch interface is configured to configure an interface in the network switch for the portion of the computed path.

14. The path computation element of claim 10, wherein the new forwarding information for the new computed path causes the network switch to establish a label switched path over the portion of the computed path.

15. The path computation element of claim 10, wherein the failure event message comprises a label switched path state report message for a path computation element communication protocol (PCEP).

16. The path computation element of claim 10, wherein the path request specifies a start time for path activation, the path computation element further comprising:

a scheduler configured to schedule the new computed path as a scheduled path for the start time,

wherein the network switch interface is configured to send the new forwarding information for the new computed path to the network switch at the start time.

17. The path computation element of claim 16, further comprising:

a generated path database configured to store the scheduled path; and

a path manager that marks the scheduled path in the generated path database as active upon sending the new forwarding information.

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

receive 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, from a client and via a client interface of the path computation element, a path request that specifies two endpoints and a requested bandwidth;

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 computed path to transport network traffic between the two endpoints, wherein at least a portion of the computed path traverses the base network layer, and wherein a network switch of the plurality of network switches is an ingress network switch for the portion of the computed path;

after computation of the computed path, receive additional topology information for at least one of the overlay network layer and the base network layer;

receive, from the network switch via a communication session, a failure event message and using the additional topology information indicating a failure of the portion of the computed path;

compute, in response to the failure event message, a new computed path that does not include the portion of the computed path;

send new forwarding information for the new computed path to the network switch when the path computation element successfully computes the new computed path; and

send, to the client via the client interface, a path rejection when the path computation element is not able to compute the new computed path.