Subject: Re: [rrg] NERD

From: [email-masked] (Noel Chiappa)
Date: Tue, 17 Nov 2009 10:04:06 -0500 (EST)

> From: Florin Coras <[email-masked]>

    > Wouldn't it be better to have ITRs store the Map-Servers .. instead of
    > the mappings?

I'm not sure it would buy you that much, because you're still facing a
minimum of an RTT to the/an authoritative mapping-server, to get a new copy
of the mapping.

I'm not sure how much larger the response-time would be if one went through
the full mapping cycle (i.e. starting from scratch), but _iff_ speed-of-light
delays are the primary component (as they are today, with the minimal
processing delays in the switches), then if the path through the resolution
hierarchy (since any resolution system other than 'every mapping server has
the entire mapping table' is going to be organized as a hierarchy) is not
_too_ far off from the optimal path to the authoritative mapping-server,
the single direct RTT should not be that much less.

On top of that, there's a bit more complexity, because you also have to deal
with the situation where the cached mapping-server is no longer the
authoritative mapping-server for that identifier.

It would be interesting to know if anyone has measured RTTs from any deployed
mapping systems, to see if my total guess (in the paragraph above) about
'stretch' in the mapping system is correct.

	Noel

---

From: Florin Coras <[email-masked]>
Date: Wed, 18 Nov 2009 00:48:56 +0100

Hello Noel,

Sorry for the lengthy reply! Hope it proves useful.
You can find some results that we presented at the IETF 75 meeting in
Stockholm this summer, regarding the delay to obtaining a mapping from
an ITR standpoint,  here: www.ietf.org/proceedings/75/slides/lisp-4.pdf
.  Unfortunately these are not measured but are obtained through
simulation over an Internet measured topology, because there is no
*large* deployment of a mapping system, at least as far as I know. The
figure you are looking for is on page 7. I would be happy to answer any
other question regarding our experiment or provide other results.

It doesn't show well there (because of the scale) but there are cases
when ALT offers a delay comparable to the one way delay from the ITR to
the ETR. Unfortunately in 90% of the cases the stretch factor (ALT/RTT)
is higher than 1.

So to answer your statement, based on these results, I think NERD does a
better job at minimizing the delay to obtaining a mapping. But I don't
know if it would scale to a global mapping system so that is why I
suggested it could be used for inter AS traffic engineering (the second
level of LISP, that makes use of private mapping database between the
AS-es).

A NERD version that caches Map-Servers can offer mobility support (not
useful in above mentioned case) because all the mobile nodes now have a
fixed "rooted" point in the global RLOC Internet, the Map-Server (this
is in fact the idea behind LISP-MN). This also addresses churn and/or
problems due to old versions of the NERD database at ITRs (Map-Servers
are not likely to change often). The drawback for this improved NERD is
that it can't forward the first packet at line speed ( this might be
against the purpose for which Eliot built it ). Nonetheless you
mentioned that there is an increase in complexity when the authoritative
Map-Server changes. Isn't this an issue with all mapping systems? Why do
you think the situation is worse for NERD?

Thanks,
Florin

Noel Chiappa wrote:
> _______________________________________________
> rrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/rrg
>

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 17 Nov 2009 16:00:46 -0800

> level of LISP, that makes use of private mapping database between the

So I am wondering what people think. Is there a hybrid that we can use?

That is, for NERD it is all or nothing. But a typical ITR needs some  
but not all mappings.

How about this:

(1) Have an ITR, when it boots up, ask its map-resolver for all  
mappings it might have cached.
(2) It may not eliminate all Map-Requests but maybe a large number of  
them.
(3) Does require the map-resolver to be a caching system.

Comments?

Dino

---

From: Robin Whittle <[email-masked]>
Date: Wed, 18 Nov 2009 13:40:00 +1100

Short version:    Dino suggested altering LISP ALT so the Map
                  Resolvers fully cache all the mapping they
                  request.  He also suggested each ITR download
                  a copy of its MR's cache at boot time.

                  This only provides marginal improvements over
                  LISP-ALT or LISP-CONS, since there still needs
                  to be a global query server system, which is
                  slow and unreliable.  This means that some
                  initial packets will still be dropped or be
                  delayed for so long that they are useless or
                  worse than useless when they arrive.

                  Making these MRs (which are local to the ITRs
                  they serve) full database would solve the
                  show-stopper problems of LISP-NERD and of
                  LISP-CONS or LISP-ALT.  There would be no
                  need for a CONS or ALT network and there would
                  be no problem with dropped or delayed initial
                  packets.   The scaling problems of NERD would
                  be eliminated.

                  The result - LISP with full-database MRs -
                  would resemble APT.

                  By distributing mapping updates to the MRs
                  in real time, the system would somewhat
                  resemble Ivip.  In such a system the ITRs
                  and ETRs can be much simpler, and the
                  mapping information simpler and more compact
                  since there is no need for the ITRs, or MRs,
                  to choose between different ETR addresses.
                  The end-user network itself would be
                  responsible for making this choice in real
                  time, which makes the system much more flexible
                  and better able to handle outages according
                  to the actual circumstances.  The end-user
                  networks would typically contract a specialised
                  company to probe ETR reachability and control
                  the mapping of their EIDs accordingly.

                  (A potential disadvantage of this over LISP
                  or APT is that LISP or APT may be able to
                  cope better with a situation where each ETR
                  is reachable from only a subset of the Net.)

Hi Dino,

In the NERD thread, you wrote:

> How about this:
> 
> (1) Have an ITR, when it boots up, ask its map-resolver for all mappings
>     it might have cached.
> (2) It may not eliminate all Map-Requests but maybe a large number of them.

Assuming that you are making these changes to LISP-ALT (or LISP-CONS)
this doesn't alter the fact that the Map-Resolvers (MRs) rely on a
mapping distribution system which is distributed and global - and
therefore complex, slow and unreliable.

It is reasonable to assume that each ITR will be quite close to its
one or more MRs.  So these are *local* MRs - local query servers.  In
this setting, there's no need for ITRs to cache any more mapping
information than they need for the packets they are handling, since
they are close enough to their one or more local MRs to be able to
get any mapping which is already cached in the MR within a few tens
of milliseconds.

I think it is fair to assume that holding an initial packet for a few
tens of milliseconds, probably up to 100 ms or so, will not cause
significant impact on any known protocol other than perhaps ping and
traceroute when compared to today's IDR system.  Assuming the source
and destination hosts are both on EID addresses, it would cause a
one-off extension in ping time for the first ping packet and probably
too for the ICMP packet which it generates.  Traceroute would take a
little longer assuming the source was on an EID address, and assuming
the routers were not.

If you take LISP-NERD and:

   Add caching MRs.
   Make the ITRs caching instead of full database.

then the result in no way resembles NERD.

If you take LISP-CONS or LISP-ALT or whatever and:

   Add caching MRs.

then you arguably still have CONS or ALT or whatever.

To this, you could have three kinds of ITR behaviour:

   A - Cache only the mapping needed by the ITR's
       traffic.

   B - (As you suggested) have the ITR cache the full
       contents of its (one or more?) MR's caches at
       boot time, and then cache only the mapping it
       needs for its traffic.

   C - Constantly receive updates from the MR, so the
       ITR's cache contents are identical to the MR's.

In A and B, the ITR still needs to query the MR for mapping it
doesn't have.  Its just that in the case of B, by storing a finite
amount of mapping at boot time (presumably mapping which is more
likely to be used by the ITR than would be a the average for the
whole mapping database) you would reduce the need for the ITR to
query the local MR.  However, this requires a large transfer of
information to each ITR at boot time, which is arguably more trouble
than it is worth.

With C, the ITR generally makes less requests to the MR, since it
is kept up to date with the MR's full mapping cache, which is a
function of the activities of all the ITRs which use this MR.  So as
with B, you reduce the number of ITR to MR requests, at the expense
of a large flow of mapping updates to each ITR, which must all be
stored - and most of those mapping updates will be of no use to a
single ITR.

In all these cases, A, B or C, you have created either:

   ALT with caching MRs.

   NERD with the full database internal query server of each
   NERD ITR replaced by a caching query server which relies on a
   local caching MR.

In all these cases, you still have ALT's global query server system
and you still have delayed or dropped initial packets.  You will have
fewer delayed or dropped initial packets than the current ALT system,
in which MRs do not cache.  However, you will still have this problem
- I think to a degree which makes such a scheme a non-starter for
voluntary adoption.

The performance differences between A, B and C are inconsequential, I
think, since all three will enable the ITR to send any packet within
a few tens of milliseconds, as long as the MR has the mapping cached.

The greater MR -> ITR mapping traffic options of B and C only reduce
this short delay time.  I think A is just as good, since the MR is
close to the ITRs and the system A ITR can quickly and reliably query
the MR.  B and C reduce the amount of query traffic each MR handles,
but require the MRs to pump out their full mapping database: B to
each ITR at its boot time and C at this time, and with a continual
stream of updates to each ITR as well.

Compared to ordinary ALT, the only substantial benefits you gain by
introducing caching MRs with systems A, B or C, are:

  1 - When an ITR X requires mapping for an EID which the MR has,
      it gets it in a few tens of milliseconds from the local MR.

      This only occurs due to another ITR which the MR serves having
      requested mapping for this EID within the caching time.

  2 - To the extent that this does occur, this reduces load on the
      ALT network and its Map Servers.

  3 - To the extent this does occur, it essentially eliminates the
      lost or unusably delayed initial packet problem.

However, these benefits only occur when another ITR served by this MR
has recently requested mapping for this EID.

Here is another approach: full database MRs for LISP:

You can take your proposal and make the MRs full database.  Or you
can take NERD, take the full database query server out of each ITR
and replace it with a caching query server.  The caching query server
talks to one or more full database MRs.

Each such MR has the same storage and mapping update traffic
requirements as a single NERD ITR, but it serves the needs of many
(dozens to thousands?) of ITRs, which are now caching ITRs.   (Of
course, you could co-locate a full database MR in an ITR, and so make
this device serve multiple nearby caching ITRs too.)

As I wrote here:

  Re: NERD - comparison with other schemes
  http://www.ietf.org/mail-archive/web/rrg/current/msg05281.html

The LISP mapping systems occupy two extremes of a spectrum of answers
to the question: "How many devices store the full mapping database?".

On one end is NERD: "Hundreds of thousands or millions - every ITR."

On the other end, CONS and ALT: "None."

Making LISP MRs full database is the most obvious enhancement to NERD
since it fixes NERD's primary problem of poor scaling with large
mapping databases.

A full-database MR version of LISP should probably have a name
different from NERD.

A full-database MR version of LISP has nothing to do with CONS or
ALT, since there would be no need for the CONS or ALT networks.  All
that is needed is a way the MRs can get their mapping information.
NERD does this, for each ITR, by downloading updates from one or more
centralised or somewhat centralised servers, such as by HTTP.

A full-database MR version of LISP would be a vast improvement on
NERD, CONS or ALT.

It would eliminate the primary objection to NERD - bad scaling.  It
would eliminate the primary objections to CONS and ALT:

  1 - Dropped or delayed initial packets.

  2 - The need for a global query server network, which is inherently
      slow, unreliable and costly.

This approach to LISP would resemble APT.

My understanding is that APT distributes its mapping to all its local
full database query servers (Default Mappers - DMs) via the data
percolating around between the DMs in all the ISPs which form an "APT
cloud".  This is a set of ISPs which share physical links, since the
data is percolated around on the back of a BGP system (either the
main BGP system or a similar one, just for APT updates - I can't
recall exactly how).

I have suggested APT be altered to allow tunneled links between ISPs
for the purpose of distributing mapping updates.  This would mean all
ISPs would be part of a single "APT cloud".  This would enable APT to
reliably handle EIDs spanning less IP addresses than the 256 IP
address granularity of today's IPv4 BGP system (which I assume is
unlikely to be reduced).

By keeping NERD's ITR/MR initiated HTTP download system, you would
avoid the relatively slow, fully distributed, nature of APT's mapping
distribution system and replace it with a somewhat centralised, much
simpler, arrangement where a limited number of servers, or
distributed systems of servers, are the authoritative source of all
mapping information.

This approach to LISP, like APT, would still require the mapping to
contain multiple ETR addresses so the individual ITRs (or DMs in APT,
which actually make the decision of which ETR to use) still need to
figure out for themselves which ETR to use when one of them becomes
unreachable.

You could simplify the mapping data, reducing it to a single ETR
address, by taking this decision process out of the ITRs (or for APT,
out of the DMs) and by making the decision a real-time responsibility
for the end-user network whose EID this is.

To do this, you would need to have an essentially real-time (a few
seconds, for instance) mapping distribution system, with the updates
going to all the full-database MRs (or for APT, DMs).  The end-user
network would probably contract out the real-time control of its
mapping to a specialised company, with a robust network, since at the
time you most need the mapping changes, the end-user network's
network is likely to be suffering connectivity problems.

Ivip is one way of doing this - local full-database query servers
with real-time mapping distribution and so much simpler ITRs and
ETRs, since the ITRs don't need to make any decisions about which ETR
to use.

The major distinctions between NERD, APT, Ivip and LISP-ALT are
listed at:

  http://www.firstpr.com.au/ip/ivip/comp/

  - Robin

---

From: Eliot Lear <[email-masked]>
Date: Wed, 18 Nov 2009 15:09:31 +0100

Dino,

> That is, for NERD it is all or nothing. But a typical ITR needs some 

I didn't really think of NERD as an all or nothing solution.  In fact, 
one could easily envision use of NERD for some notion of "local" or 
"popular", and use of ALT for The Rest.  For instance, I could envision 
a Chinese NERD that would be distributed in the China region, and ALT 
used for the rest.  Some understanding of traffic flows would be useful 
in determining this sort of thing.

> (3) Does require the map-resolver to be a caching system.

It sounds VERY good so long as cache expiration semantics are maintained 
– that is, when a refresh timer goes off, no matter where the entry is, 
it gets refreshed.  It may also make sense that when a caching resolver 
is dumping its cache, it reduce by a random epsilon the refresh time of 
each entry so as to avoid synchronization problems.

But help me on two points:

What is the difference between the ITR asking a map-resolver for all 
mappings and the map-resolver being co-resident?

Would it be possible for the map-resolver to itself pre-cache entries 
that it has some reason to believe would be "interesting"?

Regards,

Eliot

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 19 Nov 2009 00:31:15 -0800

> mappings and the map-resolver being co-resident?

(1) The ITR may be a family of products from different vendors. Some  
may be memory challenged.
(2) Those ITRs can fate share each other's destinations.
(3) The map-resolver could be a larger/higher performing device that  
is monetized by an
     infrastructure provider rather than be resident at a client site.

> Would it be possible for the map-resolver to itself pre-cache  
> entries that it has some reason to believe would be "interesting"?

Sure.

Dino