Optimization of segment routing-enabled multipath network

Patent metadata

Field	Value
Publication number	US-12137046-B2
Application number	US-202318332864-A
Country	US
Kind code	B2
Filing date	Jun 12, 2023
Priority date	Aug 30, 2021
Publication date	Nov 5, 2024
Grant date	Nov 5, 2024

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:
computing, by a computing system having a model of a multi-layer network, a total usage of a metric by each link of all paths of a first multipath provisioned in a network layer of the multi-layer network, wherein the first multipath is computed and placed to a model of the network layer in a first order;
computing, by the computing system, a total usage of the metric by each link of all paths of a second multipath that is computed and placed to the model in a second, different order; and
in response to determining that the total usage by the second multipath is less than the total usage by the first multipath, provisioning, by the computing system, the second multipath in the network layer.

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

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

4. The method of claim 1 , wherein computing and placing to the model all paths of the second multipath in the second, different order is based on a greedy algorithm.

5. The method of claim 1 , wherein computing and placing to the model all paths of the second multipath in the second, different order is based on a random order.

6. The method of claim 1 , wherein computing and placing to the model all paths of the second multipath in the second, different order is based on a priority assigned to a segment routing policy.

7. The method of claim 6 , wherein the priority assigned to the segment routing policy comprises a priority to enable modification of the first multipath or a priority to prevent modification of the first multipath.

8. The method of claim 1 , further comprising:
in response to determining that the total usage by the second multipath is not less than the total usage by the first multipath, leaving the first multipath 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 by each link of all paths of the first multipath comprises obtaining a usage of the metric of one or more links in the transport layer mapped to the first multipath.

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:
compute a total usage of a metric by each link of all paths of a first multipath provisioned in a network layer of a multi-layer network, wherein the first multipath is computed and placed to a model of the network layer in a first order,
compute a total usage of the metric by each link of all paths of a second multipath that is computed and placed to the model in a second, different order, and
in response to determining that the total usage by the second multipath is less than the total usage by the first multipath, provision the second multipath in the network layer.

11. The computing device of claim 10 , wherein to compute the total usage of the metric by each link of all paths of the first multipath, the processing circuitry is further configured to:
compute a total weighted bandwidth usage and a total weighted bandwidth capacity of the first multipath.

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

13. The computing device of claim 10 , wherein to compute and place to the model all paths of the second multipath in the second, different order is based on a greedy algorithm.

14. The computing device of claim 10 , wherein to compute and place to the model all paths of the second multipath in the second, different order is based on a random order.

15. The computing device of claim 10 , wherein to compute and place to the model all paths of the second multipath in the second, different is based on a priority assigned to a segment routing policy.

16. The computing device of claim 15 , wherein the priority assigned to the segment routing policy comprises a priority to enable modification of the first multipath or a priority to prevent modification of the first multipath.

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 multipath is not less than the total usage by the first multipath, leave the first multipath 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 by each link by all paths of the first multipath, the processing circuitry is further configured to obtain a usage of the metric of one or more links in the transport layer mapped to the first multipath.

19. The computing device of claim 10 , wherein the processing circuitry is further configured to:
determine that the first multipath has an unequitable number of paths;
in response to determining that the first multipath has an unequitable number of paths, compute a total usage of the metric by each link of all paths of a third multipath that is computed and placed to the model in a third, different order; and
in response to determining that the third multipath has an equitable number of paths, provision the third multipath in the network layer.

20. A non-transitory computer-readable storage medium encoded with instructions that, when executed, cause one or more programmable processors to:
compute a total usage of a metric by each link of all paths of a first multipath provisioned in a network layer of a multi-layer network, wherein the first multipath is computed and placed to a model of the network layer in a first order;
compute a total usage of the metric by each link of all paths of a second multipath that is computed and placed to the model in a second, different order; and
in response to determining that the total usage by the second multipath is less than the total usage by the first multipath, provision the second multipath in the network layer.

Assignees

• Juniper Networks Inc

Inventors

• Sidebottom Gregory A
• Boyle James Patrick
• Margaria Cyril

Classifications

• H04L45/34

  Source routing · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L45/42

  Centralised routing · CPC title

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title