Subject: Question on prunes?

From: "Jesus Maria Arango - Ing. Comunicaciones FSM LTDA." <[email-masked]>
Date: Wed, 19 Feb 1997 08:11:43 +0500 (GMT)

Reading throuh some documents and books about multicasting, I find that
Reverse Path Multicasting uses prunes to truncate branches where multicast
traffic is not deseired for certain branches. 

I don't understand why prune information is removed from all router's
memory periodically, thus transmiting paquets everywhere. Textbooks say
it's because of changes in the group membership and topology. My questions
are:

- Can't this problem be solved just by sending "graft" or "join" messages
back to the source?
- What are the advantages and disadvanteges of both methods?
- Is there any actual protocol that doesn't use "graft" messages and
instead erases prune information periodically?

Thanks in advance

  *****************************************
  *             Jesus Arango              *
  *      Ingeniero de Comunicaciones      *
  *  Supernet - FSM LTDA. - Cablesistema  *
  *        E-Mail: [email-masked]        *
  *       Internic POC Handle: JA406      *
  *          Tel: (574) 268-9000          *
  *          Fax: (574) 268-1281          *
  ****************************************

---

From: Bill Fenner <[email-masked]>
Date: Wed, 19 Feb 1997 08:12:43 PST

"Jesus Maria Arango - Ing. Comunicaciones FSM LTDA." <[email-masked]> 
wrote:
>it's because of changes in the group membership and topology.
>

Yes, group membership changes are handled by grafts, and topology changes
are handled by routing exchanges.

>- What are the advantages and disadvanteges of both methods?

The reason for prune information to be forgotten is so that it can go
away when a source stops transmitting.  If prunes are permanent, and
a source sends a single packet to a group to which no one is listening,
the whole network will get prune state instantiated.  Now the sender
sends no more packets, ever.  Now what?  If prunes don't time out, the
prune state will last forever in the network, taking up memory space
in routers, even though it's not needed any more.

>instead erases prune information periodically?

DVMRP and PIM-DM both do both.

  Bill

---

From: "Hugh W. Holbrook" <[email-masked]>
Date: Wed, 19 Feb 1997 09:37:11 -0800

Jesus,

What you say is true.  Sending graft messages back to the source does
suffice to handle changes in membership and changes in topology.  Both
PIM-DM and DVMRP send graft messages.  Reverse path multicasting does
not require prunes to be periodically regenerated in order to "update
the prune state."  

Prune state in routers is periodically removed in order to reclaim state
that is created by routers or hosts that crash or are partitioned from
their upstream router.

In existing implementations of RPM (at least in mrouted-3.8), the
lifetime of prune messages must be kept short (several minutes) because
prune messages are not reliably transmitted to the upstream router. 
Thus, if a prune message sent by router R is lost, traffic will continue
to flow to R until it retransmits its prune, which may not happen until
the "prune lifetime" expires.  

In an implementation of RPM where graft and prune mechanisms are
transmitted using a protocol that is robust to packet loss, the prune
lifetime can be increased to a large interval.  Both PIM-DM and DVMRP
send graft messages reliably to the upstream router, but neither
protocol mandates the reliable transmission of prune messages.  PIM-DM
allows prunes to be retransmitted in a rate-limited way on
point-to-point links.

-Hugh Holbrook
Distributed Systems Group
Stanford University

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Feb 1997 11:29:20 -0800

>> the "prune lifetime" expires.  

    Please note, that PIM-DM doesn't have this problem. A Prune can be
    triggered from receiving data for an (S,G) that has an empty outgoing
    interface list. And the Prunes are most certainly rate-limited to deal
    with lossy links.

Dino

---

From: Bill Fenner <[email-masked]>
Date: Wed, 19 Feb 1997 11:43:43 PST

>that is created by routers or hosts that crash or are partitioned from

Or that simply stop sending traffic.

>the lifetime of prune messages must be kept short (several minutes) because

The next release of mrouted has longer prune lifetimes and prune
retransmission.  (See draft-ietf-idmr-dvmrp-v3-04.{txt,ps})

  Bill

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Feb 1997 12:28:56 -0800

>> Isn't the rate-limiting needed for more than just dealing with lossy links?

    Yes.

>> On a multi-access link, a router, R, will continue to receive packets for
>> an (S,G) that R has pruned if any neighboring routers:

    This "feature" is disabled on multi-access links.

>> Thus, prunes may legitimately fail to stop arrival of unwanted packets,
>> even if prunes are not lost, so some mechanism for limiting the rate of
>> prune generation is essential.

    Right.

>> Bill pointed out to me that his approach is better for incremental
>> deployment (compatible with unmodified upstream routers).

    Right. Bill will you being doing this on multi-access links too?

Dino

---

From: Steve Deering <[email-masked]>
Date: Wed, 19 Feb 1997 12:26:00 -0800

>     interface list. And the Prunes are most certainly rate-limited to deal

Dino,

	(a) consider that link to be upstream towards S, and
	(b) have a non-empty outgoing interface list for (S,G).

I certainly agree that the lack of reliable delivery of prunes in DVMRP
was a mistake, and if I were starting from scratch, I would require
prune messages to be positively acknowledged, the same as grafts.  An
alternative that I believe Bill is putting in mrouted 3.9 is to do
triggered-prunes (like in PIM-DM) with an exponentially increasing
back-off, to limit the overall rate of prunes occuring when only
some of the downstream routers on a link have requested pruning.
Bill pointed out to me that his approach is better for incremental
deployment (compatible with unmodified upstream routers).

Steve