Subject: Re: [RRG] LISP-EMACS (was: LISPEMACS & LISP-ALT)

From: Scott Brim <[email-masked]>
Date: Fri, 16 Nov 2007 13:47:01 -0500

This response is about LISP-EMACS.

Excerpts from Robin Whittle on Fri, Nov 16, 2007 11:40:48PM +1100:
> LISP-EMACS ("EID-mappings Multicast Across Cooperating Systems for
> LISP"):
> 
>   http://tools.ietf.org/html/draft-curran-lisp-emacs-00
> 
> does not seem to be tied to LISP-ALT

That's right.

> The idea is that an ITR which has no mapping for a particular EID
> sends the traffic packet to this EMACS multicast system, which
> quickly sends it to the ETR which has the authoritative mapping (and
> I guess which is also the ETR which is supposed to handle the packet
> - though it makes no sense to me to have mapping authority vested in
> such far flung ETRs which are at risk of being unreachable) . . .

Did I answer this "unreachable" question in the last message?  It's
fate-sharing.  If the ETR is unreachable for mapping, then it's
unreachable for forwarding, and vice versa.  If you decouple
administratively-configured mapping servers from real-world
forwarders, you need some other mechanism to couple them.  The nice
thing about LISP-EMACS and LISP-ALT is that no separate mapping server
is required.  Theory matches reality.

> This seems somewhat nifty to me, but there are some scaling problems
> - and I think it is a lot of trouble to set up a whole global
> network like this, with BGP, ASNs etc.

Again, there's no separate network.

> I don't understand how LISP and APT work together, but APT has full
> database default mappers in each ISP network - so I don't think an
> LISP-EMACS-like system is needed with eFIT-APT.

Default mappers are an orthogonal feature.  Whether default mappers
exist or not, there needs to be a mechanism to figure out where to
send the first few packets.  Default mappers take care of this on
behalf of a site or set of sites, but still the default mappers need
the same information -- how to forward the first few packets -- as any
node would if it didn't have a default mapper.  A default mapper just
moves and concentrates the problem.  Also look at CRIO and LISP-EMACS
and destination-side default forwarders (DSDFs).

> LISP-EMACS does not solve the primary problem of LISP: that that
> packets from non-upgraded networks will never find their way to the
> EID addressed destination host, since (in the original conception)
> the EID addresses are not part of any conventional BGP advertised
> prefix.  (See http://psg.com/lists/rrg/2007/msg00529.html for
> possible extensions to CONS and NERD to maintain BGP advertisements
> for prefixes containing EID addresses.)

Transition issues are 80-90% orthogonal to what control plane
mechanism is used.  For example, proxy ITRs can be used with any of
these schemes.

> My main concern is the traffic amplification which this multicast
> system entails.  

Yup.  As we said in the draft, this is one of the issues that requires
further study.  LISP-EMACS was *not* presented as a beautifully
polished work of art.  It is potentially "nifty" as you say, but we
aren't sure of the right way to attack some of the problems, so we put
it out there for everyone else who like the basic premise to think
about those problems and contribute solutions.

--
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: Robin Whittle <[email-masked]>
Date: Sat, 17 Nov 2007 14:17:43 +1100

Hi Scott,

You wrote:

>> LISP-EMACS ... does not seem to be tied to LISP-ALT
> 
> That's right.

OK - but I understand that the multicast system is on an overlay
system of special routers, which use GRE tunnels - and presumably
their own instance of BGP - much like that of the LISP-ALT system.

> unreachable for forwarding, and vice versa.  

OK.  In LISP you are not relying on an ETR to give short-term new
information about which ETR to tunnel packets to, because the
options have already been spelt out in the mapping data which the
ITR has previously received and cached.

But still it seems like:

   Here are my friend's phone number and mine.  Whenever you want
   to call one of us, call my number first, then hers if mine is
   disconnected.  Anyone who wants to know our current numbers can
   phone us as just described.

Whereas I would have thought it better to say, for the second sentence:

   Anyone who wants to know our numbers can call directory
   assistance.

To me, an ETR is for decapsulating packets and getting them to the
destination host - so they may be deep within ISP networks.  Being a
reliable, redundant, secure, source of mapping information is a
totally different task, best suited to a more centralised - but
still distributed - system designed for this purpose.

> If you decouple

I guess it is a philosophical difference.  I prefer to make an
optimised system for mapping information, which does not necessarily
have anything to do with the ETRs.  Ivip end-users can choose to
make their ETRs the authoritative source of mapping information -
but they are not forced to.

The ETR would be generally owned and operated by the ISP.  With
Ivip, the end-user controls their own mapping via some secured
access directly or indirectly to a RUAS (Root Update Authorisation
Server).  This is more complex and flexible than the fixed
arrangement you have in LISP.  For example, it enables an end-user
to contract another company, unrelated to any of their ISPs, to run
an automated system to monitor their connectivity and ETRs, and
change the mapping information to restore connectivity and spread
load etc. however they desire - without involving their own servers
which are typically dependent on the very connectivity which is
threatened by the outages the system is supposed to cope with.

> Again, there's no separate network.

I think it is a new network in a logical sense, even though its data
links are carried in tunnels over existing data links.  You run
routers, each with their own LISP-ALT/EMACS-specific BPG instance
and ASN system.

> and destination-side default forwarders (DSDFs).

The LISP-EMACS ID's Problem Statement mentions APT as one of the
proposed mapping mechanisms for LISP.  The APT ID:

  http://tools.ietf.org/html/draft-jen-apt-00

is cited, but I think APT is supposed to work with eFIT, not LISP.
Perhaps someone can correct me.

eFIT-APT involves Default Mappers receiving the full set of mapping
updates (slowly) via BPG (or maybe some other mechanism?) - so I
think there is no need for approaches such as LISP-EMACS or LISP-ALT
with eFIT-APT.

> mechanism is used.  For example, proxy ITRs can be used with any of

When I proposed "anycast ITRs in the core" in June, I was criticised
by some LISP people and urged to write it up in an ID.  A month
later I produced a comprehensive ID.

Now, it seems, LISP may adopt something which looks the same to me -
but you may be calling "proxy ITRs".  I am keen to see a well
documented example of this.  I think it is the only way forward and
that if it turns out to be in principle the same as what I proposed,
you should at least mention that your proposal bears some
resemblance to Ivip's approach, and probably to what Eliot
contemplates for LISP-NERD.  This is needed so that newcomers to
this field do not see the two approaches as being fundamentally
different, just because they use different terminology, come from
different teams and apply to different ITR-ETR schemes.

> about those problems and contribute solutions.

Sure.  This is an ambitious exercise with far-reaching consequences.
 If a whole ID, or even a whole proposal, does nothing more than
provoke someone into thinking of something better which is actually
used, then I figure it was a worthwhile exercise.

  - Robin

---

From: Robin Whittle <[email-masked]>
Date: Tue, 20 Nov 2007 13:13:41 +1100

Hi Scott,

Here are some further thoughts on LISP-EMACS.  By the way,
Thunderbird 2.0.0.9 (20071031) removes the bracketed part of this
subject line when creating a reply.

The most obvious way I can think of to reduce the packet
amplification problem I referred to is to increase the number of
multicast groups - so each one sends packets to a smaller number of
ETRs.

LISP-EMACS-00 involves chopping the IPv4 destination address in the
middle, so the 16 least significant bits are discarded, and the 16
most significant bits are used to select the multicast group.

This only uses 2^16 multicast addresses, 1/16 of the 2^20 available.

You could assign multicast addresses 16 times finer and so, in
general, reduce the number of packets multicast by about this factor.

Since the unicast /8s are 0 to 223, this would require 7/8 of the
multicast address space:

  EIDs 0.0.0.0  to 0.0.15.255            Multicast 224.0.0.0
  EIDs 0.0.16.0 to 0.0.31.255            Multicast 224.0.0.1
  ...
  EIDs 223.255.240.0 to 223.255.255.255  Multicast 237.255.255.255

I have no idea what costs this imposes in structuring the multicast
system and I doubt that it adequately resolves the problems with
efficiency and susceptibility to DoS, but as far as I know, it is an
option.

I now understand why the ID (4.9) states that a nonce is inadequate
as an authentication of a map reply message.  There needs to be
either a digital signature which the ITR can use to be sure the
reply came from an ETR which is authoritative for the mapping of
this EID address, since a nonce from the ITR is sent out with
multicast to multiple ETRs.   This seems to require an overly
elaborate PKI arrangement, with the ITR having to send other packets
and get responses before it could be sure that the mapping
information it received could be trusted.  Even if this cost could
be contemplated, the delays would add up and in many cases, there
would be no point in the ITR forwarding the packet by the time it
could be sure the mapping information was valid.  Both the
LISP-EMACS network and any PKI system would be global in geographic
spread, so the delays would often be quite long.

I think any one of these problems:

   Packet amplification in multicast => inefficiency and DoS

   Delays and costs in authenticating map reply messages.

   Authenticating requests to join multicast groups => PKI.

   Generally global size of LISP-EMACS network leading to excessive
   costs and delays. (Likewise LISP-CONS' CAR-CDR network.)

   ETRs snooping on traffic packets sent to other end-user's
   networks.

are severe enough to make the EMACS proposal unworkable.
Nonetheless, I think it is worth tossing these ideas about - they
might lead to something better.

You refer to Snooping in 4.6.  Some kind of "Join Filter" would be
required to ensure only ETRs which were authoritative for the
relevant EID space could join the multicast group.  This seems to
require a large overhead of looking up some centralised system by
which the authority is delegated, perhaps with crypto to secure it.
 I am not sure how the authority is physically verified in LISP anyway.

Ivip has a comparable problem in ensuring that an attacker can't
inject bogus packets into the "Replicator" steam of mapping data
which is fanned out to ITRDs and QSCs.

Even if you did have reliable "Join Filters", this wouldn't solve
the problem of snooping.

Any "owner" of EID space within the range which is covered by a
single multicast group will be able to snoop on some of the initial
packets in communication flows to other networks which use the same
group.

This seems to be a fundamental limitation of LISP-EMACS.  I think
that alone would be sufficient for almost all end-users to regard it
as unacceptable.

I am not sure about how LISP-EMACS would scale to IPv6.  With IPv4,
about 24 bits are "in play" between the MSB of the address space and
the LSB of the currently used smallest end-user address assignment.
 I think LISP or any other ITR-ETR scheme should be used to slice
address space finer - to individual IP addresses in principle, and
certainly to /28 and /30.

This means there would be up to 32 IPv4 bits "in play".  Your
current proposal uses the most significant 16 of these to split this
space into 2^16 (actually 224 * 256 = 57344) multicast groups.  My
modification above splits the space into 16 times this number of
multicast groups.

I am not sure how small a micronet an ITR-ETR scheme should support
in IPv6.  PI /48s are currently being handed out, so I guess it
would be desirable to have something finer.  Ideally, to /64 would
be good, but for the sake of this discussion, lets say to /52.

Although, at present, a few most significant bits in IPv6 are
relatively fixed, this "52 bits in play" is a much more challenging
situation for LISP-EMACS than IPv4's 32 bits.

LISP-EMACS needs to split the "in play" bits into two categories:

  1 - Most significant bits - which set the number of multicast
      groups.  This is limited by multicast address space (I guess
      not much of a problem in the IPv6 overlay network) and by
      whatever administrative costs there are in running this number
      of groups.

  2 - The least significant bits, which - depending on how densely
      populated that region of the address space is, in terms of
      end-user networks with unique ETRs - determines how many
      ETRs each packet is multicast to.

I haven't thought much about IPv6 in general for Ivip, so I am not
saying my proposal has no scaling challenges with it, but I think
that a more fully developed LISP-EMACS proposal should contemplate
how the greater number of IPv6 "in play" bits would be split.

  - Robin