Method and system for path monitoring using segment routing

Patent metadata

Field	Value
Publication number	US-9369371-B2
Application number	US-201414292264-A
Country	US
Kind code	B2
Filing date	May 30, 2014
Priority date	Oct 5, 2012
Publication date	Jun 14, 2016
Grant date	Jun 14, 2016

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.

First claim

What is claimed is:

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

Assignees

• Cisco Tech Inc
• Cisco Tech Inc

Inventors

• Filsfils Clarence
• Frost Daniel C
• Bryant Stewart F
• Heidrich Don R

Classifications

• H04L45/22

  Alternate routing · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title

• H04L43/50 Primary

  Testing arrangements · CPC title