Optimization of segment routing-enabled multipath network

Patent metadata

Field	Value
Publication number	US-11677659-B2
Application number	US-202117446375-A
Country	US
Kind code	B2
Filing date	Aug 30, 2021
Priority date	Aug 30, 2021
Publication date	Jun 13, 2023
Grant date	Jun 13, 2023

Abstract

Techniques are described for optimizing multipaths of a segment routing-enabled network. For example, a computing device is configured to: for each link in a network layer of a multi-layer network, compute a usage (metric) of the link by all paths of a first plurality of multipaths provisioned in the network layer to compute a total usage by the first plurality of multipaths, the first plurality of multipaths having been computed and placed to a model of the network layer in a first order; compute a second plurality of multipaths, wherein the second plurality of multipaths are computed and placed, to the model of the network layer, in a second, different order; and in response to determining that the total usage by the second plurality of multipaths is less than the total usage by the first plurality of multipaths, provision the second plurality of multipaths in the network layer.

First claim

What is claimed is:

1. A method comprising:
by a computing system having a model of a multi-layer network comprising a network layer having a plurality of links, for each link of the plurality of links, computing a usage of a metric of the link by all paths of a first plurality of multipaths provisioned in the network layer to compute a total usage by the first plurality of multipaths,
wherein multipaths of the first plurality of multipaths have been computed and placed to a model of the network layer in a first order, and
wherein the multipaths of the first plurality of multipaths correspond to different, respective segment routing policies;

computing, by the computing system, a second plurality of multipaths for the respective segment routing policies, wherein computing the second plurality of multipaths comprises computing and placing, to the model of the network layer, multipaths of the second plurality of multipaths in a second, different order than the multipaths of the first plurality of multipaths;
computing, by the computing system, for each link of the plurality of links, a usage of the metric of the link by all paths of the second plurality of multipaths to compute a total usage by the second plurality of multipaths; and
in response to determining that the total usage by the second plurality of multipaths is less than the total usage by the first plurality of multipaths, provisioning, by the computing system, the second plurality of multipaths in the network layer.

2. The method of claim 1 , wherein computing the total usage by the first plurality of multipaths comprises computing a total weighted bandwidth usage and a total weighted bandwidth capacity of the first plurality of multipaths.

3. The method of claim 1 , wherein computing the usage of the metric of the link by all paths of the first plurality of multipaths comprises:
determining a fraction of bandwidth of the link used by a particular path of the first plurality of multipaths and a bandwidth capacity available to the link for the first plurality of multipaths.

4. The method of claim 1 , wherein computing and placing to the model of the network layer, the multipaths of the second plurality of paths multipaths in the second, different order to generate the second plurality of multipaths is based on a greedy algorithm.

5. The method of claim 1 , wherein computing and placing to the model of the network layer, the multipaths of the second plurality of multipaths in the second, different order to generate the second plurality of multipaths is based on a random order.

6. The method of claim 1 , wherein computing and placing to the model of the network layer, the multipaths of the second plurality of multipaths in the second, different order to generate the second plurality of multipaths is based on respective priorities assigned to the segment routing policies.

7. The method of claim 6 , wherein the respective priorities assigned to the segment routing policies comprises at least one of a priority to enable modification of corresponding multipaths of the first plurality of multipaths or a priority to prevent modification of corresponding multipaths of the first plurality of multipaths.

8. The method of claim 1 , further comprising:
in response to determining that the total usage by the second plurality of multipaths is not less than the total usage by the first plurality of multipaths, leaving the first plurality of multipaths provisioned in the network layer unchanged.

9. The method of claim 1 ,
wherein the multi-layer network comprises a transport layer, and
wherein computing the usage of the metric of the link by all paths of the first plurality of multipaths comprises obtaining a usage of the metric of one or more links in the transport layer mapped to the paths of the first plurality of multipaths.

10. A computing device of a multi-layer network comprising a network layer having a plurality of links, comprising:
a memory; and
processing circuitry in communication with the memory, the processing circuitry and memory being configured to:
for each link of the plurality of links, compute a usage of a metric of the link by all paths of a first plurality of multipaths provisioned in the network layer to compute a total usage by the first plurality of multipaths,
wherein multipaths of the first plurality of multipaths have been computed and placed to a model of the network layer in a first order, and
wherein the multipaths of the first plurality of multipaths correspond to different, respective segment routing policies;

compute a second plurality of multipaths for the respective segment routing policies, wherein computing the second plurality of multipaths comprises computing and placing, to the model of the network layer, multipaths of the second plurality of multipaths in a second, different order than the multipaths of the first plurality of multipaths; and
in response to determining that the total usage by the second plurality of multipaths is less than the total usage by the first plurality of multipaths, provision the second plurality of multipaths in the network layer.

11. The computing device of claim 10 , wherein to compute the total usage by the first plurality of multipaths, the processing circuitry is further configured to:
compute a total weighted bandwidth usage and a total weighted bandwidth capacity of the first plurality of multipaths.

12. The computing device of claim 10 , wherein to compute the total usage by the first plurality of multipaths, the processing circuitry is further configured to:
determine a fraction of bandwidth of the link used by a particular path of the first plurality of multipaths and a bandwidth capacity available to the link for the plurality of multipaths.

13. The computing device of claim 10 , wherein to compute and place to the model of network layer, the multipaths of the second plurality of multipaths in the second, different order to generate the second plurality of multipaths is based on a greedy algorithm.

14. The computing device of claim 10 , wherein to compute and place to the model of network layer, the multipaths of the second plurality of multipaths in the second, different order to generate the second plurality of multipaths is based on a random order.

15. The computing device of claim 10 , wherein to compute and place to the model of the network layer, the multipaths of the second plurality of multipaths in the second, different order to generate the second plurality of multipaths is based on respective priorities assigned to the segment routing policies.

16. The computing device of claim 15 , wherein the respective priorities assigned to the segment routing policies comprises at least one of a priority to enable modification of corresponding multipaths of the first plurality of multipaths or a priority to prevent modification of corresponding multipaths of the first plurality of multipaths.

17. The computing device of claim 10 , wherein the processing circuitry is further configured to:
in response to determining that the total usage by the second plurality of multipaths is not less than the total usage by the first plurality of multipaths, leave the first plurality of multipaths provisioned in the network layer unchanged.

18. The computing device of claim 10 ,
wherein the multi-layer network comprises a transport layer, and
wherein to compute the usage of the metric of the link by all paths of the first plurality of multipaths, the processing circuitry is further configured to obtain a usage of the metric of o

Assignees

• Juniper Networks Inc

Inventors

• Sidebottom Gregory A
• Boyle James Patrick
• Margaria Cyril

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L45/34

  Source routing · CPC title

• H04L45/42

  Centralised routing · CPC title

• H04L45/64 Primary

  using an overlay routing layer · CPC title