Bandwidth constraint for multipath segment routing

Patent metadata

Field	Value
Publication number	US-11516114-B2
Application number	US-202117214617-A
Country	US
Kind code	B2
Filing date	Mar 26, 2021
Priority date	Sep 30, 2020
Publication date	Nov 29, 2022
Grant date	Nov 29, 2022

Abstract

In an example, a method includes computing, by a computing device, for a segment routing policy that specifies a bandwidth constraint for the segment routing policy, first shortest paths through a network of network nodes, wherein each shortest path of the first shortest paths represents a different sequence of links connecting pairs of the network nodes from a source to a destination; in response to determining, by the computing device based on the bandwidth constraint for the segment routing policy, a link of one of the first shortest paths has insufficient bandwidth to meet a required bandwidth for the link, increasing a metric of the link; computing, by the computing device, for the segment routing policy that specifies the bandwidth constraint, based on the increased metric of the link, second shortest paths through the network of network nodes; and provisioning the second shortest paths in the network of nodes.

First claim

What is claimed is:

1. A method comprising:
computing, by a computing device, for a segment routing policy that specifies a bandwidth constraint for the segment routing policy, first shortest paths through a network of network nodes, wherein each shortest path of the first shortest paths represents a different sequence of links connecting pairs of the network nodes from a source to a destination;
in response to determining, by the computing device based on the bandwidth constraint for the segment routing policy, a link of one of the first shortest paths has insufficient bandwidth to meet a required bandwidth for the link, increasing a metric of the link;
computing, by the computing device, for the segment routing policy that specifies the bandwidth constraint for the segment routing policy, based on the increased metric of the link, second shortest paths through the network of network nodes; and
provisioning the second shortest paths in the network of network nodes.

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

3. The method of claim 1 , wherein the metric of the link is a link bandwidth overflow metric of the link that is separate from a policy metric of the link.

4. The method of claim 3 ,
wherein increasing the metric of the link comprises increasing the link bandwidth overflow metric of the link, and
wherein computing the second shortest paths comprises:
computing a combined metric of the link as a combination of the link bandwidth overflow metric of the link and the policy metric of the link; and
executing a shortest path algorithm with the combined metric of the link to compute the second shortest paths.

5. The method of claim 1 , further comprising:
computing, by the computing device, one or more lists of segment identifiers to realize the second shortest paths in the network of network nodes,
wherein provisioning the second shortest paths in the network of network nodes comprises provisioning the one or more lists of segment identifiers in an ingress node of the network nodes.

6. The method of claim 5 , wherein the ingress node load balances traffic steered to the segment routing policy on the second shortest paths provisioned in the network.

7. The method of claim 1 , further comprising:
computing, by the computing device, based on the bandwidth constraint for the segment routing policy, the required bandwidth for the link as an amount of traffic, for the segment routing policy, that would be forwarded by the network nodes on the link.

8. The method of claim 1 ,
wherein the segment routing policy specifies a plurality of sources and a plurality of destinations, and
wherein the second shortest paths are a first multipath for a first source of the plurality of sources to at least one of the plurality of destinations, the method further comprising:
updating a link bandwidth for each link used by the first multipath;
computing, by the computing device, a second multipath for a second source of the plurality of sources to at least one of the plurality of destinations; and
in response to determining each link used by the first multipath and the second multipath has sufficient bandwidth for the first multipath and the second multipath, provisioning the first multipath and the second multipath in the network.

9. The method of claim 1 , wherein the bandwidth constraint for the segment routing policy comprises an amount of bandwidth that a combined bandwidth of shortest paths through the network of network nodes must satisfy to implement the segment routing policy.

10. A computing device comprising:
a memory; and
processing circuitry in communication with the memory, the processing circuitry and memory being configured to:
compute, for a segment routing policy that specifies a bandwidth constraint for the segment routing policy, first shortest paths through a network of network nodes, wherein each shortest path of the first shortest paths represents a different sequence of links connecting pairs of the network nodes from a source to a destination;
in response to determining, based on the bandwidth constraint for the segment routing policy, a link of one of the first shortest paths has insufficient bandwidth to meet a required bandwidth for the link, increase a metric of the link;
compute for the segment routing policy that specifies the bandwidth constraint for the segment routing policy, based on the increased metric of the link, second shortest paths through the network of network nodes; and
provision the second shortest paths in the network of network nodes.

11. The computing device of claim 10 , wherein the computing device comprises one of a controller for the network or a network node of the network nodes.

12. The computing device of claim 10 , wherein the metric of the link is a link bandwidth overflow metric of the link that is separate from a policy metric of the link.

13. The computing device of claim 12 ,
wherein increasing the metric of the link comprises increasing the link bandwidth overflow metric of the link, and
wherein to compute the second shortest paths the processing circuitry and memory are configured to:
compute a combined metric of the link as a combination of the link bandwidth overflow metric of the link and the policy metric of the link; and
execute a shortest path algorithm with the combined metric of the link to compute the second shortest paths.

14. The computing device of claim 10 ,
wherein the processing circuitry and memory are configured to compute one or more lists of segment identifiers to realize the second shortest paths in the network of network nodes, and
wherein to provision the second shortest paths in the network of network nodes the processing circuitry and memory are configured to provision the one or more lists of segment identifiers in an ingress node of the network nodes.

15. The computing device of claim 14 , wherein the second shortest paths provisioned in the network cause an ingress node to load balance traffic steered to the segment routing policy on the second shortest paths provisioned in the network.

16. The computing device of claim 10 , wherein the processing circuitry and memory are configured to:
compute based on the bandwidth constraint for the segment routing policy, the required bandwidth for the link as an amount of traffic, for the segment routing policy, that would be forwarded by the network nodes on the link.

17. The computing device of claim 10 ,
wherein the segment routing policy specifies a plurality of sources and a plurality of destinations, and
wherein the second shortest paths are a first multipath for a first source of the plurality of sources to at least one of the plurality of destinations, and
wherein the processing circuitry and memory are configured to:
update a link bandwidth for each link used by the first multipath;
compute a second multipath for a second source of the plurality of sources to at least one of the plurality of destinations; and
in response to determining each link used by the first multipath and the second multipath has sufficient bandwidth for the first multipath and the second multipath, provision the first multipath and the second multipath in the network.

18. The computing device of claim 10 , wherein the bandwidth constraint for the segment routing policy comprises an amount of bandwidth that a combined bandwidth of shortest paths through the network of network nodes must satisfy to implement the segment routin

Assignees

• Juniper Networks Inc

Inventors

• Margaria Cyril
• Sidebottom Gregory A
• Chen Richard M

Classifications

• H04L45/123

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

• H04L47/20

  Traffic policing · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L41/0806

  for initial configuration or provisioning, e.g. plug-and-play · CPC title