Enforcing strict shortest path forwarding using strict segment identifiers
Various systems and methods for using strict path forwarding. For example, one method involves receiving an advertisement at a node. The advertisement includes a segment identifier (SID). In response to receiving the advertisement, the node determines whether the SID is a strict SID or not. If the SID is a strict SID, the node generates information, such as forwarding information that indicates how to forward packets along a strict shortest path corresponding to the strict SID.
1. A method comprising:
at each of a plurality of nodes interconnected via a network, generating an advertisement and transmitting the advertisement to other nodes on the network;
the advertisement comprising a segment identifier (SID) assigned to the node that generated and transmitted the advertisement, a value indicating a path calculation metric for the SID, and a value indicating a SID algorithm for the SID, wherein the value for the SID algorithm for the SID corresponds to either a value assigned to a strict shortest path first (strict SPF) algorithm or a value assigned to another algorithm;
at each of the plurality of nodes that receive one or more advertisements, using the received advertisements to update a packet forwarding table; and
at an ingress node associated with the plurality of nodes, receiving a packet, selecting a path comprising a plurality of SIDS between the ingress node and an egress node associated with the plurality of nodes, adding segments in the path to a segment routing (SR) header, and attaching the SR header to the packet;
wherein selecting the path uses only SIDS where the value for the SID algorithm corresponds to the value assigned to the strict SPF algorithm.
2. The method of claim 1 , further comprising forwarding the packet through the plurality of nodes, wherein every node transited by the packet corresponds to a SID advertising a strict SPF algorithm.
3. The method of claim 2 , wherein the node implements the strict SPF algorithm by ignoring any local path instructions that would override a selected shortest path, and only forwarding the packet along the selected shortest path.
4. The method of claim 1 , wherein the path calculation metric supported by the node is a shortest Internal Gateway Protocol (IGP) metric.
5. The method of claim 1 , wherein the path calculation metric supported by the node is a latency metric.
6. The method of claim 1 , wherein selecting the path includes calculating a Forwarding Equivalence Class (FEC) for the packet, and then selecting an ordered list of SIDs associated with the FEC.
7. The method of claim 1 , wherein a subset of the plurality of nodes generates and transmits a second advertisement, the second advertisement comprising a second SID assigned to the node that generated and transmitted the advertisement, a value indicating a path calculation metric for the SID, and a value indicating the SID algorithm for the SID, wherein the value indicating the SID algorithm for the SID corresponds to a value assigned to another algorithm.
8. The method of claim 7 , wherein the value indicating the SID algorithm for the SID in the second advertisement corresponds to the value assigned to a non-strict shortest path first (SPF) algorithm.
9. The method of claim 8 , wherein a node from the subset of the plurality of nodes receives a second packet with a SR header that includes a SID corresponding to the non-strict SPF algorithm, and wherein the node from the subset follows a local path instruction and forwards the packet to another node not on a shortest path.
10. A system comprising:
a plurality of nodes interconnected via a network, the plurality of nodes including an ingress node and an egress node;
wherein each node of the plurality of nodes is configured to generate an advertisement and transmit the advertisement to other nodes on the network, the advertisement comprising a segment identifier (SID) assigned to the node that generated and transmitted the advertisement, a value indicating a path calculation metric for the SID, and a value indicating a SID algorithm for the SID, wherein the value for the SID algorithm for the SID corresponds to either a value assigned to a strict shortest path first (strict SPF) algorithm or a value corresponding to another algorithm;
wherein each node in the plurality of nodes is further configured to receive one or more advertisements and use the received advertisements to update a packet forwarding table; and
wherein the ingress node is configured to receive a packet, select a path comprising a plurality of SIDS between the ingress node and the egress node, add segments in the path to a segment routing (SR) header, and attach the SR header to the packet;
wherein the selected path uses only SIDS where the value for the SID algorithm corresponds to the value assigned to the strict SPF algorithm.
11. The system of claim 10 , wherein the system forwards the packet along the selected path through the plurality of nodes, wherein every node transited by the packet corresponds to a SID advertising a strict SPF algorithm.
12. The system of claim 11 , wherein upon receiving a forwarded packet, a node on the selected path implements the strict SPF algorithm by ignoring any local path instructions that would override a selected shortest path, and only forwards the packet to a next hop in the selected shortest path.
13. The system of claim 10 , wherein the path calculation metric supported by the node is a shortest Internal Gateway Protocol (IGP) metric.
14. The system of claim 10 , wherein the path calculation metric supported by the node is a latency metric.
15. The system of claim 10 , wherein ingress node is configured to select the path by calculating a Forwarding Equivalence Class (FEC) for the packet, and then select an ordered list of SIDs associated with the FEC.
16. The system of claim 10 , wherein a subset of the plurality of nodes is configured to generate a second advertisement, the second advertisement comprising a second SID assigned to the node that generated and transmitted the advertisement, a value indicating a path calculation metric for the SID, and a value indicating the SID algorithm for the SID, wherein the value indicating the SID algorithm for the SID corresponds to a value assigned to another algorithm.
17. The system of claim 16 , wherein the value indicating the SID algorithm for the SID in the second advertisement corresponds to the value assigned to a non-strict shortest path first (SPF) algorithm.
18. The system of claim 17 , wherein a node from the subset of the plurality of nodes receives a second packet with a SR header that includes a SID corresponding to the non-strict SPF algorithm, and wherein the node from the subset follows a local path instruction and forwards the packet to another node not on a shortest path.
19. A computer-readable medium encoding instructions, which, when executed by one or more processors associated with a plurality of nodes interconnected via a network, cause actions to be performed, including:
at each of the plurality of nodes interconnected via a network, generating an advertisement and transmitting the advertisement to other nodes on the network;
the advertisement comprising a segment identifier (SID) assigned to the node that generated and transmitted the advertisement, a value indicating a path calculation metric for the SID, and a value indicating a SID algorithm for the SID, wherein the value for the SID algorithm for the SID corresponds to either a value assigned to a strict shortest path first (strict SPF) algorithm or a value corresponding to another algorithm;
at each of the plurality of nodes that receive one or more advertisements, using the received advertisements to update a packet forwarding table; and
at one of the nodes designated as an ingress node, receiving a packet, selecting a path comprising a plurality of SIDs between the ingress node and a node designated as an egress node, adding segments in the path to a segment routing (SR) header, and attaching the SR header to the packet;
wherein selecting the path uses only SIDs where the value for the SID algorithm corresponds to the value assigned to strict SPF.
20. The instructions of claim 19 , wherein the actions further comprise forwarding the packet through the plurality of nodes, wherein every node transited by the packet corresponds to a SID advertising a strict SPF algorithm.
21. The instructions of claim 20 , wherein the actions further comprise implementing the strict SPF algorithm at the node receiving the packet by ignoring any local path instructions that would override a selected shortest path, and only forwarding the packet along the selected shortest path.
22. The instructions of claim 19 , wherein the path calculation metric supported by the node is a shortest Internal Gateway Protocol (IGP) metric.
23. The instructions of claim 19 , wherein the path calculation metric supported by the node is a latency metric.
24. The instructions of claim 19 , wherein selecting the path includes calculating a Forwarding Equivalence Class (FEC) for the packet, and then selecting an ordered list of SIDs associated with the FEC.
25. The instructions of claim 19 , wherein the actions further comprise:
at a subset of the plurality of nodes, generating and transmitting a second advertisement, the second advertisement comprising a second SID assigned to the node that generated and transmitted the advertisement, a value indicating a path calculation metric for the SID, and a value indicating the SID algorithm for the SID, wherein the value indicating the SID algorithm for the SID corresponds to a value assigned to another algorithm.
26. The instructions of claim 25 , wherein the value indicating the SID algorithm for the SID in the second advertisement corresponds to the value assigned to a non-strict shortest path first (SPF) algorithm.
27. The instructions of claim 26 , wherein the actions further comprise:
at the node from the subset of the plurality of nodes, receiving a second packet with a SR header that includes a SID corresponding to the non-strict SPF algorithm, and following a local path instruction and forwarding the packet to a node not on a shortest path.