Subject: [RAM] Critical routing questions, and how to proceed

From: [email-masked] (Noel Chiappa)
Date: Fri, 8 Dec 2006 11:41:34 -0500 (EST)

> To keep this from getting too long, I'll send out a separate message in
    > a couple of hours (just on RAM) giving a little more detail on the
    > points I think RAM needs to work on

OK, so here's the promised message. First come a few things on which I think
agreement has been reached, and then I get to ones which are still open.

When I look at what the problem seems to be (according to the various
presentations), it seems to be growth in the size of the routing table (with
dynamics of routing table entries coming in second). The two main drivers of
growth seem to be i) multi-homing, and ii) general entropy and lack of
aggregation. Is this correct?

The multi-homing clearly has to be handled by use of multiple routing-names,
and identity/location separation. Is that generally agreed on?

Whether that separation happens through widescale deployment of mechanisms
above the basic internetworking layer (e.g. SHIM6 or HIP), or through what
I've been calling the "jack-up" model (inserting a new internetworking layer
underneath the existing one, and turning existing IPvN addresses into things
that are mostly identity-names), remains to be seen. (Although that's a
critical question to decide, I don't think it has a lot of impact on the
routing questions; although it is true that jack-up assumes a new
routing-name namespace, which answers question 1 below with a "yes", and
forces us to immediately move to question 2.)

So here are a number of further open questions that come to mind.

- 1. Assuming that growth through multi-homing is controlled, is general
entropy in the routing tables so bad that we need to somehow move to a
routing-name namespace which has more hierarchy, and in which less entropy is
allowed (i.e. it's more purely connectivity-based)? In other words, even if
we could deploy HIP/SHIM6/whatever, is the entropy in the IPvN namespace
going to be so big that in the not-too-distant future we will no longer be
able to do path computations using names from the space? Bluntly: do we have
to deploy a new namespace for routing-names? 

- I will leave aside less-critical questions like i) the syntax of that new
namespace (i.e. do we recycle an existing syntax), ii) what routing
algorithms we use to compute paths in that new namespace, etc, for the
moment, and get to the one that's really troubling me:

- 2. If we do have a new namespace for routing-names, then how does the
interoperability work? (This is some of what I was pondering with those
diagrams I drew.) I think we more or less have to inject old routing-names in
the new routing plane, but do we then wind up going from the frying pan to
the fire, where we have even *more* destinations to track?

My suggestion is that someone (you, David?), organize a small telecon to try
and come up with a coherent, organized "list of discussion points" to be
covered on RAM, and that someone (you, again?) then tries to guide the list
through those points in a organized and productive way, rather than simply
letting the e-conversation ramble off in a totally unguided way.

	Noel

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 8 Dec 2006 19:56:09 +0100

El 08/12/2006, a las 17:41, Noel Chiappa escribió:
> able to do path computations using names from the space?

maybe a related question would be: how many of the bgp routing entries 
today are due to multihomed sites and how many are due to more 
specifics being announced for TE reasons? i think there are some 
reports out there with this info... anyone has a pointer?

Thanks, marcelo

---

From: Jarno Lähteenmäki <[email-masked]>
Date: Fri, 08 Dec 2006 21:04:31 +0200

For IPv4 see:  http://www.cidr-report.org/
For IPv6 see: http://www.cidr-report.org/v6/

Regards,
--> Jarno Lähteenmäki

---

From: John Leslie <[email-masked]>
Date: Fri, 8 Dec 2006 15:30:53 -0500

Commenting on just this one issue:

Noel Chiappa <[email-masked]> wrote:
> presentations), it seems to be growth in the size of the routing table
> (with dynamics of routing table entries coming in second).

   This list exists because folks complained about the growth of the
routing tables.

   I agree this growth needs to be moderated; but if the issue were
_only_ the memory to hold routing tables, I'd tell the folks to stop
whining and hire people with experience in central-processor design.
There are a _lot_ of tricks used there to effectively manage large
memory requirements.

   I do not believe that is the only issue, however. Route churn is
a problem which cannot be fixed with that bag of tricks; and the
route churn problem depends on the table size.

   As mobility (inevitably) becomes more common, the need for real-
time changes in forwarding paths to end-users will increase the
demand for real-time changes in routes chosen. This is the pressure
I believe we most seriously have to moderate. (Before you ask: No
attempts to outlaw such changes can be successful, IMHO.)

   Bottom line: I agree we need to reduce the pressure leading to
increases in the size of routing tables at the "backbone".

--
John Leslie <[email-masked]>

---

From: "Spencer Dawkins" <[email-masked]>
Date: Fri, 8 Dec 2006 14:46:36 -0600

Hi, John,

> increases in the size of routing tables at the "backbone".

???

I don't attend Mobile IP working group meetings these days, but the whole 
point of Mobile IP WAS to let you send IP traffic to someone who's not in 
the "right place", based on IP address and routing tables, by using 
tunneling encapsulation to present routers with outer IP addresses that ARE 
topologically correct. I don't understand how increased use of tunneling 
would show up as route churn.

One of us is confused. Could you say more about this?

Thanks,

Spencer

---

From: Eliot Lear <[email-masked]>
Date: Fri, 08 Dec 2006 21:04:09 +0000

> attempts to outlaw such changes can be successful, IMHO.)

I agree with Spencer on this one.  With the exception of Connexion I 
know of no other applications of BGP for mobility, and it certainly does 
seem to be fitting the square peg in the round hole, when MIP and MIPv6 
exist.

Therefore, let us assume for the moment that we have two classes of use 
cases:

    * Multihoming
    * Traffic Engineering

One useful pointer would be a paper that analyzes the churn in the 
routing system and attempts to determine how much of that churn is 
useful at different points in the network.  In other words, are we 
hiding information sufficiently well to attain the stated goals for the 
two cases above?  I work has been done on this in the past, but I can't 
find the pointer.  Another way of putting this: before we march forward 
on architectural changes, are we sure we fully understand what is 
causing the pain points?

What are the exacerbating circumstances?  If we say, for instance, that 
the core routing table is O(256k) and growing at a rate of 30% per year, 
if we were to reduce that growth rate to 5% per year, would we have 
solved a problem?  In short, if we are to take Vince's and Dave's 
presentations to heart, the problem is NOT that we will hit a wall, but 
rather that we ARE hitting a knee.  How far back to we have to pull to 
get into the middle of the pack (c.f, Rogers Adoption curve)?  If we 
pull back to whatever that rate is within the core, are we going to get 
hit from other sides, like say carrying customer IGP information within 
BGP for 2547 VPNs?

In short, what is the required reading here?

Eliot

---

From: John Leslie <[email-masked]>
Date: Fri, 8 Dec 2006 16:17:22 -0500

> and identity/location separation. Is that generally agreed on?

   I think we agree; but I worry whether we all mean the same thing by
those words.

   What I think that means is that there needs to be a routing and
forwarding structure which can deliver packets to the same node via
paths which differ in the last hop (or more); and that there needs
to be some function which allows the sender (or its agent) to
determine the locators (routing-names) of those alternate paths.

   (I'm expecting to get flamed for that -- but it's really pointless
to settle on nice-sounding words if we can't agree what they mean.)

> I've been calling the "jack-up" model (inserting a new internetworking
> layer underneath the existing one, and turning existing IPvN addresses
> into things that are mostly identity-names), remains to be seen.

   Those are not the only possibilities -- even in the short-term. It's
quite reasonable to design around interface boxes, and have their
translation function be gradually integrated into operating systems.

   We should be careful how we introduce changes intended as short-term
fixes. Most of the folks that will need to adopt them don't want to
listen to lectures on architecture.

   Indeed, we'll probably need most folks to think of them as "improved
NAT boxes" or "improved office routers". ;^)

> (Although that's a critical question to decide, I don't think it has
> a lot of impact on the routing questions; although it is true that
> jack-up assumes a new routing-name namespace, which answers question 1
> below with a "yes", and forces us to immediately move to question 2.)

   We _definitely_ don't want to be selling this as a "new routing-name
namespace"!

>      entropy in the routing tables so bad that we need to somehow move
>      to a routing-name namespace which has more hierarchy, and in which
>      less entropy is allowed (i.e. it's more purely connectivity-based)?

   IMHO, this need is fairly immediate -- I expect problems within five
years if we don't, and five years is about as fast as we can hope to
deploy it.

> In other words, even if we could deploy HIP/SHIM6/whatever, is the entropy
> in the IPvN namespace going to be so big that in the not-too-distant
> future we will no longer be able to do path computations using names from
> the space? Bluntly: do we have to deploy a new namespace for routing-names? 

   Actually, that's a different question. IPv6 comes with very strong
hierarchy if we just can slow down the pressure to end-run it. HIP
and/or SHIM6 _could_ help slow that pressure; but neither can hope for
universal deployment fast enough. (Perhaps they could become part of
the bag-o-tricks in those "improved office routers"?)

> - I will leave aside less-critical questions like i) the syntax of that
> new namespace (i.e. do we recycle an existing syntax), ii) what routing

   Agreed.

>      interoperability work? (This is some of what I was pondering with
>      those diagrams I drew.) I think we more or less have to inject old
>      routing-names in the new routing plane, but do we then wind up
>      going from the frying pan to the fire, where we have even *more*
>      destinations to track?

   Good question!

   Ideally, the interoperability works seamlessly: "old routers" in the
forwarding path don't have to change anything, getting their forwarding
tables for the "new namespace" the same way they get "old namespace"
routes.

   IMHO, if we get sufficient deployment, aggressive flap-damping can
reduce the routing-table size faster than we need to add "new" routes.
> 
> My suggestion is that someone (you, David?), organize a small telecon
> to try and come up with a coherent, organized "list of discussion points"
> to be covered on RAM, and that someone (you, again?) then tries to guide
> the list through those points in a organized and productive way, rather
> than simply letting the e-conversation ramble off in a totally unguided
> way.

   Noel is asking a lot here -- perhaps too much.

   For the time being, I suggest that Noel simply posts the "discussion
points he thinks would be helpful, and anyone who disagrees explain to
Noel in private email what's wrong with them.

--
John Leslie <[email-masked]>

---

From: John Leslie <[email-masked]>
Date: Fri, 8 Dec 2006 16:47:34 -0500

Spencer Dawkins <[email-masked]> wrote:
> I don't attend Mobile IP working group meetings these days, but the
> whole point of Mobile IP WAS to let you send IP traffic to someone
> who's not in the "right place", based on IP address and routing
> tables, by using tunneling encapsulation to present routers with
> outer IP addresses that ARE topologically correct. I don't understand
> how increased use of tunneling would show up as route churn.
> 

   Well, I'm sure _I'm_ confused. ;^)

   Tunneling has a number of problems (which I won't go into). But it
doesn't _by_itself_ increase route churn.

   Consider air travel. It's common for folks to travel to different
continents. Their mobile device _should_ get an IP address on the
continent they've traveled to. Their dispatch point is likely still
on the continent they came from. They're pretty sure to want to exchange
packets with hosts on the continent they're on. Tunneling no longer
seems so attractive...

   All the "solutions" that come to mind raise questions of security
and privacy. I foresee pointy-haired bosses insisting "just fix the
routing!!!".

   Some folks just don't appreciate the subtle beauty of our work...

---

From: Dow Street <[email-masked]>
Date: Fri, 8 Dec 2006 14:02:34 -0800

I agree with John (I think).

We should not artificially scope the "Internet" for which we're  
designing a new routing system to the current set of wireline links  
managed by commercial ISPs.  Instead, try to imagine a network with  
several orders of magnitude more devices, many of them mobile  
(meaning wireless links and ad-hoc topology).  Pieces of the  
"infrastructure" may be mobile as well, and connectivity back to a  
central "core" is not guaranteed.  For example, two cars on the  
highway with an IP capable link should be able to exchange data even  
if neither can access the core.  If you include this whole scope of  
connectivity scenarios then the "fixed waypoint" model of MIP or NEMO  
breaks down quickly and you have to solve it in routing.  In other  
words, support for mobility/nomadic behavior should be a fundamental  
consideration in the architecture, not an add-on feature.

It is fine if we come to the consensus that the full scope of fixed  
ISP core, MANET, ad-hoc community WIFI, personal networks, etc.  
cannot be accommodated in a single architecture.  But, that decision  
should be due to limitations of technology, not limitations of  
imagination.

R,
Dow

---

From: John Leslie <[email-masked]>
Date: Fri, 8 Dec 2006 17:05:32 -0500

> seem to be fitting the square peg in the round hole, when MIP and MIPv6 

   Agreed... But from where I sit I see an awful lot of square pegs...

> Therefore, let us assume for the moment that we have two classes of use 

   Multihoming _should_ become more common. At the least, we must
expect it to rise as the number of businesses connected rises.

   Traffic Engineering should be pretty independent of anything we do.
The things I can think of to improve traffic engineering without adding
routes are out of scope for this list. (Hmm... I may have to eat those
words, but not now...)

> useful at different points in the network.

   Agreed. Alas, I'm not aware of such a paper.

> In other words, are we hiding information sufficiently well to attain
> the stated goals for the two cases above?

   I seriously doubt it (but I'd be happy to read actual studies).

> Another way of putting this: before we march forward on architectural
> changes, are we sure we fully understand what is causing the pain points?

   No, of course not!

> solved a problem?

   Good questions!

> How far back to we have to pull to get into the middle of the pack
> (c.f, Rogers Adoption curve)? If we pull back to whatever that rate
> is within the core, are we going to get hit from other sides, like
> say carrying customer IGP information within BGP for 2547 VPNs?

   I like to believe there's a way to reduce demand for increasing
routes, rather than just increasing costs. I definitely would expect
to get hit from other sides if we try to solve this by increasing
costs.

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Fri, 8 Dec 2006 18:26:08 -0800

i agree with this one, of course:
if it was only the routing table size,
i.e., no churn caused by dynamics,
then the first slide of
http://www.caida.org/publications/presentations/2006/dima_ietf67_scalability_routing/
says :)
--
There exist routing algorithms such that even
if all of 2^128 IPv6 'nodes' are completely de-
aggregated (i.e., all IPv6 addresses are used
as flat IDs), the 'DFZ' routing tables still
contain less than 128^2 ~ 16,000 entries
(~1000 entries for IPv4)
--
dima.
http://www.caida.org/~dima/

> -----Original Message-----
> From: John Leslie [mailto:[email-masked]] 
> Sent: Friday, December 08, 2006 12:31 PM
> To: Noel Chiappa
> Cc: [email-masked]
> Subject: [RAM] Critical routing problems
> 
>

---

From: Tony Li <[email-masked]>
Date: Fri, 8 Dec 2006 20:39:46 -0800

> There are a _lot_ of tricks used there to effectively manage large

Ummm....  been there and done exactly that.  I've got bad, bad news  
for you.  They think we're in trouble too.  They've looked at this  
and think it's a serious issue.

Tony

---

From: Pekka Nikander <[email-masked]>
Date: Sat, 9 Dec 2006 12:21:48 +0200

Noel Chiappa wrote:
> When I look at what the problem seems to be ..., it seems to be  
> growth in the size of the routing table (with dynamics of routing  
> table entries coming in second). The two main drivers of growth  
> seem to be i) multi-homing, and ii) general entropy and lack of  

I've been told that traffic engineering is another major factor.   
However, I have to admit not understanding what people mean with it.   
(A good reference would help.)

> The multi-homing clearly has to be handled by use of multiple  
> routing-names, and identity/location separation. Is that generally  
> agreed on?

I agree, but my reasons may be different than yours; see the end of  
this message.

John Leslie interpreted Noel's statement as follows:
> paths which differ...; and that there needs to be some function  
> which allows the sender (or its agent) to determine the locators  
> (routing-names) of those alternate paths.

I agree with this description.  To me, the notion of *primarily*  
doing the mapping at the sender but allowing the mapping to be  
delegated to an agent is an important one; see below.

Noel continued:
> Whether that separation happens through widescale deployment of  
> mechanisms above the basic internetworking layer ..., or through  
> what I've been calling the "jack-up" model ..., remains to be seen.

These seem to be the basic architectural choices, given the practical  
constraints.

However, one particular problem here is that people seem to see here  
more architectural choices that there are.  For example, the one that  
John Leslie proposed ...

> It's quite reasonable to design around interface boxes, and have  
> their translation function be gradually integrated into operating  
> systems.

... is in my opinion just a perhaps-good transition path.  Hence,  
from the 30000 feet high architectural perspective, having such  
"interface boxes" does not architecturally differ from the primary id/ 
loc separation approach (akin-to HIP/SHIM6/whatever).  It just  
represents a particular intermediate deployment technique towards a  
full id/loc separation.  [A thorny issue in any such proxy scheme is  
security, i.e., delegation.  With public keys it is easy to solve;  
without public keys the problem seems harder to solve.]

[I agree with John Leslie's comments on who to market such the change.]

> So here are a number of further open questions that come to mind.

I don't have any informed opinion on your two questions; I'm here to  
learn in those respects.

I do agree that organising this discussion is needed, as opposed to  
the more freely ranging discussion at arch-d.  Personally, I'd even  
be ready to accept strict moderation, if needed.

---

What follows is a piece of architectural argumentation why I think  
that multi-homing is best handled by using multiple routing-names, as  
opposed to e.g. using compact routing.  This may be a slight  
digression on this list and belong more to arch-d; I'll try to be  
very brief.  If a longer argumentation is needed, perhaps we should  
take that to arch-d?

As yet another starting point, I find the findings in compact routing  
very interesting (see e.g. Dima's presentation).  Based on them (e.g.  
the BC algorithm with stretch of 1.01 for Internet ASes), the bad  
news is on slide 20 of Dima's presentation:

> The algorithms are essentially static
>
> - Topology pre-processing (pre-computation) costs are not considered
>
> - Distributed implementations are possible, but the bounds for the  
> number of messages they need to generate in order to process a  
> topology change are not considered

This leads to me _believe_ that perhaps _time_ is a more fundamental  
problem here than space.  That is, apparently we could compress the  
routing tables quite small, given the current network structures, but  
we cannot do that fast enough.  In other words, if we had a static  
network, we would not need multiple-routing names to handle multi- 
homing.  In still other words, due to constraints on the real-life  
dynamics of the network vs. computational requirements of today's  
space-efficient representations and algorithms, it seems plausible  
that using multiple routing-names is a reasonable piece of a solution.

BTW, the same argument applies even more to mobility; there the time  
scales are typically even smaller than with typical multi-homing and  
I don't see any reasonable way of handling those time scales with  
routing at the global level.  But that's another discussion that IMHO  
does not belong to this list but more to arch-d.  I'd just remind  
people, as recently discussed at arch-d, that Mobile IP and NEMO like  
anchor-based solutions are more hacks mandated by the lack of proper  
name spaces in the architecture rather than good architectural  
solutions.

Finally, as I stated in arch-d, I believe that there are about half a  
dozen architectural issues  in the current situation where a proper  
identifier / locator separation would help.  Multi-homing and  
mobility are only two of those.

--Pekka Nikander

---

From: "Bound, Jim" <[email-masked]>
Date: Sat, 9 Dec 2006 06:44:46 -0500

Point to Note is several Mobile IP optimizations avoid tunnels
completely. I believe tunnels will not be required for mobility when it
becomes so pervasive it will impact the operators. 

I do believe it exacerbates routing churn because it will require
operators to carry potentially more routes that are from different
prefix addresses thus has an aggregation affect.

/jim

> From: Spencer Dawkins [mailto:[email-masked]] 
> Sent: Friday, December 08, 2006 3:47 PM
> To: [email-masked]
> Subject: Re: [RAM] Critical routing problems
> 
> Hi, John,
> 
> > time changes in forwarding paths to end-users will increase 
> the demand 
> > for real-time changes in routes chosen. This is the 
> pressure I believe 
> > we most seriously have to moderate. (Before you ask: No attempts to 
> > outlaw such changes can be successful, IMHO.)
> >
> I don't attend Mobile IP working group meetings these days, 
> but the whole point of Mobile IP WAS to let you send IP 
> traffic to someone who's not in the "right place", based on 
> IP address and routing tables, by using tunneling 
> encapsulation to present routers with outer IP addresses that 
> ARE topologically correct. I don't understand how increased 
> use of tunneling would show up as route churn.
>

---

From: Peter Sherbin <[email-masked]>
Date: Sun, 10 Dec 2006 16:36:30 -0800 (PST)

Now we are getting somewhere. Thank you Noel for championing this. For routing
consider the following (provider's hat on):
1. When providers merge a new network becomes a collection of ASNs. Reaching a
single ASN takes years because of re-numbering of end customers.
2. Two providers splitting the assets of the third. One gets a core and another
takes the edge. ASN goes with the core. The second provider faces re-numbering of
all acquired customers.
Both 1. and 2. are current cases worth tens of millions and a lot of people go
through a lot of pain trying to resolve them.
Hence a provider's requirement to the new routing is to allow free move of PI
addressed edge networks between ASs.

Thanks,
Peter

> letting the e-conversation ramble off in a totally unguided way.

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

---

From: John Leslie <[email-masked]>
Date: Tue, 12 Dec 2006 19:02:30 -0500

> (A good reference would help.)

http://www.oreilly.com/catalog/bgp/chapter/ch06.html

> ... is in my opinion just a perhaps-good transition path.

   I didn't mean it as "different", exactly: rather as an umbrella
not limited strictly to one side of the proffered choice.

> [A thorny issue in any such proxy scheme is  security, i.e.,
> delegation.  With public keys it is easy to solve;  without public
> keys the problem seems harder to solve.]

   Clearly that issue is real. Several partial-solutions come to mind.
This deserves discussion; but I'm not sure we're ready to discuss it.

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 13 Dec 2006 17:21:15 +0100

Sorry to be a couple ofd days behind the wave...

> determine the locators (routing-names) of those alternate paths.

The problem I'm having with this relatively simple view of id/loc is
that I see a lot of practical evidence that the distinction between
id and loc is context dependent. I've been trying to write this up
in a coherent way and haven't quite succeeded yet, but if it's correct,
it implies that same bit string may need to function as an ID during
part of a packet's lifetime, and as a locator during another part.

Having added that confusion to Noel and John's formulation, I'd also
observe that paths may or may not differ in the last hop; the point
is that they differ somewhere, and that is easier to engineer
if they use different locators.

      Brian

---

From: "tom.petch" <[email-masked]>
Date: Thu, 14 Dec 2006 10:48:07 +0100

----- Original Message -----
From: "Brian E Carpenter" <[email-masked]>
To: "John Leslie" <[email-masked]>
Cc: <[email-masked]>
Sent: Wednesday, December 13, 2006 5:21 PM
Subject: Re: [RAM] Critical routing questions, and how to proceed
> > determine the locators (routing-names) of those alternate paths.
<snip>
> if they use different locators.
Using multi-homing to achieve high availability, then I disagree with both
formulations.  What is needed is a different last mile, on the grounds that that
is where most failures occur (at least last time I saw any data).  Choosing a
different provider/telco is a good start but may not be enough since they can
share the last mile and (parts of) the node feeding it.  The best solution I
saw, some time ago, was one provider coming in through fibre, the other through
a radio link.  But even without that, I think the focus should be on having a
different provider.

A suitable addressing architecture is then to have the same 'address within
site' with the AS number (or similar) differentiating the providers.

Tom Petch