Subject: [RRG] Separation vs. Elimination

From: Dan Jen <[email-masked]>
Date: Fri, 19 Sep 2008 15:36:06 -0700

Hi all,

We have published a paper comparing the two major approaches
discussed on the RRG regarding routing scalability: separation and
elimination.  We believe that the proposals discussed on the list can be
placed into either of these two categories.  The paper goes on to argue
why separation is a better direction than elimination when trying to
achieve routing scalability.

The separation approach involves separating edge networks from core
networks, taking edge prefixes out of the routing tables.  Map & Encap
schemes such as APT, LISP, and Ivip fall into this category.  So do
translation schemes such as SixOne.

The elimination approach eliminates the use of PI addresses,
moving edge networks into aggregatable PA blocks.  Transport layer
solutions fall into this category, as well as Shim6.  

The paper will be presented at the upcoming Hotnets VII workshop.  It
can be found here:

http://conferences.sigcomm.org/hotnets/2008/papers/18.pdf

Agree?  Disagree?  Questions/Comments welcomed.

Dan Jen

--
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: Michael Menth <[email-masked]>
Date: Sat, 20 Sep 2008 23:01:20 +0200

Hi Dan,

I read the paper and liked it. Very clear and to the point!

Just one comment. The terms "separation" and "elimination" do not really 
correspond to each other as the first term points to the solution and 
the second term to a result. Elimination of longer prefixes from BGP 
routing tables by multi-homed end nodes corresponds to hiding these 
prefixes by routing separation. I hope this makes clear what I mean.

Best regards,

Michael

-- 
Dr. Michael Menth, Assistant Professor
University of Wuerzburg, Institute of Computer Science
Am Hubland, D-97074 Wuerzburg, Germany, room B206
phone: (+49)-931/888-6644, fax: (+49)-931/888-6632
mailto:[email-masked]
http://www3.informatik.uni-wuerzburg.de/research/ngn

---

From: Steven Blake <[email-masked]>
Date: Sat, 20 Sep 2008 22:42:25 -0400

> Agree?  Disagree?  Questions/Comments welcomed.

The statement "A common requirement of all the separation solutions is a
mapping system that associate an edge prefix with the corresponding
                             ^s
transit addresses." on page 2 is false.  GSE, for instance, requires no
such mapping.

Regards,

// Steve

---

From: Dan Jen <[email-masked]>
Date: Sat, 20 Sep 2008 20:52:35 -0700

Hi,

Thanks for the comments.  Response inline.

> prefixes by routing separation. I hope this makes clear what I mean.

I think I understand your comment.  We attempted to have both terms
point to solutions to scalability. 'Elimination' solutions attempt to
solve the scalability problem by eliminating the USE of PI prefixes by
edge networks.  'Separation' solutions attempt to solve the scalability
problem by still allowing PI prefixes to be USED, but to separate such
prefixes from core routing.  It's true that separation solutions
ELIMINATE PI prefixes from appearing in the bgp routing tables, but when
we used 'elimination' we were referring to eliminating the USAGE of PI
prefixes altogether.  I hope that explains the rationale behind our
chosen terms.  Let us know if there are any other suggestions for
improvements.

Dan Jen

---

From: He Yan <[email-masked]>
Date: Sat, 20 Sep 2008 23:10:38 -0600

> transit addresses." on page 2 is false.  GSE, for instance, requires  
In GSE, isn't there a similar mapping between ESD and RG?
Correct me if  I am wrong.

Thanks,
He Yan

---

From: Dan Jen <[email-masked]>
Date: Sat, 20 Sep 2008 22:29:30 -0700

> transit addresses." on page 2 is false.  GSE, for instance, requires

Well, I would say that there is still a mapping, but it is just embedded
in the DNS record.  When you resolve a url, you get the edge prefix as
well as the RG that maps to it.  When edge sites switch providers, they
have to update these mappings in their dns authoritative servers.

Dan Jen

---

From: Steven Blake <[email-masked]>
Date: Sun, 21 Sep 2008 11:23:46 -0400

On Sat, 2008-09-20 at 23:10 -0600, He Yan wrote:

> > The statement "A common requirement of all the separation solutions  
> > is a mapping system that associate an edge prefix with the corresponding
> >                                   ^s
> > transit addresses." on page 2 is false.  GSE, for instance, requires  
> > no such mapping.
>

In GSE there is no notion of globally unique edge site prefixes.
When a host resolves an address for another host in an external site and
sends a packet to it, that packet has (one of) the RG(s) of that
external site in it's destination address field.

GSE is just a very clever form of NAT.  NAT in general is a separation
scheme that does not require the mapping you describe above.

Regards,

// Steve

---

From: Dan Jen <[email-masked]>
Date: Sun, 21 Sep 2008 10:55:34 -0700

> scheme that does not require the mapping you describe above.

As I said in an earlier post, I still feel GSE requires a mapping system
like other separation schemes.  The mapping is just in the DNS record.
If an edge site stopped using the RG provider specified in the DNS
record, it must update its authoritative servers to map itself to a new
RG that IS one of its current providers.  This is a mapping change.

Dan Jen

---

From: Steven Blake <[email-masked]>
Date: Sun, 21 Sep 2008 14:27:37 -0400

> RG that IS one of its current providers.  This is a mapping change.

My operating system requires a mapping between virtual and physical addresses.

So what?

The statement in your paper that I pointed out is still false.  The
mapping change for GSE you point out above is the exact same mapping
change needed for an elimination scheme (modulo any splitting of RG and
ESD+STP in the DNS).

The definition you are using for separation in your paper is either
inconsistent, or not very useful.

Regards,

// Steve

---

From: Dan Jen <[email-masked]>
Date: Sun, 21 Sep 2008 13:24:06 -0700

Hi Dr. Blake,

Thank you for the comments.  In response, I will try to clarify our
definition of 'separation' and 'elimination'.

On Sun, 2008-09-21 at 14:27 -0400, Steven Blake wrote:
> change needed for an elimination scheme (modulo any splitting of RG
> and ESD+STP in the DNS).
> 

Elimination refers to eliminating the use of PI addresses. Separation
does not eliminate the use of PI, but places PI outside of routable
space which requires a mapping.  

So either get all edge sites off of PI(elimination) or let them use PI
and map/resolve their addresses somehow to a routable PA
address(separation).  

> inconsistent, or not very useful.

The definition is not inconsistent(see above).  The utility of the
definition and categorization I'll leave for others to judge.  There are
schemes that fall under elimination - they don't use unroutable PI and
thus need no PI->PA mapping.  For awhile, multipath transport was
discussed(not necessarily by the authors) as a way to eliminate the need
for PI to support multihoming, which would hopefully get edge sites off
of PI and into PA, thus relieving our scalability issue.  

Thank you again for taking time to review our work.  All further
comments are welcome.

Dan Jen

---

From: Lan Wang <[email-masked]>
Date: Mon, 22 Sep 2008 16:06:03 +0900

Steve,

Thank you for your comments on our paper.

> external site in it's destination address field.

I've read the GSE draft several times.  My understanding is that in  
GSE, every host has a globally unique ESD.  In fact, the unique  
source/host ESDs are used as a connection identifier at the transport  
layer (they can't be used this way if they're not globally unique).   
So it seems to me that ESDs are similar to PI addresses (i.e.  GSE  
doesn't eliminate the USE of PI addresses, but does get rid of them  
in the transit space).  DNS provides the mapping between ESDs and RGs.
> scheme that does not require the mapping you describe above.
I don't quite understand your above comment.  How is GSE similar to NAT?

Lan

---

From: "Tony Li" <[email-masked]>
Date: Mon, 22 Sep 2008 00:25:54 -0700

|So it seems to me that ESDs are similar to PI addresses (i.e.  GSE  
|doesn't eliminate the USE of PI addresses, but does get rid of them  
|in the transit space).  

This is exactly where I have to disagree.  The ESD is simply not an address.
It is a wholly orthogonal namespace.  While it is globally unique, it shares
no other properties with a PI address that I can see.

|How is GSE similar to NAT?

GSE does pure translation on the routing bits.  In a NAT environment, the
routing goop is translated into an RFC 1918 address.  In GSE, the routing
goop gets zeroed out.

GSE is better than NAT in that it does provide a real identifier that
applications can now exchange freely, so that much of the translation
ugliness within NAT (e.g., FTP port commands) can go away.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 23 Sep 2008 10:39:21 +1200

> ugliness within NAT (e.g., FTP port commands) can go away.

The cost of that excellent property is that transport protocols,
IPsec, and any address-depedencies in upper layers, all have to be
tweaked iirc. ILNP also needs DNS enhancements; probably any GSE
solution does.

However, I fully agree with Steve; I have always referred to GSE
as "architected NAT".

   Brian

---

From: Robin Whittle <[email-masked]>
Date: Tue, 23 Sep 2008 14:46:14 +1000

Hi Dan and Colleagues,

Here is some feedback on your paper:

  Towards A New Internet Routing Architecture:
  Arguments for Separating Edges from Transit Core

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.

Elimination schemes are a retreat from the current responsibilities
of the routing system - to give each host a stable IP address.  They
involve host changes, including to applications which do referrals -
and probably in the way applications find the one address of
multiple addresses which they should be using.  They involve each
host in some highly complex tasks which I think belong in the network.

Elimination schemes involve scaling problems with tens of thousands
of sending hosts trying each to do their own reachability testing to
some host or network they are all communicating with.  I think it is
better to centralise the control of multihoming service restoration
as Ivip does, rather than devolve it to sending hosts (SHIM6) or to
ITRs (non-Ivip core-edge separation schemes).

Elimination schemes are hard or impossible to introduce because they
involve host changes and only provide benefits when both hosts in a
communication are upgraded.  They do not provide portability.

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.

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.

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.

Page 2 col 1 para 1

   Solutions in the elimination category require that edge
   networks take address assignments from their providers;
   as a result a multihomed edge network will use multiple
   PA addresses internally and must modify end hosts
   to support multihoming.

It seems that all elimination schemes involve host-changes.

None of them propose that the end-user network have some new router
functions to support elimination, with the hosts unaffected.  (NAT
is an example of this, but it doesn't provide hosts with public
addresses.)

Also, the elimination schemes do not provide portability, or the
possibility of IP address referrals AFAIK.  My recent message to
Iljitsch (Re: Elegance and the rejection of SHIM6 host-based
multihoming) discusses how SHIM6 would require host changes to do
referrals, since I think it would require using two or more IP
addresses.

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.

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.

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.

Page 3 col 1 last para

Elimination schemes do away with the concept of a host having a
single IP address.  So the DNS needs to return multiple IP
addresses.  Also, the DNS entries for all hosts need to be changed
every time a new ISP is chosen.  Sending hosts need to try one
address and then the next, unless the DNS response has some new way
of stating priorities for which address to try first.

As just mentioned, elimination schemes do not provide portability or
straightforward IP address referrals.

This lack of a single stable IP address leads to complications in
other networks.  Suppose network A has an ACL for its VPN, and the
aim is to allow a particular host in, according to its IP address.
That is simple now, and would remain simple with a separation
scheme.  However, with elimination, the ACL would need to have
multiple IP addresses for this one host, and those addresses would
need to be changed whenever the remote host's network started using
another ISP.

Elimination approaches do not support mobility, but separation
approaches could, via the TTR approach, as I wrote recently:

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

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.

If there was a host in the UK in a network with two separate ISPs,
and therefore two separate addresses via SHIM6, the multipath
approach would probably only affect the path taken by packets within
the UK.  The Australian end of the paths would probably be identical
- and likewise the the paths across the Pacific and the USA.

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.

Page 4 col 2 para 2

   Separating edges from the transit core provides additional
   features that are sorely missing in today’s Internet.
   With separation, an end host can send packets through
   the transit core, but can no longer address a packet to
   any specific device inside the transit core.

This may be true of the intention with APT to achieve 100% adoption
and then to physically prevent any end-user networks' hosts from
being able to send packets to any address which is not an end-user
network.  However it does not apply at all to Ivip - or I think to
the other core-edge separation schemes.

I think APT's aim in doing this is interesting, but I doubt it could
ever be achieved with sufficient robustness to provide any real
security benefit.

Page 4 co 2 para 4

I think that this discussion of using the core-edge separation
scheme to introduce fundamentally new protocols, with new addressing
schemes, is important.  Although it would involve an upgrade to all
ITRs, and to the mapping system, it would enable the new protocol to
be widely and reliably used, provided edge networks at both ends
supported it - but without requiring an upgrade to the DFZ routers.

Page 5 col 1 para 2

I was unable to find any CIRL references - Google equated this with
"circle".

What you wrote here:

  The encapsulation of end-user packets makes it easy to trace
  attack packets back to the ER, even if they have spoofed source
  addresses, since the encapsulation header records the addresses of
  the ER and DR.

does not apply to Ivip's encapsulation approach.  Ivip uses the
sending host's address as the source address in the encapsulation
header.

Also, Ivip has two forwarding approaches which do not involve
encapsulation at all:

  ETR Address Forwarding (EAF) - for IPv4
  http://tools.ietf.org/html/draft-whittle-ivip4-etr-addr-forw

  Prefix Label Forwarding (PLF) - for IPv6
  http://www.firstpr.com.au/ip/ivip/ivip6/

There is no trace of the ITR's address in the packets forwarded in
these systems.

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.

Page 5 col 1 para 4

This description of mapping information expressing preferences for
which ETR to use when sending packets to a host in Site2 does not
apply to Ivip.  Ivip mapping specifies a single ETR address.
Site2's administrators can change the mapping to some other ETR and
can load-share over multiple ISP links by mapping some micronets to
one ETR and other micronets to another ETR.  This will work fine as
long as the incoming traffic is spread over IP addresses in separate
micronets, which should be easy to do.  If all the traffic was for
one host, the host cold be given two IP addresses in two separate
micronets, and the DNS can supply those two addresses.

In Ivip, an ITR in Site1 can encapsulate packets intended for the
Site2 host to whatever address it likes, but it would be at odds
with the intention of Ivip and it wouldn't make much sense to send
it to any address other than the one nominated in the most recent
mapping update.

I haven't thought much about multipath transport, but my impression
is that it only makes sense when most or all DFZ routers are
upgraded to do this necessarily complex task.  I am not convinced
this will ever happen, or that it would make a huge amount of
difference to the performance of the Net.

  - Robin

---

From: Michael Meisel <[email-masked]>
Date: Tue, 23 Sep 2008 02:24:38 -0700

> Hi Dan and Colleagues,

Hi Robin,

> 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.

> networks would be happy to use one or a few IP addresses, rather

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...

> 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.

> 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.

> 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. =)

> another ETR.  Each mapping update pays its way - the user pays for

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.

> 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.

> 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?

> - and likewise the the paths across the Pacific and the USA.

If that were true, it would be due to the lack of diversity in the
physical, inter-continental wires, which we can't do anything about in
software, as hard as we might try. =)

> 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 was unable to find any CIRL references - Google equated this with

Ah, it seems the URL was accidentally left out of the bibliography. Here
it is:

http://read.cs.ucla.edu/~frost/cirl/

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

> 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.

> difference to the performance of the Net.

I think you may be misunderstanding the multipath transport proposal. Of
course, I'm no expert on the subject, but I'm certain that one of its
basic assumptions is that changes need only be made in end hosts.

-Michael

---

From: Michael Meisel <[email-masked]>
Date: Tue, 23 Sep 2008 13:03:04 -0700

Hi Tony,

> no other properties with a PI address that I can see.

But it must be used as an address in edge networks, right? How else
would a packet get routed to its final destination host once it gets to
the destination network?

When Lan says "PI address", she's referring in a general sense to an
address that wasn't assigned by your provider. It could certainly come
from a different namespace than PA addresses under a separation scheme,
since the PI addresses are no longer used in core routing. So in this
sense, I would call the ESD a "PI address".

> ugliness within NAT (e.g., FTP port commands) can go away.

It seems to me that there is still an important fundamental difference:
when you address a packet to a host behind a NAT, you are addressing the
packet to the routing goop directly. The translation happens only
locally on the destination end (and ugliness results).

With GSE, on the other hand, if you address a packet to a host inside a
GSE network, you are addressing the packet to the ESD, so you need
mapping information (from DNS, in this case) to determine the correct
routing goop.

-Michael

---

From: Steven Blake <[email-masked]>
Date: Tue, 23 Sep 2008 17:28:44 -0400

On Tue, 23 Sep 2008 13:03:04 -0700, Michael Meisel <[email-masked]>
wrote:

>> This is exactly where I have to disagree.  The ESD is simply not an
>> address. It is a wholly orthogonal namespace.  While it is globally
unique, it
>> shares no other properties with a PI address that I can see.
> 

By STP + ESD (last 80 bits of the address field).  ESD is just an interface

identifier, no different than the IID in IPv6.  It's only really used in
the
neighbor table lookup on the last hop router.

Please re-read
http://ietfreport.isoc.org/all-ids/draft-ietf-ipngwg-gseaddr-00.txt.

> sense, I would call the ESD a "PI address".

ESD bits are never used in a routing lookup, so I don't know why you want
to call
it an address by itself.

>> GSE does pure translation on the routing bits.  In a NAT environment,
                                   ^backbone

>> the routing goop is translated into an RFC 1918 address.  In GSE, the
>> routing goop gets zeroed out.
>>

That's true of IPv4 NAT, but in (hypothetical) IPv6 NAT you would never
want
to translate anything other than the provider prefix. 

> mapping information (from DNS, in this case) to determine the correct

That's true of IPv6 in general, whether the edge site is using PA or PI 
prefixes internally (or would have been, if A6 records had survived).

As I pointed out previously, there is no concept of globally unique edge
site 
prefixes in GSE.  There is no destination prefix translation anywhere
upstream
of the destination edge site's border router.  Ergo, there is no mapping
system
that "associate(s) an edge prefix with the corresponding transit address". 
The
routing behavior in GSE is unchanged from IPv6 outside of the destination
edge site
(excepting the source prefix re-write).

Regards,

// Steve

---

From: Robin Whittle <[email-masked]>
Date: Wed, 24 Sep 2008 13:13:03 +1000

Hi Michael,

> 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.

> 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.

> 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.

> 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.

> we felt it would be misleading/confusing to include it. We meant no

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.

> 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.

> 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.

> I don't see why DFZ routers need to be involved -- isn't the whole point

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.

> 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.

> 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

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?

> see it as necessarily unavoidable.

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

 - Robin

---

From: Michael Meisel <[email-masked]>
Date: Wed, 24 Sep 2008 13:40:16 -0700

Hi Steve,

> ESD bits are never used in a routing lookup, so I don't know why you want

Fair enough. I think this is really just a semantics issue though, the
point is, whatever namespace you use to identify the hosts in your local
network, those names are independent of the names that get used for
global routing, and they are independent from who your provider(s)
is/are. This is consistent with our definition of separation. Perhaps we
should call it "PI namespace" or "local namespace" or something.

> (excepting the source prefix re-write).

True, there are no edge site prefixes in GSE, so this wording doesn't
quite match up. But DNS does associates the destination *portion of the
address* with the corresponding transit *portion of the address*. That
is, an "RG Name" lookup looks like a mapping lookup to me, it just
happens at the host instead of the border router.

-Michael

---

From: Michael Meisel <[email-masked]>
Date: Wed, 24 Sep 2008 15:01:14 -0700

> is not intended to prevent edge devices from sending packets to

I think the Ivip mapping system is exactly the part that doesn't fit. We
feel strongly that we need to make a technical argument (not an economic
one) as to why we aren't just moving the problem to the mapping system.
Ivip has the only mapping system that proactively pushes mapping updates
through the core.

> current technique of relying on physical links between ISPs.

Which, as you pointed out in your previous message, is fairly simple to
do. This is also not necessarily the only way.

> PTRs do this robustly.  I think APT's approach isn't so thorough.

I guess we have to agree to disagree on this. Also, keep in mind that
APT is still under active development, particularly in this area.

> support packets from non-upgraded networks, compared to none of the

I think you're reading a bit too much into it. =) We're talking
specifically about scaling the routing table here. Of course,
non-upgraded networks can still communicate with upgraded networks in an
elimination scheme. However, if upgraded networks stop injecting their
prefixes into the global routing table, they lose the benefits of
multihoming when communicating with non-upgraded networks.

So upgraded networks will want to continue to inject their prefixes into
the routing table until there are no more non-upgraded networks. So the
transit networks' routing tables won't shrink until this happens.

> arrangements for this, and of Six/One Router's inability to do this.

First, let me reiterate that we are talking in general about separation
schemes in the paper, of course any particular design may or may not be
able to achieve all of the possible benefits.

Second, some separation schemes are not intended for deployment in
end-user networks (a.k.a. edge networks) at all. We are trying to make
the point in the paper that transit networks are the ones that need the
routing table to scale, and it is possible for transit networks to
deploy separation schemes themselves, in theory, in order to directly
address that issue. This is not possible for elimination schemes.

> don't want to use different terms from LISP etc. without good reason.

We used ER and DR only when giving the specific example of map & encap,
which of course *does* use encapsulation.

> APT (eFIT??) could ever robustly achieve this.

If your *provider* is encapsulating your packets (as in APT), of course
you can't address anything in the *upgraded* transit core. But
non-upgraded transit networks are effectively in edge space, so they can
still be addressed.

> this common "separation" goal.

See above.

> a "mapping" system, with ITRs, ETRs, Default Mappers etc.

Right.

> I guess you could get one, two or maybe three or four orders of

No, it's not an issue of efficiency. BGP and the Ivip mapping system
both distribute two types of information: topology information (who is
connected to who), and reachability information (which connections are
currently working). These two types of information are indistinguishable
in these systems.

APT only distributes topology information in the mapping system. So the
increased number of edge prefixes that an APT-based network can handle
is relative to the (increasing) amount of BGP traffic that is due to
reachability changes in edge prefixes.

> the number of mapping changes or the number of EIDs in the mapping

The costs are not falling *unfairly* on the ISPs -- they are the ones
that stand to benefit. Again, the primary goal of APT is better routing
scalability, which is a DFZ problem.

I suspect you will have a lot to say on this, so perhaps it should be
moved to a separate thread, but I am curious: in regards to your
economic model, what is stopping an ISP from charging their BGP-speaking
customer for each BGP update today?

> there is no recursion.

I think you mean, there is *only* recursion, in the sense of recursive
DNS queries.

> Also the query typically is the traffic

Of course, a one-word description is necessarily way too simple. But
this was only a six page paper, and explaining LISP-ALT is tangential to
our point, so we couldn't do much better. I agree with you that LISP-ALT
has many problems that DNS does not.

> packets of other flows along the second path.

Notice the title of the slide: "What about Multipath ROUTING?" Our paper
is talking about Multipath TRANSPORT, as are the rest of Mark's slides.
Multipath TRANSPORT doesn't involve the routing system at all.

> multipath approach you illustrate in section 5.

If you mean the combination of multipath transport with separation, as
illustrated, this is an original contribution, there is (AFAIK) no prior
work.

If you mean multipath transport in general, see Mark's slides (which you
linked to above) and this reference:

P. F. Tsuchiya. Efficient and robust policy routing using multiple
hierarchical addresses. SIGCOMM Comput. Commun. Rev., 21(4):53–65, 1991.

> next hop in the faulty part of the network.

No, we don't rely on ICMP in APT. We have our own control messages that
are generated and processed at DRs and DMs. I believe the details (at
least of previous versions of our failure handling) are described in
most (if not all) of the APT-related documents.

> identical looking packet created in a host controlled by the attacker?

The answers to all of this are dependent on both how APT networks handle
packets from non-upgraded networks, on the particular DDoS mitigation
scheme, and on what (if anything) is done to ensure the authenticity of
ITR addresses. These are all works in progress and/or future work, so
I'd rather not speculate, except to reiterate that I don't see any of
these things as unsurmountable.

-Michael

---

From: Robin Whittle <[email-masked]>
Date: Fri, 26 Sep 2008 02:19:18 +1000

Hi Michael,

I am perplexed that you don't consider Ivip to be a member of the
class of solutions known as "Separation" - the class of "core-edge
separation" schemes.

> Ivip has the only mapping system that proactively pushes mapping updates

I don't see how these issues affect the question of whether Ivip is
a core-edge separation scheme.  I attest it is.

LISP, APT, Ivip and TRRP all move the problem to the mapping system
- and to ITRs and ETRs etc.  But we are crafting the new mechanisms
to scale to much larger numbers of end-user prefixed (EIDs for LISP
and APT - I call them "micronets") then the global BGP system can
handle.

In addition, with Ivip, I intend there to be business arrangements
so that end-users pay for their use of the mapping system.  This
means the whole thing can be run profitably and agreeably, scaling
to very large usage rates, since each mapping changes generates
revenue - rather than there being some end-users burdening other
parties with rates of updates which the other parties consider
unreasonable.   I wouldn't claim that every part of the entire
mapping distribution system is necessarily covered like this, but
most of the top end would be - not the tail ends of the Replicator
system and the full database query servers themselves.

> Ivip has the only mapping system that proactively pushes mapping
> updates through the core.

I disagree.

APT and Ivip are the most similar proposals, in my view.  They are
both hybrid push-pull systems.  In both APT and Ivip, the full
mapping data is pushed to full-database query servers - Default
Mappers for APT.  For both APT and Ivip these local full database
query servers provide fast, low-cost, reliable mapping responses.

This is totally different from the global query server arrangements
of LISP-CONS, LISP-ALT or TRRP.  (Six/One Router doesn't have any
particular mapping system yet.)  It is also totally different from
LISP-NERD's approach of pushing all mapping data to every ITR.

Ivip pushes the mapping fast and APT pushes it slowly.  Ivip has a
distributed, but still reasonably centralised, push system which
fans out to all full database query servers. APT has multiple
islands, with more diffuse pushing of the updates from multiple
sources of mapping data within the islands.  (I don't see any
benefit in APT islands - I think there should be one APT system.)

Your formal definition of separation is:

I attest that Ivip does this.  I see below that you mean more by
"separation" than I do.

 . . .

> I guess we have to agree to disagree on this. 

OK - but I don't understand how APT (with APT islands) can robustly
support packets from non-upgraded networks when there are two EIDs
such as /25 or longer, in the one /24, and the two end-user networks
are using ISPs in different APT islands, in a setting where it is
impossible to have advertisements for prefixes longer than /24
propagate across the DFZ.

> Also, keep in mind that  APT is still under active development,
> particularly in this area.

I wasn't trying to say that APT could never support packets from
non-upgraded networks addressed to smaller EIDs - just that with the
current arrangements, in my understanding, that it can't.

. . .

> multihoming when communicating with non-upgraded networks.

That is what I mean - with Elimination schemes, there is no way of
achieving the scalability goals whilst providing multihoming support
for packets from non-upgraded networks.  So if you want to get
anyone - or more particularly most end-user networks - to adopt the
scheme, you must run it in a way that multihoming is supported for
packets sent from non-upgraded networks.  Then, the only path to
scalability is to get practically every network to upgrade.  Only
then can we achieve the scalability goal, by withdrawing the routes
from the DFZ.

> transit networks' routing tables won't shrink until this happens.

Precisely - we agree: Elimination schemes are not a suitable
solution, in part because they could only provide scalability
benefits after essentially complete adoption during a backwards
compatible mode of operation for initial adoption, which provides no
scaling benefits.

However, it does not follow that all Separation schemes can
simultaneously achieve scaling benefits while providing multihoming
and portability support for all packets sent from non-upgraded
networks.  Hence my mention of what I perceive are the limitations
of APT and TRRP in this regard.

> able to achieve all of the possible benefits.

OK.

> end-user networks (a.k.a. edge networks) at all. 

I don't understand this, since your definition is:

The edge-network needs to adopt the new system.  They either need
new address space, for instance if they are currently using PA
space, or they need to change the way their current PI space is
administered - or gain new Scalable PI space.   There doesn't
necessarily have to be actual ITRs and ETRs in the edge networks,
but the concept of there being edge and ISP networks with or without
ITRs (or their Six/One Router equivalents) is crucial to the
operation of the Separation schemes.

> We are trying to make

I agree it is not possible for elimination schemes, but I can't
think how transit networks could deploy any of the current
separation schemes without involving the end-user networks.  Can you
give an example?

> non-upgraded transit networks are effectively in edge space, so they can

I would have thought it more correct to say:

  non-upgraded transit networks are effectively in *core* space, so
  they can still be addressed.  The Default Mapper has no mapping
  for any address in a non-upgraded edge network, and to ensure
  it can be reached from an upgraded edge network, it must forward
  the packets without encapsulation.

  (Of course, for hosts in non-upgraded edge networks to be able
  to send packets to hosts in upgraded edge networks, one or
  more border routers in the APT island need to advertise either
  the upgraded edge network's EID prefix, or some other prefix
  which covers this EID prefix.)

  Only once all edge networks adopt APT will the core be truly
  "separated" from all edge networks.

>> this common "separation" goal.

OK - so your use of the term "Separation" has a very different
meaning from the way I use it in my assertion that Ivip is a
"core-edge separation scheme".

I mean separation in the sense that the end-user address space is
managed by a separate system from the core, and does not burden the
core or contribute much or at all to its scaling problem.

You mean "separation" in that from an end-user network which adopts
the scheme, it is physically impossible to send packets to any core
address.

I understand this is a goal of APT.  I don't think it is very useful
- and I think it could only be achieved after 100% adoption by all
edge networks.

But if this meaning of "separation" is your criteria, by which you
correctly exclude Ivip, then I don't understand why you include LISP
or TRRP.  AFAIK, neither aims to physically separate all the edge
networks from the core as I understand you aim to do with APT.

>> a "mapping" system, with ITRs, ETRs, Default Mappers etc.

OK.

> currently working). These two types of information are indistinguishable

OK - though the way BGP's routers handle packets and communicate
which prefix is advertised by which router is completely different
from Ivip's arrangement of ITRs, ETRs, query servers and fast-push
mapping distribution system.

In both cases, there is a global system which enables packets
addressed to some prefix to be sent to some router.  Ivip only works
as an addition to the BGP system.  BGP works on its own.  BGP's
handling of changes is slow and expensive - and difficult or
impossible to charge end-users for when they make a change.  Ivip's
handling of changes is intended to be much faster and less expensive
- while also making it easy to charge a small fee per update, a few
cents for instance.

> APT only distributes topology information in the mapping system. 

For each micronet, Ivip's mapping system distributes the address of
the ETR to which packets addressed to that micronet should be sent
by every ITR.  It is the responsibility of the end user to change
the mapping to some other ETR which works if the current ETR is not
working, or is not connected to their network.  This requires Ivip's
mapping to be sent out fast - effectively in real-time - and it
simplifies the ITRs and ETRs and reduces the size of the mapping
information, since ITRs and ETRs are not involved in testing
reachability.

APT, like LISP or TRRP, has mapping information with two or more ETR
addresses (assuming a multihomed end-user network).

This mapping information is assumed not to need to be changed very
much, since APT's push (to the Default Mappers, from which ITRs pull
the mapping information they need) is slow by comparison to Ivip.

Consequently, each APT (or LISP or TRRP) ITR (or the ITR's Default
Mapper) needs to do its own probing of ETRs or use whatever
techniques to determine ETR reachability - then the ITRs (actually,
I think it is APT's DMs) need to make their decisions, based on the
mapping information, which ETR to tunnel the packets to.

> So the

Are you saying that a major efficiency - that is, scaling -
advantage of APT is that it doesn't convey reachability information?

Assuming this is the case, then I see it is true to this extent:
Your mapping doesn't need to be pushed as fast or as frequently as
Ivip's, or as fast or frequently as BGP would ideally propagate its
changes.

No-one else has drawn parallels between Ivip and BGP - so this is
interesting.  Clearly they are completely different, and Ivip
assumes a core routing system - BGP.  However, they are alike in
that both are in a hurry to communicate "reachability" information
across the Net.

Every time a BGP prefix is advertised, or no-longer advertised at a
given router, changes to this effect need to be propagated.  The
changes may not need to go very far, or they may involve changing
the best path decision of every router in the DFZ.

Every time an Ivip micronet is mapped to some ETR, or not mapped to
it (typically it would simply be mapped to another ETR, but it could
be mapped to NULL, or its space could be reassigned to one or more
different micronets), the Ivip system needs to convey this quickly
to every full database query server.  (And to any full database ITR,
but my current thinking is that there will be few or none of these -
just caching ITRs, some of which have a full database query server
integrated into them, or have one in the same rack.)

APT is not in a hurry to push mapping information to all the
island's Default Mappers.

Being not in a hurry is arguably a scaling benefit, as is not having
to push the mapping very often.  However, one extra cost (compared
to Ivip) is that APT needs to push more complex, more voluminous,
mapping information.  Another major extra cost your ITRs/DMs and
ETRs need to be much more complex than Ivip's because they must do
all the reachability testing and multihoming service restoration
decision making.

> scalability, which is a DFZ problem.

But what if an end-user network issued a mapping update every 10
seconds, 24 hours a day?

That would be as much of a burden on the ISPs in the APT island as
hundreds of thousands of ordinary end-user networks which only
changed their mapping every month or so.  (In terms of mapping
traffic and processing it at each DM.  In terms of storage, the
burden is the same.)

In this respect, APT achieves no benefits over BGP.  Both APT and
BGP have to accept the arguably excessively frequent changes and
propagate them - and in both cases there is no way of charging the
originator of these changes to help deter them from making so many,
or to help pay for their cost across all the ISPs.

Ivip is completely different in this regard - there will be a small
fee per update.

So I think APT continues this problem of having to propagate
end-user initiated changes across many devices, without a fee.  This
is what bedevils BGP - and is a significant part of the the heart of
the routing scaling problem.

> customer for each BGP update today?

Other folks on the list would have a better idea of this, but I
think the current BGP system relies on trust and unsecured
announcements.  To put up some kind of fence, administered in some
way to reject updates from networks which don't in fact pay a fee
per update, would require a major upgrade to all participating
routers.  It would require some pretty fancy security arrangement
and my guess is that it is all too much of a headache.  It would
also require some kind of organisation, accounting system, and
presumably some way of distributing monies to help ISPs pay for
bigger DFZ routers.

I figure it could be done.  If this was all that was required to fix
the routing scaling problem, I think people would be working on it.

However, it doesn't alter the fact that the BGP system can't
reasonably be expected to scale to as many prefixes as there are
end-user networks which need portability and multihoming.

Fees for each BGP prefix and for each updates would help deter those
who advertise and change their advertisement of prefixes for
arguably spurious reasons, so it would marginally reduce the scaling
problem.  However it wouldn't solve the scaling problem assuming we
want to have 10 million, 100 million or whatever end-user networks
with portable, multihomable address space.

> I think you mean, there is *only* recursion, in the sense of recursive

I mean "no recursion".

My understanding of ALT is that an ITR makes a query to some remote
query server it has no idea the location or Internet address of.
The query is typically the initial traffic packet for some EID
prefix for which it currently has no mapping.

It pops the packet into the ALT network, encapsulating it with a
LISP header with the ITR's address as the source address and the
initial packet's destination address as the destination address.

The ALT network's address is the same range of numbers as the
Internet's range (eg. the IPv4 ALT network has 0.0.0.0 to
255.255.255.255) but the routers in the network use these addresses
completely independently from any address those routers might have
on the Internet.

The ALT routers are linked by tunnels in the Internet.

Each ALT router aggregates some number of ALT routers below it.  The
packet is passed along these tunnels and routers, just as if it was
on the Internet, but this is a different network.  The packet's
destination address - the destination host EID address, ensures it
is forwarded to the authoritative query server for this EID.  I
understand this is typically an ETR, but it need not be.  This ETR
sends back the mapping reply directly via the ordinary Internet
(which is much faster and more direct than sending it back by the
ALT network).

There is no recursion.  It is a conceptually neat scheme -
delivering the initial packet to the ETR even when the ITR doesn't
have mapping information (the ETR's address) - and at same time
having this constitute a mapping request.  (APT has something
similar in a faster, local manner with the ITR sending packets to
DMs and getting a mapping reply in return.)

However, it is a global query server system, which I think is a
really bad idea in terms of delay and reliability.  Worse still, the
physical paths likely to be traversed by query packets will often be
geographically much longer than the shortest geographical path.

LISP-ALT has no concept of recursion, as far as I know.

> has many problems that DNS does not.

Yes . . . 6 pages:

  http://conferences.sigcomm.org/hotnets/2008/cfp.html

is not much if you have something complex to write about.

Still, I think that it is misleading to describe LISP-ALT as "DNS-like".

. . .

> Multipath TRANSPORT doesn't involve the routing system at all.

Thanks - I roughly figured out this distinction after I wrote my
last message.

> illustrated, this is an original contribution, there is (AFAIK) no prior

OK.

> hierarchical addresses. SIGCOMM Comput. Commun. Rev., 21(4):53–65, 1991.

OK - the OCR text is available for a fee:

  http://portal.acm.org/citation.cfm?doid=115992.115999

> most (if not all) of the APT-related documents.

OK - there is a message from the ETR to the DM of the sending
network that the ETR can't reach the destination network:

  http://tools.ietf.org/html/draft-jen-apt-01#section-11.4

If the ETR's unreachability is reflected in its BGP prefix no longer
being reachable, this is handled in section 6.1.1.

But what if there is some network failure between the ITR and the
ETR?  Section 6.1.2 handles this, on the assumption that the ITR can
send packets to the network in which the ETR resides, and that the
default mapper there, working with the internal routing system, will
be able to detect that the ITR sent a packet to the no-longer
reachable ETR.

OK - I see how you do this without relying on ICMP messages.  You do
however rely on:

1 -  BGP to tell the sending network's border router, and therefore
     the ITR, that the ETR's network is unreachable.

2 -  The DM in the ETRs network to tell the ITR (or the ITR's DM?)
     that the ETR is unreachable.

3 -  The reachable ETR to tell the ITR (or the ITR's DM?) that the
     destination network is unreachable.

I think 3 should be OK - and probably 2.

However, there can be long delays across the Net with BGP
propagating a notion of unreachability.  The destination network
could go off the air and nearby routers cancel their advertisements,
but other routers think their neighbour has a path, and advertise
that path's length.  This does not necessarily get propagated
quickly, due to a delays in each router, including if there is a
flurry of such announcements when a major link dies.  Also, there is
MRAI path hunting, depending on the structure of the routers.

http://www.firstpr.com.au/ip/sram-ip-forwarding/#BGP_hunting_MRAI_disc

which can delay the propagation of an unreachable condition by ~30
seconds for however many depths of this process there are.

> these things as unsurmountable.

OK - thanks for your detailed reply.  No 6 page limits around here!

  - Robin

---

From: Michael Meisel <[email-masked]>
Date: Thu, 25 Sep 2008 15:34:31 -0700

Hi Robin,

> a core-edge separation scheme.  I attest it is.

Sorry, I guess I wasn't clear on what my point was -- I definitely and
wholeheartedly agree that Ivip is a separation scheme. =) The reasoning
above was just to explain why the differences in the Ivip mapping system
would have made it somewhat contradictory to mention Ivip as an example
in the HotNets paper.

> LISP-NERD's approach of pushing all mapping data to every ITR.

Agreed.

> benefit in APT islands - I think there should be one APT system.)

I think the larger difference between the mapping systems is what I
pointed out below -- the difference in what information is distributed.

Regarding APT, I think you will find that APT islands that are not
physically connected can be logically connected in the next version of
our incremental deployment scheme. However, we can't force ISPs that
don't already have business relationships to create them, so there is
always the (as you say, probably undesirable) possibility of multiple,
disconnected islands.

> I attest that Ivip does this.  I see below that you mean more by

Actually, I don't believe I do -- just a case of miscommunication on my
part.

> propagate across the DFZ.

I assume this is not possible. But that means it provides an incentive
for the separate islands to converge to one. =)

> separation schemes without involving the end-user networks.  Can you

Sure: APT. APT is deployed by an ISP by turning their border routers
into APT EDRs (or TRs or whatever you want to call them). Customers
outgoing packets are encapped by the ISP, their incoming packets are
decapped by the ISP. If the customer is multihomed, they can ask their
providers to put their TE preferences into the mapping info for their
prefix(es), but that's totally optional.

>   "separated" from all edge networks.

Continuing from where I left off above, all packets that get sent to the
ISP from then on are either already encapped (by another ISP in the same
island), or get encapped by that ISP. Same goes for decap. No non-border
router inside that APT island is directly addressable by devices outside
the island.

> core or contribute much or at all to its scaling problem.

I agree. Sorry... all of this confusion is my fault. I didn't mean to
say Ivip isn't a separation scheme -- it definitely is. I just meant to
say that it's mapping system didn't fit some of the constraints we
wanted to place on mapping systems for this paper.

> impossible to charge end-users for when they make a change.  Ivip's

Why? Say I'm your customer, and we have a configured BGP session. You
count the number of updates that arrive over that connection per month,
and then charge me per update once a month.

> Ivip's, or as fast or frequently as BGP would ideally propagate its

Yes, exactly!

> all the reachability testing and multihoming service restoration

This is all true. But we argue this is necessary complexity. The
Internet is a complex system. I think it was Einstein that said: as
simple as possible, but no simpler.

> But what if an end-user network issued a mapping update every 10

Edge networks don't send mapping updates directly under APT. ISPs send
mapping updates that contain their customers' prefixes. We also plan to
have the protocol limit the frequency of updates to something on the
order of (very roughly) once per hour. Because we don't carry
reachability information, there is no need for frequent updates. We're
currently working on some simulations to see exactly what time scale is
workable.

> Ivip is completely different in this regard - there will be a small

Yes, our solution is technical (frequent updates are not necessary for
desired functionality), yours is economic (frequent updates are
necessary, but can be costly). The way I see it, we are technicians, not
policy makers, so I don't see how an economic solution is enforceable.

> presumably some way of distributing monies to help ISPs pay for

I was trying to say that you could charge edge networks for sending BGP
updates to their providers, not charge in the core. As we've discussed,
this is where most of the updates originate. These BGP connections are
manually configured, and, AFAIK, generally need to match up with the
physical connection that the customer's data flows across. So it seems
to me that's pretty hard to fake.

> with portable, multihomable address space.

So, if I am understanding correctly, your claim is the following: Ivip
solves routing scalability by (a) proactively distributing the same edge
network topology and reachability information as BGP, except more
efficiently, and (b) enforcing a charge per update?

> LISP-ALT has no concept of recursion, as far as I know.

Ok, I see what you mean.

>      the ITR, that the ETR's network is unreachable.

As is true in the Internet today.

> seconds for however many depths of this process there are.

All of this is true, but APT isn't meant to fix or avoid BGP's problems,
just to limit how much of the network BGP routers have to deal with.

> OK - thanks for your detailed reply.  No 6 page limits around here!

Certainly not. =)

-Michael

---

From: Robin Whittle <[email-masked]>
Date: Fri, 26 Sep 2008 17:46:39 +1000

Hi Michael,

Thanks for confirming that you include Ivip as a "Separation"
scheme.  Likewise for agreeing that there are some similarities
between APT and Ivip.

I will continue the discussion comparing APT and Ivip, and about
charging for BGP updates, in another thread:

  Comparing APT & Ivip

   - Robin