Segment routing techniques

• US 10,469,370 B2
• Filed: 11/30/2017
• Issued: 11/05/2019
• Est. Priority Date: 10/05/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Bryant, Stewart F., Frost, Daniel C., Evans, John W.
• Primary Examiner(s): Rutkowski, Jeffrey M
• Assistant Examiner(s): Tacdiran, Andre
• Application Number:
  US15/827,973
• Publication Number:
  US 20180083871A1
• Time in Patent Office: 705 Days
• Field of Search: None
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation

Abstract

An apparatus and method is disclosed for segment routing (SR). In one embodiment, the method includes a node creating a segment stack that identifies one segment calculated using a first algorithm and a second segment calculated using a second, different algorithm. The node then attaches this header to a packet and sends it to another node.

Claims

1. A method comprising:

receiving a first packet at a first node, wherein

the first packet comprises a segment stack,

the segment stack comprises a plurality of segment identifiers (IDs) that define a segment-switched path across a provider network,

a first segment ID of the plurality of segment IDs is an adjacency segment ID, wherein

the adjacency segment ID identifies a first segment that is a first sub-path of the segment-switched path, and

the first segment is an adjacency segment linking two adjacent nodes, and

a second segment ID of the plurality of segment IDs is a nodal segment ID, wherein

the nodal segment ID identifies a second segment that is a second sub-path of the segment-switched path, and

the second segment is a nodal segment comprising a plurality of hops within the provider network;

analyzing the segment stack to determine a segment type identified by an active segment ID in the segment stack;

in response to determining that the segment type identified by the active segment ID is that of the adjacency segment, sending the first packet to an adjacent node as identified by the adjacency segment ID; and

in response to determining that the segment type identified by the active segment ID is that of the nodal segment, sending the first packet to a non-adjacent node via the nodal segment.

2. The method of claim 1, further comprising:

removing the active segment ID from the segment stack, thereby creating a new active segment ID.

3. The method of claim 2, further comprising:

receiving the first packet at a second node, and

in response to receiving the first packet at the second node, analyzing the segment stack to determine a segment type identified by the new active segment ID in the segment stack.

4. The method of claim 3, further comprising:

prior to sending the first packet to a third node, determining a next node to send the first packet to, wherein

the nodal segment comprises the next node.

5. The method of claim 4, wherein

the nodal segment is selected from at least a first nodal segment and a second nodal segment, wherein

each of the first nodal segment and the second nodal segment can be used to reach the next node.

6. A network device comprising:

one or more network interface cards;

a memory storing a segment routing (SR) forwarding table; and

a processor configured to a method comprising;

receiving a first packet at a first node, wherein

the first packet comprises a segment stack,

the segment stack comprises a plurality of segment identifiers (IDs) that define a segment-switched path across a provider network,

a first segment ID of the plurality of segment IDs is an adjacency segment ID, wherein

the adjacency segment ID identifies a first segment that is a first sub-path of the segment-switched path, and

the first segment is an adjacency segment linking two adjacent nodes, and

a second segment ID of the plurality of segment IDs is a nodal segment ID,

wherein

the nodal segment ID identifies a second segment that is a second sub-path of the segment-switched path, and

the second segment is a nodal segment comprising a plurality of hops within the provider network;

analyzing the segment stack to determine a segment type identified by an active segment ID in the segment stack;

in response to determining that the segment type identified by the active segment ID is that of the adjacency segment, sending the first packet to an adjacent node as identified by the adjacency segment ID; and

in response to determining that the segment type identified by the active segment ID is that of the nodal segment, sending the first packet to a non-adjacent node via the nodal segment.

7. The network device of claim 6, wherein the method further comprises:

removing the active segment ID from the segment stack, thereby creating a new active segment ID.

8. The network device of claim 7, wherein the method further comprises:

receiving the first packet at a second node, and

in response to receiving the first packet at the second node, analyzing the segment stack to determine a segment type identified by the new active segment ID in the segment stack.

9. The network device of claim 8, wherein the method further comprises:

prior to sending the first packet to a third node, determining a next node to send the first packet to, wherein

the nodal segment comprises the next node.

10. The network device of claim 9, wherein

the nodal segment is selected from at least a first nodal segment and a second nodal segment, wherein

each of the first nodal segment and the second nodal segment can be used to reach the next node.

11. A system comprising:

a first node configured to receive a first packet at a first node, wherein

the first packet comprises a segment stack,

the segment stack comprises a plurality of segment identifiers (IDs) that define a segment-switched path across a provider network,

a first segment ID of the plurality of segment IDs is an adjacency segment ID, wherein

the adjacency segment ID identifies a first segment that is a first sub-path of the segment-switched path, and

the first segment is an adjacency segment linking two adjacent nodes, and

a second segment ID of the plurality of segment IDs is a nodal segment ID, wherein

the nodal segment ID identifies a second segment that is a second sub-path of the segment-switched path, and

the second segment is a nodal segment comprising a plurality of hops within the provider network; and

a forwarding module configured to;

analyze the segment stack to determine a segment type identified by an active segment ID in the segment stack, and

in response to determining that the segment type identified by the active segment ID is that of the adjacency segment, send the first packet to an adjacent node as identified by the adjacency segment ID, and

in response to determining that the segment type identified by the active segment ID is that of the nodal segment, sending the first packet to a non-adjacent node via the nodal segment.

12. The system of claim 11, wherein the forwarding module is further configured to:

removing the active segment ID from the segment stack, thereby creating a new active segment ID.

13. The system of claim 12, further comprising:

a second node configured to

receive the first packet, and

in response to receiving the first packet, analyze the segment stack to determine a segment type identified by the new active segment ID in the segment stack.

14. The system of claim 13, wherein the second node is further configured to:

prior to sending the first packet to a third node, determine a next node to send the first packet to, wherein

the nodal segment comprises the next node.