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

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

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 ;)

Erik Nordmark wrote:
> Greg Daley wrote:
> 
>> 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.
> 
> 
> 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.

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

>  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.

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).

> 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.

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.

> 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.

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?).

>> 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.
> 
> 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.

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.



>   > 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.
> 
> What is the wasted space and in which case?
> We have 3 cases:
> 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.

> 3. Multicast RA (periodic and solicited): RA+misc options+PIOs and DNAO 
> 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.

> I don't see much wasted space in either one of them.
> 
>  > It's actually not one bit of information either.
>  >
>  > The fact that a host knows all the number of prefixes but can't fit
> 
> s/host/router/>>>

Sorry,

>  > 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.
> 
> 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.

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.

>  > 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 :-)

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.

>  > Well, SEND already has better response matching than this
>  > using its Nonce Options (which are mandatory 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.
> 
> 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.)

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 :)

> 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.

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