DVMRP Pruning and Grafting

DVMRP Pruning and Grafting

Membership in a multicast group is dynamic and receivers can join or leave a multicast group using IGMP. Forwarding multicast traffic onto networks that have no receivers or downstream routers is an inefficient use of network resources, so DVMRP uses prunes and grafts to dynamically alter the structure of the source-based trees. To illustrate the situations when pruning and grafting comes into effect, we will examine some simple network scenarios where these mechanisms come into play. In Figure 5-25, we have a network with one multicast source and one multicast receiver.

Figure 5-25: DVMRP network used to illustrate pruning and grafting

Router A and B have no leaf networks, a network with only multicast receivers and no forwarding routers. The receiver on router C has signaled, using IGMP, that it desires to receive traffic from the multicast group (which has as its source the host attached to router A).

How do routers A and B know to forward traffic to router C so the host may receive it? Initially, DVMRP assumes that all networks have receivers and so it floods the multicast traffic received on the RPF interface on all networks. Routers A and B know that they are upstream routers in relation to router C due to the fact that router C has used poison-reverse for the network containing the source.

Assume now that the receiver no longer wishes to receive multicast traffic from the source. The host then sends an IGMP Leave message for the group, and router C queries the network and discovers that no hosts want to receive multicast traffic. At this point, there is no reason for any of the routers to forward multicast traffic from the source because there are no longer any receivers. Router C sends a Prune message to router B, and because no other networks require the forwarding of multicast traffic by router B, router B sends a Prune message to router A. Router A now has no downstream routers requiring multicast traffic, so router A prunes its serial interface.

Prunes are also necessary when hosts need to receive multicast traffic on an attached network. The network of Figure 5-26 contains a multi-access ethernet segment. From our earlier discussion, we know that either router C or D will become the designated forwarded for the ethernet network, based on the metric back to the source, or in the case of a tie, the IP address. Whichever router is not elected as designated forwarder must prune its serial interface from the source tree, so only one router will forward the multicast traffic to the receiver.

Figure 5-26: Pruning interfaces on a multi-access network

The actions that a router must take when a Prune message is received are as follows:

1.   If the Prune is received from a router that the receiving router has not formed a two-way adjacency with, then discard the message.

2.   Examine the Prune message and determine if the message is the proper format.

3.   If the Prune message does not apply to source information active on the router, then discard the message.

4.   If the neighbor that sent the prune is not a dependent neighbor for the network to be pruned, then discard the message.

5.   If there is an active Prune from this neighbor for the indicated source network and group, then reset the timer to the value received in the Prune message.

6.   If there is not an active Prune from this neighbor for the indicated source network and group, then set a time-out using the value in the Prune message.

7.   If all dependent downstream routers on this network have been sent Prunes, then determine if any group members are on the network. If there are no group members, then send a Prune message to the upstream router.

The actions a router must take when sending a prune are as follows:

1.   If the upstream router cannot receive Prunes, then do not send a Prune. This can be determined from the neighbor’s DVMRP version and capabilities.

2.   If any Graft messages need to be acknowledged, cancel them.

The Prune packet format is shown in Figure 5-27.

Figure 5-27: DVMRP Prune packet format

The Prune lifetime is the amount of time the Prune is in effect. DVMRP is a broadcast and Prune protocol, so when the Prune expires, the multicast traffic will again be forwarded until another Prune is received.

Grafting is the opposite of pruning. When a pruned network needs to again receive multicast traffic from a particular source for a multicast group, then the network needs to be added, or grafted, back onto the multicast source based tree. Graft messages are sent upstream until they reach the source tree for the particular multicast source and are acknowledged at each hop. Graft messages are sent under the following conditions:

1.   If a host joins a multicast group (using IGMP) on a network that has been pruned for that group.

2.   A DVMRP router is enabled on a pruned network and is dependent on the upstream router.

3.   A router on a pruned network restarts (signaled by the generation ID).

4.   If a Graft acknowledgment is not received for a previous Graft message.

The format of the Graft and Graft acknowledgment packets are shown in Figures 5-28 and 5-29. The values of the various DVMRP timers are listed in Table 5-7.

Figure 5-28: DVMRP Graft packet format

Figure 5-29: DVMRP Graft acknowledgment packet format

Table 5-7: DVMRP Timers and Values

Timer

Value in Seconds

Probe Interval

10

Neighbor Timeout Interval

35

Minimum Flash Update Interval

5

Router Report Interval

60

Route Expiration Time

140

Route Hold-Down

120

Prune Lifetime

Variable (less than two hours)

Prune Retransmission Time

3 with exponential back-off

Graft Retransmission Time

5 with exponential back-off