Segment routing techniques

• US 9,929,946 B2
• Filed: 10/07/2013
• Issued: 03/27/2018
• 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:
  US14/047,310
• Publication Number:
  US 20140169370A1
• Time in Patent Office: 1,632 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:

creating a segment stack at a source router, wherein

the segment stack comprises a plurality of segment identifiers (IDs),

the source router creates the segment stack such that the plurality of segment IDs define a segment-switched path between the source router and a destination router,

a first segment ID of the plurality of segment IDs identifies a first segment that is a first sub-path of the segment-switched path, wherein

the first segment is a nodal segment comprising a plurality of hops within a provider network, and

a second segment ID of the plurality of segment IDs identifies a second segment that is a second sub-path of the segment-switched path, wherein

the second sub-path comprises two adjacent nodes, and

the second segment is an adjacency segment that links the two adjacent nodes;

inserting the segment stack into a packet header; and

sending a packet from the source router to another router via a network interface of the source router, wherein

the packet comprises the packet header.

2. The method of claim 1, further comprising:

sending a request for a nodal-segment ID for the source router from the source router to a path computation element (PCE) server.

3. The method of claim 1, further comprising:

receiving a nodal-segment ID for the source router in a message from a PCE server, wherein a third sub-path of the segment-switched path is identified by the nodal-segment ID.

4. The method of claim 3, further comprising:

receiving a second nodal-segment ID for the source router in a second message from the PCE server, wherein

the second message also comprises information identifying an algorithm to use when calculating a fourth sub-path of the segment-switched path to the source router,

the fourth sub-path of the segment-switched path is identified by the second nodal-segment ID, and

the fourth sub-path of the segment-switched path is calculated using a different algorithm than was used to calculate the third sub-path of the segment-switched path.

5. The method of claim 1, further comprising:

sending a link state packet to the another router from the source router, wherein

the link state packet comprises information identifying a nodal-segment ID,

the nodal-segment ID identifies a third sub-path of the segment-switched path,

the third sub-path of the segment-switched path leads to the source router, and

the information identifies a third algorithm used to calculate the third sub-path of the segment-switched path.

6. The method of claim 1, further comprising:

receiving a link state packet advertising a segment in a first domain, wherein

the link state packet indicates that the segment is being redistributed into a second domain,

the link state packet associates the segment with a nodal-segment ID,

the link state packet is sent by a router to which the nodal-segment ID is assigned, and

the second domain comprises the source router.

7. The method of claim 6, further comprising:

generating an additional segment stack comprising the nodal-segment ID and a third segment ID of the segment in the first domain;

inserting the additional segment stack into an additional header; and

sending an additional packet, wherein the additional packet comprises the additional header.

8. The method of claim 1, further comprising:

detecting whether the first segment ID is associated with a nodal segment, an adjacency segment, or a service segment.

9. The method of claim 1, wherein

the plurality of segment IDs are advertised using a protocol that is not a label distribution protocol.

10. The method of claim 1, wherein

the packet header comprises information identifying a segment ID of the plurality of segment IDs as an active segment ID.

11. The method of claim 10, further comprising:

receiving a second packet comprising a second segment stack;

determining whether a corresponding active segment ID in the second segment stack identifies the source router;

if the determining indicates that the corresponding active segment ID identifies the source router, updating corresponding information in a corresponding packet header of the second packet; and

if the determining indicates that the corresponding active segment ID does not identify the source router, forwarding the second packet without modifying the second segment stack.

12. The method of claim 1, further comprising:

transmitting information that indicates that the source router is configured to use SR, wherein

the information is included in a sub TLV.

13. The method of claim 1, wherein

the segment-switched path comprises a plurality of routers,

the plurality of routers comprise the another router and the destination router, and

the segment stack is configured to control sending of the packet from at least one of the plurality of routers to another of the plurality of routers.

14. The method of claim 1, wherein

the first sub-path of the segment-switched path is calculated using a first algorithm,

the second sub-path of the segment-switched path is calculated using a second algorithm, and

the first algorithm and the second algorithm differ from one another.

15. A network device comprising:

one or more network interface cards;

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

a processor configured to

create a segment stack from information in the SR forwarding table, wherein

the network device is, with respect to the segment stack, a source router,

the segment stack comprises a plurality of segment identifiers (IDs),

the network device creates the segment stack such that the plurality of segment IDs define a segment-switched path between the source router and a destination router,

a first segment ID of the plurality of segment IDs identifies a first segment that is a first sub-path of the segment-switched path, wherein

the first segment is a nodal segment comprising a plurality of hops within a provider network, and

a second segment ID of the plurality of segment IDs identifies a second segment that is a second sub-path of the segment-switched path, wherein

the second sub-path comprises two adjacent nodes, and

the second segment is an adjacency segment that links the two adjacent nodes;

insert the segment stack into a packet header, and

send a packet to another router via a first one of the one or more network interface cards, wherein

the packet comprises the packet header.

16. The network device of claim 15, wherein the processor is further configured to:

send a request for a nodal-segment ID for the network device, via a second one of the one or more network interface cards, from the network device to a path computation element (PCE) server.

17. The network device of claim 15, wherein the processor is further configured to:

detect reception, via a second one of the one or more network interface cards, of a nodal-segment ID for the network device in a message from a PCE server, wherein

a third sub-path of the segment-switched path is identified by the nodal-segment ID.

18. The network device of claim 17, wherein the processor is further configured to:

detect reception, via the second one of the one or more network interface cards, of a second nodal-segment ID for the network device in a second message from the PCE server, wherein

the second message also comprises information identifying an algorithm to use when calculating a fourth sub-path of the segment-switched path to the network device,

the fourth sub-path of the segment-switched path is identified by the second nodal-segment ID, and

the fourth sub-path of the segment-switched path is calculated using a different algorithm than was used to calculate the third sub-path of the segment-switched path.

19. The network device of claim 15, wherein the processor is further configured to:

send, via a second one of the one or more network interface cards, a link state packet to the another router from the network device, wherein

the link state packet comprises information identifying a nodal-segment ID,

the nodal-segment ID identifies a third sub-path of the segment-switched path,

the third sub-path of the segment-switched path leads to the network device, and

the information identifies a third algorithm used to calculate the third sub-path of the segment-switched path.

20. The network device of claim 15, wherein the processor is further configured to:

detect reception, via a second one of the one or more network interface cards, of a link state packet advertising a segment in a first domain, wherein

the link state packet indicates that the segment is being redistributed into a second domain,

the link state packet associates the segment with a nodal-segment ID,

the link state packet is sent by a router to which the nodal-segment ID is assigned, and

the second domain comprises the network device.

21. The network device of claim 20, wherein the processor is further configured to:

generate an additional segment stack comprising the nodal-segment ID and a third segment ID of the segment in the first domain;

insert the additional segment stack into an additional header; and

send an additional packet, wherein the additional packet comprises the additional header.

22. A system comprising:

storage means for storing a segment routing forwarding table;

processing means for creating a segment stack from information in the segment routing forwarding table, wherein

the system is, with respect to the segment stack, a source router,

the segment stack comprises a plurality of segment identifiers (IDs),

the source router creates the segment stack such that the plurality of segment IDs define a segment-switched path between the source router and a destination router,

a first segment ID of the plurality of segment IDs identifies a first segment that is a first sub-path of the segment-switched path, wherein

the first segment is a nodal segment comprising a plurality of hops within a provider network, and

a second segment ID of the plurality of segment IDs identifies a second segment that is a second sub-path of the segment-switched path, wherein

the second sub-path comprises two adjacent nodes, and

the second segment is an adjacency segment that links the two adjacent nodes, and

the processing means are also means for inserting the segment stack into a packet header; and

network interface means for sending a packet from the source router to another router via a network interface, wherein

the packet comprises the packet header.