Patent Description:
According to a first aspect of the present disclosure, there is provided a method as set out in the accompanying claims.

In an implementation of the first aspect, the method can further comprise determining measures of reachability for the nodes to indicate whether the domains represented by the nodes are on a path from a source domain to a destination domain. Determining the measures of reachability can comprise determining betweenness centralities for the nodes, wherein the betweenness centralities indicate how many pairs of domains use the domains associated with the nodes as a transit. Determining the betweenness centralities for the nodes can comprises determining a number of interconnections that exist between the nodes and other nodes in the graph. The method can further comprise modifying the graph by inserting at least one temporary link between a destination node that represents the destination domain in the graph and at least one node in the graph that does not have a physical link to the destination node prior to determining the betweenness centralities. Determining the betweenness centralities can comprise determining the betweenness centralities based on the modified graph. Pruning the at least one of the domains from the actual topology can comprise pruning the at least one of the domains based on resources of the nodes in the abstract topology that are reachable on at least one path between a source node and a destination node, as indicated by the measures of reachability such that a pathfinding algorithm does not consider paths that include routers in the at least one pruned domain. The method can further comprise assigning ranks to the domains based on the measures of reachability of the corresponding nodes. The method can further comprise comparing the ranks of the source node and the nodes in the abstract topology, and selectively pruning a relationship to at least one edge in the actual topology based on the comparison of the ranks of the source node and the nodes in the abstract topology. The method can further comprise modifying weights of edges between the nodes in the actual topology based on the ranks of the nodes in the abstract topology to preference links to higher ranks nodes during path traversals of the actual topology. The method can further comprise determining a path from a source node to a destination node by applying a pathfinding algorithm to the actual topology, wherein the pathfinding algorithm does not consider the at least one of the domains that is pruned from the actual topology based on the abstract topology, and configuring the source node and the destination node to convey packets over the past determined by the pathfinding algorithm.

According to a second aspect of the present disclosure, there is provided an apparatus as set out in the accompanying claims. The processor can generate a graph comprising nodes to represent the domains and the border routers, wherein the graph represents mappings between pairs of domains and indicates domains that are used in transit between the pairs of domains. The processor can determine measures of reachability for the nodes to indicate whether the domains represented by the nodes are on a path from a source domain to a destination domain. The processor can determine betweenness centralities for the nodes, wherein the betweenness centralities indicate how many pairs of domains use the domains associated with the nodes as a transit. The processor can determine the betweenness centralities based on how many interconnections exist between the nodes and other nodes in the graph. The processor can modify the graph by inserting at least one temporary link between a destination node that represents the destination domain in the graph and at least one node in the graph that does not have a physical link to the destination node prior to determining the betweenness centralities, and determine the betweenness centralities based on the modified graph. The processor can prune the at least one of the domains based on resources of the nodes in the abstract topology that are reachable on at least one path between a source node and a destination node, as indicated by the measures of reachability such that a pathfinding algorithm does not consider paths that include routers in the at least one pruned domain. The processor can assign ranks to the domains based on the measures of reachability of the corresponding nodes. The processor can compare the ranks of the source node and the nodes in the abstract topology and selectively prune a relationship to at least one edge in the actual topology based on the comparison of the ranks of the source node and the nodes in the abstract topology. The processor can modify weights of edges between the nodes in the actual topology based on the ranks of the nodes in the abstract topology to preference links to higher ranks nodes during path traversals of the actual topology. The processor can determine a path from a source node to a destination node by applying a pathfinding algorithm to the actual topology, wherein the pathfinding algorithm does not consider the at least one of the domains that is pruned from the actual topology based on the abstract topology, and configure the source node and the destination node to convey packets over the past determined by the pathfinding algorithm.

Described is an apparatus comprising at least one processor, and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to perform generating an abstract topology that represents domains in an actual topology of a network and border routers that interconnect the domains in the actual topology, and pruning, based on the abstract topology, at least one of the domains from the actual topology during path calculations on the actual topology. The at least one memory and the computer program code can be configured to, with the at least one processor, cause the apparatus at least to perform determining measures of reachability for the nodes to indicate whether the domains represented by the nodes are on a path from a source domain to a destination domain. The at least one memory and the computer program code can be configured to, with the at least one processor, cause the apparatus at least to perform assigning ranks to the domains based on the measures of reachability of the corresponding nodes, and selectively pruning a relationship to at least one edge in the actual topology or modifying weights of edges between the nodes in the actual topology based on the ranks of the nodes in the abstract topology.

The present disclosure is better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings.

Service providers are deploying ever larger and more complex IP networks to meet user demands for accessibility and Service Level Agreement (SLA) requirements such as latency and bandwidth. Increasing the size and complexity of the IP network increases the bandwidth consumption and convergence delay for flooding state information through the IP network and increases the computational overhead needed to execute pathfinding algorithms. Routers or links in larger IP networks are therefore subdivided or partitioned into subsets to manage and contain link state flooding. For example, an IGP domain (or IGP instance) can be partitioned into IGP areas that include subsets of the routers in the IGP domain. The IGP areas are interconnected by border routers that stitch together the IGP areas.

Full inter-domain network visibility is not provided to the routers in a conventional network that is partitioned into separate areas. Instead, summaries of the topological information that represents the routers and links in the IGP areas are conveyed between the IGP areas to reduce the bandwidth consumption. Thus, the routers in one IGP area do not possess complete topological information representing the routers and links in other IGP areas. In some cases, multiple IGP instances are also interconnected via border routers and the IGP instances only exchange summarized topological information unless they are explicitly configured for redistribution or they implement an Exterior Gateway Protocol (EGP) such as the Border Gateway Protocol (BGP) between the IGP instances. However, in some cases, the constraints imposed by the SLA require using TE pathfinding techniques to identify TE paths through the network that satisfy the constraints. Individual routers cannot determine TE paths because the detailed topological information for the IGP areas (and, in some cases, the IGP instances) has been summarized between the border routers between different areas as well as between different IGP instances.

Path computation elements (PCE) or other software defined networking (SDN) controllers compute TE paths across IGP areas and domain boundaries. Inter-area and inter-domain topology information that represents links (edges) and routers (nodes) is provided to the PCE/SDN controllers to provide full network visibility so that the PCE/SDN controllers have a complete view of the network. For example, the inter-domain router topology can be represented as a graph of the interconnections between the routers in all the domains of the network, as well as all the links within the domains. The PCE/SDN controllers are therefore able to increase the scope of the search performed by pathfinding algorithms to include the entire graph of the router interconnections. However, this approach reintroduces the problem of increasing computational overhead for the path search because the PCE/SDN controller stores the topological state as one graph entity without including forwarding or border rules to aid in pruning the path search. Furthermore, network topologies used by service providers often include designated core, transit, and access domains (in a core architecture) or leaf and spine domains (in a leaf-and-spine architecture). The core domains (in a core architecture) and the spine domains (in a leaf-and-spine architecture) include more sophisticated, higher capacity routers and should therefore be given preference relative to other domains that include lower capacity routers. For example, in a core configuration, "arc" domains that include paths that bypass the core domain and "leaf" domains that only connected to one another domain should be given lower preference relative to the core domain. These preferences can be represented as constraints that are applied by a TE pathfinding algorithm using a set of TE rules. However, configuring the PCE/SDN controllers to identify different types of domains and the corresponding TE rules is a tedious and error-prone process.

<FIG> disclose systems and techniques for reducing the computational overhead required to find paths through a network including routers that are partitioned into multiple domains (or areas), while increasing the likelihood of finding an optimal TE path through the actual topology that represents the network, by generating an abstract topology that represents the domains in the actual topology and border routers that interconnect the domains in the actual topology. The abstract topology is then referenced for pruning decisions when performing path calculations on the actual topology.

The abstract topology is a graph that includes nodes to represent the domains and the border routers. The graph represents a mapping between pairs of domains in the abstract topology and the mapping indicates domains that are used in transit between each pair of domains. The abstract topology also includes measures of reachability of the domains. As used herein, the term "reachability" refers to whether nodes in the graph represent domains along a path from a source domain to a destination domain regardless of whether the domain is part of an optimal or shortest path connecting the source and destination domains. For example, if a path from a first domain to a second domain includes a third domain, the third domain is reachable on the path even if the path is not the shortest path from the first domain to the second domain. In some embodiments, the measure of reachability of a domain indicates how many pairs of domains use the domain as a transit. This measure of reachability is referred to as "betweenness centrality," which indicates how central the domain/node is in the graph based on how many interconnections exist between the node and other nodes in the graph. In some cases, before determining the betweenness centralities of the nodes, temporary links are inserted between the destination node and nodes that do not have a physical link to the destination node. In some embodiments, a rank or a weight is assigned to a domain based on the number of pairs of domains that use the domain as a transit, e.g., based on the betweenness centrality of the node.

Pathfinding through the actual topology is modified based on measures of reachability of the domains in the abstract topology. In some embodiments, the pathfinding algorithm uses the resources of reachable nodes in the abstract topology to prune graph entities in the actual topology during the path search. For example, during pathfinding from a source node to a destination node, a PCE/SDN controller can identify links in the actual topology that are associated with nodes in the abstract topology that are not in a set of reachable nodes for the source and destination nodes. The PCE/SDN controller can then prune these links so that the pathfinding algorithm does not have to consider paths that include routers in the pruned nodes. In some embodiments, the PCE/SDN controller compares the reachability rank of the source node to the ranks of nodes in the abstract topology. If the rank of the node in the abstract topology is lower than the source node rank, and the node is not the destination node for the path, the PCE/SDN controller prunes the relationship to the corresponding edge in the actual topology. In other embodiments, weights of edges between nodes in the actual topology are modified based on the ranks of the referenced nodes in the abstract topology to preference links to higher-ranked nodes during path traversals of the actual topology.

<FIG> is a block diagram of an actual topology <NUM> of an IP network that implements inter-domain path calculations based on an abstract topology derived from the actual topology <NUM> according to some embodiments. Some embodiments of the IP network are implemented using interior gateway protocols (IGPs) including link state protocols such as open shortest path first (OSPF, OSPFv3), intermediate system-to-intermediate system (IS-IS), and the like.

The actual topology <NUM> includes routers that are partitioned into domains of the network. In the illustrated embodiment, a domain <NUM> includes the routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the routers <NUM>-<NUM>"), a domain <NUM> includes the routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the routers <NUM>-<NUM>"), a domain <NUM> includes the routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the routers <NUM>-<NUM>"), a domain <NUM> includes the routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the routers <NUM>-<NUM>"), and a domain <NUM> includes the routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the routers <NUM>-<NUM>"). Although five domains including four routers each are shown in <FIG> in the interest of clarity, some embodiments of the actual topology <NUM> include more or fewer domains including more or fewer routers and the number of routers per domain can differ from domain to domain.

The domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> are interconnected by border routers that overlap with multiple domains. In the illustrated embodiment, a border router <NUM> interconnects the domains <NUM>, <NUM>, a border router <NUM> interconnects the domains <NUM>, <NUM>, a border router <NUM> interconnects the domains <NUM>, <NUM>, a border router <NUM> interconnects the domains <NUM>, <NUM>, and a border router <NUM> interconnects the domains <NUM>, <NUM>. Although a single border router <NUM>-<NUM> connects pairs of the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> in <FIG>, some embodiments of the actual topology <NUM> include other configurations of border routers. For example, multiple border routers can be used to connect a pair of domains. For another example, a single border router can interconnect more than two domains.

A controller <NUM> receives and stores information representing the actual topology <NUM>. In some embodiments, the controller <NUM> is implemented as a path computation element (PCE) or software defined networking (SDN) controller that receives and stores information that is flooded by the routers <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM>. The controller <NUM> generates an abstract topology that represents the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and the border routers <NUM>-<NUM> that interconnect the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. The controller <NUM> also uses the abstract topology to prune one or more of the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> during path calculations on the actual topology <NUM>. Interconnections between the controller <NUM> and other elements of the actual topology <NUM> are not shown in <FIG> in the interest of clarity.

<FIG> is a block diagram of an abstract topology <NUM> derived from the actual topology <NUM> shown in <FIG> according to some embodiments. The abstract topology <NUM> is represented as a graph that includes nodes representing the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and the border routers <NUM>-<NUM> that form links between the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. As discussed herein, the controller <NUM> uses the abstract topology to prune one or more of the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> during path calculations on the actual topology <NUM>. Some embodiments of the controller <NUM> determine measures of reachability for the nodes that represent the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and the border routers <NUM>-<NUM>. The measures of reachability indicate whether the domains <NUM>, <NUM>, <NUM>, <NUM>, <NUM> represented by the nodes are on a path from a source domain to a destination domain. In some embodiments, the measures of reachability include "betweenness centralities" that indicate how many pairs of domains use the domains associated with the nodes as a transit. Nodes associated with domains that are used by larger numbers of other domains as a transit have a higher betweenness centrality. Nodes associated with domains that are used by smaller numbers of other domains as a transit have a smaller betweenness centrality. Betweenness centralities are determined based on how many interconnections exist between the nodes and other nodes in the graph.

<FIG> is a block diagram of a <NUM>-stage Clos network <NUM> that supports BGP sessions between routers that are interconnected by a multi-access network according to some embodiments. The <NUM>-stage cost network <NUM> is implemented in a leaf-and-spine topology that interconnects leaf routers via one or more spines that include spine routers. In the illustrated embodiment, the <NUM>-stage Clos network <NUM> includes four leaf routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the leaf routers <NUM>-<NUM>") that are interconnected by spines <NUM>, <NUM>, <NUM>. The spine <NUM> includes the routers <NUM>, <NUM>, the spine <NUM> includes the routers <NUM>, <NUM>, <NUM>, <NUM>, and the spine <NUM> includes the routers <NUM>, <NUM>. The leaf routers <NUM>-<NUM> provide connections to one or more servers such as the servers <NUM>, <NUM>, <NUM> that are connected to the leaf router <NUM>. The routers and spines are assigned corresponding ASN <NUM>-<NUM>, <NUM>, <NUM>, <NUM>. In the <NUM> stage Clos network <NUM>, the leaf routers <NUM>-<NUM> not directly connected to the spines <NUM>, <NUM>. Instead, the leaf routers <NUM>, <NUM> are connected to a multi-access network such as the LAN <NUM>. Although not shown in <FIG> in the interest of clarity, the actual topology of the <NUM>-stage Clos network <NUM> can be used to generate an abstract topology analogous to the abstract topology <NUM> shown in <FIG>. The abstract topology that represents the <NUM>-stage Clos network <NUM> is used to prune domains during pathfinding, as discussed herein.

<FIG> is a block diagram of an abstract topology <NUM> that is derived from an actual topology of a network according to some embodiments. The abstract topology <NUM> includes nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the nodes <NUM>-<NUM>") that represent domains of the corresponding actual topology. The abstract topology <NUM> also includes nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the nodes <NUM>-<NUM>") that represent border routers on links between the domains corresponding to the nodes <NUM>-<NUM>. A controller <NUM> (such as the controller <NUM> shown in <FIG>) uses the abstract topology <NUM> to generate measures of reachability of nodes in the abstract topology <NUM>.

In the illustrated embodiment, the controller <NUM> determines reachability of the nodes for a path from a source domain associated with the node <NUM> to a destination domain associated with the node <NUM>. The controller <NUM> first determines whether the node <NUM> has a link to the node <NUM>. A link is present and therefore no temporary links are inserted.

The controller <NUM> runs a bi-connected component algorithm on the abstract topology <NUM>. The bi-connected component algorithm decomposes a graph representing the abstract topology <NUM> into a tree of bi-connected components that are referred to herein as clusters. The clusters are attached to each other at shared vertices that are referred to herein as articulation points. In the illustrated embodiment, the bi-connected component algorithm identifies the nodes <NUM>, <NUM> as articulation points <NUM>, <NUM> for the paths between the source domain and destination domain, which are represented by the nodes <NUM>, <NUM>, respectively. Based on the identified articulation points <NUM>, <NUM>, the bi-connected component algorithm identifies a first cluster including the nodes <NUM>-<NUM>, a second cluster including the nodes <NUM>-<NUM>, <NUM>, and a third cluster including the nodes <NUM>, <NUM>. The bi-connected component algorithm identifies the clusters that form a union between the nodes <NUM>, <NUM>, which in this case is the second cluster. The nodes in the second cluster are therefore considered reachable and provide transit from the node <NUM> to the node <NUM> or from the node <NUM> to the node <NUM>. The nodes <NUM>, <NUM>, <NUM> are not transits along the path from the node <NUM> to the node <NUM> (or vice versa) and can therefore be safely pruned from path calculations between the nodes <NUM>, <NUM>.

<FIG> is a block diagram of a first embodiment of a modified abstract topology <NUM> that is derived from an actual topology of the network according to some embodiments. The modified abstract topology <NUM> is formed based on the abstract topology <NUM> shown in <FIG> and therefore includes the nodes <NUM>-<NUM> that represent domains of the corresponding actual topology. The modified abstract topology <NUM> also includes the nodes <NUM>-<NUM> that represent border routers on links between the domains corresponding to the nodes <NUM>-<NUM>. The controller <NUM> uses the modified abstract topology <NUM> to generate measures of reachability of nodes in the modified abstract topology <NUM>.

In the illustrated embodiment, the controller <NUM> determines reachability of the nodes for a path from a source domain associated with the node <NUM> to a destination domain associated with the node <NUM>. The controller <NUM> first determines whether the node <NUM> has a link to the node <NUM>. No link is present in the underlying abstract topology, e.g., the abstract topology <NUM> shown in <FIG>. The controller <NUM> therefore modifies the abstract topology <NUM> by adding a temporary link <NUM> between the nodes <NUM>, <NUM>.

The controller <NUM> runs a bi-connected component algorithm on the modified abstract topology <NUM>. In the illustrated embodiment, the bi-connected component algorithm identifies the node <NUM> as an articulation point <NUM> for the paths between the source domain and destination domain, which are represented by the nodes <NUM>, <NUM>, respectively. Based on the identified articulation point <NUM>, the bi-connected component algorithm identifies a first cluster including the nodes <NUM>-<NUM>, <NUM> and a second cluster including the nodes <NUM>, <NUM>. The bi-connected component algorithm identifies the clusters that form a union between the nodes <NUM>, <NUM>, which in this case is the first cluster. The nodes in the first cluster are therefore considered reachable and provide transit from the node <NUM> to the node <NUM> (or vice versa). The node <NUM> is not a transit along the path from the node <NUM> to the node <NUM> (or vice versa) and can therefore be safely pruned from path calculations between the nodes <NUM>, <NUM>.

<FIG> is a block diagram of a second embodiment of a modified abstract topology <NUM> that is derived from an actual topology of the network according to some embodiments. The modified abstract topology <NUM> is formed based on the abstract topology <NUM> shown in <FIG> and therefore includes the nodes <NUM>-<NUM> that represent domains of the corresponding actual topology. The modified abstract topology <NUM> also includes the nodes <NUM>-<NUM> that represent border routers on links between the domains corresponding to the nodes <NUM>-<NUM>. The controller <NUM> uses the modified abstract topology <NUM> to generate measures of reachability of nodes in the modified abstract topology <NUM>.

The controller <NUM> runs a bi-connected component algorithm on the modified abstract topology <NUM>. In the illustrated embodiment, the bi-connected component algorithm identifies the node <NUM> as an articulation point <NUM> for the paths between the source domain and destination domain, which are represented by the nodes <NUM>, <NUM>, respectively. Based on the identified articulation point <NUM>, the bi-connected component algorithm identifies a first cluster including the nodes <NUM>, <NUM> and a second cluster including the nodes <NUM>-<NUM>. The bi-connected component algorithm identifies the clusters that form a union between the nodes <NUM>, <NUM>, which in this case is the second cluster. The nodes in the second cluster are therefore considered reachable and provide transit from the node <NUM> to the node <NUM> (or vice versa). The node <NUM> is not a transit along the path from the node <NUM> to the node <NUM> (or vice versa) and can therefore be safely pruned from path calculations between the nodes <NUM>, <NUM>.

<FIG> is a block diagram of a third embodiment of a modified abstract topology <NUM> that is derived from an actual topology of the network according to some embodiments. The modified abstract topology <NUM> is formed based on the abstract topology <NUM> shown in <FIG> and therefore includes the nodes <NUM>-<NUM> that represent domains of the corresponding actual topology. The modified abstract topology <NUM> also includes the nodes <NUM>-<NUM> that represent border routers on links between the domains corresponding to the nodes <NUM>-<NUM>. The controller <NUM> uses the modified abstract topology <NUM> to generate measures of reachability of nodes in the modified abstract topology <NUM>.

The controller <NUM> runs a bi-connected component algorithm on the modified abstract topology <NUM>. In the illustrated embodiment, the bi-connected component algorithm identifies the nodes <NUM>, <NUM> as articulation points <NUM>, <NUM>, respectively, for the paths between the source domain and destination domain, which are represented by the nodes <NUM>, <NUM>, respectively. Based on the identified articulation points <NUM>, <NUM>, the bi-connected component algorithm identifies a first cluster including the nodes <NUM>, <NUM>, a second cluster including the nodes <NUM>-<NUM>, <NUM>, and a third cluster including the nodes <NUM>, <NUM>. The bi-connected component algorithm identifies the clusters that form a union between the nodes <NUM>, <NUM>, which in this case is the second cluster. The nodes in the second cluster are therefore considered reachable and provide transit from the node <NUM> to the node <NUM> (or vice versa). The nodes <NUM>, <NUM> are not transits along the path from the node <NUM> to the node <NUM> (or vice versa) and can therefore be safely pruned from path calculations between the nodes <NUM>, <NUM>.

<FIG> is a block diagram of an abstract topology <NUM> that includes information indicating mappings associated with paths through the abstract topology <NUM> according to some embodiments. The abstract topology includes domains <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the domains <NUM>-<NUM>") that are interconnected by border routers <NUM>, <NUM>, <NUM> (collectively referred to herein as "the border routers <NUM>-<NUM>").

Mappings included in the abstract topology <NUM> include information representing the domains <NUM>-<NUM> along different paths. The mapping information is represented by dotted lines <NUM> (only one indicated by a reference numeral in the interest of clarity). In the illustrated embodiment, the mapping <NUM> includes information representing domains <NUM>, <NUM> along a path that connects the source domain <NUM> and the destination domain <NUM>. The mapping <NUM> includes information representing domains <NUM>-<NUM> along a path that connects the source domain <NUM> and the destination domain <NUM>. The mapping <NUM> includes information representing domains <NUM>, <NUM> along a path that connects the source domain <NUM> and the destination domain <NUM>. The mapping <NUM> includes information representing domains <NUM>-<NUM> along a path that connects the source domain <NUM> and the destination domain <NUM>. The mapping <NUM> includes information representing domains <NUM>-<NUM> along a path that connects the source domain <NUM> and the destination domain <NUM>. The mapping <NUM> includes information representing domains <NUM>, <NUM> along a path that connects the source domain <NUM> and the destination domain <NUM>. Some embodiments of the mappings <NUM>-<NUM> are determined based on domain reachabilities associated with the different paths. For example, the mappings <NUM>-<NUM> can be determined using a bi-connected component algorithm as discussed herein with regard to <FIG>.

Rankings are assigned to the domains <NUM>-<NUM> based on the mappings <NUM>-<NUM>. In the illustrated embodiment, the ranking for each of the domains <NUM>-<NUM> is equal to the number of mappings <NUM>-<NUM> that include the corresponding domain as a transit domain. The domain <NUM> has a ranking of three, the domain <NUM> has a ranking of five, the domain <NUM> has a ranking of five, and the domain <NUM> has a ranking of three. As discussed herein, the rankings of the domains <NUM>-<NUM> are used to selectively prune one or more of the domains <NUM>-<NUM>, to modify preferences or weights associated with links between the domains <NUM>-<NUM>, or a combination thereof.

<FIG> is a flow diagram of a method <NUM> of ranking domains in an abstract topology and a method <NUM> of selectively pruning or modifying preferences of the domains in the abstract topology based on the domain rankings according to some embodiments. The methods <NUM>, <NUM> are implemented in some embodiments of the network including the actual topology <NUM> shown in <FIG> based on the abstract topology <NUM> shown in <FIG>, the <NUM>-stage Clos network <NUM> shown in <FIG>, the network having an actual topology associated with the abstract topology <NUM> shown in <FIG>, and the network having an actual topology associated with the abstract topology <NUM> shown in <FIG>.

The method <NUM> is performed prior to a request to identify paths in the actual topology. At block <NUM>, an abstract topology is generated from an actual topology of a network. Generating the abstract topology includes identifying domains and border routers that interconnect the domains in the actual network. The abstract topology includes nodes that represent the domains and the border routers, e.g., as shown in <FIG>.

At block <NUM>, reachability of the domains along a path in the abstract topology is determined. As discussed herein, reachability is determined using a bi-connected component algorithm. If a source node does not have a link to a destination node for the path, one or more links are added between the source node and the destination node prior to executing the bi-connected component algorithm to determine reachability of nodes along paths between the source node and the destination node.

At block <NUM>, ranks are assigned to the domains in the abstract topology. As discussed herein, the ranks indicate betweenness centralities of the nodes associated with the domains in the abstract topology. The domain ranks or rankings are then stored for subsequent use.

The method <NUM> is performed in response to receiving a request to identify paths in the actual topology. At block <NUM>, the request is received. At block <NUM>, domains are selectively pruned (or preferences associated with the domains are selectively modified) during pathfinding on the actual topology. The domains are selectively pruned based on information in the abstract topology including reachability information and ranks that indicate betweenness centralities of the nodes.

At block <NUM>, a pathfinding algorithm determines, identifies, or selects a path in the actual topology from the source node to the destination node. Once identified, the network is configured to support the transmission and reception of information conveyed over the path between the source node and the destination node. In some embodiments, a router at the source node and a router at the destination node are configured to exchange IP packets over the path between the source node and the destination node.

<FIG> is a flow diagram of a method <NUM> of generating mappings between source and destination nodes in an abstract topology of a network according to some embodiments. The method <NUM> is implemented in a controller that generates some embodiments of the mappings <NUM>-<NUM> shown in <FIG>, as well as mappings for some embodiments of the abstract topology <NUM> shown in <FIG> (which is derived from the actual topology <NUM> shown in <FIG>), an abstract topology representing an actual topology of the <NUM>-stage Clos network <NUM> shown in <FIG>, and the abstract topology <NUM> shown in <FIG>.

The method <NUM> begins at the block <NUM>. At block <NUM>, the controller selects a source node from the set of nodes that represent domains in the abstract topology. At block <NUM>, the controller selects a destination node from the set of nodes that represent the domains in the abstract topology. At decision block <NUM>, the controller determines whether a link exists between the source node and the destination node. If not, the method <NUM> flows to the block <NUM> and the controller inserts a temporary link between the source node and the destination node. The method <NUM> then flows to the block <NUM>. If a link already exists between the source node and the destination node, the method <NUM> flows directly from the decision block <NUM> to the block <NUM>.

The illustrated embodiment of the method <NUM> identifies the presence of links between source and destination nodes in a full mesh manner so that all nodes are considered both source nodes and destination nodes. For example, the method <NUM> uses a first node as a source node and a second node as a destination node in one iteration and considers the second node as the source node and the first node as the destination node in another iteration. Some embodiments of the method <NUM> exploit the symmetry of the network to reduce the computational effort by considering the case where the first node is the source node and the second node is the destination node and subsequently skipping the case where the first node is the destination node and the second node is the source node because these cases refer to the same link between the first and second nodes. Criteria for deciding whether to include a node as a source node or destination node can be incorporated into one or more of the blocks <NUM>, <NUM>, <NUM> to implement these (and other) techniques to exploit symmetries in source/destination nodes or other characteristics of the nodes.

At block <NUM>, the controller identifies one or more clusters of nodes in the abstract topology using a bi-connected component algorithm. As discussed herein, the bi-connected component algorithm decomposes a graph representing the abstract topology into clusters that are attached to each other at articulation points. Based on the articulation points for the graph (which may include temporary links), the bi-connected component algorithm identifies clusters including different subsets of the nodes. The nodes in the subsets that form a union between the source and destination nodes are considered reachable and provide transit between the source and destination nodes. If temporary links were inserted (at block <NUM>), the temporary links are removed at block <NUM>. At block <NUM>, the controller captures the mapping between the source node and the destination node. The mapping includes information representing the reachable nodes to provide transit between the source and destination nodes.

At decision block <NUM>, the controller determines whether there are additional destination nodes associated with the source node. If so, the method <NUM> flows to block <NUM> and a new destination node is selected. If not, the method <NUM> flows to decision block <NUM>. The controller determines (at decision block <NUM>) whether there are additional source nodes in the abstract topology. If so, the method <NUM> flows to block <NUM> and a new source node is selected. Otherwise, the method <NUM> flows to block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a method <NUM> of selectively pruning or modifying weights of edges in an actual topology based on rankings of nodes in an abstract topology of a network according to some embodiments. The method <NUM> is implemented in a controller such as the controller <NUM> that performs pathfinding in the actual topology <NUM> shown in <FIG> based on the abstract topology <NUM> shown in <FIG>, a controller that performs pathfinding within an actual topology of the <NUM>-stage Clos network <NUM> shown in <FIG>, a controller that performs pathfinding in an actual topology associated with the abstract topology <NUM> shown in <FIG>, and a controller that performs pathfinding in an actual topology associated with the abstract topology <NUM> shown in <FIG>. The controller performs the method <NUM> in conjunction with executing a pathfinding algorithm, concurrently with executing the pathfinding algorithm, or in response to initiating execution of the pathfinding algorithm for traversals between a source node and a destination node in a network.

At block <NUM>, the controller selects an edge from a graph that represents the abstract topology for the actual topology used during the pathfinding operation. The edge is connected to a node in the graph that represents a domain in the abstract topology. The domain is a candidate for pruning or preferencing, e.g., by modifying a weight of the edge. In some embodiments, the edge is associated with a border router that connects to the domain.

At decision block <NUM>, the controller determines whether the domain is reachable. As discussed herein, reachability of the domain is determined using a bi-connected component algorithm to identify reachable domains on paths between the source node and the destination node. If the domain is not reachable along a path between the source node and the destination node, the method flows to the block <NUM> and the edge (or the domain) is pruned and the pathfinding algorithm does not consider the domain. If the domain is reachable, the method <NUM> flows to the block <NUM>.

At block <NUM>, the controller determines rankings of the source node and the next node in the path that is being assessed by the pathfinding algorithm. As discussed herein, the rankings are determined based on how many mappings of paths between the source node and the destination node in the graph that represents the abstract topology include the corresponding node as a transit node.

At decision block <NUM>, the controller determines whether the ranking of the source node is greater than the ranking of the next node. If so, the domain should be considered by the pathfinding algorithm during traversals so the method <NUM> flows to the block <NUM> and the edge is not pruned or modified. The controller also determines whether the next node is the destination node. If so, the domain should be considered by the pathfinding algorithm (regardless of the rank of the destination node) and method <NUM> flows to block <NUM>. If the rank of the next node is less than or equal to the source node rank, and the next node is not the destination node, the method <NUM> flows to the block <NUM>.

At block <NUM>, the controller prunes or modifies a weight of the edge. In some embodiments, the controller performs hard pruning and does not permit the edge (or link) to be expanded pondering the path traversal. Pruning the edge constrains the path to follow the higher ranking, core, transit links through the graph. In some embodiments, the controller modifies the weight of the edge to reduce a preference (or increase a cost) associated with paths that traverse the edge. For example, the controller can modify the weight of the edge relative to the domain rank to give the link a lower preference for traversal, e.g., as determined by a shortest path first pathfinding algorithm. Paths that include the lower preference link may be used as last resort paths if no other paths are available. Thus, increasing the cost of the link by modifying the weight of the corresponding edge causes the pathfinding algorithm to avoid evaluating or traversing the link until lower-cost links have been exhausted, thereby increasing the likelihood that a lower cost traffic engineer path is found sooner.

<FIG> is a block diagram of a network function virtualization (NFV) architecture <NUM> according to some embodiments. The NFV architecture <NUM> is used to implement some embodiments of a network that has the actual topology <NUM> shown in <FIG> and the abstract topology <NUM> shown in <FIG>, the <NUM>-stage Clos network <NUM> shown in <FIG>, a network associated with the abstract topology <NUM> shown in <FIG>, and a network associated with the abstract topology <NUM> shown in <FIG>. The NFV architecture <NUM> includes hardware resources <NUM> including computing hardware <NUM>, storage hardware <NUM>, and network hardware <NUM>. The computing hardware <NUM> is implemented using one or more processors, the storage hardware <NUM> is implemented using one or more memories, and the network hardware <NUM> is implemented using one or more transceivers, transmitters, receivers, interfaces, and the like.

A virtualization layer <NUM> provides an abstract representation of the hardware resources <NUM>. The abstract representation supported by the virtualization layer <NUM> can be managed using a virtualized infrastructure manager <NUM>, which is part of the NFV management and orchestration (M&O) module <NUM>. Some embodiments of the manager <NUM> are configured to collect and forward performance measurements and events that may occur in the NFV architecture <NUM>. For example, performance measurements may be forwarded to an orchestrator (ORCH) <NUM> implemented in the NFV M&O <NUM>. The hardware resources <NUM> and the virtualization layer <NUM> may be used to implement virtual resources <NUM> including virtual computing resources <NUM>, virtual storage resources <NUM>, and virtual networking resources <NUM>.

Virtual networking functions (VNF1, VNF2, VNF3) run over the NFV infrastructure (e.g., the hardware resources <NUM>) and utilize the virtual resources <NUM>. For example, the virtual networking functions (VNF1, VNF2, VNF3) may be implemented using virtual machines supported by the virtual computing resources <NUM>, virtual memory supported by the virtual storage resources <NUM>, or virtual networks supported by the virtual network resources <NUM>. Element management systems (EMS1, EMS2, EMS3) are responsible for managing the virtual networking functions (VNF1, VNF2, VNF3). For example, the element management systems (EMS1, EMS2, EMS3) may be responsible for fault and performance management. In some embodiments, each of the virtual networking functions (VNF1, VNF2, VNF3) is controlled by a corresponding VNF manager <NUM> that exchanges information and coordinates actions with the manager <NUM> or the orchestrator <NUM>.

The NFV architecture <NUM> may include an operation support system (OSS)/business support system (BSS) <NUM>. The OSS/BSS <NUM> deals with network management including fault management using the OSS functionality. The OSS/BSS <NUM> also deals with customer and product management using the BSS functionality. Some embodiments of the NFV architecture <NUM> use a set of descriptors <NUM> for storing descriptions of services, virtual network functions, or infrastructure supported by the NFV architecture <NUM>. Information in the descriptors <NUM> may be updated or modified by the NFV M&O <NUM>.

The NFV architecture <NUM> implements network slices that provide control plane functions or user plane functions. A network slice is a complete logical network that provides communication services and network capabilities, which can vary from slice to slice. User equipment can concurrently access multiple slices that support multiple service flows between a core network and the user equipment. Some embodiments of user equipment provide Network Slice Selection Assistance Information (NSSAI) parameters to the network to assist in selection of a slice instance for the user equipment. A single NSSAI may lead to the selection of several slices. The NFV architecture <NUM> can also use device capabilities, subscription information and local operator policies to do the selection. An NSSAI is a collection of smaller components, Single-NSSAIs (S-NSSAI), which each include a Slice Service Type (SST) and possibly a Slice Differentiator (SD). Slice service type refers to an expected network behavior in terms of features and services (e.g., specialized for broadband or massive IoT), while the slice differentiator can help selecting among several network slice instances of the same type, e.g. to isolate traffic related to different services into different slices.

Claim 1:
A method comprising:
generating, at a processor, an abstract topology that represents domains in an actual topology of a network and border routers that interconnect the domains in the actual topology (<NUM>); and
pruning, at the processor and based on the abstract topology and based on respective measures of reachability of the domains and respective ranks of the domains, at least one of the domains from the actual topology during path calculations on the actual topology,
wherein the respective ranks of the domains are indicative of respective numbers of pairs of domains that use the respective domains as a transit domain.