Techniques for reliable switchover to a date multicast distribution tree (MDT)

Techniques reliably provide the switchover from a default MDT to the data MDT by using reliable signaling and reliable building of a data MDT. The message notifying of the pending switchover to the data MDT is reliably sent using signaling that is reliable. Also, the switchover from the default MDT to the data MDT does not happen until all egress routers have responded to the message. Egress routers join the data MDT if associated receivers are interested in receiving the multicast stream from a source. The router does not send another response upstream until all egress routers downstream from it respond to the message in the positive or the negative.

BACKGROUND OF THE INVENTION

Embodiments of the present invention generally relate to networking and more specifically to techniques for reliably switching from a default multicast distribution tree (MDT) to a data MDT for a multicast stream.

A default MDT is a point-to-multipoint tunnel between provider edge (PE) routers. The default MDT may be used in virtual private network (VPN) to provide multicast traffic to receivers. All PE routers for the VPN join the default MDT. Each PE router may be associated with a receiver. When data for a multicast stream is sent, all receivers for the PE routers receive the multicast stream. A receiver receives the multicast stream even if the receiver is not interested in it.

A data MDT may be used to offload the multicast stream to specific receivers that are interested in receiving the multicast stream. This alleviates receivers from being flooded with data they do not wish to receive. When a switchover to a data MDT is desired, a head-end router sends messages to other PE routers on the default MDT indicating that a switchover to a data MDT will be performed for a specific multicast stream. The signaling from the head-end router is unreliable. Thus, some PE routers may not receive the message. However, making the message reliable is not considered necessary because the head-end router may send another message soon after, such as a minute after.

Receivers that are interested in the multicast stream have their associated PE routers send a response indicating that they would like to join the data MDT. A data MDT is then built based on these requests. Thus, the building of the data MDT is receiver-driven. The head-end router does not know when all receivers that are interested in the multicast stream have actually joined the data MDT (or if receivers have even received the notification of the pending switchover). Also, the head-end router may not even know if a data MDT has been set up. Rather, the switchover is performed without any of this knowledge. Accordingly, this may result in lost packets as receivers that are interested in the multicast stream will not receive the multicast stream.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

FIG. 1depicts a system100for providing reliable switchover for a default MDT to a data MDT for a multicast stream according to one embodiment. As shown, a network is provided that includes a head-end router102, P routers104, and egress routers106. Also, a source108and receivers110are provided. It will be recognized that other network configurations of the network shown will be appreciated.

Source108is configured to provide information that receivers110may be interested in receiving. For example, source108is a multicast source that outputs a multicast stream of information. The multicast stream may be packets of information, or any other form of data.

Receivers110may be any devices that can receive the stream of traffic from source108. Each receiver110is associated with an egress router106.

Head-end router102, P routers104, and egress routers106may be any network devices. Although a router is described, it will be understood that other network devices may be appreciated, such as switches, gateways, etc.

Head-end router102is configured to receive the multicast stream from source108. Head-end router102is then configured to send the stream to egress routers106.

P routers104may be routers found in the core of the network. Any number of P routers104may be appreciated. P routers104are considered to be downstream from head-end router102and route the multicast stream to egress routers106.

Egress routers106are configured to receive the multicast stream and to send it to receivers110. Egress routers106may be at the edge of a network.

In one embodiment, the network may be a virtual private network (VPN). In a multicast VPN (MVPN) domain model, a default MDT is built for the VPN. It is VPN specific. The default MDT is a tree that includes all egress routers106in it. It is used to send a multicast stream to all egress routers106in the network.

The default MDT is set up using signaling between head-end router102and egress routers106. In one embodiment, protocol independent multicast (PIM) may be used to set up the default MDT. For example, PIM joins are sent upstream from egress routers106to build the default MDT.

When the default MDT is used to send a multicast stream, all receivers110in the default MDT receive the stream even if receivers110have no interest in the multicast stream. Thus, a data MDT is used to allow only select receivers110to receive a multicast stream from source108. Receivers110can join the data MDT only if they are interested in receiving the multicast stream. Thus, when a multicast stream is sent using the data MDT, only receivers110that join the data MDT receive the multicast stream. This prevents receivers110from being flooded with data they do not wish to receive.

To send a multicast stream using a data MDT, a switchover from the default MDT to the data MDT occurs. The data MDT has to be built before the switchover. If the switchover is performed before all interested receivers110join the data MDT, then those receivers110will not receive the multicast stream after the switchover occurs. Accordingly, embodiments of the present invention provide a reliable switchover from a default MDT to a data MDT.

Embodiments of the present invention reliably provide the switchover to the data MDT by using reliable signaling and reliable building of the data MDT. The message notifying of the pending switchover to the data MDT is reliably sent using signaling that is reliable. Also, the switchover from the default MDT to the data MDT does not happen until all egress routers106have responded to the message. Egress routers106join the data MDT if associated receivers110are interested in receiving the multicast stream from source108.

When it is determined that a switchover from a default MDT to a data MDT is desired, head-end router102sends a mapping request message indicating that a switchover is going to happen for a specific multicast stream. As described above, in one embodiment, this message is sent using reliable signaling. For example, reliable signaling may be a transfer control protocol (TCP) connection between head-end router102and each of egress routers106. TCP is a protocol that guarantees reliable delivery of data. Over the connection, messages can flow in two ways. Other protocols that are reliable may be used in place of TCP. For example, border gateway protocol (BGP) may be used. In other embodiments, protocols that are not considered reliable may be used. However, other checks may be implemented to ensure that messages are received.

Accordingly, head-end router102sends a mapping request message to egress routers106advertising which data MDT should be joined to receive a specific multicast stream. Egress routers106then signal back through the connection if they are interested and will be joining this data MDT.

The joining of the data MDT is done reliably in that the switchover does not happen until responses have been received from all egress routers106. In one embodiment, when egress router106receives a mapping message through the connection, if egress router106is interested in receiving the multicast stream, it needs to join the data MDT sent in the mapping request message. The mapping request message includes information needed to join the data MDT. For example, in one embodiment, the mapping request message may include an identification of source108, a group and VPN identifier to uniquely identify the multicast stream, and a forward equivalence class (FEC) of the data MDT that should be referenced. A forward equivalence class is used to group IP packets that should be sent with the same forwarding treatment.

Egress router106may determine if an associated receiver110is interested by using the group and VPN identifier. For example, egress router106may include a list of multicast streams that receiver110is interested in. This list is checked and it is determined if receiver110is interested in the multicast stream.

If egress router106has a receiver110that is interested in the multicast stream, a mapping response message is sent to a directly-connected router upstream in the direction of head-end router102. For example, if egress router106-1is sending a mapping response message, the mapping response message is sent to P router104-1.

The mapping response message includes an indication that egress router106is interested in receiving the multicast stream. In one embodiment, the mapping response message includes the FEC for the default MDT that has already been joined, the FEC for the data MDT (learned from the mapping request message), and a specific indication as to whether egress router106wants to receive the traffic from the multicast stream or not (i.e., join the data MDT). For example, the specific indication may be a positive multicast label distribution protocol (MLDP) label binding message that includes the two FECs. If egress router106does not want to receive the traffic from the multicast stream, the mapping response message may include the two FECs with a negative label binding message. MLDP is a standard multicast protocol used to negotiate the labels (addresses) used to forward packets. Although MLDP is described, it will be understood that other protocols may be used, such as protocol independent multicast (PIM) with reliability extensions.

An upstream router receives the mapping response messages. The upstream router only forwards another upstream mapping message upstream when responses are received from all routers downstream that it should receive responses for according to the default MDT. For example, P router104-1is coupled through an interface to egress routers106-1and106-2. P router104-1can determine from the default MDT, such as from a replication list for the default MDT, which routers are coupled to it through the interface. Thus, P router104-1knows that responses should be received from egress routers106-1and106-2. The reason why the default MDT replication list can be used is that joining the default MDT is mandatory for all egress routers106in the network. Thus, it can be relied on to determine which downstream routers should send responses.

P router104-1thus waits until mapping response messages are received from both egress routers106-1and106-2. Because egress routers106are configured to send a mapping response message whether they are interested or not, P router104-1knows it will eventually receive mapping response messages from egress routers106-1and106-2. Also, since a reliable signaling protocol is used to send the mapping request message, P router104-1knows that egress routers106-1and106-2received the mapping request message.

Thus, a positive or negative mapping response message is received at P router104-1from egress routers106-1and106-2. P router104-1then forwards a mapping response message upstream that includes the responses from egress routers106-1and106-2. In one embodiment, a P router104only sends a positive or negative message upstream. It does not include which egress routers106sent the positive or negative mapping. For example, if egress routers106-1and106-2both respond with a negative mapping response, P router104-1forwards a negative response upstream to P router104-3. Likewise if egress routers106-3and106-4respond with a positive mapping, P router104-2sends a positive response upstream to104-3. Now, P router104-3only needs to send a positive response to head-end router102. The negative responses do not have a label binding, so P router104-3does not send traffic to P router104-1but sends traffic to P router104-2as the positive mapping provides a label binding that is used forward packets on. P router104-3knew that egress routers104-1and104-2were downstream receivers for the default MDT. If a positive and negative response is received at P router104, then a positive response may be sent up stream. For example, if egress router106-1sends a positive mapping response and egress router106-2sends a negative mapping response, P router104-1may send a positive mapping response upstream. However, when P router104-1receives the traffic for the multicast stream, it can send the traffic to egress router106-1and not egress router106-2. This is because P router104-1may keep track of which responses it receives.

For P router104-2, the process is the same as it expects to receive mapping response messages from egress routers106-3and106-4. When those mapping response messages are received, P router104-2sends another mapping response message upstream.

P routers104-1and104-2then send their mapping response messages to P router104-3. P router104-3is configured to wait until a response is received from P routers104-1and104-2. In this case, P router104-3knows that it should receive a mapping from P routers104-1and104-2. When the mapping response messages are received from P routers104-1and104-2, P router104-3sends another mapping response message to head-end router102.

As the mapping response messages are sent upstream, the data MDT may be built. When head-end router102receives the mapping response message, it can determine that the data MDT has been completely set up before switching the multicast stream for source108from the default MDT to the new data MDT. This is because mapping response messages are not sent upstream until all routers have responded.

While waiting for the data MDT to be set up, packets will flow via the default MDT. Thus, there is no packet loss when switching. Eventually, head-end router102receives the mapping response message for the data MDT. When head-end router102receives the mapping response messages, it knows that all egress routers106have joined the data MDT if desired.

When the final mapping response message is received from P router104-3, head-end router102knows all routers106have responded. The data MDT may be receiver-driven in that the data MDT is built as responses are being sent upstream. The FEC for the data MDT is then used to join routers106to the data MDT if they are interested in joining. Thus, the data MDT is built when the final message is received at head-end router102.

In another embodiment, the data MDT may also be built by head-end router102and thus is head-end driven. For example, resource reservation protocol-traffic extension (RSVP-TE) may be used to set up the data MDT. For example, if head-end router102receives signaling that egress routers106-1and106-3desire the traffic, head-end router102may set up the data MDT to egress routers106-1and106-3using reliable signaling.

FIG. 2depicts a more detailed embodiment of a P router104and egress routers106according to one embodiment of the present invention. As shown, a sub-section of the network is provided that includes P router104-1and egress routers106-1and106-2.

A request receiver202-1in egress router106-1is configured to receive the mapping request message for joining a data MDT for a specific multicast stream. Request receiver202-1then determines if receiver110-1is interested in receiving the multicast stream for the data MDT.

Response generator204-1is then configured to generate a mapping response message that indicates whether or not receiver110is interested in the multicast stream. For example, a mapping response message may indicate in the positive or negative whether receiver110-1wants to receive the multicast stream. Response generator204then sends a response to P router104-1.

Egress router106-2also includes a request receiver202-2and response generator204-2. Request receiver202-2and response generator204-2perform the same functions as described with respect to egress router106-1. However, they determine if receiver110-2is interested in receiving the multicast stream. A response in the positive or negative is sent to P router104-1.

Response receiver206of P router104-1is configured to receive the mapping response messages from response generators204-1and204-2. Response receiver206is configured to wait until responses are received from all routers connected through an interface. For example, response receiver206uses a default MDT list210to determine routers that are coupled to it through an interface. Default MDT list210includes all the routers106that have joined the default MDT. The FEC class for the default MDT in the response may be used to determine which default MDT list to use.

Response receiver206is configured to determine which routers106it should receive responses from. Once responses have been received from routers106-1and106-2, a response generator208is configured to send a mapping response message upstream again. The process described above is then repeated at the upstream router.

FIG. 3depicts a simplified flow chart300of a method for determining when to send a mapping response message upstream according to one embodiment of the present invention. In step302, a mapping request message is received at egress router106for joining a data MDT for a multicast stream.

In step304, router106determines if receiver110wants to join the data MDT to receive traffic for the multicast stream.

If receiver110does not want to join the data MDT, in step306, router106sends a mapping response message upstream indicating that the receiver is not interested.

If receiver110is interested, router106sends a response upstream that indicates receiver110is interested in joining the data MDT.

FIG. 4depicts a simplified flowchart400of a method for determining if all responses have been received from downstream routers according to one embodiment of the present invention. Step402receives responses from routers106. The responses indicate a positive or negative whether routers106want to join the data MDT.

Step404checks default MDT list210to determine if all responses from downstream routers have been received that should have been received. For example, responses should be received from all routers106on the same interface that are downstream.

In step406, it is determined if all responses have been received. If not, the process reiterates to step402where a router waits to receive more responses from downstream routers.

If responses have been received from all routers, step408sends a mapping response message with the responses to an upstream router. The upstream router can then perform the same process again as described inFIG. 4.

Accordingly, techniques for reliably switching from the default MDT to a data MDT are provided. The reliable switchover is provided using reliable signaling between a head-end router102and egress routers106. Further, the switchovers are reliable because responses are received from all egress routers106that have joined a default MDT. Thus, the switchover from the default MDT to the data MDT does not occur until it is known whether or not all routers106in the default MDT want to receive traffic for the multicast stream.

Although the invention has been described with respect to specific embodiments thereof, these embodiments are merely illustrative, and not restrictive of the invention. Although a default MDT and data MDT are described, it will be understood that the default MDT and data MDT may be any data structure that may be used to distribute a stream of information may be used. A person skilled in the art will appreciate mechanisms about default MDTs and data MDTs, such as those described in ietf draft “draft-ietf-13vpn-2547bis-mcast-00.txt”, which is incorporated by reference in its entirety for all purposes.

Any suitable programming language can be used to implement the routines of embodiments of the present invention including C, C++, Java, assembly language, etc. Different programming techniques can be employed such as procedural or object oriented. The routines can execute on a single processing device or multiple processors. Although the steps, operations, or computations may be presented in a specific order, this order may be changed in different embodiments. In some embodiments, multiple steps shown as sequential in this specification can be performed at the same time. The sequence of operations described herein can be interrupted, suspended, or otherwise controlled by another process, such as an operating system, kernel, etc. The routines can operate in an operating system environment or as stand-alone routines occupying all, or a substantial part, of the system processing. Functions can be performed in hardware, software, or a combination of both. Unless otherwise stated, functions may also be performed manually, in whole or in part.

A “computer-readable medium” for purposes of embodiments of the present invention may be any medium that can contain and store the program for use by or in connection with the instruction execution system, apparatus, system or device. The computer readable medium can be, by way of example only but not by limitation, a semiconductor system, apparatus, system, device, or computer memory.

Embodiments of the present invention can be implemented in the form of control logic in software or hardware or a combination of both. The control logic may be stored in an information storage medium, such as a computer-readable medium, as a plurality of instructions adapted to direct an information processing device to perform a set of steps disclosed in embodiments of the present invention. Based on the disclosure and teachings provided herein, a person of ordinary skill in the art will appreciate other ways and/or methods to implement the present invention.

Embodiments of the invention may be implemented by using a programmed general purpose digital computer, by using application specific integrated circuits, programmable logic devices, field programmable gate arrays, optical, chemical, biological, quantum or nanoengineered systems, components and mechanisms may be used. In general, the functions of embodiments of the present invention can be achieved by any means as is known in the art. Distributed, or networked systems, components and circuits can be used. Communication, or transfer, of data may be wired, wireless, or by any other means.