Patent Description:
This disclosure relates to computer networks and, more specifically, to segment routing for computer networks.

A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form.

Certain devices within the network, such as routers, use routing protocols to exchange and accumulate topology information that describes available routes through the network. This allows a router to construct its own routing topology map of the network. Upon receiving an incoming data packet, the router examines information within the packet and forwards the packet in accordance with the accumulated topology information.

Many routing protocols fall within a protocol class referred to as Interior Gateway Protocol (IGP), in which flooding-based distribution mechanisms are used to announce topology information to routers within the network. These routing protocols typically rely on routing algorithms that require each of the routers to have synchronized routing topology information for a given domain, referred to as the IGP area or domain. The contents of a Link State Database (LSDB) or a Traffic Engineering Database (TED) maintained in accordance with a link state routing protocol have the scope of an IGP domain. IGP routing protocols typically require that all routers in the IGP routing domain store, within an internal LSDB or TED, all of the routing information that has been distributed according to the IGP protocol. In operation, each router typically maintains an internal LSDB and/or TED and scans the entire database at a defined interval to generate and output link state messages to synchronize the database to neighboring routers within the routing domain. In this way, link state is propagated across the entire routing domain and stored in full at each router within the domain.

Packet-based networks use label switching protocols for traffic engineering and other purposes. Multi-Protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks according to the routing information maintained by the routers in the networks. By utilizing MPLS protocols, such as the Label Distribution protocol (LDP), the Resource Reservation Protocol (RSVP) with Traffic Engineering extensions (RSVP-TE), or the Segment Routing (SR) extension, label switching routers can forward traffic along a particular path through a network to a destination device, i.e., a Label Switched Path (LSP), using labels prepended to the traffic. An LSP defines a distinct path through the network to carry MPLS packets from the source device to a destination device. Using a MPLS protocol, each router along an LSP allocates a label in association with the destination and propagates the label to the closest upstream router along the path. Routers along the path add (push), remove (pop) or swap the labels and perform other MPLS operations to forward the MPLS packets along the established path.

Routers may employ segment routing techniques to leverage the Source Packet Routing in Networking (SPRING) paradigm. With segment routing, a head-end network node can steer a packet flow along any path by augmenting the header of a packet with an ordered list of segment identifiers for implementing a segment routing policy. Segment routing can reduce, and in some cases eliminate, intermediate per-flow states that are inherent in conventional MPLS routing. <CIT> discusses tactical traffic engineering based on segment routing policies. <CIT> discusses path computation in a segment routing network.

The invention is defined by the independent claims and particular embodiments are set out in the independent claims. Various optional examples are set out in the dependent claims. In general, techniques are described for specifying and applying acceptable deviations from initial path computation constraints used for computing each path in a multipath solution for a segment routing (SR) policy. Multiple paths computed and provisioned to implement an SR policy are referred to as multipaths, and these may, in some examples, enable equal-cost multipath (ECMP)-based load balancing of the SR policy across the multiple paths. Moreover, the SR policy may specify one or more path computation constraints that limit the acceptable paths for the SR policy from source(s) to destination(s).

In some cases, a network topology change or other network event may cause an installed multipath for an SR policy to have one or more paths that no longer satisfy the initial policy constraints, i.e., those policy constraints initially used to compute the multipath. In some examples, a network operator, script, or automated operation may specify acceptable path computation deviations from the policy constraints of an SR policy should such a network event occur. The multipath computed and provisioned for the SR policy will meet the initial policy constraints of the SR policy on the network prior to the network topology change. However, in the event of a recomputation event for the SR policy, such as a network topology change, a controller (e.g., SDN network controller) for the SR-domain may determine whether the installed multipath meets a relaxed version of the initial policy constraints, the relaxed version being defined by the specified acceptable deviations for the SR policy. If the installed multipath meets the relaxed version of the initial policy constraints, the controller may eschew recomputing a multipath for the SR policy in order that the multipath provisioned for the SR policy may again meet the initial policy constraints. Instead of recomputing the multipath for the SR policy, the controller may allow the multipath to operate, at least temporarily, in a degraded condition that is nevertheless acceptable to the network operator, e.g., in accordance with the specified acceptable deviations from the policy constraints for the SR policy.

The techniques described herein may provide one or more technical advantages that realize at least one practical application. For example, the techniques may allow network operators to externally program the path computation to provide a range of intents for one SR policy, the range of intents being defined by the constraint space permitted by the various deviations from the policy constraints. This allows the network operator to balance network churn and path optimization level. For example, applying a relaxed version of the policy constraints when considering an SR policy may reduce churn within the network, i.e., reduce resources expended to implement changes to the configuration of paths within the network. As another example, the techniques may permit services to operate in a more predictable degraded condition, and a degraded condition may not automatically trigger a competition among services. As another example, acceptable deviations for an SR policy may be specified, or allowed, according to service tiers, which may be provided to different users. For example, the techniques described herein may enable better service tiers to be configured to have lesser or no acceptable deviations from the policy constraints of an SR policy, while lesser service tiers may be configured to permit more degraded operation of a service (on the SR policy) with correspondingly larger acceptable deviations from the policy constraints of an SR policy. This may result in better network utilization. As another example, the techniques may facilitate network solutions such that, when a solution for all SR policies cannot be found, the set of acceptable intents enable the path computation to find a solution with the minimum set of deviations. The techniques may enable service providers and other network operators to engineer, with precision and flexibility, the traffic in their networks to improve service quality for their customers and reduce costs.

The details of one or more embodiments of the disclosure are set forth in the accompanying drawings and the description below.

Segment routing (SR), which may also be referred to as source packet routing or source packet routing in networking (SPRING), is a control-plane architecture that enables an ingress router to steer a packet through a specific set of network nodes and links in a network without relying on intermediate network nodes in the network to determine the path it should take. Fundamental to SPRING forwarding is the notion of Segment Identifiers (SIDs). Segment routing and SIDs are described in further detail in <NPL>; <NPL>; and <NPL>. "Segment Routing Policy Architecture" defines an SR Policy as "a framework that enables instantiation of an ordered list of segments on a node for implementing a source routing policy with a specific intent for traffic steering from that node.

<FIG> is a block diagram illustrating an example system <NUM> having network <NUM> and controller <NUM> configured to operate in accordance with techniques described in this disclosure. Network <NUM> one or more computer networks (e.g., a set of interconnected L2 / L3 networks) and, in some examples, may be a wide area network. Network <NUM> may include or more autonomous systems, data centers, branch offices, private network, public networks, cloud networks, or other types of networks.

Network <NUM> includes network nodes <NUM> that are SR-enabled and constitute an SR-domain. Network nodes <NUM> may be alternatively referred to as "SR nodes. " The SR-domain may include any number of network nodes <NUM>. Each of network nodes <NUM> may represent a router, a switch, or other network device that is capable of performing segment routing. Network <NUM> may include many other network devices that are not part of an SR-domain or otherwise not SR-enabled, such as other routers or switches.

Using segment routing, network nodes <NUM> forward network packets of packet flows from sources to destinations along segment routing paths that are encoded as lists of segment identifiers that augment network packet headers and are used by network nodes <NUM> for identifying the next segment to forward each network packet. Sources of network packets received and forwarded by network nodes <NUM> may include one or more devices (not shown) and/or any public or private network or the Internet. The destinations of the network packets being forwarded by network nodes <NUM> may include one or more destination devices and/or network that may include LANs or wide area networks (WANs) that include a plurality of devices. For example, destination devices may include personal computers, laptops, workstations, personal digital assistants (PDAs), wireless devices, network-ready appliances, file servers, print servers or other devices that receive network packets from sources.

Segment routing has multiple types of segments. These include prefix segments that represent the shortest path (e.g., according to IGP metrics) between any of network nodes <NUM> and a specified prefix. Prefix segments include node segments, where the specified prefix identifies a particular network node <NUM> (e.g., the loopback address of the particular network node <NUM>), and anycast segments, which enforced the Equal Cost Multipath (ECMP)-aware shortest path forwarding towards the closest network node <NUM> of an anycast group. An anycast group includes one or more network nodes <NUM>, and the specified prefix can be advertised by any of the network nodes <NUM> in the anycast group. A segment may be referred to by its Segment Identifier (SID).

Other segment types include adjacency segments, which are IGP adjacencies between network nodes <NUM>, binding segments, and adjacency sets. A binding segment may represent a tunnel through network nodes <NUM>. The tunnel may include a SR policy. An SR Policy may itself implement or be implemented in network <NUM> using a multipath. An adjacency set represents multiple adjacencies and the same SID is used for the multiple adjacencies. This is the adjacency parallel version of anycast SID, where the same SID indicates for multiple nodes in the network. In general, SIDs that can be used to steer traffic simultaneously to multiple paths that give rise to preferable SID reduction or minimization solutions. Adjacency sets and anycast SIDs are important such SIDs.

In some examples, network nodes <NUM> apply segment routing using a Multiprotocol Label Switching (MPLS) architecture. In such examples, each segment is encoded as an MPLS label and an SR Policy may be instantiated as a label stack appended to network packets. The active segment is on the top of the label stack. Upon completion of a segment, a network node <NUM> pops the corresponding label from the label stack.

In some examples, network nodes <NUM> apply segment routing using an IPv6 architecture and the SR Header (SRH). In such examples, an instruction may be associated with a segment and encoded as an IPv6 address that maps to a SID. An SR Policy is instantiated as an ordered list of SIDs in the routing header. The Destination Address (DA) of the packet indicates the active segment. The SegmentsLeft (SL) pointer in the SRH indicates the next active segment. When a network node <NUM> completes a segment, the network node decrements the SL pointer and copies the next segment to the destination address. A network packet is steered on an SR Policy is augmented with the corresponding SRH for the SR Policy.

In some examples, network nodes <NUM> may operate as label switching routers (LSRs) to distribute labels to neighboring LSRs within network <NUM>. For example, there may be multiple different label types including "adjacency" labels and "node" labels. Such labels may be or otherwise correspond to segment identifiers that locally or globally identify a segment in network <NUM>. To forward a packet through network <NUM>, network nodes <NUM> may push, pop, or swap one or more labels in a list of segment identifiers that is applied to the packet as it is forwarded through the network. The label stack may encode the topological and service source route of the packet under the SR policy.

An adjacency label may have a local semantic to a particular segment routing node, such as one of network nodes <NUM>. In particular, an adjacency label steers traffic onto an adjacency (e.g., communication link and/or interface) or set of adjacencies. Thus, an adjacency label may be related to a particular network node <NUM>. To use an adjacency label, a particular network node <NUM> may initially assign the adjacency label to a particular adjacency and advertise the adjacency label to other routers in the segment routing domain using an IGP, such as Intermediate System - Intermediate System (ISIS) or Open Shortest Path First (OSPF). The particular network node <NUM> may be the only network node in the SR domain to use the particular adjacency label. When a network node <NUM> forwards a packet using the adjacency label, the network node <NUM> may cause the packet to use the adjacency for the particular network node <NUM> associated with the adjacency label. In this way, adjacency labels may be used to establish onehop tunnels for segments.

A node label, by contrast, may have a global semantic within the SR domain. That is, each of network node <NUM> may be assigned a defined node label range (commonly referred to as Segment Routing Global Block (SRGB)) that is unique to each network node <NUM> within the SR domain. An operator of network <NUM> may ensure unique allocation of the different node label ranges from a global range to different network nodes <NUM>. In addition to a node label range, each particular network node <NUM> may also have a specific node identifier that uniquely identifies the particular network node <NUM> in the SR domain. Each network node <NUM> may advertise its corresponding node identifier and node label range to other network nodes <NUM> in the SR domain using, e.g., an IGP.

Based on routes determined using, e.g., shortest path routing, each of network node <NUM> may configure its forwarding state to implement SR using MPLS or using an IPv6 architecture and the SR Header (SRH), as described above. Using MPLS for instance, each of network nodes <NUM> may perform path selection using topology information learned by way of IGP to compute a shortest path within network <NUM> on a hop-by-hop basis based on the routing information maintained by the network nodes <NUM>. Each of network nodes <NUM> may then select a next hop along the locally computed shortest path and install forwarding information associated with the selected next hop in a forwarding plane of the network node, wherein the forwarding information identifies a network interface to be used when forwarding traffic and one or more labels to be applied when forwarding the traffic out the interface. The network nodes <NUM> use the next hops with the assigned labels to forward traffic hop-by-hop.

System <NUM> may implement segment routing using distributed or centralized control. With distributed control, network nodes <NUM> allocate and signal segments using routing protocols, such as IS-IS or OSPF or Border Gateway Protocol (BGP). A network node <NUM> individually decides to steer packets on an SR Policy that is implemented using one or more candidate paths. The network node <NUM> individually computes the SR Policy. With distributed control, controller <NUM> may not be part of system <NUM>. In the distributed control scenario, network nodes <NUM> are computing devices that may compute one or more lists of SIDs that satisfy each path of a plurality of paths for implementing an SR policy. In general, a path represents a different sequence of links connecting pairs of the network nodes from a source to a destination. A multipath is a plurality of such paths.

With centralized control, controller <NUM> allocates and signals segments. Controller <NUM> decides the network nodes <NUM> on which to steer packets mapped to SR policies. Controller <NUM> applies path computation to compute candidate paths for satisfying SR policies. In addition, controller <NUM> programs network <NUM>, in particular network nodes <NUM>, with forwarding information for implementing the candidate paths using lists of SIDs. Controller <NUM> may program network nodes <NUM> using Network Configuration Protocol (NETCONF), Path Computation Element Communication Protocol (PCEP), BGP, or other protocols. Controller <NUM> may represent one or more SR controllers and may be a WAN controller that is manages not just the SR domain but path computation, traffic engineering, provisioning, and other network control tasks for an operator of network <NUM>. Controller <NUM> may include or represent a path computation element and may be alternatively referred to as a PCE controller or SDN controller. Controller <NUM> may discover the SIDs instantiated at the various network nodes <NUM> and discover the sets of local (SRLB) and global (SRGB) labels that are available at the various network nodes <NUM>. Controller <NUM> may listen for other topology information using routing protocols. In the centralized control scenario, controller <NUM> is a computing device that may compute one or more lists of SIDs that satisfy each path of a plurality of paths (referred to as "multipath") for implementing an SR policy. Each of the paths is from a source for the multipath to a destination for the multipath. Controller <NUM> may compute the multipath from one or more sources to one or more destinations in order to realize the SR policy. Having computed the one or more lists of SIDs, controller <NUM> may then program network <NUM> to forward network traffic based at least on the one or more lists of SIDs.

Although the techniques of this disclosure are described primarily with respect to operations performed by controller <NUM> applying centralized control, the techniques are similarly applicable to a distributed control model in which network nodes <NUM> allocate and signal segments and perform other operations described herein with respect to controller <NUM>. Both controller <NUM> and network nodes <NUM> may be alternatively referred to as control devices or computing devices.

One or more lists of SIDs satisfy each path of a plurality of paths for implementing an SR policy when traffic forwarded by the network nodes <NUM> using a list of SIDs, from the one or more lists of SIDs, is forwarded along one of the paths and is not forwarded on a path that is not one of the paths. Moreover, the one or more lists of SIDs are satisfactory when they make complete use of the plurality of paths, i.e., network nodes <NUM> can forward traffic along any of the paths using the one or more lists of SIDs. For example, a first list of SIDs may cause a network packet steered to the SR policy to traverse a first path of the plurality of paths, while a second list of SIDs may cause a network packet steered to the SR policy to traverse a second path of the plurality of paths, or a single list of SIDs may cause a network packet steered to the SR policy to traverse both a first path and a second path of the plurality of paths. The network nodes can use weighted or non-weighted equal-cost multipath (ECMP) to forward traffic to a next segment and/or to select one of the one or more lists of SIDs.

In accordance with techniques of this disclosure, a network operator, script or other automated function such as a network management system (NMS) may specify acceptable path computation deviations from the segment routing (SR) policy constraints used for computing each path in a multipath solution for an SR policy. An SR policy may specify one or more policy constraints that limit the acceptable paths for the SR policy to those that satisfy the policy constraints. An SR policy, extended as described herein, specifies both initial policy constraints that must be satisfied for an initial path computation as well as acceptable deviations, in the form of relaxed policy constraints, that relax the initial policy constraints to in some cases allow controller <NUM> and/or network nodes <NUM> to avoid triggering path recomputation.

In some cases, a change in the network topology of network <NUM> to a modified network topology may cause an installed multipath for an SR policy to have one or more paths that no longer satisfy the policy constraints initially used to compute the multipath. As such, controller <NUM> may determine whether the installed multipath meets the relaxed policy constraints. To determine the paths of the installed multipath, which is defined using the one or more lists of SIDs for the plurality of paths initially computed to implement the SR policy and which satisfied the initial constraints, controller <NUM> may expand each list of SIDs (in the one or more lists of SIDs) into the plurality of paths on the modified network topology. In other words, controller <NUM> determines the paths of the multipath after the change in the network topology, which may be different from what was originally computed.

For example, if a link in network <NUM> fails and controller <NUM> initially computed a list of SIDs based on one or more paths of a multipath that traversed that now failed link, a node of network nodes <NUM> may forward traffic steered to the SR policy on a modified set of paths for those one or more paths in order to avoid the failed link, the node forwarding the traffic according to local routing information of the node and the SR header of the traffic. Controller <NUM> computes this modified set of paths by using the modified network topology to expand the list of SIDs to determine the modified set of paths. By expanding all of the lists of SIDs, controller <NUM> may determine the new multipath as all of the modified sets of paths for the SR policy in the modified network topology for network <NUM>. Put another way, controller <NUM> expands each list of segment identifiers to compute each path in the multipath that would be used for traffic by network nodes <NUM> in the modified network topology.

If this new multipath, as the already-installed multipath in the modified topology according to previously computed lists of SIDs, is acceptable under the relaxed policy constraints, then controller <NUM> eschews recomputing a multipath for the SR policy in order for the SR policy to again meet the initial policy constraints. Instead, controller <NUM> may allow the multipath to operate, at least temporarily, in a degraded condition.

In some examples, the relaxed policy constraints are specified using a list of different, acceptable sets of path computation deviations (or more simply, "deviations"). This list may be ordered by the network operator by preference and controller <NUM> may evaluate each set of deviations, sequentially and in order, as the relaxed policy constraints for a multipath. Each set of deviations may also be associated with a recomputation policy that specifies an action (a "recomputation policy action") for controller <NUM> if the new multipath is determined by controller <NUM> to be acceptable for the set of deviations. In response identifying the first set of deviation that accepts the multipath in this way, controller <NUM> performs the action specified by the associated recomputation policy for that set of deviations. Example actions include failing the multipath, keeping the current multipath (eschewing recomputation) for the SR policy, or recomputing a multipath for the SR policy.

By applying the above techniques, controller <NUM> may in some cases avoid churn in the network by implementing an operator preference, using SR policies extended to specify acceptable deviations as described herein, for already-provisioned SID lists for SR policies that are sufficient to meet operator requirements.

<FIG> are block diagrams illustrating an example system <NUM> having network <NUM> and controller <NUM> configured to operate in accordance with techniques described in this disclosure. Controller <NUM> and network <NUM> may be examples of controller <NUM> and network <NUM> of <FIG>, respectively.

Network <NUM> includes network nodes U11, U12, U21, U22, U31, U32, U41, U42, S11, S12, S21, S22, S31, S32, S41, and S42 (collectively, "network nodes <NUM>"). Network nodes <NUM> are located in different sites <NUM>-<NUM>. For example, network nodes S41, S42, U41, and U42 are located in site <NUM>, network nodes U31, U32, S31, and S32 are located in site <NUM>.

Some of network nodes <NUM> are members of anycast groups. Anycast group <NUM> includes network nodes S11 and S12. Anycast group <NUM> includes network nodes S21 and S22. Anycast group <NUM> includes network nodes S31 and S32. Anycast group <NUM> includes network nodes S41 and S42.

Network nodes <NUM> are connected in a network topology with links 201A-201J (collectively, "links <NUM>"). Each link of links <NUM> has an associated metric, e.g., an IGP metric, representing a cost to traverse the link for a shortest path first algorithm. The metric for a link is illustrated in <FIG> using braces "{M}", where the value of M is the metric. For example, link <NUM> connecting S41 to S31 has a metric of <NUM>. As illustrated, the default metric for a link in network <NUM> is <NUM>. For example, the unnamed links connecting U11 to S11 and U11 to S12 have metrics of <NUM>.

<FIG> illustrates a multipath from source U11 to destination U31 for implementing SR Policy "U11-U31 via Site <NUM>". The multipath includes multiple possible computed paths that may be taken by network packets from U11 to U31 to satisfy the SR policy. Controller <NUM> or one of network nodes <NUM> may compute the computed paths <NUM>, which include paths 230A-230C. Path 230A, for instance, traverses network nodes U11 to S12 to S42 to S32 to U31 and the links connecting these pairs of network nodes, e.g., the U11-S12 link, the S12-S42 link 201D, and so forth. The paths are illustrated in <FIG> as superimposed on the network <NUM> using bold arrows. Computed paths <NUM> are not the shortest paths from U11 to U31, instead traversing network nodes of Site <NUM> in order to satisfy the SR Policy.

<FIG> are block diagrams illustrating a process for computing lists of segment identifiers (SIDs) that satisfy each of paths <NUM> of <FIG> in the multipath solution for a segment routing (SR) policy. When attached to a packet steered to the SR policy by U11, for instance, a list of SIDs will cause network <NUM> to forward the packet on the multipath and prevent network <NUM> from forwarding the packet on a path that is not a path of the multipath, i.e., not one of paths <NUM>. In some examples, the techniques may include determining, based on routing (e.g., IGP) metrics, respective distances for network nodes <NUM> from source network node U11 for the multipath and identifying candidate sets (or "candidate combinations") of one or more network nodes <NUM> or adjacencies to be used as bases for SIDs to extend candidate lists of SIDs in progress. In some cases, the techniques include computing an equidistant metric graph rooted at the source network node U11 based on the metrics. Identifying candidate sets of one or more network nodes or adjacencies may include identifying one or more network nodes <NUM> that all of the multipaths traverse and that would not be bypassed, e.g., routed around, by shortest paths from earlier network nodes <NUM> to subsequent network nodes <NUM> in the multipath. Identifying candidate sets of one or more network nodes or adjacencies may include identifying two or more network nodes <NUM> that are equidistant from the source and are not bypassed, collectively, by shortest paths from earlier network nodes <NUM> to subsequent network nodes <NUM> in the multipath. SIDs generated from the identified candidate sets of network nodes may include anycast SIDs and node SIDs. The techniques may iteratively build up the candidate lists of SIDs by extending candidate lists of SIDs in progress with SIDs generated from newly identified candidate sets of one or more network nodes or adjacencies, and rooting further equidistant metric graphs from network nodes of the candidate sets of one or more network nodes or adjacencies. The techniques may be applied by controller <NUM> or by any of network nodes <NUM> but are described hereinafter primarily with respect to controller <NUM>.

<FIG> illustrates an equidistant metric graph (MG) <NUM> rooted at source network node U11 and shown alongside a paths tree <NUM> representing the multipath of paths <NUM>. Controller <NUM> computes MG <NUM> based on the paths <NUM> and the metrics for links of the paths <NUM>. Controller <NUM> may use a shortest path first algorithm, such as Dijkstra, to compute MG <NUM>. MG <NUM> includes metric graph nodes 302A-302I (collectively, "MG nodes <NUM>") and directed edges representing the links for the paths tree. For example, MG <NUM> includes a directed edge from MG node 302A to 302B. Each MG node of the MG nodes <NUM> represents at least one network node, of the one or more network nodes <NUM>, that are a same distance from the source network node U11 along at least one path, of the plurality of paths <NUM>, based on the metrics for the links represented in the plurality of paths <NUM>. <FIG> illustrates represented network nodes for any of MG nodes <NUM> using a vertical alignment. For example, network node U11 is represented by MG node 302A, network nodes S11 and S12 are represented by MG node 302B, and so forth. As used herein, network nodes may be described alternatively as "represented by" or "in" metric graph nodes for a metric graph.

Network nodes <NUM> represented by an MG node <NUM> are equidistant from network nodes <NUM> represented by preceding and subsequent MG nodes <NUM> in the directed MG <NUM>. For example, S41 and S42 are both equidistant (by metric value <NUM>) from S11 and S12 represented by MG node 302C, equidistant (by metric value <NUM>) from S32 represented by MG node 302F, and equidistant (by metric value <NUM>) from S32 also represented by MG node <NUM>. S32 is represented by multiple MG nodes <NUM> because it is traversed by multiple paths <NUM> and has different distances from the source on these multiple paths. When computed, each of MG nodes <NUM> may be, by default, a candidate MG node for extending one or more lists of SIDs.

Because they are equidistant from the source node, the multipath nodes in an MG node provide candidate node and anycast SIDs for candidate lists of SIDs. MG nodes <NUM> that have a link going around them in the order are called bypassed. Bypassed MG nodes <NUM> do not give rise to node or anycast SID candidates because traffic needs to flow around them.

<FIG> illustrates MG <NUM> with some MG nodes <NUM> indicated as bypassed because traffic needs to flow around them. MG Node 302D representing network nodes U41 and U42, for example, is marked as bypassed because path 230A does not include U41 or U42 and traffic on path 230A thus flows around U41 and U42. MG nodes 302E, 302F, and <NUM> are also marked as bypassed. MG <NUM> indicates bypassed nodes with the directed edges. The directed edge from MG node 302C to MG node 302F bypasses MG nodes 302D and 302E. MG nodes 302D and 302E are therefore marked as bypassed. Controller <NUM> can thus identify bypassed MG nodes <NUM> by traversing MG <NUM> and identifying MG nodes that have a directed edge going around them.

Another way to understand bypassed nodes is to consider what S42 would do if it received a packet with a node SID for U41 or U42 on top of the SID stack. S42 would send the traffic out on the links S42->U41 and S42->U42, respectively. And those links in those directions are not links on the paths for the multipath to keep the traffic on. Thus, looking at bypassed MG nodes in the MG becomes an efficient way to eliminate candidates without having to do a full ECMP shortest path calculation between all pairs of network nodes where one is in a bypassed MG node and the other network node is in some other MG node.

By analyzing the shortest multipaths from the represented network nodes of the source MG node 302A to the represented nodes in a non-bypassed MG node <NUM>, more candidates can be eliminated. If such shortest multipaths aren't contained in the multipath solution (here, paths <NUM>), then those MG nodes <NUM> are not candidates. This eliminates MG node <NUM> and 302I from the candidate list because the shortest paths from U11 to S32 or S31 traverse network nodes S21 and S22, and these paths are not any of paths <NUM> (the multipath).

<FIG> illustrates a step in the iterative generation of candidate lists of SIDs. Having eliminated MG nodes 302D-302I from consideration, controller <NUM> may apply a greedy heuristic in this case to select the remaining MG node 302C that is furthest by distance from MG source node 302A. MG node 302C represents anycast group <NUM> (having identifier "S4" in this example) that includes network nodes S41 and S42. Each of these correspond to candidate SIDs for candidate lists of SIDs in progress. Because the in progress list was empty, controller <NUM> creates two candidate lists of SIDs in progress, one made up of lists 350A-350B and one being list 350C, controller <NUM> adds respective S41 (the node SID thereof), S42 (the node SID thereof), and S4 (the anycast SID for group <NUM>) segments to these. By reference to <FIG>, it can be seen that that traffic forwarded according any of the candidate lists of SIDs in progress 350A-350C will reach anycast group <NUM> and encompasses all paths within the multipath that reach anycast group <NUM>.

<FIG> illustrates application of a further heuristic whereby, because all of the network nodes in anycast group <NUM> are represented by MG node 302C along with anycast group <NUM>, i.e., there are no other network nodes <NUM> outside of anycast group <NUM>, controller <NUM> applies a preference for the anycast SID for anycast group <NUM>. Controller <NUM> may therefore discard lists 350A and 350B for one of the candidate lists of SIDs.

<FIG> illustrates application of a further heuristic whereby, because all of the network nodes in anycast group <NUM> are represented by MG node 302C along with anycast group <NUM>, i.e., there are no other network nodes <NUM> outside of anycast group <NUM>, controller <NUM> applies a preference for the anycast SID for anycast group <NUM>. Controller <NUM> therefore discards lists 350A and 350B in favor of the preferred list 350C.

Although MG nodes 302B and 302C both give rise to candidates for the start of the minimum SID lists in progress, the optional preference applied is for the fewest SIDs in the SID lists. MG node 302C therefore gives rise to better candidates than MG 302B because it covers more of the multipath. One candidate start to the SID lists is to have one starting with a node SID for S41 and another node SID for S42. Since S41 and S42 are in the same anycast group <NUM> with identifier S4, another candidate start to the SID lists is a single SID list starting with S4. This anycast option may only be a candidate when there are no other members of the anycast group occurring in MG nodes <NUM> closer to the source. If that were the case, these earlier members of the anycast group would capture the traffic and send it on paths outside the multipath. Thus, when a MG node <NUM> represents multiple network nodes of the one or more network nodes <NUM>, controller <NUM> may generates a list of SIDs in progress to include an anycast SID for the at least one network node <NUM> represented by the MG node <NUM>. Controller <NUM> exclude bypassed MG nodes. Controller <NUM> may exclude an MG node <NUM> that is "not containing", that is, that do not include the shortest paths from the source network node to the nodes represented by the MG node <NUM>.

<FIG> also illustrates a sub-network of network <NUM> showing just the initial aspects of the multipath for reaching S4 (group <NUM>). All sub-paths for paths <NUM> are included. A sub-path of a path is any set of one or more connected links of the path.

<FIG> illustrates a next iteration step in generating candidate lists of SIDs in progress. The remaining task is to compute an extension of the SID List(s) to cover the remaining multipath. To do this, the perspective of S41 and S42 is considered. Controller <NUM> reorganize the remainder of the MG <NUM> (or generates new MGs) from the remaining step into two MGs, one from S41 and one from S42. For list 350C still in progress, controller <NUM> computes new MGs for paths <NUM>, this time rooted at each network node <NUM> in the anycast SID S4 (group <NUM>). That is, each reached network node <NUM> is a root of a new MG. MG 320A is therefore rooted at S41, and MG 320B is therefore rooted at S42. All the MG nodes in both of these MGs 320A, 320B are candidates, none are bypassed, and all exactly contain the shortest multipaths between their represented network nodes <NUM>.

<FIG> illustrates compatible candidate combinations <NUM> and <NUM>. When multiple nodes are reached by the SID list(s) in progress and there are multiple MGs, as with MGs 320A and 320B, controller may select compatible candidate combinations of MG nodes, one from each MG. The simplest kind of compatibility is a set of candidates that contain exactly the same network nodes. In this example, there are two such compatible combinations <NUM> and <NUM>, as shown. This is a simple example, for each compatible combination there is a single same network node in each member of each compatible combination, S32 or U31. When this is the case, the SID list can be extended with a node SID to extend the SID list in progress. <FIG> illustrates application of the greedy heuristic in which controller <NUM> chooses the compatible MG nodes further by distance from the source MG nodes of MGs 320A, 320B, that is, the respective MG nodes of MGs 320A, 320B that represent U31.

Anycast groups enable more elaborate compatible combinations. If all network nodes in a combination are in the same anycast group and no member of the anycast group occurs in the sub-multipath that will be covered by the extension of the SID list in progress, controller <NUM> can use the anycast SID to extend the SID list in progress.

The second more elaborate case is a combination where each MG node contains the same set of network nodes. In this case, the SID lists in progress can be extended by duplicating them and extending them with the node SID of each node in the set.

<FIG> also shows a subnetwork of network <NUM> illustrating that the segment for U31 will reach extend all paths of the multipath to U31. Because U31 is the destination, this completes the multipath and, therefore, the updated SID list in progress 360C updated from 350C with the SID for U31.

<FIG> are block diagrams illustrating a process for computing lists of segment identifiers (SIDs) that satisfy each of paths <NUM>, with a modified network <NUM> from <FIG>, in the multipath solution for a segment routing (SR) policy. Network <NUM> in <FIG> has been modified by changing the metric for link <NUM> from <NUM> to <NUM>. As a result, the shortest path from anycast group <NUM> to U31 is no longer via link <NUM> but instead via S21 and S22. This causes previously compatible MG nodes of MGs 420A, 420B rooted as S41, S42, respectively, to be "not containing" and eliminated from consideration as candidate MG nodes. Controller <NUM> therefore must force traffic through link <NUM> carrying the multipath using an adjacency SID. To have an adjacency SID for link <NUM>, the ingress S42 of the adjacency must also be a SID.

In other words, sometimes it is necessary to use adjacency SIDs to force traffic onto expensive links. Taking the previous example with the metric for the second link between sites <NUM> and <NUM> also set to <NUM>, it is seen that all shortest multipaths from S41 and S42 to S32 and U31 veer onto links not in the requested multipath. As adjacency SIDs are not routable, they may be preceded with node SIDs that get the traffic to the node with the adjacency. Adding S42, S42-S32 to the SID list will cover the highlighted sub-multipath, but the anycast S4 will direct some of the traffic to S42, which may not be able to pop both S4 and S42, depending on the SR implementation.

<FIG> illustrates two solutions to the above problem, a first solution with <NUM> SID lists 472A, 472B, and a second solution with a single SID list that uses a set of adjacencies (all adjacencies from Site <NUM> ("S1") to Site <NUM> ("S2").

Controller <NUM> may compute computed paths <NUM> using one or more constraint-based path computation algorithms (e.g., constrained shortest path first, or CSPF) that require any acceptable path to meet a set of defined constraints, such as those policy constraints specified in an SR policy for which controller <NUM> computes computed paths <NUM>. Example constraints are described below with respect to <FIG>.

Controller <NUM> that computes a solution with a list of SIDs may install the list of SIDs into network <NUM> for using by network nodes <NUM> to forward traffic steered to the SR policy that has the solution. In accordance with techniques of this disclosure, a network operator or other mechanism (e.g., an NMS having AI-driven intent-based automated functions) may specify acceptable deviations from the SR policy constraints used for computing the solution. An SR policy may specify one or more policy constraints that limit the acceptable paths for the SR policy to those that satisfy the policy constraints. An SR policy, extended as described herein, specifies both initial policy constraints that must be satisfied for an initial path computation as well as acceptable deviations, in the form of relaxed policy constraints, that relax the initial policy constraints to in some cases allow controller <NUM> and/or network nodes <NUM> to avoid triggering path recomputation.

<FIG> is a block diagram illustrating an example controller, according to techniques of this disclosure. Controller <NUM> may represent an example implementation of controller <NUM>. Controller <NUM> may be or implement a WAN controller, software-defined networking (SDN) controller, and/or path computation element, for instance.

In general, path computation module <NUM> and path provisioning module <NUM> of controller <NUM> may use the protocols to instantiate paths between the Path Computation Clients (e.g., routers) in a network. Southbound API <NUM> allows controller <NUM> to communicate with SR-enabled and other network nodes, e.g., routers and switches of the network using, for example, ISIS, OSPFv2, BGP-LS, and PCEP protocols. By providing a view of the global network state and bandwidth demand in the network, controller <NUM> is able to compute optimal paths and provision the network for forwarding using lists of SIDs in an SR paradigm.

In some examples, application services issue path requests to controller <NUM> to request paths in a path computation domain controlled by controller <NUM>. For example, a path request includes a required bandwidth or other constraint and two endpoints representing an access node and an edge node that communicate over the path computation domain managed by controller <NUM>. Path requests may further specify time/date during which paths must be operational and CoS parameters (for instance, bandwidth required per class for certain paths).

Controller <NUM> accepts path requests from application services to establish paths between the endpoints over the path computation domain. Paths may be requested for different times and dates and with disparate bandwidth requirements. Controller <NUM> reconciling path requests from application services to multiplex requested paths onto the path computation domain based on requested path parameters and anticipated network resource availability.

To intelligently compute and establish paths through the path computation domain, controller <NUM> includes topology module <NUM> to maintain topology information (e.g., a traffic engineering database) describing available resources of the path computation domain, including access, aggregation, and edge nodes, interfaces thereof, and interconnecting communication links.

Path computation module <NUM> of controller <NUM> computes requested paths through the path computation domain. In general, paths are unidirectional. Upon computing paths, path computation module <NUM> schedules the paths for provisioning by path provisioning module <NUM>. A computed path includes path information usable by path provisioning module <NUM> to establish the path in the network. Provisioning a path may require path validation prior to committing the path to provide for packet transport.

Further example details of a distributed WAN controller may be found in <CIT>, entitled "Software Defined Network Controller". This is merely one example, and controller <NUM> may compute and provision paths in other ways.

In this example, controller <NUM> includes northbound and southbound interfaces in the form of northbound application programming interface (API) <NUM> and southbound API (<NUM>). Northbound API <NUM> includes methods and/or accessible data structures by which, as noted above, application services may configure and request path computation and query established paths within the path computation domain. Southbound API <NUM> includes methods and/or accessible data structures by which controller <NUM> receives topology information for the path computation domain and establishes paths by accessing and programming data planes of aggregation nodes and/or access nodes within the path computation domain.

Path computation module <NUM> includes data structures to store path information for computing and establishing requested paths. These data structures include SR policies <NUM> having SR policy constraints <NUM>, path requirements <NUM>, operational configuration <NUM>, and path export <NUM>. Applications may invoke northbound API <NUM> to install/query data from these data structures. SR policy constraints <NUM> includes data that describes external constraints upon path computation.

Using northbound API <NUM>, a network operator may configure SR policies <NUM>. According to techniques of this disclosure, SR policies <NUM> specify acceptable deviations from the SR policy constraints <NUM> used for computing each path in a multipath solution for a given one of SR policies <NUM>. Any of SR policies <NUM> may specify one or more SR policy constraints <NUM> that limit the acceptable paths for the SR policy to those that satisfy the policy constraints. An SR policy, extended as described herein, specifies both initial policy constraints that must be satisfied for an initial path computation as well as acceptable deviations, in the form of relaxed policy constraints, that relax the initial policy constraints to in some cases allow controller <NUM> and/or network nodes <NUM> to avoid triggering path recomputation.

Applications may modify attributes of a link to effect resulting traffic engineering computations. In such instances, link attributes may override attributes received from topology indication module <NUM> and remain in effect for the duration of the node / attendant port in the topology. The link edit message may be sent by the controller <NUM>.

Operational configuration <NUM> represents a data structure that provides configuration information to controller <NUM> to configure the path computation algorithm with respect to, for example, class of service (CoS) descriptors and detour behaviors. Operational configuration <NUM> may receive operational configuration information in accordance with CCP. An operational configuration message specifies CoS value, queue depth, queue depth priority, scheduling discipline, over provisioning factors, detour type, path failure mode, and detour path failure mode, for instance. A single CoS profile may be used for the entire path computation domain. The Service Class assigned to a Class of Service may be independent of the node as an attribute of the path computation domain.

Path export <NUM> represents an interface that stores path descriptors for all paths currently committed or established in the path computation domain. In response to queries received via northbound API <NUM>, path export <NUM> returns one or more path descriptors. Queries received may request paths between any two edge and access nodes terminating the path(s). In some examples, path descriptors may be used by Applications to set up forwarding configuration at the edge and access nodes terminating the path(s). A path descriptor may include an Explicit Route Object (ERO). A path descriptor or "path information" may be sent, responsive to a query from an interested party. A path export message delivers path information including path type (primary or detour); bandwidth for each CoS value. In response to receiving the path descriptor, the receiving device may use RSVP-TE to signal an MPLS LSP from the ingress to the egress of the path.

Path requirements <NUM> represent an interface that receives path requests for paths to be computed by path computation module <NUM> and provides these path requests (including path requirements) to path engine <NUM> for computation. Path requirements <NUM> may be received or may be handled by the controller. In such instances, a path requirement message may include a path descriptor having an ingress node identifier and egress node identifier for the nodes terminating the specified path, along with request parameters including CoS value and bandwidth. A path requirement message may add to or delete from existing path requirements for the specified path.

Topology module <NUM> includes topology indication module <NUM> to handle topology discovery and, where needed, to maintain control channels between controller <NUM> and nodes of the path computation domain. Topology indication module <NUM> may include an interface to describe received topologies to path computation module <NUM>.

Topology indication module <NUM> may use a topology discovery protocol to describe the path computation domain topology to path computation module <NUM>. In one example, using a cloud control protocol mechanism for topology discovery, topology indication module <NUM> may receive a list of node neighbors, with each neighbor including a node identifier, local port index, and remote port index, as well as a list of link attributes each specifying a port index, bandwidth, expected time to transmit, shared link group, and fate shared group, for instance.

Topology indication module <NUM> may communicate with a topology server, such as a routing protocol route reflector, to receive topology information for a network layer of the network. Topology indication module <NUM> may include a routing protocol process that executes a routing protocol to receive routing protocol advertisements, such as Open Shortest Path First (OSPF) or Intermediate System-to-Intermediate System (IS-IS) link state advertisements (LSAs) or Border Gateway Protocol (BGP) UPDATE messages. Topology indication module <NUM> may in some instances be a passive listener that neither forwards nor originates routing protocol advertisements. In some instances, topology indication module <NUM> may alternatively, or additionally, execute a topology discovery mechanism such as an interface for an Application-Layer Traffic Optimization (ALTO) service. Topology indication module <NUM> may therefore receive a digest of topology information collected by a topology server, e.g., an ALTO server, rather than executing a routing protocol to receive routing protocol advertisements directly.

In some examples, topology indication module <NUM> receives topology information that includes traffic engineering (TE) information. Topology indication module <NUM> may, for example, execute Intermediate System-to-Intermediate System with TE extensions (IS-IS-TE) or Open Shortest Path First with TE extensions (OSPF-TE) to receive TE information for advertised links. Such TE information includes one or more of the link state, administrative attributes, and metrics such as bandwidth available for use at various LSP priority levels of links connecting routers of the path computation domain. In some instances, indication module <NUM> executes BGP-TE to receive advertised TE information for interautonomous system and other out-of-network links.

Traffic engineering database (TED) <NUM> stores topology information, received by topology indication module <NUM>, for a network that constitutes a path computation domain for controller <NUM> to a computer-readable storage medium (not shown). TED <NUM> may include one or more link-state databases (LSDBs), where link and node data is received in routing protocol advertisements, received from a topology server, and/or discovered by link-layer entities such as an overlay controller and then provided to topology indication module <NUM>. In some instances, an operator may configure traffic engineering or other topology information within MT TED <NUM> via a client interface.

Path engine <NUM> accepts the current topology snapshot of the path computation domain in the form of TED <NUM> and computes, using TED <NUM>, CoS-aware traffic-engineered paths between nodes as indicated by configured node-specific policy (constraints <NUM>) and/or through dynamic networking with external modules via APIs. Path engine <NUM> may further compute detours for all primary paths on a per-CoS basis according to configured failover and capacity requirements (as specified in operational configuration <NUM> and path requirements <NUM>, respectively).

In general, to compute a requested path, path engine <NUM> determines based on TED <NUM> and all specified constraints whether there exists a path in the layer that satisfies the TE specifications for the requested path for the duration of the requested time. Path engine <NUM> may use the Dijkstra constrained SPF (CSPF) <NUM> path computation algorithms for identifying satisfactory paths though the path computation domain. If there are no TE constraints, path engine <NUM> may revert to SPF. If a satisfactory computed path for the requested path exists, path engine <NUM> provides a path descriptor for the computed path to path manager <NUM> to establish the path using path provisioning module <NUM>. A path computed by path engine <NUM> may be referred to as a "computed" path. As described in further detail below, path engine <NUM> may determine lists of SIDs for a plurality of paths computed by path engine <NUM> for an SR policy of SR policies <NUM>.

Path manager <NUM> establishes computed scheduled paths using path provisioning module <NUM>, which in this instance includes forwarding information base (FIB) configuration module <NUM> (illustrated as "FIB CONFIG. <NUM>"), policer configuration module <NUM> (illustrated as "POLICER CONFIG. <NUM>"), and CoS scheduler configuration module <NUM> (illustrated as "COS SCHEDULER CONFIG.

FIB configuration module <NUM> programs forwarding information to data planes of aggregation nodes or access nodes of the path computation domain. The FIB of an aggregation node or access node includes the MPLS switching table, the detour path for each primary LSP, the CoS scheduler per-interface and policers at LSP ingress. FIB configuration module <NUM> may implement, for instance, a software-defined networking (SDN) protocol such as the OpenFlow protocol or the I2RS protocol to provide and direct the nodes to install forwarding information to their respective data planes. Accordingly, the "FIB" may refer to forwarding tables in the form of, for instance, one or more OpenFlow flow tables each comprising one or more flow table entries that specify handling of matching packets. FIB configuration module <NUM> may in addition, or alternatively, implement other interface types, such as a Simple Network Management Protocol (SNMP) interface, path computation element protocol (PCEP) interface, a Device Management Interface (DMI), a CLI, Interface to the Routing System (I2RS), or any other node configuration interface. FIB configuration module interface <NUM> establishes communication sessions with aggregation nodes or access nodes to install forwarding information to receive path setup event information, such as confirmation that received forwarding information has been successfully installed or that received forwarding information cannot be installed (indicating FIB configuration failure).

FIB configuration module <NUM> may add, change (i.e., implicit add), or delete forwarding table entries in accordance with information received from path computation module <NUM>. A FIB configuration message from path computation module <NUM> to FIB configuration module <NUM> may specify an event type (add or delete); a node identifier; a path identifier; one or more forwarding table entries each including an ingress port index, ingress label, egress port index, and egress label; and a detour path specifying a path identifier and CoS mode.

Policer configuration module <NUM> may be invoked by path computation module <NUM> to request a policer be installed on a particular aggregation node or access node for a particular LSP ingress. As noted above, the FIBs for aggregation nodes or access nodes include policers at LSP ingress. Policer configuration module <NUM> may receive policer configuration requests. A policer configuration request message may specify an event type (add, change, or delete); a node identifier; an LSP identifier; and, for each class of service, a list of policer information including CoS value, maximum bandwidth, burst, and drop/remark. FIB configuration module <NUM> configures the policers in accordance with the policer configuration requests.

CoS scheduler configuration module <NUM> may be invoked by path computation module <NUM> to request configuration of CoS scheduler on the aggregation nodes or access nodes. CoS scheduler configuration module <NUM> may receive the CoS scheduler configuration information. A scheduling configuration request message may specify an event type (change); a node identifier; a port identity value (port index); and configuration information specifying bandwidth, queue depth, and scheduling discipline, for instance.

Path engine <NUM> may compute lists of segment identifiers (SIDs) that satisfy each path in a multipath solution for a segment routing (SR) policy. Path provisioning module <NUM> may output the lists of SIDs to the SR-enabled network nodes to provision the network to forward traffic along the multipath.

Topology indication module <NUM> may receive an indication that a network topology for a network managed by controller <NUM> has changed to a modified network topology. The indication may be, for example, an update to a link status indicating the link is down (or up), has different bandwidth availability or bandwidth status, has a different metric, or color, has a different Shared Risk Link Group, or other change to a link status. The indication may be, for example, an indication of a failed network node that affects the link statuses of multiple different links. Topology module <NUM> may update traffic engineering database <NUM> with a modified topology that is modified based on the indication received by topology indication module <NUM>.

Controller <NUM> includes a hardware environment including processing circuitry <NUM> for executing machine-readable software instructions for implementing modules, interfaces, managers, and other components illustrated and described with respect to controller <NUM>. The components may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware, or firmware. For example, controller <NUM> may include one or more processors comprising processing circuitry <NUM> that execute program code in the form of software instructions. In that case, the various software components/modules of may comprise executable instructions stored on a computer-readable storage medium, such as computer memory or hard disk (not shown).

<FIG> is a block diagram illustrating an example implementation of path engine <NUM> in further detail. Path engine <NUM> may execute various routing protocols <NUM> at different layers of a network stack. Path engine <NUM> is responsible for the maintenance of routing information <NUM> to reflect the current topology of a network. Routing information <NUM> may include TED <NUM> and LSDB <NUM>. In particular, routing protocols periodically update routing information <NUM> to accurately reflect the topology of the network and other entities based on routing protocol messages received by controller <NUM>. The protocols may be software processes executing on one or more processors. For example, path engine <NUM> includes network protocols that operate at a network layer of the network stack, which are typically implemented as executable software instructions. The operations may overlap or instead by performed by topology module <NUM>.

Protocols <NUM> may include Border Gateway Protocol (BGP) <NUM> to exchange routing and reachability information among routing domains in a network and BGP-LS <NUM> to exchange traffic engineering and segment routing policy information among routing domains in the network. Protocols <NUM> may also include IGP <NUM> to exchange link state information and facilitate forwarding of packets or other data units between routers within each of the routing domains. In some examples, IGP <NUM> may include an IS-IS routing protocol that implements an IGP for exchanging routing and reachability information within a routing domain IGP <NUM> may include IS-IS extensions that support traffic engineering. In some examples, protocols <NUM> may include both an OSPF component and an IS-IS component.

Protocols <NUM> may also include configuration protocols. For example, protocols <NUM> may include PCEP <NUM> or NETCONF.

Path engine <NUM> includes an SR component <NUM> to implement techniques described herein to generate lists of SIDs for a multipath and to determine whether to recompute the multipath in response to an indication of a modified topology, based on acceptable deviations for an SR policy for which the multipath was initially computed. SID list <NUM> includes one or more SID lists, which may be provisioned by controller <NUM> to a network for segment routing. An ingress router may use the SIDs to steer a packet through a controlled set of instructions, called segments, by prepending the packet with a SID label stack in a segment routing header or MPLS label stack. Protocols <NUM> may include other routing protocols (not shown), such as Label Distribution Protocol (LDP), Resource Reservation Protocol with Traffic Extensions (RSVP-TE), routing information protocol (RIP), or other network protocols.

In this example, path engine <NUM> includes a command line interface (CLI) <NUM> that provides access for a network operator (or other administrator or computing agent) to monitor, configure, or otherwise manage path computation and, in some cases, SR policies. An administrator may, via CLI <NUM>, configure aspects of controller <NUM>, including aspects relating to routing as well as computing and provisioning lists of SIDs for multipaths. CLI <NUM> (and/or northbound API <NUM>) may enable specifying source, destination, user constraints, preferences, SR policies, and other configurable information. CLI <NUM> may be used in lieu of, or in addition to, northbound API <NUM>.

Changes in the network topology may affect one or more paths of a multipath computed for an SR policy. In accordance with techniques of this disclosure, a network operator may specify acceptable deviations from the SR policy constraints <NUM> used for computing each path in the computed multipath for an SR policy of SR policies <NUM>. The SR policy, extended as described herein, specifies both initial policy constraints that must have been satisfied for the initial paths computation for the multipath as well as acceptable deviations, in the form of relaxed policy constraints, that relax the initial policy constraints to allow, at least in some cases, SR component <NUM> to avoid triggering path recomputation. In response to an indication of a modified network topology that has been modified from the topology used to compute the initial, existing, and installed multipath, path computation module <NUM> may determine whether the installed multipath meets the relaxed policy constraints. To determine the paths of the installed multipath, which is defined using the one or more lists of SIDs for the plurality of paths initially computed to implement the SR policy and which satisfied the initial constraints, SR component <NUM> may expand each list of SIDs (in the one or more lists of SIDs that realize a multipath to satisfy the SR policy) into the plurality of paths on the modified network topology. In other words, SR component <NUM> determines the paths of the multipath after the change in the network topology, which may be different from what was originally computed.

For example, in response to an indication of a network topology change received by topology indication module <NUM> and subsequent update to traffic engineering database <NUM>, path computation module <NUM> may prompt SR component <NUM> to evaluate the "new multipath" for the lists of SIDs against the relaxed constraints of the SR policy. If this new multipath, as the already-installed multipath in the modified topology according to previously computed lists of SIDs, is acceptable under the relaxed policy constraints, then SR component <NUM> may eschew recomputing a multipath for the SR policy in order for the SR policy to again meet the initial policy constraints. Instead, SR component <NUM> may allow the multipath to operate, at least temporarily, in a degraded condition.

<FIG> is a flow diagram illustrating an example operation of a computing device, in accordance with one or more techniques of this disclosure. The computing device may be a computing device of controller <NUM> or <NUM> or other controller described herein, or may represent a network node, such as a head-end or ingress router for an SR policy. The flow diagram is described with respect to controller <NUM>, however. As seen in the example of <FIG>, controller <NUM> may obtain a plurality of paths <NUM> through a network <NUM> comprising one or more network nodes <NUM>, each path of the plurality of paths <NUM> representing a different sequence of links connecting pairs of the network nodes from a source network node to a destination network node (<NUM>). The paths <NUM> can be used to realize an SR policy. Next, controller <NUM> may compute one or more lists of segments identifiers (SIDs) that satisfy each path of the plurality of paths (<NUM>). In some examples, any of the lists of SIDs satisfies each path of the plurality of paths by itself. However, in some examples, the lists of SIDs may satisfy all of the paths collectively, not necessarily individually. In some cases, controller computes the one or more lists of SIDs by computing, based on the metrics for the links, an equidistant metric graph rooted at the source network node <NUM>, the equidistant metric graph comprising metric graph nodes and directed edges representing the links, each metric graph node of the metric graph nodes representing at least one network node <NUM>, of the one or more network nodes <NUM>, that are a same distance from the source network node along at least one path, of the plurality of paths <NUM>, based on the metrics for the links represented in the plurality of paths <NUM>. Next, controller <NUM> may program the network <NUM> to forward network traffic based at least on the one or more lists of SIDs (<NUM>).

<FIG> is a flow diagram illustrating an example operation, performed by a computing device, for computing candidate lists of SIDs for implementing a multipath, according to techniques of this disclosure. The operation is performed after the computing device obtains data describing a plurality of paths. The data may describe the paths using links, nodes, interfaces, or some combination thereof.

The operation is initialized by setting InProgressSet to [[]] and Candidates to [] (<NUM>). InProgressSet may correspond to candidate lists of SIDs in progress, described elsewhere in this document. Candidates may be Candidate solutions to the SID minimization problem (i.e., lists of SIDs) that satisfy, e.g. collectively or individually, the multipath to implement an SR policy. Each of Candidate s is a set of one or more SID lists.

At a next step, which enters a loop, if not InProgressSet == [] (i.e., it's not empty, NO branch of <NUM>), the computing device deletes InProgress from InProgressSet and sets Cand (idate) Combos to compatible combinations for MGs of InProgress (<NUM>).

The process then enters another loop. If not CandCombos == [] (i.e., it's empty, NO branch of <NUM>), computing device deletes Combo from CandCombos and sets InProgressExt to (InProgress extended with Combo) (<NUM>). If InProgressExt is complete and meets the user constraints (YES branch of <NUM>), the computing device adds InProgressExt to Candidates (<NUM>) and loops back to (<NUM>). If InProgressExt is not complete or does not meet the user constraints (NO branch of <NUM>), computing device must continue extending this candidate list of SIDs in progress and thus adds InProgressExt to InProgressSet (<NUM>). The computing device loops to the test for this internal loop (<NUM>).

If CandCombos == [] (YES branch of <NUM>), computing device loops back to (<NUM>) to determine whether there are additional In Progress Sets. If InProgressSet == [] (empty, YES branch of <NUM>), then computing device sorts the Candidates by evaluation criteria (<NUM>) and outputs the sorted Candidates as lists of SIDs for the network to use for forwarding on the multipath (<NUM>).

Configurable criteria for SID list computation preferences may include:.

The each of the criteria may be weighted when computing the SID lists.

In general, list of SIDs computation algorithms described herein may apply heuristics to:.

<FIG> is a block diagram illustrating an example data model for segment routing policy constraints, according to techniques of this disclosure. A controller may be configured with multiple SR policies, such as SR policies <NUM>. Example SR policy <NUM> is an example data model for any of SR policies <NUM>, in further detail. SR policy <NUM> includes SR policy constraints <NUM>.

SR policy constraints <NUM> includes a set of initial path computation constraints that must be satisfied when computing an initial multipath for SR policy <NUM>. These are optimization constraints <NUM> and include capacity 920A, hops 920B, optimization criteria 920C, link filter 920D, required hops 920E, bounded metrics 920F, require all destination nodes <NUM>, and keep on original path <NUM>. Each of optimization constraints <NUM> may be an absolute constraint. A satisfactory multipath should start on the SR policy start node, include a destination node, include all destination nodes if require all destination nodes <NUM> is set, include all of the required hops 920E (optionally specified as a list of SIDs), not exceed the capacity 920A or the bounded metrics 920F, and all links must pass the link filter 920D.

Hops 920B may be used as a multipath computation constraint as a list of hops that the computation will use. Required hops 920E are the hops that must be used in order for a multipath to be valid. Bounded metrics 920F is a set of metrics with (metric type, maximum allowed value for the metric). If a path within the multipath has an accumulated metric greater than the bound, the path is considered invalid. For instance: the optimization metric can be TE Metric, and the bounded metric (Delay, <NUM>). The multipath computation will return a path with the accumulated delay not exceeding <NUM>, routed using the TE metric. Link filter 920D is a function that excludes or includes certain links in the path computation, used to apply constraints to the link. For instance, the administrative color constraint is applied by having a link filter 920D that rejects links not matching the admin-color constraints.

Optimization criteria 920C includes a set of metrics 930A that can be used to sort between two multipaths to select the best multipath of a number of solutions. Example metrics may be number of paths in the multipath, distance to bounded metric (a multipath that has a greater distance to the bound metrics can be more tolerant to changes and is generally preferable).

SR policy constraints <NUM> also includes one or more path recomputation deviations 910A-910N (collectively, "deviations <NUM>"). Each of deviations <NUM> defines an acceptable deviation from the initial constraints-optimization constraints <NUM>-such that controller <NUM> may eschew recomputation of a multipath that no longer satisfies optimization constraints <NUM>, due to changes in the network topology, but still satisfies the constraints defined by the deviation. In general, the constraints defined by each of deviations <NUM> will be relaxed from the more stringent initial constraints of optimization constraints <NUM>.

Deviation 910A, for example, may be defined using absolute constraints similar to optimization constraints <NUM>. Deviation 910A may alternatively, or additionally, be defined using relative constraints that are relative from the optimization constraints <NUM> or other aspects of SR policy <NUM>. For example, an SR policy may list N destination nodes but deviation <NUM> may specify a number of destination nodes that are allowed to not be reached or the minimum number of destination nodes that must be reached; the number of required hops that can be omitted or the minimum number of required hops that must be included; a percentage reduction or amount/value reduction of bandwidth capacity 920A allowed; and/or a percentage or amount/value that current bound metrics 920F can be exceeded. Some individual constraints in the deviation may be absolute and some relative. Whether absolute or relative, the optimization constraints for the deviation are specified in optimization constraints 912A.

Deviation 910A also includes recomputation policy 912B and accepts empty multipath 912C. Recomputation policy 912B specifies a recomputation policy action that controller <NUM> should perform if the new multipath is determined to satisfy deviation 910A. Example recomputation policy actions include failing the multipath, keeping the current multipath (eschewing recomputation) using the already computed and provisioned lists of SIDs for the SR policy, or recomputing a multipath for the SR policy. Recomputing the multipath would typically involve recomputing the lists of SIDs to realize the recomputed multipath. If the new multipath does not satisfy any of deviations <NUM>, controller <NUM> may recompute a multipath for SR policy <NUM>.

In the case of failing the multipath, the action indicates that the behavior desired after the deviation is to fail the path (remove it from the network rather than recomputing it). For instance, for SR policies configured using a CLI, an automatic recomputation and subsequent reconfiguration may not be allowed. The "fail multipath" allows the SR policy to indicate when the path should be considered failed (and still not recompute it).

Accepts empty multipath 912C is a Boolean setting that indicates if a deviation is acceptable in the special case where the multipath on the new topology has become empty.

Deviations <NUM> may be ordered according to a preference, e.g., 910A most preferred through 910N least preferred. Controller <NUM> may evaluate deviations <NUM> according to this ordering, and controller <NUM> may perform the recomputation policy 912B action for the first one of deviations <NUM> found to be satisfied by the new multipath (expanded by controller <NUM> from the lists of SIDs using the modified network topology).

<FIG> is a flow diagram illustrating an example operation of a computing device, in accordance with the claimed invention and one or more techniques of this disclosure. The computing device may be controller <NUM>, controller <NUM>, or one or more of network nodes <NUM>, for instance.

As seen in the example of <FIG>, the computing device initial receives an indication of a modified network topology for a segment routing-enabled network comprising one or more network nodes (<NUM>). The computing device determines whether an existing, first multipath in the modified network topology for the network satisfies a path computation deviation for a segment routing (SR) policy (<NUM>). The first multipath is 'existing' in that it has been provisioned to the segment routing-enabled network using one or more lists of SIDs. The multipath may be in use to transport traffic mapped to the SR policy. The path computation deviation is a deviation from an initial path computation constraint for the segment routing policy. The computing device, when the first multipath in the modified network topology for the network satisfies the path computation deviation for the segment routing policy (YES branch of <NUM>), performs a recomputation policy action that is associated with the path computation deviation (<NUM>). The recomputation policy action comprises eschewing recomputation of a multipath for the segment routing policy. However, the computing device, when the first multipath in the modified network topology for the network does not satisfy the path computation deviation for the segment routing policy (NO branch of <NUM>), computes a second multipath in the modified network topology for the network to satisfy the initial path computation constraint for the segment routing policy (<NUM>). If the computing device computes a second multipath as a recomputation for the segment routing policy, the computing device subsequently computes one or more lists of SIDs to implement the second multipath in the network nodes, and provisions the one or more lists of SIDs in the network.

If implemented in hardware, this disclosure may be directed to an apparatus such a processor or an integrated circuit device, such as an integrated circuit chip or chipset. Alternatively or additionally, if implemented in software or firmware, the techniques may be realized at least in part by a computer-readable data storage medium comprising instructions that, when executed, cause a processor to perform one or more of the methods described above. For example, the computer-readable data storage medium may store such instructions for execution by a processor.

A computer-readable medium or computer-readable storage device may form part of a computer program product, which may include packaging materials. A computer-readable medium may comprise a computer data storage medium such as random access memory (RAM), read-only memory (ROM), nonvolatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), Flash memory, magnetic or optical data storage media, and the like. In some examples, an article of manufacture may comprise one or more computer-readable storage media.

In some examples, the computer-readable media may comprise non-transitory media. The term "non-transitory" may indicate that the medium is not embodied in a carrier wave or a propagated signal. In certain examples, a non-transitory medium may store data that can, over time, change (e.g., in RAM or cache). Additionally or alternatively, the computer-readable media can include transient media such as carrier signals and transmission media.

Claim 1:
A method comprising:
by a computing device, in response to receiving (<NUM>) an indication of a modified network topology for a segment routing-enabled network comprising one or more network nodes, the modified network topology causing an existing, first multipath for a segment routing policy (<NUM>) to have one or more paths that no longer satisfy an initial path computation constraint (<NUM>) for the segment routing policy:
determining (<NUM>) whether the existing, first multipath in the modified network topology for the network satisfies a path computation deviation (<NUM>) for the segment routing policy, wherein the path computation deviation is a deviation from the initial path computation constraint for the segment routing policy;
when the first multipath in the modified network topology for the network satisfies the path computation deviation for the segment routing policy, performing (<NUM>) a recomputation policy action that is associated with the path computation deviation wherein the recomputation policy action comprises eschewing recomputation of a multipath for the segment routing policy; and
when the first multipath in the modified network topology for the network does not satisfy the path computation deviation for the segment routing policy, computing (<NUM>) a second multipath in the modified network topology for the network to satisfy the initial path computation constraint for the segment routing policy, subsequently computing one or more lists of segments identifiers to implement the second multipath in the network nodes, and provisioning the one or more lists of segments identifiers in the network.