Method and system for path monitoring using segment routing

• US 9,369,371 B2
• Filed: 05/30/2014
• Issued: 06/14/2016
• 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, Frost, Daniel C., Bryant, Stewart F., Heidrich, Don R.
• Primary Examiner(s): Duong, Christine
• Application Number:
  US14/292,264
• Publication Number:
  US 20140269266A1
• Time in Patent Office: 746 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A method and system are disclosed for use of segment routing in monitoring of a network path. In one embodiment, the method includes selecting a plurality of segment identifiers and assembling the segment identifiers into a segment identifier stack, where the segment identifier stack encodes a test path within the network for attempted routing of a test message. The method may further include inserting the segment identifier stack into a header associated with the test message, and forwarding the test message according to an entry in a forwarding table corresponding to the segment identifier at the top of the segment identifier stack. Interior gateway protocol advertisements may be used to communicate segment identifiers for creating or updating of the data structure or the forwarding table. In an embodiment, the system includes one or more network interfaces and a processor configured to perform the steps of the method.

Claims

1. A method, comprising:

selecting a plurality of segment identifiers, wherein

said selecting comprises accessing a data structure relating each of the segment identifiers to one or more nodes within a network, and

interior gateway protocol (IGP) advertisements are used to communicate the segment identifiers for creation or updating of the data structure;

assembling the plurality of segment identifiers into a segment identifier stack, wherein the segment identifier stack encodes a test path within the network for attempted routing of a test message;

inserting the segment identifier stack into a header associated with the test message; and

forwarding the test message according to an entry in a forwarding table corresponding to a segment identifier at the top of the segment identifier stack, wherein IGP advertisements are used to communicate the segment identifier at the top of the segment identifier stack for creation or updating of the forwarding table.

2. The method of claim 1, further comprising determining whether the test message is routed through the entirety of the test path.

3. The method of claim 2, further comprising, in response to a determination that the test message is not routed through the entirety of the test path:

assembling a subset of the plurality of segment identifiers into an additional segment identifier stack, wherein the additional segment identifier stack encodes an additional test path for attempted routing of an additional test message, and wherein at least one link between adjacent nodes of the test path is not included in the additional test path;

inserting the additional segment identifier stack into a header associated with the additional test message;

forwarding the additional test message according to a forwarding table entry corresponding to a segment identifier at the top of the additional segment identifier stack; and

determining whether the additional test message is routed through the entirety of the additional test path.

4. The method of claim 1, wherein:

the plurality of segment identifiers comprises an adjacency segment identifier; and

the adjacency segment identifier is related by the data structure to a link between two adjacent nodes of the network.

5. The method of claim 4, wherein the adjacency segment identifier is associated with an instruction not to protect the link represented by the adjacency segment identifier with a backup path in the event of a failure of the link.

6. The method of claim 4, wherein the adjacency segment identifier is associated with an instruction that the link represented by the adjacency segment identifier has failed.

7. The method of claim 1, wherein:

the plurality of segment identifiers comprises a nodal segment identifier;

the nodal segment identifier is related by the data structure to a specific node of the network; and

the nodal segment identifier represents a path through the network to the specific node.

8. The method of claim 7, wherein the nodal segment identifier represents the shortest available path through the network to the specific node.

9. The method of claim 7, wherein the nodal segment identifier is related by the data structure to an internet protocol (IP) loopback address of the specific node.

10. The method of claim 4, wherein:

the plurality of segment identifiers further comprises a nodal segment identifier;

the nodal segment identifier is related by the data structure to a specific node of the network; and

the nodal segment identifier represents a path through the network to the specific node.

11. The method of claim 10, wherein said assembling comprises placing the nodal segment identifier at the top of the segment identifier stack and at least one adjacency segment identifier in a remainder of the segment identifier stack.

12. A monitoring system comprising:

one or more network interfaces adapted for data communication with one or more respective network nodes; and

a processor configured to

select a plurality of segment identifiers,

access a data structure relating each of the plurality of segment identifiers to one or more nodes within a network, wherein interior gateway protocol (IGP) advertisements are used to communicate the segment identifiers for creation or updating of the data structure,

assemble the plurality of segment identifiers into a segment identifier stack, wherein the segment identifier stack encodes a test path within the network for attempted routing of a test message,

insert the segment identifier stack into a header associated with the test message, and

forward the test message according to an entry in a forwarding table corresponding to a segment identifier at the top of the segment identifier stack, wherein IGP advertisements are used to communicate the segment identifier at the top of the segment identifier stack for creation or updating of the forwarding table.

13. The monitoring system of claim 12, further comprising:

the data structure;

the forwarding table; and

a routing engine adapted to

receive segment identifiers communicated using IGP advertisements,

create the data structure relating segment identifiers to one or more nodes within the network, and

create the forwarding table, wherein the forwarding table relates segment identifiers to corresponding network interfaces for forwarding of a message.

14. The monitoring system of claim 12, wherein the processor is further configured for data communication with a network node via the network interface, and the network node comprises:

the data structure;

the forwarding table; and

a routing engine adapted to

receive segment identifiers communicated using IGP advertisements,

create the data structure relating segment identifiers to one or more nodes within the network, and

create the forwarding table, wherein the forwarding table relates segment identifiers to corresponding network interfaces for forwarding of a message.

15. The monitoring system of claim 12, wherein the processor is further configured to determine whether the test message is routed through the entirety of the test path.

16. The monitoring system of claim 12, wherein the data structure comprises a model of a topology of an autonomous system within the network.

17. The monitoring system of claim 12, wherein the data structure comprises a link state database.

18. The monitoring system of claim 12, wherein:

the plurality of segment identifiers comprises an adjacency segment identifier; and

the adjacency segment identifier is related by the data structure to a link between two adjacent nodes of the network.

19. The monitoring system of claim 18, wherein:

the plurality of segment identifiers comprises first and second adjacency segment identifiers related by the data structure to the same primary link between two adjacent nodes of the network;

the first adjacency segment identifier is associated with an instruction to protect the primary link with a backup link in the event of a failure of the primary link; and

the second adjacency segment identifier is associated with an instruction not to protect the primary link with a backup link in the event of a failure of the primary link.

20. The monitoring system of claim 12, wherein:

the plurality of segment identifiers comprises a nodal segment identifier;

the nodal segment identifier is related by the data structure to a specific node of the network; and

the nodal segment identifier represents a path through the network to the specific node.

21. The monitoring system of claim 18, wherein:

the plurality of segment identifiers further comprises a nodal segment identifier;

the nodal segment identifier is related by the data structure to a specific node of the network; and

the nodal segment identifier represents a path through the network to the specific node.