Re: [DNA] Re: RS/RA Exchange

[Gregory Daley <Greg.Daley@eng.monash.edu.au>]

Hi Erik, 

----- Original Message -----
From: Erik Nordmark <Erik.Nordmark@sun.com>
Date: Thursday, March 4, 2004 10:12 pm
Subject: [DNA] Re: RS/RA Exchange

> > I was considering what it would be like to have a router
> > which always does unicast response at short interval, and one
> > which never unicast responds, and has a large interval between
> > (even solicited) mutlicast RAs.
> > 
> > In this case, there would actually be less packets on the link
> > in the case of solicitation storms, since the slow router
> > would sometimes use the same multicast packet to respond to 
> > many hosts. 
> 
> I don't know if others have explored this idea, so I might as well
> blurt it out.
> 
> The RA delay is based on two concerns:
> 1. multiple (lots?) of routers on the link responding at identical 
> time   to a RS
> 2. rate limiting - and using a multicast RA to respond to multiple RSs
> 
> I think we can address #1 by having the routers listen to each 
> others RAs
> on the link (per RFC 2461 they should do this to check for 
> inconsistentinformation) and track how many routers are on the link.
> Then make this reason for the delay be a function of the number
> of known routers - if there is only one router on the link the
> delay can be zero.
> If the router has a fine enough granularity and the link speed is
> 10 Mbps per second, I think having the random delay be 10 milliseconds
> for every router more than one.

I like this idea.   I guess that the current FastRA draft
is a less well specified version of this behaviour.
even distribution when the delay has 10ms granularity may be 
difficult to achieve in some OS's.  For Linux, the scheduling
timer is run every 10ms.  Therefore the delay @10ms becomes a
binary decision (delay or not).  If the clocks are sufficiently
unsynchronized, then this is OK.  Perhaps it wouldn't be for
similar devices which recently rebooted.  

The random delay mechanism could actually be applied so that 
the routers were ranked ( not sure how to do this ).
The fastest router would never delay.  The next fastest would
delay have a longer delay bound, the next may be double that 
(or a constant addition) until the maximum bound was reached.
say:  [0-0,0-100,0-200,0-400,0-600,0-600...]

This would ensure that the chance of RA collision with another
RA was low, and that the chance of a collision with many RAs was 
vanishingly low, while still achieving responsiveness.

Election could be by lowest link-local (or SLLAO) address hash,
or some other mechanism.  A poorly functioning high ranked router
would cause some delay, although the next ranked may provide
OK service.

> One way to address #2 is through a token bucket filter.
> Imagine a token bucket which can hold, say, 50 tokens,
> and that is filled with one token every 3 seconds.
> (This keeps the average rate below on RA every 3 seconds just as
> in RFC 2461.)
> When a RS arrives and the number of tokens is greater than 1,
> immediately unicast a RA (taking delay #1 into account if > 1 
> router on
> the link) and remove one token.
> When a RA arrives and the number of tokens is one,
> immediately multicast a RA (again taking #1 into account)
> and remove one token.
> When a RA arrives and the number of tokens is zero,
> record that a multicast RA should be sent when a token is added.
> 
> This ensures that one can handle a burst of RSs without delay 
> (or a very small delay when there are multiple routers) without
> loosing rate limiting.
> Also, should a flood (of more than 50 RSs) then after the 49 
> unicast RAs
> the system will multicast a RA every 3 seconds.

I believe that you mentioned token buckets when discussing 
FastRA a while back.

This is clearly a good idea.

It may be simple enough to tie the token refresh to the 
scheduling of unsolicited multicast RAs.

We'd need to look at whether there's some reduction in bucket
or token refreshing which could be provided, But I think
that we could provide defaults which are "No worse than today".

As a guess this is new function though: I don't think it can
go in the BCP.

Does anyone think otherwise?

Greg