Subject: [RRG] Properties of mapping solutions

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 10 Jan 2008 11:16:06 +0100

On 9 jan 2008, at 20:05, Tony Li wrote:

> Better yet, we should simply morph this into a more general  
> discussion about properties of mapping solutions.

I'll change the subject line accordingly.

> Presumably, the set of identifiers in the world is going to be very,  
> very large.  Simply pushing a full map to everywhere is going to be  
> expensive, both in space and time.  Pulling has latency issues.   
> Reducing the number of places that have a full map seems like an  
> attractive solution, but still leaves the push scalability problem,  
> albeit with one less order of magnitude of an issue.  For the places  
> that have only a cache, how do you deal with cache misses?

> What's the right approach here?  Let's have a conceptual discussion  
> and leave out the mechanisms, please.

Whatever we choose, we'll have to live with the unintended  
consequences. In the case of caching with dropping packets if there is  
a cache miss this will mean tightening the timing of the whole  
mechanism to reduce the number of lost packets from those misses as  
much as possible. It may even be bad enough that the transport people  
are forced to work around dropped TCP SYNs etc.

If we want reachability when there are cache misses, we essentially  
have to create a third infrastructure. (BGP/locators being the first  
and the caching ITR/ETR mechanism being the second.) I used to think  
this was an attractive solution, but now that I've seen the LISP  
variant that does this using GRE tunnels I'm having second thoughts.  
Additional issues are the QoS differences between packets that benefit  
from the cache and ones that don't, the potential for DoS attacks on  
the third infrastructure and the issue that we don't know how large  
the cache is going to need to be.

If we push out the static mapping info (EID prefix -> RLOCs) as well  
as the dynamic mapping info (which RLOCs are reachable) we're  
basically reinventing BGP. It's fairly obvious that we can achieve a  
single order of magnitude better scaling than we have currently for  
IPv4 by working per-AS rather than per-prefix, but the question is if  
we can do much better than that, and if not, whether a single order of  
magnitude is worth the trouble, especially as this only addresses the  
RIB issue and not the FIB issue.

We can also push out the static mapping info but use a pull model for  
the dynamic info. Although this doesn't affect the amount of data that  
needs to be pushed out significantly, it does make this data many  
orders of magnitude less volatile, making RIB processing a lot easier.  
This does import some of the downsides from the pull model, except  
that we can observe that today, most links are up most of the time, so  
we can probably assume that any RLOC that we choose is reachable and  
be correct 98% of the time or more, so there is probably no need for a  
third infrastructure to avoid lost packets on cache misses.  
(Especially considering that a good part of all prefixes isn't  
multihomed, anyway.) This model also requires just a bare minimum of  
signaling between ITRs and ETRs.

Last but not least, any model where the work can be done in parallel  
rather than serially gives us at least a fighting chance to get back  
on the commodity price curve. With some really hard work it's probably  
possible to make a BGP implementation that runs on loosely coupled  
parallel processors, but a protocol designed with this in mind will  
make this much easier. Part of this is that you can make an  
operational tradeoff between bringing the routing information to where  
the packets are and bringing the packets to where the routing  
information is.

--
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: [email-masked] (Noel Chiappa)
Date: Thu, 10 Jan 2008 11:58:28 -0500 (EST)

> From: Iljitsch van Beijnum <[email-masked]>

    >> Simply pushing a full map to everywhere is going to be expensive

My contention is that neither extreme end of the spectrum is going to be the
right place, but rather some place in the middle - probably with (as you
suggest) a number of different mechanism options, for places with different
usage patterns/requirements.

    >> Pulling has latency issues.

Yes, but a well-designed system can minimize them. I spent a *lot* of time
identifying i) a lot of optimizations for CONS which would speed up
resolution, and then ii) figuring out which subset made sense to include in a
first-pass trial deployment.

    >> For the places that have only a cache, how do you deal with cache
    >> misses? ... Let's have a conceptual discussion and leave out the
    >> mechanisms, please.

Depends on whether you can stand the latency of the miss. If 'yes', wait for
the resolution. If 'no', design a mechanism to deliver (inevitably in a
less-efficient way) packets which do not yet have mappings.

I kind of like the multi-cast thing myself, but if we decide it's important to
handle 'no', I'm prepared to go off and spend a month or two exploring the
'alternate delivery mechanism' space thoroughly, as I did with CONS
optimizations.

    > It may even be bad enough that the transport people are forced to work
    > around dropped TCP SYNs etc.

Sorry, but IMO in the general case that's unworkable. A few large content
sites, maybe. But in general, deployed base wins.

    > If we want reachability when there are cache misses, we essentially have
    > to create a third infrastructure. .. I used to think this was an
    > attractive solution, but now ... I'm having second thoughts.

Why? Was is problems with a specific mechanism, or something about the general
concept?

As to the latter, if we are going to i) have caching, and ii) situations where
we can't wait for a cache fill on a miss, we're going to have to have
*something*. I am optimistic that a lengthy examination will find some
relatively clean options.

    > the potential for DoS attacks on the third infrastructure

Yes, DoS - I wish we could just use the 'drop the miscreants in a pot of
boiling oil' approach... :-( I'm not sure the second infrastrucure
(ITR/ETR/mapping) is fully DoS protected yet, although it has definitely been
something that's been thought about to a certain degree.

    > If we push out the static mapping info (EID prefix -> RLOCs) as well as
    > the dynamic mapping info (which RLOCs are reachable) we're basically
    > reinventing BGP.

First, I like the jargon "reachability" for the second thing; it's not a
mapping per se, but rather further information about a particular mapping.
Second, it's a good point that they need to be considered separately (in terms
of where we want to be on the push/pull spectrum with them), in part because
they have different lifetimes. Third, it's not really BGP, because BGP
computes (effectively) entire paths, which is an *even harder* problem.

    > It's fairly obvious that we can achieve a single order of magnitude
    > better scaling than we have currently for IPv4

IPv6 is not really much better, as I suspect people will be as resistant to
changing IPv6 addresses as they have been for IPv4, and for the same reasons.
(I would put the odds of IPv6 adopting EID's as pretty low - just like TUBA,
they think there's too much deployed base - ironic how they both cripple their
chances of success for that 'reason', but I digress...)

    > by working per-AS rather than per-prefix, but the question is if we can
    > do much better than that, and if not, whether a single order of
    > magnitude is worth the trouble

Well, there's a theory that if we get the mapping right, we can do lots more
with it: for *example* (and I stress this is only an example, as process
migration was for EIDs - too bad I didn't see the provider independence angle
for EIDs back when, but that's architecture for you - you don't always see all
of what good architecture will buy for you), we might be able to do host
mobility.

    > especially as this only addresses the RIB issue and not the FIB issue.

Yes, but to the extent we would now effectively have EIDs, renumbering to make
FIBs smaller becomes a lot more viable.

    > the dynamic info.

Yes to the second, but for both, really, it's a numbers game. E.g. if the
chance of something being used *before* it's updated is really high, push is
better. If the chance is low, pull is better. For another, if the chance
if it *ever* being used is low, go pull, otherwise go push. Etc, etc... It all
depends on the actual patterns.

    > we can probably assume that any RLOC that we choose is reachable and be
    > correct 98% of the time or more, so there is probably no need for a

You're talking about cache misses on reachability info here, right? I haven't
heard anyone propose that we need a mechanism to handle that case; the "third
infrastructure" people have talked of is for cache misses on mapping info, I
thought.

    > multihomed, anyway.)

Good point. If those are down, they are down hard.

    > With some really hard work it's probably possible to make a BGP
    > implementation that runs on loosely coupled parallel processors

Umm, let's just get a mapping system deployed, eh? The path-selection we can
go back and look at as a separate sub-system later.

And yes, they need to be independent enough that we can do it separately; if
they aren't that independent, I think that's a poor architecture.

    > Part of this is that you can make an operational tradeoff between
    > bringing the routing information to where the packets are and bringing
    > the packets to where the routing information is.

Although you have an interesting point there.

	 Noel

---

From: Eliot Lear <[email-masked]>
Date: Thu, 10 Jan 2008 21:52:00 +0100

Noel,
> usage patterns/requirements.

I missed the text in the message you are quoting from Tony (it's all 
gone by in a flurry in the last 24 hours), but NERD shows that actually 
pushing the data is not cost prohibitive, using today's numbers.  What 
goes into primary cache memory is a separate question.  On Linksys, I'm 
sure the answer would be "not much".

Eliot

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 10 Jan 2008 16:31:47 -0500 (EST)

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

    > NERD shows that actually pushing the data is not cost prohibitive,
    > using today's numbers

You mean, the computational/communication bandwidth overhead is not cost
prohibitive, I assume? (Actually, now that I think about it, the memory cost
is probably not unreasonable either, particularly if the mapping table can be
kept in DRAM, and recently-used entries cached in faster RAM.)

    > What goes into primary cache memory is a separate question.

Not sure what you mean by "primary cache memory" - is this the same point as
my "cached in faster RAM" above? But you are assuming all ITR's do keep
copies of the entire mapping table, right?

Because there is another axis to 'push', which is 'how much gets pushed';
people often take 'push' to mean 'push the entire table' but of course it's
easy to visualize schemes which e.g. identify highly-used bindings and push
them to everyone, and only use pull on the infrequently used ones.

More complex, yes, but it uses less resources. As I have said elsewhere, it's
like the old "fast, cheap, good" axiom, only this version is "speed,
overhead, complexity: pick any two".

	Noel

---

From: Brian Dickson <[email-masked]>
Date: Fri, 18 Jan 2008 15:59:01 -0500

>> and leave out the mechanisms, please.
Quick question - where do we draw the line between concepts and mechanisms?

E.g. consider the following:

   1. EID existence information derived from searchable whois
      (associated with RIR->LIR allocations and LIR->customer assignments).
   2. EID->RLOC mappings published by end-site in DNS.
   3. EID->RLOC lookups done pro-actively based on set of EID prefixes
      from (1). This produces the static mapping table.
   4. RLOC *un*-reachability distributed as opaque data by LIR at
      aggregation point(s), into BGP.
   5. ITRs use static mapping from (3) plus unreachability from (4) to
      produce dynamic mapping.
         1. dynamic mapping uses unreachability to de-prefer RLOCs,
            rather than suppressing EID->RLOC mappings
         2. static mappings use MX-style preference values for RLOCs for
            TE purposes
         3. dynamic mapping sum statics and dynamic values (1 and 2) to
            produce well-ordered set of RLOCs (per EID of course).
   6. DNS lookups which return RR sets containing EIDs, are used to
      signal cache population with dynamic entries

Is this sufficiently abstract to be "conceptual"?

Does this scale sufficiently well? I think it would not require much new 
work to implement.
The DNS stuff is nearly trivial:

    * In ip6.arpa or in-addr.arpa, at the prefix level to which EID
      delegations are done, overload the meaning of MX (which has no
      sensible meaning in the reverse zone) to be the set of RLOCs for
      this EID prefix, with preference metrics.
    * Include the literal label "eid" with PTR entries for all of the
      RLOCs, pointing to ip6.arpa or in-addr.arpa reverse entries for
      the corresponding RLOC prefixes.
    * In the reverse mapping for the RLOCs themselves, include the
      literal label "rloc" with a PTR to the reverse entry for the EID
      prefix.

    Example zone file (EID reverse zone):
    @     soa (...)
    mx   10   <rloc1>.ip6.arpa.
    mx   20   <rloc2>.ip6.arpa
    rloc    PTR <rloc1>.ip6.arpa.
    rloc    PTR <rloc2>.ip6.arpa.
    (normal hex contents of this nibble of reverse zone)

> basically reinventing BGP.
This is true *only* if the two pieces of information come from the same 
source.

If the RLOC reachability does not come from the ETR, and/or if the 
EID->RLOCs is published some other way, then it looks almost nothing 
like BGP, except that it produces some kind of FIB.
> This model also requires just a bare minimum of signaling between ITRs 
> and ETRs.
I'm not sure that *any* signaling between ITRs and ETRs is necessary, or 
buys anything. It introduces an N^2 amount of state, into something 
which (ideally) scales much better than this.

Brian Dickson

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 21 Jan 2008 08:56:52 +1300

On 2008-01-19 09:59, Brian Dickson wrote:
...
>      (associated with RIR->LIR allocations and LIR->customer assignments).

Why is that an issue, even conceptually? We don't have a conceptual
issue discovering the existence of end-system addresses today.

>   2. EID->RLOC mappings published by end-site in DNS.

(a) Conceptually, I believe we need to think about generic
prefix->prefix mappings; EID->RLOC is the specific instantiation
for one particular scheme.

(b) It certainly isn't given that the mappings will be published
by the end-site. They could be published upstream, most likely by
the transit provider.

(c) Specifying DNS as the "newspaper" to be used is a mechanism.

>      from (1). This produces the static mapping table.

Yes, but you've skipped over how the mapping information is
obtained in a timely manner at the point of lookup. I think
that's the hardest part.

>      aggregation point(s), into BGP.

Why by the LIR in particular? And how is unreachability determined
by the LIR? Is unreachability as seen by the LIR certain to be equal
to unreachability as seen from the point of lookup? The network
isn't isotropic.

>      this EID prefix, with preference metrics.

That's definitely mechanism, and overloading a Mail Exchange record
is definitely a kludge. If DNS is the solution, we should surely
define a new RR type.

   Brian C

---

From: [email-masked]
Date: Sun, 20 Jan 2008 15:28:52 -0500 (EST)

> issue discovering the existence of end-system addresses today.

Exactly - precisely because location and identity are both encoded in the
IP address (IPv4 and IPv6).

And today, the existence is push-published in BGP, as NLRI data.
Because of the nature of next-hop and CIDR, it is by definition searchable.

Transit provider_S_, plural. That plurality introduces the potential for
errors. Having the end site being responsible (arguably with the ability
to outsource), gives control to the entity with an intrinsic interest in
avoiding errors.

It isn't a technical requirement, but helps scaling for both the system,
and for the transit providers.

> obtained in a timely manner at the point of lookup. I think

I would expect that is implementation-dependent mechanism stuff.
This in particular, since it will depend on how it gets used after it is
looked up.

> to unreachability as seen from the point of lookup? The network

The presumption is (and I believe it is a valid assumption) that RLOCs are
assigned by transit providers out of PA space.

So, practically by definition, if PA aggregation is done, then
more-specific reachability within the PA block, *is* isotropic.

(Scalability on the routing space isn't achievable unless more-specifics
are *not* announced as a general rule.)

The two entities who would know about reachability of an RLOC will be the
LIR and the end-site. Either could announce this, so it's an area for
further drill-down. My gut feeling is, if the data gets carried in BGP,
then either the end-site needs something doing BGP announcements (even of
opaque data), or the LIR does the unreachability stuff. I think the latter
is generally prefered, given the global scope of any data in the BGP
system, and the expected wide deployment of this to end-sites.

> is definitely a kludge. If DNS is the solution, we should surely

I agree, long-term. I am merely pointing out, that as a precursor to
requesting IANA code-point assignments of a new RR type, and the
coordination between rrg and dnsext, that proof-of-concept could be
implemented simply by use of MX.

Brian D