Subject: Re: DVMRP pruning in a circular network.

From: [email-masked] (Vivian Lu)
Date: Fri, 26 Apr 96 16:11:57 EDT

Hi Bill,

    Since I have not heard from you, I am wondering if you have seen the
    attached mail yet.   I am trying it again.

    Thanks, Vivian.
 
>>	Message 455:
>>	From vlu Thu Apr 18 12:09:59 1996
>>	To: [email-masked]
>>	Subject: DVMRP pruning in a circular network.
>>	Cc: sshieh, timm, [email-masked]
>>	Status: RO
>>	
>>	
>>	Hi Bill,
>>	
>>	   Let me introduce myself first.
>>	   My name is Vivian Lu.  I implemented pruning for Bay's DVMRP software.
>>	
>>	   Last year, at INTEROP'95 Atlanta, I talked to 3COM about the problem
>>	   of DVMRP not prune correctly in a circular topology. And they have been
>>	   following the development for this problem, meanwhile I have moved to RSVP
>>	   development.   
>>	
>>	   Attached is what they sent me in October last year.  Now that we are in
>>	   the need of implementing the real fix other than what we have right now
>>	   (i.e. having the subordinate router send prunes to the dominant router),
>>	   we are wondering if there are code diffs for the fix that you can email     
>>	   to BAY or do we just have to wait until 4.0 is out, and if so, when
>>	   will 4.0 be released?
>>	
>>	   Thanks, Vivian. 
>>	
>>	
>>	===========================================================================
>>		Message  1:
>>		From [email-masked] Tue Oct 31 14:44:59 1995
>>		Return-Path: <[email-masked]>
>>		Received: from lobster.wellfleet.com by BayNetworks.com (4.1/SMI-4.1)
>>			id AA25164; Tue, 31 Oct 95 14:44:58 EST
>>		Received: from lobster1.wellfleet (lobster1.wellfleet.com) by lobster.wellfleet.com (4.1/SMI-4.1)
>>			id AA26554; Tue, 31 Oct 95 14:43:53 EST
>>		Received: from lobster.wellfleet.com by lobster1.wellfleet (4.1/SMI-4.1)
>>			id AA28196; Tue, 31 Oct 95 14:44:09 EST
>>		Received: from lobster1.wellfleet (lobster1.wellfleet.com) by lobster.wellfleet.com (4.1/SMI-4.1)
>>			id AA26551; Tue, 31 Oct 95 14:43:50 EST
>>		Received: from lightning.synoptics.com by lobster1.wellfleet (4.1/SMI-4.1)
>>			id AA28188; Tue, 31 Oct 95 14:44:01 EST
>>		Received: from bridge2.NSD.3Com.COM by lightning.synoptics.com (4.1/SMI-4.1)
>>			id AA16843; Tue, 31 Oct 95 11:43:12 PST
>>		Received: from dutch.NSD.3Com.COM by bridge2.NSD.3Com.COM with SMTP id AA16599
>>		  (5.65c/IDA-1.4.4nsd for <[email-masked]>); Tue, 31 Oct 1995 11:44:28 -0800
>>		Received: from localhost.NSD.3Com.COM by dutch.NSD.3Com.COM with SMTP id AA20409
>>		  (5.65c/IDA-1.4.4-910730 for <[email-masked]>); Tue, 31 Oct 1995 11:38:45 -0800
>>		Message-Id: <[email-masked]>
>>		To: [email-masked]
>>		Subject: Dominants, subordinates, pruning, life, the universe, and everything.
>>		Date: Tue, 31 Oct 1995 11:38:44 -0800
>>		From: Tian-Yuan Lin <[email-masked]>
>>		Status: RO
>>		
>>		
>>		Hi, Vivian:
>>		
>>		After talking to Bill, we decide to resolve the prune problem found in Interop
>>		by implementing neighbors bitmap (see detail below).
>>		
>>		Thanks,
>>		TY
>>		
>>		>At 3:32 PM 10/13/95, Bill Fenner wrote:
>>		>
>>		>>  When we were there, Cyndi described a problem with mrouted's pruning
>>		>>implementation, which you said you solved by having a router that was
>>		>>not the dominant send a prune to the dominant router, because it was
>>		>>too much state to keep around a list of subordinates per route.
>>		>>
>>		>>  We think we have a solution that will in fact *reduce* the amount of
>>		>>state in a routing table entry, as well as speed up pruning decisions,
>>		>>at the cost of limiting the number of neighbors a router may have.
>>		>>
>>		>>  If you replace rt->rt_subordinates (32 bits * numvifs) with a bitmap
>>		>>(say, 64 bits) of subordinates, and assign each neighbor a bit number,
>>		>>then you save memory if numvifs > 2, and you can easily maintain a
>>		>>bitmap of which neighbors are subordinates per route.  If you maintain
>>		>>a similar bitmap for prune state (instead of a list), then you can
>>		>>simply do (subordinatebitmap & ~prunebitmap) to obtain prune/send
>>		>>state, instead of doing the O(number of neighbors * number of prunes)
>>		>>junk that it does now.
>>		>>
>>		>>  We are in the process of implementing this, but will need help with
>>		>>the testing -- if we send you mrouted code diffs, can you help us
>>		>>test out the idea?
>>	>