Recomputation of multipaths in a segment routing-enabled network

Patent metadata

Field	Value
Publication number	US-11418428-B2
Application number	US-202117214661-A
Country	US
Kind code	B2
Filing date	Mar 26, 2021
Priority date	Sep 30, 2020
Publication date	Aug 16, 2022
Grant date	Aug 16, 2022

Abstract

In an example, a method comprises, by a computing device, in response to receiving an indication of a modified network topology for a segment routing (SR)-enabled network comprising one or more network nodes: determining whether an existing, first multipath in the modified network topology for the network satisfies a path computation deviation for a SR policy, wherein the path computation deviation is a deviation from an initial path computation constraint for the SR policy; when the first multipath in the modified network topology satisfies the path computation deviation for the SR policy, performing a recomputation policy action that is associated with the path computation deviation; and when the first multipath in the modified network topology does not satisfy the path computation deviation for the SR policy, computing a second multipath in the modified network topology for the network to satisfy the initial path computation constraint for the SR policy.

First claim

What is claimed is:

1. A method comprising:
by a computing device, in response to receiving an indication of a modified network topology for a segment routing-enabled network comprising one or more network nodes:
determining whether an existing, first multipath in the modified network topology for the network satisfies a path computation deviation for a segment routing policy, wherein the path computation deviation is a deviation from an 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 a recomputation policy action that is associated with the path computation deviation; 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 a second multipath in the modified network topology for the network to satisfy the initial path computation constraint for the segment routing policy.

2. The method of claim 1 , wherein the recomputation policy action comprises eschewing recomputation of a multipath for the segment routing policy.

3. The method of claim 1 , wherein the recomputation policy action comprises one of failing the first multipath or recomputing a multipath for the segment routing policy.

4. The method of claim 1 , wherein the first multipath is defined by a list of segment identifiers for the network.

5. The method of claim 4 , wherein determining whether the existing, first multipath in the modified network topology for the network satisfies the path computation deviation for the segment routing policy comprises:
computing the first multipath in the modified network topology by expanding the list of segment identifiers to compute each path in the first multipath used for traffic by the network nodes in the modified network topology.

6. The method of claim 1 , further comprising:
computing, by the computing device, one or more lists of segments identifiers that satisfy each path of the second multipath; and
programming the network to forward network traffic based at least on the one or more lists of segment identifiers.

7. The method of claim 1 , wherein the computing device comprises one of a controller for the network or a network node of the one or more network nodes.

8. The method of claim 1 , wherein the segment routing policy specifies the path computation deviation.

9. The method of claim 1 ,
wherein the initial path computation constraint comprises a bandwidth capacity for each path for the segment routing policy, and
wherein the path computation deviation is a percentage reduction of the bandwidth capacity or a second, reduced amount of bandwidth capacity for each path for the segment routing policy.

10. The method of claim 1 ,
wherein the initial path computation constraint comprises a first set of required hops for each path for the segment routing policy, and
wherein the path computation deviation is (a) a second, different set of required hops for each path for the segment routing policy or (b) a number of the first set of required hops that can be omitted from each path for the segment routing policy.

11. The method of claim 1 ,
wherein the initial path computation constraint comprises a first set of destination nodes for the segment routing policy, and
wherein the path computation deviation is (a) a second, different set of nodes for the segment routing policy or (b) a number of the first set of destination nodes that can be omitted for the segment routing policy.

12. The method of claim 1 ,
wherein the initial path computation constraint comprises a metric bound that can be exceeded by each path for the segment routing policy, and
wherein the path computation deviation is a percentage reduction of the metric bound or a second, different amount of metric bound that can be exceeded by each path for the segment routing policy.

13. The method of claim 1 , wherein the path computation deviation comprises a first path computation deviation of a plurality of path computation deviations ordered according to a preference ordering, the method further comprising:
after performing the recomputation policy action that is associated with the first path computation deviation, eschewing determining whether the existing, first multipath in the modified network topology for the network satisfies any path computation deviation following the first path computing deviation in the preference ordering.

14. A computing device comprising:
a memory; and
processing circuitry in communication with the memory, the processing circuitry and memory being configured to, in response to receiving an indication of a modified network topology for a segment routing-enabled network comprising one or more network nodes:
determine whether an existing, first multipath in the modified network topology for the network satisfies a path computation deviation for a segment routing policy, wherein the path computation deviation is a deviation from an 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, perform a recomputation policy action that is associated with the path computation deviation; 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, compute a second multipath in the modified network topology for the network to satisfy the initial path computation constraint for the segment routing policy.

15. The computing device of claim 14 , wherein the recomputation policy action comprises eschewing recomputation of a multipath for the segment routing policy.

16. The computing device of claim 14 , wherein the recomputation policy action comprises one of failing the first multipath or recomputing a multipath for the segment routing policy.

17. The computing device of claim 14 , wherein the first multipath is defined by a list of segment identifiers for the network, and wherein to determine whether the existing, first multipath in the modified network topology for the network satisfies the path computation deviation for the segment routing policy, the processing circuitry and memory are configured to:
compute the first multipath in the modified network topology by expanding the list of segment identifiers to compute each path in the first multipath used for traffic by the network nodes in the modified network topology.

18. The computing device of claim 14 , wherein the processing circuitry and memory are configured to:
compute one or more lists of segments identifiers that satisfy each path of the second multipath; and
program the network to forward network traffic based at least on the one or more lists of segment identifiers.

19. The computing device of claim 14 , wherein the computing device comprises one of a controller for the network or a network node of the one or more network nodes.

20. A non-transitory computer readable medium encoded with instructions that, when executed, cause processing circuitry to:
in response to receiving an indication of a modified network topology for a segment routing-enabled network comprising one or more network nodes, determine whether an existing, first multipath in the modified network topology for the network satisfies a path computat

Assignees

• Juniper Networks Inc

Inventors

• Margaria Cyril
• Sidebottom Gregory A

Classifications

• H04L45/247

  using M:N active or standby paths · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L45/34 Primary

  Source routing · CPC title

• H04L45/124

  using a combination of metrics · CPC title