Subject: Re: [DNA] Bootstrapping router knowledge for landmark-based DNA proposal

From: Greg Daley <[email-masked]>
Date: Wed, 13 Jul 2005 13:01:46 +1000

Hi Brett and Jim, 

----- Original Message -----
From: Brett Pentland <[email-masked]>
Date: Wednesday, July 13, 2005 12:06 pm
Subject: Re: [DNA] Bootstrapping router knowledge for landmark-based 
DNA proposal
> Hi Jim,
> 
> If DNA routers refrain from answering RSs altogether, then the
> bootstapping process will achieve nothing when all the routers
> on a link startup together since they'll just ignore each others'
> RSs.

Chicken or Egg?

We've seen similar problems with this before, where
no-one advertises.

> Regarding RFC 2461, the only bit I could find on this is section
> 6.2.1 which deals with becoming an advertising interface.  It doesn't
> have any bootstrapping period; it just says that the interface
> should respond to Router Solicitations sent to the all-routers
> multicast address and that it should verify the consistancy of
> RAs sent by neighbouring routers.
> 
> So I don't think it matters whether responses are unicast or
> multicast but I think routers should respond with RAs that have
> no DNA-specific options included.

I think that for landmarks, the presence of the separate
Yes/No flags in the existing Landmark Option format allow
the router to say "I saw RS's Landmark Option", but leave
both flags unset if it is unable to say that the landmark
is present, while it is still bootstrapping knowledge

This is how I've implemented. I provide about 15 seconds 
for knowledge to be 'incomplete' in a similar way to CPL.
Routers advertise as described above. Hosts rely on CPL
logic if there's no authoritative landmark (which is always 
a decent fallback).

This also works when there are too many landmarks to track 
(for example if someone is spoofing prefixes to make it difficult
to store all seen prefixes).  Prefixes which are seen, stored and
known can be answered yes, but other prefixes can be answered
"I saw the RS's Landmark Option" with flags unset.

This provides knowledge that the state of the routers is incomplete
for the link.

This information is useful to hosts which wish to be aware of 
unusual circumstances.

With regard to advertisements, it's vitally important to immediately 
advertise your FastRA capability though, even though you may not be able
to do FastRA for a few seconds.  This means that fast RA delays won't be
available for 1/N of the RS's received in the bootstrap period, but 
those
devices should receive 50ms delayed RSs.

The reason for advertising FastRA immediately (even before you send) is 
to
ensure that RAs don't collide when you finally turn on the capability.

Greg

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 13 Jul 2005 04:21:10 -0700

Greg Daley wrote:
Greg,

overall your suggestions sound like a very useful strategy for both 
hosts and routers. Some nits below.

> is present, while it is still bootstrapping knowledge

I'm not sure it needs to say "I saw the landmark" - what would a host do 
when it receives this? The host would fall back to CPL in any case.

And while bootstrapping the router would now about the prefixes it has 
been configured to advertise, thus it can provide "yes" answers for those.

> ensure that RAs don't collide when you finally turn on the capability.

So is it for the fastRA that you need a "I saw the landmark" response?
Perhaps there should be a "I'm a fastRA router" in the RA.

   Erik

---

From: James Kempf <[email-masked]>
Date: Wed, 13 Jul 2005 09:29:22 -0700

Greg,

> is present, while it is still bootstrapping knowledge

I'm not sure what this really buys us. During a link bootstrap, I wouldn't
expect any requests for landmarks from hosts anyway, since they will be
coming up on the link too. And, as you say below, if someone hands over
during that period, they can always use CPL.

> logic if there's no authoritative landmark (which is always

15 seconds sounds like a good default link configuration time. I'm not sure,
though, how that would work on a TRILL link. If there are a lot of Rbridges,
it might take longer. But as long as it is configurable, there should not be
a problem.

> This information is useful to hosts which wish to be aware of

I don't know, it seems to be a bit of an additional refinement that I feel
probably wouldn't get used often, but seems like it would introduce
additional complexity.

> ensure that RAs don't collide when you finally turn on the capability.

I don't understand this particular point. If a host just happens to need a
link attachment confirmation during bootstrap, then why is this important?
Seems like it could get the same from nonDNA RAs.

            jak

---

From: Greg Daley <[email-masked]>
Date: Thu, 14 Jul 2005 11:37:44 +1000

Hi Erik,

Sorry about my lack of clarity.

> when it receives this? The host would fall back to CPL in any case.

Any response containing a landmark option is the "I saw the landmark" I
mentioned.

It admittedly doesn't buy much for the receiver if it receives the
landmark option except to say that the DNA advertisor hasn't seen the
prefix itself.   Some information is conceivably better than none?

> been configured to advertise, thus it can provide "yes" answers for those.

Definitely, Just as it can advertise RAs but not know that it has a
completeRA.

[cut]
>>
>> The reason for advertising FastRA immediately (even before you send) 
>> is to ensure that RAs don't collide when you finally turn on the
 >> capability.
> 
> 

I think the two are separate.  The DNA flag provides the
"I'm a fastRA router" capability.  It can be switched on even before
the router needs it though.

---

From: Greg Daley <[email-masked]>
Date: Thu, 14 Jul 2005 11:43:34 +1000

Hi James,

I think you're thinking of what happens after power failure.
While that's important, valid (and fast) configuration when
other routers are already in operation is also needed.

> during that period, they can always use CPL.

There are often other devices which will be already running,
so the router can be present, and tell hosts and routers about
its presence (for example setting the DNA flag), whilst not
countermanding existing DNA state.

> it might take longer. But as long as it is configurable, there should not be

If the period is much more than 15 seconds, it really matters that
the routers have some partial DNA capability enabled in order to
provide protection from poor environments (where it would be possible to
drop into and out of configuration).

More than 15 seconds is fine, but STP calculation is 30 seconds so I
wouldn't go more than 45 seconds on startup.

If the idea is OK, then we can fine-tune the time.

> probably wouldn't get used often, but seems like it would introduce

Not much!

I've just got a hold down timer which if it hasn't expired, you cannot
answer "no" authoritatively in the Landmark option (or call the RA a
CompleteRA).

It's called the OverFlow timer for when there are too many prefixes to
track.   DNA will need some sort of protection for that case too.
I just default the timer to exipre 15 seconds after startup.

> Seems like it could get the same from nonDNA RAs.

It's not the host's startup. Hosts are battery powered, and may just 
arrive while one of the routers is starting.

If none of the routers are bootstrapped, then the responses from the
routers will be nonDNA (non fast) RAs.

If any of the routers are already bootstrapped, then they will be able
to provide fastRA response.

Since any number of the other routers may already be advertising, they
only need to adjust their position for the joining router (actually I
think the adjustment is 20ms (RASeparation) in the draft).

This will only affect the responses for the advertisements where the
router would have advertised fastest anyway (based on the hashing
method).

Greg

---

From: James Kempf <[email-masked]>
Date: Thu, 14 Jul 2005 14:30:01 -0700

> other routers are already in operation is also needed.

You're thinking of a new router coming up when the link is already
boostrapped, yes, that's true.

> countermanding existing DNA state.

OK, so I have no objection if the DNA flag is set during link bootstrap.

> I just default the timer to exipre 15 seconds after startup.

So how many timers are there total in your implementation?

> router would have advertised fastest anyway (based on the hashing

OK, this sounds fine.

            jak

---

From: Greg Daley <[email-masked]>
Date: Fri, 15 Jul 2005 09:51:37 +1000

Hi James,

> So how many timers are there total in your implementation?

There's one timer for the gathered prefixes (this doesn't have an
expiry callback,  but is checked when the list is used or updated).
This is used as the overflow timer.

There's a timer per interface for fastRA token buckets
(this doesn't have an expiry callback, as it's checked when an RS
is received).

There's a set of timers with callback expiries for scheduling delayed
unicast RAs (Added in my version of Radvd in order to provide
parallel responses).  These have callback expiry timers, free pools etc.

There's a multicast RA timer per interface.  This already
existed in RADVD.

The first two sets require updating with gettimeofday() operations,
and have a comparison operation, but these are only called when the
data structure would otherwise be used or updated, so don't have
their own scheduling mechanisms.

The code's out now (not the most simple version, but inspectable).

Greg

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 14 Jul 2005 14:12:28 -0700

> Any response containing a landmark option is the "I saw the landmark" I

I understood that part.

> prefix itself.   Some information is conceivably better than none?

Information that the receiver isn't interested in isn't useful.
That's why I asked what you intended the receiver to do with this piece 
of information.

   Erik

---

From: Greg Daley <[email-masked]>
Date: Mon, 18 Jul 2005 12:42:20 +1000

Hi Erik,

> That's why I asked what you intended the receiver to do with this piece 

OK.  I find myself compelled to agree with you (even) by my own logic.

So if we recommend that the router incapable of answering either Yes
or No doesn't send a Landmark, do we need to specify that hosts
discard landmark options with neither Yes or No received in an RA?

Greg

---

From: Brett Pentland <[email-masked]>
Date: Mon, 18 Jul 2005 15:54:12 +1000

So attempting to summarise, during bootstrap a router needs to:

- Solicit for RAs to fill its DNAPrefixList and DNARouterList
     (It can't rely on unsolicited RAs since it might be the
      only one bootstrapping at that instant and doesn't know
      how frequent other routers are advertising, if at all)

- Respond to solicitations (otherwise the bootstrapping won't
      achieve anything if all routers are bootstrapping at the
      same time)

- Not include a Landmark Option in responses if the answer is
      NO (though there does seem to be support for allowing
      responses if the answer is YES - probably as a MAY)

- Include the DNA flag in any RAs so that other routers can
      learn that they need to include this router in calculations
      relating to Fast RA transmission.

- Though I don't think it has come up in the discussion to date,
      I think that a bootstrapping router should probably
      multicast a few unsolicited RAs to announce its presence
      on the link to any already-bootstrapped routers.

In general, RAs won't have any DNA-specific parts except for the
DNA flag.  Timings would be as specified in RFC2461.  The other
exception to this would be if an RS with a Landmark Option is
received and the answer to the question posed in it would be a
yes, in which case a DNA-style Landmark Option reply MAY be used
instead.

Does that sound about right?
Brett.

---

From: Greg Daley <[email-masked]>
Date: Mon, 18 Jul 2005 15:57:21 +1000

Hi Brett,

Fine with me (opinions may change with further conversation).

Greg

---

From: Brett Pentland <[email-masked]>
Date: Mon, 18 Jul 2005 18:26:58 +1000

>>      responses if the answer is YES - probably as a MAY)

I was putting this bootstrapping stuff into draft -01 and have
just submitted it, but I've had to leave out the optional YES
response for now because I came across an issue with it.

How would the timing go for one of these yes responses during
bootstrap?  I think it's probably not a great idea to give a
fast response yet because during bootstrap we can't be sure
that we know all of the other routers on the link. It may be
possible to go fast as the consequence of choosing the same
time slot as another router is just a higher probability of a
collision, not a guarantee of it.

If we choose not to allow the fast response, then is it worth
having the yes answer at all rather than just doing the RFC 2461
style response and letting the host fall back on CPL?

Anyone have any thoughts on this?
Brett.

---

From: James Kempf <[email-masked]>
Date: Mon, 18 Jul 2005 09:08:55 -0700

Brett,

As I believe I mentioned in an email on Fri., the alternative to the RS
technique described below is the following.

When an interface comes up, a router:

- Multicasts RAs on the interface for a period of DNAInterfaceBootstrapTime
seconds (15 default), with exponentially increasing times between multicast.
The RAs are simple RAs with complete prefix and other information on the
router, including setting the DNA flag so that other routers can learn that
they need to include this router in calculations relating to Fast RA
transmission.

- Listen on the interface for RAs from other routers and record prefix
information and DNA status of discovered routers (a router must do this all
the time, actually, in case a router comes up while the link is operating).

- Drop any RSs received during DNAInterfaceBootstrapTime.

Comparisons are:

1) RA technique has somewhat less traffic. Both techniques require repeated
multicasts (the RS technique to compensate for possible losses, the RA
technique to advertise), the RA technique has somewhat less traffic because
it does not require the unicast return RA and the RS technique requires
additional RA beacons, which the RA technique doesn't (beacons are built
in).

2) The RS technique is subject to interference from hosts that solicit
during this time period. The interference might be unintential or
intentional (i.e. a DoS attack). It is possible if the traffic volume of RSs
is heavy enough, that the router's token bucket algorithm would roll over to
multicast anyway, so using the RA multicast technique is a way to ensure
that all routers get a response (the token bucket roll over algorithm has no
provision for repeated multicast).

How about we generate an Issue in the issues list and put this out for
discussion?

            jak

----- Original Message -----
From: "Brett Pentland" <[email-masked]>
To: <[email-masked]>
Cc: "Erik Nordmark" <[email-masked]>; "James Kempf"
<[email-masked]>; "Dna" <[email-masked]>
Sent: Sunday, July 17, 2005 10:54 PM
Subject: Re: [DNA] Bootstrapping router knowledge for landmark-based DNA
proposal

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 18 Jul 2005 09:10:16 -0700

>      on the link to any already-bootstrapped routers.

That's already covered in RFC 2461, but it doesn't hurt to spell it out 
explicitly in the DNA specification.

   Erik

---

From: Brett Pentland <[email-masked]>
Date: Tue, 19 Jul 2005 09:50:55 +1000

Hi Jim,

> - Drop any RSs received during DNAInterfaceBootstrapTime.

Yes, if that covered all cases it would be simpler not to need RSs, but
there is no guarantee that there will be any unsolicited RAs from the
other routers on the link before the 15 sec expiry.  If that doesn't
happen, then the router will start behaving as a full DNA router before
it has complete information and may thus answser requests incorrectly.

I can't see how we can avoid RSs if we want to be confident of complete
information before we start behaving as a DNA router.

Brett.

---

From: Brett Pentland <[email-masked]>
Date: Tue, 19 Jul 2005 09:57:27 +1000

> explicitly in the DNA specification.

Yes I noted in the text for -01, that a few RAs should be sent and
why, and pointed at section 6.2.4 of RFC 2461.

Brett.

Note that I have posted draft -01 but it hasn't shown up in the
repository yet.  For a preview see:

http://www.ctie.monash.edu.au/dna/draft-pentland-dna-protocol-01.txt

Changes from -00 can be viewed at:

http://www.ctie.monash.edu.au/dna/draft-pentland-dna-protocol-01-from-00.diff.html

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 19 Jul 2005 01:16:07 -0700

> discard landmark options with neither Yes or No received in an RA?

We should clarify that such landmark options are a no-op, i.e. that they 
don't change any state on the receiver (since they have no semantic value).

    Erik

---

From: James Kempf <[email-masked]>
Date: Tue, 19 Jul 2005 13:32:45 -0700

Brett,

> it has complete information and may thus answser requests incorrectly.

I assume you are thinking of nonDNA routers, because if we specify something
from DNA routers, then there will be a high probability that something will
come through, since the retransmits should ensure it in the face of drops,
right?

RFC 2461 (and RFC 2461bis) has this to say about boot time sending of
unsolicited RAs (Section 6.2.4):

   For the first few advertisements (up to
   MAX_INITIAL_RTR_ADVERTISEMENTS) sent from an interface when it
   becomes an advertising interface, if the randomly chosen interval is
   greater than MAX_INITIAL_RTR_ADVERT_INTERVAL, the timer SHOULD be set
   to MAX_INITIAL_RTR_ADVERT_INTERVAL instead.  Using a smaller interval
   for the initial advertisements increases the likelihood of a router
   being discovered quickly when it first becomes available, in the
   presence of possible packet loss.

So, basically, whether or not a nonDNA router does advertisement is
configurable. If we decide to use advertisement, then I think we need to
specify what these configurable parameters need to be for nonDNA routers
(and we probably ought to do that anyway even if we decide to use
solicitation, as Eric's note mentioned).

> information before we start behaving as a DNA router.

I don't see how RSs would provide any more confidence than RAs. In order to
make sure that all routers got the RSs in the face of drops, they would need
to be multicast retransmitted too. So whether the RAs are multicast
retransmitted or the the RSs are doesn't seem to make much difference AFIKT.
Can you explain why you think this would make a difference?

            jak

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 08:38:18 +1000

Hi Erik,

> don't change any state on the receiver (since they have no semantic value).

Yes, and then also tell routers not to send them.

Is that the agreement?

Greg

---

From: Brett Pentland <[email-masked]>
Date: Wed, 20 Jul 2005 15:36:42 +1000

> come through, since the retransmits should ensure it in the face of drops,

Sorry, I guess I didn't explain the scenario I was thinking of well
enough.  If a DNA router bootstraps on a link that already has fully
bootstrapped DNA routers on it, there is no guarantee that the existing
routers will send any RAs during the new router's bootstrap period.
Unsolicited RAs might be minutes apart.  The only way that they can tell
that there is a new router is by the RAs it sends.  I guess we could use
those to trigger the sending of RAs, but the existing router discovery
method for soliciting RAs is with an RS.

Does that make sense?
Brett.

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 20 Jul 2005 03:59:51 -0700

Greg Daley wrote:
>> We should clarify that such landmark options are a no-op, i.e. that 
>> they don't change any state on the receiver (since they have no 
>> semantic value).
> 
> 

Works for me.

   Erik

---

From: James Kempf <[email-masked]>
Date: Wed, 20 Jul 2005 12:51:27 -0700

> method for soliciting RAs is with an RS.

What I am specifically concerned about is that hosts can disrupt the
bootstrap by sending too many RSs. The bootstrapping router or routers are
going to have to multicast retransmit RSs to All_Routers_Multicast anyway to
account for drops, in order to exchange information among themselves. If
lots of hosts start multicasting RSs also, it could push the routers' token
bucket algorithm into the multicast region. Note that this can even happen
without intent (i.e. not as a result of a DoS attack) during a full link
bootstrap.

Do you think there might be some way to overcome this problem using RSs to
solicit?

            jak

---

From: Brett Pentland <[email-masked]>
Date: Thu, 21 Jul 2005 10:06:39 +1000

> Do you think there might be some way to overcome this problem using RSs to

I don't think it's actually a problem.  In that case there's a large
number of RSs - enough to exhaust the token buckets in the bootstrapped
routers - and they fall back to multicasting RAs which will be
scheduled for within 3 seconds.  The end result is that the
bootstrapping router receives the RAs during its bootstrapping period.

Brett.

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 20 Jul 2005 12:10:19 -0700

>    presence of possible packet loss.

The above RAs help to let the routers already present find out about a 
newly arriving/booting router, but it doesn't let the new guy find out 
about the routers that were already present on the link.

For the second part it seems to be that the new router needs to send 
something which triggers the other routers to send their RAs. That 
sounds like an RS to me.

    Erik