Re: [RRG] Separation vs. Elimination

[Robin Whittle <rw@firstpr.com.au>]

Hi Michael,

You wrote (with some of my original text deleted):

>> Here is some feedback on your paper:
>>
>>   Towards A New Internet Routing Architecture:
>>   Arguments for Separating Edges from Transit Core
>>
>>   http://conferences.sigcomm.org/hotnets/2008/papers/18.pdf
>>
>> I agree with your basic premise that a separation scheme is
>> preferable to an elimination scheme.  My main suggestion is that it
>> would have been better if you mentioned Ivip, which is a significant
>> example of a core-edge separation scheme.  Some of the
>> characteristics you ascribe to separation schemes do apply to
>> non-Ivip separation schemes, but not to Ivip.
> 
> This is exactly why we omitted it -- it was a short paper, and Ivip's
> mapping system doesn't quite fit our definition of separation.

I think it fits it well - the edge addresses are removed from the
core routing system.  Ivip is a core-edge separation scheme.

It doesn't matter that Ivip has a faster mapping system which
enables simpler mapping data and simpler ITRs and ETRs, or that it
is not intended to prevent edge devices from sending packets to
devices in the "core".

Ivip's aims in terms of edge-core separation are identical to those
of LISP, APT, TRRP and Six/One Router, with probably exception that
APT aims to eventually prevent edge devices from being able to send
packets to core devices.  At the end of this message, I wonder how
this could be assured - how could a border router allow already
encapsulated packets from ITRs to the interdomain core while
dropping identical looking packets emitted by attacker-controlled
hosts?  Each ITR would need a secure tunnel to the border router.



>> However, only Ivip with OITRDs (Open ITRs in the DFZ) and LISP with
>> PTRs (Proxy Tunnel Routers) are clearly able to support packets sent
>> by non-upgraded hosts.  There is a business plan for OITRDs, but not
>> yet for LISP PTRs.
>>
>>   http://psg.com/lists/rrg/2008/msg02021.html
>>
>> APT can support packets from non-upgraded networks, but for IPv4, as
>> long as there are separate APT islands, and as long as the current
>> /24 filtering of BGP prefixes prevails, then there is no robust way
>> of supporting such packets sent to EID prefixes longer than /24.
>> This significantly limits the usefulness of the system, since many
>> networks would be happy to use one or a few IP addresses, rather
>> than 256.
> 
> In defense of APT, I think you are making a *lot* of assumptions about
> the present and future here which may not hold true. However, that's
> beside the point and I'd like to keep this discussion at a higher level...

I was summarising what I have mentioned in a previous critique of
APT - that in its current formulation, it only supports multihoming
etc. for packets from non-upgraded networks if the EID prefixes are
/24 or shorter:

  APT: no need for islands?  2008-03-12
  http://psg.com/lists/rrg/2008/msg00734.html

I think it is reasonable to assume that many end-user networks will
be happy to use less than 256 IPv4 addresses of SPI (Scalable PI)
space.  (In IPv6, the same argument applies in general - EIDs will
often be longer than the maximum length prefix the BGP system is
configured to recognise, in any given part of the address space.)

With separate APT islands and with the current /24 limit on BGP
advertisements, two separate end-user networks with a /25 which form
a /24 couldn't successfully get packets from non-upgraded networks
as long as they were using separate APT islands.  The problem goes
away if there is only one APT system, which could be achieved by
tunneling APT mapping information between ISPs, in addition to the
current technique of relying on physical links between ISPs.

One of the big differences between separation and elimination is
that at least some separation schemes will, or least aim to, provide
full portability and multihoming support for packets from
non-upgraded networks.

I was just pointing out that I think that only Ivip and LISP with
PTRs do this robustly.  I think APT's approach isn't so thorough.
TRRP aims to do it:

  http://bill.herrin.us/network/trrp-implementation.html

with 6 sticks and 8 carrots.  Six-One Router doesn't provide
portability or multihoming for packets from non-upgraded networks.


>> TRRP has an approach to support of packets from non-upgraded
>> networks, but I recall that it involves various carrots and sticks.
>>
>> Six/One Router doesn't work for IPv4 and doesn't support packets
>> from non-upgraded networks.  I think your paper states or implies
>> that separation schemes support packets (for multihoming and
>> portability) from non-upgraded networks whereas elimination schemes
>> don't.  I think this is not true of all separation schemes.
> 
> In the four paragraphs you wrote above, I think you are focusing on
> specific methods and implementations, whereas our paper is trying to
> argue for the broader idea of separation. Of course, only a properly
> designed realization of separation can achieve all of its benefits.

OK.  Your paper indicates that Elimination schemes can't support
packets from non-upgraded networks - at least that is my
interpretation of (page 4):

   Under Elimination, transit networks can do nothing but wait
   for a unanimous action by all the edge networks before the
   routing table begins to scale.

Perhaps I am reading too much into that statement, but it is
profound benefit of Separation schemes that at least some of them
support packets from non-upgraded networks, compared to none of the
elimination schemes.

That said, I think it is important to point out that this problem of
Elimination schemes - the benefits depending on how many other
networks have adopted it - also applies to some Separation scheme.
In particular, any scheme which can't provide multihoming and
portability for packets sent from non-upgraded networks means that
end-users adopting the system only gain usable, robust, complete,
multihoming and portability after all other end-user networks adopt
the system.  Hence my mention of the limitations of APT's support
for packets from non-upgraded networks, of TRRP's preliminary
arrangements for this, and of Six/One Router's inability to do this.


>> I think your use of "ER" and "DR" in place of "ITR" and "ETR"
>> doesn't achieve anything useful - and that if you use such new
>> terms, you should mention their equivalents in the terminology used
>> in LISP, APT, Ivip and TRRP.
> 
> We are using our own terminology because we find the LISP terminology
> confusing. A lot of people we've talked to (outside of the RRG)
> misunderstand APT because they see that TR stands for Tunneling Router,
> and they understand "tunneling" as the use of a pre-configured tunnel,
> like an ssh tunnel. We felt "encapsulating router" and "decapsulating
> router" were much clearer.

OK - the term ITR and ETR are well established in LISP, APT, Ivip
and TRRP.  However, these may not be the most appropriate terms,
because of the reasonable inference that "tunnels" are stable,
preconfigured and likely 2-way arrangements.  Since the ITR to ETR
data carriage arrangement is unidirectional and is established
without any prior arrangement, "tunnel" is less appropriate.  Now
that Ivip has Forwarding as alternatives to encapsulation, the use
of "Tunnel" is even less appropriate.

However, "Encapsulating" router doesn't suit Ivip's forwarding
arrangement.  Initially I wrote about forwarding with different
terms for ITR and ETR, but it drove me nuts.  On one hand I want to
use informative and appropriate terminology.  On the other hand I
don't want to use different terms from LISP etc. without good reason.


>> Page 2 col 2 para 3
>>
>> You mention LISP, APT, TRRP and Six/One Router, but not Ivip.
>>
>> You describe Six/One Router as using "address rewriting".
>> "Translation" is another term for this - perhaps the preferred term.
>>
>> You might also have referred to:
>>
>>   http://www.firstpr.com.au/ip/ivip/comp/
>>
>> which compares LISP, APT, TRRP and Ivip.
> 
> As I mentioned above, Ivip's mapping service does not fit the definition
> we have in the paper for a mapping system in a separation approach, so
> we felt it would be misleading/confusing to include it. We meant no
> disrespect. =)

OK.  Your definition of Separation - implicitly "core-edge
separation" - is (page 1):

  separating edge networks from the transit core, and engineering a
  control and management layer in between.

This doesn't match Ivip if "separation" means preventing edge
networks from sending packets to core addresses - but LISP, TRRP and
Six/One Router don't attempt to do this, and it is debatable whether
APT (eFIT??) could ever robustly achieve this.

If "separation" means removing the edge address space from the core
routing system, then Ivip matches this description just as well as
LISP, APT, TRRP and Six/One Router.  The differences in the mapping
systems are not relevant to the fact that all these systems achieve
this common "separation" goal.


>> Page 2 col 2 last para - continuing to page 3
>>
>> Your discussion of mapping systems for separation schemes applies
>> only to the non-Ivip schemes.  You assume that the mapping system
>> does not get information to the ITRs in "real-time" and that
>> therefore it contains two or more ETR addresses for every EID prefix
>> ("micronet" for Ivip).  Because of this, and because you assume that
>> the preferences for multihoming service restoration would not change
>> often, you assume that there would only be a mapping change every
>> month or so.
>>
>> Ivip works on completely different assumptions.  Mapping changes are
>> done in real-time, giving the end-user network direct control over
>> the world's ITRs.  This means the ITRs and ETRs are not involved in
>> reachability detection or in deciding how to restore service via
>> another ETR.  Each mapping update pays its way - the user pays for
>> mapping updates.
> 
> Yes, our philosophies differ significantly here. I think we've discussed
> this before, but I don't believe in solving a technical problem (a
> scalable number of updates in the mapping system) with an economic
> solution (pay per update). But that's a whole other can of worms.

I think it is an important difference in the design goals of the
various proposals.

From what you just wrote, I understand that APT's approach to the
technical limits and unfair costs in the current BGP system is to
reduce the number of BGP advertised prefixes and cope with many more
multihomed and portable end-user EID prefixes by handling these with
a "mapping" system, with ITRs, ETRs, Default Mappers etc.

From what you wrote, I understand your solution to the same problems
occurring in the mapping system - overly large numbers of prefixes
and/or updates to the mapping of these prefixes, and the unfair cost
burdens this places on participants in the interdomain routing
system, in this case the ISP in an APT island - is purely a
technical fix.  From that, I guess you mean that the APT mapping
system will be several orders of magnitude more efficient than BGP -
and that there is no arrangement for costs being paid by those who
benefit from the mapping changes, to those who are burdened by these
changes.

In that case, I think the gains APT would provide - the increased
number of end-user prefixes the Internet will be able to handle
relative to whatever it can handle now - is roughly equivalent to
the extra efficiency with which APT manages mapping changes relative
to the efficiency with which BGP handles changed prefix advertisements.

I guess you could get one, two or maybe three or four orders of
magnitude out of this.

The Ivip approach is to provide firstly a more efficient mapping
system relative to BGP - as does APT - but also to technically
structure the mapping system so end-users can be made to pay for
each mapping change.  This enables quite a lot of the mapping system
(not all, but most of it) to be run as a series of businesses.  More
details are in:

  http://tools.ietf.org/html/draft-whittle-ivip4-etr-addr-forw-01


Then, there funding for the mapping system, so there are incentives
to build it, extend it, run it, make it more efficient etc.  This
should greatly extend the maximum number of micronets, updates etc.
the whole system can handle, compared to what I understand is the
APT approach of a more efficient mapping system with costs falling
unfairly on the ISPs, with no backpressure on end-users to reduce
the number of mapping changes or the number of EIDs in the mapping
system.


>> Your description:
>>
>>    LISP-CONS and LISP-ALT build a DNS-like hierarchical overlay to
>>    retrieve mapping data when needed.
>>
>> strikes me as wrong.  Neither has much resemblance to DNS.  ALT is a
>> completely separate network, with its own BGP instance, using a
>> different but parallel address space, for sending mapping queries,
>> which are typically actually traffic packets.  The responses
>> typically come back via the ordinary Internet, rather then the ALT
>> network.  LISP-CONS is no longer being developed, as far as I know.
> 
> Protocols aside, they seem quite similar to me -- in both cases, you
> query a hierarchy of servers, eventually getting the information you
> requested directly from the authoritative source. The major difference
> is that DNS queries start at the root of the tree directly, whereas
> LISP-ALT queries start at a leaf before ascending to the root.

There are other differences which I consider significant, such as
the ALT network being a completely separate network, with routers,
BGP, tunnels etc.  I think these differences are such that
"DNS-like" is an inadequate description.

For instance, DNS queries go straight to the relevant server, via
the Internet.  There often needs to be a query to one server in
order to find the address of another server to send a second query to.

In the ALT system, a single query gets to the appropriate server -
there is no recursion.  Also the query typically is the traffic
packet, so the ALT system functions as an early delivery system,
before the ITR has the mapping for this packet's EID prefix.
Another difference is that there is this whole new network, with its
own BGP system (scaling problems in that too?).  The physical
location of the various routers in this system is likely to be
scattered all over the world, and the "highly aggregated" nature of
the ALT system leads to packets likely cris-crossing continents and
oceans as they traverse from source leaf and branch to trunk and
then to destination branch and leaf.

  http://psg.com/lists/rrg/2008/msg00229.html
  http://www.antd.nist.gov/~ksriram/strong_aggregation.png

I think that to call this "DNS-like" would give readers a
way-to-simple impression of LISP-ALT and its likely problems.


>> Page 3 col 2 paras 2 and 3
>>
>> I am not sure how valuable multipath transport will be, unless there
>> are fancy features built into DFZ routers, which would be costly,
>> hard to debug and manage, and which would only be useful once most
>> or all DFZ routers were upgraded.
> 
> I don't see why DFZ routers need to be involved -- isn't the whole point
> that they don't?

I was thinking of the multipath approach described by Mark Handley
at the Dublin meeting:

  Multipath Transport, Resource Pooling, and implications for
  Routing
  http://www.ietf.org/proceedings/08jul/slides/RRG-2.pdf

Page 20:

    What about Multipath Routing?

      # You can achieve resource pooling using the routing system
        if:

          * Routers can make a choice (at a flow granularity) of
            more than one path for traffic forwarding to a
            destination.

          * The load-balancing between the paths is done based on
            the measured congestion on those paths to that
            destination.

     # This has the same effect of moving traffic away from
       congested paths.

          * It’s harder to make stable.

          * It doesn’t provide resilience for individual flows
            (still need to re-route very quickly).

My perhaps faulty interpretation of this is that DFZ routers would
be identifying different flows within the packets sent from host A
to host B, and sending them via different paths.  For IPv6, this
would require the use of the Flow Label.

In my interpretation of this, the DFZ router would have two or more
paths to the destination network - or at least two neighbours which
both have a path to the destination network.  Rather than sending
all the packets along one path as it does today, the DFZ router
would send some packets of one or more flows along one path and some
packets of other flows along the second path.

What other routers than DFZ routers could do this?

I will check with Mark Handley whether my understanding is correct.

Anyway, in your paper, it might be good to cite prior work on the
multipath approach you illustrate in section 5.


>> I think what you wrote about failure detection is pertinent:
>>
>>    Being able to effectively gauge the status of
>>    multiple paths requires transmitting a large quantity of
>>    data and sophisticated subflow control; not all applications
>>    can continuously send large quantities of data (e.g.,
>>    VoIP connections), and not all end points are suited to
>>    perform complex control (e.g., small sensors).
>>
>> This critique also applies to ITRs trying to do reachability
>> detection in the non-Ivip core-edge separation schemes.  I discussed
>> this in my recent message to Iljitsch.
> 
> I'm not sure what your basis is for this claim -- in APT, for example,
> one data packet from one ER (a.k.a. ITR) to a failed DR (a.k.a. ETR) is
> generally sufficient to discover the failure.

I think you must be relying on receiving an ICMP message either from
some intermediate router than the ETR is unreachable, or from the
ETR that the destination network is unreachable.

I don't think that relying on ICMP messages to detect network
failures is robust.  A failed or flaky part of the network can't be
relied upon to do anything, including successfully sending out ICMP
messages for every packet which goes to some router which has its
next hop in the faulty part of the network.


>> Page 5 col 1 para 2
>>
>> I was unable to find any CIRL references - Google equated this with
>> "circle".
> 
> Ah, it seems the URL was accidentally left out of the bibliography. Here
> it is:
> 
> http://read.cs.ucla.edu/~frost/cirl/

  CIRL: DDoS mitigation in eFIT
  Chris Frost and Mike Mammarella July 13, 2008

> Note that this is very much a WiP. We just cited it as a
> proof-of-concept.

Thanks for this link.  I stand by my critique of basing security
responses on the assumption that an encapsulated packet sent to an
ETR was sent via the ITR whose address is in the source address of
the encapsulating header - the attacker can send encapsulated
packets directly, with any ITR address in the outer header.

In eFIT, perhaps it is impossible for an end-user host to send a
packet to an ETR, in which case my critique would not apply.
However, this is a highly idealised situation in which every
end-user network in the world adopts eFIT-mapped address space and
sits behind a router which refuses to forward any packet from inside
the network to the interdomain core, other than those which are
encapsulated already by ITRs and therefore are addressed to ETR
addresses, which are in the core.

Still, in that situation, how is the border router to distinguish
between a packet it receives from an ITR inside its network, and an
identical looking packet created in a host controlled by the attacker?


>> For the non-Ivip encapsulation core-edge separation systems, any
>> system which relies on the source address in an encapsulated packet
>> is not going to be much use for security purposes.  Indeed it could
>> be a source of further trouble.  Just because ordinary traffic goes
>> through an ITR (and by the way, Ivip allows ITR functions in sending
>> hosts, but not behind NAT) doesn't mean that an attacker would use
>> an ITR.
>>
>> Attackers can get mapping information and send an encapsulated
>> packet to the target, with the source address in the outer header
>> set to whatever they like.  The packet is encapsulated at the
>> attacker's host - it hasn't been through an ITR.  If you have a
>> security system which tries to talk to an ITR and tells it to back
>> off in some way, then this cannot be done securely due to the ease
>> with which any attacker can spoof encapsulated packets with some
>> ITR's address in the outer header.
> 
> Good point, this is definitely something that should be in a threat
> model in future work on blocking bad traffic at ERs/ITRs. But I don't
> see it as necessarily unavoidable.

I will alert Chris Frost and Mike Mammarella to this discussion.

 - Robin


--
to unsubscribe send a message to rrg-request@psg.com 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