Subject: mrouted-3.8 pruning broken

From: "Danny J. Mitzel" <[email-masked]>
Date: Sat, 09 Mar 1996 18:59:24 -0800

I've been looking at Deering's earlier papers and the current
Pusateri DVMRPv3 spec to figure out the details of pruning.  using the
simple network diagram from the early Deering/Cheriton papers:
                    
          S         
	 / \	    
     5 /     \ 6    
     /	       \    
   /	         \  
 -----         -----   	  
 | X |	       | Y |
 -----	       -----
   |             |  
  ------------------  network a
       |                       
     -----	               
     | Z |	               
     -----	               
       |  	               
  --------------      network b

router X is the dominant router for network a; X has neighbors Y and Z; 
Z is subordinant to X.  according to the pruning algorithm, X should
stop forwarding on network a and propagate a prune upstream when it
receives a prune from all subordinant routers [and there are no local
group members on network a].

here is the code segment from mrouted-3.8, accept_prune() routine:
    stop_sending = 1;
    for (vr = uvifs[vifi].uv_neighbors; vr; vr = vr->al_next)
        if (find_prune_entry(vr->al_addr, g->gt_pruntbl) == NULL) {
	    stop_sending = 0;
	    break;
	}
note that the code is searching for a prune message from all neighbors,
thus network a will never be pruned because X will never receive a
prune message from Y.

doing pruning correctly seems to require maintaining the list of
subordinant routers per-source/route [or as Deering describes in his
thesis: r.num-subordinates[k] # of subordinates, per attached subnetwork k].
using the complete list of neighbors may not be appropriate [as shown
above], and the current rtentry.rt_subordinates[] array maintained in
each route only allows tracking one subordinant per-vif which is
insufficient for any subnet with >1 subordinants.

danny

---

From: Bill Fenner <[email-masked]>
Date: Sat, 9 Mar 1996 19:51:16 PST

In message <[email-masked]> you write:
>subordinant routers per-source/route

Right.  mrouted 4.0 keeps track of this information properly, earlier
versions are broken.

  Bill

---

From: Thomas Pusateri <[email-masked]>
Date: Mon, 11 Mar 1996 00:22:25 -0500

>Right.  mrouted 4.0 keeps track of this information properly, earlier

The gated version of DVMRP is also broken with respect to pruning.
This is something I have known about but haven't had a chance to fix it.
The data structures need re-thought to efficiently keep this much state.

Tom

---

From: "Cyndi M. Jung" <[email-masked]>
Date: Mon, 11 Mar 1996 23:24:23 -0800 (PST)

What a nice description of what we found at Interop last September -
and we had redundancy just about everywhere, with two tunnels, and
neither of them ever pruned.  Made the whole trip worth it.

The right thing to do is to use the information in poison-reverse to keep
track of which routers are truly downstream with respect to a given source 
network - only require a prune from them. However, if the dominant router
has a version number lower than 4.0, the subordinant router could send a
prune message back to the dominant router when a multicast packet fails the
reverse path check on an interface, instead of simply silently discarding the 
data.  

So, until 4.0 is available, don't use redundant paths for DVMRP. 

I hope 4.0 comes out soon :-)

Cyndi