Root node shutdown messaging for multipoint-to-multipoint transport tree

[0001] The present disclosure generally relates to implementing root node redundancy for multipoint-to-multipoint network label switched paths within multipoint-to-multipoint transport trees.

[0002] The Internet Engineering Task Force (IETF) Request for Comments (RFC) 3031 specifies a multiprotocol label switching (MPLS) architecture. The MPLS architecture in RFC 3031 permits packets entering a network to be assigned by an ingress router to a prescribed “Forwarding Equivalence Class” (FEC): once a packet has been assigned to a specific FEC (identifiable by a “label” added to the packet), the packet can be forwarded with its corresponding assigned label to a next hop label switching router (LSR). The next hop LSR can use the label supplied with the packet as an index to locate a forwarding table entry that specifies the next hop, and a new label used by the corresponding next hop LSR for the corresponding FEC and which replaces the label in the received packet. Hence, the next hop LSR replaces the label in the received packet with its new label, and forwards the packet on the next hop specified in the table, resulting in forwarding the packet via a label switched path (LSP) without the necessity of executing other routing algorithms based on parsing the network layer protocol header (e.g., the Internet Protocol (IP) header). RFC 3036 specifies a label distribution protocol (LDP) that enables label switching routers to exchange label bindings, enabling the label switching routers to map network-layer routing information directly to data-link layer switched paths.

[0003] The Internet Draft by Minei et al., “Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths,” draft-ietf-mpls-1dp-p2mp-02, June 2006, describes extensions to the label distribution protocol specified in RFC 3036 for establishing multipoint-to-multipoint LSPs between label switching routers having established a tree topology with a single root and one or more leaf nodes, where the leaf nodes can operate as ingress nodes for inserting traffic into a network, and/or egress nodes for outputting traffic from the network, without requiring use of any multicast routing protocol within the network. In contrast, a point-to-multipoint LSP has one ingress label switching router and one or more egress label switching routers, and a multipoint-to-point LSP has one or more ingress label switching routers and one unique egress label switching router.

[0009] In one embodiment, a method comprises registering, by a first label switching router having been identified as a root of a prescribed transport tree for transport of a prescribed group of data packets, at least two next hop label switching routers as belonging to the prescribed transport tree based on receiving respective label mapping messages, each label mapping message specifying a prescribed identifier of the prescribed transport tree, and a corresponding label used by the corresponding next hop label switching router for identifying the data packets assigned to the prescribed transport tree; detecting by the first label switching router a prescribed condition indicating the first label switching router is to be removed from service as the root of the prescribed transport tree; and outputting, by the first label switching router, label distribution protocol messages for the prescribed transport tree to each of the next hop label switching routers determined as belonging to the prescribed transport tree, each label distribution protocol message indicating the first label switching router is to be removed from the service as the root of the prescribed transport tree, enabling the label switching routers within the prescribed transport tree to join an alternate root node of a corresponding alternate transport tree, for transport of the data packets via the alternate transport tree.

[0010] In another embodiment, a method comprises registering, by a first label switching router in a prescribed transport tree for transport of a prescribed group of data packets, with an identified root of the transport tree based on outputting, to a next hop label switching router providing reachability to the identified root, a label mapping message specifying a prescribed identifier of the transport tree and a corresponding label used by the first label switching router in identifying the data packets assigned to the prescribed transport tree; receiving from the next hop label switching router a label distribution message indicating that the identified root of the transport tree is to be removed from service; and selecting a second identified root of a second prescribed transport tree, prior to the identified root of the transport tree being removed from service, for transport of the prescribed group of data packets via the second prescribed transport tree.

[0011] In yet another embodiment, a method comprises receiving, by a first label switching router, a first label mapping message from at least one downstream next-hop label switching router, the label mapping message specifying a prescribed identifier of a prescribed transport tree having a prescribed root and configured for transport of a prescribed group of data packets, the label mapping message further specifying a first label used by the corresponding downstream next-hop label switching router for identifying the data packets assigned to the prescribed transport tree; registering, by the first label switching router, the downstream next-hop label switching router as belonging to the prescribed transport tree based on adding a link identifier for reaching the downstream label switching router, and the corresponding first label, to a forwarding table entry specifying a second label used by the first label switching router in identifying the data packets assigned to the prescribed transport tree; registering, by the first label switching router, with the prescribed root of the prescribed transport tree based on outputting, to an upstream next-hop label switching router providing reachability to the prescribed root, a second label mapping message specifying the prescribed identifier of the prescribed transport tree and the second label; receiving, by the first label switching router, from the upstream next-hop label switching router a label distribution message indicating that the prescribed root of the prescribed transport tree is to be removed from service; and outputting, by the first label switching router, to each downstream next-hop label switching router belonging to the prescribed transport tree, an updated label distribution message indicating that the prescribed root of the prescribed transport tree is to be removed from service, enabling each downstream next-hop label switching router to join an alternate root node of a corresponding alternate transport tree, for transport of the data packets via the alternate transport tree.

[0012] Particular embodiments enable a root node of a multipoint-to-multipoint transport tree to send label distribution protocol messages for its multipoint-to-multipoint transport tree, in order to notify the label switching routers within the transport tree that an alternate root node for an alternate transport tree needs to be selected. In particular, the particular embodiments expand upon the use of root node redundancy as described in commonly-assigned, copending application Ser. No. 11/346,411, filed Feb. 2, 2006 by Wijnands et al., entitled “Root Node Redundancy for Multipoint-to-Multipoint Transport Trees”.

[0013] The particular embodiments disclosed herein enable the root node to output label distribution protocol messages indicating that the root node is to be removed from service as the root of the prescribed multipoint-to-multipoint transport tree, also referred to as root shutdown messages, as identified by the corresponding transport tree identifier (e.g., the FEC element). Further, the root node outputs the root shutdown messages preferably with sufficient time to enable the leaf nodes in the transport tree to select the alternate redundant root node having its redundant transport tree for transport of the same prescribed group of data packets as classified with the original Forwarding Equivalence Class.

[0014] Hence, the particular embodiments can enable a root node to proactively cause its leaf nodes to select the alternate root node, prior to the root node being removed from service (e.g., due to maintenance, etc.), ensuring that there is no loss of any data packets that normally would occur if the leaf nodes needed to transfer to the alternate root node upon detection of a failed condition in the root node.

[0015] FIGS. 1 and 2 illustrate example multipoint-to-multipoint transport trees 10 and 10′ composed of label switching routers (LSRs) that can be implemented as either root nodes 12 and 12′, intermediate nodes 14, or leaf nodes 16. The transport trees 10 and 10′ each can implement a multiprotocol label switching architecture, for example according to RFC 3031, for the transport of data packets assigned to a given forwarding equivalence class (FEC). Each of the transport trees 10 and 10′ can be established according to existing Label Distribution Protocol (LDP) protocols, based on the exchange of label mapping messages 18 (e.g., downstream label mapping messages 18a and/or upstream label mapping messages 18b) described below. Each of the transport trees 10 and 10′ also are configured for transporting the same class of data packets for the corresponding FEC using label switched paths 42 and 46, described below (the dashed lines in FIGS. 1 and 2 indicate data links not in use by the corresponding transport tree 10 or 10′). Hence, the root nodes 12 and 12′ provide root node redundancy for the transport of data packets via the network 20 between ingress and egress points 22 (e.g., access routers (AR)). The term “upstream” refers to ingress traffic from a leaf node 16 and destined toward the root node 12, and nodes that are relatively closer to the root node 12. The term “downstream” refers to traffic forwarded from a root node 12 and destined toward a leaf node 16, and nodes that are relatively further from the root node 12.

[0016] Each root node 12 and 12′ can be configured for detecting a prescribed condition indicating that the root node is to be removed from service as the corresponding root, for example based on detecting initiation of a prescribed shutdown procedure within its operating system, or based on detecting another software or hardware-based attribute indicating that operations are to be at least temporarily suspended. Hence, each root node 12 and 12′ can be configured for responding to the detected condition indicating removal from service by outputting to the each of the label switching routers 14 or 16 a root shutdown message 24 indicating to the label switching routers 14 or 16 that the alternate root node should be selected for continued transport of the data packets via the alternate transport tree that satisfy the condition of the prescribed FEC.

[0017] FIG. 3 illustrates example messages exchanged between the leaf node 16, an intermediate node 14, and a root node 12 in establishing the prescribed transport tree, and initiating root node shutdown based on processing of root shutdown messages, according to an example embodiment. Each root node 12 (including the corresponding redundant root node 12′), intermediate node 14, and leaf node 16 includes a network interface circuit 26, a memory circuit 28, and a processing circuit 30. As illustrated in FIG. 3, the processing circuits 30 also can be configured based on operations as a root node 12, an intermediate node 14, and/or a leaf node 16; hence, the processing circuits 30 also can be described as a management circuit in the root node 12, a registration circuit in the intermediate node 14, and a label distribution circuit 30 in the leaf node 16.

[0018] Any of the disclosed circuits of the label switching routers 12, 14, or 16 (including the network interface circuit 26, the memory circuit 28, the processor circuit 30, and their associated components) can be implemented in multiple forms. Example implementations of the disclosed circuits include hardware logic that is implemented in a logic array such as a programmable logic array (PLA), a field programmable gate array (FPGA), or by mask programming of integrated circuits such as an application-specific integrated circuit (ASIC). Any of these circuits also can be implemented using a software-based executable resource that is executed by a corresponding internal processor such as a microprocessor circuit (not shown), where execution of executable code stored in an internal memory circuit (e.g., within the memory circuit 28) causes the processor circuit to store application state variables in processor memory, creating an executable application resource (e.g., an application instance) that performs the operations of the circuit as described herein. Hence, use of the term “circuit” in this specification refers to both a hardware-based circuit that includes logic for performing the described operations, or a software-based circuit that includes a reserved portion of processor memory for storage of application state data and application variables that are modified by execution of the executable code by a processor. The memory circuit 28 can be implemented, for example, using a non-volatile memory such as a programmable read only memory (PROM) or an EPROM, and/or a volatile memory such as a DRAM, etc.

[0019] Further, any reference to “outputting a message” or “outputting a packet” can be implemented based on creating the message/packet in the form of a data structure and storing that data structure in a tangible memory medium in the disclosed apparatus (e.g., in a transmit buffer). Any reference to “outputting a message” or “outputting a packet” also can include electrically transmitting (e.g., via wired electric current or wireless electric field, as appropriate) the message/packet stored in the tangible memory medium to another network node via a communications medium (e.g., a wired or wireless link, as appropriate) (optical transmission also can be used, as appropriate). Similarly, any reference to “receiving a message” or “receiving a packet” can be implemented based on the disclosed apparatus detecting the electrical (or optical) transmission of the message/packet on the communications medium, and storing the detected transmission as a data structure in a tangible memory medium in the disclosed apparatus (e.g., in a receive buffer).

[0020] FIGS. 4A and 4B illustrate an example method by the label switching routers of FIGS. 1-3, according to an example embodiment. The steps described in FIGS. 4A and 4B can be implemented as executable code stored on a computer readable medium (e.g., floppy disk, hard disk, ROM, EEPROM, CD-ROM, etc.) that are completed based on execution of the code by a processor; the steps described herein also can be implemented as executable logic that is encoded in one or more tangible media for execution (e.g., programmable logic arrays or devices, field programmable gate arrays, programmable array logic, application specific integrated circuits, etc.).

[0021] Each of the multipoint-to-multi-point transport trees 10 and 10′ are formed based on the label distribution circuit 30 in each of the leaf nodes (e.g., “D”) 16 registering in the corresponding transport tree (e.g., 10) by generating and the corresponding network interface circuit 26 outputting and outputting in step 100 a downstream label mapping message 18a to its corresponding upstream next-hop router (e.g., “B”) 14. The corresponding upstream next-hop router (e.g., “B”) 14 can provide reachability for the leaf node (e.g., “D”) 16 to the identified root (e.g., “A”) 12. Each of the label switching routers can discover each other using prescribed discovery protocols, for example Open Shortest Path First (OSPF) or Interior Gateway Protocol (IGP). As illustrated in FIG. 3, each downstream label mapping message (e.g., 18a) generated by the label distribution circuit 30 specifies a prescribed identifier (“A1”) 32 of the prescribed transport tree (i.e., FEC identifier) (e.g., 10), and a corresponding label 34 that is used by the label switching router 16 outputting the corresponding label mapping message (e.g., “DA1”) in identifying the downstream data packets assigned to the prescribed transport tree (e.g., 10).

[0022] The registration circuit 30 in the upstream next-hop router (e.g., an intermediate node 14 or a root node 12), for example the intermediate node “B” 14 of FIGS. 1 and 3, in response to the network interface circuit 26 receiving the downstream label mapping message 18a, registers in step 102 the downstream next-hop label switching router, illustrated in FIGS. 1 and 3 as the leaf node (e.g., “D”) 16, based on creating (or updating) a downstream forwarding table entry 36 that specifies the label 34 used by the corresponding downstream next-hop label switching router 16, a link identifier (e.g., “11”) 38 used by the intermediate label switching router “B” 14 for reaching the downstream label switching router (e.g., “D”) 16, and a corresponding downstream label (e.g., “BA1”) 40 created the upstream next-hop router “B” 14 for identifying any downstream data packets from the next-hop upstream node (e.g., root node 12) assigned to the transport tree (e.g. 10). Hence, the downstream forwarding table entry 36 enables the intermediate node “B” 14 to establish a downstream label switched path (LSP) 42 for sending data packets belonging to the corresponding FEC to the leaf node “D” 16.

[0023] The registration circuit 30 of the intermediate label switching router (e.g., “B”) 14 also responds to the received downstream label mapping message 18a by generating in step 104, for output to the leaf node “D” via the network interface circuit 26 an upstream label mapping message 18b. The upstream label mapping message 18b specifies the corresponding tree identifier (“A1”) 32 and a corresponding upstream label (e.g., “BA2”) 44 to be used by the leaf node “D” 16 in sending data packets upstream toward the root 12 using the upstream LSP 46 established by the upstream label mapping message 18b. The intermediate label switching router (e.g., “B”) 14 also creates in step 104 upstream forwarding table entries 48, described below.

[0024] Hence, the leaf node 16 is able to forward ingress packets into the transport tree 10 based on creating in step 106 the upstream forwarding table entry 48 based on receiving the upstream label mapping message 18b. The leaf node 16 also is able to forward packets received via the downstream LSP as egress packets to the corresponding access router (AR) based on the corresponding downstream forwarding table entry 36 established by the corresponding processing circuit 30 during transmission of the downstream label mapping message 18a.

[0025] The intermediate node “B” 14 also registers with the prescribed root (“A”) 12 of the corresponding tree (e.g., 10′) by outputting via its corresponding network interface circuit 26 a corresponding downstream label mapping message 18a′ to its upstream next-hop label switching router, namely the root node “A” 12 in step 108. As illustrated in FIG. 3, the label mapping message 18a′ specifies the tree identifier 32, and the corresponding label 40 used by the intermediate node “B” 14 for identifying downstream packets belonging to the FEC and that are transported via the transport tree 10. In response, the management circuit 30 in the root node 12 adds in step 110 a forwarding table entry 50 that registers the intermediate node “B” 14 for downstream data packets that are assigned to the transport tree 10. As illustrated in FIG. 3, the memory circuit 28 of the root node 12 includes multiple downstream forwarding table entries based on multiple next hop label switching routers (e.g., “C”, “G”, and “H”) also registering with the root node 12 based on sending similar downstream label mapping messages 18a to the root node 12.

[0026] The management circuit 30 of the root node 12 also generates, for each received downstream label mapping message 18a, a corresponding upstream label mapping message 18b′ in step 112 to the corresponding next-hop downstream LSR. The upstream label mapping message 18′ specifies the tree identifier 32 for the corresponding FEC, and a corresponding upstream label 52 to be used by the corresponding next-hop downstream node (e.g., “B”) 14 in sending messages upstream to the root node 12. As illustrated in FIG. 3, the root node 12 can generate multiple forwarding table entries that identify, for a given upstream label 52 assigned to a corresponding next-hop downstream label switching router, the downstream labels 40 that should be used for forwarding received data packets to the next hop destinations for implementation of the multipoint-to-multipoint tree 10, and the respective interface identifiers within the corresponding network interface circuit 26.

[0027] The intermediate node (e.g., “B”), in response to receiving the upstream label mapping message 18b′, updates in step 114 its upstream forwarding table entry 48 in order to enable forwarding of upstream packets to the root node 12, as well as any other downstream nodes that may have registered with the intermediate node “B” (e.g., the LSR “E” having registered using the label map “EA1”).

[0028] Hence, each of the label switching routers 12, 14 and 16 are able to distribute data packets assigned to the FEC via the multipoint-to-multipoint transport tree 10. As apparent from the foregoing, the above steps described in FIG. 4A can be repeated by each of the label switching routers for the redundant root node 12′ in establishing the alternate transport tree 10′. Hence, each of the label switching routers 14 and 16 can have concurrent registrations with the root nodes 12 and 12′ of the respective transport trees 10 and 10′.

[0029] Referring to FIG. 4B, assume that the management circuit 30 of the root node 12 detects in step 120 a prescribed condition indicating that the root node 12 is to be removed from service as the root node of the corresponding transport tree 10. For example, the management circuit 30 can detect that the label switching router is to be removed from service based on an administrator request from a network manager to halt service for the specific FEC serviced by the transport tree 10, a detected shutdown of the associated operating system executed by the management circuit 30, etc.

[0030] In response to detecting the prescribed condition indicating the label switching router is to be removed from service as a root 12 of the corresponding transport tree 10, the management circuit 30 can generate and output via the corresponding network interface circuit 26 in step 122 a shutdown message 24 for the specific FEC in the form of a label distribution protocol (LDP) message. The shutdown message 24 can specify for example the network address 54 of the root node 12, a shutdown command 60, and the corresponding label 40 used by the downstream next-hop label switching router (e.g., “B”); alternately, the shutdown message 24 also can specify the tree identifier 32. Alternately, in response to detecting a generic shutdown that all FECs administered by the root 12 are to be shut down, the management circuit 30 can output via the corresponding network interface circuit 26 in step 124 a generic shutdown message 62, illustrated in FIG. 3, which can specify the address 54 of the root node 12, and a generic shutdown command 64.

[0031] Each of the next hop downstream label switching routers (e.g., the intermediate nodes “B”, “C” 14 and the root nodes “G” and “H”), in response to receiving either the shutdown message 60 or 62 via its corresponding network interface circuit 26, can update their respective tables to indicate that the root node 12 in the corresponding transport tree 10 is to be removed from service. For example, the registration circuit 30 of the intermediate node “B” 14 can update in step 126 its upstream forwarding tables 48 and a transport tree status field 56 to specify that the root node 12 for the corresponding transport tree 10 is no longer available for service; the registration circuit 30 of the intermediate node “B” also can set an internal flag indicating the corresponding tree identifier 32 is unusable. The registration circuit 30 of the intermediate node also outputs in step 128 updated LDP shutdown messages 24 or 62 to the associated downstream label switching routers (e.g., the leaf node “D” 16), to indicate that the root 12 of the corresponding transport tree 10 is to be removed from service. Hence, the label distribution circuit 30 in each leaf node 16 can respond in step 130 to the received LDP shutdown message 24 or 62 received via its corresponding network interface circuit 26 by noting that the corresponding FEC (identified by the corresponding tree identifier 32) is unusable by updating its corresponding transport tree status field 56, and by selecting the alternate root node 12′ of the alternate transport tree 10′, in order to begin forwarding packets via the alternate transport tree 10′.

[0032] Hence, each of the label switching routers in the network 20 can mark that the root node 12 of the corresponding transport tree 10 is unavailable for service in their respective transport tree status fields 56, causing all of the label switching routers in the network 22 stop using the transport tree 10, and begin using the alternate transport tree 10′ having the alternate root node 12′, before the root node 12 is actually removed from service. Hence, each of the label switching routers in the network 20 can switch over to the alternate transport tree 10′ for the prior transport tree 10 is removed from service, ensuring that there is no packet loss.

[0033] Assume now in step 132 of FIG. 4B that the root node 12 of the transport tree 10 is able to resume service, for example following completion of the service, or for example in the case where the shutdown of the root 12 was not necessary. In this case, instead of relying upon existing routing protocols, the management circuit 30 can output in step 132 via its corresponding network interface circuit 26 an LDP reactivate message 70 via the existing links with the next hop label switching routers. The reactivate message 70 can specify that the root node 12 is reactivated for service as the root of the corresponding transport tree 10. Each of the next hop label switching routers respond in step 134 to the reactivate message 70 received via its corresponding network interface circuit 26 by updating their internal tables, and outputting updated LDP reactivate messages to the respective downstream next-hop label switching routers according to the transport tree 10. Hence, each of the leaf nodes 16 can rejoin in step 136 the original transport tree 10 serving the corresponding FEC, based on the received reactivate message 70 received via its corresponding network interface circuit 26.

[0034] According to the example embodiments, a root node of a multipoint-to-multipoint transport tree can notify leaf nodes that the root node will be shutdown from service, enabling the leaf nodes to join an alternate root node of an alternate transport tree for continued transport of data packets via the alternate transport tree, without any packet loss.

[0035] While the example embodiments in the present disclosure have been described in connection with what is presently considered to be the best mode for carrying out the subject matter specified in the appended claims, it is to be understood that the example embodiments are only illustrative, and are not to restrict the subject matter specified in the appended claims.