Subject: Re: [lisp] #16: map versioning resolution

From: [email-masked] (Noel Chiappa)
Date: Thu, 3 Sep 2009 13:30:58 -0400 (EDT)

> From: Margaret Wasserman <[email-masked]>

    > those aren't the three bits I was talking about.

Got it - I tend to not think about the R-bit, as it doesn't do anything.

    > I don't believe we have established that _we_ want to affirmatively and
    > separately control whether those two fields are present.  ...
    > I don't know why it is necessary to control them separately.

I think it's very important to do so to maximize future flexibility of new
piggybacked control functions, should be find we need them. But I guess I
already said something very close to that; really, I can't put it any better
than that, sorry.

It's an engineering judgement that I have, based on a lot of observations of
how protocols evolve over time. Your judgement may differ from mine, but I
don't know what to do about that.

    > I also don't know why you couldn't use part of the locator-status field
    > to indicate whether it is there

I think it's best if we keep all the control bits in one place; allocating
that bit out of the 32-bit field doesn't really do anything, except move it
somewhere else in the packet - to what end?

More importantly, if that bit _is_ allocated out of that 32-bit field, it
makes it impossible (or at least very confusing - e.g. 'if the X flag bit is
set, the 32-bit field isn't a 1-bit control field, and 31 bit of LS, but just
a flat 32 bits') for _other_ uses to use the full 32 bits, which might be
important (e.g. to hold an IPv4 address).

    > you seem to be confused about the purpose of the E-bit, which is to
    > request that the other side echo the nonce that is in this packet, not
    > to indicate that the nonce in this packet is echoed.

Oops, sorry, got the bit sense inverted in my head - the overall purpose I
did have correct, actually.

    > The three bits I'm talking about are the R, L and N bits ...
    > The combinations of these bits are:
    >
    > R L N
    > 1 0 0 - "Research", no locator-status, no nonce
    > 1 0 1 - Invalid
    > 1 1 0 - Invalid
    > 1 1 1 - Invalid

That was an earlier (a couple of days ago) version. As of yesterday
afternoon, the proposal ('process the packet normally, ignoring the R-bit')
would actually have allowed either L or N to be set along with R - although
depending on the (as-yet undefined) definition of the function associated
with R, setting one or the other (or perhaps both) might have been invalid.

    > nodes that implement the -04 proposal will do _exactly_ the same thing
    > in that situation (ignore the r-bit, process the packet), as they would
    > do if we didn't define the r-bit in the LISP specification at all.

Which is why I said "whether we document [the R-bit] or not, it won't make a
big difference".

    > My proposal explicitly states that ETRs that receive formats they don't
    > understand should treat them like 0 (000), ignore the LISP header bits,
    > and process the packet as normal. 

Sorry, got confused between the different values.

That logic does have basically the same effect, but it does have some
potentially significant differences. E.g. since it doesn't allow addition of
a new function _alongside_ other already-defined functions (e.g. nonce), that
might have an impact. Without a crystal ball as to how often various things
will get used, how important the nonce is, etc, one can't draw any definite
conclusion from that, though.

    >> your format does not allow doing both Locator-Status _and_ Nonce in a
    >> single packet.

    > It could, if we define a fourth format for that cases.

Yes, but if we add more functions, in going down the 'values' road, instead of
the 'bits' road, we would need an exponentially-increasing number of values to
signal different combinations.

    >> That means there has to be extra logic _in the control plane_ ... to
    >> decide which user-data packets are going to carry the LS function and
    >> which the Nonce function

    > The existence of the separate L and N bits in Dino's proposal already
    > implies that you want this logic

Ah, no. It _allows_ an ITR to decide to do that, but it doesn't _mandate_
that an ITR to do that (as the 3-bit type code would). If an ITR implementor
were to decide that it would introduce too much complexity to do one or the
other, they can just always (modulo other future control functions) do both.

    > In general, I don't understand what nonce echoing gets us that couldn't
    > be more simply and cleanly accomplished via the control plane, but
    > presumably someone sees a use for it.

Start with the recognition that the fan-out for many xTRs is going to be
_much_ larger than the fanout for any router - because neighour xTRs can be
spread out over the entire Internet, not just the local region. Routers
typically have at most a few dozen direct neighbours, and it's quite feasible
for a router to ping them all to make sure they are up and reachable.

An xTR at a large site might have _thousands_ of neighbour xTRs, and pinging
them all, especially at a high-enough rate to _quickly_ discover failures
(which need to be bypassed ASAP for good service), would create enourmous
control-traffic overhead.

That's why people accepted the considerable hassle (as you correctly noted)
involved in piggy-backing the nonce control function onto user-data traffic.

    > I hope we can avoid creating a rat's-nest-like set of interdependent
    > flag fields.

The only way to avoid interdependent control bits is to either i) use values
(which can lead to needing exponential numbers of values as the number of
functions increases, and in addition is not good for hardware
implementations), or ii) not share header fields - which means either:

- more overhead on _every_ packet, in many cases to provide private fields
  for functions that only get used once in a great while; or
- variable-format headers, so that the extra fields only get added when
  they are needed.

This conundrum has been with networking for a long time, and some of the
earlier attempts to solve it (e.g. IPv4 options) have definitely been
problematic. Maybe this one will be painful too, but I don't think there's a
simple, perfect, solution - if there was, it probably would have been worked
out a long time ago.

In the meantime, this path seems to me to have lots of nice characteristics,
and a downside (interdependencies between control bits _in terms of legal
settings_ - there is no complexity in terms of the actual operation) which I
see as smaller than the other two options.

	Noel

---

From: Margaret Wasserman <[email-masked]>
Date: Thu, 3 Sep 2009 14:01:30 -0400

> Got it - I tend to not think about the R-bit, as it doesn't do  

So, can we drop it from the LISP specification?  Having a bit defined  
that doesn't do anything just wastes a bit...

> already said something very close to that; really, I can't put it  

I am not talking about why we want to piggyback in general...  You  
have stated that we want to pre-define
the LISP header to have a flags section, and two separate fields (one  
24-bit field and one 32-bit field) that
are controlled separately.

I don't know why we wouldn't want to view the LISP header as one big  
field that we can redefine for
different uses.

Even if we decide that we do like the idea of having two separate  
fields, so that (for example) we can
include the nonce in packets with a variety of other meanings for the  
32-bit field, why do we want to
use a whole bit to say only that the locator is on or off?  If we come  
up with 6 different ways to use
that 32-bit field, are you assuming we will have 6 mutually exclusive  
bits to control the contents of
that one field -- one that says that it is or isn't a locator, one  
that says it isn't or isn't "foo",
etc?  Or would it be better to set aside a small number of bits and  
use all of their values to indicate
what is in the field -- so all-zeros means it is empty, 1 means it is  
locator-status, two means it is
"foo", etc.

> don't know what to do about that.

I've also watched protocol designers strangle themselves by allocating  
bits for all sorts of
eventually-obsolete purposes, and then having to re-use bits in  
painful combinations to
do new things...
> somewhere else in the packet - to what end?

I wasn't really suggesting a bit in the locator-status field.  I was  
suggesting something like:  If it is zero, it isn't in use.  If it is  
non-zero it is significant.  Because if all of the RLOCs for an EID  
are down, there isn't anyone left to send that message.
> with R, setting one or the other (or perhaps both) might have been  

I guess I may not be looking at the latest version.  Dino keeps  
sending new HTML diffs that all "diff" from -03, not from each other,  
so I haven't figured out a good way to tell what he is proposing to  
change in each one.  What is he date in the version you are referring  
to?

> Which is why I said "whether we document [the R-bit] or not, it  

It'll just waste a bit, so let's not do it...

> might have an impact.

It could, in the sense that the nonce and a different field could both  
be included in one of the formats.

> signal different combinations.

Ummm...  more bits is the _same_ as exponentially increasing numbers  
of values.  The values path will always have the same number of bits  
(except when it has less bits, because some combinations are  
invalid).   Let's take an example...

If we have a nonce field and five different choices for the 32-bit  
field, and we follow the current model, we'll use 6 bits:

N (for the nonce) & L1 L2 L3 L4 L5

N will tell us if the nonce field is active.

L1 tells us if the 32-bit field contains locator-status bits or not,
L2 tells us if it contains locator-use-2 bits or not,
etc.

L1, L2, L3, L4 and L5 are all mutually exclusive, since you can't put  
two things in the same 32-bit field.

However, if we use values, we need enough room to represent 11  
different choices:

- no fields active
- L1 without nonce
- L1 with nonce
- L2 without nonce
- L2 with nonce
- L3 without nonce
- L3 with nonce
- L4 without nonce
- L4 with nonce
- L5 without nonce
- L5 with nonce

And, 11 choices can fit into 4 bits.

The same thing happens if the nonce field gets reused:  If you have  
three choices for the "N" field and
5 choices for the "L" field, in your model you would require 8 bits.   
In my model, you would require
16 values (no fields and all 15 combinations), which will fit in 4 bits.

Even if you have 8 uses for each field, your model will require 16  
bits, an my model will require 7 bits
(for 65 combined choices).

With only two fields, I don't think you ever cross over into a case  
where your model requires fewer
bits than my model.  Do you?

> other, they can just always (modulo other future control functions)  

My model doesn't mandate that an ITR do that either...  How does  
representing the same
information in a different set of bits require you to do any logic you  
aren't already doing?

In your model, you need to determine how to set each of the flags.  In  
my model you
need to choose the right format for what you are sending.  These  
aren't logically
different until you get to the "write the actual packet" moment.
> for a router to ping them all to make sure they are up and reachable.

I understand that if you want to ping your neighbors all of the time  
it is best to do
it in-line.   But, why do you want to ping your neighbors all of the  
time?fic.
> functions increases,

You have this backwards.

> and in addition is not good for hardware
> implementations),

You have not offered any argument that I understand for why this is  
not good for hardware implementations.

> or ii) not share header fields - which means either:
>

My proposal is a different way to share header fields, so these  
arguments don't apply.

Margaret