Patent ID: 8824274

Claim:
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.