Subject: [DNA] Design Team solution 1: Question about DNA Option

From: Greg Daley <[email-masked]>
Date: Tue, 10 May 2005 15:24:02 +1000

from draft-pentland-dna-protocol-00.txt:

Section 4.3:

The learned prefixes in the DNA option are not
8 octet aligned, and include prefix lengths.

Assuming that advertised prefixes are global
addresses, can't the prefixes be:
1) 8 octet aligned and

2) 8 octets (64 bits) long

With no prefix length field.

 From RFC 3513 (S2.5.1):

    For all unicast addresses, except those that start with binary value
    000, Interface IDs are required to be 64 bits long and to be
    constructed in Modified EUI-64 format.

This would lead to 6 octets overhead (which is the minimum additional
cost when you consider the size of prefix lengths).
One of those octets could indicate the known number of prefixes,
and the option length could indicate how many prefixes are advertised
(effectively indicating if the RA is complete or not when the PIOs
are counted).

This would remove the need to get two bits from the RA header in the
case of

Also, if there is a requested landmark prefix, could it not appear
in the DNA option, even if the option is does not provide complete RA?
The minimum NACK for an unknown landmark would then be 8 octets
(no prefixes in the list), on top of the existing RA.

The DNA option could then be used in both solicitor and receiver.

Greg

---

From: Brett Pentland <[email-masked]>
Date: Thu, 12 May 2005 13:24:59 +1000

> 8 octet aligned, and include prefix lengths.

Yes this is something that needs more thought.

> addresses, can't the prefixes be:

Probably necessary.

>    constructed in Modified EUI-64 format.

Does this imply that all advertised prefixes MUST be 64 bits long?
If so it would simplify the DNAO considerably.

> (effectively indicating if the RA is complete or not when the PIOs

The known number of prefixes is something which we had in there and
removed.  The thinking was that if the number didn't match the number of
prefixes in PIOs and the DNAO, then it wasn't really much use, and thus
its function was no greater than a "complete" bit.  That bit could go in
the DNAO, but then the DNAO would need to be included, even when there
were no learned prefixes (ie. when routers all advertise the same set of
prefixes on a given link).  This would then mean that 64 bits were
being included to carry one bit of information.

> The DNA option could then be used in both solicitor and receiver.

Yes, I think this could be done.  It would be overloading two separate
functions on the DNAO.  Does it provide some advantage to do this?

As the draft stands, we have two modes of operation and the Landmark
Option is used for one, and the DNA Option for the other.  The preferred
mode is a unicast response.  The host uses a Landmark Option to ask
if a prefix is being advertised on a link, and any router can unicast a
response including a Landmark Option indicating yes or no for that
prefix.  The DNA Option is used in multicast RAs as a fallback position
when a unicast is not possible (due to rate limiting or insufficient
information).  It allows the RA to contain enough information for hosts
to be able to make a decision on their own.  The intention is that this
is a fallback position, however, and that the normal state of affairs
would be a simple "Is prefix X being advertised on this link?" - "Yes,
prefix X is" or "no, prefix X isn't".

Brett.

---

From: Greg Daley <[email-masked]>
Date: Thu, 12 May 2005 16:39:15 +1000

Hi Brett,

Please be aware that any hats I have are off,
and I'm trying to work on engineering issues,
providing personal opinions.

> If so it would simplify the DNAO considerably.

2462Bis Section 5.5.3 talks about this in some detail.

The prefixes in PIOs in 2462Bis are described as being potentially
variable length.

What would be sufficient here is to use the DNAO header to identify
the number of 64 bit prefixes present in the option (which would
consume a portion of the option's size), with the
space after that explicitly ignored.

This would allow for arbitrary sized prefixes later, and not penalize
existing 3513 compliant systems which advertise 64 bit IIDs (and 64 bit
Prefixes), except for 8 bits which are reserved (out of 40).

> being included to carry one bit of information.

Well the document either does CompleteRA (on every unsolicited RA) now,
or it has a prefix landmark in it.

The benefits of putting the completeness information into all the
unsolicited RAs is of very marginal benefit (only helps for
packet loss, since the initial assumption of the document is that
L2 hints are available).

The solicited RAs then already have space for either a landmark or
a completeRA (DNA) Option.  Each of the specifications will have
wasted space, which can be put to use for other purposes.

It's actually not one bit of information either.

The fact that a host knows all the number of prefixes but can't fit
them in an RA can be used to compose a complete prefix list which is
provably (with SEND) complete.  At least the MN can stop hunting for new
prefixes if in the responses from two or more routers, it can see that
a conjoined (and complete) set of prefixes is available.

> functions on the DNAO.  Does it provide some advantage to do this?

Yes.

One option is defined for solicitor and receiver.

The storage of the prefixes for both completeRA and Prefix Landmarks
are the same (they both collect a list of prefixes).

The selection of a prefix from the known prefix set for transmission
is just an ordering issue (for example, if it's not possible to transmit
the whole set).

So the option contents are the same, I guess the option should be
too.

> prefix X is" or "no, prefix X isn't".

I don't like the yes/no either.

Well, SEND already has better response matching than this
using its Nonce Options (which are mandaroty for SEND responses).

It's also possible to use this without SEND as detailed in:

draft-daley-dna-nonce-resp-01.txt

Sorry about the self plug, but I think it's a good solution.

(much cleaner than the yes/no as a faked up response match).

Greg

---

From: Brett Pentland <[email-masked]>
Date: Thu, 12 May 2005 17:54:50 +1000

> packet loss, since the initial assumption of the document is that

Yes, the primary reason for it being there was for a fallback when the
unicast response isn't possible.

> a conjoined (and complete) set of prefixes is available.

Yes, and this is why we originally had it there.  The result of our
discussion was that since the RA is not complete and the host would not
be able to make a decision based on that RA alone, there wasn't all
that much value in it.  If folks think that the assistance this provides
in building a CPL is worthwhile, it could be put back.

> So the option contents are the same, I guess the option should be

They are the same if you don't use the yes/no flags for answering
the landmark question.  If you do, then you need to tie the flags to
a particular prefix in the option (maybe there is only one in that
case) or match the RS/RA with a nonce as you suggest below, and the
overload get a bit uglier.

> (much cleaner than the yes/no as a faked up response match).

It's true that you can match responses with a SEND nonce, but I
wouldn't call this a faked up response match because response
matching was not the primary goal.  The matching is being done
between the answer and the question, and one could argue that it's
cleaner doing that match fully contained within the RA, rather than
across the RS/RA using a nonce.

Brett.

---

From: Greg Daley <[email-masked]>
Date: Thu, 12 May 2005 18:10:59 +1000

Hi Brett.

Thanks for this.

In case people aren't aware I'm travelling to Cairns next week
(hat off again) to the IEEE wireless (802.21/802.11) interim meeting.
It's a chance to express opinions just before my e-mail
becomes intermittent.

Brett Pentland wrote:
[cut]
> unicast response isn't possible.

I guess that if we're prepared to accept "no additional prefixes" option
as a tax for solicited RAs even if there's no requested landmark (even 
if it's multicast),  Then the DNAO could be used as both completeRA and
landmarking solution, without consuming RA header bits.

Please note that I'm not worried about completeRA for unsolicited RA,
or even the "Completeness" part, although that's neat.

What I'm thinking of is:

Here are a bunch of prefixes I've learned are on the link: it didn't
cost me much more to send them (even if the set is incomplete).

[cut]
> overload get a bit uglier.

Well, if you guarantee a "MUST" on the requested prefix if it is known,
then it doesn't matter with overload.  You'd just advertise "I'm
overloaded, please don't infer that the prefix is absent".

Note that overloaded is different to "decided not to advertise".

> across the RS/RA using a nonce.

Well I thought SEND was a SHOULD anyway.

If we SHOULD send it it will already be present in most RS's,
nodes interested but otherwise unwilling to implement SEND
may be able to buy in at a fairly low cost (16 octets over the
combined RS/RA).

Reception of an RA with your nonce means that other information,
like which question you were asking (is this a valid prefix?)
Don't need to be contained in the message.

The gain may be considered to be marginal, except that the
"No" response is required (perhaps in a separate option), every
time movement occurs.  That's the case to optimize...

Sure the host would have to remember the question, to match the Nonce,
but I'd argue that it probably would anyway, in order to modify state.

Plus the nonce makes a good basis for a hash lookup key ;)

Greg

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 12 May 2005 11:07:24 -0700

> With no prefix length field.

Since prefixes can be of arbitrary length (0-127 bits) [there is nothing 
that constrains the length for the 000/3 part of the address space, and 
I wouldn't be surprised if over time we relax the /64 recommendation 
either], the only way you can ensure that *all* the prefixes in the DNAO 
are 8 byte aligned is to include 16 bytes for every prefix.
 From an implementation perspective there aren't any benefits to ensure 
that some prefixes are 8 byte aligned, since you need to write code to 
handle the unaligned cases anyway.

Up leveling, I'd expect that in the wast majority of IPv6 links, all the 
routers would advertise the same set of prefixes. While RFC 2461 in its 
generality allows for different set of prefixes being advertised by 
different routers, I see no operational use for this when running a 
stable network.
When all routers advertise the same set of prefixes, DNA would never 
need to send a DNAO option. Thus spending a lot of complexity on trying 
to optimize the DNAO option layout doesn't make much sense to me.

> (no prefixes in the list), on top of the existing RA.

Since in the wast majority of cases there wouldn't be a DNAO, I don't 
see the benefits of overloading the DNAO with the landmark 
question/answer parts.

 > wasted space, which can be put to use for other purposes.

What is the wasted space and in which case?
We have 3 cases:
1. LO with "yes" answer (just the RA header + LO).
2. LO with "no" answer (RA+LO+misc options+PIOs) ["misc" being MTU etc]
3. Multicast RA (periodic and solicited): RA+misc options+PIOs and DNAO 
if there are any learned prefixes

I don't see much wasted space in either one of them.

 > The fact that a host knows all the number of prefixes but can't fit

s/host/router/>>>

 > a conjoined (and complete) set of prefixes is available.

The DT discussed whether a count of prefixes was useful when not all 
advertised and learned prefixes fit in one RA, but came to the 
conclusion that due to the prefix not being static, it actually doesn't 
help. The routers might at any time be reconfigured to advertise an 
additional prefix, one less prefix, or replace one prefix with another.
Combining this with the fact that the host in question plus the N 
routers on the link form a distributed system, and there is no definable 
order of the events in a distributed system (see "Time, clocks, and the 
ordering of events in a distributed system" by Leslie Lamport), the DT 
couldn't come up with any host processing rules that would use a count 
of prefixes that actually worked.

 > I don't like the yes/no either.

Did you have some technical comments, our should we switch to discussing 
our personal tastes and distastes :-)

 > using its Nonce Options (which are mandatory for SEND responses).
 >

But that solves the question of making matching the RA with the RS, 
which isn't a problem we need to solve.
The problem we need to solve with landmark is making sure that the 
answer applies to the question. This problem is solved in the draft by 
repeating the question with the answer. (A technique which is also used 
in the DNS protocol.)

For example, if host H1 and H2 have duplicate addresses, and send the RS 
while being in optimistic DAD mode, then it might be that the RS sent by 
H2 results in a unicast RA being delivered to H1. This is harmless, 
since the host verifies that the question in the LO is indeed the 
question they asked, and if not ignore the answer. And if both hosts 
asked the same landmark question then H1 will happily accept the LO 
answer that was a result of H2 sending an RS.

This never gets things wrong.
A nonce scheme is making a probabilistic argument about the likelihood 
of the two hosts picking the same nonce, hence needs to depend on good 
random number generators. And with a non-zero probability it will end up 
with two hosts picking the same nonce.

Note that using nonces in SEND is a bit different. First of all, to do 
security you need a good random number generator. Second, SeND doesn't 
fail if two hosts by chance pick the same nonce; SeND just needs to make 
  it unlikely that a nonce value gets repeated, since it would allow an 
attacker to replay an old message.

     Erik

---

From: Greg Daley <[email-masked]>
Date: Fri, 13 May 2005 12:52:05 +1000

Hi Erik,

I know there are a lot of opinions expressed here.

Firstly, you'll probably be aware that these are
discussions of details.

The general trend of the ideas in the proposal are
OK to me personally, so the main thing I'm trying
to see is if the solution can be simplified.

Really, the minimum requirement is one method for link
identification in DNA.

So it's arguable that the meeting of Prefix Landmarking
and CompleteRA in the proposal can be seen as an either/o
choice between them.

Actually, I think that they're not just aimed at reaching
the same end goal (link identification), but are actually
variants of each other.

In prefix landmarking, an explicit question is asked:
Am I here?

This divulges additional information about the previous,
location of the host, but implies that the host wishes
to know its actual location.

In Complete RA (or non-landmarked at least), an implicit
question is being asked, that of: Where am I?

In the movement case, both of the responses have to say
"You are here".

So my argument is that there's flexibility in allowing both
of these, so long as the implementation cost on the router
is low enough.

Some of the opinions expressed are informed by current work
I'm doing with the DNAPrefixList on RADVD.

Once again, some of them aren't informed ;)

> are 8 byte aligned is to include 16 bytes for every prefix.

Well, 000/3 can't be autoconfigured today, and there's host code which
would be broken for a while if we did so...

> handle the unaligned cases anyway.

I think 8 byte alignment is required for IPv6 addresses and their
components.  Only DHCP doesn't do this (for legacy reasons?).

So the issue is: how many octets do you want to assign to a prefix?

It's clearly more than 16 octets if you want to handle the completely
general case (7bit prefix len, +128 bits of prefix).  Unless there's
some mapping done in the first portion of the option (at least 17 
octets/prefix anyway), there will be 20/24 octets per prefix.

For the small number of prefixes you're likely to send in the option,
it would be better to have a specially marked PIO.

So, if we want to make it attractive to send additional information,
keeping the size down is fairly important.

8 octets a prefix for the common case (these are autoconfigured
EUI-64/3041/CGA addresses! which are bound to 64 bit).

> different routers, I see no operational use for this when running a 

Other than cellular infrastructure sharing (which is theoretical)...

And a router which decides not to send all prefixes in 32 octet PIOs,
but wants to advertise their complete prefix set nonetheless
(there's some flexibility in 2461 on this).

We're not necessarily talking about disjoint prefixes anyway.

We're talking about routers with incomplete lists being able
to answer authoritatively about any prefix on the link
(in response to a direct question, or a request for the
set of prefixes).

It's reasonable to assume that not every router will advertise all
prefixes.

> to optimize the DNAO option layout doesn't make much sense to me.

Well, it doesn't really seem to be useful to de-optimize things
explicitly for IIDs which aren't supported in the IPv6 Addressing
Architecture, and RFC 2374.

If the format of the option can easily be extended later (by leaving
unallocated space, which is ignored by the receiver), existing networks
could be supported easily, and fairly efficently.

Since the bulk of networks for the next X years will be 64 bit PLen,
either the benefits of CompleteRA have to be realized for them, or
the concept of sending multiple non-PIO prefixes discarded.

Here's what I'm thinking:

         0                   1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |     Type      |    Length     |  OnLinkPrefs  |  #FixedRecs   |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                          Reserved                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        |                     64 bit prefix  #1                         |
        |                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        ~                                                               ~
        |                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        |                     64 bit prefix  #N                         |
        |                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        ~       Free Space: Future Use, Ignored by receivers            ~
        |                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The number of fixed records (which may be zero for a NACK) and the
length of the option define the length used for 64 bit prefixes
(Length may be 1 and/or #fixed may be zero?)

This is the basic scheme adopted with MLDv2 (rfc3810 Section
5.1.12.  Additional Data, 5.2.10 Auxilliary Data), which allows
future extensions without explicitly defining record types and formats
for something which won't be used in the forseeable future.

This has the lowest cost for a scheme which supports advertisement of
autoconfigured 64-bit addresses.  You could even put a note
restricting the addition of prefixes to the advertisement
to those which are 64-bit into the 'completeness' set.

This could be updated later if needed (if 000/3 comes out?).

> see the benefits of overloading the DNAO with the landmark 

Well, the storage requirements for DNAO sending and Prefix Landmarks
are _exactly_ the same.

The questions answered are the same (except the landmark asks a 
different question, and the completeRA adds information if the
answer is affirmative).

The transmission requirements for the Landmark option in an RA match or
exceed the costs of a DNA option carrying the same information.

So I'd guess my idea is to have only one option, used for answering
questions in solicited RAs.

Whether the DNAO and Landmark can be combined, and what that means
for individual prefixes is the (fairly) important part to discuss.

> 1. LO with "yes" answer (just the RA header + LO).

I think this is a premature optimization myself...
After all, it is a solicited RA.

The draft is asking the host to make a decision as to whether
it wants to learn about movement (use an LO), or gather more
prefixes (when no movement occurrs, with no LO) when sending
an RS.

The host shouldn't have to make that distinction.

> 2. LO with "no" answer (RA+LO+misc options+PIOs) ["misc" being MTU etc]

Then the DNAO (if needed) will have to be sent too.

That's potentially wasteful.

> if there are any learned prefixes

Failing to make a distinction between Solicited and Unsolicited
Multicast RAs fails to help with a landmark request, which has to go out
multicast.

The addition of a landmark (or a PIO/DNAO) containing a response to a
landmark solicitation would help lots of devices checking at the same
time (at essentially only the cost of the prefix beign advertised).

Also the distinction helps with solicited multicast RAs, where even
if you don't want to answer all the landmark requests, you can still
indicate completeness.

Unsolicited Multicast RAs really don't need additional data except
rarely.

This is because the document assumes L2 hints on hosts.

>  > The fact that a host knows all the number of prefixes but can't fit

Sorry,

> of prefixes that actually worked.

We're not talking about crossing the Internet here.

The timesteps are all deltas from the original information transmitted
link-locally.

In the infrastructure side, where the Routers gather their
prefix identities, the granularity where there would be crossover
would be subsecond (assuming no loss??), on added prefixes.

So the worst thing that can happen is that for a short interval,
the number of advertised prefixes can be wrong. The same problem
exists for CompleteRA, in that it can advertise completeness, but
not include a newly introduced prefix.

We've already agreed to let the worst of the prefix add and subtract
issue be handled by ND and renumbering anyway, so I don't accept
the argument.

The essential thing about an appearing/disappearing prefix is that
it doesn't last long enough in an advertisement to cause problems in
a new/old network upon reallocation or link partition.

The argument I'd have is that the cost of the one bit for completeness
in the header of the RA is actually a lot higher than the one octet
within the RA, and the absence of a DNA option (or a Landmark Option)
in a DNA solicited RA is sufficient in itself to show
completeness (without using up more than one bit of header), if
you can match the response to the question.

> our personal tastes and distastes :-)

Elegance is a matter of taste, and of great importance in design :)

Unfortunately, I often feel the shape of something before I can
describe it succinctly.

The problem with Yes/No in the header is that the presence or absence
of something can be used to answer the same question.

Showing that the question was heard (by explicit response matching),
or that the response is complete in and of itself, is better IMHO than
devising a separate scheme to do the job in more space, less neatly.

I guess it's a matter of taste to some extent, but separation of the
response matching from the identification (and the Fast RA scheme)
seems straightforward to me.

> repeating the question with the answer. (A technique which is also used 

Well matching the content of the question, can either be done in-band
(with the landmark option), or out-of-band by identifying the
message channel.

I'm not too worried about DNS. We can talk about Radius too, which
uses a session ID...

So long as there's some identifying state for matching the response
it should work.

So I guess we're actually agreed on that :)

> with two hosts picking the same nonce.

Granted the devices may choose the same address from a broken RNG,
but this is a transient problem at best (since one or both devices will
leave the network anyway independent of the Router's RA response).

Also, unless the devices are doing Optimistic DAD, neither would have
sent a specified source address RS anyway.

Optimistic DAD puts requirements on selection of addresses, based on
strong randomness (RFC 1750/3041), CGA (which has strong encyption and
SEND implications) or unique MAC addresses (if they're not unique we
have other problems)!

So I think we have a counterexample.

For devices which send specified address RS's we have a good enough RNG
to send Nonce Options.

The Source address breaks ties for nonces which happen to collide.

Greg