Enforcing strict shortest path forwarding using strict segment identifiers

• US 10,263,881 B2
• Filed: 05/26/2016
• Issued: 04/16/2019
• Est. Priority Date: 05/26/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Psenak, Peter, Hanzl, Robert, Filsfils, Clarence, Talaulikar, Ketan Jivan
• Primary Examiner(s): Sam, Phirin
• Application Number:
  US15/165,794
• Publication Number:
  US 20170346718A1
• Time in Patent Office: 1,055 Days
• Field of Search: None
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

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.

Claims

1. A method comprising:

receiving an advertisement at a node, wherein

the advertisement comprises a segment identifier (SID);

determining whether the SID is a strict SID, wherein

the strict SID requires that a strict shortest path is used for a segment corresponding to the strict SID; and

in response to determining that the SID is a strict SID, generating information that identifies a portion of a strict shortest path corresponding to the strict SID.

2. The method of claim 1, wherein

the SID comprises a prefix SID associated with a destination.

3. The method of claim 1, wherein

the advertisement comprises an interior gateway protocol (IGP) message having a populated algorithm field, and

the determining whether the SID is a strict SID comprises accessing the populated algorithm field.

4. The method of claim 2, wherein

the node comprises specific path information that specifies a first path to the destination,

the strict shortest path is different than the first path, and

the first path does not comprises a shortest path to a destination associated with the SID.

5. The method of claim 2, further comprising:

updating forwarding information to include the information identifying the strict shortest path; and

the forwarding information includes another SID associated with the destination.

6. The method of claim 2, further comprising:

generating the advertisement; and

generating a second advertisement that includes a second SID associated with the destination.

7. The method of claim 1, further comprising:

generating a strict shortest path that comprises one or more strict SIDs.

8. The method of claim 7, wherein

the strict shortest path comprises a tunnel that comprises one or more strict SIDs.

9. The method of claim 1, further comprising:

generating a backup path that protects one or more strict SIDs, wherein

the backup path comprises one or more strict SIDs, and

the backup path does not comprises any standard SIDs.

10. The method of claim 2, further comprising:

receiving a packet at the node, wherein

the packet comprises the SID, and

the node is configured to forward packets associated with the destination represented by the SID to a tunnel;

performing a lookup using the SID; and

in response to the lookup determining that the SID is a strict SID, preventing the packet from being forwarded to the tunnel.

11. A system comprising:

a first node configured to perform

receiving an advertisement, wherein

the advertisement comprises a segment identifier (SID);

determining whether the SID is a strict SID, wherein

the strict SID requires that a strict shortest path is used for a segment corresponding to the strict SID; and

in response to determining that the SID is a strict SID, generating information that identifies a portion of a strict shortest path corresponding to the strict SID.

12. The system of claim 11, wherein

the advertisement comprises an interior gateway protocol (IGP) message having a populated algorithm field, and

the determining whether the SID is a strict SID comprises accessing the populated algorithm field.

13. The system of claim 11, wherein

the first node comprises specific path information that specifies a first path to a destination,

the strict shortest path is different than the first path, and

the first path does not comprises a shortest path to a destination associated with the SID.

14. The system of claim 11, wherein the first node is further configured to perform:

updating forwarding information to include the information identifying the strict shortest path, wherein

the forwarding information includes another SID associated with a destination.

15. The system of claim 11, wherein the first node is further configured to perform:

receiving a packet at the first node, wherein

the packet comprises the SID;

forwarding one or more packets associated with a destination represented by the SID to a tunnel;

performing a lookup using the SID; and

in response to the lookup determining that the SID is a strict SID, preventing the packet from being forwarded to the tunnel.

16. A non-transitory computer readable storage medium comprising program instructions executable by one or more processors to:

receive an advertisement at a node, wherein

the advertisement comprises a segment identifier (SID);

determine whether the SID is a strict SID, wherein

the strict SID requires that a strict shortest path is used for a segment corresponding to the strict SID; and

in response to determining that the SID is a strict SID, generating information that identifies a portion of a strict shortest path corresponding to the strict SID.

17. The non-transitory computer readable storage medium of claim 16, wherein

the advertisement comprises an interior gateway protocol (IGP) message having a populated algorithm field, and

the determining whether the SID is a strict SID comprises accessing the populated algorithm field.

18. The non-transitory computer readable storage medium of claim 16, wherein

the node comprises specific path information that specifies a first path to a destination,

the strict shortest path is different than the first path, and

the first path does not comprises a shortest path to a destination associated with the SID.

19. The non-transitory computer readable storage medium of claim 16, wherein the instructions are further executable to:

update forwarding information to include the information identifying the strict shortest path; and

the forwarding information includes another SID associated with a destination.

20. The non-transitory computer readable storage medium of claim 16, wherein the instructions are further executable to:

receive an advertisement at a node, wherein

the advertisement comprises a segment identifier (SID);

determine whether the SID is a strict SID;

in response to determining that the SID is a strict SID, generating information that identifies a portion of a strict shortest path corresponding to the strict SID.