# US 8,787,154 B1 · Multi-topology resource scheduling within a computer network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,787,154 B1 - Document ID: US8787154B1 - Status: Granted - Kind: B1 - Application number: 13/339,983 - Filed: 2011-12-29 - Granted: 2014-07-22 - Earliest claimed: 2011-12-29 - Assignees: Juniper Networks, Inc. - Applicants: Jan Medved; David Ward - Inventors: Jan Medved; David Ward - Web page: https://patentgrep.com/patent/US8787154B1 ## CPC - H04L 45/64: using an overlay routing layer - H04L 45/02: Topology update or discovery - H04L 45/12: Shortest path evaluation - H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS] - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 1 A method comprising: receiving, with 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, with the multi-topology path computation element, topology information for the overlay network layer, receiving, with the multi-topology path computation element, a path request that specifies two endpoints and a start time for path activation; determining, by the multi-topology path computation element, respective layers of the multi-topology network in which each of the two endpoints is logically located; computing, by the multi-topology path computation element, a 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, wherein computing the path comprises responsive to determining that a first one of the two endpoints is logically located in the overlay network layer and a second one of the two endpoints is logically located in the base network layer, computing a first sub-path of the path between one of the overlay switches having an interface to the first one of the two endpoints and a gateway connecting the overlay network layer and the base network layer and computing a second sub-path of the path between one of the network switches having an interface to the second one of the two endpoints and the gateway; scheduling, by the multi-topology path computation element, the computed path as a scheduled path for the start time; and installing, at the start time and by the multi-topology path computation element, forwarding information for the path to one or more of the network switches and overlay switches and also installing forwarding information for the path to the gateway to connect the first sub-path and the second sub-path in the gateway. ### Claim 2 (depends on 1) The method of claim 1, wherein the gateway comprises an integrated routing and bridging instance of one of the network switches. ### Claim 3 (depends on 1) The method of claim 1, wherein one or more of the overlay switches are OpenFlow switches, the method further comprising: receiving the topology information for the overlay network layer from an OpenFlow controller. ### Claim 4 (depends on 1) The method of claim 1, wherein one or more of the overlay switches are OpenFlow switches, and wherein installing forwarding information for the path to one or more of the network switches and overlay switches comprises directing an OpenFlow controller to install the forwarding information to the OpenFlow switches using respective OpenFlow protocol sessions. ### Claim 5 (depends on 1) The method of claim 1, wherein the topology information for the base network layer includes traffic engineering information, wherein the path request specifies a path request parameter, and wherein computing the path comprises computing a path that satisfies the path request parameter. ### Claim 6 (depends on 5) The method of claim 5, wherein the path request parameter is one of a bandwidth, latency, jitter, cost, and color. ### Claim 7 (depends on 1) The method of claim 1, wherein computing the path comprises, computing, by the multi-topology path computation element, two disjoint subgraphs of the overlay network layer that are unconnected by an overlay link, wherein a first one of the endpoint 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, the method further comprising: computing, by the multi-topology path computation element, a base network layer path through the base network layer that connects the two disjoint subgraphs; establishing, by the multi-topology path computation element, a tunnel connecting the two disjoint subgraphs; and storing a new overlay network link for the tunnel to the topology information for the overlay network layer, wherein computing the path comprises computing the path to include the new overlay network link. ### Claim 8 (depends on 7) The method of claim 7, further comprising: computing the base network layer path based at least on the topology information for the base network layer. ### Claim 9 (depends on 7) The method of claim 7, wherein establishing the tunnel comprises establishing the tunnel between a first one of the overlay switches that is logically located in a first one of the two disjoint subgraphs and a second one of the overlay switches that is logically located in a second one of the two disjoint subgraphs. ### Claim 10 (depends on 9) The method of claim 9, 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. ### Claim 11 (depends on 7) The method of claim 7, wherein the tunnel comprises a label switched path (LSP). ### Claim 12 (depends on 1) The method of claim 1, further comprising: receiving, with the multi-topology path computation element, endpoint information that describes endpoints reachable by respective network switches. ### Claim 13 (depends on 12) The method of claim 12, further comprising: validating the path request by ensuring each of the two endpoints is reachable by at least one of the network switches using the endpoint information. ### Claim 14 (depends on 1) The method of claim 1, wherein the overlay network comprises a virtual private network. ### Claim 15 (depends on 1) The method of claim 1, wherein receiving the topology information for the base network layer comprises receiving an application-layer traffic optimization network map having one or more PIDs each representing a physical interface of one of the network switches of the base network layer. ### Claim 16 (depends on 15) The method of claim 15, further comprising: receiving an application-layer traffic optimization cost map specifying traffic engineering costs between pairs of the PIDs of the network map. ### Claim 17 (depends on 1) The method of claim 1, wherein the path request specifies a path request parameter, and wherein computing the path comprises computing a path that satisfies 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; responsive to determining that 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 responsive to determining that the scheduled path is valid, installing the forwarding information for the scheduled path. ### Claim 18 (depends on 1) The method of claim 1, 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. ### Claim 19 (depends on 1) The method of claim 1, further comprising: storing scheduled paths computed by the multi-topology path computation element to a generated paths database, wherein each of the scheduled paths has an associated start time, end time, and bandwidth requirement, wherein the path request specifies an end time and bandwidth requirement, and wherein computing the 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. ### Claim 20 (depends on 19) The method of claim 19, storing, with the multi-topology path computation element, one or more 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 path. ### Claim 21 (depends on 1) The method of claim 1, further comprising: identifying, with the multi-topology path computation element, a failed one of the overlay links or the base network links; identifying, with the multi-topology path computation element, one or more scheduled paths stored to the generated paths database that include the failed link; and removing the identified scheduled paths from the generated paths database and recomputing each of the identified scheduled paths. ### Claim 22 (depends on 21) The method of claim 21, wherein the failed link is a base network link, the method further comprising: identifying, with the multi-topology path computation element, one or more scheduled paths in the overlay network that include an overlay network link that represents a path through the base network layer that includes the failed link; removing the overlay network link from the topology information for the overlay network layer; and removing the scheduled paths from the generated paths database and recomputing each of the identified scheduled paths in the overlay network based at least on the modified topology information for the overlay network layer. ### Claim 23 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 specifies two endpoints and a start time for path activation; a service path engine to determine respective layers of the multi-topology network in which each of the two endpoints is logically located, wherein the service path engine computes a 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, wherein to compute the path the service path engine, responsive to determining that a first one of the two endpoints is logically located in the overlay network layer and a second one of the two endpoints is logically located in the base network layer, computes a first sub-path of the path between one of the overlay switches having an interface to the first one of the two endpoints and a gateway connecting the overlay network layer and the base network layer and computes a second sub-path of the path between one of the network switches having an interface to the second one of the two endpoints and the gateway; a scheduler that schedules the computed path as a scheduled path for the start time; one or more topology node interfaces; and a path manager to direct the one or more topology node interfaces to install, at the start time, forwarding information for the path to one or more of the network switches and overlay switches and also to direct the one or more topology node interfaces to install forwarding information to the gateway to connect the first sub-path and the second sub-path in the gateway. ### Claim 24 (depends on 23) The multi-topology path computation element of claim 23, wherein one or more of the overlay switches are OpenFlow switches, wherein one of the topology node interfaces comprises an OpenFlow controller interface to receive the topology information for the overlay network layer from an OpenFlow controller. ### Claim 25 (depends on 23) The multi-topology path computation element of claim 23, wherein one or more of the overlay switches are OpenFlow switches, wherein one of the topology node interfaces comprises an OpenFlow controller interface, wherein the OpenFlow controller interface installs forwarding information for the path to one or more of the network switches and overlay switches by directing an OpenFlow controller to install the forwarding information to the OpenFlow switches using respective OpenFlow protocol sessions. ### Claim 26 (depends on 23) The multi-topology path computation element of claim 23, wherein the topology information for the base network layer includes traffic engineering information, wherein the path request specifies a path request parameter, and wherein the service path engine computes the path by computing the path to satisfy the path request parameter. ### Claim 27 (depends on 23) The multi-topology path computation element of claim 23, wherein the service path engine, to compute the path, computes two disjoint subgraphs of the overlay network layer that are unconnected by an overlay 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, the multi-topology path computation element further comprising: a tunnel manager to establish a tunnel connecting the two disjoint subgraphs and stores a new overlay network link for the tunnel to the topology information for the overlay network layer in the multi-topology traffic engineering database, wherein the service path engine computes the requested path to include the new overlay network link. ### Claim 28 (depends on 27) The multi-topology path computation element of claim 27, wherein the tunnel manager establishes the tunnel by establishing the tunnel between a first one of the overlay switches that is logically located in a first one of the two disjoint subgraphs and a second one of the overlay switches that is logically located in a second one of the two disjoint subgraphs. ### Claim 29 (depends on 28) The multi-topology path computation element of claim 28, 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, wherein the one or more topology node interfaces install forwarding information for the path by installing 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. ### Claim 30 (depends on 23) The multi-topology path computation element of claim 23, further comprising: an endpoint database to store endpoint information that describes endpoints reachable by respective network switches, wherein the one or more topology node interfaces receive the endpoint information and store the endpoint information to the endpoint database. ### Claim 31 (depends on 23) The multi-topology path computation element of claim 23, further comprising: a path manager that validates the path request by ensuring each of the two endpoints is reachable by at least one of the network switches using the endpoint information. ### Claim 32 (depends on 23) The multi-topology path computation element of claim 23, wherein one of the topology node interfaces comprises an application-layer traffic optimization server interface to receive the topology information for the base network layer, wherein the topology information for the base network layer comprises an application-layer traffic optimization network map having one or more PIDs each representing a physical interface of one of the network switches of the base network layer. ### Claim 33 (depends on 32) The multi-topology path computation element of claim 32, wherein the topology information for the base network layer comprises an application-layer traffic optimization cost map specifying traffic engineering costs between pairs of the PIDs of the network map. ### Claim 34 (depends on 23) The multi-topology path computation element of claim 23, wherein the path request specifies a path request parameter, and wherein the service path engine computes the path by computing the path to satisfy the path request parameter, wherein the service path engine 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, responsive to determining that 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, wherein the one or more topology node interfaces, responsive to determining that the scheduled path is valid, install the forwarding information for the scheduled path. ### Claim 35 (depends on 23) The multi-topology path computation element of claim 23, a generated path database to store scheduled paths and active paths established by the multi-topology path computation element, wherein the path manager marks the scheduled path in the generated path database as active upon installation of the forwarding information. ### Claim 36 (depends on 23) The multi-topology path computation element of claim 23, further comprising: a generated path database to store scheduled paths and active paths established 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 specifies a an end time and a bandwidth requirement, and wherein the service path engine computes the 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. ### Claim 37 (depends on 36) The multi-topology path computation element of claim 36, further comprising: one or more 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 path database and, after preempting the first scheduled path, recomputes the path. ### Claim 38 (depends on 23) The multi-topology path computation element of claim 23, wherein the multi-topology traffic engineering database identifies a failed one of the overlay links or the base network links, the multi-topology path computation element further comprising: a generated path database to store scheduled paths and active paths established by the multi-topology path computation element, wherein the generated path database identifies one or more scheduled paths stored to the generated paths database that include the failed link and removes the identified scheduled paths from the generated paths database, wherein the service path engine recomputes each of the identified scheduled paths. ### Claim 39 (depends on 38) The multi-topology path computation element of claim 38, wherein the failed link is a base network link, wherein the generated path database identifies one or more scheduled paths in the overlay network that include an overlay network link that represents a path through the base network layer that includes the failed link, wherein the multi-topology traffic engineering database removes the overlay network link from the topology information for the overlay network layer, wherein the generated path database removes the scheduled identified paths from the generated paths database, and wherein the service path engine recomputes each of the identified scheduled paths in the overlay network based at least on the modified topology information for the overlay network layer. ### Claim 40 A non-transitory computer-readable medium comprising instructions for causing one or more programmable processors to: receive, with 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, with the multi-topology path computation element, topology information for the overlay network layer; receive, with the multi-topology path computation element, a path request that specifies two endpoints and a start time for path activation; determine, by the multi-topology path computation element, respective layers of the multi-topology network in which each of the two endpoints is logically located; compute, by the multi-topology path computation element, a 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, wherein computing the path comprises responsive to determining that a first one of the two endpoints is logically located in the overlay network layer and a second one of the two endpoints is logically located in the base network layer, computing a first sub-path of the path between one of the overlay switches having an interface to the first one of the two endpoints and a gateway connecting the overlay network layer and the base network layer and computing a second sub-path of the path between one of the network switches having an interface to the second one of the two endpoints and the gateway; schedule, by the multi-topology path computation element, the computed path as a scheduled path for the start time; and install, at the start time and by the multi-topology path computation element, forwarding information for the path to one or more of the network switches and overlay switches and also install forwarding information for the path to the gateway to connect the first sub-path and the second sub-path in the gateway.