Subject: Granularity (was Re: [RRG] ALT + NERD is inelegant & inefficient, compared to APT or Ivip)

From: Brian Dickson <[email-masked]>
Date: Wed, 23 Jan 2008 17:11:29 -0500

Tony Li wrote:
> Again, the real question here is about whether we need host 
> granularity or not.
It may be that rather than having one problem/solution match-up to 
consider, that there are two:

dual-homed
multi-homed (N>2)

I'd argue that the requirements of each differ, and there can be 
significant scaling benefits from splitting them out, and handling each 
separately.

>
> However, if we do need host granularity, then I think you need about 3 
> orders of magnitude more scale, and pure push approaches simply won't 
> get you there.
For that reason, I think further exploring how to provide "host-like" 
granularity without going to full host granularity, would be wise.

So, toward that end, here I go with thoughts about 2-homed and N-homed...

N-homed (N>2)
The presumptions are that a site with >2 homes, will have the following 
characteristics:

   1. EID prefixes assigned from central authority/authorities (e.g. RIRs)
   2. has a network administrator assigning (directly, or via automated
      mechanism) EIDs
   3. handles its own TE issues
   4. handles its own EID->RLOC mapping policies
   5. has delegated PA space from upstreams for RLOCs, with PA blocks
      hierarchically aggregated by upstreams (e.g. by POP)
   6. quantities X of such sites: (current number of ASNs)<< X <<
      (number of 2-homed sites)

This can scale well enough by itself for things like NERD.

Similarly, the presumptions and requirements on 2-homed sites could be:

   1. no network administrator - just normal users with minimal
      networking knowledge
   2. prefer not to have "centrally assigned" EID prefixes
   3. want lightweight mechanism for EID->RLOC mapping, preferably automagic
   4. want scalable aggregation of EID->RLOC mappings, if possible
   5. want site EID prefixes, with EID assignment within the site via
      something like DHCP
   6. don't want actual host granularity on EIDs
   7. has delegated PA space from upsteams for RLOCs, with PA blocks
      hierarchically aggregated by upstreams (e.g. by POP)
   8. ability to "authenticate" EID->RLOC mappings to prevent spoofing
   9. needs to scale to arbitrary pairings of upstream ISP, presumably
      based on 32-bit ASNs

Putting these requirements together puts the need for addressing 
schemes, and enough bits in the address fields, into perspective.

For instance, combining requirements #2 and #3, means there would be a 
preference for a deterministic mapping scheme for (2 x RLOCs)->EID.
Similarly, adding #9 into this, means that EID prefixes must be >>64 
bits long - meaning this address space must diverge from the standard 
IPv6 use of 64-bit Interface Identifiers.

I'll take a stab at how this might look.

Let's assume first, that we are using new prefix space from IPv6.

The prefix space itself would be, for instance, the first 4 bits, such 
as 4200::/4.
Call this prefix "X:4" (meaning value X, 4 bits long).
(I'll use :N rather than /N, since /N is anchored and absolute in 
length; :N means "the next N bits", and is relative.)

The ASN-specific RLOC blocks would be constructed as:
X:4 + A:32, forming RLOC-block-A/36, and similarly RLOC-block-B/36, for 
ASNs A and B.

The actual RLOC values would be prefixes assigned from sub-blocks under 
this, constructed like:
RLOC-block-A:36 + a:28 to form RLOC-A-a/64. RLOC-B-b/64 is created 
similarly with sub-block b:28.
The assignments would presumably be done by ISP A and B, however they 
choose, probably hierarchically.

Now for the tricky part -- Constructing EID prefixes.
This is done as follows:
X:4 + A:32 + B:32 + a:28 + b:28 to form EID-AB-ab/124.
Another EID prefix (for reasons of symmetry) is also created, EID-BA-ba/124.

The "knob" for TE purposes, is the choice of which upstream is 
preferred: EID-AB-ab prefers A over B.

Note that this allows for *lots* of RLOC assignments (and thus end 
sites), but does so at the expense of the available EIDs per site 
(absolute max of 16, max usable under normal circustances is 13.)

Global reachability of RLOC blocks is aggregated. How more-specific 
information on unreachability may be carried somehow, e.g. as opaque BGP 
data used only at the edge (ITR), is unspecified.
EID->RLOC mappings are deterministic, by parsing the prefix portion, and 
appending the host portion:
X:4 + A:32 + B:32 + a:28 + b:28 + host:4 maps onto two RLOCs:

    * X:4 + A:32 + a:28 + 0:60 + host:4 (preferred)
    * X:4 + B:32 + b:28 + 0:60 + host:4 (backup)

The alternate EID has the *same* RLOCs, but in reverse preference.

Note that this means that the mappings themselves are completely 
deterministic, and as such, the requirement for push/pull of mapping 
database goes away.
It scales to 2^28 sites per ISP (268M), with arbitrary ISP/ISP pairings 
for upstreams.
It still allows for non-EID use of RLOC prefixes as individual /64's, 
with the requirement that a few fixed values be set aside (::0/4 
specifically).

Presumably prefix filtering on ingress by ISPs A and B, would permit 
only things that match (X:4 + A:32 + *:32 + a:28 + *:28)/124 as the 
encapsulated EID value, or the alternate encapsulated EID value (X:4 + 
*:32 + A:32 + *:28 + a:28)/124.

I know it's not what was necessarily envisioned by the current 
strategies, but hey, it scales pretty well, IMHO.

What do folks think?

Brian Dickson

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: Brian Dickson <[email-masked]>
Date: Wed, 23 Jan 2008 19:11:34 -0500

(Slight typo/thinko in the original, corrections in-line below. It 
probably is a lot less confusing now. :-))

Brian Dickson wrote:
> significant scaling benefits from splitting them out, and handling 
> each separately.
>
>>
>> However, if we do need host granularity, then I think you need about 
>> 3 orders of magnitude more scale, and pure push approaches simply 
>> won't get you there.
> The presumptions are that a site with >2 homes, will have the 
> following characteristics:
>
Oversight on my part - this would need *two* /4's, X and Y. X for RLOCs, 
Y for EIDs...
> X:4 + A:32, forming RLOC-block-A/36, and similarly RLOC-block-B/36, 
> for ASNs A and B.
>
> The actual RLOC values would be prefixes assigned from sub-blocks 
> under this, constructed like:
Y:4 instead of X:4... my bad.
> information on unreachability may be carried somehow, e.g. as opaque 
> BGP data used only at the edge (ITR), is unspecified.
> EID->RLOC mappings are deterministic, by parsing the prefix portion, 
> and appending the host portion:
Y:4...
> It scales to 2^28 sites per ISP (268M), with arbitrary ISP/ISP 
> pairings for upstreams.
Y:4...

---

From: David Conrad <[email-masked]>
Date: Wed, 23 Jan 2008 19:11:00 -0800

Brian,

> significant scaling benefits from splitting them out, and handling  
...
> What do folks think?

My gut feeling (FWIW) is that this would be a mistake.  The  
assumptions that you make differentiating the N=2 vs. N>2 cases appear  
to be subjective and dependent on life as we know it now, not life as  
how we might reasonably project it to be.  What is to say that in the  
'near' (for some value of that variable) future, I won't want my  
cellphone router connecting my PAN multi-homed to the (say) 6 cellular  
providers it can find signal for?

I'm not sure that coming up with an architecture that builds in these  
sorts of assumptions won't end up biting us painfully in the end.

Regards,
-drc

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 24 Jan 2008 18:27:38 +1300

On 2008-01-24 16:11, David Conrad wrote:
> My gut feeling (FWIW) is that this would be a mistake.  The assumptions
> that you make differentiating the N=2 vs. N>2 cases appear to be
> subjective and dependent on life as we know it now, not life as how we
> might reasonably project it to be.  What is to say that in the 'near'
> (for some value of that variable) future, I won't want my cellphone
> router connecting my PAN multi-homed to the (say) 6 cellular providers
> it can find signal for?

Another point is that a normal scenario for a dual homed site wishing
to change one of its ISPs would be to triple-home for a while (i.e.
add ISP C while retaining ISPs A and B) and then drop A or B once things
are stable with C. So changing from 2 to 3 and then back to 2 should
be a simple operation, not two changes of mode.

> sorts of assumptions won't end up biting us painfully in the end.

Yes, there we go predicting the future again...

   Brian

---

From: Eliot Lear <[email-masked]>
Date: Thu, 24 Jan 2008 10:16:55 +0100

> Yes, there we go predicting the future again...

That's what engineers do.  They optimize for a particular future scenario.

Eliot

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 24 Jan 2008 07:04:40 -0500 (EST)

> From: Eliot Lear <[email-masked]>

    > That's what engineers do. They optimize for a particular future

"The hallmark of great architecture is not how well it does the things it was
designed to do, but how well it does things it was never expected to handle."

	Noel

---

From: Brian Dickson <[email-masked]>
Date: Thu, 24 Jan 2008 11:01:44 -0500

David Conrad wrote:
> how we might reasonably project it to be. 
The assumptions were derived from two premises:
(1) the end "site" is a consumer-grade router, designed to operate with 
nearly zero knowledge
(2) the EIDs need to operate analogous to ULA. No conflicts, but no need 
to manage them, assign them, or otherwise add process or management to 
handling the need for EIDs

Whether the resulting design meets the needs for which it was designed, 
is the criteria that should be used for evaluating it.

None of the design aspects were built on any significant assumptions 
about life as we know it now.
> What is to say that in the 'near' (for some value of that variable) 
> future, I won't want my cellphone router connecting my PAN multi-homed 
> to the (say) 6 cellular providers it can find signal for?
>
I'd say that:

    * you are not the average user :-)
    * you can certainly use the N>2 method without any problem
    * nothing is stopping you from doing the heavier-weight stuff
    * it might be feasible to implement with multiple EIDs and
      source-address selection on the host

I wouldn't expect this to be used for any "mobile" devices, only for 
fixed (e.g. hard wired, or fixed wireless) sites, which I am presuming 
is going to be the usage driver for the bulk of 2-homed sites/hosts.

The presumption is that not a significant number of homes who are 
willing to shell out bucks for redundancy (or have their employers do 
so), would pay for a third link, if two gets them redundancy.

And add to that that in many, perhaps most, markets, there are likely to 
be two last-mile providers of layer-1 access (telco and cableco), 
regardless of who does the layer-3 stuff (DSL ISP using telco facilities).
> sorts of assumptions won't end up biting us painfully in the end.
Perhaps. But using a one-size-fits-all approach has resulted in missed 
opportunities.

What's going to be a challenge in addressing the need for host 
granularity or near-host granularity (home site) in LISP are the following:

    * big ISPs (cable and phone companies) may not want their customers
      to have this, as it lets their customers have control, and compare
      provider performance
    * whatever is done, the software/data footprint will need to be
      small, since consumer grade devices aren't likely to be
      upgradeable or have huge amounts of RAM
    * both demand and uptake will be dependent on "consumers"
    * uptake will be gated by device manufacturers for the consumer market

And most importantly - for LISP to work, it needs ITRs everywhere 
(between hosts and ETR-connected hosts).
It works best if ITRs are close to or at the site which is multihomed, 
which means consumer-grade ITRs.

Brian Dickson

---

From: Brian Dickson <[email-masked]>
Date: Thu, 24 Jan 2008 11:08:21 -0500

> be a simple operation, not two changes of mode.
By changes of mode, presumably you mean multi-homed -> single-homed -> 
multi-homed?

I don't think that would be strictly necessary.

Each EID prefix is constructed based on a pair of upstreams.

However, there could be multiple EID prefixes, announced with different 
preferences on them.

They would be ABab, ACac, and BCbc. Sort them however you want, change 
them as C gets ironed out.

And eventually disconnect A or B, and magically the EIDs with A or B in 
them go away.

Obviously, in this scheme, removing an uplink could break existing 
connections, but I doubt that's a show-stopper.

Brian Dickson

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 25 Jan 2008 06:44:10 +1300

> connections, but I doubt that's a show-stopper.

Frankly this is beginning to make shim6 look simple and straightforward...

   Brian

---

From: Scott Brim <[email-masked]>
Date: Thu, 24 Jan 2008 14:57:21 -0500

Excerpts from David Conrad on Wed, Jan 23, 2008 07:11:00PM -0800:
>> dual-homed multi-homed (N>2)
>>
> assumptions that you make differentiating the N=2 vs. N>2 cases
> appear to be subjective and dependent on life as we know it now, not
> life as how we might reasonably project it to be.  What is to say
> that in the 'near' (for some value of that variable) future, I won't
> want my cellphone router connecting my PAN multi-homed to the (say)
> 6 cellular providers it can find signal for?
>
> I'm not sure that coming up with an architecture that builds in
> these sorts of assumptions won't end up biting us painfully in the
> end.

Historically that's usually what's happened when we explored this kind
of distinction, in any area.  In the end it just wasn't worth it and
we reverted to a single general class.

There was a time when we considered special ASNs for multihomed sites.
What happened to that idea?

Scott

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 27 Jan 2008 18:30:44 +0100

> significant scaling benefits from splitting them out, and handling  

I completely disagree. There is no reason to make the assumptions you  
make.

Also, in computer science school we learn to count like this: 0, 1,  
many. If a value is larger than 1, you don't get to hardcode it in  
your solution. Experience shows that if a value isn't 0 or 1, it can  
be anything so hardcoding it will bite you at some point.

(And it's not like we need more work by splitting the problem space in  
two and then solving both parts independently.)

---

From: Brian Dickson <[email-masked]>
Date: Mon, 28 Jan 2008 10:54:22 -0500

> What happened to that idea?
I think you are thinking of single-homed sites with "special" ASNs.

Those are "private" ASNs >65000 (reserved range), and those are in use 
today.
They get removed by the upstream, and are not seen outside of the 
upstream's AS.

The RFCs and code from multiple vendors supports this.

So, thank you for providing an example where special cases *do* work, 
and do work well. :-)

Brian Dickson

---

From: Brian Dickson <[email-masked]>
Date: Mon, 28 Jan 2008 11:57:14 -0500

> I completely disagree. There is no reason to make the assumptions you 
I think you meant to say, "I *see* no reason...".

Sometimes I don't do a good enough job of explaining things, so I'll try 
again:
* As Tony Li pointed out, if you allow host granularity, you need about 
10^11 rather than 10^8 map entries - if you keep them in the map database
* If you want to keep host granularity stuff out of the map database, 
you have to encode it in the address
* You have 128 bits in the IPv6 address to work with, and 32 bits per ASN
   * The case of N=0 is non-existent.
   * The case of N=1 is trivial - EID == RLOC, no mapping needed at all
   * The case of N=2 was what I provided an example mapping for, by no 
means definitive choice, but merely showing it was possible, with some 
reasonable level of scale
   * The case of N=3, means that the number of hosts per ASN in any 
mapping scheme is <= 2^11, or 2k. Not reasonable.

So, there are three possibilities for host granularity:
* No host granularity
* mapping size 10^11 (not suitable for push)
* special case for N=2 only

Pick one and only one. I vote for N=2 as a special case, which allows 
for scalable mappings (for N>2) and host granularity (only if N=2).
The N=2 case does not *require* host granularity.
And the N>2 case is really *N>=2*, *without* host granularity.

More precisely put, the cases are:
mapped entries (no host granularity)
non-mapped entries (host granularity, N <= 2 only)
>
> Also, in computer science school we learn to count like this: 0, 1, many.
I guess it's a good thing I went to math school instead of computer 
school. They taught us about the concept of "plus a constant" (used 
mostly in calculus for integrals, but also in computers.)

Having 0, 1, many (plus a constant), means for (a constant of 2), we get:
2, 3, 3+many, which is can be further simplified as 2, 2+many (which was 
what I picked as a scheme.)
> If a value is larger than 1, you don't get to hardcode it in your 
> solution. Experience shows that if a value isn't 0 or 1, it can be 
> anything so hardcoding it will bite you at some point.
>
It's called predefined constants, as in header files full of "#define 
FOO fixed-value". We learned that in first year.
It's not hard-coding if the constant itself doesn't appear in your code.
> two and then solving both parts independently.)
The idea is to make *less* work by splitting the problem space in two.

Especially if the work parameterizes well, by having elements have 
affinity for only one of the two parts of the problem space.

Which is the case when one branch has host granularity, and the other 
branch has a mapping database to contend with.

Brian Dickson

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 28 Jan 2008 18:43:03 +0100

On 28 jan 2008, at 17:57, Brian Dickson wrote:

>>> I completely disagree. There is no reason to make the assumptions  
>>> you make.

The latter follows naturally from the former.  :-)

> Sometimes I don't do a good enough job of explaining things, so I'll  
> try again:
> * As Tony Li pointed out, if you allow host granularity, you need  
> about 10^11 rather than 10^8 map entries - if you keep them in the  
> map database

I hesitate to agree on the numbers, but obviously any number that  
includes host granularity will be higher than one that doesn't.

> * If you want to keep host granularity stuff out of the map  
> database, you have to encode it in the address

What do you mean? Encode the AS in the address? For N > 1 this  
requires that you can dynamically do a "reachable match first" lookup  
in your routing tables.

> * special case for N=2 only

We already have MIP so no host granualirity would be a completely  
reasonable choice.

Personally, I'd say: keep the host out of the mapping system, but  
allow per-host redirects. This makes the first packets always slower  
and maybe even all of them if the ITR can't spare the state. However,  
this leaves plenty of opportunities for optimization on the table  
(including simply obtaining location dependent addresses after a  
move), while pushing more entries in FIBs will only work for so long,  
even if the RIB isn't a problem.

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 29 Jan 2008 10:25:41 +1300

> The idea is to make *less* work by splitting the problem space in two.

How does that apply in the case of a site that changes from single
homed to dual homed to triple homed and back again? I expect this
will be a very common occurrence.

   Brian

---

From: Brian Dickson <[email-masked]>
Date: Mon, 28 Jan 2008 16:30:20 -0500

> requires that you can dynamically do a "reachable match first" lookup 
Yes, this is correct.

However, several of the LISP designs already separate out the "live" 
reachability from "mostly unchanging" mapping information.

So, this is not a *new* requirement, nor is it unique to this concept.

And yes, having the reachability info scale better than the population 
of any numbering system, is important - and possible.
> We already have MIP so no host granualirity would be a completely 
MIP only supports EID host granularity, if there is a "home agent" 
numbered from EID space.

This doesn't provide any way for a site that doesn't already have EIDs 
available without going through the process of acquiring EIDs, managing 
an MIP router, etc.
I.e., not something non-technical folks can do, so it doesn't scale very 
well from a global perspective.

Not that having lots of work for semi-technical IT folks is necessarily 
a bad thing - I'd just rather it be something that is fundamentally 
incapable of being engineered out of the solution space.

I see MIP as orthogonal to LISP, rather than a way of "enhancing" what 
LISP provides. Using MIP for non-mobile entities is just a bad design 
choice, IMHO.

Brian Dickson

---

From: Brian Dickson <[email-masked]>
Date: Mon, 28 Jan 2008 16:44:02 -0500

> will be a very common occurrence.
If the instance of triple homed is really a question of switching which 
second provider is being used,
then I think a suitable question to dig further along this is:

How important is it that while migrating, a site be able to use *all 
three* links, if only the redundancy is critical?

And, how likely is it that the uninvolved link will fail during the 
transition window for the other two links, as well as
one of the other two links failing simultaneously? Would that be any 
worse than if both links failed, before or
after the transition event? Is having the third link available to do a 
fast transition (or fast reversion) adequate
to meet the needs of a site which isn't so concerned with redundancy as 
to operate their own EID infrastructure?

If we can generalize this to being, "It is common operational practice 
to have an overlap period between
the provisioning of one service, and the cancellation of another 
service, and a 'hot' cut-over between those
during the overlap duration", then I think it's okay to not support 
temporary triple-homing.

Making the distinction between full-on triple-homing, and having three 
links, two of which must always be
configured for redundancy, is IMHO a reasonable situation.

When there is one link that doesn't change, and two that are in the 
hot-cut mode (one add, one drop),
the stability and redundancy is quite reasonable with a solution limited 
to N=2. IMHO.

BTW - reminder about the N=2 distinction. I should point out, that the 
"heavyweight" solution without
host granularity, is also available even in N=2. The compromise is, no 
host granularity, and more administrative,
technical, financial, and operational overhead is required.

Brian Dickson