Multi-topology resource scheduling within a computer network

• US 9,705,781 B1
• Filed: 07/21/2014
• Issued: 07/11/2017
• Est. Priority Date: 12/29/2011
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ward, David, Medved, Jan
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Rivas, Raul
• Application Number:
  US14/336,535
• Time in Patent Office: 1,086 Days
• Field of Search: None
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/64 using an overlay routing layer

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 from a client application, a path request that specifies two endpoints of a network, the two endpoints comprising an ingress endpoint and an egress endpoint;

computing, by the path computation element and in response to receiving the path request, a path through the network to transport network traffic between the two endpoints from the ingress endpoint to the egress endpoint; and

sending, by the path computation element to a router of the network that is the ingress endpoint, a message, wherein the message includes path information associated with each router along the path and traffic engineering information associated with one or more of the routers along the path, the message directing the router to establish, via a signaling protocol and based on the path information and the traffic engineering information received via the message, a traffic engineered label switched path (TE LSP) that traverses the path through the network to transport network traffic between the two endpoints from the ingress endpoint to the egress endpoint.

2. The method of claim 1,

wherein the path request specifies scheduling information indicating a time at which the path through the network to transport network traffic between the two endpoints is to be active, and

wherein sending the message comprises sending, by the path computation element to the router of the network, the message such that the path through the network to transport network traffic between the two endpoints is active at the time indicated by the scheduling information.

3. The method of claim 1, wherein the path computation element includes a client interface and wherein receiving the path request comprises receiving the path request via the client interface of the path computation element, the client interface comprising an application programming interface invoked by the client application to dynamically program the path into the network.

4. The method of claim 1,

wherein the path request specifies a bandwidth, and

wherein computing the path through the network to transport network traffic between the two endpoints comprises computing the path to satisfy the bandwidth.

5. The method of claim 1,

wherein the client application is not executed by the router, and

wherein the message is not responsive to a request from the router.

6. The method of claim 1, wherein the message conforms to an extended Path Computation Element communication Protocol (PCEP).

7. The method of claim 1, wherein the message includes an Explicit Route Object that defines the path through the network to transport network traffic between the two endpoints.

8. The method of claim 1, further comprising:

receiving, by the path computation element from the router, an indication the router failed to establish the path through the network to transport network traffic between the two endpoints; and

sending, by the path computation element to the client application in response to the indication, a path rejection message indicating the path computation element is unable to satisfy the path request.

9. The method of claim 1, wherein the path request specifies scheduling information indicating a time at which the path through the network to transport network traffic between the two endpoints is to be active, the method further comprising:

validating, by the path computation element prior to sending the message to the router, the path through the network to transport network traffic between the two endpoints,

wherein sending the message comprises sending, by the path computation element to the router of the network only in response to validating the path through the network to transport network traffic between the two endpoints, the message.

10. The method of claim 1, wherein the router of the network comprises an endpoint of the two endpoints.

11. A method comprising:

receiving, by a router of a network from a path computation element without the router having requested a path through the network to transport network traffic between two endpoints comprising an ingress endpoint and an egress endpoint, wherein the router is the ingress endpoint, a message, wherein the message includes path information associated with each router along the path and traffic engineering information associated with one or more of the routers along the path, the message directing the router to establish, via a signaling protocol and based on the path information and the traffic engineering information received via the message, a traffic engineered label switched path (TE LSP) that traverses the path through the network to transport network traffic between the two endpoints from the ingress endpoint to the egress endpoint; and

establishing, by the router in response to receiving the message, the TE LSP.

12. The method of claim 11, wherein the message conforms to an extended Path Computation Element communication Protocol (PCEP).

13. The method of claim 11, wherein the message includes an Explicit Route Object that defines the path through the network to transport network traffic between the two endpoints.

14. The method of claim 11, wherein establishing the TE LSP comprises establishing, by the router, the TE LSP using a Resource Reservation Protocol (RSVP) with Traffic Engineering extensions (RSVP-TE).

15. A path computation element device comprising:

at least one processor coupled to a memory;

a client interface executed by the at least one processor to receive, from a client application, a path request that specifies two endpoints of a network, the two endpoints comprising an ingress endpoint and an egress endpoint;

a service path engine executed by the at least one processor to compute, in response to receiving the path request, a path through the network to transport network traffic between the two endpoints from the ingress endpoint to the egress endpoint; and

a path computation element communication protocol (PCEP) interface executed by the at least one processor to send, to a router of the network that is the ingress endpoint, a message, wherein the message includes path information associated with each router along the path and traffic engineering information associated with one or more of the routers along the path, the message directing the router to establish, via a signaling protocol and based on the path information and the traffic engineering information received via the message, a traffic engineered label switched path (TE LSP) that traverses the path through the network to transport network traffic between the two endpoints from the ingress endpoint to the egress endpoint.

16. The path computation element device of claim 15,

wherein the path request specifies scheduling information indicating a time at which the path through the network to transport network traffic between the two endpoints is to be active, and

wherein to send the message the PCEP interface send, to the router of the network, the message such that the path through the network to transport network traffic between the two endpoints is active at the time indicated by the scheduling information.

17. The path computation element device of claim 15, wherein the client interface comprises an application programming interface invoked by the client application to dynamically program the path into the network.

18. The path computation element device of claim 15, wherein the message conforms to an extended Path Computation Element communication Protocol (PCEP).

19. The path computation element device of claim 15,

wherein the client application is not executed by the router, and

wherein the message is not responsive to a request from the router.

20. A router comprising:

at least one processor coupled to a memory;

a path computation client (PCC) interface executed by the at least one processor to receive, from a path computation element without the PCC interface having requested a path through the network to transport network traffic between two endpoints comprising an ingress endpoint and an egress endpoint, wherein the router is the ingress endpoint for the path, a message, wherein the message includes path information associated with each router along the path and traffic engineering information associated with one or more of the routers along the path, the message directing the router to establish, via a signaling protocol and based on the path information and the traffic engineering information received via the message, a traffic engineered label switched path (TE LSP) that traverses the path through the network to transport network traffic between the two endpoints from the ingress endpoint to the egress endpoint; and

a routing protocol module executed by the at least one processor to establish the TE LSP in response to receiving the message.