Scheduled network layer programming within a multi-topology computer network

• US 8,824,274 B1
• Filed: 12/29/2011
• Issued: 09/02/2014
• 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
• Assistant Examiner(s): Rivas, Raul
• Application Number:
  US13/340,191
• Time in Patent Office: 978 Days
• US Class Current: 370/217
• 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 multi-topology path computation element, topology information for a base network layer of a multi-topology network that comprises 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 comprises an overlay network layer having a plurality of overlay switches interconnected by overlay network links in an overlay network topology, wherein each of the overlay network links represents a path through the base network connecting two of the overlay switches;

receiving, by the multi-topology path computation element, topology information for the overlay network layer;

receiving, by the multi-topology path computation element, a path request that requests a path to be established between two endpoints;

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, computing, by the multi-topology path computation element, two disjoint subgraphs of the overlay network layer that are unconnected by an overlay network link, wherein a first one of the endpoints is reachable by a first one of the two disjoint subgraphs and a second one of the endpoints is reachable by a second one of the two disjoint subgraphs;

computing, by the multi-topology path computation element, a base network layer path through the base network layer that connects the two disjoint subgraphs, wherein a first network switch of the network switches is an ingress network switch for the base network layer path;

establishing, by the multi-topology path computation element, a communication session with the first network switch;

directing, by the multi-topology path computation element using the communication session, the first network switch to establish a tunnel connecting the two disjoint subgraphs over the base network layer path;

storing a new overlay network link for the tunnel to the topology information for the overlay network layer,

computing, by the multi-topology path computation element and using the topology information for the overlay network layer, a computed path to carry traffic between the two endpoints through the overlay network layer, wherein at least a portion of the computed path traverses the new overlay network link.

2. The method of claim 1, further comprising:

configuring, by the multi-topology path computation element, an interface in the first network switch for the base network layer path.

3. The method of claim 1, wherein directing the first network switch to establish the tunnel comprises directing the first network switch to establish a label switched path over the base network layer path.

4. The method of claim 1, further comprising:

receiving, with the multi-topology path computation element, a path setup failure event message in the communication session when the first network switch fails to establish the tunnel;

recomputing in response to the path setup failure event message, by the multi-topology path computation element, a new path to carry traffic between the two endpoints through one or more layers of the multi-topology network using the topology information for the base network layer and the topology information for the overlay network layer;

installing, by the multi-topology path computation element, new forwarding information for the new path to one or more of the network switches and overlay switches when the multi-topology path computation element successfully computes the new path; and

sending a path rejection from the multi-topology path computation element to a client that issued the path request when the multi-topology path computation element is not able to compute the new path.

5. The method of claim 1, further comprising:

receiving, with the multi-topology path computation element, a path failure event message in the communication session when the tunnel established by the first network switch fails;

recomputing in response to the path setup failure event message, by the multi-topology path computation element, a new path to carry traffic between the two endpoints through one or more layers of the multi-topology network using the topology information for the base network layer and the topology information for the overlay network layer;

installing, by multi-topology path computation element, new forwarding information for the new path to one or more of the network switches and overlay switches when the multi-topology path computation element successfully computes the new path; and

sending a path rejection from the multi-topology path computation element to a client that issued the path request when the multi-topology path computation element is not able to compute the new path.

6. The method of claim 1, wherein the communication session is an extended path computation element protocol session.

7. The method of claim 1, wherein the path request specifies one or more classifier values that identify one or more flows, the method further comprising:

installing, by the multi-topology path computation element, forwarding information for the computed path to one or more of the network switches and overlay switches, wherein the forwarding information causes the network switches and overlay switches to forward packet data units having properties that match the one or more classifier values to direct the one or more flows onto the computed path.

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

scheduling the computed path as a scheduled path for the start time; and

installing, by the multi-topology path computation element, forwarding information for the scheduled path to one or more of the network switches and overlay switches at the start time.

9. The method of claim 8,

wherein the path request specifies a path request parameter, and

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

validating the scheduled path by determining whether multi-topology network resources required to satisfy the path request parameter are available for reservation;

when the scheduled path is invalid, recomputing, by the multi-topology path computation element, a new path to carry traffic between the two endpoints through one or more layers of the multi-topology network using the topology information for the base network layer and the topology information for the overlay network layer; and

when the scheduled path is valid, installing the forwarding information for the scheduled path.

10. The method of claim 8, further comprising:

storing scheduled paths and active paths established by the multi-topology path computation element to a generated path database; and

marking the scheduled path in the generated path database as active upon installation of the forwarding information for the scheduled path.

11. The method of claim 8, further comprising:

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

wherein the path request further specifies an end time and a bandwidth requirement, and

wherein computing the computed path comprises determining whether a path satisfying the bandwidth requirement exists in the multi-topology network for the interval between the start time and end time based at least on the associated start times, end times, and bandwidth requirements of the scheduled paths.

12. The method of claim 11,

storing, with the multi-topology path computation element, policies specifying relative priorities for clients of the multi-topology path computation element;

and

when the multi-topology path computation element is unable to compute a path satisfying the bandwidth requirement, preempting a first one of the scheduled paths in the generated paths database and, after preempting the first scheduled path, recomputing the computed path.

26. The method of claim 1,

wherein a first one of the overlay switches is logically located in a first one of the two disjoint subgraphs and a second one of the overlay switches is logically located in a second one of the two disjoint subgraphs, and

wherein establishing the tunnel comprises establishing the tunnel from the first one of the overlay switches to the second one of the overlay switches.

27. The method of claim 26, wherein a first one of the network switches comprises the first overlay switch and a second one of the network switches comprises the second overlay switch, the method further comprising:

installing, by the multi-topology path computation element, forwarding information to the first and second overlay switches to connect an interface of the first network switch for the tunnel to the first overlay switch and connect an interface of the second network switch for the tunnel to the second overlay switch.

13. A multi-topology path computation element comprising:

a multi-topology traffic engineering database to store topology information for a base network layer of a multi-topology network that comprises a plurality of network switches interconnected by base network layer three (L3) links in a base network topology and to store topology information for an overlay network layer of the multi-topology network that comprises a plurality of overlay switches interconnected by overlay network links in an overlay network topology, wherein each of the overlay network links represents a path through the base network connecting two of the overlay switches;

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

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

a client interface to receive a path request that requests a path to be established between two endpoints, wherein the path request specifies the two endpoints;

a service path engine 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, two disjoint subgraphs of the overlay network layer that are unconnected by an overlay network link, wherein a first one of the endpoints is reachable by a first one of the two disjoint subgraphs and a second one of the endpoints is reachable by a second one of the two disjoint subgraphs,

wherein the service path engine computes a base network layer path through the base network layer that connects the two disjoint subgraphs, wherein a first network switch of the network switches is an ingress network switch for the base network layer path;

a network switch interface to establish a communication session with the first network switch;

a tunnel manager to, using the communication session, direct the first network switch to establish a tunnel connecting the two disjoint subgraphs over the base network layer path and store a new overlay network link for the tunnel to the topology information for the overlay network layer,

wherein the service path engine computes a computed path to carry traffic between the two endpoints through the overlay network layer using the topology information for the overlay network layer, wherein at least a portion of the computed path traverses the new overlay network link.

14. The multi-topology path computation element of claim 13, further comprising:

a management interface to configure an interface in the first network switch for the base network layer path.

15. The multi-topology path computation element of claim 13, wherein the network switch interface directs the first network switch to establish the tunnel by directing the first network switch to establish a label switched path over the base network layer path.

16. The multi-topology path computation element of claim 13,

wherein the network switch interface receives a path setup failure event message in the communication session when the first network switch fails to establish the tunnel,

wherein, in response to the path setup failure event message, the service path engine recomputes a new path to carry traffic between the two endpoints through one or more layers of the multi-topology network using the topology information for the base network layer and the topology information for the overlay network layer, the multi-topology path computation element further comprising:

one or more topology node interfaces to install new forwarding information for the new path to one or more of the network switches and overlay switches when the multi-topology path computation element successfully computes the new path; and

a client interface to send a path rejection to a client that issued the path request when the service path engine is not able to compute the new path.

17. The multi-topology path computation element of claim 13,

wherein the network switch interface receives a path failure event message in the communication session when the tunnel established by the first network switch fails;

wherein, in response to the path setup failure event message, the service path engine recomputes a new path to carry traffic between the two endpoints through one or more layers of the multi-topology network using the topology information for the base network layer and the topology information for the overlay network layer, the multi-topology path computation element further comprising;

one or more topology node interfaces to install new forwarding information for the new path to one or more of the network switches and overlay switches when the multi-topology path computation element successfully computes the new path; and

a client interface to send a path rejection to a client that issued the path request when the service path engine is not able to compute the new path.

18. The multi-topology path computation element of claim 13,

wherein the network switch interface comprises an extended path computation element protocol interface, and

wherein the communication session comprises an extended path computation protocol session.

19. The multi-topology path computation element of claim 13, wherein the path request specifies one or more classifier values that identify one or more flows, the multi-topology path computation element further comprising:

one or more topology node interfaces to install forwarding information for the computed path to one or more of the network switches and overlay switches, wherein the forwarding information causes the network switches and overlay switches to forward packet data units having properties that match the one or more classifier values to direct the one or more flows onto the computed path.

20. The multi-topology path computation element of claim 13, wherein the path request specifies a start time for path activation, the multi-topology path computation element further comprising:

a scheduler to schedule the computed path as a scheduled path for the start time; and

one or more topology node interfaces to install forwarding information for the scheduled path to one or more of the network switches and overlay switches at the start time.

21. The multi-topology path computation element of claim 20,

wherein the path request specifies a path request parameter, and

wherein computing the computed path comprises computing the computed path to satisfy the path request parameter,

wherein the service path manager validates the scheduled path by determining whether multi-topology network resources required to satisfy the path request parameter are available for reservation,

wherein the service path engine, when the scheduled path is invalid, recomputes a new path to carry traffic between the two endpoints through one or more layers of the multi-topology network using the topology information for the base network layer and the topology information for the overlay network layer, and

wherein the topology node interfaces, when the scheduled path is valid, install the forwarding information for the scheduled path.

22. The multi-topology path computation element of claim 20, further comprising:

a generated path database to store scheduled paths and active paths established by the multi-topology path computation element;

a path manager that marks the scheduled path in the generated path database as active upon installation of the forwarding information for the scheduled path.

23. The multi-topology path computation element of claim 20, further comprising:

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

wherein the path request further specifies an end time and a bandwidth requirement, and

wherein the service path engine computes the computed path by determining whether a path satisfying the bandwidth requirement exists in the multi-topology network for the interval between the start time and end time based at least on the associated start times, end times, and bandwidth requirements of the scheduled paths.

24. The multi-topology path computation element of claim 23, further comprising:

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

wherein the service path engine, when unable to compute a path satisfying the bandwidth requirement, preempts a first one of the scheduled paths in the generated paths database and, after preempting the first scheduled path, recomputes the computed path.

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

receive, by a multi-topology path computation element, topology information for a base network layer of a multi-topology network that comprises 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 comprises an overlay network layer having a plurality of overlay switches interconnected by overlay network links in an overlay network topology, wherein each of the overlay network links represents a path through the base network connecting two of the overlay switches;

receive, by the multi-topology path computation element, topology information for the overlay network layer;

receive, by the multi-topology path computation element, a path request that requests a path to be established between two endpoints, wherein the path request specifies the two endpoints;

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, compute, by the multi-topology path computation element, two disjoint subgraphs of the overlay network layer that are unconnected by an overlay network link, wherein a first one of the endpoints is reachable by a first one of the two disjoint subgraphs and a second one of the endpoints is reachable by a second one of the two disjoint subgraphs;

compute, by the multi-topology path computation element, a base network layer path through the base network layer that connects the two disjoint subgraphs, wherein a first network switch of the network switches is an ingress network switch for the base network layer path;

establish, by the multi-topology path computation element, a communication session with the first network switch;

direct, by the multi-topology path computation element using the communication session, the first network switch to establish a tunnel connecting the two disjoint subgraphs over the base network layer path;

store a new overlay network link for the tunnel to the topology information for the overlay network layer,

compute, by the multi-topology path computation element and using the topology information for the overlay network layer, a computed path to carry traffic between the two endpoints through the overlay network layer, wherein at least a portion of the computed path traverses the new overlay network link.