Subject: [RRG] Abstraction of problem space

From: Brian Dickson <[email-masked]>
Date: Wed, 09 Jul 2008 17:48:20 -0400

I've been following the discussions on ID, locater, id-loc split, etc., 
with a lot of experience in the ISP address space/routing/aggregation field.

Here's my observation:

There is a reason that IPv4 PI space *is needed* along with PA space.
And, there is a reason that there was backlash against the original GSE 
proposal.
And, there is a reason that those issues won't and can't go away. They 
are one and the same.

Simply put, there is *not* a simple (strict) hierarchy in the 
provider/customer and peering ecosystem.
And, the "locator" and "identifier" in this abstract environment needs 
to be able to accommodate change.
Someone can move up, or down, the food chain, as it were, and establish 
new (or eliminate old) relations in that space.

And, specifically, an entity's apparent role needs to be able to be 
ambiguous, simultaneously being at more than one level in the food 
chain, and simultaneously having more than one "profile".
Especially when considered over a non-trivial period of time, i.e. the 
lifetime of the entity.  (By "entity" we can mean anything with a 
routing policy, be it an ASN, ISP, site, host, or whatever.)

I fear that too many ideas being discussed, even in relatively abstract 
terms, don't take this into consideration, or are optimized for 
instantaneous state ("snapshot").

And it is this aspect of the Internet that is particularly difficult to 
accommodate, since it fundamentally makes aggregation (and thus scaling) 
very difficult.

Basically, scaling requires "layering", e.g. aggregation, or 
indirection, or other similar techniques.
But, a dynamic location in the food chain, automatically means that we 
need the *ability* to routinely handle "layer violations".

I think drilling down on this, providing means to incorporate such 
violations *into* the addressing/identifier/locator/mapping system, is 
the way forward.
Not including this in any solution, is for us to be chasing our tails, 
or producing interesting recommendations that will not yield a solution 
that can be deployed universally.
Not handling (intrinsically, elegantly, scalably) layer "violations" 
means not meeting the requirements given to the RRG.

BTW - the ability to take a piece of IPv4 PA space, and start announcing 
it as if it were PI space, is an example of the kind of thing that needs 
to be supported.
Changing the role of a "piece" of the Internet, without renumbering.
This needs to be possible without knowing ahead of time, *which* piece 
of the Internet it will be, that does this.
It should be universally possible, and at the same time scale well, and 
(ideally) work on (some/many/most) existing (classes of) hardware.

IMHO.

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: "Tony Li" <[email-masked]>
Date: Wed, 9 Jul 2008 15:03:34 -0700

Hi Brian, 

|And, specifically, an entity's apparent role needs to be able to be 
|ambiguous, simultaneously being at more than one level in the food 
|chain, and simultaneously having more than one "profile".
|Especially when considered over a non-trivial period of time, i.e. the 
|lifetime of the entity.  (By "entity" we can mean anything with a 
|routing policy, be it an ASN, ISP, site, host, or whatever.)
|
|I fear that too many ideas being discussed, even in relatively 
|abstract 
|terms, don't take this into consideration, or are optimized for 
|instantaneous state ("snapshot").

I guess I'm not understanding your concern sufficiently.  An entity that
changes its role in a locator/identifer split architecture is able to change
its addressing at least as easily as it does today.  

Can you please be more specific?  

|BTW - the ability to take a piece of IPv4 PA space, and start 
|announcing 
|it as if it were PI space, is an example of the kind of thing 
|that needs 
|to be supported.

In a locator/identifier architecture, you only advertise locators into
routing.  Whether you are an end site or a ISP is irrelevant.  There's no
need for the distinction between PA and PI, and frankly, the PI mode should
simply be eliminated to maximize aggregation.

|Changing the role of a "piece" of the Internet, without renumbering.

Without renumbering seems like an unnecessary and contradictory requirement.
One of the role changes that you might want to support is the migration from
having addresses within an upstream prefix to having a global, unaggregated
prefix.  Any such change is going to require renumbering *if you want to
maintain aggregation*.  Building in mechanisms that explicitly support
deaggregation is simply shooting ourselves in the foot.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 9 Jul 2008 17:21:05 -0700

> BTW - the ability to take a piece of IPv4 PA space, and start  
> announcing it as if it were PI space, is an example of the kind of  
> thing that needs to be supported.

So Brian, the decoupling that Loc/ID split gives you is attractive.  
And if a site decides to use PA space as an EID-prefix, let's say  
while it is still connected to the provider that owns it. If the site  
decides to discontinue contract with the provider, gives back, say the  
locator the CE box has assigned to it, what do you think should happen  
to the PA block?

That is:

1) Do you lose EID address portability in this case because a site  
decided to use PA space? And therefore doesn't get the renumbering- 
avoidance benefit of Loc/ID split.

2) The service provider is willing to give up the space, which means  
it routes only for a small part of this space (the locator space) and  
not the entire larger space where EID-prefixes would be allocated out  
of?

Some of the struggles that can make LISP much more efficient is to  
look at an address and tell from an allocation bits, if it's EID  
versus RLOC space. Then you can interwork LISP sites with non-LISP  
sites much more efficiently. Easier to do with IPv6 but we may  
struggle with IPv4 because EID-prefixes could come out of all kinds of  
allocations including PA space.

I would be interested to hear what SPs have to say about this.

Dino

---

From: Brian Dickson <[email-masked]>
Date: Thu, 10 Jul 2008 13:05:39 -0400

Dino Farinacci wrote:
> decided to use PA space? And therefore doesn't get the 
> renumbering-avoidance benefit of Loc/ID split.
>
> not the entire larger space where EID-prefixes would be allocated out of?
>

I think this turns on the question of, "Must an EID prefix be routable 
and routed?".

If an EID is not routed, it doesn't need to meet certain requirements 
that prefixes have to have, to be "routable".
Specifically, that a prefix must be of a certain minimum size (e.g. /24 
in IPv4, /64 or even /48 for IPv6).

And, if EIDs are not routed, they can be allocated in a unique fashion 
from the get-go, without needing aggregation, and possibly using 
otherwise unusable address blocks (e.g. class E in IPv4, 240.0.0.0/4).

However, if EIDs need to be routed, then existing constraints on 
prefixes apply.
In which case, the answers are:
1) Yes, you lose portability, and
2) Even if this is the case, the "hole-punching" in aggregates continues 
to drive up the cost of routing, by further fragmenting the address 
space and bloating the routing table(s).

I agree that interworking for LISP is a big issue, and I don't see a 
good solution short of widely-deployed proxies for 
otherwise-unroutable/unreachable prefixes.

The cost issues (asymmetrical costs - pushing some of the cost of 
reaching LISP sites onto third parties, by way of ITR/ETR infrastructure 
needed) are relevant, but only so far as LISP (and LISP-like) solutions 
are concerned.

What I'm driving at is, I don't think we've yet found ways of making 
mapping scale well enough, and that looking at the mapping in more 
abstract ways may be a useful place for investigation for clean-slate 
approaches.
E.g. topological and/or geographical inter-domain equivalents to "not-so 
stubby areas", may be where we should be looking for ideas.

Brian

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 11 Jul 2008 00:24:41 -0700

>> while it is still connected to the provider that owns it. If the  
>> site decides to discontinue contract with the provider, gives back,  
>> say the locator the CE box has assigned to it, what do you think  
>> should happen to the PA block?
>>
>> That is:
>>
>> 2) The service provider is willing to give up the space, which  
>> means it routes only for a small part of this space (the locator  
>> space) and not the entire larger space where EID-prefixes would be  
>> allocated out of?
>>
>> struggle with IPv4 because EID-prefixes could come out of all kinds  
>> of allocations including PA space.
>
> I think this turns on the question of, "Must an EID prefix be  
> routable and routed?".
>
> If an EID is not routed, it doesn't need to meet certain  
> requirements that prefixes have to have, to be "routable".
> Specifically, that a prefix must be of a certain minimum size (e.g. / 
> 24 in IPv4, /64 or even /48 for IPv6).
>
> And, if EIDs are not routed, they can be allocated in a unique  
> fashion from the get-go, without needing aggregation, and possibly  
> using otherwise unusable address blocks (e.g. class E in IPv4,  
> 240.0.0.0/4).

I don't see it that way at all. So let me say first off, EIDs must not  
be routed in the underlying network or we are defeating one of the  
main purposes of the Loc/ID proposals.

Second, it's a question of address ownership and not routing. The SP  
owns the block even though it doesn't route the block because it is  
transitioning to a Loc/ID split environment.

> 2) Even if this is the case, the "hole-punching" in aggregates  
> continues to drive up the cost of routing, by further fragmenting  
> the address space and bloating the routing table(s).
>
> good solution short of widely-deployed proxies for otherwise- 
> unroutable/unreachable prefixes.

Well we have two solutions in draft-lewis-lisp-interwork-01.txt  
(coming out soon, -00 has existed for a while). But that wasn't the  
question.

> reaching LISP sites onto third parties, by way of ITR/ETR  
> infrastructure needed) are relevant, but only so far as LISP (and  
> LISP-like) solutions are concerned.

If you have seen the above draft, do you think Proxy Tunnel Routers  
(PTRs) can be monetized. Rather than focusing on the cost, could we  
focus on a revenue opportunity?

Dino

---

From: Brian Dickson <[email-masked]>
Date: Sat, 12 Jul 2008 11:37:49 -0400

> Can you please be more specific?  

I'll try.

What I was thinking about was the PE/CE model of some solutions.

If a CE entity, for whatever reason, needs to become a PE, what happens 
then?

Currently, this would involve an entity with PA space from its upstream, 
having to get PI space and renumber.

Renumbering can be very time consuming and painful, and is thus a 
barrier to entry.

It may be the case that some proposed models (or solutions) don't make 
this any worse, but don't make it any better.

I'm suggesting that we give this consideration in identifying solutions 
to scaling, given that we are talking long term,
which necessarily involves the long term for all of the users of the 
resulting architecture.

> simply be eliminated to maximize aggregation.

Yes, I understand the locator part of the loc/id split being all PA.

I was thinking about the identifier portion of the split, and whether 
scalability on the combined system
can benefit from aggregation, and if so, whether and how isolated 
portions of the EID space can be
deaggregated at arbitrary boundaries.

> deaggregation is simply shooting ourselves in the foot.

I think this is one of those areas where some of the subtleties involved 
require great care in making distinctions,
and perhaps even better terminology.

Aggregation depends on two things:

    * Addresses of "things to be aggregated" being suitably close
    * Topology permitting aggregation to occur without changing path
      selection policy

If we consider "longest match wins" logic, we can get benefits from 
aggregation even when more-specific prefixes
continue to be part of the solution.

For example, having covering aggregates (permitting us to suppress a 
vast majority of covered prefixes) and also having
more-specific prefixes (which constitute prefixes whose attributes 
differ from the covering aggregate), lets us reduce the
number of prefixes, without necessarily reducing the number of prefixes 
to "1" (for the given range of prefixes).

The fact that such covering prefixes can be nested, means that even 
messy, complex prefix+policy combinations can be
significantly reduced.

What matters most, is that aggregation is possible, and that for any 
location in the topology, that aggregation reaches
a level where the resources (especially the FIB) required are not 
unreasonable.

If the above criteria can be met, while allowing localized deaggregation 
that does not impact global aggregation, then
the deaggregation itself becomes mostly moot.

Here are some specific examples, and specific observations:

    * If an addressing scheme is primarily based on geographic
      information (e.g. latitude/longitude), then:
          o the further away a region is, the more likely aggregation
            over the regions' prefixes is possible
          o the immediate (local to a router) aggregation ability
            depends primarily on the number of egress links
          o while the number of prefixes over which aggregation may
            occur is a function of local conditions, the local diversity
            means aggregation is "self-similar":
                + the aggregation ratio is likely no worse, and may
                  improve, as the number of prefixes increases locally
    * If aggregation is performed locally during the mapping of RIB ->
      FIB, RIB size is less of a concern
    * Aggregation can be performed in multiple stages, in multiple
      locations; aggregation is always a monotonically decreasing function
    * If addressing is geographic, rather than topological (PA),
      aggregation can occur to a much larger degree, all the way down to
      a single "default" covering aggregate
    * The major concern with aggregation is not so much the generation
      of covering aggregates, as much as it is about the suppression of
      more-specifics
          o If suppression of more-specifics occurs primarily at the RIB
            -> FIB boundary, then PROXY aggregation itself becomes a
            reasonable mechanism for generating covering aggregates

One possible example solution, based on the above, is as follows:

    * EIDs are assigned geographically
    * Locators are assigned topologically (PA blocks from providers)
    * Aggregation occurs both on locators (PA space as it crosses
      provider boundaries), and on EIDs
    * EID->Locator mapping is done with routing
    * Every EID must have a next-hop that is a Locator
    * The proxy aggregation that occurs, covers sets of {EID->Locator}
      routes with one or more aggregate routes, [EID->Locator(ME)],
      where each Locator(ME) is the address of the router that performed
      the aggregation
    * Proxy aggregation and announcements of aggregates, needs to honor
      routing policy (specifically, ensuring that the customer vs peer
      vs transit provider relationship is not masked by aggregates
      and/or suppression of more-specifics)
    * ASBR routers will very likely need many more prefixs than non-ASBRs
    * ASBR FIB size will likely depend on both local out-degree,
      diversity of peer tiers, and diversity within each tier
          o aggregation should be inversely proportional to diversity
    * By using routing *as* the mapping function, there are several
      immediate benefits:
          o backward compatibilty is possible
          o incremental deployment is feasible
          o compatibility with existing hardware is automatic
          o no additional network elements are strictly necessary
          o no encapsulation means no MTU issues
          o no rewriting packets means no performance impact
          o all of the important changes can be handled in the control plane
          o by partitioning the routing space into EID and Locator,
            differential rules for prefix size can be maintained with
            relative ease
          o any other advancements that occur in routing protocols (esp.
            BGP) result in immediate benefits in this solution space

I know it goes a long way down one specific path (geographic addressing) 
that has yet to be suitably described, but I think the potential 
benefits are significant.

I'll discuss the details on aggregation with multiple nested covering 
aggregates in a separate thread.

Brian