Subject: [RRG] thoughts on the design space 1: the space

From: Jari Arkko <[email-masked]>
Date: Thu, 24 Jul 2008 15:18:22 +0300

Hi,

I wanted to bring up a few thoughts about the high-level design space. 
This is based on something we did as a group exercise in a recent 
Dagstuhl seminar, with Lixia Zhang, Dave Thaler, Bob Briscoe, Christian 
Vogt, Mikko Särelä, Luise Burness, Andreas Windsam, and Wolfgang 
Mandelbrat -- though I'm only speaking for myself in this e-mail. The 
goal of the exercise was to look at the possible solutions and 
understand what impacts they might have on upper layer protocols. This 
is important so that our solutions do not end up impacting negatively on 
applications and user experience. Some of the assumptions upper layers 
have been built on are documented in [1]; I would say that document 
should be on your reading list for Dublin.

Anyway, here's the the basic design space as we saw it:

   http://www.arkko.com/ietf/rrg/designspace_dataplane.jpg
   http://www.arkko.com/ietf/rrg/designspace_mappingreso.jpg

Note that this reflects only two key pieces, what you do on data path 
and how mappings are resolved. There are equally important other aspects 
that are not covered here, such as how mapping verification is performed.

DATAPLANE
========

The root of the design space tree begins with the choice of whether the 
intent is to do efficient routing on a flat space vs. use a small 
aggregatable space and a separate identifier space. An example solution 
in the former category is ROFL. Most of the things discussed in RRG 
belong to the latter category.

The next choice in the aggregatable branch is whether the 
identifier-locator separation goes all the way to the host or not. If it 
goes all the way to the host, we can see different solutions based on 
which layer the design is at. Shim6, Six/One, and HIP are IP layer 
solutions, whereas multipath TCP would be a transport layer solution.

If on the other hand we do not take the separation to the hosts, there 
will be some device in the network that divides the network into two 
parts, the edge and core. In the core we employ aggregatable addressing, 
and edge networks and hosts run on identifiers. Many of the RRG 
solutions are in this design branch. We can see different solutions 
based on what operation is performed when you cross the edge-core 
boundary. Pure Lisp without draft-lewis is an example of a solution that 
employs encapsulation. The other main solution type is translation. 
However, translation come sin different variants:

(1) One sided translation where you always translate your edge addresses 
to core addresses. No one needs to reverse the translation, which makes 
this approach easy to deploy as it does not assume anything about other 
side's deployment. Essentially, you place a NAT on your network border 
and you can forever whatever addresses you are using inside without any 
impact to others.

(2) Two sided translation where you always undo the translation on the 
other side. This only works if the other side has upgraded to the same 
system. While conceptually different from encapsulation, the end host 
sees a very similar result from two sided translation and encapsulation. 
Possibly the only difference is what happens to path MTU.

(3) One or two sided translation, such as Six/One Router. Here you do a 
reversible translation if the other side has upgraded, and otherwise 
employ one sided translation.

MAPPING RESOLUTION
===============

I only draw a very simplistic diagram for this. But basically, the host 
based designs like Shim6 can operate without any extra mapping 
resolution system, albeit this limits their functionality a bit. For 
instance, all addresses have to be in DNS for initial connect to 
succeed, if there is a failure condition.

Designs that do use a mapping resolution system come in two variants: 
one that always attempts to hold the entire space, and one that runs a 
cache.

Jari

[1] http://tools.ietf.org/html/draft-thaler-ip-model-evolution-01

--
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: "Flinck, Hannu (NSN - FI/Espoo)" <[email-masked]>
Date: Mon, 28 Jul 2008 12:56:51 +0300

Hello Jari and others

Very good summary diagram indeed. 

I think that we are still missing something from the high-level design
space though. I do not know how to accurately or even descriptively name
this category of approaches but there is a possibility to build on
aggregation inside the network and between the ASs.
 
Examples of such approaches that are not visible in the diagram of yours
are for example following

http://tools.ietf.org/html/draft-li-ispac-00

http://www.caida.org/publications/presentations/2003/internetworking03/a
toms.internetworking03.pdf

The geographic aggregation based solutions discussed on this mailing
list would belong to this category.

All the above proposals share in common the aspect that prefixes are
aggregated and the participating ISPs/ASs need to collaborate to harvest
the benefits.  

For the shake of completeness we should also recognize that such
approaches exits.   

Best regards
Hannu

---

From: Robin Whittle <[email-masked]>
Date: Wed, 30 Jul 2008 10:43:54 +1000

Hi Jari,

Regarding your diagrams:

The Encapsulate branch is the location not just of LISP, but of APT,
Ivip and TRRP.

Here is a fuller version of the middle and right branches:

       Push the full table               Pull mapping as
              /  \                       needed to the ITR
             /    \
            /      \                          LISP-ALT
           /        \                         TRRP
          /          \
         /            \
   To the ITR      To full database
                   Query Servers and
   LISP-NERD       perhaps some full
                   database ITRs

                   (Hybrid Push-Pull)

                        APT
                        Ivip

LISP-NERD ITRs initiate the download of mapping updates, such as via
HTTP, but this is still regarded as "push".

You wrote:

> DATAPLANE
> ========
>
> The root of the design space tree begins with the choice of
> whether the intent is to do efficient routing on a flat space vs.
> use a small aggregatable space and a separate identifier space. An
> example solution in the former category is ROFL. Most of the
> things discussed in RRG belong to the latter category.

Yes, but I am wary of the use "space" in this discussion.  The
map-encap proposals, and Six/One Router (and the original host-based
Six/One) do not create a separate namespace for identifiers vs
locators.  These are two different uses of an IP address, but the IP
addresses are within the one namespace:

   Not separate namespaces: Loc-ID-separation, map-encap etc.
   http://psg.com/lists/rrg/2008/msg01637.html

> . . .
>
> Pure Lisp without draft-lewis is an example of a solution that
> employs encapsulation.

I understand from this that you are referring to LISP without the
"LISP-NAT" aspect of:

  http://tools.ietf.org/html/draft-lewis-lisp-interworking

> . . .
>
> Designs that do use a mapping resolution system come in two
> variants: one that always attempts to hold the entire space, and
> one that runs a cache.

As I depicted in the extensions to your diagram, there are important
distinctions between the various map-encap proposals which are not
properly covered by the above statement.

LISP-NERD has every ITR gain a copy of the full database, so there
is no caching whatsoever.

With LISP-ALT and TRRP, all ITRs are caching ITRs, gaining their
mapping information from a single global query system.  (With
consequent delay and reliability problems, resulting in delayed or
dropped initial packets.)

APT and Ivip are different from the other map-encap proposals in
that they both maintain one or more local (typically within the
end-user or provider network) full database Query Servers.  These
get the full mapping database, by full push - though the techniques
for doing this for APT and Ivip are very different.  APT's query
servers (Default Mappers) are also ITRs.

In Ivip, the full database query servers are not ITRs, but there may
be one or more full databases ITRs at the same location.

In both APT and Ivip, most encapsulation is done by caching ITRs and
these always get their mapping quickly and reliably from a local
full database query server.  This means these systems have no
problem with delay of initial packets, as is a problem for LISP-ALT
and TRRP.  Ivip has two optional elements: caching ITR functions in
sending hosts (not behind NAT) and local caching query servers,
between caching ITRs and the full database query servers.

3 months ago I did a detailed comparison of the map-encap proposals,
involving 23 questions:

  Comparing LISP-NERD/ALT, APT, Ivip and TRRP
  http://www.firstpr.com.au/ip/ivip/comp/

There are some areas where it is not complete, particularly for
TRRP, but this page lists the most important commonalities and
distinguishing features.

 - Robin

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 31 Jul 2008 15:58:00 +0100

Be warned: long message.

Jari: I largely agree with your conclusion on the solution direction.

However, I think the NERD data format can significantly improved.

On 24 jul 2008, at 13:18, Jari Arkko wrote:

> The next choice in the aggregatable branch is whether the identifier- 
> locator separation goes all the way to the host or not. If it goes  
> all the way to the host, we can see different solutions based on  
> solutions

One issue with these solutions, and presumably with any solutions that  
exposes the locators to the hosts, is that it doesn't solve the  
renumbering issue.

We probably want to avoid exposing locators to the end-user site in  
any shape or form to make sure that the end-users won't be tempted to  
put locators in their configurations and thus make it hard to renumber  
locators, requiring us to come up with an id-loc-loc split in the  
future.

> whereas multipath TCP would be a transport layer solution.

Note that multipath TCP doesn't necessarily have to know the actual  
locators: it could be good enough to just indicate "please use path 1  
for this packet" vs "please use path 2 for this packet".

On 24 jul 2008, at 13:21, Jari Arkko wrote:

> The caching design has a number of issues:
> - If packets are dropped while cache entries are being fetched,  
> there may be deterministic loss
> - If packets are routed through a secondary path while cache entries  
> are being fetched, there may be deterministic delay

Unfortunately, the loss isn't deterministic in its timing so the  
sending host doesn't know when to resend its packets. There are also  
not any RTT measurements that could provide guidance with that  
decision. So the choice is between relatively long delays or sending a  
large number of packets, creating a SYN flood of sorts on the  
destination.

When routing initial packets through the mapping system, this would  
allow for denial of service against the mapping system. This can be  
remedied for the most part with rate limiting, but this increases the  
average delay before a mapping can be optained; possibly to the degree  
of unusability.

On 24 jul 2008, at 13:23, Jari Arkko wrote:

> First, I am not at all convinced that we actually HAVE to employ a  
> cache for the forwarding lookup.

I think we tend to operate under the unstated assumption that a single  
router must be able to resolve mappings for the full set of  
destinations. I don't think that's necessary. If one big box is  
expensive to build, it makes sense to use multiple smaller ones, that  
each handle part of the destination name space. As long as we build  
the mapping system such that it's easy to direct different mappings to  
the appropriate router or encapsulating device, we should be able to  
get parallelism benefits when scaling up.

On 24 jul 2008, at 14:20, William Herrin wrote:

> But we already know negative acknowledgments can't be made to generate
> and return reliably during an outage event. In any operational system,
> we get unexpected routing loops or a firewall blocks the way or a
> router malfunctions or the network is congested or something else
> happens so that the packet is silently dropped without a NAK.

> That's why we detect outages through the absence of positive
> acknowledgment instead.

Right. So we apply a positive acknowledgment mechanism between the  
tunnel/translation endpoints. Perhaps you can ask Jari if he has  
designed one in recent years.  :-)

In other words: I think that the shim6 REAP protocol can be applied  
here. REAP is very light-weight when there is either no data or  
bidirectional data. In shim6 it runs between the hosts in question,  
but it could be made to run on the translators or encapsulator/ 
decapsulator.

I.e., we do push for the static information and pull for the volatile  
information.

On 25 jul 2008, at 19:39, Olivier Bonaventure wrote:

> The only case where you would detect problems with mapping are when  
> a single host is opening a single TCP connection. In this case, the  
> SYN packet will be delayed by the mapping. Note that using the DNS  
> also causes such a delay...

No, in the normal case you shoot off a DNS request and then you  
continue when you get the reply. So there is a delay, but you get to  
proceed immediately when the required information is available. With a  
cache miss in the data plane, you lose a packet and then you have to  
retransmit at some point. There is no way to determine what the right  
time is to retransmit, so either you'll be retransmitting too  
aggressively, which means the destination gets multiple copies of the  
packet, or you wait longer than necessary and the user experience  
suffers.

---

From: Robin Whittle <[email-masked]>
Date: Fri, 01 Aug 2008 11:37:23 +1000

Hi Jari,

Further to my recent message 02028, I suggest another modification
for your diagram:

Please add a third branch under "Core-Edge Separation":

     IPv6 Flow Label Forwarding

     FLOWv6

which is the name of my new proposal:

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

Although it is only applicable to IPv6, and although it requires
modest changes to DFZ routers (but not to the BGP protocol), I think
it is a much more attractive solution than map-encap or translation.
 There appear to be no PMTUD or header checksum problems.  The
packets are not made any longer and there is no address rewriting.

Also, I expect it would significantly reduce the FIB workload of DFZ
routers when handling packets addressed to the new type of address
space for end-user networks.

There is no great urgency making a scalable solution for IPv6.  If
something like FLOWv6, probably with a different name, is developed
to the RFC stage by 2012 then router firmware updates could be
widely deployed by 2014 - by which time the rest of the system,
including the mapping system, could be developed and ready to go.

  - Robin

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 02 Aug 2008 19:56:52 +1200

Jari,

Some time ago we discussed whether a hierarchical view of
the options is sufficient, and I know some of us (including me)
concluded that it isn't, and that we really need a facet-based
view. I think that hierarchies such as you have drawn tend to
conceal similarities. But if you stick to hierarchies, I think
you need at least one more, taking the view from the upper layer
protocols. So I think we need a view like this too:

          Application
       _______|_______
       |             |
     Path-aware    Path-unaware
       |             |
                   Transport
             ________|________
             |               |
           Path-aware     Path-unaware

etc.

     Brian

---

From: Jari Arkko <[email-masked]>
Date: Sat, 02 Aug 2008 13:00:41 +0300

Brian,

> protocols. 
Yes, that's right and I agree with your characterization of 
app/transport awareness as well.

I do realize that the hierarchical models are very simplistic.

Jari

---

From: Scott Brim <[email-masked]>
Date: Thu, 07 Aug 2008 08:45:27 -0400

>   http://www.arkko.com/ietf/rrg/designspace_mappingreso.jpg

I disagree that host-based approaches never need mapping.  These two
dimensions -- where the function is done and whether it needs mapping or
not -- are orthogonal.  You can place a mapping function in a host just 
as easily as you can place it in a border router.  This also implies 
that Lixia's "separation/elimination" distinction is more effective 
than "in host / at edge".

There are a number of hybrid possibilities in "push/pull".  See
draft-rrg-taxonomy-00 and the arguments Dave Thaler made on the old
architecture list.  For example, you can push an index but pull
mappings.  You can push mappings differently in space (treating some
locations as special, or pushing them partway) and time (differently at
different times of day).  So just "push/pull" as a distinguisher doesn't 
help enough.

On 7/31/08 10:58 AM, Iljitsch van Beijnum allegedly wrote:
> We probably want to avoid exposing locators to the end-user site in any 
> shape or form to make sure that the end-users won't be tempted to put 
> locators in their configurations and thus make it hard to renumber 
> locators, requiring us to come up with an id-loc-loc split in the future.

And when you explose locators within the local network at all, you 
probably require them to be used in network management.  To me this says 
that an 8+8-style approach that zeroes out the "glop" part of an address 
is better than one that replaces a globally routed prefix with a locally 
routed one.

> each handle part of the destination name space. As long as we build the 
> mapping system such that it's easy to direct different mappings to the 
> appropriate router or encapsulating device, we should be able to get 
> parallelism benefits when scaling up.

Right, this is a reasonable approach for a site that has too much 
diverse traffic to use cache effectively.  It doesn't mean that other 
sites couldn't use cache.  An effective architecture will allow a 
diversity of approaches at the edge.

Scott

---

From: Jari Arkko <[email-masked]>
Date: Thu, 07 Aug 2008 16:32:10 +0300

Scott,

> than "in host / at edge".

I don't recall if I said that host-based approach _never_ need mapping.
It seems possible to construct mechanisms that can live without one.
Shim6 and multipath TCP, for instance. However, even in these cases
having a mapping system would enable the hosts to do more. For instance,
in Shim6 you have to rely on application failover to another locator
during initial contact (which may be slow) and certain unidirectional
failure cases are unresolvable.

So yes, I agree that host-based approaches may also employ a mapping
function.

> different times of day). So just "push/pull" as a distinguisher
> doesn't help enough.

Also true. I didn't want to imply that push/pull is a binary choice.
There was only so much tree structure that I could draw in the given
amount of space and time I had for doing the graphs. But the push/pull
choice is really a continuum. As we discussed previously, even systems
that I would classify is pure push-based from a mapping perspective
would probably still employ some failure detection mechanisms and
negotiation with the peer network to deal with the choice of ITRs and
ETRs. (Because handling their dynamic failures at the mapping system
level would probably make the system non-scalable.)

Jari

>> One issue with these solutions, and presumably with any solutions
>> that exposes the locators to the hosts, is that it doesn't solve the
>> renumbering issue.
>>
>> put locators in their configurations and thus make it hard to
>> renumber locators, requiring us to come up with an id-loc-loc split
>> in the future.
>
> probably require them to be used in network management. To me this
> says that an 8+8-style approach that zeroes out the "glop" part of an
> address is better than one that replaces a globally routed prefix with
> a locally routed one.
>
>
>> I think we tend to operate under the unstated assumption that a
>> single router must be able to resolve mappings for the full set of
>> the mapping system such that it's easy to direct different mappings
>> to the appropriate router or encapsulating device, we should be able
>> to get parallelism benefits when scaling up.
>

---

From: Scott Brim <[email-masked]>
Date: Thu, 07 Aug 2008 10:54:15 -0400

Got it.  Thanks.  As usual the problem was just that the diagrams
sacrifice a lot of substance in order to represent things simply.

A facet-based approach would be great but I don't know how to do that.

Scott