Granted Patent B2

US 12,659,261 · App. 18/532,088 · Granted Jun 16, 2026

Inventors: Todd Defilippi (Redwood City, CA); Cengiz Alaettinoglu (Sherman Oaks, CA)

Assignee: Ciena Corporation

H04L45/122H04L45/03H04L45/34

Abstract

Claims (46)

1 . A non-transitory computer-readable medium comprising instructions that, when executed, cause one or more processors, to perform steps of:

tracking one or more provisioned paths for one or more Segment Routing (SR) policies in a Segment Routing network, based on maintaining Shortest Path First (SPF) pairs and corresponding SPF trees associated with segments of the one or more provisioned paths;

responsive to routing changes in the Segment Routing network, detecting affected SPF pairs based on change to corresponding SPF trees for determining which of the SPF pairs are affected due to their SPF trees changing based on the routing changes, wherein detecting comprises, for each SPF pair, comparing its SPF-tree path before and after the routing change and deeming the SPF pair affected when the paths differ; and

determining which of the one or more SR policies have veered off of their respective provisioned path based on which of the SPF pairs are affected by the routing changes.

2 . The non-transitory computer-readable medium of claim 1 , wherein the determining which of the SPF pairs are affected includes, for a given SPF pair,

determining a first path taken by the given SPF pair on its SPF tree before the routing change;

determining a second path taken by the given SPF pair on its SPF tree after the routing change; and

determining the given SPF pair is affected if the second path and the first path no longer match after the routing change.

3 . The non-transitory computer-readable medium of claim 2 , wherein the SPF tree is updated based on the routing change using dynamic SPF algorithms which update the SPF tree based on the routing change instead of recomputing the SPF tree entirely.

4 . The non-transitory computer-readable medium of claim 1 , wherein the SPF trees changing based on the routing changes are updated using dynamic SPF algorithms which update the SPF tree based on the routing change instead of recomputing the SPF tree entirely.

5 . The non-transitory computer-readable medium of claim 1 , wherein the tracking includes an index of the SPF pairs and which segment lists of the one or more provisioned paths expanded include each of the SPF pairs, such that a plurality of provisioned paths use a same SPF pair.

6 . The non-transitory computer-readable medium of claim 1 , wherein the determining which of the one or more SR policies have veered off of their respective provisioned path includes

for the one or more SR policies that have SPF pairs that are affected, performing a full expansion of all segments to check if an expanded path based on the full expansion matches a corresponding provisioned path.

7 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include

for the one or more SR policies that have veered off of their respective provisioned path, determining a respective new segment list that matches their respective provisioned path after the routing changes.

8 . An apparatus comprising:

at least one processor, and

memory storing instructions that, when executed, cause the at least one processor to

track one or more provisioned paths for one or more Segment Routing (SR) policies in a Segment Routing network, based on maintaining Shortest Path First (SPF) pairs and corresponding SPF trees associated with segments of the one or more provisioned paths,

responsive to routing changes in the Segment Routing network, detect affected SPF pairs based on change to corresponding SPF trees to determine which of the SPF pairs are affected due to their SPF trees changing based on the routing changes, wherein the affected SPF pairs are detected by, for each SPF pair comparing its SPF-tree path before and after the routing change and deeming the SPF pair affected when the paths differ, and

determine which of the one or more SR policies have veered off of their respective provisioned path based on which of the SPF pairs are affected by the routing changes.

9 . The apparatus of claim 8 , wherein, to determine which of the SPF pairs are changed includes, for a given SPF pair, the instructions that, when executed, further cause the at least one processor to

determine a first path taken by the given SPF pair on its SPF tree before the routing change,

determine a second path taken by the given SPF pair on its SPF tree after the routing change, and

determine the given SPF pair is affected if the second path and the first path no longer match after the routing change.

10 . The apparatus of claim 9 , wherein the SPF tree is updated based on the routing change using dynamic SPF algorithms which update the SPF tree based on the routing change instead of recomputing the SPF tree entirely.

11 . The apparatus of claim 8 , wherein the SPF trees changing based on the routing changes are updated using dynamic SPF algorithms which update the SPF tree based on the routing change instead of recomputing the SPF tree entirely.

12 . The apparatus of claim 8 , wherein the provisioned paths are tracked using an index of the SPF pairs and which of segment lists the one or more provisioned paths expanded include each of the SPF pairs, such that a plurality of provisioned paths use a same SPF pair.

13 . The apparatus of claim 8 , wherein, to determine which of the one or more SR policies have veered off of their respective provisioned path, the instructions that, when executed, further cause the at least one processor to

for the one or more SR policies that have SPF pairs that are affected, perform a full expansion of all segments to check if an expanded path based on the full expansion matches a corresponding provisioned path.

14 . The apparatus of claim 8 , wherein the instructions that, when executed, further cause the at least one processor to

for the one or more SR policies that have veered off of their respective provisioned path, determine a respective new segment list that matches their respective provisioned path after the routing changes.

15 . A method comprising steps of:

tracking one or more provisioned paths for one or more Segment Routing (SR) policies in a Segment Routing network, based on maintaining Shortest Path First (SPF) pairs and corresponding SPF trees associated with segments of the one or more provisioned paths;

responsive to routing changes in the Segment Routing network, detecting affected SPF pairs based on change to corresponding SPF trees for determining which of the SPF pairs are affected due to their SPF trees changing based on the routing changes, wherein detecting comprises, for each SPF pair, comparing its SPF-tree path before and after the routing change and deeming the SPF pair affected when the paths differ; and

determining which of the one or more SR policies have veered off of their respective provisioned path based on which of the SPF pairs are affected by the routing changes.

16 . The method of claim 15 , wherein the determining which of the SPF pairs are affected includes, for a given SPF pair,

determining a first path taken by the given SPF pair on its SPF tree before the routing change;

determining a second path taken by the given SPF pair on its SPF tree after the routing change; and

determining the given SPF pair has changed if the second path and the first path no longer match after the routing change.

17 . The method of claim 15 , wherein the SPF trees changing based on the routing changes are updated using dynamic SPF algorithms which update the SPF tree based on the routing change instead of recomputing the SPF tree entirely.

18 . The method of claim 15 , wherein the tracking includes an index of the SPF pairs and which segment lists of the one or more provisioned paths expanded include each of the SPF pairs, such that a plurality of provisioned paths use a same SPF pair.

19 . The method of claim 15 , wherein the determining which of the one or more SR policies have veered off of their respective provisioned path includes

for the one or more SR policies that have SPF pairs that are affected, performing a full expansion of all segments to check if an expanded path based on the full expansion matches a corresponding provisioned path.

20 . The method of claim 15 , wherein the steps further include

for the one or more SR policies that have veered off of their respective provisioned path, determining a respective new segment list that matches their respective provisioned path after the routing changes.

Assignments (1)

Continuity (1)

References Cited (43)