Using different Flex-Algo topologies for SID list compression
Segment Identifier (SID) list compression includes receiving a calculated path in a Segment Routing network from a headend node to an end node; utilizing a compression approach to determine a segment list that, when expanded, matches the calculated path, wherein each segment in the segment list is identified by a SID, and wherein the SID is selected from any of a base topology in the Segment Routing network and any Flexible Algorithm (Flex-Algo) topologies in the Segment Routing network; and providing the segment list to the headend node. The SID list compression can further include, prior to the receiving, calculating the calculated path from the headend node to the end node based one or more constraints, wherein the SIDs are selected after the calculated path is determined without regard to any purpose of the any Flex-Algo topologies.
1 . A non-transitory computer-readable medium storing instructions that, when executed, cause one or more processors to execute steps of:
receiving a calculated path in a Segment Routing network from a headend node to an end node; and
utilizing a compression approach to determine a segment list that, when expanded, matches the calculated path, wherein each segment in the segment list is identified by a Segment Identifier (SID), and wherein each SID is selected from any of a base topology in the Segment Routing network and any Flexible Algorithm (Flex-Algo) topologies in the Segment Routing network, wherein the compression approach iteratively selects, from among the Flex-Algo topologies, a SID whose shortest-path-first expansion matches a corresponding subpath of the calculated path.
2 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include
providing the segment list to the headend node.
3 . The non-transitory computer-readable medium of claim 1 , wherein the steps further include
prior to the receiving, calculating the calculated path from the headend node to the end node based one or more constraints for a given purpose, wherein SIDs are selected after the calculated path is determined without regard to any purpose of the any Flex-Algo topologies.
4 . The non-transitory computer-readable medium of claim 1 , wherein the segment list includes at least two SIDs from either (1) different Flex-Algo topologies of the any Flex-Algo topologies or (2) from a Flex-Algo topology of the any Flex-Algo topologies and from the base topology.
5 . The non-transitory computer-readable medium of claim 1 , wherein the compression approach selects node SIDs from different Flex-Algo topologies of the any Flex-Algo topologies independently during each iteration.
6 . The non-transitory computer-readable medium of claim 5 , wherein, if it is not possible for the compression approach to select a node SID in a given iteration, the compression approach selects an adjacency SID.
7 . The non-transitory computer-readable medium of claim 1 , wherein the compression approach is a greedy approach that selects a node SID from among all topologies that traverses furthest along the calculated path during each iteration.
8 . The non-transitory computer-readable medium of claim 1 , wherein the compression approach is a thorough approach that selects a node SID from among all topologies in all possible combinations to traverse along the calculated path during each iteration.
9 . A method comprising steps of:
receiving a calculated path in a Segment Routing network from a headend node to an end node; and
utilizing a compression approach to determine a segment list that, when expanded, matches the calculated path, wherein each segment in the segment list is identified by a Segment Identifier (SID), and wherein the SID is selected from any of a base topology in the Segment Routing network and any Flexible Algorithm (Flex-Algo) topologies in the Segment Routing network, wherein the compression approach iteratively selects, from among the Flex-Algo topologies, a SID whose shortest-path-first expansion matches a corresponding subpath of the calculated path.
10 . The method of claim 9 , wherein the steps further include
providing the segment list to the headend node.
11 . The method of claim 9 , wherein the steps further include
prior to the receiving, calculating the calculated path from the headend node to the end node based one or more constraints for a given purpose, wherein SIDs are selected after the calculated path is determined without regard to any purpose of the any Flex-Algo topologies.
12 . The method of claim 9 , wherein the segment list includes at least two SIDs from either (1) different Flex-Algo topologies of the any Flex-Algo topologies or (2) from a Flex-Algo topology of the any Flex-Algo topologies and from the base topology.
13 . The method of claim 9 , wherein the compression approach selects node SIDs from different Flex-Algo topologies of the any Flex-Algo topologies independently during each iteration.
14 . The method of claim 9 , wherein the compression approach is a greedy approach that selects a node SID from among all topologies that traverses furthest along the calculated path during each iteration.
15 . The method of claim 9 , wherein the compression approach is a thorough approach that selects a node SID from among all topologies in all possible combinations to traverse along the calculated path during each iteration.
16 . An apparatus comprising:
one or more processors; and
memory storing instructions, when executed, cause the one or more processors to
receive a calculated path in a Segment Routing network from a headend node to an end node, and
utilize a compression approach to determine a segment list that, when expanded, matches the calculated path, wherein each segment in the segment list is identified by a Segment Identifier (SID), and wherein the SID is selected from any of a base topology in the Segment Routing network and any Flexible Algorithm (Flex-Algo) topologies in the Segment Routing network, wherein the compression approach iteratively selects, from among the Flex-Algo topologies, a SID whose shortest-path-first expansion matches a corresponding subpath of the calculated path.
17 . The apparatus of claim 16 , wherein the instructions, when executed, further cause the one or more processors to
provide the segment list to the headend node.
18 . The apparatus of claim 16 , wherein the instructions, when executed, further cause the one or more processors to
prior to the calculated path being received, calculate the calculated path from the headend node to the end node based one or more constraints for a given purpose, wherein SIDs are selected after the calculated path is determined without regard to any purpose of the any Flex-Algo topologies.
19 . The apparatus of claim 16 , wherein the segment list includes at least two SIDs from either (1) different Flex-Algo topologies of the any Flex-Algo topologies or (2) from a Flex-Algo topology of the any Flex-Algo topologies and from the base topology.
20 . The apparatus of claim 16 , wherein the compression approach selects node SIDs from different Flex-Algo topologies of the any Flex-Algo topologies independently during each iteration.