Segment Routing Techniques

• US 20140169370A1
• Filed: 10/07/2013
• Published: 06/19/2014
• 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.
• Granted Patent: US 9,929,946 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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, wherein the segment stack comprises a plurality of segment identifiers (IDs), wherein a first segment ID of the plurality of segment IDs identifies a path calculated using a first algorithm, wherein the second segment ID of the plurality of segment IDs identifies a path calculated using a second algorithm, and wherein the first and second algorithms are different algorithms;

inserting the segment stack into a packet header; and

sending a packet to another node via a network interface, wherein the packet comprises the packet header, and wherein the creating, the inserting, and the sending are performed by a router configured to perform segment routing.

2. The method of claim 1, further comprising:

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

3. The method of claim 1, further comprising:

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

4. The method of claim 3, further comprising:

receiving a second nodal-segment ID for the router in a second message from the PCE server, wherein the second message also comprises information identifying an algorithm to use when calculating a second path to the router, wherein the second path is identified by the second nodal-segment ID, and wherein the second path is calculated using a different algorithm than the first path.

5. The method of claim 1, further comprising:

sending a link state packet to another node from the router, wherein the link state packet comprises information identifying a nodal-segment ID of a path leading to the router and information identifying an algorithm used to calculate the 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, wherein the link state packet associates the segment with a nodal-segment ID, wherein the link state packet is sent by a node to which the nodal-segment ID is assigned, and wherein the second domain comprises the router.

7. The method of claim 6, further comprising:

generating an additional segment stack comprising the nodal-segment ID and a 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. A network device comprising:

one or more interfaces;

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

a processor configured to routing engine configured to;

create a segment stack from a information in the SR forwarding table, wherein the segment stack comprises a plurality of segment identifiers (IDs), wherein a first segment ID of the plurality of segment IDs identifies a path calculated using a first algorithm, wherein the second segment ID of the plurality of segment IDs identifies a path calculated using a second algorithm, and wherein the first and second algorithms are different algorithms;

insert the segment stack into a packet header; and

send a packet to another node via one of the one or more network interfaces, wherein the packet comprises the packet header.

9. The network device of claim 8, wherein the processor is further configured to send a request for a nodal-segment ID for the network device, via one of the plurality of interfaces, from the network device to a path computation element (PCE) server.

10. The network device of claim 8, wherein the processor is further configured to detect reception, via one of the plurality of interfaces, of a nodal-segment ID for the network device in a message from a PCE server, wherein the path is identified by the nodal-segment ID.

11. The network device of claim 10, wherein the processor is further configured to detect reception, via one of the plurality of interfaces, 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 second path to the network device, wherein the second path is identified by the second nodal-segment ID, and wherein the second path is calculated using a different algorithm than the first path.

12. The network device of claim 8, wherein the processor is further configured to send, via one of the plurality of interfaces, a link state packet to another node from the network device, wherein the link state packet comprises information identifying a nodal-segment ID of a path leading to the network device and information identifying an algorithm used to calculate the path.

13. The network device of claim 8, wherein the processor is further configured to detect reception, via one of the plurality of interfaces, 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, wherein the link state packet associates the segment with a nodal-segment ID, wherein the link state packet is sent by a node to which the nodal-segment ID is assigned, and wherein the second domain comprises the network device.

14. The network device of claim 13, wherein the processor is further configured to:

generate an additional segment stack comprising the nodal-segment ID and a 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.

15. 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 segment stack comprises a plurality of segment identifiers (IDs), wherein a first segment ID of the plurality of segment IDs identifies a path calculated using a first algorithm, wherein the second segment ID of the plurality of segment IDs identifies a path calculated using a second algorithm, wherein the first and second algorithms are different algorithms, and wherein the processing means are also means for inserting the segment stack into a packet header; and

network interface means for sending a packet to another node via a network interface, wherein the packet comprises the packet header.