A METHOD AND SYSTEM FOR VERIFYING CONNECTIVITY OF MULTI- SEGMENT PSEUDO-WIRES BY TRACING

FIELD OF THE INVENTION

[0001] This invention relates to the field of network management and service provisioning, and more specifically, to a method and System for verifying connectivity for multi-segment pseudo-wires in packet switched networks.

BACKGROUND OF THE INVENTION

[0002] Multiprotocol label switching ("MPLS") provides a mechanism for engineering network traffic patterns in which short labels are assigned to network packets that describe how to forward them through a network (e.g., a packet switched network ("PSN")). In a MPLS network, a node, switch or router which supports MPLS is generally known as a label switching router ("LSR") and a LSR at the edge (ingress or egress) of the MPLS network is generally known as a label edge router ("LER").

[0003] In gênerai, as a data frame of a connectionless network layer protocol (e.g., the Internet Protocol ("IP")) travels from a source node to a destination node it travels from one node to the next through the network. Each node makes an independent forwarding décision for that packet. That is, each node analyzes the data frame's header to détermine where to forward the packet next. The forwarding décision is determined by a forwarding table that is présent on each node and that is built by network layer routing algorithme running on that node. Therefore each router independently chooses a next hop for the data frame, based on its analysis of the packet's header and the results of running the routing algorithm.

[0004] Frame headers contain considerably more information than is needed simply to choose the next hop along the path. Choosing the next hop can therefore be thought of as the combination of two fonctions. The fîrst function partitions the entire set of possible packets into a set of forwarding équivalence classes ("FECs"). In conventional IP forwarding, the FEC is a subnet IP address prefix. Therefore, a particular node will typically consider two packets to be in the same FEC if there is some address prefix "X" in that router's routing tables such that "X" is the "longest match" for each

packet's destination address. The second fonction maps each FEC to a next hop. Insofar as the forwarding décision is concerned, différent packets which get mapped into the same FEC are indistinguishable. AIl data frames which belong to a parti cular FEC and which travel from a parti cular node will follow the same path (or if certain kinds of multi-path routing are in use, they will ail follow one of a set of paths associated with the FEC). As the data frame traverses the network, each hop in turn re-examines the packet and matches it to a FEC in order to détermine the next hop.

[0005] In MPLS, the assignment of a particular data frame to a particular FEC is done just once, as the data frame enters the network. The FEC to which the packet is assigned is encoded as a short fixed length value known as a "label". When a packet is forwarded to its next hop, the label is sent along with it; that is, the packets are "labelled" before they are forwarded. At subséquent hops, there is no further analysis of the data frame's network layer header. Rather, the label in the frame header is used as an index into a table on the node. The table entry spécifies the next hop and a new label. The old label in the frame header is replaced with the new label and the data frame is forwarded to its next hop. Thus, in the MPLS forwarding paradigm, once a packet is assigned to a FEC, no further network layer header analysis is done by subséquent routers; ail forwarding is driven by the labels.

[0006] For référence, the MPLS header is made up of a stack of 32 bit labels. The MPLS "label" is 20 bits long and is the identifier that is locally significant to the LSR. The "expérimental bits" field is 3 bits long and is usedto détermine the quality of service ("QoS") that is to be appliedto the data frame. The "stack" field takes one bit and is used to détermine whether there is another label stack entry in the header. And, the time-to-live ("TTL") field is 8 bits long and is similar to the TTL field carried in the IP header and is used to détermine how many hops the frame can traverse. The IP frame is encapsulated in with an MPLS header at the ingress edge of the MPLS network. At the egress edge, the IP frame is restored by removing the MPLS header.

[0007] The label distribution protocol ("LDP") is used to build and maintain MPLS label databases that are used to forward traffic through MPLS networks. The LDP is specified in Internet Engineering Task Force ("IETF") documents request for comment ("RFC") 3036, "LDP Spécification", January 2001, and RFC 3037, "LDP Applicability", January 2001, which are

incorporated herein by référence. As mentioned above, MPLS is a method for forwarding packets that uses short, fïxed-length values carried by packets, called labels, to détermine packet next hops. A fondamental concept in MPLS is that two LSRs must agrée on the meaning of the labels used to forward traffic between and through them. This common understanding is achieved by using a set of procédures (Le., the LDP) by which one LSR informs another of label bindings it has made. Thus, the LDP is a set of procédures by which one LSR informs another of the meaning of labels used to forward traffic between and through them.

[0008] Now, a pseudo-wire (or pseudowire or "PW") is an émulation of a native service over a packet switched network ("PSN"). The native service maybe asynchronoustransfer mode ("ATM"), Frame Relay, Ethernet, low-rate time-division multiplexing ("TDM"), or synchronous optical network/synchronous digital hierarchy ("SONET/SDH"), while the PSN may be a MPLS, IP, or Layer 2 tunnelling protocol ("L2TP") based network. The PW émulâtes the opération of a "transparent wire" carrying the native service. In other words, a PW émulâtes a point-to-point link and provides a single service which is perceived by its user as an unshared link or circuit of the chosen service.

[0009] In gênerai, a PW is a connection between two provider edge ("PE") devices which connects two attachment circuits ("ACs"). An AC can be a Frame Relay data link connection identifier ("DLCI"), an ATM virtual path identifïer/virtual channel identifier ("VPI/VCI"), an Ethernet port, a virtual local area network ("VLAN"), a high-level data link control ("HDLC") link, a point-to-point protocol ("PPP") connection on a physical interface, a PPP session from an L2TP tunnel, an MPLS label switched path ("LSP"), etc. During the setup of a PW, the two PEs will be configured or will automatically exchange information about the service to be emulated so that later they know how to process packets coming from the other end. After a PW is set up between two PEs, frames received by one PE from an AC are encapsulated and sent over the PW to the remote PE, where native frames are re-constructed and forwarded over the other AC. The PE devices may be, for example, MPLS switches, LERs, or LSRs.

[0010] PW extensions to the LDP are described in IETF document RFC 4447, "Pseudowire Setup and Maintenance Using the Label Distribution Protocol (LDP)", April 2006, which is incorporated

herein by référence. According to RFC 4447, Layer 2 services (such as Frame Relay, ATM, and Ethernet) can be "emulated" over an MPLS backbone by encapsulating the Layer 2 protocol data units ("PDUs") and transmitting them over PWs. In other words, PWs are created to carry différent types of traffic across a MPLS network, the PW being a point-to-point network connection over MPLS that offers transparency of the Layer 2 service which it transports.

[0011 ] RFC 4447 spécifies a protocol for establishing and maintaining PWs, using extensions to the LDP. It defines new type -length- values ("TLVs"), FEC éléments, parameters, and codes for LDP, which enable LDP to identify PWs and to signal attributes of PWs. It spécifies how a PW endpoint uses thèse TLVs in LDP to bind a demultiplexor field value (Le., an MPLS label as described above) to a PW, and how it informs the remote endpoint of the binding. It also spécifies procédures for reporting PW status changes, for passing additional information about the PW as needed, and for releasing the bindings.

[0012] Consider the following RFC 4447 scénario. Suppose that it is desired to transport Layer 2 PDUs from ingress LSR PEi to egress LSR PE ₂ , across an intervening MPLS-enabled network. Assume that there is an MPLS tunnel from PEi to PE ₂ . That is, assume that PEi can cause a packet to be delivered to PE ₂ by encapsulating the packet in an "MPLS tunnel header" and sending the resuit to one of its adjacencies. The MPLS tunnel is a MPLS label switched path ("LSP"); thus, putting on an MPLS tunnel encapsulation is a matter of pushing on an MPLS label. Also suppose that a large number of P Ws can be carried through a single MPLS tunnel. Thus, it is never necessary to maintain state in the network core for individual PWs. It is not presupposed that the MPLS tunnels are point-to-point; although the PWs are point-to-point, the MPLS tunnels may be multipoint-to-point. It is not presupposed that PE ₂ will even be able to détermine the MPLS tunnel through which a received packet was transmitted. (For example, if the MPLS tunnel is an LSP and penultimate hop popping is used, when the packet arrives at PE ₂ it will contain no information identifying the tunnel.) When PE ₂ receives a packet over a PW, it must be able to détermine that the packet was in fact received over a PW, and it must be able to associate that packet with a particular PW. PE ₂ is able to do this by examining the MPLS label that serves as the PW demultiplexor field. This label may by called the "PW label". When PEi sends a Layer 2 PDU to PE ₂ , it créâtes an MPLS packet by adding the PW label to the packet, thus creating the fîrst entry of the label stack. If the

PSN tunnel is an MPLS LSP, the PEi pushes another label (i.e., the tunnel label) onto the packet as the second entry of the label stack. The PW label is not visible again until the MPLS packet reaches PE ₂ . PE ₂ ¹ S disposition of the packet is based on the PW label.

[0013] Thus, a PW is a point-to-point connection across an MPLS network identified by a stack of two labels. The fîrst label is called the "outer" label. It represents the outer tunnel, or outer LSP. This outer tunnel is needed to transport the packets across the network. Within this outer tunnel, "inner" connections (i.e., PWs) may be multiplexed. Each of thèse inner connections is identified by a second label, usually called the "inner" label. The outer tunnel is usually signalled (i.e., labels exchanged, etc.) using aprotocol such as LDP or the resource réservation protocol-traffic extension ("RSVP-TE"). The inner connection (i.e., the PW) is signalled using LDP in its downstream unsolicited ("DU") mode (i.e., "LDP-DU"). When LDP-DU mode is engaged, a LSR (e.g., a MPLS switch) can distribute MPLS label bindings to other LSRs that hâve not explicitly requested them. This label management behaviour is described in RFC 3036. Thus, the MPLS LDP-DU signalling protocol with PW extensions is thus used to establish bidirectional PWs across a MPLS network.

[0014] The PWs referred to above may also be referred to as single-segment pseudo-wires ("SS- PWs") as they are setup directly between two terminating PEs ("T-PEs"). Each direction of the SS- PW traverses one PSN tunnel that connects the two T-PEs. Thus, a T-PE is a PE where the customer-facing attachment circuits ("ACs") are bound to a PW forwarder. A PW may also hâve a number of segments. Such a PW may be referred to as a multi-segment pseudo-wire ("MS-PW"). Thus, a MS-PW is a static or dynamically confîgured set of two or more contiguous PW segments that behave and fonction as a single point-to-point PW. Each end of a MS-PW by définition terminâtes on a T-PE. That is, a T-PE is présent in the fîrst and last segments of a MS-PW. PEs located between T-PEs on a MS-PW are referred to as switching PEs ("S-PEs"). A S-PE is a PE capable of switching the control and data planes of the preceding and succeeding PW segments in a MS-PW. The S-PE terminâtes the PSN tunnels transporting the preceding and succeeding segments of the MS-PW. It is therefore a PW switching point for a MS-PW. A PW switching point is never the S-PE and the T-PE for the same MS-PW. A PW switching point runs necessary protocols to setup and manage PW segments with other PW switching points and T-PEs.

[0015] Now, as service providers ("SPs") deploy PW services, fault détection and diagnostic mechanisms particularly for the PSN portion of the network are pivotai. Specifîcally, the ability to provide end-to-end fault détection and diagnostics for an emulated PW service is an important considération for SPs. The terni virtual circuit connection vérification ("VCCV") has been used to refer to a control channel that is associated with a SS-PW and to the corresponding opérations and management fonctions such as connectivity vérification to be used over that control channel. In gênerai, VCCV defines a set of messages that are exchanged between PEs to verify connectivity of the SS-PW. To make sure that VCCV packets follow the same path as the SS-PW data flow, they are typically encapsulated with the same SS-PW démultiplexer and transported over the same PSN tunnel. For example, if MPLS is the PSN in use, then the same label shim header (and label stack) are typically incorporated. VCCV can be used both as a fault détection and/or a diagnostic tool for SS-PWs. An operator can periodically invoke VCCV for proactive connectivity vérification on an active SS-PW, or on an ad hoc or as-needed as a means of manual connectivity vérification. When invoking VCCV, the operator triggers a combination of one of its various connectivity check("CC") types and one of its various connectivity vérification ("CV") types. Thèse include label switched path ("LSP"), L2TP, or Internet control message protocol ("ICMP") ping modes and are applicable depending on the underlying PSN. For référence, term "ping" refers to an opération that maybe used to test connectivity in a network. A ping opération sends an écho request packet to an address, and then awaits a reply. The resuit of the ping opération can help SPs evaluate path-to-host reliability, delays over the path, and whether the host can be reached or is functioning. For example, a ping opération may be is based on ICMP traffic and may use public routing tables in order to get to the required destination (if it exists). For référence, IETF document RFC 4379, "Detecting Multi- Protocol Label Switched (MPLS) Data Plane Failures", February 2006, which is incorporated herein by référence, describes MPLS "écho requests" and "écho replys" for the purposes of fault détection and isolation for MPLS label switched paths ("LSPs").

[0016] However, for new MS-PW services, there is currently no effective method to easily pinpoint the point of failure and verify the end-to-end connectivity of a MS-PW. In particular, one problem with présent MS-PW networks is that the control plane of the ingress node (i.e., the T-PE) of the MS-PW does not hâve access to the necessary information pertaining to the next segment of the MS- PW in order to format a VCCV écho request (or ping) and to allow for the successfol validation of

the écho request at the next segment of the MS-PW. While an operator of the network can manually perform a VCCV ping for each individual segment of the MS-PW one at a time, this is time consuming, not user-friendly, and requires the operator to hâve detailed knowledge of each segment of the whole MS-PW. In addition, such a manual approach may not even be possible if the operator does not hâve access to ail the segments of the MS-PW (e.g., if the MS-PW spans the PSNs of différent SPs).

[0017] A need therefore exists for an improved method and System for verifying connectivity of multi-segment pseudo-wires connections in packet switched networks. Accordingly, a solution that addresses, at least in part, the above and other shortcomings is desired.

SUMMARY OF THE INVENTION

[0018] According to one aspect of the invention, there is provided a method for testing connectivity of a multi-segment pseudo-wire in a packet switched network, the method comprising: (a) sending an écho request message from a fîrst provider edge device to a second provider edge device for a first segment of the multi-segment pseudo-wire between the first provider edge device and the second provider edge device; and, (b) receiving an écho reply message from the second provider edge device in response to the écho request message, the écho reply message: confirming connectivity of the first segment; indicating whether there is a second segment in the multi-segment pseudo-wire between the second provider edge device and a third provider edge device; and, if there is a second segment, including information pertaining to the second segment.

[0019] The method may further include, if there is a second segment: (c) sending a second écho request message from the first provider edge device to the third provider edge device; and, (d) receiving a second écho reply message from the third provider edge device in response to the second écho request message, the second écho reply message: confirming connectivity of the second segment; indicating whether there is a third segment in the multi-segment pseudo-wire between the third provider edge device and a fourth provider edge device; and, if there is a third segment, including information pertaining to the third segment. The first provider edge device may hâve information pertaining to the first segment. The écho request message may include the information pertaining to the first segment. The second écho request message may include the information

pertaining to the second segment. The packet switched network may be a multiprotocol label switching ("MPLS") network. The information pertaining to the fîrst and second segments may include atype-length-value ("TLV") for apseudo-wire forwarding équivalence class ("FEC"). The indicating whether there is a second segment in the multi-segmentpseudo-wire betweenthe second provider edge device and a third provider edge device may be facilitated by at least one of : the écho reply message including the information pertaining to the second segment; and, first and second return codes, wherein the fîrst return code indicates that the second segment does exist, and wherein the second return code indicates that the second segment does not exist. The packet switched network may include first and second packet switched networks, wherein the fîrst and second segments may be in the first and second packet switched networks, respectively, and wherein the fîrst and second packet switched networks are controlled by fîrst and second service providers, respectively. And, the second provider edge device may be a k ^th provider edge device, the third provider edge device may be a (k+l) ^th provider edge device, the first segment may be a (k-l) ^th segment of n segments of the multi-segment pseudo-wire between the first provider edge device and the k ¹ provider edge device, the second segment may be a k ^ι segment of the n segments of the multi-segment pseudo-wire between the k ^th provider edge device and the (k+l)" ¹ provider edge device, k and n are integers, k is less than or equal to n, and further comprising repeating steps (a) and (b) for k = 3 to n.

[0020] In accordance with further aspects of the présent invention there is provided an apparatus such as a data processing System (e.g., a MPLS router or switch, a network élément, a network management System, etc.), a method for adapting this System, as well as articles ofmanufacture such as a computer readable médium having program instructions recorded thereon for practising the method of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] Further features and advantages of the embodiments of the présent invention will become apparent from the following detailed description, taken in combination with the appended drawings, in which:

[0022] FIG. 1 is a block diagram illustrating a multi-segment pseudo-wire based communications network in accordance with an embodiment of the invention;

[0023] FIG. 2 is a block diagram illustrating a data processing System adapted to implement an embodiment of the invention; and,

[0024] FIG. 3 is a fiow chart illustrating opérations of modules within the memory of a data processing System for testing connectivity of a multi-segment pseudo-wire in a packet switched network, in accordance with an embodiment of the invention.

[0025] It will be noted that throughout the appended drawings, like features are identifîed by like référence numerals.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0026] In the following description, détails are set forth to provide an understanding of the invention. In some instances, certain software, circuits, structures and techniques hâve not been described or shown in détail in order not to obscure the invention. The term "data processing System" is used herein to refer to any machine for processing data, including the network éléments and network management Systems described herein. The présent invention may be implemented in any computer programming language provided that the operating System of the data processing System provides the facilities that may support the requirements of the présent invention. Any limitations presented would be a resuit of a particular type of operating System or computer programming language and would not be a limitation of the présent invention. The présent invention may also be implemented in hardware.

[0027] FIG. 1 is a block diagram illustrating a multi-segment pseudo-wire based communications network 100 in accordance with an embodiment of the invention. The communications network (or System) 100 includes a fîrst provider edge ("PE") device PEl coupled to a second PE device PE2 over a fîrst packet switched network ("PSN") PSNl via a fîrst pseudo-wire ("PW") segment PWl. In addition, the second PE device PE2 is coupled to a third PE device PE3 over a second PSN network PSNl via a third PW segment PW3. Customer edge ("CE") devices CEI, CE2 are coupled to respective PE devices PEl, PE3 by respective attachment circuits ("ACs") ACl, AC2. The PSN

networks PSNl, PSN2 may be MPLS networks, IP networks, etc. The PE devices PEl, PE2, PE3 may be MPLS switches, nodes, éléments, switches, routers, etc. The PE devices PEl, PE2, PE3 may be maintainedby at least one service provider ("SP") to provide Layer 2 services to a subscriber or user via the CE devices CEI, CE2. According to one embodiment, the PE devices PEl, PE2, PE3 may be coupled to a network management System ("NMS") (not shown) for controlling and monitoring purposes. The NMS may be located at the SP's central office ("CO") or elsewhere.

[0028] Thus, PEl and PE3 provide PW service to CEI and CE2 and may be referred to as terminating PEs ("T-PEs") T-PEl, T-PE2. Thèse PEs réside in différent PSN domains, PSNl and PSN2, respectively. A PSN tunnel extends from PEl to PE2 across PSNl, and a second PSN tunnel extends from PE2 to PE3 across PSN2. PWs are used to connect the AC ACl attachedto PEl to the corresponding AC AC2 attachedto PE3. Each PW (i.e., PWl, PW2) on the tunnel across PSNl is stitched to a PW (i.e., PW3, PW4) in the tunnel across PSN2 at PE2 to complète a multi-segment pseudo-wire ("MS-PW") 110, 120 between PEl andPE3. PE2 is therefore the PW switching point and may be referred to as a PW switching provider edge ("S-PE") S-PE. PWl and PW3 are segments of the same MS-PW 110 while PW2 and PW4 are segments of another MS-PW 120. PW segments (e.g., PWl and PW3) of the same MS-PW (e.g., 110) may be of the same PW type or différent type, and PSN tunnels (e.g., PSNl and PSN2) may be the same or différent technology. The S-PE switches a MS-PW (e.g., 110) from one segment to another based on the PW identifiers (e.g., PW label in case of MPLS PWs). Thus, FIG. 1 illustrâtes a MS-PW 110 providing connectivity from PEl to PE3 (both T-PEs) through a switching point PE2 (an S-PE).

[0029] FIG.2 is a block diagram illustrating a data processing System 300 adapted to implement an embodiment of the invention. The data processing System 300 is suitable for opération as a PE device PEl, PE2, PE3, a CE device CEI, CE2, or aNMS. The data processing system300 includes a central processing unit ("CPU") 320, memory 330, and an interface device 350 and may optionally include an input device 310 and a display 340. The CPU 320 may include dedicated coprocessors and memory devices. The CPU 320 is operatively coupled to memory 330 which stores an operating System (not shown) for gênerai management of the System 300. The memory 330 may include PvAM, ROM, disk devices, and databases. The memory 330 may include a variety of storage devices including internai memory and external mass storage typically arranged in a hierarchy of storage as

understood to those skilled in the art. The interface device 350 may include one or more network connections. The data processing System 300 is adapted for communicating with other data processing Systems (e.g., PEl andPE3 forPE2) over a network 100, PSNl, PSN2 via the interface device 350. The input device 310 may include a keyboard, a mouse, a trackball, or a similar device. And, the display 340 may include a computer screen, terminal device, or a hardcopy producing output device such as a printer or plotter. The CPU 320 of the System 300 is typically coupled to one or more input devices 310 for receiving user commands or queries and for displaying the results of thèse commands or queries to the user on the display 340. Commands and queries may also be received over a network connection and results may be transmitted over a network connection. The data processing System 300 may include a database System 332 for storing and accessing network topology and programming information. The database System 332 may include a database management System ("DBMS") and a database and may be stored in the memory 330 of the data processing System 300. The data processing System 300 has stored therein data representing séquences of instructions which when executed cause the method described herein to be performed. Of course, the data processing System 300 may contain additional software and hardware a description of which is not necessary for understanding the invention.

[0030] Optionally, a user may interact with the data processing System 300 and its hardware and software modules 331 using an optional graphical user interface ("GUI") 380. The GUI 380 may be used for monitoring, managing, and accessing the data processing System 300. GUIs are supported by common operating Systems and provide a display format which enables a user to choose commands, exécute application programs, manage computer files, and perform other functions by selecting pictorial représentations known as icons, or items from a menu through use of an input or pointing device such as a mouse 310. In gênerai, a GUI is used to convey information to and receive commands from users and generally includes a variety of GUI objects or controls, including icons, toolbars, drop-do wn menus, text, dialog boxes, buttons, and the like. A user typically interacts with a GUI 380 presented on a display 340 by using an input or pointing device (e.g., a mouse) 310 to position a pointer or cursor 390 over an object 391 and by "clicking" on the object 391.

[0031 ] Typically, a GUI based System présents application, System status, and other information to the user in "windows" appearing on the display 340. A window 392 is a more or less rectangular area

within the display 340 in which a user may view an application or a document. Such a window 392 may be open, closed, displayed Ml screen, reduced to an icon, increased or reduced in size, or moved to différent areas of the display 340. Multiple Windows may be displayed simultaneously, such as: Windows included within other Windows, Windows overlapping otherwindows, orwindows tiled within the display area.

[0032] Thus, the data processing System 300 includes computer exécutable programmed instructions for directing the System 300 to implement the embodiments of the présent invention. The programmed instructions may be embodied in one or more hardware modules or software modules 331 which may be résident in the memory 330 of the data processing System 300. Alternatively, the programmed instructions may be embodied on a computer readable médium (such as a CD disk or floppy disk) which may be used for transporting the programmed instructions to the memory 330 of the data processing System 300. Alternatively, the programmed instructions may be embedded in a computer-readable signal or signal-bearing médium that is uploaded to a network 100 by a vendor or supplier of the programmed instructions, and this signal or signal-bearing médium may be downloaded through an interface (e.g., 350) to the data processing System 300 from the network 100 by end users or potential buyers.

[0033] As mentioned above, for new MS-PW services, there is currently no effective method to easily pinpoint the point of failure and verify the end-to-end connectivity of a MS-PW (e.g., 110 comprised of PWl and PW3). In particular, one problem with présent MS-PW networks (e.g., 100) is that the control plane of the ingress node (e.g, T-PEl for PWl) ofthe MS-PW 110 does nothave access to the necessary information pertaining to the next segment (e.g., PW3) ofthe MS-PW 110 in order to format a VCCV écho request (or ping) and to allow for the successfùl validation ofthe écho request at the next segment PW3 of MS-PW 110. While an operator ofthe network 100 can manually perform a VCCV ping for each individual segment PWl, PW3 ofthe MS-PW 110 one at a time, this is time consuming, not user-friendly, and requires the operator to hâve detailed knowledge of each segment PWl, PW3 of the whole MS-PW 110. In addition, such a manual approach may not even be possible if the operator does not hâve access to ail the segments PWl, PW3 ofthe MS-PW 110 (e.g., if the MS-PW 110 spans the PSNs PSNl, PSN2 of différent SPs).

[0034] According to one embodiment of the invention, an automated VCCV trace method is provided that allows users (e.g., SP operators) to verify end-to-end connectivity and datapaths for a MS-PW IlO. Ifthere is a failure, a user may easily pinpoint which segment PWl, PW3 is the cause of failure within the MS-PW 110 via a single operational command.

[0035] According to one embodiment, each target node or far-end (e.g., S-PE) of each segment (e.g., PWl) of a MS-PW (e.g., 110) responds to a VCCV écho request (e.g., from T-PEl) with an écho reply containing a return code of 8 (i.e., label switched at stack-depth), a FEC 128 sub-TLV, and any other necessary information regarding the next segment (e.g., PW3). The originating node (e.g., T- PEl) of the initial écho request, upon receiving the écho reply with the FECl 28 sub-TLV (e.g., from S-PE), then composes the next VCCV écho request with the received FEC 128 sub-TLV and sends it to the next segment (e.g., PW3) of the MS-PW 110. Thèse steps are then repeated for other segments (not shown) ofthe MS-PW 110. The destination node (e.g., T-PE2) ofthe MS-PW 110 or far-end of the last segment PW3 responds to a VCCV écho request with an écho reply that indicates a return code of 3 (i.e., egress router at stack-depth) and with no FEC128 sub-TLV. This indicates to the originating node (e.g., T-PEl) that this is the end ofthe MS-PW 110 and the method is completed. Advantageously, this method complies with the LSP ping infrastructure described in RFC 4379. In addition, this method fonctions regardless ofthe datapath method employedto forwardthe VCCV écho packets through the MS-PW.

[0036] Thus, according to one embodiment, a VCCV trace can be performed on a MS-PW 110 originating from PEl (or T-PEl) by a single operational command by the following method steps.

[0037] First, PEl sends a VCCV écho request with a FEC 128 sub-TLV containing PW information pertaining to the first PW segment PWl (i.e., between PEl and PE2) to PE2 (or S-PE) for validation. Note that TLVs are defined in section 7.2 of RFC 4379. The terni "FEC128 sub-TLV" refers to "TLV Type 1, Sub-Type 9, Value Field 'FEC 128' Pseudowire (Deprecated)" or "TLV Type 1, Sub-Type 10, Value Field 'FEC 128' Pseudowire" as per section 7.2 of RFC 4379. (Note that a "TLV Type 1, Sub-Type 11, Value Field 'FEC 129' Pseudowire" as per section 7.2 of RFC 4379 may also be used.) For référence, within data communication protocols, optional information may be encoded as a type-length-value ("TLV") élément inside ofthe protocol. The type and length

fields are fixed in size (e.g., 1 -4 bytes) andthe value fîeld is of variable size. Thèse fîelds are used as follows: type - a numeric code which indicates the kind of fîeld that this part of the message represents; length - the size of the value fîeld (typically in bytes); and, value - variable sized set of bytes which contains data for this part of the message. Also for référence, a forwarding équivalence class ("FEC") is a term used in MPLS to describe a set of packets with similar or identical characteristics which may be forwarded in the same way, that is, they may be bound to the same MPLS label. According to one embodiment, the TTL of the inner label controls the target S-PE for the écho request. According to one embodiment, the delivery of VCCV écho packets on the datapath can employ methods such as the use of the inner Vc label TTL as described in IETF draft document "VCCV Extensions for Segmented Pseudo-Wire" (draft-hart-pwe3-segmented-pw-vccv-00.txt), June 2006, which is incorporated herein by référence, or the use of the multi-hop TTL ("MH-TTL") as described in IETF draft document "Segmented Pseudo Wire" (draft-ietf-pwe3-segmented-pw- 02.txt), March 2006, which is also incorporated herein by référence.

[0038] Second, PE2 validâtes the écho request with a FEC 128 sub-TLV. Since it is a switching point (i.e., S-PE) between the first and second segments PWl, PW3 it builds an écho reply with a return code of 8 and a FEC128 sub-TLV for the second segment PW3 (i.e., between PE2 and PE3) and replies back to PEl. Note that return codes are defined in section 3.1 of RFC 4379. A return code of value 8 means "Label switched at stack depth <RSC>" while a return code of value 3 means

"Replying router is an egress for the FEC at stack depth <RSC>" as per section 3.1 of RFC 4379. Note that "RSC" in the forgoing represents a return subcode that contains the point in the label stack where processing was terminated. If the RSC is zéro, no labels were processed. Otherwise, the packet would hâve been label switched at depth RSC.

[0039] Third, PEl builds a second VCCV écho request based on the FEC 128 sub-TLV of the reply from PE2. PEl then sends this second VCCV écho request to PE3.

[0040] Fourth, PE3 validâtes the écho request with the FEC128 sub-TLV from PEl. Since PE3 is the destination node or the egress node (i.e., T-PE2) of the MS-PW 110 it replies to PEl with an écho reply that contains no FEC128 sub-TLV but with a return code of 3 (i.e., egress router).

[0041] Fifth, PEl receives the écho reply from PE3. PEl knows that PE3 is the destination of the MS-PW 110 because the écho reply does not contain a next FEC 128 sub-TLV and because its return code is 3. The method then ends.

[0042] Note that in the above it is assumed that only a FEC128 sub-TLV is exchanged. However, the VCCV trace method may also use other TLVs or target FEC sub-TLVs (e.g., a FEC 129, a LDP prefix, a RSVP LSP, etc.).

[0043] According to one embodiment, the method may be initiated by a user through the GUI 380 of the data processing System 300 (e.g., by entering a corresponding command, by clicking on an corresponding icon 391, by selecting a corresponding item from a menu, etc.) and the results of the method may be displayed to the user on the data processing system's display screen 340. According to another embodiment, the method may be initiated automatically.

[0044] According to one embodiment, the présent invention supports control plane processing of an VCCV écho message in a MS-PW. The challenge for the control plane is to be able to build the VCCV écho request packet with the necessary information such as the target FEC 128 PW sub-TLV (FEC 128) of the downstream PW segment to which the packet is destined. As mention above, this may be made even more difficult in that the MS-PW could span différent SPs and autonomous Systems. For example, and referring to FIG. 1 , T-PEl has the required information to compose the FEC128 of PWl but it does not hâve the information required to compose the FEC128 of PW3 if VCCV écho request is supposed to be destined for T-PE2. This challenge can be overcome by the method described in the following.

[0045] With respect to receiving a VCCV écho request, upon receiving a VCCV écho request the S- PE (or the target node of each segment PWl, PW3 of the MS-PW 110) validâtes the request and responds to the request with an écho reply consisting of the FEC128 of the next downstream segment PW3 and a return code of 8 (i.e., label switched at stack depth) indicating that it is an S-PE and not the egress router for the MS-PW 110. If the node is T-PE2 or the egress node ofthe MS-PW 110, it responds to the écho request with an écho reply with a return code of 3 (i.e., egress router) and no FEC 128 is included.

[0046] With respect to receiving a VCCV écho reply, the opérations to be taken by the node (e.g., T- PEl) that receives the écho reply in response to its écho request dépends on its current mode of opération such as "ping" or "trace". In "ping" mode, the node T-PEl may choose to ignore the target FEC128 in the écho reply and report only the return code to the user (e.g., operator). However, in "trace" mode, the node T-PEl builds and sends the subséquent VCCV écho request to the next downstream segment PW3 with the information (such as the downstreamFEC128) itreceivedinthe écho reply.

[0047] With respect to VCCV trace opérations, as an example, in FIG. 1 , a VCCV trace can be performed on a MS-PW (e.g., 110) originating from T-PEl by a single operational command. This may be accomplished by the folio wing method steps. First, T-PEl sends a VCCV écho request with a FEC128 containing the pseudo-wire information of the fîrst segment (i.e., PWl between T-PEl and S-PE) to S-PE for validation. Second, S-PE validâtes the écho request with the FEC128. Since it is a switching point between the fïrst and second segments PWl , PW3 it builds an écho reply with a return code of 8 and includes the FECl 28 ofthe second segment (i.e., PW3 between S-PE and T- PE2) and sends the écho reply back to T-PEl . Third, T-PEl builds a second VCCV écho request based on the FEC 128 in the écho reply from S-PE. It sends the next écho request out to T-PE2. According to one embodiment, the VCCV écho request packet is switched at the S-PE datapath and forwarded to the next downstream segment PW3 without any involvement from the control plane. Fourth, T-PE2 receives and validâtes the écho request with the FEC 128 ofPW3 from T-PEl. Since T-PE2 is the destination node or the egress node ofthe MS-PW 110 it replies to T-PEl with an écho reply with a return code of 3 (i.e., egress router) and no FEC128 is included. Fifth, T-PEl receives the écho reply from T-PE2. T-PEl is made aware that T-PE2 is the destination ofthe MS-PW 110 because the écho reply does not contain the any FEC128 and its return code is 3. The trace method then ends. Note that the preceding example assumes only a FECl 28 sub-TLV is exchanged but it is possible that the exchanged information could also involve other TLV or Target FEC sub-TLVs (e.g., FEC129, LDP Prefix, or RSVP LSP). Further détail with respect to the format ofthe VCCV écho packet may be found in RFC 4379.

[0048] Note that in gênerai each S-PE in the network 100 needs to conform to the method described above to allow the VCCV trace to be end-to-end.

[0049] The présent invention pro vides several advantages. First, it allows a user (e.g., a SP operator) to dynamically learn and validate both control and data paths of a MS-PW without prior knowledge of each SS-PW (i.e., each PW segment). Second, it is more efficient than manually pinging individual segments when diagnosing problems on a MS-PW. Third, it overcomes potential difficultés when dealing with MS-PWs that span différent SP networks. Fourth, it is user-friendly and easy to use. And fifth, is provides an automated method to traverse a MS-PW segment by segment and to identify the point of failure with a single operational command.

[0050] The above described method may be summarized with the aid of a flowchart. FIG.3 is a flow chart illustrating opérations 200 of modules 331 within the memory 330 of a data processing System 300 for testing connectivity of a multi-segment pseudo-wire 110 in a packet switched network 100, in accordance with an embodiment of the invention.

[0051] At step 201, the opérations 200 start.

[0052] At step (a), an écho request message is sent from a fîrst provider edge device PEl to a second provider edge device PE2 for a fîrst segment PWl of the multi-segment pseudo-wire 110 between the fîrst provider edge device PEl and the second provider edge device PE2.

[0053] At step (b), an écho reply message is received from the second provider edge device PE2 in response to the écho request message, the écho reply message: confirming connectivity of the fîrst segment PWl ; indicating whether there is a second segment PW3 in the multi-segment pseudo-wire 110 between the second provider edge device PE2 and a third provider edge device PE3; and, if there is a second segment PW3, including information pertaining to the second segment PW3.

[0054] At step 202, the opérations 200 end.

[0055] The method may further include, if there is a second segment PW3: (c) sending a second écho request message from the fîrst provider edge device PEl to the third provider edge device PE3; and, (d) receiving a second écho reply message from the third provider edge device PE3 in response to the second écho request message, the second écho reply message: confirming connectivity of the second segment PW3 ; indicating whether there is a third segment (not shown) in the multi-segment pseudo-wire 110 between the third provider edge device PE3 and a fourth provider edge device (not

shown); and, if there is a third segment, including information pertaining to the third segment. The fïrst provider edge device PEl may hâve information pertaining to the first segment PWl. The écho request message may include the information pertaining to the first segment PWl . The second écho request message may include the information pertaining to the second segment PW3. The packet switched network 100 may be a multiprotocol label switching ("MPLS") network. The information pertaining to the first and second segments PWl , PW3 may include a type-length-value ("TLV") for a pseudo-wire forwarding équivalence class ("FEC"). The indicating whether there is a second segment PW3 in the multi-segment pseudo-wire 110 between the second provider edge device PE2 and a third provider edge device PE3 may be facilitated by at least one of: the écho reply message including the information pertaining to the second segment; and, first and second return codes, wherein the first return code (e.g., "8") indicates that the second segment PW3 does exist, and wherein the second return code (e.g., "3") indicates that the second segment PW3 does not exist. The packet switched network 100 may include first and second packet switched networks PSNl, PSN2, wherein the first and second segments PWl, PW3 may be in the first and second packet switched networks PSNl, PSN2, respectively, and wherein the first and second packet switched networks PSNl, PSN2 are controlledby first and second service providers, respectively. And, the second provider edge device PE2 may be a k" ¹ provider edge device, the third provider edge device PE3 may be a (k+l/ provider edge device, the first segment PWl may be a (k-1 )' segment of n segments of the multi-segment pseudo-wire 110 between the first provider edge device PEl and the k ^ι provider edge device, the second segment PW3 may be a k segment of the n segments of the multi-segment pseudo-wire 110 between the k" ¹ provider edge device and the (k+ 1 ) ^th provider edge device, k and n are integers, k is less than or equal to n, and further comprising repeating steps (a) and (b) for k = 3 to n.

[0056] According to one embodiment of the invention, the above described method may be implemented by aNMS (not shown) rather than by, or in combination with, the PEs PEl, PE2, PE3, 300.

[0057] While this invention is primarily discussed as a method, a person of ordinary skill in the art will understand that the apparatus discussed above with référence to a data processing System 300, may be programmed to enable the practice of the method of the invention. Moreover, an article of

manufacture for use with a data processing system 300, such as a pre-recorded storage device or other similar computer readable médium including program instructions recorded thereon, may direct the data processing system 300 to facilitate the practice of the method of the invention. It is understood that such apparatus and articles of manufacture also corne within the scope of the invention.

[0058] In particular, the séquences of instructions which when executed cause the method described herein to be performed by the data processing system 300 can be contained in a data carrier product according to one embodiment of the invention. This data carrier product can be loaded into and run by the data processing system 300. In addition, the séquences of instructions which when executed cause the method described herein to be performed by the data processing system 300 can be contained in a computer software product according to one embodiment of the invention. This computer software product can be loaded into and run by the data processing system 300. Moreover, the séquences of instructions which when executed cause the method described herein to be performedby the data processing system 300 can be contained in an integrated circuit product (e.g., hardware modules) including a coprocessor or memory according to one embodiment of the invention. This integrated circuit product can be installed in the data processing system 300.

[0059] The embodiments of the invention described above are intendedto be exemplary only. Those skilled in this art will understand that various modifications of détail may be made to thèse embodiments, ail of which corne within the scope of the invention.