Patent Description:
A new stateless replication architecture, called Bit Index Explicit Replication (BIER), has been recently proposed. BIER is an optimal and scalable solution for multipoint replication by using bit-string based forwarding and by following unicast path. Numerous efforts have been made in industry to support BIER as the underlay transport mechanism for service delivery. For example, Ethernet virtual private network (EVPN) may use BIER as the underlay Point-to-Multipoint (P2MP) transport to handle Broadcast, Unknown Unicast and Multicast (BUM) traffic. Applying failure detection mechanisms such as Bidirectional Forwarding Detection (BFD) or Seamless Bidirectional Forwarding Detection (S-BFD) for P2MP scenarios such as Protocol Independent Multicast (PIM) based multicast may raise challenges on how to react to a failure. The failure may be detected by the head end while the tree needs to be built by the tail ends. BIER follows unicast path and does not require any per stream tree building from receivers (or egress) towards the sender (or ingress). The Ingress may use any available unicast path to forward the BIER encapsulated packet to Egress/Receivers. Thus, a failure detection may be easily applied to BIER resulting in rapid failure detections. Other failure detection mechanisms in multicast networks are disclosed in the patent applications <CIT> and <CIT>.

In particular embodiments, a first network apparatus may identify a plurality of target network apparatuses within a network to which the first network apparatus belongs. The first network apparatus may generate a first message comprising one or more headers. The one or more headers may comprise a reply-required indication and encoded identities for the plurality of target network apparatuses. The first network apparatus may send the first message through the network. The network may be configured to deliver a copy of the first message to each of the plurality of target network apparatuses using a point-to-multipoint packet-forwarding architecture based on the encoded identities for the plurality of target network apparatuses. The first network apparatus may receive one or more second messages from one or more of the plurality of target network apparatuses, respectively. Each of the one or more second messages may be generated as a reply to the first message by one of the one or more target network apparatuses. The first network apparatus may identify which of the plurality of target network apparatuses failed to respond to the first message based on the received one or more second messages.

In particular embodiments, a second network apparatus may receive the first message from the first network apparatus. The first message may comprise one or more headers. The one or more headers may comprise encoded identities for a plurality of target network apparatuses in a network. The plurality of target network apparatuses may comprise the second network apparatus. The network may be configured to deliver the first message to the second network apparatus using a point-to-multipoint packet-forwarding architecture based on encoded identity of the second network apparatus in encoded identities. The second network apparatus may determine that the one or more headers of the first message comprise a reply-required indication. The second network apparatus may identify the first network apparatus based on the one or more headers of the first message. The second network apparatus may generate a second message comprising a payload and one or more headers. The payload of the second message may be identical to a payload of the first message. A destination field in the one or more headers of the second message may be set with an encoded identity of the first network apparatus. A source field of the one or more headers of the second message may be set with an encoded identity of the second network apparatus. The second network apparatus may send the second message through the network. The network may be configured to deliver the second message to the first network apparatus using a point-to-multipoint packet-forwarding architecture based on the encoded identity of the first network apparatus.

Corresponding methods are also described herein. Moreover, network nodes, computer programs, computer program products, computer readable media and logic encoded on tangible media for implementing the apparatus are also described.

<FIG> illustrates an example packet switching system. In particular embodiments, a packet switching device <NUM> may comprise multiple line cards <NUM> and <NUM>, each with one or more network interfaces for sending and receiving packets over communications links (e.g., possibly part of a link aggregation group). The packet switching device <NUM> may also have a control plane with one or more processing elements <NUM> for managing the control plane and/or control plane processing of packets associated with forwarding of packets in a network. The packet switching device <NUM> may also include other cards <NUM> (e.g., service cards, blades) which include processing elements that are used to process (e.g., forward/send, drop, manipulate, change, modify, receive, create, duplicate, apply a service) packets associated with forwarding of packets in a network. The packet switching device <NUM> may comprise hardware-based communication mechanism <NUM> (e.g., bus, switching fabric, and/or matrix, etc.) for allowing its different entities <NUM>, <NUM>, <NUM> and <NUM> to communicate. Line cards <NUM> and <NUM> may typically perform the actions of being both an ingress and egress line card, in regard to multiple other particular packets and/or packet streams being received by, or sent from, packet switching device <NUM>.

In particular embodiments, a message may need to be delivered to a plurality of network apparatuses. Identities for the plurality of network apparatuses may be encoded into a destination field in a header of the message. A network may be configured to deliver a copy of a message to each of the plurality of network apparatuses using a point-to-multipoint packet-forwarding architecture based on the encoded identities for the plurality of network apparatuses in the destination field. The point-to-multipoint architecture may be Bit Index Explicit Replication (BIER). An identity of a network apparatus may be encoded into a unique bit-string. The first network apparatus may encode identities of the plurality of target network apparatuses into a destination field in the one or more headers of the first message by performing bitwise-OR operations between the bit-strings corresponding to the plurality of target network apparatuses.

<FIG> illustrates an example BIER header format. A router that supports BIER is referred to as a Bit-Forwarding Router (BFR). In a BIER network, each edge Bit-Forwarding Router (BFR) may be associated with a BFR identifier (BFR-id). A BFR-id may be an integer indicating a position of a single bit in a bit string encoding the BFR-id. A BFR-id k is encoded by a bit string of zeros except the k-th bit. The value of the k-th bit in the bit string will be one. The BFR-id may uniquely identify the corresponding BFR in the network. When a Bit-Forwarding Ingress Router (BFIR) forward a message to one or more Bit-Forwarding Egress Routers (BFERs), the BFR-id of the BFIR is encoded in the <NUM>-bit BFIR-id field of the BIER header as an unsigned integer in the range [<NUM>, <NUM>]. A BitString field of the BIER header identifies the destination BFERs for the message. The BFIR may determine the value of the BitString field by performing bitwise-OR operations between the bit-string encodings of BFR-ids for the one or more BFERs.

<FIG> illustrates an example message delivery using BIER. As an example and not by way of limitation, illustrated in <FIG>, each edge Bit-Forwarding Router (BFR) may be associated with a BFR identifier (BFR-id). In the example illustrated in <FIG>, a BFR <NUM> is associated with a bit string '<NUM>,' a BFR <NUM> is associated with a bit string '<NUM>,' a BFR <NUM> is associated with a bit string '<NUM>,' and a BFR <NUM> is associated with a bit string '<NUM>. ' A Bit-Forwarding Ingress Router (BFIR) <NUM> may want to forward a message to more than one Bit-Forwarding Egress Routers (BFERs). The BFIR <NUM> may determine BFERs <NUM> and <NUM> as destined egress routers. The BFIR <NUM> may create a destination BFR-id '<NUM>' by performing a bitwise-OR operation between the BFR-id '<NUM>' associated with BFER <NUM> and the BFR-id '<NUM>' associated with BFER <NUM>. The BFIR <NUM> may set the created destination BFR-id '<NUM>' to a destination field in a BIER header of the message. The value of the BFR-id in the BIER header may be '<NUM>. ' At step <NUM>, the BFIR <NUM> may forward the message to a connected intermediate BFR <NUM>. On receiving the message, the BFR <NUM> may determine one or more forwarding paths for the message based on the destination bit string. For each egress link, the BFR <NUM> may perform a bitwise AND operation between a bit string associated with the egress link and the destination bit string of the message. A bit string associated with the egress link toward the BFER <NUM> may be '<NUM>. ' Thus, the BFR <NUM> may perform a bitwise AND operation between '<NUM>' and '<NUM>' for the egress link. Because the result of the AND operation is '<NUM>,' the BFR <NUM>, at step <NUM>, may replicate the received message and forward the message to BFER <NUM>, which is associated with the BFR-id '<NUM>. ' A bit string associated with the egress link toward the BFER <NUM> may be '<NUM>. ' Thus, the BFR <NUM> may perform a bitwise AND operation between '<NUM>' and '<NUM>' for the egress link. Because the result of the AND operation is NULL, the BFR <NUM> may not forward the message to BFER <NUM>. A bit string associated with the egress link toward the BFER <NUM> may be '<NUM>. ' Thus, the BFR <NUM> may perform a bitwise AND operation between '<NUM>' and '<NUM>' for the egress link. Because the result of the AND operation is '<NUM>,' the BFR <NUM>, at step <NUM>, may replicate the received message and forward the message to BFER <NUM>, which is associated with the BFR-id '<NUM>.

In particular embodiments, a first network apparatus may identify a plurality of target network apparatuses within a network to which the first network apparatus belongs. The plurality of target network apparatuses may be subjects of a failure detection. In particular embodiments, the first network apparatus may be an ingress router that needs to detect any failure at one or more egress routers. The plurality of target network apparatuses may comprise egress routers of existing multicast flows. In particular embodiments, the first network apparatus may be an operations, administration and maintenance (OAM) server. The OAM server may need to detect a failure at any egress router as soon as possible. In such a case, the plurality of target network apparatuses may comprise all the edge BFRs in the network. Although this disclosure describes identifying target network apparatuses of a failure detection in a particular manner, this disclosure contemplates identifying target network apparatuses of a failure detection in any suitable manner.

In particular embodiments, the first network apparatus may generate a first message comprising one or more headers. The first message may comprise a payload data that comprises information uniquely identifying the first message. The one or more headers may comprise a reply-required indication. The one or more headers may comprise encoded identities for the plurality of target network apparatuses. In particular embodiments, the one or more headers of the first message may comprise a label. A value of the label may correspond to the first network apparatus. The reply-required indication may be encoded in the value of the label.

<FIG> illustrates an example failure detection using BIER. As an example and not by way of limitation, illustrated in <FIG>, each edge BFR (BFIR/BFER) may be associated with a value of a label, such as BIER-Multiprotocol Label Switching (MPLS)-Identifier (bmID) Label. The label may be locally unique. In particular embodiments, the values of the label may be assigned from a globally unique range. The bmID label may be different from BIER-MPLS label that is used to identify that the underlying packet is BIER-encapsulated. Non-edge BFRs are not required to be assigned with a bmID label. In particular embodiments, BFR-Prefix of an edge BFR may be used as the bmID Label. In such a case, upstream assigned lookup for BIER encapsulation may be used. In the example illustrated in <FIG>, each edge BFR is assigned with bmID from range 2200x. The BFIR <NUM> is associated with a bmID <NUM>. The BFER <NUM> is associated with a bmID <NUM>. The BFER <NUM> is associated with a bmID <NUM>. The BFER <NUM> is associated with a bmID <NUM>. The bmID may be included as a sub-Type-Length-Value (TLV) in Sub-TLV Inter-Gateway Protocol (IGP) extensions of a BIER header (not shown in <FIG>). The BFIR <NUM> may create an S-BFD echo message with your discriminator and my discriminator as local values. The S-BFD echo message may be a payload of the first message. The BFIR <NUM> may encapsulate the S-BFD echo message with its own bmID label value. The BFIR <NUM> may further encapsulate the message with BIER header. The BFIR-id field of the BIER header may be set with the BFR-id of the BFIR <NUM>. The BitString field of the BIER header may be set with a result of bitwise OR operations between the encoded identities for the destination BFERs. In the example illustrated in <FIG>, the value of the BitString field would be ` <NUM>,' a result of bitwise OR operation between the encoded BFR-id of BFER <NUM> '<NUM>' and the encoded BFR-id of BFER <NUM> '<NUM>. ' If the bmID is locally unique (upstream assigned label), the Proto field of the BIER header is set to <NUM>. If the bmID is globally unique (downstream assigned label), the Proto field of the BIER header is set to <NUM>. Although this disclosure describes creating a message for initiating a failure detection procedure in a particular manner, this disclosure contemplates creating a message for initiating a failure detection procedure in any suitable manner.

In particular embodiments, the first network apparatus <NUM> may send the first message through the network. The network may be configured to deliver a copy of the first message to each of the plurality of target network apparatuses using a point-to-multipoint packet-forwarding architecture based on the encoded identities for the plurality of target network apparatuses. The first network apparatus may set a timer for a pre-determined duration of time after sending the first message. As an example and not by way of limitation, continuing with a prior example, illustrated in <FIG>, the BFIR <NUM> may forward the created message to an intermediate BFR <NUM> based on a determined forwarding rule at step <NUM>. The bmID label value for the message is '<NUM>,' and the value of the BitString field is '<NUM>. ' After forwarding the message, the BFIR <NUM> may set a timer for a pre-determined amount of time. On receiving the message, the intermediate BFR <NUM> may determine one or more forwarding paths for the message based on the destination bit string. For each egress link, the BFR <NUM> may perform a bitwise AND operation between a bit string associated with the egress link and the destination bit string of the message. A bit string associated with the egress link toward the BFER <NUM> may be '<NUM>. ' Thus, the intermediate BFR <NUM> may perform a bitwise AND operation between '<NUM>' and '<NUM>' for the egress link. Because the result of the AND operation is '<NUM>,' the intermediate BFR <NUM>, at step <NUM>, may replicate the received message and forward the message to BFER <NUM>, which is associated with the encoded BFR-id '<NUM>. ' A bit string associated with the egress link toward the BFER <NUM> may be '<NUM>. ' Thus, the BFR <NUM> may perform a bitwise AND operation between '<NUM>' and ` <NUM>' for the egress link. Because the result of the AND operation is NULL, the BFR <NUM> may not forward the message to BFER <NUM>. A bit string associated with the egress link toward the BFER <NUM> may be ` <NUM>. ' Thus, the BFR <NUM> may perform a bitwise AND operation between ` <NUM>' and ` <NUM>' for the egress link. Because the result of the AND operation is ` <NUM>,' the BFR <NUM>, at step <NUM>, may replicate the received message and forward the message to BFER <NUM>, which is associated with the encoded BFR-id ` <NUM>. ' Although this disclosure describes delivering a copy of a message for a failure detection to each target network apparatus using a point-to-multipoint packet-forwarding architecture in a particular manner, this disclosure contemplates delivering a copy of a message for a failure detection to each target network apparatus using a point-to-multipoint packet-forwarding architecture in any suitable manner.

In particular embodiments, the second network apparatus <NUM> may receive the first message from the first network apparatus <NUM>. The second network apparatus <NUM> may be one of the plurality of target network apparatuses whose identities are encoded in the destination field in the one or more headers of the first message. In particular embodiments, a value of the label may be associated with the first network apparatus <NUM>. The second network apparatus <NUM> may determine that the one or more headers of the first message comprise a reply-required indication by looking up the value of the label in a label-action mapping table <NUM>. The label-action mapping <NUM> table may comprise one or more actions corresponding to each label. The one or more actions for the value of the label may comprise generating the second message as a reply to the first message and sending the second message through the network. As an example and not by way of limitation, continuing with a prior example, illustrated in <FIG>, the BFER <NUM> receives the message from the BFIR <NUM>. The bmID value associated with the received message is '<NUM>. ' The BFER <NUM> may look-up the bmID value associated with the received message in a label-action mapping table <NUM>. As a result of the look-up, the BFER <NUM> may determine that a reply message to the received message needs to be sent back. Although this disclosure describes determining that the first message comprises a reply-required indication in a particular manner, this disclosure contemplates determining that the first message comprises a reply-required indication in any suitable manner.

In particular embodiments, the second network apparatus <NUM> may identify the first network apparatus <NUM> by looking up the value of the label in the one or more headers of the first message in the label-action mapping table <NUM>. The one or more actions for the value of the label may comprise setting the destination filed in the one or more headers of the reply message with an encoded identify of the first network apparatus. As an example and not by way of limitation, continuing with a prior example, illustrated in <FIG>, the BFER <NUM> may look-up the value of bmID label of the received message in the label-action mapping table <NUM>. The bmID '<NUM>' associated with the BFIR <NUM> may be associated with one or more actions. The one or more actions may comprise an instruction to set the BitString field in the BIER header of the reply message with a bit-encoded BFR-id of the BFIR <NUM> '<NUM>. ' Although this disclosure describes identifying an identity of an initiator for a failure detection process in a particular manner, this disclosure contemplates identifying an identity of an initiator for a failure detection process in any suitable manner.

In particular embodiments, the second network apparatus <NUM> may generate a second message comprising a payload and one or more headers. The one or more actions corresponding to a value of the label in the one or more headers of the first message may comprise: (<NUM>) preparing a payload of the second message by copying the payload of the first message; (<NUM>) encapsulating the payload of the second message with the one or more headers; (<NUM>) setting the source field in the one or more headers of the second message with an identity of the second network apparatus <NUM>; and (<NUM>) setting the destination field in the one or more headers of the second message with an encoded identity of the first network apparatus <NUM>, wherein the encoded identity of the first network apparatus <NUM> is provided in the label-actions mapping table <NUM>. After following the instructions for the one or more actions corresponding to the value of the label in the one or more headers of the first message, the payload of the second message may be identical to the payload of the first message. The destination field in the one or more headers of the second message may be set with an encoded identity of the first network apparatus <NUM>. The encoded identify of the first network apparatus may be determined by looking up the value of the label in the one or more headers of the first message in the label-action mapping table <NUM>. The source field of the one or more headers of the second message may be set with an encoded identity of the second network apparatus <NUM>. As an example and not by way of limitation, continuing with a prior example, illustrated in <FIG>, the BFER <NUM> may create a message as a reply to the received message from the BFIR <NUM> by following instructions for the one or more actions corresponding to the bmID value in the received message. The payload of the reply message may be identical to the payload of the received message. The BitString field in the BIER header may be set with '<NUM>,' an encoded BFR-id of the BFIR <NUM>. The BFIR-id field in the BIER header of the reply message may be set with '<NUM>,' the BFR-id associated with the BFER <NUM>. Although this disclosure describes creating a reply message to a failure detection initiation message in a particular manner, this disclosure contemplates creating a reply message to a failure detection initiation message in any suitable manner.

In particular embodiments, the second network apparatus <NUM> may send the second message through the network. The network may be configured to deliver the second message to the first network apparatus <NUM> using a point-to-multipoint packet-forwarding architecture based on the encoded identity of the first network apparatus. As an example and not by way of limitation, continuing with a prior example, illustrated in <FIG>, the BFER <NUM> may forward the reply message to the intermediate BFR <NUM> based on a forwarding rule. The intermediate BFR <NUM> may perform, for each available egress link, a bitwise AND between the value of BitString field in the BIER header of the reply message '<NUM>' with a bit string associated with the egress link. The intermediate BFR <NUM> may forward a copy of the reply message to the BFIR <NUM>. Although this disclosure describes sending a reply message back to the initiator of the failure detection procedure in a particular manner, this disclosure contemplates sending a reply message back to the initiator of the failure detection procedure in any suitable manner.

In particular embodiments, the one or more processors and the one or more computer-readable non-transitory storage media used for executing the procedures at the second network apparatus <NUM> may belong to one of one or more line cards <NUM> associated with the second network apparatus <NUM>. Since the procedures performed at the second network apparatus <NUM> are just data plane procedures, the procedures may be performed at an Application Specific Integrated Circuit (ASIC) associated with a line card <NUM>. Although this disclosure describes procedures at a destination network apparatus in a particular manner, this disclosure contemplates procedures at a destination network apparatus in any suitable manner.

The first network apparatus <NUM> may receive one or more second messages from one or more of the plurality of target network apparatuses, respectively. Each of the one or more second messages may be generated as a reply to the first message by one of the one or more target network apparatuses. The first message may comprise a payload data with information uniquely identifying the first message. The first network apparatus may determine each of the one or more second messages is a reply to the first message by comparing the payload of the first message with a payload of the second message. As an example and not by way of limitation, continuing with a prior example, the BFIR <NUM> may receive the reply message from the BFER <NUM>. The BFIR <NUM> may determine that the received message is a reply to a message sent by the BFIR <NUM> by comparing S-BFD echo message in the reply message with the S-BFD echo message in the originally sent message. The BFIR <NUM> may determine the received reply message was sent by the BFER <NUM> based on a value of the BFR-id field in the BIER header of the received reply message. The BFIR <NUM> may also receive a reply message from the BFER <NUM>. Although this disclosure describes verifying a received reply message in a particular manner, this disclosure contemplates verifying a received reply message in any suitable manner.

In particular embodiments, the first network apparatus <NUM> may identify which of the plurality of target network apparatuses failed to respond to the first message based on the received one or more second messages when the timer expires. The first network apparatus may determine a target network apparatus among the plurality of target network apparatuses is not active if the target network apparatus has failed to respond for a pre-determined number of consecutive messages. As an example and not by way of limitation, continuing with a prior example, the BFIR <NUM> may have not received a reply from the BFER <NUM> until the timer expires. The BFIR <NUM> may determine that the BFER <NUM> has failed to respond to the message sent by the BFIR <NUM>. In particular embodiments, the BFIR <NUM> may determine that the BFER <NUM> is not active when the BFER <NUM> has failed to respond to a message. In particular embodiments, the BFIR <NUM> may determine that the BFER <NUM> is not active when the BFER <NUM> has failed to respond to three messages in a row, where three is a pre-determined number of messages. Although this disclosure describes determining a destination network apparatus is not active in a particular manner, this disclosure contemplates determining a destination network apparatus is not active in any suitable manner.

In particular embodiments, a pre-determined value for the label in the one or more headers of the first message may provide the reply-required indication. The first network apparatus <NUM> may set the label in the one or more headers of the first message with the pre-determined value, instead of a value corresponding to the first network apparatus <NUM>. As an example and not by way of limitation, BIER_ECHO = '<NUM>' for the bmID label may be associated with the reply-required indication. When preparing an initiation message, the BFIR <NUM> may set the bmID label of the message with a value of BIER_ECHO. Although this disclosure describes a particular manner to provide a reply-required indication, this disclosure contemplates a particular manner to provide a reply-required indication in any suitable manner.

In particular embodiments, the value of the label may be the pre-determined value for the reply-required indication. The second network apparatus <NUM> may determine that the one or more headers of the first message comprise a reply-required indication by determining the value of the label is the pre-determined value for the reply-required indication. The second network apparatus <NUM> may identify the first network apparatus <NUM> based on the one or more headers of the first message. The second network apparatus <NUM> may determine an encoded identity of the first network apparatus <NUM> from a source field in the one or more headers of the first message. In particular embodiments, the second network apparatus <NUM> may perform the following actions upon determining the value of the label is the pre-determined value for the reply-required indication: (<NUM>) preparing a payload of the second message by copying the payload of the first message; (<NUM>) encapsulating the payload of the second message with the one or more headers; (<NUM>) setting the source field in the one or more headers of the second message with an identity of the second network apparatus <NUM>; and (<NUM>) setting the destination field in the one or more headers of the second message with an encoded identity of the first network apparatus <NUM>, wherein the identity of the first network apparatus <NUM> is acquired from a source field in the one or more headers of the first message. As an example and not by way of limitation, the BFER <NUM> may determine that the bmID label of the received message is BIER_ECHO. in particular embodiments, the BFER <NUM> may look-up BIER_ECHO in the label-actions mapping table <NUM>. The BFER <NUM> may prepare a reply message by copying the S-BFD echo message in the payload of the received message. The BFER <NUM> may encapsulate the copied S-BFD echo message by a BIER header. The BFER <NUM> may set the BFIR-id field of the BIER header with '<NUM>,' the BFR-id associated with BFER <NUM>. The BFER <NUM> may set the BitString field of the BIER header with '<NUM>,' a bit string encoded BFR-id of the BFIR <NUM>. The BFR-id of the BFIR <NUM> may be available from the BFIR-id field in the BIER header of the received message from the BFIR <NUM>. Although this disclosure describes preparing a reply message upon receiving an initiation message with a pre-determined reply-required indication in a particular manner, this disclosure contemplates preparing a reply message upon receiving an initiation message with a pre-determined reply-required indication in any suitable manner.

In particular embodiments, the second network apparatus <NUM> may send the second message through the network. The network may be configured to deliver the second message to the first network apparatus <NUM> using a point-to-multipoint packet-forwarding architecture based on the encoded identity of the first network apparatus. Although this disclosure describes sending a reply message back in a particular manner, this disclosure contemplates sending a reply message back in any suitable manner.

<FIG> illustrates an example method <NUM> for initiating a failure detection in a P2MP forwarding network. The method may begin at step <NUM>, where a first network apparatus may identify a plurality of target network apparatuses within a network to which the first network apparatus belongs. At step <NUM>, the first network apparatus may generate a first message comprising one or more headers. The one or more headers may comprise a reply-required indication and encoded identities for the plurality of target network apparatuses. At step <NUM>, the first network apparatus may send the first message through the network. The network may be configured to deliver a copy of the first message to each of the plurality of target network apparatuses using a point-to-multipoint packet-forwarding architecture based on the encoded identities for the plurality of target network apparatuses. At step <NUM>, the first network apparatus may receive one or more second messages from one or more of the plurality of target network apparatuses, respectively. Each of the one or more second messages may be generated as a reply to the first message by one of the one or more target network apparatuses. At step <NUM>, the first network apparatus may determine whether a timer expires. At step <NUM>, the first network apparatus may identify which of the plurality of target network apparatuses failed to respond to the first message based on the received one or more second messages. Particular embodiments may repeat one or more steps of the method of <FIG>, where appropriate. Although this disclosure describes and illustrates particular steps of the method of <FIG> as occurring in a particular order, this disclosure contemplates any suitable steps of the method of <FIG> occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for initiating a failure detection in a P2MP forwarding network including the particular steps of the method of <FIG>, this disclosure contemplates any suitable method for initiating a failure detection in a P2MP forwarding network including any suitable steps, which may include all, some, or none of the steps of the method of <FIG>, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the method of <FIG>, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable steps of the method of <FIG>.

<FIG> illustrates an example method <NUM> for replying to a failure detection initiation message in a P2MP forwarding network. The method may begin at step <NUM>, where a second network apparatus may receive the first message from the first network apparatus. The first message may comprise one or more headers. The one or more headers may comprise encoded identities for a plurality of target network apparatuses in a network. The plurality of target network apparatuses may comprise the second network apparatus. The network may be configured to deliver the first message to the second network apparatus using a point-to-multipoint packet-forwarding architecture based on encoded identity of the second network apparatus in encoded identities. At step <NUM>, the second network apparatus may determine whether the one or more headers of the first message comprise a reply-required indication. At step <NUM>, the second network apparatus may identify the first network apparatus based on the one or more headers of the first message. At <NUM>, the second network apparatus may generate a second message comprising a payload and one or more headers. The payload of the second message may be identical to a payload of the first message. A destination field in the one or more headers of the second message may be set with an encoded identity of the first network apparatus. A source field of the one or more headers of the second message may be set with an encoded identity of the second network apparatus. At step <NUM>, the second network apparatus may send the second message through the network. The network may be configured to deliver the second message to the first network apparatus using a point-to-multipoint packet-forwarding architecture based on the encoded identity of the first network apparatus. Particular embodiments may repeat one or more steps of the method of <FIG>, where appropriate. Although this disclosure describes and illustrates particular steps of the method of <FIG> as occurring in a particular order, this disclosure contemplates any suitable steps of the method of <FIG> occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for replying to a failure detection initiation message in a P2MP forwarding network including the particular steps of the method of <FIG>, this disclosure contemplates any suitable method for replying to a failure detection initiation message in a P2MP forwarding network including any suitable steps, which may include all, some, or none of the steps of the method of <FIG>, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the method of <FIG>, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable steps of the method of <FIG>.

<FIG> illustrates an example computer system <NUM>. In particular embodiments, one or more computer systems <NUM> perform one or more steps of one or more methods described or illustrated herein. In particular embodiments, one or more computer systems <NUM> provide functionality described or illustrated herein. In particular embodiments, software running on one or more computer systems <NUM> performs one or more steps of one or more methods described or illustrated herein or provides functionality described or illustrated herein. Particular embodiments include one or more portions of one or more computer systems <NUM>. Herein, reference to a computer system may encompass a computing device, and vice versa, where appropriate. Moreover, reference to a computer system may encompass one or more computer systems, where appropriate.

In particular embodiments, processor <NUM> includes hardware for executing instructions, such as those making up a computer program. As an example and not by way of limitation, to execute instructions, processor <NUM> may retrieve (or fetch) the instructions from an internal register, an internal cache, memory <NUM>, or storage <NUM>; decode and execute them; and then write one or more results to an internal register, an internal cache, memory <NUM>, or storage <NUM>. In particular embodiments, processor <NUM> may include one or more internal caches for data, instructions, or addresses. This disclosure contemplates processor <NUM> including any suitable number of any suitable internal caches, where appropriate. As an example and not by way of limitation, processor <NUM> may include one or more instruction caches, one or more data caches, and one or more translation lookaside buffers (TLBs). Instructions in the instruction caches may be copies of instructions in memory <NUM> or storage <NUM>, and the instruction caches may speed up retrieval of those instructions by processor <NUM>. Data in the data caches may be copies of data in memory <NUM> or storage <NUM> for instructions executing at processor <NUM> to operate on; the results of previous instructions executed at processor <NUM> for access by subsequent instructions executing at processor <NUM> or for writing to memory <NUM> or storage <NUM>; or other suitable data. The data caches may speed up read or write operations by processor <NUM>. The TLBs may speed up virtualaddress translation for processor <NUM>. In particular embodiments, processor <NUM> may include one or more internal registers for data, instructions, or addresses. This disclosure contemplates processor <NUM> including any suitable number of any suitable internal registers, where appropriate. Where appropriate, processor <NUM> may include one or more arithmetic logic units (ALUs); be a multi-core processor; or include one or more processors <NUM>. Although this disclosure describes and illustrates a particular processor, this disclosure contemplates any suitable processor.

In particular embodiments, memory <NUM> includes main memory for storing instructions for processor <NUM> to execute or data for processor <NUM> to operate on. As an example and not by way of limitation, computer system <NUM> may load instructions from storage <NUM> or another source (such as, for example, another computer system <NUM>) to memory <NUM>. Processor <NUM> may then load the instructions from memory <NUM> to an internal register or internal cache. To execute the instructions, processor <NUM> may retrieve the instructions from the internal register or internal cache and decode them. During or after execution of the instructions, processor <NUM> may write one or more results (which may be intermediate or final results) to the internal register or internal cache. Processor <NUM> may then write one or more of those results to memory <NUM>. In particular embodiments, processor <NUM> executes only instructions in one or more internal registers or internal caches or in memory <NUM> (as opposed to storage <NUM> or elsewhere) and operates only on data in one or more internal registers or internal caches or in memory <NUM> (as opposed to storage <NUM> or elsewhere). One or more memory buses (which may each include an address bus and a data bus) may couple processor <NUM> to memory <NUM>. Bus <NUM> may include one or more memory buses, as described below. In particular embodiments, one or more memory management units (MMUs) reside between processor <NUM> and memory <NUM> and facilitate accesses to memory <NUM> requested by processor <NUM>. In particular embodiments, memory <NUM> includes random access memory (RAM). This RAM may be volatile memory, where appropriate. Where appropriate, this RAM may be dynamic RAM (DRAM) or static RAM (SRAM). Moreover, where appropriate, this RAM may be single-ported or multi-ported RAM. This disclosure contemplates any suitable RAM. Memory <NUM> may include one or more memories <NUM>, where appropriate. Although this disclosure describes and illustrates particular memory, this disclosure contemplates any suitable memory.

In particular embodiments, communication interface <NUM> includes hardware, software, or both providing one or more interfaces for communication (such as, for example, packet-based communication) between computer system <NUM> and one or more other computer systems <NUM> or one or more networks. As an example and not by way of limitation, communication interface <NUM> may include a network interface controller (NIC) or network adapter for communicating with an Ethernet or other wire-based network or a wireless NIC (WNIC) or wireless adapter for communicating with a wireless network, such as a WI-FI network. This disclosure contemplates any suitable network and any suitable communication interface <NUM> for it. As an example and not by way of limitation, computer system <NUM> may communicate with an ad hoc network, a personal area network (PAN), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), or one or more portions of the Internet or a combination of two or more of these. One or more portions of one or more of these networks may be wired or wireless. As an example, computer system <NUM> may communicate with a wireless PAN (WPAN) (such as, for example, a BLUETOOTH WPAN), a WI-FI network, a WI-MAX network, a cellular telephone network (such as, for example, a Global System for Mobile Communications (GSM) network, a Long-Term Evolution (LTE) network, or a <NUM> network), or other suitable wireless network or a combination of two or more of these. Computer system <NUM> may include any suitable communication interface <NUM> for any of these networks, where appropriate. Communication interface <NUM> may include one or more communication interfaces <NUM>, where appropriate. Although this disclosure describes and illustrates a particular communication interface, this disclosure contemplates any suitable communication interface.

As an example and not by way of limitation, bus <NUM> may include an Accelerated Graphics Port (AGP) or other graphics bus, an Enhanced Industry Standard Architecture (EISA) bus, a front-side bus (FSB), a HYPERTRANSPORT (HT) interconnect, an Industry Standard Architecture (ISA) bus, an INFINIBAND interconnect, a lowpin-count (LPC) bus, a memory bus, a Micro Channel Architecture (MCA) bus, a Peripheral Component Interconnect (PCI) bus, a PCI-Express (PCIe) bus, a serial advanced technology attachment (SATA) bus, a Video Electronics Standards Association local (VLB) bus, or another suitable bus or a combination of two or more of these.

In summary, in one embodiment, a method includes identifying a number of target network apparatuses within a network to which a first network apparatus belongs, generating a first message including a reply-required indication and encoded identities for the plurality of target network apparatuses, sending the first message through the network, where the network is configured to deliver a copy of the first message to each of the target network apparatuses using a point-to-multipoint packet-forwarding architecture, receiving one or more second messages from one or more of the target network apparatuses, respectively, where each of the one or more second messages is generated as a reply to the first message by one of the one or more target network apparatuses, and identifying which of the plurality of target network apparatuses failed to respond to the first message based on the received one or more second messages.

Herein, a computer-readable non-transitory storage medium or media may include one or more semiconductor-based or other integrated circuits (ICs) (such, as for example, fieldprogrammable gate arrays (FPGAs) or application-specific ICs (ASICs)), hard disk drives (HDDs), hybrid hard drives (HHDs), optical discs, optical disc drives (ODDs), magneto-optical discs, magneto-optical drives, floppy diskettes, floppy disk drives (FDDs), magnetic tapes, solid-state drives (SSDs), RAM-drives, SECURE DIGITAL cards or drives, any other suitable computer-readable non-transitory storage media, or any suitable combination of two or more of these, where appropriate.

Claim 1:
A first network apparatus, comprising:
one or more processors; and
one or more computer-readable non-transitory storage media coupled to the one or more processors and comprising instructions operable when executed by the one or more processors to cause the first network apparatus to:
identify (<NUM>) a plurality of target network apparatuses within a network to which the first network apparatus belongs;
generate (<NUM>) a first message comprising one or more headers comprising a label, wherein the one or more headers comprise:
a reply-required indication; and
encoded identities for the plurality of target network apparatuses;
send (<NUM>) the first message through the network, wherein the network is configured to deliver a copy of the first message to each of the plurality of target network apparatuses using a point-to-multipoint packet-forwarding architecture based on the encoded identities for the plurality of target network apparatuses, wherein the first message comprises a payload data, and wherein the payload data comprises information that uniquely identifies the first message;
receive (<NUM>) one or more second messages from one or more of the plurality of target network apparatuses, respectively, wherein each of the one or more second messages is generated as a reply to the first message by one of the one or more target network apparatuses;
determine that each of the one of more second messages is a reply to the first message by comparing the payload of the first message with a payload of the second message; and
identify (<NUM>), based on the received one or more second messages, which of the plurality of target network apparatuses failed to respond to the first message.