Patent Description:
<CIT> discloses techniques for detecting data plane failures in Multi-Protocol Label Switching Label-Switched Paths that may be tunneled over one or more other Label-Switched Paths.

<CIT> describes a mechanism for Autonomous System Border Routers to identify the originating node, or router, in an LSP conversant autonomous system, such as an MPLS VPN environment, where the mechanism maintains the identity of the originating node and successive nodes in subsequent autonomous systems along the path to the node to be pinged.

In certain network deployments, network nodes under a single ownership or under a single administration are spread across different Autonomous Systems (ASes) to facilitate ease of management. Multiple AS network design may also result from network mergers and acquisitions. In such scenarios, connectivity across the different ASes can be established using Segment Routing. (Recall, e.g., RFC <NUM>. ) Segment Routing also provides an easy and efficient way to provide interconnectivity in a large scale network as described in the Request for Comments (RFC) draft <NPL>).

<FIG> illustrates an example inter-AS segment routing (SR) network <NUM>. In <FIG>, "PE" denotes a provider edge router, "P" denotes a provider router, and "ASBR" denotes an AS border router. AS1 and AS2 are SR-enabled with node-segment identifiers (Node-SIDS) and adjacency segment identifiers (Adj-SIDS) advertised using an interior gateway protocol (IGP) such as open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS). In the example network <NUM>, the ASBRs advertise border gateway protocol (BGP) egress-peer-engineering segment identifiers (EPE SIDs) for the inter-AS links. The topology of AS1 and of AS2 are advertised, via BGP-LS, to a path monitoring system (PMS) controller. The EPE-SIDs are also advertised via BGP-LS, as described in the RFC draft, "<NPL>).

The PMS controller acquires the complete (of the network topology of both ASes and their interconnections) database information and uses it to build end-to-end (e-<NUM>-e) traffic-engineered (TE) paths. The TE paths are downloaded from the PMS controller to ingress PE1, for example via netconf/bgp-sr-te or the "Path Computation Element (PCE) Protocol (PCEP)," Request for Comments <NUM>, <NUM>, <NUM> and <NUM> (Internet Engineering Task Force). The head-end node PE1 may also (or instead) acquire the complete database using BGP-LS.

The following notation is used for various types of SIDs. Node-SIDs are denoted with an "N-" prefix and the node (e.g., N-PE1, N-P1, N-P2, N-ASBR1, N-ASBR2, etc.). Adjacency SIDs (Adj-SIDs) are denoted with an "Adj-" prefix and include both nodes of the adjacency (e.g., Adj-PE1-P1, Adj-P1-P2, etc.). Egress-per-engineering SIDs (EPE-SIDs) are denoted with an "EPE-" prefix and include both border routers (e.g., EPE-ASBR1-ASBR2, EPE-ASBR4-ASBR3, etc.). Finally, binding-SIDs are denoted with a "BSID{number}" prefix and include both nodes of the binding (e.g., BSID1-ASBR3-PE4 , BSID2-ASBR3-ASBR4, etc.). Although not shown in <FIG>, other types of SIDs, such as those described in RFC <NUM> (e.g., prefix SIDs, anycast SIDs, BGP segments, etc.) can be used.

In the example network <NUM> of <FIG>, e-<NUM>-e traffic engineered paths are built using Node-SIDs and Adj-SIDs. The paths within an AS may be represented using Binding-SIDs. Binding-SIDs are typically used to represent paths within an AS which will not change even if the actual path inside the AS changes due to changes in network topology. In this way, Binding-SIDs hide topology changes in one AS from another AS.

Consider a TE path built from PE1 to PE4 with label stack as below. N-P1,N-ASBR1,EPE-ASBR1-ASBR4, N-PE4. It would be desirable for MPLS ping (See, e.g., Request for Comments <NUM>, "<NPL>) (referred to as "RFC <NUM>") to be able to verify end-to-end connectivity. It would also be desirable for traceroute to validate a TE path (i.e., packet is following the path specified by controller/PCEP) and verify that the control plane and data plane are in sync.

However, in SR networks, e-<NUM>-e paths can be easily built across different ASes using Node-SIDs, adj-SIDs, EPE-SIDs, etc. Unfortunately, it is not possible to run MPLS ping and traceroute functionality on such paths to verify basic connectivity and fault isolation, respectively. This is because with existing MPLS ping and traceroute mechanisms, a reply to the MPLS echo request comes via the Internet protocol (IP), but there is no IP-connectivity for the return path from the remote-end to the source of the ping packet over the different segments (across different ASes) of the SR network. (Note that MPLS "ping" may be used interchangeably in this description with MPLS "echo request" and "echo response.

In view of the foregoing, it would be useful to provide an efficient and easy mechanism which can support Inter-AS MPLS ping and traceroute.

The RFC draft "<NPL>) describes a solution based on advertising a new inter-AS type length value (TLV) containing stack of IP addresses (rather than MPLS labels). However, MPLS ping expects a return IP path from the ping destination to the source. This mechanism can require the return ping packet to reach the control plane and get software forwarded.

Request for Comments <NUM>, "<NPL>)(referred to as "RFC <NUM>") defines continuity check and connectivity verification using path monitoring systems (PMSes) that reside outside the routing domain.

This application describes mechanisms for testing inter-AS networks which are efficient and simple and can be easily deployed in SR networks.

Echo or traceroute functionality is supported in a path spanning multiple autonomous systems (ASes) having segment routing (SR) enabled, the path including an ingress node and an egress node, by: (a) obtaining a return label stack to reach the ingress node from either (A) the egress node, or (B) a transit node in the path; (b) obtaining a label stack to reach, from the ingress node, either (A) the egress node, or (B) the transit node; (c) generating a request message including the return label stack; and (d) sending the request message towards either (A) the egress node, or (B) the transit node using the label stack. The example method may further include: (e) receiving, by either (A) the egress node, or (B) the transit node, the request message, wherein the request message includes information for performing a validity check; (f) performing a validity check using the information included in the request message to generate validity information; (g) generating a reply message including the validity information and information from the return label stack; and (h) sending the reply message towards the ingress node using information from the return label stack included in the request message.

In at least some such example methods, the information for performing a validity check is a forwarding equivalency class (FEC) of the egress node.

In at least some such example methods, the ingress node is in a first one of the multiple ASes and the egress node is in a second one of the multiple ASes.

In at least some such example methods, the request message is an echo request packet, the return label stack is for reaching the ingress node from the egress node, and the echo request packet is sent towards the egress node using the label stack. The return label stack may be encoded in a return label stack type-length-value (TLV) ping or traceroute data structure, and the TLV data structure may include a field defining a number of elements in the return label stack. The return label stack may include at least two type of labels selected from a group of label types consisting of (A) an Interior Gateway Protocol (IGP) segment identifier, (B) an IGP node segment identifier, (C) an IGP adjacency segment identifier, (D) a border gateway protocol (BGP) segment identifier, and (E) a binding segment identifier.

In at least some such example methods, the request message is an traceroute request packet, and the traceroute request packet includes a time to live (TTL) value which is set such that the traceroute request packet reaches either (A) a transit node of the path, or (B) the egress node. The return label stack may be encoded in a return label stack type-length-value (TLV) data structure. The TLV data structure may include a field defining a number of elements in the return label stack. The return label stack may include at least two type of labels selected from a group of label types consisting of (A) an Interior Gateway Protocol (IGP) segment identifier, (B) an IGP node segment identifier, (C) an IGP adjacency segment identifier, (D) a border gateway protocol (BGP) segment identifier, and (E) a binding segment identifier.

According to one option encompassed by the invention, the return label stack is obtained by the ingress node from a path monitoring system (PMS) controller outside the path.

Example embodiments consistent with the present description enable MPLs ping and traceroute procedures from a PMS controller and/or from head-end (also referred to as "ingress") nodes across inter-AS networks. MPLS ping expects a return IP path from the ping destination to the source. It is very difficult and cumbersome to build static-routes or generic routing encapsulation (GRE) tunnels to every end-point from the PMS controller. SR networks statically assign the labels to nodes and the PMS controller and/or head-end knows entire database. The return path can be built from the PMS controller by stacking labels for the return path.

A new type length value (TLV) data structure "Return Label Stack TLV" is defined. Each TLV contains a list of labels which may be a prefix SID, adjacency SID, binding SID. etc. An MPLS echo request should contain this TLV which defines reverse path to reach source from the destination.

The present description may involve novel methods, apparatus, message formats, and/or data structures for supporting Inter-AS MPLS ping and traceroute. The following description is presented to enable one skilled in the art to make and use aspects of the present disclosure, and is provided in the context of particular applications and their requirements. Thus, the following description of embodiments consistent with the present disclosure provides illustration and description, but is not intended to be exhaustive or to limit the scope of protection to the precise form disclosed. Various modifications to the disclosed embodiments will be apparent to those skilled in the art, and the general principles set forth below may be applied to other embodiments and applications. For example, although a series of acts may be described with reference to a flow diagram, the order of acts may differ in other implementations when the performance of one act is not dependent on the completion of another act. Further, non-dependent acts may be performed in parallel. No element, act or instruction used in the description should be construed as critical or essential to aspects of the present disclosure unless explicitly described as such. Also, as used herein, the article "a" is intended to include one or more items. Where only one item is intended, the term "one" or similar language is used. Thus, the scope of protection is not intended to be limited to the embodiments shown and is instead defined in the appended claims.

<FIG> is a flow diagram of an example method <NUM> for performing an MPLS ping in an inter-AS segment routing (SR) network in a manner consistent with the present description. As shown, different branches of the example method <NUM> are performed in response to the occurrence of different events. (Event branch point <NUM>).

Referring first to the left-most branch of <FIG>, responsive to a trigger to generate an echo request (to test a path from the ingress node to an egress node of the path), the ingress node obtains a label stack to reach the ingress node (itself) from the egress node of the path (referred to as the "return label stack") and a forwarding equivalence class (FEC) corresponding to packets to be forwarded on the path. (Block <NUM>) (Note that the FEC can be used to define the LSP. In the case of SR-LSPs, every label in the label-stack has separate FEC TLV. (See, e.g., "<NPL>)(Referred to as "RFC <NUM>"). The method <NUM> generates an echo request (also referred to as a "ping") message (e.g., a packet) including (<NUM>) information (e.g., as a TLV) defining the obtained return label stack and (<NUM>) the FEC (or more specifically, the top label associated with the FEC). (Block <NUM>) The example method <NUM> then sends the echo request message towards the egress node of the path (Block <NUM>) before the example method returns. (Node <NUM>).

Referring next to the right-most branch of <FIG>, responsive to receiving the echo request (e.g., at the egress node of the path), the FEC included in the echo request message is checked for validity. (Block <NUM>) If the FEC is not valid (Decision <NUM>, NO), the example method <NUM> stores invalidity information (e.g., sets a flag to invalid). (Block <NUM>) If, on the other hand, the FEC is valid (Decision <NUM>, YES), the example method <NUM> stores validity information (e.g., sets a flag to valid). (Block <NUM>) The example method <NUM> then generates an echo response message (e.g., packet) using (<NUM>) information in the return label stack that was included in the echo request message and (<NUM>) the stored validity/invalidity information. (Block <NUM>) The echo reply message is then sent towards the ingress (e.g., using the top label in the return label stack) (Block <NUM>) before the example method <NUM> returns. (Node <NUM>) Although not shown, if the echo request message is received by a transit node of the path (i.e., a node other than the egress node of the path), it is simply forwarded towards the egress node.

Referring now to the middle branch of <FIG>, in the event that an echo reply is received by the ingress node of the path being tested, the validity/invalidity information in the echo reply is checked and further processing is performed accordingly. (Block <NUM>) Note that the echo reply packet will be an MPLS packet with label stack. On non-ingress (e.g., "transit") routers, this echo reply MPLS packet is simply processed like any normal MPLS packet. Consequently, since the echo-reply header will be below (that is, encapsulated by) the MPLS header, it will not be examined by the "transit" routers on return path. This advantageously avoids unnecessary processing by the transit routers on the return path.

<FIG> is a flow diagram of an example method <NUM> for performing an MPLS traceroute in an inter-AS segment routing network in a manner consistent with the present description. As shown, different branches of the example method <NUM> are performed in response to the occurrence of different events. (Event branch point <NUM>).

Referring first to the left-most branch of <FIG>, responsive to a trigger to generate an traceroute message (to test a path from the ingress node to an egress node of the path, including each label hop of the path), the ingress node obtains a label stack to reach the ingress node (itself) from the nth node of the path (referred to as the "return label stack") and a forwarding equivalence class (FEC) corresponding to the label (in case of traceroute, as opposed to the FEC corresponding to the egress router in case of MPLS ping). (Block <NUM>) The method <NUM> generates a traceroute message (e.g., a packet) including (<NUM>) information (e.g., as a TLV) defining the obtained return label stack and (<NUM>) the FEC, where the traceroute message has a time to live (TTL) set to n. (Block <NUM>) The example method <NUM> then sends the traceroute message towards the egress node (or towards the nth node) of the path (Block <NUM>) before the example method <NUM> returns. (Node <NUM>).

Referring next to the right-most branch of <FIG>, responsive to receiving the traceroute message (e.g., at the egress node or nth node of the path, when the TTL of the traceroute packet is zero), the FEC included in the traceroute message is checked for validity. (Block <NUM>) If the FEC is not valid (Decision <NUM>, NO), the example method <NUM> stores invalidity information (e.g., sets a flag to invalid). (Block <NUM>) If, on the other hand, the FEC is valid (Decision <NUM>, YES), the example method <NUM> stores validity information (e.g., sets a flag to valid). (Block <NUM>) The example method <NUM> then generates an echo traceroute response message (e.g., packet) using (<NUM>) information in the return label stack that was included in the traceroute message and (<NUM>) the stored validity/invalidity information. (Block <NUM>) The traceroute response message is then sent towards the ingress (e.g., using the top label in the return label stack) (Block <NUM>) before the example method <NUM> returns. (Node <NUM>) Although not shown, if the echo request message is received by a transit node of the (partial) path (i.e., a node other than the egress node (or other than the nth node of the path), in which case, the TTL will not yet be zero), it is simply forwarded towards the egress node.

Referring now to the middle branch of <FIG>, in the event that traceroute response message is received by the ingress node of the path being tested, the validity/invalidity information in the echo reply is checked and further processing is performed accordingly. (Block <NUM>) For example, if the entire path being tested has not been completely tested (i.e., if the egress node is beyond the nth node), n is incremented and the TTL for the next traceroute request message is set to the new value for n.

Referring back to block <NUM> and <NUM>, according to one option encompassed by the invention the "return label stack" is computed (at least in part) by the ingress node of the path being tested. However, the ingress node might not have knowledge of the network topology beyond the AS to which it belongs. Referring back to <FIG>, a PMS controller may provide such necessary information. For example, the PMS controller may determine the entire return label stack. Alternatively, the controller may determine a part of the return label stack (with the ingress node determining a part of the label stack to be used within its AS).

Referring back to blocks <NUM> and <NUM>, the echo request message and traceroute message may include a label stack to reach the egress node of the path (or to reach the nth node of the partial path). That is, the label stack is used to forward the echo request message or traceroute message down the path being tested. The packet will be sent to the router's control plane on every hop when the packet's TTL expires. The TTL is incremented by one every-time to make sure next node on the path is visited. The return label stack may be included within the echo request message or traceroute message as a new TLV, such as the example TLV(s) described in § <NUM> below.

As just noted above, the return label stack may be included within the echo request message or traceroute message as a new TLV "Return Label Stack TLV. " Each TLV contains a list of labels which may be a prefix-SID, adjacency-SID, binding-SID, etc. An example MPLS echo request message or MPLS traceroute message consistent with the present description should contain this TLV, which defines reverse path to reach source from the destination. <FIG> illustrate example data structures which may be used for carrying MPLS ping and/or traceroute information in a manner consistent with the present description.

<FIG> illustrates details of an example TLV <NUM> (also referred to as a IPv4 or IPv6 Label stack TLV). The type field <NUM> may be <NUM> bits and may be defined (or assigned by the Internet Assigned Numbers Authority (IANA)). The <NUM>-bit length field <NUM> includes a value specifying the length of the TLV including a TLV header. The <NUM>-bit number of elements in set field <NUM> includes a value indicating how may labels (for the return label stack) are included. That is, the return label stack may include a set of one or more IPv4 or IPv6 addresses and/or labels, and the number of elements in set field <NUM> specifies how many.

Referring to both <FIG>, the flags field <NUM> may include a one-bit flag (F) which is set to <NUM> for IPv4 and set to <NUM> for IPv6.

Referring back to <FIG>, the IPv4/IPv6 Address field <NUM> defines the node to be traversed, while the label value defines the label to reach to the address in SR network. The value in the IPv4/IPv6 Address field <NUM> may be NULL. The <NUM>-bit label field <NUM> includes information that may be used to build the return (i.e., echo reply or traceroute reply) packet. The first label in the label stack represents the top-most label that should be encoded in the return packet.

<FIG> illustrates an IPv6 return SRH TLV consistent with the present description. For IPv6-only networks with SRv6 data plane deployments, the return path may be encoded using IPv6 addresses which should be used to build the return packet SRH header.

<FIG> illustrates two data forwarding systems <NUM> and <NUM> coupled via communications links <NUM>. The links may be physical links or "wireless" links. The data forwarding systems <NUM>,<NUM> may be nodes, such as routers for example. If the data forwarding systems <NUM>,<NUM> are example routers, each may include a control component (e.g., a routing engine) <NUM>,<NUM> and a forwarding component <NUM>,<NUM>. Each data forwarding system <NUM>,<NUM> includes one or more interfaces <NUM>,<NUM> that terminate one or more communications links <NUM>. The example method <NUM> and/or <NUM> described above may be implemented in the control component <NUM>/<NUM> of devices <NUM>/<NUM>.

As just discussed above, and referring to <FIG>, some example routers <NUM> include a control component (e.g., routing engine) <NUM> and a packet forwarding component (e.g., a packet forwarding engine) <NUM>.

The control component <NUM> may include an operating system (OS) kernel <NUM>, routing protocol process(es) <NUM>, label-based forwarding protocol process(es) <NUM>, interface process(es) <NUM>, configuration API(s) <NUM>, a user interface (e.g., command line interface) process(es) <NUM>, programmatic API(s), <NUM>, and chassis process(es) <NUM>, and may store routing table(s) <NUM>, label forwarding information <NUM>, configuration information in a configuration database(s) <NUM> and forwarding (e.g., route-based and/or label-based) table(s) <NUM>. As shown, the routing protocol process(es) <NUM> may support routing protocols such as the routing information protocol ("RIP") <NUM>, the intermediate system-to-intermediate system protocol ("ISIS") <NUM>, the open shortest path first protocol ("OSPF") <NUM>, the enhanced interior gateway routing protocol ("EIGRP") <NUM> and the border gateway protocol ("BGP") <NUM>, and the label-based forwarding protocol process(es) <NUM> may support protocols such as BGP <NUM>, the label distribution protocol ("LDP") <NUM> and the resource reservation protocol ("RSVP") <NUM>. One or more components (not shown) may permit a user to interact, directly or indirectly (via an external device), with the router configuration database(s) <NUM> and control behavior of router protocol process(es) <NUM>, the label-based forwarding protocol process(es) <NUM>, the interface process(es) <NUM>, and the chassis process(es) <NUM>. For example, the configuration database(s) <NUM> may be accessed via SNMP <NUM>, configuration API(s) (e.g. the Network Configuration Protocol (NetConf), the Yet Another Next Generation (e) protocol, etc.) <NUM>, a user command line interface (CLI) <NUM>, and/or programmatic API(s) <NUM>. Control component processes may send information to an outside device via SNMP <NUM>, syslog, streaming telemetry (e.g., Google's network management protocol (gNMI), the IP Flow Information Export (IPFIX) protocol, etc.)), etc. Similarly, one or more components (not shown) may permit an outside device to interact with one or more of the router protocol process(es) <NUM>, the label-based forwarding protocol process(es) <NUM>, the interface process(es) <NUM>, configuration database(s) <NUM>, and the chassis process(es) <NUM>, via programmatic API(s) (e.g. gRPC) <NUM>. Such processes may send information to an outside device via streaming telemetry.

The packet forwarding component <NUM> may include a microkernel <NUM>, interface process(es) <NUM>, distributed ASICs <NUM>, chassis process(es) <NUM> and forwarding (e.g., route-based and/or label-based) table(s) <NUM>.

In the example router <NUM> of <FIG>, the control component <NUM> handles tasks such as performing routing protocols, performing label-based forwarding protocols, control packet processing, etc., which frees the packet forwarding component <NUM> to forward received packets quickly. That is, received control packets (e.g., routing protocol packets and/or label-based forwarding protocol packets) are not fully processed on the packet forwarding component <NUM> itself, but are passed to the control component <NUM>, thereby reducing the amount of work that the packet forwarding component <NUM> has to do and freeing it to process packets to be forwarded efficiently. Thus, the control component <NUM> is primarily responsible for running routing protocols and/or label-based forwarding protocols, maintaining the routing tables and/or label forwarding information, sending forwarding table updates to the packet forwarding component <NUM>, and performing system management. The example control component <NUM> may handle routing protocol packets, provide a management interface, provide configuration management, perform accounting, and provide alarms. The processes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM> may be modular, and may interact (directly or indirectly) with the OS kernel <NUM>. That is, nearly all of the processes communicate directly with the OS kernel <NUM>. Using modular software that cleanly separates processes from each other isolates problems of a given process so that such problems do not impact other processes that may be running. Additionally, using modular software facilitates easier scaling.

Still referring to <FIG>, although shown separately, the example OS kernel <NUM> may incorporate an application programming interface ("API") system for external program calls and scripting capabilities. The control component <NUM> may be based on an Intel PCI platform running the OS from flash memory, with an alternate copy stored on the router's hard disk. The OS kernel <NUM> is layered on the Intel PCI platform and establishes communication between the Intel PCI platform and processes of the control component <NUM>. The OS kernel <NUM> also ensures that the forwarding tables <NUM> in use by the packet forwarding component <NUM> are in sync with those <NUM> in the control component <NUM>. Thus, in addition to providing the underlying infrastructure to control component <NUM> software processes, the OS kernel <NUM> also provides a link between the control component <NUM> and the packet forwarding component <NUM>.

Referring to the routing protocol process(es) <NUM> of <FIG>, this process(es) <NUM> provides routing and routing control functions within the platform. In this example, the RIP <NUM>, ISIS <NUM>, OSPF <NUM> and EIGRP <NUM> (and BGP <NUM>) protocols are provided. Naturally, other routing protocols may be provided in addition, or alternatively. Similarly, the label-based forwarding protocol process(es) <NUM> provides label forwarding and label control functions. In this example, the LDP <NUM> and RSVP <NUM> (and BGP <NUM>) protocols are provided. Naturally, other label-based forwarding protocols (e.g., MPLS) may be provided in addition, or alternatively. In the example router <NUM>, the routing table(s) <NUM> is produced by the routing protocol process(es) <NUM>, while the label forwarding information <NUM> is produced by the label-based forwarding protocol process(es) <NUM>.

Still referring to <FIG>, the interface process(es) <NUM> performs configuration of the physical interfaces (Recall, e.g., <NUM> and <NUM> of <FIG>. ) and encapsulation.

The example control component <NUM> may provide several ways to manage the router. For example, it <NUM> may provide a user interface process(es) <NUM> which allows a system operator to interact with the system through configuration, modifications, and monitoring. The SNMP <NUM> allows SNMP-capable systems to communicate with the router platform. This also allows the platform to provide necessary SNMP information to external agents. For example, the SNMP <NUM> may permit management of the system from a network management station running software, such as Hewlett-Packard's Network Node Manager ("HP-NNM"), through a framework, such as Hewlett-Packard's OpenView. Further, as already noted above, the configuration database(s) <NUM> may be accessed via SNMP <NUM>, configuration API(s) (e.g. NetConf, YANG, etc.) <NUM>, a user CLI <NUM>, and/or programmatic API(s) <NUM>. Control component processes may send information to an outside device via SNMP <NUM>, syslog, streaming telemetry (e.g., gNMI, IPFIX, etc.), etc. Similarly, one or more components (not shown) may permit an outside device to interact with one or more of the router protocol process(es) <NUM>, the label-based forwarding protocol process(es) <NUM>, the interface process(es) <NUM>, and the chassis process(es) <NUM>, via programmatic API(s) (e.g., gRPC) <NUM>. Such processes may send information to an outside device via streaming telemetry. Accounting of packets (generally referred to as traffic statistics) may be performed by the control component <NUM>, thereby avoiding slowing traffic forwarding by the packet forwarding component <NUM>.

Although not shown, the example router <NUM> may provide for out-of-band management, RS-<NUM> DB9 ports for serial console and remote management access, and tertiary storage using a removable PC card. Further, although not shown, a craft interface positioned on the front of the chassis provides an external view into the internal workings of the router. It can be used as a troubleshooting tool, a monitoring tool, or both. The craft interface may include LED indicators, alarm indicators, control component ports, and/or a display screen. Finally, the craft interface may provide interaction with a command line interface ("CLI") <NUM> via a console port, an auxiliary port, and/or a management Ethernet port.

The packet forwarding component <NUM> is responsible for properly outputting received packets as quickly as possible. If there is no entry in the forwarding table for a given destination or a given label and the packet forwarding component <NUM> cannot perform forwarding by itself, it <NUM> may send the packets bound for that unknown destination off to the control component <NUM> for processing. The example packet forwarding component <NUM> is designed to perform Layer <NUM> and Layer <NUM> switching, route lookups, and rapid packet forwarding.

As shown in <FIG>, the example packet forwarding component <NUM> has an embedded microkernel <NUM>, interface process(es) <NUM>, distributed ASICs <NUM>, and chassis process(es) <NUM>, and stores a forwarding (e.g., route-based and/or label-based) table(s) <NUM>. The microkernel <NUM> interacts with the interface process(es) <NUM> and the chassis process(es) <NUM> to monitor and control these functions. The interface process(es) <NUM> has direct communication with the OS kernel <NUM> of the control component <NUM>. This communication includes forwarding exception packets and control packets to the control component <NUM>, receiving packets to be forwarded, receiving forwarding table updates, providing information about the health of the packet forwarding component <NUM> to the control component <NUM>, and permitting configuration of the interfaces from the user interface (e.g., CLI) process(es) <NUM> of the control component <NUM>. The stored forwarding table(s) <NUM> is static until a new one is received from the control component <NUM>. The interface process(es) <NUM> uses the forwarding table(s) <NUM> to look up next-hop information. The interface process(es) <NUM> also has direct communication with the distributed ASICs <NUM>. Finally, the chassis process(es) <NUM> may communicate directly with the microkernel <NUM> and with the distributed ASICs <NUM>.

In the example router <NUM>, the example methods <NUM> and/or <NUM> consistent with the present disclosure may be implemented in an MPLS OAM module which processes echo request and reply.

Referring back to distributed ASICs <NUM> of <FIG>, <FIG> is an example of how the ASICS may be distributed in the packet forwarding component <NUM> to divide the responsibility of packet forwarding. As shown in <FIG>, the ASICs of the packet forwarding component <NUM> may be distributed on physical interface cards ("PICs") <NUM>, flexible PIC concentrators ("FPCs") <NUM>, a midplane or backplane <NUM>, and a system control board(s) <NUM> (for switching and/or forwarding). Switching fabric is also shown as a system switch board ("SSB"), or a switching and forwarding module ("SFM") <NUM>. Each of the PICs <NUM> includes one or more PIC I/O managers <NUM>. Each of the FPCs <NUM> includes one or more I/O managers <NUM>, each with an associated memory <NUM>. The midplane/backplane <NUM> includes buffer managers 935a, 935b. Finally, the system control board <NUM> includes an internet processor <NUM> and an instance of the forwarding table <NUM> (Recall, e.g., <NUM> of <FIG>).

Still referring to <FIG>, the PICs <NUM> contain the interface ports. Each PIC <NUM> may be plugged into an FPC <NUM>. Each individual PIC <NUM> may contain an ASIC that handles media-specific functions, such as framing or encapsulation. Some example PICs <NUM> provide SDH/SONET, ATM, Gigabit Ethernet, Fast Ethernet, and/or DS3/E3 interface ports.

An FPC <NUM> can contain from one or more PICs <NUM>, and may carry the signals from the PICs <NUM> to the midplane/backplane <NUM> as shown in <FIG>.

The midplane/backplane <NUM> holds the line cards. The line cards may connect into the midplane/backplane <NUM> when inserted into the example router's chassis from the front. The control component (e.g., routing engine) <NUM> may plug into the rear of the midplane/backplane <NUM> from the rear of the chassis. The midplane/backplane <NUM> may carry electrical (or optical) signals and power to each line card and to the control component <NUM>.

The system control board <NUM> may perform forwarding lookup. It <NUM> may also communicate errors to the routing engine. Further, it <NUM> may also monitor the condition of the router based on information it receives from sensors. If an abnormal condition is detected, the system control board <NUM> may immediately notify the control component <NUM>.

Referring to <FIG>, <FIG>, in some example routers, each of the PICs <NUM>,<NUM>' contains at least one I/O manager ASIC <NUM> responsible for media-specific tasks, such as encapsulation. The packets pass through these I/O ASICs on their way into and out of the router. The I/O manager ASIC <NUM> on the PIC <NUM>,<NUM>' is responsible for managing the connection to the I/O manager ASIC <NUM> on the FPC <NUM>,<NUM>', managing link-layer framing and creating the bit stream, performing cyclical redundancy checks (CRCs), and detecting link-layer errors and generating alarms, when appropriate. The FPC <NUM> includes another I/O manager ASIC <NUM>. This ASIC <NUM> takes the packets from the PICs <NUM> and breaks them into (e.g., <NUM>-byte) memory blocks. This FPC I/O manager ASIC <NUM> sends the blocks to a first distributed buffer manager (DBM) 935a', decoding encapsulation and protocol-specific information, counting packets and bytes for each logical circuit, verifying packet integrity, and applying class of service (CoS) rules to packets. At this point, the packet is first written to memory. More specifically, the example DBM ASIC 935a' manages and writes packets to the shared memory <NUM> across all FPCs <NUM>. In parallel, the first DBM ASIC 935a' also extracts information on the destination of the packet and passes this forwarding-related information to the Internet processor <NUM>/<NUM>'. The Internet processor <NUM>/<NUM>' performs the route lookup using the forwarding table <NUM> and sends the information over to a second DBM ASIC 935b'. The Internet processor ASIC <NUM>/<NUM>' also collects exception packets (i.e., those without a forwarding table entry) and sends them to the control component <NUM>. The second DBM ASIC 935b' then takes this information and the <NUM>-byte blocks and forwards them to the I/O manager ASIC <NUM> of the egress FPC <NUM>/<NUM>' (or multiple egress FPCs, in the case of multicast) for reassembly. (Thus, the DBM ASICs 935a' and 935b' are responsible for managing the packet memory <NUM> distributed across all FPCs <NUM>/<NUM>', extracting forwarding-related information from packets, and instructing the FPC where to forward packets.

The I/O manager ASIC <NUM> on the egress FPC <NUM>/<NUM>' may perform some value-added services. In addition to incrementing time to live ("TTL") values and re-encapsulating the packet for handling by the PIC <NUM>, it can also apply class-of-service (CoS) rules. To do this, it may queue a pointer to the packet in one of the available queues, each having a share of link bandwidth, before applying the rules to the packet. Queuing can be based on various rules. Thus, the I/O manager ASIC <NUM> on the egress FPC <NUM>/<NUM>' may be responsible for receiving the blocks from the second DBM ASIC 935b', incrementing TTL values, queuing a pointer to the packet, if necessary, before applying CoS rules, re-encapsulating the blocks, and sending the encapsulated packets to the PIC I/O manager ASIC <NUM>.

<FIG> is a flow diagram of an example method <NUM> for providing packet forwarding in the example router. The main acts of the method <NUM> are triggered when a packet is received on an ingress (incoming) port or interface. (Event <NUM>) The types of checksum and frame checks that are required by the type of medium it serves are performed and the packet is output, as a serial bit stream. (Block <NUM>) The packet is then decapsulated and parsed into (e.g., <NUM>-byte) blocks. (Block <NUM>) The packets are written to buffer memory and the forwarding information is passed on the Internet processor. (Block <NUM>) The passed forwarding information is then used to lookup a route in the forwarding table. (Block <NUM>) (Recall, e.g., Figures 7A-7D. ) Note that the forwarding table can typically handle unicast packets that do not have options (e.g., accounting) set, and multicast packets for which it already has a cached entry. Thus, if it is determined that these conditions are met (YES branch of Decision <NUM>), the packet forwarding component finds the next hop and egress interface, and the packet is forwarded (or queued for forwarding) to the next hop via the egress interface (Block <NUM>) before the method <NUM> is left (Node <NUM>) Otherwise, if these conditions are not met (NO branch of Decision <NUM>), the forwarding information is sent to the control component <NUM> for advanced forwarding resolution (Block <NUM>) before the method <NUM> is left (Node <NUM>).

Referring back to block <NUM>, the packet may be queued. Actually, as stated earlier with reference to <FIG>, a pointer to the packet may be queued. The packet itself may remain in the shared memory. Thus, all queuing decisions and CoS rules may be applied in the absence of the actual packet. When the pointer for the packet reaches the front of the line, the I/O manager ASIC <NUM> may send a request for the packet to the second DBM ASIC 935b. The DBM ASIC <NUM> reads the blocks from shared memory and sends them to the I/O manager ASIC <NUM> on the FPC <NUM>, which then serializes the bits and sends them to the media-specific ASIC of the egress interface. The I/O manager ASIC <NUM> on the egress PIC <NUM> may apply the physical-layer framing, perform the CRC, and send the bit stream out over the link.

Referring back to block <NUM> of <FIG>, as well as <FIG>, regarding the transfer of control and exception packets, the system control board <NUM> handles nearly all exception packets. For example, the system control board <NUM> may pass exception packets to the control component <NUM>.

Although example embodiments consistent with the present disclosure may be implemented on the example routers of <FIG> or <FIG>, embodiments consistent with the present disclosure may be implemented on communications network nodes (e.g., routers, switches, etc.) having different architectures. More generally, embodiments consistent with the present disclosure may be implemented on an example system <NUM> as illustrated on <FIG>.

<FIG> is a block diagram of an example machine <NUM> that may perform one or more of the methods described, and/or store information used and/or generated by such methods. The example machine <NUM> includes one or more processors <NUM>, one or more input/output interface units <NUM>, one or more storage devices <NUM>, and one or more system buses and/or networks <NUM> for facilitating the communication of information among the coupled elements. One or more input devices <NUM> and one or more output devices <NUM> may be coupled with the one or more input/output interfaces <NUM>. The one or more processors <NUM> may execute machine-executable instructions (e.g., C or C++ running on the Linux operating system widely available from a number of vendors) to effect one or more aspects of the present disclosure. At least a portion of the machine executable instructions may be stored (temporarily or more permanently) on the one or more storage devices <NUM> and/or may be received from an external source via one or more input interface units <NUM>. The machine executable instructions may be stored as various software modules, each module performing one or more operations. Functional software modules are examples of components which may be used in the apparatus described.

In some embodiments consistent with the present disclosure, the processors <NUM> may be one or more microprocessors and/or ASICs. The bus <NUM> may include a system bus. The storage devices <NUM> may include system memory, such as read only memory (ROM) and/or random access memory (RAM). The storage devices <NUM> may also include a hard disk drive for reading from and writing to a hard disk, a magnetic disk drive for reading from or writing to a (e.g., removable) magnetic disk, an optical disk drive for reading from or writing to a removable (magneto-) optical disk such as a compact disk or other (magneto-) optical media, or solid-state non-volatile storage.

Some example embodiments consistent with the present disclosure may also be provided as a machine-readable medium comprising the machine-executable instructions. The machine-readable medium may be non-transitory and may include, but is not limited to, flash memory, optical disks, CD-ROMs, DVD ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards or any other type of machine-readable media suitable for storing electronic instructions. For example, example embodiments consistent with the present disclosure may be downloaded as a computer program which may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of a communication link (e.g., a modem or network connection) and stored on a non-transitory storage medium. The machine-readable medium may also be referred to as a processor-readable medium. In other examples, the machine-readable medium is a transitory medium such as a carrier signal or a transmission medium.

Example embodiments consistent with the present disclosure (or components or modules thereof) might be implemented in hardware, such as one or more field programmable gate arrays ("FPGA"s), one or more integrated circuits such as ASICs, one or more network processors, etc. Alternatively, or in addition, embodiments consistent with the present disclosure (or components or modules thereof) might be implemented as stored program instructions executed by a processor. Such hardware and/or software might be provided in an addressed data (e.g., packet, cell, etc.) forwarding device (e.g., a switch, a router, etc.), a server, a laptop computer, desktop computer, a tablet computer, a mobile phone, or any device (e.g., a controller, and/or label switching router) that has computing and networking capabilities.

<FIG> and <FIG> illustrate operations of an example MPLS ping method, consistent with the present description, in an inter-AS segment routing network. Assume that there is an MPLS label switched path from ingress edge node PE1 in AS1 to egress edge node PE4 in AS2.

Referring first to <FIG>, to construct the MPLS echo request <NUM>, PE1 may need a label stack <NUM> to reach PE4 and the FEC of the PE4 <NUM>. The label stack <NUM> may be programmed by the controller. Alternatively, PE <NUM> may have imported the whole topology information (including the topology of AS2) from BGP LS. RFC <NUM> defines a new FEC for SR networks which can be included to the MPLS echo request <NUM>. However, in a typical deployment scenario, there will no IP connectivity from PE4 to PE1. Therefore, as shown, PE1 includes the return path from PE4 to PE1 in the MPLS echo request <NUM> using multiple "Return label stack" TLV defined above. This is illustrated, in simplified form, as return label stack <NUM>. For example, an MPLS echo request from PE1 to PE4 may include three (<NUM>) labels in the return label stack TLV; namely N-ASBR4, EPE-ASBR4->ASBR1 and N-PE1.

Still referring to <FIG>, as shown by the heavy arrows, the information in the label stack <NUM> is used to send the echo request message <NUM> from PE1 to P1, then from P1 to ASBR1, then from ASBR1 to ASBR4, and finally from ASBR4 to PE4. As is known, a label may be popped off of the top of the stack <NUM> at each hop. (Recall, e.g., <NUM> of <FIG>.

Referring back to block <NUM> of <FIG>, if PE1 has the topology of the whole network (including the topology of AS2), according to one option encompassed by the invention it calculates "return label stack" TLV using a traffic engineering database (TED), or a user may provide such return label stack information in the case of on-demand echo request initiated from PE1. Similarly, when the echo request is initiated from a (e.g., PMS) controller, the
controller may construct the return label stack based on the knowledge of topology and connectivity of the return path.

Referring now to <FIG>, responsive to receiving the MPLS echo request <NUM>, PE4 first validates the FEC <NUM> in the echo request <NUM> (Recall, e.g., <NUM> of <FIG>. ) and prepares a label stack to send an echo reply message <NUM> back to PE1 using information in the "return label stack. " (See <NUM> of <FIG>, <NUM> of <FIG> and recall <NUM> of <FIG>. ) More specifically, PE4 builds the echo reply message <NUM> (e.g., packet) with the label stack <NUM> (e.g., in the packet header) and sends the echo reply back towards PE1. (Recall, e.g., <NUM> of <FIG>. ) As shown by the heavy arrows in <FIG>, the label stack <NUM> in the echo reply (which was generated from the return label stack <NUM> in the echo request <NUM>) is used to forward the echo reply message <NUM> from PE4 to ASBR4, then from ASBR4 to ASBR1, and finally from ASBR1 to PE1. As is known, a label may be popped from the top of the stack at each hop of the return path.

Thus, <FIG> and <FIG> illustrate an example of the utility of the example method <NUM> of <FIG>.

<FIG> illustrate operations of an example MPLS traceroute method, consistent with the present description, in an inter-AS segment routing network. The MPLS traceroute procedures are similar to MPLS echo, but, as is conventional, the time to live (TTL) value in the traceroute request is successively increased so that the traceroute message is sent to and returned from each hop of the label switched path. The ingress (or head end node) constructs the return label stack information and the egress node (or progressive downstream nodes) uses the return label stack to construct a label stack used in the traceroute reply (e.g., packet header).

Assume that it is desired to perform a traceroute on a traffic engineered label switched path built from PE1 to PE4 with the label stack: N-P1, N-ASBR1, EPE-ASBR1-ASBR4 and N-PE4. Referring first to <FIG>, the traceroute message 1410a has a TTL value of <NUM>1420a, and a forwarding label 1430a to reach the first hop of the path, P1. P1 uses the return label stack (in this example, a single label) 1440a to construct a traceroute reply (not shown).

Referring next to <FIG>, the next traceroute message 1410b has a TTL value incremented to <NUM>1420b, a label stack 1430b and a return label stack (in this example, a single label) 1440b. As shown by the heavy arrows pointing to the right, the traceroute message 1410a is forwarded from PE1 to P1, and then from P1 to ASBR1 using the information in the label stack 1430b. As shown by the heavy arrow pointing back to the left, ASBR1 then uses the information the return label stack 1440b to generate a traceroute reply and send it back to PE1.

Referring next to <FIG> the next traceroute message 1410c has a TTL value incremented to <NUM>1420b, a label stack 1430c and a return label stack 1440c. As shown by the heavy arrows pointing to the right, the traceroute message 1410c is forwarded from PE1 to P1, then from P1 to ASBR1, and then from ASBR1 to ASBR4 using the information in the label stack 1430c. As shown by the heavy arrows pointing back to the left, ASBR4 then uses the information the return label stack 1440c to generate a traceroute reply and send it back to PE1 via ASBR1.

Finally, referring to <FIG> the next traceroute message 1410d has a TTL value incremented to <NUM>1420d, a label stack 1430d and a return label stack 1440d. As shown by the heavy arrows pointing to the right, the traceroute message 1410d is forwarded from PE1 to P1, then from P1 to ASBR1, then from ASBR1 to ASBR4 and finally from ASBR4 to PE4 using the information in the label stack 1430d. As shown by the heavy arrows pointing back to the left, ASBR4 then uses the information the return label stack 1440d to generate a traceroute reply and send it back to PE1 (via ASBR4 and ASBR1).

Assume that the controller (PMS) initiates the MPLS traceroute procedures. Assume further that there is no return path available from the nodes inside AS1 and AS2 to the PMS. During the traceroute procedure, PMS builds a return label stack TLV and includes a label to the border-node (ASBR) which has the route to PMS in the return label stack TLV. The nodes internal to the AS1 and AS2 will build the echo-reply packet and prepare MPLS header using the labels in the return label stack.

In all of the foregoing examples, the ingress (head-end) node and/or PMS is aware of the return path from every node visited in the network and builds the return label stack for every visited node accordingly.

The foregoing methods and apparatus provide efficient and easy mechanisms which can support Inter-AS MPLS ping and traceroute.

Claim 1:
A computer-implemented method for supporting echo or traceroute functionality in a path spanning multiple autonomous systems, ASes, having segment routing, SR, enabled, the path including an ingress node and an egress node, the computer-implemented method comprising:
a) obtaining a return label stack to reach the ingress node from either (A) the egress node, or (B) a transit node in the path, wherein obtaining the return label stack comprises:
calculating, by the ingress node and/or a path monitoring system, PMS, controller outside the path, the return label stack, said calculating being based on the network topology of the return path; and
obtaining, by the ingress node from the ingress node itself and/or the path monitoring system, PMS, controller, the calculated return label stack;
b) obtaining a label stack to reach, from the ingress node, either (A) the egress node, or (B) the transit node;
c) generating a request message, including the return label stack, at the ingress node; and
d) sending the request message, including the return label stack, from the ingress node towards either (A) the egress node, or (B) the transit node using the label stack.