Method enabling fast switching between multicast trees

Presented are a system and method of detecting a multicast tree link failure and performing a fast switch from the failed multicast tree communication path to a secondary multicast tree communication path. The methods are suitable for leaf nodes in a multiprotocol label switching network. The method generates a count of communication path failure detection packets and a count of communication path failure detection packets plus other packets and compares the counts to determine the status of the link. The system includes two counter components and a comparison component.

TECHNICAL FIELD

The present invention relates generally to a Multiprotocol Label Switching (MPLS) mechanism of communications over a multicast tree and more specifically to performing fast switching between different multicast trees.

BACKGROUND

With market pressure driving ever expanding service offerings, telecommunication operators are offering a service combination known as Triple-Play services. Triple-Play services combine high-speed internet access, television programming and voice over internet protocol (VOIP) communications. In an effort to reliably provide these services, telecommunication operators have implemented multiprotocol label switching (MPLS) multicast trees to deliver the services to the end users.FIG. 1illustrates a prior art MPLS network102connected to an internet protocol (IP) core network104, providing the media source, and a digital line subscriber access multiplexer (DSLAM)106. The MPLS network includes root nodes108(connected to routers114on the IP network), leaf nodes110(connected to a DSLAM), and routers112connecting the MPLS root nodes108to the MPLS leaf nodes110.

Typically, telecommunication providers employ over-provisioning techniques for redundancy by delivering the same content, from multiple root nodes, over several multicast trees to a set of routers/switches, the leaf nodes, positioned at the edge of the MPLS network. Under normal operating conditions, the router/switch leaf nodes receive the communications from a primary tree with another tree acting as a secondary or backup communication path. If the primary tree fails, then the secondary tree can step in and deliver the content from a root node to the leaf nodes.

Detecting a primary tree failure is typically accomplished with a Bidirectional Forward Detection (BFD) mechanism to reduce the time required for detection. In a typical prior art embodiment, a BFD transmitter is installed on the root node of each multicast tree and the BFD packets are replicated to each of the leaf nodes of the multicast tree. In this embodiment, each leaf node detects the failure of a path, or the source, by monitoring the arrival of the incoming BFD connectivity detection packets.

The existing BFD solutions to detecting a tree failure have two drawbacks related to failures upstream of the root node. In the case of the first failure, a failure between the MPLS network and Internet Protocol (IP) network, a leaf node cannot detect the failure because the BFD mechanism is still operational. Consequently, the failure must be detected by MPLS signaling mechanism such as Targeted Label Distribution Protocol (T-LDP) or static Pseudowires (PW) status signaling. Implementing these additional MPLS signaling mechanisms increases both the development and the maintenance costs for a system capable of delivering real-time content with acceptable levels of recovery.

In the case of the second and more damaging failure, a failure in the IP core network, the detection of the communications failure and the subsequent recovery from the failure will rely on IP resiliency. The issue associated with this type of recovery mechanism is the time required for the IP resiliency mechanism to detect the failure and respond. This longstanding mechanism cannot meet the fast service recovery time of less than fifty milliseconds as required by the services provided in a “Triple-Play” package.

Accordingly, market pressure is building for a method and system capable of providing a deterministic communication failure detection and recovery in an MPLS system of less than fifty milliseconds. It is desirable that the method and system not require any signaling facilities associated with the MPLS network.

SUMMARY

According to one exemplary embodiment, a method for switching a communication path between multicast trees generates a first count, during a predefined interval, of the communication path failure detection packets arriving at a leaf node. In another aspect of the exemplary embodiment, the method generates a second count, during the predefined interval, of the communication path failure detection packets and other packets arriving at the leaf node. In another aspect of the exemplary embodiment, the method compares the first count to the second count and if the second count is within a predefined value of the first count then the method acts to switch the communication path to a secondary multicast tree.

In another exemplary embodiment, a node on a network minimizes the time required to detect the loss of communication on a multicast tree. The node includes a processor, memory and computer instructions stored in the memory for a first counter component for counting the arrival of communication path failure detection packets at the node over a predefined interval, a second counter component for counting the arrival of the communication path failure detection packets and other packets arriving at the node over the predefined interval and a comparison component for comparing a first count associated with the first counter component with a second count associated with the second counter component and sending a request to switch to a second multicast tree when the difference between the first count and the second count is a predefined value.

In another exemplary embodiment, a system for protecting a communication path from a root node to a leaf node in a multiprotocol label switching (MPLS) network is described. The system includes a plurality of MPLS root nodes connected to a plurality of routers associated with another network, a plurality of MPLS leaf nodes connected to a plurality of DSLAMS with each leaf node further comprising a processor for executing computer instructions and a memory for storing computer instructions with the computer instructions further comprising a first counter component for counting the arrival of communication path failure detection packets at the node over a predefined interval, a second counter component for counting the arrival of the communication path failure detection packets and other packets arriving at the node over the predefined interval and a comparison component for comparing a first count associated with the first counter component with a second count associated with the second counter component and sending a request to switch to a second multicast tree when the difference between the first count and the second count are within a predefined range, and a plurality of MPLS routers connecting the plurality of leaf nodes to the plurality of root nodes.

DETAILED DESCRIPTION

Looking first toFIG. 2, a diagram200of an exemplary embodiment of a system for determining the status of a multicast tree and switching to a different multicast tree communication path if the status indicates a problem with the current multicast tree communication path is illustrated. The exemplary embodiment includes a leaf node202of a multiprotocol label switching (MPLS) network, a comparator/selector204, a failover object206, a counter object208,210including a bi-directional forward detection (BFD) detector212and a multicast tree packet counter214. It should be noted that each leaf node on the MPLS network can contain the aforementioned components and operate independently of all other leaf nodes and root nodes of the MPLS network with respect to determining when a multicast tree communication path switch should occur.

Next in the exemplary embodiment, after a predefined interval, a count of the number of BFD packets received by the BFD detector212is compared to a count of the number of other packets (including the BFD packets) received by the multicast tree packet counter214and if the two counts are equal then a determination is made that the current multicast tree communication path is experiencing a source failure and a transition to a backup multicast tree communication path is performed. It should be noted in the exemplary embodiment that the multicast tree packet counter214can include all packets received on the multicast tree communication path or a subset of packets received as long as the subset includes the BFD packets and some other set of packets. It should further be noted that the subset of packets can be identified by a demultiplexer such as internal LSP label, PW or VLAN ID. It should further be noted that the predefined interval can include, but is not limited to, a time based interval or a packet based interval such as the interval between two or more BFD packets. It should also be noted that performing the transition to another multicast tree communication path can include but is not limited to sending a request to the protection control logic to switch to the secondary multicast tree communication path for this particular leaf node.

Looking now toFIG. 3and another exemplary embodiment300, is a network node302for providing a fast detection of the failure of a multicast tree communication path and the switch to a secondary multicast tree communication path. The exemplary embodiment network node302includes a processor component304, a memory component306, a comparison component308, a first counter component310and a second counter component312. It should be noted in the exemplary embodiment, that a fast multicast tree communication path failure detection and changeover, as provided by this exemplary embodiment, should be less than fifty milliseconds. It should further be noted that one of the counters, first counter component310for example, is counting only communication path failure detection packets, including but not limited to BFD packets, while the other counter, second counter component312for example, is counting both the BFD packets and other packets arriving on the multicast tree communication path. It should also be noted that a network node can be a leaf node and that each leaf node can contain the aforementioned components and operate independently of all other leaf nodes with regard to monitoring a multicast tree communication path and determining when a multicast tree communication path has failed.

In another aspect of the exemplary embodiment, on a predefined interval a comparison component308can obtain the values from first counter component310and second counter component312and analyze the counter values to determine if the current multicast tree communication path has failed. It should be noted in the exemplary embodiment that the predefined interval can be time based or event based. It should also be noted in the exemplary embodiment that an event based predefined interval can be the arrival of two (or more) consecutive communication path failure detection packets. Next in the exemplary embodiment, the comparison component308analyzes the counters by comparing them to determine if any packets other than the communication path failure detection packets have arrived. If the exemplary comparison component308determines that the only packets arriving are communication path failure detection packets then the comparison component308acts to change the multicast tree communication path to the secondary multicast tree communication path.

Further,FIG. 3illustrates an example of a suitable computing system environment300in which the claimed subject matter can be implemented, although as made clear above, the computing system environment300is only one example of a suitable computing environment for an exemplary embodiment and is not intended to suggest any limitation as to the scope of use or functionality of the claimed subject matter. Further, the computing environment300is not intended to suggest any dependency or requirement relating to the claimed subject matter and any one or combination of components illustrated in the example computing environment300.

Looking again toFIG. 3, an example of a device for implementing the previously described innovation includes a general purpose computing device in the form of a computer302. Components of computer302can include, but are not limited to, a processing unit304, a system memory306, and a system bus322that couples various system components including the system memory to the processing unit304. The system bus322can be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures.

The system memory306can include computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) and/or random access memory (RAM). A basic input/output system (BIOS), containing the basic routines that help to transfer information between elements within computer302, such as during start-up, can be stored in memory306. Memory306can also contain data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit304. By way of non-limiting example, memory306can also include an operating system, application programs, other program modules, and program data.

The computer302can also include other removable/non-removable and volatile/nonvolatile computer storage media. For example, computer302can include a hard disk drive that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive that reads from or writes to a removable, nonvolatile magnetic disk, and/or an optical disk drive that reads from or writes to a removable, nonvolatile optical disk, such as a CD-ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM and the like. A hard disk drive can be connected to the system bus322through a non-removable memory interface such as an interface, and a magnetic disk drive or optical disk drive can be connected to the system bus322by a removable memory interface, such as an interface.

A user can enter commands and information into the computer302through input devices such as a keyboard or a pointing device such as a mouse, trackball, touch pad, and/or other pointing device. Other input devices can include a microphone, joystick, game pad, satellite dish, scanner, or similar devices. These and/or other input devices can be connected to the processing unit304through user input314and associated interface(s) that are coupled to the system bus322, but can be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB).

A graphics subsystem can also be connected to the system bus322. In addition, a monitor or other type of display device can be connected to the system bus322through an interface, such as output interface316, which can in turn communicate with video memory. In addition to a monitor, computers can also include other peripheral output devices, such as speakers and/or printing devices, which can also be connected through output interface316.

The processing unit304can comprise a plurality of processing cores providing greater computational power and parallel computing capabilities. Further, the computing environment300can contain a plurality of processing units providing greater computational power and parallel computing capabilities. It should be noted that the computing environment300can also be a combination of multi-processor and multi-core processor capabilities.

The computer302can operate in a networked or distributed environment using logical connections to one or more other remote computers, such as remote server320, which can in turn have media capabilities different from device302. The remote server320can be a personal computer, a server, a router, a network PC, a peer device or other common network node, and/or any other remote media consumption or transmission device, and can include any or all of the elements described above relative to the computer302. The logical connections depicted inFIG. 3include a network324, such as a local area network (LAN) or a wide area network (WAN), but can also include other networks/buses.

When used in a LAN networking environment, the computer302is connected to the LAN324through a network interface318or adapter. When used in a WAN networking environment, the computer302can include a communications component, such as a modem, or other means for establishing communications over a WAN, such as the Internet. A communications component, such as a modem, which can be internal or external, can be connected to the system bus322through the user input interface at input314and/or other appropriate mechanism.

In a networked environment, program modules depicted relative to the computer302, or portions thereof, can be stored in a remote memory storage device. It should be noted that the network connections shown and described are exemplary and other means of establishing a communications link between the computers can be used.

Turning now toFIG. 4, an exemplary method embodiment400based on performing a fast switch between multicast tree communication paths when a communication path failure is detected is depicted. Starting at exemplary method embodiment step402, a first count is generated, during a predefined interval, of communication path failure detection packets arriving at a leaf node. It should be noted in the exemplary embodiment that the predefined interval can be the arrival of two (or more) consecutive communication path failure packets. Further in the exemplary embodiment, it should be noted that a predefined time interval can be adopted.

Continuing at step404of the exemplary embodiment, a second count is generated, during the predefined interval, of communication path failure detection packets and other packets arriving at the leaf node. It should be noted in the exemplary embodiment that the other packets can include all arriving packets or a subset of arriving packets in addition to the communication path failure detection packets.

Next at step406of the exemplary embodiment, the first count is compared to the second count and if the second count is within a predefined difference of the first count then an action is taken to switch from the current multicast tree communication path to a secondary multicast tree communication path. It should be noted that the predefined difference can be zero, i.e., the first count and the second count are equal.

Additionally, it should be noted that as used in this application, terms such as “component,” “display,” “interface,” and other similar terms are intended to refer to a computing device, either hardware, a combination of hardware and software, software, or software in execution as applied to a computing device implementing a virtual keyboard. For example, a component may be, but is not limited to being, a process running on a processor, a processor, an object, an executable, a thread of execution, a program and a computing device. As an example, both an application running on a computing device and the computing device can be components. One or more components can reside within a process and/or thread of execution and a component can be localized on one computing device and/or distributed between two or more computing devices, and/or communicatively connected modules. Further, it should be noted that as used in this application, terms such as “system user,” “user,” and similar terms are intended to refer to the person operating the computing device referenced above.

The above-described exemplary embodiments are intended to be illustrative in all respects, rather than restrictive, of the present innovation. Thus the present innovation is capable of many variations in detailed implementation that can be derived from the description contained herein by a person skilled in the art. All such variations and modifications are considered to be within the scope and spirit of the present innovation as defined by the following claims. No element, act, or instruction used in the description of the present application should be construed as critical or essential to the invention unless explicitly described as such. Also, as used herein, the article “a” is intended to include one or more items.