Segment routing extension headers

• US 10,382,334 B2
• Filed: 07/31/2018
• Issued: 08/13/2019
• Est. Priority Date: 03/06/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Previdi, Stefano B., Filsfils, Clarence
• Primary Examiner(s): Sheikh, Ayaz R
• Assistant Examiner(s): Asefa, Debebe A
• Application Number:
  US16/050,180
• Publication Number:
  US 20180337856A1
• Time in Patent Office: 378 Days
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A system and method are disclosed for using segment routing (SR) in native IP networks. The method involves receiving a packet. The packet is an IP packet and includes an IP header. The method also involves updating the packet. Updating the packet involves writing information, including a segment routing segment identifier, to the destination address of the packet.

Claims

1. A method comprising:

receiving a packet at a node, wherein the packet comprises an internet protocol (IP) header, which comprises a first extension header, wherein the first extension header comprises a first list of elements, wherein each of the elements in the first list comprises a respective segment identifier (SID);

updating the packet, wherein the updating comprises adding a new element to the first list of elements;

wherein the new element comprises a segment identifier (SID) that identifies the node.

2. The method of claim 1 wherein the packet comprises a second extension header, wherein the second extension header comprises a second list of elements, wherein each element of the second list comprises a respective SID.

3. The method of claim 2 further comprising:

selecting a first element from the first list;

selecting a first element from the second list;

comparing a SID of the first element selected from the first list to a SID of the first element selected from the second list.

4. The method of claim 3 further comprising:

in response to determining that the SID of the first element selected from the first list compares equally to the SID of the first element selected from the second list;

selecting a second element from the first list;

selecting a second element from the second list;

comparing a SID of the second element selected from the first list to a SID of the second element selected from the second list;

setting a bit in response to determining that the SID of the second element selected from the first list does not compare equally to SID of the second element selected from the second list.

5. The method of claim 4 wherein the bit, when set, indicates that the packet was rerouted through a network.

6. The method of claim 3 further comprising:

in response to determining that the SID of the first element selected from the first list compares equally to the SID of the first element selected from the second list;

selecting a second element from the first list;

selecting a second element from the second list;

comparing a SID of the second element selected from the first list to a SID of the second element selected from the second list;

setting a bit to indicate that a path taken by the packet through was completed in response to determining that the SID of the second element selected from the first list compares equally to SID of the second element selected from the second list.

7. A non-transitory computer readable memory (CRM) comprising instructions that are executable by a processor of a node in a network, wherein a method is implemented in response to executing the instructions, the method comprising:

receiving a packet at the node, wherein the packet comprises an internet protocol (IP) header, which comprises a first extension header, wherein the first extension header comprises a first list of elements, wherein each of the elements in the first list comprises a respective segment identifier (SID);

updating the packet, wherein the updating comprises adding a new element to the first list of elements;

wherein the new element comprises a segment identifier (SID) that identifies the node.

8. The non-transitory CRM of claim 7 wherein the packet comprises a second extension header, wherein the second extension header comprises a second list of elements, wherein each element of the second list comprises a respective SID.

9. The non-transitory CRM of claim 8 wherein the method further comprises:

selecting a first element from the first list;

selecting a first element from the second list;

comparing a SID of the first element selected from the first list to a SID of the first element selected from the second list.

10. The non-transitory CRM of claim 9 wherein the method further comprises:

in response to determining that the SID of the first element selected from the first list compares equally to the SID of the first element selected from the second list;

selecting a second element from the first list;

selecting a second element from the second list;

comparing a SID of the second element selected from the first list to a SID of the second element selected from the second list;

setting a bit in response to determining that the SID of the second element selected from the first list does not compare equally to SID of the second element selected from the second list.

11. The non-transitory CRM of claim 10 wherein the bit, when set, indicates that the packet was rerouted through the network.

12. The non-transitory CRM of claim 9 wherein the method further comprises:

in response to determining that the SID of the first element selected from the first list compares equally to the SID of the first element selected from the second list;

selecting a second element from the first list;

selecting a second element from the second list;

comparing a SID of the second element selected from the first list to a SID of the second element selected from the second list;

setting a bit to indicate that a path taken by the packet through was completed in response to determining that the SID of the second element selected from the first list compares equally to SID of the second element selected from the second list.

13. A system comprising:

a node configured to

receive a packet, wherein the packet comprises an internet protocol (IP) header, which comprises a first extension header, wherein the first extension header comprises a first list of elements, wherein each of the elements in the first list comprises a respective segment identifier (SID);

update the packet, wherein the updating comprises adding a new element to the first list of elements;

wherein the new element comprises a segment identifier (SID) that identifies the node.

14. The system of claim 13 wherein the packet comprises a second extension header, wherein the second extension header comprises a second list of elements, wherein each element of the second list comprises a respective SID.

15. The system of claim 14 wherein the node is further configured to:

select a first element from the first list;

select a first element from the second list;

compare a SID of the first element selected from the first list to a SID of the first element selected from the second list.

16. The system of claim 15 wherein the node is further configured to:

in response to determining that the SID of the first element selected from the first list compares equally to the SID of the first element selected from the second list;

select a second element from the first list;

select a second element from the second list;

compare a SID of the second element selected from the first list to a SID of the second element selected from the second list;

set a bit in the packet in response to determining that the SID of the second element selected from the first list does not compare equally to SID of the second element selected from the second list.

17. The system of claim 16 wherein the bit, when set, indicates that the packet was rerouted through a network.

18. The system of claim 14 wherein the node is further configured to:

in response to determining that the SID of the first element selected from the first list compares equally to the SID of the first element selected from the second list;

select a second element from the first list;

select a second element from the second list;

compare a SID of the second element selected from the first list to a SID of the second element selected from the second list;

set a bit to indicate that a path taken by the packet through was completed in response to determining that the SID of the second element selected from the first list compares equally to SID of the second element selected from the second list.