Subject: [RRG] Consequences of no renumbering...

From: "Tony Li" <[email-masked]>
Date: Wed, 10 Sep 2008 23:00:15 -0400

Hi all,

So in thinking more about our recent consensus on renumbering, it seems to
me that this helps us prune the solution tree a bit.  In particular:

- For the entire class of 'transport' solutions that we've discussed, it
seems like renumbering would always be required for these solutions.  All of
the obvious transport protocol changes would utilize multiple PA addresses,
and since changing PA addresses would result in a renumbering event, it
seems like these solutions should be avoided.

- For the map-and-encap solutions, there seems like a similar issue.  If we
look at the current LISP transition plan, there is currently a requirement
for sites to renumber once to get into an aggregateable EID space.  

If renumbering is not required, then EID space doesn't aggregate.  If
transition boxes (PTRs) advertised EID space into legacy routing, then it
would imply that there wouldn't be any reduction in prefix count until
transition was wholly complete.  That doesn't seem very practical.

I'm not ready to say that there aren't transition schemes that could get
around this, but these are the issues that I'm seeing.

Comments?

Nomex on,
Tony

--
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: Robin Whittle <[email-masked]>
Date: Thu, 11 Sep 2008 14:09:22 +1000

Hi Tony,

I agree.  The recent rough consensus requiring no renumbering
precludes any practical solution.

You wrote:

> I'm not ready to say that there aren't transition schemes that
> could get around this, but these are the issues that I'm seeing.

I am:

There is no scalable routing system - or transition scheme to a
scalable routing system - which can meet our goals of being
attractive to end-users and generating real scalability benefits if
it is not allowed to require most small end-user networks (all PI
and probably most small PA) to renumber once when adopting the new
system.

  - Robin

---

From: "Tony Li" <[email-masked]>
Date: Thu, 11 Sep 2008 01:02:32 -0400

Hi Robin,

|There is no scalable routing system - or transition scheme to a
|scalable routing system - which can meet our goals of being
|attractive to end-users and generating real scalability benefits if
|it is not allowed to require most small end-user networks (all PI
|and probably most small PA) to renumber once when adopting the new
|system.

One word: translation.

Tony

---

From: Robin Whittle <[email-masked]>
Date: Thu, 11 Sep 2008 17:26:15 +1000

Hi Tony,

> |and probably most small PA) to renumber once when adopting the new

The only translation scheme is Six/One Router, which can't work for
IPv4 and does not provide multihoming for packets sent from hosts in
non-upgraded networks.

(27 words - my personal best!)

  - Robin

---

From: Eliot Lear <[email-masked]>
Date: Thu, 11 Sep 2008 11:38:42 +0200

Tony,
> around this, but these are the issues that I'm seeing.

Sure.  I think we're losing sight of the timetables with which we need 
to work.  I don't see a short term problem.  In fact we could expend 
resources to get us into a good long term steady state.  There are 
obvious limits on how much resources, but the argument to the business 
manager is this: eat some additional memory here and there for now and 
we'll see a tail-off effect (hopefully not too much) later.  The key, 
however, is completing transition.

Eliot

---

From: Scott Brim <[email-masked]>
Date: Thu, 11 Sep 2008 08:12:18 -0400

> around this, but these are the issues that I'm seeing.

Sorry for not having replied on your previous proposed summary of the
consensus before this.  As I believe Robin pointed out several days
ago, I don't think we agreed on simply "no renumbering".  That's too
black-and-white.  The consensus I saw was that we should not adopt an
architecture that assumes site renumbering is easy.  Based on what
network operators have said, once seems okay, and even "rarely" might
be acceptable if other benefits outweigh the cost.

As to whether sites must renumber (at least) once for map-and-encap
systems (actually just the map part), we are still uncovering new
ideas on how to approach all that so I'm not resigned yet.
Renumbering is not required for a mapping system to work, since local
numbers are decoupled from overall topological location.  It might be
required for interworking in the initial phases of deployment.  

But the main point is that afaict the consensus was not just "no
renumbering".  Rather, I think it was that we should not choose an
architecture that assumes it is easy.

Scott

---

From: marcelo bagnulo braun <[email-masked]>
Date: Thu, 11 Sep 2008 14:27:02 +0200

Hi Tony,

One question that i think someone asked but wasn't really captured in 
the consensus call is whether we are requiring no EID renumbering  or no 
locator renumbering or both.

No EID renumbering seems feasible, you can run LISP, HIP, Six/One, 
transport based solutions or some forms of shim6 based on ULAs and with 
some hacks you may get there imho . However, i guess that if we are 
looking to avoid renumbering pain, it won't be enough and you will also 
need to avoid locaotr renumbering.
If that is the case, then ou run out of options very fast.
Translation as you suggest also impose renumbering at least the 
addresses of the translation devices and probably the ACLs of these 
devices will also be locator based so, it is not clear to me how much 
renumbering pain can be avoided.

It may well be that you need to start looking into a completelly 
different direction, like Kriukov et al. compact routing schemes, or 
other forms of flat routing. That would probably provide no renumbering 
at all, but seems a significant shift from current internet.

Regards, marcelo

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 11 Sep 2008 09:14:22 -0400 (EDT)

> From: "Tony Li" <[email-masked]>

    > If we look at the current LISP transition plan, there is currently a
    > requirement for sites to renumber once to get into an aggregateable EID
    > space.

As others have said, this isn't an architectural requirement of any jack-up
scheme (such as LISP); indeed, when I first starting thinking about the
deployment of jack-up schemes, many moons ago, I was assuming no renumbering.
(I recall drawing some pictures and talking at length about what routing
tables would look like in various places during the deployment, implicitly
based on that assumption, but I'm not sure everyone followed what I was
ranting about! :-)

Yes, there are routing issues if you don't renumber, but depending on how you
deploy it (e.g. if you restrict yourself to having a contiguous chunk of the
network doing routing on 'locators' only) those issues can be reduced to
mostly second-order cost/benefit kinds of things (i.e. not 10:1 cost
variances). (Caveat: I haven't looked at the current LISP system for
distributing mapping delegations [ALT?], I'm only familiar with CONS, and
there may be some aggregation issues with that portion of the system too.)

    > transition boxes (PTRs) advertised EID space into legacy routing, then
    > it would imply that there wouldn't be any reduction in prefix count
    > until transition was wholly complete.

In looking at those pictures/messages I mentioned above (it was on the
architecture-discuss list, on Nov 10/11 2006, in the thread "Ok, so what
should we do then?" if anyone cares :-), it becomes clear to me that this
whole issue of 'how is the routing going to operate' is one that really needs
systematic exploration in depth (something I bitched about back then, too -
see the message 'It's the routing, people!' :-).

For instance, although I looked at both having only a single routing plane, in
which 'locators' and 'addresses' mixed (which seems to be the assumption in
some of what you're saying), I spent more time thinking about systems with two
separate routing planes (one for each), and where _not all routers
participated in both planes_ (exactly because, as you point out, otherwise
"there wouldn't be any reduction in prefix count [in any router] until
transition was wholly complete"), examining such issues as 'where, and how,
would routes from one need to be injected into the other'.

I don't propose to do such a systematic exploration in depth in this message,
but I will once again plead for such a systematic exploration - at an
abstract level, to make the fundamental issues clear - of how the routing
would work during the deployment phase (which is certain to be lengthy).

	Noel

---

From: Stephen Sprunk <[email-masked]>
Date: Thu, 11 Sep 2008 09:47:03 -0500

Tony Li wrote:
> So in thinking more about our recent consensus on renumbering, it seems to me that this helps us prune the solution tree a bit.  In particular:
>
> - For the entire class of 'transport' solutions that we've discussed, it seems like renumbering would always be required for these solutions.  All of the obvious transport protocol changes would utilize multiple PA addresses, and since changing PA addresses would result in a renumbering event, it seems like these solutions should be avoided.
>   

I agree.  I don't see any way that would work, though I'm open to 
suggestions if anyone has one.

However, I have some disagreement about some hidden assumptions you 
appear to be making below:

> - For the map-and-encap solutions, there seems like a similar issue.  If we look at the current LISP transition plan, there is currently a requirement for sites to renumber once to get into an aggregateable EID space.
>   

First of all, this problem only applies to sites that _already_ have PI 
space.  One of my goals here is to make multihoming achievable for 
orders of magnitude more sites which currently do not qualify for PI 
space (even with the low bar that has been set).  I discount the first 
renumbering from PA to EID space because they would _also_ have to 
renumber from PA to PI space if the latter were available to them.

Second, in v6, most sites that qualify still have not requested a PI 
prefix yet -- just a few hundred so far out of tens of thousands.  The 
sooner we finish, and PI is replaced with EID, the fewer sites that 
would theoretically have to renumber (unless you count moving from v4 to 
v6 as "renumbering").

> If renumbering is not required, then EID space doesn't aggregate.  If transition boxes (PTRs) advertised EID space into legacy routing, then it would imply that there wouldn't be any reduction in prefix count until transition was wholly complete.  That doesn't seem very practical.
>   

In v6, all existing PI space is in five clearly marked blocks (one per 
RIR).  All it takes to convert the entirety of PIv6 to EID space is a 
redesignation by the IETF, IANA, and/or RIRs and getting those folks (or 
their upstreams) to implement ETRs.  I would prefer that IANA be 
directed to issue a new top-level prefix so that all new EIDs can be 
aggregated into a single route, but that's an optimization for the future.

Lack of aggregation is a serious problem in v4, however.  The vast 
majority of PIv4 space is legacy.  It's also out of a dozen or so 
well-known /8s, and AFAIK there has not been any non-legacy PA 
assignment in those blocks to date.  It's theoretically possible to 
aggregate those /8s into EID prefixes and let non-participating sites 
punch out more-specifics.  It's certainly possible to have the IETF 
direct IANA and the RIRs to not make any more PA assignments in those 
/8s, to reuse any empty space in the existing /8s for new PI 
assignments, and to not mix PI and PA in any /8s allocated to them in 
the future.  (That directive, I think we'd listen to; it's only the 
total ban on PIv6 that we felt justified in ignoring.)

S

---

From: Lixia Zhang <[email-masked]>
Date: Thu, 11 Sep 2008 08:52:16 -0700

I've been in perhaps longest sequence of silence: after falling  
behind, it's so hard to catch up! I'm still mid of the loooong  
renumbering exchanges and attempting to make a summary out of it.

But allow me jump ahead this time:

> seems like these solutions should be avoided.

Just to clarify:

- multipath transport solutions (e.g. like the one Mark Handley  
presented in Dublin), potentially can bring great benefits to users  
and applications.

- as I presented in Dublin, transport solutions can work, orthogonal  
to whether using PI or multiple PA addresses.

- the only thing that seems problematic is an attempt to scale the  
routing system by relying on all edge networks doing renumbering.

> for sites to renumber once to get into an aggregateable EID space.

again let me clarify:

- there are multiple proposals on the RRG table that fall into the  
general map-and-encap direction. In general they do not require  
renumbering.

- LISP people can correct me here, but I believe the renumbering issue  
for ALT is an attempt to system optimization.

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Thu, 11 Sep 2008 08:56:24 -0700

> IPv4 and does not provide multihoming for packets sent from 
> hosts in non-upgraded networks.
> 

LISP-NAT proposes a translation scheme, and can work with or without
PTRs.

-D

> (27 words - my personal best!)

"If I'd have had more time, I'd have written a shorter letter."

-TS Elliot

---

From: Scott Brim <[email-masked]>
Date: Thu, 11 Sep 2008 12:59:55 -0400

> routing system by relying on all edge networks doing renumbering.

I believe all the pure endpoint-based solutions scale routing by
making all addressing hierarchical.  Endpoint-based solutions,
including multipath, still generally expect an endpoint to know its
many addresses, and when a site changes its upstream connections it
needs to reconfigure all of its services and ACLs to deal with the new
addresses.  Ouch.

---

From: Lixia Zhang <[email-masked]>
Date: Thu, 11 Sep 2008 11:04:20 -0700

On Sep 11, 2008, at 9:59 AM, Scott Brim wrote:

> many addresses

2/ knowing many addresses is one way to get there, not necessarily the  
only way

1/ even if one uses many addresses that corresponding to many  
providers, one still does not have to use PA addresses (see my Dublin  
talk)

> and when a site changes its upstream connections it

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 11 Sep 2008 15:18:15 -0700

> - LISP people can correct me here, but I believe the renumbering  
> issue for ALT is an attempt to system optimization.

But ALT doesn't require it. And if you don't get good aggregation of  
EID space, at least it's in a pseudo-control plane and not in the core.

However, with a logical ALT topology, you could take 2 independently  
assigned PI blocks which are allocated each to two sites on the  
opposite sides of the earth and aggregate them by an ALT access-layer  
of ALT routers.

Since you can tunnel anywhere, those sites can tunnel to the same ALT  
router.

Does this make for a good business model, well, that's another story.

Dino

---

From: Robert Bonomi <[email-masked]>
Date: Thu, 11 Sep 2008 20:33:37 -0500 (CDT)

> Subject: [RRG] Consequences of no renumbering...
> Date: Wed, 10 Sep 2008 23:00:15 -0400
>
> Hi all,
>
> me that this helps us prune the solution tree a bit. 

[[  munch  ]]
> around this, but these are the issues that I'm seeing.

Is a re-numbering as painful for a "pure transit" network as it is for an
end-user network?

Postulating -disjoint- address-spaces between 'transit networks', and 'leaf 
networks',  with all 'content' origination/consumption occuring on the
'leaf' networks, is it practical to require the transit network to re-
number *IF*:
   (a) they have (almost) exhausted their current 'transit-space' allocation,
   =and=
   (b) there is no adjacent contiguous block of like size available  to
       allocate to them.

In the 'pure transit' realm, I only see the following places where 
addresses would be used:
   1) loaded in the device interface, itself.
   2) in an 'in-addr.arpa' zone, and the "A' records the 'in-addr' PTR
      records point to.  (also the NS records, obviously)
   3) in 'digital certificates' used to verify identity.
      (This would seem to be solvable, by gettting a 'certificate signing
       certificate' that did -not- specify the IP address, but verified
       identity by other means.  Then  use _that_ certificate to self-
       sign certificates verifying the IP address

Things like VoIP, bittorent, Kazaa (or whatever it's "successor" is this week),
etc, don't originate/terminate _on_ the 'pure transit' network, so there won't
be any 'pure transit' addresses being carried around as 'packet data' from
those things.

Am I missing anything?

---

From: Robin Whittle <[email-masked]>
Date: Fri, 12 Sep 2008 12:06:11 +1000

Hi Lixia,

> general map-and-encap direction. In general they do not require

I think it would be best to clarify what is meant by "renumbering" -
at adoption of the new system or as a regular event during system
operation?

Once a network has some micronet space (Ivip) AKA EID space (LISP,
APT and I think TRRP) there is no renumbering of that space as
different ISPs are used, including when traffic is switched from one
ISP's ETR to another ISP's ETR.  Both involve a mapping change in
Ivip, but that is not in any sense a renumbering of the site's network.

For Ivip or any of the other potentially practical schemes - LISP,
APT and TRRP - to scalably provide full multihoming and portability
support for packets from networks without ITRs, the micronets / EID
prefixes of multiple (ideally thousands of) end-user networks need
to be contained in a single BGP advertised prefix.  In Ivip, this is
called a Mapped Address Block (MAB).  The same requirement exists
for LISP Proxy Tunnel Routers, but there isn't a name for this BGP
advertised prefix which covers many EIDs.

Renumbering to adopt the new system is a once-only change which
could be practical for many end-user networks.  Those with PA space
need to renumber anyway, just to get another ISP or to get
conventional PI space.

I wrote about the prospects of smaller PI networks and all PA
networks renumbering once to adopt the new "Scalable PI" (SPI) space:

  http://psg.com/lists/rrg/2008/msg02355.html

This is for Ivip, but I think the same principles apply to LISP with
PTRs or to however APT and TRRP provide support for packets from
non-upgraded networks.  That support can only be provided by devices
which advertise a prefix in the DFZ.  In order to scale well, they
need to advertise a much smaller number of prefixes than the number
of micronets they are serving.

If you have a thousand existing networks currently in disparate
parts of the address space - PI or PA - and they need to share one
or a few BGP advertised prefixes for LISP PTRs, Ivip OITRDs or
whatever, then it follows that all these networks need to renumber once.

So the statement above is only true of renumbering during the
operation of the new system.  Most networks will need to renumber
once to adopt the new system.

Also, while Ivip has map-encap modes for both IPv4 and IPv6, it is
no longer a purely map-encap proposal.

There are two new Forwarding modes of transporting packets from ITRs
to ETRs without encapsulation:

   ETR Address Forwarding (EAF) - for IPv4
   http://tools.ietf.org/html/draft-whittle-ivip4-etr-addr-forw-01

   Prefix Label Forwarding (PLF) - for IPv6
   http://www.firstpr.com.au/ip/ivip/ivip6/

Ideally, we could upgrade the DFZ routers to support these, so we
wouldn't need the greater complexities and lower efficiencies of
map-encap.  Alternatively Ivip would be deployed initially as
map-encap and transition to Forwarding only once the DFZ routers
were upgraded.

The Forwarding modes don't alter the renumber-once at adoption
requirement.

  - Robin

---

From: "Tony Li" <[email-masked]>
Date: Fri, 12 Sep 2008 01:54:29 -0400

Hi Robin,

|> One word: translation.
|
|The only translation scheme is Six/One Router, which can't work for
|IPv4 and does not provide multihoming for packets sent from hosts in
|non-upgraded networks.

Or, ILNP with NAT.  Or, for that matter, NAT alone.

Tony

---

From: "Tony Li" <[email-masked]>
Date: Fri, 12 Sep 2008 01:54:29 -0400

|Sure.  I think we're losing sight of the timetables with which we need 
|to work.  I don't see a short term problem.  In fact we could expend 
|resources to get us into a good long term steady state.  There are 
|obvious limits on how much resources, but the argument to the business 
|manager is this: eat some additional memory here and there for now and 
|we'll see a tail-off effect (hopefully not too much) later.  The key, 
|however, is completing transition.

When, exactly, would that be?  Right after the v6 transition completes?  ;-)

I suspect that the answer is 'never', in which case LISP is of zero benefit.

Tony

---

From: Eliot Lear <[email-masked]>
Date: Fri, 12 Sep 2008 08:05:12 +0200

Hi Tony,
>   |The key, however, is completing transition.
>
>

Putting aside the fact that LISP folk have offered a translation 
approach to transition, if sufficient numbers are PTRs are deployed 
there is incremental benefit.  However, there is always this issue of a 
tail in ANY transition.  When was the last BGP3 speaker turned off?  Is 
it turned off?

However, you've asked a very simple question: paraphrasing, all other 
things being equal would IT managers prefer not to renumber?  The answer 
of course is yes.  But all other things are not equal, and there are 
other factors as well.  If we were to move quickly and standardize 
approach we could conceivably have our cake and eat it too because it is 
quite likely that EVERYONE is about to renumber once for IPv6.  I am by 
no means suggesting that we tie the transition of this new routing 
technology to IPv6 but merely optimize in a potentially very salubrious way.

Eliot

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Fri, 12 Sep 2008 09:07:35 +0200

hi marcelo, all

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf 
> Of marcelo bagnulo braun
> Sent: Thursday, September 11, 2008 2:27 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: Re: [RRG] Consequences of no renumbering...
> 
> Hi Tony,
> 
> looking to avoid renumbering pain, it won't be enough and you 
> will also need to avoid locaotr renumbering.

it may be suitable to start investigate the compact routing direction. indeed since so far, in any of the proposed approaches, the routing protocols themselves (being all stretch-1 shortest path based) can not scale better than nlogn.

thanks,
-d.

---

From: David Williamson <[email-masked]>
Date: Fri, 12 Sep 2008 09:18:32 -0700

> I suspect that the answer is 'never', in which case LISP is of zero benefit.

There may be significant gains for some sites.  Suppose,
hypothetically, that all of the sites my site normally exchanges
business critical data with are all using LISP (or the solution
d'jour).  If that were the case, I would seriously consider leaving the
BGP4 DFZ, and would withdraw my PI routes from the DFZ, modulo my
direct upstreams.  That's a few less routes of PI space to carry about
for everyone.  Lather, rinse, repeat for other PI sites, and you may
start to see some gain on a global scale.

The exercise of figuring out whether or not all of your business
critical partners are using the same solution as you is non-trivial,
but certainly possible with enough effort.

For other destinations, a default to one of your providers is probably
sufficient.  My site doesn't exchange many packets with somewhereistan,
and those that are exchanged have zero need to be optimally routed.

Having said that, I'm still pessimistic about the reception much of
this work will get in the operator community.  As Eliot notes, we may
need to utilize *more* resources in order to get to a world of better
scaling and fewer resources.  This isn't the most altruistic group of
people on the planet (myself included).  We need to have a clear idea
of why expending additional resources up front is necessary.

In a similar vein to the post about BGP transition - there might still
be a BGP3 speaker out there somewhere.  I'm quite certain that I don't
care.  The tail can be very long, but the vast majority of sites won't
care once the remaining volume in the tail is small enough.

-David

---

From: "Tony Li" <[email-masked]>
Date: Sun, 14 Sep 2008 22:11:53 -0700

Hi David,

|There may be significant gains for some sites.  Suppose,
|hypothetically, that all of the sites my site normally exchanges
|business critical data with are all using LISP (or the solution
|d'jour).  If that were the case, I would seriously consider leaving the
|BGP4 DFZ, and would withdraw my PI routes from the DFZ, modulo my
|direct upstreams.  That's a few less routes of PI space to carry about
|for everyone.  Lather, rinse, repeat for other PI sites, and you may
|start to see some gain on a global scale.

Ok, but you're effectively withdrawing yourself from global connectivity.
You could already do so today through 1918 addresses and tunneling.  Yet you
haven't.

Tony

---

From: "Tony Li" <[email-masked]>
Date: Sun, 14 Sep 2008 22:14:18 -0700

|Putting aside the fact that LISP folk have offered a translation 
|approach to transition, if sufficient numbers are PTRs are deployed 
|there is incremental benefit.

Fair, these issues don't apply to LISP-NAT.  

|  When was the last BGP3 speaker turned 
|off?  Is 
|it turned off?

Poor analogy.  The consequences of a BGP3 speaker being out there only have
an impact on the speaker and its downstreams.

Tony

---

From: "Tony Li" <[email-masked]>
Date: Mon, 15 Sep 2008 10:28:47 -0700

Hi Lixia,

|- there are multiple proposals on the RRG table that fall into the  
|general map-and-encap direction. In general they do not require  
|renumbering.

So let's try to discuss this in full generality.  If we take a m&e approach,
and have some kind of transition that doesn't include translation, how do we
improve aggregation in the underlying routing?

Dino correctly points out that sites can avoid renumbering and advertise
aggregates in the locator space.  This would represent some amount of
savings.  However, this would seem to affect the quality of routing as when
such aggregates are injected back into legacy routing, it would create
stretch/TE issues.  We've seen that folks deaggregate to address these
issues today.  Could we address this somehow?

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 16 Sep 2008 11:17:06 +1200

> |and probably most small PA) to renumber once when adopting the new

Two words: fast mapping.

I missed the bit where it was proved that fast mapping mathematically
requires aggregatable EIDs.

As I said a couple of weeks ago:

However, would a lower estimate, say 2^23
(8 million) prefixes be an issue? If not, why can't we start on the
assumption that we know how to support a map with 8 or 10 million
entries, and have many years to figure out a sparse mapping system
with several orders of magnitude more entries?

     Brian

---

From: Eliot Lear <[email-masked]>
Date: Tue, 16 Sep 2008 09:59:11 +0200

> an impact on the speaker and its downstreams.

My point is simply that while we are all thinking about how to get up 
the hump of the S curve, we also have to be thinking about the tail when 
it comes to the old technology.  In the case of LISP, I think this is a 
natural, because service providers can get out of the business of 
offering BGP peering to their customers, when all their customers need 
to do is turn on LISP.  If that's tied to moving to IPv6, you might get 
your aggregation for PTRs for free.

Eliot

---

From: Scott Brim <[email-masked]>
Date: Tue, 16 Sep 2008 16:12:42 -0400

Excerpts from Noel Chiappa on Thu, Sep 11, 2008 09:14:22AM -0400:
> For instance, although I looked at both having only a single routing
> plane, in which 'locators' and 'addresses' mixed (which seems to be
> the assumption in some of what you're saying), I spent more time
> thinking about systems with two separate routing planes (one for
> each), and where _not all routers participated in both planes_
> (exactly because, as you point out, otherwise "there wouldn't be any
> reduction in prefix count [in any router] until transition was
> wholly complete"), examining such issues as 'where, and how, would
> routes from one need to be injected into the other'.

Just in response to the basic concepts ...

First I don't think there is ever more than one routing plane.  I
think the conceptual key is asymmetry in scope.  As things are now,
routing/forwarding scope is global.  As a site splits off and adopts
map-n-encap, the rest of the Internet is removed from its
routing/forwarding scope, so that in order for a packet to be
forwarded to it a new adaptation mechanism (map-n-encap) must be
invoked ... but everything in the global Internet is still directly
reachable by it.  The scope of the site is narrowed to just the site,
while the scope of the global Internet remains global, including the
site.  

These are not two routing planes.  At the adaptation points (xTRs)
there is a new routing mechanism to allow adapation between different
routing/forwarding *scopes*, but only one routing plane and only one
routing mechanism.  BGP is also used for discovering mapping
authorities in LISP+ALT, but that's a completely different use of a
routing protocol -- it's in support of the Internet's control plane
(mapping), not the Internet's data plane.

Scott

---

From: [email-masked] (Noel Chiappa)
Date: Tue, 16 Sep 2008 18:53:17 -0400 (EDT)

> From: Scott Brim <[email-masked]>

    > I don't think there is ever more than one routing plane.

Well, then there's a problem (although perhaps it's just a terminology issue,
and you mean something different to me from 'a routing plane'). Let me
explain...

With a M+E system in place, the system contains 3 kinds of IPvN addresses.
One set I'll label Ad - old style 'addresses' (to use Ran's suggested
terminology), which have dual location and identity semantics. Another set is
Ae - the EIDs; and the final set is Al - locators/RLOC's.

(To touch on the point of 'what does "routing plane" mean', to me a routing
<thing> which produces paths to an entirely disjoint set of destinations from
those handled by another <thing> is a different plane - even if it uses the
same protocol/code. A routing plane is, after all, nothing but a giant
distributed computation to select paths to a set of destinations. This has
nothing to do what what protocol/algorithm is being used - it's more
fundamental than that.)

Anyway, if we only have a single routing plane (in the sense in which I am
using it), then all routers in the 'core' (i.e. anything other than stub
areas of the network) will have to contain complete sets of Aj, Ae and Al in
the routing tables - in part because they could see packets with any of them
in the destination field, and must be able to correctly forward the packet
towards the appropriate destination.

In other words, deployment of M+E will be of absolutely no help in
controlling the _routing_ overhead - in fact, it will worsen it. Yes, it
might help with sites which want to switch ISP's and/or multihome - but so
will PI. So, without separate routing planes, M+E buys nothing, and will
never happen. M+E will only happen if we can use it to reduce the routing
overhead in the significant parts of the core.

One way in which this could happen is if we have two routing planes, Pe - an
"end-end" plane, which contains paths to Ad and Ae; and Pl - which contains
only locators/RLOC's. (This requires proxy mapping of the entire 'address'
space Ad - if we don't do that, the second plane has to contain Ad and Al.)

The 'converted core' runs Pl, and is _entirely_ surrounded by mapping boxes,
and packets with destination addresses in Ad and Ae are _never allowed in to
that part of the core_ - they have to be M+E'd into Al before they can be
forwarded. The 'uncoverted' part of the core runs Pe.

There are all sorts of ugly practical problems associated with actually
deploying such a system (e.g. the need to map from Al back to Ae at the edge
of the 'converted core'), but I'll stop here before this gets too long and
complicated.

    > I think the conceptual key is asymmetry in scope. As things are now,
    > routing/forwarding scope is global.

Exactly - but unless you are prepared to guarantee that packets with
destination address Ax never appears in a part of the network, you can't drop
the route to Ax in that part of the network.

I don't think such a requirement can be met in an ad-hoc way, not with a
large system - it has to be systemic.

    > As a site splits off and adopts map-n-encap, the rest of the Internet
    > is removed from its routing/forwarding scope, so that in order for a
    > packet to be forwarded to it a new adaptation mechanism (map-n-encap)
    > must be invoked ... but everything in the global Internet is still
    > directly reachable by it.

But if it's not a stub (as mentioned at the start), it cannot forward packets
in the 'right' direction without that larger routing table.

Look, there's a 1:1 mapping (to overload a term, sigh) between _non-stub
areas of the connectivity graph in which non-mapped addresses *can* appear_
and _non-stub areas of the connectivity graph in which non-mapped *routes*
*must* appear_.

So unless one is prepared to guarantee that packets with non-mapped addresses
_cannot_ appear in part of the network, then one cannot drop the requirement
for non-mapped _routes_ in that part of the network.

    > At the adaptation points (xTRs) there is a new routing mechanism to
    > allow adapation between different routing/forwarding *scopes*, but only
    > one routing plane and only one routing mechanism.

I don't care if it is the same protocol or not - that's a level of technical
detail which is irrelevant to level at which I'm trying to think about the
problem - which is entirely in terms of _sets of IPvN addresses_, etc (as
outlined above).

    > BGP is also used for discovering mapping authorities in LISP+ALT, but
    > that's a completely different use of a routing protocol -- it's in
    > support of the Internet's control plane (mapping), not the Internet's
    > data plane.

Well, routing (path selection) is part of the control plane too, but I take
your point - in ALT, BGP is not being used to select paths.

	Noel

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 18 Sep 2008 07:54:12 -0700

> issues today.  Could we address this somehow?

I said that?

You have to be clear which namespace I was talking about. When you say  
"advertise aggregates" you need to say "advertise EID-prefix  
aggregates". Is that what you intended to para-phrase?

Dino

---

From: "Heinrich Hummel" <[email-masked]>
Date: Sun, 21 Sep 2008 20:45:37

>From: [email-masked]

>with several orders of magnitude more entries?

My solution (which I once outlined on this list) does provide such a mapping: The dest. EID is not even evaluated (and btw could therefore be either IPv4 or IPv6 !!!) for doing the forwarding decision.
Instead forwarding is  based on knowing the destination DFZ-router's geographical location ID (square degree geopatch#, square minute geopatch#, square second geopatch#), conveyed somehow (e.g. inside a prepended header, like in LISP). Let's say, a router maintains 3 tables t1 ,t2, t3.
t1 has (90+90) x (180+180) = 64800 elements. t2 and t3 have 60x60 = 3600 elements. Forwarding:
if dest.square degree geopatch# not equal to the one of the current router then
next-hop = t1[dest.square degree geopatch#]
elseif dest.square minute geopatch# not equal to the one of the current router then
next-hop = t1[dest.square minute geopatch#]
elseif dest.square second geopatch# not equal to the one of the current router then
next-hop = t1[dest.square second geopatch#]
else ... /* we are close enough to have a look at the dest. IP address ! Or should we subdivide the square second geopatch once more ? */
Hence it will always be a single table-offset plus eventually 1 or 2 or 3 checks. The dest.IP address needs to be unique just at the destination geopatch. So 4 octets should be sufficient for all times. Billions of billions of users  on earth can hereby even be served.

I did  display how to fill these tables. Meanwhile however I have been progressing substantially,  so that e.g. partition-free topologies at whichever zooming level will be computed, or that this is done without the need of configurational data per node (i.e. its highest zooming level to show up), instead, that pre-given i.e. standardized zooming factors will do, and also, unlike PNNI, that any node will well be surrounded first by strict links, then by loose and looser links, i.e. such that e.g. a node close to the rim of a hemisphere won't be immediately surrounded by most loosest links (no uplinks).

IMO, this is fastest mapping, a side effect from eliminating the need to build prefixes and/or to do caching
in short from eliminating the scalability problem once and forever

Heiner

Heiner